Next Previous Contents

6. Neighbour Selection Details

For this section, we'll examine the neighbour selection algorithm in detail by running through two functions from the Squid source code. Knowledge of C is not necessarily required.

There are two primary functions to examine. First, Squid calls protoDispatch() for all requests to decide if the URL's IP address must be learned. If not, Squid calls the second function, protoDispatchDNSHandle() directly. If it does need to look up the address, then protoDispatchDNSHandle() is called when the lookup completes.

Note that these functions have evolved considerably since the first Squid versions. As bugs have been pointed out, the code has been rearranged and rewritten in an attempt to accommodate everyone's needs.

6.1 Step One - Do we need to look up the IP address?

First we examine protoDispatch():

 343      protoData->inside_firewall = matchInsideFirewall(request->host);
 344      protoData->hierarchical = BIT_TEST(entry->flag, HIERARCHICAL) ? 1 : 0;
 345      protoData->single_parent = getSingleParent(request);
 346      protoData->default_parent = getDefaultParent(request);
 347      protoData->n_peers = neighboursCount(request);

Here we are assigning some variables for future reference. We check if the origin server is inside our firewall (based only on the domain names listed with inside_firewall). The request is `hierarchical' if it does not match the hierarchy_stoplist, and if the request method is GET. The `single_parent' will be set if the only peer to which this request could be forwarded is a parent cache. Similarly, the `default_parent' will be set to the first parent cache found with the default flag set. The `n_peers' variable indicates how many neighbour caches would be queried if we decide to use ICP later on. Note that getSingleParent(), getDefaultParent(), and neighboursCount() all use the domain restrictions (i.e. cache_host_domain).

 386      if (Config.firewall_ip_list) {
 387          /* Have to look up the url address so we can compare it */
 388          protoData->source_ping = Config.sourcePing;
 389          protoData->direct_fetch = DIRECT_MAYBE;
 390          protoData->ip_lookup_pending = 1;
 391          ipcache_nbgethostbyname(request->host,
 392              fd,
 393              protoDispatchDNSHandle,
 394              (void *) protoData);

The firewall configuration takes precedence over everything else. First we see if the firewall_ip directive is configured. If so, then we need to translate the URL hostname into an address before going any further. At this point we're not sure if we can directly connect to the origin server, so we set `direct_fetch' to maybe. The neighbour selection process will continue in the protoDispatchDNSHandle() function when the DNS lookup completes.

 395      } else if (!protoData->inside_firewall) {
 396          /* There are firewall restrictions, and this host is outside. */
 397          /* No DNS lookups, call protoDispatchDNSHandle() directly */
 398          protoData->source_ping = 0;
 399          protoData->direct_fetch = DIRECT_NO;
 400          protoDispatchDNSHandle(fd,
 401              NULL,
 402              (void *) protoData);

If we have reached this code segment then there is no firewall_ip list, but inside_firewall may still be configured. If we know the request is not inside the firewall, then we cannot contact the origin server directly. We must forward the request to a neighbour cache. We do not need to look up the IP address from the domain name. We call protoDispatchDNSHandle() directly to continue the process.

 403      } else if (matchLocalDomain(request->host) || !protoData->hierarchical) {
 404          /* will fetch from source */
 405          protoData->direct_fetch = DIRECT_YES;
 406          protoData->ip_lookup_pending = 1;
 407          ipcache_nbgethostbyname(request->host,
 408              fd,
 409              protoDispatchDNSHandle,
 410              (void *) protoData);

If the request matches the local_domain list, or if this is a non-hierarchical request, we will connect to the origin server directly. First we look up the IP address.

 411      } else if (protoData->n_peers == 0) {
 412          /* will fetch from source */
 413          protoData->direct_fetch = DIRECT_YES;
 414          protoData->ip_lookup_pending = 1;
 415          ipcache_nbgethostbyname(request->host,
 416              fd,
 417              protoDispatchDNSHandle,
 418              (void *) protoData);

Recall that above we counted the number of neighbours that we would query. If the result is zero, then we will directly connect to the origin server. The `n_peers' value will be zero if the domain restrictions do not yield any appropriate neighbours for this request, or if Squid thinks the neighbour caches are down. Below we describe how Squid decides if a neighbour is down.

 419      } else if (Config.local_ip_list) {
 420          /* Have to look up the url address so we can compare it */
 421          protoData->source_ping = Config.sourcePing;
 422          protoData->direct_fetch = DIRECT_MAYBE;
 423          protoData->ip_lookup_pending = 1;
 424          ipcache_nbgethostbyname(request->host,
 425              fd,
 426              protoDispatchDNSHandle,
 427              (void *) protoData);

Here we check the local_ip_list, if defined. Before calling protoDispatchDNSHandle() we need to look up the IP address.

 428      } else if (protoData->single_parent && Config.singleParentBypass &&
 429          !(protoData->source_ping = Config.sourcePing)) {
 430          /* will fetch from single parent */
 431          protoData->direct_fetch = DIRECT_MAYBE;
 432          protoDispatchDNSHandle(fd,
 433              NULL,
 434              (void *) protoData);

Here we look for the opportunity to use the `single parent' optimization. In order for this to be used, the only peer to which this request can be forwarded must be a parent, and the single_parent_bypass configuration option must be enabled. Additionally, we will not use this optimization if the source_ping feature is enabled. If these three conditions are true, we do not need to look up the IP address, so Squid calls protoDispatchDNSHandle() directly.

 435      } else {
 436          /* will use ping resolution */
 437          protoData->source_ping = Config.sourcePing;
 438          protoData->direct_fetch = DIRECT_MAYBE;
 439          protoData->ip_lookup_pending = 1;
 440          ipcache_nbgethostbyname(request->host,
 441              fd,
 442              protoDispatchDNSHandle,
 443              (void *) protoData);
 444      }

