Routing Algorithms | Teleinf Edu

Introduction: routing algorithms

The Internet connects many networks and address prefixes. When you send a message or request a web page, a packet crosses routers that select the next forwarding step from the destination address. Each router makes a local forwarding decision and passes the packet to the next hop. Routers make these decisions at the network layer.

A sits at the junction of two or more networks and makes the forwarding decision for each passing . But to make this decision, it needs a map. This "map" is called a routing table, which contains a list of directions: "To reach network X, send the packet to the next router Y."

Network topology can change when links fail, routers are added, or configuration changes. Routers learn reachability information and update their routing tables according to a routing algorithm. An algorithm can be distributed, so each router computes routes from local data and protocol messages. The next sections describe three algorithm families.

The goal of a routing algorithm: selecting a route

A routing algorithm is a set of rules and procedures used by routers to learn about the network's , share this information with other routers, and calculate candidate paths to reachable destinations. The device then installs routes according to its selection rules.

Route selection criteria: the metric

Route selection depends on the protocol and its configuration. Not every protocol interprets a larger value as worse, so the protocol documentation defines the comparison direction. In protocols that minimize a metric, the choice is determined by a . A metric is a numerical value assigned to a path. In protocols based on minimization, it represents the cost of using that path. For equal values, a protocol can apply additional selection criteria such as a router identifier or configuration order. Common examples include:

Hop Count: The number of routers a packet must cross. Simple, but doesn't account for link speed.
Bandwidth: The data-carrying capacity of a link. In a simplified model, higher bandwidth can produce a smaller cost component written as $1/\text{bandwidth}$ . OSPF uses an interface cost and sums it along the route.
Delay (Latency): The time it takes for a packet to traverse the links.
Load: How busy the links are.
Cost: An administratively defined value, often based on a combination of factors or monetary cost.

Distance vector: exchanging metrics

Distance Vector exchanges reachability information and metrics between neighboring routers. A router knows its own prefixes and neighbors, then derives additional routes from the received values. A route entry normally records a destination, a metric, and a next hop rather than a complete description of every link.

How it works: exchanging information

The core principle of a Distance Vector algorithm is simple and decentralized, based on the $\text{Bellman-Ford}$ algorithm:

Each router maintains a routing table that lists all known destinations, the distance (metric) to that destination, and the next router (next-hop) on the path.
In RIP, a router periodically sends its entire routing table to its directly connected neighbors, usually every 30 seconds. Other distance-vector protocols use their own timers and update formats.
When a router receives a table from a neighbor, it compares the received information with its own. For each destination in the neighbor's table, it calculates a new potential distance: $d_{\text{new}} = d_{\text{neighbor}} + c_{\text{link}}$ , where $d_{\text{neighbor}}$ is the neighbor's distance to the destination and $c_{\text{link}}$ is the cost of the link to that neighbor.
If this newly calculated distance is better (lower) than the one it currently has in its table, it updates its entry, setting the new, lower distance and listing the neighbor who sent the update as the next-hop.

Repeated exchanges with neighbors produce successive route updates, sent periodically or after a change according to the protocol. A stable state with consistent routing information is known as .

Example: counting to infinity

Distance vector can react more slowly to some link failures than to improved metrics. The resulting increase of a metric through a loop is known as the counting to infinity problem.

Consider a simple network: Router A is connected to Router B, which is connected to Network X. The hop count is the metric.

Stable State: B advertises it can reach X with a metric of $1$ (directly connected). A receives this, adds its own cost of $1$ to get to B, and installs a route to X via B with a metric of $2$ .
Link Failure: The link between B and X goes down. B now has no route to X.
Bad Rumor Spreads: Before B can tell A about the failure, A's periodic update arrives at B. A's table says, "I can get to Network X in $2$ hops."
Routing Loop: B receives this advertisement from A and assumes that A has a path to X. B can reach A in $1$ hop, so its new path to X is via A with a cost of $2+1=3$ . B updates its table to point to A.
The count begins: On the next update, A tells B its route (cost $2$ ). B updates its cost to $3$ . Then A hears from B (cost $3$ ) and updates its cost to $4$ . Then B hears from A (cost $4$ ) and updates to $5$ . Packets destined for X can circulate between A and B while the metric increases toward the value treated as infinity by the protocol. In RIP, the default infinity value is $16$ .

