CNT 4704: Analysis of Computer Communication Networks
Fall 2012
Homework 3
(assigned 11/06; due: Nov. 13th midnight via webcourse)
1. 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
11100000 01000000 11111111 11111111
11100000 01000001 00000000 00000000
through
2
11100001 01111111 11111111 11111111
otherwise
3
a). Provide a forwarding table that has four entries, uses
longest prefix matching, and forwards packets to the correct
link interfaces. (hint: the IP range to interface 2 cannot be
represented by one prefix)
b). Describe how your forwarding table determines the
appropriate link inter-face for datagrams with destination
addresses:
11001000 10010001 01010001 01010101
11100001 01000000 11000011 00111100
11100001 10000000 00010001 01110111
2.
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 be within the IP range of
114.115.127/24. And also suppose IP addresses in these 3 subnets
need to have the relationship of Subnet1 < Subnet2 <
Subnet3. Subnet 1 is required to support up to 63 interfaces,
Subnet 2 is to support no smaller than 95 inter-faces, and
Subnet 3 is to support 15 interfaces. Provide three network
addresses ( of the form
a.b.c.d/x) that satisfy these constraints.
3. Considering the following network. With
the indicated link cost, use Dijkstra's shortest path algorithm
to compute the shortest paths from node W to all other nodes. You
need to show how the algorithm works by computing a table
similar to the table shown in Page 23 in Chapter4-part2.ppt.
4. Distance Vector Routing: Consider the network shown below, and assume that each node initially knows the costs to each of its neighbors. Assume all nodes receive their neighbors' update message at the same time and update their own distance table at the same time (similar to the example shown in Page 32,33 in Chapter4-part2.ppt). Show the distance table update procedure in the similar way as Page 33 in Chapter4-part2.ppt.
5. What are the three major routing protocols used in Internet? Give their full name and their acronym. Which protocol is mainly based on link-sate algorithm? Which protocol is mainly based on distance vector algorithm?