TELKOM
NIKA
, Vol.12, No
.3, Septembe
r 2014, pp. 7
25~732
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v12i3.102
725
Re
cei
v
ed Fe
brua
ry 17, 20
14; Re
vised
May 11, 20
14
; Accepte
d
Ju
ne 8, 2014
Maximization Network Throughput based on Maximal
Flow for Single-Source Two-Destinations Multicast
Huanlin Liu*,
Ruiy
an Li, L
i
ang Qin, Sheng Hu
ang
Schoo
l of Com
m
unic
a
io
n an
d Information En
gin
eeri
ng, Ch
o
ngi
qng U
n
iv
ers
i
t
y
of Posts an
d
T
e
lecommunic
a
tions
Cho
n
g
w
e
n
R
o
ad 2#, Na
n’
an
District, Chon
g
q
in
g Cit
y
,
4
0
0
0
65, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: liuhl
2@si
na.c
o
m
A
b
st
r
a
ct
F
o
r guara
n
te
ein
g
all
multic
ast destinati
o
n
nodes
rec
e
ivi
ng the sourc
e
informatio
n
with thei
r
max
i
mal fl
ow
respectiv
e
ly a
n
d
obta
i
ni
ng t
h
e
netw
o
rk
maxi
ma
l thro
ugh
put
, a he
uristic a
l
gorith
m
base
d
on
netw
o
rk codin
g
, Maximal F
l
ow
for Single-
source
T
w
o-destinati
ons Mu
lticast (MF
STM) is propose
d
t
o
max
i
mi
z
e
t
he
netw
o
rk throu
g
hput. By ca
lcul
ating th
e
e
a
ch
destin
a
tio
n
’
s
maxi
mal
flow
, the nu
mber
of lin
k-
disjo
i
nt p
a
ths
w
h
ich eq
ua
ls to desti
nati
o
n
’
s
max
i
mal fl
ow
, are se
arche
d
for each
desti
n
a
tion to c
onstr
uct
the netw
o
rk codi
ng gr
aph.
A heuristic
alg
o
rith
m bas
ed
on netw
o
rk co
din
g
is des
ign
ed to de
lete t
h
e
redu
nda
nt link
in the netw
o
rk codi
ng gr
aph a
nd
g
uar
antee th
e net
w
o
rk through
p
u
t maxi
mi
z
a
ti
o
n
.
Co
mp
arin
g the
traditio
nal
ma
ximal
mu
lticast
stream
al
gorit
hm bas
ed on netw
o
rk
codi
n
g
,
the
si
mu
lati
on
results show
that the MF
ST
M algor
ith
m
makes tw
o des
ti
natio
ns rece
iv
e the infor
m
ati
on at the sp
ee
d of
their maxi
mal
flow
respectively, and
dec
ode th
e s
ourc
e
nod
e infor
m
ation at e
a
ch
destinati
on n
o
d
e
successfully.
Ke
y
w
ords
: mu
lticast netw
o
rks; netw
o
rk coding; netw
o
rk
throug
hp
ut; maxi
ma
l flow
; heuri
s
tic algor
ith
m
1. Introduc
tion
Gro
w
th
with t
he a
ppli
c
atio
ns
of poi
nt to
mu
ltipoint
a
pplication
s
, such
a
s
hi
gh-definition
Internet tel
e
vision, vid
eo
confe
r
en
cin
g
, di
st
ributed
v
i
deo game
s
and storage
data
n
e
two
r
ks,
multica
s
t app
lication
s
hav
e increa
sed
rapidly in
future net
works
[1]-[2]. It was
proved that t
he
multica
s
t ma
ke
s n
e
two
r
k
throug
hput
d
r
op
mu
ch [3]
.
And it i
s
di
fficult to rea
c
h the
network
maximal thro
ughp
ut for multica
s
t. Network
codi
ng
was propo
se
d by Ahlswe
de
et al in 2000 to
maximize th
e sin
g
le so
urce multi
c
a
s
t ca
pa
city, whi
c
h let
s
a
ll destinatio
n
node
s rece
ive
informatio
n from
sou
r
ce n
ode
at the
m
a
ximal mult
i
c
ast
spe
ed [4]
.
Li et
al p
r
o
v
ed that lin
e
a
r
netwo
rk
codi
ng ca
n get the multica
s
t capa
city [5].
Koetter et al provided a con
s
tru
c
tion of linea
r
netwo
rk
codi
ng by t
he
alg
ebrai
c metho
d
[6]. Refere
nce
s
[7]
-
[9] furthe
r
study t
he a
ppli
c
atio
ns
of
linear net
work
codin
g
in t
he net
wo
rk.
Referen
c
e [1
0]-[12] p
r
opo
sed
many m
a
ximal multicast
strea
m
alg
o
rit
h
m ba
se
d o
n
network
codi
ng (NC)
al
gorithm to increas
e
t
he n
e
twork through
p
u
t.
But previou
s
resea
r
che
s
a
bout maximal
multic
a
s
t ca
pacity ba
se
d
on net
work
coding
ca
n on
ly
ensure th
at al
l of the destin
a
tion nod
es
receive t
he i
n
formatio
n at the same
spe
ed, the maxi
mal
multica
s
t cap
a
city, which make
s
some
node
s can
no
t achieve thei
r maximal re
ceiving ca
pabil
i
ty
(nod
e’s
maximal flow) and
kee
p
s the
m
from g
e
tting the net
work m
a
ximal throu
g
hput. Accordi
n
g
to maximal-flow-minimal
-cut theory, wh
en each de
st
ination re
ceiv
es informatio
n at the spee
d of
their maximal
flow re
spe
c
ti
vely, the network
c
an g
e
t the maximal
throug
hput. But in the act
ual
netwo
rk, it is
usu
a
l that the multicast
cap
a
ci
ty is not m
o
re than e
a
ch
node’
s maximal flow.
Figure 1
sho
w
s th
e relatio
n
shi
p
of the
maximal mult
ica
s
t ca
pa
city and n
ode’
s
maximal
flow. In the
netwo
rk, th
e
cap
a
city of
each
lin
k is
just 1, multi
c
ast’s
so
urce
node i
s
S
a
nd
destin
a
tion
s are
t
1
and
t
2
resp
ectively.
Acco
rdi
ng to
the maxim
a
l-fl
ow-minimal
-cut theory,
we
can
cal
c
ulate th
e
maximal flo
w
s
of de
stin
ation no
de
s
t
1
and
t
2
are
4 and
2, re
spectively. So
the
maximal mult
ica
s
t ca
pa
city is 2, which
is eq
ual to
minimum val
ue of
4 and 2.
In
Figu
re 1,
according
to
the lin
k-di
sj
oint ro
ute p
r
incipl
e, the
destin
a
tion
s
t
1
and
t
2
ca
n only recei
v
e
informatio
n at
maximal
sp
e
ed 1.
Wh
en t
he n
e
two
r
k coding
is used
, the de
stinati
ons
t
1
and
t
2
can
receive the in
formation
at maximal spe
ed 2. And it
i
s
le
ss th
an th
e maximal re
ceive
cap
abili
ty o
f
destin
a
tion
t
1
. How to m
a
ke all de
stinati
on nod
es
re
ceiv
e informati
on from
sou
r
ce at spee
d
of
their maxim
a
l
flow valu
e a
nd en
su
re
de
codi
ng info
rmation
corre
c
tly at ea
ch
destin
a
tion i
s
an
urge
nt p
r
oble
m
[13]. In thi
s
p
ape
r, we
prop
ose MFS
T
M alg
o
rithm
,
a heu
ri
stic
algorith
m
ba
sed
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 3, September 20
14: 72
5 – 732
726
on n
e
two
r
k
codi
ng to
co
nstru
c
t th
e n
e
twork
co
din
g
graph,
whi
c
h
ca
n ma
ke two
multicast
destin
a
tion
n
ode
s
re
ceive
the i
n
form
ation from
so
u
r
ce
n
ode
at
spe
ed
of the
i
r maxim
a
l fl
ow
respe
c
tively and ca
n de
cod
e
informatio
n corre
c
tly at each d
e
stin
ation.
Figure 1.
Sch
e
matic of mul
t
icast capa
cit
y
2. Maximal flo
w
o
f
single
-
source
t
w
o
-
destin
ation
multicast
Network codi
ng can be used
to
im
prov
e
the
m
u
ltica
s
t capa
city a
nd
save the
requi
re
d
link fo
r t
r
an
smitting inform
ation from
so
urce
nod
e
to
each d
e
stin
ation. Fig
u
re
2
sho
w
n
a
cla
s
sic
butterfly network, which in
clud
e one so
urce nod
e
S
and two de
sti
nation
s
t
1
and
t
2
, the
capa
city
of every link
is ju
st 1. The
traditional
m
u
ltica
s
t route
is sele
cted t
he ed
ge
sep
a
ration
ro
ute
to
transmit the i
n
formatio
n, where th
e inte
rmediate
n
ode
s in the
network
only repli
c
ate a
nd forward
the re
ceived
informatio
n. In Figu
re 2
(
a
), destination
node
s
t
1
and
t
2
can re
ceiv
e informatio
n
at
spe
ed of
2 a
nd 1
unit
cap
a
city at a tim
e
, re
spe
c
ti
vel
y
. Howeve
r, i
f
netwo
rk cod
i
ng is allo
wed
at
node
s, i.e., node 3 in
Figu
re 2(
b
), de
stin
ation no
des
t
1
and
t
2
ca
n re
ceive info
rma
t
ion at sp
eed
of
2 simultan
eo
usly by XOR information
a
and
b
at node 3. At node 3 in Figure 2(b), two a
rrival
information
a
and
b
from
upstream
no
de 1
a
nd
2
are
op
erate
d
as info
rmati
on
a
b
by
X
O
R.
Then at both
destin
a
tion
s
t
1
and
t
2
, information
a
b
i
s
de
cod
ed a
s
a
and
b
by
a
(
a
b
) =
b
an
d
b
(
a
b
) =
a
, res
p
ec
tively
. So, des
tinations
t
1
and
t
2
can re
ceive
information
a
and
b
at the
same time in
Figure 2(b
)
.
(
a
) T
r
aditio
n
a
l
way of routing
(
b
) Ne
twork coding
Figure 2. A classic b
u
tterfly network
s
3
2
t
1
5
4
7
6
t
2
1
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Maxim
i
zation Network Throughput
Based on Maxim
a
l
Flow for Si
ngle-Source ....
(H
uanlin Li
u)
727
The a
bove i
n
trodu
ced
is the p
r
o
c
e
s
s o
f
netwo
rk co
ding o
p
e
r
atio
n for
ea
ch
d
e
stinatio
n
with the
sam
e
re
ceivin
g speed. But
wh
en some
mu
l
t
icast d
e
stin
a
t
ions h
a
ve dif
f
erent
receiving
speed, how t
o
utilize network
codi
ng to make ea
ch
destination receive t
he information at their
own
sp
eed
i
n
a
c
cord
an
ce of the
de
stination’
s
ma
ximal flow v
a
lue from th
e source
no
de,
respe
c
tively. Many re
se
archers have
verified it is
a
NP-hard p
r
obl
e
m
and it i
s
al
most imp
o
ssi
b
le
to reach.
Figure 3. A speci
a
l network
In Figure 3,
we
can fin
d
t
hat not at all
singl
e-sou
r
ce
n-
de
stinatio
n
s
multicast
can ma
ke
all of the d
e
st
ination
s
re
cei
v
e the inform
ation fr
om
so
urce n
ode
wit
h
ea
ch d
e
stin
ation’s
maxim
a
l
flow, and
de
code the
info
rmation
corre
c
tly, where
n
i
s
g
r
eate
r
tha
n
2. In Fi
g.3, the maximal f
l
ow
of destin
a
tion
node
s
t
1
a
nd
t
n
are 2, a
n
d
the maximal
flow of de
stin
ation no
de
s
t
2
,…,
t
n-1
are 1,
respe
c
tively.
If the destina
tion node
s
t
1
and
t
n
want receive two of information
at one time, link
(3, 4) nee
ds tran
smit en
co
ding info
rmati
on
a
b
, a
nd
destin
a
tion n
ode
s
t
2
, …,
t
n-1
are u
nabl
e
to
decode
the
receive
d
info
rmation
su
cce
ssfully. So
i
n
this
pap
er,
we
study th
e
maximal flo
w
multica
s
t cap
a
city for
singl
e-sou
r
ce two
-
desti
n
a
tion
s multica
s
t,
an
d
propo
se a heuri
s
tic
met
hod
based on g
r
a
ph com
p
ressi
on to make
s each d
e
stin
ation re
ceive
the informati
on from source
node
with the
i
r destin
a
tion’
s maximal flo
w
.
In this
pape
r,
a di
re
cted
acyclic m
u
ltica
s
t netwo
rk is
modele
d
a
s
g
r
aph
G
=(
V
,
E
), wh
er
e
V
and
E
rep
r
ese
n
t nod
es
and lin
ks, re
spectively, ca
p
a
city
of all lin
ks i
s
u
n
it 1. T
he maximal fl
ow
of destin
a
tion
node
s
t
1
an
d
t
2
is set as
m
and
n
, respec
tively
(
m
n
). In o
r
de
r t
o
re
aliz
e
t
1
a
nd
t
2
receiving th
e
inform
ation f
r
om
so
urce
n
ode
with
m
a
nd
n
re
sp
ecti
vely and d
e
code i
n
form
ation
su
ccessfully,
we
need
to l
ook for
m
lin
k-di
sjoi
nt pat
hs
and
n
lin
k-disj
oint p
a
th
s for de
stinat
ion
node
s
t
1
and
t
2
, resp
ectiv
e
ly. But, in accord
an
ce wi
th the above
appro
a
ch, only destinatio
n
t
1
can g
uarant
ee
de
codi
ng
the
m
infor
m
ation co
rre
c
tly, but destination
t
2
cannot de
co
d
e
n
informatio
n. For exa
m
ple,
in Figu
re 4
(
a
), the maxi
mal flow i
s
3
and 2 fo
r d
e
s
tination
nod
es
t
1
and
t
2
, re
sp
e
c
tively. There
f
ore, we ne
e
d
to loo
k
fo
r
3 link-di
sjoint
paths for
de
stination
t
1
, whic
h
are
s
-1
-
t
1
,
s
-2
-4-
6
-
t
1
and
s
-
3
-5
-7-
t
1
. Two link-disj
oint p
a
ths a
r
e sea
r
che
d
for de
sti
nation
t
2
, whic
h
are
s
-
1
-4-6-
t
2
and
s
-2
-5-
7
-
t
2
. The tran
smissi
on
ro
ute
s
of
de
stinati
ons
t
1
and
t
2
a
r
e sh
ow
n
in
Figure 4(
b
), whe
r
e info
rm
ation
a
,
b
and
c
are tra
n
smi
tted from sou
r
ce n
ode
S
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 3, September 20
14: 72
5 – 732
728
s
1
a
2
b
3
c
t
1
a
4
b
5
c
6
a
b
7
b
c
t
2
b
c
a
b
b
c
a
b
b
a
(
a
) Original network
(
b
) Information tran
smissi
on route
s
Figure 4. Ske
t
ch of maximal flow tran
smissi
on
In Figu
re
4(
b
), the
de
stina
t
ions
t
1
ca
n d
e
co
de th
e
a
,
b
and
c
infor
m
ation success
fully
according to
Eq. (1).
1
2
3
ay
ab
y
bc
y
(1)
Whe
r
e
y
1
,
y
2
and
y
3
are th
e en
codi
ng in
formation
re
ceived by de
st
ination n
ode
t
1
. There
have thre
e li
near i
nde
pen
den
ce e
quati
ons
with thre
e un
kno
w
n v
a
riabl
es
a
,
b
and
c
in Eq.(1).
So, the destination nod
e
t
1
can decode
three inform
ation
su
ccessfully [13], which are
a
,
b
and
c
in Eq.(1).
Similarly, the decodin
g
equ
ation of desti
nation no
de
t
2
is
s
h
own as follows
4
5
ab
y
bc
y
(2)
Whe
r
e
y
4
an
d
y
5
are the
encodin
g
info
rmation
recei
v
ed by destin
a
tion nod
e
t
2
.
But, we
can find two linear in
dep
en
den
ce eq
uati
ons
with thre
e unkno
wn
s variable
s
a
,
b
and
c
in Eq.(2),
so the de
stin
ation node
t
2
can't de
co
de
the informati
on tran
smitte
d by source
node
S
and
can
not obtain the
2 unit inform
ation, in term
s of maximal flow of destin
a
tion
t
2
at a ti
me.
As discu
s
sed
above, if th
ere have
k
linear in
dep
en
den
ce eq
uations for
k
u
n
k
n
own
variable
s
for the destin
a
tion nod
e
t
, the de
stinatio
n node
t
ca
n decode th
e
k
informati
o
n
su
ccessfully. So, in this
pape
r, a
met
hod i
s
propo
sed to
en
sure that
k
lin
e
a
r ind
epe
nde
nce
equatio
ns o
n
l
y
with
k
info
rmation for th
e de
stination
node
t
in
si
ngle
sou
r
ce two d
e
stin
atio
ns
multicast.
3. Maximize
the n
e
t
w
o
r
k thro
ughp
ut ba
sed o
n
maximal flo
w
for sin
g
le sour
c
e
t
w
o
destin
ations
multicast
Assu
me
s tha
t
the maximal flow of de
stination
s
t
1
and
t
2
are
m
and
n
, res
p
ec
tively,
whe
r
e
m
is n
o
t less than
n
. Firs
tly,
m
link-disj
o
int p
a
ths a
r
e
sea
r
che
d
for d
e
st
ination no
de
t
1
.
Then,
n
link-disjoi
nt paths are sea
r
che
d
for destinati
on node
t
2
. Finally, paths in the above link-
disjoi
nt path
s
, whi
c
h
ma
ke
n
linea
r inde
pend
en
ce eq
uation
s
with
n
unkn
o
wn variabl
es for t
he
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Maxim
i
zation Network Throughput
Based on Maxim
a
l
Flow for Si
ngle-Source ....
(H
uanlin Li
u)
729
destin
a
tion n
ode
t
2
, are de
leted from th
e above link-disjoi
nt
paths. The pro
c
e
s
s of maximization
the netwo
rk throug
hput b
a
se
d on ma
ximal flow for sin
g
le sou
r
ce two
de
stination
s
multi
c
a
s
t
(MFSTM
) as f
o
llows.
Step
1: Loo
k
for
m
link-disj
oint paths for
destin
a
tion
t
1
, and co
nstructing
G
1
grap
h
by the
above
m
link-disjoi
nt paths, where dotte
d lines
ar
e u
s
ed to rep
r
e
s
e
n
t the edge
s i
n
the gra
ph
G
1
in Figure 5 (a
).
Step
2: Loo
k for
n
li
nk-di
s
j
o
int path
s
fo
r
destin
a
tion
t
2
, and
con
s
tru
c
t the graph
G
2
by the
above
n
li
nk-disjoi
n
t path
s
, where the
solid line
s
a
r
e
use
d
to represe
n
t the ed
ges i
n
the g
r
aph
G
2
but not co
nne
ct to the destinatio
n no
de in Figu
re 5
(b).
Step
3: G
r
ap
h
G
3
is con
s
tructed
by link
union of
G
1
a
nd
G
2
, whi
c
h
is shown in F
i
gure
5
(c). If the line
is both in G
1
and in G
2
, the line in G
1
is
selec
t
ed to c
o
ns
truc
t the G
3
.
Step
4: Put t
he solid lin
e li
nks of net
wo
rk
G
3
into the
s
e
t
e
, where
e
={
e
1
,…,
e
k
}
，
e
i
is the
i-
th si
de
solid
line of n
e
two
r
k
G
3
(i
∈
[1,
k
]),
k
is the number of
soli
d lines in
G
3
. Cho
o
se on
e l
i
ne
of the
set
e
t
o
be
del
eted i
n
net
work
G
3
. Ch
eck
wh
eth
e
r th
e maxim
a
l flow of d
e
stination
t
2
in
G
3
is
n
. If
yes,
delete the se
lected line in
G
3
, and update the network
G
3
an
d set
e
. Els
e
if
t
h
e
maximal flo
w
of de
stinatio
n
t
2
in
G
3
i
s
not
n
, th
en
re
s
e
r
v
e
th
e se
le
c
t
ed
lin
e in
n
e
t
w
o
rk
G
3
, and
cha
nge th
e li
ne with th
e d
o
tted line in
G
3
, and up
da
te the network
G
3
an
d
set
e
. Until en
d
of
each line in set
e
are checked.
(
a
)
G
1
gra
p
h
(
b
)
G
2
gra
p
h
(
c
)
G
3
gra
p
h
(
d
)
G
4
gr
ap
h
Figure 5.
Example process of MFSTM
Figure 5 sho
w
s a
n
examp
l
e of impleme
n
tation pro
c
e
ss of MFSTM
,
where n
ode
s
is the
sou
r
ce n
ode
and th
e no
des
8 a
nd 9
are
de
stinat
ion no
de
s. Since th
e max
i
mal flow
of
the
destin
a
tion n
ode
s 8 and 9
is 3 and 2, re
spe
c
tively.
Step 1: Lo
ok for 3 li
nk-di
s
joint p
a
ths
to de
stination
node
8
and
co
nstruct
graph
G
1
,
s
h
ow
n
in
F
i
gu
r
e
5
(
a
);
Step 2: Loo
k for 2 li
nk-di
s
joint p
a
ths to de
stination
node
s
9 an
d co
nst
r
u
c
t g
r
aph
G
2
,
s
h
ow
n
in
F
i
gu
r
e
5
(
b
);
Step 3: Const
r
uct net
wo
rk
G
3
by link uni
on of
G
1
and
G
2
, shown in Figure 5 (
c
);
Step 4: In Fig
u
re
5 (c),
set
e
={
(1, 4
)
, (2,
5)}. To
delet
e
the line
(1, 4
)
in Fi
gure 5
(
c
), we
find the maxi
mal flow
of destination node 9 i
s
st
ill 2, so the line
(1, 4) i
s
del
eted in Fi
gure
5 (
c
).
Similarly, line (2, 5) shoul
d be delete
d
.
Finally
, the netwo
rk, wh
ich ma
ke
s e
a
ch d
e
stin
ation
receive the m
a
ximal flow, is co
nst
r
u
c
ted
in Figure 5 (
d
).
In
Figu
re 5 (
d
), we
can
find
path
s
s
-1-
t
1
,
s
-2
-4
-6
-
t
1
an
d
s
-3
-5
-7-
t
1
f
o
r
de
stination
t
1
, and
find the path
s
s
-2-
4
-6
-
t
2
and
s
-3-
5
-7
-
t
2
for de
stinatio
n
t
2
. So, destination
s
t
1
and
t
2
can re
cei
v
e
information with their maximal flow res
p
ec
tively.
In the foll
owi
ng description, we illustrat
e
that the M
F
STM
can m
a
ke one-source t
w
o-
destin
a
tion
s
multica
s
t get
the m
a
ximal thro
ugh
pu
t, which let
s
ea
ch
de
stination
re
ceiv
e
informatio
n a
t
spee
d of th
eir maximal fl
ow respe
c
tively. We a
s
su
me the net
work i
s
a
b
st
ra
cted
as G, th
e two de
stination
s
a
r
e
t
1
an
d
t
2
, maximal flow of
de
stinations
t
1
an
d
t
2
are
m
an
d
n
,
r
e
spec
tively, w
h
er
e
m
is not less than
n
, the source
node
is
S
.
We a
s
sume th
a
t
the de
stinati
on
t
2
can
re
ceiv
e
n +
k
num
ber of info
rm
ation tran
smi
tting from
so
urce
node
S
usi
ng
MFST
M
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 3, September 20
14: 72
5 – 732
730
algorith
m
, wh
ere
m-
n
k
1. Th
e net
work
codin
g
o
p
e
ration
s
sh
ou
ld be
u
s
ed
a
m
ong th
e
n
li
nk-
disjoi
nt paths. The rea
s
on
is that only
n
link-di
sjoi
nt paths a
r
e se
arched fo
r de
stination
t
2
using
MFSTM, and
the input lin
k num
ber of
destin
a
tion
t
2
is
n
. So, the extra
k
inf
o
rmation should
sha
r
e the
n
e
s
tabli
s
he
d lin
k-di
sjoi
nt paths to tran
smit
the informati
on from
sou
r
ce no
de
S
. There
must exi
s
t th
e case
sho
w
n in the
Fig.6.
m
link-di
sjoi
n
t
paths fo
r d
e
s
tination
t
1
a
r
e den
oted
as
a
1
,
…,
a
m
res
pec
tively.
n
link-disjoi
nt path
s
are
den
oted
as
b
1
, …,
b
n
res
p
e
c
tiv
e
ly
in Figu
re 6. F
o
r
destin
a
tion
t
2
, if des
tination
t
2
re
ceiv
e
s
n
+
k
info
rmation from
sou
r
ce n
ode
S
, the net
work
con
s
tru
c
ted
b
y
MFSTM mu
st exist
not le
ss than
one
node,
su
ch
a
s
A, who
s
e i
n
put lin
k is mo
re
than 1
an
d i
n
formatio
n
carryin
g by
e
a
ch
lin
k
i
s
e
n
co
ded
at n
ode A
by p
e
r
formin
g n
e
t
w
ork
codi
ng. T
he li
nk
(
A, B
) tra
n
s
mits the
en
coding
informa
t
ion
a
1
a
2
. So, de
stination
s
t
2
re
ceives 2
informatio
n b
y
one link
b
3
, whi
c
h are
a
1
and
a
2
. There
have
k
simil
a
r en
codin
g
lin
ks a
s
ab
ove (
A
,
B
). Acco
rdin
g to th
e MF
STM alg
o
rith
m, the d
o
tted lin
k lin
es n
o
t belo
n
g
to
the
m
link-di
sjoin
t
paths. So, if
we delete the
dotted link line, the maximal flow of destinatio
n
t
1
is
m
also and
the
maximum flow of destina
tion
t
2
is stil
l
n
. It is conflicting with
the network coding g
r
a
p
h
con
s
tru
c
ted
b
y
MFSTM al
g
o
rithm,
whi
c
h
say if
we
del
ete any
one
li
nk i
n
the
g
r
ap
h, the m
a
ximal
flow of destin
a
tion nod
e
t
1
or
t
2
shoul
d d
e
crea
se. The
r
efore, the assumptio
n
of
n
+
k
inform
ation
received by d
e
stinatio
n
t
2
wa
s rej
e
cte
d
due to not de
cre
a
se the m
a
ximal flow o
f
destination
t
2
.
The num
ber
of information
receive
d
by destin
a
tion
t
2
is not more than
n
.
Simultaneo
usly, in the net
work
co
ding
grap
h, which
inclu
d
e
s
the
n
lin
k-disjoi
n
t
paths
sea
r
ched by
MFSTM algo
rithm, the maximal flow of d
e
stinatio
n
t
2
is
n
. If we allo
w the en
codi
ng
link exi
s
t in th
e network
co
ding g
r
ap
h, such
as
a
1
a
2
on lin
k
a
1
a
2
, the numb
e
r of info
rmat
ion
received by d
e
stinatio
n
t
2
i
s
not less
than
n
.
From the ab
o
v
e two ca
se
s, we kn
ow, th
e num
be
r of informatio
n re
ceived by de
stination
t
2
just equals
to
n
by MFSTM algorithm.
Figure 6. Simplified network co
ns
t
r
u
c
ted
by link-di
sjoi
nt paths
4. Simulation and Discu
ssion
In order to
make
the
si
mulation
net
work topolo
g
y
clo
s
e
r
to
reality network, we ta
ke
Salama mo
d
e
l to produ
ce
rand
om n
e
tworks,
whi
c
h a
r
e
similar to reality netwo
rk. The num
be
r of
netwo
rk
nod
e
s
is 2
0
, 25, 3
0
, 35 and 4
0
with tw
o de
stinations
whe
n
100 rand
o
m
netwo
rks a
r
e
prod
uced i
n
t
he
simulatio
n
,
re
spe
c
tively. The
avera
g
e
net
work through
put o
b
tai
ned
by MFST
M
is
compared
with the maxi
mal multi
c
ast
stream
al
gorit
hm ba
se
d o
n
netwo
rk codi
ng
(NC) an
d t
he
maximal flow
theory. Table
1 sho
w
s the simulation results of NC a
n
d
MFSTM.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Maxim
i
zation Network Throughput
Based on Maxim
a
l
Flow for Si
ngle-Source ....
(H
uanlin Li
u)
731
Table 1. Average net
work throu
ghp
ut
Number of
node
s
NC
MFSTM
Maximal flow the
o
r
y
20 4.05
6.48
6.48
25 3.89
5.98
5.98
30 3.57
5.08
5.08
35 3.51
4.83
4.83
40 3.45
4.74
4.74
Table
1
sh
ows that
the
net
work
average
thro
ugh
put o
f
MFSTM i
s
g
r
eate
r
tha
n
of NC i
n
the 5 types of networks. A
nd t
he netwo
rk ave
r
ag
e throug
hput of MFSTM algo
rithm is equ
al
to
the network t
h
rou
ghp
ut ca
lculate
d
by m
a
ximal
flow t
heory. Th
e result
sho
w
s t
hat the MFS
T
M
can gu
arante
e
the two destinatio
ns receivin
g
the information
at the speed
of their node’
s
maximal flow.
2
0
25
30
3
5
40
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
Probabilit
y of
r
eachi
ng m
a
ximal t
h
roughput
Number
fo Net
w
or
k
nod
es
NC algo
rit
h
m
M
F
S
T
M
algo
rit
h
m
Figure 7. Probability of maximal thr
oughput for NC and MFSTM algorithm
Figure 7
sh
ows that th
e
av
era
ge
ne
twork th
rou
g
hput of
NC
algorith
m
onl
y about
60%~7
0% of
maximal net
work th
rou
g
h
put whi
c
h i
s
calcul
ated
by maximal
flow theory,
whil
e the
MFSTM can
get the 100% of maximal throu
ghp
ut. So, the MFSTM can get the
network max
i
mal
throug
hput, which e
qual
s to the value of maximal flow theory.
5. Conclusio
n
Multicast makes it is much difficult to
get the network m
a
ximal throug
hput. T
he pap
er
studie
s
a h
e
u
risti
c
alg
o
rit
h
m, MFSTM
algorith
m
,
to make th
e mu
lticast of
sing
le-sou
rce two
-
destin
a
tion
s to get the ma
ximal netwo
rk thro
ugh
put. The net
work codin
g
g
r
ap
h is buil
d
by the
link-disj
oint
p
a
ths of
ea
ch
destin
a
tion wi
th
re
sp
ect to
destin
a
tion’
s
maximal flo
w
. The
process of
netwo
rk
co
di
ng graph
co
n
s
tru
c
tion i
s
to
guarantee
e
a
ch
de
stinati
on at the
sp
e
ed of de
stinat
ion’s
maximal flow usin
g heu
ri
stic pri
n
ci
ple.
Comp
ared
wi
th the traditio
nal maximal
multica
s
t stre
am
algorith
m
ba
sed
on
network codin
g
(NC) al
gor
ith
m
, the p
r
op
o
s
ed
MFSTM
ca
n get
net
wo
rk
maximal thro
ughp
ut of maximal flow theory.
Ackn
o
w
l
e
dg
ements
This resea
r
ch wa
s fund
e
d
by the national natu
r
e
scien
c
e fou
n
d
a
tion of Chi
n
a (NSF
C
6127
5077,
6
1371
096, 5
1
1755
35),
by the 97
3 n
a
tion
al
program o
n
key ba
sic rese
arch
proj
e
c
t of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 3, September 20
14: 72
5 – 732
732
Chin
a (2
012
CB315
803
),
and by the b
a
si
c an
d fron
tier
re
se
arch prog
ram of
Chong
qing (CSTC
2013j
cyjA400
52).
Referen
ces
[1]
Dinh DL, Miklos
M, Jerom
e
P.
An i
m
prov
ed
mu
lticast r
outin
g a
l
g
o
rith
m
in s
parse
s
p
littin
g
W
D
M
netw
o
rks
. Proceed
ings
of IEEE ComManT
el. Vietnam. 20
13
: 99-104.
[2]
Hua
ng S, W
a
n
g
Y, Liu HL, Qi
n L.
Multi-sour
ce multi-cor
e
routin
g
al
gorith
m
based
on n
e
t
w
ork c
odi
ng
in
optica
l
m
u
lti
c
ast net
w
o
rk.
Journ
a
l of
C
h
ong
qin
g
Univ
e
r
sity
of
Posts
and
T
e
l
e
co
mmu
n
ic
ations
.
201
1; 26(2): 14
3-14
9.
[3]
Xi
on
g N
X
, Ji
a
XH, Y
a
n
g
LT
, et al. A
distrib
u
ted
e
fficient fl
o
w
co
ntrol sc
h
e
me for m
u
ltir
ate multic
ast
net
w
o
rks.
IEEE Transactions
on Parallel
and Distributed S
ystem
s,
20
10; 21(9): 12
54-
12
66.
[4]
R Ahls
w
e
d
e
,
N Ca
i, SYR. L
i
. Net
w
ork inf
o
rmation flo
w
.
I
EEE Transacti
ons
on Infor
m
ation
theory
.
200
0; 46(4): 12
04-1
216.
[5]
Li SYR, Y
e
u
n
g
RW
, Nin
g C
a
i. Li
ne
ar n
e
tw
o
r
k co
din
g
.
IEEE Transactions on Infor
m
ation Theory
.
200
3; 49(2): 37
1-38
1.
[6]
Koetter R, M
edar
d M. An
alg
ebra
i
c a
ppr
oach to
net
w
o
rk cod
i
ng.
IE
EE/ACM T
r
an
sactions
on
Netw
orking
. 20
03; 11(5): 7
82-
795.
[7]
Jin T
,
W
ang Y, Z
hao F
.
Random l
i
ne
ar netw
o
rk codin
g
w
i
th
cooper
ating i
n
w
i
reless sens
or netw
o
rk
.
Procee
din
g
s o
f
W
i
reless Co
mmunicati
ons,
Net
w
or
ki
ng
a
nd Mo
bil
e
Co
mputin
g (W
iC
OM). W
uhan.
201
1: 1-4.
[8]
Nistor M,
Luca
n
i D
E
. On th
e
de
la
y
distrib
u
t
i
on
of ra
nd
om
lin
ear
net
w
o
rk
cod
i
ng.
IEEE
Journ
a
l on
Selecte
d
Areas
in Co
mmu
n
ica
t
ions
. 201
1; 29
(5): 1084-
10
93
.
[9]
Yazdi SMS, S
a
vari SA, Kram
er G. Net
w
ork c
odi
ng
in
nod
e-
constrai
ned
li
n
e
an
d star
net
w
o
rks.
IEEE
T
r
ansactio
n
s o
n
Information T
heory
. 20
11; 5
7
(7): 445
2-4
4
6
8
.
[10]
Liu H
L
, Xi
e YH
, Li, Z
,
et al. Stud
y on mi
nimiz
e
net
w
o
rk c
odi
ng li
nks bas
ed
on immun
e
al
gorithm f
o
r
optica
l
multic
a
s
t net
w
o
rk.
Jo
urna
l of Ch
on
g
q
in
g Un
iversity
of Posts and
T
e
leco
mmunic
a
tions
. 20
11
;
23(4): 38
4-3
8
8
.
[11]
Qu Z
,
Liu X, Hua
ng J.
Genetic local se
ar
ch algor
ith
m
for net
w
o
rk codin
g
resourc
e
s
mini
mi
z
a
ti
on
.
Procee
din
g
s of IEEE
Confer
ence on Com
puter Scienc
e
and
Automati
on Engi
ne
erin
g (CSAE),
Z
hang
jia
jie. 2
0
12: 782-
78
6.
[12]
Luo
L, Qin
T
F
, Luo JZ
, et al.
A
routing a
l
go
rith
m for net
w
o
rk codi
ng m
u
l
t
icast base
d
o
n
shar
eab
le
links.
T
e
lec
o
mmu
n
ic
ation En
gin
eeri
n
g
. 20
1
1
; 51(3): 79-83.
[13]
Liu GQ. Approximate const
r
uc
tion of max
i
mum decodable line
ar
net
w
ork coding for single
source.
Co
mpu
t
er Engin
eeri
n
g
.
2010; 36 (9):
94-9
6
.
Evaluation Warning : The document was created with Spire.PDF for Python.