Nalanda

Citation: Gao, L. 2001. On inferring autonomous system relationships in the internet. IEEE/ACM Trans. Netw. 9, 6 (Dec. 2001), 733-745. DOI= http://dx.doi.org/10.1109/90.974527

The relationships between autonomous systems on the Internet can be near impossible to deduce accurately, as they are, in essence, a series of bilateral commercial agreements. In this paper, Gao presents a technique to infer autonomous system relationships by looking for patterns in the ASN paths in BGP routing tables.

To do this, Gao starts with some general assumptions of rational behaviour for autonomous systems. From these assumptions, she derives the Selective Export Rule, which defines these behaviours as mechanisms by which autonomous systems selectively export routes to their peers, customers and siblings. She then derives patterns that we might expect to see in BGP routing tables, based on the Selective Export Rule: Valley-Free, Downhill Path, Uphill Path, Maximal Downhill Path and Maximal Uphill Path.

Gao combines these with the idea that if we consider the graph of all autonomous systems, those with higher degree are more likely to be larger (and hence more likely to peer) than those with a smaller degree. The result is a set of algorithms, which when applied to publicly available BGP routing tables, and compared to internal AT&T routing tables, provide surprisingly high rates of accuracy in their ability to predict different kinds of relationships. While the accuracy rates vary greatly - from as high as 100% for customer relationships to to 25% for sibling relationships - there is still immense value to be had from these figures alone.

Additionally, as a side-effect of this research, heuristics were developed whereby misconfigured routers could be identified, which would no doubt be of great benefit to network administrators tasked with managing large BGP deployments.

I like this paper, a lot, both for its content, and its presentation. Gao is clear about the assumptions she makes, and the manner in which she builds on them. She is also clear about the limitations she sees to the data that was available for analysis. I found the actual meat of the paper, the heuristic mechanism for identifying different kinds of relationships, incredibly useful, and exciting.

Citation: Lecture notes from Hari Balakrishnan and Nick Feamster.

In these notes, the authors first present an idealised view of internetworking, and then go on to demonstrate how commercial realities actually shape network topologies on the Internet, through the application of network policies expressed and enforced using the mechanisms made available by the Border Gateway Protocol.

The authors discuss the economics of transit v. peering arrangements, demonstrating how economic incentives drive network operators to prioritise the import of routes: first from customers, then from peers, and finally from transit providers. This discussion is compelling, but I would have liked to see more about how this is actually playing out. For instance, I have read that bandwidth scarcity is principally a problem at the edges of the Internet; the backbones, on the other hand, have excess capacity, and continue to upgrade in anticipation of demand. This would seem to imply variances in the patterns of transit/peering arrangements at least across the core and edges of the network, and probably in more complex ways across Tier 1, Tier 2 and Tier 3 networks operating in the same geography.

BGP is described in some detail, with a discussion of techniques for managing eBGP and iBGP deployments. It continues to surprise and fascinate me how much of the TCP/IP suite is based on an assumption of good behaviour across the different administrations comprising an internet, especially in a protocol such as BGP that is clearly intended for the political end of allowing different administrations to co-exist, rather than any technical purpose.

For instance, a topic that is not discussed in these notes is that of transitive trust; I wonder this came to be built into BGP? I can understand why this was so in ARPANET and NSFNET, but it does seem strange that this strategy was adopted for a protocol intended to “allow cooperation under competitive circumstances”, and that this persisted even after NSFNET was privatised, especially since BGP-4 was standardised in 1995, just after this transition.

Citation: Clark, D. 1988. The design philosophy of the DARPA internet protocols. In Symposium Proceedings on Communications Architectures and Protocols (Stanford, California, United States, August 16 - 18, 1988). V. Cerf, Ed. SIGCOMM ‘88. ACM, New York, NY, 106-114. DOI= http://doi.acm.org/10.1145/52324.52336

The intent of this paper appears to be to communicate the design philosophy of the Internet protocols to at least three distinct audiences: implementors of the Internet protocols, architects creating new protocols and/or extending the Internet protocols, and the ISO committee standardising the OSI protocol stack. Clark starts with an outline of the goals of the Internet architecture, and then goes to analyse how a particular ordering of importance of these goals gave rise to a particular design for the Internet architecture.

