A
zyxwv
raffic
Engineered
Routing Algorithm
Based
on
Fuzzy
Logic
Junaid A. Khan, and Hussein Alnuweiri Depment of Electrical and Computer Engineering, University of BC, Vancouver BC, V6T
zyx
24,
Canada. Tel: (604)
8229185,
Fax: (604)
8225949
Email: (iunaidk, hussein)@ece.ubc.ca AbstractThis paper presents a routing algorithm that uses fuzzy logic to solve traftic engineering
zyxwvu
E)
outing problem. Current
TE
routing algorithms are either inefficient
or
are too computationally expensive that these cannot be treated as practical solutions. The proposed algorithm performs better than many current TE routing algorithms and has time complexity equivalent to Dijkstra‘s algorithm. Therefore it is suitable to be used in practical routers.
1.
INTRODUCTION The high cost of network equipment assets and the commercial competitive nature of providing internet services have been pressing large Internet Service Providers (ISPs) to look for ways to generate more revenue without substantially increasing their investments in upgrading infrastructure. A key to achieving such goal is the ISPs’ ability to provide ‘Sigh value” IF’based services to customers, while lowering their network costs by achieving maximal operational efficiency. Some of these
“high
value” services are virtual private networking
(VPN),
ideo on demand and other multimedia applications, and distributed computation over Internet, etc.
To
provide these “high value” IF‘based services, current network development is focusing on Quality of Service
zyxwvut
QoS)
in packet networks, which aims to enable different types of information
to
be transported with different levels of service guarantees. Most of the research in this area has been focused either on simplifymg
QoS
signaling mechanism,
or
providing
QoS
in isolated network segments. Without proper longterm network capaciry planning and dynamic mechanism for allocating and sharing network resources, providing
QoS
can be an expensive and unsuccessful exercise for network service provides. In recent years, it became obvious that there is a need for a new paradigm that takes into consideration network wide topology and bandwidth resources to enable ISPs to optimize their resource utilization, by evenly distributing and balancing the traffic load on the various links, while maintaining the promised levels of services to customer flows. This is known
as
Traffic Engineering (TE). Currently, TE is still an infant area of research and many
of
its techniques and goals are vaguely defined or depend on a certain view of the network. The most definitive application
of
TE
has
been in the area of constrained routing i.e. determining explicit paths for traffic aggregates within a packet network subject to bandwidth
or
policy constraints. These explicit paths
are
supported by Multi Protocol Label Switching
(MPLS).
Unfortunately, the problem
of
finding such paths
with
TE constraints is NPhard. Current heuristic algorithms to solve this problem are either inefficient, e.g. Widest Shortest Path
(WSP)
[l],
or are computationally expensive, e.g. Minimum Interference Routing Algorithm
zyx
MIRA)
[2].
In this paper, a
zyxw
uzzy
logic based TE routing algorithm is presented. The algorithm provides better quality solution than WSP but with much smaller computational complexity than MIRA.
II.
PROBLEM FORMULAnON The network is considered
as
a graph and it is assumed that
a
TE aware routing protocol such
as
OSPFTE is operative
in
the network that provides dynamic bandwidth information on each link of the network. Also
MPLS
zy
s
deployed in the network to support explicit paths. The network is represented by a graph
zyx
N.L),
where N is the set of nodes in the graph and
L
s the set of links
(or
edges) connecting these nodes.
For
traffic engineering purposes the set
B
of residual link capacities
r,
for each link
i
and the set
C
of total capacities
ci
of each link are also given.
A
flow request is represented by a triplet
(ingress,
egress,
D),
where
ingress
and egress are source and destination nodes and
D
s
the bandwidth demand. The traffic engineering routing problem is formulated as the problem of routing the flow requests over a network graph such that bandwidth demand
D
is satisfied such that the least number of future flow requests will be rejected.
A.
NPhardness If all the future demands are known a priori (offline routing), then the
TE
routing problem can be mapped to bandwidth packing problem
[3],
whose objective is to route the maximum numher of already known demands while satisfymg bandwidth constraints for all demands. The bandwidthpacking problem is
a
wellknown NPhard problem. If these demands are not known a priori
as
it is the case in online routing) then the problem becomes much harder to solve. Therefore, it can be concluded that the online TE routing is NPhard. In.
LITERATURE
SURVEY
The most common algorithm used in explicit path routing is the shortest path routing. In this algorithm, the path with least number of hops between ingress and egress router is computed. In case of weighted links, the link weight represents the link preference. Indeed, residual bandwidth values can be conveyed between routing nodes using new TEbased protocols such as OSPFTE
[4].
For routing with bandwidth guarantees, the link weight can be set to the residual link bandwidth. In constraintbased shortest path algorithm, the
algorithm considers only those
links,
which have residual bandwidth more than the requested bandwidth. Although, the shortest path algorithm is able to find the paths with the required bandwidth, the algorithm does not guarantee the optimal utilization of network resources. For example, it is possible that selecting a particular route for requested LSP may cause congestion in certain portions of the network and result in the rejection of some future LSP requests. The example in Figure
1
shows some of the drawbacks in shortest path algorithm. Suppose that an explicit path has to be routed from
A
to
zyxwvuts
and the requested bandwidth is
zyxwvut
units. In this case, if the algorithm selected
zyxwvutsrq
A,C,Efl
zyxwvu
s
he LSP route then it is more likely that any request f?om
C
o
E
with bandwidth requirement larger than
zyxwvuts
units will be blocked. However, if
A3,Dfl
was
selected instead then bandwidth request of up to 11 units can be accepted.
zyxwvutsr
Fig
zyxwvutsrqpon
.
E.xampic
for
Shortst
Path
R&ingalgorithm.
7hc
numbm
%de
links
represents
residual
link bandwidth
and
not
the
link
costs.
Another variant
of
the shortest path algorithm is
known
as the Widest Shortest Path (WSP) algorithm
[I].
If more than one shortest path to a given destination satisfy a bandwidth request, then WSP selects the path that has largest bottleneck bandwidth. In other words, WSP maximizes the bandwidth of the bottleneck
link
as it
finds
he path with smallest number of hops.
here
are several limitations
in
WSP.
'The first limitation is that, it will never find a path with more hops than in the min hop path, even if it will result in less congestion.
As
shown in Figure 2, the least congested path is
{A,G,H,II;F),
ut it will never be selected because two other paths
are
available which have
smaller
hop count. Another shortcoming
of
the algorithm is that, the widest pa& is selected based on bottleneck link only. However, it is possible that two paths have same residual bandwidth in the bottleneck link but one may be better than the other based on other links. Thiscan be explained with the example of Figure
2,
where there
are
two possible shortest
path
with
same path bandwidth, i.e.,
{A,B,D,F
and
{A,C,EI;F),
n both cases the path bandwidth is 10. However path
{A,BD,F
s probably better
than
{A,C,E,F)
since
it has more residual bandwidth on its links. WSP is unable
to
differentiate between these two paths and may not select the best path even among the set of shortest paths (in terms of hop count).
Irn
TO,
rn
I
Fig
2
Example
for
Widest
Shorts3
Path
Routing
algorithm.
The
nmbm
hide inks
represents
residual
link bandwidth
and
not
the
link
C StS
Another class of routing algorithms
known
as Minimum Interference Routing Algorithm
(MIRA)
was
presented in
[2,5,6).
These algorithms consider routing between given ingress/egress pairs in a network graph. The basic idea is to avoid the decrease
in
the maximum possible flow (maxflow: The maxflow value between an ingredegress pair in a graph
G
is the maximum possible bandwidth that can be routed between them.) between given ingresslegress pairs
[7],
ue to cbwsing a route between some other ingress/egress pair, termed as interference. In other
words,
the objective is to decrease the interference while routing a new flow request with, potential, future flow requests. The time complexity of
MIRA
is
O@
n2
mtn),
where
n
s the number of nodes in the network,
m
is the number of links and
p
is the number
of
predetermined
ingresslegress
pairs. It
was
claimed in
[2,5,6],
that this complexity is reasonable, because the number of
ingress/egress
pairs is usually very
small
However, there is no real evidence that this is indeed the case.
In
fact, network service provider economics normally mandates increasing the ratio of border customer facing routers to internal router. Thus,
in
worst
case
scenario it
is
possible that most of the routers in a network are edge routers and the number of
ingresslegress
pairs to be
p
=
n2,
and the time complexity is
O(n4
min)
considering that current SPF algorithm has worst case complexity
O n2),
with more efficient implementations SPF algorithm requires
O n
og
m).
It does not seem practical to use any variant
of
MIRA
as an online algorithm because the typical flow setup requests
are
processed at
ingress
routers, which operate at very high load and have limited computation power.
w.
ROPOSED
ALGORITHM
It is assumed that flow demands arrive one by one and there is no knowledge about future demands. In this scenario, one of the best methods to route an optimal number
of
demands, is to avoid congestion in
any
part
of the network. Then problem
of
routing a flow demand, such that the network will be able to accommodate large number
of
future
demands,
can
be converted into routing the current demand such that it will create
less
future congestion in the network.
To
solve this problem, we have adopted a somewhat different approach that employs concepts and techniques from
Fuuy
Logic theory
[8]
(as opposed to crisp set theory). This
455
approach is motivated by the need for new thinking regarding TEbased routing, especially since TE requirements are not strict and
zyxwvutsrq
uzzy
in nature. Crisp set theory, on the other hand, deals with strict membership problems. In the proposed algorithm,
fuzzy
logic is used to determine the
fuzzy
zyxwvu
et
of
feasible links.
zyxwvutsr
nce
the
fuzzy
membership of each
li
s determined, its membership value is used to route the demand. The higher the membership of a link in the
fupy
set of feasible
links,
the higher is its chance to be included
in
the route. The following linguistic rule is proposed to find the membership of a link
tn
the
fuzzy
set of feasible links.
Rule
zyxwvutsr
1:
IF
a link has a
zyxwvutsrq
higher residua bandwidiK’
OR
“low
bandwidth urilizafion”
THEN
f is highly feasible link.
Using
ORlike Ordered Weighted Averaging (OWA) operator
zyxwvutsr
]
he rule
R1
evaluates to the following. where superscript
f
represents feasibility,
p
represents membership value of link iin
fu y
set of feasible links,
zyxwvu
U 
I
and
pibw
epresents the membership values of link n
fuzzy
subsets
of
low utilization and high bandwidth. The proposed membership functions
are
shown in Figure
3.
BL
and
BH
represent the lowest and highest residual bandwidth in a network graph.
BM
can be chosen to give preference to links having residual bandwidth in
a
particular range, in our case
EM=
L
+
0.25
EH
L .
It
is
obvious
that
zyxwvutsrq
ijkstra’s
algorithm cannot be used
as
is with these
fuzzy
membership values; therefore we propose
a
fuzzy
set of reachable nodes. Following
funy
rule is proposed to find the membership value of a node in this set
Rule
R2:
IF
a node
x
is
“highly reachable“
AND
“a
link connecting
x
zyxwvutsrqpon
o
anoiher
node
y
is
highlyfearible”
AND
“paih
io
y
has smaller number
of
hops”
THEN
the connected node y is also highly reachable. Using
AND
like OWA
[ ]
he rule
R2
evaluates to the following
P. ..
PL,
(a)
(b)
Fig
3.
(a) Membership of
link
i
in
Ule
I%ZZY
subret
of
higher residual bandwidth
vrrm~
ink residual bandwidth,
(b)
Manbaship
of
link
i
in
the
fuzzy
subset
of
low
bandwidth
utilizarion
vmus
bandwidth utilization.
*
4
rr
p;
=
maxuy,py,e,)
.
...
.
....
3)
Equation
2
represents mle
R2
whereas Equation
3
checks that hether node
y
is already highly reachable through some other path, if it is the case, then membership value of node
y
does not change. In these equations,
pi
is the membership of node
x
in
fuzzy
set of reachable nodes,
p
is the membership values of link connecting
x
and
y
and ,U&p,his the membership value of path fiom source to
y
through
x
in the
fiuq
subset of smaller paths, this value is calculated as shown in Figure
4.
NMH
is the minimum number of hops needed to reach
a
node and
H
is the maximum number of allowable hops. The membership values
of
reachable nodes are used in a
G
=
G NJ)
=
Input Graph.
C
=
Set
of
total
link
capacities
6,.
D
=
Bandwidth demand
to
be routcd.
Path,= Set of
nodes
n
the
path
fmm
inp
o
nodey
B
=Set
ofmidual
link
capacities
r,
inFeas
=
zyx
n
node.
egrers
=
Eps
ode.
Be .
1.
2.
3.
4.
5.
6.
LOOP
LOOP
Remove all links with
rm
c
D
rom
G
P= ).Pothy= ]
Vy,
p‘=l,and
p‘,=O
V’itingms.
Run
Dijkstra’s algorithm
to
find
”
or
each
node
mm
inqs
Findx
e
P
such
that
p’x
is
maximum
VXE
p;
P=PU x).IfPcontainsegrersthsnuitl~;
VYE
P
having
a
hnk
Ucsdate
Fig
5.
Strum
of F
TE
routing
algorithm.
modified
fuzzy
version of Dijkstra’s algorithm presented
in
Figure
5.
In the beginning source node has reachability with membership value
1
whereas all other nodes have membership values
equal
to
0
in the
fuzzy
set of reachable nodes.
As
he algorithm progress these values
are
updated until the best path
456

