Kim et al (2008) Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises (SIGCOMM)

This paper proposes a way to make a floodless Ethernet.

The key idea is “one-hop DHT”, which we let a host/switch to resolve addresses by querying a DHT. The directory service (address resolution) is built into switches. The switches are running link-state protocols to know about other switches on the network and maintains the routes. Then a common hash function is used to map host information into a switch, where a DHT directory is located.

The hash function \(F\) maps an input \(k\) into a switch \(r_k\). The switch \(r_k\) is the resolver for \(k\) and it stores the mapping \((k,v)\). For example, the mapping would be (MAC address, location) for L2 forwarding or (IP address, MAC address) for ARP. When a packet is being forwarded but the destination location is unknown, its destination MAC address is used as key \(k\) to compute \(r_k\) and query \(r_k\) for the location \(v\). In L2 forwarding case, the location is the destination switch ID. Once it is known, the route is determined because of the local link-state information.

To avoid control overhead when the set of switches on the network changes, consistent hashing is used. What is means is that, the hash function computes the resolver by \(F(k)=\arg\min_s\{D(H(k),H(s))\}\), where D is a simple metric function to compute the distance and H is a regular hash function. Using a consistent hashing makes the change in DHT minimal when the set of switches is changed.

Since not all switches are equally capable, we may want a different size of DHT on a different switch. This is done by having a virtual switch ID on each switch. A virtual switch ID is computed by a function R(s,i) where s is the physical switch ID and i is a counter. Every switch can allocate any number of virtual switches, by issuing different i’s. DHT is based on virtual switch IDs, then therefore, and the size of the DHT stored in a physical switch is proportional to the number of virtual switches it has.

Network-wide service discovery can also be done with SEATTLE, as we can use a service ID (e.g. a string) as input to the hash function to find a location.

ARP in SEATTLE is done in similar way, by using IP address as input key.

To maintain the DHT directory, the per-host information is managed reactively. Whenever a change is detected by a neighbouring switch (e.g. host turning on/off), a switch can issue insert/delete/update request to the DHT. Add is to add a new \((k,v)\) pair, delete is to delete it, and update is to update \(v\) for the given \(k\). The issuing switch (i.e. the one attached to the host concerned) for \(k\) is responsible to regularly check the resolving switch \(r_k\) is alive. Otherwise it has to recompute the new \(r_k\) and add the pair.

Bibliographic data

@inproceedings{
   title = "Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises",
   author = "Changhoon Kim and Matthew Caesar and Jennifer Rexford",
   booktitle = "Proc. SIGCOMM",
   year = "2008",
}