Finally, the last option is to query our neighbour caches with ICP. This decision actually occurs in protoDispatchDNSHandle(), but we need to look up the IP address here just in the event that we'll contact the origin server later on.

6.2 Step Two - Selecting the Next-Hop

Now we examine the protoDispatchDNSHandle() function, called after completion (successful or failed) of the IP address lookup, or if the lookup is unnecessary.

 186      if (protoData->direct_fetch == DIRECT_YES) {
 187          if (ia == NULL) {
 188              protoDNSError(protoData->fd, entry);
 189              return;
 190          }
 191          hierarchyNote(req, HIER_DIRECT, 0, req->host);
 192          protoStart(protoData->fd, entry, NULL, req);
 193          return;
 194      }

The variable `ia' holds the result of the DNS lookup. If we are supposed to directly connect to the origin server, and if the DNS lookup failed (indicated by `ia' being equal to NULL), then we cannot forward this request. If the DNS lookup was successful, then we call protoStart() to start the process of connecting to the server.

 195      if (protoData->direct_fetch == DIRECT_MAYBE
 196          && (Config.local_ip_list || Config.firewall_ip_list)) {
 197          if (ia == NULL) {
 198              debug(17, 3, "Unknown host: %s\n", req->host);
 199              protoData->direct_fetch = DIRECT_NO;
 200          } else if (Config.firewall_ip_list) {
 201              srv_addr = ia->in_addrs[ia->cur];
 202              if (ip_access_check(srv_addr, Config.firewall_ip_list) == IP_DENY) {
 203                  hierarchyNote(req, HIER_FIREWALL_IP_DIRECT, 0, req->host);
 204                  protoStart(protoData->fd, entry, NULL, req);
 205                  return;
 206              } else {
 215                  protoData->direct_fetch = DIRECT_NO;
 217              }
 218          } else if (Config.local_ip_list) {
 219              srv_addr = ia->in_addrs[ia->cur];
 220              if (ip_access_check(srv_addr, Config.local_ip_list) == IP_DENY) {
 221                  hierarchyNote(req, HIER_LOCAL_IP_DIRECT, 0, req->host);
 222                  protoStart(protoData->fd, entry, NULL, req);
 223                  return;
 224              }
 225          }
 226      }

This is where we check the origin server's IP address against the firewall_ip and local_ip lists. If the DNS lookup failed, then we set `direct_fetch' to no which requires that this request be forwarded to a neighbour cache if at all possible.

