Scheduling deadline-constrained packets in multi-hop networks has received increased attention recently. However, there is very limited work on this problem for wireless networks where links are subject to interference. The existing algorithms either provide approximation ratio guarantees, which diminish in quality as parameters of the network scale, or hold in an asymptotic regime when the time horizon, network bandwidth, and packet arrival rates are scaled to infinity, which limits their practicality. While attaining a constant approximation ratio has been shown to be impossible in the worst-case traffic setting, it is unclear if the same holds under stochastic traffic, in a non-asymptotic setting. In this work, we show that, in the stochastic traffic setting, a constant approximation ratio or near-optimal algorithms can be achieved. Specifically, we propose algorithms that attain$\Omega ((1-\epsilon )/\beta )$or$\Omega (1-\epsilon )$fraction of the optimal value, when the number of channels is$\mathrm{C}= \Omega ( \frac{\log (L/\epsilon )}{\epsilon ^{2}})$or$\mathrm{C}= \Omega (\frac{\chi ^{\star }\log (L/\epsilon )}{\epsilon ^{2}})$, respectively, where$L$is the maximum route length of packets,$\chi ^\star$is the fractional chromatic number of the network interference graph, and$\beta$is its interference degree. This marks the first near-optimal results under non-trivial traffic and bandwidth assumptions in a non-asymptotic regime.

We propose a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget. In each round, the algorithm selects a distribution source to sample from for data collection and updates the model parameters accordingly. The objective is to find the model parameters that minimize the expected loss across all the data sources. Our approach integrates upper-confidence-bound (UCB) sampling with online gradient descent (OGD) to dynamically collect and annotate data from multiple sources. By bridging online optimization and multi-armed bandits, we provide theoretical guarantees for our UCB-OGD approach, demonstrating that it achieves a minimax regret of $O(T^{\frac{1}{2}}(K\ln T)^{\frac{1}{2}})$ over $K$ data sources after $T$ rounds. We further provide a lower bound showing that the result is optimal up to a $\ln T$ factor. Extensive evaluations on standard datasets and a real-world testbed for object detection in smart-city intersections validate the consistent performance improvements of our method compared to baselines such as random sampling and various active learning methods.

This paper introduces PAVE (Pedestrian Awareness Via Edge analytics), a scalable real-time video analytics system that uses street cameras to enhance pedestrian safety while preserving their privacy. PAVE processes live camera streams on an edge server to track pedestrians and vehicles in real-time, predict vehicles' trajectories, and identify danger zones where pedestrians are present. The coordinates of these zones are sent to pedestrians' mobile devices via a custom iOS app, which locally determines if they are at risk without sharing any data with the edge server, hence preserving privacy. Moreover, anonymized metadata, including real-time location and speed/direction of pedestrians and vehicles, are visualized on a public map. PAVE's effectiveness was validated through deployment on the NSF COSMOS testbed, processing live video from cameras in diverse urban environments. Live field tests show that PAVE can alert at-risk pedestrians ~0.9 s before a vehicle reaches them. Through extensive profiling, we show that optimizing memory/compute configuration per pipeline stage can reduce latency by up to 10× compared to the default operating system configurations.

We showcase the workflow of PAVE (Pedestrian Awareness Via Edge analytics), a scalable system for real-time video analytics that leverages street cameras to improve pedestrians' safety while maintaining their privacy. PAVE distributes computation across edge servers and end-user mobile devices. Cameras' live streams are processed at the edge to forecast vehicles' trajectories and detect danger zones. Pedestrians' mobile devices then locally determine if the user is inside a danger zone and trigger timely alerts via a custom iOS app. In addition, anonymized metadata, such as pedestrian and vehicle positions, speeds, and directions, are aggregated and displayed on a public map for broader situational awareness. We evaluated PAVE's performance through implementation on the NSF COSMOS testbed's edge server while processing real-time video stream from cameras in diverse urban environments. Live field tests at an intersection in New York City show that PAVE can alert at-risk pedestrians about 0.9 s before a vehicle reaches them. With low-latency cameras, this lead time extends to around 1.6 s which is within the 1–2 s window pedestrians typically need to react.

