This paper presents Tiga, a new design for geo-replicated and scalable transactional databases such as Google Spanner. Tiga aims to commit transactions within 1 wide-area roundtrip time, or 1 WRTT, for a wide range of scenarios, while maintaining high throughput with minimal computational overhead. Tiga consolidates concurrency control and consensus, completing both strictly serializable execution and consistent replication in a single round. It uses synchronized clocks to proactively order transactions by assigning each a future timestamp at submission. In most cases, transactions arrive at servers before their future timestamps and are serialized according to the designated timestamp, requiring 1 WRTT to commit. In rare cases, transactions are delayed and proactive ordering fails, in which case Tiga falls back to a slow path, committing in 1.5–2 WRTTs. Compared to state-of-the-art solutions, Tiga can commit more transactions at 1-WRTT latency, and incurs much less throughput overhead. Evaluation results show that Tiga outperforms all baselines, achieving 1.3–7.2× higher throughput and 1.4–4.6× lower latency. Tiga is open-sourced at https://github.com/New-Consensus-Concurrency-Control/Tiga.

This paper presents a high-performance consensus protocol, Nezha, which can be deployed by cloud tenants without support from cloud providers. Nezha bridges the gap between protocols such as Multi-Paxos and Raft, which can be readily deployed, and protocols such as NOPaxos and Speculative Paxos, that provide better performance, but require access to technologies such as programmable switches and in-network prioritization, which cloud tenants do not have. Nezha uses a new multicast primitive called deadline-ordered multicast (DOM). DOM uses high-accuracy software clock synchronization to synchronize sender and receiver clocks. Senders tag messages with deadlines in synchronized time; receivers process messages in deadline order, on or after their deadline. We compare Nezha with Multi-Paxos, Fast Paxos, Raft, (optimized) NOPaxos, and 2 recent protocols, Domino and TOQ-EPaxos, that use synchronized clocks. In throughput, Nezha outperforms all baselines by a median of 5.4X (range: 1.9--20.9X). In latency, Nezha outperforms five baselines by a median of 2.3X (range: 1.3--4.0X), with one exception: it sacrifices 33% of latency compared with our optimized NOPaxos in one test. We also prototype two applications, a key-value store and a fair-access stock exchange, on top of Nezha to show that Nezha only modestly reduces their performance relative to an unreplicated system.

Financial exchanges have begun a move from on-premise and custom-engineered datacenters to the public cloud, accelerated by a rush of new investors, the rise of remote work, cost savings from the cloud, and the desire for more resilient infrastructure. While the promise of the cloud is enticing, the cloud's varying network latencies can lead to market unfairness: orders can be processed out of sequence, and market data can be disseminated to market participants at incorrect times due to varying latencies between participants and the exchange. We present CloudEx, a fair-access cloud exchange, which leverages high-precision software clock synchronization to compensate for noisy network conditions in the public cloud. We also discuss refinements to the CloudEx design that were informed by lessons learned from deploying CloudEx in two academic courses and conclude by outlining future research directions.

There is a growing interest in serverless compute, a cloud computing model that automates infrastructure resource- allocation and management while billing customers only for the resources they use. Workloads like stream processing benefit from high elasticity and fine-grain pricing of these serverless frameworks. However, so far, limited concurrency and high latency of server CPUs prohibit many interactive workloads (e.g., web servers and database clients) from taking advantage of serverless compute to achieve high performance.In this paper, we argue that server CPUs are ill-suited to run serverless workloads (i.e., lambdas) and present λ-NIC, an open- source framework, that runs interactive workloads directly on a SmartNIC; more specifically an ASIC-based NIC that consists of a dense grid of Network Processing Unit (NPU) cores. λ- NIC leverages SmartNIC's proximity to the network and a vast array of NPU cores to simultaneously run thousands of lambdas on a single NIC with strict tail-latency guarantees. To ease the development and deployment of lambdas, λ-NIC exposes an event-based programming abstraction, Match+Lambda, and a machine model that allows developers to compose and execute lambdas on SmartNICs easily. Our evaluation shows that λ- NIC achieves up to 880x and 736x improvements in workloads' response latency and throughput, respectively, while significantly reducing host CPU and memory usage.

Conventional distributed data storage services, like databases and file systems, rely on replication for fault tolerance; as a consequence, the performance of these services depends heavily on the performance of the underlying replication system in use. Existing replication systems, built using a replication protocol (e.g., CURP), are implemented as user-level processes capable of performing replication with relatively low latencies (~10+ μs). However, such user-level processes are susceptible to performance degradation at scale, due to software overheads (e.g., operating system and networking stack), and contention for server resources (e.g., CPU, disk, and memory) between multiple processes; thus, leading to higher latencies with longer tails.

