System for wireless push and pull based services

• US 7,058,691 B1
• Filed: 06/12/2000
• Issued: 06/06/2006
• Est. Priority Date: 06/12/2000
• Status: Expired due to Fees

• Current Assignee: The Trustees of Princeton University (Princeton University)
• Original Assignee: The Trustees of Princeton University (Princeton University)
• Inventors: Kobayashi, Hisashi, Yu, Shun Zheng
• Primary Examiner(s): DINH, KHANH Q
• Application Number:
  US09/591,746
• Time in Patent Office: 2,185 Days
• Field of Search: 709/206, 709/217, 709/218, 709/219, 709/220, 709/222, 709/227, 709/228, 709/232, 709/234, 709/2, 709/203, 709/207, 709/238, 707/10, 707/203, 707/20, 713/201, 713/202, 713/16, 455/405, 455/456
• US Class Current: 709/207
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/566 Grouping or aggregating service requests, e.g. for unified processing
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor
• CPC Class Codes: H04W 88/16 Gateway arrangements

Abstract

The present invention relates to a method and system for providing Web content from pull and push based services running on Web content providers to mobile users. A proxy gateway connects the mobile users to the Web content providers. A prefetching module is used at the proxy gateway to optimize performance of the pull services by reducing average access latency. The average access latency can be reduced by using at least three factors: one related to the frequency of access to the pull content; second, the update cycle of the pull content determined by the Web content providers; and third, the response delay for fetching pull content from the content provider to the proxy gateway. Pull content, such as documents, having the greatest average access latency are sorted and a predetermined number of the documents are prefetched into the cache. Push services are optimized by iteratively estimating a state of each of the mobile users to determine relevant push content to be forward to the mobile user.

Claims

1. In a system comprising a proxy gateway connected by a first network to a plurality of mobile users and by a second network to at least one Web server, said proxy gateway comprising a cache for storing pull content received from said at least one Web server of a pull service, a method comprising the steps of:

storing data that is indicative of a request for said pull content from at least one of said plurality of mobile users and data indicative of interactions between said cache and said Web server;

determining access probability of access to said pull content from said stored data;

determining an average hit rate for said pull content from said stored data;

determining an average response delay for said pull content from said stored data;

determining average wired network access latency for said pull content from said access probability, said average hit rate and said average response delay;

storing said pull content in said cache based on said determined average wired network access latency when there is no said pull content in said cache or said pull content has expired,

wherein said pull content having a greater average wired network access latency is prioritized for being stored in said cache.

2. The method of claim 1 wherein said pull content is n documents, n=1, 2 . . . N, wherein N is the total number of documents, and said stored data comprises:

an average rate of access to document n, R_n;

a size of said document n, s_n;

an average time delay imposed by said second network, Δ

T_n; and

an update cycle of said document n, μ

_n.

3. The method of claim 2 wherein said access probability is determined by:

γ

_n=R_n/R

wherein R is the total rate of access to documents on said second network.

4. The method of claim 3 wherein said average hit rate for document n, h_n is determined by:

$h_n=1-\frac{g_n}{R_n<br><br>{\mathrm{\mu <br><br>}}_n},$

in which;

g_n is the probability that there is at least one request to document n during a given update cycle, μ

_n, given by;

g_n=1−

e<sup>−

Rnμ

n</sup>, n=1, 2, . . . , N,

and

R_nμ

_n is an expected number of accesses to document n in an update cycle of document n.

5. The method of claim 4 wherein average wired-network-access latency when there is no said pull content in said cache or said pull content has expired is determined from

η

_n=γ

_n(1−

h_n)Δ

T_n, n=1, . . . , N.

6. The method of claim 5 wherein said pull content is prioritized by the steps of:

sorting said plurality of N documents in descending order with a document having the greatest average wired network access latency when there is no said pull content in said cache or said pull content has expired labeled as η

₁, and document having the least average wired-network-access latency when there is no said Web content in said cache or said Web content has expired labeled as η

