idnits 2.17.1 draft-ietf-opsawg-large-flow-load-balancing-08.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 issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (April 6, 2014) is 3672 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 OPSAWG R. Krishnan 2 Internet Draft Brocade Communications 3 Intended status: Informational L. Yong 4 Expires: October 5, 2014 Huawei USA 5 A. Ghanwani 6 Dell 7 Ning So 8 Tata Communications 9 B. Khasnabish 10 ZTE Corporation 11 April 6, 2014 13 Mechanisms for Optimizing LAG/ECMP Component Link Utilization in 14 Networks 16 draft-ietf-opsawg-large-flow-load-balancing-08.txt 18 Status of this Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. This document may not be modified, 22 and derivative works of it may not be created, except to publish it 23 as an RFC and to translate it into languages other than English. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF), its areas, and its working groups. Note that 27 other groups may also distribute working documents as Internet- 28 Drafts. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 The list of current Internet-Drafts can be accessed at 36 http://www.ietf.org/ietf/1id-abstracts.txt 38 The list of Internet-Draft Shadow Directories can be accessed at 39 http://www.ietf.org/shadow.html 41 This Internet-Draft will expire on October 6, 2014. 43 Copyright Notice 45 Copyright (c) 2014 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Abstract 60 Demands on networking infrastructure are growing exponentially due to 61 bandwidth hungry applications such as rich media applications and 62 inter-data center communications. In this context, it is important to 63 optimally use the bandwidth in wired networks that extensively use 64 link aggregation groups and equal cost multi-paths as techniques for 65 bandwidth scaling. This draft explores some of the mechanisms useful 66 for achieving this. 68 Table of Contents 70 1. Introduction...................................................3 71 1.1. Acronyms..................................................4 72 1.2. Terminology...............................................4 73 2. Flow Categorization............................................5 74 3. Hash-based Load Distribution in LAG/ECMP.......................5 75 4. Mechanisms for Optimizing LAG/ECMP Component Link Utilization..7 76 4.1. Differences in LAG vs ECMP................................8 77 4.2. Operational Overview......................................9 78 4.3. Large Flow Recognition...................................10 79 4.3.1. Flow Identification.................................10 80 4.3.2. Criteria for Recognizing a Large Flow...............10 81 4.3.3. Sampling Techniques.................................11 82 4.3.4. Automatic Hardware Recognition......................12 83 4.3.5. Use of More Than One Detection Method...............13 84 4.4. Load Rebalancing Options.................................13 85 4.4.1. Alternative Placement of Large Flows................14 86 4.4.2. Redistributing Small Flows..........................14 87 4.4.3. Component Link Protection Considerations............15 88 4.4.4. Load Rebalancing Algorithms.........................15 89 4.4.5. Load Rebalancing Example............................15 90 5. Information Model for Flow Rebalancing........................16 91 5.1. Configuration Parameters for Flow Rebalancing............16 92 5.2. System Configuration and Identification Parameters.......17 93 5.3. Information for Alternative Placement of Large Flows.....18 94 5.4. Information for Redistribution of Small Flows............19 95 5.5. Export of Flow Information...............................19 96 5.6. Monitoring information...................................20 97 5.6.1. Interface (link) utilization........................20 98 5.6.2. Other monitoring information........................20 99 6. Operational Considerations....................................21 100 6.1. Rebalancing Frequency....................................21 101 6.2. Handling Route Changes...................................21 102 7. IANA Considerations...........................................21 103 8. Security Considerations.......................................21 104 9. Contributing Authors..........................................22 105 10. Acknowledgements.............................................22 106 11. References...................................................22 107 11.1. Normative References....................................22 108 11.2. Informative References..................................22 110 1. Introduction 112 Networks extensively use link aggregation groups (LAG) [802.1AX] and 113 equal cost multi-paths (ECMP) [RFC 2991] as techniques for capacity 114 scaling. For the problems addressed by this document, network traffic 115 can be predominantly categorized into two traffic types: long-lived 116 large flows and other flows. These other flows, which include long- 117 lived small flows, short-lived small flows, and short-lived large 118 flows, are referred to as "small flows" in this document. Long-lived 119 large flows are simply referred to as "large flows." 121 Stateless hash-based techniques [ITCOM, RFC 2991, RFC 2992, RFC 6790] 122 are often used to distribute both large flows and small flows over 123 the component links in a LAG/ECMP. However the traffic may not be 124 evenly distributed over the component links due to the traffic 125 pattern. 127 This draft describes mechanisms for optimizing LAG/ECMP component 128 link utilization while using hash-based techniques. The mechanisms 129 comprise the following steps -- recognizing large flows in a router; 130 and assigning the large flows to specific LAG/ECMP component links or 131 redistributing the small flows when a component link on the router is 132 congested. 134 It is useful to keep in mind that in typical use cases for this 135 mechanism the large flows are those that consume a significant amount 136 of bandwidth on a link, e.g. greater than 5% of link bandwidth. The 137 number of such flows would necessarily be fairly small, e.g. on the 138 order of 10's or 100's per LAG/ECMP. In other words, the number of 139 large flows is NOT expected to be on the order of millions of flows. 140 Examples of such large flows would be IPsec tunnels in service 141 provider backbone networks or storage backup traffic in data center 142 networks. 144 1.1. Acronyms 146 COTS: Commercial Off-the-shelf 148 DOS: Denial of Service 150 ECMP: Equal Cost Multi-path 152 GRE: Generic Routing Encapsulation 154 LAG: Link Aggregation Group 156 MPLS: Multiprotocol Label Switching 158 NVGRE: Network Virtualization using Generic Routing Encapsulation 160 PBR: Policy Based Routing 162 QoS: Quality of Service 164 STT: Stateless Transport Tunneling 166 TCAM: Ternary Content Addressable Memory 168 VXLAN: Virtual Extensible LAN 170 1.2. Terminology 172 ECMP component link: An individual nexthop within an ECMP group. An 173 ECMP component link may itself comprise a LAG. 175 ECMP table: A table that is used as the nexthop of an ECMP route that 176 comprises the set of component links and the weights associated with 177 each of those component links. The weights are used to determine 178 which values of the hash function map to a given component link. 180 LAG component link: An individual link within a LAG. A LAG component 181 link is typically a physical link. 183 LAG table: A table that is used as the output port which is a LAG 184 that comprises the set of component links and the weights associated 185 with each of those component links. The weights are used to 186 determine which values of the hash function map to a given component 187 link. 189 Large flow(s): Refers to long-lived large flow(s). 191 Small flow(s): Refers to any of, or a combination of, long-lived 192 small flow(s), short-lived small flows, and short-lived large 193 flow(s). 195 2. Flow Categorization 197 In general, based on the size and duration, a flow can be categorized 198 into any one of the following four types, as shown in Figure 1: 200 (a) Short-lived Large Flow (SLLF), 201 (b) Short-lived Small Flow (SLSF), 202 (c) Long-lived Large Flow (LLLF), and 203 (d) Long-lived Small Flow (LLSF). 204 Flow Size 205 ^ 206 |--------------------|--------------------| 207 | | | 208 Large | SLLF | LLLF | 209 Flow | | | 210 |--------------------|--------------------| 211 | | | 212 Small | SLSF | LLSF | 213 Flow | | | 214 +--------------------+--------------------+-->Flow Duration 215 Short-lived Long-lived 216 Flow Flow 218 Figure 1: Flow Categorization 220 In this document, as mentioned earlier, we categorize long-lived 221 large flows as "large flows", and all of the others -- long-lived 222 small flows, short-lived small flows, and short-lived large flows 223 as "small flows". 225 3. Hash-based Load Distribution in LAG/ECMP 227 Hash-based techniques are often used for traffic load balancing to 228 select among multiple available paths within a LAG/ECMP group. The 229 advantages of hash-based techniques for load distribution are the 230 preservation of the packet sequence in a flow and the real-time 231 distribution without maintaining per-flow state in the router. Hash- 232 based techniques use a combination of fields in the packet's headers 233 to identify a flow, and the hash function computed using these fields 234 is used to generate a unique number that identifies a link/path in a 235 LAG/ECMP group. The result of the hashing procedure is a many-to-one 236 mapping of flows to component links. 238 If the traffic mix constitutes flows such that the result of the hash 239 function across these flows is fairly uniform so that a similar 240 number of flows is mapped to each component link, if the individual 241 flow rates are much smaller as compared to the link capacity, and if 242 the rate differences are not dramatic, hash-based techniques produce 243 good results with respect to utilization of the individual component 244 links. However, if one or more of these conditions are not met, hash- 245 based techniques may result in imbalance in the loads on individual 246 component links. 248 One example is illustrated in Figure 2. In Figure 2, there are two 249 routers, R1 and R2, and there is a LAG between them which has 3 250 component links (1), (2), (3). There are a total of 10 flows that 251 need to be distributed across the links in this LAG. The result of 252 applying the hash-based technique is as follows: 254 . Component link (1) has 3 flows -- 2 small flows and 1 large 255 flow -- and the link utilization is normal. 257 . Component link (2) has 3 flows -- 3 small flows and no large 258 flow -- and the link utilization is light. 260 o The absence of any large flow causes the component link 261 under-utilized. 263 . Component link (3) has 4 flows -- 2 small flows and 2 large 264 flows -- and the link capacity is exceeded resulting in 265 congestion. 267 o The presence of 2 large flows causes congestion on this 268 component link. 270 +-----------+ -> +-----------+ 271 | | -> | | 272 | | ===> | | 273 | (1)|--------|(1) | 274 | | -> | | 275 | | -> | | 276 | (R1) | -> | (R2) | 277 | (2)|--------|(2) | 278 | | -> | | 279 | | -> | | 280 | | ===> | | 281 | | ===> | | 282 | (3)|--------|(3) | 283 | | | | 284 +-----------+ +-----------+ 286 Where: -> small flow 287 ===> large flow 289 Figure 2: Unevenly Utilized Component Links 291 This document presents mechanisms for addressing the imbalance in 292 load distribution resulting from commonly used hash-based techniques 293 for LAG/ECMP that were shown in the above example. The mechanisms use 294 large flow awareness to compensate for the imbalance in load 295 distribution. 297 4. Mechanisms for Optimizing LAG/ECMP Component Link Utilization 299 The suggested mechanisms in this draft are about a local optimization 300 solution; they are local in the sense that both the identification of 301 large flows and re-balancing of the load can be accomplished 302 completely within individual nodes in the network without the need 303 for interaction with other nodes. 305 This approach may not yield a global optimization of the placement of 306 large flows across multiple nodes in a network, which may be 307 desirable in some networks. On the other hand, a local approach may 308 be adequate for some environments for the following reasons: 310 1) Different links within a network experience different levels of 311 utilization and, thus, a "targeted" solution is needed for those hot- 312 spots in the network. An example is the utilization of a LAG between 313 two routers that needs to be optimized. 315 2) Some networks may lack end-to-end visibility, e.g. when a 316 certain network, under the control of a given operator, is a transit 317 network for traffic from other networks that are not under the 318 control of the same operator. 320 4.1. Differences in LAG vs ECMP 322 While the mechanisms explained herein are applicable to both LAGs and 323 ECMP groups, it is useful to note that there are some key differences 324 between the two that may impact how effective the mechanism is. This 325 relates, in part, to the localized information with which the scheme 326 is intended to operate. 328 A LAG is usually established across links that are between 2 adjacent 329 routers. As a result, the scope of problem of optimizing the 330 bandwidth utilization on the component links is fairly narrow. It 331 simply involves re-balancing the load across the component links 332 between these two routers, and there is no impact whatsoever to other 333 parts of the network. The scheme works equally well for unicast and 334 multicast flows. 336 On the other hand, with ECMP, redistributing the load across 337 component links that are part of the ECMP group may impact traffic 338 patterns at all of the nodes that are downstream of the given router 339 between itself and the destination. The local optimization may 340 result in congestion at a downstream node. (In its simplest form, an 341 ECMP group may be used to distribute traffic on component links that 342 are between two adjacent routers, and in that case, the ECMP group is 343 no different than a LAG for the purpose of this discussion. It 344 should be noted that an ECMP component link may itself comprise a 345 LAG, in which case the scheme may be further applied to the component 346 links within the LAG.) 348 +-----+ +-----+ 349 | S1 | | S2 | 350 +-----+ +-----+ 351 / \ \ / /\ 352 / +---------+ / \ 353 / / \ \ / \ 354 / / \ +------+ \ 355 / / \ / \ \ 356 +-----+ +-----+ +-----+ 357 | L1 | | L2 | | L3 | 358 +-----+ +-----+ +-----+ 360 Figure 3: Two-level fat tree 362 To demonstrate the limitations of local optimization, consider a two- 363 level fat-tree topology with three leaf nodes (L1, L2, L3) and two 364 spine nodes (S1, S2) and assume all of the links are 10 Gbps. 366 Let L1 have two flows of 4 Gbps each towards L3, and let L2 have one 367 flow of 7 Gbps also towards L3. If L1 balances the load optimally 368 between S1 and S2, and L2 sends the flow via S1, then the downlink 369 from S1 to L3 would get congested resulting in packet discards. On 370 the other hand, if L1 had sent both its flows towards S1 and L2 had 371 sent its flow towards S2, there would have been no congestion at 372 either S1 or S2. 374 The other issue with applying this scheme to ECMP groups is that it 375 may not apply equally to unicast and multicast traffic because of the 376 way multicast trees are constructed. 378 Finally, it is possible for a single physical link to participate as 379 a component link in multiple ECMP groups, whereas with LAGs, a link 380 can participate as a component link of only one LAG. 382 4.2. Operational Overview 384 The various steps in optimizing LAG/ECMP component link utilization 385 in networks are detailed below: 387 Step 1) This involves large flow recognition in routers and 388 maintaining the mapping of the large flow to the component link that 389 it uses. The recognition of large flows is explained in Section 4.3. 391 Step 2) The egress component links are periodically scanned for link 392 utilization and the imbalance for the LAG/ECMP group is monitored. If 393 the imbalance exceeds a certain imbalance threshold, then re- 394 balancing is triggered. Measurement of the imbalance is discussed 395 further in 5.1. Additional criteria may also be used to determine 396 whether or not to trigger rebalancing, such as the maximum 397 utilization of any of the component links, in addition to the 398 imbalance. 400 Step 3) As a part of rebalancing, the operator can choose to 401 rebalance the large flows on to lightly loaded component links of the 402 LAG/ECMP group, redistribute the small flows on the congested link to 403 other component links of the group, or a combination of both. 405 All of the steps identified above can be done locally within the 406 router itself or could involve the use of a central management 407 entity. 409 Providing large flow information to a central management entity 410 provides the capability to globally optimize flow distribution as 411 described in Section 4.1. Consider the following example. A router 412 may have 3 ECMP nexthops that lead down paths P1, P2, and P3. A 413 couple of hops downstream on path P1 there may be a congested link, 414 while paths P2 and P3 may be under-utilized. This is something that 415 the local router does not have visibility into. With the help of a 416 central management entity, the operator could redistribute some of 417 the flows from P1 to P2 and/or P3 resulting in a more optimized flow 418 of traffic. 420 The mechanisms described above are especially useful when bundling 421 links of different bandwidths for e.g. 10 Gbps and 100 Gbps as 422 described in [ID.ietf-rtgwg-cl-requirement]. 424 4.3. Large Flow Recognition 426 4.3.1. Flow Identification 428 A flow (large flow or small flow) can be defined as a sequence of 429 packets for which ordered delivery should be maintained. Flows are 430 typically identified using one or more fields from the packet header, 431 for example: 433 . Layer 2: source MAC address, destination MAC address, VLAN ID. 435 . IP header: IP Protocol, IP source address, IP destination 436 address, flow label (IPv6 only), TCP/UDP source port, TCP/UDP 437 destination port. 439 . MPLS Labels. 441 For tunneling protocols like GRE, VXLAN, NVGRE, STT, etc., flow 442 identification is possible based on inner and/or outer headers. The 443 above list is not exhaustive. The mechanisms described in this 444 document are agnostic to the fields that are used for flow 445 identification. 447 This method of flow identification is consistent with that of IPFIX 448 [RFC 7011]. 450 4.3.2. Criteria for Recognizing a Large Flow 452 From a bandwidth and time duration perspective, in order to recognize 453 large flows we define an observation interval and observe the 454 bandwidth of the flow over that interval. A flow that exceeds a 455 certain minimum bandwidth threshold over that observation interval 456 would be considered a large flow. 458 The two parameters -- the observation interval, and the minimum 459 bandwidth threshold over that observation interval -- should be 460 programmable to facilitate handling of different use cases and 461 traffic characteristics. For example, a flow which is at or above 10% 462 of link bandwidth for a time period of at least 1 second could be 463 declared a large flow [DevoFlow]. 465 In order to avoid excessive churn in the rebalancing, once a flow has 466 been recognized as a large flow, it should continue to be recognized 467 as a large flow for as long as the traffic received during an 468 observation interval exceeds some fraction of the bandwidth 469 threshold, for example 80% of the bandwidth threshold. 471 Various techniques to recognize a large flow are described below. 473 4.3.3. Sampling Techniques 475 A number of routers support sampling techniques such as sFlow [sFlow- 476 v5, sFlow-LAG], PSAMP [RFC 5475] and NetFlow Sampling [RFC 3954]. 477 For the purpose of large flow recognition, sampling needs to be 478 enabled on all of the egress ports in the router where such 479 measurements are desired. 481 Using sFlow as an example, processing in a sFlow collector will 482 provide an approximate indication of the large flows mapping to each 483 of the component links in each LAG/ECMP group. It is possible to 484 implement this part of the collector function in the control plane of 485 the router reducing dependence on an external management station, 486 assuming sufficient control plane resources are available. 488 If egress sampling is not available, ingress sampling can suffice 489 since the central management entity used by the sampling technique 490 typically has multi-node visibility and can use the samples from an 491 immediately downstream node to make measurements for egress traffic 492 at the local node. 494 The option of using ingress sampling for this purpose may not be 495 available if the downstream device is under the control of a 496 different operator, or if the downstream device does not support 497 sampling. 499 Alternatively, since sampling techniques require that the sample be 500 annotated with the packet's egress port information, ingress sampling 501 may suffice. However, this means that sampling would have to be 502 enabled on all ports, rather than only on those ports where such 503 monitoring is desired. There is one situation in which this approach 504 may not work. If there are tunnels that originate from the given 505 router, and if the resulting tunnel comprises the large flow, then 506 this cannot be deduced from ingress sampling at the given router. 507 Instead, if egress sampling is unavailable, then ingress sampling 508 from the downstream router must be used. 510 To illustrate the use of ingress versus egress sampling, we refer to 511 Figure 2. Since we are looking at rebalancing flows at R1, we would 512 need to enable egress sampling on ports (1), (2), and (3) on R1. If 513 egress sampling is not available, and if R2 is also under the control 514 of the same administrator, enabling ingress sampling on R2's ports 515 (1), (2), and (3) would also work, but it would necessitate the 516 involvement of a central management entity in order for R1 to obtain 517 large flow information for each of its links. Finally, R1 can enable 518 ingress sampling only on all of its ports (not just the ports that 519 are part of the LAG/ECMP group being monitored) and that would 520 suffice if the sampling technique annotates the samples with the 521 egress port information. 523 The advantages and disadvantages of sampling techniques are as 524 follows. 526 Advantages: 528 . Supported in most existing routers. 530 . Requires minimal router resources. 532 Disadvantages: 534 . In order to minimize the error inherent in sampling, there is a 535 minimum delay for the recognition time of large flows, and in 536 the time that it takes to react to this information. 538 With sampling, the detection of large flows can be done on the order 539 of one second [DevoFlow]. 541 4.3.4. Automatic Hardware Recognition 543 Implementations may perform automatic recognition of large flows in 544 hardware on a router. Since this is done in hardware, it is an inline 545 solution and would be expected to operate at line rate. 547 Using automatic hardware recognition of large flows, a faster 548 indication of large flows mapped to each of the component links in a 549 LAG/ECMP group is available (as compared to the sampling approach 550 described above). 552 The advantages and disadvantages of automatic hardware recognition 553 are: 555 Advantages: 557 . Large flow detection is offloaded to hardware freeing up 558 software resources and possible dependence on an external 559 management station. 561 . As link speeds get higher, sampling rates are typically reduced 562 to keep the number of samples manageable which places a lower 563 bound on the detection time. With automatic hardware 564 recognition, large flows can be detected in shorter windows on 565 higher link speeds since every packet is accounted for in 566 hardware [NDTM]. 568 Disadvantages: 570 . Such techniques are not supported in many routers. 572 As mentioned earlier, the observation interval for determining a 573 large flow and the bandwidth threshold for classifying a flow as a 574 large flow should be programmable parameters in a router. 576 The implementation of automatic hardware recognition of large flows 577 is vendor dependent and beyond the scope of this document. 579 4.3.5. Use of More Than One Detection Method 581 It is possible that a router may have line cards that support a 582 sampling technique while other line cards support automatic hardware 583 detection of large flows. As long as there is a way for the router 584 to reliably determine the mapping of large flows to component links 585 of a LAG/ECMP group, it is acceptable for the router to use more than 586 one method for large flow recognition. 588 4.4. Load Rebalancing Options 590 Below are suggested techniques for load rebalancing. Equipment 591 vendors should implement all of these techniques and allow the 592 operator to choose one or more techniques based on their 593 applications. 595 Note that regardless of the method used, perfect rebalancing of large 596 flows may not be possible since flows arrive and depart at different 597 times. Also, any flows that are moved from one component link to 598 another may experience momentary packet reordering. 600 4.4.1. Alternative Placement of Large Flows 602 Within a LAG/ECMP group, the member component links with least 603 average port utilization are identified. Some large flow(s) from the 604 heavily loaded component links are then moved to those lightly-loaded 605 member component links using a PBR rule in the ingress processing 606 element(s) in the routers. 608 With this approach, only certain large flows are subjected to 609 momentary flow re-ordering. 611 When a large flow is moved, this will increase the utilization of the 612 link that it moved to potentially creating imbalance in the 613 utilization once again across the component links. Therefore, when 614 moving large flows, care must be taken to account for the existing 615 load, and what the future load will be after large flow has been 616 moved. Further, the appearance of new large flows may require a 617 rearrangement of the placement of existing flows. 619 Consider a case where there is a LAG compromising four 10 Gbps 620 component links and there are four large flows, each of 1 Gbps. 621 These flows are each placed on one of the component links. 622 Subsequent, a fifth large flow of 2 Gbps is recognized and to 623 maintain equitable load distribution, it may require placement of one 624 of the existing 1 Gbps flow to a different component link. And this 625 would still result in some imbalance in the utilization across the 626 component links. 628 4.4.2. Redistributing Small Flows 630 Some large flows may consume the entire bandwidth of the component 631 link(s). In this case, it would be desirable for the small flows to 632 not use the congested component link(s). This can be accomplished in 633 one of the following ways. 635 This method works on some existing router hardware. The idea is to 636 prevent, or reduce the probability, that the small flow hashes into 637 the congested component link(s). 639 . The LAG/ECMP table is modified to include only non-congested 640 component link(s). Small flows hash into this table to be mapped 641 to a destination component link. Alternatively, if certain 642 component links are heavily loaded, but not congested, the 643 output of the hash function can be adjusted to account for large 644 flow loading on each of the component links. 646 . The PBR rules for large flows (refer to Section 4.4.1) must 647 have strict precedence over the LAG/ECMP table lookup result. 649 With this approach the small flows that are moved would be subject to 650 reordering. 652 4.4.3. Component Link Protection Considerations 654 If desired, certain component links may be reserved for link 655 protection. These reserved component links are not used for any flows 656 in the absence of any failures. In the case when the component 657 link(s) fail, all the flows on the failed component link(s) are moved 658 to the reserved component link(s). The mapping table of large flows 659 to component link simply replaces the failed component link with the 660 reserved link. Likewise, the LAG/ECMP table replaces the failed 661 component link with the reserved link. 663 4.4.4. Load Rebalancing Algorithms 665 Specific algorithms for placement of large flows are out of scope of 666 this document. One possibility is to formulate the problem for large 667 flow placement as the well-known bin-packing problem and make use of 668 the various heuristics that are available for that problem [bin- 669 pack]. 671 4.4.5. Load Rebalancing Example 673 Optimizing LAG/ECMP component utilization for the use case in Figure 674 2 is depicted below in Figure 4. The large flow rebalancing explained 675 in Section 4.4 is used. The improved link utilization is as follows: 677 . Component link (1) has 3 flows -- 2 small flows and 1 large 678 flow -- and the link utilization is normal. 680 . Component link (2) has 4 flows -- 3 small flows and 1 large 681 flow -- and the link utilization is normal now. 683 . Component link (3) has 3 flows -- 2 small flows and 1 large 684 flow -- and the link utilization is normal now. 686 +-----------+ -> +-----------+ 687 | | -> | | 688 | | ===> | | 689 | (1)|--------|(1) | 690 | | | | 691 | | ===> | | 692 | | -> | | 693 | | -> | | 694 | (R1) | -> | (R2) | 695 | (2)|--------|(2) | 696 | | | | 697 | | -> | | 698 | | -> | | 699 | | ===> | | 700 | (3)|--------|(3) | 701 | | | | 702 +-----------+ +-----------+ 704 Where: -> small flow 705 ===> large flow 707 Figure 4: Evenly utilized Composite Links 709 Basically, the use of the mechanisms described in Section 4.4.1 710 resulted in a rebalancing of flows where one of the large flows on 711 component link (3) which was previously congested was moved to 712 component link (2) which was previously under-utilized. 714 5. Information Model for Flow Rebalancing 716 In order to support flow rebalancing in a router from an external 717 system, the exchange of some information is necessary between the 718 router and the external system. This section provides an exemplary 719 information model covering the various components needed for the 720 purpose. The model is intended to be informational and may be used 721 as input for development of a data model. 723 5.1. Configuration Parameters for Flow Rebalancing 725 The following parameters are required the configuration of this 726 feature: 728 . Large flow recognition parameters: 730 o Observation interval: The observation interval is the time 731 period in seconds over which the packet arrivals are 732 observed for the purpose of large flow recognition. 734 o Minimum bandwidth threshold: The minimum bandwidth threshold 735 would be configured as a percentage of link speed and 736 translated into a number of bytes over the observation 737 interval. A flow for which the number of bytes received, 738 for a given observation interval, exceeds this number would 739 be recognized as a large flow. 741 o Minimum bandwidth threshold for large flow maintenance: The 742 minimum bandwidth threshold for large flow maintenance is 743 used to provide hysteresis for large flow recognition. 744 Once a flow is recognized as a large flow, it continues to 745 be recognized as a large flow until it falls below this 746 threshold. This is also configured as a percentage of link 747 speed and is typically lower than the minimum bandwidth 748 threshold defined above. 750 . Imbalance threshold: A measure of the deviation of the 751 component link utilizations from the utilization of the overall 752 LAG/ECMP group. Since component links can be of a different 753 speed, the imbalance can be computed as follows. Let the 754 utilization of each component link in a LAG/ECMP group with n 755 links of speed b_1, b_2, .., b_n, be u_1, u_2, .., u_n. The mean 756 utilization is computed is u_ave = [ (u_1 x b_1) + (u_2 x b_2) + 757 .. + (u_n x b_n) ] / [b_1 + b_2 + b_n]. The imbalance is then 758 computed as max_{i=1..n} | u_i - u_ave | / u_ave. 760 . Rebalancing interval: The minimum amount of time between 761 rebalancing events. This parameter ensures that rebalancing is 762 not invoked too frequently as it impacts packet ordering. 764 These parameters may be configured on a system-wide basis or it may 765 apply to an individual LAG. It may be applied to an ECMP group 766 provided the component links are not shared with any other ECMP 767 group. 769 5.2. System Configuration and Identification Parameters 771 The following parameters are useful for router configuration and 772 operation when using the mechanisms in this document. 774 . IP address: The IP address of a specific router that the 775 feature is being configured on, or that the large flow placement 776 is being applied to. 778 . LAG ID: Identifies the LAG on a given router. The LAG ID may be 779 required when configuring this feature (to apply a specific set 780 of large flow identification parameters to the LAG) and will be 781 required when specifying flow placement to achieve the desired 782 rebalancing. 784 . Component Link ID: Identifies the component link within a LAG 785 or ECMP group. This is required when specifying flow placement 786 to achieve the desired rebalancing. 788 . Component Link Weight: The relative weight to be applied to 789 traffic for a given component link when using hash-based 790 techniques for load distribution. 792 . ECMP group: Identifies a particular ECMP group. The ECMP group 793 may be required when configuring this feature (to apply a 794 specific set of large flow identification parameters to the ECMP 795 group) and will be required when specifying flow placement to 796 achieve the desired rebalancing. We note that multiple ECMP 797 groups can share an overlapping set (or non-overlapping subset) 798 of component links. This document does not deal with the 799 complexity of addressing such configurations. 801 The feature may be configured globally for all LAGs and/or for all 802 ECMP groups, or it may be configured specifically for a given LAG or 803 ECMP group. 805 5.3. Information for Alternative Placement of Large Flows 807 In cases where large flow recognition is handled by an external 808 management station (see Section 4.3.3), an information model for 809 flows is required to allow the import of large flow information to 810 the router. 812 The following are some of the elements of information model for 813 importing of flows: 815 . Layer 2: source MAC address, destination MAC address, VLAN ID. 817 . Layer 3 IP: IP Protocol, IP source address, IP destination 818 address, flow label (IPv6 only), TCP/UDP source port, TCP/UDP 819 destination port. 821 . MPLS Labels. 823 This list is not exhaustive. For example, with overlay protocols 824 such as VXLAN and NVGRE, fields from the outer and/or inner headers 825 may be specified. In general, all fields in the packet that can be 826 used by forwarding decisions should be available for use when 827 importing flow information from an external management station. 829 The IPFIX information model [RFC 7012] can be leveraged for large 830 flow identification. 832 Large Flow placement is achieved by specifying the relevant flow 833 information along with the following: 835 . For LAG: Router's IP address, LAG ID, LAG component link ID. 837 . For ECMP: Router's IP address, ECMP group, ECMP component link 838 ID. 840 In the case where the ECMP component link itself comprises a LAG, we 841 would have to specify the parameters for both the ECMP group as well 842 as the LAG to which the large flow is being directed. 844 5.4. Information for Redistribution of Small Flows 846 Redistribution of small flows is done using the following: 848 . For LAG: The LAG ID and the component link IDs along with the 849 relative weight of traffic to be assigned to each component link 850 ID are required. 852 . For ECMP: The ECMP group and the ECMP Nexthop along with the 853 relative weight of traffic to be assigned to each ECMP Nexthop 854 are required. 856 It is possible to have an ECMP nexthop that itself comprises a LAG. 857 In that case, we would have to specify the new weights for both the 858 ECMP nexthops within the ECMP group as well as the component links 859 within the LAG. 861 5.5. Export of Flow Information 863 Exporting large flow information is required when large flow 864 recognition is being done on a router, but the decision to rebalance 865 is being made in an external management station. Large flow 866 information includes flow identification and the component link ID 867 that the flow currently is assigned to. Other information such as 868 flow QoS and bandwidth may be exported too. 870 The IPFIX information model [RFC 7012] can be leveraged for large 871 flow identification. 873 5.6. Monitoring information 875 5.6.1. Interface (link) utilization 877 The incoming bytes (ifInOctets), outgoing bytes (ifOutOctets) and 878 interface speed (ifSpeed) can be measured from the Interface table 879 (iftable) MIB [RFC 1213]. 881 The link utilization can then be computed as follows: 883 Incoming link utilization = (ifInOctets 8 / ifSpeed) 885 Outgoing link utilization = (ifOutOctets 8 / ifSpeed) 887 For high speed Ethernet links, the etherStatsHighCapacityTable MIB 888 [RFC 3273] can be used. 890 For scalability, it is recommended to use the counter push mechanism 891 in [sflow-v5] for the interface counters. Doing so would help avoid 892 counter polling through the MIB interface. 894 The outgoing link utilization of the component links within a 895 LAG/ECMP group can be used to compute the imbalance (See Section 5.1) 896 for the LAG/ECMP group. 898 5.6.2. Other monitoring information 900 Additional monitoring information that is useful includes: 902 . Number of times rebalancing was done. 904 . Time since the last rebalancing event. 906 . The number of large flows currently rebalanced by the scheme. 908 . A list of the large flows that have been rebalanced including 910 o the rate of each large flow at the time of the last 911 rebalancing for that flow, 913 o the time that rebalancing was last performed for the given 914 large flow, and 916 o the interfaces that the large flows was (re)directed to. 918 . The settings for the weights of the interfaces within a 919 LAG/ECMP used by the small flows which depend on hashing. 921 6. Operational Considerations 923 6.1. Rebalancing Frequency 925 Flows should be rebalanced only when the imbalance in the utilization 926 across component links exceeds a certain threshold. Frequent 927 rebalancing to achieve precise equitable utilization across component 928 links could be counter-productive as it may result in moving flows 929 back and forth between the component links impacting packet ordering 930 and system stability. This applies regardless of whether large flows 931 or small flows are redistributed. It should be noted that reordering 932 is a concern for TCP flows with even a few packets because three out- 933 of-order packets would trigger sufficient duplicate ACKs to the 934 sender resulting in a retransmission [RFC 5681]. 936 The operator would have to experiment with various values of the 937 large flow recognition parameters (minimum bandwidth threshold, 938 observation interval) and the imbalance threshold across component 939 links to tune the solution for their environment. 941 6.2. Handling Route Changes 943 Large flow rebalancing must be aware of any changes to the FIB. In 944 cases where the nexthop of a route no longer to points to the LAG, or 945 to an ECMP group, any PBR entries added as described in Section 4.4.1 946 and 4.4.2 must be withdrawn in order to avoid the creation of 947 forwarding loops. 949 7. IANA Considerations 951 This memo includes no request to IANA. 953 8. Security Considerations 955 This document does not directly impact the security of the Internet 956 infrastructure or its applications. In fact, it could help if there 957 is a DOS attack pattern which causes a hash imbalance resulting in 958 heavy overloading of large flows to certain LAG/ECMP component 959 links. 961 9. Contributing Authors 963 Sanjay Khanna 964 Cisco Systems 965 Email: sanjakha@gmail.com 967 10. Acknowledgements 969 The authors would like to thank the following individuals for their 970 review and valuable feedback on earlier versions of this document: 971 Shane Amante, Fred Baker, Michael Bugenhagen, Zhen Cao, Brian 972 Carpenter, Benoit Claise, Michael Fargano, Wes George, Sriganesh 973 Kini, Roman Krzanowski, Andrew Malis, Dave McDysan, Pete Moyer, 974 Peter Phaal, Dan Romascanu, Curtis Villamizar, Jianrong Wong, George 975 Yum, and Weifeng Zhang. 977 11. References 979 11.1. Normative References 981 11.2. Informative References 983 [802.1AX] IEEE Standards Association, "IEEE Std 802.1AX-2008 IEEE 984 Standard for Local and Metropolitan Area Networks - Link 985 Aggregation", 2008. 987 [bin-pack] Coffman, Jr., E., M. Garey, and D. Johnson. Approximation 988 Algorithms for Bin-Packing -- An Updated Survey. In Algorithm Design 989 for Computer System Design, ed. by Ausiello, Lucertini, and Serafini. 990 Springer-Verlag, 1984. 992 [CAIDA] Caida Internet Traffic Analysis, http://www.caida.org/home. 993 [DevoFlow] Mogul, J., et al., "DevoFlow: Cost-Effective Flow 994 Management for High Performance Enterprise Networks," Proceedings of 995 the ACM SIGCOMM, August 2011. 997 [ID.ietf-rtgwg-cl-requirement] Villamizar, C. et al., "Requirements 998 for MPLS over a Composite Link," September 2013. 1000 [ITCOM] Jo, J., et al., "Internet traffic load balancing using 1001 dynamic hashing with flow volume," SPIE ITCOM, 2002. 1003 [NDTM] Estan, C. and G. Varghese, "New directions in traffic 1004 measurement and accounting," Proceedings of ACM SIGCOMM, August 2002. 1006 [RFC 2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and 1007 Multicast," November 2000. 1009 [RFC 6790] Kompella, K. et al., "The Use of Entropy Labels in MPLS 1010 Forwarding," November 2012. 1012 [RFC 1213] McCloghrie, K., "Management Information Base for Network 1013 Management of TCP/IP-based internets: MIB-II," March 1991. 1015 [RFC 2992] Hopps, C., "Analysis of an Equal-Cost Multi-Path 1016 Algorithm," November 2000. 1018 [RFC 3273] Waldbusser, S., "Remote Network Monitoring Management 1019 Information Base for High Capacity Networks," July 2002. 1021 [RFC 3954] Claise, B., "Cisco Systems NetFlow Services Export Version 1022 9," October 2004. 1024 [RFC 5475] Zseby T., et al., "Sampling and Filtering Techniques for 1025 IP Packet Selection," March 2009. 1027 [RFC 7011] Claise, B. et al., "Specification of the IP Flow 1028 Information Export (IPFIX) Protocol for the Exchange of IP Traffic 1029 Flow Information," September 2013. 1031 [RFC 7012] Claise, B. and B. Trammell, "Information Model for IP Flow 1032 Information Export (IPFIX)," September 2013. 1034 [sFlow-LAG] Phaal, P. and A. Ghanwani, "sFlow LAG counters 1035 structure," http://www.sflow.org/sflow_lag.txt, September 2012. 1037 [sFlow-v5] Phaal, P. and M. Lavine, "sFlow version 5," 1038 http://www.sflow.org/sflow_version_5.txt, July 2004. 1040 [YONG] Yong, L., "Enhanced ECMP and Large Flow Aware Transport," 1041 draft-yong-pwe3-enhance-ecmp-lfat-01, September 2010. 1043 [RFC 5681] Allman, M. et al., "TCP Congestion Control," September 1044 2009 1046 Appendix A. Internet Traffic Analysis and Load Balancing Simulation 1048 Internet traffic [CAIDA] has been analyzed to obtain flow statistics 1049 such as the number of packets in a flow and the flow duration. The 1050 five tuples in the packet header (IP addresses, TCP/UDP Ports, and IP 1051 protocol) are used for flow identification. The analysis indicates 1052 that < ~2% of the flows take ~30% of total traffic volume while the 1053 rest of the flows (> ~98%) contributes ~70% [YONG]. 1055 The simulation has shown that given Internet traffic pattern, the 1056 hash-based technique does not evenly distribute the flows over ECMP 1057 paths. Some paths may be > 90% loaded while others are < 40% loaded. 1058 The more ECMP paths exist, the more severe the misbalancing. This 1059 implies that hash-based distribution can cause some paths to become 1060 congested while other paths are underutilized [YONG]. 1062 The simulation also shows substantial improvement by using the large 1063 flow-aware hash-based distribution technique described in this 1064 document. In using the same simulated traffic, the improved 1065 rebalancing can achieve < 10% load differences among the paths. It 1066 proves how large flow-aware hash-based distribution can effectively 1067 compensate the uneven load balancing caused by hashing and the 1068 traffic characteristics [YONG]. 1070 Authors' Addresses 1072 Ram Krishnan 1073 Brocade Communications 1074 San Jose, 95134, USA 1075 Phone: +1-408-406-7890 1076 Email: ramkri123@gmail.com 1078 Lucy Yong 1079 Huawei USA 1080 5340 Legacy Drive 1081 Plano, TX 75025, USA 1082 Phone: +1-469-277-5837 1083 Email: lucy.yong@huawei.com 1085 Anoop Ghanwani 1086 Dell 1087 San Jose, CA 95134 1088 Phone: +1-408-571-3228 1089 Email: anoop@alumni.duke.edu 1091 Ning So 1092 Tata Communications 1093 Plano, TX 75082, USA 1094 Phone: +1-972-955-0914 1095 Email: ning.so@tatacommunications.com 1097 Bhumip Khasnabish 1098 ZTE Corporation 1099 New Jersey, 07960, USA 1100 Phone: +1-781-752-8003 1101 Email: vumip1@gmail.com