Upon receipt of a query for a key K, there are three basic cases to consider. In each of the cases, the node updates its popularity measure for K and sets the appropriate bit in the interest bit vector for K if the query originates from a neighbor. Otherwise, if the query is from a local client, the node maintains the connection until it can return a fresh answer to the client. To simplify the protocol description we use the phrase ``push the query'' to indicate that a node pushes a query upstream toward the authority node. We use the phrase ``push the update'' to indicate that a node pushes an update downstream in the direction of the reverse query path.
Case 1: Fresh Entries for key K are cached. The node uses its cached entries for K to push the response to the querying neighbor or local client.
Case 2: Key K is not in cache. The node adds K to its cache and marks it with a Pending-Response flag. The flag's purpose is to coalesce bursts of queries for K into one query. A subsequent query for K will be suppressed since the node is already awaiting the response for the first query of the burst. Query coalescing results in significant network savings, for both PCX and CUP. In some of the workloads we evaluate, coalesced queries can form up to 90 percent of the total number of queries that miss.
With every query push, a timer is set so that if the query response is delayed, the node pushes up another query.
Case 3: All cached entries for key K have expired. The node must obtain the fresh index entries for K. If the Pending-Response flag is set, the node does not need to push the query; otherwise, the node sets the flag and pushes the query.