Cis 307 Midterm 2

Front 1

State and explain Amdhal's Law.

Back 1

Amdhal has suggested that any computation can be analyzed in terms of a portion that must be executed sequentially, Ts, and a portion that can be executed in parallel, Tp. Then
T(n) = Ts + Tp/n
This is known as Amdhal's Law.

Front 2

What is Little's Law?

Back 2

Little's Law applies to the single server queueing system. It is the equation:
N = a * T
where:
N is the number of jobs in the queueing system
a is the arrival rate (the number of jobs that arrive to the system per unit of time), and
T is the Response or TurnAround Time for a job (total time from arrival to departure from the system).
For example, if at the supermarket I notice that a teller has always 4 customer and that customers arrive every 2 minutes, then I know that customers, on average will be in line for 8 minutes.

Front 3

We have been using the files csapp.c csapp.h in our homeworks.
In there we find the function
ssize_t rio_readn(int fd, void *usrbuf, size_t n)
to robustly read (i.e. coping with interruptions due to
signals and with the system policies for returning from read)
from fd n bytes into usrbuf. It returns the number of
bytes actually read, or -1 in case of read error. Implement
this function.

Back 3

ssize_t rio_readn(int fd, void *usrbuf, size_t n)
{
size_t nleft = n;
ssize_t nread;
char *bufp = usrbuf;

while (nleft > 0) {
if ((nread = read(fd, bufp, nleft)) < 0) {
if (errno == EINTR) /* interrupted by sig handler return */
nread = 0; /* and call read() again */
else
return -1; /* errno set by read() */
}
else if (nread == 0)
break; /* EOF */
nleft -= nread;
bufp += nread;
}
return (n - nleft); /* return >= 0 */
}

Front 4

When we communicate on a data link we want to detect
errors that have occurred in transmission. Describe
one method of error detection.

Back 4

t

Front 5

You have heard the terms: Error Detection, Error Correction,
Error Recovery. Explain these terms and indicate a technique
used to carry them out.

Back 5

h

Front 6

few facts about Ethernet:
(1) What does CSMA/CD stand for?
(2) What is Exponential Backoff?
(3) How big is an Ethernet address (in bits)?
(4) How big is the largets Ethernet packet (in bytes)?

Back 6

c

Front 7

Ethernet uses a CSMA/CD protocol to share the
communication channel. The size of a frame
in the 10Mbps Ethernet is between 64 and 1518 bytes.
How do you think they came up with such sizes?

Back 7

c

Front 8

What is a Router and how it differs from a Bridge?

Back 8

A router is a box (often a regular computer) with (at least) two ports (i.e. interfaces), used to connect possibly dissimilar networks and help packets go from a source to a destination. It differs from bridges since it operates at the network level.

Front 9

Describe the data structure kept at a router and the algorithm
used to forward to the next router a packet with destination D.

Back 9

d

Front 10

Describe what is the Backward Learning Algorithm (for
Learning or Adaptive Bridges) and how it operates.

Back 10

d

Front 11

You know about IP addresses.
(a) Can a computer have more than one IP address?
and if so how?
(b) How many IP addresses are there (IP version 4,
the only one we discussed)?
(c) What is the structure of an IP address?
(d) Is the IP address like the Ethernet address
stored in the hardware or is it a software
concept?
(e) What is a subnet mask?

Back 11

r

Front 12

What is a routing table and how is it used to route
a packet to the next node.

Back 12

j

Front 13

What is the difference between Routing Algorithms and Routing
Protocols? Name at least one routing algorithm and one routing
protocol.

Back 13

r

Front 14

In an IP header we find (among others) the following fields:
Identification, Fragment-Offset, Time-To-Live, Flags.
Indicate what are their purposes.

Back 14

f

Front 15

Describe the OSI Model. Be as detailed as you can within
our constraints of time

Back 15

v

Front 16

In a homework you have used interprocess communication with
sockets. Explain in detail the following two statements:
(a) s = socket(AF_INET, SOCK_DGRAM, 0);
(b) y = htonl(x);

Back 16

f

Front 17

What is the Internet?

Back 17

f

Front 18

Here are various statements about the Transmission
Control Protocol. For each statement, indicate if true or false.
(1) It is connection oriented.
(2) It is message oriented.
(3) It is stream oriented.
(4) It is Best-Effort.
(5) It is Half-Duplex
(6) It is a Session Layer protocol.
(7) Between two computers at one time there can
only be one TCP session.
(8) It uses piggy-backed acknowledgements.
(9) It supports up to 256 ports.
(10) It is used to implement the IP protocol.

Back 18

f

Front 19

We are using CIDR routing. An ISP owns 6 class C networks, 200.77.0/24,
200.77.1/24, 200.77.2/24, 200.77.3/24, 200.77.4/24, 200.77.5/24.
Another ISP owns 200.77.6/24 and 200.77.7/24.
A. What mask will be used for the first ISP?
B. What mask will be used for the second ISP?
C. Which route will be selected for the address 200.77.6.15 and why.

Back 19

f

Front 20

I am at home with my PC. I have a modem. I have an ISP.
Describe as well as you can how with my browser I reach
the Yahoo web server. In your explanation try to identify
things like, local loop, POP, ISP, Autonomous System, NAP,
internal and external routing.

Back 20

f

Front 21

