Inter-domain Traffic Engineering (TE) is an important aspect of network operation both technically and economically. Outbound Traffic Engineering is less problematic as routers under the control of the network operator are responsible for the way traffic leaves the network. The inbound direction is considerably harder as the way traffic enters a network is based on routing decisions in other networks. There are very few mechanisms available today that facilitate inter-domain inbound traffic engineering, such as prefix deaggregation (i.e., advertise more specific prefixes), AS path prepending and systems based on BGP communities. These mechanisms have severe drawbacks such as exacerbating the increase of the size of global routing table or providing only coarse-grained control. In this chapter, an alternative mechanism is described and evaluated. The proposed solution does not increase the size of the global routing table, is easy to configure through a simple numeric value and provides a finer-grained control compared to currently used mechanisms that also do not add additional prefixes to the global routing table.
TopIntroduction
During the evolution of the Internet, Autonomous Systems (ASes) have become increasingly interconnected. Both at the edge and in the core of the Internet, ASes have continuously increased the number of other ASes they are directly connected to (see e.g. Dhamdhere & Dovrolis, 2008). This trend is mainly driven by the need to increase both capacity and reliability of the connection to the global Internet. Given more than a single attachment point, an Internet Service Provider (ISP) can actually engineer its traffic, i.e., it can influence the way traffic leaves and enters its network.
To do that, ASes need to rely on the Border Gateway Protocol (BGP) (Rekhter, Li, & Hares, 2006), which is used to exchange IP reachability information. BGP however is very limited when it comes to Traffic Engineering (TE). This is especially true for the inbound direction as the flow of traffic depends on the forwarding decision made at other routers in other ASes. In other words, in order to engineer the way traffic enters a network, the route selection process at other routers in other ASes has to be influenced remotely. Unfortunately, BGP has no obvious means built in that allows the origin of an advertisement to express a preference which could be used by other routers in the route selection process.
BGP selects a single best route towards a given destination, whereby a destination is represented by an IP prefix. If more than a single route towards a given prefix is known to a BGP router, it follows an ordered sequence of steps to select the best amongst these routes. This sequence of steps is called the BGP decision process (Rekhter, Li, & Hares, 2006) (see Figure 1). Each step in the process removes routes from the set of candidate routes until a single best route remains, which is subsequently used for packet forwarding.
Figure 1. Pseudo-code for the BGP decision process
The first step in the BGP decision process is to compare an operator set preference value called local preference. The local AS has therefore absolute control over the path selection process. A criterion for such preference could be the business relationship with the neighboring AS, such as customer-provider or peer-to-peer (Gao & Rexford, 2001). In the case that multiple routes are equally preferable as perceived by the local AS, other tie breaking rules are applied. The first one is based on the AS path length. Obviously shorter paths are preferred over longer ones as the AS path length seems a reasonable estimate of quality in the absence of other quality metrics. The decision process continues with comparing the origin attribute, the multi-exit discriminator, preferring routes learnt from external BGP peers (E-BGP routes) over routes learnt from internal BGP peers (I-BGP routes) and comparing the interior cost towards the E-BGP exit router. Finally, tie breakers are employed that have no other significance than having different I-BGP routers consistently choose a single “best” route. In other words, these tie breakers could be replaced by any other deterministic rule which results in a single route being chosen.
The above described process has no mechanism directly built in that facilitates inbound Traffic Engineering (TE). Quoting Internet Engineering Task Force (IETF) Request for Comments (RFC) 3221 (Houston, 2001): “At this stage the only tool being used for inter-provider traffic engineering is that of the BGP routing table”–this has not really changed. In the absence of an explicit mechanism, ISPs have devised means to achieve their goal in three main ways (Van Beijnum, 2002). The first is to make the AS path longer by “prepending” their AS number one or more additional times. The second is making IP prefixes more specific and announcing them selectively. Third, BGP community attributes can be used to perform a limited form of TE. Community attributes (Chandra, Traina, & Li, 1997) are not part of the decision process itself but can trigger certain actions to be applied to an advertisement such as the manipulation of path attributes or filtering.