TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.6, Jun
e
201
4, pp. 4400 ~ 4
4
0
4
DOI: 10.115
9
1
/telkomni
ka.
v
12i6.547
4
4400
Re
cei
v
ed
De
cem
ber 2
1
, 2013; Re
vi
sed
Febr
uary 11,
2014; Accept
ed Feb
r
ua
ry
24, 2014
Resear
ch on End-to-End Delay Performance Based on
GPS Sc
heduling System
Wang Yan
g
*
，
Zhou Jin-h
e
，
Ye Keng
Schoo
l of Information a
nd T
e
lecommu
nicati
o
n
Engi
ne
erin
g,
Beiji
ng Informa
tion Scie
nce a
nd T
e
chnol
og
y Universit
y
,
Beiji
ng 1
0
0
101
, China
*
Corres
p
o
ndi
n
g
author, e-ma
i
l
:
w
a
ng
ya
n
g28
2@1
26.com
A
b
st
r
a
ct
T
h
is pa
per
su
mmar
i
z
e
s
s
o
me resu
lts of
ne
tw
ork calcul
us. It derives
the
bo
unds
on
e
n
d
-to-en
d
del
ay and effe
ctive ban
dw
idth by netw
o
rk based o
n
leaky
bucket reg
u
lat
o
rs. T
he simu
l
a
tion res
u
lts sho
w
that the
netw
o
rk calc
ulus
is
a g
o
o
d
fit for c
a
lcul
atin
g
end-
to-end
d
e
lay.
And
it prov
id
e
s
effective c
o
n
t
rol
,
sched
uli
ng a
n
d
man
a
g
e
m
e
n
t in the inte
gratio
n
netw
o
rk cond
itions i
n
the foll
ow
ing step.
Ke
y
w
ord:
statistical netw
o
rk calcul
us, GPS sched
ul
i
ng sys
tem, de
lay, effective ba
ndw
id
th
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Gene
rali
zed
Processo
r Sh
aring
(GPS
) i
s
a
kin
d
of id
eal type, cont
inuou
s
wo
rk
of the fair
sched
uling
st
rategy, put
fo
rwa
r
d
by Pa
rekh
an
d G
a
ll
ange
r [1]; b
e
cause GPS
provides a m
e
thod
in respon
se
to different service req
uest
s
.
So GPS become
s
a resea
r
ch
hotspot in the
guarantee
d service
[2]
n
e
twork. Net
w
ork cal
c
ulu
s
, a
kind
of n
e
w
netwo
rk
syst
em p
e
rfo
r
ma
nce
quantitative analysi
s
, is important an
d effective as
a teaching tool. Comp
ared wi
th the traditional
method of qu
euing the
o
ry [3], the biggest advantag
e
of
network calcul
us i
s
that it can provide
netwo
rk que
u
e
with d
e
term
inistic
analy
s
i
s
[4]. In this p
aper,
we
have ded
uced th
e upp
er b
oun
ds
of delay and
band
width eff
i
cient
frontie
r
based on GP
S model by using n
e
two
r
k
cal
c
ulu
s
theo
ry,
and e
s
tabli
s
h
ed a
se
rie
s
of uppe
r b
o
u
nds
of the
statistical
mod
e
l whi
c
h
suit
for time d
e
l
a
y
perfo
rman
ce
of conve
r
ged
netwo
rk. So,
resear
chi
ng
end-to
-e
nd converg
ed net
work time del
ay
perfo
rman
ce
based on n
e
twork calculu
s
has very im
p
o
rtant theo
ret
i
cal an
d pra
c
t
i
cal value [4, 5].
2
．
Relev
a
nt Theore
t
ical
Kno
w
l
e
dge
2.1. GPS Sy
s
t
em
GPS, Genera
lized Processor Shar
i
ng, is the basi
s
of fair cla
s
s sche
duling alg
o
rit
h
m and
provide
s
a gu
arante
e
to ba
ndwi
d
th allocation
fairne
ss. GPS is a scheduli
ng algo
rithm ba
sed
on
contin
uou
s work. A GPS serve
r
is thro
ugh the po
sitive number p
a
ram
e
ters
12
,,
,
N
said
and the serv
er is at a fixed rate for
continuo
us
wo
rk. Let
,
At
t
be the
quality of service
obtaine
d by t
he flo
w
I du
ri
ng a tim
e
int
e
rval
,
tt
.The GP
S model
defi
nes the flo
w
i
w
h
ic
h
is
transmitted d
u
ring the time
interval
,
tt
as
follows
[1]:
,
,1
,
2
,
.
.
.
,
,
i
i
jj
At
t
j
N
At
t
The GPS alg
o
rithm ha
s th
e followin
g
feature
s
:
a) Flow
i
can ge
t a stable se
rvice rate a
n
d
avoid being i
n
fluen
ced by
other bu
sin
e
ss
flows du
ring
the
pro
c
e
s
s of
re
-tra
nsmi
ssi
on
whe
n
the
avera
ge
spe
ed
of the
busi
n
e
ss flo
w
i
is greate
r
than its gua
rant
eed rate;
b)
After the
pa
cket q
ueu
e in
buffer, the
de
lay of the
pa
cket i
s
defined
by the
maxi
mum
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Re
sea
r
ch on
End-to-E
nd Delay Pe
rform
ance Base
d o
n
GPS Sched
uling System
(Wang Yan
g
)
4401
length
of the
busi
n
e
s
s flow, becau
se
ea
ch
que
en i
s
usin
g the
F
C
FS strategy,
has
nothing to do
with bu
sine
ss flow and gro
uping.
2.2. Net
w
o
r
k
Calculus
Statistical net
work
cal
c
ulu
s
is ba
sed
on
determi
nisti
c
netwo
rk
cal
c
ulus. Usu
a
lly netwo
rk
busi
n
e
ss
can
tolerate a
ce
rtain de
gre
e
of data
loss a
nd delay[6].T
hrou
gh the
statistical n
e
twork
cal
c
ulus, we can
make
a better use
of the
net
work
service so
as i
m
prove the
utilization
ratio of
resou
r
ces
an
d refle
c
t the capabilitie
s of t
he dynam
i
c
a
nd integ
r
ated
servi
c
e
s
of th
e network. Th
e
netwo
rk calculus u
s
e
cum
u
lative fun
c
tion to
def
ine
arrival
process, servi
c
e p
r
oce
s
s a
nd l
e
ave
pro
c
e
ss. Ddfi
ne
A
t
as
arrival
pro
c
e
ss,
*
()
A
t
as l
eave process and
St
as
the service process
of the node
s. Here is the b
a
si
s of statisti
cal net
work calcul
us
whi
c
h
is
use
d
in this pap
er [7].
Definition
1. The Min
-
plu
s
Convol
ution:
The
Min
-
pl
u
s
convolutio
n
ope
ration
of function
s
f
and
g
is:
0
inf
0
0
,
0
st
ft
s
g
s
t
fg
t
t
Definition 2. Ran
dom arri
val envelope
s: If the cumulative flow
,
At
t
in any time
interval
,
tt
s
a
tis
f
ies
the following relationship:
,1
PA
t
t
Call
the statistical traffic
e
n
velope
of the flow
process, and
call
the bigg
est
bre
a
k
probability.
Definition 3.
Effective serv
ice curve: Giv
en a cum
u
lati
ve function
A
t
in traffic
,
if the
output functio
n
D
t
of the traffic satisfie
s the followin
g
rel
a
tionship:
1
PD
t
A
t
Say
t
is the effective se
rvice
curve
whi
c
h i
s
provid
ed by
traffic flow
A
t
Unli
ke service cu
rve, the e
ffective se
rvice curve i
s
corre
s
p
ondin
g
to the prob
abilist
i
c
lowe
r bo
und
of the network
syste
m
service
ca
pa
ci
ty.Therefore,it can
de
scri
be the re
sid
ual
servi
c
e cap
a
c
ity
re
sulted from
the ran
dom
vari
at
ion
s
of othe
r
co
existen
c
e d
a
ta flow. Whet
her
the effective servi
c
e curve
can be u
s
ed
in stat
istical
analysi
s
of n
e
twork servi
c
e perfo
rman
ces
mainly depe
n
d
s on the ava
ilability of t
he
equivalent m
odel of the ne
twork.
Theo
rem
1
node
seri
e
s
the
o
re
m: In a seri
al
system
co
ntaining
n
n
ode
s, if
12
,,
,
N
tt
t
are th
e arriv
a
l cu
rve of t
he no
de
s re
spe
c
tively, the end
-to-end
effective
s
e
rvic
e curve is
[8]:
12
N
3
．
The A
n
aly
s
is of the En
d-to
-en
d
Del
a
y
The total del
ay of GPS system
based
on leaky bu
cket model is
dd
l
[9], where
d
is
the variable delay
(also
c
a
lle
d the delay jitter).It mainly in
c
l
udes the delay when bus
i
ness
flow pa
sse
s
throu
gh the
le
aky bu
cket re
gulator
and t
he waiting d
e
l
ay of the bu
siness flo
w
in t
h
e
GP
S
sy
st
em
buf
f
e
r.
W
h
ile
l
is the fixed
delay which
is mainly fo
r the GPS sy
stem sche
dulin
g
fo
r
w
ar
d
de
la
y.
(1) Delay
jitter
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4400 – 4
404
4402
No
wad
a
ys, the bu
sine
ss flow is u
s
uall
y
c
ontrolle
d
by a leaky b
u
cket re
gulat
or. The
arrival
curve
controlled
by
t
h
e
le
ak
y bu
ck
e
t
r
e
gu
la
to
r
is
t
and it
s d
e
l
a
y jitter i
s
,
dA
. So
we can d
r
aw
that the delay jitter is equal
to the wa
iting delay of the data flow in the buffer of th
e
GP
S
sy
st
em.
Acco
rdi
ng to the definition
of the GPS system:
1
N
j
j
tt
,1
,
2
,
,
i
i
jj
t
jN
t
Next, let s
e
ssion
i
be u
s
ed a
s
a investig
ation obje
c
t, we
can kno
w
that:
0
0:
in
f
ii
t
dd
t
t
d
Simultaneo
us above three f
o
rmul
as:
0
1
0
1
1
1
,,
1
0
0:
0
:
0
:
inf
in
f
in
f
i
i
i
i
N
t
j
j
c
i
i
N
t
k
j
j
N
j
c
j
ik
ik
k
i
t
dd
t
t
d
dt
t
d
rb
R
t
dd
T
R
And becau
se
1
,
1
i
N
j
c
j
ik
k
i
rR
,
1
,
1
/
i
N
j
c
j
ik
k
i
dT
b
R
The waitin
g d
e
lay of sessio
n
i
in the buffer is defined in
the above formula. That is
the
uppe
r bou
nd
of delay jitter of the GPS system ba
sed
on lea
k
y bucket regulato
r
.
(2)
Delay
If
l
is for the fixed delay of the GPS system, the total delay will be:
1
,
1
/
i
N
j
c
j
ik
k
i
dd
l
T
l
b
R
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Re
sea
r
ch on
End-to-E
nd Delay Pe
rform
ance Base
d o
n
GPS Sched
uling System
(Wang Yan
g
)
4403
4.
The Improv
e
m
ent on th
e Upper
Boun
ds of End-to
-end Statis
tical Dela
y
s
There are u
s
ually two way
s
to analyze t
he se
rvice pe
rforma
nce of
the data flow in th
e
end-to
-e
nd n
e
twork. Th
e f
i
rst o
ne i
s
th
at we
ca
l
c
ula
t
e the upp
er
boun
d of service pe
rforma
nce
of each n
ode
according to t
he co
rrespon
ding rela
tion
s betwee
n
out
put and inp
u
t of the adjace
n
t
node
s, an
d th
en put them t
ogethe
r a
s
th
e re
sult
of the
end-to
-e
nd d
e
lay; The second o
ne i
s
th
at
we
use the
same
meth
o
d
to
cal
c
ulat
e the
st
atisti
cal upp
er b
ound
of
e
n
d
-
to-e
nd se
rvice
perfo
rman
ce
according to the tandem e
q
u
ival
en
ce of several servi
c
e node mo
del
[10].
In this pa
pe
r, we a
dopt th
e format of th
e se
rial
ca
scade, which
can be
ea
sily extende
d
from a
single
node d
e
lay
boun
dary to t
he en
d-to
-en
d
delay bo
un
dary. In this
ca
se, the u
p
per
boun
d of the end-to
-e
nd d
e
lay can b
e
concl
ude
d ba
sed on this the
o
ry:
1
,
11
11
12
mi
n
,
,
,
c
N
ik
j
SS
kj
ne
t
mm
mm
iS
Sb
dl
T
rr
r
5.
Resul
t
s and
Analy
s
is of the Simulation
In the e
nd-to
-end
net
wo
rk, the num
be
r of data
sou
r
ce
s
rem
a
in
s the
same,
a
nd the
sched
uling
q
ueue i
n
the
cach
e is fixed. Com
pari
ng
with the
dela
y
which ha
s
not bee
n imp
r
oved
throug
h the
simulatio
n
, we ca
n exami
ne the
effect
s of the
corresp
ondi
ng p
a
ram
e
ters o
n
the
delay bou
nda
ry of network.
Next, we cal
c
ulate the
re
lationship
s
a
m
ong the
up
per b
oun
ds
d
of the end-t
o
-en
d
statistical del
ay, the length of the leaky bucket
b
and the wei
ght
of the GPS mod
e
l.
Figure 1. The
Relation
ship
of Uppe
r Bou
nd
of the Del
a
y, Weight an
d the Length
of Leaky
Buc
k
et
From
the Fi
gure
1, the sel
f
-similar tra
ffic
will decrease with the i
n
crease
of
w
h
ic
h
is
the GPS
wei
ght an
d the
decrea
s
e
of
the len
g
th
of
lea
k
y bu
cke
t.Therefo
r
e,
according
to
the
cha
r
a
c
teri
stics of traffic b
a
s
ed
on this f
eature,
we
can re
du
ce th
e length of th
e lea
k
y bucket to
redu
ce the e
nd-to
-en
d
del
ay under the
premi
s
e
of m
eet the data in the backlo
g
.
Then we ca
n
further
re
du
ce the b
and
width fo
r th
e bu
sine
ss f
l
ow to
achie
v
e the pu
rp
ose
of net
work
optimizatio
n.
6.
Conclusion
In this pap
er,
we u
s
e the
netwo
rk
cal
c
ulus
the
o
ry to
study the be
havior of GP
S system
based
on le
aky b
u
cket
regulato
r
a
n
d
ded
uce the
statisti
cal
d
e
lay up
per b
ound
of the
GPS
system.
Und
e
r no
rmal
ci
rcu
m
sta
n
ces,
the net
work provide
s
band
width a
c
cordi
ng to
the
maximum
rat
e
of the
d
a
ta
flow; thi
s
will
ma
ke th
e n
e
twork to
opti
m
ization
an
d
ca
use
wa
ste
o
f
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
20
25
30
35
40
45
50
55
Th
e
w
e
i
g
h
t
U
p
pe
r bo
un
d of
t
h
e s
t
at
i
s
t
i
c
a
l
d
e
l
a
y
d
b=
50
0k
b
b=
10
00k
b
b=
15
00k
b
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4400 – 4
404
4404
resou
r
ces. And this articl
e, by analyzing end
-t
o-e
n
d
delay, can
provide
imp
o
rtant theoretical
basi
s
for the
allocation of the network b
and
width.
Ackn
o
w
l
e
dg
ements
This work wa
s su
ppo
rted b
y
National Na
tural Scie
nce Found
ation of
China (612
7
1198
)
and Beijing
Natural Sci
e
n
c
e Found
ation
(413
100
3).
Referen
ces
[1]
Parekh AK, Galla
ger RG. A Genera
lize
d
Processor
Sh
arin
g Appro
a
ch to
F
l
o
w
C
ontro
l i
n
Integrate
d
Services N
e
t
w
ork:
T
he Singl
e
Node C
a
se.
IEEE Network
. 1993; 1(3): 3
44-
357.
[2]
Dai Y
ou, Z
h
g
e
Bin, Son
g
H
u
a
nhu
an, W
a
n
g
W
e
im
ing,
Lan
Julo
ng. T
he future n
e
t
w
ork re
search
bas
e
d
on rec
onfi
gurat
ion
an
d e
x
pans
ible
. T
E
LKOM
NIKA Indo
nesi
an Jo
urn
a
l
of E
l
ectrical
En
gin
e
erin
g.
20
13
;
11(1
0
): 592
9-5
937
[3]
He T
ao, chen F
u
cai, Qin
T
ao. Establishi
ng p
e
rf
ormanc
e ev
alu
a
tion mo
del
w
i
t
h
que
ui
ng
th
eor
y in
No
C.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(10):
569
4-57
02.
[4]
Boun
dec JYL,
T
h
iran P. Net
w
ork Calc
ulus. B
e
rlin: Spr
i
ng
er Verla
g
. 200
4.
[5]
Z
hang Qi-Z
hi,
Z
hang Bin, Z
han
g W
e
i-do
n
g
. Calc
ul
atio
n
of maximum
del
a
y
i
n
s
w
itc
hed i
ndustri
a
l
Ethernet b
a
sed
on net
w
o
rk ca
l
c
ulus
. Co
ntrol
and D
e
cisi
on
. 200
5; 20(1): 11
7-12
0.
[6]
Leb
ou
ndec J
y
, T
h
iran P. Net
w
ork Calc
ulus. L
ond
on, Britai
n: Sprin
ger Verl
a
g
. 2004.
[7]
Shuru
i
F
an, H
e
xu Su
n. Jie
Li. On app
licat
ion meth
od
of Net
w
ork Ca
lc
ulus to u
p
p
e
r del
a
y
bo
un
d
researc
h
. Computer Scie
nce
and Informati
o
n
T
e
chnolog
y (
I
CCSIT
). 3
rd
IEEE Internation
a
l Conf
erenc
e
on. 201
0; 4: 56
6-57
0.
[8]
Burchar
d Almu
t. A min-plus c
a
lcul
us for e
n
d
-
to-end statisti
cal servic
e gu
a
r
antees.
IEEE Transactions
on Infor
m
atio
n
T
heory
. 200
6; 52(9): 41
05-
41
14.
[9]
Urvo
y G, Dall
e
r
y
Y, He
buter
n
e
G. CAC proc
edur
e for le
ak
y bucket co
nstrain
ed so
urces.
Performanc
e
Evalu
a
tion. 2
0
00; 41(2): 1
17-
132.
[10]
El
w
a
l
i
d A, Mitr
a D.
Desi
gn of
gen
eral
i
z
e
d
p
r
ocessor
sh
ari
ng
sch
edu
lers w
h
ich
statistically mu
ltipl
e
x
hetero
g
e
neo
us
QoS class
e
s.
Proceeding
of
IEEE IN
FOCOM’99. Ne
w
Y
o
rk, NY, USA:
IEEE. 1999:
122
0-12
30.
Evaluation Warning : The document was created with Spire.PDF for Python.