4. The Basic Neighbour Selection Process

Before we describe Squid features for hierarchical caching, we first briefly explain the neighbour selection process, aspects of which have motivated features described in the following section.

First, what does ``neighbour selection process'' refer to? When Squid is unable to satisfy a request from the cache (i.e. its a cache miss), Squid must decide where to forward the request next. There are basically three choices: a parent cache, a sibling cache, or the origin server. Squid uses ICP to make this decision.

1. Squid sends an ICP query message to its neighbours (both parents and siblings). The ICP query includes the requested URL and is sent in a UDP packet. Squid remembers how many queries it sends for a given request.
2. Each neighbour receives its ICP query and looks up the URL in its own cache. If a valid copy of the URL exists, the cache sends ICP_HIT, otherwise an ICP_MISS message.
3. The querying cache now collects the ICP replies from its peers. If the cache receives an ICP_HIT reply from a peer, it immediately forwards the HTTP request to that peer. If the cache does not receive an ICP_HIT reply, then all replies will be ICP_MISS. Squid waits until it receives all replies, up to two seconds. If one of the ICP_MISS replies comes from a parent, Squid forwards the request to the parent whose reply was the first to arrive. We call this reply the FIRST_PARENT_MISS. If there is no ICP_MISS from a parent cache, Squid forwards the request to the origin server.

We have described the basic algorithm, to which Squid offers numerous possible modifications, including mechanisms to:

1. Send ICP queries to some neighbours and not to others.
2. Include the origin server in the ICP ``pinging'' so that if the origin server reply arrives before any ICP_HITs, the request is forwarded there directly.
3. Disallow or require the use of some peers for certain requests.

We further describe these options below.