AU J.T. 12(4): 217-226 (Apr.

2009)

Local Routing in Multihop Networks

Dobri Atanassov Batovski
Faculty of Science and Technology, Assumption University,
Bangkok, Thailand
<dbatovski@[Link]>

Abstract

The overlapping of multihop paths in decentralized networks may cause

congestion at certain nodes and underutilization of other neighbor nodes. The choice of
a given path for the delivery of packets from source to destination makes other
connected nodes, located one hop away from the said path, prospective candidates for
local rerouting in case of substantial increase of the traffic rates. Two-hop local
rerouting is considered for general queuing with the use of the method of decomposition
for non-product networks. Rate-delay equalization of packet flows among two
concurrent local paths is used for splitting a packet flow for a given set of input
parameters. The analytic model is solved numerically for both M/M/1 and GI/G/1
queues at the individual nodes. Each node has a single output channel having different
service rates for packet delivery to different neighbor nodes .
Keywords: Rate-delay equalization, local routing, two-hop path, general queuing.

be considered in this contribution is to find the

Introduction optimal splitting ratio for a given packet rate so
that the two paths could be utilized in the most
The local routing in decentralized efficient way for a given set of input traffic and
networks becomes an important factor in the service parameters. The realistic scenario of a
establishment of reliable fault-tolerant paths for single output channel, where the service rate of
the delivery of packets over multiple hops. A the channel changes dynamically when packets
reason for the occurrence of packet drop is the are sent to different neighbors, is used to
increased utilization of some nodes which interpret the packets from queuing perspective
handle more traffic while there are similar local as different types of customers with their
paths along a chosen path, which can be used specific service rates. Also, each node can
to share the traffic load. Such local paths exist receive packets from several input channels
in variety of topological configurations. In well simultaneously where the incoming packets are
connected network configurations, the optimal stored in a single first-come first-serve (FCFS)
choices from a multitude of local paths are queue. This approach has been used by
made by solving a combinatorial problem. Batovski (2008) to implement the well known
A typical case, especially in planar method of decomposition (Pujolle and Wu
networks, is the rhombic configuration of four 1986) for the development of a custom network
connected nodes where two opposite nodes analyzer in multihop networks.
represent local source and destination and the The said approach can be used to analyze
remaining two nodes could be used as the properties of local routing as well. Local
intermediate nodes along two concurrent paths rate-delay optimization model (Inthawadee and
since each path consists of two hops as shown Batovski 2008) is to be defined for the chosen
in Fig. 1. The said configuration of four nodes rhombic configuration of two paths and used
seems topologically trivial but there are together with the method of decomposition to
challenging queuing issues associated with it. obtain a suitable analytic model.
The problem statement of local routing to

Regular Paper 217

AU J.T. 12(4): 217-226 (Apr. 2009)

N1 The traffic and service distributions of

N1 are described by the following pairs of
P1 known parameters related to: the background
LS DS traffic at N1, ( λ N 1, B , c N2 1, B ,λ ); the service
P2
distribution for the link N1→LD,
N2 ( μ N 1→ LD , c N 1→ LD , μ );
2
and the cumulative
Fig. 1. A sample rhombic configuration of four background traffic service distribution
connected nodes and two alternative paths. ( μ N 1, B , c N2 1, B ,λ ).
Similarly, the pairs of known parameters
Input Parameters of N2 are: ( λ N 2, B , c N2 2, B ,λ ); ( μ N 2→ LD , c N2 2→LD , μ );

Denote the four nodes in Fig. 1 as local and ( μ N 2, B , c N2 2, B , μ ).

source (LS), local destination (LD),
intermediate node N1 of local path P1 and
Analytic Model of Two-Hop Routing
intermediate node N2 of local path P2,
correspondingly.
The problem statement is to split the pair
The description of traffic and service
characteristics is considered in terms of the ( λ LS , c LS
2
,λ ) into two pairs: ( λ LS → N 1 , c LS → N 1,λ )
2

