Blame view
net/netfilter/ipvs/ip_vs_sed.c
3.93 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 |
/* * IPVS: Shortest Expected Delay scheduling module * |
1da177e4c Linux-2.6.12-rc2 |
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
* Authors: Wensong Zhang <wensong@linuxvirtualserver.org> * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version * 2 of the License, or (at your option) any later version. * * 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 |
59c51591a Fix occurrences o... |
19 |
* jobs on the ith server and Ui is the fixed service rate (weight) of |
1da177e4c Linux-2.6.12-rc2 |
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
* 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 <marko@buuri.name> 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). * */ |
9aada7ac0 IPVS: use pr_fmt |
37 38 |
#define KMSG_COMPONENT "IPVS" #define pr_fmt(fmt) KMSG_COMPONENT ": " fmt |
1da177e4c Linux-2.6.12-rc2 |
39 40 41 42 |
#include <linux/module.h> #include <linux/kernel.h> #include <net/ip_vs.h> |
c16526a7b ipvs: fix overflo... |
43 |
static inline int |
1da177e4c Linux-2.6.12-rc2 |
44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
ip_vs_sed_dest_overhead(struct ip_vs_dest *dest) { /* * We only use the active connection number in the cost * calculation here. */ return atomic_read(&dest->activeconns) + 1; } /* * Weighted Least Connection scheduling */ static struct ip_vs_dest * |
bba54de5b ipvs: provide iph... |
58 59 |
ip_vs_sed_schedule(struct ip_vs_service *svc, const struct sk_buff *skb, struct ip_vs_iphdr *iph) |
1da177e4c Linux-2.6.12-rc2 |
60 61 |
{ struct ip_vs_dest *dest, *least; |
c16526a7b ipvs: fix overflo... |
62 |
int loh, doh; |
1da177e4c Linux-2.6.12-rc2 |
63 |
|
1e3e238e9 IPVS: use pr_err ... |
64 65 |
IP_VS_DBG(6, "%s(): Scheduling... ", __func__); |
1da177e4c Linux-2.6.12-rc2 |
66 67 68 69 70 71 72 73 74 75 76 77 78 |
/* * We calculate the load of each dest server as follows: * (server expected overhead) / dest->weight * * Remember -- no floats in kernel mode!!! * The comparison of h1*w2 > h2*w1 is equivalent to that of * h1/w1 > h2/w2 * if every weight is larger than zero. * * The server with weight=0 is quiesced and will not receive any * new connections. */ |
9be52aba7 ipvs: convert sed... |
79 |
list_for_each_entry_rcu(dest, &svc->destinations, n_list) { |
1da177e4c Linux-2.6.12-rc2 |
80 81 82 83 84 85 86 |
if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) && atomic_read(&dest->weight) > 0) { least = dest; loh = ip_vs_sed_dest_overhead(least); goto nextstage; } } |
41ac51eed ipvs: make "no de... |
87 |
ip_vs_scheduler_err(svc, "no destination available"); |
1da177e4c Linux-2.6.12-rc2 |
88 89 90 91 92 93 |
return NULL; /* * Find the destination with the least load. */ nextstage: |
9be52aba7 ipvs: convert sed... |
94 |
list_for_each_entry_continue_rcu(dest, &svc->destinations, n_list) { |
1da177e4c Linux-2.6.12-rc2 |
95 96 97 |
if (dest->flags & IP_VS_DEST_F_OVERLOAD) continue; doh = ip_vs_sed_dest_overhead(dest); |
c16526a7b ipvs: fix overflo... |
98 99 |
if ((__s64)loh * atomic_read(&dest->weight) > (__s64)doh * atomic_read(&least->weight)) { |
1da177e4c Linux-2.6.12-rc2 |
100 101 102 103 |
least = dest; loh = doh; } } |
b14198f6c IPVS: Add IPv6 su... |
104 105 106 |
IP_VS_DBG_BUF(6, "SED: server %s:%u " "activeconns %d refcnt %d weight %d overhead %d ", |
4d316f3f9 ipvs: use correct... |
107 108 |
IP_VS_DBG_ADDR(least->af, &least->addr), ntohs(least->port), |
b14198f6c IPVS: Add IPv6 su... |
109 110 111 |
atomic_read(&least->activeconns), atomic_read(&least->refcnt), atomic_read(&least->weight), loh); |
1da177e4c Linux-2.6.12-rc2 |
112 113 114 115 116 117 118 119 120 121 |
return least; } static struct ip_vs_scheduler ip_vs_sed_scheduler = { .name = "sed", .refcnt = ATOMIC_INIT(0), .module = THIS_MODULE, |
d149ccc9c ipvs: Initialize ... |
122 |
.n_list = LIST_HEAD_INIT(ip_vs_sed_scheduler.n_list), |
1da177e4c Linux-2.6.12-rc2 |
123 124 125 126 127 128 |
.schedule = ip_vs_sed_schedule, }; static int __init ip_vs_sed_init(void) { |
1da177e4c Linux-2.6.12-rc2 |
129 130 131 132 133 134 |
return register_ip_vs_scheduler(&ip_vs_sed_scheduler); } static void __exit ip_vs_sed_cleanup(void) { unregister_ip_vs_scheduler(&ip_vs_sed_scheduler); |
ceec4c381 ipvs: convert ser... |
135 |
synchronize_rcu(); |
1da177e4c Linux-2.6.12-rc2 |
136 137 138 139 140 |
} module_init(ip_vs_sed_init); module_exit(ip_vs_sed_cleanup); MODULE_LICENSE("GPL"); |