Maseno University

• SCS 30

• 1 Introduction to Internet 1.1 W&P, P1.1 2 Points. How many hosts can one have on the Internet if each one needs a distinct IP address? [Solution] Since the IP(v4) address is 4-byte, there can potentially be 232 distinct addresses. 1.2 Adapted from W&P, P1.3 8 Points. Imagine that all routers have 17 ports. There are 216 hosts to be connected. Assume you can organize the hosts and routers any way you like. Your goal is to (i) design the network structure so as to minimize the number of routers required, and (ii) based on the network design in (i), assign the addresses to minimize the size (number of entries) of the routing table required in each router. (a) 4 Points. Describe your network structure and explain why your design gives the minimum number of routers. (b) 4 Points. Describe your scheme for assigning addresses and routing. Explain why your design gives the minimum routing table size in each router. There exist theoretical lower bounds on the number of routers and the size of the routing table. Point out these lower bounds explicitly in your solution, and use them to verify your design. [Solution] The routers will be arranged in a tree topology, with each of 16 of the ports representing the next half-byte in the network address. The 17th port would be the link to the parent router. The root router would have a dead 17th port, and so there would be a routing table of size 16 on the first router, and 17 on every other router. This would be of the form: • (prefix, halfbyte, unmatched) routes to the port indexed by halfbyte, where prefix is the total specified address on the parent router that points to this router on its 17th port; • default route goes to port 17; • the root router is just: (halfbyte, unmatched) routes to the port indexed by halfbyte. The total number of routers we use is 212 + 28 + 24 + 20 = 4369. This is optimal because: (a) Consider all the routers and hosts as vertex and links as edge. Then in the result graph, it should be a tree, otherwise we can further remove edges and/or vertexes to simplify the graph. Assume we 1 have N routers. For each router, we have 17 ports. For each host, we have 1 port. The total number of edges should be no less than the total number of vertex minus 1, which is (N + 216 − 1) to provide connectivity. Also we have the number of edges should be no larger than half of the total ports, which is (17N + 216)/2. Hence we have (17N + 216)/2 ≥ (N + 216 − 1), so N ≥ 4368.9. (b) The routing table at every router except the root has only 17 entries, which is minimum with a router fanout of 17. 1.3 W&P, P1.4 3 Points. Assume that a host A in Berkeley sends packets with a bit rate of 100Mbps to a host B in Boston. Assume also that it takes 130ms for the first acknowledgment to come back after A sends the first packet. Say that A sends one packet of 1Kbyte and then waits for an acknowledgment before sending the next packet, and so on. What is the long-term average bit rate of the connection? Assume now that A sends N packets before it waits for the first acknowledgment. Express the long-term average bit rate of the connection as a function of N. [Note: 1 Mbps = 106 bits per second; 1 ms = 1 millisecond = 10−3 second.] [Solution] It takes 1KB/100Mbps = 0.08ms to transmit one packet. When N = 1, the connection transfers 1 packet per RTT, i.e., 1KB per 130.08ms ∼ 130ms. This represents a throughput of 1KB/0.13s = 61.5 kbps. (If you use 1KB = 1,024 bits instead of 1,000 bits, then the throughput will be 63 kbps.) It is OK to ignore the packet transmission time (0.08ms) since it is order of magnitude smaller than the propagation delay of 130ms. When N is small enough (see below), the sender sends N packets, and then stops and waits for the first ACK which arrives after one RTT of 130.08ms ∼ 130ms. Therefore the throughput is N KB/130ms = 61.5N kbps. Let K be the largest integer such that K 1 KB 100Mbps ≤ 130.08 ms, i.e., K = 1, 626. When N ≥ K, the sender would have already received the first ACK when it fini