Caching provenance information

This invention was made with Government support under Contract No.: W911NF-09-2-0053 awarded by Army Research Office (ARO). The Government has certain rights in this invention.

FIELD OF THE INVENTION

The present invention relates generally to information systems and, more particularly, to techniques for caching provenance information.

BACKGROUND OF THE INVENTION

Information systems are computer-based systems that obtain, process, store and/or output various forms of data depending on the purpose of the system. Users rely on information systems every day to provide accurate data for critical and non-critical purposes.

One example might involve a doctor or other health professional requesting a patient record from a hospital database (information system). Another example might be an accountant or other tax professional requesting a tax record for a client from a tax return database (information system). Yet another example might be a website user requesting a web page containing some transaction-specific information from the website (information system). It is important to note that such examples of information systems may comprise multiple servers distributed in remote locations.

In the example cases above, it may also be important for the user (doctor, accountant or website user) to review information pertaining to how the record he/she has requested (patient record, tax record or web page) was derived or from what source(s) it was obtained. This additional information is typically referred to as provenance information.

SUMMARY OF THE INVENTION

Principles of the invention provide techniques for caching provenance information.

For example, in an information system comprising a first computing device requesting provenance data from at least a second computing device, a method for improving the delivery of provenance data to the first computing device, comprises the following steps. At least one cache is maintained for storing provenance data which the first computing device can access with less overhead than accessing the second computing device. Aggregated provenance data is produced from input provenance data. A decision whether or not to cache input provenance data is made based on a likelihood of the input provenance data being used to produce aggregated provenance data. In one embodiment, the first computing device may comprise a client and the second computing device may comprise a server.

Further, the at least one cache may be maintained by at least one network central location in the given network. The at least one network central location may be selected based on its accessibility by one or more other nodes within the given network. Still further, a marginal provenance level or score for the data item is computed and used to prioritize storage of the data item closer to the at least one network central location.

Advantageously, illustrative principles of the invention provide for provenance information to be distributed more efficiently throughout the information system.

These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idrefs="DRAWINGS">FIG. 1</figref> depicts an information system in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 2</figref> depicts a method for caching provenance information in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 3</figref> depicts an object dependency graph in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 4</figref> depicts an opportunistic path in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 5</figref> depicts a trace summary recorded in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIGS. 6(</figref><i>a</i>) through <b>6</b>(<i>d</i>) depict values of a network central location selection metric on exemplary traces in accordance with an embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 7</figref> depicts an information system in accordance with another embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 8</figref> depicts one step of a method for caching provenance information in accordance with another embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 9</figref> depicts another step of a method for caching provenance information in accordance with another embodiment of the invention.

<figref idrefs="DRAWINGS">FIG. 10</figref> depicts a computer system in accordance with which one or more components/steps of the techniques of the invention may be implemented.

DETAILED DESCRIPTION

Illustrative embodiments of the invention will be described herein in the context of one or more illustrative information systems. However, it is to be understood that principles of the invention are not limited to any particular information system and may be implemented in systems other than the illustrative ones described herein.

As used herein, the term “provenance” refers to an indication or determination of where a given object, such as a unit of data, came from, or an indication or determination of one or more objects from which the given object was derived. That is, the term “provenance” refers to the history or lineage of a given object. Thus, “provenance information” or “provenance data” is information or data that provides this indication or results of such determination.

Furthermore, as used herein, the phrase “data object” or simply “object” refers to any given data item or data unit that may be part of an information network. An object or data object may take on any form and it is to be understood that the invention is not limited to any particular form. For example, an object may be electronic data such as one or more web pages, documents, records, files, images, videos, or any other type of data set, data item, or data unit. Thus, the invention is not limited to any particular type of data object.

By way of additional example only, data objects could be scholarly research papers. The provenance information for a paper could be the bibliographic references cited in the paper. In some situations, the provenance information could be just a subset of the bibliographic references, such as the references cited in the related work section. In other cases, the provenance information could include all of the bibliographic references. In some cases, provenance information for a paper could include other references. For example, if paper A cites paper B which in turn cites paper C, then paper C could be considered to be provenance information for paper A.

Still further, as used herein, a “node” refers to any processing, computing and/or communication element in the information system.

Also, as used herein, the term “overhead” refers to overhead refers to a cost for performing a computation such as CPU cycles, memory consumed, storage consumed, network bandwidth consumed, etc.

It is often desirable to have information on the provenance of a data object. Provenance information can indicate how a data object got to its current state. It can be in several forms. For example, provenance information could indicate how a particular object O is created from multiple constituent objects c<b>1</b>, c<b>2</b>, . . . , cn. It could also indicate the data sources resulting in object O.

Information systems are comprised of one or more nodes (e.g., processors, servers, computing devices, communication devices, etc.) which communicate with each other. One or more of the nodes may be remote from one or more other nodes, or the nodes could all be co-located. Principles of the invention are not limited to any particular information system architecture or layout.

It is realized that it may be desirable to disseminate provenance information throughout the information system. When provenance information is disseminated throughout an information system, it is realized that it is advantageous to cache (store) the provenance information at nodes throughout the system. Caching this information allows the provenance information to be distributed more efficiently throughout the information system.

<figref idrefs="DRAWINGS">FIG. 1</figref> depicts an information system <b>100</b> with nodes n<b>1</b>, n<b>2</b>, n<b>3</b>, n<b>4</b> and n<b>5</b>. Note that the number of nodes can be a number significantly larger than five, but also less than five. Five nodes are used here solely for purposes of illustration of inventive principles. The lines between nodes represent communication links between the nodes. Note that principles of the invention apply to a wide variety of system topologies. Such inventive principles are also applicable to systems in which connectivity is dynamic. For example, connectivity may change over time. The system might be part of a disruption-tolerant network (DTN) in which the nodes are mobile and connectivity with other nodes may be intermittent and changing over time. An illustrative embodiment in a DTN will be described below in the context of <figref idrefs="DRAWINGS">FIGS. 4-6</figref>.

Assume that the information system <b>100</b> allows queries to be made for an object O requesting the provenance of O. Note that a query may be generated by a user of information system <b>100</b>, and that the “user” may be a human or another computer system. Such queries might have to be propagated throughout multiple nodes of an information system <b>100</b>. Thus, the nodes of the system in <figref idrefs="DRAWINGS">FIG. 1</figref> can cache provenance information for satisfying queries regarding provenance information. This makes it possible to answer provenance queries more quickly and with less overhead. Note in <figref idrefs="DRAWINGS">FIG. 1</figref> that each node has a cache <b>101</b> associated with it. Caches <b>101</b> can store provenance information.

As an example of provenance queries, assume that object O is a scientific research paper. There are multiple provenance queries regarding object O including but not limited to the following: <ul><li id="ul0001-0001" num="0000"><ul><li id="ul0002-0001" num="0033">Find all references from the related work section of object O.</li><li id="ul0002-0002" num="0034">Find all references in the entire paper.</li><li id="ul0002-0003" num="0035">Find all references in object O with an author who is also an author of object O.</li><li id="ul0002-0004" num="0036">Recursively get all references in the paper and references contained in other references published since 1980.</li></ul></li></ul>

A key aspect of the invention is that provenance data for object O can be aggregated from simpler cached provenance information. For example, object O may be comprised of three constituent objects c<b>1</b>, c<b>2</b>, and c<b>3</b>. In this case, the provenance information for object O can be obtained by aggregating provenance information from c<b>1</b>, c<b>2</b>, and c<b>3</b>. If the provenance information from c<b>1</b>, c<b>2</b>, and c<b>3</b> is stored within a cache, then a query for the provenance information corresponding to object O can be satisfied by simply obtaining the cached information. This results in considerably less overhead than if the provenance information has to be computed from scratch.

<figref idrefs="DRAWINGS">FIG. 2</figref> shows a method <b>200</b> for satisfying queries for provenance information in accordance with an embodiment of the invention.

In step <b>201</b>, provenance information is cached. For example, the system <b>100</b> may be handling web pages. Web pages may be constructed from fragments f<b>1</b>, f<b>2</b>, f<b>3</b>, . . . , fn. More information about constructing web pages from fragments is described in the paper “A Publishing System for Efficiently Generating Dynamic Web Content,” Jim Challenger, Paul Dantzig, Arun Iyengar, Karen Witting, ACM Transactions on Internet Technology vol. 5, no. 2, May 2005, the disclosure of which is incorporated by reference herein.

A cache <b>101</b> could store provenance information for fragments f<b>1</b>, f<b>2</b>, f<b>3</b>, . . . , fn. In order to make intelligent decisions about what provenance information to cache in step <b>201</b>, the cache maintains information on how frequently cached provenance information is requested. If an object o<b>1</b> comprising provenance information is frequently accessed for satisfying provenance queries, then object o<b>1</b> should be assigned a higher priority for being cached. By contrast, if an object o<b>2</b> is less frequently accessed for satisfying provenance queries, then object o<b>2</b> should be assigned a lower priority for being cached.

