Computer Laboratory

Course pages 2013–14

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 mininet network emulator in the first four weeks of the project to allow you to develop, test and debug your software without the extensive resource requirements that doing so on a real network would require.


Getting Started

Become familiar with this initial simple-router assignment, targeted at undergraduate students. The requirements for the software router you will be building in this module are a superset of those for this simpler router.


Mininet Topologies

When evaluating your program, you shall be using the three topologies inside the course's github directory: forth, tyne and humber.


Overview of the Project Code

The project code provides the foundation on which you will build 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 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.

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 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.

  • At first you have to compile your software. Go inside your SW_stub directory and run: $ make.
  • Then, you need to run a topology: $ sudo python ~/P33/sr_topologies/{name of topology}.py.
  • Open routers and the hosts terminals (i.e., "> xterm r0 h0 h1").
  • Inside the r0 run the SW_stub for the router: # ./sr -z r0 -r rtable.conf -i cpuhw/cpuhw_*
  • 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
  • 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 inside any mininet host configured in the manner of CaMT.
  • 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 directory - these are essentially interfaces to pieces of your router as required above.
    • 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 telnet {your_router_port_IP_address}. 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 module.
  • 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.

Checkpoints

Less deliverables and more guidance to ensure you don't fall behind....

Week 1: Write Clear, concise design document. 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