CS640 Programming Assignment 2: Packet Forwarder

Due: November 19, 2009 at 6:00 pm

1. Description

For this programming assignment you will create a packet forwarder which delivers packets between blaster(s) and blastee(s) you created for the first programming assignment. Your blaster and blastee will have additional requirements to support the forwarder.

The packet forwarder will receive a packet, decide where it is to be forwarded, and, based on the packet priority level, queue it for sending. Upon sending, you will delay the packet to simulate link bandwidth, and randomly drop the packet to simulate a lossy link.

There will be three priority levels, and there will be a separate sending queue for each priority level. Each queue will have a fixed size, defined in the number of packets. If the outbound queue for a particular priority level is full, the packet will be dropped. Higher priority packets are always forwarded before lower priority packets.

As with the first programming assignment, you are to work in two person teams and write your code in C or C++ using the Linux workstations in 1350, 1351 or 1370 CS. You may also use WAIL to test your assignment (use "FC6-STD" as your OS).

2. Details + Requirements

2.1. Forwarding Encapsulation

In order to implement priority levels and forwarding, you will encapsulate the packet type from programming assignment one inside a new packet.

(New Packet)
  --------------------------------------------------------------------------- ... --
 | 8 bit   | 32 bit src | 16 bit src | 32 bit dest | 16 bit dest | 32 bit | payload |
 |priority | IP address |  port      | IP address  |    port     | length |         |
  --------------------------------------------------------------------------- ... --
                                                                         /         /
                                                                /                 /
                                              /                                   /
                                   /                                             /
                              ---------------------------------------- ... ------
                             |    8 bit    |  32 bit  | 32 bit | variable length |
                             | packet type | sequence | length |     payload     |
                              ---------------------------------------- ... ------
			      (Packet from Programming Assignment #1)

Essentially, you are adding an 8-bit priority, a 32-bit source IP address, a 16-bit source port, a 32-bit destination IP address, a 16-bit destination port and a 32-bit length to the front of the packet layout from programming assignment #1. Compare this with how UDP datagrams are encapsulated inside IP datagrams (which are then encapsulated in a layer 2 protocol, such as ethernet).

Valid values for priority levels are:

1. 0x01 - highest priority
2. 0x02 - medium priority
3. 0x03 - lowest priority

END packets always have priority level 0x01. DATA packets may be any one of the three priority levels.

2.2. Logical Functions of Forwarder

The logical functions of the forwarder consist of routing, queueing, sending, and logging. Each sub-function is detailed below.

The logical functions depend on the static forwarding table provided to the program through a file. The file should contain lines in the format below, with space as delimiter between the various fields:-

<forwarder> <destination> <nexthop> <delay> <loss probability>

• forwarder is a "<IP Address> <Port>" pair that identifies the forwarder for which the current entry is associated with,
• destination is a "<IP Address> <Port>" pair that identifies the destination blastee of the packet,
• next hop is a "<IP Address> <Port>" pair that identifies the next entity to forward the packet to,
• delay value is in milliseconds, and
• loss probability is in percentage.

The routing function is based on a static forwarding table that you provide to your program through a file as described above. The destination of an incoming packet is compared with destination in the forwarding table to find a match. If a match is found, the packet is queued for forwarding to the next hop. If a match is not found, the packet is dropped and the event is logged (see logging requirements below).

The queueing function should examine the priority field on the packet and place the packet in the appropriate queue. All the three queues are of fixed size, defined in the number of packets. This queue size is specified on the command line to the forwarder at start up. If a queue is full, the packet is dropped and this event is logged (see logging requirements below).

The send function accepts packets from the three queues defined above and simulates network link conditions for each destination. Packets bound for a destination are first delayed to simulate link bandwidth. The delay is defined in the forwarding table and is specified in milliseconds. After a packet has been delayed, it may be dropped to simulate a lossy link based on the loss probability provided in the forwarding table, and the event is logged (see logging requirements below). If a packet is not dropped, it is then passed to the network.

The logging function is integral to all functions of the forwarder. A packet may be dropped in the forwarder in the routing function, the queueing function, or in the send function. Any and all packet drop events must be logged to a file. Loss events must provide a textual reason for the loss (e.g., "no forwarding entry found", "priority queue 1 was full", "loss event occurred.") Each log event must include the source IP address and port, the intended destination IP address and port, the time of loss (to millisecond resolution), the priority level of the packet, and the size of the payload.

2.3. Forwarding Summary

The order of processing should be similar to the following (note that logging is not an explicit part of this sequence):

1. receive packet from network in a non-blocking way,
2. decide whether packet is to be forwarded by consulting the forwarding table,
3. queue packet according to packet priority level if the queue is not full,
4. if a packet is currently being delayed and the delay has not expired, goto Step 1.
5. if no packet is currently being delayed, select the packet at the front of the queue with highest priority, remove that packet from the queue and delay it,
6. when the delay expires, randomly determine whether to drop the packet,
7. otherwise, send the packet to the proper next hop.
8. goto Step 1.

2.4. Specification

The forwarder should be invoked in the following way:

 forwarder -p <port> -q <queue_size> -f <filename> -l <log>

 blaster -f <f_hostname> -g <f_port> -i <priority> 

 ~cs640-1/handin/<CS_USERNAME>/P2