BotGraph: Large Scale Spamming Botnet Detection

Summary

This paper looks for correlations in bot activity to detect and stop botnet account registrations. The design uses two methods for detecting botnets: aggressive signup detection and login across different AS detection.

The aggressive signup detection uses an exponentially weighted moving average of signups. If the the number of signups jumps unexpectedly the system assumes it may be due to bot activity. This assumes that bot owners cannot slowly ramp up the signup rate due to high churn of bot machines.

BotGraph, also detects "stealthy bot-accounts." These are groups of bots that operate in a collaborative way. They authors assume that collaborative bots will login to a small number of accounts in many locations. This is justified by the fact that aggressive signup detection limits the number of available accounts. The proposed technique create a graph of users with an edge weight equal to the number of ASes both users have logged in from. They use this to look for clusters of users with high edge weights - these usually indicate bot accounts.

Thoughts

This paper makes many assumptions about the limitation of botnets. For example, I am not convinced that it is impossible to ramp up account creation from one node slowly enough to avoid the EWMA limit. Similarly, bot owners could simply assign one account per bot or one account per AS to defeat the stealthy bot detection algorithm. While the proposed techniques probably work well now, I suspect that when deployed widely botnets well adapt and overcome these protections.

Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks

Summary

This paper aims to reduce botnet attacks by identifying humans through activity patterns. Specifically, the authors propose installing a secure, trusted piece of code which will detect "human activity" and attest that requests are coming from a human.

The proposed design uses an "Attester" which is loaded from a TPM chip before the OS. This code intercepts all mouse and keyboard activity. The attester could operate in one of two ways: either prompt the user to answer questions or guess that a human is making requests. The authors choose to guess when a human is making the requests because the alternative might lead to "always-click-OK" behavior. When keyboard or mouse activity is detected within a short time of an HTTP request, the Attester sends a cryptographically signed token along with the request. This token attests that a user made this request no a bot.

The key benefit of the proposed technique over CAPTCHA is that it attests that the originating requests come from a human at the requesting machine. CAPTCHA images can be sent to remote human solvers while the proposed attester is not susceptible to this.

Thoughts

I like the idea of using a trusted piece of code to ensure that the attestation comes from the requesting machine and has not been tampered with. However, I can't imagine this being widely used. Presumably, users install this voluntarily, so backwards compatibility would be required thus leaving an way for bots to operate. The second problem is that bots could become smarter and only send requests after user activity.

Skilled in the Art of Being Idle: Reducing Energy Waste in Networked Systems

Summary

This paper proposes the idea of sleeping networked desktops when they are idle. It analyzes the traffic normally seen by desktops during idle periods and concludes that a proxy is necessary to handle this traffic on behalf of the sleeping node.

The authors address three main problems:

1. How much energy can be saved by sleeping nodes when idle?
2. What network traffic do idle machines use?
3. How to design a proxy to handle traffic on behalf of sleeping nodes?

The authors find that enterprise desktops are idle over 50% of the time and most have power management disabled. Thus, there is an opportunity for large energy savings by sleeping nodes.

Next, the authors look at network traffic seen by idle machines. They find that office machines receive roughly 3 packets a second during idle times. Therefore, the periods of network inactivity are very small. The authors classify this traffic and find that over 50% of incoming traffic is multicast and broadcast. The majority of broadcast traffic is ARP and NetBIOS, while the majority of multicast is router traffic. A large part of this traffic can safely be ignored but some requests must be replied to.

The authors design a proxy that handles traffic on behalf of sleeping nodes. It responds to DHCP, ARP and NetBIOS traffic, it ignores router traffic, and wakes the node for all other incoming traffic.

Thoughts

The most interesting part of this paper was the classification of network traffic seen by idle machines. It is unfortunate that a proxy is required to handle traffic for sleeping nodes. It would be interesting to think about how protocols could be redesigned to support sleeping nodes without a proxy.

Cutting the Electric Bill for Internet-Scale Systems

Summary

The key idea of this paper is to shift load to data centers with lower energy costs. The authors make two observation that enable the proposed design:

1. Electricity prices vary. The price of electricity varies both in time and by location. For example, prices at night are generally less than during the day and prices for locations closer to generators are less than far away locations.
2. Large distributed systems already incorporate request routing and replication. Most internet services can easily route requests to one of multiple locations.

The savings in energy cost depends on the "energy elasticity" (also known as power proportionality) of clusters. In other words, how much does the energy consumption drop in response to a drop in load. The authors estimate that current servers use about 60% of peak power when idle, but they expect this number to improve.

The authors examine the price variations for energy over time and in various locations. They show that prices often vary by a factor of 2 with a day. They also show that prices are not correlated across different locations thus enabling savings by redirecting load.

Overall, the authors estimate that they can save 2% of energy costs now and that savings increase rapidly with system energy elasticity. In a fully elastic system they expect over 30% cost savings.

Thoughts

This paper presents a neat idea for cost savings, however, as the authors point out it hinges on the energy elasticity of servers. Without improvements in elasticity the savings would be fairly negligible. I suspect that this may be part of the reason companies don't bother to do this right now.

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

Summary

This paper presents a general framework for building different multicast services. They argues that "multicast applications have widely different requirements for reliability." Specifically applications differ along three axis:

1. Ordering requirements. Some applications require a total ordering while others do not.
2. Number of senders. Some applications have one sender while others have many.
3. Choice of sender. In some applications multiple nodes have the data and any one can send.

Given this variation the authors strive to build a general framework that can be extended by the application.

A key aspect of their design is to make receivers responsible for reliable delivery rather than senders as done in TCP. Specifically, each receiver in the multicast group is responsible for detecting loss and requesting retransmission. Loss is detected by a gap in the sequence numbers and by periodically broadcasting the highest sequence number received from each source. When loss is detected a "repair" message is broadcast, any node that has the data can reply and all other potential senders are suppressed when the reply is seen. Similarly, if other nodes need the same data repaired they suppress sending a message if a repair is seen.

The authors implement wb a shared whiteboard system on top of their framework. In wb commands are idempotent so total ordering is not required. Also, any node can forward lost data to any other an other node and any node can be the sender of new data.

Thoughts

The idea of making the receivers responsible for recovery is fairly interesting. However, I am concerned by the amount of broadcasting that goes on. Each repair request and response is multicast to the whole group. This seems to limit the scale of the system. An alternative approach would be to have nodes send unicast repair requests to nearest neighbors.

Scalable Application Layer Multicast

Summary

The goal of this project is to provide a low-overhead multicast service as an overlay. Currently, true multicast is generally not supported at the ISP level, however, it can be approximated by application layer multicast. This works by having end nodes forward packets instead of doing forwarding in the network (e.g. at routers or switches). There are two main goals for application layer multicast:

1. Minimize stress. Stress is the number of times an identical packet is sent over a link.
2. Minimize stretch. Stretch is the path length from the source to a member along the overlay divided by the length of the unicast path.

These two goals are often at odds: minimizing stress may require many forwarders, however, this increases stretch. More generally the paper evaluates application layer multicasts protocols based on:

