CIP ( Common Indexing Protocol )

• CIP in the Information Retrieval World


• Information Retrieval in the Abstract
  In order to better understand how CIP fits into the information retrieval world, we need to first understand the unifying abstract features of existing information retrieval technology.
  
  An abstract view of the client/server data retrieval process includes data sets and data access protocols. An individual server is responsible for handling queries over a fixed domain of data. For the purposes of CIP, we call this domain of data the dataset. Clients make searches in the dataset and retrieve parts of it via a data access protocol. There are many data access protocols, each optimized for the data in question. For instance, LDAP and Whois++ are access protocols that reflect the needs of the directory services application domain. Other data access protocols include HTTP and Z39.50.



• Indexing Information Facilitates Query Routing
  The above description reflects a world without indexing, where no server knows about any other server. In some cases (as with X.500 referrals, and HTTP redirects) a server will, as part of its reply, implicate another server in the process of resolving the query. However, those servers generate replies based solely on their local knowledge. When indexing information is introduced into a server's local database, the server now knows not only answers based on the local dataset, but also answers based on external indices. These indices come from peer servers, via an indexing protocol. CIP is one such indexing protocol.



• Abstracting the CIP index object
  As useful as indices seem, the fact remains that not all queries can benefit from the same type of index. For example, say the index consists of a simple list of keywords. With such an index, it is impossible to answer queries about whether two keywords were near one another, or if a keyword was present in a certain context (for instance, in the title).



• Architectural Details
  CIP implements index passing, providing the forward knowledge necessary to generate the referrals used for query routing. The core of the protocol is the index object. In the following sections, the structure of the index objects themselves is presented. Next, how and why indices are passed from server to server is discussed. Finally, the circumstances under which a server may synthesize an index object based on incoming ones are discussed.