,
.......................
.
zyxwvuts
Fig
6 Nmo*
zyxwvutsrqpon
sed
zyxwvutsrq
simulation, thin
lines
have capacity
of
1200
bandwdth
units
and
thick
lints
have
capacity
of4800
units
21.
to
egress is found.
zyxwvuts
V.
SIMULATION
zyxwvuts
ND
RESL‘LTS
A
simulator is developed to test the performance
of
the proposed algorithm. This simulator is capable of simulating different routing algorithms for hfferent input graphs and set of flows. Random set
of
flows (random ingress/egress pairs and random flow demand between
I
and
4
uts)
were created for each
test
and saved in a ~ext
ilc
Each algorithm is tested on these set of flows, this setup guarantees that
algonthms
are compared for exactly the same sets of
flows,
therefore provides accurate comparison. The network used in the simulation is shown in Figure
6,
it
is same
as
in
[2].
Table
I
shows the end results after different tests. In both tests, FTE performance is in between
MIRA
and
WSP,
which
was
expected. However, time complexity of FTE is much smaller than that of
MIRA,
therefore it can be a better choice in those networks where routers with limited resources
zyxwv
re
used. Time complexiry of FTE and
WSP
s same. Figure
7
compares the algorithms based on their performance after each flow request. These figures show that
FTE
performs
bener than
WSP
and
slightly
worst
than
MRA