mean value and squared coefficient of variation and ( λ LS → N 2 , c LS

2
→ N 2 ,λ ), where:
(scv) of corresponding arbitrary distributions
assuming GI/G/1 queuing (Kleinrock 1975) at λ LS = λ LS → N 1 + λ LS → N 2 . (1)
each node.
Let the traffic to be relayed from LS to
LD be described by an arbitrary inter-arrival Node LS
distribution of mean λ LS and squared
The total arrival rate at LS is the sum of
2
coefficient of variation c LS ,λ . The remaining the rates of the chosen flows from LS to N1
traffic to be delivered to all alternative and N2 as well as the cumulative background
neighbors of LS is considered as a cumulative flow:
background traffic being described by a similar λ LS ,T = λ LS → N 1 + λ LS → N 2 + λ LS , B . (2)
arbitrary distribution of mean λ LS , B and
2 The total node utilization of LS is
squared coefficient of variation c LS , B ,λ .

The packet delivery from LS to N1 is ρ LS ,T = ρ LS → N 1 + ρ LS → N 1 + ρ LS , B (3)

described by an arbitrary service distribution of
where:
mean μ LS → N 1 and squared coefficient of
λ LS → N 1
ρ LS → N 1 =
2
variation c LS → N 1, μ . Similarly, the packet , (4)
μ LS → N 1
delivery from LS to N2 is described by another
arbitrary distribution with μ LS → N 2 and
λ LS → N 2
2
c LS → N 2 , μ . The cumulative service distribution
ρ LS → N 2 = , (5)
μ LS → N 2
for the background traffic is described by the
pair of parameters μ LS , B and c LS
2
,B,μ . λ LS , B
ρ LS , B = . (6)
Thus, the set of all input parameters of μ LS , B
LS consists of the aforesaid pairs:
Therefore, the mean service rate of LS is
( λ LS , c LS ,λ ), ( λ LS , B , c LS , B ,λ ), ( μ LS → N 1 , c LS → N 1, μ ),
2 2 2
derived from the reciprocal relationship for the
( μ LS → N 2 , c LS → N 2 , μ ) and ( μ LS , B , c LS , B , μ ).
2 2
total node utilization:

Regular Paper 218

AU J.T. 12(4): 217-226 (Apr. 2009)

λ LS ,T obtained:
μ LS ,T = . (7)
λ LS → N 1 λ LS → N 2 λ LS , B ρ LS → N 1 c LS → N 1,λ + c LS → N 1, μ
2 2
+ + DLS → N 1 = ρ LS → N 1 +
μ LS → N 1 μ LS → N 2 μ LS , B 1 − ρ LS ,T 2
2
The coefficient of variation c LS × φ ( ρ LS ,T , c LS
2 2
→ N 1,λ , c LS → N 1, μ ) , (13)
,B of the service

time of LS is given by the following expression

ρ LS → N 2 c LS → N 2,λ + c LS → N 2, μ
2 2
(Belch et al. 1998): DLS → N 2 = ρ LS → N 2 +
2 1 − ρ LS ,T 2
λ ⎛ μ LS ,T ⎞ 2
2
c LS = −1 + LS → N 1 ⎜ ⎟ (c LS → N 1, μ + 1) × φ ( ρ LS ,T , c LS
2 2
→ N 2 ,λ , c LS → N 2 , μ ) , (14)
λ LS ,T ⎜⎝ μ LS → N 1 ⎟⎠
,B

2 where the non-linear terms associated with

λ ⎛ μ LS ,T ⎞ 2 GI/G/1 queues, φ ( ρ LS ,T , c LS
⎜ ⎟ (c LS → N 2, μ + 1)
2 2
+ LS → N 2 → N 1,λ , c LS → N 1, μ ) and
λ LS ,T ⎜μ ⎟
⎝ LS → N 2 ⎠ φ ( ρ LS ,T , c LS
2 2
→ N 2 ,λ , c LS → N 2 , μ ) , are obtained using

2 the fit for arbitrary pairs of coefficients of

λ LS , B ⎛ μ LS ,T ⎞ 2 variation introduced by Whitt (1993):
+ ⎜ ⎟ (c LS , B , μ + 1) . (8)
λ LS ,T ⎜μ ⎟
⎝ LS , B ⎠ ⎧ 4(c A2 − c S2 ) c S2
⎪ 2 φ1 + 2 Ψ; c A2 ≥ c S2
The method of decomposition consists of ⎪ 4c − 3c 2
4c A − 3c S2
φ = ⎨ 2A 2 S ,
⎪ c S − c A φ + c S + 3c A Ψ; c 2 ≤ c 2
three distinct phases: merging, flow, and 2 2

