A Conjecture on Bandwidth Estimation

After discussing in class a couple of peer-selection algorithms for enhanced peer-to-peer data transfer performance, along with a couple of techniques related to video broadcasting and incremental peer optimization, I asked myself how much would the Internet benefit if a fast, accurate estimate of the theoretical maximum throughput, minimum latency, and expected data loss rate could be obtained for any arbitrary connection between two hosts. Some of the benefits I imagined include:

• More efficient overlays, either via IP multicast or peer-to-peer applications, for multicasting applications.
• Better match-making for online games. Users that are near each other could be more likely to be matched together to improve latency and performance.
• Easier estimates for expected bandwidth and latency based on the theoretical values and the current load on both hosts.
• Better TCP utilization. Instead of a TCP connection gradually raising its transfer rate and then halving the rate when packets are dropped, a smarter algorithm might attempt to maintain a steady transfer state around a computed expected bandwidth and latency. In addition, dynamic ACK timeout values could be derived to avoid premature packet re-transfer.
• Better user warnings and errors for applications with strict latency/bandwidth requirements like voice/video conferencing and video streaming. Before the application even begins to transfer data, warnings could be displayed to the user that the potential or expected bandwidth or latency between connection is lower than is required for the service to operate smoothly.

I do not know what infrastructure changes would be required to enable such a feature in the Internet or how much trust would be placed between nodes to provide honest answers to bandwidth and latency queries, but it seems that such a feature would have a positive impact on current Internet applications.

Internet Video Broadcast and Peer-to-Peer selection

In our Internet architecture class this week we presented and discussed several papers related to peer-to-peer networking. I in particular focused on the article "Opportunities and Challenges of Peer-to-Peer
Internet Video Broadcast", which discussed the current state of the art in peer-to-peer video broadcasting. The two example techniques for video broadcast that were described in this paper both attempted to incrementally optimize the broadcast overlay. In other words, peers periodically attempted to change the peers they shared data with to improve the flow of data in the system. Also, both methods appeared to go make such peer-switching decisions by having peers track the history of the performance of other peers they interact with.

At the same time, we also discussed another paper on a peer selection heuristic for improving the performance of Bittorrent downloads. This method relies on the use of CDNs. When a node joins the system, it contacts a CDN-distributed site and tracks the chain of redirects it follows to retrieved the cached content. Then, when choosing peers initially, it compares these redirects against those of other nodes to select those that appear to be in the same or the closest CDN. The use of this technique resulted in significant performance gains.

Having studied both papers, it seems very easy to ask why anyone has not tried tried applying a similar technique to improving the performance of peer-to-peer video broadcasts. That's when I started to see one of the values of collaborating together and sharing information in a class or lab setting. By sharing what we know, we can synthesize new ideas from existing ones much more easily. Most ideas seem simple in hindsight, but the process of discovering those ideas is often much more complicated, and sharing research knowledge in a lab setting appears to be an effective way to spark innovation.

Why distributed data stores matter

After our recent discussion on Chord, a distributed hash table (DHT) implementation, I began to try to connect the ideas Chord presented with all of the other popular persistent storage technologies that have been advertising themselves recently, such as the NoSQL solutions, as I wanted to know how these ideas are related. Chord's decentralized approach to data lookup allows it to be robustly fault-tolerant as nodes enter and leave the system. While most companies that use such data stores don't have to worry about autonomous nodes entering and leaving at will, they do need an easy way to add additional nodes to their systems as their business scales upward. Also, their data storage systems, consisting of large clusters of commodity servers, must handle node failures gracefully, which means both redundant data storage and system stabilization algorithms are required. Lastly, many companies need to perform distributed computations on large data sets, which is made possible by the distributed nature of these data stores.

A few interesting commercial and open source implementations of distributed databases are the Apache Cassandra project, google's proprietary BigTable, the Hadoop-compatible Hypertable. While Cassandra, based on Dynamo, uses a DHT internally, BigTable and Hypertable both use a different data storage format. Wikipedia describes BigTable as a "sparse, distributed multi-dimensional sorted map".

While Chord itself may not have caught on in large commercial organizations like Yahoo, Google, or Facebook, it would be interesting to learn how much DHT's like Chord have influenced the design of the next generation of persistent data stores, and what problems they focus on trying to solve compared to Chord.

Analyzing Internet Packet Flow

The paper End-to-End Internet Packet Dynamics provides a classic example of Internet measurement studies. Based on my reading and discussing of the paper in class, I thought of some interesting questions or directions that might be useful to answer or explore.

1. What if it were possible to actually determine the exact link that formed the bottleneck in a connection? I don't think this is possible with the current architecture, but if it were, routers might be able to update costs temporarily for a particular TCP connection. This would require a small amount of transient state, but could lead to more optimized data transfer and less packet queueing if an alternative route could be discovered that had a higher bottleneck rate.
2. The paper concludes that certain pathological scenarios like out-of-order-delivered packets and data and ACK packet loss are highly connection-specific or specific to the current level of traffic. One interesting avenue of exploration might be to analyze the connections that generated the disproportionate amount of pathological cases to determine their cause. If they are only congestion-specific, for example, then some transient router state to detect such cases might prove valuable in reducing the number of retransmissions that occur.
3. The authors hypothesize that 16-bit TCP checksums are insufficient for the large amount of data that is currently transferred over the Internet, but that the chance of a corrupted packet being accepted as valid is too high. This claim is hard to believe 15 years later, as we still use the same size checksums and our data transfer rates and Internet usage have only increased. Even still, it might be valuable to mathematically analyze certain pathological scenarios like the probability of a file transfer of a certain size containing corrupted data, and then empirically evaluating the probability with different connections.