• Quality of the data delivery path. This consists of the stress and stretch metrics.
• Robustness of the overlay. This quantifies the extent of data delivery disruption that occurs when an end node crashes.
• Control overhead. This is the overhead of the multicast protocol.

The proposed solution is to create a NICE tree over the end nodes which defines the data paths. NICE assigns nodes to different layers in a hierarchy. Each layer consists of a set of clusters of size 3k-1. Each cluster is a set of nearby nodes. The center of each cluster is considered the "leader" and placed at the next layer up. The source node sends data to all nodes within its cluster and to its parent node. At each layer this repeats recursively.

Thoughts

I am not convinced by the evaluation in this paper. The authors show their average link stress during the join phase to range from 1.6 to 2.1. This is significantly more than the "stress" of 1 we would expect from network based multicast, which would seem to limit the use cases of their approach. Also, their evaluation only stresses building the NICE tree by having nodes joining and leaving. It seems crucial to have stress and stretch graphs for actually sending data from a variety of end points.

X-Trace: A Pervasive Network Tracing Framework

X-Trace is a debugging tool for tracing a packet through the network across all layers.

Summary

X-Trace is motivated by the need to understand the movement of packets through the complex set of components that makes up a network. It provides a generic mechanism to trace packet movement at all layers of the network stack.

X-Trace works by piggybacking tracing data on top of data packets. Specifically, packet headers are annotated with a task identifier and tree information. The task identifier uniquely identifies the high-level operation being performed. This can tie together many seemingly independent network requests.

The tree information metadata records causal relationships between operations. The network stack is modified to add "pushDown" and "pushNext" function calls. A push down copies metadata to a lower layer, thus ensuring that the metadata stays on the data path. For example, an HTTP proxy calls push down to copy metadata to each TCP connection. Push next is used to propagate metadata to the next hop in the same layer. For example, an HTTP proxy calls push next for each HTTP request it processes. Using these annotations X-Trace is able to construct a tree of operations.

Thoughts

X-Trace is clearly a very useful tool. My main concern is that it requires modifications to protocol implementations, especially to do causal tracking. As the authors explain, the difficulty of this varies a lot from application to application. I wonder if there is a way for the operating system to automate this through "taint tracking."

NetFPGA: A Tool for Network Research and Education

Summary

The goal of NetFPGA is to provide hardware for easily prototyping new router designs. It allows designs to be implemented in real hardware instead of the alternatives of simulation or creating a software router on a general purpose computer using a framework such as Click. NetFPGA has also been used for education purposes in the networking classes at Stanford. This gives students experience with implementing low level transport and routing protocols.

NetFPGA is a PCI card with an FPGA and 18MB of RAM. The PCI format allows several cards to be connected through the PCI "backplane."

Thoughts

This is a useful idea that can improve the evaluation of new protocols. NetFPGA would however require a significant amount of work to program (in Verilog). Also, a single NetFPGA has only one Ethernet port and fairly limited performance, therefore many cards may have to be used to create a realistic router.

Internet Indirection Infrastructure

This paper describes an overlay network for multicast, anycast and mobility services.

Summary

This paper addresses the issues of supporting multicast/anycast on current networks. The Internet is designed for point-to-point connections so adding true multicast is hard. Current approaches require the sender to know a list of recipients and the recipient locations to be fixed. The proposed design logically /decouples the act of sending from the act of receiving/.

The mechanism is to have receivers register interest in a particular type data. This is done with a "trigger" consisting of a (id, address) pair where the id is an m-bit identifier. When a sender sends a packet with the specified id, the packet is forwarded to all receivers that registered triggers.

To generalize the identifier matching the system forwards packets if

1. The ids have a prefix match of at least k bits and
2. There is no trigger with an id that has a longer prefix.

Mobility is supported by allowing receivers to register a new trigger with a different address. Multicast is supported by having a group of triggers with the same id. Anycast is supported by having a group of servers with triggers that are identical in the k most significant bits. All other bits of the ids are different, thus the matching mechanism will pick the single server with the longest prefix match.

Thoughts

This paper describes a clever way to build in support for multicast, anycast and mobility in an overlay. The core of the idea is quite simple: add a layer of indirection where receivers must register. In some sense this sounds similar to the mobile IP model of having a representative node that forwards packets to one's real location.

A Policy-aware Switching Layer for Data Centers

This paper presents a policy-aware switch design that routes data through a specified set of middle-boxes.

Summary

This paper addresses the problem of inserting middle-boxes such as firewalls, load balancers, etc. into a network. The current approach is to place these boxes in series on the physical path or to modify path weights in the spanning tree to force data through these boxes. This method makes it difficult to provide the following desirable properties:

1. Correctness. Traffic should traverse middle boxes in a specified order.
2. Flexibility. It should be easy to reconfigure the sequence of middle boxes or to add new ones.
3. Efficiency. Traffic should only traverse the required middle boxes.

To achieve these goals the authors propose a policy-aware switching layer (pswitch). The goal of this layer is to

1. Separate policy from reachability. Explicitly dictate which middle boxes traffic should traverse, not by changing network paths.
2. Take middle boxes off the physical network path. Data is explicitly forwarded to middle boxes so they no longer have to be on choke points in the network.

The pswitch will match packets based on the source IP, destination IP, port number and protocol type and then forward them to a specified middle box. Middle boxes can be put in series by next hop forwarding rules e.g. [previous hop, traffic selector]: next hop.

The authors use a formal model to verify the correctness of the proposed deign.

Thoughts

Overall, this sounds like a good solution to a real problem in data centers. One concern is that the pswitch mechanism introduces extra overhead. For example, data must make an additional round trip through each middle box instead of traversing all of them in series.

Development of the Domain Name System

Summary

This paper describes the motivation for and design of the DNS system. Before DNS, naming was done through HOSTS files which were copied from central repositories. This approach lacked scalability and was not consistent with the distributed way in which the Internet was growing. A new system was designed with the following goals:

• Distributed data storage
• No size limits for names
• Interoperability across Internet and other environments
• No specific OS requirements
• Tolerable performance

These goals led to several key design decisions. 1) A hierarchical name space was used to deal with distribution and size requirements. 2) Data was cached at clients and intermediate nodes to improve performance. 3) The system was independent of network topology.

The DNS design uses a tree of name servers to lookup domain names. Organizations are delegated a sub-tree (zone) which they administer. For example, berkeley.edu is free to create any sub-domains deeper in the tree. The lookup process traverses the tree until the leaf node is found. Next, a resource record (RR) which contains an IP address or other data is read form the leaf. Caching is used throughout the tree to reduce load. Each cache entry has an associated time to live (TTL) which dictates how soon it is invalidated.

Thoughts

The design of DNS is very interesting because it is quite simple and yet very effective. Particularly, the authors recognized the importance of eventual consistency and caching. These issues are still being discussed today. Overall, it is impressive that DNS still works and is widely used over 20 years after its creation.

DNS Performance and the Effectiveness of Caching

This paper analyzes DNS performance using traces collected in 2000 at MIT and Korea of client DNS queries.

Summary

The paper explores two key questions:

What is the latency of DNS requests and how often do they fail?
How does varying the TTL and caching sharing impact caching effectiveness?

