This patch is generated from the rttpeer branch of HEAD in squid Tue Aug 17 18:58:44 2004 GMT See http://devel.squid-cache.org/ Index: squid/src/cf.data.pre diff -u squid/src/cf.data.pre:1.78 squid/src/cf.data.pre:1.78.4.1 --- squid/src/cf.data.pre:1.78 Wed Aug 28 14:45:43 2002 +++ squid/src/cf.data.pre Sun Sep 1 07:18:43 2002 @@ -2795,6 +2795,24 @@ which are no more than this many rtt milliseconds away. DOC_END +NAME: minimum_direct_rtt_diff +TYPE: int +DEFAULT: 15 +LOC: Config.minDirectRttDiff +DOC_START + If using the ICMP pinging stuff, do direct fetches for sites + which difference of RTT are no more than this many rtt milliseconds away. + The Difference of RTT is the difference between SOURCE RTT and PARENT FULL RTT(OR PARENT RTT when HIT). +DOC_END + +NAME: minimum_fast_peer_rtt +TYPE: int +DEFAULT: 90 +LOC: Config.minFastPeerRtt +DOC_START + if 0 < neighbor's RTT <= minimum_fast_peer_rtt, we consider this neighbor is the FAST neighbor. +DOC_END + NAME: cachemgr_passwd TYPE: cachemgrpasswd DEFAULT: none Index: squid/src/neighbors.c diff -u squid/src/neighbors.c:1.19 squid/src/neighbors.c:1.19.4.1 --- squid/src/neighbors.c:1.19 Wed Aug 28 14:45:44 2002 +++ squid/src/neighbors.c Sun Sep 1 07:18:44 2002 @@ -682,7 +682,7 @@ choice_count++; if (lookup == LOOKUP_MISS) continue; - p_rtt = netdbHostRtt(p->host); + p_rtt = p->stats.rtt; /* Change here! use RTT from local cache to peer when Cache Digest Hit, rather than RTT from parent cache to destination*/ debug(15, 5) ("neighborsDigestSelect: peer %s rtt: %d\n", p->host, p_rtt); /* is this peer better than others in terms of rtt ? */ @@ -1438,3 +1438,27 @@ mem->ping_reply_callback(p, ntype, PROTO_HTCP, htcp, mem->ircb_data); } #endif + +peer * +getFastUpParent(request_t * request) +{ /* This NEW public function perform getting the fastest Up Parent according to Parent's RTT */ + peer *p = NULL, *p_min = NULL; + int rtt_min = 0; + + for (p = Config.peers; p; p = p->next) { + if (!neighborUp(p)) + continue; + if (neighborType(p, request) != PEER_PARENT) + continue; + if (!peerHTTPOkay(p, request)) + continue; + if (p->stats.rtt == 0) + continue; + + if (p->stats.rtt < rtt_min || rtt_min == 0) { + rtt_min = p->stats.rtt; /* get New Parent Peer with minimum RTT */ + p_min = p; + } + } + return p_min; +} \ No newline at end of file Index: squid/src/net_db.c diff -u squid/src/net_db.c:1.15 squid/src/net_db.c:1.15.8.1 --- squid/src/net_db.c:1.15 Wed Jun 26 10:28:32 2002 +++ squid/src/net_db.c Sun Sep 1 07:18:44 2002 @@ -1091,11 +1091,13 @@ netdbClosestParent(request_t * request) { #if USE_ICMP - peer *p = NULL; + peer *p = NULL, *p_min_rtt = NULL; netdbEntry *n; const ipcache_addrs *ia; net_db_peer *h; int i; + double rtt_min = 0, hops_min, full_rtt; + n = netdbLookupHost(request->host); if (NULL == n) { /* try IP addr */ @@ -1108,24 +1110,60 @@ if (0 == n->n_peers) return NULL; /* - * Find the parent with the least RTT to the origin server. + * Find the parent with the least FULL RTT to the origin server. * Make sure we don't return a parent who is farther away than * we are. Note, the n->peers list is pre-sorted by RTT. */ for (i = 0; i < n->n_peers; i++) { h = &n->peers[i]; - if (n->rtt > 0) - if (n->rtt < h->rtt) - break; p = peerFindByName(h->peername); if (NULL == p) /* not found */ continue; + if (p->stats.logged_state == PEER_DEAD) continue; /* a dead cache peer cannot be chosen */ if (neighborType(p, request) != PEER_PARENT) continue; if (!peerHTTPOkay(p, request)) /* not allowed */ continue; - return p; + if (p->stats.rtt == 0) continue; /* cache peer RTT cannot be 0*/ + + full_rtt = p->stats.rtt + h->rtt; /* Note: full_rtt is always greater than Zero */ + if (rtt_min && full_rtt > rtt_min) continue; /* cache peer FULL RTT is not minimum, search again*/ + if (full_rtt == rtt_min) /* Peer with least hops is preferable, if both FULL RTT are equal */ + if (h->hops >= hops_min) continue; + + rtt_min = full_rtt; /* we get the NEW minimum FULL RTT */ + hops_min = h->hops; /* we get new hops to source site */ + p_min_rtt = p; /* we get the NEW peer with minimum FULL RTT */ } -#endif + return p_min_rtt; /* choose the closest cache peer*/ +#else return NULL; +#endif +} + +int +netdbRtt(struct in_addr addr) +{ /* Add New Public Function in net_db.c,it allow look up Host RTT by IP Address in Network DB*/ +#if USE_ICMP + netdbEntry *n = netdbLookupAddr(addr); + if (n) { + n->last_use_time = squid_curtime; + return (int) (n->rtt + 0.5); + } +#endif + return 0; +} + +int +netdbPeerRtt(struct in_addr addr, peer * p) +{ /* Add New Public Function in net_db.c,it allow look up Peer RTT by Host's IP Address in Network DB*/ +#if USE_ICMP + const netdbEntry *n = netdbLookupAddr(addr); + if (n) { + const net_db_peer *np = netdbPeerByName(n, p->host); + if (np && np->expires >= squid_curtime) + return (int) (np->rtt + 0.5); + } +#endif + return 0; } Index: squid/src/peer_select.c diff -u squid/src/peer_select.c:1.15 squid/src/peer_select.c:1.15.8.1 --- squid/src/peer_select.c:1.15 Sun Jun 23 07:57:13 2002 +++ squid/src/peer_select.c Sun Sep 1 07:18:44 2002 @@ -85,6 +85,7 @@ static void peerHandleHtcpReply(peer *, peer_t, htcpReplyData *, void *); #endif static int peerCheckNetdbDirect(ps_state * psstate); +static int peerCheckNetdbDirectAgain(ps_state *, peer*, hier_code); static void peerGetSomeNeighbor(ps_state *); static void peerGetSomeNeighborReplies(ps_state *); static void peerGetSomeDirect(ps_state *); @@ -233,6 +234,83 @@ return 0; } +static int +peerCheckNetdbDirectAgain(ps_state * ps, peer* p, hier_code code) +{/* Check netdb again to make sure: whether peer is faster than direct access or not + Note: This function cannot be used for DIRECT_YES */ + request_t *request = ps->request; + int n_rtt, h_rtt, full_rtt; + const ipcache_addrs *ia; + if (ps->direct == DIRECT_MAYBE) { + if (p->stats.logged_state == PEER_DEAD) return 1; + n_rtt = netdbHostRtt(request->host); + if (n_rtt == 0) { /* try IP addr again */ + ia = ipcache_gethostbyname(request->host, 0); + if (NULL != ia) n_rtt = netdbRtt(ia->in_addrs[ia->cur]); + } + + if (n_rtt) { + switch (code) { + case CLOSEST_PARENT: + case CLOSEST_PARENT_MISS: + case FIRST_PARENT_MISS: + case SOURCE_FASTEST: + h_rtt = netdbHostPeerRtt(request->host, p); + if (h_rtt == 0) { /* try IP addr again */ + ia = ipcache_gethostbyname(request->host, 0); + if (NULL != ia) h_rtt = netdbPeerRtt(ia->in_addrs[ia->cur], p); + } + full_rtt = p->stats.rtt + h_rtt; + if (n_rtt <= full_rtt) + return 1; /* DIRECT ACCESS is preferable, by comparing FULL RTT with DIRECT RTT, and the smaller one will be preferable. */ + if (full_rtt == 0) { /* Squid just start up AND no RTT data is found in netdb */ + if (Config.onoff.prefer_direct) return 1; + } else if ((n_rtt - full_rtt) <= Config.minDirectRttDiff) + return 1; /* the difference is small enough to access source directly */ + else if (h_rtt == 0 || p->stats.rtt == 0) /* full_rtt is actually HALF RTT, DIRECT ACCESS is preferable by Cache Administrator */ + if (Config.onoff.prefer_direct) return 1; + break; + case CD_PARENT_HIT: + case CD_SIBLING_HIT: + case PARENT_HIT: + case SIBLING_HIT: + if (n_rtt <= p->stats.rtt) + return 1; /* DIRECT ACCESS is preferable, by comparing Peer RTT with DIRECT RTT, the smaller one will be preferable */ + if (p->stats.rtt == 0) { /* Squid just start up */ + if (Config.onoff.prefer_direct) return 1; /* DIRECT ACCESS is preferable by Cache Administrator */ + } else if ((n_rtt - p->stats.rtt) <= Config.minDirectRttDiff) + return 1; /* the difference is small enough to access source directly */ + default: + } + } else { /* when n_rtt == 0 , there are three reasons: 1. network is not reachable. 2. network admin of destination shut down ICMP echo. 3. no record is found in netdb */ + switch (code) { + case CLOSEST_PARENT: + case CLOSEST_PARENT_MISS: + case FIRST_PARENT_MISS: + case SOURCE_FASTEST: + h_rtt = netdbHostPeerRtt(request->host, p); + if (h_rtt == 0) { /* try IP addr again */ + ia = ipcache_gethostbyname(request->host, 0); + if (NULL != ia) h_rtt = netdbPeerRtt(ia->in_addrs[ia->cur], p); + } + if (h_rtt == 0) + if (Config.onoff.prefer_direct) + return 1; /* DIRECT ACCESS is preferable by Cache Administrator. */ + break; + case CD_PARENT_HIT: + case CD_SIBLING_HIT: + case PARENT_HIT: + case SIBLING_HIT: + if (p->stats.rtt == 0 || p->stats.rtt > Config.minFastPeerRtt) + if (Config.onoff.prefer_direct) + return 1; /* If this HIT peer is not fast enough, DIRECT ACCESS is preferable by Cache Administrator */ + default: + } + } + } + return 0; +} + static void peerSelectFoo(ps_state * ps) { @@ -293,12 +371,22 @@ peerGetAllParents(ps); break; default: - if (Config.onoff.prefer_direct) - peerGetSomeDirect(ps); + if (Config.onoff.prefer_direct) { + if (ps->servers) { /* avoid add DIRECT forward twice */ + if (ps->servers->code != CLOSEST_DIRECT) + peerGetSomeDirect(ps); + } + else peerGetSomeDirect(ps); + } if (request->flags.hierarchical || !Config.onoff.nonhierarchical_direct) peerGetSomeParent(ps); - if (!Config.onoff.prefer_direct) - peerGetSomeDirect(ps); + if (!Config.onoff.prefer_direct) { + if (ps->servers) { /* avoid add DIRECT forward twice */ + if (ps->servers->code != CLOSEST_DIRECT) + peerGetSomeDirect(ps); + } + else peerGetSomeDirect(ps); + } break; } peerSelectCallback(ps); @@ -361,6 +449,13 @@ } if (code != HIER_NONE) { assert(p); + if (ps->direct == DIRECT_MAYBE + #if USE_CARP + && code != CARP + #endif + ) + if (peerCheckNetdbDirectAgain(ps, p, code)) + peerAddFwdServer(&ps->servers, NULL, CLOSEST_DIRECT); /* Try Direct access First if possible*/ debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host); peerAddFwdServer(&ps->servers, p, code); } @@ -402,6 +497,9 @@ code = FIRST_PARENT_MISS; } if (p && code != HIER_NONE) { + if (ps->direct == DIRECT_MAYBE) + if (peerCheckNetdbDirectAgain(ps, p, code)) + peerAddFwdServer(&ps->servers, NULL, CLOSEST_DIRECT); /* try Direct Access First */ debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host); peerAddFwdServer(&ps->servers, p, code); } @@ -432,6 +530,8 @@ peer *p; request_t *request = ps->request; hier_code code = HIER_NONE; + int n_rtt; + const ipcache_addrs *ia; debug(44, 3) ("peerGetSomeParent: %s %s\n", RequestMethodStr[request->method], request->host); @@ -447,12 +547,29 @@ code = ROUNDROBIN_PARENT; } else if ((p = getWeightedRoundRobinParent(request))) { code = ROUNDROBIN_PARENT; + } else if ((p = getFastUpParent(request))) { + code = CLOSEST_PARENT; /* the Fastest Parent we found */ } else if ((p = getFirstUpParent(request))) { code = FIRSTUP_PARENT; } else if ((p = getAnyParent(request))) { code = ANY_OLD_PARENT; } if (code != HIER_NONE) { + if (ps->direct == DIRECT_MAYBE) + if (!ps->servers) { + /* Foward list is NULL, check which is better ? DIRECT ACCESS or Parent Peer*/ + n_rtt = netdbHostRtt(request->host); + if (n_rtt == 0) { /* try IP addr again */ + ia = ipcache_gethostbyname(request->host, 0); + if (NULL != ia) n_rtt = netdbRtt(ia->in_addrs[ia->cur]); + } + if (n_rtt) { + if (n_rtt <= p->stats.rtt) + peerAddFwdServer(&ps->servers, NULL, CLOSEST_DIRECT); /* DIRECT ACCESS is the First option*/ + else if (p->stats.rtt && (n_rtt - p->stats.rtt) <= Config.minDirectRttDiff) + peerAddFwdServer(&ps->servers, NULL, CLOSEST_DIRECT); /* DIRECT ACCESS is the First option*/ + } + } debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host); peerAddFwdServer(&ps->servers, p, code); } Index: squid/src/protos.h diff -u squid/src/protos.h:1.59 squid/src/protos.h:1.59.8.1 --- squid/src/protos.h:1.59 Sat Jul 20 05:33:16 2002 +++ squid/src/protos.h Sun Sep 1 07:18:44 2002 @@ -644,7 +644,7 @@ /* Labels for hierachical log file */ /* put them all here for easier reference when writing a logfile analyzer */ - +extern peer *getFastUpParent(request_t *); extern peer *getFirstPeer(void); extern peer *getFirstUpParent(request_t *); extern peer *getNextPeer(peer *); @@ -689,6 +689,8 @@ extern void netdbPingSite(const char *hostname); extern void netdbDump(StoreEntry *); extern int netdbHops(struct in_addr); +extern int netdbRtt(struct in_addr); +extern int netdbPeerRtt(struct in_addr, peer *); extern void netdbFreeMemory(void); extern int netdbHostHops(const char *host); extern int netdbHostRtt(const char *host); Index: squid/src/structs.h diff -u squid/src/structs.h:1.64 squid/src/structs.h:1.64.4.1 --- squid/src/structs.h:1.64 Wed Aug 28 14:45:44 2002 +++ squid/src/structs.h Sun Sep 1 07:18:44 2002 @@ -535,6 +535,8 @@ } fqdncache; int minDirectHops; int minDirectRtt; + int minDirectRttDiff; /* minimum difference between SOURCE RTT and FULL RTT(OR parent RTT) */ + int minFastPeerRtt; cachemgr_passwd *passwd_list; struct { int objectsPerBucket;