On the Boundaries of randomization for throughput-optimal scheduling in switches

Numerous Queue-Length-Based (QLB) schedulers, both deterministic and randomized, can achieve the maximum possible throughput region of wireless networks. While randomization is useful in allowing flexibilities in the design and implementation of the schedulers, it may lead to throughput loss if it is not within limits. In this work, we focus on the N × N input-queued switch topology to identify the boundaries of randomization in QLB scheduling for achieving throughput-optimality. To that end, we introduce a class of randomized QLB schedulers that are characterized by a wide range of functions. Then, we identify necessary and sufficient conditions on the number of switch ports N and the class of functions that can guarantee throughput-optimality of these randomized schedulers.We show that while our randomized QLB schedulers are throughput-optimal when N = 2, they cease to be so when N ≥ 3 for a large set of functional forms. For N ≥ 3, we further characterize an achievable rate region described via l₂ and l_∞ norms in an N² dimensional space that extends the existing achievable rate region descriptions. For N = 2, we also study the delay performance of various throughput-optimal randomized QLB schedulers through simulations. This preliminary work reveals the sensitivity of throughput-optimal scheduling to the topological characteristics of the network and the functional characteristics of the randomization.