Chapter 4 Review Questions 1. A network-layer packet is a datagram. A router forwards a packet based on the packet’s IP (layer 3) address. A link-layer switch forwards a packet based on the packet’s MAC (layer 2) address. 2. Datagram-based network layer: forwarding; routing. Additional function of VCbased network layer: call setup. 3. Forwarding is about moving a packet from a router’s input link to the appropriate output link. Routing is about determining the end-to-routes between sources and destinations. 4. Yes, both use forwarding tables. For descriptions of the tables, see Section 4.2. 5. Single packet: guaranteed delivery; guaranteed delivery with guaranteed maximum delay. Flow of packets: in-order packet delivery; guaranteed minimal bandwidth; guaranteed maximum jitter. None of these services is provided by the Internet’s network layer. ATM’s CBR service provides both guaranteed delivery and timing. ABR does not provide any of these services. 6. Interactive live multimedia applications, such as IP telephony and video conference, could benefit from ATM CBR’s service, which maintains timing. 7. With the shadow copy, the forwarding decision is made locally, at each input port, without invoking the centralized routing processor. Such decentralized forwarding avoids creating a forwarding processing bottleneck at a single point within the router. 8. Switching via memory; switching via a bus; switching via an interconnection network 9. Packet loss occurs if queue size at the input port grows large because of slow switching fabric speed and thus exhausting router’s buffer space. It can be eliminated if the switching fabric speed is at least n times as fast as the input line speed, where n is the number of input ports. 10. Packet loss can occur if the queue size at the output port grows large because of slow outgoing line-speed. 11. HOL blocking – a queued packet in an input queue must wait for transfer through the fabric because it is blocked by another packet at the head of the line. It occurs at the input port. 12. Yes. They have one address for each interface.

13. 11011111 00000001 00000011 00011100 14. Students will get different correct answers for this question. 15. 8 interfaces; 3 forwarding tables 16. 50% overhead 17. The 8-bit protocol field in the IP datagram contains information about which transport layer protocol the destination host should pass the segment to. 18. Typically the wireless router includes a DHCP server. DHCP is used to assign IP addresses to the 5 PCs and to the router interface. Yes, the wireless router also uses NAT as it obtains only one IP address from the ISP. 19. See Section 4.4.4 20. Yes, because the entire IPv6 datagram (including header fields) is encapsulated in an IPv4 datagram 21. Link state algorithms: Computes the least-cost path between source and destination using complete, global knowledge about the network. Distance-vector routing: The calculation of the least-cost path is carried out in an iterative, distributed manner. A node only knows the neighbor to which it should forward a packet in order to reach given destination along the least-cost path, and the cost of that path from itself to the destination. 22. Routers are aggregated into autonomous systems (ASs). Within an AS, all routers run the same intra-AS routing protocol. Special gateway routers in the various ASs run the inter-autonomous system routing protocol that determines the routing paths among the ASs. The problem of scale is solved since an intra-AS router need only know about routers within its AS and the gateway router(s) in its AS. 23. No. Each AS has administrative autonomy for routing within an AS. 24. No. The advertisement tells D that it can get to z in 11 hops by way of A. However, D can already get to z by way of B in 7 hops. Therefore, there is no need to modify the entry for z in the table. If, on the other hand, the advertisement said that A were only 4 hops away from z by way of C, then D would indeed modify its forwarding table. 25. With OSPF, a router periodically broadcasts routing information to all other routers in the AS, not just to its neighboring routers. This routing information sent by a router has one entry for each of the router’s neighbors; the entry gives the distance from the router to the neighbor. A RIP advertisement sent by a router

contains information about all the networks in the AS, although this information is only sent to its neighboring routers. 26. “sequence of ASs on the routes” 27. See “Principles in Practice” on page 401 28. ISP C can use the BGP Multi-Exit Descriptor to suggest to ISP B that the preferred route to ISP D is through the east coast peering point. For example, the east coast BGP router in ISP C can advertise a route to D with an MED value of 5. The west coast router in ISP C can advertise a route to D with an MED value of 10. Since a lower value is preferred, ISP B knows that ISP C wants to receive traffic on the east coast. In practice, a router can ignore the MED value, and so ISP B can still use hot potato routing to pass traffic to ISP C destined to ISP D via the west coast peering point. 29. A subnet is a portion of a larger network; a subnet does not contain a router; its boundaries are defined by the router and host interfaces. A prefix is the network portion of a CDIRized address; it is written in the form a.b.c.d/x ; A prefix covers one or more subnets. When a router advertises a prefix across a BGP session, it includes with the prefix a number of BGP attributes. In BGP jargon, a prefix along with its attributes is a BGP route (or simply a route). 30. Routers use the AS-PATH attribute to detect and prevent looping advertisements; they also use it in choosing among multiple paths to the same prefix. The NEXTHOP attribute indicates the IP address of the first router along an advertised path (outside of the AS receiving the advertisement) to a given prefix. When configuring its forwarding table, a router uses the NEXT-HOP attribute. 31. A tier-1 ISP B may not to carry transit traffic between two other tier-1 ISPs, say A and C, with which B has peering agreements. To implement this policy, ISP B would not advertise to A routes that pass through C; and would not advertise to C routes that pass through A. 32. N-way unicast has a number of drawbacks, including: • • Efficiency: multiple copies of the same packet are sent over the same link for potentially many links; source must generate multiple copies of same packet Addressing: the source must discover the address of all the recipients

