cse123A Computer Networks Fall 99 Final ------------------------------------------- Thursday, December 16, 3pm to 5pm CENTER 212 ANSWER KEY ----------- Name:(please print) ucsd id No. Answer all questions. Exam is closed book. Write your answers in the space indicated and provided for with each question. Write legibly. Avoid Overwriting. Write with pen only. Do not write on the reverse side. Keep rough work separate and do not submit it. Rough work not evaluated. For rough work separate blank sheets are provided. Q. No. marks Q.No. marks Q.No. marks Q.No. marks -------------- ------------- ------------- ------------ 1 5 10 1 20 1 30 2 2 3 11 4 21 2 31 10 3 9 12 6 22 2 32 4 4 5 13 2 23 1 33 2 5 3 14 2 24 1+2 34 3 6a 1 15 2 25 1 6b 2 16 2 26 3 7 15 17 2 27 3 8 1 18 1 28 1 9 2 19 2 29 1 ---------------------------------------------------------------------- Total (out of 109) : PAGE 1 (there are 17 pages - PAGE 1 to PAGE 17) -------------------------------------------------------------------------- Question 1: A large population of Aloha users manage to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40 msec. What is the expected number of transmission attempts needed? Answer: G, the average number of transmissions per slot, is 2. Expected number of transmission attempts is e**G (page 250 in text book) which calculates to 7.4 --------------------------------------------------------------------------- Question 2: If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full duplex) line is taken by the distributed routing algorithm? Assume each router has three lines to other routers. Answer: The routing table is 50 x 8 = 400 bits. This information is sent twice a second on each link each way. So 800 bps are consumed on each link in each direction. --------------------------------------------------------------------------- Question 3: A datagram subnet allows routers to drop packets whenever they need to. The probability of a router discarding a packet is p. Consider the case of a source host connected to source router, which is connected to the destination router, and then to the destination host. If either of the routers discards a packet, the source host eventually times out and tries again. If both host-router and router-router lines are counted as hops, what is the mean number of (a) hops a packet makes per transmission? (b) transmissions a packet makes? (c) hops required per received packet? Answer: (a) Each packet may make 1, 2 or 3 hops. For 1 hop, the first router drops it and the probability is p. For 2 hops, it goes through first router but not the second and the probability is (1-p)p. For 3 hops, it goes through both routers and the probability is (1-p)(1-p). Mean hops per transmission is given by 1 x p + 2 x (1-p)p + 3 x (1-p)(1-p) which simplifies to p**2 - 3p +3 (b) The probability of successful transmission all the way is (1-p)**2 Let us denote it by w. The average number of transmissions per packet is given by w + 2w(1-w) + 3w(1-w)**2 + + nw(1-w)**(n-1) + .... which reduces to 1/w, that is, 1/(1-p)**2 (c) mean hops per packet = mean hops per transmission x mean number of transmissions which is ( pxp - 3p + 3 ) / ((1-p) x (1-p)) -------------------------------------------------------------------------- Question 4: z bits of data are to be transmitted over a k-hop path in a packet-switched network as a series of packets, each containing p data bits and h header bits. Assume z>>p+h. The line speed is b bits per sec and the propagation delay is negligible. What value of p minimizes the total transmission time for the data? Answer: The total number of packets needed is z/p. The total of data+header works out to (p+h)z/p bits. The source takes (p+h)z/(pb) sec to transmit this. The forwarding of the last packet by intermediate routers on the way takes up (k-1)(p+h)/b sec. Adding up the two gives the time to clear the full pipe (that is, from start at source of the first bit of first packet to move out till the receipt of the last bit of the last packet at the destination). Total time = (p+h)z/(pb) + (p+h)(k-1)/b. Minimize with respect to p by differentiating with respect to p, setting to zero and solving for p, we get p = sqrt((hz/(k-1)) --------------------------------------------------------------------------- Question 5: Three packet-switching networks each contain N nodes. The first is star topology with a central router, the second is a bidirectional ring, and the third is fully interconnected (every node is connected to every other). What are the best, average and worst case tranmission paths in hops for each of the above networks? Answer: star - 2, 2, 2 hops (best, average, worst) ring - 1, N/4, N/2 full - 1, 1, 1 --------------------------------------------------------------------------- Question 6: (a). The following data fragment occurs in the middle of a data stream using character stuffing for frames. DLE STX A DLE B DLE ETX What is the output after stuffing? Answer: DLE STX A DLE DLE B DLE ETX 7 5 (b). What is the remainder obtained by dividing x + x + 1 3 by x + 1 ? 2 Answer: x + x + 1 --------------------------------------------------------------------------- Question 7: For the network described in the table, give the routing table for each of the nodes A, B, C, D, E, F. Shortest path (Dijkstra's)routing is used. Link table of the network: Router A A B C C D Router C D E E F E cost 3 8 2 1 6 2 Answer: Fill in the following table. Each entry is (hop, total distance) If hop itself is destination mark it as *. To: A B C D E F -------------------------------------- From A - C,6 *,3 C,6 C,4 C,9 B E,6 - E,3 E,4 *,2 E,9 C *,3 E,3 - E,3 *,1 *,6 D E,6 E,4 E,3 - *,2 E,9 E C,4 *,2 *,1 *,2 - C,7 F C,9 C,9 *,6 C,9 C,7 - --------------------------------------------------------------------------- Question 8: Give an example of a 4-bit error that will not be detected by two dimensional parity. You may use the following as a hint. 0 1 0 1 0 0 1 |1 | 1 1 0 1 0 0 1 |0 | 1 0 1 1 1 1 0 |1 | 0 0 0 1 1 1 0 |1 | 0 1 1 0 1 0 0 |1 | 1 0 1 1 1 1 1 |0 | ---------------| | 1 1 1 1 0 1 1 |0 <----- column parity bits Answer: invert any 4 bits which lie on the corners of a rectangle. --------------------------------------------------------------------------- Question 9: A network with four routers A, B, C, D uses Distance Vector Routing. The distance table for the router A is < 0 1 4 100>. Router A receives from B the vector < 1 0 1 1 >. Show the updated distance table for router A. Answer: < 0 1 2 2 > --------------------------------------------------------------------------- Question 10: To provide more reliability than what single parity bit can give, an error detecting code uses one parity bit for the odd numbered bits of a message and a second parity bit for the even numbered bits of the message. What is the Hamming distance of this code? Answer: 2 --------------------------------------------------------------------------- Question 11: Identify the class of each of the following IP addresses. (a) 128.36.199.3 (b) 21.12.240.17 (c) 183.194.76.253 (d) 200.3.6.2 Answer: (a) class B (b) class A (c) class B (d) class C --------------------------------------------------------------------------- Question 12: Frames of 1000 bits are sent over a 1 Mbps satellite channel - propagation delay of 270 msec. Acks are always piggybacked. Headers are very short. Three bit sequence numbers are used. What is the maximum achievable channel utilization in frames per sec for (a) stop-and-wait protocol (b) protocol with go-back-n and (c) protocol with selective-repeat ? Answer: At 1Mbps, 1000 bits take 1 msec (neglect headers). The round trip time for a frame is 1+270++270+1 = 542 msec. (till ack is received by the sender). (a) channel utilization is 1 frame in 542 msec = 1.85 frames per sec (b) pipeline 7 frames (3 bit seq number) with roundtrip of 548 msec giving channel utilization 7/548 = 12.77 frames per sec (c) pipeline 4 frames ( window size is sequence-size /2 ) in 545 msec giving channel utilization 4/545 = 7.34 frames per sec --------------------------------------------------------------------------- Question 13: In wired LANs, all stations can monitor the medium and detect collisions, but not so in a wireless LAN. What are the two problems this gives rise to in wireless LANs called? Answer: i) hidden Station (ii) exposed station. --------------------------------------------------------------------------- Question 14: In binary exponential backoff scheme to deal with collisions, after k consecutive collisions, how long does a colliding station wait before attempting transmission? Answer: for a random time chosen from the interval [ 0, T x 2**k ], where T is the worst case round trip propagation time for the channel. --------------------------------------------------------------------------- Question 15: In MACA (Multiple Access, Collision Avoidance) in wireless LANs, what happens if two stations send an RTS (Request to send) at the same time? Answer: If the RTSs do not collide, the two senders will both receive CTS and go ahead. If the RTSs collide, they will not get CTS and will have to try again using some randomised backoff. --------------------------------------------------------------------------- Question 16: What is does a station, say, A do when it hears an RTS in MACA? Answer: If the RTS is for it, it sends a CTS. Otherwise, it pauses for time sufficient for a CTS to go to the sender (from some one else). --------------------------------------------------------------------------- Question 17: In datagram service, routing table is looked up for every incoming datagram to a router. In virtual circuit service, packets are forwarded using the VCI - virtual circuit index - by routers. Do we need routing tables for virtual circuit service? Answer: Yes - for establishing connection (virtual circuit) from source to destination. --------------------------------------------------------------------------- Question 18: Why are large networks (communication subnet of routers) organized hierarchically? Answer: To keep size of routing tables small/manageable and to reduce the time to compute routing tables. --------------------------------------------------------------------------- Question 19: State one advantage and one disadvantage of source-routing. Answer: Advantage - smaller routing tables in routers; routers need not exchange information and compute routing tables. Disadvantage - increased size of packets (to carry route information); static (non-adaptive) routing. [any one for each of Advantage/Disadvantage will do]. --------------------------------------------------------------------------- Question 20: In link-state routing, how many lsps (link-state-packets) does a router create for broadcasing to other routers? Answer: one for each link that the router has. --------------------------------------------------------------------------- Question 21: When is it a good idea to use hop count as a criterion for routing? Answer: In a homogeneous network (like link-characteristics) with uniformly distributed load. --------------------------------------------------------------------------- Question 22: Tokens are added every 0.5 secs to a token bucket of capacity 500 bytes. Each token is 100 bytes in size. (a) If a packet of size 400 bytes arrives from the host when the bucket has tokens worth 200 bytes, and there are no other packets queued for service, what is the least and most waiting the packet will face before transmission? Answer: The packet needs 2 more tokens - (400-200)/100. If it arrives just when a token is about to arrive, it waits 0.5 sec - the least. Most waiting is 1.0 sec. --------------------------------------------------------------------------- Question 23: Why is multicasting more efficient than multiple unicasts? Answer: (atmost) only one copy of a packet is sent on a link. --------------------------------------------------------------------------- Question 24: In a wireless LAN, (i) sender P who may send to Q can not hear R who may also send to P. What is R called? (ii) Q sends to P and though R can send to S without collision, it defers. Why? What is R called? Answer: (i) R is a Hidden Station (from P) Note: The question should read "R who may send to Q" and not "R who may send to P" - this is a typo. Every one gets 1 mark. (ii) R hears Q (but does not know it 'll not interfere for P) and defers. R is an exposed station (exposed to Q) -------------------------------------------------------------------------- Question 25: What is the name of the protocol that translates network-layer IP address of a host to datalink-layer address? Answer: ARP (Address Resolution Protocol) --------------------------------------------------------------------------- Question 26: What are the network number, subnet number and host number for IP address 135.194,192.100 and mask 255.255.128.0 ? Answer: The IP address is class B, so the network number is 7.194 The mask selects the leftmost 17 bits which is gives just a 1-bit subnet number; the subnet number is 1. Host number is 40.100 --------------------------------------------------------------------------- Question 27: How many addresses are spanned by (that is, the maximum number of hosts in the subnet) the CIDR address 205.12.192.0 with 20 bit subnet mask 255.255.240.0 ? What is the range spanned (give the low and high host addresses)? Answer: With a 20 bit subnet mask, the number of hosts is spanned by 12 bits, giving 4096 hosts. The range is 205.12.192.0 to 205.12.255.255 --------------------------------------------------------------------------- Question 28: Reverse path forwarding for broadcast eliminates duplicate packets of the same broadcast reaching nodes - True or False? Answer: False --------------------------------------------------------------------------- Question 29: What is the name of the technique used to reduce the size of routing tables and the time for computing them? Answer: Hierarchical structuring of network (routers/host addresses) --------------------------------------------------------------------------- Question 30: Why does the Offset field in the IP header specify the offset in 8-byte units? Answer: The offset field is 13-bits long and an IP packet can have maximum 65536 bytes length (2**16). Possible values for offset are 0 to 65535 in bytes and only with 8-byte units, this range can be specified in 13 bits. --------------------------------------------------------------------------- Question 31: A router has built up its routing table as given. The router can deliver packets directly over interfaces 0 and 1, or can forward to routers R2, R3 or R4. What does the router do with each of the packets (a) to (e) it receives? Routing Table: SubnetNumber SubnetMask NextHop 128.96.39.0 255.255.255.128 Interface 0 128.96.39.128 255.255.255.128 Interface 1 128.96.40.0 255.255.255.128 R2 194.4.153.0 255.255.255.192 R3 default R4 The destinations of the packets received are: (a) 128.96.39.10 (b) 128.96.40.12 (c) 128.96.40.151 (d) 192.4.153.17 (e) 192.4.153.90 Answer: The router masks the destination address of packet with SubnetMask and matches with SubnetNumber and accordingly sends the packet corresponding to the matching entry in routing table. For no match, the packet is sent to the default router. (a) on Interface 0 to the host (using ARP) (b) to R2 (c) to default router R4 (d) to default router R4 (e) to default router R4 --------------------------------------------------------------------------- Question 32: Differentiate between flow control and congestion control. Answer: Flow control is to establish good rate between sender and receiver to ensure that sender is not too fast or too slow with respect to reciver. Congestion control is to regulate the load from host into the network to eliminate the situation that the network is unable to handle the traffic. --------------------------------------------------------------------------- Question 33: In token ring, what is token holding time? What purpose does it serve? Answer: Token holding time is the maximum time a station can use the token (when it gets a free token) after which it must put out a free token for other stations on the ring. It ensures that no station can monopolise the token for long periods resulting in unbounded delays for other stations wanting to transmit. --------------------------------------------------------------------------- Question 34: Name three functions of monitor in a token ring which make the token ring robust. Answer: Detecting and resolving (i) duplicate tokens -eliminate (ii) lost tokens - regenerate (iii) continuously busy token (transmitting station crash) (iv) clearing the ring of garbled frames (v) taking action when ring breaks [any three will do]. ------------------------------------------------------------------------------- END OF ANSWER KEY ------------------------------------------------------------------------------