The evolution of Internet routing

If you ask "how do I get a video from Netflix to my TV screen?" you will probably get a variety of answers depending on whom you ask. Here are a TL;DR of the answers you are most likely to get:

• the home setting answer "your access point gets the video from the Netflix over the Internet and sends it over wifi to your TV" 
• the smart apps and video encoding answer "the Netflix app creates an HTTP request specifying your account and some chunks of the video you are about to watch and the Netflix server replies with HTTP responses that contain the chunks"
• the Internet Protocol (IP) answer "your smart TV creates packets addressed to the Netflix server by its IP address. Based on the IP address, the packets are first sent to the access point which sends it over fiber or telephone landlines to the Internet Service Provider (ISP), like AT&T, the ISP then sends it to other networks which eventually deliver it to Netflix (the ISP can also directly deliver it to Netflix). All this journey is guided by the IP address in the packets created by your TV"

In this blog post, I will focus on the third journey which is so revolutionary that it earned its creator (Vint Cerf) a Turing Award (Nobel Prize of computing). It is also so important to the core operation of the Internet that it is one of the very few things that survived from the inception of the Internet till now. It is also the only "agreement" all participating networks in the Internet has to agree on. The Border Gateway Protocol (BGP) has been at the heart of this consensus for almost 30 years. Like almost any other field, things that require consensus will stifle innovation.

BGP Basics

The Internet, as broadly known, is a network of networks. Each of those networks is called an Autonomous System (AS). All autonomous systems have to be registered (pretty much like all domain names have to be registered) and they have to speak to each other in BGP. In short, BGP is the main language of the Internet. With the rise of the web as the killer app of the Internet and the need for monetization of the networks, BGP became a language that expresses not only how data should flow over the Internet, but who has to pay whom to deliver it. At the time of the development of BGP, the Internet was pretty hierarchical as shown below

from wikipedia

Consumers, which can be home subscribers or web-based services, pay Tier 3 networks (ISPs) which pay Tier 2 and Tier 1 networks (ISPs of ISPs or transit networks) to move data for them. This hierarchy started to create a problem when latency became a main concern for web consumers over the past 15 years or so. Basically, your Netflix video has to travel through the Tier 3 connected to Netflix then up to a Tier 2 and then even to a Tier 1 before going down again to your Tier 3 and then to you.

This increased latency motivated content providers (e.g., Netflix) to create direct links with all Tier 3 networks who are willing to participate creating what is called "peering links" as shown below.

from drpeering

The current state of the Internet has Content Providers connected directly to ISPs through multiple connection points. BGP allows each party to specify their preference of which link to be used for every group of addresses through various ways which are configured in each router. This changed the Internet from a multi-hop network (in terms of Autonomous systems) into a single hop network [1][2]. This "single hop" architecture is much better in terms of latency from the perspective of consumer and in terms of cost from the perspective of content providers and ISPs.

The Problems with BGP

It is clear that BGP has taken us very far with simple language that everyone can agree on. However, BGP has problems that, due to its age, are very well documented and very well known. I will discuss some of the most prominent ones that motivate a need for the evolution.

1. BGP was developed for a relatively small Internet where routers can be configured by people with relative ease. The Internet has evolved and increased in scale orders of magnitude over compared to its younger self. This increase in scale makes the basic task of configuring BGP routers a problematic task that can cause misconfigurations and outages.
2. BGP failures can be expensive which requires robust hardware. Moreover, BGP routers require the moving of terabytes of data per second. These requirements translate into extremely high cost of routers that are relatively rigid and are not flexible enough to support the rapid change in requirements.
3. BGP is not very dynamic as it was developed primarily to connect autonomous system with little to no representation of dynamic load and preferences. However, current networks, where autonomous systems are connected to each other through multiple peer links, have dynamic requirements and require complex operations (e.g., load balancing).
4. Other notable problems include lack of control over end-to-end behavior, routing data based only on destination address without consideration of the source, and indirect expression of policies. For interested readers, check one of the following papers [3][4][5].

Because of these problems, BGP research has been long, innovative, but highly unsuccessful. One main source of the failure is the need for consensus requires that EVERY stakeholder to agree on the change which is highly problematic for many reasons including political and monetary reasons. However, there are some recent approaches that bypass the hurdles against BGP.

Innovations "beyond/around" BGP

To avoid the need for consensus content providers have been attempting to create solutions that allow for avoiding BGP problems while avoiding the need for consensus. The following are the most prominent approaches:

Creating a more compact Internet topology: This approach presents the simplest solution: To simplify the hierarchical tier-based topology of the Internet, lets move the content servers (e.g., Netflix servers) to the ISP. This solution requires coordination between ISPs and content providers, where content providers provide ISPs with hardware that they can place inside their networks. This approach bypasses BGP completely by having content move from content providers to consumers without leaving a single autonomous system. One of the prominent examples of such cooperation between ISPs and content providers is used by Netflix.

from presentation by flavio amaral from Netlfix

As shown in the picture above, the ISP includes the Netflix appliance in their network to serve data directly to users. The appliance periodically collects data from Netflix servers in the cloud and caches it locally. This solution is adopted by a wide variety of content providers (a very nice illustration of their infrastructure is provided by Google here). This approach is convenient despite having scalability problems. The main scalability problem is manifested by the impossibility of providing enough appliances to match the actual infrastructure of Netflix at every ISP. However, this solution was shown to provide good enough improvements in performance compared to traditional approaches.

Leveraging Software Defined Networks (SDNs): SDNs have allowed for rapid evolution of networks by moving the implementation of network rules from individual routers which work in a distributed way, to a central controller that configures all routers which in the case of SDN are simpler than the ordinary ones. This allows for easier configuration of networks and reduction of network cost. It also allows for better network telemetry and expression of policy which can be easily translated into network routing rules. This approach has been mapped to be used to control BGP routers by translating complex policies into BGP rules. Such approach has been used by Google and Facebook to control their peering links. A picture from Facebook's approach is below

from Facebook's engineering blog

As the picture shows, the network collects information about traffic load and possible routes to the same address. Then, based on that data, the controller creates route overrides which are then injected in the BGP peering router to modify BGP behavior. This allows the content providers to choose peering links based on their requirements overcoming some of the problems of the drawbacks of relying solely on BGP.  However, several problems remain unsolved as the rest of the ASes still rely on BGP. Furthermore, solutions presented so far rely on the knowledge afforded by content providers only.

Conclusion

Internet is one the main drivers of innovation in this age, despite lack of innovation in the Internet's infrastructure. Some aspects of this infrastructure has seen some improvements in the past few yeats, but I believe that we are still a long way from an infrastructure that can support dynamic loads and policies that we currently need and will need more to drive more innovation.