Computer Laboratory > Teaching > Course material 2009–10 > Building an Internet Router > Schedule (SW) > Basic Router

 

Basic Router

Overview

The first stage in the development of the software for the router is to develop a functional skeleton router completely in software. You will be using the Virtual Network System (VNS) located at Stanford to emulate your network topology and to give you access to traffic on the Internet. If you don’t have experience working with VNS you should familiarize yourself through the link above as the VNS is used heavily throughout the module.


Please do NOT approach Stanford for VNS acccount information - this will be provided through your Cambridge lecturer and module demonstrators.


After groups have been confirmed each group will be provided with VNS topology pack. This will be done in the first scheduled laboratory slot, Tuesday 13th October.

Getting Started

Become familiar with this initial, simpler, router assignment. The requirements for the software router you will be building in this module are a superset of those for this simpiler router. You will need to download the project code available here.


Overview of the Project Code

The project code provides the foundation on which you will build your router. It communicates with the VNS to read packets from the network, send packets from you to the network, and to get the interface information for your router.

The first file you will want to get familiar with when going over the project code is sr_integration.c. This file contains the definitions for the interface functions between your code and the provided code. You should extend these functions (with the possible exception of sr_integ_low_level_output(…)) to interface with your router implementation.

The integration methods work by accepting a pointer to the router’s state as the first argument. The core state of the router (which includes information needed by VNS) is held in struct sr_instance and defined in sr_base_internal.h. A global singleton instance of struct sr_instance is held in sr_base.c. This is the instance passed to the methods in sr_integration.c and can also be accessed by calling get_sr().

You must create a struct for your router’s state (routing table, ARP cache, interface list etc.) and register it with the global instance. You can do this as follows:

  • Create a new file (say router.h) and define a struct (say struct sr_router) that will be used to hold the state of your router.
  • Modify the method sr_integ_init(…) in sr_integration.c to register your struct with the the global instance. The code should look something as follows:
    struct sr_router* subsystem = (struct sr_router*)malloc(sizeof(struct sr_router));
    assert(subsystem);
    sr_set_subsystem(get_sr(), subsystem);
  • Anytime you have a pointer to the global instance you can retrieve a pointer to your subsystem as follows:
    struct sr_router* subsystem = (struct sr_router*)sr_get_subsystem(sr);

Simplified Program Flow

Once compiled and run, the project code will connect to the VNS, attempt to connect with the named topology, read the interface information for the router and start reading packets to the router from the network. The most important steps of the process are enumerated below.

  • Start the sr binary. To connect it to a VNS topology, just run the sr with the single argument -t followed by the number of the topology you were given (above.) It then connects to your topology on VNS.
  • main(…) starts the low level networking subsystem (which spawns a thread for itself) and starts a thread that you will extend to be a user level application in the future.
  • The core of the router is initialized
  • sr_integ_init(…) is called
  • VNS is contacted and the host and topology are reserved
  • The interface information is read from the VNS. For each interface, the method sr_integ_add_interface(…) is called. You should extend this method to copy the interface information into your subsystem. It is up to you to decide the best method for handling interfaces.
  • sr_integ_hw_setup(…) is called signaling that all the interface information has been read. You may use this function for any additional setup (such as creating the default routing table) and/or debugging.
  • For each packet destined to your router on the network, sr_integ_input(…) is called. This is where packets enter your system.
  • For each forwarded or generated packet to be placed on the network you must call sr_integ_low_level_output(…).

Basic Requirements

