From d1b63fc8156f8f941cdd4d02ca478609e17927bb Mon Sep 17 00:00:00 2001
From: hno <>
Date: Sun, 23 Jun 2002 20:50:06 +0000
Subject: [PATCH] Peering enhancement options for satellite or other high
 latency links by Robert Cohen

---
 src/cache_cf.cc    |  9 ++++++-
 src/cf.data.pre    | 32 ++++++++++++++++++++++-
 src/defines.h      |  3 ++-
 src/neighbors.cc   | 64 +++++++++++++++++++++++++++++++++++++++++-----
 src/peer_select.cc | 12 ++++++---
 src/protos.h       |  3 ++-
 src/structs.h      |  6 ++++-
 7 files changed, 115 insertions(+), 14 deletions(-)

diff --git a/src/cache_cf.cc b/src/cache_cf.cc
index 86d2bc9803..e39c7387e8 100644
--- a/src/cache_cf.cc
+++ b/src/cache_cf.cc
@@ -1,6 +1,6 @@
 
 /*
- * $Id: cache_cf.cc,v 1.407 2002/04/13 23:07:49 hno Exp $
+ * $Id: cache_cf.cc,v 1.408 2002/06/23 14:50:06 hno Exp $
  *
  * DEBUG: section 3     Configuration File Parsing
  * AUTHOR: Harvest Derived
@@ -1435,6 +1435,7 @@ parse_peer(peer ** head)
     p->http_port = CACHE_HTTP_PORT;
     p->icp.port = CACHE_ICP_PORT;
     p->weight = 1;
+    p->basetime = 0;
     p->stats.logged_state = PEER_ALIVE;
     if ((token = strtok(NULL, w_space)) == NULL)
 	self_destruct();
@@ -1451,12 +1452,16 @@ parse_peer(peer ** head)
 	    p->options.proxy_only = 1;
 	} else if (!strcasecmp(token, "no-query")) {
 	    p->options.no_query = 1;
+	} else if (!strcasecmp(token, "background-ping")) {
+	    p->options.background_ping = 1;
 	} else if (!strcasecmp(token, "no-digest")) {
 	    p->options.no_digest = 1;
 	} else if (!strcasecmp(token, "multicast-responder")) {
 	    p->options.mcast_responder = 1;
 	} else if (!strncasecmp(token, "weight=", 7)) {
 	    p->weight = atoi(token + 7);
+	} else if (!strncasecmp(token, "basetime=", 9)) {
+	    p->basetime = atoi(token + 9);
 	} else if (!strcasecmp(token, "closest-only")) {
 	    p->options.closest_only = 1;
 	} else if (!strncasecmp(token, "ttl=", 4)) {
@@ -1469,6 +1474,8 @@ parse_peer(peer ** head)
 	    p->options.default_parent = 1;
 	} else if (!strcasecmp(token, "round-robin")) {
 	    p->options.roundrobin = 1;
+	} else if (!strcasecmp(token, "weighted-round-robin")) {
+	    p->options.weighted_roundrobin = 1;
 #if USE_HTCP
 	} else if (!strcasecmp(token, "htcp")) {
 	    p->options.htcp = 1;
diff --git a/src/cf.data.pre b/src/cf.data.pre
index 3d16e7d79f..2118cc6165 100644
--- a/src/cf.data.pre
+++ b/src/cf.data.pre
@@ -1,6 +1,6 @@
 
 #
-# $Id: cf.data.pre,v 1.264 2002/06/23 13:32:24 hno Exp $
+# $Id: cf.data.pre,v 1.265 2002/06/23 14:50:06 hno Exp $
 #
 #
 # SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -262,10 +262,13 @@ DOC_START
 
 	    options: proxy-only
 		     weight=n
+		     basetime=n
 		     ttl=n
 		     no-query
+		     background-ping
 		     default
 		     round-robin
+		     weighted-round-robin
 		     multicast-responder
 		     closest-only
 		     no-digest
@@ -284,6 +287,12 @@ DOC_START
 		     The weight must be an integer.  The default weight
 		     is 1, larger weights are favored more.
 
+		     use 'basetime=n' to specify a base amount to
+		     be subtracted from round trip times of parents.
+		     It is subtraced before devision by weight in calculating
+		     which parent to fectch from. If the rtt is less than the
+		     base time then the rtt is set to a minimal value.
+
 		     use 'ttl=n' to specify a IP multicast TTL to use
 		     when sending an ICP queries to this address.
 		     Only useful when sending to a multicast group.
@@ -294,6 +303,11 @@ DOC_START
 		     use 'no-query' to NOT send ICP queries to this
 		     neighbor.
 
+		     use 'background-ping' to only send ICP queries to this
+		     neighbor infrequently. This is used to keep the neighbor 
+		     round trip time updated and is usually used in 
+		     conjunction with weighted-round-robin.
+
 		     use 'default' if this is a parent cache which can
 		     be used as a "last-resort." You should probably
 		     only use 'default' in situations where you cannot
@@ -303,6 +317,12 @@ DOC_START
 		     should be used in a round-robin fashion in the
 		     absence of any ICP queries.
 
+		     use 'weighted-round-robin' to define a set of parents 
+		     which should be used in a round-robin fashion with the 
+		     frequency of each parent being based on the round trip 
+		     time. Closer parents are used more often. 
+		     Usually used for background-ping parents.
+
 		     'multicast-responder' indicates that the named peer
 		     is a member of a multicast group.  ICP queries will
 		     not be sent directly to the peer, but ICP replies
@@ -537,6 +557,16 @@ no_cache deny QUERY
 NOCOMMENT_END
 DOC_END
 
+NAME: background_ping_rate
+COMMENT: time-units
+TYPE: time_t
+DEFAULT: 10 seconds
+LOC: Config.backgroundPingRate
+DOC_START
+	Controls how often the ICP pings are sent to siblings that
+	have background-ping set.
+DOC_END
+
 
 COMMENT_START
  OPTIONS WHICH AFFECT THE CACHE SIZE
diff --git a/src/defines.h b/src/defines.h
index 64c80bf73e..e83e1840c7 100644
--- a/src/defines.h
+++ b/src/defines.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: defines.h,v 1.104 2002/06/21 12:58:20 hno Exp $
+ * $Id: defines.h,v 1.105 2002/06/23 14:50:07 hno Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -166,6 +166,7 @@
 
 #define PEER_MAX_ADDRESSES 10
 #define RTT_AV_FACTOR      50
+#define RTT_BACKGROUND_AV_FACTOR      25	/* Background pings need a smaller factor since they are sent less frequently */
 
 #define PEER_DEAD 0
 #define PEER_ALIVE 1
