A traffic engineered routing algorithm based on fuzzy logic

of 4
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Others

Published:

Views: 76 | Pages: 4

Extension: PDF | Download: 0

Share
Description
A traffic engineered routing algorithm based on fuzzy logic
Tags
Transcript
  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) 822-9185, Fax: (604) 822-5949 E-mail: (iunaidk, hussein)@ece.ubc.ca Abstract-This 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 long-term 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 NP-hard. 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 OSPF-TE 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. NP-hardness If all the future demands are known a priori (off-line 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 bandwidth-packing problem is a well-known NP-hard 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 NP-hard. 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 TE-based protocols such as OSPF-TE [4]. For routing with bandwidth guarantees, the link weight can be set to the residual link bandwidth. In constraint-based 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. This-can 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 (max-flow: The max-flow 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 pre-determined 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 TE-based 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 OR-like 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 -: ____ .-,. .&, iI-i-i--ii- .. 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 Max-Flow,” 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. 2566-2579, 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. 7-18. 1987. LA. Zadeh, “Outline of a Nm Approach to the Analysis of Complcx Systems and Lkcision Rocerses,” EEE Transaction Systems Man. Cybm, vol SMC-3, 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
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks