Modeling Autonomous System Relationships using Heuristics

TEMPLATE

Inside the Internet and the BGP

This lecture notes by Hari Balakrishnan and Nick Feamster entitled “Interdomain Internet Routing” is about the Internet's routing process and architecture. The author tried to explain the concept that even non computer science (or computer science related) people can understand it. In this blog entry I will only briefly summarize and cite important details on the different topics on the paper.

The Internet is composed of different Autonomous Systems, or AS, which are connected by routers to exchange information. These ASs are controlled by Internet Service Providers, or ISP (ISPs are the one that provide us internet services!), or by large corporations. The Routing protocols within an AS are called Interior Gateway Protocols while the routing between ASs are controlled by the Border Gateway Protocol. BGP is created to provide reachability announcements of an AS (AS<-->AS reachability). BGP can also have its own routing policy in choosing the optimal or best route. A provider gives internet connectivity to a customer, and the customer pays the transit cost (transit is the provider->customer relationship. A provider can be an ISP or a university while the customers are the home users or other small ISPs). But a customer does not need to pay transit cost to two providers if the customer needs the services of the two providers. Instead, the two providers can negotiate to each other for exchange of traffic to allow the customer to access the services of the other provider for free. This is called peering (peering between two providers).

The BGP protocol runs on top of TCP protocol and is usually a router-to-router connection. It operates by first establishing a TCP connection on the BGP port. After that a router can now send update messages which is either announcements (add/modify new routes) or withdrawals (delete routes). An announcement update is constructed by an IP prefix plus an attribute. The attribute is primarily used for route selection. The router also sends keep-alive or heartbeat messages to maintain the BGP connection.

BGP uses attributes to decide in which route to select (AS<-->AS routing). I will only show the top 3 attributes used for route preference. One is the local preference attribute. It used to prefer directly an exit point from the local AS for a specific route, and is the top priority in route preference. Another is ASPATH attribute. Before an announcement from an AS source leaves the AS to search the best route, it appends an ASPATH code from the AS it left behind to its ASPATH. Through this the optimal route is the announcement with the shortest ASPATH. Last is the MED attribute or the Multi-Exit Discriminator. MED is used by an AS (eg. Customer AS) to suggest another AS (eg. Provider AS) what route to select usually in order to the (customer) to cut cost.

PS(The blogger hopes to add pictures so the readers could fully understand what the blogger is writing LOL)

On The Design Philisophy of the DARPA Internet Protocols

The Internet was created primarily for military purposes. As the Internet evolved it became widely used specially in commercial systems. This paper by David D. Clark explains the reasons why its architecture is as it is, why the Internet protocol is a “dumb” protocol, and why the whole protocol is divided into layers (TCP/IP).

The paper discusses the Internet's goal which is to interconnect multiple large networks, mainly the ARPANET and the ARPA packet radio. It will utilize the most obvious and practical technique they saw at that time, the packet-switching technique using store and forward algorithm. Then it tackles the most important objectives such as survivability (of the network on failures) and types of services, which will dictate their decisions on the protocol design. Other objectives that are least significant (distributed management, accountability) are also tackled (almost a page).

At first I wonder if the author is involved on the Internet project because the tone of his/her reasoning is as if he is part of the project. Then I realized i'm correct, after reading the acknowledgements. The author carefully and completely explained the answers to the question from the abstract. IP is a connection-less protocol that is only concerned in routing and packet fragmentation (to fit through small networks). IP is designed as a building block for the layers above it (I just understood how important end to end arguments is). TCP splits from IP because TCP cannot support some services such as the cross-Internet debugger and the digitizes speech. TCP provides only byte-based flow control because they realized its sufficient enough compared to byte and packets, it takes advantage on one-large-packet retransmission for failure control, etc.

Protocols and standards are defined by the decisions of the researchers and engineers which are affected by objectives, the things they see what is possible using current technology and the things they can forsee what must be possible after some years. Some application layer protocols have accountability as one of their objectives so the design and implementation of the engineers includes accounting to track the consumption of network resources by users. Relatively new protocol such as SCTP emerges to replace TCP and UDP. But even SCTP offers more powerful services and security, migration is costly, and old protocols still get the job done, eg. TCP reliability is still justified. (I was in a simulation project for 4 months (before I resigned because of personal issues ^^) which uses the Diameter-base protocol, and out of curiosity I read a lot about stuff like AAA protocols and the SCTP protocol)

This paper is a must read for network researcher wannabes. It describes the reasons why the Internet architecture is built this way and not that way.

End to end arguments

This paper by J.H. Saltzer, D.P. Reed and D.D. Clark shows the basic principle on communication protocol design. It says instead of placing functions such as error control on the network subsystem, it is better to implement them on the endpoints of the network. The rule states that in order to create a desirable function on a subsystem layer, that layer must have a knowledge on the application that will use it. A designer cannot implement a function that services itself. For example this paper explains that in securing transmission of data, the lower layer subsystem doesn't need to encrypt the traffic because the application on both ends must implement all the requirements for secure data transmission, thus removing redundant security. Another example is guaranteeing FIFO message delivery. Sometimes, the application specially a distributed one needed its own control of ordering actions because the subsystem cannot guarantee the correct ordering if the messages are sent along independent virtual circuits.

The logic in end to end argument is very much rational and straight forward and every network researcher must understand what the principle is trying to explain about system design. Its fundamental logic (in theory, not in actuality) will be a great help on obtaining the goals when designing and implementing network protocols. Effectively implementing such protocols have huge impact on scalability and performance. The success of the Internet architecture is one proof when the implementation of TCP/IP adheres to end to end argument. The only difficult part on the principle is how to identify the endpoints of the network. It requires much effort when it comes to layering communication protocols.

Some of the technologies today challenges the end to end argument. One example is the network address translation or NAT. NAT emerges as a temporary solution of IP addresses exhaustion. Network address translation allows a router, to act as an agent between the Internet and a local network. This means that only one IP address is required to represent an entire group of computers. NAT rewrites the TCP/IP (or IP only) parts of a packet, hence violating the end to end connectivity of a network. The solution that sticks to end to end argument is switching to ipv6, but the cost of general worldwide deployment slows down the migration.

Until now there are still debates going on (specially on internet forums) whether or not the end to end argument is still relevant on the evolution of the Internet even new emerging technologies (eg. NAT, multicasting) violate the principle. Of course it's as important as it is decades ago. End to end argument is a valuable guide. Correctly placing functionality on correct communication layers will always produce good system design.