Improving MapReduce Performance in Heterogeneous Environments

This paper introduces a new scheduling algorithm to optimize MapReduce (specifically the Hadoop implementation) performance in heterogeneous conditions: Longest Approximate Time to End (LATE). The motivation here lies in the fact that the MapReduce task scheduler assumes linear progress and node homogeneity to make re-execution decisions in case of a straggler, a node that is performing poorly for various reasons (e.g., faulty hardware). Since this "speculative execution" is crucial to MapReduce's high performance, the authors set out to optimize the scheduler to finish the fastest tasks first without wasting unnecessary resources.

In short, task scheduling does not simply identify slow tasks but those that will hurt the average response time the most, as with any scheduling algorithm. Scheduling priority should be given to failed tasks, followed by non-running tasks and finally tasks for speculative execution. Moreover, speculative tasks should be scheduled on fast nodes. The ideas presented in this paper are all very intuitive and not too complicated - honestly, I'm surprised that MapReduce implementations didn't already use at least this level of sophistication in task scheduling. Overall, I definitely enjoyed this paper as I have plenty of Hadoop experience; this is certainly a keeper for the syllabus.

A Policy-aware Switching Layer for Data Centers

This paper addresses the need for more control over middlebox traversal in today's data centers. Data centers use a variety of middleboxes to improve the performance and security of services but existing networks provide suboptimal means to coerce traffic through a specific path of middleboxes. For this reason, the authors propose a policy-aware layer (PLayer) for data centers that is flexible, efficient and resilient to stern network conditions. Essentially, the solution is to wrap another layer of headers on each ethernet frame in order to track its progress through the policy (intended series of middleboxes).

