Project 2 - Longest Prefix Match

Project 2: Longest Prefix Match (LPM)

Assigned: 10/15/09, Due: 10/29/09

Project Goal

Internet prefixes were originally envisioned to belong to three classes: Class A, Class B, and Class C. That changed with the invention of Classless Inter-Domain Routing (CIDR), which allows prefixes in routing tables to be of arbitrary lengths. In this project, we will provide you with CIDR prefixes from one core router in the backbone of the Internet. Your task is to load up the prefixes in the form of a routing table and record 1) the time to construct the routing table, 2) memory required to hold it, 3) average lookup time to perform longest prefix match and 4) average time to update the routing table. Your program must be written in C/C++ and should work on the Burrow or Sharkestra Linux machines.

Project Specification

Your program, lpm, should take a plain-text file containing IPv4 prefixes and their corresponding next hop router addresses, one on each line, as its input. The steps you should follow in this project are:

Load prefixes longer than one bit and shorter than 31 from the input file in a specified data structure. Details on the data structures are in the next Section. This data structure is your routing table.
Record the time for the trie operations to construct the routing table using the RDTSC instruction. This instruction returns the number of clock cycles since the last CPU reset on Intel Pentium processors.
Record the storage requirements for the routing table.
Allow the user the option to judge the performance of 1) longest-prefix match, 2) routing table update, or 3) simply quitting the program.
If the user chooses the first option, request a plain-text input file containing destination IPv4 addresses, one on each line. Skipping any mal-formed IPv4 addresses, report on the minimum, maximum, mean, and median lookup time (trie operations only) for an IP address using the RDTSC instruction. Also print the results of your lookups, or if the IP address is not routable, print a message saying so. (however, printing time should not be included in your lookup time calculation).
Should the user choose the second option, request a plain-text input file containing IPv4 prefixes, one on each line. Skipping prefixes shorter than two bits or longer than 30, report on the minimum, maximum, mean, and median update time for loading a prefix (trie operations only).

Routing Table Data Structures

The basic version of the project requires you to implement one type of data structure for the routing table: binary trie.

Binary Trie: A binary trie allows consulting one bit of the destination IPv4 address bit at a time, requiring 32 lookups in the worst case. For details on binary tries, consult the IEEE Network Magazine paper from 2001, Survey and taxonomy of IP address lookup algorithms.

Program Output

Output the following statistics for each instance of routing table:

Total number of prefixes in the routing table
Number of prefixes outside of the specified lengths
Total time to construct the routing table. This time should include only the actual trie operations for inserting the prefixes into the table. It should not include file reading and parsing time.
Memory required to hold the routing table
Minimum, maximum, mean, and median time to perform a longest prefix match. These times should include only the trie lookup itself. It should not include time to read the input file, parse it, or print the results.
Minimum, maximum, mean, and median time to update an entry in the routing table. These times should include only the trie lookup itself. It should not include time to read the input file, parse it, or print the results.

Testing

The following three sample input files should help you in your testing.

Also, try testing these specific addresses for the following behaviors:

1.2.3.4 does not exist
84.205.69.7 added by the update
118.103.180.13 removed by the update
196.27.108.17 exists before and after the update, but answer changed
200.143.92.1 falls into two prefixes identical aside from length, make sure you get the correct answer (next hop 64.71.255.61)

Miscellaneous/Resources

The RTDSC instruction is not implemented as a C or C++ function directly. Instead it is an assembly language command that must be accessed using inline assembly. You may use the following code to define RTDSC:
#define rdtsc(x) __asm__ volatile ("rdtsc" : "=A" (x))
This defines RDTSC as a macro in C or C++. This code is not compliler independant, but will work with gcc on the CS Linux machines. Refer the sample rtdsc.c for a simple program that uses this macro.
There is not a good direct way of measuring your routing table memory usage within the program. Instead, you should measure it in an indirect way. Keep track of how many nodes are contained in your trie, and measure the size of a trie node, and you can calculate the memory usage of the trie.
Sections 2 and 3 of the following research paper can be helpful in planning various implementation-related components of your project: http://www.cs.indiana.edu/~minaxi/pubs/ipv607.pdf.

Extra Credit

For 10% extra credit, implement multibit trie.

Multibit Trie: A multibit trie allows consulting multiple bits of the destination IP address at a time, with number of lookups depending on the stride of the trie. Each parent node can choose the stride for each child independent of what any other node chooses. For simplicity, implement only a fixed-stride multibit trie where each stride is of length two. For details on binary tries, consult the IEEE Network Magazine paper from 2001, Survey and taxonomy of IP address lookup algorithms.

Deliverables and Grading

The grading will be based on the following four deliverables. The Status Report is due, Thursday October 22, 2009 in class. The remaining deliverables are due by 11:55 pm on the due date.

Status Report: Prepare a power point presentation that describes your Binary Tree data structure and C or C++ primitives that will be used to implement them . Each group will present their status report will be made in class on Thursday, October, 22.
Project report: Prepare a 2-page report detailing your implementation. The report should contain implementation details of each data structure used to build the routing table and any steps you took to make it efficient. Be sure to state any assumptions you made in your program and all of its known limitations, including portions that are not implemented or do not work correctly. The report should use a 10-point font, with margins on either of the four sides not exceeding 1 inch. Submit the report in pdf format with your code (more details below). No other format, e.g., doc, will be accepted. Also, print your project report double-sided and bring the hard copy to the demo.
Code submission and demo: Submit your code, and project report files as a single archive file (.tar or .tar.gz file formats only) via OnCourse. The demo slots will be posted by the AIs on the Web board soon after the submission deadline. Schedule an appointment with them to demonstrate your project. Failure to attend your scheduled demonstration timeslot will result in a 10 point reduction in your grade. Each group is required to complete a demonstration in order to receive credit for the project.
Partner evaluation: Evaluate your project partner. Send your evaluation to the email address. Failure to submit a partner evaluation by the project submission deadline will result in a 10 point reduction in your grade.