Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications May 29, 2009

(i) the three most important things the paper says

1. One of the most important things mentioned in this paper is the fact that, in a distributed peer-to-peer system, no single node needs to know about more than two other nodes in order for that system to function properly (assuming a ring-type topology, and ignoring the requirements to remove a node).  Although slow, this interconnection scheme is the most scalable (in terms of adding nodes) and will continue to maintain an all-inclusive state within the system.  Another item mentioned on the same topic is that a reasonable lookup time can be achieved in this system by only requiring each node to remember the locations of log N nodes (where N is the number of nodes in the system).
2. Another important observation is the fact that the system will always converge (possibly barring any severe partitions) from any number of joins (whether concurrent or not) using the stabilize machinery given the proper amount of time.  Basically, the authors guarantee that no additions to the system (joins) can ruin its consistency.  All that is required is time for the proper stabilize commands to complete and distribute the predecessor and successor information to each node.
3. A third important observation of the paper is the fact that probability and statistics of typical usage are on the side of the system’s design.  The authors bring up the point that this system will work well based upon a typical failure rate for hosts on the internet.  I would say that if this system was used for distributing data from server to server, this scheme would never encounter problems with performance that would require it to reduce to minimal performance (because of the sheer number of failures that it would have to deal with).

(ii) the most glaring problem with the paper

Although mentioned in the “Future Work” section, the lack of security to this protocol is a bit disconcerting.  Even though security can be added later, I would think that for a protocol whose main deployment is on the Internet security would be a main concern (and most likely integrated directly into the protocol design and not just patched in later).  It may be that this entire protocol could be invalidated just because of the fact that it would be difficult to guard against a host spoofing the system for malicious purposes.

(iii) the future research directions of the work

I feel that it would be very interesting for the authors to investigate the effect of changing the distance between the entries in each for the finger tables per server (instead of log N).  Another study could display the empirical results of these comparisons alongside the theoretical results, just for the sake of accuracy on both ends.

Ten Things Lawyers Should Know About the Internet May 25, 2009

Although this paper has ten points which concern laws and the Internet, they can be boiled down to three:

1. The laws relating to copyright, privacy, wiretapping, and common carriage are not relevant to the Internet today. Furthermore, trying to apply them to the Internet has many deleterious effects with no real gains, since the usage model of the Internet differs so much from the services provided at the time when the laws were written.
2. Furthermore, we actually know very little about the Internet from an empirical perspective. This is due to two factors. First, much of the current legislation (see point 1) makes it impossible (or rather, illegal) to gather the very information that would illuminate the usage patterns on the Internet. This hamstrings researchers, who are able to come up with many wonderful theories about current or future traffic patterns, algorithms, etc., but are unable to test or validate them on the Internet at large. Secondly, even when legal, these same efforts are frustrated by the fact that the Internet is composed of many private companies only motivated by relatively short-term financial concerns and unconcerned with the viability of their practices in the mid- to far future.
3. With both the legal and financial restrictions on what can and cannot be implemented, the Internet as it stands today is in a fair amount of risk. The underlying routing and naming services are insecure because they were designed for an Internet that is very different from the one present today. Not only are they insecure, but they are not designed to scale to the size of the modern Internet. Even though these problems are evident from even the limited amount of data available under current laws and from the companies operating the core routers in a secretive manner, the educated people who have exposed these problems are helpless to enact any change at a global level.

The main problem with this paper (and likely this summary) is that it views the current state of the Internet from a very pessimistic perspective. While it may be true that there are many unresolved problems on the Internet, it is risky for the researchers to look down from an ivory tower and proclaim that the Internet is doomed unless we do X, Y, and Z. What does need to happen is that government regulation needs to be designed in such a way as to not stifle the approaches that the market takes to optimizing the Internet for its current and future needs.

Future research needs to look at ways to incentivize the change that researchers think needs to be implemented. Unless they can provide economic incentives for the companies that control the Internet, then the changes will fall on deaf ears.

Internet Mapping: from Art to Science May 25, 2009

This paper describes Archipelago (Ark), which is a measurement infrastructure being used primarily for mapping the IP topology of the Internet. The main body of the paper describes their efforts to measure the topology of the Internet, but they start by describing the three features they are striving toward in the Ark infrastructure. We will examine how their topology mapping benefits from the architecture of the Ark infrastructure by examining their goals:

