Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

This is a paper with provides good arguing points for the proponents of a single layer-2 domain in the data center networks. Main points are:

1. The paper talks about the advantage of retaining plug-and-play approach of traditional Ethernet in huge data center clusters. It shows that the fixing configuration and maintenence problems associated with traditional IP routing incurs a significant cost to the service provider. The paper proposes a one-hop DHT routing protocol which routes packets based on MAC addresses.
2. The authors also point out that using Ethernet for routing comes with its own set of problems. Ethernet bridges are not scalable beyond a fixed number of hosts and are inefficient because it requires the routing based on a spanning tree. Absence of TTLs in layer-2 necessitates spanning tree to avoid loops. This means that certain links are left unused, which leads to loss of resources.
3. They claim that SEATTLE approach is scalable because it does not rely on broadcasts to update forwarding tables. Updates happen through a reliable cache update protocol based on unicast. Switches observe link state advertisements and are responsible for determining when a host or link fails.

Some of the problems of SEATTLE are: Each edge switch has to maintain state of each end-host it is responsible for. This means the switch state grows with the number of hosts in the data center, which is not desirable. Also, forwarding loops are not completely eliminated as the authors admit.

This area has a lot of scope for future research, partly because the problems related to data centers are becoming known only recently as the Internet reach spreads across the world. Chief among them is exploring if we are able to eliminate the need for broadcasts in layer-2, for operations like ARP, fault tolerance etc. That would prove a significant milestone in the merger of layer-2 and layer-3 into one single domain.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

Three Important Things:

• The motivating question for this work is that Ethernet networks provide several benefits such as “zero configuration” and a flat address space but do not scale well. The proposed solution operates at the network level and leverages a scalable DHT that does not require level 2 switches to maintain state for every host. Instead, host information (MAC, IP address) is mapped to a switch as the result of a distributed hash query. This removes the need for flooding in order to dissminate information, and protocols like ARP and DHCP can be replaced with on-demand queries and updates to a directory service abstraction.
• SEATTLE was designed to provide the appearance of regular ethernet to regular hosts, while maintaining a new internal network structure. This is a key selling point and paves the way for realistic, practical deployment. This feature is achieved by making the switches “link aware.” A switch is able to detect which links are connected to hosts as opposed to other switches by sending a control messge not recognized by end host level 2 NICs. Such links are treated in a special way in order to perform discovery and configuration. DHCP and ARP packets are snooped for this purpose.
• Experimental results were important in order to justify the claims of scalability and Ethernet class performance. Using simulation traces, the authors determined that forwarding table size is reduced by a factor of 41 in a 50K host network when compared to Ethernet. Table size and control overhead scale linearly with the number of hosts. In an Emulab implementation, SEATTLE switches significantly outperformed Ethernet in the middle of the network, however border switches required more processing time in order to deal with learning host addresses.

Glaring Problem:

Although a SEATTLE deployment would be transparent from the perspective of the end hosts, it would require a complete overhaul of the underlying network. This represents a significant cost barrier for an organization with a large existing infrastructure, the likes of which such a solution would be directed at. The authors dedicated little or no discussion to incremental deployment and coexistence with regular Ethernet switches and level 3 routers. Such a scenario has significant implications for the adoption of SEATTLE.

Future Work:

The DHT abstraction provided by the network is currently hidden from  the end hosts. Assuming the hosts can be made “SEATTLE aware,” they could make great use of the DHT for applications such as peer-to-peer content sharing. In order for this to happen future work would need to explore the necessary modifications to the host and possibly to the network.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

This SIGCOMM ‘08 paper describes an evolved architecture for large ethernets, motivated by the increasing management complexity of company-scale ethernets and by the intermediate patches used to deal with this complexity in the moment. Furthermore, this works aims at removing the need for broadcast-dependent protocols supporting basic ethernet functionality like ARP and DHCP. The central pieces to this architecture are:

1) The introduction of a one-hop distributed hash table storing the location of a host (MAC,SwitchLocation). With this mechanism, the replication of network information about a host on all switches is not needed anymore. By using a hash function, each host can determine independently which hosts carries the current location information to reach a particular machine. Since this information exists only once, it can be updated in an easy way without worrying about consistency.

2) The extension of this table to storing the (IP,MAC) associations for hops, therefore providing address resolution information in a distributed way. This information is discovered by snooping gratuitous ARP requests and DHCP requests, which in turn can be forwarded to the relevant hosts for this information service.

Packet forwarding in this system uses the first DHT, and uses shortest path forwarding for each single egress switch location, therefore having more than tree for the network and leveraging more links. To forward from the ingress switch, it can find the location resolver location by calculating the hash and then tunneling to this location resolver, which in turn tunnels to the egress host. This path is taken for the first few packets, until the ingress switch is notified about the egress switch for the destination.

