We formulate the problem of performing optimal data compression under the constraints that compressed data can be used for accurate classification in machine learning. We show that this translates to a problem of minimizing the mutual information between data and its compressed version under the constraint on error probability of classification is small when using the compressed data for machine learning. We then provide analytical and computational methods to characterize the optimal trade-off between data compression and classification error probability. First, we provide an analytical characterization for the optimal compression strategy for data with binary labels. Second, for data with multiple labels, we formulate a set of convex optimization problems to characterize the optimal tradeoff, from which the optimal trade-off between the classification error and compression efficiency can be obtained by numerically solving the formulated optimization problems. We further show the improvement of our formulations over the information-bottleneck methods in classification performance.

Network coding allows distributed information sources such as sensors to efficiently compress and transmit data to distributed receivers across a bandwidth-limited network. Classical network coding is largely task-agnostic – the coding schemes mainly aim to faithfully reconstruct data at the receivers, regardless of what ultimate task the received data is used for. In this paper, we analyze a new task-driven network coding problem, where distributed receivers pass transmitted data through machine learning (ML) tasks, which provides an opportunity to improve efficiency by transmitting salient task-relevant data representations. Specifically, we formulate a task-aware network coding problem over a butterfly network in real-coordinate space, where lossy analog compression through principal component analysis (PCA) can be applied. A lower bound for the total loss function for the formulated problem is given, and necessary and sufficient conditions for achieving this lower bound are also provided. We introduce ML algorithms to solve the problem in the general case, and our evaluation demonstrates the effectiveness of task-aware network coding on distributed image classification tasks on MNIST, CIFAR10, CIFAR100, and satellite imagery datasets.

Motivated by the need to accelerate bulk transfers (i.e., flows which transfer files with large sizes) over WAN enterprise networks, we present OSBulk, a system which optimizes sparse bulk transfers over a given network. OSBulk allocates bandwidth to bulk transfers according to an optimal solution to any given multi-commodity flow (MCF) formulation. The key components of OSBulk include logical network provision which sets flow rates and Multiple Path Protocol (MPP) which specifies flow paths. OSBulk can dynamically react to varying network conditions by logical network reprovision and MPP reconfiguration. Evaluation demonstrates that OSBulk is able to achieve near optimal throughput, which improves over the performance of TCP and MPTCP by 1.1 - 2.1× in cloud testing.

Local differential privacy (LDP) can be adopted to anonymize richer user data attributes that will be input to sophisticated machine learning (ML) tasks. However, today’s LDP approaches are largely task-agnostic and often lead to severe performance loss – they simply inject noise to all data attributes according to a given privacy budget, regardless of what features are most relevant for the ultimate task. In this paper, we address how to significantly improve the ultimate task performance with multi-dimensional user data by considering a task-aware privacy preservation problem. The key idea is to use an encoder-decoder framework to learn (and anonymize) a task-relevant latent representation of user data. We obtain an analytical near-optimal solution for the linear setting with mean-squared error (MSE) task loss. We also provide an approximate solution through a gradient-based learning algorithm for general nonlinear cases. Extensive experiments demonstrate that our task-aware approach significantly improves ultimate task accuracy compared to standard benchmark LDP approaches with the same level of privacy guarantee.

Local differential privacy (LDP) is a state-of-the-art technique for privacy preservation. In this paper, we provide upper bounds for mutual information, a common information-theoretic metric, under pure LDP and approximate LDP constraints. Compared to existing results, our results have the advantage of holding for any discrete distribution and any privacy budget, and are tighter over some regions of the distribution and privacy budget.

Sharing forecasts of network timeseries data, such as cellular or electricity load patterns, can improve independent control applications ranging from traffic scheduling to power generation. Typically, forecasts are designed without knowledge of a downstream controller's task objective, and thus simply optimize for mean prediction error. However, such task-agnostic representations are often too large to stream over a communication network and do not emphasize salient temporal features for cooperative control. This paper presents a solution to learn succinct, highly-compressed forecasts that are co-designed with a modular controller's task objective. Our simulations with real cellular, Internet-of-Things (IoT), and electricity load data show we can improve a model predictive controller's performance by at least 25% while transmitting 80% less data than the competing method. Further, we present theoretical compression results for a networked variant of the classical linear quadratic regulator (LQR) control problem.

