Chapter 4

In this question, we consider some of the pros and cons of virtual-circuit and datagram networks. a. Suppose that routers were subjected to conditions that might cause them to fail fairly often. Would this argue in favor of a VC or datagram architecture? Why? b. Suppose that a source node and a destination require that a fixed amount of capacity always be available at all routers on the path between the source and destination node, for the exclusive use of traffic flowing between this source and destination node. Would this argue in favor of a VC or datagram architecture? Why? c. Suppose that the links and routers in the network never fail and that routing paths used between all source/destination pairs remains constant. In this scenario, does a VC or datagram architecture have more control traffic overhead? Why?

Let's review some of the terminology used in this textbook. Recall that the name of a transport-layer packet is segment and that the name of a link-layer packet is frame. What is the name of a network-layer packet? Recall that both routers and link-layer switches are called packet switches. What is the fundamental difference between a router and link-layer switch? Recall that we use the term routers for both datagram networks and VC networks.

Consider a virtual-circuit network. Suppose the VC number is an 8-bit field. a. What is the maximum number of virtual circuits that can be carried over a link? b. Suppose a central node determines paths and VC numbers at connection setup. Suppose the same VC number is used on each link along the VC's path. Describe how the central node might determine the VC number at connection setup. Is it possible that there are fewer VCs in progress than the maximum as determined in part (a) yet there is no common free VC number? c. Suppose that different VC numbers are permitted in each link along a VC's path. During connection setup, after an end-to-end path is determined, describe how the links can choose their VC numbers and configure their forwarding tables in a decentralized manner, without reliance on a central node.

What are the two most important network-layer functions in a datagram network? What are the three most important network-layer functions in a virtualcircuit network?

A bare-bones forwarding table in a VC network has four columns. What is the meaning of the values in each of these columns? A bare-bones forwarding table in a datagram network has two columns. What is the meaning of the values in each of these columns?

What are the two most important network-layer functions in a datagram network? What are the three most important network-layer functions in a virtualcircuit network?

Do the routers in both datagram networks and virtual-circuit networks use forwarding tables? If so, describe the forwarding tables for both classes of networks.

Describe some hypothetical services that the network layer can provide to a single packet. Do the same for a flow of packets. Are any of your hypothetical services provided by the Internet's network layer? Are any provided by ATM's CBR service model? Are any provided by ATM's ABR service model?

List some applications that would benefit from ATM's CBR service model.

Suppose two packets arrive to two different input ports of a router at exactly the same time. Also suppose there are no other packets anywhere in the router. a. Suppose the two packets are to be forwarded to two different output ports. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses a shared bus? b. Suppose the two packets are to be forwarded to two different output ports. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses a crossbar? c. Suppose the two packets are to be forwarded to the same output port. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses a crossbar?

Discuss why each input port in a high-speed router stores a shadow copy of the forwarding table.

Describe how packet loss can occur at input ports. Describe how packet loss at input ports can be eliminated (without using infinite buffers).

Describe how packet loss can occur at output ports. Can this loss be prevented by increasing the switch fabric speed?

Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: \begin{tabular}{cc} \hline Prefix Match & Interface \\ \hline 00 & 0 \\ 010 & 1 \\ 011 & 2 \\ 10 & 2 \\ 11 & 3 \\ \hline \end{tabular} For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range.

Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: \begin{tabular}{cc} \hline Prefix Match & Interface \\ \hline 1 & 0 \\ 10 & 1 \\ 111 & 2 \\ otherwise & 3 \\ \hline \end{tabular} For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range.

Do routers have IP addresses? If so, how many?

Consider a router that interconnects three subnets: Subnet 1, Subnet 2, and Subnet 3. Suppose all of the interfaces in each of these three subnets are required to have the prefix \(223.1 .17 / 24\). Also suppose that Subnet 1 is required to support at least 60 interfaces, Subnet 2 is to support at least 90 interfaces, and Subnet 3 is to support at least 12 interfaces. Provide three network addresses (of the form a.b.c.d/x) that satisfy these constraints.

What is the 32 -bit binary equivalent of the IP address \(223.1 .3 .27 ?\)

Suppose there are three routers between a source host and a destination host. Ignoring fragmentation, an IP datagram sent from the source host to the destination host will travel over how many interfaces? How many forwarding tables will be indexed to move the datagram from the source to the destination?

Consider a subnet with prefix \(128.119 .40 .128 / 26\). Give an example of one IP address (of form \(x x x \cdot x x x \cdot x x x \cdot x x x\) ) that can be assigned to this network. Suppose an ISP owns the block of addresses of the form \(128.119 .40 .64 / 26\). Suppose it wants to create four subnets from this block, with each block having the same number of IP addresses. What are the prefixes (of form a.b.c. \(\mathrm{d} / \mathrm{x}\) ) for the four subnets?