3) To replace the VLAN construct on Ethernets, SEATTLE uses a group notion which is implemented on top of this architecture and provides broadcast groups on the network, which now may also span multiple subnets. The traffic for this (multicast) group can be forwarded more efficiently as before, because the forwarding looks for shortest path per egress switch.

The most glaring problem seems to me a missing way to rollout this network architecture on top of a normal ethernet, a gradual implementation pathway is missing.

Future work should be in this deployment area and in experimenting with it on a larger scale.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

This paper proposes a new scalable Ethernet architecture, SEATTLE which provides plug-and-play functionality via flat addressing, while ensuring scalability and efficiency through shortest-path routing and hash-based resolution of host information. The paper claims that SEATTLE efficiently handles network failures and host mobility, while reducing control overhead and state requirements by two orders of magnitude compared with Ethernet bridging.

SEATLLE forwards packets based on end-host MAC addresses but it doesn’t require every switch to maintain state for every host, nor does it require network-wide floods to disseminate host locations. Rather, it uses link-state routing protocol to form one-hop DHT which stores location of each host. Also, it forwards packets along shortest paths and to avoid excessive loads, SEATLLE switches caches responses to queries. It eliminates the need of location resolution by caching ARP replies. SEATLLE proposes an explicit and reliable cache update protocol based on unicast. This ensures that all packets are delivered based on up-to-date state while maintaining low control overhead. SEATLLE switches support unicast-based bootstrapping instead of traditional DFCP and ARP protocols for which it uses a directory service. It implements hash-based on demand resolution which deterministically maps a host to a switch which is termed as its location resolver. SEATLLE switches run link-sate routing to maintain only switch-level topology which helps in ensuring dataplane efficiency. All the host address and host location resolution is achieved through the directory service which maintains current mappings of host MAC addresses and their locations and host IP address and their MAC address. SEATLLE switches are able to handle host mobility efficiently by modifying the contents of the directory service via insert, delete and update operations. SEATLLE   switches are fully backward-compatible with conventional Ethernet and they internally convert ARP and DHCP messages to unicast.

The authors built SEATLLE protoptye using user-level Click and XORP and tested it using EMULAB. They observed that SEATLLE requires more processing time than Ethernet at an ingress switch as compared to non-ingress hops, intermediate and egress switches. This is because former needs to encapsulate a packet and then look up the next-hop table with the outer header while the later switches do not need to learn source MAC addresses. They also report the effects of network dynamics and fail-over performance and compare and contrast SEATLLE with Ethernet.

The authors conclude that Ethernet is not a viable alternative due to poor scaling and inefficient path selection. SEATLLE provides scalable self-configuring routing to counter this limitation.

Floodless in SEATTLE: A Scalable Ethernet Architecture for large Enterprise May 12, 2009

Paper proposes a network architecture combining best of both worlds IP and Ethernet. This combines the scalability of IP with the simplicity of Ethernet. Paper discusses a solution that provides plug-and-play functionality via flat addressing, and high efficiency using shortest-path routing and hash based resolution of host information. Paper discusses that conventional Ethernet has limitations caused by the network-wide flooding to locate end hosts, inefficiency introduced by the use of spanning tree, security and privacy concerns due to broadcasts. These issues can be handled to make a better system.

Paper introduces flat addressing and self-learning that enables plug-and-play networking. Permanent and location independent addresses simplify the host mobility, access-control policies and network trouble shooting. It introduces a control plane mechanism which avoids the flooding happening in when address in not known.  It uses a directory based service to support unicast based bootstrapping rather than using broadcast based DHCP or ARP. Paper keeps its forwarding table small by storing hosts location information only when it is needed.

To support existing systems backward compatibility end hosts are not modified.  Switches use hosts MAC addresses for routing rather than doing the broadcast. Switches automatically detect the arrival/departure of the host and avoid flooding. Hash deterministically maps a host to a switch. This way switch resolves end-host’s location and address via hashing. Switches use shortest path forwarding between switches and they run link-state routing to maintain switch level topology.  Each host location is advertised to only two switches.

This system is ideal for data centre and provides the features like workload balance failure recovery which are required in these applications. In summary, paper explores the tradeoffs between data-plane and control plane to make a better system.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

(i) the three most important things the paper says

One of the most important ideas that the paper discusses are the changes to the link state protocol.  Most notably, the change that allows SEATTLE to only map the switch locations (instead of mapping individual machines).  This reduces the number of broadcast advertisements sent throughout the network, which helps to address one of the biggest problems with Ethernet and IP.  Another important idea that the paper speaks about is the fact that this scheme can do away with the spanning tree protocol, which will actually allow for more efficiency in switch communication (instead of letting a shortest path go to waste for the sake of configurability).  This is important because the authors are attempting to address one of the weak points of Ethernet, because of the bottlenecks that it could possibly create.  A third important idea that the authors put forth is that this scheme can still function properly while still maintaining end-to-end Ethernet and IP semantics.  This means that only the switching hardware needs to change in order to implement this scheme and all end-host hardware can remain the same.

