of 15
arXiv:1808.03602v1 [math.PR] 9 Aug 2018
Temporal starvation in multi-channel CSMA networks:
an analytical framework
Alessandro Zocca
August 13, 2018
Abstract
In this paper we consider a stochastic model for a frequency-
agile CSMA protocol for wireless networks where
multiple orthogonal frequency channels are available. Eve
n when the possible interference on the different
channels is described by different conflict graphs, we show
that the network dynamics can be equivalently
described as that of a single-channel CSMA algorithm on an ap
propriate virtual network. Our focus is on
the asymptotic regime in which the network nodes try to activ
ate aggressively in order to achieve maximum
throughput. Of particular interest is the scenario where th
e number of available channels is not sufficient for all
nodes of the network to be simultaneously active and the well
-studied temporal starvation issues of the single-
channel CSMA dynamics persist. For most networks we expect t
hat a larger number of available channels should
alleviate these temporal starvation issues. However, we pr
ove that the aggregate throughput is a non-increasing
function of the number of available channels. To investigat
e this trade-off that emerges between aggregate
throughput and temporal starvation phenomena, we propose a
n analytical framework to study the transient
dynamics of multi-channel CSMA networks by means of first hi
tting times. Our analysis further reveals that
the mixing time of the activity process does not always corre
ctly characterize the temporal starvation in the
multi-channel scenario and often leads to pessimistic perf
ormance estimates.
1 Introduction
The Carrier-Sense Multiple-Access (CSMA) algorithm is a popular dist
ributed medium-access control mechanism
and indeed various incarnations of which are currently implemented in
IEEE 802.11 WiFi networks. CSMA is a
random-access algorithm, in the sense that it relies on randomness
to both avoid simultaneous transmissions and
share the medium in the most efficient way. Being intrisincally a random
ized scheme, many stochastic models
have been developed in the literature to study its performance in te
rms of throughput, stability, delay, and spatial
fairness, see e.g., [18] and references therein for a detailed overv
iew.
It is well-known that the delay performance of CSMA algorithms can b
e rather poor and much worse than for
other mechanisms, such as MaxWeight. One of the root causes for
these poor delay performances has been identified
in the
temporal starvation phenomenon
: even in scenarios where all nodes have a good long-term throughp
ut, they
may individually experience long sequences of transmissions in rapid su
ccession, interspersed with extended periods
of starvation. These starvation effects are particularly pronou
nced when the nodes become more aggressive in trying
to activate, which is the regime in which the network should operate t
o achieve maximum throughput.
Most of the literature focuses on single-channel CSMA algorithms,
in which all the transmission occur on
the same frequency. In this paper we consider the natural gener
alization in which multiple orthogonal frequency
channels are available; various variations of this multi-channel CSMA
model have been studied in [1, 2, 4, 5, 13,
15, 16]. Our ultimate goal is understanding whether temporal star
vation effects can be effectively mitigated by the
usage of multiple channels, as suggested in [13].
In order to make a fair comparison, we do not assume that additiona
l channels can be added to the existing
one, but rather that the total available wireless spectrum could be
divided into
C
non-overlapping channels with
smaller capacity on which nearby nodes can transmit without interfe
ring with each other. In this way, at the cost
of a potentially lower throughput, the starvation effects in the ne
twork can be alleviated or even eliminated and
in this way obtain substantial improvements in delay performance. T
he aim of the present paper is to investigate
this non-trivial trade-off and for this reason we analyze the aggr
egate throughput of multi-channel CSMA networks
and develop an analytical framework for quantifying temporal sta
rvation effects for these networks.
California Institute of Technology, Pasadena, US. Email:
azocca@caltech.edu
1
The temporal starvation in the context of multi-channel CSMA net
works has been mostly studied by means
of mixing times [13]. The large majority of these results, however, as
sumes either that the activation rate is very
small or that there are enough channels for all the nodes to be act
ive simultaneously, so that existing results for
multi-color Glauber dynamics can be exploited. The first crucial diffe
rence of our approach is that we are mostly
interested in the scenario in which the number of available channels do
es not allow simultaneous activity of all the
nodes. This creates a complex network dynamics in which nodes still c
ompete for transmission and phenomena
like temporal starvation and spatial unfairness persist. Further
more, instead of focusing on mixing times, inspired
by [11], we study temporal starvation by means of hitting times of th
e Markov process describing the CSMA
dynamics.
We focus on the regime in which the activation rate grows large, in whic
h the CSMA dynamics favors the
activity states with a maximum number of active nodes, to which we will
refer as
dominant states
. These activity
states play a crucial role in our analysis, since the timescales at which
transitions between them occur are intimately
related to the magnitude of the temporal starvation effects.
Our contributions can be summarized as follows.
We show that the multi-channel CSMA dynamics can be represented
as single-channel CSMA dynamics on
an appropriate virtual network, even when the possible interfere
nce on the different channels is described
by different conflict graphs. This equivalent representation allows
us to immediately derive the stationary
distribution of multi-channel CSMA dynamics and to prove its insensit
ivity to back-off and transmission time
distributions.
We prove various properties of the asymptotic aggregate throug
hput and, in particular, that is a non-
increasing function of the number
C
of available channels.
We show how the temporal starvation can be evaluated in the high-a
ctivation limit by studying the expected
transition times between the dominant activity states. Furthermo
re, we characterize the timescale of temporal
starvation phenomena in terms of the structure of the state spa
ce of the Markov process describing the CSMA
dynamics.
We analyze the mixing time of multi-channel CSMA dynamics using the sa
me framework built to study
the transition times between dominant states. Our analysis sugges
ts that in the high-activation regime the
mixing time does not always correctly characterize the temporal st
arvation timescale in multi-channel CSMA
networks, often leading to pessimistic performance estimates.
By means of various counterexamples, we show that many desirable
properties and performance indices are
not monotone in the number
C
of available channels, revealing the difficulty of finding analytically the
best
trade-off between throughput and temporal starvation effec
ts.
The rest of the paper is organized as follows. The CSMA network mod
els for both the single-channel and
multiple-channel case are described in Section 2. The equivalent rep
resentation for multi-channel CSMA networks is
presented in Section 3. In Section 4 we introduce the notion of domin
ant activity states and derive the properties of
the aggregate throughput. We show in Section 5 how we character
ize temporal starvation by looking at asymptotic
results for transition times between dominant states and relate it t
o structural property of the underlying state
space. Section 6 is entirely devoted to mixing times and to their relatio
n with the worst temporal starvation
timescale. Lastly, in Section 7 we discuss some generalizations of our
model and show how our framework extends
to them.
2 Model description
In this section we introduce the stochastic models that describe th
e dynamics of random-access networks operating
according to CSMA-like algorithms. We present first the model for t
he case of single-channel CSMA algorithm
and later its generalization to the multi-channel scenario. The two m
odels are presented separately for notational
convenience especially since in the next section we will show how the mu
lti-channel model has an equivalent
representation as single-channel model.
2.1 Single-channel CSMA network
We consider a network of transmitter-receiver pairs sharing a wire
less medium according to a CSMA-type algorithm.
A
node
indicates potential data transmission between a transmitter and a
receiver.
2
Every node can either be active or inactive, depending on whether t
he data transmission is ongoing or not. We
assume that the network consists of
N
such nodes, so that the network activity state can then be descr
ibed by an
N
-dimensional vector
x
, where
x
i
= 1 if node
i
is active and
x
i
= 0 otherwise.
We assume that the network structure and interference conditio
ns can be described by means of an undirected
finite graph
G
= (
V, E
), called
conflict graph
, where the set of vertices
V
=
{
1
, . . . , N
}
represents the nodes of the
network and the set of edges
E
V
×
V
indicate which pairs of nodes cannot be active simultaneously. There
fore,
neighboring nodes in the conflict graph are prevented from simultan
eous activity by the carrier-sensing mechanism.
We focus on the scenario where nodes are saturated, which means
that nodes always have packets available for
transmission and it is particularly relevant in high-load regimes. The tr
ansmission times of node
i
are independent
and exponentially distributed with mean 1
i
. When the transmission of a packet is completed, node
i
deactivates
(i.e., releases the medium) and starts a back-off period. The back-
off periods of node
i
are independent and
exponentially distributed with mean 1
i
. At the end of each back-off period node
i
activates
(i.e., starts the
transmission of a new packet) if and only if all its neighboring nodes on
G
are currently inactive.
Let
X ⊆{
0
,
1
}
N
be the set of all feasible joint activity states of the network. Since
the interference is modeled
by the conflict graph
G
, the set
X
consists of the incidence vectors of all independent sets of the co
nflict graph
G
:
X
:=
n
x
∈{
0
,
1
}
N
:
x
i
x
j
= 0
(
i, j
)
E
o
.
If we let
X
(
t
)
∈ X
denote the network activity state at time
t
, then the CSMA dynamics is described by a
continuous-time Markov process
{
X
(
t
)
}
t
0
on the state space
X
with transition rates between
x, y
∈X
given by
q
(
x, y
) :=
ν
i
if
y
=
x
+
e
i
∈X
,
μ
i
if
y
=
x
e
i
∈X
,
0 otherwise,
where
e
i
∈ {
0
,
1
}
N
is the vector with all zeros except for a 1 in position
i
. The Markov process
{
X
(
t
)
}
t
0
is
reversible [6] and has a product-form stationary distribution
π
(
x
) :=
Z
1
N
Y
i
=1

