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.