(ii) the most glaring problem with the paper

One of the biggest problems that I can see with this scheme is the fact that it requires 100% proprietary hardware, and in order to function properly cannot use any traditional hardware.  This requires a user to completely revamp their entire networking system with potentially expensive hardware all at once.  This will make this idea much more difficult to transition to.

(iii) the future research directions of the work

A couple future directions would be useful.  First, reducing the complexity of the hardware would be an option, as this would make the “glaring problem” much more tolerable.  Another option would be to somehow adapt the scheme to work partly with commodity hardware, so that users could gradually move their scheme over (which would probably give this scheme more feasibility).

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

The SEATTLE protocol is a giant leap forward in configuration-free LAN functionality. This protocol has the potential to replace the hodgepodge of routers and switches within an autonomous system with a single scalable, low maintenance, high performance network. It hearkens the convergence of layers 2 and 3. The system is backwards compatible with existing Ethernet network adapters and provides Ethernet services such as ARP and DHCP, allowing the plug-and-play end-station deployment that people have come to expect.

The convergence of the datalink and the network layers is completed by replacing both the spanning-tree and OSPF routing algorithm with a single “configuration-free” hybrid. The system automatically adjusts to host movement using a single scalable architecture. The novel shortest-path algorithm provides freedom from addressing and location constraints. Switches require less per-host state than the current generation of switches using the spanning-tree algorithm.

Much of the functionality and scalability results from the use of servers as opposed to broadcast to perform required services. Switches track their host connectivity and update a central distributed server. Broadcast requests ,e.g., ARP requests,  are intercepted by the attached switch and forwarded to the server. Replies are cached by the switch locally to optimize performance and enhance scalability.

Policy configurations are managed in a centralized server and are not topology dependent.  The system is also resistant to malicious users. DOS attacks are prevented because broadcast is prevented having been replaced by multicast.

Overall system complexity, once distributed between layers 2 and 3, is now aggregated into a single hybrid layer. Management responsibilities and management skill-sets where defined by the separation of layers. This system merges these responsibilities and skill-sets. The cost of these complex switches may be offset by lower memory requirements but will be aggravated by troubleshooting and management issues.

The automated shortest path routing and configuration qualities of the system are applicable within an autonomous system. Can these qualities be applied to Internet backbone networks? The routing techinque could be used to optimize and simplify inter-domain routing. Peering aggreements can begin to include further “automated” components.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

Important Things:
1) Ethernet’s reliance on flooding, spanning tree, and broadcasting for plug-and-play operation severely limit its scalability in an age when larger and larger networks are being built.
2) They were able to make Ethernet scalable while maintaining compatibility with existing end hosts and applications by employing a one-hop DHT to implement a distributed directory service. This handles the plug-and-play functionality while avoiding broadcasting, etc.
3) They tested and verified their design through simulation and actual implementation.

Problems:
One argument they made was that hosts in enterprise networks “typically communicate with a small number of other hosts”. However, they are also targeting data centers, where this may not be true. It would be interesting to see what traffic patterns might cause cache thrashing what impact it would have on performance.

Future Work:
The scalability of Ethernet is an important area of research. Various design approaches should be proposed and evaluated on many dimensions including performance, flexibility, robustness, security, etc.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

This paper presents a noble solution that could become a practical replacement for the Ethernet. The authors note that while Ethernet is flexible and simple, it does not scale well due to its high reliance on broadcast messages and its inefficient spanning-tree approach. Their aim is to achieve the scalability of the IP networks while keeping the simplicity of Ethernet. They do so by using a dynamic hashing approach, while providing shortest-path routing at the same time. In essence, using SEATTLE could remove the need to use a combination of routers and switches and replace both by SEATTLE switches. SEATTLE has the plug-and-play semantics of Ethernet, without breaking backwards compatibility. The main contributions of the paper are:

