Skilled in the Art of Being Idle: Reducing Energy Waste in Networked Systems

S. Nedevschi, J. Chandrashekar, J. Liu, B. Nordman, S. Ratnasamy, N. Taft, "Skilled in the Art of Being Idle: Reducing Energy Waste in Networked Systems," NSDI'09, (April 2009).

One line summary: This paper examines the value of using proxies to handle idle-time traffic for sleeping hosts with the goal of reducing wasted energy consumption in networked end-systems; it does this by analyzing and classifying traffic to see what can be ignored or automatically handled and by examining several potential proxy designs.

Summary

This paper examines the problem of reducing wasted energy consumption in powered-on but idle networked end-systems such as desktops in home and office environments. It discusses various solutions, and in particular examines the value of using a proxy to handle idle-time traffic on behalf of sleeping hosts. The main problem is that while vendors have built in hardware support for sleep (S-states) to reduce power consumption while idle, surveys of office buildings indicate that the vast majority of machines are fully on while idle, instead of taking advantage of these sleep states. One reason for this is that a sleeping machine loses its network presence i.e. it cannot send or receive network messages, and another reason is that users or administers occasionally want to be able to schedule tasks to run during these idle times. Both of these reasons cause users to not make use of sleep states. This paper thus tries to answer the following questions: (1) Is the problem worth solving? (2) What network traffic do idle machines see? (3) What is the design space for a proxy? (4) What implications does proxying have for future protocol and system design.

To begin to answer these questions, the authors first collect network and user-level activity traces from 250 client machines belonging to Intel employees and attempt to classify the traffic. They first classify each packet as being either broadcast, multicast, or unicast, then whether it is incoming or outgoing. They find outgoing traffic tends to be dominated by unicast while incoming traffic is made of significant proportions of all three. They estimate the potential for sleep in four scenarios: (a) ignore broadcast and wake for the rest, (b) ignore multicast and wake for the rest, (c) ignore both broadcast and multicast, and (d) wake for all packets. They find that broadcast and multicast are mainly responsible for reducing the amount of potential sleep time and that doing away with just one of broadcast or multicast is not effective. The authors next classify the traffic based on protocol type, and evaluate each protocol on two metrics: total volume of traffic, and something the authors call half-sleep time. A high half-sleep time means that protocol’s packets could be handled by waking the machine up, whereas a low half-sleep time means that to achieve useful amounts of potential sleep time the proxy would have to handle them. They find that the bulk of broadcast traffic is for address resolution and service discovery, and a lot of other broadcast traffic is from router-specific protocols. Broadcast traffic allows for very little sleep in the office, but significantly more in the home. A proxy could easily handle most of these broadcast protocols. Multicast traffic is mostly caused by router protocols and is often absent or extremely reduced in homes as compared to offices. All router traffic is ignorable. From their analysis of unicast traffic, they speculate that it might be possible to ignore or eliminate much of unicast traffic. Finally, they classify traffic into one of the following three categories regarding the need to proxy that traffic: don’t wake, don’t ignore, and policy-dependent, and into one of the following three categories regarding the difficulty in proxying that traffic: ignorable/drop, handle via mechanical responses, and require specialized processing.

Next, they present four proxy designs. The first ignores all traffic classified as ignorable and wakes the host for the rest. The second ignores all traffic classified as ignorable, responds to traffic listed as capable of being handled by mechanical responses, and wakes the machine for the rest. The third does the same as the second except that it wakes up for traffic belonging to a certain set and drops any other incoming traffic. Lastly, the fourth does the same as the third except that it also wakes up for a certain set of scheduled tasks. They find that the simplest proxy, proxy 1, is inadequate for office environments and nearly inadequate for home environments, but that proxy 3 achieves a good amount of sleep time in all scenarios – more than 70% of the idle time. They also find that the effectiveness of proxy 2 depends a great deal on the environment. Given this, the best trade-off between complexity of design and power savings depends on the environment. Also, the authors also note that since scheduled wake-ups are infrequent, the impact on sleep is minimal, so proxy 4 performs practically the same as proxy 3. Finally, they offer a basic proxy architecture that could serve as a framework to building the different proxies designs they considered, and to demonstrate the feasibility of building a proxy, they implemented a simple proxy prototype in Click. The authors end by speculating about how systems could be redesigned to make them more power-aware, thereby simplifying the implementation of proxies, making proxies more effective, or eliminating the need for proxies altogether.

Critique

