# Class-Based Constraint-Based Routing with Implemented Fuzzy Logic in MPLS-TE Networks

Authors: Michal Pištek; Martin Medvecký
Journal: Journal of Computer Networks and Communications
 (2014)

---

## Abstract

The paper deals with constraint-based routing (CBR) in MPLS-TE networks and proposes a new CBR algorithm based on fuzzy logic called Fuzzy Class-Based Algorithm (FCBA). Multiprotocol label switching with traffic engineering (MPLS-TE) networks represent a popular mechanism to effectively use resources of service providers’ core networks. The paths can be either built by administrators (explicit routing) or built by using existing routing algorithms which mostly decide based on the shortest paths towards the destination which might not be sufficient in nowadays’ multimedia networks. To address this problem various CBR algorithms have emerged which take into consideration various aspects important to existing traffic like QoS parameters or administrative policies. FCBA makes routing decisions based on traffic classes and by using fuzzy logic we can assign normalized values to various constraints based on the traffic class’ preferences (e.g., low delay paths for voice traffic) and network administrator’s preferences (e.g., avoiding congested links). The paper provides comparison of FCBA with existing CBR approaches based on their ability to provide QoS parameters loss. The simulations show that FCBA provides the best results for the highest priority traffic where it uses lower priority traffic to efficiently utilize the network.


---

## Body

## 1. Introduction

Nowadays the modern telecommunication networks should be able to transfer very varied multimedia traffic resulting in a fully converged network. Transferring data, voice, and video traffic in one network requires effective mechanisms which take the various traffics’ requirements in consideration [1]. Such requirements are in a form of quality of service (QoS) parameters. The proposed QoS mechanism should try to meet the desired delay, jitter, or loss values desired by the traffic flows [2].Recently MPLS-TE networks have been widely implemented in the core networks of telecommunication operators. MPLS-TE provides connection-oriented approach in IP networks. It creates end-to-end paths (LSPs) where it can guarantee bandwidth and with traffic engineering it can truly optimize the network’s resources. It enables using explicit routes which might not be ideal according to the routing algorithms but they enable using network’s resources more efficiently. Otherwise MPLS-TE relies on the routing algorithms to build the LSPs.The routing algorithms play an important role in terms of QoS ensuring and optimal resource allocation from the network’s point of view. Routing based on the destination address using minimal hop count as the decision criteria is not sufficient anymore. Administrative policies, performance requirements, load balancing, and scalability are thus becoming increasingly significant factors in the routing decisions. Constraint-based routing (CBR) uses such parameters to make the routing decisions.Many CBR algorithms were proposed which in most cases do not take into consideration various aspects important to various traffic types so we propose a class-based algorithm which ensures that delay-intolerant higher priority classes are treated differently from delay-tolerant lower priority classes. The algorithm uses multiple constraints to make the routing decision. The decision is based on fuzzy logic which allows the algorithm to take all the constraints into consideration using their normalized (fuzzificated) values by predefined membership functions which provide conversion between real and fuzzy values. We use additional class-based metric weights to differentiate how much impact the particular constraint has on the particular traffic priority to make sure that the high priority classes are treated as best as possible whereas the lower priority classes use higher weights for the metrics improving the overall network utilization.The paper is divided as follows. In the following chapter we provide a brief survey of CBR and fuzzy logic. The existing CRB algorithms are represented in Section3. In Section 4 we propose the new CBR algorithm called Fuzzy Class-Based Algorithm. Section 5 presents our simulation model and the simulation results are discussed in Section 6 where we focus on the differences in routing decisions of the proposed and compared CBR algorithms. We conclude the paper in Section 7.


## 2. Background

### 2.1. Constraint-Based Routing