Use the whois service at the American Registry for Internet Numbers (http://www.arin.net/whois) to determine the IP address blocks for three universities. Can the whois services be used to determine with certainty the geographical location of a specific IP address? Use www.maxmind.com to determine the locations of the Web servers at each of these universities.

Suppose you purchase a wireless router and connect it to your cable modem. Also suppose that your ISP dynamically assigns your connected device (that is, your wireless router) one IP address. Also suppose that you have five PCs at home that use \(802.11\) to wirelessly connect to your wireless router. How are IP addresses assigned to the five PCs? Does the wireless router use NAT Why or why not?

Consider sending a 2400-byte datagram into a link that has an MTU of 700 bytes. Suppose the original datagram is stamped with the identification number 422 . How many fragments are generated? What are the values in the various fields in the IP datagram(s) generated related to fragmentation?

Compare and contrast the IPv4 and the IPv6 header fields. Do they have any fields in common?

Suppose datagrams are limited to 1,500 bytes (including header) between source Host A and destination Host B. Assuming a 20-byte IP header, how many datagrams would be required to send an MP3 consisting of 5 million bytes? Explain how you computed your answer.

It has been said that when IPv6 tunnels through IPv4 routers, IPv6 treats the IPv4 tunnels as link-layer protocols. Do you agree with this statement? Why or why not?

It has been said that when IPv6 tunnels through IPv4 routers, IPv6 treats the IPv4 tunnels as link-layer protocols. Do you agree with this statement? Why or why not?

Suppose you are interested in detecting the number of hosts behind a NAT. You observe that the IP layer stamps an identification number sequentially on each IP packet. The identification number of the first IP packet generated by a host is a random number, and the identification numbers of the subsequent IP packets are sequentially assigned. Assume all IP packets generated by hosts behind the NAT are sent to the outside world. a. Based on this observation, and assuming you can sniff all packets sent by the NAT to the outside, can you outline a simple technique that detects the number of unique hosts behind a NAT? Justify your answer. b. If the identification numbers are not sequentially assigned but randomly assigned, would your technique work? Justify your answer.

Discuss how a hierarchical organization of the Internet has made it possible to scale to millions of users.

Is it necessary that every autonomous system use the same intra-AS routing algorithm? Why or why not?

Fill in the blank: RIP advertisements typically announce the number of hop to various destinations. BGP updates, on the other hand, announce the to the various destinations.

Why are policy considerations as important for intra-AS protocols, such as OSPF and RIP, as they are for an inter-AS routing protocol like BGP?

Consider a general topology (that is, not the specific network shown above) and a synchronous version of the distance-vector algorithm. Suppose that at each iteration, a node exchanges its distance vectors with its neighbors and receives their distance vectors. Assuming that the algorithm begins with each node knowing only the costs to its immediate neighbors, what is the maximum number of iterations required before the distributed algorithm converges? Justify your answer.

Define and contrast the following terms: subnet, prefix, and \(B G P\) route.

How does BGP use the NEXT-HOP attribute? How does it use the AS-PATH attribute?

Describe how a network administrator of an upper-tier ISP can implement policy when configuring BGP.

Consider the count-to-infinity problem in the distance vector routing. Will the count-to-infinity problem occur if we decrease the cost of a link? Why? How about if we connect two nodes which do not have a link?

What is an important difference between implementing the broadcast abstraction via multiple unicasts, and a single network- (router-) supported broadcast?

Argue that for the distance-vector algorithm in Figure \(4.30\), each value in the distance vector \(D(x)\) is non-increasing and will eventually stabilize in a finite number of steps.

When a host joins a multicast group, must it change its IP address to that of the multicast group it is joining?

What are the roles played by the IGMP protocol and a wide-area multicas routing protocol?

Will a BGP router always choose the loop-free route with the shortest ASpath length? Justify your answer.

Suppose ASs \(\mathrm{X}\) and \(\mathrm{Z}\) are not directly connected but instead are connected by AS Y. Further suppose that \(\mathrm{X}\) has a peering agreement with \(\mathrm{Y}\), and that \(\mathrm{Y}\) hasa peering agreement with Z. Finally, suppose that Z wants to transit all of Y's traffic but does not want to transit X's traffic. Does BGP allow Z to implement this policy?

Consider the two basic approaches identified for achieving broadcast, unicast emulation and network-layer (i.e., router-assisted) broadcast, and suppose spanning-tree broadcast is used to achive network-layer broadcast. Consider a single sender and 32 receivers. Suppose the sender is connected to the receivers by a binary tree of routers. What is the cost of sending a broadcast packet, in the cases of unicast emulation and network-layer broadcast, for this topology? Here, each time a packet (or copy of a packet) is sent over a single link, it incurs a unit of cost. What topology for interconnecting the sender, receivers, and routers will bring the cost of unicast emulation and true network-layer broadcast as far apart as possible? You can choose as many routers as you'd like.

In Section 4.5.1 we studied Dijkstra's link-state routing algorithm for computing the unicast paths that are individually the least-cost paths from the source to all destinations. The union of these paths might be thought of as forming a least-unicast-cost path tree (or a shortest unicast path tree, if all link costs are identical). By constructing a counterexample, show that the least-cost path tree is not always the same as a minimum spanning tree.

Consider a network in which all nodes are connected to three other nodes. In a single time step, a node can receive all transmitted broadcast packets from its neighbors, duplicate the packets, and send them to all of its neighbors (except to the node that sent a given packet). At the next time step, neighboring nodes can receive, duplicate, and forward these packets, and so on. Suppose that uncontrolled flooding is used to provide broadcast in such a network. At time step \(t\), how many copies of the broadcast packet will be transmitted, assuming that during time step 1 , a single broadcast packet is transmitted by the source node to its three neighbors.

What is the size of the multicast address space? Suppose now that two multicast groups randomly choose a multicast address. What is the probability that they choose the same address? Suppose now that 1,000 multicast groups are ongoing at the same time and choose their multicast group addresses at random. What is the probability that they interfere with each other?