Chapter 3 A2 Flashcards
Forwarding table vs Routing table
Forwarding table
* Used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function
* A row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet Address of the next hop
Routing table
* Built by the routing algorithm as a precursor to build the
forwarding table
* Generally contains mapping from network numbers to next hops
Routing Table Format vs Forwarding Table Format
Routing:
* Prefix/Length
* Next Hop
Forwarding
* Prefix/Length
* Interface
* MAC Address
Distance Vector
- Each node constructs a 1D array containing all distances to all other nodes and distributes this vector to all its neighbours.
- Initial assumption is only nodes adjacent are on the table
When a node detects failure - Distance Vectore
- F detects that link to G has failed
- F sets distance to G to infinity and sends update to A (Neighbour)
- A sets distance to G to infinity since it uses F to reach G
- A receives periodic update from C with 2-hop path to G
- A sets distance to G to 3 and sends update to F
- F decides it can reach G in 4 hops via A
Testing link failure
- Send control packets to neighbours and see if the acks received
- No periodic routing updates received for a few cycles
Counting to Infinity Problem
- Suppose the link from A to E goes down
- In the next round of updates, A advertises a distance of infinity to E, but B and C advertise a distance of 2 to E
- This causes an infinite cycles of updates causing the length to increase because there technically should not be a path available but there is
Solution 1 for Counting to Infinity Problem
Use a relatively small number to approx. infinity.
Solution 2 for CtIP - Split Horizon
when a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.
Split Horizon with Poison Reverse
Send back to neighbour but with infinite distance
Routing Information Protocol (RIP)
Rather than advertising the cost of reaching other routers, the routers advertise the cost of reaching networks. Uses the distance vector stuff as well for determining costs.
Link State Routing
Each node is assumed to be capable of finding out the state of the link to its neighbors (up or down) and the cost of each link.
Link State Packet
- id of the node that created the LSP
- Cost of the link to each directly connected neighbour
- Seqeunce number
- Time to Live for this packet
Reliable Flooding
- store the most recent LSP from each node
- Forward LSP to all nodes but one that sent it
- Generate new LSP periodically
- Incremenr Sequence Number
- Start sequence number at 0 when reboot
- decrement TTL of each stored LSP
- Discard when TTL = 0
Shortest Path Routing
- Dijkstra’s Algorithm - Assume non-negative link weights
- N: set of nodes in the graph
- I(i, j): the non negative cost associated with the edge between the nodes
- let s be the starting node
- M: the set of nodes incorporated so far by the algorithm
- C(n): the cost of the path from s to each node n
Dijkstra’s Algo
- Initialize the Confirmed list with an entry for myself; this entry has a cost of 0
- For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP
- For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach
this Neighbor as the sum of the cost from myself to Next and from Next
to Neighbor- If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, Nexthop) to the Tentative list, where Nexthop is the direction I go to reach Next
- If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for the Neighbor, then replace the current entry with (Neighbor, Cost, Nexthop) where Nexthop is the direction I go to reach Next
- If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to Step 2.
