This is a beta course, so its structure, chapters, and examples may continue to change.
Routing Algorithms
1. Overview of Routing Algorithms
A routing algorithm is the core of the network layer. It chooses the best transmission path for a packet.
Objectives of Routing Algorithms
- Shortest path: choose the path with the smallest distance
- Minimum delay: choose the path with the smallest delay
- Maximum bandwidth: choose the path with the largest bandwidth
- Minimum cost: choose the path with the lowest cost
Classification of Routing Algorithms
- Static routing: configured by an administrator, not updated automatically
- Dynamic routing: learned automatically and updated as the network changes
2. Static Routing
Characteristics
- Manually configured: set up by a network administrator
- Fixed: unchanged unless a human modifies it
- Simple and reliable: easy to configure and stable in operation
- Suitable for small networks: used when the network scale is modest
Configuration Methods
- Directly connected routes: networks that the router is attached to
- Static routes: manually configured routing entries
- Default route: used when no other route matches
Advantages and Disadvantages
Advantages:
- Simple to configure
- Stable in operation
- Uses no network bandwidth
- Good security
Disadvantages:
- Cannot adapt to network changes
- Requires a large configuration effort
- Prone to configuration errors
- Not suitable for large networks
3. Dynamic Routing
Characteristics
- Automatic learning: routers learn the network topology automatically
- Automatic updating: the routing table is updated as the network changes
- Adaptive: copes with changes in the network topology
- Suitable for large networks: used when the network scale is large
Classification
- Distance vector algorithms: based on distance information
- Link state algorithms: based on link state information
- Path vector algorithms: based on path information
4. Distance Vector Routing Algorithms
Basic Principle
- Distance information: each router knows only the distance to its neighbours
- Periodic exchange: routing information is exchanged with neighbours at regular intervals
- Distributed computation: each router computes the shortest path on its own
- Bellman-Ford algorithm: a shortest path algorithm based on dynamic programming
How It Works
- Initialization: the router knows only the distance to the directly connected networks
- Information exchange: routing table information is exchanged with neighbours
- Distance computation: the Bellman-Ford algorithm computes the shortest path
- Routing update: the local routing table is updated
- Repeat: steps 2 to 4 repeat until the network converges
Typical Protocols
- RIP: Routing Information Protocol, limited to 15 hops
- IGRP: Interior Gateway Routing Protocol, a Cisco proprietary protocol
- EIGRP: Enhanced Interior Gateway Routing Protocol
Advantages and Disadvantages
Advantages:
- Simple to implement
- Low computational cost
- Suitable for small networks
Disadvantages:
- Slow convergence
- Prone to routing loops
- The hop limit restricts the network scale
5. Link State Routing Algorithms
Basic Principle
- Link state information: every router collects the link state of the whole network
- Topology database: a complete topology graph of the network is built
- Centralized computation: the Dijkstra algorithm computes the shortest path
- Global view: every router holds topology information about the whole network
How It Works
- Discover neighbours: neighbouring routers are found through Hello packets
- Measure costs: the link cost to each neighbour is measured
- Build the LSA: a link state advertisement is constructed
- Flood: the LSA is flooded across the whole network
- Build the topology: a complete topology database is constructed
- Compute paths: the Dijkstra algorithm computes the shortest path
Typical Protocols
- OSPF: Open Shortest Path First
- IS-IS: Intermediate System to Intermediate System
Advantages and Disadvantages
Advantages:
- Fast convergence
- Supports large networks
- Supports multiple metrics
- Not prone to routing loops
Disadvantages:
- Complex to implement
- High computational cost
- Consumes more resources
6. Hierarchical Routing
Basic Principle
- Hierarchical structure: the network is divided into several levels
- Intra-domain routing: an intra-domain routing protocol is used within a domain
- Inter-domain routing: an inter-domain routing protocol is used between domains
- Autonomous system: each autonomous system is managed independently
Hierarchical Structure
- Autonomous system (AS): a network managed independently
- Intra-domain routing protocols: RIP, OSPF, IS-IS
- Inter-domain routing protocols: BGP
Advantages
- Scalability: supports large-scale networks
- Simple management: hierarchical management with clear responsibilities
- Security: inter-domain routing can enforce security policies
- Flexibility: different domains can use different routing protocols
Exercise 1
What is the difference between distance vector and link state routing algorithms?
Approach: compare the two on the six axes that actually differ in practice.
Steps:
The main differences are:
-
Information exchange:
- Distance vector: exchanges only distance information with neighbours
- Link state: exchanges link state information with the whole network
-
Topology information:
- Distance vector: knows only the neighbours’ information
- Link state: knows the topology of the whole network
-
Computation:
- Distance vector: distributed computation with the Bellman-Ford algorithm
- Link state: centralized computation with the Dijkstra algorithm
-
Convergence speed:
- Distance vector: converges slowly
- Link state: converges quickly
-
Applicable scale:
- Distance vector: suitable for small networks
- Link state: suitable for large networks
-
Resource consumption:
- Distance vector: low computational cost and low resource consumption
- Link state: high computational cost and high resource consumption
Answer: distance vector exchanges only distances with neighbours and computes paths locally with Bellman-Ford, which is cheap but slow to converge; link state floods the topology to every router and computes paths with Dijkstra, which converges faster and scales better but costs more.
Exercise 2
What are the advantages and disadvantages of static routing and of dynamic routing?
Approach: list the four advantages and four disadvantages of each, then summarize the trade-off.
Steps:
Advantages of static routing:
- Simple to configure and easy to understand
- Stable in operation, and it does not produce routing loops
- Uses no network bandwidth
- Good security, since it is not easy to attack
Disadvantages of static routing:
- Cannot adapt to network changes
- Requires a large configuration effort
- Prone to configuration errors
- Not suitable for large networks
Advantages of dynamic routing:
- Adapts to network changes automatically
- Requires little configuration effort
- Supports large networks
- Strong fault tolerance
Disadvantages of dynamic routing:
- Complex to implement
- May produce routing loops
- Consumes network bandwidth
- Relatively weaker security
Answer: static routing is simple, stable, and quiet on the network but cannot adapt to change; dynamic routing adapts automatically and scales to large networks but is more complex, consumes bandwidth, and can create routing loops.
| Term | Abbreviation | Explanation |
|---|---|---|
| Routing Algorithm | - | An algorithm that selects the transmission path of a packet |
| Static Routing | - | Manually configured routing |
| Dynamic Routing | - | Routing that is learned and updated automatically |
| Distance Vector | DV | A routing algorithm based on distance and direction |
| Link State | LS | A routing algorithm based on link state information |
| Routing Information Protocol | RIP | A distance vector routing protocol |
| Open Shortest Path First | OSPF | A link state routing protocol |
| Border Gateway Protocol | BGP | An inter-domain routing protocol |
| Autonomous System | AS | A collection of networks under a single administrative domain |
| Metric | - | The cost measure used in route selection |
| Hop Count | - | The number of routers a packet traverses |
| Routing Table | - | The table that stores routing information |
| Convergence | - | The routing tables becoming consistent again after a topology change |
| Routing Loop | - | A packet circulating in a loop forever |
| Split Horizon | - | A technique that prevents routing loops |
| Poison Reverse | - | A technique that prevents routing loops |