29-06-2012, 11:14 AM
Delay Analysis for Maximal Scheduling with Flow Control in Wireless Networks with Bursty Traffic
Wireless Networks with Bursty Traffic.pdf (Size: 271.25 KB / Downloads: 56)
Introduction
Our analysis shows that this type of scheduling also yields
tight delay guarantees. In particular, when arrival processes
are modulated by independent Markov processes, we show that
average delay grows at most logarithmically in the number of
nodes in the network. We then obtain an improved delay bound
in the important special case when the individual Markov
chains have at most two states (such as bursty ON/OFF
sources). Average delay in this case is shown to be independent
of the network size, and hence is order-optimal.
Maximal Scheduling
Define the network capacity region as the closure of
the set of all arrival rate vectors (l)l2L that can be stably
supported, considering all possible scheduling algorithms that
conform to the above constraints (see [6] for a discussion of
capacity regions and stability). It is well known that scheduling
according to a generalized max-weight rule every timeslot
ensures stability and maximum throughput whenever arrival
rates are interior to the capacity region [5] [6].1 However, the
max-weight rule involves an integer optimization that may be
difficult to implement, and has delay properties that are difficult
to analyze. Here, we assume scheduling is done according
to a simpler maximal scheduling algorithm. Specifically.
TIME-CORRELATED ARRIVALS WITH TWO STATES
Consider the case of Markov modulated arrivals, as described
in Section II-A, where all Markov chains Zl(t) have
at most two states (labeled “1” and “2”). Note that this model
includes the important special case of ON/OFF inputs, where
Al(t) has a single packet arrival when in the ON state and has
no arrivals when in the OFF state.3 Let ~ L be the set of all links
l 2 L that have exactly two states with different conditional
rates (1)
l and (2)
Wireless Networks with Bursty Traffic.pdf (Size: 271.25 KB / Downloads: 56)
Introduction
Our analysis shows that this type of scheduling also yields
tight delay guarantees. In particular, when arrival processes
are modulated by independent Markov processes, we show that
average delay grows at most logarithmically in the number of
nodes in the network. We then obtain an improved delay bound
in the important special case when the individual Markov
chains have at most two states (such as bursty ON/OFF
sources). Average delay in this case is shown to be independent
of the network size, and hence is order-optimal.
Maximal Scheduling
Define the network capacity region as the closure of
the set of all arrival rate vectors (l)l2L that can be stably
supported, considering all possible scheduling algorithms that
conform to the above constraints (see [6] for a discussion of
capacity regions and stability). It is well known that scheduling
according to a generalized max-weight rule every timeslot
ensures stability and maximum throughput whenever arrival
rates are interior to the capacity region [5] [6].1 However, the
max-weight rule involves an integer optimization that may be
difficult to implement, and has delay properties that are difficult
to analyze. Here, we assume scheduling is done according
to a simpler maximal scheduling algorithm. Specifically.
TIME-CORRELATED ARRIVALS WITH TWO STATES
Consider the case of Markov modulated arrivals, as described
in Section II-A, where all Markov chains Zl(t) have
at most two states (labeled “1” and “2”). Note that this model
includes the important special case of ON/OFF inputs, where
Al(t) has a single packet arrival when in the ON state and has
no arrivals when in the OFF state.3 Let ~ L be the set of all links
l 2 L that have exactly two states with different conditional
rates (1)
l and (2)