1. One-hop DHT approach provides mobility, load balancing, and flexible service discovery: SEATTLE uses consistent hashing to map key-value pairs to switches. Key-value pairs could be of type (ip, mac), (mac, switch id), or (’string id’, switch id). This provides host mobility, as no matter where the host is located on the network, looking up which switch is responsible for resolving its address is discovered by the same simple hash function. A publisher switch publishes this key-value binding for a node connected to it, and the resolver switch (determined by the hash function) stores this value. Switches can act like several virtual switches and thus provide better load balancing: the more powerful switches, or switches with less traffic could hold more virtual IDs, thus hashing more of the key-value pairs to themselves. Also this address resolution method removes the need for routers, thus enabling the SEATTLE switches handle the job of a router and a switch.
2. SEATTLE provides scalability in a large network and offers better utilization of the network links. As opposed to Ethernet, SEATTLE only uses the link-state protocol to communicate between the switches and not end hosts. The switches can use active polling to determine which of their hosts are active, which are disconnected, and monitor for changes in the hosts. This ensures that the service scales well with number of hosts in the network. Link-state also allows the switches to find the shortest path between other switches, thus achieving the same shortest-path principles as Ethernet. Further, since SEATTLE does not use the spanning-tree approach, it can use all available links for routing, as opposed to Ethernet where links not in the spanning tree remain underutilized.
3. Removing broadcast messages: SEATTLE does not forward all broadcast messages. For example ARP messages are handles by the switches, since they already know this information. SEATTLE also takes advantage of ARP messages by sending the location of the switch in addition to the MAC address to the host who initiated the ARP request. Therefore, the host packets can traverse shortest-paths by knowing the location of the destination switch. DHCP messages are handled by the switches as well.

Glaring problems: While one of the aims was to keep simplicity of Ethernet, I think the protocol is more complicated than Ethernet and network operators might hesitate before adapting to a more complicated design like SEATTLE. Also, when a switch leaves or joins the network, the hash function could change, and all key-value pairs must be reassigned again using link-state protocol. Although the hierarchical design tries to tackle this problem, it might be difficult to determine such hierarchy. The solution is desired for large scale networks of many switches. In such networks it might be probable for several switches to join or leave the network periodically. This means that in a large enough network of switches, the hash function would change periodically, and thus the switches would need to communicate their new key-pair values with each other. This would generate a lot of undesirable traffic and might hinder network performance. Also the initial lookup of the resolver switch adds several hops. While this only reduces latency for the first lookup, it might still be a problem if the majority of the network traffic is short-lived bursts to various hosts, requiring constant address resolution.

Future Research: it would be interesting to see performance measurements for a large-scale deployment of SEATTLE (rather than simulation of the same scenario).

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

SEATTLE is a proposal for an architecture that is as auto-configuring as Ethernet, but scales like configured IP networks. The problems with Ethernet are its use of flooding to communicate, forwarding tables proportional to the number of hosts, and a single spanning tree that does not provide shortest path semantics. The problems with IP networks are the need for subnetting, coordinating IP prefixes (for DHCP servers), and lack of support for mobility.

The paper provides contributions in the way of building a scalable auto-configuring network that uses a distributed directory service as the basis for address resolution and location information. Some key features include the use of a single hop DHT as the directory service, and reactive caching for address and location information to avoid excessive load.

The directory service is used to distribute key value pairs such as: (MAC, IP) and (MAC, location info). This information is used by switches to avoid broadcasting requests across the network. For example, when an ARP request is received by a switch, it looks up the switch that corresponds to the MAC address and asks it for the current IP address. This alleviates the need to store per node information in each switch. Additionally, it makes IP changes (perhaps from node mobility) easy to implement. The MAC address never changes, and therefore neither does the switch that corresponds to it. Therefore, when an IP address changes, it needs to be updated in only 1 location.

A DHT is the underlying mechanism for the directory service. All the switches use the same hash function to identify which switch corresponds to which key (in a key value pair). Thus, every access to the DHT is a single hop. For extremely large networks, the DHT can cover a large geographic range. Therefore, the authors considered a region grouped variant of the DHT. In this variant, the hash function for a region identifies switches only within that region. When link state is written to a switch, that information is also written to a border switch (on the network’s so called backbone). The border switch is the externally responsible switch that other regions will hash to for nodes in the original, local region.

The last contribution is the use of fastidious caching. The authors recognized that within large enterprises/organizations most nodes communicate only with a small set of other nodes with in the network (i.e. email server, file server, etc.). Thus when the authors added address and location caching to the switches (as an optimization), they do so reactively instead of proactively. This reduces the amount of forwarding table use in each switch while at the same time providing shortest path information.

The SEATTLE architecture is quite impressive. As with other “scalable Ethernet” alternatives it suffers from the fact that switches must be modified to implement the new architecture. Until switches become configurable or a vendor begins implementing modified switches, I don’t expect these new architectures to be anything other than good simulations.

Despite its applicability in real world networks (as of the moment), I think that further research would make it a more attractive option for business to adopt. Research in the area of multicast and anycast would add to the usefulness and could push this design closer to real world adoption.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

