[Review] Understanding BGP Misconfiguration

This paper presents a quantitative study on BGP misconfigurations. Specifically, it focuses on the frequency of misconfiguration and its impact to global connectivity and routing load, causes of misconfigurations, and some proposed resolution to reduce frequency and impact.

The paper starts off with an overview of BGP. BGP is a path vector routing and policy based protocol used by autonomous systems to exchange routing information with each other. This protocol is used to ensure connectivity of customers to the Internet. However misconfiguration of BGP may result in network outages, isolation of web-based services, and redirection of traffic to different paths. The authors categorized BGP misconfigurations into two: origin misconfiguration and export misconfiguration.  Origin misconfiguration happens when AS accidentally injects a prefix into global BGP tables. This includes failure of summarizing an address space, hijacking, and propagating private network prefixes. Export misconfiguration, on the other hand, is more inclined to policy violation of one of the ASes in the AS-path. The authors choose to focus on these two kinds of misconfigurations because they have the greatest potential to disrupt connectivity in the network.

To analyze these misconfigurations, the authors used RouteView’s BGP listener. They identified misconfigurations based on short-lived changes that lasts less than a day. To further understand the nature of these short-lived routes, the misconfigurations were further classified into various categories such as self-deaggregation, related origin, and foreign origin for origin misconfiguration. For export misconfiguration, since the AS relationships are closely guarded secrets by commercial ASes, they used Gao’s inference on AS relationship and commonly observed behaviors. With this, they also classified export misconfiguration into four categories: Provider-AS-Provider, Provider-AS-Peer, Peer-AS-Provider, and Peer-AS-peer.

Aside from just observing the data from the BGP listener, they also conducted email surveys to operators and conducted connectivity testing. The email survey is to disambiguate the intentions of the network provider and the connectivity testing was used to verify the results of the email surveys.

Result shows that at least 72% of new routes seen by routers are short-lived, meaning, they can be results of misconfiguration. The results also show 0.2-1% of the global table size suffer from misconfiguration each day. The routing load also shoots up to 60% for extreme cases, however, connectivity was found to be robust to these misconfigurations.

After measuring the extent of misconfiguration in the network, the author tried to find the causes of these misconfiguration. They found out that most misconfiguration are due to human error whether in execution (slips) or in the plan (mistakes). They also uncovered potential bug in the software of major router vendors. They also found out that common practice that led to undesired behavior during failures were the ultimate cause of export misconfiguration.

Lastly, the authors proposed techniques to lessen BGP misconfiguration. First they proposed user interface to lessen human error instead of command line interfaces. Next is to create software to check routing policies and database consistency. Lastly, they propose to extend the BGP protocol to prevent misconfiguration.

General comments:

  • The authors described difficulties they encounter in their data gathering and analysis and they were honest enough to discuss possible inaccuracies in their work.
  • They were also optimistic and their proposed solution is now being used in software defined networks (SDN).
  • Tables and graphs were helpful in summarizing the discussion.
  • Flow of discussion is easy to follow.

[Review] Interdomain Internet Routing

This paper describes routing from different domains throughout the internet. It tackles autonomous systems and how ISPs exchange routing information with each other and generate money from customers. It also discusses basic concepts of BGP routing protocol and cited some real world scenarios wherein BGP was misconfigured thus making a web application inaccessible.

I find the discussion of this paper easy to follow. First, the paper first describes about autonomous systems and the internet backbone. I learned that the internet is not only composed of routers connected in a fault tolerant network, rather, each network is grouped into domains connected to an ISP (Internet service providers). ISPs are categorized into different groups according to scope. The tier-3 ISPs caters for local customers found in a certain geographic location;Tier-2 ISPs has a regional scope (i.e. state-wide or region-wide); And tier-3 for global scope. Next the paper discusses inter AS relationship in which it describes transit and peering. Transit relationship is equivalent to provider-customer relationship wherein the provider AS provides routes and forwards packets from the customer AS. The transient relationship involves financial settlements wherein the customer AS pays for the service provided by the provider AS. Peering relationship on the other is a business deal but sometimes doesn’t involve financial settlements. Peering happens when two ASes (often business competitors) provide mutual access to each other. This relationship is mostly applied to Tier-1 ISPs to avoid monopoly and ensure default free routes. Another reason for peering relationship is for ISPs to save money and making services from different ISPs accessible to their customers. Lastly, the paper describes how ASes generate money and save money by exporting and importing routes. In importing the routes highest priority is given to customer routes since customers pay and expect good service from providers. Next, ASes prioritize routes from peers since they don’t have any financial settlements with them.  The least priority is given to provider routes since ASes doesn’t want to spend money paying providers for traffic destined to its direct customers. For exporting routes, the ASes export all routes to transit customers, some routes to peer customers and doesn’t export routes to transit providers.

Another topic discussed in this paper is the BGP or Border Gateway Protocol. First, it discusses scalability, policy, and cooperation under competitive circumstance as BGP’s main design goals. BGP is actually a network layer protocol used to exchange routing information from different domains or ASes. To start participation, border routers establish BGP sessions—TCP connection to the BGP ports—to other border routers. After establishing session, it will send OPEN message as handshake for the two routers. After OPEN is completed, both the routers can exchange tables using route UPDATE wherein routes can either be imported or withdrawn in the router’s table.

