Chapter3 - Basic concepts of routing (Part1)

1. Introduction

Routing refers to the process of selecting the optimal path for data packets to travel from their source to their destination in a computer network. This is typically done by network devices called routers, which examine the destination address of incoming packets and determine the best path. Routing typically involves two main steps: Route Determination and Packet Forwarding. 

Routing protocols correspond to the implementation of routing algorithms, there are several:
IGRP (Interior Gateway Routing Protocol), EIGRP (Enhanced Interior Gateway Routing Protocol), OSPF
(Open Shortest Path First), EGP (Exterior Gateway Protocol), RIP (Routing Information Protocol)...etc. In this chapter, we explain the basic principles of routing and then describe RIP and OSPF protocols.

2. Route Determination

In this step, routers determine the best path for forwarding packets from the source to the destination. This involves examining routing tables, which contain information about available network paths and their associated costs. Various routing algorithms are used to calculate the optimal path based on factors such as hop count, bandwidth, latency, and network congestion.

Routing tables store "among other things" the following information: destination / next hop. These indicate to the router having received the packet that a given destination has been reached by sending the packet to another router which represents the "next hop". In other words, when a router receives a packet, it attempts to associate a next hop with its destination address.

In cases where there are multiple routes to the same destination learned from different sources (e.g., multiple dynamic routing protocols or a combination of static and dynamic routes), routers use administrative distance tp choose the route. Administrative distance is a measure of the reliability of the routing information source. Routes with lower administrative distances are preferred over routes with higher administrative distances.

Within a single routing protocol, if there are multiple routes to the same destination with the same administrative distance, routers compare the metrics associated with each route. The metric is a measure of the "cost" associated with using a particular route, which can include factors such as hop count, bandwidth, delay, reliability, and load.

3. Packet forwarding

Once the best path has been determined, routers forward packets along that path towards the destination. This involves encapsulating packets with appropriate headers containing routing information and transmitting them to the next hop router in the selected path. The process continues until the packets reach their final destination.

4. Goals of routing 

The primary goal of routing algorithms is to determine the best paths for forwarding data packets from their source to their destination in a computer network. These algorithms aim to achieve determine the best paths for forwarding data packets from their source to their destination in a computer network. These algorithms aim to achieve
several key objectives:
 
Efficiency: Routing algorithms should efficiently utilize network resources, such as bandwidth and router processing power, while ensuring timely delivery
of packets. 
Scalability: Routing algorithms should scale effectively as network size and complexity
grow.
Resilience and Robustness: Routing algorithms should provide robustness and resilience
to network failures or changes (detect and respond to failures).
Adaptability and flexibility: Routing algorithms should be adaptable to changing network conditions, such as fluctuations in traffic load, changes in link bandwidth or reliability, and additions or removals of network devices.
Convergence: it refers to the process by which routers in a network reach a
consistent and synchronized view of the network's topology and routing
information. It involves ensuring that all routers have up-to-date routing
tables that reflect the current state of the network, including any changes in network topology, link costs, or routing paths. Routing algorithms need to converge quickly.
Security: Routing algorithms should incorporate mechanisms to ensure the
security and integrity of routing information and prevent unauthorized
manipulation.
Optimality: Routing algorithms strive to find routes that optimize certain
metrics. 
Simplicity: Routing algorithms should be simple
as possible.
 

5. Classification of routing algorithms

• Static routing and dynamic routing: In static routing, network administrators manually configure routing tables on routers to define specific paths for forwarding packets to particular destinations. This table do not change unless manually modified by the administrator. This kind of routing work in small networks and does not adapt to changes in network conditions. Dynamic routing protocols automate the process of route determination by allowing routers to exchange routing information and dynamically update their routing tables. These protocoles use algorithms to calculate optimal routes and share routing updates with neighboring routers, enabling routers to adapt to network changes in real-time. These protocols are well-suited for large and complex networks where network topology changes frequently or where scalability, resilience, and efficient resource utilization are important. Example: OSPF (Open Shortest Path First), RIP (Routing Information Protocol), EIGRP (Enhanced Interior Gateway Routing Protocol), and BGP (Border Gateway Protocol).

• Link state algorithms and distance vector algorithms: 
  

In link state algorithms, routers transmit routing information to everyone (all the nodes of the same zone), however, routers only send the status of their own links. Each router builds a complete image of the network in its routing table (small updates everywhere).

In distance vector algorithms, each router sends part or the total routing table only to neighbors routers (important updates to neighbors). The first kind of algorithms is more demanding in terms CPU and memory.