Collaborative filtering (CF) is one of the most effective approaches for recommender systems by exploiting user-item behavior interactions. However, in real applications, the rating matrix is usually sparse, causing a poor performance. Numerous CF methods tend to incorporate the side information for the enrichment of priors. Cross-domain recommendation is an alternative to alleviate these two problems by referring to the knowledge of relevant domains. Due to the sparsity of the ratings and side information, the resulting latent factors might not be effective as expected. In this paper, we incorporate both the side information and deep knowledge transfer in CF models. A general architecture of deep transfer collaborative filtering with geometry preservation (DTCFGP) is proposed by integrating cross-domain collective matrix factorization, deep feature learning and the graph modeling. We exhibit a instantiations of our architecture by employing non-negative matrix tri-factorization and stacked denoising autoencoder (SDAE) in both source and target domains, where the common latent factors are taken as a bridge between domains due to its across-domain stability and data geometric structure is evaluated by using a nearest neighbor graph modeling. Extensive experiments on various real-world datasets demonstrate the effectiveness of our proposed approach in comparison to state-of-the-art approaches.

Multivariate time series forecasting has attracted wide attention in areas, such as system, traffic, and finance. The difficulty of the task lies in that traditional methods fail to capture complicated non-linear dependencies between time steps and between multiple time series. Recently, recurrent neural network and attention mechanism have been used to model periodic temporal patterns across multiple time steps. However, these models fit not well for time series with dynamic-period patterns or nonperiodic patterns. In this paper, we propose a dual self-attention network (DSANet) for highly efficient multivariate time series forecasting, especially for dynamic-period or nonperiodic series. DSANet completely dispenses with recurrence and utilizes two parallel convolutional components, called global temporal convolution and local temporal convolution, to capture complex mixtures of global and local temporal patterns. Moreover, DSANet employs a self-attention module to model dependencies between multiple series. To further improve the robustness, DSANet also integrates a traditional autoregressive linear model in parallel to the non-linear neural network. Experiments on real-world multivariate time series data show that the proposed model is effective and outperforms baselines.

Time series prediction plays a key role in wide applications and has been investigated for a couple of decades. Nevertheless, most of the prior works fail to identify the most effective frequency components of time series before passing through the prediction, which induces the drop of the performance. In this paper, we propose a novel predictor which integrates the sequence to sequence (seq2seq) model based on long short-term memory units (LSTM) with interpretable data reconstruction, where the learned hidden state is taken as a bridge. The reconstructor can effectively regularize data based on the learned frequency components and extract the effective components of time series. Moreover, we present an alternative training mechanism and a dedicated loss function to guarantee the success of prediction. Experimental results on extensive real-world datasets show a prominent superiority in comparison to state-of-the-art methods.

Software-defined networks (SDNs) facilitate more efficient routing of traffic flows using centralized network view. On the other hand, traditional distributed routing still enjoys the advantage of better scalability, robustness, and swift reaction to events such as failure. There are therefore significant potential benefits to adopt a hybrid operation where both distributed and centralized routing mechanisms co-exist. This hybrid operation however imposes a new challenge to network stability since a poor and inconsistent design can lead to repeated route switching when the two control mechanisms take turns to adjust the routes. In this paper, we discuss ways of solving the stability problem. We first define stability for hybrid SDNs and then establish a per-priority stabilizing framework to obtain stable routing patterns. For each priority class, we discuss three approaches to reach hybrid SDN stability: global optimization, greedy, and local search. It is argued that the proposed local search provides the best tradeoff among cost performance, computational complexity, and route disturbance. Furthermore, we design a system on a centralized controller, which utilizes those algorithms to stabilize the network. The design is implemented and extensively tested by simulations using realistic network information, including a trace of the Abilene network and data from a tier-1 Internet service providers backbone network.

WANs are often over-provisioned to accommodate worst-case operating conditions, with many links typically running at only around 30% capacity. In this paper, we show that in-network congestion management can play an important role in increasing network utilization. To mitigate the effects of in-network congestion caused by rapid variations in traffic demand, we propose using high-frequency traffic control (HFTraC) algorithms that exchange real-time flow rate and buffer occupancy information between routers to dynamically coordinate their link-service rates. We show that the design of such dynamic link-service rate policies can be cast as a distributed optimal control problem that allows us to systematically explore an enlarged design space of in-network congestion management algorithms. This also provides a means of quantitatively comparing different controller architectures: we show, perhaps surprisingly, that centralized control is not always better. We implement and evaluate HFTraC in the face of rapidly varying UDP and TCP flows and in combination with AQM algorithms. Using a custom experimental testbed, a Mininet emulator, and a production WAN, we show that HFTraC leads to up to 66% decreases in packet loss rates at high link utilizations as compared to FIFO policies.

