Cutting the Electric Bill for Internet-Scale Systems

A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, B. Maggs, "Cutting the Electric Bill for Internet-Scale Systems," ACM SIGCOMM Conference, (August 2009).

One line summary: In this paper the authors suggest a new method for reducing the energy costs of running large Internet-scale systems by rerouting traffic on an hourly basis to data centers in regions where the price of energy is cheaper.

Summary

This paper examines a new method for reducing energy costs of running large Internet-scale systems. This method is based on the observations (1) that electricity prices vary on an hourly basis and are not well correlated across different geographic locations and (2) that large distributed systems already incorporate request routing and replication. Considering this, the problem the authors want to solve is: given a set of datacenters or server clusters spread out geographically, map client requests to clusters such that the total electricity cost in dollars of the system is minimized, possibly subject to constraints such as staying under a maximum response time.

The authors first do an empirical market analysis. They verify that prices are not well correlated at different locations, and also note that the price differentials between any two locations generally vary hourly and somewhat unpredictably, suggesting that a pre-determined assignment is not optimal. They examine the overall differential distribution and conclude that there does exist the opportunity to exploit these differentials for savings. To evaluate their method, they use traffic data from Akamai to derive a distribution of client activity and cluster sizes and locations. They then use a simple model to map prices and cluster-traffic allocations to energy prices. They handle the issue of bandwidth costs (i.e. changing assignments of clients to clusters could increase bandwidth costs) by estimating the 95th percentile from the data and constrain their reassignments such that this 95th percentile is not increased for any location. To estimate network performance in their model, they use the geographic distance between client and server. They model the energy consumption of a cluster to be roughly proportional to its utilization. The authors assume the system is fully replicated and that the optimization for cost happens every hour. They then use a simple discrete time simulator that steps through the Akamai usage statistics. At each time step a routing module with a global view of the network allocates clusters, and from this they model each cluster’s energy consumption, and use observed hourly market prices to calculate expenditures.

The authors are able to show that existing systems can reduce energy cost by 2% without significant increase in bandwidth or reduction in client performance. They also find that savings rapidly increase with energy elasticity, which is the degree to which energy consumed by a cluster depends on the load placed on it. Lastly, they find that allowing increased distances between the client and server leads to increased savings.

Critique

This paper was somewhat thought-provoking and brought up some interesting issues. However, what I didn’t really enjoy about this paper is that their model is forced to make so many simplifying assumptions about so many things, such as network performance, cluster power usage, and bandwidth costs, to name a few, that I’m not sure how valid their actual findings turn out to be or how much credence to give them. Along this vein, it would be interesting to know to what extent their results depend on the traffic data they used. Another assumption I didn’t really like is that they assume complete replication in the system in question, so that any request can be routed anywhere. I personally can’t guess how true that is in practice but my inclination is that it is not necessarily true for all Internet-scale systems, though it may be true for many. Furthermore, while in theory the basic idea seems like it would work, the authors do hint at a few complicating factors (that are not necessarily purely computer science problems), and it’s hard to know what others might arise in actually trying to implement something like this. For instance, the authors assume that rerouting traffic in this way would not increase bandwidth prices, but that may not be true, and companies are averse to increasing their bandwidth costs. As another example, in reality, renegotiating existing contracts between companies and cluster operators work if the company rents space in a co-located and between companies and the utility companies to take into account this new method may be difficult. Given all the assumptions the authors are forced to make and other complicating details that they may or may not be aware of, it’s hard to judge whether or not something like this would be feasible in reality. And, if everybody did this, it does make you wonder how that would change things, since there is likely feedback between the number of requests routed to an area and the price of energy there. So in summary, although the authors didn’t really have a choice but to try to make good assumptions or estimates of the various unknowns in their model, I couldn’t help but be frustrated by this aspect of the paper. Regardless, I was still impressed by their model and simulation and found it interesting.

