2.5. Routing algorithm

2.5.1. Introduction

A routing algorithm is an algorithm used to find an optimal path from a source router to a destination router. There are many kinds of routing algorithms, each of which has a different impact on network and router resources; because routing algorithms use a variety of metrics, the optimal path selection for different routing algorithms is also different.

2.5.2. Functions of Routing Algorithms

Path selection between source/sink pairs, and routing of packets to their destinations.

Requirements for the routing algorithm:

  • Correctness: ensure that packets are transmitted from source node to destination node

  • Simplicity: easy to implement, low hardware and software overhead

  • Adaptive: Also known as robustness, the algorithm can adapt to changes in traffic and network topology

  • Stability: can run for a long time without trouble

  • Fairness: every node has the opportunity to transmit information

  • Optimality: try to choose the best route

2.5.3. AS (Autonomous System)

Classic Definition:

  • A complete set of routers and networks managed by one organization.

  • An intra-AS routing protocol and common metrics are used to determine the routing of packets within the AS.

  • An inter-AS routing protocol is used to determine the routing of packets between ASs.

Although an AS uses multiple internal routing protocols and metrics, it presents a single and consistent routing strategy to other ASs.

2.5.4. Two types of routing protocols

In the Internet, routing protocols can be divided into interior gateway protocol IGP (Interior Gateway Protocol) and exterior gateway protocol EGP (External Gateway Protocol).

IGP is a routing protocol used within an AS, such as RIP and OSPF, which is an interdomain routing. When the source host and the destination host are in different ASs, when the datagram reaches the boundary of the AS, the external gateway protocol EGP is used to transmit the routing information to another autonomous system, such as BGP-4, which is the inter-domain routing ( intradomain routing).

2.5.5. RIP

Routing Information Protocol (RIP) is a distance vector-based routing protocol. The RIP protocol requires each router in the network to maintain the distance and next-hop router address from itself to every other destination network in the autonomous system.

2.5.6. OSPF

Open Shortest Path First (OSPF), this algorithm is called “Shortest Path First” because it uses the shortest path algorithm SPF proposed by Dijkstra, which is just the name of a protocol, it does not mean that other routing protocols are not “Shortest Path First”.