A relatively simple method for handling cache replacement (i.e., making space for new objects when a cache is full) is least recently used, or LRU. Using this approach, the cached object which was accessed most distantly in the past is the one that is replaced when the cache runs out of space. Another method for handling cache replacement is LRU-K. LRU-K removes the cached object whose kth most recent access was farthest in the past for some positive integer k.

The cache <b>101</b> can also take other factors into consideration besides (or in addition to) access frequencies when making caching decision. For example, if two objects o<b>1</b> and o<b>2</b> are accessed with similar frequencies but object o<b>1</b> is much smaller than object o<b>2</b>, then object o<b>1</b> should be given priority for storing in a cache because object o<b>1</b> will take up less space. If an object o<b>3</b> is very expensive to materialize and/or fetch, then object o<b>3</b> should be given higher preference for caching than an object which is less expensive to materialize and/or fetch. Preference should be given for caching objects with longer expected lifetimes over those with shorter expected lifetimes.

A more sophisticated cache replacement algorithm than LRU is to assign a utility value to each cached object based on factors such as access frequency, size, cost to fetch or materialize, and expected lifetime. The cache then attempts to store objects with the highest utility values in the cache. Since it can be computationally expensive to maintain exact utility values for all objects, there are approximation methods such as greedy-dual-size which allow utility values to be estimated without too much overhead. An example of a greedy-dual-size approximation method is described in “Cost-Aware WWW Proxy Caching Algorithms,” Pei Cao and Sandy Irani, Proceedings of USITS '97, December 1997, the disclosure of which is incorporated by reference herein.

In step <b>202</b>, a query for provenance information about an object o<b>1</b> is received. Assume this query is made from a client and is directed to at least one server. For example, suppose that object o<b>1</b> is a web page constructed from fragments f<b>1</b>, f<b>2</b>, and f<b>3</b>. The provenance information for object o<b>1</b> in this case can be aggregated from the provenance information for f<b>1</b>, f<b>2</b>, and <b>3</b>.

In step <b>203</b>, one of the nodes (n<b>1</b> through n<b>5</b>) of the system <b>100</b> attempts to obtain the provenance information by querying the caches <b>101</b> to determine if they contain provenance information for object o<b>1</b>. In the case of an information system such as the one in <figref idrefs="DRAWINGS">FIG. 1</figref>, a node may have to query multiple caches on nodes distributed throughout the system.

If the system (i.e., one or more of the plurality of nodes n<b>1</b>, n<b>2</b>, . . . , n<b>5</b>) is able to locate some or all of the provenance information requested for object o<b>1</b> by querying one or more caches, the cached information is used to compute and return the final result. Note a particular cache <b>101</b> might contain some but not all provenance information for object o<b>1</b>. For example, if cache c<b>1</b> contains provenance information for f<b>1</b>, cache c<b>2</b> contains provenance information for f<b>2</b>, and cache c<b>3</b> contains provenance information for f<b>3</b>, then provenance information stored in these three caches can be merged to yield the provenance information for object o<b>1</b>.

If all of the caches <b>101</b> are queried and the provenance information is not located in its entirety, the system (i.e., again, one or more of the plurality of nodes n<b>1</b>, n<b>2</b>, . . . , n<b>5</b>) could return the portion of provenance information which it was able to locate. Alternatively, there may be one or more data source nodes which could be contacted and queried to obtain the missing information. In general, obtaining provenance information from a data source node is more expensive than obtaining it from a cache. Therefore, if the information is obtained from one or more caches <b>101</b>, the overhead will be lower.

Provenance relationships among objects can be represented by an object dependency graph, an example of which is shown in <figref idrefs="DRAWINGS">FIG. 3</figref>. One example of a dependency graph may be based on a semi-ring model. Graph <b>300</b> depicts provenance relationships among seven objects. The nodes marked V indicate that the provenance information for a node can be computed from the provenance information from any child node. For example, the provenance information for object o<b>2</b> can be computed from the provenance information for either object o<b>4</b> or object o<b>5</b>. Nodes marked ^ indicate that the provenance information for a node is computed from the provenance information from all child nodes. For example, the provenance information for object o<b>1</b> can be computed from the provenance information from object o<b>2</b> and the provenance information for object o<b>3</b>. In the example in <figref idrefs="DRAWINGS">FIG. 3</figref>, all nodes have two children. However, in general, a node may have an arbitrary number of children.