’
......
z
_
zyxwv

i

f,
TU
:
____
.,. .&,
iIiiii
.. I
c
e)
a)
Fig
7.
Compuison
of
routing
algorithms.
(a)
and
@)
arc
for
4
ingrMd
egress
pairs.
c)
and
(d) are for
12
ingress
I
rgrar
ppim
whereas execution time
of
MIRA
increases considerably when number of ingress egress pairs
is
increased. From this result it can be imagined that how much time
MIRA
will
need, if full set of ingressfegress
pairs
is taken into consideration. These simulation results also support the asymptotic time complexity ofthe algorithms.
REFERENCES [i] Roch
A.
G.,
Ariel
Orda,
and
Douglcr
Williams,
9 s
Routing
Mvhanism
and
OSPF
Extensions,”
in
zyxw
roceedings OJGLOBCOM,
,907
TABLE
I
SIMULATIONRESULTS
[21
Kcdialam
M,
and
lalishman
T.V.,
“Minimum
nlderence
Rouling
with Application
IO
MPLS
Tm..c
Engineering”,
n
prdngr
of 19‘
Amount
of accepted
BW
Annual
loin1
Canfmss of the IEEE Computer and
Commpunicatiau
Test
of
Society,
March
2000,
pp.
88G893.
Typ
requests [3] Sadiq M.
Sait
and Habib Yousscf,
ltermive
Computer
Alprilhm
wirh
of
acccpted
requests
wsp
wusp
MIRA
5000
2867 3280 3073 7196
8242
7728
Applicmiom
in
Engineering.
Solving
Combinatorial Opiimirotion
Problem.
EEE
Cammtcr
Socictv.
1999.
ndm
..
<
Yme. and
Kimti
Kmnella
‘.Traffic Eoeincain.
Engincmng
Using
Enhanced
Minimum
Intcrfermce
Routing:
An
Appmach
Based
on
Lexicographic
MaxFlow,”
In
Proceedings
ofth
Inrenolional
Workshop
on
QoS
(IWQoS),
Pittsburgh,
USA
June
2000. (61
K.
Kar,
M.
Kcdialam,
and
T.V.
Lakshmah
“Minimum
Interference
Routing
of Bandwidth
Guaranteed
Tunnels
with MPLS
Tmffic
Engineering
Applications,”
IEEE
Journal
an
Selected
Area in
Communicalion,val.
8.
no.
12,
pp.
25662579,
Dec.
2000.
A.
V.
Coldberg,
and
R.E.
Tarjan,
‘Solving
Minimum Cost
‘Flow
Problem by
Successive Approximation,”
n
Proceedings
0119’~
CM
Symposium on
omputing
Themy,
pp.
718.
1987.
LA. Zadeh,
“Outline of
a
Nm
Approach
to
the
Analysis
of
Complcx
Systems
and
Lkcision
Rocerses,”
EEE
Transaction
Systems
Man.
Cybm,
vol
SMC3,
no.
pp.
2844,
973.
comparison with 0(n4mi”)). Table
2
shows the exact
Operaton
in
Multisritaia
Decision
Making,”
lEEE Transaction
on
simulation time for different test cases. It can be easily seen that FTE takes around
2
o
3
times more time than
WSP.
TABLE
2
SIMULATION
Time
Simulation
time
in
secs
Of
WSP
MmA
FE
Typc
req
nests
ingieg
inueg
(71 000 0.47 22.47 1.07
9000
0.73 238.3 2.30
Simulation
results
in
im
f
number
of
accepted
rqusrts
and
[8]
amount
of
total
bandwidth routed.
but with considerably less time complexity
qn’)
in
[9] Rinald
R.
yagrr,
ordered
weighted
ragi
~g ari~
Systems,
MAN, and
Cybanctics
vol.
18,
no.
I,
January 1988.
457