12 Mar
2012
12 Mar
'12
7:05 p.m.
Module: sip-router
Branch: master
Commit: d8fe0def83736c204dd1eace89e8ca1823704fc3
URL:
http://git.sip-router.org/cgi-bin/gitweb.cgi/sip-router/?a=commit;h=d8fe0de…
Author: Andrei Pelinescu-Onciul <andrei(a)iptel.org>
Committer: Andrei Pelinescu-Onciul <andrei(a)iptel.org>
Date: Fri Mar 9 19:12:59 2012 +0100
dns: srv load balancing distribution fix
The load distribution when doing SRV based load balancing was not
completely fair. The first listed server had always an extra
(sum_of_weights-weight)/(sum_of_weights*(sum_of_weights+1) chance
of being selected.
For example for 2 servers both with weight 50, the first one
will have an extra (100-50)/100*101 change of being selected =>
extra 0.495% which gives a 50.495% - 49.505% distribution
instead of 50% - 50%. For large weight values this doesn't make a big
difference (e.g. for 500-500 => 50.049% instead of 50%) but for
small values it becomes very noticeable (e.g. for 1-1 =>
66% - 33% distribution instead of 50%-50%).
The chance of selecting a 0-weight record was also changed. It was
1/(sum_of_weights+1) and now is 1/(sum_of_weights*1000).
Reported-by: Michal Matyska michal.matyska iptel org
---
dns_cache.c | 18 ++++++++++++++----
1 files changed, 14 insertions(+), 4 deletions(-)
diff --git a/dns_cache.c b/dns_cache.c
index da8f97d..1a7f1c5 100644
--- a/dns_cache.c
+++ b/dns_cache.c
@@ -100,6 +100,8 @@
#define DNS_HE_MAX_ADDR 10 /* maxium addresses returne in a hostent struct */
#define MAX_CNAME_CHAIN 10
#define SPACE_FORMAT " " /* format of view output */
+#define DNS_SRV_ZERO_W_CHANCE 1000 /* one in a 1000*weight_sum chance for
+ selecting a 0-weight record */
int dns_cache_init=1; /* if 0, the DNS cache is not initialized at startup */
static gen_lock_t* dns_hash_lock=0;
@@ -2286,6 +2288,7 @@ inline static struct dns_rr* dns_srv_get_nxt_rr(struct
dns_hash_entry* e,
unsigned rand_w;
int found;
int saved_idx;
+ int zero_weight; /* number of records with 0 weight */
int i, idx;
struct r_sums_entry{
unsigned r_sum;
@@ -2307,6 +2310,7 @@ retry:
prio=((struct srv_rdata*)start_grp->rdata)->priority;
sum=0;
saved_idx=-1;
+ zero_weight = 0;
found=0;
for (idx=0;rr && (prio==((struct srv_rdata*)rr->rdata)->priority)
&&
(idx < MAX_SRV_GRP_IDX); idx++, rr=rr->next){
@@ -2328,6 +2332,7 @@ retry:
if ((saved_idx==-1) || (((struct srv_rdata*)rr->rdata)->weight==0)){
saved_idx=idx;
}
+ zero_weight += (((struct srv_rdata*)rr->rdata)->weight == 0);
sum+=((struct srv_rdata*)rr->rdata)->weight;
r_sums[idx].r_sum=sum;
r_sums[idx].rr=rr;
@@ -2338,10 +2343,15 @@ retry:
n+=idx; /* next group start idx, last rr */
srv_reset_tried(tried);
goto retry;
- }else if ((found==1) || ((rand_w=dns_srv_random(sum))==0)){
- /* 1. if only one found, avoid a useless random() call or
- * 2. if rand_w==0, immediately select a 0 weight record if present,
- * or else the first record found
+ }else if ((found==1) || (sum==0) ||
+ (((rand_w=(dns_srv_random(sum-1)+1))==1) && zero_weight &&
+ (dns_srv_random(DNS_SRV_ZERO_W_CHANCE)==0))){
+ /* 1. if only one found, avoid a useless random() call
+ and select it (saved_idx will point to it).
+ * 2. if the sum of weights is 0 (all have 0 weight) or
+ * 3. rand_w==1 and there are records with 0 weight and
+ * random(probab. of selecting a 0-weight)
+ * immediately select a 0 weight record.
* (this takes care of the 0-weight at the beginning requirement) */
i=saved_idx; /* saved idx contains either first 0 weight or first
valid record */