We now describe, in the context of <figref idrefs="DRAWINGS">FIGS. 4-9</figref>, an illustrative embodiment whereby the above-described provenance caching techniques are applied to an information system in the form of a disruption-tolerant network (DTN). As mentioned above, DTNs are characterized by low node density, unpredictable node mobility and lack of global network information. In accordance with principles of the invention, we apply provenance caching to a DTN which enables a user to establish trust in an information product that is obtained by fusing (combining) raw data from one or more information sources (with varying degrees of trust). In particular, principles of the invention are applied to support provenance queries in DTNs using the cooperative in-network caching approach described above.

To address the challenges of opportunistic network connectivity in DTNs, principles of the invention intentionally cache both data and its provenance at a set of Network Central Locations (NCLs), which can be easily accessed by other nodes in the network. Correspondingly, queries are forwarded to these NCLs for data access. In section I below, we describe the concept of NCLs, and in section II, we describe an illustrative provenance caching methodology.

I. Network Central Locations

In this section, we describe how to appropriately select NCLs based on a probabilistic metric evaluating the data transmission delay among mobile nodes in DTNs. The applicability of such selection in practice is then validated by the heterogeneity of node contact patterns in realistic DTN traces.

A. NCL Selection Metric

In order to develop an appropriate metric for NCL selection, we first define the multi-hop opportunistic connection on the network contact graph G=(V, E).

Opportunistic path is defined as follows:

A r-hop opportunistic path P_AB=(V_P, E_P) between nodes A and B consists of a node set V_P={A, N₁, N₂, . . . , N_r-1, B}⊂V and an edge set E_P=(e₁, e₂, . . . , e_r)⊂E with edge weights {λ₁, λ₂, . . . , λ_r}. The path weight is the probability p_AB(T) that a data item is opportunistically transmitted from A to B along P_ABwithin time T.

An opportunistic path is illustrated in <figref idrefs="DRAWINGS">FIG. 4</figref>. The inter-contact time X_kbetween nodes N_kand N_k+1, as a random variable, follows an exponential distribution with probability density function (PDF) px_k(x)=λ_ke^−λ^{<sub2>k</sub2>}^x. Hence, the total time needed to transmit data from A to B is

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mi>Y</mi><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>r</mi></munderover><mo>⁢</mo><msub><mi>X</mi><mi>k</mi></msub></mrow></mrow></math></maths><br /> following a hypoexponential distribution, such that:

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>p</mi><mi>Y</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>r</mi></munderover><mo>⁢</mo><mrow><msubsup><mi>C</mi><mi>k</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msubsup><mo>⁢</mo><mrow><msub><mi>p</mi><msub><mi>X</mi><mi>k</mi></msub></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where the coefficients

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><msubsup><mi>C</mi><mi>k</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msubsup><mo>=</mo><mrow><munderover><mo>∏</mo><mrow><mrow><mi>s</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mrow><mi>s</mi><mo>≠</mo><mi>k</mi></mrow></mrow><mi>r</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mfrac><msub><mi>λ</mi><mi>s</mi></msub><mrow><msub><mi>λ</mi><mi>s</mi></msub><mo>-</mo><msub><mi>λ</mi><mi>k</mi></msub></mrow></mfrac><mo>.</mo></mrow></mrow></mrow></math></maths>

From Eq. (1), the path weight is written as:

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>p</mi><mi>AB</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msubsup><mo>∫</mo><mn>0</mn><mi>T</mi></msubsup><mo>⁢</mo><mrow><mrow><msub><mi>p</mi><mi>Y</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow><mo>⁢</mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo>⁢</mo><mrow><mo>ⅆ</mo><mi>x</mi></mrow></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>r</mi></munderover><mo>⁢</mo><mrow><msubsup><mi>C</mi><mi>k</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msubsup><mo>·</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><msup><mi>ⅇ</mi><mrow><mrow><mo>-</mo><msub><mi>λ</mi><mi>k</mi></msub></mrow><mo>⁢</mo><mi>T</mi></mrow></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and the data transmission delay between two nodes A to B is measured by the weight of the shortest opportunistic path between the two nodes.

The metric C_ifor a node i to be selected as a central node to represent an NCL is then defined as follows:

<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></mfrac><mo>·</mo><mrow><munderover><mo>∑</mo><mrow><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mrow><mi>j</mi><mo>≠</mo><mi>i</mi></mrow></mrow><mi>N</mi></munderover><mo>⁢</mo><mrow><msub><mi>p</mi><mi>ij</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where N is the total number of nodes in the network. This metric indicates the average probability that data can be transmitted from a random node in the network to node i within time T, and therefore can also be considered as indicating the average distance from a random node in the network to node i.

