Introduction to JailPT2's IP Project!

This project is an implementation of IP pipelines in Go. The project is split into two parts, the first being the IPStack, which is a library that implements the IP pipeline, and the second being the vhost and vrouter, which are the two nodes that are used to test the IPStack.

Because the vhost and vrouter are so similar, we maintain most of the logic within the IPStack in which the vrouter and vhost call when necessary.

Abstractions

IP Layer and Interface abstraction

Using these two structs and two data structures below, we abstract for the interfaces into the IP layer:

// structs
type Interface struct {
    Name     string
    IpPrefix netip.Prefix
    UdpAddr  netip.AddrPort

    Socket    net.UDPConn
    SocketChannel chan bool
    State         bool
}

type Neighbor struct {
    Name    string
    VipAddr netip.Addr
    UdpAddr netip.AddrPort
}

// data structures
var myInterfaces []*Interface
var myNeighbors = make(map[string][]*Neighbor)

The interface struct holds the UDP socket used for sending and receiving data over a particular interface, abstracting its low-level Link Layer into a Socket. The IP stack then populates the myInterfaces slice with every interface defined for the node to store and access its interfaces.

The Neighbor struct represents "endpoints" of the Link Layer from a particular interface, where, in our case, the "endpoint" is the UDPAddr of the neighbor. The myNeighbors maps each interface to a slice of neighbors, abstracting one end of an interface's Link Layer to all possible endpoints (Neighbors) on the other side of the switch.

In this way, if the IPStack needs to send a packet to a particular neighbor, it must iterate over every interface and check if the neighbor is in the slice of neighbors for that interface. But, more often than not, we know the interface to receive or send on, so finding the neighbor to communicate with doesn't require an iteration over all interfaces.

vrouter/vhost and ipstack abstraction

The ipstack offers an API to nodes to abstract the large amounts of similar code that different types of nodes share. The API is as follows:

// functions
func Initialize(lnxFilePath string) error
func RegisterProtocolHandler(protocolNumber uint8) bool
func SendIP(src *netip.Addr, dest *Neighbor, protocolNum int, 
        message []byte, destIP string, hdr *ipv4header.IPv4Header) (int, error)
func InterfaceUp(iface *Interface)
func InterfaceDown(iface *Interface)
func Route(src netip.Addr) Hop
func SprintRoutingTable() string
func SprintNeighbors() string
func SprintInterfaces() string
// ... other getters not shown

// constants
RIP_PROTOCOL
TEST_PROTOCOL

In general, to correctly use the API, the node must: 1) First, call initialize to setup the IPStack data structures. 2) Then, call RegisterProtocolHandler(X_PROTOCOL) to subscribe to a protocol. 3) After that, depending on the node's needs, use other API functions to interact with the IPStack.

The only protocols that are currently supported are the TEST_PROTOCOL and RIP_PROTOCOL, as given by the constants. To add more, like TCP_PROTOCOL, the current best way is to implement them in the IPStack.

In our case, vhost will subscribe to ONLY the TEST_PROTOCOL, while vrouter will subscribe to BOTH the TEST_PROTOCOL and RIP_PROTOCOL.

The other API functions allow for more specific actions within vrouter and vhost, such as Route, SprintNeighbors, SendIP, (and all getters). The REPL inside a node is expected to use these functions to implement its REPL commands.

For vhost and vrouter, we use the API's functions to implement the following REPL:

li: List interfaces
lr: List routes
ln: List available neighbors
up: Enable an interface
down: Disable an interface
send: Send test packet
q/exit: Quit program

Note: we originally planned to also incorporate the REPL into either the IPStack or separate API, but due to time constraints, we have the REPL in the VRouter and VHost. For TCP, we will consider abstracting the REPL in this way.

Thread Design

Main routines are clearly distinguished by the function name, ending in Routine (e.g. InterfaceListenerRoutine, ManageTimeoutRoutine, etc.). These main routines are defined as having "forever" loops, repeatedly executing the same task in succession.

