Admission control system and method for media-on-demand servers

• US 6,330,609 B1
• Filed: 11/07/1997
• Issued: 12/11/2001
• Est. Priority Date: 11/07/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Garofalakis, Minos N., Ozden, Banu, Silberschatz, Abraham, Ioannidis, Yannis E.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/966,095
• Time in Patent Office: 1,495 Days
• Field of Search: 709/229, 709/219, 709/225, 709/203, 711/167
• US Class Current: 709/229
• CPC Class Codes: H04Q 3/0066 Bandwidth allocation or management

Abstract

In a server system having a predetermined total bandwidth providing data files to a plurality of clients in response to requests received from the clients, a method for providing admission control comprises the steps of allocating a plurality of channel partitions to a plurality of channel groups such that each channel group includes one or more of the channel partitions. The system then obtains a channel group number based on the length of the data file requested by one of the clients and transmits the requested data file when a channel group corresponding to the obtained channel group number contains a vacant channel partition.

Claims

1. In a server system having a predetermined total bandwidth providing data files to a plurality of clients in response to requests received from said clients, a method for providing admission control comprises the steps of:

dividing said predetermined total bandwidth into a plurality of channel partitions;

allocating said plurality of channel partitions to a plurality of channel groups such that each channel group includes one or more of said channel partitions;

obtaining a channel group number for a data file based on the length of said data file requested by one of said clients; and

transmitting said requested data file when a channel group corresponding to said channel group number contains a vacant channel partition.

2. The method in accordance with claim 1 further comprising the step of denying transmittal of said requested data file when all channel partitions in said channel group are in-use.

3. The method in accordance with claim 1 wherein prior to said step of dividing, the method comprises the step of obtaining a ratio Δ

corresponding to the longest specifiable duration of data, l_max, requested among said requests over the shortest specifiable duration of data, l_min, requested among said requests.

4. The method in accordance with claim 3 wherein said longest and shortest specifiable durations correspond respectively to the longest and shortest data files stored in said server system.

5. The method in accordance with claim 3 wherein said longest and shortest specifiable durations are provided by an administrator of said server system.

6. The method in accordance with claim 3 wherein said longest and shortest specifiable durations is dynamically obtained based on the length of files requested by a plurality of said clients.

7. The method in accordance with claim 3 wherein said channel partitions are divided into ┌

log Δ

┐

channel groups and requests from said clients require the same bandwidth.

8. The method in accordance with claim 7 wherein each channel group contains the same number of channel partitions.

9. The method in accordance with claim 8 further comprising the step of allocating a channel group number “

i”

in response to a request based on the length of the data file requested, l_j, such that

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

10. The method in accordance with claim 9 further comprising the steps of:

searching for a vacant channel partition within channel groups equal and lower than said allocated channel group number “

i”

; and

transmitting said requested data file when a vacant channel partition is located.

12. The method in accordance with claim 1 further comprising the step of denying transmittal of said requested data file when all channel partitions in said channel group are in-use.

11. In a server system having a predetermined total bandwidth providing data files to a plurality of clients in response to requests received from said clients, a method for providing admission control comprises the steps of:

dividing said predetermined total bandwidth into a plurality of channel partitions, wherein said number of channel partitions is based on the probability of file lengths requested by said plurality of clients;

allocating said plurality of channel partitions to a plurality of channel groups such that each channel group contains a number of said channel partitions;

obtaining a channel group number for a data file based on the length of said data file requested by one of said clients; and

transmitting said requested data file when a channel group corresponding to said channel group number contains a vacant channel partition.

13. The method in accordance with claim 11 wherein prior to said step of dividing, the method comprises the step of obtaining a ratio Δ

corresponding to the longest specifiable duration of data, l_max, requested among said requests over the shortest specifiable duration of data, l_min, requested among said requests.

14. The method in accordance with claim 13 wherein said longest and shortest specifiable durations correspond respectively to the longest and shortest data files stored in said server system.

15. The method in accordance with claim 13 wherein said longest and shortest specifiable durations are provided by an administrator of said server system.

16. The method in accordance with claim 13 wherein said longest and shortest specifiable durations is dynamically obtained based on the length of files requested by a plurality of said clients.

17. The method in accordance with claim 13 wherein said channel partitions are divided into ┌

log Δ

┐

channel groups and requests from said clients require the same bandwidth.

18. The method in accordance with claim 17 further comprising the step of:

allocating a plurality of data file lengths, l_j, to one of said channel groups “

i,”

such that the range of data file lengths in each channel group i is

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

19. The method in accordance with claim 18 further comprising the step of calculating a cumulative probability

P_j=Σ

l_j.p_j

wherein l_j is the length of a data file allocated to said channel group i and p_j is the probability that the length of an incoming request is l_j.