33. a) uncontrolled flooding: T; controlled flooding: T; spanning-tree: F b) uncontrolled flooding: T; controlled flooding: F; spanning-tree: F 34. False

35. IGMP is a protocol run only between the host and its first-hop multicast router. IGMP allows a host to specify (to the first-hop multicast router) the multicast group it wants to join. It is then up to the multicast router to work with other multicast routers (i.e., run a multicast routing protocol) to ensure that the data for the host-joined multicast group is routed to the appropriate last-hop router and from there to the host. 36. In a group-shared tree, all senders send their multicast traffic using the same routing tree. With source-based tree, the multicast datagrams from a given source are routed over s specific routing tree constructed for that source; thus each source may have a different source-based tree and a router may have to keep track of several source-based trees for a given multicast group.

Chapter 4 Problems
Problem 1
a) With a connection-oriented network, every router failure will involve the routing of that connection. At a minimum, this will require the router that is “upstream” from the failed router to establish a new downstream part of the path to the destination node, with all of the requisite signaling involved in setting up a path. Moreover, all of the routers on the initial path that are downstream from the failed node must take down the failed connection, with all of the requisite signaling involved to do this. With a connectionless datagram network, no signaling is required to either set up a new downstream path or take down the old downstream path. We have seen, however, that routing tables will need to be updated (e.g., either via a distance vector algorithm or a link state algorithm) to take the failed router into account. We have seen that with distance vector algorithms, this routing table change can sometimes be localized to the area near the failed router. Thus, a datagram network would be preferable. Interestingly, the design criteria that the initial ARPAnet be able to function under stressful conditions was one of the reasons that datagram architecture was chosen for this Internet ancestor. b) In order for a router to maintain an available fixed amount of capacity on the path between the source and destination node for that source-destination pair, it would need to know the characteristics of the traffic from all sessions passing through that link. That is, the router must have per-session state in the router. This is possible in a connectionoriented network, but not with a connectionless network. Thus, a connection-oriented VC network would be preferable. c) In this scenario, datagram architecture has more control traffic overhead. This is due to the various packet headers needed to route the datagrams through the network. But in VC

architecture, once all circuits are set up, they will never change. Thus, the signaling overhead is negligible over the long run.

Problem 2
a) Maximum number of VCs over a link = 28 = 256. b) The centralized node could pick any VC number which is free from the set {0,1,…,28-1}. In this manner, it is not possible that there are fewer VCs in progress than 256 without there being any common free VC number. c) Each of the links can independently allocate VC numbers from the set {0,1,…,281}. Thus, a VC will likely have a different VC number for each link along its path. Each router in the VC’s path must replace the VC number of each arriving packet with the VC number associated with the outbound link.

Problem 3
For a VC forwarding table, the columns are : Incoming Interface, Incoming VC Number, Outgoing Interface, Outgoing VC Number. For a datagram forwarding table, the columns are: Destination Address, Outgoing Interface.

Problem 4
a). Data destined to host H3 is forwarded through interface 3 Destination Address H3 Link Interface 3

b). No, because forwarding rule is only based on destination address. c). Incoming interface Incoming VC# Outgoing Interface Outgoing VC# 1 12 3 22 2 63 4 18 Note, those two flows (from H1 and H2) must have different VC#s, true for both incoming and outgoing VC#s. d). Router B. Incoming interface 1 Router C. Incoming interface 1

Incoming VC# 22

Outgoing Interface 2

Outgoing VC# 24

Incoming VC# 18

Outgoing Interface 2

Outgoing VC# 50

Router D. Incoming interface 1 2

Incoming VC# 24 50

Outgoing Interface 3 3

Outgoing VC# 70 76

Problem 5
a) No VC number can be assigned to the new VC; thus the new VC cannot be established in the network. b) Each link has two available VC numbers. There are four links. So the number of combinations is 24 = 16. One example combination is (10,00,00,10).

