Routing Algorithms Flashcards
Network Layer
What does the term “Routing Algorithm” refer to?
Router table construction
What are the two classes of algorithms? Define them.
Link-State
Routers, by the end, have knowledge of the entire network. Routers exchange information about state of links. Each router uses this information to compute its distances to all destinations.
Distance Vector
Routers only communicate with their immediate neighbours. A router uses the distance vectors received
from its neighbors to compute its own distances. This is done iteratively.
What are the main functions of the network layer?
Host-to-Host Communication
This includes…
- addressing,
- routing,
- forwarding,
- congestion control,
- admission control.
Define Routing
Computing the path between source and destination
Define Congestion Control
Limit on the amount of data a source can send in the network at a given time.
Define Admission Control
Limits on the number of sources that can send data in the network at a given time.
(part of system-wide congestion control)
Define Addressing
Identifying where a destination is with respect to the network’s topology
Define forwarding
Receive, see address, send packets along the path found via “routing”.
A distributed routing system must be safe and live… what do those two terms mean?
Safe
computing a vaild route within finite time
Live
no deadlocks/ loops
What are components of every routing system?
- Identifier space to denote destinations
- A routing metric (distance, link weight, src, des)
- Distributed Algorithms and protocols used to compute routes based on the routing metric
- Routing tables storing computed values for routes
- Algorithm and protocols used to forward packets based on data in routing tables
- A mapping from user- or application- friendly names to identifiers used in routes
What is necessary for an SRA (shortest-path routing algorithm) to converge?
Mustn’t have any loops
If the shortest path to C is
[stuff]→B→C
then the shortest path to B cannot contain C
Each subset of the shortest path must be a shortest path!
When is an SRA said to have converged?
When the shortest path has been reached at time t, and it does not contain any loops
What information is maintained at each router?
Distance Table, Link-Cost Table, Routing Table
(to node, from node, cost) + (sequence number)
What is the purpose of sequence numbers in DBF (Distributed Bellman Ford)?
Describe how it is used.
DBF performs poorly given numerous routers. Sequence numbers let the routers know which data containing the link’s state is newest.
To ensure the newest data gets shared, flood the entire topology. Routes are then computed locally with the new data.
Comment on safety and liveliness for DBF for a connected network
Liveliness: each node updates its routing table independently of others. Deadlock can only occur in the exchange of distance vectors. (Point-to-Multipoint ARQ handles that)
Safety: Given no deadlocks, algorithm guaranteed to produce valid path in finite time.
What is ARQ? Give examples of its implementation.
Automatic Repeat reQuest (ARQ) is a protocol used in computer networks to ensure reliable data transmission. It works by using acknowledgments and timeouts to detect and correct errors in data packets.
Examples.
Go-Back-N ARQ: The sender waits for an ACK for each packet before sending the next one.
Stop-and-Wait ARQ: The sender can send several packets before needing an ACK, but if an error is detected, all subsequent packets are retransmitted.
Selective Repeat ARQ: Only the erroneous packets are retransmitted, not the entire sequence.
Point-to-Multipoint ARQ: ARQ specifically for MAC
Describe the dissemination of link state updates (LSU) for Link-State Algorithms.
Only the router where a LSU originates can update the sequence number
An age is assigned to the LSU, periodically, an LSU will be sent out with LSU age 0 - reset.
HANDLING TOPOLOGY CHANGES
Sharing
A router that detects a new neighbor sends its topology graph to that neighbor.
Informing
A router that hears a more recent LSU from a neighbor for one of its outgoing links creates a new LSU with a higher sequence
number and sends it to all its neighbors
Is any distance-vector algorithm subject to temporary loops?
No, that problem exists when using path information to find loops.
