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.

November 25, 2010

What do they exactly deny??

I am sure that most people who are interested in Internet Security have heared about the prefix hijacking event that has appeared on April, 8th 2010. Triggered by a U.S. government report published at the beginning of last week, the event gained high attention in media this month. In brief: China Telecom hijacked a huge number of address prefixes for around 18 minutes. 

Plausible Denial

On wednesday last week, reuters reported that "The spokesman of China Telecom Corporation Limited denied any hijack of internet traffic". An interesting questions is what does this exactly mean? Data publicly available in the Internet and gathered from different independent ASs unambiguously show that a high number of public prefixes was hijacked by China Telecom. Of course, traffic directed to these prefixes was hijacked.


As it seems unlikely that China Telecom denies facts everyone could verify in principle, I belive the interpretation I found on seems to be most plausile: They reported that "China Telecom did not deny the incident occurred, but did deny that it intentionally 'hijacked' U.S. citizens' traffic." As described in my last post, this makes pefectly sense.

Prefixes and Traffic

Another aspect I want to mention here concerns the statement you find on several blogs and media that around 11/15/etc. percent of the Internet traffic was hijacked. From the techincal perspective this is not quite correct. Even if the order of magnitude matches the proportion of global prefixes that was hijacked, this does not mean that the same proportion of the global traffic was hijacked: Generally, the amount of traffic forwarded to different address spaces differs significantly. Details on that may be found in the Arbor Networks blog.


November 18, 2010

U.S. Commission accuses China of data hijacking... the title of an article published yesterday on Spiegel Online (German), one of the biggest news-websites in Germany (an article discussing this topic may also be found on Referring to a report published by the United States-China Economic and Security Review Commission on Wednesday, they raise the question whether a prefix-hijacking event observed in April 2010 and caused by a Chinese ISP could have been a deliberated (eavesdropping) attack against the U.S. government and U.S. companies. Even if the article does not give a final answer to this question, it suggests that this interpretation of the event is likely.

Motivated by this interpretation, I had a closer look at this event yesterday evening. The following analyses are based on the data provided by the Route Views Project. The event took place at April 8th, starting at around 3:54 p.m. UTC. At this point in time, AS23724 (China Telecom Corp. Ltd., the largest ISP in the People's Republic of China) started to originate at least 22,311 address prefixes. This is around 6.84% of the number of prefixes covered by the global routing table at this point in time. Before the event started, China Telecom originated 39 global prefixes. The events last for around 18 minutes.

From my point of view, four aspects seem to be relevant to assess the intention behind this event: Firstly, an important question is who is involved in the event. The report tells us that
, a state-owned Chinese telecommunications firm ‘‘hijacked’’ massive volumes of Internet traffic. [...]
China Telecom advertised erroneous network traffic routes that instructed U.S. and other foreign Internet traffic to travel through Chinese servers. [...]
This incident affected traffic to and from U.S. government (".gov") and military (".mil") sites, including those for the Senate, the army, the navy, the marine corps, the air force, the office of secretary of Defense, the National Aeronautics and Space Administration, the Department of Commerce, the National Oceanic and Atmospheric Administration, and many others. Certain commercial websites were also affected, such as those for Dell, Yahoo!, Microsoft, and IBM.
Even if this is indeed right, also organizations and companies from other countries were affected. Examples are France Telecom (, Vodafone Ireland (e.g., Sanyo (, the Russian Institute for Public Networks (, the Australian Department of Defence (, and ChinaNet (many, many 110.x.x.x/24 networks), but also a lot of other companies and organizations could be mentioned. In fact, most parts of the "first world" were affected (the full list of Org-Names can be found here).

The second important aspect is the precision of the "attack". The event that has appeared on April 8th affected a lot of different organizations: We find the U.S. government, government organizations from other countries, business concerns from Europe, telcos from Asia, but also several other companies and organizations from many different countries. Obviously, purposefully redirecting such different kinds of traffic at the same time to the same destination does not really makes sense in practice.

Thirdly, the duration of the event should be kept in mind. 18 minutes is not that much time. It's seems not to be long enough to hijack specific information from any of the affected organizations (even if it is theoretically indeed enough time to gather IP- or mail-addresses). However, it seems long enough to identify and correct an error in the configuration.

Fourthly, China Telecom did not try to hide the prefix hijacking. In all new AS-paths, AS23724 can be identified as origin of the information announcement. After a few minutes, the event and its origin was clearly visible in the whole world.

All in all, from my point of view, an intended hijacking of network traffic is highly unlikely. I would guess that we have observed a simple but fatal configuration failure. If someone would try to hijack or eavesdrop on traffic, a plausible strategy would be to attack few prefixes that belong to one target. Most likely, the attacker would try to cloud the attack or at least its source, for example by manipulating parts of the AS-path.

However, even if we have observed most likely a simple misconfiguration event in this case, the basic problem lasts: BGP is highly vulnerable to misconfiguration and intended attacks. Most likely, a good attack could be hidden effectively today. But the report also has an upside: Politicians and the public start to become aware of the problem.


Update: Of course, I am not the only one who had a closer look at the hijacking event on April, 8th 2010. Some further interesting details may be found in the renesys and Arbor Networks blogs.