correctly implement split horizon + reverse poison by fixing the timeout table. also added comments to explain the complexity of recv ip.

4 files changed, 84 insertions, 64 deletions

diff --git a/go.mod b/go.mod
index b7e6cbe..503fdb4 100644
--- a/go.mod
+++ b/go.mod
@@ -1,6 +1,6 @@
 module iptcp
 
-go 1.20
+go 1.21
 
 require (
 	github.com/brown-csci1680/ipstack-utils v0.0.0-20231005044334-c7ffd5865555 // indirect
diff --git a/pkg/ipstack/ipstack.go b/pkg/ipstack/ipstack.go
index 959e5ff..61b33b0 100644
--- a/pkg/ipstack/ipstack.go
+++ b/pkg/ipstack/ipstack.go
@@ -513,9 +513,9 @@ func RecvIP(iface *Interface, isOpen *bool) error {
 
 	// at this point, the packet is valid. next steps consider the forwarding of the packet
 	// 2) check if the message is for me, if so, sendUP (aka call the correct handler)
-	if hdr.Protocol != RIP_PROTOCOL {
-		fmt.Println("I see a non-rip packet")
-	}
+	//if hdr.Protocol != RIP_PROTOCOL {
+	//	fmt.Println("I see a non-rip packet")
+	//}
 	for _, myIface := range myInterfaces {
 		if hdr.Dst == myIface.IpPrefix.Addr() {
 			// see if there is a handler for this protocol
@@ -654,7 +654,7 @@ func periodicUpdateRoutine() {
 }
 
 var mu sync.Mutex
-var timeoutTable = make(map[netip.Addr]int)
+var timeoutTable = make(map[netip.Prefix]int)
 var MAX_TIMEOUT = 12
 
 func sendTriggeredUpdates(newEntries []RIPEntry) {
@@ -676,6 +676,10 @@ func sendTriggeredUpdates(newEntries []RIPEntry) {
 	}
 }
 
+func timeoutKey(prefix netip.Prefix, addr netip.Addr) string {
+	return prefix.String() + "-" + addr.String()
+}
+
 func manageTimeoutsRoutine() {
 	for {
 		time.Sleep(time.Second)
@@ -700,18 +704,14 @@ func manageTimeoutsRoutine() {
 		//mu.Unlock()
 
 		mu.Lock()
-		for addr, _ := range timeoutTable {
-			timeoutTable[addr]++
-			if timeoutTable[addr] == MAX_TIMEOUT {
-				delete(timeoutTable, addr)
+		for key, _ := range timeoutTable {
+			timeoutTable[key]++
+			if timeoutTable[key] == MAX_TIMEOUT {
+				delete(timeoutTable, key)
 
 				newEntries := make([]RIPEntry, 0)
-				for p, hop := range routingTable {
-					if hop.VIP == addr {
-						delete(routingTable, p)
-						newEntries = append(newEntries, RIPEntry{p, INFINITY})
-					}
-				}
+				delete(routingTable, key)
+				newEntries = append(newEntries, RIPEntry{key, INFINITY})
 				// send triggered update on timeout
 				if len(newEntries) > 0 {
 					sendTriggeredUpdates(newEntries)
@@ -827,70 +827,90 @@ func handleRIP(src *Interface, dest *Neighbor, message []byte, hdr *ipv4header.I
 			entries = append(entries, RIPEntry{prefix, cost})
 		}
 
-		// add to routing table
+		// update the routing table
+		triggeredEntries := make([]RIPEntry, 0)
 		for _, entry := range entries {
-			// fmt.Printf("Received RIP update: %s\t%d\t%d\n", address, entry.mask, entry.cost)
+			destination := entry.prefix.Masked()
 
-			if entry.prefix.Addr() == netip.MustParseAddr("0.0.0.0") { // TODO: investigate this
-				continue
+			// make upperbound for cost infinity
+			var newCost uint32
+			if entry.cost == INFINITY {
+				newCost = INFINITY
+			} else {
+				newCost = entry.cost + 1
 			}
 
-			// TODO: investigate this. should we be sharing local nodes too?
-			// potentially, may have to apply mask first
-			// fmt.Println(address)
+			hop, isin := routingTable[destination]
+			// if prefix not in table, add it (as long as it's not infinity)
+			if !isin {
+				if newCost != INFINITY {
+					// given an update to table, this is now a triggeredUpdate
+					// triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
 
-			destination := entry.prefix.Masked()
-			// fmt.Println(prefix.String())
-
-			triggeredEntries := make([]RIPEntry, 0)
-			// check if the entry is already in the routing table and update if need be
-			if hop, ok := routingTable[destination]; ok {
-				// if the hop is the same as the incoming neighbor,
-				// then we can increase the cost by that new value
-				if hop.VIP == hdr.Src &&
-					entry.cost > hop.Cost {
-					// fmt.Println("Updating route to ", destination.String(), "with cost", entry.cost)
-					if entry.cost >= INFINITY {
-						// if we receive infinity from the same neighbor, then delete the route
-						delete(routingTable, destination)
-						triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
-					} else {
-						routingTable[destination] = Hop{entry.cost + 1, "R", src, hdr.Src}
-						triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
-					}
+					routingTable[destination] = Hop{newCost, "R", src, hdr.Src}
+					timeoutTable[destination] = 0
 				}
+				continue
+			}
 
-				// if there is a shorter route for this destination on a different (or same) neighbor
-				// then update to use that one
-				if entry.cost < hop.Cost {
-					if entry.cost == INFINITY {
-						routingTable[destination] = Hop{entry.cost, "R", src, hdr.Src}
-						triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost})
-					} else {
-						routingTable[destination] = Hop{entry.cost + 1, "R", src, hdr.Src}
-						triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
+			// if the entry is in the table, only two cases affect the table:
+			// 1) the entry SRC is updating (or confirming) the hop to itself
+			//		in this case, only update if the cost is different
+			//		if it's infinity, then the route has expired.
+			//		we must set the cost to INF then delete the entry after 12 seconds
+			//
+			// 2) a different entry SRC reveals a shorter path to the destination
+			//		in this case, update the routing table to use this new path
+			//
+			// all other cases don't meaningfully change the route
+
+			// first, upon an update from this prefix, reset its timeout
+			if hop.Type == "R" {
+				mu.Lock()
+				_, in := timeoutTable[destination]
+				if in {
+					if routingTable[destination].VIP == hdr.Src {
+						timeoutTable[destination] = 0
 					}
 				}
+				mu.Unlock()
+			}
 
-				// upon an update from this prefix, reset its timeout
-				if hop.Type == "R" {
-					mu.Lock()
-					timeoutTable[hdr.Src] = 0
-					mu.Unlock()
-				}
-			} else {
-				if entry.cost < INFINITY {
-					// if we receive infinity from the same neighbor, then delete the route
-					routingTable[destination] = Hop{entry.cost + 1, "R", src, hdr.Src}
-					// triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
+			// case 1) the entry SRC == the hop to itself
+			if hop.VIP == hdr.Src &&
+				newCost != hop.Cost {
+				// given an update to table, this is now a triggeredUpdate
+				triggeredEntries = append(triggeredEntries, RIPEntry{destination, newCost})
+				routingTable[destination] = Hop{newCost, "R", src, hop.VIP}
+
+				// if we receive infinity from the same neighbor, then delete the route after 12 sec
+				if entry.cost == INFINITY {
+					// remove after GC time if the COST is still INFINITY
+					go func() {
+						time.Sleep(12 * time.Second)
+						if routingTable[destination].Cost == INFINITY {
+							delete(routingTable, destination)
+							mu.Lock()
+							delete(timeoutTable, destination)
+							mu.Unlock()
+						}
+					}()
 				}
+				continue
 			}
 
-			// send out triggered updates
-			if len(triggeredEntries) > 0 {
-				sendTriggeredUpdates(triggeredEntries)
+			// case 2) a shorter route for this destination is revealed from a different neighbor
+			if newCost < hop.Cost && newCost != INFINITY {
+				triggeredEntries = append(triggeredEntries, RIPEntry{destination, entry.cost + 1})
+				routingTable[destination] = Hop{entry.cost + 1, "R", src, hdr.Src}
+				continue
 			}
 		}
+
+		// send out triggered updates
+		if len(triggeredEntries) > 0 {
+			sendTriggeredUpdates(triggeredEntries)
+		}
 	}
 
 	return nil
diff --git a/vhost b/vhost
index ac23975..f9b9407 100755
--- a/vhost
+++ b/vhost
diff --git a/vrouter b/vrouter
index 5455b09..b5f089b 100755
--- a/vrouter
+++ b/vrouter