IP Routing

Overview

You currently have a four-port non-learning switch. The goal of this part is to overhaul the Output Port Lookup module to implement an IP router as per RFC 1812. You will be doing this in a number of steps over the next several weeks.

As an IP router, your system (hardware plus software) must do the following:

• Forward IP packets to the next hop router (according to a longest-prefix match of the destination address in a route table).
• Exchange route information with adjacent routers according to the PWOSPF protocol. This information is used to construct the route table that is used when forwarding IP packets.
• Implement ARP to determine the MAC address of a next-hop IP address when that MAC address is not already known (and store it in a local table).

Required functionality in more detail

The hardware comonent of the router must:

• provide a route table that can store at least 32 IP address/prefix pairs with their associated port and next-hop IP address. The route table must be accessible by the software via register reads and writes.
• use the route table to perform a longest prefix match on destination IP addresses and return the appropriate egress port (or none) and next-hop address (or 0.0.0.0 for a directly attached destination)
• provide an ARP table that can store at least 32 entries. This will accept an IP address as a search key and will return the associated MAC address (if found). This table is created and modified by the software (which runs its own ARP protocol) via register reads/writes
• provide a “local IP address table” that can store at least 32 entries. This will accept an IP address as a search key and will return a signal that indicates whether the correspond address was found. This table is used to identify IP addresses that should be forwarded to the CPU.
• decode incoming IP packets and perform the operations required by a router. These include (but are not limited to):
  • verify that the existing checksum and TTL are valid
  • look up the next-hop port and IP address in the route table
  • look up the MAC address of the next-hop in the ARP table
  • decrement TTL
  • calculate a new IP checksum
  • transmit the new packet via the appropriate egress port
  • local IP packets (destined for the router) should be sent to the software.
  • PWOSPF packets should be sent to the software.
  • any packets that the hardware cannot deal with should be forwarded to the CPU. (e.g. not Version 4 IP)
• Provide counters for the following:
  • ARP misses
  • LPM misses
  • Packets sent to the CPU/software
  • Packets with IP options
  • Packets with bad IP checksums
  • Packets with bad TTLs
  • Non-IP packet received
  • Packets forwarded by the router (not sent to CPU)
  • Packets with a bad Ethernet destination address
  • Packets sent to CPU matching one of the addresses in the local IP address table (register name is filtered)
  • ARP packet received (Please remove this register after the first deliverable)
  • OSPF packet received (Please remove this register after the first deliverable)

Do not use the CAM device provided by the Xilinx Coregen tool to implement any of the tables. You must implement your own lookup mechanism

The objective is for the hardware to process all regular IP packets without requiring intervention from the software. Packets should only be forwarded to the software in the following instances:

• they are incorrect (bad TTL, version, etc)
• some information is missing (no MAC address found in the ARP table)
• they are explicitly destined for the software (ARP, PWOSPF, IP address is same as router’s…)
• the packet is of an unknown type (not IP or ARP)

Note: You should follow the register map provided by this XML file. To use this file, copy the file into the project’s include directory: projects/<project>/include   You need to add the reference_op_lut to the project.xml file in the UDP section. Add the line in bold below:

    ...
    <nf:group name="udp">
      <nf:instance name="in_arb" />
      <nf:instance name="router_op_lut" />
      <nf:instance name="strip_headers" />
      <nf:instance name="output_queues" />
    </nf:group>
    ...

How-to guide: a suggested procedure for getting from A to B

• Understand the Internet Protocol, and how a router makes a decision about forwarding an IP packet based on its route table.
• Review the packet structure of an IP packet - see the Network Sorcery site if you are not sure.
• Develop a new verilog module that parses an IP packet. Your module (and sub-modules) should perform all of the necessary operations that an IP router would perform on an ordinary packet.
• Your router will need to provide ARP functionality. This should be implemented in software. The software will construct the ARP request packet and forward it to the network via the NetFPGA/VNS protocol. The hardware should simply decode ARP packets and forward them to the software via the NetFPGA/VNS protocol implemented earlier.
• Your router needs to forward PWOSPF packets to the software. You have a choice as to how the hardware accomplishes this:
  • Add an extra packet decode section to decode the IP address used for PWOSPF packets and always forward them to the software.
  • Implement the Destination IP Filter table (ROUTER_OP_LUT_DST_IP_FILTER_*_REG)—any packets with IP addresses matching entries in this table should be forwarded to software