This paper studies routing performance loss due to traffic split ratio granularity constraints. For any given fineness of traffic splitting capability, we provide upper bounds on the loss of performance. Based on tight convex relaxation, we further develop an efficient approximation algorithm to compute a good routing solution that satisfies given constraints on traffic splitting. The results can be useful for network operators to trade-off between attainable performance and implementation overhead. Some of the mathematical techniques developed here can be of independent interest for studying other similar nonconvex optimization problems.

Many network flows nowadays, especially in a data center environment, have associated deadlines by which they must be fully transmitted. Nevertheless, traditional transport protocols such as TCP, focus on concepts like throughput and fairness, and do not aim to satisfy flow deadlines. Motivated by this limitation, several alternative transport designs and solutions have been recently proposed. These approaches generally achieve a better performance in terms of the number of satisfied deadlines and are usually built upon various heuristics. In contrast to these previous works, this article approaches the problem directly from an optimization perspective. We first prove that the problem belongs to the class of NP-hard problems that do not even admit a constant ratio approximation solution (unless P=NP), and formulate it as a mixed integer-linear optimization program. Then, using linear programming approximations, we further develop offline and online optimization-based rate control algorithms to approach the problem. Flow-level simulation results indicate that the proposed algorithms can be near-optimal, and hence they can be served as benchmarks against which other solutions to this problem can be evaluated. We additionally performed simulations incorporating such real network features as deployment delays and packet-level granularity to evaluate the performance of the proposed algorithms in a more realistic environment.

In this paper, we study network utility maximization over both routing choice and path rate assignment for any given path cardinality constraint. We provide a novel convex relaxation, which leads to a randomized algorithm with performance guarantees. The new relaxation also enables distributed algorithm design and allows us to obtain performance estimation for nonconvex routing optimization problems that is significantly better than previous work based on the multipath routing relaxation. Convergence and performance of the proposed randomized algorithm are characterized theoretically and further illustrated numerically through examples to demonstrate its superiority over existing work.

Hand posture recognition (HPR) is quite a challenging task, due to both the difficulty in detecting and tracking hands with normal cameras and the limitations of traditional manually selected features. In this article, we propose a two-stage HPR system for Sign Language Recognition using a Kinect sensor. In the first stage, we propose an effective algorithm to implement hand detection and tracking. The algorithm incorporates both color and depth information, without specific requirements on uniform-colored or stable background. It can handle the situations in which hands are very close to other parts of the body or hands are not the nearest objects to the camera and allows for occlusion of hands caused by faces or other hands. In the second stage, we apply deep neural networks (DNNs) to automatically learn features from hand posture images that are insensitive to movement, scaling, and rotation. Experiments verify that the proposed system works quickly and accurately and achieves a recognition accuracy as high as 98.12%.

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph$G$with$n$nodes, we derive bounds of the minimum number of measurements needed to recover any$k$-sparse vector over$G$($M^{G}_{k,n}$). Using the Erdős-Rényi random graph as an example, we characterize the dependence of$M^{G}_{k,n}$on the graph structure. This paper suggests that$M^{G}_{k,n}$may serve as a graph connectivity metric.

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our solution achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide explicit necessary and sufficient conditions on the parameters to guarantee synchronization. We then study the effect of noisy measurements (jitter) and frequency drift (wander) on the offsets and synchronization frequency, and further optimize the parameter values to minimize their variance. Our study reveals a few insights, for example, we show that our algorithm can converge even in the presence of timing loops and noise, provided that there is a well-defined leader. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme as it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. The results are supported by experiments running on a cluster of IBM BladeCenter servers with Linux.