In one embodiment, the top K nodes with the highest metric values are selected by the network administrator as the central nodes of NCLs, and such NCL selection is done before any data access operation. A network warm-up period is provided for the administrator to collect information about the pairwise node contact rate, and to calculate the weight of opportunistic paths among mobile nodes. The NCL information is provided by the administrator to each node in the network, and a node maintains its shortest opportunistic path to each NCL. We assume that the set of NCL nodes remain stable over time. As a result, the selected NCLs will not be changed during data access.

B. Trace-Based Validation

The practical applicability of NCL selection is based on the heterogeneity of node contact patterns. In this section, we validate this applicability using realistic DTN traces. These traces record contacts among users carrying hand-held mobile devices at a technical conference and a university campus. The devices equipped with a Bluetooth interface periodically detect their peers nearby, and a contact is recorded when two devices move close to each other. The devices equipped with a WiFi interface search for nearby WiFi Access Points (APs) and associate themselves to the APs with the best signal strength. A contact is recorded when two devices are associated to the same AP. The traces are summarized in the table of <figref idrefs="DRAWINGS">FIG. 5</figref>. It is to be appreciated that the term “contact” could be defined in ways other than the two examples given above (i.e., proximity for Bluetooth, and common AP for WiFi).

In order to calculate the weight of an opportunistic path according to Eq. (2), we calculate the pairwise contact rates based on the cumulative contacts between each pair of nodes during the entire trace. According to Eq. (2), inappropriate values of T will make C_iclose to 0 or 1. Therefore, due to the heterogeneity of the pairwise contact frequency in different traces, different values of T are used adaptively chosen; T is set as 1 hour for the two Infocom traces, 1 week for the MIT Reality trace, and 3 days for the UCSD trace.

The results in <figref idrefs="DRAWINGS">FIGS. 6(</figref><i>a</i>) through <b>6</b>(<i>d</i>) show that the distributions of NCL selection metric values of mobile nodes are highly skewed in all traces, such that the metric values of a few nodes are much higher than that of other nodes. This difference can be up to tenfold in some traces, and validates that the above-described NCL selection metric appropriately reflects the heterogeneity of node contact patterns. As a result, the selected NCLs can be easily accessed by other nodes in the network, which hence ensures the performance of the provenance caching methodology described below in section II.

II. Provenance Caching

In this section, we describe a provenance caching methodology for use in a DTN. As shown in <figref idrefs="DRAWINGS">FIG. 7</figref>, each NCL is represented by a central node, which corresponds to a star in the figure. The push and pull caching strategies conjoin at the NCLs. The data source S actively pushes its generated data towards the NCLs. If the buffer of a central node C<b>1</b> is full, data is cached at one or more nodes near a NCL (e.g., node A near C<b>1</b>). Correspondingly, the requester R pulls the data by querying the NCLs, and data copies from multiple NCLs are returned to the requester in order to ensure data accessibility within the time constraint of the query. Note that C<b>2</b> is another NCL, and that B, C and D are other nodes in the network.

The functionality of the application of the provenance caching approach to a DTN is comprised of the following three components:

1) When a data source generates new data, it pushes the data and its provenance expressions to the central nodes of NCLs which are prioritized to cache data. The NCL node stores a copy of all provenance expressions. One copy of data is cached at each NCL; if the caching buffer of a central node is full, another node near the central node will be identified to cache the data. Such decisions are automatically made based on the buffer conditions of nodes involved in the pushing process. This concept is illustrated in <figref idrefs="DRAWINGS">FIG. 8</figref>. Note that, as shown, the R's are nodes in a computer network. The letter R was used because the nodes relay information throughout the network. These relay nodes are distinct from NCL nodes which are denoted by stars. The subscripts serve to differentiate the nodes from each other.

2) A requester multicasts a query to the central nodes of NCLs to pull the data, and a central node forwards the query for the data (along with its provenance expression) to the nodes caching the required data items. A number of cached data copies are returned to the requester, and the tradeoff between provenance level, data accessibility and transmission overhead is optimized by probabilistically controlling the number of returned data copies. This concept is illustrated in <figref idrefs="DRAWINGS">FIG. 9</figref>. As in <figref idrefs="DRAWINGS">FIG. 8</figref>, stars represent NCL nodes. A, R. and B are nodes in the network. The solid arrow represents a query propagating through the network. The dashed line represents data propagating through the network.