Distance vector protocols use mechanisms such as Split Horizon (omitting a route from an update sent through the interface on which it was learned), Route Poisoning, and Hold-Down Timers. In RIP, a metric of 16 represents infinity, so hop counts from 1 through 15 are usable. A classic protocol using this algorithm is $\text{RIP}$ ( $\text{Routing Information Protocol}$ ).

Link-state: a topology database

The second major family, Link-State, distributes descriptions of local links. Routers in the same area maintain a consistent topology database and calculate routes independently from their own perspective. The database describes relationships between routers, while the area scope limits the information required for computation.

How it works: topology database and shortest path

The Link-State process can be broken down into a few key steps, based on $\text{Dijkstra's}$ $\text{Shortest Path First}$ ( $\text{SPF}$ ) algorithm:

Discovering neighbors and link costs: Each router first discovers its directly connected neighbors and determines the cost (metric) of the link to each of them.
Create a Link-State Packet (LSP): Each router packages this information: its ID, its list of neighbors, and the cost to each neighbor, into a small message called a .
Flood link-state information within the area: The router sends its link-state description to neighbors. Each neighbor stores it and forwards it according to the protocol's flooding rules. This process, known as flooding, distributes descriptions to routers in the area.
Build a topology database: By collecting link-state descriptions, each router builds a consistent database for the area.
Run the Shortest Path First ( $\text{SPF}$ ) Algorithm: With the complete map, each router runs the $\text{SPF}$ ( $\text{Dijkstra's}$ ) algorithm, placing itself at the root of a tree and calculating the shortest path to every other node and network. The result is a complete tree of the best routes.
Populate the Routing Table: From the calculated shortest-path tree, the router extracts the best paths and installs them into its routing table.

When a network change occurs, such as a link failure, the affected router updates its link-state description and floods it according to the protocol. Other routers update their databases and rerun $\text{SPF}$ . The resulting shortest-path tree is then converted into forwarding entries for reachable prefixes. $\text{OSPF}$ ( $\text{Open Shortest Path First}$ ) and $\text{IS-IS}$ use link-state routing, with different information formats, message types, and flooding scopes.

Path vector: routing between autonomous systems

The third major family, Path Vector, exchanges information between independently managed networks called . Route selection in this model can consider business relationships, security, and operator policy.

How it works: advertising the AS path

The Path Vector algorithm extends distance-vector exchange with a list of autonomous systems. When an advertisement is forwarded, the next AS prepends its number to the AS_PATH attribute. Other path attributes can describe the origin, next hop, or local preference used in route selection:

Routers advertise the destination network along with the entire path of AS numbers that the route traverses and the other attributes required by the protocol.
For example, a router in AS 1 might advertise to its neighbor in AS 2: "I can reach Network Z via the path (AS 1)."
AS 2 then advertises to its neighbor in AS 3: "I can reach Network Z via the path (AS 2, AS 1)."

Loop prevention and routing policy

The path list supports two mechanisms:

AS_PATH loop detection: A router scans the path list. If it finds its own AS number, it excludes the route as a potential loop. BGP uses this mechanism to reject an advertisement that has returned through its own autonomous system.
Policy-based routing: The known path list lets administrators influence routing decisions according to operator policy and business requirements. For instance:
- "Do not accept routes that pass through my competitor's AS."
- "Prefer routes learned from my primary transit provider over my backup."
- "Do not announce my internal customer networks to other transit providers."

Decisions use a set of path attributes and local policies. Attributes can influence route preference, announcement, and acceptance, so selection can depend on operator rules and configured relationships. A contemporary example of a path-vector protocol is $\text{BGP}$ ( $\text{Border Gateway Protocol}$ ), which routes between autonomous systems under advertised policies.