Exercises – Network layer

Exercise 6.1.
With reference to Figure 6.4, consider host B with IP address 131.175.201.14 which sends a datagram with 2000 bytes of payload and identification = 27,901 to host A with IP address 197.203.12.7. Assuming routing at minimum distance (number of hops), default MTU except for network N2 in which this parameter assumes value 1500 bytes, show graphically the format of the IP datagrams, for all the known fields, exchanged between hosts and routers.

Figure 6.4 Network configuration according to Example 6.1 (Exercise 6.1).

The format of the IP datagram generated in host B is the one furthest to the left in Figure E6.1: it shows all the fields defined in the exercise, that is the version (4) of the protocol, the number of bytes of the header (20) assuming no options, the datagram number (27901), single fragment (MF = 0) and therefore null offset. Given the MTU of network , this datagram crosses network to router in the form of two fragments, the first of 1480 bytes of information and the second with the remaining 520 bytes. The first fragment bears MF = 1 and offset = 0, while the second and last fragment bears MF = 0 and offset = 185, given by the number of user bytes divided by 8. The two fragments must therefore be transferred from router to router R1 through the direct connection , characterized by a default MTU, i.e. MTU = 576. Taking into account the consistency of the IP datagram header, the payload of each datagram will have a maximum size of 552 bytes, i.e. the largest integer not exceeding 556 and divisible by 8. Then the original payload of 1480 bytes is transmitted from router to host A in three fragments with payload 552, 552 and 376 bytes, to account for the 20 bytes header of the IP datagram. The corresponding offsets are 0, 69, 138. These three fragments, once received in host A together with the fragment, are recomposed into a single datagram that is delivered to the destination port specified in the payload.

Figure E6.1 Contents of IP datagrams exchanged between hosts and routers according to Exercise 6.1.

Exercise 6.6.
Partition the class A network with address 64.0.0.0 in subnets /17 (i.e. with netmask having the first 17 bits set at 1), determining the number of subnets that are obtained and the decimal format of the subnet number 163. This last “network” is in turn divided into subnets /n that allow addressing at least 1023 hosts each. Determine the subnet prefix /n, the resulting number of subnets and the broadcast address of subnet number 10.

Since the address 64.0.0.0 defines an 8-bit net-id, then 17-8 = 9 bits identify the = 512 subnets of which the number 163 has an address of 64.81.128.0/17. Partitioning this last network into subnets that support 1023 hosts each implies that 11 bits must be used for the new host-id and the remaining 32 _ 17 _ 11 = 4 bits to indicate the subnet. So the new netmask is /21 and the broadcast address of network number 10 is given by 64.81.215.255. Note that the last 15 bits are 1010111.11111111 indicating that this is the broadcast configuration (last 11 bits set to 1) in subnet number 10 (first 4 bits set to 1010).

Exercise 6.10.
An operator manages the following physical networks: (i) network that connects 40 hosts, (ii) network that connects 100 hosts, (iii) network that connects 14 hosts, (iv) network that connects 8 hosts, and obtains from the Internet authority multiple blocks of addresses starting at address 199.2.3.0. Assuming classful addressing without variable length netmask adoption, assign blocks of IP addresses to individual networks starting from the smallest available address, specifying for each of them also the corresponding netmask, in order to minimize the total number of addresses that can no longer be used outside these four networks.

The address blocks available to the operator are in class C and therefore each of them can provide addresses to 254 hosts. However, the need to assign address blocks to four distinct physical networks requires partitioning the available addresses into blocks, each assigned to a subnet. The unavailability of the use of variable length netmasks requires that all addresses of a class-C block are characterized by the same netmask, which is necessarily the one required by the subnet that supports the largest number of hosts. So a class C address block will be used with netmask /25, since the network connects 100 hosts, so as to provide addresses to networks and A second class-C address block will be partitioned into /28 address blocks, as 4 bits are required to address hosts on networks and (useful addresses in a /29 subnet would only be 6). The address assignment thus created, represented in Table E6.1, shows that the second block of addresses in class C assigns only one eighth of the available addresses, leaving unused the others that have already been partitioned with netmask /28.

Table E6.1 Assignment of IP addresses according to Exercise 6.10.

Exercise 6.12.
An operator manages the following physical networks: (i) network that connects 40 hosts, (ii) network that connects 100 hosts, (iii) network that connects 14 hosts, (iv) network that connects 8 hosts, and obtains an Internet address block from the Internet authority starting from address 199.2.3.0. Assuming classful addressing, suppose that the administrator is going to associate a subnet with the following rules to each of the physical networks from to : (i) all routers support variable length subnet mask (VLSM), which allows assigning variable length netmasks to different subnets; (ii) the subnet associated with each physical network must be such that the number of addresses not used by the hosts is as small as possible; (iii) the four physical networks are associated with blocks of contiguous addresses starting from the network address with smallest net-id and host-id.

The ability to define variable-length netmasks allowed by the VLSM mechanism allows for greater efficiency in addressing than in Exercise 6.10. In fact, considering the definition of subnets having addresses that are powers of two, 64 + 128 + 16 + 16 = 224 addresses are now required which can be obtained from a single address block in class C. The partitioning of the block requires assigning addresses to subnets in descending order of the number of hosts to connect per subnet. So the first partitioning takes place with netmask /25 in the two blocks 199.2.3.0/25 and 199.2.3.128/25, of which the first is assigned to network and the second is further partitioned with netmask /26, as required for addressing of hosts in network . So block 199.2.3.128/26 is assigned to network , while block 199.2.3.192 is further partitioned into four blocks, of which the first two are assigned to networks and . The address assignment thus created, represented in Table E6.2, shows that the unused addresses of the single class-C block in use are only 32 starting from address 199.2.3.224.

