1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
# 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.
|