Interactive visualization interfaces enable users to efficiently explore, analyze, and make sense of their datasets. However, as data grows in size, it becomes increasingly challenging to build data interfaces that meet the interface designer's desired latency expectations and resource constraints. Cloud DBMSs, while optimized for scalability, often fail to meet latency expectations, necessitating complex, bespoke query execution and optimization techniques for data interfaces. This involves manually navigating a huge optimization space that is sensitive to interface design and resource constraints, such as client vs server data and compute placement, choosing which computations are done offline vs online, and selecting from a large library of visualization-optimized data structures. This paper advocates for a Physical Visualization Design (PVD) tool that decouples interface design from system design to provide design independence. Given an interfaces underlying data flow, interactions with latency expectations, and resource constraints, PVD checks if the interface is feasible and, if so, proposes and instantiates a middleware architecture spanning the client, server, and cloud DBMS that meets the expectations. To this end, this paper presents Jade, the first prototype PVD tool that enables design independence. Jade proposes an intermediate representation called Diffplans to represent the data flows, develops cost estimation models that trade off between latency guarantees and plan feasibility, and implements an optimization framework to search for the middleware architecture that meets the guarantees. We evaluate Jade on six representative data interfaces as compared to Mosaic and Azure SQL database. We find Jade supports a wider range of interfaces, makes better use of available resources, and can meet a wider range of data, latency, and resource conditions.

We consider scheduling deadline-constrained packets in multihop wireless networks. Packets with arbitrary deadlines and weights arrive at and are destined to different nodes. The goal is to design online admission, routing, and scheduling algorithms in order to maximize the cumulative weight of packets that reach their destinations within their deadlines. Under a general interference graph model of the wireless network, we provide online algorithms that are$(\gamma ,\mathrm {R})$-competitive, i.e., they achieve at least$1/\gamma $fraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor$\mathrm {R}\geq 1$. In particular, our algorithm can achieve$\gamma =O({\psi }^{\star } \log (\Delta \rho L)/\mathrm {R})$when$\mathrm {R}\mathrm {C} = \Omega ({\psi }^{\star } \log (\Delta \rho L))$, where$\rho $is the ratio of maximum weight to minimum weight of packets,Lis the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here,$\Delta $is themaximum degreeand$ {\psi }^{\star } $is thelocal clique cover numberof the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks,$ {\psi }^{\star } =2$, and in the case of wired networks (no interference),$ {\psi }^{\star } =1$. We further provide lower bounds that show that our results are asymptotically optimal in many settings. Finally, we present extensive simulations that show our algorithms provide significant improvement over the prior approaches.

We consider decentralized learning over a network of workers with heterogeneous datasets, in the presence of Byzantine workers. Byzantine workers may transmit arbitrary or malicious values to neighboring workers, leading to degradation in overall performance. The heterogeneous nature of the training data across various workers complicates the identification and mitigation of Byzantine workers. To address this complex problem, we introduce a resilient decentralized learning approach that combines the gradient descent algorithm with a novel robust aggregator. Specifically, we propose a remove-then-clip aggregator, whereby each benign worker meticulously filters the neighbors' values and subsequently projects the remaining values to a sphere centered at its local value, with an appropriately selected radius. We prove that our proposed method converges to a neighborhood of a stationary point for non-convex objectives under standard assumptions. Furthermore, empirical evaluations are provided to demonstrate the superior performance of our method in comparison to existing algorithms, under various Byzantine attack models.

Scheduling deadline-constrained packets in multihop networks has received increased attention recently. However, there is very limited work on this problem for wireless networks where links are subject to interference. The existing algorithms either provide approximation ratio guarantees which diminish in quality as parameters of the network scale, or hold in an asymptotic regime when the time horizon, network bandwidth, and packet arrival rates are scaled to infinity, which limits their practicality. While attaining a constant approximation ratio has been shown to be impossible in the worst-case traffic setting, it is unclear if the same holds under stochastic traffic, in a non-asymptotic setting. In this work, we show that, in the stochastic traffic setting, constant approximation ratio or near-optimal algorithms can be achieved. Specifically, we propose algorithms that attain Ω((1 − ϵ)/β) or Ω(1 − ϵ) fraction of the optimal value, when the number of channels is ${\text{C}} = \Omega \left( {\frac{{\log (L/\varepsilon )}}{{{\varepsilon ^2}}}} \right)$ or ${\text{C}} = \Omega \left( {\frac{{{\chi ^ \star }\log (L/\varepsilon )}}{{{\varepsilon ^3}}}} \right)$respectively, where L is the maximum route length of packets, χ⋆is the fractional chromatic number of the network’s interference graph, and β is its interference degree. This marks the first near-optimal results under nontrivial traffic and bandwidth assumptions in a non-asymptotic regime.