The paper describes the bottlenecks present in making current Ethernet as one large scalable network and also proposes a novel architecture called SEATTLE to overcome them. Ethernet is vastly simpler to manage and has many desirable properties like seamless virtual machine migration that is not possible in IP based networks. Moreover the maintenance and configuration overhead of IP networks is huge compared to a Ethernet. The proposed SEATTLE architecture attempts to combine the best of both worlds by taking the simplicity of Ethernet and scalability of IP. The main problem of the Ethernet is the flooding of broadcasts to keep every switch updated of the knowledge about every other host. These floodings can generate a lot of traffic and consume significant bandwidth. To overcome this, the SEATTLE architecture uses the link state protocol to maintain hop by hop paths from source to destination. Hence it does not require each switch to maintain state information of every host, nor does it require network wide floods to disseminate host locations. The SEATTLE architecture also follows a shortest path based forwarding rather than the conventional spanning tree protocol which is inefficient and ignorant of load balancing. Also to avoid excessive load on directory service which maintains the mapping between mac addresses and their location, switches cache response to queries. Since in enterprise networks hosts typically communicate with a limited number of hosts, caching becomes highly effective. Finally SEATTLE also provides a reliable cache update protocol that ensures that all packets are delivered based on up-to-date state.

The main challenge of the architecture is its scalability. To avoid such a network architecture to grow into one large and hence slow monolithic network, they have proposed the technique of hierarchical design in which LANs are divided into regions connected by backbone switches. Relating to this is also the problem of unnecessarily large forwarding tables due to the flat address space of the Ethernet. Also in case of handling host dynamicities, a large number of complex actions have to be taken to restore the network information to a consistent state. Thus this may invite the same problems that existed in conventional IP networks, only being translated to the Ethernet domain.

The ideas presented in the paper can be further extended to design a protocol that is backward compatible with the existing Ethernet. Verification and performance evaluation of the protocol should be done by deploying it to a real network. The ramifications of such protocol on switch architectures must also be studied for making modifications to them tailored for efficiency under the given protocol design. Finally the flexibility of changing the Ethernet stack may also be considered to explore the scope of further improvements.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

The paper proposes a network architecture (SEATTLE) that aims to combine the plug-and-play simplicity of Ethernet networks with the scalability of IP. Flat namespaces and self learning have vastly aided the plug-and-play features of Ethernet. But its broadcast based discovery protocols and underutilization of network redundancy (due to spanning tree based forwarding) are a huge hurdle when it comes to scalability. On the other hand, IP based networks are highly scalable, but require a lot of manual configuration. So, modern large scale networks are typically constructed as a hybrid of IP and Ethernet based architectures. This paper proposes an architecture that attempts to combine the best features of both worlds. SEATTLE achieves these goals without any modifications to end-hosts.

One of the primary contributions of the design is the avoidance of network wide broadcasts to disseminate individual host locations. SEATTLE uses a one-hop DHT to store the location of each host. This avoids broadcast storms even when a switch that needs to forward a packet does not know the location of the destination host in the network. The packet is just forwarded to the resolver for that MAC address and forwarded with MAC-in-MAC encapsulation.

The second contribution of the paper is the avoidance of broadcast based implementations of bootstrapping protocols – ARP and DHCP in particular. The DHT service is used by SEATTLE switches to respond to ARP requests directly rather than broadcasting ARP requests to all the hosts. DHCP is also handled specially by SEATTLE switches by directly forwarding the DCHP request to the DHCP server through unicast rather than broadcasting the request throughout the network.

Another contribution of the paper is the use of a link state routing protocol to maintain switch topology. This allows for IP style routing based on shortest paths rather than the traditional spanning tree approach used for Ethernets. This is an increasingly important concern in modern large  scale networks where there is a lot of path redundancy.

There are certain points about the paper that are weak or require better exploration. The paper states that it can do with small routing tables in the switches and do away with large state in individual switches. This claim is not always true. Caching is used to actually fetch the host location information only upon demand, but this need not lead to smaller forwarding tables. The paper states data centers as a prime target for the design. But most data centers have a lot of all-to-all communication in short time frames and so in the worst case, SEATTLE would have to maintain entries for each host in the topology because of the forwarding based on flat address space. With regard to fault tolerance of in the DHT service, it is mentioned that if a resolver fails, then a local switch that published an entry in the resolver would have to detect this and republish the mapping on the fallback resolver. The paper however does not mention what happens when the local switch loses its state (perhaps an unexpected reboot). This would require it to update its data from all the resolvers to which it might have published information. Otherwise, it could just wait to get updated based on traffic received from its connected hosts (which can cause unavailability of service). Worse, if both the resolver and the local switch lose their state simultaneously, then the data will have to be updated only from the hosts which can cause extended periods of unavailability of service. Another minor issue – In the section on bootstrapping of hosts, the authors mention that if a host does not generate a gratuitous ARP, the switch can learn of the host’s IP address via snooping on DHCP messages or sending out an ARP request on the port connected to the host.  An ARP request is sent out to find out the MAC address mapping for an IP address while inverse ARP is the one to find out the IP address given the MAC address. Now if the switch neither knows the IP address nor the MAC address of the host, how can it send any ARP/inverse ARP request to the host? Also the notion of broadcast groups as proposed in the paper does not seem to be any different from traditional IP multicast groups except that the group membership might now be decided upon by a network administrator, and reachability policies can be imposed directly upon them. But with the approaches described in the paper, this should be possible for traditional multicast groups as well.