Constraint-based routing (CBR) represents a class of routing algorithms that base path selection decisions on a set of requirements or constraints, in addition to the destination. These constraints may be imposed by administrative policies, or by QoS requirements. Constraints imposed by policies are referred to as policy constraints, and the associated routing is referred to as policy routing (or policy-based routing). Constraints imposed by QoS requirements, such as bandwidth, delay, or loss, are referred to as QoS constraints, and the associated routing is referred to as QoS routing [3].QoS constraints are represented in the form of metrics. One metric for each constraint is to be specified like bandwidth metric, jitter (variation in delay) metric, delay metric, number of hops metric, packet loss ratio, and so forth for one node to all other nodes in the network. Metric for a complete path with respect to each parameter is determined by the composition rules of metrics. The metrics might have the following character.(i)
Additive Metric. The value of that constraint for a path is the addition of all links constituting path (delay, hop count, cost, and jitter). For example, overall delay of the path Dpath is represented as a sum of the partial delay values of the links forming the path
(1)Dpath=∑dlink.(ii)
Multiplicative Metric. Using this metric, the value for the complete path is multiplication of all its edges (reliability, loss ratio). For example, the overall reliability of the path Rpath is represented as
(2)Rpath=∏rlink.(iii)
Concave Metric. In this metric, we can take either min value or max value among all the edges for a path. For example, bandwidth of the path Bpath can be represented as
(3)Bpath=max⁡min⁡⁡blink.The constraints for a complete path may be in a constrained or in an optimization form. In constrained form, some condition is put on constraint value, for example, a path which has delay less than a desired value. The path satisfying the condition is called feasible. On the other hand optimization refers to path having minimum or maximum value for a constraint, for example, a path that has minimum delay among all the paths. This path is called optimal path [4].


### 2.2. Fuzzy Logic

Fuzzy logic differs from the traditional Boolean logic by introducing terms like partial truth or partial lie so multiple truth values can be achieved as depicted in Figure1.Figure 1
Comparison of traditional and fuzzy logic.A fuzzy logic system (FLS) is a system that is defined as the nonlinear mapping of an input data set to a scalar output data. A FLS (shown in Figure2) involves four main sections: fuzzification, rules, inference engine, and defuzzification. First, a crisp set of input data is received and then is converted to a fuzzy set using fuzzy linguistic variables, fuzzy linguistic terms, and membership functions. This phase is called fuzzification. Thereafter, an inference is made using a set of rules. Finally, the resulted fuzzy output is mapped to a crisp output by the membership functions. This phase is called defuzzification [5].Figure 2
Fuzzy logic system.


## 2.1. Constraint-Based Routing

Constraint-based routing (CBR) represents a class of routing algorithms that base path selection decisions on a set of requirements or constraints, in addition to the destination. These constraints may be imposed by administrative policies, or by QoS requirements. Constraints imposed by policies are referred to as policy constraints, and the associated routing is referred to as policy routing (or policy-based routing). Constraints imposed by QoS requirements, such as bandwidth, delay, or loss, are referred to as QoS constraints, and the associated routing is referred to as QoS routing [3].QoS constraints are represented in the form of metrics. One metric for each constraint is to be specified like bandwidth metric, jitter (variation in delay) metric, delay metric, number of hops metric, packet loss ratio, and so forth for one node to all other nodes in the network. Metric for a complete path with respect to each parameter is determined by the composition rules of metrics. The metrics might have the following character.(i)
Additive Metric. The value of that constraint for a path is the addition of all links constituting path (delay, hop count, cost, and jitter). For example, overall delay of the path Dpath is represented as a sum of the partial delay values of the links forming the path
(1)Dpath=∑dlink.(ii)
Multiplicative Metric. Using this metric, the value for the complete path is multiplication of all its edges (reliability, loss ratio). For example, the overall reliability of the path Rpath is represented as
(2)Rpath=∏rlink.(iii)
Concave Metric. In this metric, we can take either min value or max value among all the edges for a path. For example, bandwidth of the path Bpath can be represented as
(3)Bpath=max⁡min⁡⁡blink.The constraints for a complete path may be in a constrained or in an optimization form. In constrained form, some condition is put on constraint value, for example, a path which has delay less than a desired value. The path satisfying the condition is called feasible. On the other hand optimization refers to path having minimum or maximum value for a constraint, for example, a path that has minimum delay among all the paths. This path is called optimal path [4].


## 2.2. Fuzzy Logic