As our teacher told us that this paper is seminal in its field, it is likely that all of these questions have been explored already, but I find them interesting to think about nonetheless and perhaps useful in understanding how the Internet currently works.

The Permissiveness of Active Architectures

After studying two research papers in my Internet research class on active architectures, I wonder why these researchers did not settle on proposing a plugin-based architecture instead. Relatively few systems exist that allow arbitrary code to be executed. Google App Engine, Google NaCl, the JVM, and the CLR are all good examples of such system and provide facilities for controlled and secure execution of arbitrary code. However, all of these examples are platforms that were built explicitly as Turing-complete machines to run any application on, trusted or untrusted. I do not, however, believe that a network architecture should have the same kind of flexibility as a programming language runtime. A network need not execute untrusted code, and its scope is much more limited than that of a general language runtime. In proposing such an architecture, these researchers almost seem to be considering the interests of a few minority parties over the those of the public at large.

Instead of proposing an architecture where any user can execute arbitrary code, why not propose one with a plugin system? Such a design would place control and responsibility of the code that gets executed on the network back in the hands of the network owners and operators themselves, without sacrificing generality. Such a system could allow autonomous systems to advertise which plugins they support, and BGP-like protocols could take such information into account when routing a packet that requires a specific plugin.

While such a design would require manual intervention by ISPs to install a new network feature, the number of security and performance issues would drop dramatically and those that remained would be much simplified. Also, if a plugin provided significant benefits to customers or ISPs, the utility of the plugin itself should be enough incentive for organization to install it on their existing hardware. Lastly, not all of the Internet needs to have a plugin installed for it to be used, only enough that a path can be found between a source and destination where each AS hop supports the plugin.

A plugin architecture can make the Internet just as dynamic as an active architecture, but through much safer and less radical means.

Measuring the Utility of the Internet

The paper Modeling the Adoption of Network Architectures attempts to define a simple user utility-based model for measuring the migration from an existing network architecture to a new one. The model is based primary around standalone utility, the benefits a single user or organization receives from using the Internet, and network effects, or the benefits a user or organization receives because other users and organizations use the same network architecture. However, the authors lament that they have no way of determining real world values for any of their model parameters. This prompted to think about the value that the current Internet provides to different groups of people and ask if it is even possible to provide an accurate numeric value for something as complex as user utility.

At its core, the Internet provides a protocol, IP, for hosts to send messages to each other, and two protocols, TCP and UDP, for sending arbitrary-sized chunks of data between hosts. To hardware, manufacturers, this provides value in that if their equipment can communicate with a IP-aware router, then it can communicate to the Internet. To software developers, on the other hand, this means that they can rely on underlying TCP/UDP operating system calls to write network-aware applications. For specialized applications like web servers, even higher-level abstractions exist for HTTP-based communication, and yet higher abstractions that attempt to hide the HTTP request/response cycle. At their core, they are all built on TCP/IP.

Most organizations, however, will use the Internet through a variety of applications running on a variety of hardware devices. Their internal networks will also have to respond to a multitude of disparate needs. Our university campus, for instance, most likely has many kinds of "middlebox" network technologies like web filters and caches, and network activity monitors to detect malware. And, of course, the users in an organization can differ vastly in their needs from one another. Some users may user Internet primarily for basic communication: email, chat, and web-conferencing. Home users, on the other hand, may use any of a number of applications ranging from streaming video to casual Flash games. As a final interesting note, the standalone utility of the Internet for any user is constantly changing as new applications are developed and the infrastructure evolves to provide more bandwidth.

While the Internet itself provides only one network effect, the ability for any connected, addressable host to communicate with any other connected, addressable host, there are a host of applications that also take advantage of network effects. Social media, for instance, notoriously benefit from increased numbers of users, as well as any other communication tool like email. E-commerce businesses like Amazon.com also see increased revenue with more Internet adoption. As a last example, there has recently been increased effort poured into collaboration tools like Google Office, Google Wave, and Etherpad, all of which provide a limited amount of network effect-based benefits to some users in that they really only benefit from networking with a few others. at a time.

After considering not only the large number of different ways different users can benefit from a network architecture but also the different ways in which individual users may use such a broad and general tool, it begins to seem very difficult to deduce a general numeric value to assign to "user utility" for all network architectures. Perhaps the biggest value from this research, though, simply comes from the fact that it may cause others to consider what will be required to making breaking changes to the Internet.

I Told Him We Already Got One!