diff --git a/src/neighbors.cc b/src/neighbors.cc
index 0f6cd9d84f..088c31b943 100644
--- a/src/neighbors.cc
+++ b/src/neighbors.cc
@@ -1,6 +1,6 @@
 
 /*
- * $Id: neighbors.cc,v 1.301 2002/04/13 23:07:51 hno Exp $
+ * $Id: neighbors.cc,v 1.302 2002/06/23 14:50:07 hno Exp $
  *
  * DEBUG: section 15    Neighbor Routines
  * AUTHOR: Harvest Derived
@@ -171,6 +171,8 @@ peerWouldBePinged(const peer * p, request_t * request)
 	return 0;
     if (p->options.no_query)
 	return 0;
+    if (p->options.background_ping && (squid_curtime - p->stats.last_query < Config.backgroundPingRate))
+	return 0;
     if (p->options.mcast_responder)
 	return 0;
     if (p->n_addresses == 0)
@@ -185,8 +187,9 @@ peerWouldBePinged(const peer * p, request_t * request)
     /* Ping dead peers every timeout interval */
     if (squid_curtime - p->stats.last_query > Config.Timeout.deadPeer)
 	return 1;
-    if (!neighborUp(p))
-	return 0;
+    if (p->icp.port == echo_port)
+	if (!neighborUp(p))
+	    return 0;
     return 1;
 }
 
@@ -275,6 +278,43 @@ getRoundRobinParent(request_t * request)
     return q;
 }
 