Recent advances in Visual Language Models (VLMs) have significantly enhanced video analytics. VLMs capture complex visual and textual connections. While Convolutional Neural Networks (CNNs) excel in spatial pattern recognition, VLMs provide a global context, making them ideal for tasks like complex incidents and anomaly detection. However, VLMs are much more computationally intensive, posing challenges for large-scale and real-time applications. This paper introduces EdgeCloudAI, a scalable system integrating VLMs and CNNs through edge-cloud computing. Edge-CloudAI performs initial video processing (e.g., CNN) on edge devices and offloads deeper analysis (e.g., VLM) to the cloud, optimizing resource use and reducing latency. We have deployed EdgeCloudAI on the NSF COSMOS testbed in NYC. In this demo, we will demonstrate EdgeCloudAI's performance in detecting user-defined incidents in real-time.

Blind and low-vision (BLV) people rely on GPS-based systems for outdoor navigation. GPS’s inaccuracy, however, causes them to veer off track, run into obstacles, and struggle to reach precise destinations. While prior work has made precise navigation possible indoors via hardware installations, enabling this outdoors remains a challenge. Interestingly, many outdoor environments are already instrumented with hardware such as street cameras. In this work, we explore the idea of repurposing existing street cameras for outdoor navigation. Our community-driven approach considers both technical and sociotechnical concerns through engagements with various stakeholders: BLV users, residents, business owners, and Community Board leadership. The resulting system, StreetNav, processes a camera’s video feed using computer vision and gives BLV pedestrians real-time navigation assistance. Our evaluations show that StreetNav guides users more precisely than GPS, but its technical performance is sensitive to environmental occlusions and distance from the camera. We discuss future implications for deploying such systems at scale.

Social distancing is an effective public health tool to reduce the spread of respiratory pandemics such as COVID-19. To analyze compliance with social distancing policies, we design two video-based pipelines for social distancing analysis, namely, automated video-based social distancing analyzer (Auto-SDA) and bird’s eye view social distancing analyzer (B-SDA). Auto-SDA is designed to measure social distancing using street-level cameras. To avoid privacy concerns of using street-level cameras, we further develop B-SDA, which uses bird’s eye view cameras, thereby preserving pedestrian’s privacy. We used the COSMOS testbed deployed in West Harlem, New York City (NYC), to evaluate both pipelines. In particular, Auto-SDA and B-SDA are applied on videos recorded by two of COSMOS cameras deployed on the 2nd floor (street-level) and 12th floor (bird’s eye view) of Columbia University’s Mudd building, looking at 120th St. and Amsterdam Ave. intersection, NYC. Videos are recorded before and during the peak of the pandemic, as well as after the vaccines became broadly available. The results represent the impact of social distancing policies on pedestrians’ social behavior. For example, the analysis shows that after the lockdown, less than 55% of the pedestrians failed to adhere to the social distancing policies, whereas this percentage increased to 65% after the vaccines’ availability. Moreover, after the lockdown, 0%–20% of the pedestrians were affiliated with a social group, compared to 10%–45% once the vaccines became available. The results also show that the percentage of face-to-face failures has decreased from 42.3% (prepandemic) to 20.7% (after the lockdown).

Blind and low-vision (BLV) people use GPS-based systems for outdoor navigation assistance, which provide instructions to get from one place to another. However, such systems do not provide users with real-time, precise information about their location and surroundings which is crucial for safe navigation. In this work, we investigate whether street cameras can be used to address aspects of navigation that BLV people still find challenging with existing GPS-based assistive technologies. We conducted formative interviews with six BLV participants to identify specific challenges they face in outdoor navigation. We discovered three main challenges: anticipating environment layouts, avoiding obstacles while following directions, and crossing noisy street intersections. To address these challenges, we are currently developing a street camera-based navigation system that provides real-time auditory feedback to help BLV users avoid obstacles, know exactly when to cross the street, and understand the overall layout of the environment. We close by discussing our evaluation plan.