What two main activities does a router do?

Back 21

Forwarding (or Switching): The process taking place at a router when it receives a packet and has to decide where to send it next on the basis of its destination and of information available at the router. And
Routing: The process through which routers receive and elaborate the information that they will need in the forwarding process. Usually this information is gathered and transmitted using protocols called routing protocols, and elaborated using algorithms. And usually the gathered information takes the form of routing (or forwarding) tables.

Front 22

What three types of routing/forwarding/switching take place?

Back 22

Source Routing, where the decision on what intermediate nodes to cross is made before a packet is sent; then the packet knows from the beginning where to go next after arriving at an intermediate node.
Virtual Circuit Routing, where a connection is established before the first packet is sent. Then each packet as it travels will contain as destination the id of a virtual circuit (this id may change as the packet moves across the network) and each intermediate node will contain a table with 4 entries, an entry-port, an entry-virtual-circuit-id, an exit-port, and an exit-virtual-circuit-id. Routing at a node determines the port the packed arrived from and its virtual circuit, then it will send the packet forward with the exit virtual circuit id as new destination and using the exit port as indicated by the table.
[Packet] Routing, where each packet is individually routed in accordance to a next-hop routing table. In these tables, for a given destination, there is usually a single next-hop. Even when there are more than one next-hop, the decision on where to go next is not done on the basis of source of the packet, but on the basis of some form of cost

Front 23

What are routing tables and what do they contain?

Back 23

Routing tables contain information that will indicate for each packet on the basis of its final destination (usually an IP address) where to go next (next-hop forwarding - the address of the next router). If there is no explicit indication of how to get to some destination, a default next-hop will be used

Front 24

What two portions does a IP address consist of?

Back 24

Network Identifier and Host identifier

Front 25

What does a subnet mask do?

Back 25

The subnet mask is what differentiates the network ID and the host ID for a given TCP/IP address

Front 26

What are routing protocols?

Back 26

ROUTING PROTOCOLS are the software that allow routers to dynamically advertise and learn routes, determine which routes are available and which are the most efficient routes to a destination. (Ex. RIP, RIP II, OSPF, IGRP, EIGRP)

Front 27

What are routed protocols?

Back 27

ROUTED PROTOCOLS are nothing more than data being transported across the networks. Routed protocols include:(ex. Internet Protocol
Telnet
Remote Procedure Call (RPC))

Front 28

What is subnetting?

Back 28

Applying a subnet mask to an IP address allows you to identify the network and node parts of the address.

Front 29

What is supernetting?

Back 29

Supernetting, also called Classless Inter-Domain Routing (CIDR), is a way to aggregate multiple Internet addresses of the same class

Front 30

h

Back 30

g

Front 31

What is framing problem?

Back 31

In general the problem of recognizing start and end of a packet

Front 32

what is error detection?

Back 32

Error detection is a form of error control.

Front 33

describe three methods that allow the receiver to detect errors.

Back 33

Parity bits
Check sums - faster
Cyclic Redundancy Checks (CRC) Best method

Front 34

What is forward error recovery?

Back 34

By using redundancy (i.e. transmitting in addition to the data a number of extra bits], it is possible to not only detect but also recover from certain kinds of errors without need of retransmission. Forward Error Recovery used to be called just Error Correction.

Front 35

What is ARQ? Name the three methods.

Back 35

Automatic repeat request

Stop-and-Wait: a transmitter after sending a frame waits for a message (ACK/NACK) back from receiver indicating if the previous frame was or not received correctly. If not, the frame is retransmitted.
Go-Back_N: Now frames are numbered and the transmitter is allowed to send a number of frames (up to N) without waiting for acknowledgement ( Sliding Window Protocol), but when the receiver sends a "NACK i" to indicate an error with frame i, then frame i and all its transmitted successors are retransmitted.
Selective-Repeat: Similar to Go-Back-N, but now for the response "NACK i" only frame i is retransmitted.

Front 36

what is fragmentation problem?

Back 36

One message at a layer may have to be fragmented over multiple messages at a lower layer. A layer may be able to accept messages of length N, but the implementation of the layer in terms of a protocol at the layer below may accept only messages of length M, with M < N. Thus the original layer must be able to fragment the original message into a number of messages at the lower level. These fragment may then be sent across different routes and the receiver will have to worry about missing fragments, incorrect received order, in recombining them into the correct received message. This problem occurs in particular between the network layer (IP protocol) and the data link layer, where the IP packet needs to be split into a number of fragments. Maximum Segment Size (MSS) is the minimum maximum size of the segments used at different layers in a connection (so if at a layer the maximum segment is 4096 bytes and at another it is 1500, then the MSS is 1500).

Front 37

What is flow control?

Back 37

How do we make sure we don't send too much information to the receiver so that it cannot handle it and has to "drop it on the floor"; it is normally managed by the receiver that informs the sender about how much data it is ready to accept;

Front 38

How do we make sure that we don't have too many messages trying to get into a communication channel. Thus causing delays and perhaps lost packets;

Back 38

managed by the sender and possibly the router

Front 39

What is multiplexing?

Back 39

How a single communication channel can be shared for more than one conversation;

Front 40

How do interlocutors address each other [host interfaces are known by their IP address (a 32 bit integer);

Back 40

This handled by the ARP (Address Resolution Protocol)