Problem 6
In a virtual circuit network, there is an end-to-end connection in the sense that each router along the path must maintain state for the connection; hence the terminology connection service. In a connection-oriented transport service over a connectionless network layer, such as TCP over IP, the end systems maintain connection state; however the routers have no notion of any connections; hence the terminology connection-oriented service.

Problem 7
To explain why there would be no input queuing, let’s look at a specific design. For simplicity suppose each packet is the same size. We design the switch with time division multiplexing: time is broken into frames with each frame divided into n slots, with one slot needed to switch a packet through the fabric, and with one slot per frame devoted to each input line. Since at most one packet can arrive on each input line in each frame, the switching fabric will clear all packets in each frame.

Problem 8
The minimal number of time slots needed is 3. The scheduling is as follows. Slot 1: send X in top input queue, send Y in middle input queue. Slot 2: send X in middle input queue, send Y in bottom input queue Slot 3: send Z in bottom input queue. Largest number of slots is still 3. Actually, based on the assumption that a non-empty input queue is never idle, we see that the first time slot always consists of sending X in the top input queue and Y in either middle or bottom input queue, and in the second time

slot, we can always send two more datagram, and the last datagram can be sent in third time slot. NOTE: Actually, if the first datagram in the bottom input queue is X, then the worst case would require 4 time slots.

Problem 9
a) Prefix Match 11100000 00 11100000 01000000 1110000 11100001 1 otherwise b) Link Interface 0 1 2 3 3

Prefix match for first address is 5th entry: link interface 3 Prefix match for second address is 3nd entry: link interface 2 Prefix match for third address is 4th entry: link interface 3

Problem 10
Destination Address Range 00000000 through 00111111 01000000 through 01011111 01100000 through 01111111 10000000 through 10111111 11000000 through 11111111 number of addresses for interface 0 = 2 6 = 64 number of addresses for interface 1 = 2 5 = 32 Link Interface 0

1

2

2

3

number of addresses for interface 2 = 2 6 + 2 5 = 64 + 32 = 96 number of addresses for interface 3 = 2 6 = 64

Problem 11
Destination Address Range 11000000 through (32 addresses) 11011111 10000000 through(64 addresses) 10111111 11100000 through (32 addresses) 11111111 00000000 through (128 addresses) 01111111 Link Interface

0

1

2

3

Problem 12
223.1.17.0/26 223.1.17.128/25 223.1.17.192/28

Problem 13
Destination Address 200.23.16/21 200.23.24/24 200.23.24/21 otherwise Link Interface 0 1 2 3

Problem 14
Destination Address Link Interface

11100000 00 (224.0/10) 11100000 01000000 (224.64/16) 1110000 (224/8) 11100001 1 (225.128/9) otherwise

0 1 2 3 3

Problem 15
Any IP address in range 128.119.40.128 to 128.119.40.191 Four equal size subnets: 128.119.40.64/28, 128.119.40.80/28, 128.119.40.96/28, 128.119.40.112/28

Problem 16
From 214.97.254/23, possible assignments are a) Subnet A: 214.97.255/24 (256 addresses) Subnet B: 214.97.254.0/25 - 214.97.254.0/29 (128-8 = 120 addresses) Subnet C: 214.97.254.128/25 (128 addresses) Subnet D: 214.97.254.0/31 (2 addresses) Subnet E: 214.97.254.2/31 (2 addresses) Subnet F: 214.97.254.4/30 (4 addresses) b) To simplify the solution, assume that no datagrams have router interfaces as ultimate destinations. Also, label D, E, F for the upper-right, bottom, and upper-left interior subnets, respectively. Router 1 Longest Prefix Match 11010110 01100001 11111111 11010110 01100001 11111110 0000000 11010110 01100001 11111110 000001 Router 2 Longest Prefix Match 11010110 01100001 11111111 0000000 11010110 01100001 11111110 0 11010110 01100001 11111110 0000001 Outgoing Interface Subnet D Subnet B Subnet E Outgoing Interface Subnet A Subnet D Subnet F

Router 3 Longest Prefix Match 11010110 01100001 11111111 000001 11010110 01100001 11111110 0000001 11010110 01100001 11111110 1 Outgoing Interface Subnet F Subnet E Subnet C

Problem 17
The maximum size of data field in each fragment = 680 (because there are 20 bytes IP  2400 − 20  header). Thus the number of required fragments =  =4  680   Each fragment will have Identification number 422. Each fragment except the last one will be of size 700 bytes (including IP header). The last datagram will be of size 360 bytes (including IP header). The offsets of the 4 fragments will be 0, 85, 170, 255. Each of the first 3 fragments will have flag=1; the last fragment will have flag=0.

