Routing protocols and architectures/Forwarding and routing

Routing is the process which determines the 'best' path for a packet and sends it out toward the destination:

• routing algorithm: it is in charge of deciding the paths to take for incoming packets:
  1. it determines the destinations reachable by each node;
  2. it computes the best paths (according to certain criteria) in a cooperative way with the other nodes;
  3. it stores local information in each node;
• forwarding algorithm: it is in charge of taking the path decided for each incoming packet:
  1. it performs a lookup in the local information computed and stored by the routing algorithm;
  2. it sends the outgoing packet along the best path.

Routing protocols differentiate into two classes:

• Interior Gateway Protocol (IGP): it includes the protocols used in intra-domain routing (e.g. RIP, IGRP, OSPF) to propagate routing information inside an Autonomous System;
• Exterior Gateway Protocol (EGP): it includes the protocols used in inter-domain routing (e.g. BGP) to propagate routing information between Autonomous Systems.

According to the OSI model, routing is a feature proper to the network layer, but it can be implemented at different layers:

• routing is implemented altogether at the network layer by protocols such as IP, X.25 and OSI/Decnet;
• some of the routing algorithms are implemented at the data-link layer by protocols such as Frame Relay and ATM and by bridges in switched LANs.

Modern routers implement two tables:

• Routing Information Base (RIB): it is the classical routing table listing all the destinations reachable within the network;
• Forwarding Information Base (FIB): it is a routing table optimized to speed up packet forwarding:
  • dedicated hardware: TCAMs are able to store bits whose possible values are 0, 1 and 'don't care' → the netmask is integrated in the network address itself: each bit in the aggregated part has value 'don't care';
  • cache: the FIB only includes the last used destination addresses;
  • additional information: output port, destination MAC address.

Forwarding algorithms

Routing by network address

• Each node is identified by a network address.
• Each packet contains the address of the destination node.
• Each node contains the list of the reachable destination addresses with their corresponding next hops.

When a packet comes, the node uses the destination address included in it as the 'key' in the forwarding table to find the next hop.

Advantage

It is a simple and efficient algorithm because it is stateless: packet forwarding takes place regardless of the forwarding of other packets, that is the node once a packet is forwarded will forget about it.

Disadvantage

It is not possible to select different routes for the same destination based on the kind of traffic for quality of service.

Adoption

Connectionless protocols (such as IP) typically use this forwarding algorithm.

'Coloured path' technique

• Each path between two nodes is identified by a PathID ('color').
• Each path contains a label corresponding to the PathID of the path to follow.
• Each node contains the lists of PathIDs with their corresponding output ports.

When a packet comes, the node uses the label included in it as the 'key' in the forwarding table to find the output port.

Advantage

Several paths towards the same destination are possible → it is possible to choose the best path based on the kind of traffic for quality of service.

Disadvantage

The PathID is global:

• path 'colouring' must be coherent on all the nodes over the network;
• scalability: the number of possible paths between all the node pairs in the network is very big → a lot of bits are needed to encode each PathID, and it is hard to find an identifier which has not been used yet.

Label swapping

Label swapping in an MPLS network.

The forwarding table in each node contains the mapping between the labels of the input ports and the labels of the output ports, including entries like:

<input port> <input label> <output port> <output label>

When a packet comes, the node uses the label included in it and the input port as the 'key' in the forwarding table to find the output port, and it replaces the current label in the packet with the output label.

Advantages

• scalability: the PathID of the path to follow is not global, but the label is decided locally node by node, and it must be coherent only between the nodes to the link endpoints:
  • labels are made up of less bits because they have to encode less paths;
  • each node must know only the labels of the paths crossing it → the forwarding table is smaller;
• efficiency: label swapping is fast with respect to forwarding algorithms such as 'longest prefix matching' in IP.

Adoption

Label swapping is used by:

• telecommunication-derived network technologies (e.g. X.25, Frame Relay, ATM): label swapping allows quality of service, a feature considered as important by the world of phone operators;
• MPLS: in the backbone paths are in a fairly limited number and quite stable because they are created not end-to-end but in the MPLS cloud, where the network topology changes less frequently and traffic is more regular with respect to edges.

Path setup

When a host wants to generate and send the first packet toward a destination, how does it ask for setup of a new path and which label should it use?

Manual setup

Paths and their corresponding labels are manually set by the network administrator.

Disadvantages

• high risk of human configuration mistakes;
• no automatic re-routing in case of faults;
• not suitable for highly dynamic networks where users frequently ask for new paths.

On-demand setup

A signaling phase for path setup, that is for preparing labels in every node, is required, after which the host learns the label to use and it can send the first packet toward the destination.

Advantages
Quality of service is simpler:

• it is possible to set up different paths based on the source asking for its setup (e.g. the rector can have a path privileged compared to the researcher);
• it is possible to include inside the signaling packet a piece of information specifying how much bandwidth to reserve for the path.

Disadvantages

• complexity: signaling is achieved through another forwarding technique (e.g. routing by network address) over a dedicated circuit → complexity increases because the network must now manage two different forwarding techniques;
• scalability: if the path is long and the number of nodes to cross is high, the signaling phase may last too long, especially if the communication sessions are quite short like in the network world.

Source routing

The sender host writes into the packet itself the whole path which must follow to arrive at the destination.

Advantage

Internal routers in the network are extremely simple.

Disadvantage

The sender host must know the network topology and must interact directly with the other hosts in order to be able to compute paths → this breaks the paradigm according to which end users should just send packets and the network is in charge of forwarding packets toward their destinations.

Adoption

IPv4 and IPv6 contemplate an option affecting the path of packets.

Comparison

Routing by network address

• + simplicity: no setup, no state
• + scalability (forwarding): no 'per-session' state (stateless)
• − efficiency: big packet header
• − scalability (routing): very big routing table
• − reliability: difficult to guarantee the service
• − multipath: it does not support multiple paths between two entities

Label swapping

• + scalability (routing): reduced routing table
• + efficiency: small packet header
• + guarantee of service: possibility to guarantee the service (path booking)
• + multipath: multiple paths allowed between two entities
• − scalability (setup): processing of the packets for path setup (critical with 'short' sessions)
• − scalability (forwarding): 'per-session' state (needed for quality of service)
• − complexity: path setup (path setup process, ad-hoc forwarding for path setup packets)

Source routing

• + efficiency (routers): intermediate systems are extremely simple
• − efficiency (sources): end systems should worry about computing paths