Your router must support the following functionality. Note that some of the features under the forwarding heading are beyond what was originally required for the initial router assignment above.

  • Your code can be compiled and run on any nf-test OR SW02 machine in the Computer Laboratory
  • IP
    • Check incoming IP packets for validity. Incoming IP packets must be version 4, have no options, must not be fragments and have a valid checksum.
    • TCP packets addressed to the router should be forwarded to the TCP stack by calling sr_transport_input(…) defined in sr_lwtcp_glue.c. The router’s provided CLI will then process the packet.
  • Forwarding
    • A dynamic forwarding table that can be modified at runtime by multiple threads
    • Longest prefix match
    • Decrementing the TTL in the IP header and recalculating the checksum
    • You should support a next hop route of 0.0.0.0 which denotes that the next hop is equivalent to the destination. This is useful for subnets directly connected to interfaces.
    • Entries in the routing table should be marked as either static (specified by the input routing table) or dynamic (determined dynamically by PWOSPF in a later assignment).
  • ARP
    • Responding to ARP requests
    • Issuing ARP requests and queueing packets pending the replies
    • An arp cache of MAC/IP pairs that can be modified at runtime by a seperate thread safely
    • The addition and deletion of static ARP cache entries.
  • ICMP
    • ICMP host unreachable to packets that don’t respond to ARP requests
    • ICMP time exceeded to forwarded packets whose decremented TTL is less than 1
    • ICMP echo request in response to an ICMP echo reply addressed to one of the router’s interfaces
    • ICMP no route to host if route does not exist in routing table
    • ICMP protocol not supported (unreach prot) should be returned if the transport layer is not TCP.
  • Complete Command-Line Interface Stubs
    • Complete all functions in cli_stubs.h - these are essentially interfaces to pieces of your router as required above. Feel free to define these stubs wherever you like (preferably with related code; they are currently grouped into cli_stubs.h since you have to build the related router code yourself).
    • Complete code in cli.c wherever you find the text not yet implemented. This includes show commands which requires you to create a string representation of your router internals, setting the IP and mask of an interface, and performing a ping. You may use cli_send_str to send text back to a client connected to the CLI.
    • You do not have to implement cli_traceroute though it might be helpful later. You do not have to implement OSPF-related methods until the PWOSPF assignment later in the module.
    • You can login to the CLI by running sr and then telnetting to port 2300. Learn about the commands available on the CLI by connecting and then typing help. To learn about a specific command, try help <COMMAND>.

Integrating with the TCP Stack

The project code contains a functional TCP stack which is a modified version of the TCP portion of Adam Dunkel’s lwip stack. To integrate with the IP stack you must extend the following functions defined in sr_integration.c.

  • sr_integ_findsrcip(…) given a destination IP, return the correct source address based on the current routing table. If none exists return 0.
  • sr_integ_ip_output(…) called by the TCP stack whenever it needs to send out an IP packet. The router must add the IP headers and forward the packets.

A Few Comments

  • This basic router will provide the foundation for the rest of the project. Design it well! The real testimony of a good design is that it gracefully handles testing, maintanence and the addition of new components.
  • Browse through the rest of the software milestones to get a feeling for the functionality you will need to support by the end of the quarter.
  • Be sure to design your router such that it can be accessed by multiple threads safely and efficiently.
  • You will be adding support for a router-to-router protocol in the future. This means your design should support a thread-safe and dynamic routing table. Getting this wrong can make the later stages of the project very difficult.
  • You must create new threads with sys_thread_new(func,arg); (defined in lwip/sys.h) instead of pthread_create or lwtcp will not work properly.

Deliverables

Week 1: Clear, concise design document. This should be emailed to the tick-submission email address for this subject. We would also suggest this document be available online - perhaps as a google doc? - allowing for continuous update and revision. We want to be able to determine:

  • The modularity level of your router
  • How you plan on handling thread issues for accessing the router
  • Your implementation plan for the following subsystems:
    • Routing table
    • ARP (cache and queue)
  • A clear overview of packet flow through your router - a bulleted list will be fine. You may present packet flow for multiple scenarios (e.g., locally addressed packets, forwarded packets, bad packets).
  • Your testing strategy (adding testing hooks or stubs is encouraged!)
  • Any additional support you plan to add for debugging
  • You will need to convince us that your design will do the following:
    • Elegantly handle extension
    • Thread-safe
    • Efficient

Please note that this document is not binding! It is alive and will change throughout the life of the project. You will want to maintain this section as your design changes based on lessons learned during implementation. Be sure to keep your design document up to date. It is our window into your router and if it is not consistent with your implementation we can only assume your implementation is incorrect.

Week 2: Your Completed Router. We will test your implementation in a number of ways including but not limited to:

  • Pinging each of the router’s interfaces
  • Sending TCP packets to your router
  • Tracerouting through (and to!) your router
  • Downloading a large file through your router