Indonesian
J
our
nal
of
Electrical
Engineering
and
Computer
Science
V
ol.
12,
No.
2,
No
v
ember
2018,
pp.
873
–
882
ISSN:
2502-4752,
DOI:
10.11591/ijeecs.v12.i2.pp.
873-882
873
Impact
of
MRAI
T
imer
on
BGP
Updates
and
Con
v
er
gence
T
ime
R.
N.
De
vikar
*
,
D
.
V
.
P
atil
**
,
and
V
.
Chandraprakash
***
*
Research
Scholar
,
Department
of
CSE,
K
oneru
Lakshmaiah
Education
F
oundation,
V
addesw
aram,
Guntur
,
AP
,
India
**
Department
of
Computer
Engineering,
MET
IOE,
Bhujbal
Kno
wledge
City
,
Pune
Uni
v
ersity
***
Professor
,
Department
of
CSE,
K
oneru
Lakshmaiah
Education
F
oundation,
V
addesw
aram,
Guntur
,
AP
.,
India
Article
Inf
o
Article
history:
Recei
v
ed
October
16,
2017
Re
vised
August
24,
2018
Accepted
K
eyw
ord:
Con
v
er
gence
T
ime
MRAI
FMRAI
Inter
-domain
routing
ABSTRA
CT
BGP
is
a
vital
routing
protocol
for
the
communication
amongst
autonomous
systems
in
the
internet
and
has
been
broadly
applie
d
in
all
cate
gories
of
lar
ge
scale
netw
ork.
The
inter
-
domain
routing
protocol
(BGP)
sho
ws
slo
w
con
v
er
gence,
which
ef
fects
on
man
y
internet
applications
due
to
its
high
con
v
er
gence
delay
.
The
netw
ork
operators
broadly
use
dif
fer
-
ent
MRAI
timers
in
BGP
routers
to
deal
with
the
issue
of
gro
wing
con
v
er
gence
time
of
the
netw
ork.
The
v
ariation
in
MRAI
timer
and
its
impact
on
netw
ork
con
v
er
gence
and
update
messages
has
been
broadly
studied
o
v
er
the
years.
The
increasing
size
of
autonomous
sys-
tems
leads
to
rise
in
number
of
MRAI
timers.
Hence,
the
optimum
use
of
MRAI
timers
can
decrease
the
problem
of
slo
w
con
v
er
gence
and
necessity
of
huge
number
of
MRAI
timers.
The
proposed
system
uses
the
ckle
minimum
route
adv
ertisement
interv
al
timer
(FMRAI)
for
f
ast
update
of
routing
table,
which
leads
to
reduce
the
con
v
e
r
gence
time
of
a
netw
ork.
In
comparison
with
static
MRAI
t
imer
of
30s
the
FMRAI
timer
leads
to
better
result
in
terms
of
con
v
er
gence
time
and
number
of
update
messages.
Copyright
c
2018
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Rohit
Nilkanth
De
vikar
Research
Scholar
Departement
of
Computer
Science
and
Engineering
K
oneru
Lakshmaiah
Education
F
oundation,
V
addesw
aram,
Guntur
,
AP
,
India
+919028339491
rohit.de
vikar89@gmail.com
1.
INTR
ODUCTION
The
Border
Gate
w
ay
Protocol
(BGP)
is
an
inter
-domain
routing
protocol.
The
BGP
is
use
in
the
autonomous
system
(AS).
Each
and
e
v
ery
AS
is
identified
by
autonomous
system
number
(ASN).
The
router
which
is
used
to
con-
nect
tw
o
dif
ferent
AS
is
called
BGP
speak
er
node.
The
primary
functionality
of
a
BGP
speak
er
node
is
to
e
xchange
netw
ork
reachability
information
with
other
BGP
speak
er
node
of
neighbour
autonomous
system.
This
netw
ork
reach-
ability
information
contains
information
on
the
list
of
Autonomous
Systems
(AS)
that
tra
v
erses
the
reachability
infor
-
mation
[1],
[2].
This
information
is
suf
ficient
to
construct
a
graph
of
AS
connecti
vity
from
which
routing
loops
may
be
pruned
and
some
polic
y
decisions
at
the
AS
le
v
el
may
be
enforced.
BGP
use
a
b
ulk
y
number
of
features
to
spread
the
information
through
the
AS
path.
Such
AS-path,
records
this
pathw
ay
through
all
the
autonomous
systems,
hence
it
is
to
be
re
g
arded
as
path
v
ector
protocol.
Currently
,
Internet
is
f
acing
man
y
problems
because
of
netw
ork
instability
.
Routing
instability
will
causes
increasing
con
v
er
gence
time,
netw
ork
message
delay
and
may
e
v
en
cause
the
entire
re
gional
netw
ork
interruption.
As
the
netw
ork
is
scaling
rapidly
,
the
topology
become
more
and
more
comple
x.
Due
to
this
f
ast
routing
con
v
er
gence
of
BGP
is
a
serious
issue
no
w
days.
Ho
we
v
er
,
the
BGP
protocol
is
sensiti
v
e
to
definite
Internet
topological
characteristics;
it
still
remains
totally
insensiti
v
e
to
the
de
viation
of
other
characteristics.
Whene
v
er
there
is
a
topology
change,
which
may
happen
due
to
polic
y
changes,
brok
en
links
or
connections,
or
the
arri
v
al
of
a
ne
w
node,
the
con
v
er
gence
process
is
acti
v
ated,
and
while
a
stable
state
is
not
reached,
pack
et
losses
and
inconsistencies
might
tak
e
place.
During
this
period,
the
speedy
fluctuation
in
the
netw
ork
reachability
characterizes
the
routing
instability
[2].
J
ournal
Homepage:
http://iaescor
e
.com/journals/inde
x.php/ijeecs
Evaluation Warning : The document was created with Spire.PDF for Python.
874
ISSN:
2502-4752
The
problem
of
con
v
er
gence
can
be
roughly
di
vided
into
tw
o
cate
gories:
1.
Routing
con
v
er
gence
due
to
the
strate
gy
conflict
between
ASs,
such
problem
generally
does
not
in
v
olv
e
AS
internal
structure;
2.
Another
is
routing
oscillation
because
of
some
f
aultiness
of
BGP
system,
which
is
related
to
the
AS
internal
structure.
When
such
fluctuations
are
happened
in
the
netw
orks,
BGP
may
tak
e
long
duration
to
con
v
er
ge.
The
high
con
v
er
gence
delay
of
fered
on
the
Internet
acquires
in
service
una
v
ailability
with
pack
et
loss
and
poor
quality
for
ap-
plications.
W
ith
the
gro
wth
of
man
y
real-time
applications
on
the
Internet
such
as
netw
ork
banking,
Sk
ype,
and
video
conferences,
increases
the
traf
fic
demand.
The
slo
w
con
v
er
gence
of
BGP
,
for
e
xample,
seriously
impacts
on
V
OIP
service,
accounting
for
almost
90%
of
the
dropped
calls.
In
the
last
fe
w
years,
a
number
of
ef
forts
ha
v
e
been
made
to
impro
v
e
inter
-domain
routing
con
v
er
gence,
proposing
BGP
modifications,
changes
on
inter
-domain
architecture
or
ne
w
routing
protocols.
One
problem
BGP
has
encountered,
due
to
the
decentralized
nature,
is
its
slo
w
con
v
er
ging
speed.
According
to
studies
in
[1],
after
a
topology
change,
it
tak
es
an
a
v
erage
of
3
minutes
for
the
Internet
to
up-
date
all
the
routing
tables,
with
a
w
orst
case
of
15
minutes.
Such
a
delay
may
lead
to
e
xtreme
pack
et
losses,
and
is
t
hus
not
acceptable
to
man
y
delay-sensiti
v
e
applications
.
Therefore,
speeding
up
BGP
con
v
er
gence
is
a
critically
important
and
yet
challenging
problem.
Our
research
is
bas
ed
on
impro
ving
the
con
v
er
gence
time
of
a
netw
ork
by
introducing
fickle
Mean
route
adv
ertisement
interv
al
timer
(FMRAI).
Literature
surv
e
y
sho
ws
that
man
y
trials
ha
v
e
been
done
to
impro
v
e
con
v
er
gence
by
reducing
minimum
route
adv
ertisement
interv
al
(MRAI)
timer
.
But
the
y
f
ailed
in
dynamically
changing
topology
.
In
the
Internet,
netw
ork
f
ailures
happen
commonly
and
the
e
xisting
routing
protocols
can
tak
e
se
v
eral
duration
to
con
v
er
ge
after
a
f
ailure
[3].
During
con
v
er
gence
times,
se
v
eral
pack
ets
may
be
loss
or
may
already
be
en-route
to
their
destinations.
These
in-flight
pack
ets
can
encounter
routing
loops,
delays
and
pack
et
losses.
Ho
we
v
er
,
due
to
this
the
ma
in
question
rais
ed
ho
w
man
y
pack
ets
are
lost
or
not
reach
to
the
gi
v
en
destination
during
con
v
er
gence
periods?
In
this
paper
,
we
study
the
impact
of
M
RAI
timer
on
con
v
er
gence
time
and
number
of
updates.
The
MRAI
timer
is
directly
proportional
to
the
con
v
er
gence
time
and
in
v
ersely
proportional
to
the
number
of
updates.
Increase
in
MRAI
increases
the
con
v
er
gence
time,
b
ut
decreases
the
number
of
updates.
In
literature
surv
e
y
we
study
and
e
xamined
man
y
routing
protocols
those
are
w
ork
to
reduce
the
MRAI
timer
.
T
w
o
main
aspects
in
designing
the
routing
protocol,
k
eeping
alternati
v
e
path
transmission
information
at
e
v
ery
router
and
rapidly
spreads
ne
w
reachabil
ity
information,
appear
to
ha
v
e
the
more
impact
on
the
pack
et
deli
v
ery
beha
viour
during
con
v
er
gence.
Netw
ork
instability
is
one
of
the
major
problem
in
currently
changing
netw
ork
topology
.
Instability
in
the
netw
ork
results
in
loss
o
f
pack
ets,
which
in
turn
increases
the
latenc
y
and
con
v
er
gence
time.
F
ollo
wing
section
describes
the
research
w
ork
done
by
dif
ferent
researchers
to
impro
v
e
the
con
v
er
gence
time
[4]
and
instability
of
the
netw
ork.
Grif
fin
et
al.
[5]
e
xplained
a
study
on
the
sta
ble
paths
and
conclude
that
it
is
al
w
ays
possible
to
con
v
er
ge
BGP
netw
ork
by
using
three
methodologies.
1.
The
first
is
by
using
operational
guidelines,
which
is
a
g
athering
of
rules
that
al
l
ASes
must
follo
w
to
confirm
polic
y
safety
and
correctness.
2.
The
second
approach
is
based
on
static
analysis,
making
programs
analyse
routing
policies
and
detect
if
an
y
polic
y
conflict
or
other
inconsistenc
y
e
xists,
which
may
cause
protocol
di
v
er
gence.
3.
The
t
hird
approach
is
a
dynamic
detection,
which
a
v
oids
and
suppresses
routing
fluctuation
as
soon
as
it
is
detected.
RFD
uses
this
third
approach,
b
ut
the
authors
kno
w
its
issues
and
do
not
recommend
its
use.
T
o
identify
potential
oscillation
on
netw
ork,
Cittadini
et
al.
[6]
introduced
a
heuristic
algorithm
that
performs
static
detection
in
an
AS.
F
abrikant
et
al.
[7]
observ
ed
t
hat
although
the
def
ault
v
alue
of
MRAI
timer
is
30
seconds
,
router
v
endors
are
eliminating
or
lo
wering
the
timer
,
e
xpecting
that
with
a
small
v
alue
of
MRAI,
the
con
v
er
gence
time
will
be
reduced.
The
authors
illustrate
that
by
decrementing
MRAI
timer
does
not
impro
v
e
netw
ork
con
v
er
gence
time,
and
the
be-
ha
viour
of
a
netw
ork
in
con
v
er
gence
process
might
actually
get
e
v
en
poorer
.
So,
the
deplo
yment
of
MR
AI
v
ariations
may
be
done
carefully
.
Elmokash
et
al.
[8]
observ
ed
that
the
churns
of
BGP
updates
are
caused
by
an
interaction
of
three
f
actors:
1.
The
routing
protocol,
which
has
the
BGP
technique
such
as
MRAI,
RFD
and
routing
policies,
etc.
2.
Ev
ents
lik
e
BGP
updates,
link
f
ailures,
traf
fic
engineering
operations
etc.
3.
The
features
of
the
Internet
topology
.
The
authors
focused
on
the
impact
of
the
third
f
actor
,
i.e.
topology
,
on
the
e
xistence
of
BGP
churn.
The
y
created
a
topology
generator
to
e
xamine
churns
at
dif
ferent
locations
of
the
generated
topologies,
and
analysed
the
number
of
updates
with
increase
in
size
of
each
topology
.
Schrieck
et
al.
[9]
detected
some
f
actors
that
may
cause
BGP
churn
issues.
First,
certain
inter
-domain
links
are
frequently
f
ailed
and
unstable,
transmitting
this
information
to
neighboring
ASes
through
withdra
w
als.
Second,
when
routes
are
una
v
ailable
BGP
suf
fers
from
path
e
xploration.
In
Indonesian
J
Elec
Eng
&
Comp
Sci
V
ol.
12,
No.
2,
No
v
ember
2018:
873
–
882
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
875
addition
to
this
f
actor
,
MRAI
and
RF
D
may
also
be
foundation
to
BGP
churn
and
further
delay
con
v
er
gence.
Elmokash
et
al.
[10]
e
xperiment
the
study
on
BGP
churn
e
v
olution
in
four
netw
orks
at
the
Internet
backbone
during
a
period
of
se
v
en
years
and
eight
months.
By
taking
an
e
xperimental
data
analysis
author
suggested
that
duplicate
announcements
are
the
major
BGP
churn
contrib
utor
for
BGP
updates.
Elmokash
et
al.
[11]
introduced
a
model
to
predict
ho
w
BGP
churn
will
gro
w
in
the
future
by
considering
routing
policies,
inter
-domain
topology
,
and
traf
fic
characteristics
those
changes
frequently
.
The
model
pro
v
ed
that
the
number
of
updates
standardised
by
the
size
of
the
topology
is
constant,
and
qualitati
v
ely
related
to
IPv4
and
IPv6.
Huston
[12]
obtained
a
report
on
BGP
churn
from
the
period
2008
to
2014
and
concl
udes
the
number
of
routing
updates
remains
stable
for
se
v
eral
years,
e
v
en
though
the
number
of
prefix
in
the
routing
tables
are
continuously
gro
wing.
This
is
e
xplained
by
the
f
act
that
as
the
Internet
gro
ws
continuously
,
the
pattern
of
ne
w
connected
ASs
is
repeated
through
the
netw
ork
topology
.
It
means
that
the
Internet
is
gro
wing
in
density
rather
than
in
size,
resulting
in
comparati
v
el
y
constant
AS
path
length.
The
E.A.
AiabduIkreem
et.
al.
[13]
has
e
xpected
to
modify
the
path
e
xploration
process
by
maximum
reducing
the
con
v
er
gence
time.
T
o
speed
up
this
process
authors
ha
v
e
used
fight
or
flight
response
technique.
This
w
as
carried
out
by
ignoring
se
v
eral
parameters
when
the
update
message
w
as
a
withdra
wn.
Due
to
this
modification,
con
v
er
gence
time
w
as
reduced
by
29%.
X.
W
ang
et.
al.
[14]
proposed
a
technique
called
Churn
Aggre
g
ation
(CA
GG),
which
tries
to
decrease
path
e
xploration
by
collecting
multiple
AS
paths
in
one
route,
without
harming
con
v
er
gence.
T
o
aggre
g
ate
those
paths,
CA
GG
nds
the
P
ath
Locality
e
xplored
by
a
highly
acti
v
e
prefix,
which
reduces
the
total
number
of
e
xchange
updates.
Y
u
C.W
.
et
al.
[15]
introduced
the
concept
of
alternate/backup/secondary
paths
along
with
the
main/primary
path
for
which
if
main
route
f
ails
then
the
backup
route
immediately
tak
en
for
the
further
process.
But
the
comple
xity
is
more
due
to
managing
and
storing
backup
routes.
Shi
v
ani
deshpande
et
al.
[16]
intr
od
uc
ed
a
BGP
instability
detection
technique
that
can
be
e
x
ecuted
by
indi
vidual
routers.
The
input
data
for
detection
of
instability
is
BGP
update
messages
recei
v
ed
by
routers
from
its
neighbor
.
From
thi
s
BGP
update
messages
attrib
utes/features
(lik
e
AS
path
length,
AS
path
edit
distance)
are
e
xtracted
in
e
v
ery
fi
v
e
minutes,
this
sho
ws
the
change
in
topology
.
The
GLR
(Generalized
Lik
elihood
Ratio
test),
Boundary
position
opti
mization
algorithms,
Se
gmentation
boundary
detection
are
used
to
detect
the
changes.
Geo
Huston
et
al.
[17]
proposed
a
P
ath
Exploration
Damping
(PED)
mechanism
which
reduces
the
number
of
BGP
update
messages
and
also
decreases
the
a
v
erage
time
required
to
restore
reachability
.
The
y
compare
PED
ef
fect
on
con
v
er
gence
ti
me
with
MRAI,
W
ithdra
w
al
Rate
Limiting
(WRA
TE),
and
Route
Flap
Damping
(RFD).
Mohammad
Y
anuar
Hariya
w
an
[18]
compared
dif
ferent
methods
lik
e
local
rerouting,
Haskin,
1+1
path
protection
reco
v
ery
mechanism,
F
ast
Reroute
one
to
one
backs
up,
and
PSL
oriented
path
protection
mechanism
technique
for
sooner
rerouting
after
f
ailure.
The
performance
sho
ws
that
1+1
path
protection
reco
v
ery
technique
has
mi
nimum
pack
et
loss,
b
ut
ha
ving
more
cost.
Rajvir
Gill
et
al.
[19]
proposed
the
FLD-MRAI
(Fle
xible
Load
Dispersing
MRAI)
algorithm
that
disperses
the
load
in
the
netw
ork,
which
results
in
reducing
the
routers
l
o
a
d.
The
authors
concentrat
ed
on
routing
policies
and
their
ef
fects
on
con
v
er
gence
time,
number
of
updates.
The
FLD-MRAI
algorithm
w
orks
in
case
of
both
normal
and
high
loads.
When
de
gree
of
preference
(DoP)
selects
the
shortest
path,
then
FLD-MRAI
belie
v
e
this
situation
as
normal
load,
and
when
DoP
selects
the
longest
path
then
FLD-MRAI
belie
v
e
this
situation
as
high
load.
In
a
netw
ork
running
the
BGP
,
the
end
to
end
reachability
information
can
be
temporarily
disturbed
due
to
node
or
link
f
ailures
and
the
time
required
for
con
v
er
ging
a
netw
ork
lead
to
service
de
gradation
or
e
v
en
interruption,
which
creates
a
critical
issue
for
real-time
interacti
v
e
applications.
The
J.
R.
Alzate
et.
al.
[20]
e
v
aluates
the
beha
viour
of
ghost
flushing
and
EPIC
proposal
in
W
axman
topology
netw
orks
for
reducing
the
impact
of
path
e
xploration
and
MRAI
on
con
v
er
gence
time
of
a
netw
ork.
R.
N.
De
vikar
et
al.
[21]
surv
e
yed
the
dif
ferent
issues
that
are
occured
at
the
time
of
pack
et
transmission.
Con
v
er
gence
time
is
one
of
the
issue
in
the
netw
ork
that
are
described
in
[21].
In
[22]
author
described
about
the
study
of
con
v
er
gence
time
by
considering
BGP
protocol.
In
this
the
y
analyse
dif
ferent
techniques
and
algorithms
those
are
used
to
impro
v
e
the
con
v
er
gence
time
of
a
netw
ork.
R.
N.
De
vikar
et
al.
[23]
proposed
a
technique
which
reduced
the
con
v
er
gence
time,
the
y
also
introduced
a
load
balancing
algorithm
for
pack
et
transmission
to
reduce
the
congestion
in
the
netw
ork.
Chen
Chen
et.
al.
[24]
proposed
a
mathematical
model
to
compute
the
BGP
con
v
er
gence
time
by
catching
only
the
important
components
in
BGP
con
v
er
gence
process.
The
y
further
presented
a
greedy
approach
that
selects
ASes
for
incremental
softw
are-defined
netw
orking
(SDN)
deplo
yed
with
the
idea
of
reducing
the
BGP
con
v
er
gence
time.
The
paper
tells
about
the
impro
v
ement
in
con
v
er
gence
time
and
update
messages
with
respect
to
MRAI
timer
.
Section
2
contains
research
method,
which
tells
about
the
Methodology
and
Algorithm
for
FMRAI
timer
using
mathematical
approach.
The
res
u
l
t
and
analysis
sho
wn
in
secti
on
3
contains
e
xperimental
results.
And
finally
,
the
last
section
discuss
about
conclusion
and
future
scope
of
the
research
w
ork.
Impact
of
MRAI
T
imer
on
BGP
Updates
and
Con
ver
g
ence
T
ime
(R.
N.
De
vikar)
Evaluation Warning : The document was created with Spire.PDF for Python.
876
ISSN:
2502-4752
2.
RESEARCH
METHOD
T
o
reduce
the
netw
ork
con
v
er
gence
time
by
changing
MRAI
timer
v
ariable
dynamically
.
In
the
Netw
ork,
routing
update
will
done
after
e
v
ery
30s.
No
w
,
if
an
y
link
f
a
ilure
occur
immediately
after
the
routing
update
of
30s.
Then,
to
get
the
idea
about
l
ink
f
ailure
the
node
has
to
w
ait
until
ne
xt
update.
During
that
much
time
the
load
on
both
link
f
ailure
node
increases
rapidly
.
Due
to
which
there
may
be
a
chance
of
pack
et
loss.
On
making
MRAI
timer
v
ariable
changing
dynamically
.
The
v
alue
of
MRAI
timer
v
ariable
can
be
calculated
as
early
as
possible
after
the
link
f
ailure
or
an
y
other
change
in
topology
.
The
v
alue
of
MRAI
will
get
reduced
and
will
be
belo
w
30s
which
will
mak
e
the
routing
updation
f
aster
and
hence
the
reduction
in
con
v
er
gence
time
of
netw
ork.
The
follo
wing
algorithm
sets
the
v
alue
of
MRAI
timer
.
X
P
i
=
(
p
1
;
p
2
;
p
3
;
p
4
:::::::::::p
n
)
(1)
P
consist
of
total
paths
p
1
,
p
2
,
p
3
...........
p
n
those
are
reaching
to
the
destination
D.
Where,
P
i
is
i
th
path
reaching
to
destination.
P
1
=
X
R
1
X
R
1
=
(
r
1
;
r
2
;
r
3
;
r
4
:::::::::::r
n
)
Ev
ery
path
P
consist
of
lar
ge
number
of
routers
R
n
.
Suppose
path
P
1
consist
of
R
1
number
of
routers,
Where
R
1
contains
the
r
1
,r
2
,r
3
..r
n
router
those
are
a
v
ailable
on
the
path
P
1
.
R
1
=T
otal
number
of
routers
a
v
ailable
on
path
P
1
.
L(P
i
)
=
(l
1
,
l
2
,
l
3
,
l
4
...........l
d
)
.
L(P
i
)
=T
otal
number
of
links
present
in
path
P
1
.
D[L(P
i
)]
=D
(l
1
,
l
2
,
l
3
,
l
4
...........l
d
)
D[L(P
1
)]
=T
otal
delay
in
the
links
on
pathP
1
.
W(P
i
)]
=W
(l
1
,
l
2
,
l
3
,
l
4
...........l
d
)
W(P
1
)
=T
otal
pr
ocessing
time
on
pathP
1
.
Q[R(P
i
)]
=Q
(qr
1
,
qr
2
,
qr
3
,
qr
4
...........qr
d
)
Q[R(P
1
)]
=T
otal
queuing
delay
at
eac
h
r
outer
on
pathP
1
Maximum
delay
(TD)=
D[L(P
i
)]+W(P
i
)+Q[R(P
i
)
MRAI=TD
if(TD
>
=
Default
MRAI)
f
MRAI=
Default
MRAI
;
r
eturn
MRAI
;
g
else
f
MRAI=TD
;
r
eturn
MRAI
;
g
The
Con
v
er
gence
time
of
a
netw
ork
is
reduced
by
introducing
the
FMRAI
(Fickle
mean
route
adv
ertisement
interv
al)
timer
algorithm
sho
wn
belo
w
.
The
simulation
performed
in
NS2
simulator
by
considering
the
topology
sho
wn
in
figure
1.
T
opology
consist
of
nodes
represent
as
BGP
routers
which
w
ork
as
a
speak
er
node
for
its
domain.
The
Indonesian
J
Elec
Eng
&
Comp
Sci
V
ol.
12,
No.
2,
No
v
ember
2018:
873
–
882
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
877
BGP
e
x
ecution
is
based
on
BGP-4
specific
ations.
The
netw
ork
topology
is
manually
created,
each
node
signifies
an
AS,
and
all
the
links
are
configured
in
such
w
ay
that
ha
ving
similar
bandwidth
and
v
ariable
delays.
Algorithm
1
Algorithm
for
FMRAI
Step
1.
Check
Autonomous
System
(AS)
Step
2.
Get
path
to
destination
MRAI
SUM=0;
MAX
MRAI=0;
Step
3.
F
or
each
Connected
AS
f
Calculate
P
ath
delay
P
D=path
delay
-
>
get
delay(connected
as
list
.
node
id[i]);
P
D
is
add
into
node
parameter
.
g
Step
4.
F
or
each
path
to
destination
Initialise
p
delay=0;
l
delay=0;
r
delay=0;
q
delay=0;
Step
5.
F
or
each
path
calculate
p
delay
=
max(p
delay
,
path
delay
-
>
delay[j]);
q
delay=max(q
delay
,
queue
delay
get
delay(path
delay
-
>
nodeid[j]));
l
delay
=
max(l
delay
,link
delay
);
r
delay=max(r
delay
,
path
delay-
>
get
delay(connected
as
list
.nodeid[i]));
Maximum
delay(TD)=
p
delay
+
q
delay
+
l
delay
+
r
delay;
Step
6.
if(TD
>
=
MAX
MRAI)
f
MRAI
SUM
=
MAX
MRAI;
return
MRAI
SUM;
g
else
f
MRAI
SUM=TD;
return
MRAI
SUM;
g
Figure
1.
Node
T
opology
Impact
of
MRAI
T
imer
on
BGP
Updates
and
Con
ver
g
ence
T
ime
(R.
N.
De
vikar)
Evaluation Warning : The document was created with Spire.PDF for Python.
878
ISSN:
2502-4752
3.
RESUL
T
AND
AN
AL
YSIS
3.1.
MRAI
Vs
Con
v
er
gence
T
ime
and
Updates
Con
v
er
gence
time
v
aries
with
respect
to
MRAI
interv
al
for
def
ault
as
well
as
FMRAI
approach.
The
con-
v
er
gence
time
is
directly
propo
r
tional
with
the
MRAI
timer
which
sho
wn
in
figure
2.
The
con
v
er
gence
time
increases
with
increasing
MRAI
v
alue.
Figure
3
sho
ws
number
of
updates
decreases
with
increasing
MRAI
v
alue.
The
graph
sho
ws
tw
o
dif
ferent
approaches
for
increasing
MRAI
v
alues
with
respect
to
number
of
updates.
It
sho
ws
the
FMRAI
has
more
number
of
updates
than
def
ault
MRAI
v
alue.
S
o
,
to
impro
v
e
the
netw
ork
a
v
ailability
and
for
f
ast
netw
ork
con
v
er
gence
i
t
is
necessary
to
k
eep
the
v
alue
of
MRAI
timer
less.
T
able
1
sho
ws
the
netw
ork
con
v
er
gence
and
update
acti
vities
by
considering
dif
ferent
MRAI
v
alues.
3.2.
Node
Vs
P
ack
et
Deli
v
ery
Ratio
The
dif
ferent
performance
metrics
such
as
pack
et
deli
v
ery
ratio,
end
to
end
delay
,
routing
o
v
erhead
and
throughput
are
used
for
analysis
of
routing
protocols
[25].
Figure
4
sho
ws
pack
et
deli
v
ery
ratio
for
v
arying
number
of
nodes.
From
the
abo
v
e
gi
v
en
results
we
can
say
,
that
def
ault
MRAI
returns
poor
result
as
we
start
increasing
the
number
of
nodes.
FMRAI
protocols
returns
best
result
and
thus
achie
v
es
pack
et
deli
v
ery
ratio
in
range
of
90%
to
95%.
But
as
we
start
increasing
number
of
nodes
results
f
alls
do
wn
belo
w
90%.
T
able
2
sho
ws
the
v
alues
of
pack
et
deli
v
ery
ratio
for
dif
ferent
scenario
of
nodes
(Number
of
Nodes).
Figure
2.
MRAI
vs
Con
v
er
gence
T
ime
Figure
3.
MRAI
vs
Number
of
Updates
Indonesian
J
Elec
Eng
&
Comp
Sci
V
ol.
12,
No.
2,
No
v
ember
2018:
873
–
882
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
879
T
able
1.
MRAI
vs
Con
v
er
gence
time
and
Number
of
updates
Sr
.
No.
MRAI
T
raditional
BGP
Optimized
BGP
T
raditional
BGP
Updates
Optimized
BGP
Updates
1
5
50.23
4.47644
39
259
2
10
52.13
7.47462
39
154
3
15
59.43
10.2025
38
110
4
20
60.17
11.5735
38
92
5
25
70.32
13.8668
35
69
6
30
79.19
14.4961
34
67
Figure
4.
Node
vs
P
ack
et
Deli
v
ery
Ratio
3.3.
Number
of
Node
Vs
Delay
In
this
part,
we
compare
the
end-to-end
delay
from
the
source
node
to
the
destination.
In
Figure
5
the
end
to
end
delay
v
aries
with
number
of
nodes.
The
end-to-end
delay
for
netw
ork
increases
much
f
aster
than
others.
When
no
node
is
a
v
ailable,
then
it
increases
delay
of
pack
et
transmission.
More
nodes
in
netw
ork
will
pro
vide
more
opportunities
to
find
some
suitable
node
for
ef
ficient
forw
arding
of
pack
et
by
considering
potential
score
of
neighbor
nodes.
W
ith
high
node
density
,
the
transmission
delay
is
dramatically
reduced
in
the
netw
ork
sho
wn
in
table
2.
Figure
5.
Number
of
Node
vs
Delay
Impact
of
MRAI
T
imer
on
BGP
Updates
and
Con
ver
g
ence
T
ime
(R.
N.
De
vikar)
Evaluation Warning : The document was created with Spire.PDF for Python.
880
ISSN:
2502-4752
3.4.
Number
of
nodes
vs
Number
of
Updates
Figure
6
sho
ws
number
of
update
messages
are
v
aries
with
respect
to
number
of
nodes.
As
we
increase
the
number
of
nodes
in
the
netw
ork
which
increases
the
respecti
v
e
update
messages.
T
abel
2
sho
ws
the
comparati
v
e
results
for
number
of
updates
in
traditional
BGP
and
optimized
BGP
with
respect
to
number
of
nodes.
Figure
6.
Number
of
nodes
vs
Number
of
Updates
T
able
2.
Number
of
nodes
vs
Number
of
Updates
Sr
.
No.
No.
of
Nodes
P
ack
et
Deli
v
ery
Ratio
Delay
T
raditional
BGP
Optimized
BGP
1
60
80.7411
0.402744
457
990
2
70
87.105
0.280598
462
992
3
80
82.3763
0.366363
488
1039
4
90
84.7848
0.29666
498
1035
5
100
85.5714
0.300134
506
1037
4.
CONCLUSION
AND
FUTURE
SCOPE
The
Con
v
er
gence
time
of
a
netw
ork
is
i
mpro
v
e
by
decreasing
MRAI
timer
.
But
as
we
decrease
it
upto
zero
then
in
the
netw
ork
only
updates
are
transmitted.
The
proposed
technique
Fickle
Mean
R
ou
t
e
Adv
ertisement
Interv
al
(FMRAI)
use
to
impro
v
e
the
netw
ork
con
v
er
gence
time.
The
FMRAI
ha
v
e
lo
wer
pack
et
dropping
ratio,
delay
,
in
comparison
with
traditional
MRAI
technique.
The
proposed
algorithm
also
impro
v
es
the
pack
et
deli
v
ery
ratio,
con
v
er
gence
time,
and
number
of
updat
es
compare
with
tradition
technique
for
dif
ferent
scenarios
(Number
of
Nodes).
In
future
for
impro
ving
the
con
v
er
gence
time,
we
will
compute
P
articl
e
Sw
arm
Optimization
(PSO)
tech-
nique,
which
detects
global
minimizer
to
address
the
problem
of
f
ast
con
v
er
gence
time.
A
CKNO
WLEDGEMENT
I
w
ould
lik
e
to
e
xpress
my
deep
sens
e
of
gratitude
to
w
ards
my
research
supervisors
Dr
.
V
.Chandra
prakash
and
Dr
.
D.
V
.
P
atil
for
their
v
aluable
guidance
and
encouragement.
Also,
I
w
ould
lik
e
to
thank
Mr
.
P
a
v
an
D.
Upadh
ye
for
his
suggestions
to
w
ards
impro
v
ement
of
this
paper
.
REFERENCES
[1]
McPherson
D,
Gill
V
,
W
alton
D,
“Border
g
ate
w
ay
protocol
persistent
route
oscillation
condition”,
RFC3345,
August
2002.
[2]
Anindya
Basu,
Chih-Hao
Luk
e
Ong,
April
Rasala,
“Route
oscillations
in
I-BGP
with
route
reflection
[J]”,
Com-
puter
Communication
Re
vie
w
,
2002;
32(4):
235-247.
Indonesian
J
Elec
Eng
&
Comp
Sci
V
ol.
12,
No.
2,
No
v
ember
2018:
873
–
882
Evaluation Warning : The document was created with Spire.PDF for Python.
Indonesian
J
Elec
Eng
&
Comp
Sci
ISSN:
2502-4752
881
[3]
https://en.wikipedia.or
g/wiki/Border
Gate
w
ay
Protocol.
[4]
Mahesh
K
umar
,
Shishir
K
umar
,
“
Analyzing
and
Impro
ving
Netw
ork
A
v
ailability
in
a
Interdomain
Routing”,
in
Applied
Po
wer
Electronics
Conference
and
Exposition,
2009.
APEC
2009.
T
wenty-F
ourth
Annu
a
l
IEEE
,
2009;
128-131.
[5]
T
.
Grifn,
B.
Shepherd,
and
G.
W
ilfong,
“The
stable
paths
problem
and
interdomain
routing”,
IEEE/A
CM
T
rans-
actions
on
Netw
orking
,
2002;
10:
232243.
[6]
L.
Cittadini,
M.
Rimondini,
M.
Corea,
and
G.
Di
Battista,
“On
the
feasibility
of
static
analysis
for
BGP
con
v
er
-
gence”,
in
IFIP/IEEE
International
Symposium
on
Inte
grated
Netw
ork
Management-
IM
09
,
2009;
521528.
[7]
A.
F
abrikant,
U.
Syed,
and
J.
Re
xford,
“Theres
something
about
MRAI:
T
iming
di
v
ersity
can
e
xponentially
w
orsen
BGP
con
v
er
gence”,
in
INFOCOM11
,
2011;
29752983.
[8]
A.
Elmokash,
A.
Kv
albein,
and
C.
Do
vrolis,
“On
the
scalability
of
BGP:
The
roles
of
topology
gro
wth
and
update
rate-limiting”,
in
Proceedings
of
the
2008
A
CM
CoNEXT
Conference,
(Ne
w
Y
ork,
NY
,
USA)
,
pp.
8:18:12,
2008.
[9]
V
.
Schrieck,
P
.
Francois,
C.
Pelsser
,
and
O.
Bona
v
enture,
“Pre
v
enting
the
unnecessary
propag
ation
of
BGP
with-
dra
ws”,
in
Proceedings
of
IFIP
Netw
orking
Springer
V
erlag
,
2009;
495508.
[10]
A.
Elmokash,
A.
Kv
albein,
and
C.
Do
vrolis
,
“BGP
churn
e
v
olution:
A
perspecti
v
e
from
the
core”,
IEEE/A
CM
T
ransactions
on
Netw
orking
,
2012;
20:
571584.
[11]
A.
Elmokash
and
A.
Dhamdhere,
“Re
visiting
BGP
churn
gro
wth”,
SIGCOMM
Comput.
Commun.
Re
v
.
,
2013;
44:
512.
[12]
G.
Huston,
“The
Churn
Report”,
https://labs.apnic.net/?p=457,
2014.
[13]
E.A.
AiabduIkreem,
H.
S.
Al-Ra
weshidy
,
and
M.
F
.
Abbod,
“Using
a
Fight-or
-Flight
Mechanism
to
Reduce
BGP
Con
v
er
gence
T
ime”,
International
Conference
on
Communications
and
Netw
orking
(ComNet)
,
19-22
Mar
2014.
[14]
X.
W
ang,
O.
Bona
v
enture,
and
P
.
Zhu,
“Stabilizing
BGP
routing
without
harming
con
v
er
gence”,
in
IEEE
Con-
ference
on
Computer
Communications
W
orkshops
(INFOCOM
WKSHPS)
,
2011;
840845.
[15]
Y
u
K.-M.,
Y
u
C.W
.and
Y
an
S.-F
.
,
“
An
ad
hoc
routing
protocol
with
multiple
backup
routes”,
W
ireless
Personal
Communications
,
2014;
57(4);
533-551.
[16]
Shi
v
ani
Deshpande,
Marina
Thottan,
T
inKamHo,
and
Biplab
Sikdar
,
“
An
Online
Mechanism
for
BGP
Instability
Detection
and
Analysis”,
IEEE
T
ransactions
on
Computers
,
2009:
58(11);
1470-1484.
[17]
Geo
Huston,
Mattia
Rossi,
a
n
d
Gren
ville
Armitage,
“
A
T
echnique
for
Reducing
BGP
Update
Announcements
through
P
ath
Exploration
Damping”,
IEEE
Journal
on
Selected
Areas
in
Communications
,
2010:
28(8);
1271-
1286.
[18]
Mohammad
Y
anuar
Hariya
w
an,
“Comparison
Analysis
of
Reco
v
ery
Mechanism
at
MPLS
Netw
ork”,
Interna-
tional
Journal
of
Electrical
and
Computer
Engineering(IJECE)
,
2011:1(2);
151-160.
[19]
Rajvir
Gill,
Ra
vinder
P
aul,
and
Ljiljana
T
rajk
o
vic,
“Ef
fect
of
MRAI
T
imers
and
Routing
Polic
ies
on
BGP
Con-
v
er
gence
T
imes”,
In
proc.
IPCCC,
IEEE
31st
International
Conference
,
1-3
Dec
2012.
[20]
Jackson
Reina
Alzate;
Roberto
Carlos
Hincapi
Re
yes,
“Ev
aluation
of
impro
v
ement
proposals
for
Border
Gate
w
ay
Protocol
(BGP)”,
IEEE
Colombian
Communications
Conference
(COLCOM)
,16-18
May
2012:
1-6.
[21]
Rohit
Nilkanth
De
vikar
,
Dipak
V
.
P
atil,
and
V
.
Chandra
Prakash,
“Issues
in
Routing
Mechanism
for
P
ack
et
F
orw
arding:
A
Surv
e
y”,
International
Journal
of
Electrical
and
Com
puter
Engineering
(IJECE)
,
2016:
6(1);
421-
430.
[22]
Rohit
Nilkanth
De
vikar
,
Dipak
V
.
P
atil,
and
V
.
Chandra
Prakash,
“St
u
dy
of
BGP
Con
v
er
gence
T
ime”,
Interna-
tional
Journal
of
Electrical
and
Computer
Engineering
(IJECE)
,
2016:
6(1);
413-420.
[23]
Rohit
N.
De
vikar
,
D.
V
.
P
atil
and
V
.
Chandra
prakash,
“
A
Mathematical
Approach
to
Impro
v
e
the
Netw
ork
Performance”,
Indian
Journal
of
Science
and
T
echnology
,2016:
9(2).
[24]
Chen
Chen,
Bo
Li
,
Dong
Lin,
and
Baochun
Li,
“Softw
are-Dened
Inter
-Domain
Routing
Re
visited”,
IEEE
International
Conference
on
Communications
(ICC)
,
22-27
May
2016.
[25]
Anton
P
a
vlo
vich
T
e
ykhrib,
“Data
transmission
in
Hybrid
Distrib
uted
En
vironment”,
International
Journal
of
Electrical
and
Computer
Engineering
(IJECE)
,
2016:
6(6);
2989-2993.
Impact
of
MRAI
T
imer
on
BGP
Updates
and
Con
ver
g
ence
T
ime
(R.
N.
De
vikar)
Evaluation Warning : The document was created with Spire.PDF for Python.
882
ISSN:
2502-4752
BIOGRAPHY
OF
A
UTHORS
Rohit
De
vikar
obtained
Bachelor
of
Engineeri
ng
de
gree
in
Computer
Engineering
from
Sa
vitribai
Phule
Pune
Uni
v
ersity
(M.S.),
India,
in
2010.
Also
he
recei
v
ed
Mast
er
of
T
echnology
de
gree
in
Computer
Engineering
from
Dr
.
B
A
TU,
Lonere,
(M.S.),
India
in
2012.
Currently
he
is
a
PhD
Research
Scholar
in
Computer
Science
and
Engineering
in
K.
L.
Uni
v
ersity
,
V
ijaya
w
ada.
He
is
w
orking
as
Assistant
Professor
in
Amrutv
ahini
Colle
ge
of
Engineering,
Sang
amner
,
(M.S.),
India.
His
major
area
of
interest
is
Congestion
Control,
A
v
ailability
of
netw
ork,
Load
Balancing,
Con
v
er
-
gence
speed
etc.
E-mail:
rohit.de
vikar89@gmail.com
(Corresponding
author)
D
.
V
.
P
atil
recei
v
ed
the
PhD
de
gree
in
Computer
Scienc
e
and
Engineering
from
the
S.G.G.S.
insti-
tute
of
Engineering
and
T
echnology
,
S.R.T
.M.U.,
Nanded,
Sept.
2013.
He
is
presently
a
Professor
and
Head
of
Computer
Engineering
department
in
R.
H.
Sapat
Colle
ge
of
Engineering,
(M.S.),
In-
dia
.
His
research
interests
include
Data
center
,
Soft
computing,
Distrib
uted
processing,
and
Data
Mining.
E-mail:
dipakvpatil17@gmail.com
V
.
Chandra
Prakash
recei
v
ed
the
P
hD
de
gree
in
Computer
Science
and
Engineering
from
Acharya
Nag
arjuna
Uni
v
ersity
in
2011.
He
is
presently
w
orking
as
Professor
of
Computer
Science
and
Engineering
department
in
K.
L.
Uni
v
ersity
(A.P
.),
India.
His
research
interests
include
Softw
are
Engineering,
Softw
are
T
esting,
Soft
Computing,
Artificial
Intelligence
and
Data
Mining.
E-mail:
vchandrap@kluni
v
ersity
.in
Indonesian
J
Elec
Eng
&
Comp
Sci
V
ol.
12,
No.
2,
No
v
ember
2018:
873
–
882
Evaluation Warning : The document was created with Spire.PDF for Python.