The area of designing large scalable L2 networks is a very hot topic in networks currently and there is a lot of scope for future research in the space. Considering that SEATTLE has been proposed for general deployment for large scale networks, exploring the incremental deployment of SEATTLE could be an interesting aspect to look into. Exploring the failover characteristics of the DHT mechanism described in the paper in detail and improving it to speedup recovery times is another possible direction.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

The paper proposes SEATTLE, an Ethernet architecture for large enterprises that is more scalable that the conventional Ethernet and has less configuration and management overheads than IP. The authors pinpoint limitations of conventional Ethernet bridging as having to flood the network to discover end hosts, non-usage of redundant end-to-end paths in a spanning tree and excessive reliance on broadcast for service discovery. IP on the other hand has the ability to scale but poses the limitations of address space wastage due to sub-netting and configuration overhead due to dynamic host IP addresses. An architectural alternative to Ethernet/IP adopted by operators today is the usage of VLANs encompassing a subset of end hosts in different domains for broadcast. But even VLAN requires a lot of prohibitive manual reconfiguration, spanning tree rebalancing, have excessive trunk configuration overhead and use power hungry CAM technology. To circumvent these limitations the authors propose a network architecture which uses a link-state like one-hop DHT protocol to disseminate end host location, uses query caching for shortest path routing and implements unicast based cache update mechanisms that ensures reliable transmission in a dynamic network environment. The main points discussed in the paper are the description of the hashing scheme, the scalability argument and the performance evaluation of SEATTLE.

To have an interface similar to that of Ethernet, the authors use a one-hop DHT directory service to map hosts MAC and IP addresses to their locations. They use a network level approach to reduce lookup complexity and enable maintainability. Instead of a conventional host-level link-state protocol SEATTLE uses switch link-state algorithms in which every switch has the location information of every other switch in the network. To remove network flooding during host dissemination SEATTLE does on-demand information hashing on every switch. SEATTLE implements a hashing mechanism in which a location resolver switch is associated with a key and a value and other switches can look up a value (MAC address/location) by applying a commonly available hash function on the key (MAC address/IP address). Link state advertisements between switches communicate the switch identifiers thereby enabling switches to have complete sate information. Since this mechanism is unicast based, broadcast ARP type of network intensive protocols are not required. Virtual switching and service discovery are made simply by attaching advertisements with the number of virtual switches per physical switch and service discovery string when required and subsequently applying appropriate hashing function. SEATTLE supports hierarchical networking by multi-level, one-hop DHT wherein every disparate region is associated with a border switch and these border switches are interconnected to form the network backbone. Hashing mechanism similar to single-level on-hop DHT is applied to border .

In the most common case, any given host in an enterprise network communicates with only a subset of popular hosts. In this scenario, the reactive nature of one-hop DHT algorithm works best as against proactive Ethernet dissemination which introduces heavy overheads. Further, ARP optimization is handled by having the address resolvers maintain host locations in addition to host MAC addresses thereby eliminating the need perform forwarding via location resolvers. Atomic operations like insert, update and delete are provided to handle host dynamics and to create new resolvers. Also to reflect host dynamics (e.g. change of MAC address) on the cache of a remote, the link-state advertisements are made by the initializer switch to the list of switches which need to have their caches updated (revocation list). This method of multicast to switches on the revocation list scales better than conventional gratuitous ARP. The authors point out that Ethernet like semantics are retained by using DHCP service string multicast instead of broadcast and by using groups to replace VLANs.

The authors implement the architecture using XORP and Click and they conduct a performance evaluation on the system by running synthetic traces of network traffic patterns pertaining to four different network topologies on it. It is shown from the performance measurements that SEATTLE scales better than Ethernet when it is subject to host dynamics and network changes and is also better in terms of the control overhead and the size of forwarding tables required (since ARP flooding is eliminated). Although the initial slack in bringing up the network and configuring the inbound queue is higher than Ethernet, overall SEATTLE exhibits much better performance.

