Abstract-CSMA-based scheduling is a recently proposed distributed scheduling algorithm that is shown to achieve the maximal throughput. Central to this algorithm is a Markov chain that produces samples from a desired distribution. In this work, we discuss the relationships of the achievable throughput, queueing delay and the mixing time of the Markov chain in a variant of the algorithm. This result suggests that a small mixing time is desirable for low delay. We then discuss how a generic bound on the mixing time can be tightened in specific topologies. As in [1], we describe the basic model. Assume there are K links in the network, where each link is an (ordered) transmitter-receiver pair. The network is associated with a conflict graph (or "CG") G = {V, E}, where V is the set of vertices (each of them represents a link) and E is the set of edges. Two links k 1 and k 2 cannot transmit at the same time (i.e., "conflict") iff there is an edge between them, i.e., (k 1 , k 2 ) ∈ E. Assume that G has N independent sets ("IS"). Denote the i'th IS by a vector Packets arrive at link k with a rate λ k > 0. Let λ ∈ R K be the vector of arrival rates. We say that λ is feasible if and only if λ = ip i x i for some probability distributionp ∈ R N + satisfyingp i ≥ 0 and ip i = 1. That is, λ is a convex combination of the IS's, such that it is possible to serve the arriving traffic with some transmission schedule. Denote the set of feasible λ byC. The links follow a continuous-time CSMA protocol similar to that in [1] . Before attempting a transmission, the transmitter of link k waits (or backs-off) for a random period of time that is exponentially distributed with mean 1/R k and then senses the medium. If any conflicting link (i.e., any link m such that (k, m) ∈ E) is transmitting, then link k starts another waiting period with the same distribution, but independent of the previous waiting times. Otherwise, link k starts the transmission, whose duration is exponentially distributed with This work is supported by MURI grant BAA 07-036.18. mean 1. Define r k := log(R k ) to be the "transmission aggressiveness" (TA) of link k. This CSMA protocol leads to a Markov chain among the independent set which is called the CSMA Markov chain. Given r = (r k ), it has the following stationary distribution: where K be the state of the Markov chain at (continuous) time t. Then, x k (t) ∈ {0, 1} indicates whether link k is transmitting at time t. Time is divided into slots, where each slot has a duration of one time unit. Assume that the arrival rates λ is feasible, i.e., λ ∈C. Consider the following scheduling algorithm which updates the TA parameters r. Algorithm 1: Scheduling algorithm with bounded queue lengths 1) Initially, r k (0) = 0, ∀k. The actual queue length Q k (0) = 0, ∀k. The algorithm updates r(j) every T time units (or slots) where T is an integer. Initially j = 0. Fix a constant β > 0. (We refer to the interval between time jT and (j + 1)T as frame j where j = 0, 1, . . . . ) 2) Use r(j) in the CSMA operation for T time units. 3) After T time units (i.e., in the (j + 1)-th update), let
Jiang et al. REF demonstrate the relation between the small mixing time and a low delay, and investigate on how to tighten the generic bound of mixing time for specific topologies.
Performance bounds of distributed CSMA scheduling
2010 Information Theory and Applications Workshop (ITA)
2010 Information Theory and Applications Workshop (ITA)
Computer Science