Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Fei_thesis.pdf (5 MB)

ETD Abstract Container

Abstract Header

Ultra-Low Delay in Complex Computing and Networked Systems: Fundamental Limits and Efficient Algorithms

Wu, Fei
http://rave.ohiolink.edu/etdc/view?acc_num=osu155559337777619

Abstract Details

2019, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Latency has emerged as one of the most important requirements for these services that are intertwined with our economy, entertainment, comfort, and education. In this dissertation, we investigate the fundamental limits and develop efficient algorithms for achieving ultra-low delay in two computer systems: (1) the 5G networks; (2) the cloud systems. In 5G networks, a fundamental challenge in wireless multicast has been how to simultaneously achieve high-throughput and low-delay for reliably serving a large number of users. In a line of works, we propose coding and rate control algorithms, which can simultaneously realize the following three benefits: (i) High throughput: We show that in the many-user many-channel asymptotic regime, to achieve a non-vanishing throughput, the multi-channel resources required by our scheme achieves an algorithm independent lower bound in an order sense. (ii) Low delay: Using large deviations theory, we show that the delay of our scheme decreases linearly as the number of channels grows, while the delay reduction of conventional schemes is bounded by a constant factor. (iii) Constant feedback overhead: The feedback overhead of our scheme is a constant that is independent of both the number of receivers in each session and the number of sessions in the network. Trace-driven simulation and numerical results are provided to demonstrate these benefits. Our research suggests that large-scale wireless multicast with high throughput and low delay guarantees could be achieved. The significant promise of wireless multicast may be finally realized in practice. In cloud systems, load balancing is a key component for achieving low delay performance. Heavy-traffic delay optimality is considered to be an important metric in evaluating the delay performance of load balancing schemes. We argue that heavy-traffic delay optimality is a coarse metric that does not necessarily imply good delay performance. Specifically, we show that any load balancing scheme is heavy-traffic delay optimal as long as it satisfies a fairly weak condition. This condition only requires that in the long-term the dispatcher favors, even slightly, shorter queues over longer queues. Hence, although a load balancing scheme could be heavy-traffic delay optimal, the empirical delay performance of heavy-traffic delay optimal schemes can range from very good (that of join-shortest-queue) to very bad (arbitrarily close to the performance of random routing). To overcome this limitation, we introduce a new metric called degree of queue imbalance, which measures the queue length difference between all the servers in steady-state. Given a heavy-traffic delay optimal load balancing scheme, we can characterize the resultant degree of queue imbalance. This, in turn, allows us to explicitly differentiate between good and poor load balancing schemes. Thus, our result suggests that when designing good load balancing schemes, they should not only be heavy-traffic delay optimal, but also have a low degree of queue imbalance. Our research results enable a deeper understanding of how to achieve ultra-low delay performance in complex computing and networked systems.
Ness Shroff (Advisor)
Kannan Srinivasan (Advisor)
Eryilmaz Atilla (Committee Member)
Zhang Yinqian (Committee Member)
314 p.
Computer Engineering; Computer Science
Delay, Networks, 5G, Wireless, Cloud systems, Feedback, Resource allocation, Coding, Load balancing, Full-duplex, Rate control, Throughput, Complexity

Recommended Citations

Citations

  • Wu, F. (2019). Ultra-Low Delay in Complex Computing and Networked Systems: Fundamental Limits and Efficient Algorithms [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu155559337777619

    APA Style (7th edition)

  • Wu, Fei. Ultra-Low Delay in Complex Computing and Networked Systems: Fundamental Limits and Efficient Algorithms. 2019. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu155559337777619.

    MLA Style (8th edition)

  • Wu, Fei. "Ultra-Low Delay in Complex Computing and Networked Systems: Fundamental Limits and Efficient Algorithms." Doctoral dissertation, Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu155559337777619

    Chicago Manual of Style (17th edition)

osu155559337777619
286
© 2019, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.