Routing protocols and architectures/Hierarchical routing

Hierarchical routing allows to partition the network into autonomous routing domains. A routing domain is the portion of the network which is handled by the same instance of a routing protocol.

• Example: forwarding of a packet from node A to node H.
• 
  View from domain A.
• 
  View from domain B.

Routers belonging to a domain do not know the exact topology of another domain, but they only know the list of destinations included in it with their related costs (sometimes fictitious) → a good choice to reach them is to take the best exit path toward the target domain across a border router.

Every border router has visibility on both the domains which it interconnects:

• it is called egress router when the packet is exiting the domain;
• it is called ingress router when the packet is entering the domain.

Hierarchical routing introduces a new rule for handling the routes related to destinations which are outside the current domain:

• internal destinations: if the destination is inside the same routing domain, the routing information generated by the "internal" routing protocol has to be used;
• external destinations: if the destination is inside another routing domain, traffic has to be forwarded toward the closest egress router out from the current domain to the target domain, and then the latter will be in charge of delivering the packet to the destination by using its internal routing information.

The sub-path from the source to the closest egress router and the sub-path from here to the final destination taken individually are optimal, but the overall path which is their concatenation is not optimal: given a destination, the first part of the path (source-border router) is the same for all the destinations in the remote domain.

Motivations

• interoperability: domains handled by different routing protocols can be interconnected;
• visibility: an ISP does not want to let a competitor know details about its network;
• scalability: a too wide portion of network can not be handled by a single instance of a routing protocol, but needs to be partitioned:
  • memory: it excludes information about the precise topology of remote domains, reducing the amount of information which every router needs to keep in memory;
  • summarization: it allows to announce a 'virtual' destination (with a conventional cost) grouping together several 'real' destinations (e.g. in IP networks multiple network addresses can be aggregated into a network address with a longer netmask);
  • isolation: if inside a certain domain a failure occurs or a new link is added, route changes do not perturb other domains, that is routing tables in routers of remote domains stay unchanged → less transients, more stable network, quicker convergence.

Implementations

Hierarchical routing can be implemented in two ways (not mutually exclusive):

• automatic: some protocols (such as OSPF, IS-IS) automatically partition the network into routing domains (called 'areas' in OSPF);
• manual: the redistribution process can be enabled on a border router to interconnect domains handled by even different routing protocols.

Partitioned domains

A domain becomes partitioned if starting from a border router it is no longer possible to reach all its internal destinations through paths always remaining within the domain itself.

Example of partitioned domains.

In the example in the side figure, the packet sent by node A exits routing domain A as soon as possible, but once it has entered domain B it can not reach final destination H due to the link failure between the border router and node I. Really an alternative path exists leading to destination H across the other border router, but it can not be taken because the packet would be required to exit domain B and cross domain A.

Moreover, paths can be asymmetrical: the reply packet may take a path other than the one taken by the query packet, by going across a different border router → data may be received, but ACKs confirming they have been received may go lost.

Solutions

• links inside every domain can be redounded to make it strongly connected, to avoid that a link failure could cause a domain to be partitioned;
• the OSPF protocol allows the manual configuration of a sort of virtual tunnel between two border routers called Virtual Link.

Redistribution

Redistribution is the software process, running on a border router, which allows to transfer routing information from a routing domain to another one.

Example of redistribution.

In the example in the side figure, destinations learnt in a RIP domain can be injected into an OSPF domain and vice versa.

Remarks

• The command for redistribution is unidirectional → it is possible to do a selective redistribution in one direction only (for example the ISP does not accept untrusted routes announced by the customer).
• Redistribution can be performed also among domains handled by instances of the same protocol.
• Routes learnt by the redistribution process can be marked as 'external routes' by the routing protocol.

Costs

Routers in a domain will know a broader set of destinations, even if some of them may have a 'wrong' (simplified) topology: in fact the redistribution process can

• either keep the cost of the original route, at most fixed by a coefficient,
• or set the cost to a conventional value when:
  • the two protocols use different metrics: for example a cost learnt in 'hop count' can not be converted to another one using 'delays';
  • multiple destinations with different costs are aggregated into a summarized route.

Main default administrative distances in Cisco routers.

Route source		Administrative distance
connected interface		0
static route		1
dynamic route	external BGP	20
	internal EIGRP	90
	IGRP	100
	OSPF	110
	RIP	120

When a destination is announced as reachable by both the domains, handled by routing protocols with different metrics, how can the border router compare costs to determine the best route toward that destination? Each routing protocol has an intrinsic cost pre-assigned by the device manufacturer → the router always chooses the protocol with the lowest intrinsic cost (even if the selected route could be not the best one).