EE 122 1st Term Exam

Date: October 9, 2002

Name:

SID:

ee122 login:

Day/Time of section you attend:

Problem / Points
1 / /10
2 / /10
3 / /20
4 / /20
5 / /20
6 / /20
Total / /100
  1. Question 1 (10 pt)

Use no more than three sentences to answer the questions below:

(a)State the “end-to-end arguments”. (4 pt)

(b)Error detection techniques detect corrupt bits. Give an example of an error that can be detected by the transport layer that the link layer cannot. (3 pt)

(c)Given that the transport layer can detect errors that the data link layer cannot, why would you implement error detection in the lower layers? (3 pt)

Solution:

(a) A lower layer should not implement functionality that can be correctly and completely implemented only by a higher layer. The only exception is when partial functionality in a lower layer optimizes performance significantly, and doesn't adversely affect applications at the higher layer that do not require this functionality.
(b) The transport layer can detect errors that occur after a packet has passed the data link layer. For example, a packet can be corrupted in the buffer or the switching backplane of a router.
Another example is when a stronger error detection technique is used at the transport layer. Since the transport layer is implemented only at end-hosts and not on every router along the path, typically more computational resources are available at the transport layer.
Note: You have to give an example that some how involves corrupt bits. If you talk about lost or out-of-order packets, you receive partial credit only.
(c) Implementing error detection at a lower layer can improve performance. The transport layer can only detect errors at the destination, and hence the packet with the error is carried over the entire path wasting bandwidth. The retransmission has to be done over the entire path too.
Another example is that different data link layer technologies have different error characteristics, so a high error rate technology (wireless) can have strong error detection, while a low error rate technology (optical) can have weak error detection. We can thus avoid the overhead of having strong error detection over the entire path.

  1. Question (10 pt)

Compare packet switching and circuit switching using the following criteria: (a) forwarding cost, (b) bandwidth utilization, and (c) ability to handle resource reservations. Briefly explain your reasoning.

Solution:

(a) Packet switching has a higher per-packet forwarding cost because

  • The router has to examine (and possibly rewrite) the header of every packet it forwards.
  • The router has to maintain routing tables which may have a large number of entries.
  • The router needs to do a longest prefix matching for every packet,

The per-packet forwarding cost is much lower in circuit switching once the connection has been established.
(b) In packet switching, different users use statistical multiplexing to share the bandwidth on any link. In the absence of congestion and packet drops, no bandwidth is wasted and the utilization is typically high.
In circuit switching, bandwidth may be wasted if an established connection is idle. For applications with a high peak to average sending rate ratio, this wastage can be high.
(c) Circuit switching inherently requires resources to be reserved for a particular connection. On the other hand, in packet switching the bandwidth available to a particular user (flow) depends on the sending rate of other flows. We need additional scheduling mechanisms at the router to support reservations to a particular flow.

  1. Question (20 pt)

We want to transfer a file of size d bits. Each link has bandwidth b bps and fixed delay f sec. All the routers on the path are store-and-forward. We use packets of size p bits, which includes headers of size h bits. We always pad the last packet so that it is full. There is no setup time for the transfer. Packets are sent continuously and are not lost. There is no queueing delay and processing overhead.

(a)How many packets are sent? (5 pt)

(b)What is the delay to transfer the file across one link? (5 pt)

(c)What is the delay for one packet to arrive at a destination n links away? (5 pt)

(d)What is the delay to transfer the file across n links? (5 pt)

Solution:

(a)You have to send all of your data, only p – h of your data fits in a packet, and you have to round up because the last packet may not be full, so the number of packets is .

(b)


(c)



(d)

Alternatively, you can think about it as
(this simplifies to the same as above)

  1. Question (20 pt)

Assume two end-hosts communicate using the sliding window protocol. Assume the receiver window is always smaller than the sender’s window and the size of the receiver window is w bits. Let C be the link capacity between the two end-hosts in bps, and RTT be the roundtrip time between the two end-hosts in sec. What is the maximum throughput achieved by the two end-hosts?

