Congestion aware multipath routing: performance improvements in core networks

INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER Congestion Aware Multipath Routing: Performance Improvements in Core Networks Matej KULTAN, Martin MEDVECKY Institute of Telecommunications, Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava, Ilkovicova 3, 812 19 Bratislava, Slovakia [email protected], medvec[email protected] DOI: 10.15598/aeee.v13i5.1449 Abstract. In this paper the improved Congestion Aware Multipath Routing algorithm is analysed in terms of Core network throughput and longer paths contribution. The algorithm discovers unused network resources and dynamically adapts to the actual traffic load and available resources displacement. Several simulation scenarios have been benchmarked in order to verify algorithm in typical Internet Service Provider cases. Simulation scenarios in this paper are focused on verifying functionality in dense core networks. For this purpose, tests were performed on TeraStream based network – the Deutsche Telekom Group design concept. Simulation results have proven better performance and resource utilization of the proposed algorithm than traditional Bellman-Ford based algorithms and equal cost multipath approaches. Keywords Congestion, load-balancing, multipath, throughput. 1. Introduction Currently, the Internet Service Provider (ISP) transport network is designed as a completely independent system, providing autonomous operations such as path discovery, routing and basic statistic load-balancing with OSPF and ISIS, ECMP, LAG protocols [1]. Thus, each node in the network is responsible for the local service operation. The disadvantage of this approach is missing resource utilization strategy and overall network visibility in terms of congestion and traffic loadbalancing. Here is where software defined networking (SDN) approach for traffic steering comes into place. Network operators can flexibly split arbitrary flows to outgoing links through the deployment of the SDN via hybrid controlled network [2]. This brings a completely autonomous operation for the whole network and gives options for network operators to handle critical or specific flows. Additionally the new network architectures [3] are showing up due to mass virtualization and data demand growth. Specially, all mass services become datacentre-oriented, distributed in content delivery networks or using mass peer-to-peer communication [4] demanding higher bandwidth. To address new trends in future Internet, the improved Congestion Aware Multipath Routing (CAMRv2) approach provides new options for network optimization. The new approach benefits in terms of higher throughput for any flow in the network, link stabilization, efficient usage of resources and thus overall cost efficiency. The new algorithm runs in parallel with existing Internet Protocol IPv4/IPv6 and multiprotocol label switching (MPLS). Furthermore, due to control and data plane separation CAMRv2 is designed to be integrated as SDN distributed [5], centralized or standalone network level application. The CAMRv2 is providing optimal path set selection, relying on link load and topology knowledge, thus able to react more efficiently in dynamically changing environment. The selection based on knowledge instead of estimation provides higher routing performance, far behind selecting normally, statistically optimal paths. In this paper, the algorithm performance was analysed in dense core networks. The second part analyses stability factor impact on the long paths activation time. The results were compared to equal cost shortest multipath routing approach. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 508 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER 2. CAMRv2 Design Basic Principles The new CAMRv2 algorithm (Fig. 1) is based on 5 principal phases, identical for all PE (Provider Edge) nodes: •Source/Destination selection. •Path and flow search. •Metric calculation. •Metric to interval calculation. •Encapsulation and proportional data distribution. All mentioned phases are independent in terms of computing and they run in parallel. In the control plane, the Source/Destination selection phase is triggered by timer and topology update event. While the Path set and flow search phase is triggered by Link-State congestion vector arrivals. According to the found Path Sets for individual destinations, metric calculations and interval assignments are done in highly parallelized environment due to extensive Routing Information Base and Forwarding Information Base sizes. 2.1. Source/Destination Selection The source and destination selection is a phase when control plane takes care about prioritizing path calculation in the destination queues for highly loaded destinations. The computation frequency is linearly proportional to the volume of destination traffic in the past intervals. Thus the probability of high loads balancing in time increases and provides the algorithm higher efficiency and overall performance. 2.2. Path and Flow Search Improvements CAMRv2 algorithm (Alg. 1) searches for all paths p, from oriented graph G(V, E)- between nodes sand t and finds free capacity cfor the flow fi in order to maximize the flow f. Every algorithm iteration, the overall residual capacity Gfi is decreasing, until there is no path pibetween s and t. Then f(s, t)represents the maximum flow possible found by the algorithm. The path and flow search phase is derived from Breadth-First Search/Edmonds-Karp algorithm adapted for CAMRv2 purposes. For lowering the calculation complexity O(VE2)of the original CAMR algorithm [6], several conditions and mechanisms were applied. The first improvement (Eq. (1)) is the algorithm interruption condition, when the found paths capacity for the destination is exceeding the expected load with sufficient load margin B, distributed over a sufficient number of found paths M. This improvement aims to lower processing overhead for less significant traffic loads. The distribution is fine for higher loaded destinations, the very low destinations will use best-effort balancing, while (M≥ |p|)∧(B≥f).(1) Algorithm 1 Improved CAMRv2 Path Search. Require: Capacity matrix c, nodes s, t, parameters M, B, N Ensure: Path set p, Path flow capacities cf 1: ∀V, E : 0 →f(u, v) 2: If ∃pi(s, t)∈Gf,where cf(u, v)>0∧((M≥ |p|)∧(B≥f))∨(pi< N +p1) for ∀(u, v)∈pithen: 3: Find cfi(p)= min{cfi(u, v):(u, v)∈p} 4: Q={s}#Qis FIFO buffer 5: For every node w∈V 6: n(w)=0;where nrepresents visited node binary value 7: d(w) = ∞;where d(w)is the distance from s 8: pd(w)=null# where pd(w)is predecessor of w 9: n(s)=0 10: d(s) = 0 11: DQ ={s} 12: while (Q6=∅): 13: u,where pd(u) ∈DQ, Q =Q−u 14: for every link (u, v)∈E: 15: if (n(v)6= 0) 16: n(v)=1 17: d(v) = d(u)+1 18: Q=Q+v 19: if v=t, then cfi(pi) = min {cfi(s, t):(s, t)∈pi} 20: for ∀(u, v)∈p: 21: f(u, v)←f(u, v) + cfi(pi) 22: Gfi+1 ←Gfi −cfi(pi) The secondary interruption condition (Eq. (2)) is based on rule of using only the shortest path set and neglecting very long paths. In the 3rd and 4th algorithm phases, the stability factor exponentially suppresses load for paths with much higher hop count than the shortest path. Thus it is desirable to interrupt the max-flow algorithm to avoid costly long path set calculations if long paths would not be used due to the stability factor in next steps. while (|pi|< N +|p1|).(2) c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 509 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER Fig. 1: CAMRv2 protocol (CAMPv2) based IP/MPLS router architecture. 2.3. Metric Calculation In the third round the metric (Eq. (3)) is generated for each path in the path set. The unique approach of CAMRv2 algorithm is the 2nd round of benefiting the shortest path set selection and flow distribution by distance. For this purpose the compound CAMRv2 metric sfreflects the proportion of data sent over a specific path: ρ(pi) = cfief d(ti)sf,(3) where sf∈<0,∞),ef∈<0,1). The metric ρ(pi)is dependent on the path capacity cfi, its length d(ti)in terms of the number of hops, the network stability sfand exponential factor ef: •The d(ti)represents an integer value in terms of hops between the inspected tunnel ti. •The cfi is representing path capacity derived from the minimal link bandwidth over the selected path. The bandwidth is considered as a mean value from the last time the measurement was performed. The sampling period in simulations below are 14 seconds long. •The efprovides continuous flow redistribution for smoother convergence to the balanced state and flow flapping avoidance between paths. The ef out of specified range causes high-instability. •The sfsuppresses distribution over the longer path in favor of the shortest path. Selecting longer paths increases the overall throughput, but on the other hand, the load generated in network by selecting too long paths may inefficiently congest the network. 2.4. Metric to Interval Calculation The metric has only local significance and it is used as a proportional value to calculate intervals of hashfunction. The path piproportion of forwarded data is represented by the αiwidth of interval Hi. The interval Hibelongs to specific path piand it is dependent from ρ(pi)metric proportion to overall metric for destination t: if δi=ρ(pi) Piρ(pi),0then α1=δi 2m,(4) where m= 16, H1<1, δi),for i > 1 : Hi(δi−1, δi−1+δi).(5) The implementation of such packet assignment into specific path is done by packet header processing with hash function. The CRC-16 hash function allows high granularity and low complexity labelling for each packet. In expected traffic load level of 100 Gb ·s−1, the assignment brings 1.53 Mb ·s−1step granularity. Using Hash functions on subscriber packet header maintains high probability of the subscriber flow to be assigned to the same path. 2.5. Flow Classification and Encapsulation The last phase is performed completely in the data plane. As CAMRv2 can be implemented in parallel with existing infrastructure and services, it is upon ISP its deployment model. The CAMRv2 routing can be applied on network, access or hybrid interface mode. In case of access mode by implementing Service Access Point (SAP) approach [7], only limited set of traffic is processed by CAMRv2. The SAP selects incoming traffic by specific rule, for example: •Incoming physical interface, e.g. port 1/1/2. •Incoming VLAN Id e.g. 1/1/2:210. •Incoming Source/Destination prefix. •Filter L2/L3/L4 combined filtering. The access mode SAP can further provide accounting and statistics per flow and customer. The network mode is applied on the node for only enabling the source routing packets to be processed by c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 510 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER the node. The network and hybrid modes allow to interface inspect Routing Header Extension and forward source routed packets to the next destination. When hybrid mode is applied, the node is forwarding source routing based packets. If no Extension Header is found on incoming packet, the appropriate source routing encapsulation will be applied. 3. Core Network Scenarios To verify CAMRv2 as a stable algorithm ready for real ISP network integration, the case on 2-layer TeraStream concept was analysed [8]. In the network concept, the first layer consists of all-meshed 100GE interconnected routers R2. The second layer consists of 100GE interconnected aggregation nodes via redundant horseshoe topology. To fulfil high density interconnection demand, there is no need for optical fiber installation between each particular router. Dense Wavelength Division Multiplexing (DWDM) optical layer provides the interconnectivity with dedicated wavelengths and OTU4 framing between nodes. In the TeraStream network, the new algorithm shall provide two main advantages: •Firstly, it allows the aggregation links loadbalancing, even not all destinations have equal cost shortest paths. •Secondly, it provides much higher bandwidth for any flow in the network than traditional equal and unequal cost shortest path algorithms. The scope of this paper is to prove higher bandwidth and analyse stability factor influence on long path activation into forwarding. Following scenarios have tested the network performance without and with additional traffic. For illustration, let’s consider the TeraStream topology with 6x core R2 nodes (nodes 1–6) and 15x aggregation equally distributed R1 nodes (nodes 7–21) in horseshoe topology. Furthermore, the direct link between the source and destination has been broken, to benefit equal cost shortest multipath approach in benchmarking (Fig. 2) 3.1. Simulation Scenario 1: CAMRv2 Flow Distribution Unloaded Core This simulation verifies the maximum achievable bandwidth in the unloaded network between core routers. In the first phase CAMRv2 has found 9 tunnels with equal capacity (1=100 Gb ·s−1) between nodes R2 (1) R1: Aggregation nodes R2: Core nodesR2: Core nodes Flow Path - 3 hops Path - 5 hops Broken link Core link Agrr. link Fig. 2: TeraStream Network topology under the test. and R2 (6). If the sf= 0, all 9 paths regardless of the length will be loaded equally as all paths will get equal metric 1 (Fig. 3). The total traffic over all 9 independent paths will allow up to theoretical 9 ×10 Gb ·s−1. Equal cost multipath SPF approach in such case would provide only 5 ×100 Gb ·s−1over the shortest path (tunnels 2–6). Fig. 3: Scenario 1: Path Load ratio dependency from Stability factor; s=1, t=6. By increasing the sf, the node will prefer shorter paths, and the overall possible traffic will decrease to the SPF capacity (sf=5, max-flow=5.31). By this observation we can assume that the network provides maximum capacity when sf=0. This scenario is synthetic as normally the network is loaded from various sources and destinations. The number of discovered paths in unloaded scenario is often lower than in case a load in network is present. This phenomenon consists in minimum available capacity common for all paths, setting the metric equal for all paths. In loaded cases, one link with lower capacity is blocking lower the path capacity, leaving options for alternative paths. Although the number of paths in the unloaded scenario is lower, the overall throughput is still at maximum flow possible. The aim of this scenario is to visualize algorithm in limit situations. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 511 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER 3.2. Simulation Scenario 2: CAMRv2 Flow Distribution Loaded Core The next simulation reveals the CAMRv2 sfcontrol strength in terms of flow distribution control. In this simulation we are introducing load into the network according the TeraStream concept. The generated network load is set to 20 %. For the same topology, CAMRv2 have found now 15 paths, with free network capacities in longer paths. New longer paths 6–9 and 14–15 were found due to the unequally spread load in the network. As seen, depending on sfCAMRv2 can benefit from higher throughput of new discovered paths, if network remains stable sf<2, or completely turn into short path balanced routing sf>4in unstable or heavy loaded network. High sfalmost completely suppress long paths in order to prevent path frequent flapping. Paths 6–9 and 14–15 are available with very low throughput. If only standard metric would be used and Unequal Cost Multipath approach activated, it is very probable that these paths would be congested as SPF and Unequal Cost Multipath Load-balancing (UCMP) do not take into consideration path link availability. CAMRv2 will suppress these paths because of the present congestion knowledge (Fig. 4). Fig. 4: Scenario 2, flow load ratio between available paths. Tab. 2: Scenario 2: Flow redistribution into loaded network. 3.3. Simulation Scenario 3: Stability Factor vs. Offloading Last simulations introduce sfcontrol feature in terms of longer paths activation. In this simulation we are introducing continuously rising load between core nodes 1–6 until CAMRv2 routing suffers traffic drop. Firstly, the SPF approach will be useful only up to the shortest path capacity – 100 Gb ·s−1. The Equal Cost Multipath Load-balancing (ECMP) approach will congest links at the maximum load 5 ×100 Gb ·s−1due to 5 available paths. CAMRv2, due to suppression factor equals 0 as expected, the load on shorter and longer paths is maintaining the same level, until reaching the full capacity. The red line and green are overlapping. In this case the full capacity reached is 781 Gb ·s−1 (Fig. 5). Increasing the stability factor, the maximum bandwidth suffering continuously increased load doesn’t change before sf<2(Fig. 6). Although the load distribution over the time is different, the maximum bandwidth remains 781 Gb ·s−1. The load is sent over shorter paths with higher priority. While the congestion on the main link is increasing, longer paths maintain offloading significantly the shorter path. Tab. 1: Scenario 1: Path metric, Link Load dependency from Stability factor. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 512 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER Fig. 5: R2 Core node 1: link load with Stability factor = 0. Fig. 6: R2 Core node 1: link load with Stability factor = 1. Considering the scenario with sf= 5, it can be observed that the contribution of shorter paths into the overall capacity is more significant. Such high stability factor doesn’t provide the best performance in terms of overall throughput - 725 Gb ·s−1, but maintains high stability by using longer paths only during critical shortest path congestion levels. Fig. 7: R2 Core node 1: link load with Stability factor = 5. Considering the scenario where sf= 10. This approach is activating secondary paths only when shortest paths come to the congestion level of 80 % (Step 400, Fig. 8). Afterwards longer paths start to be active and try to compensate high load. Considering the maximum throughput of SPF/ECMP approach is 5, CAMRv2 gave to the flow another 20 % of throughput, but only in the case of limit load. In the last scenario where sf= 20 (Fig. 9) is too high the routing completely ignores longer paths. It can be observed that the system completely behaves as SPF/ECMP scenario. Longer paths would be activated only in case shorter links will fail or will be completely congested. Fig. 8: R2 Core node 1: link load with sf= 10. Fig. 9: R2 Core node 1: link load with sf= 20. The overall CAMRv2 throughput in the Core network strictly depends on stability factor (Tab. 3, Fig. 10). Simulations in this scenario were repeated with sfstep 0.5. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 513 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER Tab. 3: Throughput Stability-Suppression factor. Stability-Suppression factor 0 1 2 3 4 5 20 Throughput [×100 Gb ·s−1]7.81 7.81 7.81 7.65 7.49 7.25 5.06 Fig. 10: Throughput Stability-Suppression factor dependency. 4. Conclusion In this paper, the new Congestion Aware Multipath Routing algorithm was introduced with several improvements in terms of calculation time and overall computation complexity than original Edmonds-Karp algorithm (Section 2.2). Several simulations were performed over the TeraStream network focusing on core network throughput, load-balancing and stability factor influence. Simulation results have proved several performance and control advantages over traditional network routing approaches. An ISP operator can fully control the network by setting or limiting the stability factor value to get the desired throughput or stability control over the network. Any pair of core nodes would be able to find additional resources when bandwidth demand overcomes shortest paths capacity. It does not depend whether the network is unloaded (Section 3.1) or loaded (Section 3.2). Additionally, by setting properly the stability factor the operator can avoid packet drop or buffering. If high value is set, the offload will be activated only in critical path loads, if low value is used the offload is activated immediately (Section 3.3). The sfthroughput benchmarking allows to service provider better planning in terms of maximum achievable capacity. Acknowledgment This article was created with the support of the Ministry of Education, Science, Research and Sport of the Slovak Republic within the Research and Development Operational Programme for the projects "Centre of Excellence for SMART Technologies, System and Services II", ITMS 26240120029 and "University Science Park of STU Bratislava", ITMS 26240220084, co-funded by the European Regional Development Fund. References [1] RFC 7424. Mechanisms for Optimizing Link Aggregation Group (LAG) and Equal-Cost Multipath (ECMP) Component Link Utilization in Networks. Internet Engineering Task Force (IETF), 2015. [2] GUO, Y., Z. WANG, X. YIN, X. SHI and J. WU. Traffic Engineering in SDN/OSPF Hybrid Network. In: 22nd IEEE International Conference on Network Protocols ICNP. Raleigh: IEEE, 2014, pp. 563–568. ISBN 978-1-4799-62037. DOI: 10.1109/ICNP.2014.90. [3] CORDERO, A. and D. FERNANDEZ. Rethinking ISP architectures through virtualization. In: International Conference on Data Communication Networking. Seville: IEEE, 2011, pp. 1–4. ISBN 978-989-8425-69-0. [4] ZHANG, N., T. LEVA and H. HAMMAINEN. Value networks and two-sided markets of Internet content delivery. Special issue on: Selected papers from the 10th Conference in Telecommunications, Media and Internet Techno-economics. 2014, vol. 38, iss. 5–6, pp. 460–472. ISSN 03085961. DOI: 10.1016/j.telpol.2013.03.004. [5] RFC 7426. Software-Defined Networking (SDN): Layers and Architecture Terminology. Internet Research Task Force (IRTF), 2015. [6] KULTAN, M. and M. MEDVECKY. CAMR - Congestion Aware Multipath Routing. In: 16th International Conference on Research in Telecommunication Technology. Frymburk: Czech Technical University in Prague, 2011, pp. 24–28. ISBN 978-80-01-05540-3. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 514 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 13 |NUMBER: 5 |2015 |DECEMBER [7] WARNOCK, G. and A. NATHOO. Alcatel-Lucent Network Routing Specialist II. Hoboken: Wiley, 2011. ISBN 978-0-470-94772-2. [8] LOTHBERG, P. TeraStream - A Simplified IP Network Service Delivery Model. In: RIPE 67. Athens, 2013. About Authors Matej KULTAN was born in 1989. He earned his B.Sc., M.Sc. and Ph.D. degrees from the Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava in 2010, 2012 and 2015, respectively. At present, he is an IP Routing Pre-Sales Engineer at Alcatel-Lucent. Martin MEDVECKY was born in 1968. He earned his M.Sc. and Ph.D. degrees from the Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava in 1991 and 1998, respectively. He is currently an Associate professor at the Institute of Telecommunications, Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava. c 2015 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 515