Despite the rich literature on scheduling algorithms for wireless networks, algorithms that can provide deadline guarantees on packet delivery for general traffic and interference models are very limited. In this paper, we study the problem of scheduling real-time traffic under a conflict-graph interference model with unreliable links due to channel fading. Packets that are not successfully delivered within their deadlines are of no value. We consider traffic (packet arrival and deadline) and fading (link reliability) processes that evolve as an unknown finite-state Markov chain. The performance metric is efficiency ratio which is the fraction of packets of each link which are delivered within their deadlines compared to that under the optimal (unknown) policy. We first show a conversion result that shows classical non-real-time scheduling algorithms can be ported to the real-time setting and yield a constant efficiency ratio. In particular, Max-Weight Scheduling (MWS) yields an efficiency ratio of 1/2. We then propose randomized algorithms that achieve efficiency ratios strictly higher than 1/2, by carefully randomizing over the maximal schedules. Further, we propose low-complexity and myopic distributed randomized algorithms, and characterize their efficiency ratio. Simulation results are presented that verify that the randomized algorithms outperform classical ones such as MWS and GMS for scheduling real-time traffic over fading channels.

We consider scheduling deadline-constrained packets in multihop wireless networks. Packets with arbitrary deadlines and weights arrive at and are destined to different nodes. The goal is to design online admission, routing, and scheduling algorithms in order to maximize the cumulative weight of packets that reach their destinations within their deadlines. Under a general interference graph model of the wireless network, we provide online algorithms that are (γ, R)-competitive, i.e., they achieve at least 1/γ fraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor R ≥ 1. In particular, our algorithm can achieve γ = O(Ψ* log(ΔρL)/R) when RC = Ω(Ψ* log(ΔρL)), where ρ is the ratio of maximum weight to minimum weight of packets, L is the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here, Δ is the maximum degree and Ψ* is the local clique cover number of the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks, Ψ* = 2, and in the case of wired networks (no interference), Ψ* = 1. We further provide lower bounds that show that our results are asymptotically optimal in many settings. Finally, we present extensive simulations that show our algorithms provide significant improvement over the prior approaches.

Crowded metropolises present unique challenges to the potential deployment of autonomous vehicles. Safety of pedestrians cannot be compromised and personal privacy must be preserved. Smart city intersections will be at the core of Artificial Intelligence (AI)-powered citizen-friendly traffic management systems for such metropolises. Hence, the main objective of this work is to develop an experimentation framework for designing applications in support of secure and efficient traffic intersections in urban areas. We integrated a camera and a programmable edge computing node, deployed within the COSMOS testbed in New York City, with an Eclipse sensiNact data platform provided by Kentyou. We use this pipeline to collect and analyze video streams in real-time to support smart city applications. In this demo, we present a video analytics pipeline that analyzes the video stream from a COSMOS' street-level camera to extract traffic/crowd-related information and sends it to a dedicated dashboard for real-time visualization and further assessment. This is done without sending the raw video, in order to avoid violating pedestrians' privacy.

Applications in data-parallel computing typically consist of multiple stages. In each stage, a set of intermediate parallel data flows (Coflow) is produced and transferred between servers to enable starting of next stage. While there has been much research on scheduling isolated coflows, the dependency between coflows in multi-stage jobs has been largely ignored. In this paper, we consider scheduling coflows of multi-stage jobs represented by generalDAGs (Directed Acyclic Graphs) in a shared data center network, so as to minimize the total weighted completion time of jobs. This problem is significantly more challenging than the traditional coflow scheduling, as scheduling even a single multi-stage job to minimize its completion time is shown to be NP-hard. In this paper, we propose a polynomial-time algorithm with approximation ratio of$O(\mu \log (m)/\log (\log (m)))$, where$\mu $is the maximum number of coflows in a job and$m$is the number of servers. For the special case that the jobs’ underlying dependency graphs arerooted trees, we modify the algorithm and improve its approximation ratio. To verify the performance of our algorithms, we present simulation results using real traffic traces that show up to 53% improvement over the prior approach. We conclude the paper by providing a result concerning an optimality gap for scheduling coflows with general DAGs.

