Bandwidth management system

• US 7,478,158 B1
• Filed: 03/01/2004
• Issued: 01/13/2009
• Est. Priority Date: 03/01/2004
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Rodgers, Dwight O., Morris, James T., Hosmer, Basil C., Sellier, Laurent E., Connolly, Brian P.
• Primary Examiner(s): Cardone; Jason D
• Assistant Examiner(s): Pollack; Melvin H
• Application Number:
  US10/791,311
• Time in Patent Office: 1,779 Days
• Field of Search: 709/203, 709217-219, 709/226, 709/229, 709/231, 709/234, 709/249, 370/310, 370/395.21, 370/395.41, 370/395.42, 370/395.43, 705/52
• US Class Current: 709/226
• CPC Class Codes: H04L 12/14 Charging , metering or billing arrangements for data wireline or wireless communications
• CPC Class Codes: H04L 12/1453 Methods or systems for payment or settlement of the charges for data transmission involving significant interaction with the data transmission network
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A method of enforcing network bandwidth limitation includes receiving a request from a client for transmission of a server'"'"'s feed data and receiving a client timestamp from the client. The method further includes determining if feed data in a previous transmission from the server to the client has been lost, and if so, reimbursing the client for the lost data. The method further includes determining if the client is eligible to receive the requested feed data transmission from the server, and if the client is eligible, then immediately transmitting of the most recent available requested feed data from the server to the client, but if the client is not eligible, then preventing the transmission and withholding the feed data from the client without prolonging the duration of any network connection from the server to the client.

Claims

1. A system for enforcing network bandwidth limitation, comprising:

an eligibility system that determines if a client or multiple clients on said network is eligible to receive requested feed data transmission from a server or multiple servers on said network based upon an amount of time since last successful receipt of a feed data transmission;

if said client is not eligible, then said system is able to prevent said transmission and to withhold said feed data from said client without prolonging the duration of any network connection from said server to said client;

otherwise

if said client is eligible, then said system is able to permit immediate transmission of the most recent available requested feed data from said server to said client; and

said system is able to determine if requested feed data in previous transmissions from said server to said client has been lost;

if said previously requested feed data has been lost, then said system is able to reimburse said client for said lost requested feed data, otherwise not to reimburse said client.

2. The system of claim 1 wherein said network is a wireless network.

3. The system of claim 1 wherein said network is selected from a local area network and the Internet.

4. The system of claim 1 wherein said multiple clients are personal computers.

5. The system of claim 1 wherein said multiple clients are wireless telephones.

6. The system of claim 1 wherein said server comprises a feed timestamp that monotonically increases whenever said feed data at said server is updated.

7. The system of claim 1 wherein said client comprises permanent storage for client data and a client timestamp.

8. The system of claim 1 comprising a permanent storage system for expected timestamp, confirmed timestamp, and copies of eligibility system data.

9. The system of claim 1 comprising:

a sequence of bandwidth-limitation descriptions, each of which consists of a start-time and a bandwidth-limitation data, such that said bandwidth-limitation descriptions are sorted by start-time, such that an Nth bandwidth-limitation description defines the bandwidth limitation from its start-time to the start-time of an N+1 th bandwidth-limitation description, such that the last bandwidth-limitation description of said sequence of bandwidth-limitation descriptions defines said bandwidth limitation from its start-time to 24, and such that said start-times are interpreted as hours since midnight, and repeat after each day.

10. The system of claim 1 further able to compute for said client and said feed data the earliest elapsed time E at which said client will be eligible to receive said feed data.

11. The system of claim 1 wherein the amount of said feed data eligible to be received by said client from said server at a current time is determined as a function of credit existing at the time of a previous data transmission, time elapsed between said time of previous data transmission and said current time, the size of said previous data transmission, and bandwidth limitation configuration settings.

12. The system of claim 11, wherein the amount of said feed data eligible to be received by said client from said server is computed by the equations:

new-credit=X*Exp(−

C*T)−

(K/C)*(Exp(−

C*T)−

1), where

C=−

ln(1−

R/M);

K=R*C/(1−

Exp(C)), and

where X is the previous value of credit reduced by the size of the last transmission, T is the number of seconds elapsed between the last-transmission-time and the current time, Exp denotes the exponential function, in denotes the natural logarithm function, K and C are intermediate computational values, M corresponds to the amount of data credit that will be accumulated if an infinite amount of time elapses with no requests, and R corresponds to the amount of data that will be transmitted during a time interval of unity length.

13. A method of enforcing network bandwidth limitation, said method comprising:

receiving a request for transmission of data;

computing transmission eligibility; and

modifying eligibility data based upon an amount of time since last successful receipt of a feed data transmission.

