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.