Fuzzy logic differs from the traditional Boolean logic by introducing terms like partial truth or partial lie so multiple truth values can be achieved as depicted in Figure1.Figure 1
Comparison of traditional and fuzzy logic.A fuzzy logic system (FLS) is a system that is defined as the nonlinear mapping of an input data set to a scalar output data. A FLS (shown in Figure2) involves four main sections: fuzzification, rules, inference engine, and defuzzification. First, a crisp set of input data is received and then is converted to a fuzzy set using fuzzy linguistic variables, fuzzy linguistic terms, and membership functions. This phase is called fuzzification. Thereafter, an inference is made using a set of rules. Finally, the resulted fuzzy output is mapped to a crisp output by the membership functions. This phase is called defuzzification [5].Figure 2
Fuzzy logic system.


## 3. Related Work

Multiple CBR algorithms were proposed. The basic CBR algorithms are Widest Shortest Path (WSP) and Shortest Widest Path (SWP). WSP first selects the path with maximum available bandwidth capacity of the bottleneck link among the paths having the least hop count. On the other hand SWP is optimized on the hop count first and, when there are multiple such paths, selects among them the one with the maximum available bottleneck bandwidth. Minimum Interference Routing Algorithm (MIRA) tries to route the new connection so that it interferes as little as possible with the possible future demands by calculating the critical links. Dynamic Online Routing Algorithm (DORA) is similar to MIRA but watches the number of the paths and not flows transmitting through the link. Profile Based Routing (PBR) algorithm is based on the preknown classes of the flows, named as profiles. The approach is splitting the domain resources into the profiles between ingress-egress pairs known a priori, which constitutes the first phase of the algorithm. In the second phase, the flows are admitted one at a time based on their resource requests and the remaining capacity in the traffic class they map into. Fuzzy Routing Algorithm (FRA) applies fuzzy logic to combine the desired goals into one condition. The goals are maximizing maxflow, for example, the capacity of the bottleneck link on the path, maximizing the residual bandwidth on the links other than the bottleneck link, and minimizing path length for its number of hops. It defines membership functions for these goals and combines them in the defined rule which finds the best compromised path [6, 7].


## 4. Proposed CBR Algorithm

The aim of our proposed CBR algorithm called Fuzzy Class-Based Algorithm (FCBA) algorithm is to bring flexibility to the chosen routing constraints (metrics) and to make the routing decisions based on various needs of the traffic classes and/or the network itself.Fuzzy logic represents an ideal tool to make the routing decisions based on multiple constraints by normalizing these constraints in interval between 0 and 1 by membership functions. This way the constraints can be treated in a single compromised rule which decides which path the traffic should be routed to. Similar approach could be seen with FRA (mentioned in Section3) but the main difference is that FCBA makes class-based routing decisions by deciding which metric will have the biggest impact for the particular traffic class so at the same time various paths can be chosen for various traffic classes with the same computed metrics.The routing decision of the proposed algorithm is based on three metrics.(i)
Hop Count. Shorter paths should be chosen to limit the delay.(ii)
Available Bandwidth of Bottleneck Link. Bottleneck links with low available bandwidth should be avoided.(iii)
Path Utilization. Paths with low utilization should be chosen to efficiently use the overall network’s resources.Unlike WSP or SWP algorithms the proposed algorithm does not make the first decision based on one metric and with the remaining feasible paths performs the routing decisions based on the other one.Each metric is represented by its membership function. The membership function converts the real (crisp) values into the fuzzy values. This way FCBA does not have to deal with various measurement units like bit/s or number of hops and only deals with the normalized (fuzzificated) values which are all in the[0,1] interval. Thanks to this, FCBA can combine the used metrics into one routing decision at the end. It applies that the higher value the particular membership function achieves the better the path appears from the point of view of the particular metric.The hop count is represented byap membership function:
(4)ap=1-hmax⁡+1h.Hereh represents the actual hop count of the particular path. This function achieves the highest value (=1) when only one hop is between the ingress LER and the destination (meaning that ingress and egress LERs are directly connected without any LSRs between them). It decreases linearly up to the hmax⁡+1 value, where hmax⁡ represents maximum possible hop count.The available bandwidth of bottleneck link is represented bybp membership function:
(5)bp=b1bmax⁡.Valueb represents actual available bandwidth of the particular path’s bottleneck link. This function linearly rises up to the bmax⁡ value which represents maximum possible available bandwidth of the links in the network. The algorithm always uses the link with the lowest available bandwidth of the particular path.The path utilization is represented bycp membership function:
(6)cp=0,ifcp′<0cp′L,otherwise,(7)cp′=∑lμ∈plμ,(8)lμ=1,ifμl<μmin⁡1-μl-μmin⁡μavg-μmin⁡,ifμmin⁡<μl<μavg-1+μl-μmax⁡μavg-μmax⁡,ifμavg<μl<μmax⁡0,ifμl>μmax⁡,(9)μavg=∑l=1LμlL.First the algorithm calculates the average utilizationμl of all the links of the network and then assigns a value lμ to every link’s utilization μl based on the following function. Positive lμ value means that the link has lower than average utilization and the negative value means that its utilization is above average. For every path, the cp′ value is computed which achieves the highest value when all the links of the path have utilization below the predefined minimum utilization value (μmin⁡). The final cp value is normalized in [0,1] interval. The aim of cp value is to route the traffic through the underutilized paths in the network.The routing decision is then based on the computed costcostp which combines these three metrics which leads to choosing a path which provides the best compromise of these metrics. Note that the algorithm calculates this cost for every possible path in the network:
(10)costp=w1,cap+w2,cbp+w3,ccp.We define the weightsw1,c, w2,c, and w3,c to take into consideration various needs of the traffic class c. The weight w1,c should be set high for those traffic classes which require low delay values (e.g., voice). For such classes the weight w2,c should be set low because it enables these classes to use short paths with lower available bandwidth of bottleneck link and on the other hand tries to limit the delay tolerant classes to use such paths. The weight w3,c should be set high for those traffic classes which can tolerate higher delay values (e.g., web traffic) and so there is higher chance that the longer and underutilized path will be chosen for these classes so the shorter ones can be later used by delay intolerant classes and the utilization in network is better distributed.The best path for the incoming flow is then represented by the lowestcostp value. And consequentially the path (LSP) with this cost is chosen and explicitly established using CR-LDP protocol and the particular flow is mapped into this LSP.For better visualization we provide the membership functionsap and bp and the function lμ in Figures 3, 4, and 5. As mentioned earlier note that the higher the function’s value is, the better the path seems.Figure 3
Membership functionap.Figure 4
Membership functionbp.Figure 5
Functionlμ representing normalized μl.