In many ways, the ideas here are similar to the one that advocated a smoother integration of middleboxes into the Internet backbone by adding new identifiers. However, the solution proposed here appears to integrate rather seamlessly and with less overhead. The applications are also very obviously relevant (unlike the other middlebox paper, which didn't have a very convincing motivation in my opinion) and the concepts are generally explained clearly. I didn't completely understand the use of MAC addresses for pswitch-routing.

Scalable Application Layer Multicast

This paper presents an overlay-style protocol for scalable, application-layer multicast delivery. The primary focus here is on developing a hierarchical node organizational structure that minimizes control overhead. Even though the paper focuses on low-bandwidth applications, the authors claim that applications with different requirements can be handled by varying the overlay paths and metrics. The protocol employs a tree structure to avoid loops and data duplication, with a careful explanation of joining mechanisms for nodes. However, this tree model has several clusters at each layer and that may present problems - nodes at the top are overloaded compared to those at the bottom, which effectively lose bandwidth in one direction.

The cluster-based model may get complicated in a real network, especially merging and growing the tree. To an extent, this paper presents general approaches towards application-layer multicast rather than a specific protocol that can be readily implemented. It's more interesting than the previous one but once again, it may not really belong in the syllabus. The previous paper provides a better basic exposure to the requirements for multicast delivery.

A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing

This paper describes SRM, an algorithm designed to support scalable, reliable multicast delivery. The authors importantly explain that several integral TCP parameters lose meaning in a multicast environment; for example, the round-trip time used for retransmission or the delay-bandwidth product is difficult to pinpoint when receivers have several orders of difference in magnitude. For this reason, receiver-based control is preferred to the traditional sender-based, fate-sharing approach. The SRM framework builds upon application-level framing (ALF) as well as the Light-Weight Session (LWS) protocol that was designed for large-scale conferencing applications. SRM includes some interesting features, such as localized retransmissions to avoid multicast spamming. However, I found some of the detailed discussion of simulation somewhat tedious. This was an interesting paper but not necessary essential to the syllabus.

A Delay-Tolerant Network Architecture for Challenged Internets

This paper presents the DTN architecture, designed for networks with exceptionally poor or unpredictable performance characteristics. The existing TCP/IP service model makes basic assumptions about the existence of end-to-end paths between any two nodes, as well as upper bounds on round-trip times and packet drop probabilities. The growing importance of networks that violate these assumptions - for example, sensor networks or military ad-hoc networks - is the motivation behind the DTN architecture. Rather than adopting band-aid solutions using link-repair approaches or proxies, DTN uses a messaging scheme and is based on a partially connected network graph model.

Unlike the majority of papers covered in this course (apart from the really early ones), this challenged some fundamental assumptions of the Internet. Given that deep-space and military communication, as a few examples, will remain essential for years to come, the motivation behind a DTN-like architecture is very convincing. It's compatible with the current TCP/IP stack, appears to be a practical solution at first-glance and definitely merits further study. This one definitely belongs in the syllabus as a bit of a wild-card paper.

An Architecture for Internet Data Transfer

This paper introduces an extensible data-oriented transfer (DOT) service that decouples application-specific content negotiation from generic data transfers. One motivation behind the DOT service is to optimize bandwidth usage by minimizing control overhead (e.g., from HTTP or SMTP messages). Moreover, this modular architecture not only eliminates the need for re-implementation for each new service but also enables more focused efforts to improve data transfer. The authors acknowledge that since the DOT service is essentially designed for bulk transfers, services that promise low round-trip latency (e.g., CDNs or Google web services) or those with small-sized transfers pose an inherent incompatibility issue. The solution offered here is to use traditional delivery mechanisms for such cases rather than compromise the advantages of DOT.

The concept proposed in this paper is already used in sectors of the Internet today; for example, real-time media can use a TCP-based control plane and RTP over UDP for bulk packet delivery. Even though several complications arise with the large-scale employment of a DOT-like service (many of them addressed in the paper), it seems worthy of further exploration nevertheless. The idea is not too far-fetched and somewhat feasible, even if not completely practical for the Internet.

X-Trace: A Pervasive Network Tracing Framework

This paper introduces X-Trace, a unified network tracing framework for that spans several protocol layers (as opposed to tcpdump, for example) and applications. The concept behind X-Trace debugging is essentially to carry X-trace meta-data in packets. Received meta-data at one node's layer will be forwarded to the next node at that layer and related packets (such as in a DNS response) will all carry meta-data so that they are effectively linked together in traces. Finally, a reporting infrastructure (with a website, etc.) is presented to ensure visibility of network trace data to all relevant parties.

This is a neat idea that could potentially be quite useful for today's large-scale distributed systems. That said, I'm not certain whether the packet overhead due to X-Trace is justified by its benefits. Some of the applications that are mentioned (tracing messages, ISP troubleshooting, etc.) make a lot of sense and this is definitely a concept worthy of additional investigation. The paper goes well with Paxson's study on packet dynamics and definitely belongs in the syllabus.

End-to-End Internet Packet Dynamics

This paper sets out to model and explore measurements that reflect packet dynamics over a network. The author approaches the Internet as a mysterious quantity that needs to be probed to discover "pathologies" in the network. Specifically, out-of-order delivery, packet replication and packet corruption are examined using TCP-based measurement techniques. Of course, there is an emphasis on the need to account for TCP protocol-related symptoms to attain accurate measurements. Statistical analysis reveals several interesting trends, such as the occurrence of spikes (indicating a minimum time related to common 56 kbps links) in time-plots for out-of-order delivery . Moreover, measurements are explained in the context of TCP congestion control and acknowledgment mechanisms and reveal valuable insight into why, for example, TCP uses triple duplicate acknowledgments to trigger fast retransmission (and why it should but can't make a change to only two duplicate acknowledgments).

One thing that I appreciated here was the clear acknowledgment of possible improvements in measurement techniques and the drawbacks of some techniques employed in this study. This paper definitely gives an idea of just how complex and unpredictable Internet packet dynamics can be and provides approaches to measuring them; such measurements may be more difficult in today's significantly more evolved Internet, but several notions discussed here still hold value. For its time, Paxson's paper dispels several crucial assumptions about the Internet.

Internet Indirection Infrastructure

This paper proposes an architectural revamping of the Internet to decouple the act of sending and receiving. In this scheme, packets carry identifiers rather than IP addresses - all packets with a given identifier are directed towards an i3 node using a Chord-style mapping infrastructure. Finally, receivers will trigger the appropriate i3 nodes to route packets to receivers with matching identifiers. In addition to using identifier matching at i3 nodes to route packets to the intended destination, partial matches can be used to simplify multicast and load-balancing mechanisms.

One immediate concern with this mechanism, quite like the ones that arose for the previous DOA paper, is that the DHT look-up and intermediate i3 node traversal could significantly hamper the round-trip latency. Implementing reliability mechanisms (i.e., TCP) on such an architecture could also be a mess, as could security complications. Overall, there are some neat ideas presented here (more so than in the DOA paper) but the concept seems quite unrealistic and impractical.

Middleboxes No Longer Considered Harmful

This paper underscores the vital role of middle-boxes - specifically, NAT boxes and firewalls - in the modern Internet. Traditional networking principles dictate that such middle-boxes violate not only the end-to-end principle but also the notion that end hosts must be uniquely identifiable throughout a network. The authors claim, however, that these components provide essential security mechanisms, address space utilization and performance enhancements (in the case of caching). Instead of trying to achieve compliance with the "rules" of the Internet, the authors present a Delegation Oriented Architecture (DOA) that seamlessly incorporates middle-boxes. Essentially, DOA provisions unique endpoint IDs in a flat name-space and the ability for the sender and receiver to specify intermediaries that must be traversed (for example, a NAT that must process the packet).

In my mind, the proposed DOA architecture has several issues, starting with the fact that the intermediary specification still appears to defy the end-to-end principle. More importantly, the overhead introduced in the DOA packet header is considerable and I'm not sure how the authors underplayed this issue. Finally, the idea that DHT look-ups (going by previous papers, these are already intricate) will be required on a regular basis raises doubts over the performance and scalability of this architecture. The concept was interesting but the motivation is not very convincing (do we really want to introduce so much overhead just to maintain the sanctity of some networking "rules" or middle-boxes?) and the potential drawbacks are not sufficiently addressed.

DNS Performance and the Effectiveness of Caching

This paper evaluates the performance of DNS over several network traces, specifically looking at query failures (no response or response indicating nonexistent record) and latency perceived by Internet clients. Moreover, it takes the discussion of DNS caching in the previous paper one step further by questioning its impact on overall performance. The authors claim that DNS caching may inherently conflict with some applications that use the naming system, such as Content Delivery Networks (I'm still a bit confused about exactly why there's a conflict here). Looking at the trace analysis, they conclude that caching does not significantly improve performance for the clients but merely acts as a load-controlling mechanism for the name servers.

Even though the evaluation results were convincing, an intuitive explanation for the minimal impact of caching on client-perceived latency (for example) seemed missing. Yet again, several critical performance issues (negative responses, negative caching, etc.) were identified but a deeper insight into these problems was not necessarily offered. The paper provided a useful understanding of the practical issues surrounding the DNS, especially as it begins to interact with other protocols (e.g. TCP) and mechanisms such as CDNs.

Development of the Domain Name System

This paper discusses the motivation and design behind the Internet's Domain Name System (DNS). Initially, the authors describe the existing centralized HOSTS.TXT record file (which seems like a terrible idea right now, given the single point of failure) and the clear need for a distributed scheme. The hierarchical, tree-like structure that is presented seems quite intuitive and there is little mention of possible architectural alternatives. Unlike most previous papers in the syllabus, this one spends less time foreseeing potential problems; instead, the focus is on DNS design, functionality and a few immediately observed performance issues.

Caching was probably one of the more interesting points of discussion. One issues that was mentioned is that while meaningful query results are cached, negative results for nonexistent records are not. In my opinion, this is a valid but somewhat trivial concern. Instead, some foresight into security issues (i.e., cache poisoning) would have been appropriate. Interestingly, there appears to be a trend throughout many of the original Internet papers - strong assumptions are made about the trustworthiness of participants. Overall, this was an informative paper that underscored the reasons behind the DNS architecture. However, it did not pose as many questions going ahead; in a sense, it felt like undergraduate networking material.

Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications

coming soon

Looking Up Data in P2P Systems

coming soon

Active Network Vision and Reality: Lessons from a Capsule-Based System

coming soon

Resilient Overlay Networks

This paper presents the concept of a Resilient Overlay Network (RON) that provides reliable packet delivery by reducing detection and recovery time following network failures or outages. The authors discuss the scalability advantages that come along with the hierarchical organization of the Internet and then describe some disadvantages in terms of reliable packet delivery. Inter-domain routing with BGP can damp routing updates to minimize oscillations; this distortion of link-state information inevitably leads to suboptimal fault tolerance. RON nodes are deployed in various domains and communicate with each other to provide optimal packet delivery, via either direct Internet paths or other RON nodes.

These application-layer overlay networks are a neat concept and somewhat reminiscent of middleboxes - an intermediary structure to bypass certain shortcomings of the Internet infrastructure. One important point that the authors make is that forwarding via at most one RON node provides sufficient reliability gains. Even so, I'm not sure a) how the modern Internet would react to a heavy influx (not just a small set as in this paper) of RON nodes b) whether inter-domain routing latency and distortion is still a big enough problem today to warrant the use of RONs. Interesting paper, must say.

A First-Principles Approach To Understanding the Internet's Router-level Topology

This paper presents a slightly different perspective on modeling the topology of the Internet. The authors initially point out flaws in the power-laws approach - essentially, several different network models can give rise to similar degree distributions, thereby reducing the effectiveness of power-laws. Instead, a "first-principles" approach with an emphasis on practical network engineering considerations is adopted here. One must identify which factors are fundamental to topology construction rather than simply searching for data-driven power-law analysis. In doing so, router technology and economic considerations must be taken into account.

Using probabilistic methods to generate graphs that model network behavior is a flawed approach as random rewiring between the nodes can damage the performance and efficiency of these models. Interestingly, the authors bring up the point that they have used "toy models" rather than actual network data to illustrate the new modeling approach. Even though they refute this criticism to a degree, there will remain some lack of credibility due to this facet of the research. Unlike the power-laws paper, this one appears to spend more time discussing the flaws of other approaches and not enough on concrete modeling techniques backed by network-based evaluation. Valid points are brought up but the paper feels a bit incomplete.

On Power-Law Relationships of the Internet Topology

This paper addresses the need for accurate models of the Internet topology, for simulation purposes as well as for analyzing and optimizing protocols. Topology can be studied at the intra-domain or inter-domain level using metrics such as node out-degree and inter-node distance. Power-laws have previously been used to describe network traffic but not network topology; probabilistic distance-based models have been very popular for this purpose. The authors aim to identify useful relationships between graph parameters, choosing parameters that can be captured with one number. For example, some chosen parameters are the rank exponent, the out-degree exponent and the hop-plot exponent.

One naturally wonders how such strict relationships emerge in a chaotic network of both cooperative and antagonistic forces such as the modern Internet. The authors anticipate and respond to this quandary with a discussion of the dynamic equilibrium reached in the disorder of the Internet. Several arguments are made in favor of further exploring such power-laws, such as the ubiquity of self-similarity and chaos. I really enjoyed this read and agree that this could be very important for network research going forward. The emergence of these power-laws is reminiscent of Gaussian and Poisson distributions describing various environments in communication and biology - we all know how these mathematical models have guided research in those disciplines.

Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks

This paper describes the directed diffusion approach for coordinated sensing and data dissemination in wireless sensor networks. The design of this new paradigm is driven by robustness, scalability and energy efficiency requirements. Data-centric communication in this scheme involves a request for "interests" followed by data propagation and local aggregation. The authors stress that energy efficiency requirements dictate the need for short-range hop-by-hop communication and local computation. Directed diffusion has a few features reminiscent of the TAG service discussed in the previous paper, such as in-network data aggregation and caching.

The evaluation suggests that novel features such as reinforcement-based best path adaptation do indeed provide substantial energy savings, especially given the task-specific nature of modern sensor networks. One interesting point of discussion would be the potential feasibility of the local approach adopted here for a general IP-based network. I found this paper interesting but it is perhaps not as essential in the syllabus as the TAG paper.

TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks

This paper presents TAG, a distributed aggregation scheme for wireless sensor networks. Many applications of ad-hoc mote networks require the execution of declarative queries to extract meaningful information from collected data. TAG provides an efficient alternative to centralized data processing mechanisms as it reduces communication requirements and hence bandwidth consumption. Essentially, sensor nodes are organized in a routing tree structure with a root base station serving as the data processing interface to the end user. This tree structure exploits the broadcast nature of radio transmission by maintaining level information at each node - even if a sensor node loses communication with its parent, it can detect a new parent by overhearing messages from the next higher layer in the routing tree. Upon applying the query locally and aggregating results from its children, each node routes data back to the root via its parent.

One appeal of the TAG service is the use of simple SQL-style queries. The concept is also somewhat resemblant of the distributed Map-Reduce implementation of a full inverted index. In that scenario, a query can be efficiently processed by distributing the work across many mappers, each dealing with a small subset of the text base. The primary concern that came to mind while reading this paper was the effect of disconnected nodes or lost messages. The authors answer this quite thoroughly with a caching solution. This paper addresses many issues inherent in sensor networks and certainly belongs in the syllabus.

XORs in The Air: Practical Wireless Network Coding

In line with the recent trend of papers that discuss throughput optimization over wireless networks, this paper introduces network coding theory for this very purpose in the COPE scheme. The initial example of two receivers exchanging messages via a router by XORing them into a single stream provides an intriguing preview for the reader. The authors importantly show that the network coding approach can integrate seamlessly with existing TCP and UDP protocols - unlike the ExOR mechanism of the previous paper, this one is a more immediately practical solution. That said, the throughput gains are still hindered by the presence of TCP, mainly due to congestion control restricting the queue size and limiting the impact of coding. In general, only packets that are headed to different hops and are of different lengths are XORed.

The results show that COPE provides significant gains in throughput under TCP and especially UDP, which allows router queue sizes to grow large. Moreover, coding gains are greater when uplink and downlink traffic is similar. This paper was quite interesting because it integrated information theory and networking in a way that I had not been previously exposed to. The last two papers have probably been among the most exciting thus far, in my opinion.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

This paper presents ExOR, an integrated network-link layer protocol for the routing of large unicast transfers over multi-hop wireless networks. In traditional routing mechanisms, a single lossy link can trigger a complete retransmission. On the other hand, ExOR chooses the next hop of a route after confirming transmission on that hop. By deferring this choice, the packet transmission has multiple opportunities to make progress and is not restricted to a fixed path of loss-vulnerable points-of-failure. In essence, this dynamic approach to routing enables transmission (without unnecessary retransmissions) over long radio links with high loss rates and provides substantial increases in throughput.

For me, the discussion of interference between potential forwarding nodes was inadequate and I wasn't quite convinced by some of the assumptions that were made. Moreover, the evaluation results were quite conclusive but I would've preferred a better explanation of why the additional inter-node communication required for this scheme is not a major drawback in its adoption. The use of ETX as a path metric in determining hop priority was very appropriate given the papers we've read recently. Finally, I've been thinking about such dynamic routing mechanisms ever since I started learning about networking and wondering why it's rarely mentioned - in that sense, this paper was a very satisfying read. I'd definitely keep it in the syllabus. One last thing - the acronym ExOR (Extremely Opportunistic Routing) is pretty neat. This paper also described a good example of when the end-to-end principle can be compromised.

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

This paper compares the performance of various routing protocols over "ad hoc" multi-hop wireless networks that do not require network infrastructure or centralized administration, such as the rooftop network discussed in a previous paper. Specifically, the DSDV, TORA, DSR and AODV protocols are evaluated over a ns-2 network simulator. The authors provide a very useful introduction to the potential applications of ad hoc networks and briefly discuss the ns-2 physical and link layer simulator. Destination-sequenced Distance Vector (DSDV) ensures loop-freedom and updates routing tables based on temporal locality of path information as well as optimal path metrics. Temporally-reordered Routing Algorithm (TORA) takes a very different approach, discovering routes on-demand and placing less emphasis on shortest-path routing. Dynamic Source Routing (DSR) completely abandons hop-by-hop routing and stores the complete, optimal node path at the source. This protocol does not require periodic route advertisement but one wonders how effective this can be over larger networks. Finally, Ad Hoc On-demand Distance Vector (AODV) combines several features of the DSDV and DSR protocols.

The simulation results indicate that while all protocols perform well in the absence of node mobility (large pause time), DSR and AODV come out on top in the presence of mobility. In terms of overhead, only the periodic DSDV routing protocol maintains a nearly constant overhead with respect to mobility rate. I really enjoyed this paper because it provided an overview of various approaches to multi-hop routing and built upon the previous few papers. The discussion was fairly straightforward as well.

A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper presents the Expected Transmission Count (ETX) metric, discussing its advantages and describing its design and implementation for DSDV and DSR routing protocols. Unlike the minimum hop-count metric, the ETX metric accounts for (potentially asymmetric) link loss ratios and interference between successive links to find the optimal path - the one with the highest throughput. The EXT metric will make such a network as the multi-hop rooftop (discussed in the previous paper) practical to implement. Initially, the authors point out the various shortcomings of the minimum hop-count metric.

Upon describing the use of the ETX metric with DSDV and DSR routing protocols, the performance is evaluated with respect to link loss ratios and interference. One thing that confused me is why Figures 2 and 6 both display crossing lines - how can the DSDV hopcount route achieve higher throughput in that small period than the best static route? Overall, this paper was interesting but several points were rather obvious. The analysis of the effect of link loss ratios was especially thorough. This probably belongs in the syllabus.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper discusses the design of an unplanned urban rooftop 802.11b mesh network. The unconstrained node placement, omni-directional antennas, self-configuring software and other robust features make this easily deployable. Each rooftop node is hosted by a participating volunteer at a random, unplanned location. The impact of this approach is seen in the fact that this network has evolved 37 nodes in just a year with minimal administrative effort.

Upon evaluating the performance of this rooftop network, it is clear that the unplanned, multi-hop mesh network provides increased connectivity and throughput. Given that this network requires little global coordination, it appears to be a very significant breakthrough. The throughput-optimizing routing protocol was especially interesting - in addition to standard link-state flooding using Djikstra's algorithm, can the best route be chosen taking current link usage into account? Unlike many of the papers in the syllabus, this one focused on architecture rather than protocol and was an appropriate change-up in the syllabus.

Modeling Wireless Links for Transport Protocols

This paper discusses the role of wireless link modeling in the design of transport protocols. Due to non-congestion-related packet losses and the latency associated with corrective link-layer mechanisms, wireless links can have a drastic effect on TCP transport performance. The authors present that a wireless link model should be simple but realistic - as long as the model simulates the net effect of a mechanism, it need not completely represent the actual mechanism. The authors describe the topology and traffic characteristics for cellular, WLAN and satellite wireless links. Transport protocols are evaluated using "goodput", the portion of delivered data that is useful, as well as the standard performance metrics: throughput, delay, fairness and dynamics. Having introduced the work, the authors present models for corruption, delay variation, reordering, channel allocation, bandwidth variation, asymmetry, buffering and handovers.

Finally, the authors comment on the interplay between transport protocols and wireless technologies. Characteristics that are not fundamental to transport protocols (or wireless technologies) should be modified to accommodate smooth interaction with wireless technologies (or transport protocols). Having read the previous paper on TCP performance over wireless links, this one was very appropriate and provided a more balanced approach to the unison of transport-layer protocol and link-layer technology. One thing I'm still confused about is the following statement: "Furthermore, because cellular and satellite links have high latency, connections traversing them can be penalized by the bias of TCP congestion control toward flows with high RTT (Round-Trip Time)". Assuming that high latency is related to high RTT, why does a congestion control mechanism biased towards connections with high RTT "penalize" such connections?

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

This paper discusses several schemes designed to improve the performance of TCP over wireless links that suffer from significant packet losses due to bit errors and handoffs. Currently, TCP control mechanisms are insufficient for such links because they assume that all losses are congestion-related and thus can unnecessarily reduce end-to-end throughput. The authors classify these schemes as end-to-end protocols, link-layer protocols and split-connection protocols. Using end-to-end throughput over wired and wireless hops as a performance metric, a TCP-aware link-layer protocol with selective acknowledgments proved to provide the highest throughput. End-to-end schemes also proved to be effective, do not require additional support from intermediate nodes and can improve throughput dramatically when combined with an ELN mechanism.

Reading this paper provided a good insight into a variety of methods for effective TCP-based transmission over lossy wireless links without having to learn the details of these methods. The focus was on the bottom line: optimizing end-to-end throughput. However, the evaluation seemed rather simplistic as the protocols were implemented under a basic range of bit-error rates. This provided valuable results but simulation and analysis under real network conditions may reveal new information in this field. Overall, this was a very informative paper and built somewhat on the previous one.

MACAW: A Media Access Protocol for Wireless LAN's

In light of the recent emergence of mobile computing devices that will necessitate controlled access to indoor wireless media, this paper proposes a new media access protocol for wireless LAN's: MACAW. Given that the relevant congestion in the described infrastructure is at the receiver, carrier-sense approaches are avoided and Karn's MACA (multiple access, collision avoidance) proposal is used as a starting point. The MACA protocol uses an RTS-CTS-DATA packet exchange and a binary exponential backoff (BEB) scheme. The authors argue that reliable transmission can be enforced more efficiently using link-layer recovery. Moreover, bi-directional transmission schemes require attention to congestion at both the receiver and the sender. Instead of adopting a standard CSMA/CA approach, the MACAW protocol sends a data-sending packet (DS) to block all other transmissions until the ACK packet has been transmitted - this prevents useless transmission requests in the exposed terminal case. Hence, MACAW uses an RTS-CTS-DS-DATA-ACK packet exchange. Moreover, a coordinated MILD (multiplicative increase, linear decrease) backoff scheme is used to ensure fairness of access.

The development of MACAW revolves around fair access to wireless media - the multiple stream model, RRTS mechanism and coordinated backoff scheme are all introduced with this goal in mind. That said, I wonder why the focus is completely on fairness and there isn't even the slightest trade-off with performance. Moreover, the discussion of the MILD (MIAD) backoff scheme made me wonder why the AIMD scheme is not used here, given that it helped achieve fairness in the congestion control scheme discussed earlier. These are different manifestations of fairness but I was surprised to see no mention of AIMD. Finally, the illustrations of the exposed terminal, hidden terminal and other situations were very effective in explaining the reasoning behind the features of the MACAW protocol. Overall, I really enjoyed this paper.

A Fast Switched Backplane for a Gigabit Switched Router

This paper presents a strong case for routers with a switched backplane. Initially, the authors provide a very useful overview of router architecture, breaking the path of a packet down into the forwarding decision, the backplane and the output-link scheduler. Router architectures are moving away from the use of shared backplanes as they can easily become congested and limit the performance of the system. Using crossbar switches instead allows multiple packets to be simultaneously transferred across the backplane, thereby increasing the aggregate bandwidth of the system. Simply making the backplanes faster has proven to be insufficient to keep up with common high packet arrival rates, so switched backplanes are the optimal solution. The authors briefly discuss why handling variable-length packets leads to lower throughput - essentially, abnormally long packets at the input can hold up other packets instead of being forwarded to a starved output. HOL blocking severely limits the throughput since the cell at the head of the FIFO input queue blocks cells behind it from access to the outputs. The authors present a solution in virtual output queueing (VOQ), which was also discussed in the previous paper. Next, the iSLIP algorithm is introduced as an input-output matching algorithm that provides a fast, high-throughput, starvation-free solution.

I truly enjoyed reading this paper. First of all, the background material was reviewed very well before jumping into any algorithms or proposals. Router architecture was covered in great detail and the decision to focus or not focus on each aspect of this architecture was explained quite well. This paper should definitely be part of the syllabus. One thing I wasn't sure about was whether these ideas were already being implemented at the time or whether they were proposed ideas for future implementation.

Scaling Internet Routers Using Optics

This paper introduces the use of optical technology inside routers to increase their capacity and enable it to keep up with the rapid growth in Internet traffic. Despite the expected growth of router capacity, traffic will likely outgrow it and balloon in comparison within a decade. In describing the problems of existing multi-rack routers, the authors reveal the need for a scalable solution that guarantees 100% throughput. Having expressed the motivation behind the new technology, the authors initially present Chang's load-balanced switch architecture and explain how it satisfies the aforementioned requirements. To address the first major issue present in the load-balanced switch, the expensive optical switch fabric can be replaced by a single fixed mesh of optical channels. Here, the actual packet switching occurs in the intermediate linecards. Due to TCP's poor performance in the presence of out-of-order packets, the Full Ordered Frames First (FOFF) scheme is used to prevent packet mis-sequencing. The FOFF scheme is efficient, practical and has no pathological traffic patterns. The router must also be robust: it must support an arbitrary placement of an arbitrary number of linecards. This requires a reconfigurable switch that scatters traffic uniformly across the linecards. Here, the authors propose a hybrid electro-optical switch, as well a pure optical switch that should be implementable in the near future.

The primary obstacle for me throughout this paper was my limited knowledge of router internals such as linecards and racks. To an extent, I had to deduce what these terms meant from the early sections of the paper. Otherwise, this was an interesting read on router technology and the need to increase router capacity. I wouldn't say it's absolutely essential for the syllabus.

Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism

This paper considers real-time applications in an Integrated Services Packet Network (ISPN) and proposes a modified ISPN architecture. The authors observe that real-time applications may not always require a pre-computed worst-case delay bound provided by a guaranteed service. Instead, a predicted service that tracks network performance and uses it as a guide in computing dynamic delay bounds. The introduction of this predicted service would provide not only superior application performance due to the use of adaptive playback, but also higher link utilizations and thereby greater apportioning of service costs. The authors provide a unifying mechanism for real-time as well as datagram traffic - the concepts of isolation and sharing are central to this mechanism. Finally, there is an emphasis on the importance of pricing to encourage use of suboptimal service. This will avoid having to enforce sharing by refusing a large fraction of requests for real-time traffic. Price discrimination is also used to explain the potential value of the predicted service.

Given that I worked with real-time streaming and multimedia over the summer, I definitely found myself quite engaged in this paper. The innovative concept of predicted service also intrigued me after having worked with fixed-delay packet-dropping mechanisms in video streaming. This paper definitely builds upon the previous one by giving an explicit case of providing various classes of service to suit different application requirements. The discussion of price discrimination felt a little incomplete as a few assumptions were made about lower prices leading to requests for lower-quality service.

Fundamental Design Issues for the Future Internet

This paper considers whether the Internet should adopt a new service model to satisfy the traffic characteristics and service requirements of the variety of applications that are growing in demand among the general public. One example of the problems posed by such a variety of applications is that real-time multimedia applications not only suffer from the delays and dropped packets typical of the Internet architecture, but also do not back off in the face of congestion - in the process, data applications that adhere to congestion control receive very little bandwidth. Essentially, the primary goal in designing a network architecture is to optimize the efficacy, or total utility to various applications, of the architecture. This can be achieved by supplying more bandwidth or by extending the service model to accommodate applications requiring different classes of service. The authors condense the trade-off between increased bandwidth and extended services to the fact that while delivering real-time suitable service to all Internet applications is not feasible, extending the service model for real-time applications would automatically free up bandwidth for data applications. To maintain the service interface and the layering model, the particular class of service should be "explicitly requested" by a flow rather than detected and "implicitly supplied" by the network.

The authors add further commentary to the trade-off between bandwidth and mechanism. Extensions to the service model could be rendered superfluous if incorrect assumptions are made about application service requirements. On the other hand, additional bandwidth may not be extremely inexpensive and this would result in a suboptimal architecture that cannot be feasibly provisioned. The authors clearly state that their intention is to open a discussion and present the issues rather than to present definite solutions. This paper didn't seem to add as much value as some of the others since it simply touches upon issues that are somewhat obvious. However, it does present a picture of the future direction of the Internet and the issues that must be resolved to make it flourish even more. This is not essential but it's worth reading and keeping in the syllabus.

Congestion Control for High Bandwidth-Delay Product Networks

This paper suggests that the inevitable move towards networks with high bandwidth-delay products will cripple the congestion control mechanism currently provided by TCP. In its place, the authors propose a new "explicit" congestion control protocol, XCP. The key feature of XCP is that unlike TCP, it separates efficiency control and fairness control. The authors argue that since efficiency and fairness are independent factors, decoupling them provides optimal control. For example, AIMD achieves fairness but the additive increase isn't quite the most efficient solution for high-bandwidth connections as too many RTTs are wasted in achieving the capacity. XCP continues to use an AIMD scheme for fairness control but instead opts for MIMD for efficiency control - the separation allows each control to use a suitable scheme. Despite using the AIMD scheme employed by TCP, XCP has quicker convergence to fairness than TCP since multiplicative decrease is performed more often than merely on the detection of dropped packets. Upon describing the XCP control mechanisms, the authors present simulations that compare XCP and TCP in the presence of previously discussed features such as RED and CSFQ queues. The results demonstrate that XCP matches TCP under normal conditions and that it outperforms TCP when the per-flow delay-bandwidth product becomes large.

This paper was a surprise after reading so many older publications that assumed TCP congestion control. The arguments made for XCP seem quite convincing; that said, I'd be surprised if there are no tradeoffs in TCP's favor as this paper appears to imply. The provision for security extensions is compelling and the section on XCP's TCP-compatibility is a very good idea considering the resistance to the status quo that always arises to some degree in technology. Papers like this really diversify the syllabus and differentiate this course from the standard undergraduate networking course.

Random Early Detection Gateways for Congestion Avoidance

This paper explores the use of Random Early Detection (RED) gateways as a congestion control mechanism in cooperation with network transport protocols such as TCP. The primary goal of RED gateways is to maintain the network in a high throughput, low delay region by detecting incipient congestion and responding appropriately. Other crucial goals stem from the shortcomings of Random Drop and Drop Tail gateways. One is to avoid global synchronization due to many connections reduce their transport windows in response to congestion and lead to suboptimal network throughput. Another is to accommodate bursty traffic by allowing transient congestion. RED gateways use minimum and maximum thresholds for the average queue size to control packet dropping. If the average queue size is less than the minimum threshold, no packets are dropped; if the average queue size exceeds the maximum threshold, all packets are dropped. In the critical region between the two thresholds, RED gateways mark packets for dropping with a probability linearly related to the average queue size. This approach ensures that a particular connection is notified of congestion with a probability that is roughly proportional to the connection's share of the gateway bandwidth. Moreover, this definitely avoids the global synchronization problem. To determine the average queue size, RED gateways use an exponential weighted average low-pass filter, which effectively eliminates any bias against bursty network traffic. The authors assert that the optimum average queue size for maximizing throughput and minimizing delay is dependent on network characteristics.

This paper was an enjoyable read, especially because the explanations were very lucid and there was no unnecessary mathematical notation to explain a relatively simple concept. The discussion of using packet-based vs byte-based queue control was excellent, especially because that was a central issue in the previous papers on gateway FQ-based congestion control. The mention of using separate queues for separate classes of traffic was essential. Even though the authors accounted for the ambiguity in the optimal queue size, some examples of average queue sizes and min/max thresholds used for RED gateways would have been appropriate. The coverage of misbehaving hosts felt a little inadequate as well, but overall this is a must for the syllabus.

Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

This paper addresses the drawbacks of the Fair Queuing (FQ) algorithm proposed in the previous paper: the need for state maintenance, buffer management and per-flow packet scheduling. Instead, the authors propose a simpler architecture comprised of edge routers and core routers. Edge routers maintain per-flow state and insert flow rate information into packet headers; core routers use the flow rate information to implement a probabilistic dropping algorithm. The authors analyze the performance of this Core-Stateless FQ scheme and present simulations to illustrate the scheme. The goal here is to achieve reasonable approximations to fair bandwidth allocation rather than matching the FQ scheme perfectly. The packet dropping algorithm is carefully explained using a fluid model, followed by a discussion of rate estimation at the edge routers and determining the fair share. One impressive caveat of this algorithm is the weighted CSFQ mechanism, which enables the use of differential services such as the file server pair that was problematic with the FQ scheme of the previous paper. The authors also assure that each operation that the CSFQ scheme requires can be efficiently implemented. Finally, CSFQ is compared to other queueing algorithms by simulation and evaluation of the results. The authors also explore the effect of high latency in an "all-core" design. Later, the identification approach is introduced as an alternative method of achieving gateway-based congestion control.

I really enjoyed this paper as the concept of separation into edge routers and core routers seems quite innovative. The authors did an excellent job of identifying the areas where this scheme may or may not thrive, rather than presenting a purely positive assessment. This should definitely remain in the syllabus.

Analysis and Simulation of a Fair Queueing Algorithm

This paper discusses the role of gateway queueing algorithms in congestion control and proceeds to present the many advantages of a proposed fair queueing algorithm. Unlike the previous papers that detailed source-based congestion control schemes, this one focuses on the effect of gateway-based queueing algorithms on congestion control. The authors argue that standard FCFS queuing algorithms place the burden of congestion control completely on hosts, thereby leaving the network bandwidth vulnerable to ill-behaved hosts that do not comply with standard TCP congestion control schemes. In this light, Nagle's round-robin-based fair queueing (FQ) algorithm aims to provide protection against "antisocial" behavior by employing gateway queueing-based congestion control. Unfortunately, Nagle's proposal does not ensure fairness for several reasons - for one, it does not account for packet lengths. Before diving into their own proposal, the authors clarify the motivation behind a fair queueing algorithm.

The fair allocation of bandwidth, promptness and buffer space among users is complicated by the question of what defines a user. Rather than defining the user as the source, the destination or a process running on the source host, the best trade-off is achieved by allocating by conversations (source-destination pairs). The proposed algorithm uses a packetized queueing mechanism based on the end times of packets; this successfully accounts for packet lengths. Moreover, newly arriving packets are accommodated in the queue by dropping the last packet from the dominant conversation. In effect, this punishes ill-behaved hosts by charging them for poor congestion control on their end. Finally, the authors compare the performance of the FQ scheme to that of the FCFS-based standard congestion control. In conclusion, the authors assert that achieving low delay or avoiding dropped packets is very difficult with congestion control only at hosts, especially in a non-cooperative environment. Two objections have been raised to FQ algorithm-based congestion control. The first objection is that some conversations need more bandwidth than would be deemed "fair" (file server pairs, for example) - one solution to this is to utilize bandwidth priorities in the queueing algorithm. The second objection is that such a FQ algorithm requires advanced gateways, which may not be technologically or economically feasible.

This paper was very intriguing because it provided a new angle to congestion control, one which I'd never seen before. I'm surprised that this aspect of congestion control is rarely covered in undergraduate networking. The authors did a fairly good job of covering the caveats involved, such as applications that require "unfair" bandwidth allocation, but elaboration on assigning bandwidth priorities would have been interesting indeed. Definitely one to keep in the syllabus.

Congestion Avoidance and Control

This paper describes several early algorithms put in place for TCP congestion control and avoidance. Initially, the authors introduce the slow-start algorithm as a means to gradually increase the amount of data in transit. This algorithm starts with a congestion window of one packet and increases the window in response to acknowledgments - in this sense, it is a self-clocking mechanism that moves towards equilibrium. Unlike other start-up mechanisms, the authors argue, slow-start contains the data rate to within twice the maximum allowable on the network path. Next, a method to estimate the round-trip time is presented and a case is made for exponential back-off. Although the need for such a retransmission mechanism is rather obvious, the actual proof is not provided here. Finally, the authors delve into congestion avoidance - what happens around the "knee" of the curve. The additive increase, multiplicative decrease scheme from the previous paper is substantiated here in a congestion avoidance algorithm for TCP. There is also some talk on adding congestion control mechanisms at network gateways. This definitely seems to be very important in promoting fair sharing of the network. One interesting caveat here is that misbehaving hosts will have their packets dropped even if they try to ignore gateway signals - that's pretty neat.

Given the background from the previous paper, this was very appropriate and took a different angle on congestion control and avoidance. The authors probably should have spent more time talking about edge cases as the basic mechanisms presented seem pretty obvious, but that's probably with hindsight more than anything else. Finally, it was good to see appended sections with more rigorous explanations of the algorithms.

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

This paper explores a class of increase/decrease algorithms that can be used for congestion avoidance schemes and concludes that the additive increase, multiplicative decrease algorithm quickly converges to the key performance metrics: efficiency and fairness. The authors classify both congestion avoidance (operating around the "knee" of the network traffic curve) and congestion control (staying to the left of the "knee") mechanisms as dynamic resource management problems. Congestion avoidance mechanisms specifically increase or decrease the packet output rate in response to the network load. For simplicity, the analysis in this paper is based on the binary feedback model, which assumes a synchronous feedback and control loop. Four general increase/decrease algorithms are presented - MIMD (multiplicative increase/multiplicative decrease), MIAD, AIMD and AIAD - and the criteria to be used to evaluate their effectiveness are also established: efficiency, fairness, distributedness and convergence. Next, the additive increase, multiplicative decrease scheme is graphically shown to converge to the optimal point marked by the intersection of the fairness and efficiency lines. On the other hand, the path traced by the additive increase, additive decrease scheme remains parallel to the fairness line and never converges. The case for an AIMD scheme is further supported by sections with somewhat rigorous algebraic and vector analysis.

I really enjoyed this paper because it provided detailed, technical reasoning behind the choice of the AIMD increase/decrease scheme in TCP transport, something that is taken for granted throughout undergraduate networking. Moreover, there was no inherent bias towards the AIMD scheme - the authors set out to explore all four classes of increase/decrease algorithms and demonstrated exactly why they arrived at this scheme. Even though the authors provided a preview of delayed feedback and asynchronous operation at the end of the paper, an actual effort to incorporate it into the initial analysis would have been interesting. Some of the assumptions that were made may be a little too strong. Overall, very interesting paper and definitely a keeper for the syllabus.

On Inferring Autonomous System Relationships in the Internet

This paper proposes a method to explore relationships between ASes, which were described in the previous paper. These relationships can provide insights into network traffic and optimal interdomain routing policy. The author suggests that BGP routing table entries can be used to generate graphs that accurately represent AS relationships. The communication subsystem is only one among several possible sources of error for the described mechanism. Since the file transfer application must perform an extensive end-to-end check even in the presence of low-level reliability measures, the communication subsystem should not implement expensive functionality to guarantee reliability. The degree of low-level reliability to strive for should be carefully determined based on the performance tradeoff. Low-level functionality may be efficient for applications that can perfectly leverage the provided reliability measures; on the other hand, it may force applications to bear the burden regardless of whether they actually require the reliability measures.

Even though this paper was an interesting read, it isn't quite as fundamental to the Internet as the previous papers. Reading this immediately after the Interdomain Internet Routing is a great idea for two reasons - the author elaborates on aspects of AS routing policy that may have been previously unclear and the reader already has a basic understanding of the topic before trying to delve into the proposed algorithm and method for generating graphs that depict AS relationships. I'm not sure if this is vital for the syllabus.

Interdomain Internet Routing

This paper clearly explains the routing mechanisms that connect administrative domains in the Internet topology. The Internet comprises Autonomous Systems, administered by a single commercial entity, that exchange reachability information with one another using the Border Gateway Protocol (BGP). Unlike intradomain routing, interdomain routing requires a great emphasis on scalability. Internet Service Providers (ISPs) can engage in transit relationships, financial agreements to share access to each other's routing tables. Peering relationships, on the other hand, involve granting access to a subset of each other's routing tables for mutual benefit. In the commercial reality, interdomain routing decisions must be based not only on reachability but also economic considerations. For example, an ISP may deny access to a competitor or seek a financial gain before agreeing to transit packets from another AS. Rather than looking to optimize the path cost, BGP revolves around scalability, policy and cooperation.

The content of this paper is still very relevant today and the clarity of the explanation makes it an essential read in the syllabus. This is the first paper that has explored the real-world, commercial aspect of the Internet rather than focusing on theoretical mechanisms and hypothetical situations. Perhaps some elaboration on potential security threats for interdomain routing would have been appropriate. Overall, this was a very informative read.

The Design Philosophy of the DARPA Internet Protocols

This paper discusses the design goals that drove the development of early Internet architecture. The primary objective was to interconnect and unify existing networks such as ARPANET and the packet radio network. Other goals included survivability in the face of network failures, support for multiple types of service and a variety of networks and distributed resource management. The communication subsystem is only one among several possible sources of error for the described mechanism. Since the file transfer application must perform an extensive end-to-end check even in the presence of low-level reliability measures, the communication subsystem should not implement expensive functionality to guarantee reliability. The degree of low-level reliability to strive for should be carefully determined based on the performance tradeoff. Low-level functionality may be efficient for applications that can perfectly leverage the provided reliability measures; on the other hand, it may force applications to bear the burden regardless of whether they actually require the reliability measures.

The author proceeds to provide further illustrative examples of this end-to-end principle such as delivery acknowledgment (the case where acknowledgments must be sent from the application layer), secure transmission (the case where data must not be vulnerable before or after network transmission) and duplicate message suppression (the case where the application generates duplicates beyond the recognition of lower layers). Finally, the end-to-end argument should not be used as an absolute guide but in conjunction with a careful assessment of application requirements and performance tradeoffs.

Given that this paper presents a principle that is the foundation of modern data communication networks, it should be a fundamental part of the syllabus. The author suggests that this end-to-end principle applies to general systems but only elaborates on applications that involve data communication systems. Some of the examples seem slightly far-fetched but overall, the argument is quite convincing.

End-to-End Arguments in System Design

This paper presents an argument against excessive low-level functionality in distributed systems, especially those with a data communication component. Initially, this line of reasoning is illustrated through the example of a file transfer mechanism in which one host reads a file from disk and communicates it across a network to a second host, which then writes the data to disk. The communication subsystem is only one among several possible sources of error for the described mechanism. Since the file transfer application must perform an extensive end-to-end check even in the presence of low-level reliability measures, the communication subsystem should not implement expensive functionality to guarantee reliability. The degree of low-level reliability to strive for should be carefully determined based on the performance tradeoff. Low-level functionality may be efficient for applications that can perfectly leverage the provided reliability measures; on the other hand, it may force applications to bear the burden regardless of whether they actually require the reliability measures.

The author proceeds to provide further illustrative examples of this end-to-end principle such as delivery acknowledgment (the case where acknowledgments must be sent from the application layer), secure transmission (the case where data must not be vulnerable before or after network transmission) and duplicate message suppression (the case where the application generates duplicates beyond the recognition of lower layers). Finally, the end-to-end argument should not be used as an absolute guide but in conjunction with a careful assessment of application requirements and performance tradeoffs.

Given that this paper presents a principle that is the foundation of modern data communication networks, it should be a fundamental part of the syllabus. The author suggests that this end-to-end principle applies to general systems but only elaborates on applications that involve data communication systems. Some of the examples seem slightly far-fetched but overall, the argument is quite convincing.