1. Easy development and rapid prototyping. The process of generating IP topology data requires multiple steps involving creative uses of (primarily) ICMP and UDP probing. Since the Ark infrastructure provides high-level APIs and services, like the scamper measurement tool, generating these probes is a very straightforward process involving only a few commands in a high-level scripting language (they use Ruby). In addition, Ark facilitates writing new measurement tools, like those comparing ICMP traceroute against UDP link measurement and analyzing probes from spoofer clients, which have been developed by other researchers for use on Ark.
2. Dynamic and coordinated measurements. The Ark infrastructure proves a tuple space which allows storage and communication of data through a map-like interface. This tuple space provides shared state which is vital for creating distributed services, since it allows them to communicate without having to coexist temporally or geographically. It also provides greater flexibility since messages don’t have to be directed to an address which might not be known a priori.
3. Measurement services. Another useful attribute of the tuple space is that it enables the construction of named services without having to know who is providing them. For example, by placing the tuple ["PING", "<some IP address>"] into the tuple space, the user or program requesting the ping is counting on someone providing a ping service to the tuple space. However, the requester does not have to know who is providing the service in order to receive the response. It also allows great parallelism, since multiple service providers have access to the tuple space and one or many of them can respond to a given request, depending on its semantics.

The weakness of this peper is that the Ark service does not seem to have any real provisions for security. Anyone who is connected to the tuple space can serve requests without having to provide credentials certifying that they will produce a valid result. While this may not be a problem at the earlier stages of the network (similarly to the Internet, where initially all users were assumed to be trusted), it might be a problem if it is used on a larger scale or for commercial purposes.

Future research might include a layer of security that is simple to use in a similar manner to the tuple paradigm already in effect. For example, a credential server could provide service registration through a shared key system whereby only the registered service providers had the private key necessary to decrypt requests.

Delayed Internet Routing Convergence April 23, 2009

Three Important Things:

• There is common acceptance that the internet in its current form is robust and efficient in adjusting routes in the face of link failures. Such occurrences are fairly common in such a huge infrastructure, and the authors recognized that it would be valuable to evaluate this accepted belief. By evaluating BGP convergence they came to the conclusion that inter-domain failover has significant delay, and that the path vector approach is incorrectly believed to provide improved convergence properties over distance vector routing. The claim is that the delay stems from ambiguity in the BGP protocol, and varying implementations across different router vendors.
• The paper was focused on experimental trails conducted over a long period of time, lending strength to the obtained results. The authors emphasize several points about designing and executing their experiments in order to produce quality, meaningful, relevant results.  Faults were injected into the actual internet backbone as opposed to a simulation environment. Latency effects were measured at the router level by routing ISP routing tables, this allowed the examination of several events: route repair, route failure, repair and failover, failurea and failover. End-to-end measurements were performed to determine the application level impact, the results proved that even moderate routing table flux caused packet loss, increased packet latency, and out-order-delivery.
• In addition to the hard data, the authors provide theoretical lower and upper bounds. The exploration of these bounds resulted in several insights about delayed convergence. For example, a lack of minimum route advertisement interval timer in some implementations influences the order in which link updates are processed, which impacts the rate of convergence. There are numerous implementation variations across vendors that contribute to the performance bounds.

Glaring Problem:
A major concern that I had with this work is that it only focues on BGP, and that it didn’t really discuss the parallels between inter-domain and intra-domain results. It would have been useful to see how the obtained results pertained to other routing protocols, if at all.

Future Work:
Following this thorough treatment of BGP convergence analysis, it would be useful to follow up on the root causes of delayed convergence and try to design new protocols, or at least new features in future routers that could help alieviate the strain on the internet backbone.  These topics were mentioned in the paper, but not at length. Such research would be crucial to the continued viability of the internet from a QoS perspective.

An Experimental Study of Delayed Internet Routing Convergence April 23, 2009

This paper presents the results of a very comprehensive study of routing convergence behavior on the internet. By monitoring the internet in many different places while injecting routing faults at various points in the network, they were able to measure in great detail the effects of such faults on both the routing tables themselves and their effect on end users.

They present a few important conclusions. The first is that the amount of time it takes for new routes to stabilize after a fault is actually much longer than previously thought. In addition to this insight, they have discovered that this delay will increase linearly in the best case and exponentially in the worst case with the number of additional autonomous systems on the internet. This presents a significant challenge to the designers of internet routers, especially if the growth rate increases more exponentially than linearly.

Their second conclusion is that much of this large failover time is due to differences in how vendors implement the BGP specification. If more loop detection was done by the sender instead of just at the receiver, the number of total updates could be reduced dramatically. However, this adds complexity to routers which are likely already quite expensive and complicated to design.