Problem 18
MP3 file size = 5 million bytes. Assume the data is carried in TCP segments, with each TCP segment also having 20 bytes of header. Then each datagram can carry 150040=1460 bytes of the MP3 file  5 × 10 6  Number of datagrams required = =   = 3425 . All but the last datagram will be  1460  1,500 bytes; the last datagram will be 960+40 = 1000 bytes. Note that here there is not fragmentation – the source host does not create datagrams larger than 1500 bytes, and these datagrams are smaller than the MTUs of the links.

Problem 19
a) Home addresses: 192.168.1.1, 192.168.1.2, 192.168.1.3 with the router interface being 192.168.1.4 b) NAT Translation Table WAN Side LAN Side 24.34.112.235, 4000 192.168.1.1, 3345 24.34.112.235, 4001 192.168.1.1, 3346

24.34.112.235, 4002 24.34.112.235, 4003 24.34.112.235, 4004 24.34.112.235, 4005

192.168.1.2, 3445 192.168.1.2, 3446 192.168.1.3, 3545 192.168.1.3, 3546

Problem 20
a. Since all IP packets are sent outside, so we can use a packet sniffer to record all IP packets generated by the hosts behind a NAT. As each host generates a sequence of IP packets with sequential numbers and a distinct (very likely, as they are randomly chosen from a large space) initial identification number (ID), we can group IP packets with consecutive IDs into a cluster. The number of clusters is the number of hosts behind the NAT. For more practical algorithms, see the following papers. “A Technique for Counting NATted Hosts”, by Steven M. Bellovin, appeared in IMW’02, Nov. 6-8, 2002, Marseille, France. “Exploiting the IPID field to infer network path and end-system characteristics.” Weifeng Chen, Yong Huang, Bruno F. Ribeiro, Kyoungwon Suh, Honggang Zhang, Edmundo de Souza e Silva, Jim Kurose, and Don Towsley. PAM'05 Workshop, March 31 - April 01, 2005. Boston, MA, USA. b. However, if those identification numbers are not sequentially assigned but randomly assigned, the technique suggested in part (a) won’t work, as there won’t be clusters in sniffed data.

Problem 21
It is not possible to devise such a technique. In order to establish a direct TCP connection between Arnold and Bernard, either Arnold or Bob must initiate a connection to the other. But the NATs covering Arnold and Bob drop SYN packets arriving from the WAN side. Thus neither Arnold nor Bob can initiate a TCP connection to the other if they are both behind NATs.

Problem 22 y-x-u, y-x-v-u, y-x-w-u, y-x-w-v-u, y-w-u, y-w-v-u, y-w-x-u, y-w-x-v-u, y-w-v-x-u, y-z-w-u, y-z-w-v-u, y-z-w-x-u, y-z-w-x-v-u, y-z-w-v-x-u,

Problem 23 x to z: x-y-z, x-y-w-z, x-w-z, x-w-y-z,

x-v-w-z, x-v-w-y-z, x-u-w-z, x-u-w-y-z, x-u-v-w-z, x-u-v-w-y-z z to u: z-w-u, z-w-v-u, z-w-x-u, z-w-v-x-u, z-w-x-v-u, z-w-y-x-u, z-w-y-x-v-u, z-y-x-u, z-y-x-v-u, z-y-x-w-u, z-y-x-w-y-u, z-y-x-v-w-u, z-y-w-v-u, z-y-w-x-u, z-y-w-v-x-u, z-y-w-x-v-u, z-y-w-y-x-u, z-y-w-y-x-v-u z to w: z-w, z-y-w, z-y-x-w, z-y-x-v-w, z-y-x-u-w, z-y-x-u-v-w, z-y-x-v-u-w

Problem 24
Step N’ D(t),p(t) D(u),p(u) D(v),p(v) D(w),p(w) D(y),p(y) D(z),p(z)

0 1 2 3 4 5 6

x xv xvu xvuw xvuwy xvuwyt xvuwytz

∞ 7,v 7,v 7,v 7,v 7,v 7,v

∞ 6,v 6,v 6,v 6,v 6,v 6,v

3,x 3,x 3,x 3,x 3,x 3,x 3,x

6,x 6,x 6,x 6,x 6,x 6,x 6,x

6,x 6,x 6,x 6,x 6,x 6,x 6,x

8,x 8,x 8,x 8,x 8,x 8,x 8,x

Problem 25
a.
Step N’ D(x), p(x) ∞ ∞ 7,v 7,v 7,v 7,v 7,v D(u),p(u) 2,t 2,t 2,t 2,t 2,t 2,t 2,t D(v),p(v) 4,t 4,t 4,t 4,t 4,t 4,t 4,t D(w),p(w) ∞ D(y),p(y) D(z),p(z) ∞ ∞ ∞ ∞ 15,x 15,x 15,x