SEATTLE paper presents a very interesting proposition for substituting the ubiquitous Ethernet/IP hybrid networks and using a simplified switch-level forwarding architecture. Although the scalability argument is visited many times in the paper, no substantial experimental results are provided to back the argument. Also, no quantitative results are shown in term of host count to support the scalability of SEATTLE as compared to Ethernet. Even with these limitation SEATTLE draws on a future where one-hop DHT based hardware switch architectures can be explored and the validity of such a network architecture be proven by effective deployment of schemes and methods discussed thus far.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

(i) The three most important things the paper says:

1. There are tradeoffs between Ethernet and IP: Ethernet is easy to use and configure, and can automatically learn host addresses, but cannot scale well due to the flooding techniques it uses to find hosts, and the poor scalability of routing information. IP scales well but has many configuration issues (such as a lack of a persistent identifier like a MAC address)
2. SEATTLE improves the scalability of Ethernet by using distributed hash tables to store host address and location information across switches. Switches maintain a switch-level topology view by using a link-state protocol, and hashing host information to particular switches to create a directory service.
3. SEATTLE avoids broadcast storms by suppressing broadcast protocols such as ARP and DHCP, instead using the directory service to register information to the appropriate switch.

(ii) The most glaring problem with the paper:

From my understanding of the architecture, it seems like it would be difficult to incrementally deploy this architecture (that is, use a mix of conventional switches along with SEATTLE switches). The distributed hashing would only be able to be done on the SEATTLE switches, which might complicate the scalability of the system. For the large topologies which this paper is envisioning, a complete deployment of SEATTLE switches may not be realistic.

(iii) The future research directions of the work:

It would be interesting to see the network “in action” with an actual topology consisting of multiple SEATTLE switches running the directory service, and to evaluate the performance, efficiency and reliability of the architecture. I am also curious as to how much bigger this architecture can scale in comparison to Ethernet, and what (if any) the eventual bottlenecks would be.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

1)

i. Ethernet has very desirable properties for an enterprise network. It has very little configuration allowing it to be “plug-and-play” and works well with mobility since the address does not determine the location. The problems however is that it doesn’t scale very well. One of the main issues with scaling Ethernet are the fact it uses broadcast protocols to get IP addresses (DHCP) and also to locate a host with only an IP address (ARP). Another issue is the fact it uses a spanning tree configuration which makes it less fault tolerant and also overloads links near the root of the spanning tree.

ii. By introducing the concept of IP like routing based on MAC addresses, the authors have proposed a scalable network architecture with Ethernet like semantics. To do this they use a one hop DHT to map a MAC address to the switch that host is currently connected to. This allows clients to send packets only using the MAC address, not an IP address. When the switch that client is connected to see the packet, it looks up which switch the destination is connected to and routes the packet to that switch which then delivers it to the destination. This setup allows for a routable architecture similar to IP with the semantics of a Ethernet like architecture.

iii. Maintaining backwards compatibility is important for adoption. To this end the switches in SEATTLE respond to both ARP and DHCP requests from clients. Furthermore maintaining the ability to broadcast is important for many applications such as IP multicast. To this end SEATTLE allows and administrator to setup “groups” and when a client sends a message to the group, the switches take care of ensuring that message gets delivered to all the members of the group.

2) One flaw in SEATTLE is that it doesn’t deal with congestion. Given how the switches automatically set themselves up and inform each other of their link state, I think it would be beneficial if the switches attempted to detect long lasting flows and try to use that to assist in making routing decisions.

3) Future research directions might include researching how this system works in practice. Examining if it scales as well as promised and ensuring it doesn’t break anything on Ethernet.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

1. Maintain only switch-level topology

The link state protocol implemented by SEATELL maintains only switch-level topology which is used for forwarding packets at each switch. This, not only reduces the control traffic, it also reduces the control and routing information that needs to be maintained by the network devices. Each switch only maintains information about those hosts directly connected to it.

2. Efficient utilization of hash functions to determine host location.

The paper uses hash functions to determine the switch that would maintain IP-MAC-location mappings of a host. This way, flooding resulting from ARP and DHCP is avoided. It also  provides for consistent hashing which reduces overhead in case a switch maintaining MAC-IP-location mapping of a host goes down due to network failure or a new switch is added to the network. SEATTLE also runs multiple virtual switches on each switch allowing the more powerful switches to handle more load by supporting a larger number of virtual switches.

3. Backward compatible with conventional Ethernet and support for ARP & DHCP

The switches in SEATTLE network are capable of discovering hosts supporting only conventional Ethernet. They learn the new hosts MAC address in the same way Ethernet does and learn its IP by snooping on gratuitous ARP requests. The switches support DHCP and ARP while prevent flooding of the network with the ARP and DHCP traffic.

Drawbacks

