Untitled Document EECS 489 Fall 1999 Mid-term Exam Name\SSN: ___________________________\ ___________ (Please print) HONOR CODE: I have neither given nor received help from the sources disallowed in this exam. Sign your name here:____________________________________________ This is an 80-minute midterm exam. You are allowed to see a one-page note but not anything else. There are 7 large questions with a total of 118 points on 9 pages. Write clearly answers and all your work in the space provided. State any assumptions you make when you solve a problem. Good luck! 1 2 3 4 5 6 7 Total /118 1. Socket Programming 1.1 (3 points) Why would a socket be created with a wild card for a foreign destination? When creating a socket for a server, it is not known in advance who is going to connect. A wild card is given as the foreign destination to allow any host to connect. 1.2 (3 points) True or False: Justify your answer. It impossible for two TCP/IP sockets on host A, both bound to the same local IP address and local port number, to communicate with two different hosts B and C respectively. False. It is possible to have have two different sockets with the same local port and IP address if the destination port and IP address's are different. 1.3 (3 points) What happens if time-out=0 in the select (maxfd, inputset, outputset, exceptionset, timeout)? Two answers were accepted. If the time-out pointer is NULL then the select function blocks indefinitely. If the time-out structure is not NULL but has a value of zero seconds the function returns immediately. This last case would be polling. 2. Big Endian (6 points) Write a function to discover if a computer is big endian or not. The function should return non-zero if the computer is big endian and zero otherwise. The function cannot make any system calls. Explain and comment your code and logic to be eligible for partial credit if the function does not work. Hint: The function can be written in a couple of lines with a few type casts. /*
* Return non-zero if the computer is a big endian machine.
* cIsBigEndian must not make any system calls.
*
*/
char
cIsBigEndian(void)
{
short s = 0xFF00; char * c = (char *)(&s); return *c;
} 3. Fragmentation and Reassembly 3.1 (5 points) Why does knowledge of the network MTU yield better utilization of network bandwidth? Please accompany your explanation with an example. Packets will not be fragmented if the MTU is known. No fragments means less overhead which means better utilization of network bandwidth. 3.2 (4 points) Give two reasons why an intermediate router isn't allowed to reassemble fragments. Fragments may not all arrive at the same router. Reassembled packet may be fragmented again. Would take up too much time. The router is supposed to be dumb. 3.3 (3 points) Most IP datagram reassembly algorithms have a timer to avoid having a lost fragment tie up reassembly buffers forever. Suppose a datagram is divided into four fragments. The first three segments arrive, but the last one is delayed. Eventually the timer goes off and the three fragments in he receiver's buffer are discarded. A little later, the last segment stumbles in. What should be done with it? Toss it. Even if we don' toss it there is no guarantee that it will be fragmented in a way as to make the saved fragment useful. 3.4 (4 points) What is the minimum network MTU required to send an IP datagram that contains at least one octet of data? 21 or 24 if you added padding. 4. Naming and Addressing 4.1 (4 points) If you choose the record-route option, what limits the maximum number of hops can you record? The header length field in the IPv4 header is 4 bits. Hence only 2^4 words - 1 = 15 words. 16 - 5 (the minimum header size) = 10 4.2 The following figure shows a zoning partition of the DNS domain hierarchy. The square boxes represent zones, while the rounded ovals represent hosts. 4.2.1 (3 points) Assuming all nameserver caches started out empty, list, in order, the name servers contacted when thumper.telcordia.com tries to resolve xor.engin.umich.edu. thumper > telcordia; telcordia > root; telcordia > umich/eecs; telcordia > engin; 4.2.2 (3 points) After the above resolution, list, in order, the name servers contacted when thumper.telcordia.com tries to resolve and.engin.umich.edu. thumper > telcordia; telcordia > engin; 4.2.3 (3 points) After the above two resolutions, list, in order, the name servers contacted when thumper.telcordia.com tries to resolve teton.eecs.umich.edu. thumper > telcordia; telcordia > umich/eecs; 4.2.4 (3 points) After the above three resolutions, list, in order, the name servers contacted when nor.engin.umich.edu tries to resolve bambi.telcordia.com. nor > engin > root > telcordia 5. RIP, Routing Loops, Split-horizon & Path-hold-down (15 points) The "split-horizon" routing heuristic, when used alone, is not sufficient to prevent all routing loops. Show this by constructing a network topology and a sequence of events such that a routing loop will be created if only the "split-horizon" heuristic is used but will not be created if both "split-horizon" and "path hold down" (with a period of 1) are used. Every link in the network should must have a cost of 1. When the routing loop is created in the "split-horizon-only" case, a set of routers S will be "counting to infinity" for a destination D. For both "split-horizon-only" and "split-horizon with path hold down" show the to D in the routing tables of each router in S. Stop listing entries when the routes to D converge or when a router's distance to D reaches 6. Topology Sequence of Events 6. Link State, Path Computation & Hierarchical Routing 6.1 (15 points) Showall steps in applying Djikstra's Shortest Path First (SPF) to the network topology given below. Permanent Temporary Comments A(A,0) B(A,10), D(A,30), E(A,40) Root and its neighbors A(A,0), B(A, 10) C(B, 60), D(A, 30), E(A, 40) A(A,0), B(A, 10), D(A, 30) C(D, 45), E(D, 35) A(A,0), B(A, 10), D(A, 30), E(D, 35) C(D, 45) A(A,0), B(A, 10), C(D, 45), D(A, 30), E(D, 35) Done 6.2 (6 points) When is a link state packet (LSP) with sequence number A older than an LSP with sequence number B in the lollipop sequence space? Assume the sequence numbers are signed 32 bit numbers. A < B <= 0; A < 0 <= B; 0 < A < B & (B - A < N / 4); 0 < B < A & (A - B > N / 4); 6.3 (4 points) Give one advantage and one disadvantage of setting the link state packet (LSP) age large. If the LSP age (i.e. cache lifetime) is large then the frequency of updates to refresh the caches is lower thus making better use of network bandwidth. This is an advantage. However if the lollipop sequence is not used and a router is rebooted it does not know what sequence number to start with. Hence it needs to wait for all the others to time out before it can begin to send updates. If the cache lifetime is large then the start up time of a rebooted router is longer. That is a disadvantage. 6.4 (8 points) For hierarchical routing with 4800 routers, what region/area and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? Suppose there are B big areas containing M middle areas containing S small areas containing R routers. Each area has a router designated as its representative. All traffic into this area passes through this router. All traffic out of this area passes through this router to a pier area. If you can imagine this then the routers with the most entries are the representatives to the big areas (which are also representatives to their respective medium and small areas). They would have (B - 1) + (M - 1) + (B - 1) entries or approximately B + M + S entries. Thus B * M * S = 4800. Now we want to minimize B + M + S subject to B * M * S = 4800. Minimum occurs when B = M = S = (4800)^(1/3) approx.. 16 or 17. 7. CIDR, Subnetting, IPv6, and multicast 7.1 (6 points) How many addresses are spanned by the CIDR address 205.12.192.0 with a mask of 0xFFFFF000? And what are the lowest and highest address? 2^12 = 4096 addresses are spanned. Lowest address: 205.12.192.0; Highest address: 205.12.207.255 7.2 (3 points) Give one main reason why multicast group membership is not kept track of by anyone. Keeping track of this information would result in too much overhead; membership information is constantly changing. 7.3 A new Silicon Valley startup would like to acquire network space for 2040 hosts. 7.3.1 (2 points) Under CIDR, how many contiguous class C addresses would this request necessitate? 8 contiguous class C networks are required. 7.3.2 (2 points) What would the appropriate netmask be? 255.255.248.0 7.3.3 (2 points) Assume that this network has been assigned a base address of 196.150.56.0, and that a packet destined for address 196.150.60.101 arrives at its main router. Is the packet accepted? Yes, this packet is accepted. 7.4 For the multicast LAN shown below 7.4.1 (4 points) The router R needs to know the existence of one host interested in a particular multicast group without knowing all hosts which are interested in the multicast group. How is this fact exploited in IGMP (Internet Group Management Protocol) to reduce the traffic overhead associated with IGMP Query -- Reply over the LAN ? The router will send an IGMP query to every host on its LAN; each host will set a random timer, and the first host whose timer expires will reply. Upon hearing an IGMP reply, each host will cancel its timer. This prevents R from being flooded with IGMP reply. 7.4.2 (4 points) When all hosts on the LAN have left a particular multicast group, what does the router R do? R will send a message to its parent, pruning itself from the multicast session.
