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 =

X∈S

|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

ρ

X∈S

X

i

, and thus this probability is

maximized when

X∈S

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 ﬁnd 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 efﬁcient distributed MAC schemes that solves the maximal matching

problem given the random and ﬂuctuating 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 ﬁxed 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 ﬁrst 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 deﬁnition:

I

j

(C

j

) =

r:A

jr

=0

ν

r

(1 − e

τ

C

j

A

jr

) + Cτ

C

j

where τ

C

j

satisﬁes:

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 deﬁnition:

∂τ

C

j

∂ν

r

=

−A

jr

e

A

jr

τ

C

j

r

ν

r

A

2

jr

e

A

jr

τ

C

j

Using this, the deﬁnition 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.