0 1 2 3 4 5 6

t tu tuv tuvw tuvwx tuvwxy tuvwxyz

5,u 5,u 5,u 5,u 5,u 5,u

7,t 7,t 7,t 7,t 7,t 7,t 7,t

b.
Step N’ D(x), p(x) D(t),p(t) D(v),p(v) D(w),p(w) D(y),p(y) D(z),p(z)

u ut utv utvw utvwx utvwxy utvwxyz

∞ ∞ 6,v 6,v 6,v 6,v 6,v

2,u 2,u 2,u 2,u 2,u 2,u 2,u

3,u 3,u 3,u 3,u 3,u 3,u 3,u

3,u 3,u 3,u 3,u 3,u 3,u 3,u

∞

9,t 9,t 9,t 9,t 9,t 9,t

∞ ∞ ∞ ∞ 14,x 14,x 14,x

c.
Step N’ D(x), p(x) 3,v 3,v 3,v 3,v 3,v 3,v 3,v D(u),p(u) 3,v 3,v 3,v 3,v 3,v 3,v 3,v D(t),pt) 4,v 4,v 4,v 4,v 4,v 4,v 4,v D(w),p(w) D(y),p(y) D(z),p(z) ∞ 11,x 11,x 11,x 11,x 11,x 11,x

v vx vxu vxut vxutw vxutwy vxutwyz

4,v 4,v 4,v 4,v 4,v 4,v 4,v

8,v 8,v 8,v 8,v 8,v 8,v 8,v

d.
Step N’ D(x), p(x) D(u),p(u) D(v),p(v) D(t),p(t) D(y),p(y) D(z),p(z)

w wu wuv wuvt wuvtx wuvtxy wuvtxyz

6,w 6,w 6,w 6,w 6,w 6,w 6,w

3,w 3,w 3,w 3,w 3,w 3,w 3,w

4,w 4,w 4,w 4,w 4,w 4,w 4,w

∞

5,u 5,u 5,u 5,u 5,u 5,u

∞ ∞

12,v 12,v 12,v 12,v 12,v

∞ ∞ ∞ ∞ 14,x 14,x 14,x

e.
Step N’ D(x), p(x) 6,y 6,y 6,y 6,y 6,y 6,y 6,y D(u),p(u) ∞ ∞ 9,t 9,t 9,t 9,t 9,t D(v),p(v) 8,y 8,y 8,y 8,y 8,y 8,y 8,y D(w),p(w) ∞ D(t),p(t) D(z),p(z) 12,y 12,y 12,y 12,y 12,y 12,y 12,y

y yx yxt yxtv yxtvu yxtvuw yxtvuwz

12,x 12,x 12,x 12,x 12,x 12,x

7,y 7,y 7,y 7,y 7,y 7,y 7,y

f.
Step N’ D(x), p(x) D(u),p(u) D(v),p(v) D(w),p(w) D(y),p(y) D(t),p(t)

z zx zxv zxvy zxvyu zxvyuwg zxvyuwt

8,z 8,z 8,z 8,z 8,z 8,z 8,z

∞ ∞ 14,v 14,v 14,v 14,v 14,v

∞ 11,x 11,x 11,x 11,x 11,x 11,x

∞ 14,x 14,x

14,x 14,x 14,x 14,x

12,z 12,z 12,z 12,z 12,z 12,z 12,z

∞ ∞ 15,v 15,v 15,v 15,v 15,v

Problem 26
Cost to u v v From x z ∞ ∞ ∞ ∞ ∞ 6

x ∞ ∞ 2

y ∞ ∞ ∞

z ∞ ∞ 0

Cost to u v From x z 1 ∞ 7 v 0 3 5 x 3 0 2 y ∞ 3 5 z 6 2 0

Cost to u v From x z 1 4 6 v 0 3 5 x 3 0 2 y 3 3 5 z 5 2 0

u

Cost to v

x

y

z

v From x z

1 4 6

0 3 5

3 0 2

3 3 5

5 2 0

Problem 27
The wording of this question was a bit ambiguous. We meant this to mean, “the number of iterations from when the algorithm is run for the first time” (that is, assuming the only information the nodes initially have is the cost to their nearest neighbors). We assume that the algorithm runs synchronously (that is, in one step, all nodes compute their distance tables at the same time and then exchange tables). At each iteration, a node exchanges distance tables with its neighbors. Thus, if you are node A, and your neighbor is B, all of B's neighbors (which will all be one or two hops from you) will know the shortest cost path of one or two hops to you after one iteration (i.e., after B tells them its cost to you). Let d be the “diameter” of the network - the length of the longest path without loops between any two nodes in the network. Using the reasoning above, after d − 1 iterations, all nodes will know the shortest path cost of d or fewer hops to all other nodes. Since any path with greater than d hops will have loops (and thus have a greater cost than that path with the loops removed), the algorithm will converge in at most d − 1 iterations. ASIDE: if the DV algorithm is run as a result of a change in link costs, there is no a priori bound on the number of iterations required until convergence unless one also specifies a bound on link costs.

