Due to increasing circuit densities and data throughput rates, power consumption has become a significant concern in the design and operation of high-performance packet switches. We extend the idea of Dynamic Power Management (DPM) to input queued switches, allowing operators to tradeoff power and delay in a useful way. We frame the problem as a dynamic program and solve a relaxation using techniques from Linear Quadratic Regulation (LQR). This optimal policy is combined with existing, nonpower-aware switch controls to generate two novel scheduling algorithms: 1) LQR Power Aware Maximum Weight Matching (LQR PA MWM) and 2) LQR Power Aware Projective Cone Scheduling (LQR PA PCS). Simulation results suggest that our algorithms result in significant power savings compared to MWM and previous power control schemes with little performance degradation.

Previous work has proposed the Dynamic Switch Buffer Management (DSBM) scheme, a promising approach for improving the scalability of switch ingress memories. In this paper, we extend these results by adding increased backlog awareness into the latter. In particular, we propose using a novel combination of two backlog-aware algorithms: BA-DSBM to map incoming packets to the switch's ingress buffers and the Backlog-Aware Wrapped Wavefront Arbiter (BA-WWFA) to set the configuration of the switch fabric. We then simulate these algorithms under a variety of load intensities and types. These simulations suggest that adding backlog-awareness into the DSBM scheme leads to significant performance enhancements, particularly as the switch is "stressed" by asymmetric or heavy loading. Our algorithms, therefore, mitigate some of the design tradeoffs made in this novel, highly-scalable switch design.

In this paper we propose two advanced algorithms which allow for both differentiated quality-of-service (QOS) and power conservation in input-queued packet switches. These algorithms are based on two core ideas: first, we assume that the switch can operate in a number of operational speed modes; a higher speed mode serves more packets per time slot at the cost of higher power consumption. Second, each virtual output queue may tolerate a certain low backlog which is called a target in this setting. Thus, one can control power by adjusting the speed mode and QOS by setting the targets appropriately. We first survey previous work to provide the necessary background behind our approach. We then describe our algorithms and evaluate their performance experimentally through simulation. Our preliminary results show that these new procedures offer significant performance gains compared to existing approaches.

We present a practical, market-based solution to the resource provisioning problem in a set of heterogeneous resource clusters. We focus on provisioning rather than immediate scheduling decisions to allow users to change long-term job specifications based on market feedback. Users enter bids to purchase quotas, or bundles of resources for long-term use. These requests are mapped into a simulated clock auction which determines uniform, fair resource prices that balance supply and demand. The reserve prices for resources sold by the operator in this auction are set based on current utilization, thus guiding the users as they set their bids towards under-utilized resources. By running these auctions at regular time intervals, prices fluctuate like those in a real-world economy and provide motivation for users to engineer systems that can best take advantage of available resources. These ideas were implemented in an experimental resource market at Google. Our preliminary results demonstrate an efficient transition of users from more congested resource pools to less congested resources. The disparate engineering costs for users to reconfigure their jobs to run on less expensive resource pools was evidenced by the large price premiums some users were willing to pay for more expensive resources. The final resource allocations illustrated how this framework can lead to significant, beneficial changes in user behavior, reducing the excessive shortages and surpluses of more traditional allocation methods.

In various settings, such as when customers use the same passwords at several independent web sites, security decisions by one organization may have a significant impact on the security of another. We develop a model for security decision-making in such settings, using a variation of linear influence networks. The linear influence model uses a matrix to represent linear dependence between security investment at one organization and resulting security at another, and utility functions to measure the overall benefit to each organization. A simple matrix condition implies the existence and uniqueness of Nash equilibria, which can be reached by a natural iterative algorithm. A free-riding index, expressible using quantities computed in this model, measures the degree to which one organization can potentially reduce its security investment and benefit from investments of others. We apply this framework to investigate three examples: web site security with shared passwords, customer education against phishing and identity theft, and anti-spam email filters. While we do not have sufficient quantitative data to draw quantitative conclusions about any of these situations, the model provides qualitative information about each example.

