Routing Strategies for IP Networks
Traffic routing within a telecommunication network defines how the traffic matrix is mapped on the network topology. Routing mechanisms are thus identified as an essential feature in the control of the network performance [Awduche_1]. The routing mechanisms involved allow assigning the network capacities, more or less efficiently, to the demands. The routing choice has a direct impact on the existence and location of congestion within the network. A high level of congestion may decrease the grade of service (call blocking, increased delays, packet losses, etc.).
Routing mechanisms within an IP network may induce some restrictions on the path choice related to the path selection algorithm. The problem occurs more specifically in the case of IP networks running an IGP (Interior Gateway Protocol) routing protocol. In this case, the routes derive from very simple routing algorithms (shortest path calculations) which offer only limited control over the routing paths. This often leads to a sub-optimal utilisation of the network resources. Today several new mechanisms are proposed to increase the routing control and to optimise the network performance, and among them MPLS. However, such mechanisms also introduce some complexity in the network management. We try to analyse the compromise between routing performance and complexity. We propose two off-line Traffic Engineering methodologies: the first one is based on an IGP/ MPLS architecture; the second one is based only on the IGP routing using an optimised load balancing scheme.
Some Static Routing Patterns
We first need the following definitions:
Network topology: We assume that we can represent the network topology as a simple non oriented graph that is represented by its nodes and edges. Multiple parallel links are represented by a unique edge between the nodes.
Routing pattern: For a given network topology, we define a routing pattern as a set of (possibly multiple) directed routes between pairs of nodes in the network. If there is at least one route in each direction between each pair of nodes, the routing pattern is fully meshed.
Various static routing patterns are introduced here with their possible realisation in an IP intradomain network. We also focus on some specific IP routing strategies based on the modification of the IGP routing with ER-LSP (Explicit Routed Label Switched Path) created with MPLS. Though In the sequel the terms ER-LSP, tunnel, and MPLS tunnel are indifferently used.
Single-path Routing Patterns
In a single-path routing pattern there is at most one route between each pair of nodes. We can distinguish symmetric single-path routing patterns if the paths between A and B and B and A use the same edges for all pairs of nodes (A,B). Single-path routing patterns may be divided into the following interesting sub-classes:
- Shortest path routings patterns: If there exists a metric (a set of pairs of values, one for each direction, on the edges of the network) such that all paths of the routing pattern are a shortest path between the end-points according to that metric. A special case is when all shortest paths are also unique (unique shortest path).
- Routing patterns satisfying a sub-optimality (SO) property: Two given paths having two points in common satisfy the sub-optimality condition if they share the same sub-path between these two points (check below image). Note that this sub-optimality condition excludes traffic load balancing and load distribution which aim to divide at an intermediate node the traffic toward the same destination on several distinct paths. Note also that routing patterns satisfying the SO condition are necessarily symmetric. Routing patterns based on unique shortest paths satisfy the sub-optimality condition when the metric values are the same on the two interfaces of a link
- Destination-based single-path routing: Any packet is forwarded through the network using the destination address. Obviously, shortest path routing and sub-optimal routing are also based on destination. However, this class of routing patterns is larger. In fact, this is equivalent to establishing a spanning tree for each destination. The destination trees can be completely independent.
- General single-path routing patterns without constraints: The whole traffic demand between an origin-destination pair is routed through a single path without any additional constraint. – In an IP network running a classical IGP routing protocol, only shortest path routing patterns can be realised. Other single-path routing patterns can be realised with the explicit routing functionality enabled by MPLS (strict ER-LSP). As an ER-LSP is always unidirectional, symmetric or directional routing patterns can be realised. When the routing pattern is fully meshed, the total number of ER-LSP to create is equal to n * (n – 1) where n is the number of nodes.
Multi-path Routing Patterns
In a multi-path routing pattern, traffic between two nodes can be forwarded among several distinct paths.
In IP networks, load sharing can be achieved at an intermediate node in multiple ways: on a packet per packet basis, or with a hashing function evaluated from the information read in the packet header, etc. A hashing function based on the origin and destination can achieve sufficient granularity in a core network.
- An IGP routing protocol can provide multiple equal cost paths between which load sharing can be implemented. Because there is no information in current IGP routing protocols about traffic loading on distant links, techniques have been utilised to divide traffic somewhat evenly among the available paths. Those techniques are referred to as Equal Cost MultiPath (ECMP). A classical utilisation of ECMP is to assign the same metric to parallel links between two routers so that all those links will be used to forward traffic. This is thus equivalent to single-path routing in our topology model where we consider multiple parallel links as a unique (aggregated) link. Another technique, Optimised MultiPath (OMP) [OSPF-OMP], tries to adjust the load balancing parameters at each node in function of the network load. This requires significant changes to the IGP because dynamic information is needed in each router about link loads in the network. This proposition was never implemented;
- General ECMP: Instead of splitting the traffic evenly between the shortest paths, we can split it in any arbitrary way. In fact, it is very easy to see that when no particular routing constraints are added (number of hops for example), the link loads of any multi-path routing pattern can be reproduced by a routing strategy where forwarding is based only on destination. That is to say, a node B which has to route a packet to A, will randomly choose a path (an interface) using only the destination address. In other terms, if a certain proportion of the traffic demands from C to A and from D to A, uses B as an intermediate node, then this traffic will be split in the same way between B and A whatever the origin (C or D) (check below image).
- With MPLS, several tunnels can be opened between a pair of nodes, and traffic can be arbitrarily shared among them
Specific Routing Patterns in IP Networks
The realisation of the routing patterns mentioned above is based either on the IGP routing or on administratively configured TE tunnels. Both mechanisms can be integrated: the IGP routing can be modified to take into account TE tunnels. Three different models can be identified: in the first two models, only the path selection process of the IGP in a node is modified taking into account the TE tunnels originating at this node, in the third model TE tunnels are advertised by the IGP protocol.
- “Basic IGP Shortcut”: If a packet arrives in a router where a tunnel originates with remote egress equal to the destination of the packet, then the packet is forwarded to the destination. Otherwise the packet follows the classical IGP routing;
- “IGP Shortcut”: In this model proposed in the IETF [Smit], the shortest path calculation in the routers remains unchanged but the determination of the next hop is modified in the following way: if a tunnel originates in the router with its egress belonging to the shortest path, then the packet will be forwarded in this tunnel;
- “Advertise tunnels into the IGP”: In this model implemented by some manufacturers, tunnels are advertised in the IGP and used in the shortest path calculations as virtual interfaces.
Depending on implementation details and in particular on the tunnels metric assignment, many different options are possible in the path selection process. They give more flexibility to the current IGP routing protocols: the resulting routing patterns will not necessarily be shortest paths, nor satisfy the SO condition, nor even be destination based