Note: Assume every bit is acknowledged.

Answer: There are two cases (see figure below)

case a: RTT > w/C, throughput = w/RTT

case b: RTT <= w/C, throughput = C

  1. Question (20 pt)

Consider the network below. Assume that the network implements the Distance Vector routing protocol.

(a) Assume that the routing protocol has converged. Write down the routing table of each node. (5 pt)

(b) Assume the cost of the link between nodes A and B increases from 1 to 3. Write down the routing table of each node at every step until routing tables converge. Assume that both A and B see that the change of the link (A, B)’s cost at the same time, and that exchanges of routing information and routing table updates are synchronous (i.e., they happen at the same time at all nodes) (5 pt)

(c) Assume the cost of the link between nodes A and B increases from 1 to 50. How many iterations does it take the routing protocol to converge? (5 pt)

(d) Give one solution to reduce the number of iterations at point (c). Explain. (5 pt)

a) See first row below

b) See the last three rows below

c) There are 20 iterations (i.e., the second highest cost of a link). See below:

Note: Full credit was awarded for only specifying the number of iterations. Also we gave full credit to students that were slightly off in estimating the number of iterations, e.g., 19, 21.

d) Poisoned reverse: a node sends to its neighbor the route learnt from that node with a cost of infinity.

  1. Question (20 pt)

Consider a wireless network consisting of n nodes where nodes are placed on a line at the coordinates 0, d, 2*d, …, (n-1)*d. Assume the range of transmission of each node is d + e, where 0 < ed, and that n is even.

(a) What is the maximum number of packets that can be simultaneously transmitted in such a network? (10 pt)

(b) What is the maximum number of packets that can be simultaneously transmitted in a network with n2 nodes arranged in an n x n matrix, where the distance between any two nodes on both the x and y axis is d? (10 pt)

For full credit it is enough to give an example that achieves the maximum number of transmitted packets for each case. There is a 10 points bonus if you prove that your examples indeed achieve the maximum number of transmitted packets in all cases.

Note: A node cannot send and receive at the same time, and a node cannot receive if it is within the transmission range of two or more senders.

Solution:

(a) The maximum number of packets is n/2; see the example below. Each arrow represents a packet that is transmitted from the sender to the receiver. Note that two neighbor nodes can send successfully two packets as long as the receivers are at a distance larger than d + e

(b) There are two possible cases:

(b.1) ; the maximum number of packets is n2/2 (see example below)

(b.2) ; the maximum number of packets is n2/3 (see example below)

Proof (for bonus points):

(a) Let S be the number of senders that successfully send a packet, and let R be the number of receivers that successfully receive a packet. Since a node cannot send and receive at the same time, it follows that S + R <= n. Finally, for each successfully transmitted packet there is exactly one sender and one receiver, it follows that the maximum number of transmitted packets is at most n/2.

(b.1) Same as (a).

(b.2) Let S be the number of senders, R the number of receivers, and I the number of idle nodes, i.e., a node that can neither send nor receive a packet. The crux of the proof is to show that we can associate an idle node with each pair of nodes that communicate. Since transmitting one packet involves exactly one sender and one receiver, the total number of transmitted packets is min(S, R). Since according to the above statement we have min(S, R) <= I, and by definition I + S + R = n2, it follows that min(S,R) <= n2/3.

To prove that we can associate with each transmission an idle node, we define a simple rule: To each pair of nodes (A, B) that communicate we associate node C that is a neighbor of both A and B. Ties are broken according to the lowest y-coordinate first, and then according to the lowest x-coordinate. The following figure shows all possible cases.

Note two things. First, node C can neither send nor receive other packets than the one exchanged between A and B. This holds true irrespective of which is the sender, i.e., A or B. Second, a node C cannot be associated to more than one transmission (this can be easily verified by taking case by case).