One thing I really liked about this paper is how the authors analyzed and classified network traffic before considering proxy design. In retrospect it seems absolutely necessary to guiding the design of a proxy. It was also just informative in general to look at the traffic traces from the perspective of which packets are ignorable, which can be handled automatically, and which are actually “important”. I also liked how they examined several points in the proxy design space and compared them. Overall I thought this was a very thoughtful and well organized paper and I think it should stay in the syllabus.

Detailed Diagnosis in Enterprise Networks

S. Kandula, R. Mahajan, P. Verkaik, S. Agarwal, J. Padhye, P. Bahl, "Detailed Diagnosis in Enterprise Networks," ACM SIGCOMM Conference, (August 2009).

One line summary: This paper presents NetMedic, a diagnostic system for enterprise networks that uses network history to infer causes of faults without application specific knowledge by representing components as a directed graph and reasoning over this structure; this paper shows NetMedic is able to pinpoint fault causes with relative specificity compared to previous diagnostic systems.

Summary

This paper describes a diagnostic system for enterprise networks called NetMedic. NetMedic approaches the problem of diagnosing faults as one of inference. The goal of NetMedic is to build a system that can identify the likely causes of a fault with as much specificity as possible and to do so with minimal application specific knowledge. It does this by modeling the network as a dependency graph and then using history to detect abnormalities and likely causes. The nodes of this graph are network components such as application processes, machines, and configurations, and network paths. There is a directed edge from a node A to a node B if A impacts B, and the weight of this edge represents the magnitude of this impact. Each component has a state consisting of many variables. The abnormality of a component at a given time is determined and used to compute the edge weights. The authors describe various extensions to make this process more robust to large and diverse sets of variables. After these weights are obtained, causes are ranked such that more likely causes have lower ranks.

The authors implement NetMedic on the Windows platform, using Windows Performance Counter framework for their source of data. They claim to be developing a prototype for Linux as well. They evaluate NetMedic in comparison to a course diagnosis method loosely based on previous methods. They evaluate in a live environment and a controlled environment, but it is unclear how realistic even the live environment is, as they inject the faults they are trying to detect. In one of their evaluations, for 80% of the faults the median rank of the true cause is 1 in NetMedic, meaning NetMedic correctly identifies the culprit in these cases. They also demonstrate the benefit of their extensions by comparing them with a version of NetMedic that has application specific information hand coded in it. Their extensions perform well in this comparison. They also study how NetMedic does when diagnosing two simultaneous faults and study the impact of the length of history used.

Critique

This paper was interesting to read. After reading the first section or two the first question that comes to mind is how they manage without knowing application specific details, because it is pretty obvious that this method isn’t workable in the general case. They have a clever way of getting around this in the analysis phase but then they do admit that in the data collection phase of their experiments they do utilize application specific information about where configuration data is stored, though they claim to be working on a way to get around this. There is one part in the section on implementation where they talk about how they handle some counters differently from others because they represent cumulative values and it made me wonder how they determine which counters fall into this category. Does that not count as having application specific information? They talk about automatically detecting cumulative variables earlier in the paper when discussing their extensions, such as aggregate relationships across variables, but the example they give with the counter (number of exceptions a process has experienced) doesn’t seem to fall into the same category as those discussed in the extension section.

Since NetMedic would be used by network administrators and you can imagine that some things about a network stay the same all the time (such as what kind of applications are running) it might be interesting to see how NetMedic could be enhanced if administrators had the option of providing some application specific details, and if there are ways NetMedic could leverage this. I’m not really sure how or if that would work, but it is something to consider.

I wasn’t particularly impressed by their evaluation. It would be more compelling if they had more data from real-world situations instead of constructed situations with injected faults. It might have been informative too if they had shown some results measuring metrics other than the rank of the correct cause, although I can’t think of another metric off the top of my head. Also, they compared their system against another that was “loosely based” on systems such as Sherlock and Score, and they don’t really discuss that system much, so it seems a bit questionable as to whether this is a fair comparison. Lastly, their evaluation in which they show NetMedic identifies a virus scanning program or sync utility as abnormal doesn’t seem like something to brag about. I’m not sure I understand this section or why this is a good thing, since presumably virus scanning is an acceptable activity. In this section, they claim to be showing how NetMedic can help with naturally occurring faults, but I’m not sure they actually accomplish that. I could be just entirely misunderstanding this section.

It might potentially be interesting to explore using variables as nodes in the graph instead of just the components. This could probably make it much harder to scale though. It would also be interesting to see how NetMedic performs when a fault is due to a confluence of factors and not just one culprit alone.

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.