The SEATTLE network, while elimination broadcast and control traffic overheads introduces its own set of overheads. The switch that the host is connected to (pulisher switch) needs to monitor the liveliness of the switch that maintains the hosts mapping information (resolver switch) through link state advertisements. In case of hierarchiacal implementation of SEATTLE, each publisher switch needs to send periodical probes to backbone resolvers that lie outside its reagion. There is also the triangle problem that might arrise. The looks like a trade-off between latency and state maintaining overhead.

Future work

The idea can be extended to support mutiple protocols. It can be enhanced to provide for greater security that is an important concern in enterprise networks.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

(i) Three most important things

1. It is difficult to construct large efficient LANs with the current Ethernet architecture due to broadcast storms which can flood the local network. The paper proposes a new Ethernet architecture known as SEATTLE which partitions large networks into small ones and limiting broadcasts to the small networks. Each host lies behind a “border switch” which the broadcasts are not allowed to cross.

2. It is difficult to construct large efficient LANs with the current Ethernet architecture due to inefficient path selection. Ethernet uses a spanning tree to forward packets to avoid loops during flooding but forwarding along single tree leads to inefficiency and lower utilization. SEATTLE uses shortest-path forwarding between switches

3. Flooding and self-learning with the current Ethernet architecture lead to unnecessarily large forwarding tables. SEATTLE uses a reactive location resolution and caching. A hash deterministically maps a host to a switch. Switches resolve end-hosts’ location and address via hashing.

(ii) Most glaring problem

The most glaring problem would be that the authors of the paper didn’t do any experiments on preventing broadcast storms and flooding attacks which were the reasons why the current Ethernet architecture could not be applied to large networks.

(iii) Future Research Directions

Future research directions for this work would be to investigate how to design switch hardware to efficiently support SEATTLE and to determine what performance optimizations can be made if end host software can be changed.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

(i) The three most important things the paper says:

1) The problem with flat addressing in Ethernet can be addressed with one hop DHT (Dynamic Hash Table).  They argue that using one hop DHT, SEATTLE can build a flexible directory service with address resolution at the same time.  This is key since it flat addressing is one of the key problems in scalability.

2) Replacement of traditional broadcast ARP with an extension to the one hop DHT directory service.  Essentially they change the ARP system to use unicast instead of broadcast.  This is key since relying on broadcast protocols (especially if unnecessary) reduces network performance.

3) Since not all broadcast protocol (current/future) can be avoided, they support it via multicast through a tree which also avoid loops.  Furthermore, this was done via a concept of groups, similar to VLAN, which provides a broadcast domain.  Unlike VLANs however, they provide additional benefit since it doesn’t need to be tied to a switch which makes configuration easier.

(ii) The most glaring problem with the paper:

The biggest problem with the paper is that although one of the argument was ease of configuration/simplicity with SEATTLE, they didn’t dive into it much in their results.  Mostly it was documenting the performance aspect of SEATTLE, which is important, however that was only one of their argument points.  To be more complete, they could have discuss the challenges, or lack their of, in the implementation section.

(iii) The future research directions of the work:

The future research of the work could investigate the SEATTLE system with peer to peer network traffic.  Since a network with lots of broadcast traffic, which rely on the multicast tree, may cause SEATTLE to perform on par with existing systems.  In which case, it may not be feasible to switch to SEATTLE.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

The purpose of this article was to describe an alternative protocol to Ethernet known as SEATTLE. The authors goal was to develop an that would be largely configuration free and dynamic but also be able to scale to the necessary size to be practical. The key points in this article were:

1.SEATTLE implements a one hop network layer DHT to create and manage a shortest path routing structure as opposed to implementing identity bases routing. This location based routing provides for more efficient routing through decreased latency as well as greater flexibility in determining the way that services may be discovered and directed to.

2.In order to implement the routing tables without every host needing to know every other host and therefore ruining scalability, the protocol implemented several features such as reactive rather than proactive discovery, hierarchical tables treat regions of computers as a black box and reduce the size that the tables need to be to implement shortest path, and extended ARP commands that carry much more information in order to reduce the amount of over head traffic on the network.

3.Testing showed that SEATTLE did scale to a significantly larger size than a standard Ethernet and with significantly less management traffic. It also performed better on large networks. However, on smaller networks the improvements were not as drastic or were even slower as the Ethernet protocol was able to administer to a small number of hosts effectively without the improvements that SEATTLE provided.

One issue that I saw with the paper is that they did not include a test where the protocol was deployed incrementally across a network and measured for performance. It would have been interesting to see how a partial deployment would look in order to make it more attractive for someone to test it in a real setting such as a university.

The future research of this paper, as pointed out by the authors, would be to examine the deployability of such a system into a real network of significant size and also how hardware could be optimized to further improve performance. Some other features such as traceback and authentication could be looked into since this protocol uses location based routing. Adding security features to this protocol could make it very attractive to those who have large networks that exceed the capacity of standard ethernet.