Computer Laboratory

Course pages 2012–13

Building an Internet Router

Principal lecturer: Dr Andrew Moore
Taken by: MPhil ACS, Part III
Code: P33
Hours: 16 (1 introductory lecture + 8 × two-hour supervised laboratory slots)
Prerequisites: Undergraduate courses in digital communication, good working knowledge of C/C++, ECAD, Unix

Aims

This module requires the full design, implementation, testing and inter-operability of a complex hardware and software system.

Syllabus

This subject is lab-centric and project-based. The first class is the only scheduled lecture. During the term, groups of two or three students will work together to develop a fully functional IP router. The groups will consist of at least one student familiar with designing hardware in Verilog and one student who is comfortable writing large, system-level network programs in C. Students will be paired by area on the first day of class.

The hardware uses the NetFPGA boards which provide a programmable hardware platform for developing network equipment. Given the Verilog HDL code for a simple four port switch the hardware designer will extend/modify/discard this code to provide the functionality of a four-port IP router. A set of tools are provided to assist the student with design, verification and synthesis.

Each group will:

  • design and implement a router in 8 weeks,
  • an inter-router protocol (PW-OSPF),
  • show router interoperability with other groups, and
  • extend the basic router with new features (e.g., Firewall, NAT, Fairly-resourced Output queues, Packet capture, Traffic generator).

Objectives

On completion of this module, students should be able to:

  • Describe what responsibilities a user-level application, operating system, or device driver has in communication. (For example, a web browser talking to a web server)
  • Identify the challenges inherent in efficiently transferring data from the general-purpose machine to the network peripheral.
  • Compare and contrast a network interface built with an embedded processor versus dedicated (fixed) hardware on the basis of design time (up-front expenses), manufacturing cost (per-unit), performance, functionality, etc...
  • Explain how the OSPF routing protocol enables communication when presented with a new network topology
  • Describe how the spanning tree Ethernet protocol prevents circular paths from developing in computer networks.

By the end of this course, students choosing to focus on network hardware will be able to:

  • Create an FPGA-based hardware router that implements longest-prefix-matching lookups
  • Explain the required functions that the hardware router must provide to enable basic network functionality
  • Determine which functionality should be implemented in hardware versus software
  • Evaluate different implementations that can achieve the basic functions
  • Optimize their FPGA design for both logic (device utilization) and performance (network throughput)
  • Integrate the hardware router with control software being co-developed by other group members

By the end of this course, students choosing to focus on network software will be able to:

  • Create a program that controls and manages the hardware router being implemented by other group members
  • Explain the required functions that the router must provide to enable basic network functionality
  • Determine which functionality should be implemented in software versus hardware
  • Design a control program using the Virtual Network System that participates in the PW-OSPF dynamic routing protocol and responds to ARP and ICMP messages.
  • Design a control program using the Virtual Network System that exports a command-line interface and allows a user to inspect and modify the state of the hardware router.
  • Integrate the control program with the hardware router being co-developed by other group members

Coursework

Not applicable – course consists entirely of the assessed practical work.

Practical work

Two supervised laboratory slots are scheduled per week; however, additional laboratory work will be required to complete this project. In addition to ad-hoc availability, each group will have one-on-one time with the lecturer for a fixed slot each week to track progress.

Additional time is provided both for small-group tutorials on specialist skills, not present in all the incumbent students. Precise material to be covered is heavily dictated by the students on the course but material has included: perl, unix, make, advanced verilog, digital design including metastability issues, software timer loops, protocol implementation, Dikjstra's algorithm, along with using debugging tools such as gdb and modelsim.

Deliverables are due at the end of each week; exact details of dates and mechanism will be provided at the time of the module.

  • [Week 1] Develop a functional router in software.
  • [Week 2] Develop a functional router in software (continued), Adding a command line interface to your router.
  • [Weeks 3 and 4] Develop router-router protocol in software router.
  • [Week 5] Add Hardware control to router.
  • [Week 6] Advanced feature development and router interoperation.
  • [Week 7] Develop advanced functionality.
  • [Week 8] Software: Finish advanced functionality.

Full details are given on the course web page.

Assessment

This subject is marked 0-100; 60 is the pass mark.

Recommended reading

Strazisar, V. (1979). How to build a gateway.
Postel, J. (ed.) (1981). Internet protocol.
Baker, F. (ed.) (1995). Requirements for IP Version 4 Routers.
Comer D. (2006). Internetworking with TCP-IP, Vol. 1.

Other:

Comer, D. & Stevens, D. (1995). Internetworking with TCP-IP, vol. 2. Prentice Hall (3rd ed.).
Peterson, L.L. & Davie, B.S. (2007). Computer networks: a systems approach. Morgan Kaufmann (4th ed.).
Varghese, G. (2005). Network algorithmics. Morgan Kaufmann (1st ed.).

Note:

P33 Building an Internet Router cannot be taken in conjunction with L21 Interactive Formal Verification or R211 Biomedical Informatics in 2012-13.