Language is dynamic, constantly evolving and adapting with respect to time, domain or topic. The adaptability of language is an active research area, where researchers discover social, cultural and domain-specific changes in language using distributional tools such as word embeddings. In this paper, we introduce the global anchor method for detecting corpus-level language shifts. We show both theoretically and empirically that the global anchor method is equivalent to the alignment method, a widely-used method for comparing word embeddings, in terms of detecting corpus-level language shifts. Despite their equivalence in terms of detection abilities, we demonstrate that the global anchor method is superior in terms of applicability as it can compare embeddings of different dimensionalities. Furthermore, the global anchor method has implementation and parallelization advantages. We show that the global anchor method reveals fine structures in the evolution of language and domain adaptation. When combined with the graph Laplacian technique, the global anchor method recovers the evolution trajectory and domain clustering of disparate text corpora.

We develop two models of highway traffic: (i) a deterministic fluid model based on conservation laws building on previous work and (ii) a mean-field model of a series of infinite server queues, where each stage in the tandem models a segment of highway. The models define the ``highway-map''---a transformation of time-varying arrival rate functions according to which vehicles arrive at the highway to the corresponding departure rate functions of vehicles exiting the highway. The two models are shown to be equivalent in that they obtain the same highway-map. The cost of congestion for vehicles traversing the highway is the total extra time they spend on the highway due to congestion. This cost is shown to be equal to the ``d-bar'' distance between the input and the output rate measures of the highway-map. This fact is used to formulate a convex optimization problem for determining the optimal way to shift users from peak to off-peak hours using incentives so that congestion costs are lowered.

In this paper we present pFabric, a minimalistic datacenter transport design that provides near theoretically optimal flow completion times even at the 99th percentile for short flows, while still minimizing average flow completion time for long flows. Moreover, pFabric delivers this performance with a very simple design that is based on a key conceptual insight: datacenter transport should decouple flow scheduling from rate control. For flow scheduling, packets carry a single priority number set independently by each flow; switches have very small buffers and implement a very simple priority-based scheduling/dropping mechanism. Rate control is also correspondingly simpler; flows start at line rate and throttle back only under high and persistent packet loss. We provide theoretical intuition and show via extensive simulations that the combination of these two simple mechanisms is sufficient to provide near-optimal performance.

In many of the challenges faced by the modern world, from overcrowded transportation systems to overstretched healthcare systems, large benefits for society come about from small changes by very many individuals. We survey the problems and the cost they impose on society, and describe a framework for designing "nudge engines"---algorithms, incentives and technology for influencing human behavior. We present a model for analyzing their effectiveness and results from transportation pilots conducted in Bangalore, at Stanford and in Singapore, and a wellness program for the employees of Accenture-USA.

Engineering large-scale data center applications built from thousands of commodity nodes requires both an underlying network that supports a wide variety of traffic demands, and low latency at microsecond timescales. Many ideas for adding innovative functionality to networks, especially active queue management strategies, require either modifying packets or performing alternative queuing to packets in-flight on the data plane. However, configuring packet queuing, marking, and dropping is challenging, since buffering in commercial switches and routers is not programmable.

We present, pFabric, a minimalistic datacenter fabric design that provides near-optimal performance in terms of completion time for high-priority flows and overall network utilization. pFabric's design eliminates nearly all buffering on switches (switches have only ~20KB of buffering per port), requires almost no congestion control and uses only simple mechanisms at each switch. Specifically, switches are only required to locally and greedily decide what packets to schedule and drop according to priorities in the packet header and do not maintain any flow state or rate estimates. Rate-control is almost unnecessary, all flows start at line-rate and only slow down in the extreme case of congestion collapse. We show via simulations using realistic workloads and topologies that this simple design achieves near optimal flow completion times and network utilization.

Many dynamical networks, such as the ones that produce the collective behavior of social insects, operate without any central control, instead arising from local interactions among individuals. A well-studied example is the formation of recruitment trails in ant colonies, but many ant species do not use pheromone trails. We present a model of the regulation of foraging by harvester ant (Pogonomyrmex barbatus) colonies. This species forages for scattered seeds that one ant can retrieve on its own, so there is no need for spatial information such as pheromone trails that lead ants to specific locations. Previous work shows that colony foraging activity, the rate at which ants go out to search individually for seeds, is regulated in response to current food availability throughout the colony's foraging area. Ants use the rate of brief antennal contacts inside the nest between foragers returning with food and outgoing foragers available to leave the nest on the next foraging trip. Here we present a feedback-based algorithm that captures the main features of data from field experiments in which the rate of returning foragers was manipulated. The algorithm draws on our finding that the distribution of intervals between successive ants returning to the nest is a Poisson process. We fitted the parameter that estimates the effect of each returning forager on the rate at which outgoing foragers leave the nest. We found that correlations between observed rates of returning foragers and simulated rates of outgoing foragers, using our model, were similar to those in the data. Our simple stochastic model shows how the regulation of ant colony foraging can operate without spatial information, describing a process at the level of individual ants that predicts the overall foraging activity of the colony.

