More Like this

1. Efficient Scheduling for Synchronized Demands in Stochastic Networks

   Bin Li, Zai Shi (May 2018, IEEE WiOpt)

   There is a rich theory and plethora of algorithms in the literature aiming at the efficient scheduling of stochastic networks. These solutions are predominantly designed under the assumption of traffic demands that are independently generated at network nodes, without any requirement for synchronization among their received services. In this work, we note that many applications, including cloud computing, virtual reality, gaming, autonomous vehicular networks and collaborative design, generate traffic simultaneously at multiple nodes when they arrive, with possibly non-uniform file sizes, whose performance relies on the synchronous completion of the traffic across the network. This calls for the design of new scheduling algorithms that aims to coordinate the service of packets of the same traffic across the network. Towards this end, we propose a novel scheduling algorithm that not only accounts for the heterogeneity of the file size distributions, but also works towards synchronizing the completion time of the same traffic stream across the network. This is achieved by employing two insights that emanate from key motivating examples we develop: (1) the normalization of traffic load with respect to the non-uniform file sizes; and (2) the incorporation of deviation of normalized loads across network nodes that serve synchronized traffic. After establishing the throughput-optimality of our algorithm in general stochastic networks, we perform extensive simulations under various (spanning both wired and wireless) settings to reveal the potential completion time gains that it yields over other throughput-optimal strategies designed under the assumption of independent traffic generation. 

   more » « less
2. Hybrid Scheduling in Heterogeneous Half- and Full-Duplex Wireless Networks

   https://doi.org/1801.01108v2  

   Tingjun Chen, Jelena Diakonikolas (January 2018, ArXiv.org)

   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 GreedyMaximal 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 throughputoptimal. 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 HGMS 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× better delay performance and improves fairness between HD and FD users by up to 50% compared with the fully decentralized Q-CSMA algorithm. 

   more » « less
3. Hybrid scheduling in heterogeneous half- and full-duplex wireless networks

   Chen, T.; Diakonikolas, J.; Ghaderi, J.; Zussman, G. (January 2020, IEEE/ACM Transactions on Networking)

   Abstract—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 throughputoptimal. 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 HGMS 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× better delay performance and improves fairness between HD and FD users by up to 50% compared with the fully decentralized Q-CSMA algorithm. 

   more » « less
4. Expanding across time to deliver bandwidth efficiency and low latency

   William M. Mellette, Rajdeep Das (January 2020, USENIX Symposium on Networked Systems Design and Implementation (NSDI))

   Datacenters need networks that support both low-latency and high-bandwidth packet delivery to meet the stringent requirements of modern applications. We present Opera, a dynamic network that delivers latency-sensitive traffic quickly by relying on multi-hop forwarding in the same way as expander-graph-based approaches, but provides near-optimal bandwidth for bulk flows through direct forwarding over time-varying source-to-destination circuits. Unlike prior approaches, Opera requires no separate electrical network and no active circuit scheduling. The key to Opera's design is the rapid and deterministic reconfiguration of the network, piece-by-piece, such that at any moment in time the network implements an expander graph, yet, integrated across time, the network provides bandwidth-efficient single-hop paths between all racks. We show that Opera supports low-latency traffic with flow completion times comparable to cost-equivalent static topologies, while delivering up to 4x the bandwidth for all-to-all traffic and supporting up to 60% higher load for published datacenter workloads. 

   more » « less
5. Adaptive Vehicle Platooning with Joint Network-Traffic Approach

   https://doi.org/10.1109/GLOBECOM46510.2021.9685116  

   Mahabal, Chinmay; Fang, Hua; Wang, Honggang; Yang, Qing (December 2021, 2021 IEEE Global Communications Conference (GLOBECOM))

   The Intelligent Transportation System has become one of the most globally researched topics, with Connected and Autonomous Vehicles(CAV) at its core. The CAV applications can be improved by the study of vehicle platooning immune to realtime traffic and vehicular network losses. In this work, we explore the need to integrate the Network model and Platooning system model for highway environments. The proposed platoon model is designed to be adaptive in length, providing the node vehicles to merge and exit. This overcomes the assumption that all the platoon nodes should have a common source and destination. The challenges of the existing platoon model, such as relay selection, acceleration threshold, are addressed for highly modular platoon design. The presented algorithm for merge and exit events optimizes the trade-off between network parameters such as communication range and vehicle dynamic parameters such as velocity and acceleration threshold. It considers the network bounds like SINR and link stability and vehicle trajectory parameters like the duration of the vehicle in the platoon. This optimizes the traffic throughput while maintaining stability using the PID controller. The work tries to increase the vehicle inclusion time in the platoon while preserving the overall traffic throughput. 

   more » « less