Reading about one of the many proposals for a brand new Internet recently reminded me of the famous Monty Python Scene where King Arthur offers to allow the Master of the French Guards to join him in his quest for the holy grail, and the guards respond by saying they've already got one. It felt to me like those proposing a new Internet architecture were doing much the same by inviting others to join them in a quest for a holy grail, except that the invitees really do already have a grail that works nicely. This issue is not common to the Internet. Those on the fringes of programming language research, for example, have claimed that the current crop of programming languages is insufficient for the parallel programming needs of the future, and yet the industry still churns out code well enough using existing tools. And, of course, one need not look long beyond the field of computing to see scenarios where change is resisted because the status quo is good enough.

In the paper I read, "A Data-Oriented (and Beyond) Network Architecture", the author proposes layering a name-based anycast protcol atop IP in order to more properly fulfill three current primary needs that the original Internet did not foresee: persistence, availability, and authenticity. It is interesting to learn how the architecture proposed in this paper meets these needs relative to how the current Internet handles them.

First is name-based persistence. The authors believe that as long as the data or service underlying a particular name is available, a user should be able to access it using that name. Currently, this is handled through the DNS system. If the resource underlying a URL moves, the distributed DNS system must be updated as to its new location. Intermediate measures like redirects are needed until all DNS caches have been updated. In contrast, using the anycast protocol described in the paper, a moved resource will most likely still remain in the same AS in which it originated, and since routing at the naming level occurs between AS's, no updating of the route handlers will need to occur most of the time. However, updates will still need to occur if inter-AS movement occurs, and the authors also appear to ignore the issues of reliability and failover, which suggests that a new TCP-like service would need to be built on the named routing layer to maintain functionality similar to the existing Internet.

Secondly, the proposed named routing system encourages the replication of data to multiple nodes for both high availability and low latency access. The routing system is designed to handle the ambiguity of multiple locations for a named piece of data by allowing route handlers to choose the current "best" route to the named entity. Currently, the Internet provides this type of service through the use of content distribution networks like Akamai. From my limited understanding on the matter, the routing layer already allows for multiple locations for a single IP address, enabling these systems to route a client to the nearest copy of data made available by the CDN instead of the location of the original data or service. While I have been told that routing table sizes are growing at an alarming rate, I do not know at what point this issue will have a visible impact on the level of service provided by the current Internet infrastructure.

Lastly, the named routing system integrates an authentication scheme into the system through the use of asymmetric encryption keys, allowing anyone to verify that the server of a service or piece of data is authorized to serve that content. This same feature is currently provided through the use of SSL certificates verified by a third party VeriSign. Since I am not an expert in security, I do not know the difficulty in performing authentication attacks against the current system relative to performing the same attacks on the system proposed in the paper, but the proposed system is likely inherently more secure and easier to implement than the system the current Internet uses.

Again, the new Internet system described in the paper was conceived to more correctly handle needs that the current Internet is meeting but for which it was never designed to handle. At what point will existing solutions be sufficiently worse than such a system that upgrading begins to be seen as cost-effective? For now, the Internet, decades old as it is, already seems to handle all of these needs effectively enough.

Software Design Principles and the Building of the Internet

The article "The Design Philosophy of the DARPA Internet Protocols" impressed me as it described a very organic process for building a successful large software system. It struck me as a very healthy way to build a software product and one which many of the modern software development methods share much in common with. It also shows that good engineering principles have existed for many years, even though we still flounder in our attempts to codify an apply them consistently.

The first principle the article exemplfies is that of properly defining and prioritizing requirements. The builders of the Internet knew exactly what their client, the government, needed, and knew exactly the order of importance of the requested features. Prioritization of features is especially important when the cost of implementation of features is calculated during the initial design and implementation phases. For instance, if a feature is of relatively low importance to a customer but would require disproportionately significant engineering effort to implement, it can be safely discarded even if it is higher in priority than other features that are much easier to integrate into the system.

In relation to the first principle, I was also impressed that the designers of the Internet did not attempt to generate a cohesive design that would fulfill the majority of their customer requirements at once. Instead, they focused on the most important features first and then iteratively modified their design as they reconsidered the extending the existing system to fulfill new requirements. As an example, TCP was originally written as the common protocol by which the primary government requirements of robust, reliable communication between disparate networks would be met. However, when the system was analyzed in light of the need for multiple types of service, the Internet authors subsequently split TCP into TSoftware Design Principles and the Building of the InternetCP and IP and added UDP as an alternative transport layer protocol. This organic growth process is much easier for a development team to cope with, and also allows for the team to show progress and obtain feedback faster by delivering working software to their clients sooner.

Finally, the architecture of the Internet is a great example of effective distributed system design, and shows one way one of the most fundamental problems of software design, the problem of composing reusable software components, was handled. Evidence of this problem's inherent complexity abounds, from the existence of module frameworks like OSGi to dependency injection systems like Spring, to the fundamental methods of composition found in differing software paradigms like object-oriented and functional programming. The design of the Internet has been described as effectively applying the "end-to-end" principle in meeting its objectives in a layered architecture. Value lies in studying both this generic principle and its specific manifestation in the TCP/IP stack in order to learn more about how to compose software component in building a larger system.