Methods, apparatus, and program products for inferring service usage

• US 20040103066A1
• Filed: 11/08/2002
• Published: 05/27/2004
• Est. Priority Date: 11/08/2002
• Status: Active Grant

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica N., Johnson, Robert T.
• Granted Patent: US 7,363,244 B2
• Time in Patent Office: Days
• US Class Current: 705/80
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: G06Q 50/188 Electronic negotiation
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]

Abstract

Given the recent changes in the policy governing Internet content distribution, such as the institution of per listener royalties for Internet radio broadcasters, content distributors now have an incentive to under-report the size of their audience. Previous audience measurement schemes only protect against inflation of audience size. We present the first protocols for audience measurement that protect against both inflation and deflation attempts by content distributors. The protocols trade-off the amount of additional information the service providers must distribute to facilitate audience inference with the amount of infrastructure required and are applicable to Internet radio, web plagiarism, and software license enforcement. The protocols can be applied to other situations, such as auditing website screen scrapers and per-seat licensed software installations.

Claims

1. A method comprising:

providing, by a service provider, a service responsive to one or more requests from one or more of a plurality of serviced clients, said plurality of serviced clients including an audit client;

negotiating, between said service provider and requesting one of said plurality of serviced clients, a tag for each of said one or more requests;

accumulating said tag with a lossy data representation of negotiated tags for each of said one or more requests;

seeding a plurality of seeded requests, by said audit client, to said service provider, said audit client maintaining audit client tag information representing the tags negotiated by said audit client; and

estimating a number of said one or more requests serviced from said lossy data representation of negotiated tags and said audit client tag information.

2. The method of claim 1, wherein the step of accumulating is performed over an interval and the step of estimating determines said number with respect to said interval.

3. The method of claim 2, wherein, in the step of seeding, the maintaining of said audit client tag information occurs throughout said interval.

4. The method of claim 1, wherein the step of seeding is performed by said audit client.

5. The method of claim 1, wherein said lossy data representation of negotiated tags is a bit vector.

6. The method of claim 1, further comprising verifying that said plurality of seeded requests were recognized in said lossy data representation of negotiated tags.

7. The method of claim 1, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

8. The method of claim 1, wherein said service provider is obligated to measure how much the service is used.

9. A system comprising:

a service provider configured to provide a service responsive to one or more requests from one or more of a plurality of serviced clients, the plurality of serviced clients including an audit client;

a negotiation mechanism configured to negotiate a tag for each of said one or more requests between said service provider and requesting one of said plurality of serviced clients;

an accumulation mechanism configured to accumulate said tag with a lossy data representation of negotiated tags for each of said one or more requests;

a seeding mechanism configured to seed a plurality of seeded requests, by said audit client, to the service provider, said audit client configured to maintain audit client tag information representing the tags negotiated by said audit client; and

an estimation mechanism configured to estimate a number of said one or more requests serviced from said lossy data representation of negotiated tags and said audit client tag information.

10. The system of claim 9, wherein the accumulation mechanism operates over an interval and the estimation mechanism determines said number with respect to said interval.

11. The system of claim 10, wherein, in the seeding mechanism maintains said audit client tag information throughout said interval.

12. The system of claim 9, wherein the seeding mechanism is incorporated within said audit client.

13. The system of claim 9, wherein said lossy data representation of negotiated tags is a bit vector.

14. The system of claim 9, further comprising a verification mechanism configured to verify that said plurality of seeded requests were recognized in said lossy data representation of negotiated tags.

15. The system of claim 9, wherein the service provider provides content, software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

16. The system of claim 9, wherein said service provider is obligated to measure how much the service is used.

17. A method comprising:

providing a service responsive to one or more requests;

negotiating a tag for each of said one or more requests;

accumulating said tag with a lossy data representation of negotiated tags for each of said one or more requests; and

providing said lossy data representation of negotiated tags.

22. The method of claim 17, wherein said lossy data representation of negotiated tags is a bit vector.

23. The method of claim 22, wherein said bit vector is a bloom filter.

24. The method of claim 23, wherein said tag is a nonce.

25. The method of claim 17, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

18. The method of 17, wherein the step of accumulating extends over an interval.

19. The method of 17, wherein the step of negotiating negotiates with a serviced client.

20. The method of 17, wherein the step of providing provides said lossy data representation of negotiated tags to an audit client.

21. The method of 20, wherein said audit client has seeded requests within said one or more requests.

26. An apparatus comprising:

a network interface;

a receiver mechanism configured to receive, using the network interface, one or more requests for a service;

a negotiation mechanism, responsive to the receiver mechanism, capable of negotiating a tag for each of said one or more requests;

a tag accumulator mechanism configured to accumulate said tag with a lossy data representation of negotiated tags for each of said one or more requests; and

a transmission mechanism configured to provide, using the network interface, said lossy data representation of negotiated tags.

31. The apparatus of claim 26, wherein said lossy data representation of negotiated tags is a bit vector.

32. The apparatus of claim 31, wherein said bit vector is a bloom filter.

33. The apparatus of claim 32, wherein said tag is a nonce.

34. The apparatus of claim 26, wherein said service provided is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

27. The apparatus of 26, wherein the tag accumulator mechanism operates over an interval.

28. The apparatus of 26, wherein the negotiation mechanism negotiates with a serviced client.

29. The apparatus of 26, wherein the transmission mechanism is configured to provide said lossy data representation of negotiated tags to an audit client.

30. The apparatus of 29, wherein said audit client has seeded requests within said one or more requests.

35. A method comprising:

seeding a plurality of seeded requests to a service provider;

negotiating a tag for each of said plurality of seeded requests;

maintaining audit client tag information representing one or more tags negotiated by said audit client;

receiving a lossy data representation of negotiated tags; and

estimating a number of one or more requests serviced by said service provider from said lossy data representation of negotiated tags and said audit client tag information.

36. The method of claim 35, further comprising-verifying from said lossy data representation of negotiated tags that said plurality of seeded requests were recognized.

37. An apparatus comprising:

a network interface;

a transmission mechanism capable of sending, using the network interface, a plurality of seeded requests to a service provider

a negotiation mechanism capable of negotiating a tag for each of said plurality of seeded requests with said service provider;

a tag storage mechanism configured to maintain audit client tag information representing one or more tags negotiated by the negotiation mechanism;

a reception mechanism capable of receiving, using the network interface, a lossy data representation of negotiated tags from said service provider; and

an estimation mechanism configured to estimate a number of one or more requests serviced by said service provider from said lossy data representation of negotiated tags and said audit client tag information.

38. The apparatus of claim 37, further comprising a checking mechanism configured to verify from said lossy data representation of negotiated tags that said plurality of seeded requests were recognized by said service provider.

39. The apparatus of claim 37, further comprising a reporting mechanism configured to report said number.