Nalanda

Citation: Clark, D. D., Shenker, S., and Zhang, L. 1992. Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism. In Conference Proceedings on Communications Architectures & Protocols (Baltimore, Maryland, United States, August 17 - 20, 1992). D. Oran, Ed. SIGCOMM ‘92. ACM, New York, NY, 14-26. DOI= http://doi.acm.org/10.1145/144179.144199

It was odd reading this paper alongside Shenker’s. Although it is from three years earlier, it seems much more modern, almost prescient in its analysis. Clark et al., propose a unified architecture that provides different kinds of service - predicted and guaranteed - to real-time applications, in addition to supporting traditional datagram applications. In particular, a class of real-time applications called play-back applications is considered, in which data is buffered at the receiver up to a playback point (which can be thought of as a delivery deadline), and then played on the client, to reduce jitter. Assuming that the majority of future real-time applications will be of this nature, the authors use the requirements of play-back applications to drive their architecture: sensitivity to delivery delay, information about estimated delay to set playback points, indifference to delivery so long as it is before the playback point, and limited tolerance to loss.

Analysing real-time applications along two axes - tolerance to brief interruptions and rigidity of delay requirements - the authors show that the dominant classes of such applications would be intolerant/rigid and tolerant/adaptive. Intolerant/rigid applications need guaranteed service with a priori limits on delay bounds, while tolerant/adaptive applications only need predicted service, as they will dynamically adjust their playback points to suit network conditions.The discussion of the packet scheduling algorithm for this architecture is motivated by these considerations, as it points to a need to separately consider the isolation of flows (to minimise effects of one flow on another), and sharing of bandwidth (to allow operation in a unified network).

A counter-intuitive result is that FIFO queueing works better than WFQ to satisfy the sharing requirement. Where WFQ penalizes sources with bursts of packets, FIFO passes them through as a unit, providing better control of delay bounds for real-time applications, but penalizing other flows as a result. Conversely, WFQ provides better isolation than FIFO, as it minimises the effects of bursty sources on other flows. The authors propose a new scheme, FIFO+, which allows sharing of jitter across multiple hops. A new header field maintaining the difference between the delay for a packet, and the average delay for its aggregate class, is maintained by switches, allowing insertion of a packet into the queue to minimize delay.

The unified algorithm that is presented is based on timestamp-based WFQ at the highest level, to serve flows that required guaranteed service, along with a pseudo-flow encapsulating predicted service flows and datagram flows, which is managed under a FIFO+ regime. This pseudo-flow maintains multiple classes of service, shifting jitter from higher classes of predicted service to lower, with datagram flows being at the lowest level, since they are most resistant to jitter. Admission control is used within each class to maintain delay bounds. This strikes a good balance, as guaranteed flows and the different classes of predicted service and datagram flows are isolated from one another, with jitter shared by progressively shifting it down to the lowest class.

The network fixes the clock rate for each guaranteed service flow, with no further checks on behaviour. Predicted service flows must declare the parameters for their service characterization (token bucket rate and size), and request a maximum delay and tolerable loss rate, to allow the network to assign the flow to an appropriate aggregate class, and also to make admission control decisions based on whether or not a source with these declared parameters can be carried. To maintain good shared behaviour, the network enforces conformance to the service characterization for predicted service flows.

I really enjoyed the discussion in this paper, especially the separation of concerns for sharing and isolation. Most of all, I liked the FIFO+ scheme, as it recalls XCP, but at the same time has no requirements of trust on endpoints; the assumption that switches trust one another seems far more reasonable.

Citation: S. Shenker, Fundamental design issues for the future Internet, IEEE J. Selected Areas Comm., 13 (1995)

I found this paper really useful for two reasons. First, Shenker provides a view of what the future Internet might look like from 1995, anticipating widespread use of real-time applications. Second, and more importantly perhaps, he gives us a set of abstractions by which to judge network architectures based on different the demands imposed by elastic and real-time applications.

The applications in common use on the Internet at the time were “elastic”, in the sense that they were tolerant of delays in transmission, with design decisions that were motivated by the packet-switched nature of the Internet. It is, however, much harder to meet the demands of real-time applications, such as voice and video streams, using a packet-switched network, as they are much less tolerant to delay and loss.

Shenker demonstrates that a unified network infrastructure would provide the highest utility. To allow different kinds of applications to coexist, he considers overprovisioning, and modifications of the basic Internet architecture to provide a variety of service models beyond just best-effort service, which may also depend on admission control. The general intuition at work here is that aligning services with application requirements results in better overall network utilization.

Two models for assigning service to applications are presented: an implicit model where the network attempts to guess an application’s requirements, and an explicit model, where an application can declare its requirements to the network. The implicit model can be introduced with no changes to current service models, but may not be able to service applications that it does not know about, or variations in an application. The explicit model, on the other hand, requires a new service model (and therefore changes to the Internet architecture), stable service offerings, and also raises interesting questions of incentives: how can applications be incentivized to seek the levels of service they actually require, rather than always seeking the highest available level? Shenker suggests that they only way to address this concern is through variable pricing for different classes of service, though raising the concern that such variable pricing might change the nature of the gift economy prevalent on the Internet.

The most interesting section of this paper, for me, was the discussion of utility curves for different classes of applications: elastic, hard real-time, delay-adaptive and rate-adaptive. The shifts between concave and convex shapes, and the inflection points at which these occur, provide a compelling framework for thinking about the design of different classes of service in a unified network.

