October 30, 2010

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 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!


October 24, 2010

My very first post - or: about this blog...

Hi folks,

I spent the last few minutes to think about the topic of the first post on "IDR issues". For sure, the best I could do is to use this opportunity to introduce myself and explain the basic idea behind this blog.

So, let's start with the latter: "IDR issues": what is this blog about? A brief look at wikipedia is not really helpful at this point: "Indonesian Rupiah" or "Inner Distribution Road" is not what I have really in mind with IDR. IDR stands for "Inter-Domain Routing", which - simply speaking - terms routing of global addresses in the Internet. Today, the Border Gateway Protocol (BGP) is used for that purposes.

Even if the Border Gateway Protocol works fine in principle, BGP in its current state seems not to be the answer to everything. For example, by applying common (Autonomous System-)internal BGP schemes like BGP Route Reflection and AS Confederations, routing may end up in sub-optimal or inconsistent states. Routing processes may behave non-deterministic or even non-convergent. Besides operational problems, also security problems are present: In principle, it is really easy to hijack IP address space or eavesdrop on someones global network traffic. Obviously, all these possibilities are highly unwanted and problematic. Discussing these - for many, many people highly important but yet unknown - aspects and potential problem solutions is what I want to do in this blog. So, this is another technical geek blog ;-).

After sketching the basic idea behind this blog, its a good idea to introduce myself. My name is Uli Bornhauser. I am a computer scientist at the University of Bonn, Germany, and researching in the area of the correctness and security of the Border Gateway Protocol. If you are interested in more details, you can have a look at my website.

Finally, I want to say a few words about the "comment policy". If you have any remarks or suggestions, I'm very happy to hear about them! For that purpose, you can use the "post a comment" function you usually find at the end of each post or directly send me an email. You find my email address on my website.

For the future, I plan to write new posts every few weeks. Looking forward to see you again...

photo taken at "The Cell", Denver, CA, USA