We present HALO, the first link-state routing solution with hop-by-hop packet forwarding that minimizes the cost of carrying traffic through packet-switched networks. At each node u, for every other node t, the algorithm independently and iteratively updates the fraction of traffic destined to t that leaves u on each of its outgoing links. At each iteration, the updates are calculated based on the shortest path to each destination as determined by the marginal costs of the network's links. The marginal link costs used to find the shortest paths are in turn obtained from link-state updates that are flooded through the network after each iteration. For stationary input traffic, we prove that HALO converges to the routing assignment that minimizes the cost of the network. Furthermore, we observe that our technique is adaptive, automatically converging to the new optimal routing assignment for quasi-static network changes. We also report numerical and experimental evaluations to confirm our theoretical predictions, explore additional aspects of the solution, and outline a proof-of-concept implementation of HALO.

Active end-to-end available bandwidth estimation is intrusive, expensive, inaccurate, and does not work well with bursty cross traffic or on high capacity links. Yet, it is important for designing high performant networked systems, improving network protocols, building distributed systems, and improving application performance. In this paper, we present minProbe which addresses unsolved issues that have plagued available bandwidth estimation. As a middlebox, minProbe measures and estimates available bandwidth with high-fidelity, minimal-cost, and in userspace; thus, enabling cheaper (virtually no overhead) and more accurate available bandwidth estimation. MinProbe performs accurately on high capacity networks up to 10 Gbps and with bursty cross traffic. We evaluated the performance and accuracy of minProbe over a wide-area network, the National Lambda Rail (NLR), and within our own network testbed. Results indicate that minProbe can estimate available bandwidth with error typically no more than 0.4 Gbps in a 10 Gbps network.

In the network layer, an internet service provider controls the traffic across an autonomous system by load balancing via traffic engineering and by varying the offered traffic of the users via feedback signals. In the transport layer, users send traffic into the network using the TCP protocol, which adjusts offered traffic according to the received feedback. We investigate how feedback and current traffic engineering practice interact with congestion control under the network utility maximization framework. We show that the current interaction is stable, increases network utility, but does not necessarily improve the traffic engineering objective. The mismatch in outcome and incentives prompt us for a more holistic view using game theory. With suitable modification of the feedback, we show that the interaction converges to a socially optimal solution for users running either primal or dual algorithms. We further show that the results hold even when traffic engineering is performed at any irregular intervals. More generally, we show via heterogeneous feedback the same optimality result for a mix of users running primal and dual algorithms.

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our algorithm achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide necessary and sufficient conditions on the parameters to guarantee synchronization. We then implement our solution on a cluster of IBM BladeCenter servers running Linux and study its performance. In particular, both analytically and experimentally, we show that our algorithm can converge in the presence of timing loops. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme. For example, it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. It is also experimentally demonstrated that our algorithm outperforms other well-established software-based solutions such as the NTPv4 and IBM Coordinated Cluster Time (IBM CCT).

Current intra-domain routing protocols like OSPF and IS-IS use link-state routing algorithms with hop-by-hop forwarding that sacrifice traffic engineering performance for ease of implementation and management. Though optimal traffic engineering algorithms exist, they tend to be either not link-state algorithms or to require source routing - characteristics that make them difficult to implement. As the focus of this paper, we introduce HALO, the first optimal link-state routing algorithm with hop-by-hop forwarding, where link weights can be calculated locally. Furthermore, our solution can adapt to changing traffic patterns automatically. The optimality of the algorithm is proved theoretically and also verified numerically.

Network-on-chip (NoC) promises better scalability and power efficiency compared to traditional on-chip interconnects. But in order to fully exploit the benefits offered by the new paradigm, especially as the number of cores in the network increases, challenging resource management questions need to be addressed. Of particular interest and the subject of our study is the question of how to map applications to processors (network nodes) in a NoC so as to minimize the dynamic power consumption of the NoC.

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G (Mk,nG). Our study suggests that Mk,nGmay serve as a graph connectivity metric.

In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with n nodes, it is shown that, using O(k log(n)) path measurements, we are able to recover any k-sparse link vector (with no more than k nonzero elements), even though the measurements have to follow the graph path constraints. We mainly show that the computationally efficient ℓ1minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.

