[armd] For your consideration: SEATTLE

[Matthew Caesar <[e-mail]>]

Hi,

I've been watching this list with a lot of interest. We wanted to post 
for your consideration a protocol called SEATTLE we've been developing, 
which targets large improvements in scalability of layer-2 in the 
context of data centers/cloud computing by eliminating the need for 
broadcasts. We think SEATTLE addresses some of the goals in ARMD's 
charter. More details below, but we'd be quite interested to 
discuss/answer questions if there's interest.

SEATTLE achieves the same configuration-free properties as Ethernet 
bridging yet scales to large networks. Unlike other proposals (e.g., 
TRILL, Rbridges, Viking, SmartBridges), SEATTLE completely eliminates 
the need for network-wide broadcasting, achieving data-plane control 
overheads that grow logarithmically with network size. SEATTLE is 
backwards-compatible with existing Ethernets, simplifying incremental 
deployment, and supporting existing Ethernet functions (e.g., VLANs and 
host bootstrapping). SEATTLE also supports more advanced (optional) 
features, such as the ability to search and look up services based on 
text strings, more flexible routing and more control over layer-2 
routing policies, and the ability to anycast and load balance directly 
over named services. SEATTLE has two main features:

Distributed in-network directory service: The switches collectively run 
a directory service that handles ARP and DHCP requests, as well as 
packets sent to unknown destination addresses. The directory service 
leverages consistent hashing and the link-state routing protocol to form 
a one-hop distributed hash table. The directory is a key-value store, 
where the hash of the key determines the switch(es) responsible for 
storing the information. For example, for ARP queries, the key is an IP 
address and the value includes the IP address and the host’s location. 
When an ingress switch cannot handle an ARP/DHCP request or a data 
packet directly, the switch computes the hash and directs the packet 
through the responsible intermediate switch. The intermediate switch can 
response to ARP and DHCP queries, and direct data packets onward to 
their egress switch while returning the destination host’s location to 
the ingress switch.

Reactive caching and invalidation: To minimize the portion of traffic 
directed over longer paths, an ingress switch reactively caches the 
responses from the intermediate switch. For example, while an 
intermediate switch may handle an ARP query, the data packets typically 
flow directly along the shortest path. In addition, other hosts 
connected to the same ingress switch benefit from the cached 
information. However, the cached information becomes stale if a host 
moves to a new location. SEATTLE includes an efficient cache 
invalidation protocol that reactively updates the stale cache entries 
when a packet wrongly travels to the old egress switch.

The first feature leads to good performance (by keeping traffic in the 
data plane, and avoiding broadcast) and self scaling (by having the 
directory service naturally scale with the size of the network), and the 
second ensures fast recovery after failures and migration.

Our writeup on SEATTLE:

http://www.cs.princeton.edu/~jrex/papers/seattle08.pdf

presents more details on this protocol, our experiences designing and 
implementing a system prototype, and a performance evaluation of the 
protocol through simulations and deployment in a testbed.

-- Matt