Otherwise, we first check the firewall_ip list. If the address matches the list then the origin server is inside the firewall, in which case we will make a direct connection. The firewall_ip list must be exhaustive. That is, if the IP address does not match the list, Squid assumes that the origin server is on the other side of the firewall. Again we set `direct_fetch' to no to require use of a neighbour cache.

If the address matches the local_ip list then we'll contact the origin server directly. If not, we continue:

 227      if ((e = protoData->single_parent) && Config.singleParentBypass) {
 228          /* Don't execute this block simply because direct == NO, we
 229           * might have some DOWN peers and still need to ping them */
 230          /* Only one parent for this host, and okay to skip pinging stuff */
 231          hierarchyNote(req, HIER_SINGLE_PARENT, 0, e->host);
 232          protoStart(protoData->fd, entry, e, req);
 233          return;
 234      }

Above we're using the single parent optimization if possible.

 235      if (protoData->n_peers == 0 && protoData->direct_fetch == DIRECT_NO) {
 236          if ((e = protoData->default_parent)) {
 237              hierarchyNote(req, HIER_DEFAULT_PARENT, 0, e->host);
 238              protoStart(protoData->fd, entry, e, req);
 239          } else if ((e = getFirstUpParent(protoData->request))) {
 240              hierarchyNote(req, HIER_FIRSTUP_PARENT, 0, e->host);
 241              protoStart(protoData->fd, entry, e, req);
 242          } else {
 243              hierarchyNote(req, HIER_NO_DIRECT_FAIL, 0, req->host);
 244              protoCantFetchObject(protoData->fd,
 245                  entry,
 246                  "No peers to query"
 247                  " and the host is beyond your firewall.");
 248          }
 249          return;
 250      }

Above, we have reached a code point where we cannot connect directly to the origin server, and there are no neighbours to query (`n_peers' == 0), so we must select a suitable parent cache. First we try a default parent. If one is not available, we'll take the first parent cache which Squid believes to be up. Otherwise, we generate an error message.

 251      if (!neighbours_do_private_keys && !protoData->hierarchical &&
 252          (e = getFirstUpParent(req))) {
 253          /* for private objects we should just fetch directly (because
 254           * icpHandleUdp() won't properly deal with the ICP replies). */
 255          hierarchyNote(req, HIER_FIRSTUP_PARENT, 0, e->host);
 256          protoStart(protoData->fd, entry, e, req);
 257          return;

This section of code Squid hopefully never uses anymore; it is called only when one of the neighbour caches does not support `private keys'. Squid can not use private keys if one of its neighbours is a Harvest-1.4 (or earlier) cache. Harvest-1.4 does not properly support the ICP Reqnum field which enables Squid to implement private cache keys.

 258      } else if (protoData->direct_fetch == DIRECT_MAYBE && ia
 259          && netdbHops(ia->in_addrs[ia->cur]) <= Config.minDirectHops) {
 260          hierarchyNote(req, HIER_DIRECT, 0, req->host);
 261          protoStart(protoData->fd, entry, NULL, req);
 262          return;

This is where we check the minimum_direct_hops parameter. If our estimated hops is less than or equal to this value, then we forward the request directly and skip any ICP queries.

 263      } else if (neighboursUdpPing(protoData)) {
 264          /* call neighbourUdpPing and start timeout routine */
 265          if (entry->ping_status != PING_NONE)
 266              fatal_dump("protoDispatchDNSHandle: bad ping_status");
 268          entry->ping_status = PING_WAITING;
 269          commSetSelect(protoData->fd,
 270              COMM_SELECT_TIMEOUT,
 271              (PF) getFromDefaultSource,
 272              (void *) entry,
 273              Config.neighbourTimeout);
 278          return;
 279      }

Here we call the routine which sends ICP queries. If neighboursUdpPing() returns zero, then it didn't really send any queries and we should continue execution of this function. Also note that here we start the two-second neighbour_timeout alarm.

 280      if ((e = protoData->default_parent)) {
 281          hierarchyNote(req, HIER_DEFAULT_PARENT, 0, e->host);
 282          protoStart(protoData->fd, entry, e, req);
 283      } else if ((e = getRoundRobinParent(req))) {
 284          hierarchyNote(req, HIER_ROUNDROBIN_PARENT, 0, e->host);
 285          protoStart(protoData->fd, entry, e, req);

If we reach this far, then we have not sent any ICP queries and it is time for desperate selection of an appropriate next-hop cache. If a default parent is defined, we'll take it. Otherwise, if a round-robin parent is defined we'll take that instead.

 286      } else if (protoData->direct_fetch == DIRECT_NO) {
 287          hierarchyNote(req, HIER_NO_DIRECT_FAIL, 0, req->host);
 288          protoCantFetchObject(protoData->fd, entry,
 289              "No neighbours or parents were queried "
 290              "and the host is beyond your firewall.");

At this point we have decided that none of the peer caches should receive this request. If we also have decided that this request cannot be forwarded to the origin server directly, then we generate an error message.

 291      } else if (ia == NULL) {
 292          protoDNSError(protoData->fd, entry);

Here we know that we are allowed to connect to the origin server, but if the IP address lookup has failed, then we must generate an error message.

 293      } else {
 294          hierarchyNote(req, HIER_DIRECT, 0, req->host);
 295          protoStart(protoData->fd, entry, NULL, req);
 296      }
 297  }

Finally, as a last resort, we have chosen to forward the request directly to the origin server and we have an IP address for it, so off we go with protoStart().

6.3 Up/Down Status

Squid tracks the reachability status of its neighbour caches. When using ICP, Squid marks a neighbour as down when the neighbour fails to reply to 20 consecutive ICP queries. As soon as a reply is received again, the neighbour is marked up.

In addition to ICP, Squid also monitors TCP connections. When a TCP connection to a neighbour fails, Squid marks the neighbour down and begins a process to periodically (every 80 seconds) retry a diagnostic TCP connection. When the diagnostic connection succeeds, the neighbour is marked up.

So, in order for Squid to consider a neighbour cache as up, these two conditions must be true:

  1. The last TCP connection must have been successful.
  2. There must be fewer than 20 consecutive unacknowledged ICP queries.

Next Previous Contents