3) Utility-based cache replacement is conducted whenever two caching nodes contact each other, and ensures that high utility data is cached nearer to the central nodes. An approach is provided to quantify utility of a data item based on its marginal impact on the provenance of the requested data and the popularity of the requested data itself. Below, we describe the utility-based caching approach in illustrative detail.

A. Utility-Based Caching

There are two major components that contribute towards the utility of a data item: data popularity and marginal provenance level.

1) Data Popularity: The popularity of a data item in the network is probabilistically estimated based on the occurrences of the past k requests to this data, which happened during the time period [t₁, t_k]. We assume that such occurrences of data requests in the past follow a Poisson distribution with the parameter λ_d=k/(t_k−t₁), and data popularity is defined as the probability that this data will be requested again in the future before the data expires. If data d_iexpires at time t_e, the popularity w_iof d_iis written as: <br /><i>w</i>_i=1<i>−e</i>^−λ^{<sub2>d</sub2>}^·(t^{<sub2>e</sub2>}^−t^{<sub2>k</sub2>}⁾,  (4)<br /> which is actually the probability that d_iis requested at least once again in the future before time t_e. To calculate the popularity of a data item, a node needs to recursively maintain two time values about the past occurrences of data requests, and therefore will only incur negligible space overhead.

2) Marginal Provenance Level: Besides the popularity of a data item, we quantify the vitality of a data item in establishing the provenance of the requested data item. In order to do so, we examine the provenance expression of data items. For example, given a provenance expression d=(a<img id="CUSTOM-CHARACTER-00001" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00001.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />b)<img id="CUSTOM-CHARACTER-00002" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00002.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />c, the data item c is more important in establishing the provenance of d than data items a or b. In general, we denote a provenance expression as a Boolean monotone function d=ƒ(a₁, . . . , a_n). The contribution of data item a_itowards the provenance of d is quantified as:

<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>w</mi><mi>i</mi><mi>d</mi></msubsup><mo>=</mo><mfrac><mrow><mi>#</mi><mo>⁢</mo><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>a</mi><mn>1</mn></msub><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msub><mi>a</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>,</mo><mn>1</mn><mo>,</mo><msub><mi>a</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><msub><mi>a</mi><mi>n</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><msup><mn>2</mn><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msup></mfrac></mrow></mtd><mtd><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

Where the notation a_iis overloaded to denote both the data item and 0/1 Boolean variable and #ƒ denotes the number of satisfiable assignments to Boolean variables {a₁, . . . , a_i+1, a_i+1, . . . , a_n} such that ƒ evaluates to true. For example, given d=(a<img id="CUSTOM-CHARACTER-00003" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00001.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />b) <img id="CUSTOM-CHARACTER-00004" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00002.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />c the marginal provenance levels are given as

<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><mrow><msubsup><mi>w</mi><mi>a</mi><mi>d</mi></msubsup><mo>=</mo><mrow><msubsup><mi>w</mi><mi>b</mi><mi>d</mi></msubsup><mo>=</mo><mrow><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>w</mi><mi>c</mi><mi>d</mi></msubsup></mrow><mo>=</mo><mn>1</mn></mrow></mrow></mrow><mo>;</mo></mrow></math></maths><br /> given d=a<img id="CUSTOM-CHARACTER-00005" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00001.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />(b<img id="CUSTOM-CHARACTER-00006" he="3.13mm" wi="1.78mm" file="US08577993-20131105-P00002.TIF" alt="custom character" img-content="character" img-format="tif" orientation="portrait" inline="no" />c) the marginal provenance levels are given as

<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><msubsup><mi>w</mi><mi>b</mi><mi>d</mi></msubsup><mo>=</mo><mrow><msubsup><mi>w</mi><mi>c</mi><mi>d</mi></msubsup><mo>=</mo><mrow><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mi>w</mi><mi>a</mi><mi>d</mi></msubsup></mrow><mo>=</mo><mrow><mfrac><mn>3</mn><mn>4</mn></mfrac><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><br /> We also set w_*^d=0 for all data items that do not contribute to the provenance of d. Thus, we refer to Eq. (5) as a marginal provenance level or score of a data item and, in one embodiment, this level or score may be computed using the provenance metadata expressed in a semi-ring model.

We note that while counting the number of satisfiable assignments to a general Boolean expression is a NP-hard problem; however, counting such assignments over monotone Boolean expressions is relatively easier. A key observation here is that if for some assignment of {a_i}, ƒ(a₁, . . . , a_n) evaluates to true, then for all a_i=0 in the satisfiable assignment setting α_i=1 retains the satisfiability of ƒ (due to the monotone property).