Cloud computing, social networking and information networks (for search, news feeds, etc) are driving interest in the deployment of large data centers. TCP is the dominant Layer 3 transport protocol in these networks. However, the operating conditions---very high bandwidth links, low round-trip times, small-buffered switches---and traffic patterns cause TCP to perform very poorly. The Data Center TCP (DCTCP) algorithm has recently been proposed as a TCP variant for data centers and addresses these shortcomings.

Data Center Networks have recently caused much excitement in the industry and in the research community. They represent the convergence of networking, storage, computing and virtualization. This paper is concerned with the Quantized Congestion Notification (QCN) algorithm, developed for Layer 2 congestion management. QCN has recently been standardized as the IEEE 802.1Qau Ethernet Congestion Notification standard.

Cloud data centers host diverse applications, mixing workloads that require small predictable latency with others requiring large sustained throughput. In this environment, today's state-of-the-art TCP protocol falls short. We present measurements of a 6000 server production cluster and reveal impairments that lead to high application latencies, rooted in TCP's demands on the limited buffer space available in data center switches. For example, bandwidth hungry "background" flows build up queues at the switches, and thus impact the performance of latency sensitive "foreground" traffic.

Randomized load balancing greatly improves the sharing of resources in a number of applications while being simple to implement. One model that has been extensively used to study randomized load balancing schemes is the supermarket model. In this model, jobs arrive according to a rate-nλ Poisson process at a bank of n rate-1 exponential server queues. A notable result, due to Vvedenskaya et.al. (1996), showed that when each arriving job is assigned to the shortest of d ≥ 2 randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as n to ∞. This is a substantial improvement over the case d=1, where queue sizes decay exponentially.

A novel counter architecture, called counter braids, has recently been proposed for accurate per-flow measurement on high-speed links. Inspired by sparse random graph codes, counter braids solves two central problems of per-flow measurement: one-to-one flow-to-counter association and large amount of unused counter space. It eliminates the one-to-one association by randomly hashing a flow label to multiple counters and minimizes counter space by incrementally compressing counts as they accumulate. The random hash values are reproduced offline from a list of flow labels, with which flow sizes are decoded using a fast message passing algorithm. The decoding of counter braids introduces the problem of collecting flow labels active in a measurement epoch. An exact solution to this problem is expensive. This paper complements the previous proposal with an approximate flow label collection scheme and a novel error-resilient decoder that decodes despite missing flow labels. The approximate flow label collection detects new flows with variable-length signature counting Bloom filters in SRAM, and stores flow labels in high-density DRAM. It provides a good trade-off between space and accuracy: more than 99 percent of the flows are captured with very little SRAM space. The decoding challenge posed by missing flow labels calls for a new algorithm as the original message passing decoder becomes error-prone. In terms of sparse random graph codes, the problem is equivalent to decoding with graph deficiency, a scenario beyond coding theory. The error-resilient decoder employs a new message passing algorithm that recovers most flow sizes exactly despite graph deficiency. Together, our solution achieves a 10-fold reduction in SRAM space compared to hash-table based implementations, as demonstrated with Internet trace evaluations.

In this extended abstract the authors summarize recent work they have done on the design of a novel counter architecture for estimating flow sizes in high-speed networks, the algorithms and the theory that goes along with it. This note will provide a description of the problem and our approach. It serves as a pointer to papers ([2] and [3]) which cover the design, the algorithms and the theory of Counter Braids in more detail.

Fine-grained network measurement requires routers and switches to update large arrays of counters at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at link speed. This has made accurate per-flow measurement complex and expensive, and motivated approximate methods that detect and measure only the large flows.This paper revisits the problem of accurate per-flow measurement. We present a counter architecture, called Counter Braids, inspired by sparse random graph codes. In a nutshell, Counter Braids compresses while counting. It solves the central problems (counter space and flow-to-counter association) of per-flow measurement by braiding a hierarchy of counters with random graphs. Braiding results in drastic space reduction by sharing counters among flows; and using random graphs generated on-the-fly with hash functions avoids the storage of flow-to-counter association.The Counter Braids architecture is optimal (albeit with a complex decoder) as it achieves the maximum compression rate asymptotically. For implementation, we present a low-complexity message passing decoding algorithm, which can recover flow sizes with essentially zero error. Evaluation on Internet traces demonstrates that almost all flow sizes are recovered exactly with only a few bits of counter space per flow.