Despite the rich literature on scheduling algorithms for wireless networks, algorithms that can provide deadline guarantees on packet delivery for general traffic and interference models are very limited. In this paper, we study the problem of scheduling real-time traffic under a conflict-graph interference model with unreliable links due to channel fading. Packets that are not successfully delivered within their deadlines are of no value. We consider traffic (packet arrival and deadline) and fading (link reliability) processes that evolve as an unknown finite-state Markov chain. The performance metric is efficiency ratio which is the fraction of packets of each link which are delivered within their deadlines compared to that under the optimal (unknown) policy. We first show a conversion result that shows classical non-real-time scheduling algorithms can be ported to the real-time setting and yield a constant efficiency ratio, in particular, Max-Weight Scheduling (MWS) yields an efficiency ratio of 1/2. We then propose randomized algorithms that achieve efficiency ratios strictly higher than 1/2, by carefully randomizing over the maximal schedules. We further propose low-complexity and myopic distributed randomized algorithms, and characterize their efficiency ratio. Simulation results are presented that verify that randomized algorithms outperform classical algorithms such as MWS and GMS.

Social distancing can reduce infection rates in respiratory pandemics such as COVID-19, especially in dense urban areas. Hence, we used the PAWR COSMOS wireless edge-cloud testbed in New York City to design and evaluate two different approaches for social distancing analysis. The first, \textbf{Auto}mated video-based \textbf{S}ocial \textbf{D}istancing \textbf{A}nalyzer (\textbf{Auto-SDA}), was designed to measure pedestrians compliance with social distancing protocols using street-level cameras. However, since using street-level cameras can raise privacy concerns, we also developed the \textbf{B}ird's eye view \textbf{S}ocial \textbf{D}istancing \textbf{A}nalyzer (\textbf{B-SDA}) which uses bird's eye view cameras, thereby preserving pedestrians' privacy. Both Auto-SDA and B-SDA consist of multiple modules. This demonstration illustrates the roles of these modules and their overall performance in evaluating the compliance of pedestrians with social distancing protocols. Moreover, we demonstrate applying Auto-SDA and B-SDA on videos recorded from cameras deployed on the 2nd and 12th floor of Columbia's Mudd building, respectively.

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource demands (e.g. memory requirements) arrive over time and must be served by a cluster of servers. To improve throughput and delay, the scheduler can pack as many jobs as possible in each server, however the sum of the jobs' resource demands cannot exceed the server's capacity. Motivated by the increasing complexity of workloads in shared clusters, we consider a setting where jobs' resource demands belong to a very large set of diverse types, or in the extreme case even infinitely many types, i.e. resource demands are drawn from a general unknown distribution over a possibly continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) type setting. We first characterize a fundamental limit on the maximum throughput in such setting. We then develop oblivious scheduling algorithms, based on Best-Fit and Universal Partitioning, that have low complexity and can achieve at least 1/2 and 2/3 of the maximum throughput respectively, without the knowledge of the resource demand distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.

In this paper, we consider the problem of scheduling real-time traffic in wireless networks under a conflict-graph interference model and single-hop traffic. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio. This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First) that can lead to poor delivery ratio for general traffic patterns. In this paper, we pursue a different approach through randomization over the choice of maximal links that can transmit at each time. We design randomized policies in collocated networks, multipartite networks, and general networks, that can achieve delivery ratios much higher than what is achievable by LDF. Further, our results apply to traffic (arrival and deadline) processes that evolve as positive recurrent Markov chains. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work. We further present extensive simulation results over various traffic patterns and interference graphs to illustrate the gains of our randomized policies over LDF variants.