+peer *
+getWeightedRoundRobinParent(request_t * request)
+{
+    peer *p;
+    peer *q = NULL;
+    int weighted_rtt;
+    for (p = Config.peers; p; p = p->next) {
+	if (!p->options.weighted_roundrobin)
+	    continue;
+	if (neighborType(p, request) != PEER_PARENT)
+	    continue;
+	if (!peerHTTPOkay(p, request))
+	    continue;
+	if (q && q->rr_count < p->rr_count)
+	    continue;
+	q = p;
+    }
+    if (q && q->rr_count > 1000000)
+	for (p = Config.peers; p; p = p->next) {
+	    if (!p->options.weighted_roundrobin)
+		continue;
+	    if (neighborType(p, request) != PEER_PARENT)
+		continue;
+	    p->rr_count = 0;
+	}
+    if (q) {
+	weighted_rtt = (q->stats.rtt - q->basetime) / q->weight;
+
+	if (weighted_rtt < 1)
+	    weighted_rtt = 1;
+	q->rr_count += weighted_rtt;
+	debug(15, 3) ("getWeightedRoundRobinParent: weighted_rtt %d\n", (int) weighted_rtt);
+    }
+    debug(15, 3) ("getWeightedRoundRobinParent: returning %s\n", q ? q->host : "NULL");
+    return q;
+}
+
 /* This gets called every 5 minutes to clear the round-robin counter. */
 void
 peerClearRR(void *data)
@@ -691,7 +731,7 @@ neighborAlive(peer * p, const MemObject * mem, const icp_common_t * header)
 static void
 neighborUpdateRtt(peer * p, MemObject * mem)
 {
-    int rtt;
+    int rtt, rtt_av_factor;
     if (!mem)
 	return;
     if (!mem->start_ping.tv_sec)
@@ -699,8 +739,11 @@ neighborUpdateRtt(peer * p, MemObject * mem)
     rtt = tvSubMsec(mem->start_ping, current_time);
     if (rtt < 1 || rtt > 10000)
 	return;
+    rtt_av_factor = RTT_AV_FACTOR;
+    if (p->options.weighted_roundrobin)
+	rtt_av_factor = RTT_BACKGROUND_AV_FACTOR;
     p->stats.rtt = intAverage(p->stats.rtt, rtt,
-	p->stats.pings_acked, RTT_AV_FACTOR);
+	p->stats.pings_acked, rtt_av_factor);
 }
 
 #if USE_HTCP
