Week 10 - Routing Algorithms Flashcards
(33 cards)
How is graph abstraction useful in networking contexts like P2P?
In P2P networks, the system can be modeled as a graph where N is the set of peers and E is the set of TCP connections, helping analyze connectivity and data flow.
What is the difference between global and decentralized routing algorithms?
- Global (Link State): All routers have complete topology and link cost info.
- Decentralized (Distance Vector): Each router only knows info about its neighbors and exchanges data iteratively.
What distinguishes static from dynamic routing algorithms?
- Static: Routes change slowly over time.
- Dynamic: Routes update frequently, either periodically or in response to changes in link cost.
What is the goal and approach of Dijkstra’s Algorithm in routing?
- Goal: Compute the least-cost paths from a source node to all other nodes.
- Approach: Iteratively builds the set of nodes with known shortest paths using complete network topology and link cost info.
What key terms are used in Dijkstra’s Algorithm?
- c(x, y): cost from node x to y (∞ if not directly connected)
- D(v): current shortest path cost from source to v
- p(v): predecessor of v on the shortest path
- N’: set of nodes with confirmed shortest paths
What is the time complexity of Dijkstra’s Algorithm and how can it be improved?
Basic implementation: O(n²) due to checking all nodes not in N′ during each of n iterations.
Optimized implementation (e.g., using a priority queue): O(n log n)
What causes oscillations in Dijkstra’s Algorithm when link costs depend on traffic?
- Cause: Link costs are based on the amount of traffic, so changes in routing affect traffic, which in turn alters the link costs, creating a feedback loop.
- Result: This can cause oscillations, as new routes change the traffic load, leading to new cost calculations and potentially unstable routing.
What is the key idea behind the Distance Vector algorithm?
The key idea is that each node periodically sends its own distance vector estimate to its neighbors, which helps in updating and computing the shortest paths in the network.
How does a node update its distance vector using the Bellman-Ford equation in the Distance Vector algorithm?
When node x receives a distance vector from a neighbor v, it updates its own vector for each destination y:
Dx(y)←minv{c(x,v)+Dv(y)}.
How does the Distance Vector algorithm converge to the actual least cost?
Under minor natural conditions, the distance vector estimates will converge to the actual least cost from any node to every destination.
How does the Distance Vector Algorithm operate in terms of updates?
It is iterative and asynchronous, where each local iteration occurs due to a local link cost change or a Distance Vector (DV) update message from a neighbor.
How is the Distance Vector Algorithm distributed across the network?
Each node notifies its neighbors only when its distance vector changes. Neighbors then propagate updates to their neighbors if necessary.
What happens when a node receives a change in link cost or a message from a neighbor in the Distance Vector Algorithm?
The node recomputes its distance estimates and, if any estimates change, it notifies its neighbors to update them.
How does the Distance Vector Algorithm handle link cost changes?
When a node detects a local link cost change, it updates its routing information, recalculates its distance vector, and notifies its neighbors if the distance vector changes.
What happens after a node detects a link cost change and updates its distance vector?
The node informs its neighbors, and the neighbors update their own distance tables and potentially propagate the changes further.
In the Distance Vector Algorithm, what happens if a link cost increases?
If the link cost increases, the node recalculates the new least cost and informs its neighbors. The update propagates through the network, adjusting the routing tables as necessary.
What is the message complexity of Link-State (LS) and Distance Vector (DV) algorithms?
- LS: O(NE) messages with N nodes and E links.
- DV: Exchange between neighbors only.
How do Link-State (LS) and Distance Vector (DV) algorithms compare in terms of convergence time and robustness?
- LS: O(N²) complexity, may have oscillations.
- DV: Convergence time varies, may experience routing loops and count-to-infinity problems.
How do Link-State (LS) and Distance Vector (DV) handle errors or router malfunctions?
- LS: A node can advertise incorrect link cost, but each node computes only its own table.
- DV: A node can advertise incorrect path costs, which propagate errors through the network as each node’s table is used by others.
Why is hierarchical routing necessary in large-scale networks?
- Scale: Storing all destination addresses in routing tables is not feasible (e.g., 600 million destinations).
- Routing Table Exchange: Would overwhelm network links.
What is the concept of administrative autonomy in hierarchical routing?
- The Internet is a network of networks.
- Each network admin may want to control routing within their own network.
Why is the flat network model not realistic in practice?
- All routers being identical and the network being flat doesn’t scale for large networks.
- Hierarchical routing allows more efficient routing and better scalability.
What is an Autonomous System (AS) in hierarchical routing?
- An Autonomous System (AS) is a group of routers aggregated into a region.
- Routers in the same AS run the same intra-AS routing protocol.
What is the role of a Gateway Router in hierarchical routing?
- A Gateway Router is located at the edge of its own AS.
- It has a link to a router in another AS to facilitate communication between different ASes.
