Chapter 4 Questions

Problem #4: Consider the network below:

a.Suppose that this network is a datagram network. Show the forwarding table in router A, such that all traffic destined to host H3 is forwarded through interface 3.

Header Value Destination	Output Interface Link
H3	3

b.Suppose that this network is a datagram network. Can you write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4? (Hint: this is a trick question.)

• No, this is impossible. A datagram bases what path to take based off of the destination. If the output link from router A is determined to be link 3 as denoted in the routing table above, then this will be the only path that H2 will be able to send on. H2 can only tell the datagram to send to router A, from there router A will pick the link with the lowest cost, which is link 3.

c. Now suppose that this network is a virtual circuit network and that there is one ongoing call between H1 and H3, and another ongoing call between H2 and H3. Write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4.

Host	Virtual Circuit Number	Outgoing Link	Outgoing Circuit Number
H1	20	3	52
H2	531	4	981

d.Assuming the same scenario as (c), write down the forwarding tables in nodes B, C, and D

VC Router (through B)	Incoming VC Number	Link	Outgoing VC Number
A	20	3	52
B	52	2	98
D	98	3	7
VC Router (through C)	Incoming VC Number	Link	Outgoing VC Number
A	531	4	981
C	981	2	56
D	56	3	12

Problem #6: In the text we have used the term connection-oriented service to describe a transport-layer service and connection service for a network-layer service.Why the subtle shades in terminology?

• The reason for the subtle change in terminology  is due to the ways that the network interacts along the path. The transport layer connection oriented service is implemented at the edge of the network in the end systems, where the network layers connection service is implemented at both the end systems and the routers along the path (Kurose, Ch4.2, 4/12/13). The Network layers connection service, known as a virtual circuit, mandates that the routers along the path must maintain state with each other and know of the next router  in the path towards the destination until the connection has been terminated by one of the end systems. In a connection-oriented service , over the transport layer, or TCP, a handshake is made, and correct inorder delivery is promised, however, unlike in a virtual circuit where all traffic takes the same path, the datagrams in TCP can take a different path and show up out of order before being reorganized. TCP simulates a connection, where a virtual circuit is a constant connection maintained through the communicating hosts.

Problem #10: Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows:

Destination Address Range Link Interface

11100000 00000000 00000000 00000000

through(0)

11100000 00111111 11111111 11111111

11100000 01000000 00000000 00000000

through (1)

111100000 01000000 11111111 11111111

11100000 01000001 00000000 00000000

through (2)

11100001 01111111 11111111 11111111

otherwise (3)

a.Provide a forwarding table that has five entries, uses longest prefix matching, and forwards packets to the correct link interfaces.

Address	Link
11100000 00 (/10)	0
11100000 01(/10)	1
11100000 01000001 (/16)	2
11100001(/8)	2
Otherwise	3

b.Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses:

11001000 10010001 01010001 01010101

• Interface 3

11100001 01000000 11000011 00111100

• Interface 1

11100001 10000000 00010001 01110111

• Interface 2

Problem #11: Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table:

Prefix Match      Interface

    00                          0

   010                         1

   011                          2

   10                            2

   11                             3

For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range

Prefix	Min	Max	Range
00	00000000= 0	00111111 = 63	64
010	01000000 = 64	01011111 = 95	32
011	01100000= 96	01111111 = 127	32
10	10000000 = 128	10111111 = 191	64
11	11000000 = 192	11111111 = 255	64

• The minimum number of the address and the maximum number of the address can be found by substituting 0 (min) or 1(max) for the remaining bits in an 8 bit address not defined by the prefix. The Range can then be found as the difference between the minimum possible value and the maximum possible value

Problem #27:Consider the following network. Using Dijkstra’s algorithm, and show your work, create a table for T, U, V, W, Y, Z

• According to Dijkstra’s Algorithm, the routers figure out to which host they can make the fastest hop based on the cost. For example, in my first table shown below, the routing table for T,  the first hop made is to U as the cost is the smallest at 3. After U has joined the new supernode TU, you add the cost (2) of getting from T to U to the links not contained within the supernode because in the case that the packet reaches the next node, in T’s case V through U it must take the time fro m T->U and U->V, in this case, it does not pass through T to reach V, but that is the general concept,
• T Routing Table

• U Routing Table

• W Routing Table

• V Routing Table

• Y Routing Table

• Z Routing Table

Problem #37: Consider the network shown below. Suppose AS3 and AS2 are running OSPF for their intra-AS routing protocol. Suppose AS1 and AS4 are running RIP for their intra-AS routing protocol. Suppose eBGP and iBGP are used for the inter-AS routing protocol. Initially suppose there is no physical link between AS2 and AS4.

 

a.Router 3c learns about prefix x  from which routing protocol: OSPF, RIP,eBGP, or iBGP?

• eBGP, because router 3c would learn about x from router 4c, which means that it would hear from another AS .

b.Router 3a learns about x from which routing protocol?

• OSPF 3a would learn about x from 3b, which means that it is learning about x from 3b, which because it is not on any border is only able to run OSPF.

c.Router 1c learns about x from which routing protocol?

• eBGP, learns about X from 3a, which means that it is learning from another AS

d.Router 1d learns about x from which routing protocol?

• RIP, learns about X from 1a, which is not on any borders and therefore is only running RIP to communicate with other hosts on its network.

Problem #45: 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 achieve 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? 

• The image above shows 32 receivers(the darkened nodes at the bottom) connected to a single sender through a binary tree configuration in which each node can have a maximum of 2 connections. According to the network layer broadcast, a packet is sent over  each link only once. Therefore, the number of link crossings can be determined by the number of edges that connect each node or 2+4+8+16+32 or 62 total link crossings.  With unicast emulation, the sender sends a copy of the packet to each of the 32 receivers. Each packet must traverse 5 hops before reaching the 32 receivers, which means that the total number of link crossings can be denoted as 5*32 for the number of hops*the number of end packets or 160 total crossings.