90 LOSS MODELS FOR NETWORKS
is random of length σ
i
and ρ
i
= λ
i
E[σ
i
]. Assuming the durations are all independent, then let X(t)
denote the vector of links with X
i
(t) = 1 if link i is transmitting at time t.Then it is easy to see that
the equilibrium distribution of X(t) is given by:
π(X) =
1
G
|E|
i=1
ρ
X
i
i
,X S (3.32)
where G =
XS
|E|
i=1
ρ
X
i
i
.
This is a simple loss network model of links with capacity 1 and requests requiring 1 unit of
capacity. It is interesting to examine the behavior of the equilibrium distribution. Suppose the nodes
have identical behavior, i.e., ρ
i
= ρ. In that case, π(X) =
1
G
ρ
XS
X
i
, and thus this probability is
maximized when
XS
X
i
is largest, i.e., X
i
belongs to the largest independent set– called the
maximal matching. This set corresponds to the largest throughput assuming the load is ρ. Thus,
we see that in the homogeneous case, the protocol model leads to the situation where the network
is in the state corresponding to the maximal independent set or matching with highest probability.
One implication of this result is that nodes at the center of a network are less likely to be in many
independent sets and thus might suffer from unfairness of access.Thus, MAC scheduling algorithms
that try to find the maximal matching for a given set of channel conditions (links that can be
simultaneously ON) must also take into account the inherent unfairness arising from the geometry
of the network. Much of the current research in so-called multi-hop ad hoc wireless networks
focusses on trying to develop efficient distributed MAC schemes that solves the maximal matching
problem given the random and fluctuating channel conditions while trying to provide fair access to
all nodes.
3.8 SOME PROPERTIES OF LARGE MULTI-RATE SYSTEMS
We have seen that multi-rate Erlang loss systems with complete sharing (when all classes of arrival
requests can access the available bandwidth without restrictions) result in stationary systems with
product-form probabilities for the joint probability of number of calls in progress.
One of the nice consequences of the product-form structure is the elasticity property given
below:
P
B
m
∂ν
k
=
P
B
k
∂ν
m
, 1 k, m R. (3.33)
In other words, the sensitivity of the blocking of class m to changes in the class k rates is equal
to the sensitivity of the class k blocking to the class m rates. However, as mentioned earlier there
is no general monotonicity property for the blocking in multi-rate loss systems as was seen in the
single rate classical Erlang loss formula i.e., increasing the rates of a given class does not necessarily
increase the overall blocking in the system.
In large loss systems in the lightly loaded regime, monotonicity does occur, and this has im-
portant consequences in using the single-link approximations to develop Erlang fixed point methods
as well as blocking sensitivity based routing algorithms. We now discuss these issues.
3.8. SOME PROPERTIES OF LARGE MULTI-RATE SYSTEMS 91
If we examine the formula for blocking in the uniform light load case, (3.25), we note that
the blocking on route r is given by:
P
B
r
=
j,A
j,r
=0
B
jr
1 + O(
1
N
)
(3.34)
where B
jr
can be seen as the single link blocking formula for class r at link j that belongs to route
r given by equation (3.20). We see that the blocking formula depends on the behavior of the rate
function I
j
(C
j
) in the first order approximation (in terms of N).
Lemma 3.11 Let I
j
(C
j
) be the rate function corresponding to the measure change on a link j with
capacity C
j
. Let ν
r
denote the arrival rate of a connection of type r on that link and assume that
r:A
j,r
=0
ν
r
A
jr
<C
j
i.e., the link is lightly loaded. Then:
∂I
j
(C
j
)
∂ν
r
< 0 (3.35)
Proof. First note that by definition:
I
j
(C
j
) =
r:A
jr
=0
ν
r
(1 e
τ
C
j
A
jr
) +
C
j
where τ
C
j
satisfies:
C
j
=
r
e
A
jr
τ
C
j
ν
r
A
jr
Noting that
r:A
jr
=0
A
jr
ν
r
<C
j
, we see that τ
C
j
> 0. Noting that from the definition:
∂τ
C
j
∂ν
r
=
A
jr
e
A
jr
τ
C
j
r
ν
r
A
2
jr
e
A
jr
τ
C
j
Using this, the definition of I
j
(C
j
) and the fact that e
A
jr
τ
C
j
> 1 whenever A
jr
= 0 we obtain:
∂I
j
(C
j
)
∂ν
r
= 1 e
A
jr
τ
C
j
< 0
2
Using this result, we can show the following monotonicity property for blocking in large loss
networks that is not true in small networks.

Get Performance Modeling, Loss Networks, and Statistical Multiplexing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.