14. The method of claim 13 wherein said request is for transmission of high priority data and wherein said high priority data may be sent at all times, regardless of the computed transmission eligibility.

15. The method of claim 14 further comprising ignoring said computed transmission eligibility, such that the increased bandwidth usage by said high-priority data reduces bandwidth available for future standard transmissions.

16. A method of enforcing network bandwidth limitation, said method comprising:

receiving a request from a client for transmission of a server'"'"'s feed data;

receiving a client timestamp from said client;

determining if feed data in a previous transmission from said server to said client has been lost, and if so, reimbursing said client for said lost data;

determining if said client is eligible to receive said requested feed data transmission from said server by computing the elapsed time between a last feed data transmission and a current feed data request;

multiplying said elapsed time by a predetermined bandwidth allocation, adding the product to a stored credit value reduced by the size of said last feed data transmission, and storing the result as a new credit value; and

if said new credit value is greater than zero, said client is eligible;

otherwise said client is not eligible;

if said client is eligible, then immediately transmitting the most recent available requested feed data from said server to said client; and

if said client is not eligible, then preventing said transmission and withholding said feed data from said client without prolonging the duration of any network connection from said server to said client.

17. The method of claim 16 wherein said determining if feed data has been lost comprises comparing said client timestamp to an expected timestamp, and if equal, then writing said expected timestamp into a confirmed timestamp and writing an expected data into a confirmed data, and if smaller, then making no change to said confirmed timestamp and said confirmed data.

18. The method of claim 16 wherein said determining if said client is eligible comprises:

providing a sequence of bandwidth-limitation descriptions, each of which consists of a start-time and a bandwidth-limitation data;

sorting said bandwidth-limitation descriptions by start-time, such that an Nth bandwidth-limitation description defines the bandwidth limitation from its start-time to the start-time of an N+1th bandwidth-limitation description, such that the last bandwidth-limitation description defines the bandwidth limitation from its start-time to 24, and such that said start-times are interpreted as hours since midnight, and repeat after each day.

19. The method of claim 18 further comprising:

selecting the set of said bandwidth-limitation descriptions which overlaps with the elapsed time between the most recent previous transmission and the current time;

computing new credit, based on the size of said most recent previous transmission, the previous stored value of credit, and the elapsed time from said last transmission time to the earlier of the current-time or the end of said bandwidth limitation description;

for each remaining bandwidth-limitation description, in sequence, computing new credit, based on zero transmission size, the credit returned from the previous bandwidth limitation description, and the elapsed time from the start of said bandwidth limitation description and the earlier of said current-time or end of said bandwidth limitation description;

storing the result as a new credit value; and

if said new credit value is greater than zero, said client is eligible;

otherwise

said client is not eligible and no feed data transmission is available to said client.

20. The method of claim 18 further comprising:

determining a single bandwidth-limitation-description whose time-slice encompasses the current time;

if said time-slice encompasses the last transmit time, then computing new credit, based on the size of said most recent previous transmission, the previous stored value of credit, and the elapsed time from said last transmission time to the earlier of the current-time or the end of said bandwidth limitation description;

otherwise,

if said time-slice does not encompass said last transmit time, then computing said new credit, based on the size of said last transmission, zero previous credit, and the interval from the beginning of said time-slice to said current time.

21. A method of enforcing network bandwidth limitation, wherein the amount of feed data eligible to be received by a client from a server at a current time is determined as a function of credit existing at the time of a previous data transmission, time elapsed between said time of previous successful data transmission and said current time, the size of said previous data transmission, and bandwidth limitation configuration settings.

22. The method of claim 21 wherein said amount of said feed data eligible to be received by said client from said server is computed by the equations:

new-credit=X*Exp(−

C*T)−

(K/C)*(Exp(−

C*T)−

1);

where

C=−

ln(1−

R/M);

K=R*C/(1−

Exp(C)); and

where X is the previous value of credit reduced by the size of the last transmission, T is the number of seconds elapsed between a last-transmission-time and a current time, Exp denotes the exponential function, ln denotes the natural logarithm function, K and C are intermediate computational values, M corresponds to the amount of data credit that will be accumulated if an infinite amount of time elapses with no requests, and R corresponds to the amount of data that will be transmitted during a time interval of unity length.

23. The method of claim 21 further comprising computing for said client and said feed data the earliest elapsed time E at which said client will be eligible to receive said feed data.

24. A system for enforcing network bandwidth limitation, said system comprising:

means for receiving a request from a client for transmission of a server'"'"'s feed data;

means for receiving a client timestamp from said client;

means for determining if feed data in a previous transmission from said server to said client has been lost, and if so, reimbursing said client for said lost data; and

means for determining if said client is eligible to receive said requested feed data transmission from said server based upon an amount of time since last successful receipt of a feed data transmission.