linux/net/netfilter/ipvs/ip_vs_twos.c

// SPDX-License-Identifier: GPL-2.0-or-later
/* IPVS:        Power of Twos Choice Scheduling module
 *
 * Authors:     Darby Payne <[email protected]>
 */

#define KMSG_COMPONENT …
#define pr_fmt(fmt) …

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/random.h>

#include <net/ip_vs.h>

/*    Power of Twos Choice scheduling, algorithm originally described by
 *    Michael Mitzenmacher.
 *
 *    Randomly picks two destinations and picks the one with the least
 *    amount of connections
 *
 *    The algorithm calculates a few variables
 *    - total_weight = sum of all weights
 *    - rweight1 = random number between [0,total_weight]
 *    - rweight2 = random number between [0,total_weight]
 *
 *    For each destination
 *      decrement rweight1 and rweight2 by the destination weight
 *      pick choice1 when rweight1 is <= 0
 *      pick choice2 when rweight2 is <= 0
 *
 *    Return choice2 if choice2 has less connections than choice 1 normalized
 *    by weight
 *
 * References
 * ----------
 *
 * [Mitzenmacher 2016]
 *    The Power of Two Random Choices: A Survey of Techniques and Results
 *    Michael Mitzenmacher, Andrea W. Richa y, Ramesh Sitaraman
 *    http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/twosurvey.pdf
 *
 */
static struct ip_vs_dest *ip_vs_twos_schedule(struct ip_vs_service *svc,
					      const struct sk_buff *skb,
					      struct ip_vs_iphdr *iph)
{ … }

static struct ip_vs_scheduler ip_vs_twos_scheduler = …;

static int __init ip_vs_twos_init(void)
{ … }

static void __exit ip_vs_twos_cleanup(void)
{ … }

module_init(…) …;
module_exit(ip_vs_twos_cleanup);
MODULE_LICENSE(…) …;
MODULE_DESCRIPTION(…) …;