This paper describes SPAIN, a method to build data center networks (load balanced networks) from commodity ethernet switches and specialized hosts.

The hosts are required with no special hardware but a specialized driver so that all the packets sending out are in a VLAN and all the hosts are capable of doing some kind of signalling to other hosts. The idea is, for all hosts to any other hosts, we find \(k\) paths, preferably disjoin but not required, and combine them into a small number of VLAN spanning trees. Then the switches are configured with those VLANs with hand-coded forwarding tables. The host is then send packets with a per-flow random VLAN so that the traffic can be balanced. The merit of this paper is in the algorithm to combine paths into VLANs.


Problem of ethernet:

  • Spanning tree
    • STP makes a tree, which means inefficient use of cross-sectional bandwidth
    • STP makes network susceptible to failure near root
    • Making STP network of high bandwidth need ultra-fast cores, which is expensive
  • Packet floods
    • Ethernet learns and relearns the location of MAC
    • If packet’s address is not known at the moment, packets are flood to all ports
  • Host broadcasts
    • Protocols such as ARP, DHCP relies on bcast

SPAIN: Use VLAN to select different trees, so that total comm. bandwidth can be larger than a single VLAN

VLAN building:

  • Find k paths from node s to node t, disjoint paths preferred, but not required
  • Among all the paths, build loop-free aggregates (VLAN trees)
    • Each path belongs to a unique tree
    • Number of trees are minimized
  • Optimal solution is NP-hard, so heuristic algorithm is used


  • Compare different topologies: FatTree, BCube, 2D HyperX, CiscoDC
  • The algorithm works good: Number of VLANs is close to optimal
  • The algorithm is doing stochastic VLAN packing, the time required is reasonable

Fault tolerance

  • Either by Per-VLAN Spanning Tree (Cisco) / Multiple Spanning Tree (IEEE 802.1s)
  • Or by end-host failure mechanisms
  • End-host failure mechanisms can do faster repair

FIB pinning: Directly program the FIB tables on the switches

  • Requires central knowledge of MAC locations
  • Program the VLAN map and FIB tables on all switches
  • Disadvantage: May produce a larger FIB table
    • If FIB is learning-based, unused host are not recorded
    • FIB pinning will always have an entry for all possible destinations
  • Typical switch FIB table: 16K entries on SRAM, 128K entries on DRAM

End host algorithm

  • Five goals:
    • Spread load
    • Minimize overhead of bcast and flooding
    • Detect and react to failures
    • Facilitate mobility (e.g. VM migration)
    • Enable incremental deployment
  • Send packet:
    • Select an usable VLAN and send (randomly select)
    • If no candidate VLAN, send on default VLAN (VLAN 1)
    • Probe on all candidate but not usable VLANs
      • Send unicast chirp message to the destination on a VLAN
      • Rx of chirp signals VLAN usable at rx side
      • Respond of chirp may be requested
  • Re-pinning: Change a flow’s selected VLAN
    • Only in case of
      • Failure (immediate re-pin)
      • VM migration (immediate re-pin)
      • Improve load balance
      • Probe for revived VLANs
    • Re-pin algorithm for a flow
      • This host moved
      • My destination host moved
      • This flow is new
      • Non-TCP flow hasn’t re-pinned for too long
      • TCP flow becomes too slow (cwnd < threshold) due to rexmit
  • Receive packet
    • If chirp packet, do respond as requested on unicast
    • Any incoming packet is a proof of the health of the source on this VLAN
    • If chirp hasn’t been sent, send one to the source to signal for healthy VLAN
  • End hosts keeps the following information
    • VLAN in use for a dest switch (addr)
    • VLAN usable for a dest switch (addr)
    • These info are cleared periodically
  • Failure detection: By no packet received in VLAN
    • Stop using that VLAN for that destination

Bibliographic data

   title = "SPAIN: Design and Algorithms for Constructing Large Data-Center Ethernets from Commodity Switches",
   author = "Jayaram Mudigonda and Praveen Yalagandula and Mohammad Al-Fares and Jeffrey C. Mogul",
   howpublished = "HP TechRep",
   institution = "HP",
   number = "2009-241",
   year = "2009",