It is well known that the generalized max-weight matching (GMWM) scheduling policy, and in general throughput-optimal scheduling policies, often require the solution of a complex optimization problem, making their implementation prohibitively difficult in practice. This has motivated many researchers to develop distributed sub-optimal algorithms that approximate the GMWM policy. One major assumption commonly shared in this context is that the time required to find an appropriate schedule vector is negligible compared to the length of a timeslot. This assumption may not be accurate as the time to find schedule vectors usually increases polynomially with the network size. On the other hand, we intuitively expect that for many sub-optimal algorithms, the schedule vector found becomes a better estimate of the one returned by the GMWM policy as more time is given to the algorithm. We thus, in this paper, consider the problem of scheduling from a new perspective through which we carefully incorporate channel variations and time-efficiency of sub-optimal algorithms into the scheduler design. Specifically, we propose a dynamic control policy (DCP) that works on top of a given sub-optimal algorithm, and dynamically but in a large time-scale adjusts the time given to the algorithm according to queue backlog and channel correlations. This policy does not require the knowledge of the structure of the given sub-optimal algorithm, and with low-overhead can be implemented in a distributed manner. Using a novel Lyapunov analysis, we characterize the stability region induced by DCP, and show that our characterization can be tight. We also show that the stability region of DCP is at least as large as the one for any other static policy. Finally, we provide two case studies to gain further intuition into the performance of DCP.
The GMWM scheduling despite its optimality, in every timeslot, requires the solution of the GMWM problem, which can be, in general, NP-hard and Non-Approximable @cite_6 . Thus, many studies has focused on developing sub-optimal constant factor approximations to the GMWM scheduling. One interesting study addressing the complexity issue is the work in @cite_31 , where sub-optimal algorithms are modeled as randomized algorithms, and it is shown that throughput-optimality can be achieved with linear complexity. In a more recent work @cite_1 , the authors propose distributed schemes to implement a randomized policy similar to the one in @cite_31 that can stabilize the entire capacity region. These results, however, assume non-time-varying channels. Other recent studies in @cite_19 @cite_23 generalize the approach in @cite_31 to time-varying networks, and prove its throughput-optimality. This optimality, as expected, comes at the price of requiring excessively large amount of other valuable resources in the network, which in this case is memory storage. Specifically, the memory requirement in @cite_19 @cite_23 increases exponentially with the number of users, making the generalized approach hardly amenable to practical implementation in large networks.
@cite_1 @cite_6 @cite_19 @cite_23 @cite_31
2039917366 2170717320 2038187727 2952389041
Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50 throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100 throughput. Moreover, in networks in which the σ-Local Pooling conditions hold, GMS achieves σ throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100 throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 × n, GMS is guaranteed to achieve 66 throughput, thereby improving upon the previously known 50 lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms. Throughput optimal scheduling policies in general require the solution of a complex and often NP-hard optimization problem. Related literature has shown that in the context of time-varying channels, randomized scheduling policies can be employed to reduce the complexity of the optimization problem but at the expense of a memory requirement that is exponential in the number of data flows. In this paper, we consider a linear-memory randomized scheduling policy (LM-RSP) that is based on a pick-and-compare principle in a time-varying network with N one-hop data flows. For general ergodic channel processes, we study the performance of LM-RSP in terms of its stability region and average delay. Specifically, we show that LM-RSP can stabilize a fraction of the capacity region. Our analysis characterizes this fraction as well as the average delay as a function of channel variations and the efficiency of LM-RSP in choosing an appropriate schedule vector. Applying these results to a class of Markovian channels, we provide explicit results on the stability region and delay performance of LM-RSP. Developing scheduling mechanisms that can simultaneously achieve throughput optimality and good delay performance often require solving the Maximum Independent Weighted Set (MWIS) problem. However, under most realistic network settings, the MWIS problem can be shown to be NP-hard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of the opportunistic gain, and may no longer guarantee good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size, and achieves provable performance guarantees (which is arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). Through simulations we verify that both the throughput and the delay under our proposed distributed scheduling scheme are close to that of the optimal solution to MWIS. Further, we implement a preliminary version of our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The preliminary experiment results show that our implementation successfully accounts for wireless fading, and attains the opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF. We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, ON OFF channels. It is well-known that the performance of scheduling over fading channels heavily depends on the accuracy of the available Channel State Information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally-correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration trade-off, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly-coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: (1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for the problem at hand. These results establish, for the first time to the best of our knowledge, that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally-correlated channels.