Max / 25 / 10 / 20 / 10 / 20 / 15 / 100
Pts
EECS 122 - COMMUNICATION NETWORKS - SPRING 2002
Midterm – March 21, 2002
1 Multiple Choice (25%)
[You lose credits if you select an incorrect statement or do not select a correct statement. Select by putting a cross to the left of the statement. E.g., to mark statement A(d) you out a cross to the left of (d):
X (d) Routers…] Note. By “router” we mean “Internet router.”
A. Overview and Layers [select correct statements, if any] (5%)
(a) DNS maps a name into an IP address
(b) Virtual circuit switching is more efficient than packet switching for infrequent short communications
(c) Routers maintain a soft state about end-to-end connections
(d) Routers see an Ethernet as a single hop
(e) In the Internet, the link layer generally provides a reliable packet transmission
B. Physical Layer [select correct statements, if any] (6%)
(a) Self-clocking codes are required by TDM, not by statistical multiplexing
(b) The Shannon channel capacity of a fast Ethernet link (in one direction) is 100Mbps
(c) A signal with a maximum frequency of 1kHz can be reconstructed exactly from samples measured every 2 milliseconds
(d) Ignoring the queuing delay, it takes approximately 0.5ms to send a 1000-bit packet over 100km of fiber with a transmitter at 1Gbps
(e) Assuming that a link corrupts bits independently of one another with probability 10-6, the probability that a 10-kbit packet is corrupted is about 10%.
(f) Manchester encoding is self-clocking
C. Link Layer [select correct statements, if any] (4%)
(a) HDLC is a technique to control packet transmission errors
(b) TDM is possible only with bit streams that have precisely known rates
(c) FDM cannot be used to send packets
(d) Ethernet can be used without CSMA/CD
D. Ethernet [select correct statements, if any] (5%)
(a) An Ethernet switch sends collision detection signals
(b) A switch has a higher throughput than a hub because simultaneous transmissions are possible on each link
(c) The spanning tree algorithm is a link state algorithm
(d) When sending a packet on a bridged Ethernet, a host finds the MAC address of the first bridge using ARP
(e) One reason why a bridged Ethernet does not scale is that the rate of collisions increases as one bridges more Ethernets
E. Network Layer [select correct statements, if any] (5%)
(a) A link state algorithm requires fewer message exchanges than a distance vector algorithm. (Assume no topology change. We consider the messages until the algorithm converges.)
(b) A path vector algorithm does not face the count-to-infinity problem of a distance vector algorithm
(c) A host finds out if another host is on the same subnet by comparing the MAC addresses
(d) In multicast, reverse path broadcasting computes the shortest path from the receiver to the source using either a distance vector or a link state algorithm
(e) In PIM-SM (protocol independent multicast – sparse mode), the RPB tree is truncated by “prune” messages
2 Problem (10%)
In the figure below, cs and ee are Ethernet LANs; e1- e6 are Ethernet(MAC) addresses for each hosts; mingus.cs, dns.cs, mail.ee , and cory.ee are hostnames. R1 and R2 are routers and their IP addresses are 128.32.32.1 and 128.32.33.1. The host dns.cs is the domain name server for both the cs and ee networks. The IP addresses of the hosts are shown in the figure. The link between R1 and R2 is an unnumbered point-to-point link.
Computer mingus.cs sends a packet to computer cory.ee.
Our notation for an Ethernet packet is as follows:
[ ED | ES | IPS | IPD | data ]
where ED is the Ethernet address of the destination of the Ethernet packet, ES is the Ethernet address of the source of the Ethernet packet, IPS is the IP address of the source of the IP packet, IPD is the IP address of the destination of the IP packet.
For example, if cory.ee wants to send a packet to mail.ee assuming that it knows the IP address 128.32.33.3 of mail.ee, there would be two steps:
1. cory.ee gets the Ethernet address(e6) of 128.32.33.3 using ARP
2. cory.ee sends [e6 |e5 | 128.32.33.2 | 128.32.33.3 |data] to mail.ee
Question. Assume that computer mingus.cs knows only the name of computer cory.ee. R1 and R2 have never seen any packet. List the steps needed for mingus.cs to send the packet to cory.ee, in their chronological order.
Answer:
[all | e2 | 128.32.32.3 | all | who is 128.32.32.2?] – ARP request for dns.ee from mingus.ee
[e2 | e1 | 128.32.32.2 | 128.32.32.3 | I am] - ARP reply
[e1 | e2 | 128.32.32.3 | 128.32.32.2 | what is the IP address of cory.ee?] dns request
[e2 | e1 | 128.32.32.2 | 128.32.32.3 | IP address of cory.ee = 128.32.32.2] dns reply
[all | e2 | 128.32.32.3 | all | who is 128.32.32.1?] – ARP request for R1 from mingus.ee
[e2 | e3 | 128.32.32.1 | 128.32.32.3 | I am] – ARP reply
[e3 | e2 | 128.32.32.3 | 128.32.33.2 | data]
[128.32.32.3 | 128.32.33.2 | data] on link from from R1 to R2 {We assume that the routing tables are set up.}
[all | e4 | All | 128.32.33.1 | who is 128.32.33.2] ARP request
[e4 | e5 | 128.32.33.2 | 128.32.33.1 | I am ] ARP reply
[e5 | e4 | 128.32.32.3 | 128.32.33.2 | data]
3 Problem (20%)
In the graph below, the links lengths are shown in the figure. (The links are bi-directional and have the same length in both directions.)
a) Use Dijkstra's algorithm to find the tree of shortest paths from A to all the destinations. Your task is to indicate the list of labels of all the nodes at the successive steps of the algorithm. Initially, all the labels are 'infinity: Y', except the label of node A that is 0. Put a star (*) next to the label of a node whose children have been explored. For instance, label 2* for node D means that at the current step of the algorithm the shortest path from A to D has length 2 and all the children of D have been examined from node D. At each step, the algorithm examines all the neighbors of one node.
(Each column corresponds to one step of the algorithm.)
A / 0* / 0* / 0* / 0* / 0* / 0*
B / 5 / 5 / 5 / 5 / 5* / 5*
C / ¥ / ¥ / ¥ / 9 / 6 / 6*
D / 2 / 2* / 2* / 2* / 2* / 2*
E / 3 / 3 / 3* / 3* / 3* / 3*
F / ¥ / 5 / 4 / 4* / 4* / 4*
b) Using distance vector. Assume the cost of link between nodes E and F increase from 1 to 6. Write down the forwarding table entry for node f at each node(A,…,F) at each step. The first entry corresponds to the converged state before change in the link state. Assume that exchanges of routing information and routing table updates are synchronous (i.e., they happen at the same time at all nodes). We assume a simple version of DV (no split horizon).
Before increase(Distance/next hop) / 1 / 2 / 3 / 4 / 5
A to F / 4, E / 4, E / 5, D / 5, D / 5, D
B to F / 3, E / 3, E / 5, C / 5, C / 6, C
C to F / 4, B / 4, B / 4, B / 5, F / 5, F
D to F / 3, F / 3, F / 3, F / 3, F / 3, F
E to F / 1, F / 5, B / 5, B / 6, B / 6, D
4 Problem (10%)
Consider the arrangement of learning bridges shown in the following figure. Assuming all are initially empty, give the forwarding table (station caches) for each of the bridges B1- B2 after the following transmissions: (1) B sends to C; (2) D sends to B; (3) E sends to F.
Solution:
1. After B sends to C:
Bridge B1
Destination / Port numberB / 1
Bridge B2
Destination / Port numberB / 2
2. After D sends to B:
Bridge B1
Destination / Port numberB / 1
D / 2
Bridge B2
Destination / Port numberB / 2
D / 2
3. After E sends to F:
Bridge B1
Destination / Port numberB / 1
D / 2
E / 1
Bridge B2
Destination / Port numberB / 2
D / 2
E / 1
5 Problem (20%)
Consider the following setup:
Each link has the following characteristics: propagation delay a and bandwidth b. Data packets are k-bit long. A sends the next packet as soon as it gets the ACK for the previous packet from B. [This is the stop-and-wait protocol.] Assume ACK time (time it takes to transmit and propagate ACKs) is negligible.
A transmits down path1 with probability p and down path2 with probability 1-p. What is the effective bandwidth between A and B. Here, effective bandwidth is defined as the average (i.e., mean or expected value of the) rate at which A sends bits to B.
Answer
A sends a packet of k bits to B
With probability p, the packet takes 2(k/b + a) seconds to reach B and for an ACK to get back to A.
With probability 1 - p, the packet takes 3(k/b + a) seconds to reach B and for an ACK to get back to A.
Accordingly, the average time to transmit a packet of k bits is
p2(k/b + a) + (1 – p) 3(k/b + a) = (3 – p) (k/b + a).
It follows that A sends bits to B with the average rate
k/[(3 – p) (k/b + a)].
6 5. Problem (15%)
a) We would like to transmit the following bit string:
“0110101100111”
In order to detect errors that may occur during transmission, we would like to add CRC bits. If the CRC generator polynomial is x3 + 1, then what are the CRC bits that need to be appended to the bit string?
b) Assume that a code allows you to detect at most t errors. Using this code, can you also correct those t errors? Explain your answer.
Answers:
a) We perform the long division of 0110101100111000 by 1001: The remainder is 000.
b) No. For instance, if the code has a distance of t + 1, it can detect up to t errors. Indeed, since two codewords have a Hamming distance at least equal to t + 1, a codeword cannot be transformed into another codeword by t or fewer errors. However, t errors may transform a codeword C into a word W that is closer to another codeword C’ than C. Indeed, the distance between C’ and W may be as small as 1. In that case, the decoder would mistakenly try to correct W as C’ whereas C was the transmitted word.