The fundamental goal of the Internet architecture was to provide the means to interconnect disparate networks to provide services spanning these utilities. An additional priority was the issue of managing the interconnection of networks under separate administrations. Store and forward packet switching was chosen as the solution to this goal, since it was well understood, and already in use in the ARPANET networks initially interconnected.

Several second level goal are listed, with survivability, support for multiple types of service, and support for a variety of networks being the most important. The least important goal listed is accountability, which, as Clark notes, would likely be the most important goal for a commercial network.

Clark introduces the mechanism of “fate-sharing” as the means for survivability, whereby hosts on a network are responsible for maintaining state information for ongoing conversations. He also relates how TCP was split into TCP and IP in order to provide IP as a more fundamental building block from which applications could build general purpose services. As he notes later, the IP datagram also functions as the “minimum network service assumption”, which has made it easier for wide variety of networks to interconnect using the Internet protocols. These decisions seem to reflect an end-to-end approach to design, showing how function can be decomposed and placed to create a more flexible architecture.

In specific advice to protocol implementors, Clark relates how much more difficult it can be provide guidelines for building adequate performance, against the relatively easier task of correct protocol implementation.

Finally, Clark discusses the choice of flow control based on byte number, rather than packet number, in TCP. He argues that this choice provides efficiency both for connecting to networks with small packet sizes, and for unifying messages for retransmission when necessary.

Clark suggests early in the paper that packet switching was chosen in large part as it was the technique employed on the original networks being interconnected. What if a circuit switched mechanism was chosen instead? What would the Internet architecture look like under that circumstance? Is packet switching an inevitable choice? For instance, Donald Davies came to the idea of a packet switched, rather than circuit switched, network in the early 1960s to enable the bursty communications that commercial time sharing services require, while Paul Baran used the same principles to design a network for survivability. On the other hand, one could imagine that modern commercial networks, with their relatively stable and reliable topologies, might prefer the use of virtual circuits.

As with the last reading, this paper is invaluable for the insights it offers into the thinking of the architects of the Internet, providing a historical perspective with which we can understand protocol design decisions.

Citation: Saltzer, J. H., Reed, D. P., and Clark, D. D. 1984. End-to-end arguments in system design. ACM Trans. Comput. Syst. 2, 4 (Nov. 1984), 277-288. DOI= http://doi.acm.org/10.1145/357401.357402

The end-to-end arguments provide a principle of system design to help designers choose the appropriate layer, or layers, of a system at which to implement particular functions. In general, it argues for function to be pushed up to the application layer of a system, so that assumptions made in lower layers do not unnecessarily hobble applications, or impact overall system performance.

The authors provide a wide range of examples to help illustrate their arguments, ranging from seemingly simple file transfer, to complex two-phase commit protocols. Through these examples, they give us a more nuanced view of the general principle, showing varying circumstances in which application layer protocols implement most of the required function, and more instructive cases where application and lower layer protocols complement one another. As the authors say clearly, “[a] great deal of information about system implementation is needed to make this choice intelligently.”

One of the examples in particular stood out to me: in describing the “wait” message of the MIT Compatible Time-Sharing System, it is noted how it was of value when when crashes and communication failures were common in the early days of the system. I found this a useful reminder of the ways in which trade-offs are made between design principles and engineering practicalities.

I wonder how the end-to-end arguments could be used in the context of today’s Internet. The paper seems to argue for placement of function based on the requirements of applications at the edges of a network. Today these same principles are used to make the claim that the Internet protocols form a general purpose suite, over which new and arbitrary application layer protocols may be developed.

It is not clear to me that the holistic approach detailed in this paper - evaluate application requirements and split function across different protocol layers - would work as well in the design of general purpose protocols, which by their very definition are unable to anticipate the demands that might be placed upon them by applications. As the TCP/IP protocol suite has become locked in through widespread adoption, it may be interesting to consider what the limits of these protocols are for modern applications, how these limits came to be designed in, and the ways in which applications have worked around them.

Furthermore, end-to-end arguments seem to assume a decentralized network with a degree of trust in correctness of implementation of function amongst the hosts on the network. How far have such assumptions contributed to the threats that the modern Internet faces?

That said, the principles that this paper elucidates are important considerations in the design of any kind of system, from a self-contained library, to a distributed architecture. In addition, the paper provides invaluable insights into the thinking of those who helped design the Internet protocol suite.