Full-duplex (FD) wireless is an attractive communication paradigm with high potential for improving network capacity and reducing delay in wireless networks. Despite significant progress on the physical layer development, the challenges associated with developing medium access control (MAC) protocols for heterogeneous networks composed of both legacy half-duplex (HD) and emerging FD devices have not been fully addressed. Therefore, we focus on the design and performance evaluation of scheduling algorithms for infrastructure-based heterogeneous HD-FD networks (composed of HD and FD users). We first show that centralized Greedy Maximal Scheduling (GMS) is throughput-optimal in heterogeneous HD-FD networks. We propose the Hybrid-GMS (H-GMS) algorithm, a distributed implementation of GMS that combines GMS and a queue-based random-access mechanism. We prove that H-GMS is throughput-optimal. Moreover, we analyze the delay performance of H-GMS by deriving lower bounds on the average queue length. We further demonstrate the benefits of upgrading HD nodes to FD nodes in terms of throughput gains for individual nodes and the whole network. Finally, we evaluate the performance of H-GMS and its variants in terms of throughput, delay, and fairness between FD and HD users via extensive simulations. We show that in heterogeneous HD-FD networks, H-GMS achieves 16-$30\times $ better delay performance and improves fairness between HD and FD users by up to 50% compared with the fully decentralized Q-CSMA algorithm.

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs' resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have tow complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.

Full-duplex (FD) wireless is an attractive communication paradigm with high potential for improving network capacity and reducing delay in wireless networks. Despite significant progress on the physical layer development, the challenges associated with developing medium access control (MAC) protocols for heterogeneous networks composed of both legacy half-duplex (UD) and emerging FD devices have not been fully addressed. Therefore, we focus on the design and performance evaluation of scheduling algorithms for infrastructure-based heterogeneous networks (composed of UD and FD users). We develop the hybrid Greedy Maximal Scheduling (U-GMS) algorithm, which is tailored to the special characteristics of such heterogeneous networks and combines both centralized GMS and decentralized Q-CSMA mechanisms. Moreover, we prove that H-GMS is throughput-optimal. We then demonstrate by simple examples the benefits of adding FD nodes to a network. Finally, we evaluate the performance of U-GMS and its variants in terms of throughput, delay, and fairness between FD and UD users via extensive simulations. We show that in heterogeneous UD-FD networks, U-GMS achieves 5-10x better delay performance and improves fairness between HD and FD users by up to 50% compared with the fully decentralized Q-CSMA algorithm.

Many data-parallel computing frameworks in today's datacenters consist of multiple computation and communication stages. A stage often cannot start or be completed unless all the required data pieces from the preceding stages are received. Coflow is a recently proposed networking abstraction to capture such communication patterns. We consider the problem of efficiently scheduling coflows with release dates in a shared datacenter network so as to minimize the total weighted completion time of coflows. This problem has been shown to be NP-complete, and several polynomial-time approximation algorithms have been recently proposed with provable performance guarantees. Our main result in this paper is a new polynomial-time approximation algorithm that improves the best prior known results. Specifically, we propose a deterministic algorithm with an approximation ratio of 5, which improves the prior best known ratio of 12. For the special case when all the coflows are released at time zero, we obtain an algorithm with an approximation ratio of $4$ which improves the prior best known ratio of 8.

We study the problem of load balancing in datacenter networks, namely, assigning the end-to-end data flows among the available paths in order to efficiently balance the load in the network. The solutions used today rely typically on an equal-cost multi path (ECMP) mechanism, which essentially attempts to balance the load in the network by hashing the flows to the available shortest paths. However, it is well-known that the ECMP performs poorly when there is asymmetry either in the network topology or the flow sizes, and thus, there has been much interest recently in alternative mechanisms to address these shortcomings. In this paper, we consider a general network topology where each link has a cost, which is a convex function of the link congestions. Flows among the various source-destination pairs are generated dynamically over time, each with a size (bandwidth requirement) and a duration. Once a flow is assigned to a path in the network, it consumes bandwidth equal to its size from all the links along its path for its duration. We consider low-complexity congestion-aware algorithms that assign the flows to the available paths in an online fashion and without splitting. Specifically, we propose a myopic algorithm that assigns every arriving flow to an available path with the minimum marginal cost (i.e., the path which yields the minimum increase in the network cost after assignment) and prove that it asymptotically minimizes the total network cost. Extensive simulation results are presented to verify the performance of the myopic algorithm under a wide range of traffic conditions and under different datacenter architectures. Furthermore, we propose randomized versions of our myopic algorithm, which have much lower complexity and empirically show that they can still perform very well in symmetric network topologies.

