Optimal Buffer Partitioning on a Multiuser Wireless Link

Date

2010-02-05

Author

Ozel, Omur
Uysal, Elif
GİRİCİ, TOLGA

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

125
views

0
downloads

We consider a finite buffer shared by multiple packet queues. Throughput can be considerably improved by partitioning the buffer space among the queues judiciously, especially under a high load regime. We formulate optimal buffer partitioning as a resource allocation problem, the solution of which is found through a greedy incremental algorithm in polynomial time. The rest of the work is devoted to applying the optimal buffer allocation strategy in different scenarios modeling a wireless downlink. First, the strategy is applied in a general parallel M/M/1/mi system and a numerical study verifies that the strategy may boost the throughput considerably. Then, a multichannel extension of this system is considered when the users have different arrival rates and channels have different outage probabilities. Jointly optimal buffer space allocation and channel assignment problems in this scenario are shown to be separable. Lastly, buffer allocation is considered in a system where users need to be multiplexed and scheduled based on channel state. It is shown that this system can be modeled as a set of parallel M/G/1/m(i) queues to which the optimum buffer allocation strategy is again applicable. The improvement brought by optimal buffer allocation to scheduling based solely on channel- state is explored. It is observed that buffer optimization can result in remarkable throughput increase on top of channelbased user selection.

Subject Keywords

RESOURCE ALLOCATIONS, MEMORY MANAGEMENT, NETWORKS, QUEUES

URI

https://hdl.handle.net/11511/53164

Conference Name

Information Theory and Applications Workshop (ITA)

Collections

Department of Electrical and Electronics Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Exit probabilities of markov modulated constrained random walks Başoğlu Kabran, Fatma; Sezer, Ali Devin; Department of Financial Mathematics (2018) Let X be the constrained random walk on Z2+ with increments (0, 0), (1, 0), (−1, 1), (0, −1) whose jump probabilities are determined by the state of a finite state Markov chain M. X represents the lengths of two queues of customers (or packets, tasks, etc.) waiting for service from two servers working in tandem; the arrival of customers occur with rate λ(Mk), service takes place at rates μ1(Mk), and μ2(Mk) where Mk denotes the current state of the Markov chain M. We assume that the average arrival rate is l...
Enhanced adjacent extreme-point search and tabu search for the minimum concave-cost uncapacitated transshipment problem Bazlamaçcı, Cüneyt Fehmi (Informa UK Limited, 1996-09-01) Practicable methods for optimising concave-cast, uncapacitated transshipment networks are non exact. In this paper, one such effective method, that of adjacent extreme point search, is further developed to enhance its overall computational efficiency. The enhanced search algorithm is then imbedded in a tabu search scheme which proved capable of finding better solutions, by a wide margin in some instances. Another tabu search scheme, somewhat inferior in terms of solution quality but computationally more eff...
Approximation of excessive backlog probabilities of two parallel queues Ünlü, Kamil Demirberk; Sezer, Ali Devin (2018-07-25) Let X be the constrained random walk on Z 2 + with increments (1, 0), (−1, 0), (0, 1) and (0, −1) representing the lengths at service completion times of two queues with exponentially distributed interarrival and service times running in parallel. Denote the arrival and service rates by λ i , µ i , i = 1, 2; we assume λ i < µ i , i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume ρ 1 ≥ ρ 2. Let τ n be the first time X hits the line ∂A n = {x ∈ Z 2 : x(1)+x(2) = n}, i.e., when the sum ...
Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed Azizoğlu, Meral; Koksalan, SK (Informa UK Limited, 2003-06-01) We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algori...
Minimizing flowtime and maximum earliness on a single machine Koksalan, M; Azizoğlu, Meral; Kondakci, SK (1998-02-01) We consider the bicriteria scheduling problem of minimizing flowtime and maximum earliness on a single machine. The problem is known to be NP-hard. We develop heuristic procedures for generating all efficient sequences for the cases where machine idle time is either allowed or not allowed. For both cases we also discuss an algorithm that finds the best of the approximately efficient sequences for a given objective function by generating only a small subset of those sequences. We present computational result...

Citation Formats

O. Ozel, E. Uysal, and T. GİRİCİ, “Optimal Buffer Partitioning on a Multiuser Wireless Link,” presented at the Information Theory and Applications Workshop (ITA), Univ Calif San Diego, San Diego, CA, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/53164.