Application-aware routing exploits static knowledge of an application's traffic pattern to improve performance compared to generalpurpose routing algorithms. Unfortunately, traditional approaches to application-aware routing cannot efficiently handle dynamic changes in the traffic pattern limiting its usefulness in practice. In this paper, we study application-aware routing under traffic uncertainty. Our problem formulation allows an application to statically specify an uncertainty set of traffic patterns that each occur with a given probability, and our goal is to find a single set of combined routes that will enable high-performance across all of these traffic patterns. We show how efficient combined routes can be found for this problem using convex optimization. These combined routes are optimal when the performance for every traffic pattern using the combined routes is the same as the performance using routes that are specialized for just that traffic pattern. We derive necessary and sufficient conditions for when our optimization framework will find optimal combined routes. We use theoretical and numerical analysis for the important class of permutation traffic patterns to quantify how often optimal combined routes exist and to determine the performance loss when optimal combined routes are infeasible. Finally, we use a cycle-level simulator that includes realistic pipeline latencies, arbitration, and buffered flow-control to study the latency and throughput of combined routes compared to specialized routes and routes generated using general-purpose routing algorithms. The theoretical analysis, numerical analysis, and simulation results in this paper provide a first step towards more flexible application-aware routing.

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users and sensing and access decisions are undertaken by them in a completely distributed manner. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the sum regret in distributed learning and access, which is the loss in secondary throughput due to learning and distributed access. For the scenario when the number of secondary users is known to the policy, we prove that the total regret is logarithmic in the number of transmission slots. This policy achieves order-optimal regret based on a logarithmic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated at each user through feedback. We propose a policy whose sum regret grows only slightly faster than logarithmic in the number of transmission slots.