The paper also discusses external BGP (eBGP) and internal BGP (iBGP). eBGP are used by border routers communicating with another border router from different AS. This is the “standard” mode in which BGP is used. To preserve all information about routes gleaned from eBGP sessions, it is best to run BGP sessions inside an AS as well. Thus iBGP for border routers located in the same AS was created. The paper also described key BGP attributes such as the NEXT HOP attribute, AS path, LOCAL PREF, and Multiple-Exit Discriminator (MED). The BGP path selection criteria prioritize LOCAL PREF over ASPATH, ASPATH over MED, MED over eBGP, eBGP over iBGP, iBGP over lowest IGP path, and lowest IGP path over Router ID.

Lastly the paper cited some BGP issues such as route and prefix hijacking resulting, BGP misconfigurations and convergence problems. It cited a some real life example of BGP misconfiguration such as youtube being inaccessible due to Pakistan government’s route advertisement to PCCW and to the whole internet and email spamming using hijacked prefixes. To prevent routing advertisements from propagating throughout the network, each router implements a route flap damping scheme by not paying attention to frequently changing advertisements. However this can cause an increase in convergence time and performance issues.

The paper stated that BGP is actually a simple protocol but its operation in practice is extremely complex. In a large scale perspective, misconfiguration of routes may lead to inaccessible services and congestion in the network. Despite much activity, further research is still required to make inter domain routing more resilient.

Overall, I find the paper interesting and easy to read. The paper is well organized and the ideas are presented in orderly fashion. One strong point for this paper is that it describes only an overview of BGP and leaves RFC for curious and interested readers. Most of all, terminologies presented are also well defined, making discussions easy to understand (no need to consult google for networking jargons).

[Review] Rethinking the design of the Internet: The End to End Argument vs the Brave New World.

The end to end argument is a key principle that shaped the early internet. It suggests that application level functions should be built in the network edges rather than in the network core. One reason is because when functions are developed in the network core, applications from the edges might be affected. Thus, network core was simply designed to focus on routing and transporting data.

Today’s internet, however, is much complicated compared to the early days. Originally, messages that were sent were only understood by the end users that has knowledge of the underlying protocol. Anyone trying to interrupt the communication or sniff packets without prior knowledge of these protocols used will not succeed. However, there is a shift from designing the internet for military purposes to designing it for public use. Nowadays, protocols used are being reviewed by the public and the internet is becoming more and more commercialized.

This paper tackles the shift from the old design perspective of the internet due to behavior and needs of the users. Nowadays, nodes will require communication but doesn’t necessarily trust each other. When performing banking transactions through the internet, a user may question the “authenticity” of the website of the bank. For this case, privacy and security should be both implemented in the network edge and in the core. Another example cited by the authors was email spams. During early days, advertisements and spams may flood a user’s inbox and it was the responsibility of the users to delete them. This was deemed costly by many users so nowadays, email classification and filters are implemented at the core to remove or sort these messages.

The message of this paper is that the Internet must accept changes to meet the demands of new users. Flexibility, open-mindedness, and support for innovation of the Internet architecture must be conserved. End-to-end argument should still be applicable to some extent. However, this should not be imposed as a strict guideline. User input and experience is very much necessary in designing the new internet. Network architects should open their minds and embrace these new challenges and concerns from new generation users.

[Review] A Protocol for Packet Network Intercommunication

This paper brings us back to the time wherein protocols for packet switched network communication are still being created. During that time the major challenge is the different behaviors of each network – how the network reads address, how big are the packet sizes, how the network deals with lost packets, how they fragment packets, timings, among others. The proposal of the authors is to create a protocol that that provides for these variations – to support communication and data sharing between nodes from different packet switching network.

The paper presented the ideas in chronological order making them easy to read and understand. First the authors discussed internetwork protocol issues such as the ones described above. Next they  discussed gateways as interfaces to these packet switched network and how it should handle internetwork packets in standard format. Afterwards, they described process level communication wherein they argued that every packet must contain a process header to determine the correct process for arriving packets. Then they discussed segment and packet formats with mentions of address formats, TCP addressing, and port addressing. The internetwork header contains the sequence number, byte count, flag field, and check sum which were used for reassembly and sequencing in the receiving node. Next they discussed the window strategy step-by-step for retransmissions and duplicate detection in senders and receivers. They also discussed acknowledgements for flow controls, input/output handling, TCP process communication, connections and  associations, and associations within connection-free protocols.

It is also surprising that TCP was originally designed just for communication between two nodes from different. Network congestion was not initially considered as a design constraint maybe because only few nodes are participating in the network during their time. It is also interesting to note how design considerations were very much simpler in the early days unlike today wherein millions of people are using the internet.

Hello world!

Welcome to WordPress.com. After you read this, you should delete and write your own post, with a new title above. Or hit Add New on the left (of the admin dashboard) to start a fresh post.

Here are some suggestions for your first post.

  1. You can find new ideas for what to blog about by reading the Daily Post.
  2. Add PressThis to your browser. It creates a new blog post for you about any interesting  page you read on the web.
  3. Make some changes to this page, and then hit preview on the right. You can always preview any post or edit it before you share it to the world.