Weighted HRW and its applications
draft-mohanty-bess-weighted-hrw-00
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Replaced".
|
|
|---|---|---|---|
| Authors | Satya Mohanty , Mankamana Prasad Mishra , Acee Lindem , Ali Sajassi | ||
| Last updated | 2019-03-11 | ||
| Replaced by | draft-ietf-bess-weighted-hrw | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-mohanty-bess-weighted-hrw-00
BESS Working Group S. Mohanty
Internet-Draft M. Misra
Intended status: Standards Track A. Lindem
Expires: September 12, 2019 A. Sajassi
Cisco Systems, Inc.
March 11, 2019
Weighted HRW and its applications
draft-mohanty-bess-weighted-hrw-00
Abstract
Rendezvous Hashing also known as Highest Random Weight (HRW) has been
used in many load balancing applications where the central problem is
how to map an object to as server such that the mapping is uniform
and also minimally affected by the change in the server set.
Recently, it has found use in DF election algorithms in the EVPN
context and load balancing using DMZ. This draft deals with the
problem of achieving load balancing with minimal disruption when the
servers have different weights. It provides an algorithm to do so
and also describes a few use-case scenarios where this algorithmic
technique can apply.
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). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on September 12, 2019.
Copyright Notice
Copyright (c) 2019 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
Mohanty, et al. Expires September 12, 2019 [Page 1]
Internet-Draft Weighted HRW and its Applications March 2019
(https://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. 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.
Table of Contents
1. Requirements Language . . . . . . . . . . . . . . . . . . . . 2
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
3. HRW Introduction . . . . . . . . . . . . . . . . . . . . . . 3
4. HRW with weights . . . . . . . . . . . . . . . . . . . . . . 4
5. HRW and Consistent Hashing . . . . . . . . . . . . . . . . . 5
6. Weighted HRW and its application to the EVPN DF Election . . 5
7. Weighted HRW and its application to Resilient Hashing . . . . 7
8. Weighted HRW and its application to Multicast DR Election . . 7
9. Protocol Considerations . . . . . . . . . . . . . . . . . . . 8
10. Operational Considerations . . . . . . . . . . . . . . . . . 8
11. Security Considerations . . . . . . . . . . . . . . . . . . . 8
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
13.1. Normative References . . . . . . . . . . . . . . . . . . 8
13.2. Informative References . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
1. Requirements Language
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 [RFC2119].
2. Introduction
Given an object O, a set of servers and a set of clients, a
fundamental problem is how do the set of clients, independently and
unanimously agree in a distributed framework, which server to assign
O? This is the distributed hash table problem. The assignment
should be "minimally disruptive" which means that there should be a
minimal remapping of objects whenever a server is down or a new
server comes up or the object set changes. This is a very common
problem in practice in the Internet load balancing and web caching as
described in the 'Akamai' paper [CHASH], database [DYNAMODB] and
networking context.
Mohanty, et al. Expires September 12, 2019 [Page 2]
Internet-Draft Weighted HRW and its Applications March 2019
+----+ +----+ +----+ +-----+
| | | | | | | |
| S0 | | S1 | | S2 | | Sn |
| | | | | | | |
+----+ +----+ +----+ +-----+
| | | |
| | | |
| | | |
| | | |
| | | |
+----------+----------+-------------|
O0, O1, O2 ... ON
Set of Objects need to be assigned to the set of servers.
All the servers are of same capacities
Figure 1 The object to server assignment problem
Figure 1
In the Fig 1, we show a set of servers, S0,..,Sn and object pool
O0,..,On and the requirement is to assign Oi to Sj such that the
servers are uniformly loaded. In addition, when any server goes down
or a new one is introduced, there should be minimal reassignments.
There are two standard techniques to address this problem.
1. Consistent Hashing
2. Rendezvous Hashing
3. HRW Introduction
Highest Random Weight (HRW) as defined in [HRW1999]is originally
proposed in the context of Internet Caching and proxy Server load
balancing. Given an object name and a set of servers, HRW maps a
request to a server using the object-id (Oi) and server-id(Sj) rather
than the state of the server states. HRW computes a hash, Hash(Oi,
Sj) from the server-id and the object-id; this hash value can be
considered as a score, and forms an ordered list of the servers based
on the hash value (i.e. score) in decreasing order. The server for
which the score is the highest, serves as the primary responsible for
that particular object, and the server with the next highest score
serves as the backup server. HRW always maps a given object object
name to the same server within a given cluster; consequently it can
Mohanty, et al. Expires September 12, 2019 [Page 3]
Internet-Draft Weighted HRW and its Applications March 2019
be used at client sites to achieve global consensus on object-server
mappings. When that server goes down, the backup server becomes the
responsible designate.
Choosing an appropriate hash function that is statistically oblivious
to the key distribution and imparts a good uniform distribution of
the hash output is an important aspect of the algorithm. The
original HRW [HRW1999] provides pseudorandom functions based on Unix
utilities rand and srand and easily constructed XOR functions that
perform considerably well. Any good uniform hash function like the
Jenkins hash for instance will also work. HRW already finds use in
multicast and ECMP [RFC2991],[RFC2992].
4. HRW with weights
The issue when the servers are not of the same capacity is also quite
a common problem. However this problem has not gained as much
attention as it should. In such a case, an obvious approach is to
take the normalized weight factor into account, fi=wi/Sum(wi)and
multiply the Hash(Oi, Sj) with that value i.e. the value fi*Hash(Oi,
Sj). The Cache Array Routing Protocol [CARP] used this method.
However there is a problem with this approach, since any change in
weight of any of the servers, will result in a change in the
normalized weights for everyone. This will necessitate re-computing
all the weighted hash values all over again. Therefore this approach
does not have the minimal disruption property of the HRW. We address
this issue of the weighted HRW with minimal disruption in this draft.
Instead of re-normalizing the weights, or, in other words relatively
scaling them, the approach taken by [WHRW] is to adjust the score
before weighing them. When a server is added, removed or modified
(its weight changes), only the score for that server changes. That
server may win or lose some objects. Other servers remain affected.
There is no needless transfer of objects between servers whose weight
did not change. [WHRW] uses a clever way to accomplish this by
defining the score function as:
1. Score(Oi, Sj) = -wi/log(Hash(Oi, Sj)/Hmax); where Hmax is the
maximum hash value.
The author provides a mathematical proof as to why this choice of the
Score function works with very mild assumptions on the probability
distribution of the hash function.
Mohanty, et al. Expires September 12, 2019 [Page 4]
Internet-Draft Weighted HRW and its Applications March 2019
+----+ +----+ +----+ +----+
| | | | | | | |
| S0 | | S1 | | S2 |-------| Sn |
| w0 | | w1 | | w2 | | wn |
+----+ +----+ +----+ +----+
| | | |
| | | |
| | | |
| | | |
| | | |
+----------+----------+-------------|
O1, O2 ... ON
Set of Objects need to be assigned to the set of servers.
Each server is now associated with a weight
Figure 1 The object to server assignment problem
Figure 2
5. HRW and Consistent Hashing
HRW is not the only algorithm that addresses the object to server
mapping problem with goals of fair load distribution, redundancy and
fast access. There is another family of algorithms that also
addresses this problem; these fall under the umbrella of the
Consistent Hashing Algorithms [CHASH]. These will not be considered
here.
6. Weighted HRW and its application to the EVPN DF Election
The notion and need for the Designated Forwarder is described in
[RFC7432]. Consider a CE that is a host or a router that is multi-
homed directly to more than one PE in an EVPN instance on a given
Ethernet segment. One or more Ethernet Tags may be configured on the
Ethernet segment. In this scenario only one of the PEs, referred to
as the Designated Forwarder (DF), is responsible for certain actions:
a. Sending multicast and broadcast traffic, on a given Ethernet Tag
on a particular Ethernet segment, to the CE.
b. Flooding unknown unicast traffic (i.e. traffic for which an PE
does not know the destination MAC address), on a given Ethernet
Tag on a particular Ethernet segment to the CE, if the
environment requires flooding of unknown unicast traffic.
Mohanty, et al. Expires September 12, 2019 [Page 5]
Internet-Draft Weighted HRW and its Applications March 2019
+---------------+
| IP/MPLS |
| CORE |
+----+ ES1 +----+ +----+
| CE1|-----| |-----------| |____ES2
+----+ | PE1| | PE2| \
| |-------- +----+ \+----+
+----+ | | | CE2|
| | +----+ /+----+
| |__| |____/ |
| | PE3| ES2 /
| +----+ /
| | /
+-------------+----+ /
| PE4|____/ES2
| |
+----+
Figure 3 Multi-homing Network of EVPN
Figure 3
Figure 3 illustrates a case where there are two Ethernet Segments,
ES1 and ES2. PE1 is attached to CE1 via Ethernet Segment ES1 whereas
PE2, PE3 and PE4 are attached to CE2 via ES2 i.e. PE2, PE3 and PE4
form a redundancy group. Since CE2 is multi-homed to different PEs
on the same Ethernet Segment, it is necessary for PE2, PE3 and PE4 to
agree on a DF to satisfy the above mentioned requirements.
The use of HRW in the EVPN DF Election is described in
[I-D.ietf-bess-evpn-df-election-framework]. In that draft it is
explained how the HRW DF Election performs better than the modulo DF
Election algorithm in [RFC7432]. However, it is implicitly assumed
there that all the PEs are of the same capacity (weights equal).
DMZ link bandwidth for load balancing flows across multiple EBGP
egress points is described in [I-D.ietf-idr-link-bandwidth]. It has
been extended to the case of cumulative DMZ load balancing
[I-D.mohanty-bess-ebgp-dmz] in the case of an all EBGP network in the
data center. [I-D.ietf-bess-evpn-unequal-lb] describes the use of
the DMZ in the EVPN DF Election. The argument is made that ideally
one should be able to change the link bandwidth in one or more of the
multi-homed PEs rather than have to change in all of the multi-homed
PEs simultaneously. The draft describes the bandwidth increments to
be taken into consideration and proposes an iterative way to assign
Mohanty, et al. Expires September 12, 2019 [Page 6]
Internet-Draft Weighted HRW and its Applications March 2019
the score function. The description in Section 4.3.2 of
[I-D.ietf-bess-evpn-unequal-lb] is an non-optimal solution and
somewhat empirical. It does not obey the minimal disruption property
of the HRW.
In contrast to the procedures for weighted HRW in 4.3.2 of
[I-D.ietf-bess-evpn-unequal-lb], we can achieve an optimal solution
for weighted HRW in [I-D.ietf-bess-evpn-unequal-lb] using the score
function as described in Section 4 above and obviating the need to
take bandwidth increments. It is an order of magnitude faster and
efficient and minimally disruptive.
7. Weighted HRW and its application to Resilient Hashing
With the exponential increase in the number of physical links used in
data centers, there is also the potential for an increase in the
number of failed physical links. In systems that employ static
hashing for load balancing flows across members of port channels or
Equal Cost Multipath (ECMP) groups, each flow is hashed to a link.
When a link fails, all flows including those that were previously
mapped to the non-failed links are rehashed across the remaining
working links. This causes packet reordering of flows that were in
fact not mapped to the link that failed. A similar rehashing with
packet re-ordering also happens when a link is added to the port
channel or Equal Cost Multipath (ECMP) group. With the ever
increasing number of physical links used in the data centers there
the possibility for increasing number of failed links only increases.
Hence the resilient hashing is very important.
However when the links are not of the same speed, Resilient hashing
for ECMP does not apply per-se. However, one can use the method
explained in Section 4 to achieve resilient hashing even in the
Unequal Cost Multipath (UCMP)case or when member links are of
different bandwidths.
8. Weighted HRW and its application to Multicast DR Election
[I-D.mankamana-pim-bdr]propose a mechanism to elect backup DR on a
shared LAN. A backup DR on LAN would be useful for faster
convergence. When the access bandwidth is different for the PIM
routers and we want to do a load balancing among the PIM routers for
DR/backup DR functionality with regards to the various (S,G) flow,
technique similar to Section 4 can be applied. The details of the
problem is out of the scope of the current draft and is being worked
on separately at this time.
Mohanty, et al. Expires September 12, 2019 [Page 7]
Internet-Draft Weighted HRW and its Applications March 2019
9. Protocol Considerations
A request needs to registered with IANA registry for the weighted HRW
EVPN DF Election Algorithm in the DF Alg field in the DF Election
Extended Community in draft
[I-D.ietf-bess-evpn-df-election-framework].
10. Operational Considerations
TBD.
11. Security Considerations
This document raises no new security issues for EVPN.
12. Acknowledgements
The authors would like to thank Shyam Sethuram and Peter Psenak for
useful discussions related to this draft.
13. References
13.1. Normative References
[HRW1999] Thaler, D. and C. Ravishankar, "Using Name-Based Mappings
to Increase Hit Rates", IEEE/ACM Transactions in
networking Volume 6 Issue 1, February 1998.
[I-D.ietf-bess-evpn-df-election-framework]
Rabadan, J., satyamoh@cisco.com, s., Sajassi, A., Drake,
J., Nagaraj, K., and S. Sathappan, "Framework for EVPN
Designated Forwarder Election Extensibility", draft-ietf-
bess-evpn-df-election-framework-09 (work in progress),
January 2019.
[I-D.ietf-bess-evpn-unequal-lb]
Malhotra, N., Sajassi, A., Rabadan, J., Drake, J.,
Lingala, A., and S. Thoria, "Weighted Multi-Path
Procedures for EVPN All-Active Multi-Homing", draft-ietf-
bess-evpn-unequal-lb-00 (work in progress), September
2018.
[I-D.ietf-idr-extcomm-iana]
Rosen, E. and Y. Rekhter, "IANA Registries for BGP
Extended Communities", draft-ietf-idr-extcomm-iana-02
(work in progress), December 2013.
Mohanty, et al. Expires September 12, 2019 [Page 8]
Internet-Draft Weighted HRW and its Applications March 2019
[I-D.ietf-idr-link-bandwidth]
Mohapatra, P. and R. Fernando, "BGP Link Bandwidth
Extended Community", draft-ietf-idr-link-bandwidth-07
(work in progress), March 2018.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A
Border Gateway Protocol 4 (BGP-4)", RFC 4271,
DOI 10.17487/RFC4271, January 2006,
<https://www.rfc-editor.org/info/rfc4271>.
[RFC7432] Sajassi, A., Ed., Aggarwal, R., Bitar, N., Isaac, A.,
Uttaro, J., Drake, J., and W. Henderickx, "BGP MPLS-Based
Ethernet VPN", RFC 7432, DOI 10.17487/RFC7432, February
2015, <https://www.rfc-editor.org/info/rfc7432>.
[WHRW] Resch, J., "New hashing Algorithms for Data Storage",
Storage Developer Conference 18, November 2015.
13.2. Informative References
[CARP] Valloppillil, V. and K. Ross, "Cache Array Routing
Protocol v1.1", IEEE/ACM Transactions in networking Volume
6 Issue 1, February 1998.
[CHASH] Karger, D., Lehman, E., Leighton, T., Panigrahy, R.,
Levine, M., and D. Lewin, "Consistent Hashing and Random
Trees: Distributed Caching Protocols for Relieving Hot
Spots on the World Wide Web", ACM Symposium on Theory of
Computing ACM Press New York, May 1997.
[CLRS2009]
Cormen, T., Leiserson, C., Rivest, R., and C. Stein,
"Introduction to Algorithms (3rd ed.)", MIT Press and
McGraw-Hill ISBN 0-262-03384-4., February 2009.
[DYNAMODB]
Decennia, G., Hastorun, D., Jampani, M., Kakulapati, G.,
Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall,
P., and W. Vogels, "Dynamo: Amazon's Highly Available Key-
value Store", SOSP 07, October 2007.
Mohanty, et al. Expires September 12, 2019 [Page 9]
Internet-Draft Weighted HRW and its Applications March 2019
[I-D.mankamana-pim-bdr]
mishra, m., "PIM Backup Designated Router Procedure",
draft-mankamana-pim-bdr-00 (work in progress), June 2018.
[I-D.mohanty-bess-ebgp-dmz]
satyamoh@cisco.com, s., Millisor, A., and A. Vayner,
"Cumulative DMZ Link Bandwidth and load-balancing", draft-
mohanty-bess-ebgp-dmz-00 (work in progress), March 2018.
[RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
Multicast Next-Hop Selection", RFC 2991,
DOI 10.17487/RFC2991, November 2000,
<https://www.rfc-editor.org/info/rfc2991>.
[RFC2992] Hopps, C., "Analysis of an Equal-Cost Multi-Path
Algorithm", RFC 2992, DOI 10.17487/RFC2992, November 2000,
<https://www.rfc-editor.org/info/rfc2992>.
Authors' Addresses
Satya Ranjan Mohanty
Cisco Systems, Inc.
225 West Tasman Drive
San Jose, CA 95134
USA
Email: satyamoh@cisco.com
Mankamana Misra
Cisco Systems, Inc.
170 W. Tasman Drive
San Jose, CA 95134
USA
Email: mankamis@cisco.com
Acee Lindem
Cisco Systems, Inc.
170 West Tasman Drive
San Jose, CA 95134
USA
Email: acee@cisco.com
Mohanty, et al. Expires September 12, 2019 [Page 10]
Internet-Draft Weighted HRW and its Applications March 2019
Ali Sajassi
Cisco Systems, Inc.
170 West Tasman Drive
San Jose, CA 95134
USA
Email: sajassi@cisco.com
Mohanty, et al. Expires September 12, 2019 [Page 11]