## 5. Simulation Model

The simulations were performed using Network Simulator 2 (NS-2). The network topology (Figure6) consists of two label edge routers (LERs) and seven label switching routers (LSRs) forming twelve possible paths between the traffic source and the traffic receivers. These paths differ from each other in various link’s bandwidth (from 2 Mbit/s to 4 Mbit/s), which is indicated by the numbers on the links, and in the hop count (from 2 to 5 hops).Figure 6
Simulation model.We add Table1 with available paths and their assigned path number which will be referred to in the next chapter.Table 1
Available paths.
Path between LER1 and LER2
Path number
LSR1-LSR2
1
LSR3
2
LSR4
3
LSR5-LSR6-LSR7
4
LSR1-LSR3-LSR2
5
LSR1-LSR2-LSR3
6
LSR3-LSR1-LSR2
7
LSR3-LSR2
8
LSR4-LSR5-LSR6-LSR7
9
LSR4-LSR7
10
LSR5-LSR4
11
LSR5-LSR4-LSR7
12We used three traffic classes representing voice, video, and web traffic. The simulation lasts for 20 seconds where each traffic class is represented by three flows. The flows’ description and their star times are depicted in Table2.Table 2
Traffic description.
Traffic flow
Rate [kbit/s]
Packet length [B]
Traffic generator
Start [s]
Web1
1000
450
Exp.
1
Web2
1000
450
Exp.
4
Web3
1000
450
Exp.
7
Video1
1500
800
CBR
2
Video2
1500
800
CBR
5
Video3
1500
800
CBR
8
Voice1
600
98
CBR
3
Voice2
600
98
CBR
6
Voice3
600
98
CBR
9The weights introduced in (10) for each traffic class and utilization values introduced in (8) are chosen as follows:(i)
w1,voice=0.75,(ii)
w2,voice=0.25,(iii)
w3,voice=0.5,(iv)
w1,video=0.5,(v)
w2,video=0.5,(vi)
w3,video=0.5,(vii)
w1,web=0.25,(viii)
w2,web=0.5,(ix)
w3,web=0.75,(x)
μmin⁡=10%,(xi)
μmax⁡=90%.