The authors use data collected over three months at two different sites to answer these questions. The data consists of 60% lookups for A records and between 24% and 31% reverse lookups from addresses to host names. They found that around 20% of queries were not answered and had to be retransmitted. The average number of query packets sent for a successful reply was 1.27.

The median latency was 42ms with 35% of the responses taking less than 10ms. They found that caching NS records substantially reduces lookup latency.

Curiously they found that the hit rate of the cache does not increase substantially with additional clients beyond 10. They explain this by noticing that most DNS queries are for a very small but popular set of addresses. They also notice that increasing the TTL beyond several minutes has very little additional benefit.

Thoughts

This is an interesting study of how DNS works in real life. Particularly the statistics about the number of clients needed to have useful caching is very practical.

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

Summary

Chord addresses the problem of looking up data in a peer-to-peer system. It aims for "simplicity, probably correctness and probable performance."

The key challenges in designing the system are:

• Load balancing: keys must be assigned to nodes evenly
• Decentralization: all nodes are equal
• Scalability: O(log N) lookup performance allowing a large number of nodes
• Availability: nodes can join or leave at any time but keys can still be found

Key Assignment

Chord uses consistent hashing for all keys. This creates an "identifier circle" of all possible keys. Nodes are also assigned an id which is a location on this circle. Each key is assigned to the first node whose identifier is equal to or follows it. This way if a node disappears, its keys are automatically assigned to its successor and similarly when a node is added it takes on part of the successor's keys. This technique ensures a fairly even load across all nodes.

Lookup

Each node in the identifier circle must know its successor. This information is sufficient to do a lookup by checking each node in sequence. However, Chord adds a "finger table" to improve performance and scalability. The finger table contains pointers to nodes 1/2 around the circle, 1/4 of the way, 1/8, etc. Using the difference between the key and the current node id, Chord decides how far to forward the lookup. This results in a O(log N) lookup time.

Joining

When a node joins it first performs a lookup (using any existing node) to determine its predecessor and successor in the circle. It then creates a finger table by starting with the predecessor's table and updating it in the background. Finally, keys are transfered lazily.

Stabilization

Chord uses a stabilization protocol to deal with failures. This consists of keeping successor pointers up to date since this is the minimum requirement for correctness. This is done by having each node, n, periodically asking its successor for the predecessor pointer. If the predecessor is not n then a new node has been added and the successor pointer must be updated. In the process the successor is made aware n so the predecessor pointer can be updated.

Evaluation

The authors plot the lookup cost (path length) versus the number of nodes in the system and show that the path length is about 0.5*log2 N. They also explore the load balance of keys across nodes. They find that in the basic system the balance is not very good however using multiple virtual nodes allows for a better distribution.

Thoughts

The Chord system is widely recognized and used in many subsequent designs (including SEATTLE) . It has the benefit of being fairly simple and backed up by proofs.

One criticism is that it is unclear how often a fully peer-to-peer system is really necessary. Systems such as Google BigTable operate with replicated master nodes instead of having each storage node be a peer. In this case, the scalability of the system depends on being able to scale the master nodes.

Looking Up Data in P2P Systems

Summary

This paper outlines the key challenges in distributed, P2P data lookup and compares current solutions.

To motivate the work, this paper lists three reasons P2P systems are attractive:

1. Low barriers to starting and growing the system
2. Allows pooling of resources
3. Robustness and fault-tolerance

Finding data is the central problem in P2P systems because nodes can join, leave, or crash at any time. The lookup mechanism must be both scalable and fault-tolerant. So simple solution such as a centralized database are not applicable because they are not scalable and create single point of failure. Other approaches include broadcasting requests to all nodes as done in the Gnutella and preforming lookups hierarchically as done in DNS. Unfortunately, the broadcast method suffers from a lack of scalability and the hierarchical approach is not robust against failures of top level nodes. DHTs are a method to perform lookups with both both scalability and fault-tolderance.

The paper describes three DHT algorithms in detail: Coord, Pastry and CAN. In general they all have three features:

1. Assigning keys to nodes in a load-balanced way
2. Forwarding a lookup to a closer node as defined by a distance function
3. Building routing tables adaptively

For example, in Coord keys are assigned based on proximity in a ring, forwarding happens using a skiplist of pointers to nodes at specific distances in the ring, and routing tables are updated by periodically checking liveness and updating broken entries from neighbors.

There are several key differences between the DHT algorithms. For example, the chosen distance function is symmetric (d(x, y) = d (y, x)) then a stabilization protocol is not necessary

Thoughts

This paper takes a big picture view of all the work on DHTs and provides concise summaries. The key contribution is the comparison the the different algorithms. I thought the distance function example was quite neat.

Active network vision and reality: lessons from a capsule-based system

Summary

This paper describes active networks and some of the problems they face. The idea of active networks is to allow user-extensible network functionality. In other words users can run custom programs in the network. This has two potential benefits:

1. Enables a range of new applications
2. Allows services to be location independent

The main problems are performance and security. The authors describe the ANTS system which addresses these concerns.

ANTS allows users to send executable capsules to active nodes in the network. These capsules contain Java code of a limited size which is executed on a special JVM. This JVM contains security restrictions to prevent the code from damaging the underlying system.

The authors also evaluate the performance of ANTS capsules. They find them to be about twice as slow as a C implementation.

Finally, the authors argue that the main benefit of active networks is not a "killer app" but rather the flexibility to add functionality over time.

Thoughts

It is not entirely clear when active networks are better than a separate service running on a networked server. While the idea of decoupling services from a specific location sounds tantalizing, it would be very hard to implement in practice. In a way services such as Amazon EC2 have taken over many of the use cases Active Networks target. For example, services such as video trans-coding can be run on rented, networked, hardware in the EC2 cloud.

Resilient Overlay Networks

Summary

The goal of this paper is to use an overlay network to increase reliability of transmission.

The authors observe that connectivity problems are most often due to BGP faults and misconfigurations rather than link failures. So, it is likely that different nodes are still reachable and they may be able to connect to the final destination. RON takes advantage of this fact to route packets through other reachable nodes to the final destination.

For all nodes in the overlay network RON keeps track of latency, loss rate and throughput obtained through periodic probes. Client may specify their own metrics to use in place of the defaults. RON uses link-state dissemination to buildup forwarding tables. Path selection is done based on the metrics collected about each virtual link.

The authors find that RON improves the packet loss rate by about 5%. It also improved latency for packets that would normally traverse slow links.

Thoughts

RON is a neat idea but it seems like a "hack" to fix a failure of the underlying routing protocols. Maybe some of this functionality should be built into router rather than implemented as an overlay.

On Inferring Autonomous System Relationships in the Internet

The goal of this work is to discover the types of relationships between ASes using publicly observable route announcements. The authors observe BGP announcements from the Route Views router and apply heuristics to classify relationships into provider, peer, and sibling.

The key idea is to use the "Valley Free" property to classify relationships. This property states that:

• A provider-to-customer edge can be followed by only provider-to-customer and sibling-to-sibling edges.
• A peer-to-peer edge can be followed by only provider-to-customer or sibling-to-sibling edges.

