Derivation of a propagation specification from a predicted utility of information in a network

• US 8,325,718 B2
• Filed: 07/03/2006
• Issued: 12/04/2012
• Est. Priority Date: 07/03/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Liu, Juan, Greene, Daniel H., Huang, Qingfeng, Reich, James E., Mosko, Marc E.
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): HAILE, AWET A
• Application Number:
  US11/428,435
• Publication Number:
  US 20080039113A1
• Time in Patent Office: 2,346 Days
• Field of Search: 370/235, 370/254, 370/389, 455/91, 455/99, 709/217, 709/238
• US Class Current: 370/389
• CPC Class Codes: G08G 1/091 Traffic information broadcasting broadcasting communication H04H
• CPC Class Codes: G08G 1/093 Data selection, e.g. prioritizing information, managing message queues, selecting the information to be output
• CPC Class Codes: G08G 1/14 indicating individual free spaces in parking areas
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of transmitting data includes determining how much data is desired to be transmitted from a data source. A utility function is used to determine a pattern of microutilities to be associated with data samples from the data source. The pattern of microutilities specifies a pattern of data delivery to at least one predetermined location relative to the data source. The data samples are propagated according to the pattern of microutilities.

Claims

1. A method of transmitting data, comprising:

determining how much data is desired to be transmitted from a data source by an application;

applying a utility function provided by the application to data samples generated by the data source producing a microutility that travels with each data sample that specifies a distance of transmission and a frequency of updates for the data sample;

using the utility function to determine a pattern of microutilities to be delivered from the data source to a predetermined region based upon the distances and frequencies of the data samples, wherein the pattern of microutilities is selected to increase a sum of utility minus a cost of bandwidth; and

propagating the data samples and their accompanying microutility to the region according to the pattern of microutilities,

wherein using the utility function to determine the pattern of microutilities further comprises using the utility function to increase utility of the patterns of data delivery,

determining a marginal utility for data samples received at different frequencies at different locations;

determining when the marginal utility exceeds a threshold; and

determining the pattern of microutilities such that the frequency of delivery at different distances includes any instances where the marginal utility exceeds the threshold.

2. The method of claim 1, wherein using the utility function to determine the pattern of microutilities further comprises using the utility function to increase a utility to recipients of the patterns of data delivery.

3. The method of claim 1, wherein each microutility within the pattern of microutilities includes information to allow in transit modification of a pattern of data delivery.

4. The method of claim 3, wherein the in transit modification of the pattern of data delivery decreases bandwidth used to propagate the data.

5. The method of claim 3, where the in transit modification of the pattern of data delivery decreases the bandwidth used to propagate the data samples with a minimal effect on utility of the patterns of data delivery.

6. The method of claim 3, wherein the information includes a dynamic priority.

7. The method of claim 6, wherein the dynamic priority approximates a utility that remains to be delivered in subsequent propagation of the data samples.

8. The method of claim 1, the method further comprising setting a cost of bandwidth for data transmissions from the data source.

9. The method of claim 8, wherein setting the cost of bandwidth for data transmission further comprises communicating with neighboring nodes to determine a cost.

10. The method of claim 8, wherein setting the cost of bandwidth further comprises one of basic split cost, equilibrium cost, and spatially smoothed cost.

11. The method of claim 8, wherein generating the pattern of microutilities further comprises choosing the pattern of microutilities such that a sum of the utility of data delivered minus the cost of bandwidth is increased.

12. An article of non-transitory computer-readable media containing instructions that, when executed, cause the computer to:

determine how much data is desired to be transmitted from an application on a data source;

apply a utility function to data samples generated by the data source;

producing a microutility for each data sample that travels with the data sample, the microutility specifying a distance of transmission and a frequency of updates for the data sample;

use the utility function to determine a pattern of microutilities based upon the distances and frequencies of the data samples to be delivered from the data source to a predetermined region, wherein the pattern of microutilities is selected to increase a sum of utility minus a cost of bandwidth; and

propagate the data samples and their microutilities according to the pattern of microutilities,

wherein the code causing the computer to use the utility function to determine the pattern of microutilities further causes the computer to use the utility function to increase utility of the patterns of data delivery,

determine a marginal utility for data samples received at different frequencies at different locations;

determine when the marginal utility exceeds a threshold; and

determine the pattern of microutilities such that the frequency of delivery at different distances includes any instances where the marginal utility exceeds the threshold.

13. The article of claim 12, wherein the code causing the computer to use the utility function to determine the pattern of microutilities further causes the computer to use the utility function to increase a utility to recipients of patterns of data delivery.

14. The article of claim 12, the code further causing the computer to set a cost of bandwidth for data transmissions from the data source.

15. The article of claim 14, the code causing the computer to set the cost of bandwidth for data transmission further causes the computer to communicate with neighboring nodes to determine a cost.