The input-queued switch architecture is widely used in Internet routers due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is the scheduling algorithm that decides which packets to transfer from ingress ports to egress ports in a given timeslot. It is desirable that such algorithms be iterative (so as to be pipelineable), distributed (allowing flexibility in hardware implementation) and are able to deliver high performance (in terms of throughput and delay). In practice, implementable algorithms have so far had limited success in combining all of the above properties. For example, the popular iSLIP algorithm is known to perform suboptimally, but it is commercially deployed mainly because it is iterative and distributed. The main contribution of this paper is the design and systematic analysis of two algorithms which, to the best of our knowledge, are the first high-performance iterative and distributed scheduling algorithms with possibility of efficient implementation. We first present an iterative, distributed and low-delay maximal throughput algorithm based on the celebrated "auction algorithm". This algorithm can be seen as a natural extension of iSLIP when queue-size information is allowed to be exchanged. The standard auction algorithm can take an unbounded number of iterations to converge in the worst case. However we show that under admissible Bernoulli i.i.d. traffic, our algorithm takes O(n2) iterations, where n is the number of ingress/egress ports in the switch. Moreover for a switch with finite buffer-size, the algorithm allows for a graceful trade-off between running time and performance, which we verify by representative simulation results. Next, we propose and analyze a throughput-optimal, iterative and distributed scheduling algorithm influenced by Max-product belief propagation. Recently the problem of efficient transmission over multi-hop wireless networks has been formulated as that of finding an appropriate schedule over the grid-graph abstraction of the network. A key feature of the multi-hop wireless transmission problem is that while the communication subgraph is bipartite, the bi-partition is allowed to change in each scheduling epoch. We show that our algorithm can be used to efficiently schedule traffic in multi-hop wireless networks.

A number of algorithms have been proposed in the literature for scheduling CIOQ switches. The algorithms which have been proven to provide strict performance guarantees on delay (via the emulation of an output-queued switch) have been too complicated to implement because they require the exchange of a large amount of information between inputs and outputs. With implementation as our primary focus, we consider scheduling algorithms that are "fully local." This means inputs and outputs must be able to make decisions regarding matchings using only local information (except requests, grants and accepts). This constraint, which is essentially necessary for high-speed implementations, appears too restrictive for designing algorithms which enable the emulation of an output-queued switch. Rather surprisingly, we find a very simple and fully local algorithm FLGS (for fully local Gale-Shapley) which, at a speedup of 2, emulates an output-queued switch implementing a number of different output link scheduling algorithms such as weighted round robin and strict priority. We explore the performance of the algorithm at speedups between 1 and 2 using simulations and find that it partitions the bandwidth nearly as well as an output-queued switch at speedups 1.2 or higher.