These rules encode the economics of network relationships. For example, it does not make sense to provide transit for a peer to another peer because that does not benefit one's customers. The authors also use the size of an AS to estimate its status. Larger ASes are assumed to have a higher degree.

Using these heuristics the authors find that most relationships are provider-to-customer with a small percentage of peering and siblings.

On Power-Law Relationships of the Internet Topology

This paper describes Internet topology and growth using power laws. The authors find that a surprising number of Internet attributes grow as a power function. They study traces of the Internet over a year in 1998.

The key findings are:

1. The out degree of a node is proportional to the rank of that node to the power of a constant. This means that the out degrees of nodes on the internet follow a "power law" distribution
2. The frequency of an out degree is proportional to the out degree of the power of a constant. The authors find the constant to be negative implying that there are a small number of nodes with a large out degree and a larger number of nodes with a small out degree.
3. The total number of nodes within h hops is proportional to the number of hops to the power of a constant. In other words the number of reachable nodes grows as a power function of the number of hops.
4. The eigenvalues of a graph are proportional to the order to the power of a constant.

Overall the authors explain these surprisingly regular relationships by stating that changes propagate up through the network. In other words adding nodes at the bottom forces additional connectivity at the top.

The authors suggest several applications of this work including tuning protocol performance and extrapolating Internet growth.

It would be interesting to see how well these laws extrapolate; are they still applicable today?

White Space Networking with Wi-Fi like Connectivity

Thoughts

This paper addresses the problem of creating wireless access points operating in the "white spaces" of the UHF band. The authors first identify the key challenges of using white spaces:

1. Spatial variation in spectrum availability - in different areas there will be different channels that are unused and thus available for wireless devices.
2. Spectrum fragmentation - TV channels and microphones get priority in the UHF band so the spectrum is split up by the existing users.
3. Temporal variations - Wireless microphones can turn on and off at any time. The wireless access point cannot cause any interference.

The proposed design consists of three parts: spectrum assignment, AP discovery and disconnection. The spectrum assignment algorithm must choose which of the available channels to use. It considers information from clients in order to detect interference both at the sender and the receiver. A bit vector of available channels and a vector of airtime utilization is generated by each node. The access point uses this information the choose the best available channel.

Access point discovery is performed using the SIFT algorithm which allows "clients to discover APs without tuning into all possible channel combinations." This allows fast discovery and reconnection.

Finally, when the access point or a client discovers a new user of the spectrum they broadcast this information on a special backup channel. The access point periodically scans the backup channel and the client switches to it when packets are not received. The backup channel is used to choose a new channel and have all clients switch to it.

The authors evaluate their system and show that it quickly detects access points and effectively disconnects when a primary user appears.

Interactive WiFi Connectivity For Moving Vehicles

Summary

The key idea of this paper is to exploit opportunistic reception of packets by all base stations within range of the source to improve connectivity of WiFi for moving vehicles. The paper motivates this work by noting that currently 802.11b connections can only connect to one base station at a time. The authors compare the performance and connectivity of several hand off mechanisms:

• RSSI - picks the BS with highest signal strength
• BRR - picks the BS with the highest beacon reception ratio
• Sticky - keeps the current BS until it is absent for some time
• History - picks the historically best BS at this location
• BestBS - picks the single best BS using an ideal model
• AllBSes - opportunistically uses all BSes in the vicinity

They find that AllBSes performs best by about 25%, RSSI, BRR, and History all perform similarly. Sticky performs worst. Motivated by the results of this study the authors design a system that uses all BSes in the area to improve connectivity.

The design uses beacons to designate an anchor or primary base station and all other base stations are designated as auxiliary. When the source broadcasts a packet, if the anchor hears it then it broadcasts an ACK. All the auxiliary nodes listen for packets. If an auxiliary node hears a packet but does not hear an ACK shortly after, it probabilistically relays the overheard packet to the anchor. Also, when switching anchors the new anchor will "salvage" unsent packets from the old anchor.

The authors show that their proposed algorithm significantly outperforms BRR in all cases and approaches the ideal performance.

Thoughts

The idea proposed in this paper seems very similar to ExOR idea of exploiting overhearing only applied to a set of access points with a "back-plane" instead of a full mesh network.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

Summary

ExOR is a protocol for multi-hop wireless networks where data is sent and opportunistically heard by intermediate nodes. The routing decisions are made based on which nodes happen to hear the packet rather than a preconceived route.

Specifically, the sender creates a prioritized list of intermediate receivers which is sent with the data. The prioritization is done by computing the ETX metric from each node to the destination. A schedule is setup such that each node in the prioritized list has a chance to broadcast its received data. All nodes listen to broadcasts and if they overhear some packets being sent they avoid re-sending those packets. In the end most of the packets (~90%) reach the final destination. The remaining 10% can be sent by traditional routing methods.

The authors evaluate the system using the RoofNet deployment of 38 nodes distributed over six square kilometers in Cambridge, Massachusetts. They show that they achieve two to four times the throughput of traditional TCP.

Thoughts

Overall this is a cleaver way to use the broadcast nature of wireless communication to improve throughput. It would be interesting to look at forms of forward error correction to encode the 10% of the data that is lost in the process.

XORs in The Air: Practical Wireless Network Coding

Summary

The key idea of this paper is to take advantage of the broadcast nature of wireless and coding to reduce the number of packets that must be sent to transmit data.

The proposed design, COPE, uses three main techniques:

1. Opportunistic learning. COPE overhears packets destined for other nodes and stores them for some time
2. Opportunistic coding. COPE tries to send data encoded in such a way that multiple receivers can extract the packets they need using the data they already have.
3. Learning neighbor state. COPE guesses what packets neighbors may have using the ETX metric.

COPE works by basically "adding" together packets such that multiple recipients can "subtract" the data they already have and obtain a new piece of data. In practice this is accomplished using XOR. This technique is particularly useful when multiple nodes are exchanging data.

The authors find a 3-4x performance improvement when using COPE for UDP flows.

Thoughts

This is a clever use of the broadcast nature of wireless to improve performance. I am actually quite surprised it works as well as it does.

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

Summary

This paper presents a new metric, expected transmission count (ETX), for choosing high-throughput paths in a multi-hop wireless network. This metric takes into account link loss rates, asymmetry in loss ratios and interference among the successive links in a path. The authors evaluate this metric in a real test environment and compare it to minimum hop count.

The authors first analyze the shortcomings of the minimum hop-count metric. They find that minimum hop count performs well "whenever the shortest route is also the fastest route." However, minimum hop-count does not consider loss rates which the authors find to vary widely in their test environment. Also, minimum hop-count does not have a way to choose among multiple paths of the same length.

ETX is designed to address these issues. It works by predicting the number of transmissions required to deliver data. In other words, it computes 1 / (df X dr) where df is the probability that the data packet makes it across the link and dr is the probability the ACK is successfully returned. df and dr are computed empirically by occasionally sending probe packets and counting the delivery rate.

The authors implement ETX in the DSDV routing algorithm and compare it to the original DSDV using minimum hop-count. They find that ETX provides a throughput improvement in all cases but it is less significant when large packets are used because the small probe packets do not accurately model the transmission probability for large packets.

