linux/net/netfilter/ipvs/ip_vs_sed.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * IPVS:        Shortest Expected Delay scheduling module
 *
 * Authors:     Wensong Zhang <[email protected]>
 *
 * Changes:
 */

/*
 * The SED algorithm attempts to minimize each job's expected delay until
 * completion. The expected delay that the job will experience is
 * (Ci + 1) / Ui if sent to the ith server, in which Ci is the number of
 * jobs on the ith server and Ui is the fixed service rate (weight) of
 * the ith server. The SED algorithm adopts a greedy policy that each does
 * what is in its own best interest, i.e. to join the queue which would
 * minimize its expected delay of completion.
 *
 * See the following paper for more information:
 * A. Weinrib and S. Shenker, Greed is not enough: Adaptive load sharing
 * in large heterogeneous systems. In Proceedings IEEE INFOCOM'88,
 * pages 986-994, 1988.
 *
 * Thanks must go to Marko Buuri <[email protected]> for talking SED to me.
 *
 * The difference between SED and WLC is that SED includes the incoming
 * job in the cost function (the increment of 1). SED may outperform
 * WLC, while scheduling big jobs under larger heterogeneous systems
 * (the server weight varies a lot).
 *
 */

#define KMSG_COMPONENT …
#define pr_fmt(fmt) …

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

#include <net/ip_vs.h>


static inline int
ip_vs_sed_dest_overhead(struct ip_vs_dest *dest)
{ … }


/*
 *	Weighted Least Connection scheduling
 */
static struct ip_vs_dest *
ip_vs_sed_schedule(struct ip_vs_service *svc, const struct sk_buff *skb,
		   struct ip_vs_iphdr *iph)
{ … }


static struct ip_vs_scheduler ip_vs_sed_scheduler = …;


static int __init ip_vs_sed_init(void)
{ … }

static void __exit ip_vs_sed_cleanup(void)
{ … }

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