 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.