OPSAWG R. Krishnan
Internet Draft S. Khanna
Intended status: Informational Brocade Communications
Expires: August 12, 2013 L. Yong
February 13, 2013 Huawei USA
A. Ghanwani
Dell
Ning So
Tata Communications
B. Khasnabish
ZTE Corporation
Mechanisms for Optimal LAG/ECMP Component Link Utilization in
Networks
draft-krishnan-opsawg-large-flow-load-balancing-03.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on August 13, 2013.
Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
Krishnan Expires August 13, 2013 [Page 1]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Abstract
Demands on networking infrastructure are growing exponentially; the
drivers are bandwidth hungry rich media applications, inter-data
center communications, etc. In this context, it is important to
optimally use the bandwidth in wired networks that extensively use
LAG/ECMP techniques for bandwidth scaling. This draft explores some
of the mechanisms useful for achieving this.
Table of Contents
1. Introduction...................................................3
1.1. Conventions...............................................3
1.2. Acronyms..................................................4
1.3. Terminology...............................................4
2. Hash-based Load Distribution in LAG/ECMP.......................4
3. Mechanisms for Optimal LAG/ECMP Component Link Utilization.....6
3.1. Large Flow Recognition....................................8
3.1.1. Flow Identification..................................8
3.1.2. Criteria for Identifying a Large Flow................8
Krishnan Expires August 13, 2013 [Page 2]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
3.1.3. Sampling Techniques..................................9
3.1.4. Automatic Hardware Recognition.......................9
3.2. Load Re-Balancing Options................................11
3.2.1. Alternative Placement of Large Flows................11
3.2.2. Redistributing Small flows..........................11
3.2.3. Component Link Protection Considerations............12
3.2.4. Load Re-Balancing Example...........................12
4. Future Work...................................................13
5. IANA Considerations...........................................14
6. Security Considerations.......................................14
7. Acknowledgements..............................................14
8. References....................................................14
8.1. Normative References.....................................14
8.2. Informative References...................................14
9. Appendix A. Internet Traffic Analysis and Load Balancing
Simulation.......................................................15
10. Appendix B. Techniques for Automatic Hardware Recognition...16
1. Introduction
Networks extensively use LAG/ECMP techniques for capacity scaling.
Network traffic can be predominantly categorized into two traffic
types: long-lived large flows and other flows (which include long-
lived small flows, short-lived small/large flows). Stateless hash-
based techniques [ITCOM, RFC 2991, RFC 2992, RFC 6790] are often used
to distribute both long-lived large flows and other flows over the
component links in a LAG/ECMP. However the traffic may not be evenly
distributed over the component links due to the traffic pattern.
This draft describes best practices for optimal LAG/ECMP component
link utilization while using hash-based techniques. These best
practices comprise the following steps -- recognizing long-lived
large flows in a router; and assigning the long-lived large flows to
specific LAG/ECMP component links or redistributing other flows when
a component link on the router is congested.
1.1. Conventions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Krishnan Expires August 13, 2013 [Page 3]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
1.2. Acronyms
COTS: Commercial Off-the-shelf
DOS: Denial of Service
ECMP: Equal Cost Multi-path
GRE: Generic Routing Encapsulation
LAG: Link Aggregation Group
MPLS: Multiprotocol Label Switching
NVGRE: Network Virtualization using Generic Routing Encapsulation
PBR: Policy Based Routing
QoS: Quality of Service
STT: Stateless Transport Tunneling
TCAM: Ternary Content Addressable Memory
VXLAN: Virtual Extensible LAN
1.3. Terminology
Large flow(s): long-lived large flow(s)
Small flow(s): long-lived small flow(s) and short-lived small/large
flow(s)
2. Hash-based Load Distribution in LAG/ECMP
Hashing techniques are often used for traffic load balancing to
select among multiple available paths with LAG/ECMP. The advantages
of hash-based load distribution are the preservation of the packet
sequence in a flow and the real-time distribution without maintaining
per-flow state in the router. Hash-based techniques use a combination
Krishnan Expires August 13, 2013 [Page 4]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
of fields in the packet's headers to identify a flow, and the hash
function on these fields is used to generate a unique number that
identifies a link/path in a LAG/ECMP. The result of the hashing
procedure is a many-to-one mapping of flows to component links.
If the traffic load constitutes flows such that the result of the
hash function across these flows is fairly uniform so that a similar
number of flows is mapped to each component link, if, the individual
flow rates are much smaller as compared to the link capacity, and if
the rate differences are not dramatic, the hash-based algorithm
produces good results with respect to utilization of the individual
component links. However, if one or more of these conditions are not
met, hash-based techniques may result in unbalanced loads on
individual component links.
One example is illustrated in Figure 1. In the figure, there are two
routers, R1 and R2, and there is a LAG between them which has 3
component links (1), (2), (3). There are a total of 10 flows that
need to be distributed across the links in this LAG. The result of
hashing is as follows:
. Component link (1) has 3 flows -- 2 small flows and 1 large
flow -- and the link utilization is normal.
. Component link (2) has 3 flows -- 3 small flows and no large
flow -- and the link utilization is light.
o The absence of any large flow causes the component link
under-utilized.
. Component link (3) has 4 flows -- 2 small flows and 2 large
flows -- and the link capacity is exceeded resulting in
congestion.
o The presence of 2 large flows causes congestion on this
component link.
Krishnan Expires August 13, 2013 [Page 5]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
+-----------+ +-----------+
| | -> -> | |
| |=====> | |
| (1)|--/---/-|(1) |
| | | |
| | | |
| (R1) |-> -> ->| (R2) |
| (2)|--/---/-|(2) |
| | | |
| | -> -> | |
| |=====> | |
| |=====> | |
| (3)|--/---/-|(3) |
| | | |
+-----------+ +-----------+
Where: ->-> small flows
===> large flow
Figure 1: Unevenly Utilized Component Links
This document presents improved load distribution techniques based on
the large flow awareness. The techniques compensate for unbalanced
load distribution resulting from hashing as demonstrated in the above
example.
3. Mechanisms for Optimal LAG/ECMP Component Link Utilization
The suggested techniques in this draft are about a local optimization
solution; they are local in the sense that both the identification of
large flows and re-balancing of the load can be accomplished
completely within individual nodes in the network without the need
for interaction with other nodes.
This approach may not yield a globally optimal placement of large
flows across multiple nodes in a network, which may be desirable in
some networks. On the other hand, a local approach may be adequate
for some environments for the following reasons:
Krishnan Expires August 13, 2013 [Page 6]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
1) Different links within a network experience different levels of
utilization and, thus, a "targeted" solution is needed for those hot-
spots in the network. An example is the utilization of a LAG between
two routers that needs to be optimized.
2) Some networks may lack end-to-end visibility, e.g. when a
certain network, under the control of a given operator, is a transit
network for traffic from other networks that are not under the
control of the same operator.
The various steps in achieving optimal LAG/ECMP component link
utilization in networks are detailed below:
Step 1) This involves large flow recognition in routers and
maintaining the mapping of the large flow to the component link that
it uses. The recognition of large flows is explained in Section 3.1.
Step 2) The egress component links are periodically scanned for link
utilization. If the egress component link utilization exceeds a pre-
programmed threshold, an operator alert is generated. The large flows
mapped to the congested egress component link are exported to a
central management entity.
Step 3) On receiving the alert about the congested component link,
the operator, through a central management entity, finds the large
flows mapped to that component link and the LAG/ECMP group to which
the component link belongs.
Step 4) The operator can choose to rebalance the large flows on
lightly loaded component links of the LAG/ECMP group or redistribute
the small flows on the congested link to other component links of the
group. The operator, through a central management entity, can choose
one of the following actions:
1) Indicate specific large flows to rebalance;
2) Have the router decide the best large flows to rebalance;
3) Have the router redistribute all the small flows on the
congested link to other component links in the group.
The central management entity conveys the above information to the
router. The load re-balancing options are explained in Section 3.2.
Steps 2) to 4) could be automated if desired.
Krishnan Expires August 13, 2013 [Page 7]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
Providing large flow information to a central management entity
provides the capability to further optimize flow distribution at with
multi-node visibility. Consider the following example. A router may
have 3 ECMP nexthops that lead down paths P1, P2, and P3. A couple
of hops downstream on P1 may be congested, while P2 and P3 may be
under-utilized, which the local router does not have visibility into.
With the help of a central management entity, the operator could
redistribute some of the flows from P1 to P2 and P3 resulting in a
more optimized flow of traffic.
The techniques described above are especially useful when bundling
links of different bandwidths for e.g. 10Gbps and 100Gbps as
described in [I-D.ietf-rtgwg-cl-requirement].
3.1. Large Flow Recognition
3.1.1. Flow Identification
A flow (large flow or small flow) can be defined as a sequence of
packets for which ordered delivery should be maintained. Flows are
typically identified using one or more fields from the packet header
from the following list:
. Layer 2: source MAC address, destination MAC address, VLAN ID.
. IP header: IP Protocol, IP source address, IP destination
address, flow label (IPv6 only), TCP/UDP source port, TCP/UDP
destination port.
. MPLS Labels.
For tunneling protocols like GRE, VXLAN, NVGRE, STT, etc., flow
identification is possible based on inner and/or outer headers. The
above list is not exhaustive. The mechanisms described in this
document are agnostic to the fields that are used for flow
identification.
3.1.2. Criteria for Identifying a Large Flow
From a bandwidth and time duration perspective, in order to identify
large flows we define an observation interval and observe the
bandwidth of the flow over that interval. A flow that exceeds a
certain minimum bandwidth threshold over that observation interval
would be considered a large flow.
The two parameters -- the observation interval, and the minimum
bandwidth threshold over that observation interval -- should be
Krishnan Expires August 13, 2013 [Page 8]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
programmable in a router to facilitate handling of different use
cases and traffic characteristics. For example, a flow which is at or
above 100 Mbps for a time period of at least 5 minutes could be
declared a large flow. Various techniques to identify a large flow
are described below.
3.1.3. Sampling Techniques
A number of routers support sampling techniques such as sFlow [sFlow-
v5, sFlow-LAG], PSAMP [RFC 5475] and Netflow Sampling [RFC 3954].
For the purpose of large flow identification, sampling must be
enabled on all of the egress ports in the router.
For example, through sFlow processing in a sFlow collector, an
approximate indication of the large flows mapping to each of the
component links in each LAG/ECMP group is available.
If egress sampling is not available, ingress sampling can suffice
since the central management entity used by the sampling technique
typically has multi-node visibility and can use the samples from an
immediately downstream node to make measurements for egress traffic
at the local node. This may not be available if the downstream
device is under the control of a different operator, or if the
downstream device does not support sampling.
The advantages and disadvantages of sampling techniques are as
follows.
Advantages:
. Supported in most routers.
. Requires minimal router resources.
Disadvantages:
. There is a delay in the recognition time for large flows, and
in the time that it takes to react to this information.
With sampling, the detection of large flows can be done on the order
of one to a few seconds [DevoFlow].
3.1.4. Automatic Hardware Recognition
Implementations may perform automatic recognition of large flows in
hardware on a router. Since this is done in hardware, it is an inline
solution and would be expected to operate at line rate.
Krishnan Expires August 13, 2013 [Page 9]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
Using automatic hardware recognition of large flows, a faster
indication of large flows mapped to each of the component links in a
LAG/ECMP group is available (as compared to the sampling approach
described above).
The advantages and disadvantages of automatic hardware recognition
are:
Advantages:
. Accurate and performed in real-time.
Disadvantages:
. Not supported in many routers.
As mentioned earlier, the observation interval for determining a
large flow and the bandwidth threshold for classifying a flow as a
large flow should be programmable parameters in a router.
The implementation of automatic hardware recognition of large flows
is vendor dependent. Below is a suggested technique.
This technique requires a few tables -- a flow table, and multiple
hash tables.
The flow table comprises entries which are programmed with packet
fields for flows that are already known to be large flows and each
entry has a corresponding byte counter. It is initialized as an
empty table (i.e. none of the incoming packets would match a flow
table entry).
The hash tables each have a different hash function and comprise
entries which are byte counters. The counters are initialized to
zero and would be modified as described by the algorithm below.
Step 1) If the large flow exists in the flow table (for e.g. TCAM),
increment the counter associated with the flow by the packet size.
Else, proceed to Step 2.
Step 2) The hash function for each table is applied to the fields of
the packet header and the result is looked up in parallel in
corresponding hash table and the associated counter corresponding to
the entry that is hit in that table is incremented by the packet
size. If the counter exceeds a programmed byte threshold in the
observation interval (this counter threshold would be set to match
the bandwidth threshold) in the entries that were hit in all of the
Krishnan Expires August 13, 2013 [Page 10]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
hash tables, a candidate large flow is learnt and programmed in the
flow table and the counters are reset.
Additionally, the counters in all of the hash tables must be reset
every observation interval.
There may be some false positives due to multiple small flows
masquerading as a large flow. The number of such false positives is
reduced by increasing the number of parallel hash tables using
different hash functions. There will be a design tradeoff between
size of the hash tables, the number of hash tables, and the
probability of a false positive. More details on this algorithm are
found in Appendix B.
3.2. Load Re-Balancing Options
Below are suggested techniques for load re-balancing. Equipment
vendors should implement all of these techniques and allow the
operator to choose one or more techniques based on their
applications.
3.2.1. Alternative Placement of Large Flows
In the LAG/ECMP group, choose other member component links with least
average port utilization. Move some large flow(s) from the heavily
loaded component link to other member component links using a Policy
Based Routing (PBR) rule in the ingress processing element(s) in the
routers. The key aspects of this are:
. Small flows are not subjected to flow re-ordering.
. Only certain large flows are subjected to momentary flow re-
ordering.
Note that perfect re-balancing of large flows may not be possible
since flows arrive and depart at different times.
3.2.2. Redistributing Small flows
Some large flows may consume the entire bandwidth of the component
link(s). In this case, it would be desirable for the small flows to
not use the congested component link(s). This can be accomplished in
one of the following ways.
This method works on some existing router hardware. The idea is to
prevent, or reduce the probability, that the small flow hashes into
the congested component link(s).
Krishnan Expires August 13, 2013 [Page 11]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
. The LAG/ECMP table is modified to include only non-congested
component link(s). Small flows hash into this table to be mapped
to a destination component link. Alternatively, if certain
component links are heavily loaded, but not congested, the
output of the hash function can be adjusted to account for large
flow loading on each of the component links.
. Small flows may be subject to momentary packet re-ordering.
. The PBR rules for large flows (refer to Section 3.2.1) must
have strict precedence over the LAG/ECMP table lookup result.
3.2.3. Component Link Protection Considerations
If desired, certain component links may be reserved for link
protection. These reserved component links are not used for any flows
which are described in Section 3.2. In the case when the component
link(s) fail, all the flows on the failed component link(s) are moved
to the reserved component link(s). The mapping table of large flows
to component link simply replaces the reference pointer from the
failed component link to the reserved link. Likewise, the LAG/ECMP
hash table replaces the reference pointer from the failed component
link to the reserved link.
3.2.4. Load Re-Balancing Example
Optimal LAG/ECMP component utilization for the use case in Figure 1
is depicted below in Figure 2. The large flow rebalancing explained
in Section 3.2.1 is used. The improved link utilization is as
follows:
. Component link (1) has 3 flows -- 2 small flows and 1 large
flow -- and the link utilization is normal.
. Component link (2) has 4 flows -- 3 small flows and 1 large
flow -- and the link utilization is normal now.
. Component link (3) has 3 flows -- 2 small flows and 1 large
flow -- and the link utilization is normal now.
Krishnan Expires August 13, 2013 [Page 12]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
+-----------+ +-----------+
| | -> -> | |
| |=====> | |
| (1)|--/---/-|(1) |
| | | |
| |=====> | |
| (R1) |-> -> ->| (R2) |
| (2)|--/---/-|(2) |
| | | |
| | | |
| | -> -> | |
| |=====> | |
| (3)|--/---/-|(3) |
| | | |
+-----------+ +-----------+
Where: ->-> small flows
===> large flow
Figure 2: Evenly utilized Composite Links
Basically, the use of the mechanisms described in Section 3.2.1
resulted in a rebalancing of flows where one of the large flows on
component link (3) which was previously congested was moved to
component link (2) which was previously under-utilized.
4. Future Work
There are two areas that would benefit from further standards work:
1) Development of a data model used to move the large flow
information from the router to the central management entity.
2) Development of a data model used to move the large flow re-
balancing information from the central management entity to the
router.
Krishnan Expires August 13, 2013 [Page 13]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
5. IANA Considerations
This memo includes no request to IANA.
6. Security Considerations
This document does not directly impact the security of the Internet
infrastructure or its applications. In fact, it could help if there
is a DOS attack pattern which causes a hash imbalance resulting in
heavy overloading of large flows to certain LAG/ECMP component
links.
7. Acknowledgements
The authors would like to thank the following individuals for their
review and valuable feedback on earlier versions of this document:
Shane Amante, Curtis Villamizar, Fred Baker, Wes George, Brian
Carpenter, George Yum, Michael Fargano, Michael Bugenhagen, Jianrong
Wong, and Peter Phaal.
8. References
8.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2234] Crocker, D. and Overell, P. (Editors), "Augmented BNF for
Syntax Specifications: ABNF", RFC 2234, Internet Mail
Consortium and Demon Internet Ltd., November 1997.
8.2. Informative References
[I-D.ietf-rtgwg-cl-requirement] Villamizar, C. et al., "Requirements
for MPLS over a Composite Link", June 2012.
[RFC 6790] Kompella, K. et al., "The Use of Entropy Labels in MPLS
Forwarding", November 2012.
Krishnan Expires August 13, 2013 [Page 14]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
[CAIDA] Caida Internet Traffic Analysis, http://www.caida.org/home.
[YONG] Yong, L., "Enhanced ECMP and Large Flow Aware Transport",
draft-yong-pwe3-enhance-ecmp-lfat-01, September 2010.
[ITCOM] Jo, J., et al., "Internet traffic load balancing using
dynamic hashing with flow volume", SPIE ITCOM, 2002.
[RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
Multicast", November 2000.
[RFC2992] Hopps, C., "Analysis of an Equal-Cost Multi-Path
Algorithm", November 2000.
[RFC5475] Zseby, T., et al., "Sampling and Filtering Techniques for
IP Packet Selection", March 2009.
[sFlow-v5] Phaal, P. and M. Lavine, "sFlow version 5", July 2004.
[sFlow-LAG] Phaal, P., and A. Ghanwani, "sFlow LAG counters
structure", September 2012.
[RFC 3954] Claise, B., "Cisco Systems NetFlow Services Export Version
9", October 2004
[DevoFlow] Mogul, J., et al., "DevoFlow: Cost-Effective Flow
Management for High Performance Enterprise Networks", Proceedings of
the ACM SIGCOMM, August 2011.
Appendix A. Internet Traffic Analysis and Load Balancing Simulation
Internet traffic [CAIDA] has been analyzed to obtain flow statistics
such as the number of packets in a flow and the flow duration. The
five tuples in the packet header (IP addresses, TCP/UDP Ports, and IP
Krishnan Expires August 13, 2013 [Page 15]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
protocol) are used for flow identification. The analysis indicates
that < ~2% of the flows take ~30% of total traffic volume while the
rest of the flows (> ~98%) contributes ~70% [YONG].
The simulation has shown that given Internet traffic pattern, the
hash-based technique does not evenly distribute the flows over ECMP
paths. Some paths may be > 90% loaded while others are < 40% loaded.
The more ECMP paths exist, the more severe the misbalancing. This
implies that hash-based distribution can cause some paths to become
congested while other paths are underutilized [YONG].
The simulation also shows substantial improvement by using the large
flow-aware hash-based distribution technique described in this
document. In using the same simulated traffic, the improved
rebalancing can achieve < 10% load differences among the paths. It
proves how large flow-aware hash-based distribution can effectively
compensate the uneven load balancing caused by hashing and the
traffic characteristics [YONG].
Appendix B. Techniques for Automatic Hardware Recognition
B.1 Comparison of Single Hash vs Multiple Hash for Large Flow
Identification
The suggested multiple hash technique is scalable in terms of hash
table storage and flow-table storage. This is independent of the
quality of the hash functions. Scalability is an important
consideration because there could be millions of flows only a small
percentage of which are large flows which need to be examined. The
amount of hash table storage is proportional to the number of large
flows - the exact number would depend on the use cases and traffic
characteristics. The amount of flow-table storage needed is only
slightly more than the number of large flows; a little extra space is
needed to accommodate any false positives (small flows which may have
been incorrectly identified as large flows).
Krishnan Expires August 13, 2013 [Page 16]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
With a single hash, the hash table storage would be proportionate to
the total number of flows in order to minimize false positives. The
amount of flow-table storage needed depends on the total number flows
and the hash table size.
B.2 Steady state analysis of suggested multiple hash technique
Objective:
Determine the probability of short-lived flows masquerading as long-
lived-flows
Assumptions:
The small flows are uniformly distributed over all of the hash
buckets. Further, assume that the small flows have an identical
number of packets in the observation interval.
Notation:
Number of hash stages - m
Number of hash buckets per stage - n
Minimum large flow rate (bytes/sec) - s
Time interval of examination (sec) - t
Number of small flows in time interval t - x1
Number of packets per small flow in time interval t - y
Average packet size of small flow - z
Average number of small flows in a hash bucket - x2 (x1/n)
Minimum number of small flows in the same hash bucket that would lead
to one small flow being incorrectly identified as a large flow -
x3Basically, if we have some number of small flows hashing into a
bucket, only those buckets which hit the minimum bandwidth threshold
would trigger large flow identification and only the last small flow
which triggered the event would be incorrectly identified as a large
flow.
Using the above notation, it would take at least x3 small flows
hashing to the same bucket to trigger the minimum bandwidth threshold
Krishnan Expires August 13, 2013 [Page 17]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
for that bucket, and the flow to which the last packet belongs would
be incorrectly identified as a large flow.
x3 = (s*t)/(y*z)
Let p1 be the probability of such an incorrectly identified large
flow per hash stage. Let x be a variable denoting the number of small
flows which hash to the same bucket and can take a value {0, 1, ...,
x1}. As noted above, the mean value of x is x2.
p1 = Prob(x >= x3)
Overall probability with m independent hash stages - p1^m
Thus, larger tables and more number of tables would lead to a lower
probability of incorrectly identified large flows.
An example:
m = 4, n = 2K, s = 1 MB/sec, t = 1 sec, x1 = 200K, y = 10, z = 1K
x2 = 200K/2K = 100
x3 = (1024*1024)/(10*1024) = 102.4
p1 = Prob (x >= x3) ~= 0.5
(x2 = 100 small flows fall into one hash bucket on the average)
Overall probability with m independent hash stages is
(p1)^m = (0.5)^4 = 0.0625
Thus, by having 4 stages, the probability of a small flow being
incorrectly identified as a large flow is reduced from 0.5 to 0.0625.
Authors' Addresses
Ram Krishnan
Brocade Communications
San Jose, 95134, USA
Phone: +1-408-406-7890
Email: ramk@brocade.com
Sanjay Khanna
Krishnan Expires August 13, 2013 [Page 18]
Internet-Draft Optimal Load Distribution over LAG/ECMP February 2013
Brocade Communications
San Jose, 95134, USA
Phone: +1-408-333-4850
Email: skhanna@brocade.com
Lucy Yong
Huawei USA
5340 Legacy Drive
Plano, TX 75025, USA
Phone: +1-469-277-5837
Email: lucy.yong@huawei.com
Anoop Ghanwani
Dell
San Jose, CA 95134
Phone: +1-408-571-3228
Email: anoop@alumni.duke.edu
Ning So
Tata Communications
Plano, TX 75082, USA
Phone: +1-972-955-0914
Email: ning.so@tatacommunications.com
Bhumip Khasnabish
ZTE Corporation
New Jersey, 07960, USA
Phone: +1-781-752-8003
Email: bhumip.khasnabish@zteusa.com
Krishnan Expires August 13, 2013 [Page 19]