3) Overall Utility: The overall utility of a data item d depends upon its popularity and the popularity of all data items d′ such that the marginal provenance level w_d^d′&gt;0. Further, assuming finite cache space, we set the overall utility as being inversely proportional to the size of the data item d. Hence, the overall popularity of d and its utility is given by:

<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><mrow><mi>pop</mi><mo>⁡</mo><mrow><mo>(</mo><mi>d</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><msub><mi>w</mi><mi>d</mi></msub><mo>+</mo><mrow><munder><mo>∑</mo><mrow><msup><mi>d</mi><mi>′</mi></msup><mo>≠</mo><mi>d</mi></mrow></munder><mo>⁢</mo><mrow><msub><mi>w</mi><msup><mi>d</mi><mi>′</mi></msup></msub><mo>*</mo><msubsup><mi>w</mi><mi>d</mi><msup><mi>d</mi><mi>′</mi></msup></msubsup></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00009-2" num="00009.2"><math overflow="scroll"><mrow><msub><mi>u</mi><mi>d</mi></msub><mo>=</mo><mfrac><mrow><mi>pop</mi><mo>⁡</mo><mrow><mo>(</mo><mi>d</mi><mo>)</mo></mrow></mrow><mrow><mi>size</mi><mo>⁡</mo><mrow><mo>(</mo><mi>d</mi><mo>)</mo></mrow></mrow></mfrac></mrow></math></maths>

4) Caching Policy: Given an opportunistic contact between two nodes in the DTN, the nodes collectively examine all the data items available in their caches.

Each node caches a data item d (from the aggregate pool of data items) with probability that is proportional to its utility u_d. This process is repeated until the cache node runs out of storage space. We observe that high utility items are likely to be cached on both nodes, while low utility items may fade out from the caches.

B. Answering Provenance Queries

As shown in <figref idrefs="DRAWINGS">FIG. 9</figref>, due to the probabilistic nature of data delivery in DTNs, multiple data copies are replied to the requester from NCLs to ensure that the requester is able to receive data before the query expires. However, only the first data copy received by the requester is useful, and all the others are essentially useless and waste the network bandwidth. This problem is further complicated since there may be multiple ways to establish the provenance of the requested data item—there is evidently a tradeoff between provenance level and networking overhead. Illustrative principles of the invention provide a probabilistic approach to address these challenges and optimize the tradeoff between provenance level and transmission overhead. A main concept behind this illustrative approach is that, having received the query, a caching node probabilistically decides whether to return the cached data to the requester.

We assume that the query is generated with a time constraint T_q, and it takes t₀&lt;T_qfor the query to be forwarded from requester R to caching node C. If there is no tight constraint on the network storage and bandwidth, each node is able to maintain the information about the shortest opportunistic paths to all the other nodes in the network. According to the above description, C can determine whether to reply data to R with the probability w_d^q*p_CR(T_q−t₀), where w_d^qdenotes the marginal provenance level of d with respect to query q and P_CR(T_q−t₀) denotes the probability that the data can be transmitted from C to R within the remaining time T_q−t₀.

Otherwise, a node only maintains the information about the shortest opportunistic paths to the central nodes, and it is difficult for C to estimate the data transmission delay to R. Instead, the probability for deciding the data response is calculated only based on the remaining time T_q−t₀for responding to the query and the marginal provenance level of a data item with respect to the queried data item. In general, this probability should be inversely proportional to T_q−t₀, and we calculate this probability as a Sigmoid function p_R(t), where p_R(T_q)=p_maxε(0,1] and p_R(0)=p_minε(p_max/2, p_max). This function is written as:

<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>p</mi><mi>R</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><msub><mi>k</mi><mn>1</mn></msub><mo>*</mo><msubsup><mi>w</mi><mi>d</mi><mi>q</mi></msubsup></mrow><mrow><mn>1</mn><mo>+</mo><msup><mi>ⅇ</mi><mrow><mrow><mo>-</mo><msub><mi>k</mi><mn>2</mn></msub></mrow><mo>·</mo><mi>t</mi></mrow></msup></mrow></mfrac></mrow><mo>,</mo><mstyle><mtext /></mstyle><mo>⁢</mo><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>k</mi><mn>1</mn></msub></mrow><mo>=</mo><mrow><mn>2</mn><mo>⁢</mo><msub><mi>p</mi><mi>min</mi></msub></mrow></mrow><mo>,</mo><mrow><msub><mi>k</mi><mn>2</mn></msub><mo>=</mo><mrow><mfrac><mn>1</mn><msub><mi>T</mi><mi>q</mi></msub></mfrac><mo>·</mo><mrow><mrow><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><mfrac><msub><mi>p</mi><mi>max</mi></msub><mrow><mrow><mn>2</mn><mo>⁢</mo><msub><mi>p</mi><mi>min</mi></msub></mrow><mo>-</mo><msub><mi>p</mi><mi>max</mi></msub></mrow></mfrac><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Our approach allows the user to tune the provenance level of a query response by suitably selecting parameters p_maxand p_min(the maximum and minimum response probabilities).