## 6. Simulation Results

We compared the classical constraint-based routing algorithms WSP and SWP and our new proposed FCBA algorithm.We tried classical routing based on minimum hop count but we do not include detailed results of this implementation because routing based on a distance vector (DV) algorithm causes all the traffic to traverse through the same path (Path 2 in our case) resulting in very high loss rates which make the traffic unusable.SWP algorithm makes routing decisions firstly based on available bandwidth (AB) of the bottleneck link so when Web1 flow starts to transmit, Path 4 is used because it has the highest AB. The remaining AB of Path 4 then drops to 3 Mbit/s which is the AB of Path 3 but because Path 3 has fewer hops, it is used when the next flow, Video1, arrives. We provide full path selection together with the actual AB of each path in Table3. The flows in the table are queued as they arrive. We highlight the AB of the path which is to be selected for the arriving flow. For simplification only the paths which are chosen are shown in the table (Paths 1–4). Note that when the same AB occurs the path with fewer hops is chosen.Table 3
The path selection and the available bandwidth of the paths using SWP.
Traffic flow
Path number
AB
Path
1
AB
Path
2
AB
Path
3
AB
Path
4
[Mbit/s]
[Mbit/s]
[Mbit/s]
[Mbit/s]
Web1
4
3
2
2
4
Video1
1
3
2
2
3
Voice1
4
1.5
2
2
3
Web2
4
1.5
2
2
2.4
Video2
2
1.5
2
2
1.4
Voice2
3
1.5
0.5
2
1.4
Web3
1
1.5
0.5
1.4
1.4
Video3
3
0.5
0.5
1.4
1.4
Voice3
4
0.5
0.5
0
1.4Implementing SWP in our scenario resulted in a better distributed traffic than using the DV algorithm. But we observed a packet loss of Voice2 flow because of Video3 flow which could not find a path with sufficient bandwidth (1.5 Mbit/s) and was forced to use Path 3 which only had AB = 1.4 Mbit/s.WSP algorithm makes routing decisions firstly based on the hop count which at the beginning of the simulation resulted in choosing Path 2 because its AB is higher than that of Path 3 which has the same hop count. The algorithm uses the higher hop count paths when the AB of the lower hop count paths is insufficient to the flows’ requirements. The selection of the paths of the flows is depicted in Table4 in the same manner as Table 3.Table 4
The path selection and the available bandwidth of the paths using WSP.
Traffic flow
Path number
AB
Path
1
AB
Path
2
AB
Path
3
AB
Path
4
[Mbit/s]
[Mbit/s]
[Mbit/s]
[Mbit/s]
Web1
2
3
2
2
4
Video1
3
3
1
2
4
Voice1
2
3
1
0.5
4
Web2
1
3
0.4
0.5
4
Video2
1
2
0.4
0.5
4
Voice2
4
0.5
0.4
0.5
4
Web3
4
0.5
0.4
0.5
3.4
Video3
4
0.5
0.4
0.5
2.4
Voice3
4
0.5
0.4
0.5
0.9Implementing WSP resulted in a lossless transmission of all the flows. Note that Path 4 which has the highest AB is used after all the other paths are unable to fulfil the flows’ requirements.FCBA does not make two-step decisions as SWP and WSP but tries to find a path which has the best combined characteristics and consequently the best costcostp. Figure 7 shows the ap values of the paths; you can see that they range from 0.2 for Path 9 to 0.8 for Paths 2 and 3. Note that bp and cp values change rapidly over time so we do not include simplified figures. Also note that hmax⁡ from (4) is equal to 5 hops and bmax⁡ from (5) is equal to 4 Mbit/s.Figure 7
The values ofhp of the paths in the simulation scenario.The aim of the algorithm is to make the routing decision based on the classes’ preferences, so with the same computedap, bp, and cp values the path selection differs with regard to the traffic class.For example, when the simulation starts,costp for every class is different resulting in various possible path selections (see Table 5).Table 5
The values ofcostp at the beginning of the simulation.
Path
cost
p
cost
p
cost
p
(Web)
(Video)
(Voice)
Path 1
0.637
0.588
0.569
Path 2
0.6
0.575
0.613
Path 3
0.6
0.575
0.613
Path 4
0.675
0.6
0.525
Path 5
0.55
0.475
0.463
Path 6
0.55
0.475
0.463
Path 7
0.55
0.475
0.463
Path 8
0.575
0.525
0.537
Path 9
0.525
0.425
0.388
Path 10
0.575
0.525
0.537
Path 11
0.575
0.525
0.537
Path 12
0.613
0.537
0.494As you can see before the arrival of the first flow Path 2 is the most suitable for the voice traffic but for the video and web traffic the most suitable path is Path 4 and so it is selected for the first flow Web1. Selecting this path results in lowering thebp and cp values not just for Path 4 but also for Paths 9, 10, 11, and 12. The further path selection with the actual costp values of the actually arriving traffic class is shown in Table 6.Table 6
The path selection and the actualcp values of the currently arriving flows using FCBA.
Traffic
Path
Cost
Cost
Cost
Cost
Cost
flow
number
Path 1
Path 2
Path 3
Path 4
Path 5
Web1
4
0.637
0.6
0.6
0.675
0.613
Video1
1
0.588
0.575
0.575
0.537
0.537
Voice1
2
0.271
0.363
0.363
0.244
0.244
Web2
5
0.17
0.188
0.225
0.237
0.238
Video2
3
0.246
0.287
0.325
0.289
0.287
Voice2
2
0.273
0.344
0.315
0.227
0.212
Web3
4
0.166
0.15
0.133
0.178
0.174
Video3
1
0.246
0.25*
0.229
0.35*
0.287*
Voice3
2
0.225
0.325
0.315
0.275
0.244Note that when the Video3 flow arrives Path 1 is chosen although it has only the fourth highestcostp value but the other paths with higher costp value (marked with “*” in Table 6) are unable to fulfil the bandwidth requirement of the Video3 flow. FCBA enables the delay intolerant voice traffic to use the shortest paths and utilizes the longer paths with the delay tolerant web traffic.We compare the three CBR algorithms based on the achieved QoS parameters delay, jitter, and loss rate. Regarding the loss rate, only SWP caused the traffic loss when the Video3 flow was unable to find a path with sufficient resources resulting in 13.8% loss rate of this flow which consequentially resulted in a lower packet delivery ratio compared to WSP and FCBA which is depicted in Table7.Table 7
Packer delivery ratio (PDR) comparison.
CBR algorithm
PDR [%]
SWP
97.07
WSP
100
FCBA
100This had also a big impact on average jitter value of the video traffic. FCBA was able to achieve the best results regarding the delay and jitter values of the delay intolerant voice traffic. See Figures8 and 9 for the achieved average delay and jitter values of the particular traffic classes with various CBR algorithms implemented. Table 8 then provides a comparison of maximum achieved delay and jitter values of each algorithm.Table 8
Maximum delay and jitter comparison.
CBR algorithm
Max. delay [ms]
Max. jitter [ms]
WSP
69.63
27.62
SWP
68.51
24.22
FCBA
67.63
11.76Figure 8
Average delay values of the traffic classes.Figure 9
Average jitter values of the traffic classes.


## 7. Conclusion

We proposed a new CBR algorithm called FCBA based on fuzzy logic which does not discard a path based on one metric although it can be optimal based on another metric as it is done with SWP and WSP algorithms. We introduced the metric weights which aim to fulfil various needs of the traffic classes. We implemented our approach in NS-2 and by performing multiple simulations we were able to observe that FCBA achieved the best average delay value for delay intolerant voice traffic which achieved average delay of 41.85 ms compared to 56.72 ms achieved by WSP and SWP’s 62.60 ms. The best performance was also achieved regarding jitter values where FCBA achieved 0.374 ms jitter compared to 15.73 ms and 3.98 ms achieved by WSP and SWP, respectively. The reason for such results lies in the fact that the voice traffic was routed through the shortest paths and FCBA was able to utilize the longer paths with the delay tolerant web traffic. But because three constraints are used the voice traffic does not use those short paths that are overutilized and uses those that can accommodate the incoming flow. We believe that MPLS-TE network can benefit from such approach because the overall utilization is more or less equally divided between the paths and the class-based metric weights ensure the required treatment of the various traffic classes.



---

*Source: 237810-2014-12-18.xml*