A third conclusion they arrive at is that different classes of update traffic have different behavior with regards to the amount of time and number of messages necessary to reach routing convergence. The loss of a route causes messages which are monotonically increasing while the addition of a route causes messages which are strictly increasing. While this may not seem like a significant difference, it actually has a profound effect on the convergence time, since it can take a long time for a faulted route to disappear from the system as routers bounce messages back and forth slowly increasing their distance to the faulted route until eventually they all realize that it is no longer present. This is in contrast to an added route, which either creates a shorter path which is propagated, or doesn’t, and doesn’t generate any new routes.

A weakness of this paper is that their bounds on the convergence rate of routes are fairly loose. While it is valuable to know that it is at least linear, the upper bound is quite high and does not necessarily describe the behavior accurately. However, since the growth rate is at least linear, future research needs to focus on ways to either improve BGP or supplant it with something more intelligent, which is less susceptible to implementation dependencies and superfluous messages during routing convergence.

A Protocol for Packet Network Interconnections April 7, 2009

The authors make the observation that hosts often need to communicate across homogeneous networks, and that the best way to facilitate this is through gateways at the network boundaries. This approach handles formatting and fragmentation issues without compromising the integrity of the message. A key point is that gateways can perform fragmentation as needed but should not be responsible for reconstructing segments. This is left to the end host, because there are no guarantees that any one node other than the host will have all the packets go through it, and because the processing done at the gateways should be kept to a minimum. This follows from the end-to-end argument.

This paper introduces the concept of a reliable message queue between two processes. This is a natural and powerful abstraction for designers as it allows a process to provide a message and a destination and not have to worry any further about transportation. Key points are that each host must have a globally unique identifier, and that the notion of a locally unique port must be introduced to handles multiple processes on the same host.

The most important thing about the protocol is that its functionality is built on top of an unreliable, best effort network. By constructing the protocol around a sliding window, the authors are able to achieve reliable, in-order delivery. In addition, they are able to leverage the size of the window to implement flow control. This again falls in line with the end-to-end argument, and represents the “smart” host’s attempt at deducing the state of the network without any explicit information.

I would say that a drawback of this paper is that it does not contain any formal verification or at least simulation results. One or both of these would have been very useful in backing up the major contributions like flow control. The authors provided a solid framework for implementing TCP, but it does not seem that they actually deployed it at this point.

This is an incredibly significant paper in the history of networking research, and the concepts contained in it have been thoroughly analyzed, refined, and followed up on. In this context it is useful to think about what fundamental new directions future research could take. One such direction could be to identify abstractions other than the shared queue that TCP provides that might be useful for process communication. I believe that as the internet evolves and overlay networks become prominent a variety of special purpose abstractions will find widespread use.

A Protocol For Packet Network Intercommunication April 7, 2009

Title: A Protocol For Packet Network Intercommunication

(i) The three most important things the paper says:

1) Problems with individual packet switching networks are compounded when dissimilar networks are interconnected. This was the key point of the paper, as Cerf and Kahn saw that the future of computing would involve connecting dissimilar networks. In addition to pointing out the problem, they also provide a rudimentary system for how the common problems can be handled (e.g. flow control, retransmission, addressing).

2) Interface between networks should be abstracted into a gateway. Instead of proposing a system in which all processes share a protocol, they pushed the idea of abstraction. By using gateways, they allow different systems to continue and use the internal network protocol that was most efficient for them, and rely on the gateway to pass packets to other network seamlessly. This is a practical approach to allow their proposal to be adopted quickly by the community, since it doesn’t require current network systems to be completely rewritten.

3) The idea of TCP which handles the transmission and acceptance of messages on the behalf of process. The paper discusses in great length the problems with communication between internetworks and how the TCP can solve these problems. Their discussion in detail of the TCP was the starting point of our current TCP/IP protocol which obviously was a huge success. Their ideas of sequencing and using windows to detect retransmission and ACKs was revolutionary at the time.

(ii) The most glaring problem with the paper:

This paper gives discusses in length a “hypothetical” approach to solve this problem. However there were no experiments that was performed to prove that their solutions for the common problems (e.g. out of sequence) are solved by using their strategy. Unless concrete proof is provided they can not be sure that the major problems associated with internetwork communications are addressed by their proposal. For instance, just off the top of my head, I can see how their system wouldn’t be able to recover from a faulty gateway performing incorrect translations.

(iii) The future research directions of the work:

The future direction of their work would definitely involve how this system could be extended for a larger user base such as the current internet. For example, their system of addressing is obviously not sufficient to handle the many computers on the internet today. Also other problems that are associated with a larger user base that should be considered are security (e.g. man in middle attacks) and time out issues with packets traveling longer distances.