Thoughts

ETX is clearly a better metric than minimum hop when dealing with lossy links. It could be improved by estimating actual throughput, as in RoofNet, not just transmission count. This would account for different transmission rates. Finally, it seems that the link loss probabilities could be computed/updated from the data actually being sent not just the probe packets. Overall, this paper presents a simple and clearly useful idea.

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

Summary

This paper compares four multi-hop routing protocols, DSDV, TORA, DSR and AODV, using a network simulator. The simulation is done in a modified ns-2 network simulator with an 802.11 MAC implementation and a realistic radio signal attenuation model.

The authors briefly describe each of the protocols being considered:

1. DSDV: Each node maintains a table with the next hop for all destinations. Routing updates are broadcast.
2. TORA: Routes discovered on demand. Quickly establishing routes is preferred over choosing the shortest path.
3. DSR: The source decides the full route of each packet. Routes are discovered through flooding "Route Request" packets.
4. AODV: Combines route request and maintenance from DSR with hop-by-hop routing from DSDV.

In the evaluation the authors simulated 50 nodes over an area of 1.5k x 300m. The nodes moved at different rates and in different patters. The measured metrics were packet delivery ratio, routing overhead and path optimality.

Packet delivery rates were good (>95%) for DSR and AODV at all rates of mobility. However, DSDV had a poor delivery ratios when nodes moved quickly and TORA could not handle a large number of sources.

The routing overhead also changed significantly with the movement of nodes. In both DSR and AODV the routing overhead was much higher at high mobility. DSDV overhead remained fairly constant and TORA had the constantly very high overhead.

Thoughts

This seems like a thorough and useful analysis of routing protocols. However, the protocols being compared are fairly old. I am curious if any of these are still used today or if they have been superseded. Also, it is not clear how well this simulation would translate to real-world performance.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes the design of a wireless mesh network. The key goal of the design is ease of deployment. So nodes are in unplanned locations and they use omni-directional antennas to avoid having to configure antenna placement. This necessitates a multi-hop routing and path optimization to provide adequate throughput.

The network is auto-configuring and has only some nodes that act as external gateways to the Internet. It uses an internal addressing system based on the MAC address of the Ethernet cards to route within the mesh. At the gateways, NAT is used to translate internal addresses to external ones. This means that connections are tied to a specific external gateway and cannot shift if network conditions change. However, new connections always use the "optimal" gateway.

To route within the wireless mesh each node uses Dijkstra's algorithm to choose the best path. The cost of each link is estimated using an "estimated transmission time" metric. This takes into consideration the throughput bit-rate of the link and the probability of delivery at that bit-rate. For example, "a single-hop route with 40% loss can deliver more data than a two-hop route with perfect links." By considering these trade-offs the node is able to maximize its throughput.

The authors deploy a system of 33 nodes and 4 gateways on rooftops in Cambridge Massachusetts by asking volunteers to install the nodes. They obtain an average throughput of 627 kbits/s with links having a median loss rate of 20%. The throughput is mostly dependent on the number of hops with just 89 kbit/s at 5 hops.

Modeling Wireless Links for Transport Protocols

Summary

This paper details the key features of models of wireless links. The goal is to help address the issue of how to modify TCP and link-layer protocols to improve performance over wireless links.

This paper points out the key problems in current wireless models: unrealistic assumptions, small parameter space, overly realistic and lack reproducibility. Next, they list characteristics of wireless links and how to model them:

1. Error Losses: represent packet loss after link-layer retransmission attempts. Model by dropping packets with some probability.
2. Delay Variation: represents delay due to link-layer recovery, etc. Model by randomly suspending transmission.
3. Packet Reordering: caused by retransmission attempts. Model by randomly swapping packets or delaying single packets.
4. Resource Allocation: some wireless links temporarily allocate bandwidth to streams. Model by introducing delay when a packet arrives to a queue that has been empty for longer than the channel holding time.
5. Bandwidth Variation: may occur on CDMA and UMTS links. Model by occasionally reducing bandwidth of the link.
6. Bandwidth Asymmetry: wireless links typically have asymmetric bandwidths.
   

Finally the paper makes some recommendations. They suggest that bit errors should be handled at the link layer using FEC and retransmissions. However, explicit corruption notification can be used to inform TCP when transmission fails after link-layer recovery attempts. TCP should be more resilient to reordering which would give link-layer protocols more flexibility in recovery. Finally, where possible, link layer protocols should reduce delay variation but delay tolerant TCP may be useful as well.

Thoughts

This paper seemed to state fairly obvious characteristics of wireless links and modeling techniques. The key contribution seems to be in pulling all of these characteristics together and stating where previous work has failed to do so.

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

Summary

This paper explores different mechanisms to deal with loss in wireless networks. Specifically, it compares the performance of three classes of solutions:

1. End-to-end protocols
2. Link-layer protocols
3. Split-connection protocols

End-to-end protocols include standard TCP Reno and modifications. The basic problem is that standard TCP uses packet loss as a signal of congestion, however, in wireless networks packet losses can occur due to noise or interference, treating these losses as congestion degrades performance. The authors find that basic TCP Reno achieves a throughput of 50% of the maximum with a 2.3% packet loss rate on the wireless link. Other variations of TCP Reno include partial acknowledgments (new Reno) which performs better because it can fill large holes, resending one packet for each additional ACK (after 3 duplicates). A different approach is to use explicit loss notification, this allows the sender to maintain the congestion window size while retransmitting lost packets. Both of these modifications perform similarly.

The second class of solutions is link-layer protocols. These solutions perform re-transmissions at the link layer and attempt to hide the lossy link from TCP. The problem with this approach is that re-transmitting at the link-layer can lead to out of order packets received at the destination. This will cause duplicate ACKs which will activate TCP fast retransmit unnecessarily. Several solutions are explored, all involve "TCP awareness" or suppressing duplicate ACKs for packets that have already been retransmitted. The authors find that this solution is best, out performing the end-to-end solutions.

The final class of solutions is split-connection protocols. These isolate TCP from the wireless link by using a different connection to make the wireless hop. If the protocol used for the wireless hop is optimized to handle losses then the overall throughput is quite good. However, the authors argue that this approach breaks the end-to-end principle and is not necessary for good performance.

Thoughts

I am curious to know what is actually done in 802.11b/g/n networks. The link-layer recovery seems like a fairly clear solution but admittedly requires duplicating recovery functionality.

MACAW: A Media Access Protocol for Wireless LAN's

Summary

This paper analyzes the existing MACA wireless protocol and proposes changes that improve fairness and performance. The key problem they address is how to handle congestion fairly and efficiently. First the authors make several observations about congestion:

1. Contention is at the receiver not the sender
2. Congestion is location dependent
3. MACs should propagate congestion information explicitly
4. MACs should propagate synchronization information about contention periods

 The first two observations motivate using a RTS/CTS protocol instead of a carrier-sense protocol. With just carrier sensing, senders can potentially interfere with other senders that are out of range ("hidden terminal" scenario). Similarly, carrier sensing may prevent transmission even when the receivers are out of range ("exposed terminal" scenario). The solution is to use RTS/CTS, where each sender first requests to send and all stations hearing the RTS delay transmission for the length of a reply. If the receiver sends a CTS, then the sender can send and all stations hearing the CTS must wait. The key is that delaying transmission is now tied to who can hear (and thus interfere with) the messages.

