idnits 2.17.1 draft-kapoor-rtgwg-dynamic-multipath-routing-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 201 has weird spacing: '...OR each commo...' == Line 250 has weird spacing: '...R {each commo...' -- The document date (September 12, 2017) is 2418 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? 'M75' on line 386 looks like a reference -- Missing reference section? 'CRS99' on line 359 looks like a reference -- Missing reference section? 'ST92' on line 406 looks like a reference -- Missing reference section? 'DSAK11' on line 363 looks like a reference -- Missing reference section? 'SKDA13' on line 402 looks like a reference -- Missing reference section? 'PU12' on line 388 looks like a reference -- Missing reference section? 'RG10' on line 394 looks like a reference -- Missing reference section? 'GWH11' on line 367 looks like a reference -- Missing reference section? 'RH10' on line 398 looks like a reference -- Missing reference section? 'AP13' on line 354 looks like a reference -- Missing reference section? 'M05' on line 372 looks like a reference -- Missing reference section? 'M06' on line 376 looks like a reference -- Missing reference section? 'M07' on line 379 looks like a reference -- Missing reference section? 'M08' on line 383 looks like a reference -- Missing reference section? '0' on line 126 looks like a reference -- Missing reference section? '1' on line 412 looks like a reference Summary: 3 errors (**), 0 flaws (~~), 5 warnings (==), 17 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group F. Devetak 3 Internet-Draft S. Kapoor 4 Expires: March 16, 2018 Illinois Institute of Technology 5 September 12, 2017 7 Dynamic MultiPath Routing 8 draft-kapoor-rtgwg-dynamic-multipath-routing-01 10 Abstract 12 In this draft we consider dynamic multipath routing and introduce two 13 methods that use additive increase and multiplicative decrease for 14 flow control, similar to TCP. Our first method allows for congestion 15 control and re-routing flows as users join in or leave the network. 16 As the number of applications and services supported by the Internet 17 grows, bandwidth requirements increase dramatically so it is 18 imperative to design methods to ensure not only that network 19 throughput is maximized but also to ensure a level of fairness in 20 network resource allocation. Our second method provides fairness 21 over multiple streams of traffic. We drive the multiplicative 22 decrease part of the algorithm with link queue occupancy data 23 provided by an enhanced routing protocol. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on March 16, 2018. 42 Copyright Notice 44 Copyright (c) 2017 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (https://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 1. Introduction 59 Internet packet traffic keeps growing as the number of applications 60 and services it supports as well as their bandwidth requirements 61 explode. It has then become necessary to find ways to ensure that 62 network throughput is maximized. In this draft we propose dynamic 63 multi-path routing to improve network throughput. 65 Multipath routing is important, not only for throughput but also for 66 reliability and security. In multipath routing, improvements in 67 performance are achieved by utilizing more than one feasible path 68 [M75]. This approach to routing makes for more effective network 69 resource utilization. Various research on multipath routing have 70 addressed network redundancy, congestion, and QoS issues [CRS99] 71 [ST92]. Prior work on multipath routing includes work on bounding 72 delays as well as delay variance [DSAK11] [SKDA13]. 74 The prior work is primarily from the viewpoint of static network 75 design but, in practice, congestion control is necessary to prevent 76 some user flows from being choked due to link bottlenecks. Single 77 path routing implementations of TCP achieve that by rate control on 78 specified paths. TCP is able to handle elastic traffic from 79 applications and establishes a degree of fairness by reducing the 80 rate of transmission rapidly upon detecting congestion. Regular TCP 81 has been shown to provide Pareto-optimal allocation of resources 82 [PU12]. However, unlike the single path approach of TCP, we consider 83 multipath routing with associated issues of path selection and 84 congestion. We may note that multipath TCP (MPTCP) has been studied 85 extensively [RG10] [GWH11] [RH10] [AP13] with a number of IETF 86 proposals [M05] [M06] [M07] [M08]. Prior work on multipath TCP is 87 defined over a specific set of paths and the choice of paths or the 88 routing is independent of congestion control; determining the right 89 number of paths thus becomes a problem. The variation of throughput 90 with the number of paths has been illustrated in [RG10] [GWH11] 92 Along with consideration of congestion, we also need to ensure a 93 level of fairness in network resource allocation. Factoring fairness 94 into the protocol is important in order to prevent some user's flows 95 from suffering due to bottlenecks in some links. Based on 96 mathematical optimization formulations, we consider route 97 determination methods that ensure fairness where all users can 98 achieve at least a minimum percentage of their demand. We introduce 99 an algorithm that uses additive increase and multiplicative decrease 100 for flow control and we have experiments to illustrate its stability 101 and convergence. The algorithm may be considered as a generalization 102 of TCP. 104 We have performed an extensive set of simulations using the NS-3 105 simulation environment. In our implementation we drive the 106 multiplicative decrease part of the algorithm using queue occupancy 107 data at each outgoing network link, with that data provided by an 108 enhanced routing protocol. For a more in-depth evaluation of the 109 algorithm's performance we simulated not only the fairness algorithm 110 but also a version of the same without the fairness component. We 111 also performed and compared simulations using standard TCP and TCP 112 with ECMP enabled. 114 2. Joint Routing and Congestion Control: Preliminaries 116 The Joint Routing and Congestion Control utilizes the Link State of 117 the network. The algorithm utilizes a price variable that models 118 congestion at each link and a variable that models the fairness 119 coefficient. The fairness coefficient is used to establish the same 120 percentage of traffic is being routed for multiple source-sink pairs. 122 2.1. The Price function 124 Each edge of the network has a price function associated with it, 125 referred to as P(e). The price function measures the congestion on 126 the link. The price function lies in the interval [0,1] and is 0 if 127 the edge occupancy is low and 1 if the edge occupancy is high. 129 In theory the edge occupancy is given by f(e)/C(e) where f(e) is the 130 amount of traffic on the link and C(e) is the capacity of the link. 131 In practice, the edge occupancy is measured by the congestion in the 132 queue serving the link. 134 The price function increases as the congestion grows. This 135 function's values will be referred to by a price variable on link e 136 which is denoted by PBQ(e) 138 2.2. The Fairness function 140 The price function is complemented by an "increase" function, i.e. a 141 variable that regulates the amount of traffic changes based on the 142 fraction of traffic of the commodity that has been routed. This 143 function, th values represented by the variable PBF(s-t), is used to 144 model the fairness. This variable is related to the source- 145 destination pair, denoted by s-t, whose requirements are being 146 satisfied. 148 The variable PBF(s-t) starts with an initial value and goes down to 149 zero as the requirement of s-t is being increasingly met. The 150 increase in PBF is dictated by a fairness co-efficient, Gamma. 152 The formula for PBF(s-t) is 1- y(s-t)/[Gamma *d(s-t)] where Gamma is 153 the fairness co-efficient, d(s-t) is the demand and y(s-t) is the 154 amount of requirement that is being met. 156 3. Joint Routing and Congestion Control: Algorithm 158 We present the details of the algorithms below 160 3.1. Preliminaries 162 Let T be the time interval used to increment or modify routing. 164 We use two coefficients for each path Pi 166 1. Additive increase coefficient: A positive value ai by which we 167 increment the flow on a path at each iteration xi(t) = xi(t-T ) + 168 ai 170 2. Multiplicative decrease coefficient: The coefficient bi that we 171 apply to decrement flows: xi(t) = (1-bi)xi(t-T ) where x, t, T 172 are the same as above. 174 We utilize multiple methods for calculating bi: 176 METHOD 1: bi may be computed as follows: 178 1. bi =0 if no edge on the path Pi is congested. 180 2. bi =0.5 if one edge on the path Pi is congested. 182 3. bi= 1.0 if more than one edge on the path Pi is congested 184 METHOD 2: bi may be computed as follows: 186 1. bi = 1-1/2^c where c is the number of congested edges. 188 3.2. The Basic Multi-path Algorithm 190 We propose two routing mechanisms. The first, presented here,is a 191 basic mechanism that is primarily based on multiplicative decrease 192 and additive increase 193 In the first routing method, for each commodity c, let P(c) be the 194 set of paths being used. If any of the paths Pi is congested, the 195 flow on the path is reduced using the multiplier (1-bi). Next, the 196 shortest path is found to push additional flow requirements if they 197 exist. An additive flow of value ai, which is chosen to be a 198 constant independent of i, is pushed on that path. 200 At the end of each time interval T 201 FOR each commodity c: 202 Calculate commodity flow 203 FOR each flow path, i, of commodity c 204 Calculate bi 205 IF {demand is met and bi = 0} 206 No change in path flow 207 ELSE 208 Apply coefficient bi to 209 decrease path flow 210 ENDIF 211 ENDFOR 212 IF {demand not met} 213 Find shortest path for commodity c 214 IF{shortest Path is new} 215 Add new path to list 216 ENDIF 217 Increment shortest path flow by a 218 ENDIF 219 ENDFOR 221 If the number of paths used is excessive then no new paths need be 222 generated. 224 3.3. The Multi-path Algorithm with Fairness 226 In order to ensure that different source-sink pairs are treated 227 fairly, the coefficient bi for path Pi is chosen as PBQ - PBF with 228 two components: a congestion component PBQ and a fairness component 229 PBF . 231 1. PBQ is calculated as bi before; 233 2. PBF is calculated using the formula PBF(s-t) = 234 1-Total_current_FLOW(S-t)/(Gamma* Demand(s-t)) 236 where Gamma is the fairness parameter and DEMAND(s-t) is the demand. 238 In the second routing method, again, for each commodity c, let P(c) 239 be the set of paths being used. If any of the paths is congested, 240 the flow on the path Pi is reduced using the multiplier (1-bi). The 241 key difference is in the computation of bi. bi is not uniform across 242 various user requests but is dependent on the fraction of flow of 243 that commodity that is already being serviced by the network. Having 244 reduced congestion, if it exists, a shortest path is found to push 245 additional flow requirements if they exist. Again an additive flow 246 of value ai, which in our current implementation is chosen to be a 247 constant independent of i, is pushed on that path. 249 At the end of each time interval T 250 FOR {each commodity} 251 Calculate commodity c flow 252 FOR {each path i} 253 Calculate PBQ and PBF 254 IF {demand is met} 255 IF {NO Congestion} 256 No change in path flow 257 ELSE 258 bi = max (0, PBQ-PBF) 259 flow on path i, 260 xi(t) = (1-bi)*xi(t-T)) 261 ENDIF 262 ELSE 263 IF {NO Congestion} 264 bi = -PBF 265 ELSE 266 bi = max (0, PBQ-PBF) 267 ENDIF 268 xi(t) = a + (1-bi)*xi(t-T)) 269 ENDIF 270 ENDFOR 271 Recalculate Commodity flow 272 IF {flow change in any path AND demand not met} 273 Find shortest path 274 IF {shortest path is new} 275 Add new path to list 276 ENDIF 277 Increment shortest path flow by a 278 ENDIF 279 ENDFOR 281 If the number of paths become excessive then they can be curtailed. 282 At that stage no additional flow is pushed until congestion is 283 relieved. 285 4. Experiments 287 We implemented [1] the two algorithms using the NS-3 simulation 288 environment. We modeled the network topology on the network of a 289 large service provider, with link capacities proportional to 290 capacities in the actual physical network. In our implementation we 291 used, for routing, a combination of link-state routing protocol and 292 source routing. For the link-state part we augmented the NS-3 293 implementation of the OSPF routing protocol by adding link queue 294 occupancy to the data exchanged by nodes in Link State Advertisement 295 (LSA) messages, a minimal increase in LSA data. That allows for more 296 sophisticated monitoring of network status: if the queue occupancy 297 for one of more links of a path exceeds a given threshold we conclude 298 that the path is experiencing congestion and that the multiplicative 299 decrease has to be applied to adjust the allocation of flow to the 300 paths. The additive increase is applied at each iteration, if demand 301 is not met, to augment the sending rate. Details of congestion 302 measurement are as follows: In a node-to-node connection (data link) 303 both the source (originating) node and the sink (destination) node 304 have a PointToPointNetDevice. The PointToPointNetDevice at the 305 originating node is associated with a queue function of type 306 DropTailQueue. The queue function stores the number of packets in 307 the queue (waiting to be sent to the destination node). A 308 queueOccupancy parameter is calculated: numPacketsInQueue/ 309 queueMaxSize and compared to a queueThreshold parameter. If 310 queueOccupancy> queueThreshold the path that uses the data link is 311 flagged as congested. queueThreshold is an input parameter declared 312 at the start of the simulation. At the same time path delay is also 313 calculated. The source node uses OSPF to find the shortest path to 314 the destination and, based on available network data, builds a 315 source-routing vector that is inserted in the packet and used by 316 intermediate nodes to route the packet to the destination. To 317 implement the source-routing function we augmented the NS-3 Nix- 318 Vector protocol that builds the source-routing vector from the list 319 of nodes to be traversed, list that is obtained from OSPF. The main 320 process is iterative as we refresh LSA at a fixed interval: for our 321 simulations we experimented with updating LSAs every 50 ms and 500 322 ms. 324 Our results for the throughput improvement are presented below and 325 compared with throughput results for the standard TCP and TCP using 326 ECMP. We show the average throughput over multiple runs. 328 |------------------------------------------------------------| 329 |No of Commodities | TCP | TCPw ECMP | DMP |DMP/Fairness| 330 |------------------------------------------------------------| 331 | 5 | 4008 | 3330 | 7949 | 4139 | 332 |------------------------------------------------------------| 333 | 10 | 3275 | 2966 | 6017 | 5612 | 334 |------------------------------------------------------------| 335 | 15 | 2849 | 2715 | 5373 | 5090 | 336 |------------------------------------------------------------| 337 | 20 | 2912 | 2582 | 4633 | 3703 | 338 |------------------------------------------------------------| 340 5. Conclusion 342 In conclusion we found that our algorithm with fairness provides 343 throughput improvement over both regular TCP and TCP with ECMP. In 344 addition, its ability to discover additional path dynamically 345 eliminates the need to set a preselected set of paths, allowing the 346 spreading of the traffic load amongst a wider but still reasonable 347 set of paths. Further results may be found at 348 www.cs.iit.edu/~kapoor/papers/reducerate.pdf . 350 6. References 352 6.1. References 354 [AP13] Amer, P. and F. Pang, "Non-renegable selective 355 acknowledgments (nr-sacks) for mptcp.", Proceedings of the 356 2013 27th International Conference on Advanced Information 357 Networking and Applications Workshops , 2013. 359 [CRS99] Cidon, I., Rom, R., and Y. Shavitt, "Analysis of multi- 360 path routing", IEEE/ACM Trans on Networking pages 885-896, 361 1999. 363 [DSAK11] Devetak, F., Shin, J., Anjali, T., and S. Kapoor, 364 "Minimizing path delay in multipath networks", IEEE ICC, 365 2011. 367 [GWH11] Greenhalgh, A., Wischik, D., Handley, M., and C. Raiciu, 368 "Design, implementation and evaluation of congestion 369 control for multipath tcp.", 8th USENIX conference on 370 Networked systems design and implementation , 2011. 372 [M05] Internet Engineering Task Force, "Coupled congestion 373 control for multipath transport protocols", RFC 6356 , 374 2011. 376 [M06] Internet Engineering Task Force, "Multipath tcp (mptcp) 377 application interface considerations", RFC 6897 , 2013. 379 [M07] Internet Engineering Task Force, "Tcp extensions for 380 multipath operation with multiple addresses", RFC 6824 , 381 2013. 383 [M08] Internet Engineering Task Force, "Architectural guidelines 384 for multipath tcp development", RFC 6182 , 2011. 386 [M75] Maxemchuk, N., "Dispersity Routing", IEEE ICC, 1975. 388 [PU12] Popovic, M., Upadhyay, U., Le Boudec, J., Khalili, R., and 389 N. Gast, "Mptcp is not pareto-optimal: performance issues 390 and a possible solution", Proceedings of the 8th 391 international conference on Emerging networking 392 experiments and technologies , 2012. 394 [RG10] Barre, S., Greenhalgh, A., Wischik, D., Handley, M., 395 Raiciu, C., and C. Pluntke, "Data center networking with 396 multipath tcp.", 9th ACM SIGCOMM , 2010. 398 [RH10] Raiciu, C., Handley, M., Barre, S., and O. Bonaventure, 399 "Experimenting with multipath tcp.", Proceedings of the 400 ACM SIGCOMM 2010 conference , 2010. 402 [SKDA13] Devetak, F., Anjali, T., Shin, J., and S. Kapoor, 403 "Concurrent multipath routing over bounded paths: 404 Minimizing delay variance", Globecom 2013 , 2013. 406 [ST92] Suzuki, H. and F. Tobagi, "Fast bandwidth reservation with 407 multiline and multipath routing in atm networks", 408 Proceedings of IEEE Infocom pages 2233-2240, 1992. 410 6.2. URIs 412 [1] http:www.cs.iit.edu/~kapoor/papers/reducerate.pdf 414 Authors' Addresses 416 Fabrizio Devetak 417 Illinois Institute of Technology 418 10W 31 Street 419 Stuart Building 420 Chicago, IL 60565 421 US 422 Sanjiv Kapoor 423 Illinois Institute of Technology 424 10W 31 Street 425 Stuart Building 426 Chicago, IL 60565 427 US 429 Phone: +1 312 567 5329 430 Email: kapoor@iit.edu 431 URI: http:www.cs.iit.edu/~kapoor