There are cases where we can spawn wait-free threads doing parallelize actions for every element in a loop, but it's not worth to have this our implementation. We simply use threads to avoid blocking conditions or update something consecutively.

The main routines are discussed below.

Listener Routine

Each interface needs a listener routine to ensure that the node acts when it receives a packet on any interface. Hence, this routine should be setup for each interface. It hangs on an interface's UDP socket, then calls RecvIP upon receiving a packet. RecvIP beings the pipeline of corresponding function calls, based on the packet.

There is some added complexity with the listener thread interacting with the state of the interface (up, down) through a channel, managed by a subroutine inside of this listener routine. For more detail on this, see the implementation of InterfaceListenerRoutine() in ipstack.go.

RIP Routines

Following StartRipRoutines(), we use two main routines to maintain the RIP protocol: PeriodicUpdateRoutine() and ManageTimeoutRoutine().

Periodic Update Routine

This routine is responsible for sending periodic updates to all neighbors every 5 seconds.

Manage Timeout Routine

This routine is responsible for managing the timeout table. Every second it increments the timeout of every entry in the table by 1. Once the entry reaches MAX_TIMEOUT == 12 (if it wasn't reset to 0 by an update), this thread removes the entry from the routing table (and timeout table) then sends a triggered update to all neighbors. A mutex is used on the timeout table to ensure safe interaction from RIP updates resetting timeouts (in a separate thread).

Processing IP packets

Processing Incoming Packets

Upon receiving a packet at the Link Layer, a node should call RecvIP to process the IP packet.

RecvIP then does the following: 1) Check if the interface is up/down. If down, drop the packet (i.e. return). 2) Parse the header. Check if the packet is valid by validating checksum and seeing TTL > 0. If not, drop the packet. 3) Check if the packet is for me (any of my interface). If so, SENDUP to handler (if protocol is register) with the parsed message. End function. 4) Check the routing table for the next hop. If not found, drop the packet. If found, determine if the hop is a neighbor or not, then: 1) If the hop is a neighbor, send directly to that neighbor. 2) If the hop is not neighbor, forward the packet to the appropriate neighbor (i.e. the neighbor matches the packet's destination header). 8) If failed to find a route in the table, print an error & drop the packet (note: vhost will always succeed due it's static route).

This allows for the ip stack to completely handle the processing of packets, given that even the listener thread that calls RecvIP is managed by the IPStack.

Processing Outgoing Packets

To sending a packet at the Link Layer, a node should call SendIP to process the IP packet, which consumes the source address, neighbor to send to, protocol number, and message content. For forwarding, you can resuse the same header in SendIP's final argument.

SendIP then does the following: 1) Check if the interface is up/down. If down, don't send the packet (i.e. return). 2) Build the header, then update its checksum. 3) Build the message buffer. 4) Send the packet to the desired neighbor's socket.

Miscellaneous

Notable Design Decisions

Our design is mostly straighforward. However, we did improve our design from the basic design in two following ways.

More RIP requests and triggered updates

When an interface is set to down or up from the REPL, the router instantly knows new information. Hence, it makes sense to act on this new information to propagate information quicker. - If an interface goes down, then send a triggered update to all neighbors of the new INFINITY cost to the neighbors affected by that LL loss. - If an interface goes up, then send a RIP request to all neighbors to instantly get the new, expanded routes, versus waiting 5 seconds for the next periodic update.

See InterfaceUp() & InterfaceDown() for specific info.

Specific Garbage Collection for Expired Entries

If a route is expired, as told by receiving a cost of INFINITY for a route, we let that route exist for 12 seconds with value INFINITY before deleting it. The textbook states this is the preferred method.

This is different from the reference, which would delete these routes instantly.

Known Bugs

No known bugs :)

However, the reference often crashed on startup when spawning the loop network with tmux.