Citation: Katabi, D., Handley, M., and Rohrs, C. 2002. Congestion control for high bandwidth-delay product networks. SIGCOMM Comput. Commun. Rev. 32, 4 (Oct. 2002), 89-102. DOI= http://doi.acm.org/10.1145/964725.633035

Following a clean slate approach to network design, the authors propose the new eXplicit Transport Protocol, XCP. Where prior approaches attempt to build to TCP’s behaviour (e.g., signal congestion by dropping packets), XCP starts from scratch, addressing TCP’s shortcomings head-on. The principal issues with TCP that XCP attempts to remedy are its unstable and oscillatory behaviour as the delay-bandwidth product of a network increases, the inefficiency of its additive increase policy (a large number of RTTs may be required to achieve full utilization), and unfairness as flows with different RTTs contend at the same bottleneck.

XCP uses explicit notification of congestion, with an indication of the actual amount of congestion in the network, rather than just a single bit. The authors come to this approach from the conclusion that dropping a packet is a bad way to signal congestion: since the network’s objective is to get packets through, this should only be used as a last resort. Instead, a congestion header is maintained on every XCP packet, which contains the sender’s cwnd and estimated RTT, as well as a feedback field which is modified by routers as the packet flows through the network. XCP routers modify the feedback field based on their available bandwidth. XCP receivers copy these headers into their ACKs, allowing XCP senders to change their cwnd rapidly based on feedback, rather than just one packet per RTT. This approach allows efficient implementation in the routers, as no per-flow state needs to be maintained, just adjustments to feedback based on aggregate flows.

The other major innovation in XCP is the separation of utilization control from fairness control. The algorithms for both these estimate values over the average RTT, leading to responsive feedback. Utilization control determines by how much overall bandwidth should change, by computing feedback proportional to spare bandwidth, hence following a Multiplicative-Increase-Multiplicative-Decrease policy. The fairness control algorithm handles allocation of the spare bandwidth, which is done, like TCP, through an Additive-Increase-Multiplicative-Decrease policy: when feedback is positive, an equal increase is allocated to all flows, and when it is negative, the decrease is proportional to each flow’s throughput. In addition, XCP attempts to prevent stalling of convergence when efficiency is close to optimal through “bandwidth shuffling”, which forces AIMD on at least 10% of traffic; while this introduces some disturbance, it is a trade-off that helps more rapid convergence.

Most interestingly, the parameters required for XCP’s operation are tuned independent of network topology, and number of flows. With fixed parameters, it is shown that XCP has practically zero packet loss, fair allocation, good utilization, and reasonable queue size in comparison to several other protocols.

While XCP would certainly be of benefit on a controlled network, it is an open question as to how well it might function in the environment of the Internet where hosts (and even routers) cannot be trusted to conform to the protocol. From their discussion of implementing policing agents (which may themselves become bottlenecks, as they have to maintain per-flow state) at the edges of a network, it seems apparent that the authors are aware of this issue. I would have liked to see more discussion of this point, as it seems central to XCP’s viability. More generally, I wonder whether it is even possible to design a protocol that functions to XCP’s level of efficiency in the absence of trust.

Citation: Floyd, S. and Jacobson, V. 1993. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw. 1, 4 (Aug. 1993), 397-413. DOI= http://dx.doi.org/10.1109/90.251892

Floyd and Jacobson’s work on RED gateways is motivated by the observation that TCP is designed to detect congestion only after a packet is dropped at a gateway, which would typically result in large, mostly full, queues at gateways, contributing to increased average delay in the network. While RED’s congestion notification mechanisms (which are referred to as “marking”) are similar to those available in TCP (drop a packet) and explicit notification as proposed by Chiu and Jain (1989), RED detects congestion differently. Instead of reporting congestion when it occurs (i.e., queues approaching full), RED computes average queue size, and probabilistically “marks” packets when the the average queue size exceeds a a certain threshold value.

This approach should allow a RED gateway to maintain smaller queues on average, while also responding well to bursty connections, especially TCP’s Slow Start phase. Additionally, the probabilistic marking of packets ensures avoidance of global synchronization, where multiple TCP connections respond to congestion notification by concurrently reverting to Slow Start.

Two distinct algorithms are used to satisfy RED’s design goals, one for congestion detection, and another for deciding which connections to notify when congestion is detected. These function differently across three different ranges of operation, depending on the average queue size, computed as an exponential weighted moving average, with a low-pass filter. When average queue size is under a minimum threshold, all packets are passed through. When it is over a maximum threshold, all packets are marked. In between these two thresholds, packets are marked with a probability proportional to the share of bandwidth that a connection is consuming. I found the discussion of approaches to randomization in order to avoid clustering of marked packets (and hence global synchronization problems) particularly interesting.

RED makes two major assumptions: that FIFO scheduling will continue to be useful and prevalent, and that the host transport protocols are responsive to congestion notifications. From discussions in class, it would seem that the former assumption is no longer an issue with the current generation of routers. The latter assumption, that of cooperative transport protocols, is explicitly stated in the paper initially, but also refuted later, when the authors state that one of their design goals is to maintain proper function even in the presence of uncooperative transport protocols. In my reading, it seems to me an open question as to how well RED would function in the presence of uncooperative transport protocols.

An interesting characteristic of RED that I would have liked to see more discussion of is the fact that it does not attempt to be fair. Rather, it allows connections to take more than their fair share of bandwidth for brief periods, as long as average queue sizes are under the maximum threshold. While this is dependent on tuning the thresholds and weight, it seems a sensible approach - get as much through as possible - which is, after all, the function of the network.

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.