A Policy-aware Switching Layer for Data Centers

D. Joseph, A. Tavakoli, I. Stoica, "A Policy-aware Switching Layer for Data Centers," ACM SIGCOMM Conference, (August 2008)

One line summary: This paper presents a new layer-2 mechanism for supporting middleboxes in datacenters called the PLayer that incorporates pswitches, which allow administrators to specify the sequence of middleboxes a given type of traffic should traverse.

Summary

This paper presents PLayer, a new layer-2 for data centers consisting of policy-aware switches called pswitches. The main goal of the PLayer is to provide a mechanism to support the use of middleboxes in datacenters. The problem with using middleboxes in datacenters today is that (1) they are hard to configure to ensure traffic traverses the correct sequence of middleboxes without physically changing the network topology or overloading other layer-2 mechanisms, which is difficult and error-prone, (2) network inflexibility makes introducing changes difficult and can result in fate-sharing between middleboxes and other traffic flow, and (3) some traffic is often forced to traverse some middleboxes unnecessarily and load balancing across multiple instances of a middlebox is difficult. PLayer seeks to address these problems by providing correctness, flexibility, and efficiency. It does this by adhering to two main design principles: (1) separate policy from reachability and (2) take middleboxes off the physical network path.

The PLayer consists of pswitches, which forward frames according to an administrator-specified policy. Policies define the sequence of middleboxes that a given type of traffic should traverse and are of the form “[start location, traffic selector] → sequence”, where a traffic selector is a 5-tuple consisting of source and destination IP addresses and port numbers and the protocol type. These policies get translated into rules of the form “[previous hop, traffic selector] → next hop”. Administrators specify policies at a centralized policy controller, which disseminates those policies to each pswitch. A centralized middlebox controller monitors the liveness of middleboxes and keeps the pswitches informed of failures. The PLayer achieves requiring minimal infrastructure changes by only requiring switches be replaced, using encapsulation, and being incrementally deployable. It allows the use of unmodified middleboxes and servers by ensuring packets only reach middleboxes and servers in the proper Ethernet format, using only nonintrusive techniques to identify previous hops, and supporting the various middlebox addressing requirements. It supports the use of non-transparent middleboxes, that is, middleboxes that modify frame headers or content, through the use of something called per-segment policies. The PLayer can be enhanced through the use of stateful switches, which store hash tables in order to track the processing of a flow. PLayer guarantees correctness under network, policy, and middlebox churn, as demonstrated in the paper. The end of the paper includes a description of the implementation of pswitches in Click and a validation of the their functionality. It also includes a performance test, and as expected, pswitches achieve less TCP throughput and increased latency, as do middleboxes deployed with them. It concludes with a summary of the limitations of the PLayer. Briefly, these include the introduction of indirect paths since the PLayer directs traffic to off-path middleboxes, difficulty in traffic classification and policy specification, incorrect packet classification when the 5-tuple is insufficient for correct classification, failure of the PLayer if middleboxes are incorrectly wired, the existence of some policies the PLayer cannot support, and the added complexity of pswitches.

Critique

I thought the PLayer seemed like a good idea, and very well-motivated. I don’t think we should have necessarily read this version of the paper, however. Some sections, such as the formal analysis and the appendix, didn’t really add much toward understanding the PLayer, but rather just made the paper an annoyingly long read. With respect to the PLayer itself, it seems that if it could overcome its poor performance when compared to current datacenter switches, it could become pretty competitive. Or, at least the idea of allowing administrators to specify which traffic should traverse which middleboxes in a flexible way requiring minimal changes to existing infrastructure seems like an idea that could be very applicable, and perhaps companies such as Cisco would do well to incorporate some of those ideas into their products.

Understanding TCP Incast Throughput Collapse in Datacenter Networks