• The CIP Index Object
  A CIP index object is composed of two parts, the header and the payload. The header contains metadata necessary to process and make use of the index object being transmitted. The actual index resides in the payload.
  
  Three particular headers warrant specific mention at this point. The type of the index object selects one of many distinct CIP index object specifications which define exactly how the index blocks are to be created, parsed and used to facilitate query routing. Another header of note is the DSI (Dataset Identifier), which uniquely identifies the dataset from which the index was created. Another header that is crucial for generating referrals is the Base-URI. The URI (or URI's) contained in this header form the basis of any referrals generated based on this index block. The URI is also used as input during the index aggregation process to constrain the kinds of aggregation possible, due to multi protocol constraints. How that URI is used is defined by the aggregation algorithm. The exact syntax of these headers is specified in the CIP MIME specification document.



• Moving Index Objects: How to Build a Mesh
  Indices are transmitted among servers participating in a CIP mesh. By distributing this information in anticipation of a query, efficient, accurate query routing is possible at the time a query arrives.
  
  A CIP mesh is a set of CIP servers which pass indices of the same type among themselves. Typically, a mesh is arranged in a hierarchical tree fashion, with servers nearer the root of the tree having larger and more comprehensive indices. See Figure 1. However, a CIP mesh is explicitly allowed to have lateral links in it, and there may be more than one part of the mesh that has the properties of a "root". Mesh administrators are encouraged to avoid loops in the system, but they are not obliged to maintain a strict tree structure. Clients wishing to completely resolve all referrals they receive should protect against referral loops while attempting to traverse the mesh to avoid wasting time and network resources.




          base level           index servers           index servers 

          directory               for base             for lower-level 

           servers             level servers           index servers

                                             

                                                

           _______

          |       |

          |   A   |__

          |_______|              _______

                      ---CIP----|       |

           _______               |   D   |__

          |       |   /---CIP----|_______|               ------

          |   B   |__/                       --CIP------|      |

          |_______|                                      |  F   |

                                             /--CIP------|______|

                                            /

           _______                _______  /

          |       |              |       |-

          |   C   |-------CIP----|   E   |

          |_______|              |_______|-

                                      |    

                                      r     

           _______                    e                  ______

          |       |                   f       --CIP-----|      |

          |   G   |-------CIP---------e------------------|  H   |

          |_______|                   r                  |______|

                  --referral---|     r      --referral-/

                                |     a     |

                                |     l     |

                                 3   | 2   | 1

                                  --------/

                                 |        |

                                  | client |

                                  |        |

                                   --------



             Figure 1: Sample layout of the Index Service mesh



• Index Object Synthesis
  Indexing servers read and write index objects as they pass them around the mesh. However, a CIP server need not simply pass the in-bound indices through as the out-bound ones. While it is always permissible to pass an index object through to other servers, a server may choose to aggregate two or more of them, thereby reducing redundancy in the index, at the cost of longer referral chains.
  
  The following two rules control how a CIP server formulates its outgoing indices:


• An index server may pass any of the index objects in its local index and its in-bound indices through unchanged to polling servers.



• If and only if the following three conditions are true, an index server can aggregate two or more index objects into a single new index object, to be added to the set of out-bound indices.


a. Each index object to be aggregated covers exactly the same set of protocols, as defined by the scheme component of the Base- URI's in each index object.
b. The index server supports every one of the data access protocols represented by the Base-URI's in the index objects to be aggregated.
c. The specification for the index object type specified by the type header of the index objects explicitly defines the aggregation operation.

• The Referral
  The concept of a referral and the mechanism for deciding when they should be issued is described by CIP. However, the referral itself must be transferred to the client in the native protocol, so its syntax is not directly a CIP issue. The mechanism for deciding that a referral needs to be made and generating that referral resides in the CIP implementation in the server. The mechanism for sending the referral to the client resides in the server's native protocol implementation.
  
  A referral is made when a search against the index objects held by the server shows that there may be hits available in one of the datasets represented by those index objects. If more that one index object indicates that a referral must be generated to a given dataset, the server should generate only one referral to the given dataset, as the client may not be able to detect duplicates.
  
  Though the format of the referral is dependent on the native protocol(s) of the CIP server, the baseline contents of the referral are constant across all protocols. At the least, a DSI and a URI must be returned. The DSI is the DSI associated with the dataset which caused the hit. This must be presented to the client so that it can avoid referral loops. The Base-URI parameter which travels along with index objects is used to provide the other required part of a referral.



• Cross-protocol Mappings
  Each data access protocol which uses CIP will need a clearly defined set of rules to map queries in the native protocol to searches against an index object. These rules will vary according to the data domain. In principle, this could create a bit of a scaling difficulty; for N protocols and M data domains, there would be N x M mappings required. In practice, this should not be the case, since some access protocols will be wholly unsuited to some data domains. Consider for example, a LDAP server trying to make a search in an index object composed from unorganized text based pages.



• Moving through the mesh
  From a client's point of view, CIP simply pushes all the "hard work" onto its shoulders. After all, it is the client which needs to track down the real data. While this is true, it is very misleading. Because the client has control over the query routing process, the client has significant control over the size of the result set, the speed with which the query progresses, and the depth of the search.
  
  The simplest client implementation provides referrals to the user in a raw, ready-to-reuse form, without attempting to follow them. For instance, one Whois++ client, which interacts with the user via a Web-based form, simply makes referrals into HTML hypertext links. Encoded in the link via the HTML forms interface GET encoding rules is the data of the referral: the hostname, port, and query. If a user chooses to follow the referral link, he executes a new search on the new host. A savvier client might present the referrals to the user and ask which should be followed. And, assuming appropriate limits were placed on search time and bandwidth usage, it might be reasonable to program a client to follow all referrals automatically.

• The Stream Transport
  CIP messages are transmitted over bi-directional TCP connections via a simple text protocol. The transaction can take place over any TCP port, as specified by the mesh configuration. There is no well known port for CIP transactions. All configuration information in the system must include both a hostname and a port.
  
  All sender-CIP actions (including requests, connection initiation, and connection finalization) are acknowledged by the receiver-CIP with a response code.



• Internet mail infrastructure as transport
  As an alternative to TCP streams, CIP transactions can take place over the existing Internet mail infrastructure. There are two motivations for this feature of CIP. First, it lowers the barriers to entry for leaf servers. When the need for a full TCP implementation is relaxed, leaf nodes (which, by definition, only send index objects) can consist of as little as a database and an indexing program (possibly written in a very high level language) to participate in the mesh.
  
  Second, it keeps with the philosophy of making use of existing Internet technology. The MIME messages used for requests and responses are, by definition of the MIME specification, suitable for transport via the Internet mail infrastructure. With a few simple rules, we open up an entirely different way to interact with CIP servers which choose to implement this transport.



• HTTP transport
  HTTP may also be used to transport CIP objects, since they are just MIME objects. A transaction is performed by using the POST method to send an application/index.cmd and returning an application/index.response or an application/index.obj in the HTTP reply. The URL that is the target of the post is a configuration parameter of the CIP-sender to CIP-receiver relationship.

■ Parent layer
■ Child layer