Implements the Google's Maglev hashing algorithm as a IPVS scheduler. Basically it provides consistent hashing but offers some special features about disruption and load balancing. 1) minimal disruption: when the set of destinations changes, a connection will likely be sent to the same destination as it was before. 2) load balancing: each destination will receive an almost equal number of connections. Seel also: [3.4 Consistent Hasing] in https://static.googleusercontent.com/media/research.google.com/ko//pubs/archive/44824.pdf v2: Add and refactor some features about MH and attach distribution test results based on the MH's realtive weights. I ran test program that pushes bunch of IP[:PORT] values via MH's realtive weights algorithm. The test program overview is: - Send 1000 packet requests in test program per different weights test case. - Use same ip address and different ports per packet requests. - IP_VS_MH_TAB_SIZE(prime number, M) is 4093. - Use the highest 6 bits when the weight is very huge. - It depends on IP_VS_MH_TAB_BITS. The results are below. 1. All same weights. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32906 Masq 1 0 236 -> 10.105.181.70:32907 Masq 1 0 231 -> 10.105.181.70:32908 Masq 1 0 254 -> 10.105.181.70:32909 Masq 1 0 239 2. Relative weigths. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32914 Masq 1 0 88 -> 10.105.181.70:32915 Masq 2 0 212 -> 10.105.181.70:32916 Masq 3 0 296 -> 10.105.181.70:32917 Masq 4 0 364 3. Realtive weights with zero weight. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32947 Masq 1 0 92 -> 10.105.181.70:32948 Masq 2 0 187 -> 10.105.181.70:32949 Masq 3 0 280 -> 10.105.181.70:32950 Masq 4 0 401 -> 10.105.181.70:32951 Masq 0 0 0 3-1. Turn a destination with zero weight to 5. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32947 Masq 1 0 57 -> 10.105.181.70:32948 Masq 2 0 121 -> 10.105.181.70:32949 Masq 3 0 200 -> 10.105.181.70:32950 Masq 4 0 245 -> 10.105.181.70:32951 Masq 5 0 337 4. Divided all weights with gcd. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32926 Masq 10 0 27 -> 10.105.181.70:32927 Masq 20 0 55 -> 10.105.181.70:32928 Masq 30 0 61 -> 10.105.181.70:32929 Masq 40 0 106 -> 10.105.181.70:32930 Masq 50 0 145 -> 10.105.181.70:32931 Masq 60 0 162 -> 10.105.181.70:32932 Masq 70 0 194 -> 10.105.181.70:32933 Masq 80 0 210 5. Can not divided weights with gcd. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32934 Masq 15 0 128 -> 10.105.181.70:32935 Masq 31 0 284 -> 10.105.181.70:32936 Masq 63 0 548 6. Huge weights(each weight > M=4093). IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32937 Masq 5000 0 326 -> 10.105.181.70:32938 Masq 5000 0 331 -> 10.105.181.70:32939 Masq 5000 0 303 7. Gcd is not working with one huge weight. IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32940 Masq 64 0 31 -> 10.105.181.70:32941 Masq 127 0 55 -> 10.105.181.70:32942 Masq 2000 0 874 8. Gcd is not working and all weights are bigger then M(=4093). IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 10.105.181.70:80 mh (flag-1,flag-2) -> 10.105.181.70:32943 Masq 4127 0 128 -> 10.105.181.70:32945 Masq 8191 0 269 -> 10.105.181.70:32946 Masq 16381 0 563 Inju Song (3): netfilter: ipvs: Add some configuration of Maglev hashing. netfilter: ipvs: Keep latest weight of destination. netfilter: ipvs: Refactor Maglev hashing scheduler include/net/ip_vs.h | 1 + net/netfilter/ipvs/Kconfig | 37 ++++++ net/netfilter/ipvs/Makefile | 1 + net/netfilter/ipvs/ip_vs_ctl.c | 4 + net/netfilter/ipvs/ip_vs_mh.c | 291 +++++++++++++++++++++++++---------------- 5 files changed, 221 insertions(+), 113 deletions(-) -- 1.8.3.1 -- Inju Song NAVER Corporation -- To unsubscribe from this list: send the line "unsubscribe lvs-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
