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.