BANDWIDTH MANAGEMENT 45

(Step 4 and Step 5) After obtaining the updated clique price

q

t( 1)µ +

, v(s) computes a per-hop

subﬂow price

s

t( 1)λ +

according to

+ = +

s q

q s V q

t t

: ( )

( 1) ( 1)

λ µ

Î

å

R

qs

for each ﬂow f that satisﬁes

s E f( )Î

, then sends

s

t( 1)λ +

to the source of f. For example, in Figure 3.1b, the delegation node

{3,2} receives the clique prices for clique q

1

, q

2

, and q

3

since it resides in all three maximal

cliques, i.e., any subﬂow going through the link {3,2} will have a subﬂow price

+ = + + + + +

q q q

t t t t

1 2 3

{3,2}

( 1) ( 1) ( 1) ( 1)

λ µ µ µ

+ = + + + + +

q q q

t t t t

1 2 3

{3,2}

( 1) ( 1) ( 1) ( 1)

λ µ µ µ

. In Figure 3.1a, ﬂows f

1

and f

3

are going through the wireless

link {3,2}, so the source node {1} for ﬂow f

1

and the source node {6} for ﬂow f

3

will receive the sub-

ﬂow price

{3,2}

λ

. Similarly, we calculate prices for all other subﬂows at each delegation node in V

c

and distribute the prices for subﬂows to the ﬂows’ sources (nodes in V ).

(Step 6 and Step 7) For the ﬂow f, its source node performs the task of rate update. When

the source node receives the per-hop prices l

s

(t), it computes the ﬂow price l

f

(t) according to

( ) ( )t t

f s

s s E f: ( )

λ λ

Î

=

å

and adjusts the rate x

f

according to x

f

(t + 1) = x

f

(l

f

(t)). It also notiﬁes

v(s) (

s E f( )Î

) of x

f

(t + 1). For example, in Figure 3.1a, the ﬂow price for f

1

, ﬂowing from

source node 1, through nodes 2, 3, 4, to destination node 5, will consist of per-hop subﬂow prices

λ λ λ λ

{1,2} {2,3} { 3,4} {4,5}

, , ,

. Note that the per-hop subﬂow prices consist of clique prices through which

the subﬂows pass. Since subﬂow {1,2} passes through one clique q

1

,

q

1

{1,2}

λ µ=

. On the other hand,

since the subﬂow {2,3} passes through three cliques,

+ = + + + + +

q q q

t t t t

1 2 3

{3,2}

( 1) ( 1) ( 1) ( 1)λ µ µ µ

.

Note that we are dealing with undirected graphs, hence, the price for subﬂow {2,3} is the same as

the price for subﬂow {3,2}. Similar considerations are taken when determining the per-hop subﬂow

prices

{3,4} {4,5}

λ λ, .

The overall ﬂow price for ﬂow f

1

is then:

Similar calculations apply to price calculations for ﬂows f

2

, f

3

, and f

4

in Figure 3.1.

3.2.4 Practical Issues

There are several practical issues to be considered in realistic ad hoc network environments. First,

our two-tier algorithm assumes that updates at the sources and the relaying nodes are synchronized

to occur at times t = 1,2,….. In realistic wireless networks, however, such synchronization is difﬁ-

cult to achieve. It means in an asynchronous environment, node v(q) which updates the price

q

t( )µ

at time t ∈ T

q

, (T

q

is a set of time instances at which master node v(q) updates m

q

.), may not have

the knowledge of rate information y

s

(t). Instead, it only knows the sequence of recent rate updates

1 2

q q

s s s s

y y( ) , ( ) ,....τ τ

which satisﬁes

1 2

t B

t

( ) ( ) ...- £ £ £ £

q q

s s

τ τ

, where B is the time interval when

last price

µ

q

was calculated.

One can improve the two-tier algorithm to an asynchronous setting, where sending rates

and clique prices are updated at different times at different nodes. For example, one approach

λ

f

1

(t) = λ

{1,2}

(t) + λ

{3,2}

(t) + λ

{3,4}

(t) + λ

{4,5}

(t) = [

µ

q

1

(t)] + [

µ

q

1

(t) +

µ

q

2

(t) +

µ

q

3

(t)] +

[

µ

q

1

(t) +

µ

q

2

(t) +

µ

q

3

(t)] + [

µ

q

2

(t)] = 3

µ

q

1

(t) + 3

µ

q

2

(t) + 2

µ

q

3

(t).

Get *Quality of Service in Wireless Networks Over Unlicensed Spectrum* now with O’Reilly online learning.

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