2015/01/14 by Sucha Supittayapornpong, Supittayapornpong, Sucha, Michael J. Neely +1
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #Age of Information Optimization #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1501.03457
openalex publication_date 2015/01/14 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
One practical open problem is the development of a distributed algorithm that\nachieves near-optimal utility using only a finite (and small) buffer size for\nqueues in a stochastic network. This paper studies utility maximization (or\ncost minimization) in a finite-buffer regime and considers the corresponding\ndelay and reliability (or rate of packet drops) tradeoff. A floating-queue\nalgorithm allows the stochastic network optimization framework to be\nimplemented with finite buffers at the cost of packet drops. Further, the\nbuffer size requirement is significantly smaller than previous works in this\narea. With a finite buffer size of B packets, the proposed algorithm achieves\nwithin O(e-B) of the optimal utility while maintaining average per-hop\ndelay of O(B) and an average per-hop drop rate of O(e-B) in steady\nstate. From an implementation perspective, the floating-queue algorithm\nrequires little modification of the well-known Drift-Plus-Penalty policy\n(including MaxWeight and Backpressure policies). As a result, the\nfloating-queue algorithm inherits the distributed and low complexity nature of\nthese policies.\n