splitting (Pujolle and Wu 1986, Belch et al. ⎪⎩ 2(c A2 + c S2 ) 3 2(c A2 + c S2 ) A S

1998).
The merging phase is performed on the (15)
basis of statistical averaging of arriving flows: ⎧ 1; c2 ≥1 c A2 + c S2
Ψ = ⎨ 2 (1−c 2 ) where c 2
= ,
1 ⎩φ 4 ; 0 ≤ c2 ≤1 2
,A = ,λ λ LS + c LS , B ,λ λ LS , B ) .
2 2 2
c LS (c LS (9)
λ LS ,T (16)
2
In fact, c LS , A could directly be measured at LS φ1 = 1 + γ , (17)
and its approximate calculation is optional.
Among several known alternatives, the φ 2 = 1 − 4γ , (18)
formula of Whitt (1983, 1983b) is used here for
the flow phase: ⎛ 2(1 − ρ ⎞
φ3 = φ 2 exp⎜⎜ − ⎟, (19)
c 2
= 1+ ρ 2
(c 2
− 1) ⎝ 3ρ ⎟⎠
LS , D LS ,T LS , B

+ (1 − ρ LS ⎧ φ1 + φ3 ⎫
,T )(c LS , A − 1) . φ 4 = min ⎨1,
2 2
(10) ⎬, (20)
⎩ 2 ⎭
2 2
Then c LS → N 1,λ and c LS → N 2 ,λ are obtained

during the splitting phase: ⎧ (1 − ρ )(m − 1)( 4 + 5m − 2) ⎫

γ = min ⎨0.24, ⎬,
λ LS → N 1 2 ⎩ 16mρ ⎭
2
c LS → N 1,λ = 1 + ( c LS ,D - 1), (11)
λ LS ,T (21)
where: ρ = λ/μ, λ is the mean arrival rate; μ is
λ the mean service rate; m is the number of
2
c LS → N 2 ,λ = 1 + LS → N 2 ( c LS
2
,D - 1). (12) servers; c A2 is the scv of the inter-arrival
λ LS ,T
process; and c S2 is the scv of the service-time
2 2
Knowing c LS → N 1,λ and c LS → N 2 ,λ , the distribution.
delay associated with each traffic flow can be For the chosen communication model
involving a single output server per node,
Regular Paper 219
AU J.T. 12(4): 217-226 (Apr. 2009)

assume that m = 1 (Batovski 2008). Then, λ Ni , B ⎛ μ Ni ,T

2
⎞ 2
whenever c A2 ≥ c S2 and c 2 = (c A2 + c S2 ) / 2 ≥ 1 , it + ⎜ ⎟ (c Ni , B , μ + 1) , (29)
λ Ni ,T ⎜μ ⎟
follows that φ = 1 and Eqs. (13) and (14) ⎝ Ni , B ⎠
reduce to the well-known Allen-Cunneen 1
,A = ,λ λ Ni + c Ni , B , λ λ Ni , B ) ,
2 2 2
approximation (Allen 1990): c Ni (c Ni (30)
λ Ni ,T
ρ LS → N 1 c LS → N 1,λ + c LS → N 1,λ
2 2

DLS → N 1 = ρ LS → N 1 + ,
1 − ρ LS ,T , D = 1 + ρ Ni ,T (c Ni , B − 1)
2 2 2
2 c Ni
(22)
+ (1 − ρ Ni2 ,T )(c Ni
2
, A − 1) , (31)
ρ LS → N 2 c
2
LS → N 2 ,λ +c 2
LS → N 2 ,λ
DLS → N 2 = ρ LS → N 2 + .
1 − ρ LS ,T 2 2 λ Nii → LD 2
c Ni → LD ,λ = 1 + ( c Ni ,D - 1), (32)
(23) λ Ni ,T
Similar formulae are used for the
ρ Ni → LD c Ni → LD ,λ + c Ni → LD , μ
2 2
calculation of c N2 1→ LD ,λ of node N1 and D Ni→ LD = ρ Ni → LD +
1 − ρ Ni ,T 2
c N2 2→ LS ,λ of node N2. For completeness, the
analytical expressions are included below. × φ ( ρ Ni ,T , c Ni
2 2
→ LD ,λ , c Ni → LD , μ ) , (33)

where:
Nodes N1 and N2
λ Ni = λ Ni → LD = λ LS → Ni , (34)
Due to the equivalence of the expressions
,λ = c LS → Ni ,λ .
2 2
for nodes N1 and N2, index i is used instead to c Ni (35)
denote each node, i = 1, 2. The total arrival rate
at Ni is the sum of the rate of the chosen flow
from each node Ni to LD as well as the Rate-Delay Equalization
cumulative background flow. Therefore:
The rate-delay (λD) product of each path
λ Ni ,T = λ Ni→ LD + λ Ni , B , (24)
P1 and P2 is obtained as follows:

ρ Ni ,T = ρ Ni → LD + ρ Ni , B , (25) λ LS → N 1 DP1 = λ LS → N 1 ( DLS → N 1 + D N 1→ LD ) , (36)

λ LS → N 2 DP 2 = λ LS → N 2 ( D LS → N 2 + D N 2→ LD ) . (37)
λ
ρ Ni → LD = Ni → LD , (26) During the rate-delay equalization
μ Ni → LD
process, the following system of two equations
is solved:
λ Ni , B
ρ Ni , B = , (27) λ LS → N 1 D P1 (λ LS → N 1 ) = λ LS → N 2 D P 2 (λ LS → N 2 ) ,
μ LNiB
(38)
λ Ni ,T λ LS = λ LS → N 1 + λ LS → N 2 , (39)
μ Ni ,T = , (28)
λ Ni → LD λ Ni , B
+ which reduces to a single nonlinear equation
μ Ni → LD μ Ni , B after substituting Eq. (39) in Eq. (38):
2 λ LS → N 1 D P1 (λ LS → N 1 ) =
λ ⎛ μ Ni ,T ⎞ 2
2
c Ni = −1 + Ni → LD ⎜ ⎟ (c Ni → LD , μ + 1) (λ LS − λ LS → N 1 ) D P 2 (λ LS − λ LS → N 1 ) . (40)
,B
λ Ni ,T ⎜μ ⎟
⎝ Ni → LD ⎠

Regular Paper 220

AU J.T. 12(4): 217-226 (Apr. 2009)

For the most general case of GI/G/1 LS: { λ LS , λ LS , B , μ LS → N 1 , μ LS → N 2 , μ LS , B , c LS

2
,λ ,
queuing at the individual nodes, Eq. (40) can 2 2 2 2
be rewritten in a more explicit form: c LS , B ,λ , c LS → N 1, μ , c LS → N 2 , μ , c LS , B , μ },

N1: { λ N 1, B , μ N 1→ LD , μ N 1, B , c N2 1, B ,λ , c N2 1→ LD , μ ,
ρ LS → N 1 → N 1,λ + c LS → N 1, μ
2 2
c LS
λ LS → N 1 [ ρ LS → N 1 + c N2 1, B , μ },
1 − ρ LS ,T 2
× φ ( ρ LS ,T , c LS
2 2 N2: { λ N 2, B , μ N 2→ LD , μ N 2, B , c N2 1, B ,λ , c N2 1→ LD , μ ,
→ N 1,λ , c LS → N 1, μ )
c N2 1, B , μ },
ρ N 1→ LD c N 1→ LD ,λ + c N 1→ LD , μ
2 2
the value of λ LS → N 1 can be obtained and the
+ ρ N 1→ LD +
1 − ρ N 1,T 2 resultant rate-delay product can be compared
× φ ( ρ N 1,T , c N2 1→ LD,λ , c N2 1→ LD, μ ) ] with the case when only one of the two paths is
utilized.
= (λ LS − λ LS → N 1 )[
ρ LS → N 2 c LS → N 2,λ + c LS → N 2,μ
2 2 M/M/1 Queuing
ρ LS → N 2 +
1 − ρ LS ,T 2 Eq. (42) can be further simplified for the
× φ ( ρ LS ,T , c 2
LS → N 2 ,λ ,c 2
LS → N 2 , μ ) private case of M/M/1 queuing (Kleinrock
1975) at the individual nodes (assuming that all
the squared coefficients of variation of both
ρ N 2→ LD c N 2→ LD ,λ + c N 2→ LD , μ
2 2

+ ρ N 2→ LD + traffic and service distributions are equal to 1),

1 − ρ N 2,T 2 as follows:
× φ ( ρ N 2,T , c N2 2→ LD ,λ , c N2 2→ LD , μ ) ]. (41) ρ LS → N 1 ρ
λ LS → N 1 [ ρ LS → N 1 + + ρ N 1→ LD + N 1→ LD
If the Allen-Cunneen approximation 1 − ρ LS ,T 1 − ρ N 1,T
(Allen 1990) can be applied for a given set of ]
input parameters, Eq. (41) reduces to:
ρ LS → N 2
ρ LS → N 1 c LS → N 1,λ + c LS → N 1, μ
2 2
= (λ LS − λ LS → N 1 )[ ρ LS → N 2 +
λ LS → N 1 [ ρ LS → N 1 + + 1 − ρ LS ,T
1 − ρ LS ,T 2
ρ N 1→ LD c N 1→ LD ,λ + c N 1→ LD , μ
2 2

ρ N 1→ LD + ρ N 2→ LD
1 − ρ N 1,T
] + ρ N 2→ LD + ]. (43)
2 1 − ρ N 2,T

= (λ LS − λ LS → N 1 )[ Expressing the node utilizations as a

function of the single variable, λ LS → N 1 , the
ρ LS → N 2 c LS → N 2,λ + c LS → N 2,μ
2 2

ρ LS → N 2 + following equation is obtained:

1 − ρ LS ,T 2
λ LS → N 1
λ LS → N 1 [
ρ N 2→ LD c
2
N 2→ LD ,λ +c 2
N 2→ LD , μ
μ LS → N 1
+ ρ N 2→ LD + ].
1 − ρ N 2,T 2
λ LS → N 1
(42)
μ LS → N 1
Equation (42) is a polynomial equation +
λ LS → N 1 (λ LS − λ LS → N 1) λ LS , B
which can be solved for λ LS → N 1 with standard 1− ( + + )
numerical methods. μ LS → N 1 μ LS → N 2 μ LS , B
For a given set of 22 input parameters
consisting of 11 (mean value, scv) pairs for the
three nodes LS, N1, and N2:

Regular Paper 221

AU J.T. 12(4): 217-226 (Apr. 2009)

λ LS → N 1 Clear[λLSN1, λLS, λLSB, μLSN1, μLSN2,

μLSB, λN1B, μN1LD, μN1B, λN2B, μN2LD,
λ LS → N 1 μ N 1→ LD
+ + ] μN2B];
μ N 1→ LD λ λ N 1, B
1 − ( LS → N 1 + ) λLS=0.2; λLSB=0.5; μLSN1=1.0; μLSN2=1.0;
μ N 1→ LD μ N 1, B μLSB=1.0; λN1B=0.6; μN1LD=0.9; μN1B=0.8;
λN2B=0.4; μN2LD=0.7; μN2B=0.9;
(λ LS − λ LS → N 1 )
= (λ LS − λ LS → N 1 ) [ + Plot[(λLSN1*((λLSN1/μLSN1)+((
μ LS → N 2 λLSN1/μLSN1)/(1.0-((λLSN1/μLSN1)+(( λLS-
(λ LS − λ LS → N 1 ) λLSN1)/μLSN2)+(λLSB/μLSB))))+(
λLSN1/μN1LD)+((λLSN1/μN1LD)/(1.0-
μ LS → N 2 ((λLSN1/μN1LD)+(λN1B/μN1B)))))),
+
λ LS → N 1 (λ LS − λ LS → N 1) λ LS , B ((λLS-λLSN1)*(((λLS-λLSN1)/μLSN2)+((( λLS-
1− ( + + )
μ LS → N 1 μ LS → N 2 μ LS , B λLSN1)/μLSN2)/(1.0-((λLSN1/μLSN1)+((λLS-
λLSN1)/μLSN2)+( λLSB/μLSB))))+((λLS-
(λ LS − λ LS → N 1 ) λLSN1)/μN2LD)+((( λLS-λLSN1)/μN2LD)/(1.0-
(((λLS-λLSN1)/μN2LD)+( λN2B/μN2B)))))),
μ N 2→ LD
{λLSN1, 0.0, λLS}, TextStyle -> {FontFamily ->
"Arial", FontSize -> 12}, Frame -> True,
(λ LS − λ LS → N 1 )
FrameLabel -> {"λLS -> N1", "Rate-Delay
μ N 2→ LD Product"}]
+ ]. (44)
(λ LS − λ LS → N 1 ) λ N 2, B Fig. 2. A sample source code for obtaining
1− ( + )
μ N 2→ LD μ N 2, B solutions of Eq. (44).

For a given set of 11 input parameters for M/M/1 queues

the three nodes LS, N1, and N2:
The ideal case of equal background
LS: { λ LS , λ LS , B , μ LS → N 1 , μ LS → N 2 , μ LS , B }, traffic rates and equal service rates is shown as
N1: { λ N 1, B , μ N 1→ LD , μ N 1, B }, an example of equal splitting of the initial rate
N2: { λ N 2, B , μ N 2→ LD , μ N 2, B }, λ LS among two equivalent paths P1 and P2.
The second example deals with different
the value of λ LS → N 1 can be easily obtained. service rates and the unequal splitting of the
initial rate λ LS between paths P1 and P2.
Computational Examples
Equal Background Traffic Rates and Equal
Service Rates of Paths P1 and P2
The simplest case of M/M/1 queues is
Consider the following set of input
considered first. A sample source code for
parameters (the highest mean service rate is
M/M/1 queues is shown in Fig. 2 where the
normalized to 1):
input parameters are presented similarly to
their appearance in Eq. (44). Two examples of LS: { λ LS = 0.2, λ LS , B = 0.5, μ LS → N 1 = 1,
solving Eq. (44) with Mathematica version 5.1
μ LS → N 2 = 1, μ LS , B = 1},
(2004) are provided for two different sets of
input parameters. N1: { λ N 1, B = 0.5, μ N 1→ LD = 1, μ N 1, B = 1},
The source code for GI/G/1 queues is not N2: { λ N 2, B = 0.5, μ N 2→ LD = 1, μ N 2, B = 1}.
shown here due to space limitations but it has a
similar structure and contains much more lines This example is provided as a
to include the node delay formulae and the demonstration that if traffic and service
formulae of the method of decomposition. conditions for both paths remain the same, the
traffic is equally split among paths P1 and P2.

Regular Paper 222

AU J.T. 12(4): 217-226 (Apr. 2009)

This is also a typical case of background

traffic when the congestion builds up and the
node utilization exceeds 40%. It is assumed
that multiple flows of packets contribute to the
background traffic.
A visual representation of the optimal
point of the rate-delay equalization problem is
shown in Fig. 3. The two curves in Fig. 3
represent the rate-delay product of paths P1 vs.
λ LS → N 1 and the rate-delay product of path P2
vs. λ LS → N 2 , where λ LS → N 2 = λ LS - λ LS → N 1 . The
crossing point between the two curves is the Fig. 4. Sample graphical solution of rate-delay
optimal point of λ LS → N 1 for which the balance equalization problem for equal traffic rates and
different service rates of paths P1 and P2.
of the two traffic flows is achieved.
GI/G/1 Queues
Equal Background Traffic Rates and
Different Service Rates of Paths P1 and P2 The use of the method of decomposition
Consider the following set of input for GI/G/1 queues is illustrated for three sets of
parameters: input parameters of the three nodes LS, N1,
LS: { λ LS = 0.2, λ LS , B = 0.5, μ LS → N 1 = 1, and N2. Figures 5-7 shown below include the
solutions obtained for M/M/1 queues, GI/G/1
μ LS → N 2 = 1, μ LS , B = 1}, queues with the Allen-Cunneen approximation,
N1: { λ N 1, B = 0.1, μ N 1→ LD = 1, μ N 1, B = 1}, and GI/G/1 queues with the Whitt formula.
N2: { λ N 2, B = 0.1, μ N 2→ LD = 0.35, μ N 2, B =
Equal Background Traffic Rates, Equal
0.35}. Service Rates and Different SCVs of Paths P1
In this example, the service rates of path and P2
P1 are greater than the service rates of path P2. Consider the following set of input
The result of rate-delay equalization is shown parameters:
in Fig. 4. The optimal point is shifted to the LS: { λ LS = 0.2, λ LS , B = 0.5, μ LS → N 1 = 1,
right indicating that the traffic rate λ LS → N 1 of
μ LS → N 2 = 1, μ LS , B = 1, c LS
2 2
,λ = 1, c LS , B ,λ = 1,
path P1 is greater than the traffic rate λ LS → N 2 2 2 2
c LS → N 1, μ = 1, c LS → N 2 , μ = 1, c LS , B , μ = 1},
of path P2.
N1: { λ N 1, B = 0.5, μ N 1→ LD = 1, μ N 1, B = 1,
c N2 1, B ,λ = 4, c N2 1→ LD , μ = 4, c N2 1, B , μ = 4},
N2: { λ N 2, B = 0.5, μ N 2→ LD = 1, μ N 2, B = 1,
c N2 1, B ,λ = 0.5, c N2 1→ LD, μ = 0.5, c N2 1, B , μ = 0.5}.

The SCVs of path P1 are set to 4 and the

SCVs of path P2 are set to 0.5. The optimal
point of rate-delay equalization is shown in
Fig. 5. The optimal λ LS → N 1 is shifted to the left
so that λ LS → N 1 < λ LS → N 2 . The solution obtained
Fig. 3. Sample graphical solution of rate-delay for M/M/1 queues is identical with the one
equalization problem for equal background shown in Fig. 3 and is provided here for
traffic rates and equal service rates of paths comparison. No significant difference is
P1 and P2.
observed for graphs obtained with the Allen-
Regular Paper 223
AU J.T. 12(4): 217-226 (Apr. 2009)

Cunneen approximation and with the Whitt

formula and the said graphs almost coincide
with each other. The differences in the SCVs
have an effect similar to the one observed for
different service rates of paths P1 and P2.
Therefore, the knowledge of the second
GI/G/1
moment of traffic and service distributions
could allow certain adjustment of the optimal
M/M/1
λ LS → N 1 if the distributions are non-exponential.

Different Background Traffic Rates and Fig. 5. Sample graphical solution of rate-delay
Service Rates and Different SCVs of Paths P1 equalization problem for equal background
and P2 traffic rates, equal service rates and different
Consider the following set of input SCVs of paths P1 and P2.
parameters:
LS: { λ LS = 0.2, λ LS , B = 0.5, μ LS → N 1 = 1,
μ LS → N 2 = 1, μ LS , B = 1, c LS
2 2
,λ = 1, c LS , B ,λ = 1,
2 2 2
c LS → N 1, μ = 1, c LS → N 2 , μ = 1, c LS , B , μ = 1},

N1: { λ N 1, B = 0.5, μ N 1→ LD = 1, μ N 1, B = 1, GI/G/1

2 2 2
c N 1, B ,λ = 4, c N 1→ LD , μ = 4, c N 1, B , μ = 4},
M/M/1
N2: { λ N 2, B = 0.5, μ N 2→ LD = 0.75, μ N 2 , B =0.75,
c N2 1, B ,λ = 0.5, c N2 1→ LD , μ = 0.5, c N2 1, B , μ = 0.5}.
Fig. 6. Sample graphical solution of rate-delay
The SCVs of path P1 are set to 4 and the equalization problem for different background
SCVs of path P2 are set to 0.5. The service traffic rates and service rates and different
rates of path P2 are reduced to 0.75. The SCVs of paths P1 and P2.
optimal point of rate-delay equalization is
shown in Fig. 6. The optimal solution, Congested Single Paths
λ LS → N 1 ≈ λ LS → N 2 , is located at the center of the Consider the following set of input
parameters:
graph and can be interpreted in terms of the
mutual compensation of two opposing LS: { λ LS = 0.2, λ LS , B = 0.5, μ LS → N 1 = 1,
tendencies, a shift to the left in favor of path P2 μ LS → N 2 = 0.4, μ LS , B = 1, c LS
2 2
,λ = 1.5, c LS , B ,λ =
due to the higher SCVs (uncertainties) of path 2 2 2
1.1, c LS → N 1, μ = 1.1, c LS → N 2 , μ = 1.1, c LS , B , μ =
P1 and another shift to the right in favor of path
P1 due to the lower service rates of path P2. 1},
The solution obtained for M/M/1 queues is N1: { λ N 1, B = 0.2, μ N 1→ LD = 0.4, μ N 1, B = 0.4,
shifted to the right, λ LS → N 1 > λ LS → N 2 , due to the c N2 1, B ,λ = 4, c N2 1→ LD, μ = 4, c N2 1, B , μ = 4},
reduced service rates of path P2.
N2: { λ N 2, B = 0.5, μ N 2→ LD = 1, μ N 2, B = 1,
This example shows that both first and
second moments of traffic and service c N2 1, B ,λ = 1.1, c N2 1→ LD, μ = 1.1, c N2 1, B , μ = 1.1}.
distributions play an important role in shifting The optimal point of λ LS → N 1 for rate-
the optimal point of λ LS → N 1 . The most
delay equalization is shown in Fig. 7. The
significant shifts are to be expected when result indicates that the reduced service rates of
service rates increase and SCVs decrease for both paths could follow to congestion if only
one of the paths as compared to the second one. one of the paths is utilized. The splitting of λ LS
greatly improves the performance.
Regular Paper 224
AU J.T. 12(4): 217-226 (Apr. 2009)

rates after rate-delay equalization do not

exceed the service rates or specific node
utilization thresholds above which packet
traffic drop is initiated. The exact level of
performance depends on the specific set of
parameters for a given scenario.
It should be noted that more precise
results with the method of decomposition for
small or big SCVs can be obtained with a
complex modification proposed by Whitt
(1994). Small SCVs in wireless networks being
related to quasi-deterministic traffic and
Fig. 7. Sample graphical solution of rate-delay
service distributions are to be expected in some
equalization problem for congested single
paths.
private cases with low congestion levels in
efficiently configured wireless network
topologies and high service rates for channels
Analysis and Discussion with high signal-to-noise ratios.

The obtained graphs show that it is not

mandatory to obtain the exact optimization Conclusion
point of rate-delay equalization in order to have
a significant improvement of the performance. The local routing along a rhombic
The slow increment of intersecting curves configuration of four nodes is considered for a
around the optimal point allows one to use sub- given packet flow assuming that the
optimal solutions with the same success. This information about all other flows is interpreted
is quite obvious especially for the case of in terms of known background traffic. The
strong congestion as shown in Fig. 7 where a proper splitting of a traffic flow among two-
wide plateau is formed around the optimal hop local paths P1 and P2 requires the
exchange of control packets only one hop away
point and any choice of λ LS → N 1 within the
from each node. Thus the local topology
plateau could significantly improve the forming a loop of four connected nodes is
performance of local packet relaying as estimated to be most reliable among other
compared to the long delays at the edges of the alternatives because the local rerouting
displayed graphs. involving more than two hops is unstable in
The provided numerical examples decentralized networks in mobile environment.
demonstrate that the optimization problem for Also, it is more difficult to provide real-time
the rhombic configuration of four nodes is optimization with the substantial increase of
easily solvable numerically and fast sub- the number of parameters to be shared more
optimal algorithms could possibly be than one hop away from each node.
implemented in decentralized networks Note that a loop of three nodes is to be
whenever a loop of four nodes is formed considered as a private case and a
locally for a certain period of time. simplification of the four-node loop. In the
The analysis of different traffic and triangular case, one local path consists of a
service scenarios follows to the conclusion that single hop and the second path has two hops.
the performance in terms of delay optimization Such scenario could be beneficial in some
can be improved up to one order of magnitude cases when the single-hop path has
in cases of uncongested and slightly congested substantially lower service rates and higher
local paths and up to two orders of magnitude SCVs (uncertainties) than the two-hop
in extreme cases of strongly congested local alternative.
paths. The throughput is also improved and in
most scenarios remains optimal if the traffic

Regular Paper 225

AU J.T. 12(4): 217-226 (Apr. 2009)

Volume 1: Theory, Wiley Interscience, New

References York, NY, USA.
Mathematica. 2004. Version 5.1. Wolfram
Allen, A.O. 1990 Probability, statistics and Research, Inc., Champaign, IL, USA.
queueing theory with computer science Pujolle, G., and Wu, A. 1986. A solution for
applications. Academic Press Professional, multiserver and multiclass open queueing
Inc., San Diego, CA, USA. networks. Information Systems and
Batovski, D.A. 2008 Semi-analytic evaluation Operations Research 24(3): 221-30.
of quality of service parameters in multihop Whitt, W. 1983. The queueing network
networks. Assumption University Journal of analyzer. Bell System Technical Journal
Technology (AU J.T.) 11(4): 215-224, 62(9): 2779-815, November.
April. Whitt, W. 1983b. Performance of the queueing
Belch, G.; Greiner, S.; de Meer, H.; and network analyzer. Bell System Technical
Trivedi, K.S. 1998. Queueing networks and Journal 62(9): 2817-43, November.
Markov chains: Modeling and performance Whitt, W. 1993. Approximations for the
evaluation with computer science GI/G/m queue. Production and Operations
applications. Wiley-Interscience, John Management 2(2): 114-61, Spring.
Wiley & Sons, Inc., New York, NY, USA. Whitt, W. 1994. Towards better multi-class
Inthawadee, S.; and Batovski, D.A. 2008. Flow parametric-decomposition approximations
control in distributed gateways. Annals of for open queueing networks. Annals of
Telecommunications 63(9-10): 523-527, Operations Research 48: 221-48.
September-October.
Kleinrock, L. 1975. Queueing systems,

Regular Paper 226