Problem 28
a. Dx(w) = 2, Dx(y) = 4, Dx(u) = 7 b. First consider what happens if c(x,y) changes. If c(x,y) becomes larger or smaller (as long as c(x,y) >=1) , the least cost path from x to u will still have cost at least 7. Thus a change in c(x,y) (if c(x,y)>=1) will not cause x to inform its neighbors of any changes. If c(x,y)= δ 6, then the least cost path now passes through y and has cost 11; again x will inform its neighbors of this new cost. c. Any change in link cost c(x,y) (and as long as c(x,y) >=1) will not cause x to inform its neighbors of a new minimum-cost path to u .

Problem 29
Node x table Cost to x 0 ∞ ∞ y 3 ∞ ∞ Cost to y 3 0 6 z 4 ∞ ∞

x From y z

x From y z Node y table

x 0 3 4

z 4 6 0

x From y z

x ∞ 3 ∞

Cost to y ∞ 0 ∞

z ∞ 6 ∞ z 4 6 0

x From y z

Cost to x y 0 3 3 0 4 6

Node z table Cost to x y ∞ ∞ ∞ ∞ 4 6 Cost to y 3 0 6 z ∞ ∞ 0

x From y z

x From y z

x 0 3 4

z 4 6 0

Problem 30
NO, this is because that decreasing link cost won’t cause a loop (caused by the next-hop relation of between two nodes of that link). Connecting two nodes with a link is equivalent to decreasing the link weight from infinite to the finite weight.

Problem 31
At each step, each updating of a node’s distance vectors is based on the Bellman-Ford equation, i.e., only decreasing those values in its distance vector. There is no increasing in values. If no updating, then no message will be sent out. Thus, D(x) is non-increasing. Since those costs are finite, then eventually distance vectors will be stabilized in finite steps.

Problem 32
a). Router z Router w Router y Informs w, Dz(x)=∞ Informs y, Dz(x)=6 Informs y, Dw(x)=∞ Informs z, Dw(x)=5 Informs w, Dy(x)=4 Informs z, Dy(x)=4

b). Yes, there will be a count-to-infinity problem. The following table shows the routing converging process. Assume that at time t0, link cost change happens. At time t1, y updates its distance vector and informs neighbors w and z. In the following table, “ ” stands for “informs”. time t0 z w, Dz(x)=∞ y, Dz(x)=6 w y, Dw(x)=∞ z, Dw(x)=5 y w, Dy(x)=4 z, Dy(x)=4 t1 t2 No change y, Dw(x)=∞ z, Dw(x)=10 w, Dy(x)=9 z, Dy(x)= ∞ No change t3 w, Dz(x)=∞ y, Dz(x)=11 No change w, Dy(x)=14 z, Dy(x)= ∞ t4

We see that w, y, z form a loop in their computation of the costs to router x. If we continue the iterations shown in the above table, then we will see that, at t27, z detects that its least cost to x is 50, via its direct link with x. At t29, w learns its least cost to x is 51 via z. At t30, y updates its least cost to x to be 52 (via w). Finally, at time t31, no updating, and the routing is stabilized. time t27 z w, Dz(x)=50 y, Dz(x)=50 t28 t29 t30 t31 via w, ∞ via y, 55

w

y, Dw(x)=∞ z, Dw(x)=50 w, Dy(x)=53 z, Dy(x)= ∞

y, Dw(x)=51 z, Dw(x)= ∞ w, Dy(x)= ∞ z, Dy(x)= 52

y

via z, 50 via w, ∞ via y, ∞ via z, 51 via w, 52 via y, 60 via z, 53

c). cut the link between y and z.

Problem 33
Since full AS path information is available from an AS to a destination in BGP, loop detection is simple – if a BGP peer receives a route that contains its own AS number in the AS path, then using that route would result in a loop.

Problem 34
The chosen path is not necessarily the shortest AS-path. Recall that there are many issues to be considered in the route selection process. It is very likely that a longer loop-free path is preferred over a shorter loop-free path due to economic reason. For example, an AS might prefer to send traffic to one neighbor instead of another neighbor with shorter AS distance.

Problem 35
a. eBGP b. iBGP c. eBGP d. iBGP