This paper proposes several optimizations to the RTS/CTS protocol. Namely, using additive decrease and multiplicative increase of the backoff counter which is used to determine how quickly to re-try transmission. The paper also proposes a fairness optimization: keeping per-stream backoff counters and ordering data using "shortest wait time." They also propose using link-layer ACKs to allow faster retransmissions and DS messages to avoid collisions at the senders, who must now also receive ACKs.

Thoughts

There are a lot of similarities between the techniques used in this paper, at the MAC level, and previous papers we read that dealt with TCP/IP.  For example, the backoff counter operates much like the inverse of the congestion window in TCP/IP, dictating how much to wait before sending rather than the sending rate. Similarly, keeping per-stream queues and using shortest wait-time ordering has been used in routers (Analysis and Simulation of a Fair Queueing Algorithm). Finally, sending ACKs at the link layer is similar to ACKs at the transport layer. All of these similarities make me wonder if it is good that the same type of solutions apply at different layers of if there should be a single mechanism that solve these problems at all layers.

Finally, I am curious if any of this is used in today's wireless networks. I know my home router has RTS/CTS settings but they are turned off by default. Is this not the case for larger enterprise networks?

Understanding TCP Incast Throughput Collapse in Datacenter Networks

Thoughts

This paper explores the incast problem and evaluates proposed solutions.

The authors first reproduce the incast problem on several different clusters. They verify that the problem occurs repeatably in different environments. Next, they implement the solutions proposed in "Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication." They evaluate four possible modifications:

1. Decreasing minimum RTO
2. Randomizing minimum RTO
3. Setting a smaller multiplier for RTO exponential back-off
4. Using a randomized multiplier for RTO exponential back-off

The authors find that adjusting the RTO exponential back-off was unhelpful because there were only a small number of exponential back-offs during the transfer. Surprisingly, they found that randomizing the minimum RTO was also unhelpful. They attempt to explain this by stating that router queues are a fixed resource so even if the retransmissions are randomized, the packet loss is synchronized by the shared router queues. The only approach that was helpful was decreasing the minimum RTO. This works well for a limited number of senders.

Finally, the authors propose a model for throughput given the number of senders. The model works well for 200ms timers but fails to predict throughput at smaller timer values.

Thoughts

I like the idea of creating a model to explain the odd behavior of TCP during incast. However, some of the explanations in the paper were not completely convincing. For example, I am not convinced by the explanation of why randomizing the RTO does not help.

Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

Summary

This paper describes the "TCP incast" problem and proposes several possible solutions.

Incast occurs when a program issues "barrier-synchronized requests" to multiple servers. For example, parallel reads in a distributed FS. The servers all respond at roughly the same time so a large volume of traffic is sent. This causes congestion and large packet loss. Next, TCP goes into retransmission and waits for the RTO of approximately 200ms. Due to this slow retransmission, the link gets very low utilization and the clients cannot progress.

This problem may repeat due to syntonization of the RTO timers, so multiple servers can attempt to retransmit at the same time again causing packet loss and slow retransmission. This issues is particularly acute in data centers because normal transmission latencies are very low, much less than the default RTO of 200ms.

To solve this problem the authors propose to reduce the RTO timer and make it fine grained. The reduced RTO value will increase throughput by waiting for less time after packet loss. However, the authors find that this does not completely solve the problem for large (>1024) sets of servers. The issue is that the timers become synchronized. To avoid this the authors propose randomizing the RTO value.

Thoughts

This paper provides an interesting look at an unexpected problem. I am surprised that the RTO value does not automatically adjust below 200ms based on round trip latency.

VL2: A Scalable and Flexible Data Center Network

Summary

This paper presents a layer 2 network design for large data centers with a focus on "agility." The paper identifies 3 problems in today's data center networks:

1. Insufficient capacity between servers
2. Lack of isolation between services
3. Poor support for VM migration

To solve these problems the authors propose building a virtual layer 2 network connecting all of the servers being used for a particular service. This network would be structured in a Clos topology and use OSPF routing algorithms to make use of multiple routes thus improving capacity. Isolation can be provided by adjusting the bandwidth available for each virtual network. Finally, VMs can be easily migrated because IP addresses are used only as names with no topological significance.

To route packets, VL2 introduces an additional location-specific IP (LA) much like the hierarchical MAC in PortLand. VL2 also uses a proxy to handle ARP requests that are looked up in a centralized directory service rather than broadcasted to all switches.

Thoughts

This paper includes an interesting analysis of data center network activity showing that it is fairly unpredictable and also split between lots of small flows and a few large ones.

The evaluation was also quite convincing. The authors built a real system and used it to evaluate the system when performing an all-to-all shuffle. They show that the system has 94% efficiency with high fairness.

PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric

Summary

This paper describes a network architecture for large data centers running virtual machines. The key requirements are:

1. Support for VM migration
2. No administrator configuration
3. Efficient communication along any physical path
4. No forwarding loops
5. Rapid failure detection

The key design feature of this paper is to use hierarchical MAC addresses and a centralized fabric manager with soft-state. The hierarchical MAC addresses correspond to physical topology and thus simplify routing. However, manual configuration can be avoided by using a Location Discovery Protocol.

ARP requests are handled by the fabric manager which has a global view of IPs and MAC addresses. Migrating a VM just involves changing an entry in the fabric manager's table to assign an IP to a different machine.

They key difference between this approach and SEATTLE is the use of hierarchical addressing to simplify routing and using a fabric manager to provide fast and reliable ARP lookups.

Thoughts

It was not clear how well the LDP protocol works. The authors state that switch positions may be set manually or automatically, but the trade offs where not made clear.

I also would have liked to see a comparison between SEATTLE and PortLand in the evaluation.

Detailed Diagnosis in Enterprise Networks

Summary

This paper describes and automated system for determining potential causes of errors in machines and applications in a network. The authors propose building a dependency graph of which components may impact one another. This is done using templates such as "a machine depends on its processes and its configuration" and "an application process depends on its configurations, its NbrSet, its host machine and the configuration of the machine." Using these heuristics a graph of dependent components is built. When a problem is encountered the system searches for the potential cause. To do this the authors assume that correlation implies causation. They calculate the probability of the erroneous outcome given the state of each of its dependencies. This is done using historical data collected during normal operation. This probability determines the weight, w, of the corresponding edge in the dependency graph, implying that this edge has a potential impact of w. Finally, the potential causes are ranked based on the total weight of the path from the cause to the error combined with a measure of the abnormality of each component in that path. Components that are highly impacting more abnormal components will have a higher score.

Thoughts

This is a neat high-level way to diagnose problems, but I am surprised that it works as well as they claim. I am concerned that this approach may be limited to a small set of problems. Also, using correlation to imply causation will not work well in all cases even if the authors found it to be accurate for a set of problems. Specifically, this can be a problem when interactions become more complex and an unknown factor causes both correlated outcomes.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises

