Lesson 3 - Intradomain routing Flashcards
What is the difference between the forwarding and routing?
By forwarding we refer to transferring a packet from an incoming link to an outgoing link within a single router.
By routing we refer to how routers work together using routing protocols to determine the good paths (or good routes as we call them) over which the packets travel from the source to the destination node.
What is the main idea behind link state routing algorithm?
Djikstra’s algorithm. All nodes know the network topology and link costs. Start with N’ just containing the source node. Initialize all paths to infinity except directly attached nodes. Perform iterations and update whenever we find lower costs until every node is examined and added to N’.
Name an example of link state routing algorithm
- Open shortest path first
- IS-IS
What is the computational complexity of the link state routing algorithm?
n^2 (decreases each iteration by n-1)
num iterations is always N-1
What is the main idea behind distance vector routing algorithm?
It is a routing algorithm in which a router periodically sends its entire routing table to its neighbors.
Bellman Ford algorithm. Iterative (continues until no more updates), asynchronous (nodes do not have to be synchronized with each other), and distributed (no need to know network topology or have some central point of calculation)
Explain the steps of distance vector routing
Each node maintains its own distance vector with costs to reach every other node in the network.
They send each other their distance vectors and update accordingly if there are shorter paths found between what was already in its distance vector and newly received information.
When does count to infinity problem occur in DV?
When there is a large increase in cost between nodes, such as a severed connection.
What is poison reverse in DV?
Refers to the practice of advertising a route, but with a special metric value called Infinity. Routers consider routes advertised with an infinite metric to have failed.
When one node knows there is a path through another node, it will poison the opposite path so it is never taken. When bad news comes, it will take the opposite path and pass on this information so the new path is quickly used and the previous path becomes poisoned.
What is RIP?
Based on the Distance Vector protocol and uses hop count as the metric (each link = 1 cost). Uses RIP response message instead of distance vectors. Each node maintains a RIP Table (Routing Table), which will have one row for each subnet in the AS. Uses UDP.
What is OSPF?
A routing protocol that uses the link-state routing algorithm to find the best path between source and destination router. Advancement of RIP. Uses flooding of link-state info and Dijkstra. Advances include authentication of messages, option to use multiple same cost paths, and support for hierarchy within a single routing domain.
What is hot potatoe routing
When there are equally good egress points (network exits) - choose the one that is the shortest (closest) path cost away = hot potato routing.
What are classes of intradomain routing algorithmms (or interior gateway protocols)?
- Link-state algorithms (OSPF)
- Distance vector algorithms (RIP)
What are the characteristics of distance vector alrogithm?
- Its iternative (iterates until the neighbors do not have new updates)
- Asynchronous (does not require nodes to be synchronized)
3 Distrbuted/not centralized (nodes send info to each other, then send results back)
What are the characteristics of the link state alrogithm?
- link costs are known to all nodes
- the network topology is known by all nodes
what are the differences between link state routing and distance vector routing?
Distance vector sends its entire table to its neightbords and link state broadcasts its neighbor info to every router
Distance vector has slow convergence and suffer from count to infinity problems where as link state has fast convergence and high reliability