Accordingly, as is evident from the above description, the system probabilistically propagates queries on the DTN based on the desired provenance level of the query response. Furthermore, cache replacement policies are triggered based on contacts in the underlying DTN, and such cache replacement policies exploit both the popularity of a queried data item and its provenance. Still further, the system advantageously uses the marginal provenance scores of data items to prioritize their storage closer to the network central locations (NCLs). In this manner, provenance information is distributed more efficiently throughout the given information system.

As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, apparatus, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

Referring again to <figref idrefs="DRAWINGS">FIGS. 1 through 9</figref>, the diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in a flowchart or a block diagram may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagram and/or flowchart illustration, and combinations of blocks in the block diagram and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

Accordingly, techniques of the invention, for example, as depicted in <figref idrefs="DRAWINGS">FIGS. 1-9</figref>, can also include, as described herein, providing a system, wherein the system includes distinct modules (e.g., modules comprising software, hardware or software and hardware). By way of example only, the modules may include but are not limited to node modules and cache modules. These and other modules may be configured, for example, to perform the steps described and illustrated in the context of <figref idrefs="DRAWINGS">FIGS. 1-9</figref>.

One or more embodiments can make use of software running on a general purpose computer or workstation. With reference to <figref idrefs="DRAWINGS">FIG. 10</figref>, such an implementation <b>1000</b> employs, for example, a processor <b>1002</b>, a memory <b>1004</b>, and an input/output interface formed, for example, by a display <b>1006</b> and a keyboard <b>1008</b>. The term “processor” as used herein is intended to include (but not be limited to) any processing device, such as, for example, one that includes a CPU (central processing unit) and/or other forms of processing circuitry. Further, the term “processor” may refer to more than one individual processor. The term “memory” is intended to include (but not be limited to) memory associated with a processor or CPU, such as, for example, RAM (random access memory), ROM (read only memory), a fixed memory device (for example, hard drive), a removable memory device (for example, diskette), a flash memory and the like. In addition, the phrase “input/output interface” as used herein, is intended to include (but not be limited to) one or more mechanisms for inputting data to the processing unit (for example, keyboard or mouse), and one or more mechanisms for providing results associated with the processing unit (for example, display or printer).

The processor <b>1002</b>, memory <b>1004</b>, and input/output interface such as display <b>1006</b> and keyboard <b>1008</b> can be interconnected, for example, via bus <b>1010</b> as part of a data processing unit <b>1012</b>. Suitable interconnections, for example, via bus <b>1010</b>, can also be provided to a network interface <b>1014</b>, such as a network card, which can be provided to interface with a computer network, and to a media interface <b>1016</b>, such as a diskette or CD-ROM drive, which can be provided to interface with media <b>1018</b>.

A data processing system suitable for storing and/or executing program code can include at least one processor <b>1002</b> coupled directly or indirectly to memory elements <b>1004</b> through a system bus <b>1010</b>. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

Input/output or I/O devices (including but not limited to keyboard <b>1008</b>, display <b>1006</b>, pointing device, and the like) can be coupled to the system either directly (such as via bus <b>1010</b>) or through intervening I/O controllers (omitted for clarity).

Network adapters such as network interface <b>1014</b> may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.

As used herein, including the claims, a “server” includes a physical data processing system (for example, system <b>1012</b> as shown in <figref idrefs="DRAWINGS">FIG. 10</figref>) running a server program. It will be understood that such a physical server may or may not include a display and keyboard.

Accordingly, it is to be understood that the computer architecture <b>1000</b> shown in <figref idrefs="DRAWINGS">FIG. 10</figref> may represent one illustrative implementation of a node and/or a cache, as shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. Also, the computer architecture <b>1000</b> could represent an illustrative implementation of a client.

It will be appreciated and should be understood that the exemplary embodiments of the invention described above can be implemented in a number of different fashions. Given the teachings of the invention provided herein, one of ordinary skill in the related art will be able to contemplate other implementations of the invention. Indeed, although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be made by one skilled in the art without departing from the scope or spirit of the invention.