November 27, 2010

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.

No comments:

Post a Comment