Deliverables

Implement basic packet counter registers
(Due Wed, Oct 28, 2009)

Implement the following three basic packet count registers: IP packets, ARP packets, and OSPF packets. You should create all registers required in the final deliverable of this part but just tie the currently unused ones to 0. (Your design should still be a non-learning switch.)
Written/drawn design of the Output Port Lookup module
(Due Wed, Oct 28, 2009)

Study the remaining deliverables in this section. Design on paper the major functional blocks needed to implement this functionality. The design should show the major functional blocks/sub-modules and the dataflow between these modules. Please use a diagram to show the dataflow between modules and include a brief written description of the purspose of each module. This should be added to your hardware design document and should be one to two pages in length.

As an example, you may implement a Packet Classification block. A suitable descpription is:

Packet Classification: Classify each packet processed by the Output Port Lookup module. Inspects the Ethertype and IP version and protocol fields to identify IPv4, ARP and OSPF packets.

Forwarding path to/from software and TTL/Checksum verification and update
(Due Wed, Nov 4, 2009)

Implement code that verifies the TTL and checksum of all IPv4 packets. If the TTL and checksum are valid, then decrement the TTL, update the checksum and forward the packet out the same port that it arrived on. (This behavior will change soon.) If the TTL or checksum are invalid then forward the packet without modification to the CPU.

Note that the presence of IP options complicated the checksum calculation process as the options increase the length of the IP header. IP options are rarely used in the internet today&msdash;as a result you should forward all IP packets with options to the software for processing. This allows the hardware to handle all regular packets at high speed without requiring complicated logic to deal with variable-length IP headers.

Forward all non-IP packets to the CPU. Packets sent to the CPU should not be modified.

Implement code that forwards all packets from the CPU to the corresponding Ethernet port. Packets from the CPU should not be modified when forwarded to an Ethernet port.

Note: You should remove the ARP and OSPF packet counters from this deliverable and all future deliverables.

Updated hardware design document (verification section)
(Due Wed, Nov 4, 2009)

Add a verification section to your hardware design document explaining how you will test your design (eg. what sorts of tests will you run. How will you test the hardware etc.)

Verification of MAC addresses/lookup in local IP table
(Due Wed, Nov 11, 2009)

You should have implemented a set of registers that allow the MAC addresses of each port to be specified. Verify that the MAC address of all incoming packets either matches the MAC address assigned to that port or is a broadcast address. (Broadcast MAC addresses are indicated by a 1 in the LSB of the first byte of the MAC address.) Packets that do not meet this requirement should be silently dropped.

Implement a table that allows a set of IP addresses to be specified that should be forwarded to the CPU (the “local IP address table”). Lookup the destination IP address of all IP packets in this table. If a match is found in the IP table then forward the packet to the CPU (without modification). If a match is not found, proceed with the normal forwarding path (eg. verify/update TTL and checksum and send to CPU/output as appropriate).

Hardware design document — Router interoperability testing
(Due Wed, Nov 11, 2009)

Add a section to your hardware design document outlining how you intend to test the interoperability of your router with the other groups.

Working router (tested interoperability with software)
(Due Wed, Nov 18, 2009)

Implement all remaining functionality, including the routing table and ARP table. Verify that your design works correctly your group’s software.

Fully working interoperable router
(Due Wed, Nov 25, 2009)

Your fully-operational router should interoperate correctly with the routers from the other groups. We will conduct an interoperability test session in which all groups will have to demonstrate the correct operation of their routers in a test topology under a number of failure conditions. A date/time for this session will be announced.

The deliverables from this step are:

• The bit file for your router. At this stage you should have implemented all of the registers described in the Register Specification. We will use the bit file to verify that you have achieved the Required Functionality described above. We will not attempt to debug your hardware!
• An updated Hardware Design Document with:
  • Updated Verification section. You must show which tests pass on your current design. Each test must give the test directory in which that test is actually performed.
  • Register description.
  • Description of each table (IP addresses, routes, etc).
• A tarball of your design directory (with src, synth, verif). We will check a few of your tests against the bit file you supply.