It is known that a high-dimensional sparse vector x* in TV can be recovered from low-dimensional measurements y = Ax* where Am×n(mp-minimization (0 ≤ p ≤ 1) as p varies, where ℓp-minimization returns a vector with the least ℓpquasi norm among all the vectors x satisfying Ax = y. Besides analyzing the performance of strong recovery where ℓp-minimization is re quired to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of "weak" recovery of ℓp-minimization (0 ≤ pm/n) → 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via ℓp-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0, 1), while the threshold is 1 for ℓ1-minimization. We also explicitly demonstrate that ℓp-minimization (pp-minimization. For any a G (0.1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which ℓp-minimization succeeds. Our bound of strong recovery improves on the existing bounds when a is large. In particular, regarding the recovery threshold, this paper argues that ℓp-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and ℓp-minimization can outperform ℓp-minimization for weak recovery. These are in contrast to traditional wisdom that ℓp-minimization, though computationally more expensive, always has better sparse recovery ability than ℓ0-minimization since it is closer to ℓ1-minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to un ambiguously confirm and illustrate the theoretical predictions.

This paper studies the performance difference of joint routing and congestion control when either single-path routes or multipath routes are used. Our performance metric is the total utility achieved by jointly optimizing transmission rates using congestion control and paths using source routing. In general, this performance difference is strictly positive and hard to determine-in fact an NP-hard problem. To better estimate this performance gap, we develop analytical bounds to this “cost of not splitting” in routing. We prove that the number of paths needed for optimal multipath routing differs from that of optimal single-path routing by no more than the number of links in the network. We provide a general bound on the performance loss, which is independent of the number of source-destination pairs when the latter is larger than the number of links in a network. We also propose a vertex projection method and combine it with a greedy branch-and-bound algorithm to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique and estimation algorithms.

The problem of cooperative allocation among multiple secondary users to maximize cognitive system throughput is considered. The channel availability statistics are initially unknown to the secondary users and are learnt via sensing samples. Two distributed learning and allocation schemes which maximize the cognitive system throughput or equivalently minimize the total regret in distributed learning and allocation are proposed. The first scheme assumes minimal prior information in terms of pre-allocated ranks for secondary users while the second scheme is fully distributed and assumes no such prior information. The two schemes have sum regret which is provably logarithmic in the number of sensing time slots. A lower bound is derived for any learning scheme which is asymptotically logarithmic in the number of slots. Hence, our schemes achieve asymptotic order optimality in terms of regret in distributed learning and allocation.

An unknown vector f in Rncan be recovered from corrupted measurements y = Af + e where Am×n(m ≥ n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0p-norm" of y-Ax. We give sharp thresholds of the fraction of errors that is recoverable. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is 2/3 for all p in (0, 1), and 1 for p = 1.

In this paper, we investigate the uniqueness of positive semidefinite matrix solution to compressed linear observations. We show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. It is further shown, through concentration of measure phenomenon and sphere covering arguments, that a randomly generated Gaussian linear compressed observations operator will satisfy this necessary and sufficient condition with overwhelmingly large probability.

ℓ1minimization, also called Basis Pursuit, has been known to have strong sparse recovery performance both theoretically and empirically. Previously known analytical approaches for ℓ1minimization have limitations in deriving custom stability performance bounds for signals with sparsity (the number of nonzero elements) level beyond the ℓ1weak recovery threshold [6]. In this paper, instead of focusing on the static decoding results of ℓ1minimization, we develop a microscopic analytical approach by studying the dynamics of ℓ1minimization. This approach can give useful characterizations of ℓ1decoding results and lead to new performance bounds on ℓ1decoding error. Contrary to known stability results for ℓ1minimization below the ℓ1weak threshold, we prove that ℓ1minimization decoding errors can experience an explosive growth in terms of the signal tail immediately beyond the ℓ1minimization weak threshold. This new analytical approach is motivated by the applications of analyzing the emerging iterative reweighted ℓ1minimization algorithms.

This paper develops a new model that describes the queueing process of a communication network when data sources use window flow control. The model takes into account the burstiness in sub-round-trip time (RTT) timescales and the instantaneous rate differences of a flow at different links. It is generic and independent of actual source flow control algorithms. Basic properties of the model and its relation to existing work are discussed. In particular, for a general network with multiple links, it is demonstrated that spatial interaction of oscillations allows queue instability to occur even when all flows have the same RTTs and maintain constant windows. The model is used to study the dynamics of delay-based congestion control algorithms. It is found that the ratios of RTTs are critical to the stability of such systems, and previously unknown modes of instability are identified. Packet-level simulations and testbed measurements are provided to verify the model and its predictions.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the current theory based on utility maximization fails to predict the network behavior. The pricing signals can be different types of signals such as packet loss, queueing delay, etc, or different values of the same type of signal such as different ECN marking values based on the same actual link congestion level. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be non-unique, suboptimal and unstable. InTang(“Equilibrium of heterogeneous congestion control: Existence and uniqueness,”IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 824–837, Aug. 2007), existence and uniqueness of equilibrium of heterogeneous protocols are investigated. This paper extends the study with two objectives: analyzing the optimality and stability of such networks and designing control schemes to improve those properties. First, we demonstrate the intricate behavior of a heterogeneous network through simulations and present a framework to help understand its equilibrium properties. Second, we propose a simple source-based algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns by only updating a linear parameter in the sources' algorithms on a slow timescale. It steers a network to the unique optimal equilibrium. The scheme can be deployed incrementally as the existing protocol needs no change and only new protocols need to adopt the slow timescale adaptation.

This paper investigates the network performance loss of using only single-path routing when multiple paths are available. The performance metric is the aggregate utility achieved by the joint optimization of congestion control and routing. As computing the exact loss for a general network topology is NP-hard, we develop analytical bounds on this "cost of not splitting". Our bound is independent of the number of source-destination pairs when the latter one is larger than the number of links in a network. We also propose a vertex projection method and combine it with branch-and-bound to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique.

Peer-to-peer (P2P) file distribution is a scalable way to disseminate content to a wide audience. For a P2P network, one fundamental performance metric is the average time needed to deliver a certain file to all peers, which in general depends on the topology of the network and the scheduling of transmissions. Despite its apparent importance, how to minimize average finish time remains an open question even for a fully- connected network. This is mainly due to the analytical challenges that come with the combinatorial structures of the problem. In this paper, by using the water-filling technique, we determine how each peer should use its capacity to sequentially minimize the file download times in an upload-constrained P2P network. Furthermore, it is argued that this scheduling also potentially minimizes average finish time for the network. This result not only provides fundamental insight to scheduling in such P2P systems, but also can serve as a benchmark to evaluate practical algorithms and illustrate the scalability of P2P networks.

Energy use of computer communication systems has quickly become a vital design consideration. One effective method for reducing energy consumption is dynamic speed scaling, which adapts the processing speed to the current load. This paper studies how to optimally scale speed to balance mean response time and mean energy consumption under processor sharing scheduling. Both bounds and asymptotics for the optimal speed scaling scheme are provided. These results show that a simple scheme that halts when the system is idle and uses a static rate while the system is busy provides nearly the same performance as the optimal dynamic speed scaling. However, the results also highlight that dynamic speed scaling provides at least one key benefit - significantly improved robustness to bursty traffic and mis-estimation of workload parameters.

A novel continuous time fluid flow model of the dynamics of the interaction between ACK-clocking and the link buffer is presented. A fundamental integral equation relating the instantaneous flow rate and the window dynamics is derived. Properties of the model, such as well-posedness and stability, are investigated. Packet level experiments verify that this new model is more accurate than existing models, correctly predicting qualitatively different behaviors, for example when round trip delays are heterogeneous.

This paper studies window flow control focusing on bridging the gap between microscopic factors such as burstiness in sub-RTT timescales, and observable macroscopic properties such as steady state bandwidth sharing and flow level stability. Using new models, we analytically capture notable effects of microscopic behavior on macroscopic quantities. For loss-based protocols, we calculate the loss synchronization rate for different flows and use it to quantitatively explain the unfair bandwidth sharing between paced and unpaced TCP flows. For delay-based protocols, we show that the ratios of round trip delays are critical to the stability of the system. These results deepen the fundamental understanding of congestion control systems. Packet level simulations are used to verify our theoretical claims.

This paper presents a link model which captures the queue dynamics when congestion windows of TCP sources change. By considering both the self-clocking and the link integrator effects, the model is a generalization of existing models and is shown to be more accurate by both open loop and closed loop packet level simulations. It reduces to the known static link model when flows' round trip delays are similar, and approximates the standard integrator link model when the heterogeneity of round trip delays is significant. We then apply this model to the stability analysis of FAST TCP. It is shown that FAST TCP flows over a single link are always linearly stable regardless of delay distribution. This result resolves the notable discrepancy between empirical observations and previous theoretical predictions. The analysis highlights the critical role of self-clocking in TCP stability and the scalability of FAST TCP with respect to delay. The proof technique is new and less conservative than the existing ones.

This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. Then we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of Nash equilibrium and convergence of the best response strategy. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse-engineering TCP and BGP, this paper further advances the recent efforts in reverse-engineering layers 2-4 protocols. In contrast to the TCP reverse-engineering results in earlier literature, MAC reverse-engineering highlights the non-cooperative nature of random access.

When heterogeneous congestion control protocols that react to different pricing signals (e.g. packet loss, queueing delay, ECN marking etc.) share the same network, the current theory based on utility maximization fails to predict the network behavior. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be non-unique, inefficient and unfair. This paper has two objectives. First, we demonstrate the intricate behaviors of a heterogeneous network through simulations and present a rigorous framework to help understand its equilibrium efficiency and fairness properties. By identifying an optimization problem associated with every equilibrium, we show that every equilibrium is Pareto efficient and provide an upper bound on efficiency loss due to pricing heterogeneity. On fairness, we show that intra-protocol fairness is still decided by a utility maximization problem while inter-protocol fairness is the part over which we don't have control. However it is shown that we can achieve any desirable inter-protocol fairness by properly choosing protocol parameters. Second, we propose a simple slow timescale source-based algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns and prove its feasibility. The scheme needs only local information.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium may no longer be interpreted as a solution to the standard utility maximization problem. We prove the existence of equilibrium in general multi-protocol networks under mild assumptions. For almost all networks, the equilibria are locally unique, and finite and odd in number. They cannot all be locally stable unless it is globally unique. Finally, we show that if the price mapping functions that map link prices to effective prices observed by the sources are similar, then global uniqueness is guaranteed.

This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium may no longer be interpreted as a solution to the standard utility maximization problem. We prove the existence of equilibrium under mild assumptions. Then we show that multi-protocol networks whose equilibria are locally non-unique or infinite in number can only form a set of measure zero. Multiple locally unique equilibria can arise in two ways. First, unlike in the single-protocol case, the set of bottleneck links can be non-unique with heterogeneous protocols even when the routing matrix has full row rank. The equilibria associated with different sets of bottleneck links are necessarily distinct. Second, even when there is a unique set of bottleneck links, network equilibrium can still be non-unique, but is always finite and odd in number. They cannot all be locally stable unless it is globally unique. Finally, we provide various sufficient conditions for global uniqueness. Numerical examples are used throughout the paper to illustrate these results.

Layered architecture is one of the most fundamental and influential structures of network design. Can we integrate the various protocol layers into a single coherent theory by regarding them as carrying out an asynchronous distributed primal-dual computation over the network to implicitly solve a global optimization problem? Different layers iterate on different subsets of the decision variables using local information to achieve individual optimalities, but taken together, these local algorithms attempt to achieve a global objective. Such a theory will expose the interconnection between protocol layers and can be used to study rigorously the performance tradeoff in protocol layering as different ways to distribute a centralized computation. In this talk, we describe some preliminary work towards this goal and discuss some of the difficulties of this approach.

This paper describes the tradeoff between fairness criteria of different allocation policies and throughput in a general network. A class of utility functions parameterized by a scalar defines a bandwidth allocation policy. An allocation is fair if the scalar is large and efficient if the aggregate source rate is large. The conjecture depends on the network topology in terms of routing and link capacities. A fairer allocation is always more efficient.

A recently proposed active queue management, CHOKe, is stateless, simple to implement, yet surprisingly effective in protecting TCP from UDP flows. We present an equilibrium model of TCP/CHOKe. We prove that, provided the number of TCP flows is large, the UDP bandwidth share peaks at (e+1)/sup -1/=0.269 when UDP input rate is slightly larger than link capacity, and drops to zero as UDP input rate tends to infinity. We clarify the spatial characteristics of the leaky buffer under CHOKe that produce this throughput behavior. Specifically, we prove that, as UDP input rate increases, even though the total number of UDP packets in the queue increases, their spatial distribution becomes more and more concentrated near the tail of the queue, and drops rapidly to zero toward the head of the queue. In stark contrast to a nonleaky FIFO buffer where UDP bandwidth shares would approach 1 as its input rate increases without bound, under CHOKe, UDP simultaneously maintains a large number of packets in the queue and receives a vanishingly small bandwidth share, the mechanism through which CHOKe protects TCP flows.

In this paper, we investigate how to design AQM with a low-pass filter (average queuing) in supporting TCP based on the well-known AIMD dynamic model sharing a common bottleneck router. Since we formulate the AQM design problem for the given TCP as a state-space model, we get two interesting and important results: (1) we derive PD-type (proportional-derivative) AQM structure is derive in terms of queue length which supports the conjecture in the literature that the AQM RED is not enough to control TCP dynamic behavior, where RED can be classified as P-type AQM structure; (2) we propose a delay-dependent AQM structure to compensate for delays in congestion measure explicitly from the knowledge of RTT, capacity and number of sources, where the previous AQMs RED, REM/PI and AVQ are delay-independent controls. As one trial to obtain stabilizing gains of the proposed structures, we minimize a LQ (linear quadratic) cost of the transients on average-queue length, average-queue length rate, jitter in the rate and the loss probability. Finally, we illustrate the above theoretical results through ns simulations for TCP Reno.

A recently proposed active queue management, CHOKe, is stateless, simple to implement, yet surprisingly effective in protecting TCP from UDP flows. As UDP rate increases, even though the number of UDP packets in the queue rises, its bandwidth share eventually drops to zero, in stark contrast to the behavior of a regular FIFO buffer. We derive a detailed model of CHOKe that accurately predicts this, and other behaviors of CHOKe, and validate the model with simulations. Its key features are the incorporation of the feedback equilibrium of TCP with dropping probability and the spatial characteristics of the queueing process. CHOKe produces a "leaky buffer" where packets can be dropped as they move toward the head of the queue. This leads to a spatially nonuniform distribution of packets and their velocity, and makes it possible for a flow to simultaneously maintain a large number of packets in the queue and receive a vanishingly small bandwidth share. This is the main mechanism through which CHOKe protects TCP from UDP flows.

This paper discussed the spatial or angular spreading properties of wireless propagation in the urban microcell environment, which is of great interests of future mobile technology, especially in case of using smart antennas. Based on the elliptical scattering model, the power azimuth spectrum in microcell environments is derived and it is found that the result approximately followed a truncated Laplacian distribution. The parameter of the Laplacian function is determined by regression. The results can provide insight into the spatial spreading properties of the wireless channel and can be used easily for further research.

A recently proposed active queue management, CHOKe, aims to protect TCP from UDP flows. Simulations have shown that as UDP rate increases, its bandwidth share initially rises but eventually drops. We derive an approximate model of CHOKe and show that, provided the number of TCP flows is large, the UDP bandwidth share peaks at (e+1)-1 = 0.269 when the UDP input rate is slightly larger than the link capacity, and drops to zero as UDP input rate tends to infinity, regardless of the TCP algorithm.