Routing Assignment: Distance Vector Routing
In this assignment you will implement a simplified version of RIPv1, once one of the most popular routing protocols in the Internet. It is a distance vector routing protocol of which link cost is simply a hop count. It runs on top of UDP and uses a well-known port 520. You must implement UDP. You have already implemented TCP in previous assignments. Implementing UDP should be a breeze. Below is the UDP packet header format from RFC 768. The source and destination ports are the same as in TCP. The length field is the length of the UDP header and the UDP data in bytes. The checksum is computed over the header and the data. When the data length is in odd bytes, then a pad byte of 0 is appended at the end just for the computation. The padded byte is not transmitted. As in the case of the TCP checksum computation, 12-byte pseudo-header is included in the checksum computation.
0 7 8 15 16 23 24 31
+--------+--------+--------+--------+
| Source | Destination |
| Port | Port |
+--------+--------+--------+--------+
| | |
| Length | Checksum |
+--------+--------+--------+--------+
|
| data octets ...
+---------------- ...
User Datagram Header Format
The main task of this assignment is to implement a simplified version of RIPv1 in KENSv3. RFC1058 includes sections on distance vector algorithms, specifications for the protocol, and control functions. You will implement only the very basic parts of each section. The main difference between RIPv1 and the theoretic Bellman-Ford algorithm is the link cost. RIPv1 uses a hop count, while the latter arbitrary values. In the first part of this assignment, you will implement a simple case of RIPv1, where the link cost is uniformly set to 1.
RIPv1 uses the following format for its messages.
0 1 2 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1) | version (1) | must be zero (2) |
+---------------+---------------+-------------------------------+
| address family identifier (2) | must be zero (2) |
+-------------------------------+-------------------------------+
| IP address (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| must be zero (4) |
+---------------------------------------------------------------+
| metric (4) |
+---------------------------------------------------------------+
.
.
.
The portion of the datagram from address family identifier through
metric may appear up to 25 times. IP address is the usual 4-octet
Internet address, in network order.
Figure 1. Packet format
For the command field, you will implement only the following two types:
- 1 - request: a request for the responding system to send all or part of its routing table. It is broadcast to 255.255.255.255 only once when the routing protocol starts.
- 2 - response: a message containing all or part of the sender’s routing table. This message is sent in response to a request or upon a timer expiration in this assignment. In the former case, the response is addressed to the requesting host. In the latter case, the response is broadcast to 255.255.255.255.
Of course, the version is always set to 1 in this assignment.
The address family identifier field must be set to 2 in this assignment, which means the IP address is the usual 4-byte Internet IP address in network order.
The metric field must contain a value between 1 and 15 for reachable destinations and 16 for unreachable ones.
Once initiated, a node must broadcast a request. The first request will have the address family identifier set to 0, IP address set to 0, and the metric to 16. Then the node starts a timer. Upon a timer expiration, the node will send out a response. When the node receives a request, it sends out its distance vector table. When the node receives a response, it updates its distance vector table. All the IP broadcast packets in this assignment reach only immediate neighbors, as they are not routed beyond in KENSv3. Recall that every network interface has an IP address. A node with multiple links must have as many IP addresses as the number of links. The IP address assignments to nodes are in testrouting.cpp.
The following packet captures via WireShark will help you understand the above mechanics of RIPv1 in detail.
Note
We use host IP addresses in the address field of RFC. Yet the following packet capture pcap files use network numbers or subnet numbers for the destination field. Stick to host IP addresses.
- A reference to RIPv1 packet format: pcap packet capture log of a basic route exchange between two RIP v1 routers [src]: https://wiki.wireshark.org/SampleCaptures?action=AttachFile&do=get&target=RIP_v1
- A RIPv1 router periodically flooding its database. Capture perspective from R1's 10.0.1.1 interface [src]: https://packetlife.net/media/captures/RIPv1.cap
- RIPv1 routes are being flooded on the R1-R2 link. R2's connection to 192.168.2.0/24 goes down, and the route is advertised as unreachable (metric 16) in packet #5. Capture perspective from R1's 10.0.1.1 interface [src]: https://packetlife.net/media/captures/RIPv1_subnet_down.cap
Section 4 of RFC1058 describes administrative controls. In this assignment, you should implement only one control function used for correctness of your protocol implementation: ripQuery().
Size RoutingAssignment::ripQuery(const ipv4_t &ipv4);The ripQuery() call receives an IP address from the application layer. It should return the cost to reach the IP address. In RIPv1, the cost is just hop-count.
You have implemented RIPv1 for uniform link costs. Now for extra credit you will modify your implementation such that the link costs are integers in the rage of [1..20]. The upgraded RIPv1 implementation must have the following few modifications from the standard RIPv1:
- The metric for the distance vector routing algorithm is the sum of link costs, not the hop count.
- The cost for a link is in the range from 1 to 20.
- The maximum value for the metric is 300 (15 x 20). The numbers bigger than 300 mean unreachable.
To obtain link costs, you should use the portCost() method in RoutingAssignment.hpp.
Size RoutingAssignment::portCost(int port_num);The portCost() call receives a port number from your RIP implementation. It should return the link cost for the port number.
- Build: same as KENS (TCP)
- macOS/Linux (CLI):
./app/routing/routing - Windows (CLI):
app\routing\Debug\routing.exe - Others (GUI):
routing target
The testing script is in testrouting.cpp. It includes network topologies in the following figures.