Hash tables are a fundamental data structure in many network applications, including route lookups, packet classification and monitoring. Often a part of the data path, they need to operate at wire-speed. However, several associative memory accesses are needed to resolve collisions, making them slower than required. This motivates us to consider minimal perfect hashing schemes, which reduce the number of memory accesses to just 1 and are also space-efficient. Existing perfect hashing algorithms are not tailored for network applications because they take too long to construct and are hard to implement in hardware. This paper introduces a hardware-friendly scheme for minimal perfect hashing, with space requirement approaching 3.7 times the information theoretic lower bound. Our construction is several orders faster than existing perfect hashing schemes. Instead of using the traditional mapping-partitioning-searching methodology, our scheme employs a Bloom filter, which is known for its simplicity and speed. We extend our scheme to the dynamic setting, thus handling insertions and deletions

Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Theta(1/radic(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=Theta(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Theta(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Theta(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of Oscr(1/radic(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=Theta(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Theta(nlogn), which is the delay for throughput of Theta(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.

In Part I of this paper, the optimal throughput-delay tradeoff for static wireless networks was shown to be D(n)=Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this tradeoff captures the essential network dynamics, packets need to scale down with the network size. In this "fluid model, " no buffers are required. Due to this packet scaling, D(n) does not correspond to the average delay per bit. This leads to the question whether the tradeoff remains the same when the packet size is kept constant, which necessitates packet scheduling in the network. In this correspondence, this question is answered in the affirmative by showing that the optimal throughput-delay tradeoff is still D(n)=Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queuing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by devising a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queuing theory for continuous-time networks.

Over the past 10-15 years the area of Network Algorithms has grown from a collection of isolated algorithms and analysis methods into a cohesive body of research and development. The problems in this area are characterized by several requirements, of which speed, scalability and simplicity are the most important. For algorithms designed to operate in high-speed router hardware, there is the additional stringent constraint of low heat dissipation. We overview the development of Network Algorithms, emphasizing algorithms designed for high-speed hardware implementations. Specifically, we describe the algorithms and analysis methods developed for bandwidth partitioning, routing and security applications. We highlight the crucial role of randomization and probabilistic techniques in simplifying the implementation while delivering high performance.

Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.

Many practical systems perform load balancing. The main aim of load balancing is to utilize the capacity of a system of parallel processors efficiently and to reduce the delay of processing jobs. This paper is concerned with load balancing, or process migration, when there is a penalty associated with migration. We consider the following model: jobs arrive at each of n parallel servers. An arriving job can either be processed in a unit of time, on average, at the server where it arrives, or it can migrate to another server where it creates K ges 1 independent jobs. When K = 1, migrating jobs impose no extra cost and this problem is considered extensively in the literature. We are interested in the situation K > 1. The problem is to decide whether a job should migrate or not. On the one hand migration leads to load balancing and hence reduces backlogs. However, it also leads to the creation of extra work and, hence, to a potential loss of throughput. We ask: do there exist simple migration policies that can reduce backlogs while providing the highest throughput? Somewhat surprisingly, we find that policies like "migrate to the least loaded server" are unstable: they cause a loss of throughput. However, we find that a simple variant of this rule is stable and leads to a reduction of backlogs

In previous work (2004), we characterized the optimal throughput-delay trade-off in static wireless networks as D(n) = Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this trade-off captured the essential network dynamics, packets needed to scale down with the network size. In this "fluid model", no buffers were required. Due to this packet scaling, D(n) did not correspond to the average delay per bit. That led to the question whether the trade-off remains the same when the packet size is kept constant, which necessitates buffers and packet scheduling in the network. In this paper, we answer this question in the affirmative by showing that the optimal throughput-delay trade-off is still D(n) = Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queueing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by looking at a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queueing theory for continuous-time networks

As the Internet grows, it is becoming increasingly difficult to collect performance measurements, to monitor its state, and to perform simulations efficiently. This is because the size and the heterogeneity of the Internet makes it time-consuming and difficult to devise traffic models and analytic tools which would allow us to work with summary statistics. We explore a method to side step these problems by combining sampling, modeling, and simulation. Our hypothesis is this: if we take a sample of the input traffic and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original. Our main findings are as follows. When we scale an IP network which is shared by short- and long-lived TCP-like and UDP flows and which is controlled by a variety of active queue management schemes, then performance measures such as queueing delay and drop probability are left virtually unchanged. We show this in theory and in simulations. This makes it possible to capture the performance of large networks quite faithfully using smaller scale replicas.

Network-to-transport signaling is desirable for ensuring efficient resource usage and timely notice of network status. ICMP is the standard way for signaling, but unfortunately it generates extra load and does not traverse firewalls. In this paper, we develop M-ECN, an in-band network-to-transport signaling mechanism, which does not generate any extra packets and does not require dedicated header bits. The key idea is to sneak messages into the stream of ECN bits, but without interfering with ECN congestion signaling. Compared to other alternatives, M-ECN is easy to deploy because routers read/write to the IP header, and the mechanism requires no change to legacy routers along the path which do not participate in the signaling.

Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in a wireless network when the nodes are fixed, and showed that the throughput per source-destination pair is /spl otimes/(1//spl radic/nlogn). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant or /spl otimes/(1) throughput scaling per source-destination pair. The focus of this paper is on characterizing the delay and determining the throughput-delay trade-off in such fixed and mobile ad hoc networks. For the Gupta-Kumar fixed network model, we show that the optimal throughput-delay trade-off is given by D(n) = /spl otimes/(nT(n)), where T(n) and D(n) are the throughput and delay respectively. For the Grossglauser-Tse mobile network model, we show that the delay scales as /spl otimes/(n/sup 1/2//v(n)), where v(n) is the velocity of the mobile nodes. We then describe a scheme that achieves the optimal order of delay for any given throughput. The scheme varies (i) the number of hops, (ii) the transmission range and (iii) the degree of node mobility to achieve the optimal throughput-delay trade-off. The scheme produces a range of models that capture the Gupta-Kumar model at one extreme and the Grossglauser-Tse model at the other. In the course of our work, we recover previous results of Gupta and Kumar, and Grossglauser and Tse using simpler techniques, which might be of a separate interest.

The random network model assumed in this paper is a generalization of the model that incorporates transmission energy consumption. The throughput, delay and energy-per-bit for a communication scheme are related through the scheme's average transmission range, i.e., average hop distance is considered. For mobile networks, the same model with additional feature that each node moves with velocity according to an independent Brownian motion is considered.

Consider the problem of minimizing cost when assigning n jobs to n machines. An assignment is a one-to-one mapping of jobs onto the machines. Assume that the cost of executing job i on machine j is C/sub ij/, i,j = 1,...,n. When the c/sub ij/ are i.i.d. exponentials of mean 1, Parisi conjectured that the average cost of the minimum assignment equals /spl Sigma//sub i=1//sup n/1/i/sup 2/. Recently, the authors, and independently, Linusson and Wastlund, have proved this conjecture. In the above work the authors also made a refined conjecture that, if established, would yield another proof of the Parisi's conjecture. This paper establishes the refined conjecture, thus providing a new proof of Parisi's conjecture.

This note considers an n-letter alphabet in which the ith letter is accessed with probability p/sub i/. The problem is to design efficient algorithms for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector q/sup */=(q/sup *//sub 1/,...,q/sup *//sub n/) in an appropriate convex set, S, so as to minimize the relative entropy D(p/spl par/q) over all q/spl isin/S. Methods from convex optimization give an explicit solution for q/sup */ in terms of p. We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.

Suppose that there are n jobs and n machines and it costs c/sub ij/ to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. The average case analysis of the classical random assignment problem has received a lot of interest in the recent literature, mainly due to the following pleasing conjecture of Parisi: The average value of the minimum-cost permutation in an n /spl times/ n matrix with i.i.d. exp(1) entries equals /spl Sigma//sub i=1//sup n/ 1/(i/sup 2/). D. Coppersmith and G. Sorkin (1999) have generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. We prove both conjectures based on a common set of combinatorial and probabilistic arguments.

In networks and in Web server farms, it is useful to collect performance measurements, to monitor the state of the system, and to perform simulations. However, the sheer volume of traffic in large high-speed network systems makes it hard to monitor their performance or to simulate them efficiently. And the heterogeneity of the Internet means it is time-consuming and difficult to devise the traffic models and analytic tools which would allow us to work with summary statistics. We explore a method to side-step these problems by combining sampling, modeling and simulation. Our hypothesis is this: if we take a sample of the input traffic, and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original. Our main findings are: When we scale an IP network which is shared by TCP-like, UDP and Web flows; and which is controlled by a variety of active queue management schemes, then performance measures such as queueing delay and drop probability are left virtually unchanged. We show this in theory and in simulations. This makes it possible to capture the performance of large networks quite faithfully using smaller scale replicas.

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.

Queueing systems which map Poisson input processes to Poisson output processes have been well-studied in classical queueing theory. This paper considers two discrete-time queues whose analogs in continuous-time possess the Poisson-in-Poisson-out property. It is shown that when packets arriving according to an arbitrary ergodic stationary arrival process are passed through these queueing systems, the corresponding departure process has an entropy rate no less (some times strictly more) than the entropy rate of the arrival process. Some useful by-products are discrete-time versions of: (i) a proof of the celebrated Burke's (1956) theorem, (ii) a proof of the uniqueness, amongst renewal inputs, of the Poisson process as a fixed point for exponential server queues proposed by Anantharam (1993), and (iii) connections with the timing capacity of queues described by Anantharam and Verdu (1996).

A standard load balancing model considers placing n balls into n bins by choosing d possible locations for each ball independently and uniformly at random and sequentially placing each in the least loaded of its chosen bins. It is well known that allowing just a small amount of choice (d = 2) greatly improves performance over random placement (d = 1). In this paper, we show that similar performance gains occur by introducing memory. We focus on the situation where each time a ball is placed, the least loaded of that ball's choices after placement is remembered and used as one of the possible choices for the next ball. For example, we show that when each ball gets just one random choice, but can also choose the best of the last ball's choices, the maximum number of balls in a bin is log log n/2 log /spl phi/ + O(1) with high probability, where /spl phi/ = (1 + /spl radic/5)/2 is the golden ratio. The asymptotic performance is therefore better with one random choice and one choice from memory than with two fresh random choices for each ball; the performance with memory asymptotically matches the asymmetric policy, using two choices introduced by Vocking (1999). More generally, we find that a small amount of memory, like a small amount of choice, can dramatically improve the load balancing performance. We also investigate continuous time variations corresponding to queueing systems, where we find similar results.

The speedup of a switch is the factor by which the switch, and hence the memory used in the switch, runs faster compared to the line rate. In high-speed switches, line rates are already touching the limits at which memory can operate. It is very important for a switch to run at as low a speedup as possible. For an input queued (IQ) switch at speedup 1, 100% throughput can be achieved for any admissible traffic (McKeown, N. et al., 1999; Dai, J. and Prabhakar, B., 2000). This gives finite average delays but does not guarantee control on packet delays. S.T. Chuang et al. (see IEEE J. Selected Areas of Commun., vol.17, no.6, p.1030-9, 1999) show that a combined input output queued (CIOQ) switch can emulate perfectly an output queued (OQ) switch at a speedup of 2 and, thus, control the packet delays. This motivates a study of the possibility of obtaining delay control at speedup less than 2. To guarantee optimal control of delays for a general class of traffic, as shown by Chuang et al., speedup 2 is necessary. Hence, to obtain control of delays at lower speedup, we need to restrict the class of arrival traffic. We study the speedup requirement for a class of admissible traffic, which we denote as (1, nF)-regulated traffic, with parameters n and F. We obtain the necessary speedup for this class of traffic. Further, we present a general class of algorithms working at the necessary speedups and thus providing bounded delays.

The paper explores the adaptation of transmission rate and power jointly to the data generation rate and channel fading, for minimizing transmission energy. The optimal offline adaptation problem is solved, which provides a lower-bound on the transmission energy consumed by any practical, that is, online, scheme. A heuristic online algorithm, look-ahead water-filling, is developed for adapting to the queue state as well as the channel state, and is shown through simulations to achieve transmission energy per packet close to optimal. As the packet arrival rate is varied within known limits, the average energy per packet used by look-ahead water-filling is significantly lower than that achieved by optimal adaptation to the channel only (water-filling in time). The delay per packet is larger, but is almost constant for all data arrival rates. The results can be generalized to multi-access and broadcast fading channels.

High-aggregate bandwidth switches are those whose port count multiplied by the operating line rate is very high; for example, a 30 port switch operating at 40 Gbps or a 1000 port switch operating at 1 Gbps. Designing high-performance schedulers for such switches is challenging for the following reasons: (i) high performance requires finding good matchings; (ii) good matchings take time to find; (iii) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers: (a) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time; (b) observing arriving packets conveys useful information about the state of the switch. These features are exploited using hardware parallelism and randomization to yield three scheduling algorithms for IQ (input-queued) switches - APSARA, LAURA and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite competitive with respect to the maximum weight matching. The stability proof involves a derandomization procedure and uses methods which may have wider applicability.

The paper develops algorithms for minimizing the energy required to transmit packets in a wireless environment. It is motivated by the following observation: In many channel coding schemes it is possible to significantly lower the transmission energy by transmitting packets over a long period of time. Based on this observation, we show that for a variety of scenarios the offline energy-efficient transmission scheduling problem reduces to a convex optimization problem. Unlike for the special case of a single transmitter-receiver pair studied by (see Prabhakar, Uysal-Biyikoglu and El Gamal. Proc. IEEE Infocom 2001), the problem does not, in general, admit a closed-form solution when there are multiple users. By exploiting the special structure of the problem, however, we are able to devise energy-efficient transmission schedules. For the downlink channel, with a single transmitter and multiple receivers, we devise an iterative algorithm, called MoveRight, that yields the optimal offline schedule. The MoveRight algorithm also optimally solves the downlink problem with additional constraints imposed by packet deadlines and finite transmit buffers. For the uplink (or multiaccess) problem MoveRight optimally determines the offline time-sharing schedule. A very efficient online algorithm, called MoveRightExpress, that uses a surprisingly small look-ahead buffer is proposed and is shown to perform competitively with the optimal offline schedule in terms of energy efficiency and delay.

The problem of document replacement in Web caches has received much attention and it has been shown that the eviction rule "replace the least recently used document" performs poorly in Web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size and the cost of fetching a document, leads to a sizable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following observation. With many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering transmission power and code rate and therefore transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to perform closely to the optimal offline schedule. Taking the deadline to infinity, we provide an exact probabilistic analysis of our offline scheduling algorithm. The results of this analysis enable us to devise a lazy online algorithm that varies transmission times according to backlog. We show that this lazy schedule is significantly more energy-efficient compared to a deterministic (fixed transmission time) schedule that guarantees queue stability for the same range of arrival rates.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following key observation: in many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering the transmission power and transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to be energy-efficient. Finally, we relax the deadline constraint and provide an exact probabilistic analysis of our offline scheduling algorithm. We then devise a lazy online algorithm that varies transmission times according to backlog and show that it is more energy efficient than a deterministic schedule that guarantees stability for the same range of arrival rates.

The problem of document replacement in Web caches has received much attention in the literature research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in Web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizeable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M

We explore the problem of sharing network resources when agents' preferences lead to temporally concentrated, inefficient use of the network. In such cases, external incentives must be supplied to smooth out demand. Taking a game-theoretic approach, we consider a setting in which bandwidth is available during several time slots at a fixed cost, but all agents have a natural preference for choosing the same slot. We present four mechanisms that motivate agents to distribute load optimally by probabilistically waiving the cost for each time slot, and analyze equilibria.

In this paper we use fluid model techniques to establish two results concerning the throughput of data switches. For an input-queued switch (with no speedup) we show that a maximum weight algorithm for connecting inputs and outputs delivers a throughput of 100%, and for combined input- and output-queued switches that run at a speedup of 2 we show that any maximal matching algorithm delivers a throughput of 100%. The only assumptions on the input traffic are that it satisfies the strong law of large numbers and that it does not oversubscribe any input or any output.

The problem of route address lookup has received much attention recently and several algorithms and data structures for performing address lookups at high speeds have been proposed. In this paper we consider one such data structure-a binary search tree built on the intervals created by the routing table prefixes. We wish to exploit the difference in the probabilities with which the various leaves of the tree (where the intervals are stored) are accessed by incoming packets in order to speedup the lookup process. More precisely, we seek an answer to the question: How can the search tree be drawn so as to minimize the average packet lookup time while keeping the worst-case lookup time within a fixed bound?" We use ideas from information theory to derive efficient algorithms for computing near-optimal routing lookup trees. Finally, we consider the practicality of our algorithms through analysis and simulation.

We investigate the problem of providing a fair bandwidth allocation to each of n flows that share the outgoing link of a congested router. The buffer at the outgoing link is a simple FIFO, shared by packets belonging to the n flows. We devise a simple packet dropping scheme, called CHOKe, that discriminates against the flows which submit more packets per second than is allowed by their fair share. By doing this, the scheme aims to approximate the fair queueing policy. Since it is stateless and easy to implement, CHOKe controls unresponsive or misbehaving flows with a minimum overhead.

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars, instead of shared memory systems; and QoS can be provided using WFQ-based packet scheduling. However, until now, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing, or centralized shared memory. This paper demonstrates that a combined input output queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet scheduling algorithms, including WFQ and strict priorities. More precisely, we show that a "speedup" of 2 is sufficient, and a speedup of 2-1/N is necessary, for this exact emulation. We introduce a variety of algorithms that configure the crossbar so that emulation is achieved with a speedup of two, and consider their running time and implementation complexity. An interesting feature of our work is that the exact emulation holds for all input traffic patterns. We believe that, in the future, these results will make possible the support of QoS in very high bandwidth routers.

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N/spl times/N switch, a "speedup" of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies.

We design a scheduler for an M/spl times/N input-queued multicast switch. It is assumed that: 1) each input maintains a single queue for arriving multicast cells and 2) only the cell at the head of line (HOL) can be observed and scheduled at one time. The scheduler needs to be: 1) work-conserving (no output port may be idle as long as there is an input cell destined to it) and 2) fair (which means that no input cell may be held at HOL for more than a fixed number of cell times). The aim is to find a work-conserving, fair policy that delivers maximum throughput and minimizes input queue latency, and yet is simple to implement. When a scheduling policy decides which cells to schedule, contention may require that it leave a residue of cells to be scheduled in the next cell time. The selection of where to place the residue uniquely defines the scheduling policy. Subject to a fairness constraint, we argue that a policy which always concentrates the residue on as few inputs as possible generally outperforms all other policies. We find that there is a tradeoff among concentration of residue (for high throughput), strictness of fairness (to prevent starvation), and implementational simplicity (for the design of high-speed switches). By mapping the general multicast switching problem onto a variation of the popular block-packing game Tetris, we are able to analyze various scheduling policies which possess these attributes in different proportions. We present a novel scheduling policy, called TATRA, which performs extremely well and is strict in fairness. We also present a simple weight-based algorithm, called WBA.

We consider policies for scheduling cells in an input-queued multicast (ATM) switch. It is assumed that each input maintains a single queue for arriving multicast cells and that only the cell at the head of line (HOL) can be observed and scheduled at one time. The policies are assumed to be work-conserving, which means that cells may be copied to the outputs that they request over several cell times. When a scheduling policy decides which cells to schedule, contention may require that it leave a residue of cells to be scheduled in the next cell time. The selection of where to place the residue uniquely defines the scheduling policy. We prove that for a 2/spl times/N switch, a policy that always concentrates the residue, subject to a natural fairness constraint, always outperforms all other policies. Simulation results indicate that this policy also performs well for more general M/spl times/N switches. We present a heuristic round-robin policy called mRRM that is simple to implement in hardware, fair and performs almost as well as the concentrating policy.