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>

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>
The packet forwarder must implement the routing, queueing, sending, and logging logical functions described above.

Note that the following requirements for your blaster and blastee are in addition to requirements stated for programming assignment 1.

You will have to modify your blaster to add the following additional commandline options:

 blaster -f <f_hostname> -g <f_port> -i <priority> 
The behavior of the blaster should be modified to increment the sequence number by 1 for each packet, instead of by the packet length.

You will have to modify your blastee to:

  1. retain statistics for each blaster it receives packets from,
  2. verify that the destination IP address is indeed its own IP address,
  3. suppress display of individual DATA packet information,
  4. indicate the number and the percentage of packets lost, on receiving an END packet, in addition to the statistics from programming assignment 1, and
  5. not terminate on the receipt of an END packet, since multiple blasters can send packets to the blastee.

The executable program names must be "blaster", "blastee" and "forwarder". You also must supply a makefile with your source code to produce these binaries. The source code file names are up to you.

3. Advice

Get started early, read this description carefully and ask questions. The advice from the first programming assignment to "start small" applies to this project.

4. Grading

It is essential that you follow the required packet format and output specification so that your programs can interoperate with our grading versions. To turn in your code, copy your code to the directory

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

Grading will be according to the following schedule:

Points Requirement
20 Your source code compiles and it is clear from the source that you are not just compiling "helloworld.c". (Something compiles, but that's about it.)
20 Packets get forwarded from blaster to blastee through one or more forwarders, but not necessarily according to the forwarding table.
5 Blaster sends packets with forwarding header.
10 Packets get forwarded according to the forwarding table.
5 Blastee verifies packets it receives are actually meant for it.
10 Loss probability can be specified at the packet forwarder; packets get dropped according to that rate.
10 Packets get dropped if queues are full.
10 The blaster sends packets with a priority level; forwarder handles priorities correctly.
10 Delay can be specified and works correctly.
5 The blastee keeps statistics and print logs correctly.
5 The forwarder prints logs correctly.