College of Computer & Information Science Fall 2004 Northeastern University Handout 12 CSU640: Network Fundamentals 22 November 2004

Sample Solution to Problem Set 3

1. (8 points) IP fragmentation

Suppose a TCP message that contains 2048 bytes of data and 20 bytes of TCP header is passed to IP for delivery across two networks of the Internet (i.e., from the source host to a router to the destination host). The first network has an MTU (maximum transmission unit) of 1024 bytes while the second has an MTU of 512 bytes. Give the sizes and offsets of the sequence of fragments delivered to the network layer at the destination host. Assume all IP headers are 20 bytes.

Answer: Before entering the first network, we have an IP datagram of 2048 + 20 (TCP header) + 20 (IP header) = 2088 bytes. So the IP payload is 2068 bytes. This datagram needs to split into 3 fragments.

• Fragment 1: IP header of 20 bytes, and data of 1000 bytes. Offset is 0.

• Fragment 2: IP header of 20 bytes, data of 1000 bytes. Offset is 1000/8 = 125.

• Fragment 3: IP header of 20 bytes, and data of 68 bytes. Offset is 2000/8 = 250.

When fragment 1 goes through the second network, it needs to be split into three fragments. Each fragment can contain at most 512 − 20 = 492 bytes of data. Since 492 is not a multiple of 8, each fragment can, in fact, contain at most 488 bytes of data. So we have the following 3 fragments:

• Fragment 4: IP header of 20 bytes, and data of 488 bytes. Offset is 0.

• Fragment 5: IP header of 20 bytes, and data of 488 bytes. Offset is 488/8 = 61.

• Fragment 6: IP header of 20 bytes, and data of 1000 − 488 · 2 = 24 bytes. Offset is 976/8 = 122.

Similarly, when fragment 2 goes through the second network, it needs to be split into three fragments.

• Fragment 7: IP header of 20 bytes, and data of 488 bytes. Offset is 125.

• Fragment 8: IP header of 20 bytes, and data of 488 bytes. Offset is 125+61 = 186.

• Fragment 9: IP header of 20 bytes, and data of 1000 − 488 · 2 = 24 bytes. Offset is 125+122 = 247.

Finally, fragment 3 goes as is through the second network since it is of size 88 bytes.

The fragments that reach the destination are 4, 5, 6, 7, 8, 9, and 3. They are assembled in this order. This is because their offsets are in increasing order (0, 61, 122, 125, 186, 247, and 250). Also note that fragments 4 through 9 will have their fragmentation bit set while fragment 3 will not, indicating that it is the last fragment of the original datagram.

2. (8 points) Allocation of IP addresses

An organization has a network with the allocated range of IP addresses being 200.1.1/24, and wants to form subnets for four departments, with hosts as follows: subnet A with 72 hosts, subnet B with 35 hosts, subnet C with 20 hosts, and subnet D with 18 hosts. Thus, there are 145 hosts in all.

(a) Give a possible arrangement of subnet masks to make this possible.

Answer: Giving each department a single subnet, the nominal subnet sizes are 2^{7}, 2^{6}, 2^{5}, and 2^{5}, respectively; we obtain these by rounding up to the nearest power of 2. A possible arrangement of subnet numbers is as follows. For each network, we have the subnet number and then the subnet mask. At the end of each line is the initial segment of the last byte of the subnet that forms the network; this is for clarification purposes only.

A 200.10.10.0 255.255.255.128 0/

B 200.10.10.128 255.255.255.192 10/

C 200.10.10.192 255.255.255.224 110/

D 200.10.10.224 255.255.255.224 111/

The essential requirement is that any two distinct subnet numbers remain distinct when the longer one is truncated to the length of the shorter one.

(b) Suggest what the organization might do if department D grows to 34 hosts.

Answer: We have two choices: either assign multiple subnets to single departments, or abandon subnets and put all the nodes on one network. Here is a solution giving A two subnets, of sizes 64 and 32; every other department gets a single subnet of size the next highest power of 2:

A 01/ and 001/

B 10/

C 000/

D 11/

There are other options too, though less desirable, including getting an additional subnet address, and hence setting up two different networks.

3. (8 points) Routing tables with CIDR addressing

Suppose X, Y, and Z are network service providers (ISPs), with respective CIDR address allocations (in hexadecimal form) C1.0.0.0/8, C2.0.0.0/8, and C3.0.0.0/8. Each provider’s customers receive address allocations that are a subset of the providers.

ISP X has two customers: XA, with allocation C1.B2.0.0/16, and XB, with allocation C1.B0.0.0/16.

ISP Y also has two customers: YA with allocation C2.0A.10.0/20, and YB with allocation C2.0B.0.0/16.

Suppose X is connected to Y and Y to Z. Give routing tables for X, Y, and Z. Each routing table has 2 fields: one is the network/masklength (in CIDR format), and the other is the nexthop. In the nexthop field, you can simply write the name of the ISP or the customer on the next hop.

Answer:

For X:

C1.B2.0.0/16 XA C1.B0.0.0/16 XB C2.0.0.0/8 Y C3.0.0.0/8 Y

For Y:

C2.0A.10.0/20 YA C2.0B.0.0/16 YB C1.0.0.0/8 X C3.0.0.0/8 Z

For Z:

C3.0.0.0/8 Z C1.0.0.0/8 Y C2.0.0.0/8 Y

4. (8 points) NAT and P2P applications

Problem 18 of Chapter 4, page 407.

Answer:

(a) NAT maintains a mapping associated with each connection initiated by a LAN host. It maps pairs of LAN-IP-address and port numbers to port numbers that it includes in every outgoing packet. NAT does not have an entry for a connection initiated from the WAN side, hence will drop incoming packets from Arnold.

(b) Bernard can know the IP address of Arnold through Cindy. Then, the p2p application running at Bernard can initiate a connection through NAT to Arnold and upload the file.

5. (9 points) Dijsktra’s shortest path algorithm

Problem 21 of Chapter 4, page 408.

Answer:

N′  D(s), p(s) D(t), p(t) D(u), p(u) D(v), p(v) D(w), p(w) D(y), p(y) D(z), p(z)
∞  ∞  ∞  3, x  1, x  6, x  ∞
w  ∞  ∞  4, w  2, w  6, x  ∞
wv  ∞  11, v  3, v  3, v  ∞
wvu  7, u  5, u  3, v  ∞
wvuy  7, u  5, u  17, y
wvuyt 6, t  7, t
wvuytz  7, t

6. (9 points) Distance vector algorithm Problem 26 of Chapter 4, page 409. Answer:

• Node X’s table: Cost to  Cost to X  Y  Z  X  Y  Z X 0  5  2  X 0  5  2 from Y ∞  ∞  ∞  from Y 3  0  6 Z ∞  ∞  ∞  Z 2  6  0

• Node Y ’s table: Cost to  Cost to X  Y  Z  X  Y  Z X ∞  ∞  ∞  X 0  5  2 from Y 5  0  6  from Y 5  0  6 Z ∞  ∞  ∞  Z 2  6  0

• Node Z’s table: Cost to  Cost to X  Y  Z  X  Y  Z X ∞  ∞  ∞  X 0  5  2 from Y ∞  ∞  ∞  from Y 5  0  6 Z 2  6  0  Z 2  6  0