The main function of the network layer is to route packets from the source machine to the destination machine
The routing algorithm is used to decide which output line an incoming packet should be transmitted on
– For datagram networks this decision must be made anew for every arriving data packet since the best route may have changed since last time
– For virtual circuit networks this decision is made only when a new virtual circuit is being set up Thereafter, data packets just follow the previously established route
•A router performs two tasks:
– To forward the incoming packet according to the routing table Forwarding
– To fill in and update the routing table Routing
• Desirable properties in a routing algorithm:
– Correctness simplicity no comment
– Robustness : The routing algorithm should cope with changes in the topology and traffic without requiring all processes in all hosts to be aborted and the network to be rebooted every time some router crashes.
– Stability A stabl e algorithm reaches equilibrium and stays there.
– Fairness Efficiency: Conflict between fairness and efficiency
•Classes of routing algorithms
– Nonadaptive algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead, the choice of the route to use to get from I to J (for all I . and J) is computed in advance, off line, and downloaded to the routers when the network is booted.
–Adaptive algorithms, in contrast, change their routing decisions to reflect changes in the topology, and usually the traffic as well.
They differ in
•where they get their information,
•when they change the routes,
•what metric is used for optimization.