Wireless object tracking applications are gaining popularity and will soon utilize emerging ultra-low-power device-to-device communication. However, severe energy constraints require much more careful accounting of energy usage than what prior art provides. In particular, the available energy, the differing power consumption levels for listening, receiving, and transmitting, as well as the limited control bandwidth must all be considered. Therefore, we formulate the problem of maximizing the throughput among a set of heterogeneous broadcasting nodes with differing power consumption levels, each subject to a strict ultra-low-power budget. We obtain the oracle throughput (i.e., maximum throughput achieved by an oracle) and use Lagrangian methods to design EconCast - a simple asynchronous distributed protocol in which nodes transition between sleep, listen, and transmit states, and dynamically change the transition rates. We also show that EconCast approaches the oracle throughput. The performance is evaluated numerically and via extensive simulations and it is shown that EconCast outperforms prior art by 6x - 17x under realistic assumptions. Finally, we implement EconCast using the TI eZ430-RF2500-SEH energy harvesting nodes and experimentally show that in realistic environments it obtains 57% - 77% of the achievable throughput.

We consider the problem of scheduling VMs (Virtual Machines) in a multi-server system motivated by cloud computing applications. VMs arrive dynamically over time and require various amounts of resources (e.g., CPU, Memory, Storage, etc.) for the duration of their service. When a VM arrives, it is queued and later served by one of the servers that has sufficient remaining capacity to serve it. The scheduling of VMs is subject to: (i) packing constraints, i.e., multiple VMs can be be served simultaneously by a single server if their cumulative resource requirement does not violate the capacity of the server, and (ii) non-preemption, i.e., once a VM is scheduled in a server, it cannot be interrupted or migrated to another server. To achieve maximum throughput, prior results hinge on solving a hard combinatorial problem (Knapsack) at the instances that all the servers become empty (the so-called global refresh times which require synchronization among the servers). The main contribution of this paper is that it resolves these issues. Specifically, we present a class of randomized algorithms for placing VMs in the servers that can achieve maximum throughput without preemptions. The algorithms are naturally distributed, have low complexity, and each queue needs to perform limited operations. Further, our algorithms display good delay performance in simulations, comparable to delay of heuristics that may not be throughput-optimal, and much better than the delay of the prior known throughput-optimal algorithms.

We study the problem of load balancing in datacenter networks, namely, assigning the end-to-end data flows among the available paths in order to efficiently balance the load in the network. The solutions used today rely typically on ECMP (Equal Cost Multi Path) mechanism which essentially attempts to balance the load in the network by hashing the flows to the available shortest paths. However, it is well known that ECMP performs poorly when there is asymmetry either in the network topology or the flow sizes, and thus there has been much interest recently in alternative mechanisms to address these shortcomings. In this paper, we consider a general network topology where each link has a cost which is a convex function of the link utilization. Flows among the various source-destination pairs are generated dynamically over time, each with a size (bandwidth requirement) and a duration. Once a flow is assigned to a path in the network, it consumes bandwidth equal to its size from all the links along its path for its duration. We propose a low-complexity congestion-aware algorithm that assigns the flows to the available paths in an online fashion and without splitting, and prove that it asymptotically minimizes the total network cost. Extensive simulation results are presented to verify the performance of our algorithm under a wide range of traffic conditions and under different datacenter architectures.

Motivated by emerging big streaming data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data-flows between these compute tasks. Jobs (graphs) arrive randomly over time, and upon completion, leave the system. When a job arrives, the scheduler needs to partition the graph and distribute it over the servers to satisfy load balancing and cost considerations. Specifically, neighboring compute tasks in the graph that are mapped to different servers incur load on the network; thus a mapping of the jobs among the servers incurs a cost that is proportional to the number of "broken edges''. We propose a low complexity randomized scheduling algorithm that, without service preemptions, stabilizes the system with graph arrivals/departures; more importantly, it allows a smooth trade-off between minimizing average partitioning cost and average queue lengths. Interestingly, to avoid service preemptions, our approach does not rely on a Gibbs sampler; instead, we show that the corresponding limiting invariant measure has an interpretation stemming from a loss system.

