More Like this

1. Average Age of Information in Update Systems with Active Sources and Packet Delivery Errors

   https://doi.org/10.1109/LWC.2020.2983397  

   Farazi, S.; Klein, A.; Brown, D. (August 2020, IEEE wireless communications letters)

   This paper studies the “age of information” (AoI) in a multi-source status update system where N active sources each send updates of their time-varying process to a monitor through a server with packet delivery errors. We analyze the average AoI for stationary randomized and round-robin scheduling policies. For both of these scheduling policies, we further analyze the effect of packet retransmission policies, i.e., retransmission without re- sampling, retransmission with resampling, or no retransmission, when errors occur. Expressions for the average AoI are derived for each case. It is shown that the round-robin schedule policy in conjunction with retransmission with resampling when errors occur achieves the lowest average AoI among the considered cases. For stationary randomized schedules with equiprobable source selection, it is further shown that the average AoI gap to round-robin schedules with the same packet management policy scales as O(N). Finally, for stationary randomized policies, the optimal source selection probabilities that minimize a weighted sum average AoI metric are derived. 

   more » « less
2. Trade-Off Study of Localizing Communication and Balancing Network Traffic on a Dragonfly System

   Wang, Xin; Mubarak, Misbah; Yang, Xu; Ross, Rob; Lan, Zhiling (May 2018, IPDPS .... [proceedings])

   Dragonfly networks are being widely adopted in high-performance computing systems. On these networks, however, interference caused by resource sharing can lead to significant network congestion and performance variability. We present a comparative analysis exploring the trade-off between localizing communication and balancing network traffic. We conduct trace-based simulations for applications with different communication patterns, using multiple job placement policies and routing mechanisms. We perform an in-depth performance analysis on representative applications individually and show that different applications have distinct preferences regarding localized communication and balanced network traffic. We further demonstrate the effect of external network interference by introducing background traffic and show that localized communication can help reduce the application performance variation caused by network sharing. 

   more » « less
3. On Non-Preemptive VM Scheduling in the Cloud

   https://doi.org/10.1145/3219617.3219644  

   Psychas, Konstantinos; Ghaderi, Javad (January 2018, SIGMETRICS '18 Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems)

   We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) for the duration of their service. To avoid costly preemptions, we consider non-preemptive scheduling: Each VM has to be assigned to a server which has enough residual capacity to accommodate it, and once a VM is assigned to a server, its service cannot be disrupted (preempted). Prior approaches to this problem either have high complexity, require synchronization among the servers, or yield queue sizes/delays which are excessively large. We propose a non-preemptive scheduling algorithm that resolves these issues. In general, given an approximation algorithm to Knapsack with approximation ratio r , our scheduling algorithm can provide rβ fraction of the throughput region for β < r. In the special case of a greedy approximation algorithm to Knapsack, we further show that this condition can be relaxed to β<1. The parameters β and r can be tuned to provide a tradeoff between achievable throughput, delay, and computational complexity of the scheduling algorithm. Finally extensive simulation results using both synthetic and real traffic traces are presented to verify the performance of our algorithm. 

   more » « less
4. Efficient scheduling for synchronized demands in stochastic networks

   https://doi.org/10.23919/WIOPT.2018.8362848  

   Li, Bin; Shi, Zai; Eryilmaz, Atilla (May 2018, 16th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (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
5. 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