Y. Chen, R. Griffith, J. Liu, A. Joseph, R. H. Katz, "Understanding TCP Incast Throughput Collapse in Datacenter Networks," Workshop on Research in Enterprise Networks (WREN'09), (August 2009).

One line summary: This paper examines the problem of TCP incast throughput collapse by attempting to reproduce the results of previous papers and examining in depth the behavior observed, as well as developing a quantitative model that attempts to explain it.

Summary

This paper examines the TCP incast problem and (1) shows that it is a general problem and occurs in a variety of network environments, (2) reproduces the experiments from prior work, and (3) proposes a quantitative model to understand some of the observed behavior. The authors describe the difference between fixed-fragment and variable-fragment workloads used in previous papers. In variable-fragment workloads, the amount of data sent by each sender decreases as the number of senders increases. They justify their use of a fixed-fragment workload as being more representative. They perform their experiments in two different test environments, avoiding the use of simulation. They first step is to verify that the incast problem can be replicated, which they do. They then test a number of modifications, including decreasing the minimum TCP RTO, randomizing the minimum TCP RTO, setting a smaller multiplier for the RTO exponential backoff, and randomizing the multiplier value. Their results suggested that reducing the minimum TCP RTO value was the most helpful modification, while the majority of the other modifications were unhelpful.

They performed experiments in which they used a fixed-fragment workload for different minimum RTO values, varying the number of senders and measuring goodput. They found that there are three regions of interest in the resulting graph: (1) the initial goodput collapse, (2) goodput increase, and (3) another region of slower goodput decrease. They then did a similar experiment only in this case they tested different RTOs with and without delayed ACKs enabled. Unlike in previous papers by other researchers, they found that disabling ACKs resulted in suboptimal behavior. They hypothesize that this is because disabling ACKs causes the TCP congestion window to be over-driven, and examine some internal TCP state variables to verify that this hypothesis is correct. They also conclude that this sub-optimal behavior is independent of type of workload. The results for their experiments were very different from the results in previous papers. They conclude that this is in part due to the difference in workloads (fixed-fragment versus variable-fragment), but also due to the difference in the network test environments.

They propose a simple quantitative model to describe the behavior in the case of the delayed ACK enabled, low-resolution timer using the fixed-fragment workload. It comes close to describing the observed behavior for the 200ms minimum RTO timer. However, their model does not come as close for the lower 1ms minimum RTO timer. Their model reveals that the goodput is affected by both the minimum RTO value and also the inter-packet wait times between packet transmissions, and that for larger RTO values, reducing the value helps, but for smaller RTO values, controlling the inter-packet wait time is important. The authors provide a number of refinements to their model which they use to explain several details observed in the graphs from their earlier experiments.

Critique

There are many things I appreciated about this paper. At first I thought it was going to be redundant and not contribute much beyond what they paper we read before this did, but it is clear that the authors’ comparison of their results with the results from the previous paper revealed a lot of interesting things. This paper brings up a lot of points regarding important details and influencing factors that were not examined in the previous paper and that weren’t immediately obvious from reading the previous paper. It was just nice to see them try to reproduce the previous experiments and results from the earlier paper; I don’t think I’ve seen that elsewhere even though it seems like it would be good to make this standard practice.

I’m not sure I completely buy some of their explanations in this paper but I appreciate that they tried to explain the behavior they observed so thoroughly. For instance, I’m not sure their possible explanation for why randomizing the minimum and initial RTO values is unhelpful, but that could very likely be because I don’t understand it. One other thing that is not clear to me is if when they examined enabling delayed ACKs, if they adjusted the delayed ACK timer so that it wasn’t the default 40ms, or if they left it alone. I wonder if they would have drawn other conclusions had they tried adjusting the delayed ACK timer along with the minimum RTO timer. I thought their attempt at a model was an impressive undertaking but I’m not so sure the results of this attempt were very good.

Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

V. Vasudevan, A. Phanishayee, H. Shah, E. Krevat, D. G. Andersen, G. R. Ganger, G. A. Gibson, B. Mueller, "Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication," ACM SIGCOMM Conference, (August 2009).

One line summary: This paper suggests reducing or eliminating the minimum RTO and enabling fine-grained RTT and RTO measurement and calculation on the order microseconds as a way of eliminating the problem of TCP incast collapse in data centers.

Summary

This paper presents a solution to the TCP incast problem. TCP incast collapse results in severely reduced throughput when multiple senders try to send to a single receiver. The preconditions for TCP incast collapse are: (1) the network must have high bandwidth and low latency with switches that have small buffers, (2) the workload must be a highly parallel barrier synchronization request workload, (3) the servers must return a small amount of data per request (high fan in). An example scenario in which TCP incast collapse occurs is one in which a client sends a request for data that has been partitioned across many servers. The servers all try to respond with their data and overload the client’s buffers. Packets are lost and some servers experience a TCP retransmission timeout (RTO). But the default minimum retransmission timeout is 200ms, so the client must wait at least this long to receive the extra data, even though the client’s link may be idle for most of this waiting time. This results in decreased throughput and link utilization. The authors postulate that in order to prevent TCP incast collapse, the RTO must operate on granularity closer to the RTT of the underlying network, which in datacenters is hundreds of microseconds or less.

The authors demonstrate via a series of simulations and experiments in real clusters that allowing for a minimum RTO on the order of microseconds or eliminating the minimum RTO altogether improves throughput and helps avoid TCP incast collapse. They also experiment with desynchronizing retransmissions by adding a randomizing component. They advocate such desychronization in data centers but note that it is likely unnecessary in the wide-area since different flows have different RTTs and thus different RTOs. The authors explain that it is not enough to lower the minimum RTO but that it is also necessary to enable measurement and computation of the RTT and RTO on a fine-grained level as well. They describe their implementation of fine-grained RTT and RTO computation using Linux high-resolution timers. This involved making modifications to the kernel and the TCP stack.

The authors then discuss whether eliminating the minimum RTO and allowing microsecond retransmissions is appropriate for the wide-area or if such techniques should be limited to the data center. They note two potential conflicts: spurious retransmissions when the network RTT suddenly spikes, and delayed ACKs acting as an additional timeout mechanism in certain situations because the delayed ACK timer is set higher than the RTO. They argue that problems arising from these conflicts don’t occur often and are mitigated by newer TCP features. They perform some wide-area experiments to test this claim and find that spurious retransmissions aren’t an issue and while better performance can be achieved by disabling delayed ACKS, leaving them enabled and with a high timer only slightly harms performance.

Critique

I liked this paper and I think it should remain on the syllabus. I don’t have many criticisms, although I did find it strange that in their wide-area experiments, two different servers experienced almost the exact same distribution of flows. This suggests that something funny might be going on with those experiments. I thought the proposed solution in this paper was good, it would be perfect if enabling fine-grained RTT and RTO measurements and calculation didn’t require special kernel hacking. Perhaps in the future the OS will automatically provide such capabilities. In the meantime, I thought their suggestion of setting the minimum RTO to the lowest value possible was at least a nice practical idea. I also liked how they did both simulations and experiments on a real cluster.

VL2: A Scalable and Flexible Data Center Network

A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, S. Sengupta, "VL2: A Scalable and Flexible Data Center Network," ACM SIGCOMM 2009, (August 2009).

One line summary: This paper presents VL2, a data center network architecture that provides layer 2 semantics, high capacity, and performance isolation between services using flat addressing, Valiant Load Balancing, and a directory service for mappings, and runs over a Clos topology.

Summary

This paper presents a data center network architecture called VL2. The goals of VL2 are to achieve uniform high capacity, performance isolation between services, layer 2 semantics, as well as agility (the ability to assign any server to any service). VL2 is built from low cost switches arranged into a Clos topology and uses Valiant Load Balancing (VLB) to spread traffic across available paths and adapt to volatility in traffic and failure patterns. The authors of the paper first conduct a data center traffic analysis by implementing a data center that supports data mining. From this their major findings were that (1) the majority of flows are small, (2) the number of concurrent flows through a machine is around ten more than half the time, (3) the variability in traffic patterns is not easily summarized and there are a large number of representative traffic matrices, (4) traffic patterns change nearly constantly and unpredictably, (5) most failures are small in size, and (6) the main causes of downtimes are network misconfigurations, firmware bugs, and faulty components, and there is no obvious way to eliminate failures from the top of the data center topology hierarchy.

Briefly, VL2 operates as follows. VL2 is built on a Clos network topology. It uses two different kinds of addresses: location specific IP addresses (LAs) and application specific IP addresses (AAs). All switches and interfaces have LAs. Each server has an AA that remains the same no matter where the application is located and is assigned when the server is provisioned to a service. All servers within a service believe they are in the same subnet. The AA of a server is associated with the LA of the ToR switch to which the server is connected. Switches run a link-state routing protocol using these LAs. In performing routing, VL2 uses VLB to distribute traffic across intermediate switches and ECMP to distribute across equal cost paths. There is a VL2 agent at each server that encapsulates packets emanating from the servers within a packet that has the LA address of the destination ToR in the header. A directory service stores AA-LA-MAC address mappings. The directory service consists of a number of read-optimized directory services that cache AA-LA mappings and a smaller number of write-optimized replicated state machine servers that reliably store AA-LA mappings. The directory service performs lookups, updates, and reactive cache updates.

The authors perform an evaluation of VL2, which serves to demonstrate that VL2 provides uniform high capacity, VLB fairness, performance isolation, convergence after link failures, and has a directory service that is scalable and resilient, with high availability and throughput. Of these experiments, I thought the most interesting was the one where they performed an all-to-all data shuffle stress test to show VL2 achieves high utilization and fairness between flows.

Critique

In terms of criticisms, here are several notes I made about this paper:

I liked that before designing VL2 they did an analysis of data center traffic. The results of this were somewhat surprising to me so I found them interesting. However, for this analysis, the authors instrumented a data mining workload, but it’s probably not the case that a data mining workload is representative of most traffic in data centers in general.

I didn’t understand why they exclude UDP traffic from consideration in their evaluations, in which they only use TCP flows, not UDP flows. I don’t know if this is realistic. They make some hand wavy claim that techniques such as STCP to make UDP “TCP friendly” are well known and can be used, but I am not convinced it is really that easy. Also in their evaluations, they state that they rely on TCP to ensure that each flow is rate limited to its fair share of the bottleneck, but many of the previous papers we read suggest that TCP is not very good at fairness. Another thing is that in their evaluation using data shuffle, they claim that a conventional design would take 11x longer but they don’t explain where they got their figures. Also, they claim several times throughout the paper that agility is a big goal for VL2 but they don’t do an experiment to show what happens when a server is migrated, as was done in the PortLand paper. I don’t think that by agility they necessarily mean ease of VM migration but perhaps this still would have been interesting to examine.

Some miscellaneous points are that in one part of the paper, they claim that that VL2 enables fine-grained path control by adjusting the randomization used in VLB but they don’t elaborate further on this. Also the performance of VL2 appears to depend on traffic obeying the hose model. I don’t know what the hose model is, but is it safe to assume all data center traffic will obey the hose model?

A general point not just about this paper in particular but about all of these papers on data center networks is that it seems that every paper only uses evaluations that highlight the good features of the solution suggested in that paper, so it is hard to compare solutions. It would be nice if there were at least some standard experiments or similar experiments that could facilitate comparison, analogous to the sets of benchmarks used for processors in architecture.

PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric

R. N. Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, A. Vahdat, "PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric", ACM SIGCOMM, (August 2009).

One line summary: This paper presents PortLand, a layer 2 network fabric consisting of a set of Ethernet-compatible routing and addressing protocols tailored for data centers with multi-rooted tree topologies.

Summary

This paper presents PortLand, a network fabric for data centers with layer 2 semantics. The goals of PortLand are that it be scalable, easy to manage, flexible, fault-tolerant, and that it support virtual machine migration. The authors motivate their approach by first describing the problems with traditional Ethernet-, LAN-, and VLAN-based solutions. These problems are essentially the same ones that were mentioned in the SEATTLE paper, so refer to the SEATTLE post below for a discussion of them. One main difference between PortLand and other data center network fabric solutions is that PortLand is designed for use over a specific topology, the fat tree or similar multi-rooted tree topologies. Central in the design of PortLand is the fabric manager (FM), which maintains soft state about network configuration information such as topology. Also key is that in PortLand, each end host has a pseudo-MAC (PMAC) address, of which the hosts are unaware, that encodes the hosts’ location in the topology. These PMACs are mapped to the hosts’ actual MAC (AMAC) address.

Forwarding in PortLand is done using PMACs and host-connected edge switches perform the AMAC to PMAC header rewriting so that the hosts remain unaware of the PMACs. AMAC-PMAC-IP address mappings are maintained in the FM, which responds with this information to ARP requests that are unicast to it from the edge switches. This special handling of ARP messages is called proxy-based ARP in the paper. Switches learn of their location in the topology using the Location Discovery Protocol (LDP), which requires no administrator configuration. After the switches establish their location, they use updates from their neighbor switches to populate their forwarding tables. Forwarding in PortLand is provably loop-free (by observing up-down semantics – if a packet is forwarded down a layer in the topology it shouldn’t be forwarded back up). Multicast groups in PortLand are mapped to core switches using a hash function, and all multicast packets are forwarded to the core switch the group is hashed to. The FM is responsible for installing the proper forwarding state in core and aggregation routers to ensure that every host in a multicast group receives multicast packets for that group. LDP also provides switch failure detection and failure recovery is aided by the FM, which tracks the state of switches.

The authors conclude by evaluating PortLand in a testbed of 20 4-port switches and 16 end hosts. They measure the time for convergence for UDP flows in the presence of link failures as well as for TCP flows. They also measure multicast convergence when a link to a core switch fails. They measure scalability and VM migration as well. In all these experiments, they evaluate PortLand alone without comparing it to other solutions.

Critique

I didn't really like this paper. One thing I didn't like is that the authors claim that they restrict the amount of centralized knowledge in PortLand but they never explain what happens when the central FM goes down. They discuss several fault cases but not one that deals with this. Clearly if the FM were down this would be catastrophic, so you would think they would address this. Also, they claim that the FM is amenable to a distributed realization but they don’t elaborate on this so it is not very convincing. Also, the FM doesn’t seem very scalable, especially if they don’t distribute it somehow. Distributing the FM seems like it would be more complicated to do than they admit.

I also was struck by how often they mentioned special failure cases. Maybe this is always the case for these kinds of systems and other papers just don’t emphasize it like the authors do here, but having so many cases where PortLand could fail and special measures need to be taken makes it seem kind of fragile.

Another obvious criticism is that PortLand isn’t applicable to general topologies; they assume that the fat-tree or a similar topology is the obvious best one, so in some sense their solution depends on this assumption remaining true. Also, they mention at one point that their implementation uses a separate control network for communication between the FM and the switches. I feel like they should have been more upfront about this, and perhaps evaluated PortLand without the separate control network as well.

I also thought that the authors were slightly unfair and misleading in their description of SEATTLE. They make a lot of criticisms of SEATTLE and TRILL but they don’t compare PortLand to them in their experiments. While a direct comparison might have been difficult for many reasons, it would have been nice if they had at least attempted to do similar experiments as done in the SEATTLE and TRILL papers. It doesn’t seem fair that they didn’t.

One thing that is good about PortLand is that, as the authors claim, it is implementable using existing hardware and software, although maybe that’s true of most of the alternatives as well.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises

C. Kim, M. Caesar, J. Rexford, "Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises," ACM SIGCOMM Conference, (August 2008).

One line summary: This paper describes SEATTLE, an Ethernet-based architecture for use as a building block in large enterprise networks that uses a DHT to provide the same functionality as conventional Ethernet, but in a scalable and easy-to-administer way.

Summary

This paper discusses an alternative Ethernet-based protocol for use as a network building block in enterprise and access provider networks called SEATTLE. It is motivated by the observation that despite it’s usefulness especially concerning its plug-and-play semantics, conventional Ethernet scales poorly and has several limitations. (1) It disseminates every host’s location globally using flooding, resulting in high control overhead and large forwarding table sizes, (2) it forces paths to make up a spanning tree, constraining route selection, and (3) bootstrapping protocols such as ARP and DHCP rely on broadcasts for frequent and basic operations, degrading network performance. One alternative that attempts to address some of the problems with Ethernet is to decompose the network into multiple LANs interconnected by IP routing. The disadvantages of this approach include (1) configuration overhead due to hierarchical addressing and difficulty in maintaining consistency between routers and DCHP servers, (2) complexity in implementing network policies, since these are often based on the IP prefix of a host, which is subject to change, and (3) limited support for host mobility, making it difficult for hosts to move from one subnet to another. An additional approach that uses virtual LANs (VLANs) instead of LANS is used to address these deficiencies in turn, however, it too has its limitations. These include (1) overhead in configuring trunks – deciding which bridges should be in a given VLAN must often be done manually, (2) large forwarding table entries on bridges in multiple VLANs, and (3) a single spanning tree in each VLAN limits route selection and requires manual rebalancing and updating to adjust to shifts in network load.

SEATTLE in turn addresses all of these problems. It maintains MAC-IP and MAC-location mappings using a one-hop DHT. This information is hashed onto switches using consistent hashing to reduce re-hashing overhead when a switch fails and keys must be remapped. Among switches, a link-state routing protocol allows routing between switches along the shortest path. SEATTLE allows for the creation of virtual switches for load balancing i.e. more powerful switches can have more virtual switches and thus a higher load. Also, the DHT can be used to store information about various network services or attributes, such as printers and servers, by hashing a descriptor of that service along with its location or other information. SEATTLE can also be configured to use a multi-level one-hop DHT to run over hierarchical networks with several regions connected by backbones. In this case, separate regional and backbone hash rings are maintained. SEATTLE is backwards compatible with end hosts using conventional Ethernet. SEATTLE also allows for the definition of groups, which is defined as a set of hosts that share the same broadcast domain. This is important for backward compatibility with conventional Ethernet and also facilitates the implementation of reachability policies.

The paper then provides results of several simulations using four topologies that the authors consider representative. They measure SEATTLE’s sensitivity to cache eviction timeouts, network changes, host mobility, switch failure, the forwarding table size, its control overhead, and compare it with other approaches. They describe a prototype implementation of SEATTLE.

Critique

I liked this paper. There was quite a bit of time between me reading it and writing the summary so I can’t remember specific criticisms or points I wanted to make about it. They did a good job of explaining what was wrong with current solutions and I liked how they addressed each of these problems. One thing that confused me in their simulations is that they said they leveraged real network traces and supplemented them with synthetic traces, but I must not understand fully how these are used because it seems like once you have a different building block (SEATTLE in place of Ethernet) that alters the trace so a sequence of events in the original trace might no longer make sense if you are assuming you are using SEATTLE instead. One thing I liked about their simulations is that, unlike in many of the other papers we’ve read, at least their simulation networks were big. I feel like a lot of other experiments that use topologies with only a handful of hosts are not as interesting, although in many cases there is probably nothing wrong with evaluating in this way.