In this paper we look at content placement in the high-dimensional regime: there are n servers, and O(n) distinct types of content. Each server can store and serve O(1) types at any given time. Demands for these content types arrive, and have to be served in an online fashion; over time, there are a total of O(n) of these demands. We consider the algorithmic task of content placement: determining which types of content should be on which server at any given time, in the setting where the demand statistics (i.e. the relative popularity of each type of content) are not known a-priori, but have to be inferred from the very demands we are trying to satisfy. This is the high-dimensional regime because this scaling (everything being O(n)) prevents consistent estimation of demand statistics; it models many modern settings where large numbers of users, servers and videos/webpages interact in this way.

It has been recently shown that queue-based carrier sense multiple access (CSMA) algorithms are throughput-optimal. In these algorithms, each link of the wireless network has two parameters: a transmission probability and an access probability. The transmission probability of each link is chosen as an appropriate function of its queue length, however the access probabilities are simply regarded as some random numbers since they do not play any role in establishing the network stability. In this paper, we show that the access probabilities control the mixing time of the CSMA Markov chain and, as a result, affect the delay performance of the CSMA. In particular, we derive formulas that relate the mixing time to access probabilities and use these to develop the following guideline for choosing access probabilities: Each link i should choose its access probability equal to 1/(di+1), where diis the number of links that interfere with link i. Simulation results show that this choice of access probabilities results in good delay performance.

The paper studies throughput-optimal scheduling in wireless networks when there are file arrivals and departures. In the case of single-hop traffic, the well-studied Max Weight algorithm provides soft priorities to links with larger queue lengths. If packets arrive in bursts during file arrival instants, then large variances in file sizes would imply that some links will have very large queue lengths while others will have small queue lengths. Thus, links with small queue lengths may be starved for long periods of time. An alternative is to use only MAC-layer queue lengths in making scheduling decisions; in fact, typically only this information is available since scheduling is performed at the MAC layer. Therefore the questions we ask in this paper are the following: (i) is scheduling using only MAC-layer queue length information throughput-optimal? and (ii) does it improve delay performance compared to the case where scheduling is performed using the total number of packets waiting at a link? We affirmatively answer both questions in the paper (the first theoretically and the second using simulations), making minimal assumptions on the transport-layer window control mechanism.

It has been recently shown that queue-based CSMA algorithms can be throughput optimal. In these algorithms, each link of the wireless network has two parameters: a transmission probability and an access probability. The transmission probability of each link is chosen as an appropriate function of its queue-length, however, the access probabilities are simply regarded as some random numbers since they do not play any role in establishing the network stability. In this paper, we show that the access probabilities control the mixing time of the CSMA Markov chain and, as a result, affect the delay performance of the CSMA. In particular, we derive formulas that relate the mixing time to access probabilities and use these to develop the following guideline for choosing access probabilities: each link i should choose its access probability equal to 1/(di+ 1), where diis the number of links which interfere with link i. Simulation results show that this choice of access probabilities results in good delay performance.

The problem of anonymous networking when an eavesdropper observes packet timings in a communication network is considered. The goal is to hide the identities of source-destination nodes, and paths of information flow in the network. One way to achieve such an anonymity is to use mixers. Mixers are nodes that receive packets from multiple sources and change the timing of packets, by mixing packets at the output links, to prevent the eavesdropper from finding sources of outgoing packets. In this paper, we consider two simple but fundamental scenarios: double input-single output mixer and double input-double output mixer. For the first case, we use the information-theoretic definition of the anonymity, based on average entropy per packet, and find an optimal mixing strategy under a strict latency constraint. For the second case, perfect anonymity is considered, and a maximal throughput strategy with perfect anonymity is found that minimizes the average delay.

For a wireless network withnnodes distributed in an areaA, and withnsource-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in (Ozgur, Leveque, and Tse, 2007) is analyzed and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily improve the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending onn. In addition, to apply the hierarchical cooperation scheme to random networks, a clustering algorithm is developed, which divides the whole network into quadrilateral clusters, each with exactly the number of nodes required.

For a wireless network with n nodes distributed in an area A, with n source-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in [A. Ozgur et al., 2007] is studied and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily increase the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending on n.