Explain the routing principles and its algorithms.
The main functions of the network layer is routing packets from the source machine to the destination machine. The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted … on.
Routing principle : making the decision which routes to use. Also it is responsible for filling in and updating the routing tables.
Properties of routing algorithm:
- correctness
- simplicity
- robustness
- stability
- fairness
- optimality
Routing algorithms can be grouped into two major classes: Non-adaptive (static) and adaptive(dynamic)
Non-adaptive: do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead, the choice of the route is computed in advance,offline
- a network administrator configures information about remote networks manually (add/delete static routes)
- manual maintenance of routing table require lot of administrative time
- not scalable
- default administrative distance=1
- sometimes used for backup purpose
Adaptive algorithm:
- uses a route that a routing protocol adjusts automatically for topology or traffic changes
- avoids the time-consuming and exacting process of configuring static routes.
- two types: Distance vector and link state
Distance Vector:
- passes periodic copies of a routing table from router to router. Each router receives a routing table from its directly connected neighbor routers.
- also called Bellman-ford algorithm
- Eg: Routing Information protocol (RIP), Interior Gateway Routing Protocol (IGRP), Enhanced IGRP (EIGRP), Border Gateway Protocol (BGP)
Link state routing:
- also called Dijkastra’s algorithm or the shortest path first (SPF) algorithm
- maintains a complex database of topology information
- maintains full knowledge of distant routers and how they interconnect
- eg: open shortest path first (OSPF)