PATCH: modification to make better use of satellite bandwidth

I have developed some squid modifications based on what I need to make
btter use of a satellite circuit.
I though I'd make them available in case they are of more general
interest. If people show interest in them, I will make the effort to put
them up on a web page with more documentation etc.

We have a satellite circuit with RTT of about 500 millisec. We also have
a terrestrial connection. The satellite is fixed price bandwidth but we
pay by the meg for the terrestrial link.
So what I want to achieve is to use the satellite when possible and fall
over to the the landline when the satellite is overloaded.

The traditional squid setup for this would be to use squids on the other
side of each link as parents and weight them appropropriatly.
The downside with this is that it involves a ICP ping for each request.
The satellite latency is already high and an ICP ping for each request
doubles it.

The solution I have developed is as follows.

A background ping option for parents.
This sends an ICP ping to parents only occasionally (default 30 sec) to
keep the RTT info updated.

A Weighted Round Robin Option for parents.
This divides traffic between parents of this kind proportionally to
their weighted RTT. A parent with half the weighted RTT gets twice the
traffic.

The justification for the weighted round robin option is that using a
standard parent with a background ping option is inappropriate as the
"best" parent would get all the traffic until the next ping was sent.

I also have the problem that the existing weight option for parents
doesnt work well in these circumstances. I would have to set such a high
weight for the satellite that the difference between a slow satellite
link and a fast satellite link gets lost in the noise.
To address this, I added a basetime option for parents. This is
subtracted from the RTT before dividing by the weight when choosing
parents.

Here is the patch for my modifications. The patch is actually against
squid-2.2STABLE5 with the hno patches, but it drops cleanly into
squid-2.3STABLE2.
It seems to be working OK for me. Comments are welcome.

diff -ru squid-2.2.STABLE5-hno/src/cache_cf.c squid-local/src/cache_cf.c
--- squid-2.2.STABLE5-hno/src/cache_cf.c Mon Feb 21 18:08:39 2000
+++ squid-local/src/cache_cf.c Sun Apr 9 17:36:15 2000
@@ -985,6 +985,7 @@
     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();
@@ -1010,12 +1011,16 @@
             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)) {
@@ -1028,6 +1033,8 @@
             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 -ru squid-2.2.STABLE5-hno/src/cf.data.pre
squid-local/src/cf.data.pre
--- squid-2.2.STABLE5-hno/src/cf.data.pre Mon Feb 21 18:08:39 2000
+++ squid-local/src/cf.data.pre Sun Apr 9 18:20:16 2000
@@ -218,10 +218,13 @@
 
             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
@@ -238,6 +241,12 @@
                      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 request to this address.
                      Only useful when sending to a multicast group.
@@ -248,6 +257,11 @@
                      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
@@ -257,6 +271,12 @@
                      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
@@ -439,6 +459,17 @@
 
 acl QUERY urlpath_regex cgi-bin \?
 no_cache deny QUERY
+DOC_END
+
+NAME: background_ping_rate
+COMMENT: time-units
+TYPE: time_t
+DEFAULT: 30 seconds
+LOC: Config.backgroundPingRate
+DOC_START
+ Controls how often the ICP pings are sent to siblings that have
background-ping set.
+
+background_ping_rate 30 seconds
 DOC_END
 
 
diff -ru squid-2.2.STABLE5-hno/src/neighbors.c
squid-local/src/neighbors.c
--- squid-2.2.STABLE5-hno/src/neighbors.c Mon Feb 21 18:08:39 2000
+++ squid-local/src/neighbors.c Sun Apr 9 17:38:16 2000
@@ -161,6 +161,8 @@
         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)
@@ -289,6 +291,42 @@
 }
 
 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;
+}
+
+peer *
 getDefaultParent(request_t * request)
 {
     peer *p = NULL;
@@ -1208,12 +1246,16 @@
         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 -ru squid-2.2.STABLE5-hno/src/peer_select.c
squid-local/src/peer_select.c
--- squid-2.2.STABLE5-hno/src/peer_select.c Mon Feb 21 18:08:39 2000
+++ squid-local/src/peer_select.c Sun Apr 9 17:39:11 2000
@@ -445,6 +445,8 @@
         code = DEFAULT_PARENT;
     } 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,8 @@
     /* 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->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
         ps->first_parent_miss = p->in_addr;
         ps->ping.w_rtt = rtt;
@@ -622,7 +625,8 @@
     /* 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->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
         ps->first_parent_miss = p->in_addr;
         ps->ping.w_rtt = rtt;
diff -ru squid-2.2.STABLE5-hno/src/protos.h squid-local/src/protos.h
--- squid-2.2.STABLE5-hno/src/protos.h Mon Feb 21 18:08:39 2000
+++ squid-local/src/protos.h Sat Apr 8 22:23:03 2000
@@ -607,6 +607,7 @@
 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);
 extern peer *getAnyParent(request_t * request);
 extern lookup_t peerDigestLookup(peer * p, request_t * request,
StoreEntry * entry);
 extern peer *neighborsDigestSelect(request_t * request, StoreEntry *
entry);
Only in squid-local/src: squid.conf.local
diff -ru squid-2.2.STABLE5-hno/src/structs.h squid-local/src/structs.h
--- squid-2.2.STABLE5-hno/src/structs.h Mon Feb 21 18:08:39 2000
+++ squid-local/src/structs.h Sun Apr 9 17:37:36 2000
@@ -245,6 +245,7 @@
     time_t negativeDnsTtl;
     time_t positiveDnsTtl;
     time_t shutdownLifetime;
+ time_t backgroundPingRate;
     struct {
         time_t read;
         time_t lifetime;
@@ -1036,9 +1037,11 @@
     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
@@ -1051,6 +1054,7 @@
         unsigned int allow_miss:1;
     } options;
     int weight;
+ int basetime;
     struct {
         double avg_n_members;
         int n_times_counted;

--
Robert Cohen
Apex Internet