Lesson 3: Study Guide Flashcards
What is the difference between forwarding and routing?
Forwarding - transfer packet from incoming to outgoing link within a single router
Routing - multiple routers work together to determine paths between source and destination host
What is the main idea behind a link-state routing algorithm?
(what is known to the nodes?)
link costs and network topology are known to all nodes
What is an example of a link-state routing algorithm?
Dijkstra’s Algorithm
D(v) = min(D(v), D(w) + c(u,v))
distance u to v = old cost to v or new cost plus cost to neighbor
Walk through an example of the link-state routing algorithm.
- Initialize - set least cost path for neighbors, set infinity for non-neighbors
- Iterate - update with new information or Distance value using Dijkstra’s
- Exit - return shortest paths and their costs of the source node to every other node in the network
What is the computational complexity of the link-state routing algorithm?
O(n^2)
What is the main idea behind the distance vector routing algorithm?
based on the Bellman Ford Equation. it is iterative, asynchronous, and distributed where each node maintains its own distance vector. calculates the last cost path over all neighbors to reach the destination node.
Walk through an example of the distance vector algorithm.
1st iteration: each node’s distance vector has distance to neighbors.
2nd iter…: nodes exchange distance vectors, update view of network via bellman ford equation
Stops when no more updates, each node has own routing table.
When does the count-to-infinity problem occur in the distance vector algorithm?
when a link cost change takes a long time to propagate through all the nodes
How does poison reverse solve the count-to-infinity problem?
- One node lies to the other node to say its distance to the 3rd node is infinity instead of its actual cost; this path is poisoned and packets wont be sent
- Only works for 2 nodes that are directly connected
What is the Open Shortest Path First (OSPF) protocol?
uses a link-state routing algorithm to find the best path between the source and the destination router. Advancement of RIP.
What is the Routing Information Protocol (RIP)?
Based on distance vector protocol. uses RIP advertisements instead of distance vectors, info is exchanged to neighbors periodically with time constraint. Routers send messages over UDP. RIP is implemented as an application-level process.
challenges with RIP: updating routes, reducing convergence time, and avoiding loops/count-to-infinity problems
How does a router process advertisements?
in OSPF:
1. LS Update packet is received; LSAs from a neighboring router reaches the current router’s OSPF (route processor) - trigger for the route processor.
2. As the LS Updates reach the router, a consistent view of the topology is being formed and this information is stored in the link-state database.
3. OSPF protocol checks whether it is a new or a duplicate LSA. Using the link-state database, the current router calculates the shortest path using shortest path first (SPF) algorithm. The result of this step is fed to the Forwarding Information Base (FIB)
4. The information in the FIB is used when a data packet arrives at an interface card of the router, where the next hop for the packet is decided and its forwarded to the outgoing interface card.
5. For every new LSA, the database is updated, an SPF calculation is scheduled (T2) and it’s determined which interface the LSA needs to be flooded out of.
6. After the SPF calculation is completed, the FIB is updated
What is hot potato routing?
technique/practice of choosing a path within the network, by choosing the closest egress point based on intradomain path cost (Interior Gateway Protocol/IGP cost)
makes sure that the IGP path remains consistent, thus simplifying computations
reduces the network’s resource consumption by getting the traffic out as soon as possible.