Many data center devices, for instance packet switches, can be modeled within the context of resource constrained queueing systems. In this paper, we define a novel algorithm class which simultaneously addresses three significant concerns in the operation of such systems: stability, differentiated QOS, and power control. This class, which we refer to as target/power projective cone scheduling (TP-PCS), encapsulates many previously studied algorithms as special cases. At the same time, however, it is broad enough to include a rich set of other, potentially superior control procedures. In the first part of our paper, we explain our model as well as some previously studied approaches to scheduling in these systems. We then define TP-PCS, show how it relates to the former algorithms, and discuss how members of this class can be tailored to control for both power and QOS. Finally, we test some instances of TP-PCS on a simulated, input-queued switch. These show that a wide variety of operating modes are possible by adjusting various scheduling parameters. Hence, TP-PCS opens up for exploration a large set of new controls for packet switches and other systems operating in the queueing space.

A novel architecture was proposed in [1] to address scalability issues in large, high speed packet switches. The architecture proposed in [1], namely OBIG (output buffers with input groups), distributes the switch fabric across multiple chips, which communicate via high speed interconnects enabled by proximity communication (PC), a recently developed circuit technology [2]. An OBIG switch aggregates multiple input flows inside the switch fabric, thereby significantly reducing the amount of memory required for internal buffers, vis-a-vis a conventional buffered crossbar, which has buffers at every crosspoint. Thus, the OBIG architecture is promising for realizing terabit switches with hundreds of ports. This paper studies packet scheduling algorithms which help realize the potential of OBIG-like switch architectures. The emphasis here is on designing backlog aware scheduling algorithms, while ensuring desirable traits such as low computational complexity and scalability. The efficacy of the proposed scheduling algorithms with respect to performance metrics such as average delay and fairness is demonstrated via simulations under a variety of scenarios.

In this paper, we explore two novel scheduling algorithms which allow for both differentiated quality-of-service (QOS) and power conservation in input-queued packet switches. At their core is the idea of a backlog target which represents the delay sensitivity of each input/output port combination. The first algorithm, target-based projective cone scheduling (T- PCS), incorporates these targets into the well-studied projective cone scheduling algorithm, a generalized form of maximum weight matching (MWM). The second algorithm, average backlog scheduling(ABS), uses a 'memory window' to push average backlogs towards their targets. We explain the intuition behind each of these and then show, through simulation, that both exhibit high performance in terms of managing power and QOS, while simultaneously addressing these two key concerns in switches.

In this paper, we examine the wireless network power control problem. We first consider two approaches that have evolved in parallel, catering to distinct concerns: (a) a distributed approach with convergence to 'hard' SIR targets, introduced by Foschini and Miljanic [1] and (b) an incentive- based, game theoretic approach, investigated by Saraydar, Man- dayam, and Goodman [2] among others. We then seek to reconcile these two approaches and explore the rich space in between by formulating a utility-based model in which users have 'soft' SIR targets. We prove that, under certain cost conditions, a Nash Equilibrium of the resulting game is identical to the convergence point of the Foschini-Miljanic (FM) algorithm. Thus, one can use the latter in an incentive-compatible way. If these conditions are not met, however, then the system necessarily will operate at a non-FM point, i.e. one in which some SIR targets are not attained. We propose an algorithm for this case and show by simulation that the resulting Nash points may have desirable power efficiency properties. Thus, under our model, the network can be either aligned or not aligned with the FM scheme, each of which potentially has its advantages.

High power dissipation in packet switches and routers is fast turning into a key problem, owing to increasing line speeds and decreasing chip sizes. To address this issue, we introduce and develop the notion of a power-managed input-queued (PMIQ) switch in this paper. A PMIQ switch is an input-queued switch with an additional hierarchy of control to regulate the power dissipated by the switch. We formulate the joint scheduling and power management problem for a PMIQ switch as a dynamic program (DP). Leveraging intuition gained from provable structural properties of the optimal solution to the DP, we propose the power-aware switch scheduling (PASS) switch management policy. PASS dynamically selects the rate/speed at which the switch operates, in conjunction with the switch configuration, as a function of the backlogs of the input buffers. PASS can easily be tuned to tradeoff high power consumption for larger queuing delays. Experimental results show that PASS yields an attractive power-delay tradeoff relative to the benchmark maximum weight matching (MWM) scheduler. The low computational complexity of PASS makes it amenable to implementation in large, high-speed switches.