20. The method in accordance with claim 19 further comprising the step of allocating to each channel group a number of channel partitions C_i equal to P_i×

c for i=1, . . . , ┌

log Δ

┐

, wherein c is the number of total available channels in said server.

21. The method in accordance with claim 20 further comprising the step of allocating a channel group number “

i”

in response to a request based on the length of the data file requested, l_j, such that

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

22. The method in accordance with claim 21 further comprising the steps of:

searching for a vacant channel partition within channel groups equal and lower than said allocated channel group number “

i”

; and

transmitting said requested data file when a vacant channel partition is located.

23. In a server system having a predetermined total bandwidth providing data files to a plurality of clients in response to requests received from said clients, a method for providing admission control comprises the steps of:

obtaining a ratio Δ

corresponding to the longest specifiable duration of data, l_max, requested among said requests over the shortest specifiable duration of data, l_min, requested among said requests;

dividing the total server bandwidth into ┌

log Δ

┐

bandwidth partitions;

obtaining a bandwidth partition number based on the length of a data file requested by one of said clients; and

transmitting said requested data file when a bandwidth partition corresponding to said bandwidth partition number is vacant.

24. The method in accordance with claim 23 further comprising the step of denying transmittal of said requested data file when said bandwidth partition is in-use.

25. The method in accordance with claim 23 wherein said longest and shortest specifiable durations correspond respectively to the longest and shortest data files stored in said server system.

26. The method in accordance with claim 23 wherein said longest and shortest specifiable durations are provided by an administrator of said server system.

27. The method in accordance with claim 23 wherein said longest and shortest specifiable durations is dynamically obtained based on the length of files requested by a plurality of said clients.

28. The method in accordance with claim 23 further comprising the step of allocating a bandwidth partition number “

i”

in response to a request based on the length of the data file requested, l_j, such that

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

29. The method in accordance with claim 28 further comprising the steps of:

searching for a vacant bandwidth partition corresponding to a bandwidth partition number equal and lower than said allocated bandwidth partition number “

i”

; and

transmitting said requested data file when a vacant bandwidth partition is located.

30. In a server system having a predetermined total bandwidth providing data files to a plurality of clients in response to requests received from said clients, a method for providing admission control comprises the steps of:

dividing said predetermined total bandwidth into a plurality of channel partitions;

allocating a size to said plurality of bandwidth partitions that defines said total bandwidth such that the size of each one of said bandwidth partition is based on the probability of file lengths requested by said plurality of clients;

obtaining a bandwidth partition number for a data file based on the length of said data file requested by one of said clients; and

transmitting said requested data file when a bandwidth partition corresponding to said bandwidth partition number is vacant.

31. The method in accordance with claim 30 further comprising the step of denying transmittal of said requested data file when said bandwidth partition is in-use.

32. The method in accordance with claim 30 wherein prior to said step of dividing, the method comprises the step of obtaining a ratio Δ

corresponding to the longest specifiable duration of data, l_max, requested among said requests over the shortest specifiable duration of data, l_min requested among said requests.

33. The method in accordance with claim 32 wherein said longest and shortest specifiable durations correspond respectively to the longest and shortest data files stored in said server system.

34. The method in accordance with claim 32 wherein said longest and shortest specifiable durations are provided by an administrator of said server system.

35. The method in accordance with claim 32 wherein said longest and shortest specifiable durations is dynamically obtained based on the length of files requested by a plurality of said clients.

36. The method in accordance with claim 32 wherein the number of said bandwidth partitions is ┌

log Δ

┐

.

37. The method in accordance with claim 36 further comprising the step of:

allocating a plurality of data file lengths, l_j, to one of said bandwidth partitions, i, such that the range of data file lengths in each bandwidth partition i is

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

38. The method in accordance with claim 37 further comprising the step of calculating a cumulative probability

39. The method in accordance with claim 38 further comprising the step of allocating to each bandwidth partition B_i a size equal to P_i×

B for i=1, . . . , ┌

log Δ

┐

, wherein B is the total available bandwidth of said server.

40. The method in accordance with claim 39 further comprising the step of allocating a bandwidth number “

i”

in response to a request based on the length of the data file requested, l_j such that

2<sup>i−

1</sup>.l_min≦

l_j<

2ⁱ.l_min allowing for l_j=2ⁱ.l_min if i=┌

log Δ

┐

.

41. The method in accordance with claim 40 further comprising the steps of:

searching for a vacant bandwidth partition having a number equal or lower than bandwidth partition number “

i”

; and

transmitting said requested data file when one or more vacant bandwidth partitions are located.

42. The method in accordance with claim 40 wherein said data file is transmitted via a portion of an available bandwidth partition based on the bandwidth requirement of a request received from one of said clients.