Summary

This paper describes a network architecture that combines the scalability of IP networks with the plug-and-play functionality of ethernet networks. The key idea is to extend ethernet routing to prevent broadcasts and optimize routing. Specifically, the paper proposes a DHT based lookup mechanism. When a node first joins the network it is discovered by the switch to which it is connected. This switch is responsible to adding the node's MAC to the directory. It does this by applying a consistent hash function to the MAC address and determining which switch is responsible for that hash value. The (MAC, location) pair is then stored by the designated switch. When a different host sends a packet, a lookup is preformed in the same manner and the packet is subsequently routed along the shortest path to the destination.

The key aspect of this algorithm is that the directory service eliminates the need for broadcasts, thus making the solution scalable. The network architecture also separates naming from locations, unlike TCP where nodes in a subnet must have a common prefix. This feature allows plug-and-play functionality where nodes do not have to be configured.

Thoughts

Overall, I like the idea; it would certainly be nice to have a large network with no configuration.

Part of the design requires caching directory entries, however, it is not clear how these caches would be invalidated when nodes disconnect from the system of failures occur. Also, I am concerned about the security of the system, it seems that nothing prevents nodes from spoofing MAC addresses or pretending to be switches.

Random Early Detection Gateways for Congestion Avoidance

Summary

This paper describes a method of notifying senders of upcoming congestion before it occurs. The method has the key benefits of being compatible with TCP and not requiring all gateways to use the same congestion control mechanism. This makes it a pragmatic choice, requiring fewer changes than "Congestion Control for High Bandwidth-Delay Product Networks."

The RED algorithm uses the average queue size to detect upcoming congestion. If the queue size is greater than a minimum threshold, packets form each connection may be marked with a congestion bit with some probability. This probability is proportional to he connection's share of the bandwidth at the gateway, thus the RED algorithm addresses both congestion and fairness.

Traditionally, TCP congestion control waits until the queue is full and then drops all packets. This has two negative consequences: dropped packets must be resent and all connections with dropped packets must slowly ramp up again. The RED algorithm addresses these issues by preemptively marking some connections as congested.

Overall, RED helps prevent congestion and keep delay low while being easy to implement on top of TCP.

Thoughts

RED still uses a binary signal for congestion in the same way as traditional TCP congestion control. It is less precise than the algorithm presented in "Congestion Control for High Bandwidth-Delay Product Networks" which allows routers to explicitly control the sender's congestion window. However, RED seems much easier to implement since it can work with TCP and current routers. It would be interesting to see how these two algorithms compare in efficiency and fairness.

Congestion Control for High Bandwidth-Delay Product Networks

Summary

This paper presents a new protocol that explicitly tracks the degree of congestion in the network and reacts accordingly. The authors observe that regardless of queuing scheme, TCP becomes oscillatory and prone to instability when facing high delay-bandwith products. Moreover, with current high bandwidth links, TCP "might waste thousands of RTTs ramping up to full utilization following a burst of congestion." The proposed solution is to have routers inform senders about the degree of congestion at the bottleneck.

The protocol adds an additional congestion header containing the current cwnd and rtt values on all outgoing packets. Routers along the path can set a feedback parameter that instructs the sender to change the cwnd size. Each router in the path can override previous feedback with a stricter requirement thus the bottleneck link will dictate the changes. Finally, the receiver must forward this congestion header in the ACK.

The specific feedback values are computed in two steps. First, the "efficiency controller" computes the window size that would use all available link bandwidth. Next, the "fairness controller" allocates this window to individual flows to preserve fairness. This is done using the Additive Increase Multiplicative Decrease algorithm.

The authors evaluate this protocol through a theoretical stability analysis and a simulation based empirical analysis. The results show that XCP significantly out performs TCP in both high bandwidth and high delay environments.

Thoughts

This paper presents a very precise solution for the congestion problem, relying on explicit signals rather than implicit packet drops. This sounds like a great idea that should be put to use. It also solves the problem in wireless networks of determining if packets were dropped due to congestion or interference.

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

Summary

The key idea of this paper is to implement a fair queueing algorithm with low implementation complexity and resource requirements.

In core-stateless fair queueing the edge routers mark flows and compute per-flow estimates of arrival rates. Next, the core routers compute the fair-share rate based on the number of incoming flows. If a flow has a rate exceeding its fair-share, packets are dropped. This is efficient because there are a lot more edge router than core routers so the complex work of estimating rates and annotating flows is spread out.

Thoughts

This is a clever idea to spread out the work of fair queueing across lots of routers. The obvious limitation is that the edge routers must be trusted to give accurate estimates. It is also unclear if this approach is necessary given the available processing power in modern routers.

Analysis and Simulation of a Fair Queueing Algorithm

Summary

This paper presents an algorithm that emulates bit-by-bit round robin to ensure fairness for multiple flows in the case of congestion. The authors observe that the standard first-come-first-serve algorithms have a number of problems that make them "unfair." For example, a "fire hose" sender that ignores congestion signals (e.g. dropped packets) can get a disproportionate fraction of the bandwidth.

There two main design requirements the authors follow:

1. Fairness - ill-behaved senders get no more than their fair share of bandwidth
2. Delay control - ability to control delay independent of bandwidth

The authors propose a new fair queueing algorithm. They first decide to do allocation based on conversations, e.g. source-destination pairs. To ensure fairness the algorithm emulates bit-by-bit round robin of packets from each conversation. To implement this they send packets by earliest finishing time.

Thoughts

This paper presents a good idea for improving fairness in networks. I wonder why this technique is not currently widely used?

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

This paper presents an analytical analysis of congestion avoidance algorithms and proposes an "optimal" algorithm.

The paper assumes that network throughput typically follows the curve shown in the figure on the right. In other words, throughput increases quickly with load until a point when the system is nearly saturated (the knee) after which the increase in throughput is slow and soon afterwards the throughput falls dramatically (the cliff) due to packet loss. Using this model, the authors argue that the optimal algorithm will keep the system at "the knee" to avoid congestion rather than using a back-off algorithm to control congestion after it occurs.

The authors evaluate algorithms on efficiency, fairness, distributedness and convergence. Efficiency refers to how close to the load is to the knee with the assumption that the knee is the optimal operating point. Fairness means that users bottle-necked on the same resource should have an equal share of it. Distributedness means that there is no central control with full system knowledge. Finally, convergence refers to the rate of reaching equilibrium (the knee) and the size of oscillations about the equilibrium point.

Using these criteria the authors determine the key traits of an optimal algorithm. Specifically, one should increase transmission rate additively but decrease it multiplicatively when congestion occurs.

I am not fully convinced that the throughput vs load curve is always of the shape that the authors assume. That being said the mathematical analysis of congestion is very valuable and suggests that currently used policies are probably quite good.

Congestion Avoidance and Control

Summary

This paper describes the key algorithms used to control data transmission and limit congestion in the Internet. The following algorithms are described in detail:

1. Slow-start
2. Round-trip timing
3. Exponential back-off
4. Window sizing