@@ -1184,6 +1227,8 @@ peerCountMcastPeersDone(void *data)
 static void
 peerCountHandleIcpReply(peer * p, peer_t type, protocol_t proto, void *hdrnotused, void *data)
 {
+    int rtt_av_factor;
+
     ps_state *psstate = data;
     StoreEntry *fake = psstate->entry;
     MemObject *mem = fake->mem_obj;
@@ -1192,7 +1237,10 @@ peerCountHandleIcpReply(peer * p, peer_t type, protocol_t proto, void *hdrnotuse
     assert(fake);
     assert(mem);
     psstate->ping.n_recv++;
-    p->stats.rtt = intAverage(p->stats.rtt, rtt, psstate->ping.n_recv, RTT_AV_FACTOR);
+    rtt_av_factor = RTT_AV_FACTOR;
+    if (p->options.weighted_roundrobin)
+	rtt_av_factor = RTT_BACKGROUND_AV_FACTOR;
+    p->stats.rtt = intAverage(p->stats.rtt, rtt, psstate->ping.n_recv, rtt_av_factor);
 }
 
 static void
@@ -1214,12 +1262,16 @@ dump_peer_options(StoreEntry * sentry, peer * p)
 	storeAppendPrintf(sentry, " proxy-only");
     if (p->options.no_query)
 	storeAppendPrintf(sentry, " no-query");
+    if (p->options.background_ping)
+	storeAppendPrintf(sentry, " background-ping");
     if (p->options.no_digest)
 	storeAppendPrintf(sentry, " no-digest");
     if (p->options.default_parent)
 	storeAppendPrintf(sentry, " default");
     if (p->options.roundrobin)
 	storeAppendPrintf(sentry, " round-robin");
+    if (p->options.weighted_roundrobin)
+	storeAppendPrintf(sentry, " weighted-round-robin");
     if (p->options.mcast_responder)
 	storeAppendPrintf(sentry, " multicast-responder");
     if (p->options.closest_only)
diff --git a/src/peer_select.cc b/src/peer_select.cc
index eea01106e3..5f94f24370 100644
--- a/src/peer_select.cc
+++ b/src/peer_select.cc
@@ -1,6 +1,6 @@
 
 /*
- * $Id: peer_select.cc,v 1.121 2002/04/13 23:07:51 hno Exp $
+ * $Id: peer_select.cc,v 1.122 2002/06/23 14:50:07 hno Exp $
  *
  * DEBUG: section 44    Peer Selection Algorithm
  * AUTHOR: Duane Wessels
@@ -445,6 +445,8 @@ peerGetSomeParent(ps_state * ps)
 #endif
     } else if ((p = getRoundRobinParent(request))) {
 	code = ROUNDROBIN_PARENT;
+    } else if ((p = getWeightedRoundRobinParent(request))) {
+	code = ROUNDROBIN_PARENT;
     } else if ((p = getFirstUpParent(request))) {
 	code = FIRSTUP_PARENT;
     } else if ((p = getAnyParent(request))) {
@@ -534,7 +536,9 @@ peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
     /* set FIRST_MISS if there is no CLOSEST parent */
     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 	return;
-    rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
+    rtt = (tvSubMsec(ps->ping.start, current_time) - p->basetime) / p->weight;
+    if (rtt < 1)
+	rtt = 1;
     if (ps->first_parent_miss.sin_addr.s_addr == any_addr.s_addr ||
 	rtt < ps->ping.w_rtt) {
 	ps->first_parent_miss = p->in_addr;
@@ -622,7 +626,9 @@ peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
     /* set FIRST_MISS if there is no CLOSEST parent */
     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 	return;
-    rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
+    rtt = (tvSubMsec(ps->ping.start, current_time) - p->basetime) / p->weight;
+    if (rtt < 1)
+	rtt = 1;
     if (ps->first_parent_miss.sin_addr.s_addr == any_addr.s_addr ||
 	rtt < ps->ping.w_rtt) {
 	ps->first_parent_miss = p->in_addr;
diff --git a/src/protos.h b/src/protos.h
index d9cc73cef4..32d1912e44 100644
--- a/src/protos.h
+++ b/src/protos.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: protos.h,v 1.440 2002/06/23 13:32:24 hno Exp $
+ * $Id: protos.h,v 1.441 2002/06/23 14:50:07 hno Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -664,6 +664,7 @@ extern peer *peerFindByName(const char *);
 extern peer *peerFindByNameAndPort(const char *, unsigned short);
 extern peer *getDefaultParent(request_t * request);
 extern peer *getRoundRobinParent(request_t * request);
+extern peer *getWeightedRoundRobinParent(request_t * request);
 EVH peerClearRR;
 extern peer *getAnyParent(request_t * request);
 extern lookup_t peerDigestLookup(peer * p, request_t * request);
diff --git a/src/structs.h b/src/structs.h
index c136d6d7b1..4b6f9c884e 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: structs.h,v 1.421 2002/06/23 13:32:25 hno Exp $
+ * $Id: structs.h,v 1.422 2002/06/23 14:50:07 hno Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -393,6 +393,7 @@ struct _SquidConfig {
     time_t negativeDnsTtl;
     time_t positiveDnsTtl;
     time_t shutdownLifetime;
+    time_t backgroundPingRate;
     struct {
 	time_t read;
 	time_t lifetime;
@@ -1264,9 +1265,11 @@ struct _peer {
     struct {
 	unsigned int proxy_only:1;
 	unsigned int no_query:1;
+	unsigned int background_ping:1;
 	unsigned int no_digest:1;
 	unsigned int default_parent:1;
 	unsigned int roundrobin:1;
+	unsigned int weighted_roundrobin:1;
 	unsigned int mcast_responder:1;
 	unsigned int closest_only:1;
 #if USE_HTCP
@@ -1282,6 +1285,7 @@ struct _peer {
 #endif
     } options;
     int weight;
+    int basetime;
     struct {
 	double avg_n_members;
 	int n_times_counted;
-- 
2.47.3