Table E6.2Assignment of IP addresses according to Exercise 6.12.

Exercise 6.20.
With reference to the address translation functionality implemented in a router R, identify the “mapping” table of a NAPT having only one public address, which interfaces three hosts, , , , of a private network whose addresses are the last three private addresses of the block in class B; these hosts access an FTP server , a mail server POP3 and a WWW server with the first public address, respectively, in class A, in class B and in class C. It is assumed that the NAPT device selects the largest possible values for identifying the NAPT port number starting from host H1 and that each host selects the smallest value as the private port identifier.

Table E6.3 shows the contents of the NAPT device “mapping” table for the specified connections.

Table E6.3 Content of NAPT table according to Exercise 6.20.

Exercise 6.23.
Wiven the routing table below of an IP router for increasing netmasks (the netmask and the next hop router are shown for each network address). build a table that specifies the next hop that the router assigns according to the longest prefix match algorithm to datagrams whose destination IP address is: 90.160.67.64, 90.169.1.66, 92.0.6.3, 90.168.1.80, 88.32. 7.4, 91.32.27.43, 90.48.128.7, 90.34.128.0, 90.168.193.80, 90.170.192.3.

Table E6.4 shows the contents of the routing table by increasing network address, also reporting the corresponding binary notation. The writing in binary format of the assigned destination addresses shown in Table E6.5 helps us to identify the rows of the routing table with equality of the first n bits of the destination network with netmask /n, thus selecting from these the next hop router of the row with the largest value of n, according to the longest prefix match algorithm.

Table E6.4 Reordered routing table according to Exercise 6.23.

Table E6.5 Routing with longest prefix match algorithm according to Exercise 6.23.

Exercise 6.26.
Repeat Example 6.15 identifying the routing table of router ordered by netmasks of increasing value and also aggregating addresses, if possible, in order to reduce the entries of the routing table.

Figure 6.15 Network configuration according to Example 6.15 (Exercise 6.26).

The required routing table, shown in Table E6.6, contains nine entries, of which two indicate local forwarding on the two directly interfaced networks and , four entries indicate the interface of router with address 56.64.8.1, three entries indicate the interface of router with address 56.0.0.1. Only the latter can be aggregated under the default routing item, removing rows 1 and 3. In fact, in the absence of “matching” with network addresses in the routing table, the datagrams are routed along the default route.

Table E6.6 Routing table of router according to Exercise 6.26.

Exercise 6.31.
A network is given having 6 nodes, A, B, C, D, E, F, and 10 edges, A-B of cost 1, B-C of cost 2, C-D of cost 3, D-E of cost 2, E-F of cost 6, F-A of cost 4, A-E of cost 11, B-F of cost 3, C-E of cost 7, CF of cost 3. Determine the evolution of the routing table of node E on the basis of the distance vectors received from the adjacent nodes in the first four updating steps of the routing tables, assuming that the vectors are transmitted between nodes at the same times and that the updating in each node occurs only once per step considering all the vectors received.

The assigned network is represented in Figure E6.2. The evolution of the routing table of node E, in accordance with subsequent updates received with the distance vectors received from adjacent nodes A, C, D, F is shown in Table E6.7. It can be noted that four updating steps are necessary so that node E can have a complete view of the network, thus determining the minimum cost path to every other node in the network. This path, except for node F reached with the direct connection, always crosses node D.

Figure E6.2 Network with six nodes and ten branches with relative distances according to Exercise 6.31.

Table E6.7 Routing table evolution of node E according to Exercise 6.31.

Exercise 6.33.
Consider a six-node network of which node D just connected to the network receives the following sequence of LSU messages, indicating the cost of traversing the links between adjacent nodes shown in the following table. Assuming that the cost is the same for both directions of each link, show how receiving these LSU messages allows the construction of the complete network topology seen by node D.

As shown in Figure E6.3, the receipt of the first LSU message from node A allows node D to know the existence of three other nodes, A, B, F and related links. The existence of node C is known only with the second LSU message describing the connectivity of node B. The third LSU message informs about the nodes adjacent to node C, while the fourth LSU message, received from node E, allows the network topology to be completed in node D. Receiving the fifth LSU message from node F provides only repeated information that does not change the topology.

Figure E6.3 Generation of network topology in node D according to Exercise 6.33.

Exercise 6.34.
For the network topology found in Exercise 6.33, find the minimum spanning tree (MST) for node D, which therefore is the tree root, applying the Dijkstra’s algorithm.

The application of Dijkstra’s algorithm is represented in Table E6.8. Nodes D, F, E, A, B are gradually added to the initial node D in the set M. It is interesting to observe how the path towards node E is varied as nodes are added to the tree, as there are routes at a lower cost than the previous ones. The same thing happens for the path towards node B which in the last step of the algorithm crosses node A instead of node C.

Table E6.8 Application of Dijkstra’s algorithm for node D according to Exercise 6.34.

Figure E6.4 MST of node D according to Exercise 6.34.