Programming Assignment 1: IP Lookups using Multi-bit Trie

CS 636: Spring 2009

Programming Assignment 1 : IP lookups using a multi-bit trie.

Deadline : Feb 19th -- 11:59:59pm

There are two portions for this assignment.

Code [75%]
Analysis [25%]

Code

Implement the IP lookup algorithm using multi-bit tries we have discussed in the class using a program (in C, Java, or C++). The value of m, range from 1 to 8, should be a command line argument.

The input to the IP lookup algorithm is a database that has the fields <ID, prefix, mask, next hop> one per line. The goal is to input this database and store it in a fashion such that it is amenable towards fast lookups.

Here are three files provided:

Sample Database

Sample input

Sample output corresponding to the input.

The command line input should like the following.

iplookup -d <database file> -i <input file> -o <output file> -m <stride size>

While I do not care about the language you choose to implement your algorithm, I want to care about the amount of time it takes to output your results. To promote the use of efficient data structures, I would do the following. I will award 10 extra points for the submission that has the best timing among all the submissions for a test suite, different than the one that I am giving you as a sample input.

This assignment will count 10% towards your grade.

Analysis

I would want you to vary the number of bits used in the multi-bit trie to study the tradeoff between memory usage and time complexity.

In particular, I would expect you to generate a graph, with the x-axis showing the number of bits used and two y-axes one involving time complexity and the second involving memory usage.

Memory usage can be measured using the top command, while the time complexity can be measured using the unix time command.

Discussions and Help

The TA is a good source of help for this assignment. I also encourage discussion on the blackboard discussion board in case you have questions. The TA will be able to post some answers for public use.

POLICY : Please no cheating or downloading any IP lookup algorithms publicly available. It will not be worth your cause and would lead to a reduced overall grade in the course. The assignment is also an individual one and no sharing of code is allowed.