ν
i
μ
i

x
i
, x
∈X
,
(1)
where
Z
is the normalizing constant
Z
:=
X
x
∈X
N
Y
i
=1

ν
i
μ
i

x
i
.
The stationary distribution (1) is insensitive to the distributions of b
ack-off periods and transmission times, in the
sense that it depends on these only through their averages 1
i
and 1
i
, as proved in [17]. Hence, (1) holds in
fact for general back-off and transmission time distributions.
2.2 Multi-channel CSMA network
In this paper we consider a generalization of the saturated single-c
hannel CSMA model described in Subsection 2.1
where each node can sense the interference and transmit on any o
f the
C
available channels, but at most on one
at a time. We assume that for every
c
= 1
, . . . , C
all possible conflicts between nodes on channel
c
are described
by a conflict graph
G
c
= (
V, E
c
). Node
i
in the network has a different back-off timer for each of the
C
available
channels and we model these timers as
C
independent Poissonian clocks, ticking at rates
ν
i,
1
, . . . , ν
i,C
. When the
first of these
C
clocks rings for an inactive node, it activates on the corresponding
channel, say
c
, if and only if the
neighboring nodes of
i
in
G
c
are not active on the same channel. The transmission times of node
i
on channel
c
are independent and exponentially distributed with mean 1
i,c
.
A network activity state is described by a vector
x
∈ {
0
,
1
, . . . , C
}
N
where
x
i
= 0 if node
i
is inactive and
x
i
=
c
if node
i
is active on channel
c
with 1
c
C
. Let
X
C
be the collection of feasible network activity states,
which consists of all the vectors
x
∈ {
0
,
1
, . . . , C
}
N
such that for every
c
= 1
, . . . , C
two neighboring nodes in
G
c
are not simultaneously active on channel
c
, i.e.,
X
C
:=
{
x
∈{
0
,
1
, . . . , C
}
N
:
c
(
i, j
)
E
c
x
i
x
j
= 0
or
x
i
6
=
x
j
}
.
(2)
3
If the vector
X
C
(
t
)
∈X
C
describes the activity state of the network at time
t
, then
{
X
C
(
t
)
}
t
0
is a Markov process
on the state space
X
C
with transition rates between
x, y
∈X
C
given by
q
C
(
x, y
) =
ν
i,c
if
y
=
x
+
c
·
e
i
∈X
C
,
μ
i,c
if
y
=
x
c
·
e
i
∈X
C
,
0
otherwise.
(3)
Later we will briefly discuss a generalization of this multi-channel CSM
A model in which each node can possibly
be simultaneously active on more than one channel and discuss which
of our results extend to this setting, see
Section 7.
3 An equivalent representation for multi-channel CSMA netw
orks
In this section we argue that the evolution of a network using a multi-
channel CSMA algorithm can be equivalently
described as a
virtual network
operating under the single-channel CSMA algorithm on a modified con
flict graph
G
.
Consider the undirected graph
G
= (
V
, E
) with vertex set
V
:=
V
×{
1
, . . . , C
}
where two nodes (
i, c
) and
(
i
, c
) are adjacent if and only if
(
c
6
=
c
,
i
=
i
,
or
(
c
=
c
,
(
i, i
)
E
c
.
To avoid confusion with the original nodes, we refer to the nodes of
G
as
virtual nodes
. The activity state of the
virtual network is then represented by a 0-1 vector of length
C
·
N
and we denote by
X
⊂ {
0
,
1
}
C
·
N
the set of
admissible virtual activity states on
G
.
Define the function
V
:
X
→ X
C
that maps a virtual network state
x
∈ X
in the network state
V
(
x
)
∈ X
C
such that for every
i
= 1
, . . . , N
V
(
x
)
i
=
(
c
if
c
s.t.
x
(
i,c
)
= 1
,
0 otherwise
.
The function
V
is well defined, since for every
c
6
=
c
the virtual nodes (
i, c
) and (
i, c
) are neighbors in
G
and thus
only one of them can be active. Furthermore, it is easy to check tha
t
V
is a bijection, from which the following
lemma immediately follows.
Lemma 3.1.
The collection
X
of activity states on the virtual network
G
is in one-to-one correspondence with
the collection
X
C
of multi-channel activity states on
G
introduced in
(2)
.
Suppose further that the
C
·
N
virtual nodes in
G
operate using the single-channel CSMA algorithm described
in Subsection 2.1, assuming that the virtual node (
i, c
) has back-off periods that are exponentially distributed with
mean 1
i,c
and transmission periods that are exponentially distributed with mea
n 1
i,c
. The virtual network
activity evolves then as a continuous-time Markov process on
X
, which we denote as
{
e
X
(
t
)
}
t
0
.
It is easy to check that the transition rate between any two virtua
l network states
x
,
y
∈ X
is the same as
the transition rate given in (3) between the multi-channel activity s
tates
V
(
x
)
,
V
(
x
)
∈ X
C
. Hence, the processes
{
X
C
(
t
)
}
t
0
and
{
e
X
(
t
)
}
t
0
are two representations of the same Markovian dynamics, and if
X
C
(0) =
V
(
e
X
(0)),
then
X
C
(
t
)
d
=
V
(
e
X
(
t
))
,
t
0
.
This equivalent representation can be used in combination with (1) to
obtain the stationary distribution
π
C
of
the multi-channel activity process
{
X
C
(
t
)
}
t
0
, as illustrated by the following proposition.
Proposition 3.2.
The multi-channel network activity process
{
X
C
(
t
)
}
t
0
has product-form stationary distribution
π
C
(
x
) =
Z
1
N
Y
i
=1
C
Y
c
=1

ν
i,c
μ
i,c

1
{
x
i
=
c
}
, x
∈X
C
,
(4)
where
Z
is the appropriate normalizing constant.
We remark that multi-channel CSMA dynamics was already shown in [5
] to have a product-form distribution and,
in the special case where the interference is described by the same
conflict graph on every channel
E
1
=
···
=
E
C
,
also in [16]. Our proof approach based on this equivalent representa
tion recovers the same result in the most
general case and immediately shows that the insensitivity property
carries over to the stationary distribution (4)
of the multi-channel CSMA dynamics, which thus holds for general b
ack-off and transmission time distributions.
4
4 Dominant states and aggregate throughput
In this section we study how the number of channels
C
affects the performance in terms of aggregate throughput.
While increasing the number of channels evidently provides greater t
ransmission opportunities, the net impact on
throughput performance is non-obvious since the transmission ca
pacity per channel is inversely proportional to the
number of channels.
Consider a multi-channel CSMA network as described in Subsection 2
.2 and assume further that each of these
channels has capacity 1
/C
and that all the nodes have homogeneous activation and transmiss
ion rates, namely
ν
i,c
ν
and
μ
i,c
μ
c
= 1
, . . . , C,
i
= 1
, . . . , N.
Without loss of generality, we henceforth also assume that
μ
= 1. The stationary distribution (4) of the activity
process
{
X
C
(
t
)
}
t
0
then reads
π
C
(
x
) =
Z
1
N
Y
i
=1
ν
1
{
x
i
6
=0
}
=
Z
1
ν
a
(
x
)
, x
∈X
C
,
(5)
where
a
(
x
) :=
P
N
i
=1
1
{
x
i
6
=0
}
is the number
a
(
x
) of active nodes in
x
, regardless of the channels they are active on.
As (5) shows, when
ν >
1, the stationary probability of an activity state
x
∈ X
C
increases with its cardinality in
an exponential fashion.
Define
A
(
C
) to be the maximum number of active nodes in conflict graph
G
when
C
channels are available,
i.e.,
A
(
C
) := max
x
∈X
C
X
i
V
1
{
x
i
6
=0
}
= max
x
∈X
C
a
(
x
)
.
In this regime, the stationary distribution (5) favors the activity s
tates with a maximum number of active nodes.
We refer to such activity states as
dominant (activity) states
and denote by
D
C
their collection, i.e.,
D
C
:= arg max
x
∈X
C
a
(
x
) =
{
x
∈X
C
:
a
(
x
) =
A
(
C
)
}
.
In the rest of the section, we assume further that the same conf
lict graph
G
= (
V, E
) describes the interference
on all
C
channels, allowing us to draw a parallel between network activity sta
tes and colorings of the graph
G
.
In order to characterize the dominant states of a multi-channel C
SMA network, we need some further definitions.
A
vertex coloring
of the graph
G
is a labelling of the graph’s vertices with colors such that no two vertic
es sharing
the same edge have the same color. A
(proper)
C
-coloring
is a vertex coloring using at most
C
colors, see e.g.,
[3, 7]. The smallest number of colors needed to color a graph
G
is called its
chromatic number
, and is denoted as
χ
(
G
).
If
C
= 1, we are back in the single-channel scenario and the activity stat
es are in one-to-one correspondence
with the independent sets of the graph
G
. In particular,
A
(1) is equal to the cardinality
α
(
G
) of the maximum
independent set on
G
, often referred to as the
independence number
of the graph
G
.
For
C
2, we showed in Section 3 that the multi-channel activity on
G
is equivalent to the single-channel activity
on the virtual network
G
. Since we assumed
E
1
=
···
=
E
C
, the virtual network
G
is the Cartesian product of
G
and the complete graph with
C
nodes. In this scenario
A
(
C
) =
α
(
G
), where
α
(
G
) is the independence number
of the graph
G
, as proved [3, Lemma 1].
If the number of available channels in a CSMA network is larger than or
equal to the chromatic number of
the corresponding conflict graph, i.e.,
C
χ
(
G
), then every proper
C
-coloring of the graph
G
corresponds to a
dominant state for the network dynamics and, in particular,
A
(
C
) =
N
.
If instead
C < χ
(
G
), by definition of the chromatic number, a proper
C
-coloring of the graph
G
does not exist
and, in particular, there are no admissible activity states where all n
odes are active. All admissible activity states
correspond to
partial
C
-colorings
of the graph
G
. However, the problem of finding the maximum number of nodes
that can be active simultaneously in a general conflict graph
G
with
C
available channels is non-trivial, since it is
at least as hard as finding the maximum independent sets of
G
.
Since nodes are saturated, the
throughput
θ
i
(
C
) of node
i
is proportional to the long-run fraction of time that
node
i
is active and can be expressed as
θ
i
(
C
) :=
1
C
X
x
∈X
C
π
C
(
x
)
1
{
x
i
6
=0
}
,
(6)
5
where the constant 1
/C
accounts for the fact that each channel has capacity 1
/C
. Being a function of the stationary
distribution, the throughput is also insensitive to the distributions o
f the back-off and transmission times.
We analyze the
aggregate throughput
Θ(
C
) of a multi-channel CSMA network with
C
available channels in the
asymptotic regime where the activation rate
ν
grows large, defined as
Θ(
C
) := lim
ν
→∞
X
i
V
θ
i
(
C
) = lim
ν
→∞
X
i
V
1
C
X
x
∈X
C
π
C
(
x
)
1
{
x
i
6
=0
}
.
Even if it may be infeasible to calculate
A
(
C
) for a given random-access network using
C
channels, some conclusions
for its aggregate throughput Θ(
C
) can still be drawn, as illustrated by the following theorem.
Theorem 4.1
(Aggregate throughput)
.
The following statements hold for the aggregate throughput
Θ(
C
)
of a multi-
channel CSMA network where the same conflict graph
G
= (
V, E
)
describes the interference on all
C
channels:
(i)
Θ(
C
) =
A
(
C
)
/C
for every
C
1
;
(ii)
Θ(
C
) =
α
(
G
)
for every
1
C
C
(
G
)
, where
C
(
G
)
is the number of disjoint maximum independent sets
of the graph
G
;
(iii)
Θ(
C
) =
N/C
for every
C
χ
(
G
)
;
(iv)
Θ(
C
)
is a non-increasing function of the number of channels
C
.
Proof.
The definition of dominant state and (5) yield that
P
x
∈D
C
π
C
(
x
)
1 as
ν
→∞
, and thus
Θ(
C
) = lim
ν
→∞
X
i
V
1
C
X
x
∈X
C
π
C
(
x
)
1
{
x
i
6
=0
}
=
1
C
lim
ν
→∞
X
x
∈X
C
π
C
(
x
)
X
i
V
1
{
x
i
6
=0
}
=
A
(
C
)
C
lim
ν
→∞
X
x
∈D
C
π
C
(
x
) =
A
(
C
)
C
.
As mentioned earlier, when
C
χ
(
G
) there exists a proper
C
-coloring of the graph
G
, which means all nodes can
be simultaneously active and thus
A
(
C
) =
N
. Furthermore, it is easy to prove by induction that
A
(
C
) =
C
·
α
(
G
)
for every
C
C
(
G
). To prove (iv), we will show that the following inequality holds
A
(
C
+ 1)
C
+ 1
A
(
C
)
C
,
C
1
.
The inequality trivially holds when
C
χ
(
G
), since
A
(
C
) =
N
. The proof in the case
C
χ
(
G
) readily follows by
considering a (
C
+1)-coloring that yields
A
(
C
+1), pick the color that is used the least and discolor the correspon
ding
nodes, which are at most
A
(
C
+1)
C
+1
, obtaining a
C
-coloring with
A
(
C
+ 1)
−⌊
A
(
C
+1)
C
+1
⌋ ≥
C
C
+1
A
(
C
+ 1) colored
nodes. Using this newly obtained
C
-coloring we immediately get that
A
(
C
)
C
C
+1
A
(
C
+ 1).
In view of the fact that Θ(
C
) is a non-increasing function of the number of channels
C
, it seems that the network
should be operated using a single channel, but this is also the scenario
where temporal starvation phenomena and
spatial unfairness are often more pronounced.
Jain’s fairness index [9] is often used as a fairness measure in the con
text of random-access algorithms and we
consider here its asymptotic counterpart
J
(
C
) in the high-activation limit
ν
→∞
, i.e.,
J
(
C
) := lim
ν
→∞

P
N
i
=1
θ
i
(
C
)

2
N
P
N
i
=1
θ
i
(
C
)
2
.
One may conjecture that a larger number of available channels shou
ld always reduce the spatial unfairness in the
network. This is indeed true for many conflict graphs, but does not
hold in general. Figure 1 shows a particular
example of a network in which by adding an additional channel, the spa
tial unfairness worsens as
J
(2)
< J
(1).
As far as temporal starvation is concerned, we expect that by ex
ploiting more channels the temporal starvation
effects can be mitigated. However, making this dependence more e
xplicit is a challenging task, since the structure
of the conflict graph plays a crucial role via the parametric family
D
C
of dominant activity states. In general, a
non-trivial trade-off emerges between the magnitude of tempor
al starvation effects and the aggregate throughput
that the network can achieve and a balance can be found using a num
ber of channels in the range between 1 and
χ
(
G
).
6
(a) The three dominants states in
D
1
, which yield
J
(1) = 9
/
13
0
.
692
(b) The two dominants states in
D
2
, which yield
J
(2) = 2
/
3
0
.
667
Figure 1: Example of a network and its dominant states with
C
= 1 and
C
= 2 channels available, respectively.
5 Temporal starvation evaluation via transition times
In this section, we introduce a framework to study and quantify te
mporal starvation effects in multi-channel CSMA
networks in the high-activation regime
ν
→∞
.
When the activation rate grows large, the network spends roughly
the same fraction of time in each dominant
state. However, it takes a long time for the activity process to mov
e from one dominant state to the other, since
such a transition involves the occurrence of rare events. Indeed
, intuitively, the activity process must follow a
transition path through some activity states with fewer active nod
es which are highly unlikely in view of (5) and
the time to reach such activity states is correspondingly long.
We study the transitions between dominant states in terms of first
hitting times of the activity process
{
X
C
(
t
)
}
t
0
. In the limit
ν
→ ∞
the asymptotic behavior of the transition time between any pair of d
ominant
states can be characterized exactly on a logarithmic scale by study
ing the structural properties of state space
X
C
.
The main idea of our method is inspired by the concept of “traps” of t
he state space introduced in the context
of single-channel CSMA networks in [10, 11]. Traps are essentially s
ubsets of activity states where the activity
process remains for a long time before leaving. By focusing on the as
ymptotic regime
ν
→ ∞
, we can restrict
our analysis only to the traps corresponding to dominant states an
d, moreover, characterize the timescale of the
transitions between them without the need of a detailed description
of the structure of these traps.
In this section, we consider the multi-channel CSMA dynamics with ho
mogeneous rates as in Section 4 but here
we do
not
need to assume that the interference structure on different ch
annels is described by the same conflict
graph
G
. Note that the assumption of homogeneous rates across differe
nt nodes and channels is not crucial and in
fact it can be relaxed, but to keep the exposition simple we do not pre
sent here the general case and the interested
reader is referred to Section 7, where we illustrate also other gene
ralizations of our model for which this framework
is still valid.
Let
τ
x,A
(
ν
) := inf
{
t >
0 :
X
C
(
t
)
A
}
be the
first hitting time
of the subset
A
⊂ X
C
for the Markov process
{
X
C
(
t
)
}
t
0
starting in
x
at
t
= 0. For any
x, y
∈X
C
, we say that ø
⊂X
C
is a
path
from
x
to
y
in
X
C
, and denote
it by ø :
x
y
, if ø is a finite sequence of states ø
1
, . . . ,
ø
n
∈X
C
such that ø
1
=
x
, ø
n
=
y
and the CSMA dynamics
allows the step from ø
i
to ø
i
+1
for every
i
= 1
, . . . , n
1. The
communication height
between two states
x, y
∈X
C
is the minimum number of nodes (with respect to that of any dominant
state) that need to become simultaneously
inactive at some point along any path from
x
to
y
, i.e.,
∆(
x, y
) := min
ø:
x
y
max
z
ø
(
A
(
C
)
a
(
z
))
.
(7)
7
Both the notions of a path and communication height naturally exten
ds to the case of two subsets
A, B
⊂X
C
.
The communication height is a crucial quantity in our analysis since in th
e regime
ν
→ ∞
the most likely
trajectories from
x
to
y
are precisely those that achieve the min-max in (7). Indeed, all the
other trajectories
ø :
x
y
will visit at some point an activity state with fewer active nodes and th
us correspondingly more rare in
view of (5). The communication height ∆(
·
,
·
) defines an
ultrametric
on
X
C
, since
1. ∆(
x, y
)
0 and equality holds if and only if
x
=
y
;
2. ∆(
x, y
) = ∆(
y, x
);
3. ∆(
x, y
)
max
{
∆(
x, z
)
,
∆(
z, y
)
}
.
The second statement in property (1) holds since if
x
6
=
y
at every step of the CSMA dynamics the number of
active nodes must either increase or decrease by 1 and cannot sta
y constant along any path from
x
to
y
and, hence,
∆(
x, y
)
>
0.
For any
a
R
+
, we denote by log
ν
a
the logarithm in base
ν
. Since most of the results are in the limit
ν
→∞
,
we will henceforth assume that
ν >
1, so that log
ν
(
·
) is a strictly increasing function from
R
+
to
R
. The next
theorem shows that the communication height ∆(
s, D
) between a dominant state
s
∈D
C
and a subset
D
⊆D
C
\{
s
}
completely characterizes on a logarithmic scale the expected trans
ition time from
s
to
D
in the limit
ν
→∞
.
Theorem 5.1
(Timescale of transitions between dominant states)
.
For every dominant state
s
∈ D
C
and target
subset
D
⊆D
C
\{
s
}
of dominant states different from
s
, the following asymptotic equality holds
lim
ν
→∞
log
ν
E
τ
s,D
(
ν
) = ∆(
s, D
)
1
.
The proof of this result is presented in Subsection 5.1. We now illustra
te how Theorem 5.1 allows us to identify
the longest timescale for which each node of the network starves.
For each node
i
V
let
S
C
(
i
) :=
{
s
∈D
C
:
s
i
6
= 0
}
be the subset of dominant states in which node
i
is active. It is natural to study the temporal starvation only
for the nodes which are active in at least one dominant states, i.e.,
S
C
(
i
)
6
=
, and that are not active in every
dominant states, i.e.,
S
C
(
i
)
6
=
D
C
. For every such node
i
we define its
starvation index
as
Υ
i
(
C
) := max
s
∈D
C
\S
C
(
i
)
min
s
∈S
C
(
i
)
∆(
s, s
)
.
(8)
From property (1) of the communication heights it immediately follows
that Υ
i
(
C
)
1. We choose not to define
the starvation index of the nodes
i
V
such that
S
C
(
i
) =
, since these nodes do not properly suffer from
temporal
starvation, since they permanently starve in the limit
ν
→ ∞
having asymptotically zero throughput. Similarly,
Υ
i
(
C
) is not defined for any node
i
that is active in every dominant state of the network, i.e.,
S
C
(
i
) =
D
C
, since
any such node
i
does not starve in view of the fact that
P
x
∈X
C
π
C
(
x
)
1
{
x
i
6
=0
}
1 as
ν
→∞
.
The starvation index Υ
i
(
C
) captures the largest timescale at which node
i
suffers from temporal starvation at
stationarity in the high-activation regime
ν
→ ∞
. Indeed, Υ
i
(
C
) characterizes on a logarithmic scale how long it
takes the activity process to reach the subset
S
C
(
i
) of dominant states where node
i
is active when starting in the
worst possible dominant state in
D
C
\S
C
(
i
), as illustrated by the following identity
lim
ν
→∞
log
ν

max
s
∈D
C
\S
C
(
i
)
E
τ
s,
S
C
(
i
)
(
ν
)

= Υ
i
(
C
)
1
.
Lastly, we define the
starvation index of the network
as the worst starvation index of its nodes, i.e.,
Υ(
C
) :=
max
i
V
:
S
C
(
i
)
6
=
,
D
C
Υ
i
(
C
)
.
(9)
The index Υ(
C
) is a non-increasing function of the number of available channels for
all networks of which we
analyzed numerically the corresponding state spaces
X
1
, . . . ,
X
χ
(
G
)
1
. However, proving this claim analytically
is challenging in view of the intricate nature of the dominant states. I
ndeed, dominant states in
D
C
+1
are not
necessarily obtained from dominant states in
D
C
by activating a maximum number of inactive nodes on the
C
+1-th
channel, as illustrated for the network in Figure 2. Hence, there is n
o simple relation between the sets
D
C
and
D
C
+1
nor any other “monotonicity property” that one could leverage. I
n particular, this means that the maximum
in (9) may have to possibly be taken over different and/or non-nes
ted subsets of nodes when increasing
C
.
8
Figure 2: Example of a network with the unique dominant state
s
(1)
∈ D
1
(on the left) and two dominant states
s
(2)
, s
(3)
∈ D
2
(in the middle and on the right). In particular, the dominant
state
s
(2)
is not superset of the dominant state
s
(1)
.
5.1 Asymptotics for transition times between dominant stat
es
This subsection is devoted to the proof of Theorem 5.1. We first intr
oduce the uniformized discrete-time version
of the activity process, which will allow us to use classical results for
expected hitting times of reversible Markov
chains and their analogy with electrical networks, see e.g., [8, Sectio
n 2.1] and references therein.
In this subsection we will almost entirely suppress the subscript
C
for notational compactness, but the reader
should keep in mind that the results hold for a general multi-channel
CSMA dynamics as described in Subsection 2.2.
We consider the uniformized discrete-time version of the activity pr
ocess
{
X
C
(
t
)
}
t
0
. In more detail, we construct
a discrete-time Markov chain
{
e
X
(
t
)
}
t
N
starting from the continuous-time Markov process
{
X
C
(
t
)
}
t
0
by means
of uniformization at rate
q
max
:= max
x
∈X
C
P
y
6
=
x
q
(
x, y
) =
CN ν
. The transition probabilities of this Markov chain
read
P
(
x, y
) =
1
CN
ν
[
a
(
x
)
a
(
y
)]
+
if
d
(
x, y
) = 1
,
0
if
d
(
x, y
)
>
1
,
1
P
z
∈X
,z
6
=
x
P
(
x, z
) if
x
=
y,
where
d
(
x, y
) is the distance function on
X ×X
defined as
d
(
x, y
) :=
|{
i
V
:
x
i
6
=
y
i
}|
+
|{
i
V
:
x
i
6
=
y
i
and
x
i
y
i
6
= 0
}|
.
The quantity
d
(
x, y
) represents the minimum number of steps that the CSMA dynamics n
eeds to go from state
x
to state
y
; the second term on the right-hand side accounts for the fact th
at if a node is active on a channel
c
, the
immediate activation on another frequency
c
6
=
c
is not allowed and requires first the node to become inactive.
This distance function on
X
reflects the main difference between the multi-channel CSMA dyna
mics and
the classical multi-color Glauber dynamics, in which a node can change
channel/color in a single step (see [12,
Section IV.C] for more details). The two corresponding state spac
es, while still having the same states, have thus
fundamentally different structures and, in particular, there are
many more possible trajectories between dominant
states in the one corresponding to the Glauber dynamics. This fact
means that using Glauber dynamics to study
temporal starvation phenomena may lead to overly optimistic perfo
rmance bounds.
It is easy to check that (5) is the stationary distribution also for th
e uniformized chain
{
e
X
(
t
)
}
t
N
. Let
T
x,A
(
ν
) :=
inf
{
t
N
:
e
X
(
t
)
A
}
be the discrete-time counterpart of the first hitting time
τ
x,A
(
ν
). These hitting times are
closely related as
τ
x,A
(
ν
)
d
=
T
x,A
(
ν
)
X
i
=1
E
i
(
ν
)
,
where
{E
i
(
ν
)
}
i
N
are i.i.d. exponential random variables with mean
q
1
max
= (
CN ν
)
1
. In particular, it holds that
E
τ
x,A
(
ν
) = (
CN ν
)
1
E
T
x,A
(
ν
)
.
(10)
This equality shows that we can study the expected transition times
between dominant states in the discrete-time
setting where the theory is richer and then immediately translate th
em back for the continuous-time activity process
{
X
C
(
t
)
}
t
0
. We are now ready to present the proof of the main result of this se
ction.
Proof of Theorem 5.1.
We first introduce the following notation to asymptotically compare t
wo functions
f, g
:
R
R
: we write
f
(
ν
)
g
(
ν
) if
f
(
ν
) =
o
(
g
(
ν
)),
f
(
ν
)

g
(
ν
) if
f
(
ν
) =
O
(
g
(
ν
)) as
ν
→∞
and
f
(
ν
)
g
(
ν
) if both
f
(
ν
)

g
(
ν
) and
g
(
ν
)

f
(
ν
).
9
Furthermore, we will need some classical notions from the theory o
f reversible Markov chains on finite state
spaces. For every pair of states
x, y
∈ X
for which
P
(
x, y
)
6
= 0, we define the
resistance
of the edge
e
= (
x, y
) as
r
(
e
) =
r
(
x, y
) = (
π
(
x
)
P
(
x, y
))
1
. For any state
x
∈X
and subset
A
⊂X \{
x
}
, define then the
effective resistance
R
(
x
A
) :=
π
(
x
)
1
P
(
T
x,A
< T
+
x,x
) and the
critical resistance
Ψ(
x, A
) := min
ø:
x
A
max
e
ø
r
(
e
). As shown [8,
Proposition 2.2], effective resistance and critical resistance of th
e same pair of states are intimately related, namely
there exists a constant
k
1 independent of
ν
such that
1
k
Ψ(
x, A
)
R
(
x
A
)
k
Ψ(
x, A
)
.
(11)
As illustrated in [8, Section 2.1], the following identity holds for the expe
cted hitting time of the target subset
A
starting from a state
x
6∈
A
E
T
x,A
=
π
(
x
)
R
(
x
A
)
X
z
∈X
π
(
z
)
π
(
x
)
P
(
T
z,x
< T
z,A
)
,
(12)
Consider now the special case relevant for this theorem in which the
starting state is a dominant state, i.e.,
x
=
s
∈D
C
, and the target subset
D
is such that
D
⊆D
C
\{
x
}
. From (5) it immediately follows that
π
(
s
)
π
(
z
)
z
∈X \D
C
and
π
(
s
)

π
(
z
)
z
∈D
C
.
Using this fact and the identity (12) we deduce that
E
T
s,D
π
(
s
)
R
(
s
D
) as
ν
→ ∞
. In view of (11), it then
follows that
E
T
s,D
π
(
s
) Ψ(
s, D
)
,
as
ν
→∞
,
and thus
lim
ν
→∞
log
ν
E
T
s,D
= lim
ν
→∞
log
ν
π
(
s
) Ψ(
s, D
)
.
(13)
Consider the right-hand side of the latter identity. Using the definit
ion of critical resistance, it follows that
log
ν
π
(
s
)Ψ(
s, D
) = log
ν
min
ø:
s
D
max
e
ø
π
(
s
)
r
(
e
)
= log
ν
min
ø:
s
D
max
(
x,y
)
ø
π
(
s
)
π
(
x
)
P
(
x, y
)
= min
ø:
s
D
max
(
x,y
)
ø
log
ν
CN ν
A
(
C
)
ν
a
(
x
)
ν
[
a
(
x
)
a
(
y
)]
+
= log
ν
CN
+ min
ø:
s
D
max
(
x,y
)
ø
A
(
C
)
a
(
x
) + [
a
(
x
)
a
(
y
)]
+
= log
ν
CN
+ min
ø:
s
D
max
(
x,y
)
ø
A
(
C
)
(
a
(
x
)
a
(
y
))
= log
ν
CN
+ min
ø:
s
D
max
x
ø
A
(
C
)
a
(
x
)
= log
ν
CN
+ ∆(
s, D
)
,
(14)
where the third last passage above follows from the identity
a
(
x
) + [
a
(
x
)
a
(
y
)]
+
=
(
a
(
x
)
a
(
y
)), while the
second last one is a consequence of the fact that we take the maxim
um over
all the configurations visited by the
path
ø, rather than the edges crossed by the same.
Taking the limit in (14) we obtain lim
ν
→∞
log
ν
π
(
s
)Ψ(
s, D
) = ∆(
s, D
), which, combined with identity (13),
yields
lim
ν
→∞
log
ν
E
T
s,D
(
ν
) = ∆(
s, D
)
.
In view of (10), we have
lim
ν
→∞
log
ν
E
τ
s,D
(
ν
) = lim
ν
→∞
log
ν
(
CN ν
)
1
E
T
s,D
(
ν
) = lim
ν
→∞
log
ν
E
T
s,D
(
ν
) + lim
ν
→∞
log
ν
(
CN ν
)
1
= ∆(
s, D
)
1
,
and this concludes the proof.
10