idnits 2.17.1 draft-kapoor-rtgwg-dynamic-multipath-routing-00.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 (March 13, 2017) is 2600 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 325 looks like a reference -- Missing reference section? 'CRS99' on line 327 looks like a reference -- Missing reference section? 'ST92' on line 331 looks like a reference -- Missing reference section? 'DSAK11' on line 335 looks like a reference -- Missing reference section? 'SKDA13' on line 339 looks like a reference -- Missing reference section? 'PU12' on line 343 looks like a reference -- Missing reference section? 'RG10' on line 349 looks like a reference -- Missing reference section? 'GWH11' on line 353 looks like a reference -- Missing reference section? 'RH10' on line 358 looks like a reference -- Missing reference section? 'AP13' on line 362 looks like a reference -- Missing reference section? 'M05' on line 367 looks like a reference -- Missing reference section? 'M06' on line 371 looks like a reference -- Missing reference section? 'M07' on line 374 looks like a reference -- Missing reference section? 'M08' on line 378 looks like a reference -- Missing reference section? '0' on line 126 looks like a reference -- Missing reference section? '1' on line 384 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: September 14, 2017 Illinois Institute of Technology 5 March 13, 2017 7 Dynamic MultiPath Routing 8 draft-kapoor-rtgwg-dynamic-multipath-routing-00 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 http://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 September 14, 2017. 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 (http://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. Conclusion 287 We implemented [1] a discrete time version of the two algorithms 288 using the NS-3 simulation environment. We modeled the network 289 topology on the network of a large service provider, with link 290 capacities proportional to capacities in the actual physical network. 291 In our implementation we used, for routing, a combination of link- 292 state routing protocol and source routing. For the link-state part 293 we augmented the NS-3 implementation of the OSPF routing protocol by 294 adding link queue occupancy to the data exchanged by nodes in Link 295 State Advertisement (LSA) messages, a minimal increase in LSA data. 296 That allows for more sophisticated monitoring of network status: if 297 the queue occupancy for one of more links of a path exceeds a given 298 threshold we conclude that the path is experiencing congestion and 299 that the multiplicative decrease has to be applied to adjust the 300 allocation of flow to the paths. The additive increase is applied at 301 each iteration, if demand is not met, to augment the sending rate. 302 The source node uses OSPF to find the shortest path to the 303 destination and, based on available network data, builds a source- 304 routing vector that is inserted in the packet and used by 305 intermediate nodes to route the packet to the destination. To 306 implement the source-routing function we augmented the NS-3 Nix- 307 Vector protocol that builds the source-routing vector from the list 308 of nodes to be traversed, list that is obtained from OSPF. The main 309 process is iterative as we refresh LSA at a fixed interval: for our 310 simulations we experimented with updating LSAs every 50 ms and 500 311 ms. 313 In conclusion we found that our algorithm with fairness provides 314 throughput improvement over both regular TCP and TCP with ECMP. In 315 addition, its ability to discover additional path dynamically 316 eliminates the need to set a preselected set of paths, allowing the 317 spreading of the traffic load amongst a wider but still reasonable 318 set of paths. The results may be found at 319 www.cs.iit.edu/~kapoor/papers/reducerate.pdf . 321 5. References 323 5.1. References 325 [M75] Maxemchuk, N., "Dispersity Routing", IEEE ICC, 1975. 327 [CRS99] Cidon, I., Rom, R., and Y. Shavitt, "Analysis of multi- 328 path routing", IEEE/ACM Trans on Networking pages 885-896, 329 1999. 331 [ST92] Suzuki, H. and F. Tobagi, "Fast bandwidth reservation with 332 multiline and multipath routing in atm networks", 333 Proceedings of IEEE Infocom pages 2233-2240, 1992. 335 [DSAK11] Devetak, F., Shin, J., Anjali, T., and S. Kapoor, 336 "Minimizing path delay in multipath networks", IEEE ICC, 337 2011. 339 [SKDA13] Devetak, F., Anjali, T., Shin, J., and S. Kapoor, 340 "Concurrent multipath routing over bounded paths: 341 Minimizing delay variance", Globecom 2013 , 2013. 343 [PU12] Popovic, M., Upadhyay, U., Le Boudec, J., Khalili, R., and 344 N. Gast, "Mptcp is not pareto-optimal: performance issues 345 and a possible solution", Proceedings of the 8th 346 international conference on Emerging networking 347 experiments and technologies , 2012. 349 [RG10] Barre, S., Greenhalgh, A., Wischik, D., Handley, M., 350 Raiciu, C., and C. Pluntke, "Data center networking with 351 multipath tcp.", 9th ACM SIGCOMM , 2010. 353 [GWH11] Greenhalgh, A., Wischik, D., Handley, M., and C. Raiciu, 354 "Design, implementation and evaluation of congestion 355 control for multipath tcp.", 8th USENIX conference on 356 Networked systems design and implementation , 2011. 358 [RH10] Raiciu, C., Handley, M., Barre, S., and O. Bonaventure, 359 "Experimenting with multipath tcp.", Proceedings of the 360 ACM SIGCOMM 2010 conference , 2010. 362 [AP13] Amer, P. and F. Pang, "Non-renegable selective 363 acknowledgments (nr-sacks) for mptcp.", Proceedings of the 364 2013 27th International Conference on Advanced Information 365 Networking and Applications Workshops , 2013. 367 [M05] Internet Engineering Task Force, , "Coupled congestion 368 control for multipath transport protocols", RFC 6356 , 369 2011. 371 [M06] Internet Engineering Task Force, , "Multipath tcp (mptcp) 372 application interface considerations", RFC 6897 , 2013. 374 [M07] Internet Engineering Task Force, , "Tcp extensions for 375 multipath operation with multiple addresses", RFC 6824 , 376 2013. 378 [M08] Internet Engineering Task Force, , "Architectural 379 guidelines for multipath tcp development", RFC 6182 , 380 2011. 382 5.2. URIs 384 [1] http:www.cs.iit.edu/~kapoor/papers/reducerate.pdf 386 Authors' Addresses 388 Fabrizio Devetak 389 Illinois Institute of Technology 390 10W 31 Street 391 Stuart Building 392 Chicago, IL 60565 393 US 395 Sanjiv Kapoor 396 Illinois Institute of Technology 397 10W 31 Street 398 Stuart Building 399 Chicago, IL 60565 400 US 402 Phone: +1 312 567 5329 403 Email: kapoor@iit.edu 404 URI: http:www.cs.iit.edu/~kapoor