BGP Path Selection - What's the right perspective?

Using classical BGP as specified in RFC4271, the routing information a router learns from its neighborhood depends on the perspective of its BGP peers. The peer speakers provide those paths they have chosen as best path and use for traffic forwarding. Simply speaking, we can say that BGP implements a sender-based selection of advertised routing information.

Receiver-based Selection of Advertised Routing Information

A few weeks ago, I wrote about “BGP Optimal Route Reflection”, a new draft that was published a few days before the 79th IETF meeting in Beijing. In principle, the draft proposes to combine classical Route Reflection with a receiver-based selection of routing information: Instead of advertising their own best paths, reflectors shall advertise the best known path(s) according to the topological position of the client. Generally, every client may be provided with different information. Today, I read a post in the blog of Cristel Pelsser, another researcher who is working on solutions for the iBGP anomaly problems. In her post, she describes a new concept of distributed Route Servers that provide routers with customized routing information matching to their topological position. Similar to the centralized iBGP Route Server architecture we proposed in 2009, this scheme implements a received-based selection of advertised routing information. Having now at least three schemes that implement a receiver-based selection of advertised routing information, it seems that this idea attracts the interest of more and more protocol designers and researchers. Thus, let’s have a closer look at the pros and cons of the basic idea.

Advantages of a Receiver-based Selection of Advertised Paths

Realizing iBGP via a full-mesh, a router certainly learns a path that optimizes its traffic forwarding costs (the formal prove may be found in our KIVS 2011 paper). Implementing an information reduction by means of Route Reflection (or AS Confederations), this property gets lost in general. To avoid problems at this point, the routing decision of a Route Reflector must reflect the local views of its clients. This usually limits the topological size of the clusters, which forces Network Operators to set up a high number of reflectors in their ASs.
If the best path decision of a reflector is separated from the information it provides to its clients, it can be located independently of its clients. For example, as proposed by Raszuk et al., this allows operators to centralize the reflectors. In a next step, reflectors may be replaced by several party-centralized Route Servers or even by one centralized Router Server. This may reduce the effort to operate existing or establish new POPs significantly.
Taking Add-path into account, there is no reason why routers should not be provided with several paths. As we could show in 2008, providing routers with several paths that match to their topological position, routing anomalies can inherently be avoided (without affecting the semantics of iBGP), while the scalability of the routing is ensured. Thus, a receiver-based selection of advertised routing information allows us to solve the iBGP anomaly problem in practice.

Drawbacks of a Receiver-based Path Selection

Generally, a receiver-based reduction of routing information comes along with several highly interesting advantages. However, as so often in the real world, advantages come along with disadvantages: Using classical BGP, it is very easy to implement the path announcement process. In principle, a router simply determines and advertises its best path to all BGP peers that do not already know the best path. Using a receiver-based selection of advertised information, deciding which information has to be advertised to which peer is not that easy any more: The sender must see things from the receiver’s topological perspective. In general, this perspective may differ from receiver to receiver, which results in additional effort for the sender. But even if this scheme is more complicated than the classical sender-based selection of advertised routing information, the effort seems to be manageable in practice: Up to step c) of the path selection process (comparison of MEDs), routing decisions are independent of the routers’ topological points of view. The most costly sub-decisions are identical for all routers.

Next Steps

From my point of view, standardizing techniques to implement a receiver-based reduction of routing information is a logical step to ensure scalability and solve the anomaly problem iBGP comes along with. Starting with a concept that extends the functionality of Route Reflectors certainly makes it easy for Network Operators to integrate the concept in their ASs. However, the (formally provable) benefits that come along with a server-based architecture should motivate us to think about leaving the known way of Route Reflection and think about Route Servers.

IETF 79 IDR WG, what's up? Correctness, Correctness, Correctness!

Hi experts,

being concerned about the correctness of the iBGP routing, the recent days were really exciting. Certainly motivated by the upcoming IETF meeting, two new drafts focussing the correctness of the iBGP routing became available. These are the "Stable iBGP Decision Process with Route-Reflection" (available since yesterday) and the "BGP Optimal Route Reflection (BGP-ORR)" (available since 2010/10/16) drafts.

Let's have a closer look at the former draft first: The basic goal of the authors, Jamak et al., is to force stable routing decisions in ASs that implement BGP Route Reflection. To reach this, the authors proposed to prefer paths learned from close Route Reflection clusters over those learned from distant clusters. Technically speaking, they proposed to evaluate the CLUSTER_LIST length right after the LOCAL_PREF, the AS-path length, and the Origin Number (i.e. right before the MED attribute, cf. RFC4271, section 9.1.2.2). In principle, this implements the necessary condition Griffin et al. specified in 2002 to ensure forwarding correctness. So, the basic idea is well known in the scientific community and the resulting property (that is that the routing converges) is formally verified.

Even if convergence independent of any network design rules is an important property, the concept comes along with two fundamental disadvantages that - from my point of view - outweigh the advantages:
Firstly, hot-potato routing is "subverted". Let assume that as shown in figure 1, two paths p and q to the destination exist. Both paths specify the same LOCAL_PREF, AS-path length, Origin Number, peer-AS, and MED. In this case, BGP usually implements hot-potato routing, meaning that traffic is forwarded via the shortest path out of the AS (here path q). In the example I sketched below, the shortest path is the cluster-external path q from v's point of view. Since the cluster-internal paths are preferred, traffic is forwarded via path p. Unnecessary IGP costs are induced.
Secondly, ASs loose the ability to specify primary and secondary exit-/entry-points by means of the MED attribute. If the primary path for a prefix is cluster-external while a backup path for the same prefix is cluster-internal (both paths specify equivalent global path attributes), the backup path is preferred. Obviously, this is highly unwanted. To avoid this problem, Jamak et al. proposed to make use of communities, but realizing this in practice may be difficult in general.

Figure 1: Hot-potato routing does not work.

The second draft, BGP Optimal Route Reflection, is proposed by Raszuk et al.. In contrast to the former draft, the main goal of this proposal is to ensure that hot-potato routing is realized even if Route Reflection is used. Using classical Route Reflection, a reflector provides its clients with its best path. If the topological position of a client differs significantly from the topological position of its reflector, this method may cause situations where routers do not learn the closest exit-point.
In principle, this problem could be solved by using Add-path to advertise all available exit-points to a client. However, as this scheme may cause serious scalability problems in practice, Raszuk et al. proposed to provide clients only with information on their closest exit-point.
Putting aside the principal idea, a very interesting aspect of this draft is the paradigm shift it specifies. While today, the routing information a router advertises is strictly chosen from its local point of view, this drafts recommends to implement a "receiver-based" selection of advertised routing information. In principle, this selection may differ from receiver to receiver. Thinking this idea through to the end, it leads us to a Route Server based iBGP routing architecture (slides), in which every router is provided with specific routing information that ensures optimal, consistent, and stable routing decisions.
Even if ensuring hot-potato routing is an interesting feature, Raszuk et al.'s proposals is only a small step towards inherently optimal routing decisions. Indeed, unnecessary internal forwarding costs are avoided, but traffic may still be forwarded via an exit-point that specifies a suboptimal MED for its peer-AS group. Traffic may be forwarded via backup path into an AS even if the primary exit-/entry-point is available.

Even if the new drafts can sadly not entirely solve the correctness problems of iBGP, I'm really happy to see that network protocol designers working for the global players start to think about the correctness of this protocol. Its still a long path, but I am sure we are on the right way!

UB