Problem 36
a) I1 because this interface begins the least cost path from 1d towards the gateway router 1c. b) I2. Both routes have equal AS-PATH length but I2 begins the path that has the closest NEXT-HOP router. c) I1. I1 begins the path that has the shortest AS-PATH.

Problem 37
One way for C to force B to hand over all of B’s traffic to D on the east coast is for C to only advertise its route to D via its east coast peering point with C.

Problem 38

w

B A C y

x

w

B A C y

x

X’s view of the topology

W’s view of the topology

In the above solution, X does not know about the AC link since X does not receive an advertised route to w or to y that contain the AC link (i.e., X receives no advertisement containing both AS A and AS C on the path to a destination.

Problem 39
BitTorrent file sharing and Skype P2P applications. Consider a BitTorrent file sharing network in which peer 1, 2, and 3 are in stub networks W, X, and Y respectively. Due the mechanism of BitTorrent’s file sharing, it is quire possible that peer 2 gets data chunks from peer 1 and then forwards those data chunks to 3. This is equivalent to B forwarding data that is finally destined to stub network Y.

Problem 40
A should advise to B two routes, AS-paths A-W and A-V. A should advise to C only one route, A-V. C receives AS paths: B-A-W, B-A-V, A-V.

Problem 41
The minimal spanning tree has z connected to y via x at a cost of 14(=8+6). z connected to v via x at a cost of 11(=8+3); z connected to u via x and v, at a cost of 14(=8+3+3); z connected to w via x, v, and u, at a cost of 17(=8+3+3+3). This can be obtained by Prim’s algorithm to grow a minimum spanning tree.

Problem 42

The 32 receives are shown connected to the sender in the binary tree configuration shown above. With network-layer broadcast, a copy of the message is forwarded over each link exactly once. There are thus 62 link crossings (2+4+8+16+32). With unicast emulation, the sender unicasts a copy to each receiver over a path with5 hops. There are thus 160 link crossings (5*32). A topology in which all receivers are in a line, with the sender at one end of the line, will have the largest disparity between the cost of network-layer broadcast and unicast emulation.

Problem 43
A c B

D F E G
Th e t hi cke r s h ad e d lin e s re p re se n t Th e s h ort es t pa t h tre e f rom A t o a ll d e stin a tio n . Ot h e r so lu tio n s are p o ssib le , bu t in t he s e solu tio n s, B ca n n o t ro ut e to eit h e r C or D f rom A .

Problem 44

A c B

D F E G

Problem 45
Z

y v x

t

u w

Problem 46
The center-based tree for the topology shown in the original figure connects A to C; B to C; E to C; and F to C (all directly). D connects to C via E, and G connects to C via D, E. This center-based tree is different from the minimal spanning tree shown in the figure.

Problem 47
The center-based tree for the topology shown in the original figure connects t to v; u to v; w to v; x to v; and y to v (all directly). And z connected to v via x. This center-based tree is different from the minimal spanning tree.

Problem 48
Dijkstra’s algorithm for the network below, with node A as the source, results in a leastunicast-cost path tree of links AC, AB, and BD, with an overall free cost of 20. The minimum spanning tree contains links AB, BD, and DC, at a cost of 11.

10

c
1

1

A

9

D

B

Problem 49
After 1 step 3 copies are transmitted, after 2 steps 6 copies are transmitted. After 3 steps, 12 copies are transmitted, and so on. After k steps, 3*2k-1 copies will be transmitted in that step.

3 6 12 24 48 …

Problem 50
The protocol must be built at the application layer. For example, an application may periodically multicast its identity to all other group members in an application-layer message.

Problem 51
A simple application-layer protocol that will allow all members to know the identity of all other members in the group is for each instance of the application to send a multicast message containing its identity to all other members. This protocol sends message inband, since the multicast channel is used to distribute the identification messages as well as multicast data from the application itself. The use of the in-band signaling makes use of the existing multicast distribution mechanism, leading to a very simple design.

Problem 52
32 − 4 = 28 bits are available for multicast addresses. Thus, the size of the multicast address space is N = 2 28 .
The probability that two groups choose the same address is

1 = 2 − 28 = 3.73 ⋅ 10 −9 N

The probability that 1000 groups all have different addresses is N ⋅ ( N − 1) ⋅ ( N − 2) L ( N − 999)  1  2   999  = 1 − 1 −  L 1 −  1000 N  N  N  N  Ignoring cross-product terms, this is approximately equal to 999 ⋅ 1000  1 + 2 + L + 999  1−  = 0.998  = 1− 2N N  

Chapter 5 Review Questions
1. The transportation mode, e.g., car, bus, train, car. 2. Although each link guarantees that an IP datagram sent over the link will be received at the other end of the link without errors, it is not guaranteed that IP datagrams will arrive at the ultimate destination in the proper order. With IP, datagrams in the same TCP connection can take different routes in the network, and therefore arrive out of order. TCP is still needed to provide the receiving end of the application the byte stream in the correct order. Also, IP can lose packets due to routing loops or equipment failures. 3. Framing: there is also framing in IP and TCP; link access; reliable delivery: there is also reliable delivery in TCP; flow control: there is also flow control in TCP; error detection: there is also error detection in IP and TCP; error correction; full duplex: TCP is also full duplex. 4. There will be a collision in the sense that while a node is transmitting it will start to receive a packet from the other node. 5. Slotted Aloha: 1, 2 and 4 (slotted ALOHA is only partially decentralized, since it requires the clocks in all nodes to be synchronized). Token ring: 1, 2, 3, 4. 6. In polling, a discussion leader allows only one participant to talk at a time, with each participant getting a chance to talk in a round-robin fashion. For token ring, there isn’t a discussion leader, but there is wine glass that the participants take turns holding. A participant is only allowed to talk if the participant is holding the wine glass. 7. When a node transmits a frame, the node has to wait for the frame to propagate around the entire ring before the node can release the token. Thus, if L/R is small as compared to tprop, then the protocol will be inefficient. 8. 248 MAC addresses; 232 IPv4 addresses; 2128 IPv6 addresses. 9. C’s adapter will process the frames, but the adapter will not pass the datagrams up the protocol stack. If the LAN broadcast address is used, then C’s adapter will both process the frames and pass the datagrams up the protocol stack. 10. An ARP query is sent in a broadcast frame because the querying host does not which adapter address corresponds to the IP address in question. For the response, the sending node knows the adapter address to which the response should be sent, so there is no need to send a broadcast frame (which would have to be processed by all the other nodes on the LAN).

11. No it is not possible. Each LAN has its own distinct set of adapters attached to it, with each adapter having a unique LAN address. 12. The three Ethernet technologies have identical frame structures. 13. 20 million transitions per second. 14. After the 5th collision, the adapter chooses from {0, 1, 2,…, 31}. The probability that it chooses 4 is 1/32. It waits 204.8 microseconds. 15. 2 (the internal subnet and the external internet) 16. In 802.1Q there is a 12- bit VLAN identifier. Thus 212 = 4,096 VLANs can be supported. 17. We can string the N switches together. The first and last switch would use one port for trunking; the middle N-2 switches would use two ports. So the total number of ports is 2+ 2(N-2) = 2N-2 ports.

Chapter 5 Problems
Problem 1
11101 10111 10010 11011 00011

Problem 2
Suppose we begin with the initial two-dimensional parity matrix: 0000 1111 0101 1010 With a bit error in row 2, column 3, the parity of row 2 and column 3 is now wrong in the matrix below: 0000 1101 0101 1010 Now suppose there is a bit error in row 2, column 2 and column 3. The parity of row 2 is now correct! The parity of columns 2 and 3 is wrong, but we can't detect in which rows the error occurred! 0000 1001 0101 1010 The above example shows that a double bit error can be detected (if not corrected).

Problem 3
01001100 01101001 + 01101110 01101011 -----------------------------10111010 11010100 + 00100000 01001100 ------------------------------

11011011 00100000 + 01100001 01111001 ----------------------------00111100 10011010 (overflow, then wrap around) + 01100101 01110010 -----------------------------10100010 00001100 The one's complement of the sum is 01011101 11110011

Problem 4

a) To compute the Internet checksum, we add up the values at 16-bit quantities:
00000001 00000010 00000011 00000100 00000101 00000110 00000111 00001000 00001001 00001010 ------------------------00011001 00011110 The one's complement of the sum is 11100110 11100001.

b) To compute the Internet checksum, we add up the values at 16-bit quantities:
01000001 01000010 01000011 01000100 01000101 01000110 01000111 01001000 01001001 01001010 ------------------------01011000 01011111 The one's complement of the sum is 10100111 10100000 c) To compute the Internet checksum, we add up the values at 16-bit quantities:

01100001 01100010 01100011 01100100 01100101 01100110 01100111 01100111 01101000 01101001 ------------------------11111001 11111101 The one's complement of the sum is 00000110 00000010.

Problem 5
If we divide 10011 into 1010101010 0000, we get 1011011100, with a remainder of R=0100. Note that, G=10011 is CRC-4-ITU standard.

Problem 6
a) we get 1000100011, with a remainder of R=0101. b) we get 1011111111, with a remainder of R=0001. c) we get 0101101110, with a remainder of R=0010.

Problem 7
a. Without loss of generality, suppose ith bit is flipped, where 0