When transmitting data it is key to send at the rate of the slowest link in the path. This is necessary to avoid losses due to congestion. The rate of the slowest link can be approximated by the spacing (delay) between the returning ACKs, thus ACKs can be used to trigger sending the next packet. The problem is how to start this system, before data is sent there are no acknowledgments. This paper proposes the slow-start algorithm which creates a congestion window that is increased by one for each ACK received. The result is an exponential growth in the number of packets transmitted, until data is lost.

The next improvement concerns round-trip timing. It is important to have an accurate estimate of the round-trip time because the sender must know when to assume a packet has been lost, in other words, how long to wait for an acknowledgment before re-transmitting. The proposed improvement takes into account the fact that round-trip time variance increases with load. This avoids "the network equivalent of pouring gasoline on a fire" by preventing spurious retransmissions during times of heavy network load.

Finally, the paper describes how to avoid congestion. Specifically, it suggests that packet loss is a good indicator of congestion, since it is often caused by overflowing buffers in the path. So when packet loss is encountered the end points should exponentially decrease the rate of sending data. Specifically, the congestion window size is cut in half whenever a timeout occurs.

Thoughts

This paper very clearly explains the causes of network congestion and proposes simple and very well described techniques for dealing with it. Overall, I really enjoyed reading this paper.

I am concerned about the use of packet loss as a signal of congestion. Especially in wireless networks this seems like a bad idea. If a packet is lost due to wireless "noise" it is unclear that sending slower will have any benefit, in fact it may even make sense to send duplicate data faster to improve the chances of it reaching then receiver.

Understanding BGP Misconfiguration

This paper analyzes the prevalence of BGP misconfigurations and their causes. Specifically the authors focus on two types of misconfigruations:

1. Origin Misconfiguration. These occur when routes are injected accidentally into the BGP tables. Specifically this includes hijacking addresses and propagating private prefixes.

2. Export Misconfiguration. These occur when a route is exported in violation of policy.

The authors use a BGP listener (RouteViews) to view updates for 19 ASes. They identify origin misconfigurations by looking for updates that are short lived, lasting less than 1 day. To verify this classification they email the network administrators. For export misconfigurations the authors inferred relationships between ASes using "Gao's algorithm" and tested for violations to standard policies.

The findings showed that "at least 72% of new routes seen by a router during the day are a result of misconfiguration." However, these misconfigurations only lead to disruptions in connectivity 13% of the time. 80% of these incidents are corrected within less than an hour.

Interdomain Internet Routing

Summary

This paper describes the mechanism, policy and economics of Internet routing. The Internet uses topological addressing, so each route corresponds to some address prefix (e.g. 18.31.*). The key mechanisms and policies involve deciding how to route to addresses outside of one's network.

There are two types of agreements between ISPs: transit and peering. In transit agreements an ISP (or individual) will pay for access to a set of routes. In contrast, peering agreements are reciprocal, allowing traffic to from two networks to be exchanged freely. ISPs typically have peers, transit providers and transit customers.

The BGP protocol is the mechanism used to advertise routes allowing routers to build routing tables. To maximize profits, ISPs want to advertise routes to all customers, but not routes through peers (since no money is made from transmitting peer traffic) or routes through transit providers (since these cost money). Similarly, when importing routes ISPs prefer routes directly to customers (these earn money), followed by routes through peers (there are free), and finally routes through transit providers (these cost money). All of these policies are implemented automatically in the routers through prioritizing and filtering.

Unfortunately, the BGP protocol is not secure because it does not verify advertised routes. This allows malicious users and misconfiguration to cause traffic to be erroneously routed. For example, YouTube traffic was mistakenly routed to a "blackhole" in Pakistan.

Thoughts

At first glance, I am very surprised that this complex system with so many conflicting interests manages to (mostly) route traffic from anywhere to anywhere.

I am also curious about traffic ratios in peering arrangements. There seems to be an implicit assumption that the sender should pay for the traffic when both parties are interested in the connection.

Finally, as pointed out in the paper, the lack of security is alarming. Does one have to be an ISP to broadcast BGP advertisements or could any (small) customer potentially broadcast erroneous routes?

The Design Philosophy of the DARPA Internet Protocols

Summary

This paper describes the design goals and origin of current Internet protocols. The DARPA Internet originated as a way to interconnect separate networks, specifically packet radio and the ARPANET. Many of the original design decisions were pragmatic with the goal of leveraging as much existing technology as possible. For example, packet switching was used because it was already in use in existing networks. Gateways were the key new element that allowed multiple, separately administered, networks to communicate.

Next, the paper lists secondary design goals in order of priority:

1. Survivability
2. Multiple communication types
3. Variety of networks
4. Distributed management
5. Cost effective
6. Easy host attachment
7. Accountable resources
   

The top goals, namely survivability and support of multiple types of communication, heavily influenced the design and are still visible today. Survivability was key in a military setting to allow data to flow even if some links were cut. Similarly, multiple communication types were important because different applications had different requirements. For example, telephony requires low-latency but can tolerate loss while file transfer can tolerate delay but needs high throughput. These considerations led to the creation of both TCP and IP. TCP provided reliable communication while IP was a basic "datagram" protocol that could be built upon.

Thoughts

It is very interesting to see how the Internet evolved and how key decisions made over twenty years ago have a huge effect on how the Internet works today. While clearly many requirements have changed, for example, we now don't trust all nodes / networks, I am actually surprised how forward-looking the original design was. I was particularity impressed, that the original design anticipated the differing requirements of many types of communication and that the overall design was scalable.

End-to-End Arguments in System Design

Summary

This paper argues that providing extra functionality or strong guarantees in the communication system is redundant because applications must still re-implement this functionality at higher levels.

The authors provide a motivating example of a simple file transfer application. The application may fail for a number of reasons including disk errors, crashes, and errors in delivery. The argument is that because of this large set of errors, the application must implement a check for accurate delivery whether or not the communication system does a similar check at a lower level, thus, the low-level check is redundant.

A similar argument are made for secure data transmission. The network is not the only place where data may be leaked, thus encryption must be done at a higher level to protect against all leaks at once. Similarly, suppressing duplicate packets is unnecessary because the application may itself erroneously issue duplicate requests as part of failure/retry procedures.

Thoughts

This paper gets at the key question of how to design abstractions. On one hand, the application has the big picture knowledge of what is happening and what the goals are. In the extreme, this could be used to justify putting all functionality into the application, as in fact it has in the OS world in papers such as Exokernel. On the other hand, the whole point of an abstraction is to separate concerns thus making each piece easier to develop and maintain. This is why modern systems provide basic functionality, such as memory management or scheduling in operating systems, even when it may be more efficient to implement at a higher level.

This paper seems to argue for the "end-point" or application implementing all functionality extreme, however, a careful balance is needed. The paper alludes to this in the performance section when they admit that some reliability at the low-level is necessary to obtain acceptable performance (i.e. don't retransmit a whole file for one lost packet).

Overall, I agree with most of the examples in this paper, however, I believe that a careful balance must be struck between low and high levels to maintain ease-of-use and performance not just eliminating redundancy.