_N; and

determining a number of documents to be stored in said cache, r, by considering at least one constraint selected from the group consisting of spare cache capacity, spare transmission bandwidth on said second network and desired hit probability.

7. The method of claim 6 wherein said constraint of said spare cache capacity, Δ

C, is given by;

$\underset{n=1}{\overset{r}{\sum <br><br>}}<br><br><br><br>s_n<br><br>\left(1-h_n\right)\le <br><br>\mathrm{\Delta <br><br>}<br><br><br><br>C,$

wherein

$\mathrm{\Delta <br><br>}<br><br><br><br>C\approx <br><br>C-\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>s_n<br><br>h_n,$

C is given capacity of the cache, s_n is the size of the document n and h_n is the average hit rate for document n.

8. The method of claim 6 wherein said constraint of said spare transmission bandwidth, Δ

B, is given by;

$\underset{n=1}{\overset{r}{\sum <br><br>}}<br><br>\left(1-g_n\right)<br><br>\frac{s_n}{{\mathrm{\mu <br><br>}}_n}\le <br><br>\mathrm{\Delta <br><br>}<br><br><br><br>B,$

wherein

$\mathrm{\Delta <br><br>}<br><br><br><br>B\approx <br><br>B-\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>g_n<br><br>\frac{s_n}{{\mathrm{\mu <br><br>}}_n},$

B is given bandwidth, g_n is the probability that there is at least one request to document n during a given update cycle μ

_n and s_n is the size of the document.

9. The method of claim 6 wherein said constraint of a desired minimum hit probability, Δ

H, is given by;

$\underset{n=1}{\overset{r}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_n<br><br>\left(1-h_n\right)\ge <br><br>\mathrm{\Delta <br><br>}<br><br><br><br>H$

wherein

$\mathrm{\Delta <br><br>}<br><br><br><br>H\approx <br><br>H-\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\gamma <br><br>}}_n<br><br>h_n$

H is given hit probability, γ

_n is an access to document n and h_n is an average hit rate for document n.

10. The method of claim 2 further comprising the step of:

updating said stored pull content in said cache based on said update cycle of document n, μ

_n.

11. In a system comprising a proxy gateway connected by a first network to a plurality of mobile users and by a second network to at least one Web server, a method comprising the steps of:

measuring each of said mobile users current geo-location position and behavior;

computing a first probability that said measured current geo-location position and behavior is an actual position and behavior of each of said mobile users;

determining a state sequence estimation variable for each of said mobile users by iteration over time from a second probability that each of said mobile users transit in a geo-location and behavior sequence;

determining a current state for each of said mobile users from said state sequence estimation variable and

pushing push content related to said current state to each of said mobile users.

12. The method of claim 11 wherein said first probability is given by

P_r{Y_t|X}

wherein Y_t is said measured current geo-location position and behavior and X is said actual position and behavior.

13. The method of claim 12 wherein said state sequence estimation variable is determined by

${\alpha }_{}$

t ⁡

( m ) = ∑

m ′

= 0 M - 1 ⁢

⁢

α

t - 1 ⁡

( m ′

) ⁢

p m ′

⁢

n ⁢

∑

x ⁢

⁢

Pr ⁢

{ x ❘

m } ⁢

Pr ⁢

{ Y t ❘

x }

wherein p<sub>m′

m</sub> is the state transition probability of one of said plurality of mobile users, Pr{x|m} is the probability that said one of said plurality of mobile users locates at position and behavior as x when it is in state m at time t, and Pr{Y_t|x} is the probability that said measured geo-location is Y_t when said one of said plurality of mobile users position and behavior is x at time t.

14. The method of claim 13 wherein said current state is determined by

$z=\arg$

⁢

max m ⁢

{ α

t ⁡

( m ) ❘

m = 1 , 2 , …

⁢

, M - 1 } .

15. The method of claim 14 wherein said proxy gateway comprising a cache for storing push content received from said at least one Web server and said push content is stored in said based on said current state.