Weighted HRW and its applications
draft-mohanty-bess-weighted-hrw-02
BESS Working Group S. Mohanty
Internet-Draft M. Misra
Intended status: Standards Track A. Lindem
Expires: June 11, 2021 A. Sajassi
Cisco Systems, Inc.
J. Drake
Juniper Networks, Inc.
December 08, 2020
Weighted HRW and its applications
draft-mohanty-bess-weighted-hrw-02
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 June 11, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
Mohanty, et al. Expires June 11, 2021 [Page 1]
Internet-Draft Weighted HRW and its Applications December 2020
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(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.
Show full document text