Data networks

• US 20050152272A1
• Filed: 06/18/2004
• Published: 07/14/2005
• Est. Priority Date: 02/19/1997
• Status: Active Grant

• Current Assignee: Corvil Ltd. (Pico Quantitative Trading LLC)
• Original Assignee: Dublin Institute of Technology, Cambridge University (Government of United Kingdom), Telia Research AB (Telia Company AB)
• Inventors: Crosby, Simon Andrew, Russell, Raymond Philip, Toomey, Fergal William, Bjoerkman, Nils, Leslie, Ian Malcolm, Lewis, John Trevor, Latour-Henner, Alexander
• Granted Patent: US 7,388,867 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5684 Characteristics of traffic flows
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A data network in which at least one switch is provided with the facility for estimating current network demands using a polygonal approximation to scaled cumulant generating function. The approximation is iteratively refined in accordance with sampled data passing through the switch. The switch estimates the demand associated with a new data processing request as it is received by the switch and decides whether to accept the request based on available resources.

Claims

1. A method of maintaining a target quality of service in a network switch behaving as a buffer of fixed size transmitting a multiplex of current connections at a constant service rate by controlling the admission of a connection requesting admission on the basis of a declared parameter comprising the steps of:

recording the volume of traffic for each current connection over a block of time;

estimating the scaled cumulant generating function (SCGF) λ

(θ

,s) for each connection;

summing all the estimated SCGFs to obtain an aggregate SCGF;

using the aggregate SCGF to obtain an estimated bandwidth requirement for the multiplex of current connections;

providing a predicted SCGF for the connection requesting admission from the declared parameter;

predicting the bandwidth requirement of the connection requesting admission from the predicted SCGF;

summing the estimated and predicted bandwidth requirements; and

accepting the connection requesting admission when the sum of the bandwidth requirements is less than the service rate of the switch.

2. A method as claimed in claim 1 in which the target quality of service (QoS) parameter is the cell loss ratio.

3. A method as claimed in claim 1 in which there is a plurality of sequential blocks of time of variable duration for each connection defined by specifying the initial and final times for each block and in which the SCGF for each connection is updated for each block of time.

4. A method as claimed in claim 1 in which the duration of the block of time is chosen randomly whereby resonance due to periodicites in the multiplex of current connection is avoided.

5. A method as claimed in claim 1 in which the duration of the block of time is dependent on random events occurring during the carrying out of the method.

6. A method as claimed in claim 1 in which the SCGF of each connection is calculated as:

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\mathrm{Log}<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{1}{K}<br><br>\underset{k=1}{\overset{k=K}{\sum <br><br>}}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}$

where;

λ

(θ

,s) is the SCGF,

X_k is the volume of traffic recorded in the k^th time block

T_k is the duration of the k^th time block

and K is the number of time blocks in which the volume of traffic was recorded up to the current time.

7. A method as claimed in claim 1 in which the SCGF is used in an effective bandwidth approximation to provide the estimated bandwidth requirement for the multiplex of current connections.

8. A method as claimed in claim 1 in which the bandwidth requirement is obtained and then the steps are performed of estimating the quality of service the multiplex of current connections would experience if it were queued in a small buffer and refining the estimate of the bandwidth requirement using the estimated quality of service.

9. A method as claimed in claim 1 in which the steps are performed of:

choosing a virtual buffer of size smaller than the buffer size for the switch;

running a simulation of the aggregate of the current connections in the virtual buffer;

recording the quality of service; and

providing a refined effective bandwidth requirement.

10. A method as claimed in claim 1 in which each SCGF is replaced by a polygonal approximation.

11. A method as claimed in claim 1 in which each SCGF is replaced by a polygonal approximation and is iteratively updated each time a volume count of traffic is recorded so that when the volume count X_K in the K^th time block becomes available, the SCGF λ

(θ

,s) for a service rate s is replaced by

$\log \left(\frac{K<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)}+{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}}{K+1}\right)$

where T_K is the length of the K^th time block.

12. A method as claimed in claim 1 in which the SCGF is iteratively updated and the starting value of the SCGF in the iterative updating is the predicted SCGF of the connection requesting admission based on the declared parameter of the connection.

13. A method as claimed in claim 1 in which:

a value θ

₀ of the parameter θ

is chosen; and

the calculated values of λ

(θ

,s) for values of θ

greater than θ

₀ are replaced by

λ

(θ

₀,s)+(p−

s)(θ

−

θ

₀),

where p is the Peak Cell-Rate (PCR) of the connection.

14. A method as claimed in claim 1 in which:

a value θ

₀ of the parameter θ

is chosen to be

$-\frac{\log <br><br>\left(\mathrm{target}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{QoS}\right)}{\mathrm{switch}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{buffer}<br><br>\text{-}<br><br>\mathrm{size}}$

15. A method as claimed in claim 1 of predicting the SCGF λ

(θ

,s) of a connection requesting admission from its declared parameter in which

λ

(θ

,s)=(p−

s)θ

where p the is declared Peak Cell-Rate (PCR).

16. A method as claimed in claim 1 of predicting the SCGF [λ

(θ

,s)] of a connection requesting admission from its declared parameter in which

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\{\begin{array}{cc}<br><br>\left(\mathrm{\sigma <br><br>}-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}⩽<br><br>\frac{c}{\mathrm{\sigma <br><br>\tau <br><br>}},\\ <br><br>\frac{c}{\mathrm{\tau <br><br>}}<br><br>\left(1-\frac{t}{\mathrm{\tau <br><br>}}\right)+\left(t-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}><br><br>\frac{c}{\mathrm{\sigma <br><br>\tau <br><br>}}.\end{array}<br><br><br><br>c=-\log <br><br>\left(\mathrm{target}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{QoS}\right)$

where p is its declared Peak Cell-Rate (PCR),

σ

is its declared Sustainable Cell-Rate (SCR),

τ

is its declared Intrinsic Burst Tolerance (IBT) and

c=−

log (target QoS).

17. A method as claimed in claim 2 in which there is a plurality of sequential blocks of time of variable duration for each connection defined by specifying the initial and final times for each block and in which the SCGF for each connection is updated for each block of time.

18. A method as claimed in claim 2 in which the duration of the block of time is chosen randomly whereby resonance due to periodicities in the multiplex of current connection is avoided.

19. A method as claimed in claim 2 in which the duration of the block of time is dependent on random events occurring during the carrying out of the method.

20. A method as claimed in claim 2 in which the SCGF of each connection is calculated as:

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\mathrm{Log}<br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{1}{K}<br><br>\underset{k=1}{\overset{k=K}{\sum <br><br>}}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}$

where;

λ

(θ

,s) is the SCGF,

X_k is the volume of traffic recorded in the k^th time block

T_k is the duration of the k^th time block

and K is the number of time blocks in which the volume of traffic was recorded up to the current time.

21. A method as claimed in claim 2 in which the SCGF is used in an effective bandwidth approximation to provide the estimated bandwidth requirement for the multiplex of current connections.

22. A method as claimed in claim 2 in which the bandwidth requirement is obtained and then the steps are performed of estimating the quality of service the multiplex of current connections would experience if it were queued in a small buffer and refining the estimate of the bandwidth requirement using the estimated quality of service.

23. A method as claimed in claim 2 in which the steps are performed of:

choosing a virtual buffer of size smaller than the buffer size for the switch;

running a simulation of the aggregate of the current connections in the virtual buffer;

recording the quality of service; and

providing a refined effective bandwidth requirement.

24. A method as claimed in claim 2 in which each SCGF is replaced by a polygonal approximation.

25. A method as claimed in claim 2 in which each SCGF is replaced by a polygonal approximation and is iteratively updated each time a volume count of traffic is recorded so that when the volume count X_K in the k^th time block becomes available, the SCGF λ

(θ

,s) for a service rate s is replaced by

$\log \left(\frac{K<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)}+{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}}{K+1}\right)$

where T_K is the length of the K^th time block.

26. A method as claimed in claim 2 in which the SCGF is iteratively updated and the starting value of the SCGF in the iterative updating is the predicted SCGF of the connection requesting admission based on the declared parameter of the connection.

27. A method as claimed in claim 2 in which:

a value θ

₀ of the parameter θ

is chosen; and

the calculated values of λ

(θ

,s) for values of a greater than θ

₀ are replaced by

λ

(θ

₀,s)+(p−

s)(θ

−

θ

₀),

where p is the Peak Cell-Rate (PCR) of the connection.

28. A method as claimed in claim 2 in which:

a value θ

₀ of the parameter θ

is chosen to be

$-\frac{\log <br><br>\left(\mathrm{target}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{QoS}\right)}{\mathrm{switch}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{buffer}<br><br>\text{-}<br><br>\mathrm{size}}$

29. A method as claimed in claim 2 of predicting the SCGF λ

(θ

,s) of a connection requesting admission from its declared parameter in which

λ

(θ

,s)=(p−

s)θ

where p is the declared Peak Cell-Rate (PCR).

30. A method as claimed in claim 2 of predicting the SCGF [λ

(θ

,s)] of a connection requesting admission from its declared parameter in which

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\{\begin{array}{cc}<br><br>\left(\mathrm{\sigma <br><br>}-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}⩽<br><br>\frac{c}{\mathrm{\sigma <br><br>\tau <br><br>}},\\ <br><br>\frac{c}{\mathrm{\tau <br><br>}}<br><br>\left(1-\frac{t}{\mathrm{\tau <br><br>}}\right)+\left(t-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}><br><br>\frac{c}{\mathrm{\sigma <br><br>\tau <br><br>}}.\end{array}$

where p is its declared Peak Cell-Rate (PCR),

σ

is its declared Sustainable Cell-Rate (SCR),

τ

is its declared Intrinsic Burst Tolerance (IBT) and

c=−

log (target QoS).

31. A method as claimed in claim 1 in which the target quality of service parameter is the cell loss ratio and in which there is a plurality of sequential blocks of time of variable duration for each connection defined by specifying the initial and final times for each block and in which the SCGF for each connection is updated for each block of time.

32. A method as claimed in claim 31 in which the duration of the block of time is chosen randomly whereby resonance due to periodicities in the multiplex of current connection is avoided.

33. A method as claimed in claim 31 in which the duration of the block of time is dependent on random events occurring during the carrying out of the method.

34. A method as claimed in claim 31 in which the SCGF of each connection is calculated as:

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\log <br><br>\frac{1}{K}<br><br>\underset{k=1}{\overset{k=K}{\sum <br><br>}}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}$

where;

λ

(θ

,s) is the SCGF.

X_k is the volume of traffic recorded in the k^th time block

T_k is the duration of the k^th time block

and K is the number of time blocks in which the volume of traffic was recorded up to the current time.

35. A method as claimed in claim 31 in which the SCGF is used in an effective bandwidth approximation to provide the estimated bandwidth requirement for the multiplex of current connections.

36. A method as claimed in claim 31 in which the bandwidth requirement is obtained and then the steps are performed of estimating the quality of service the multiplex of current connections would experience if it were queued in a small buffer and refining the estimate of the bandwidth requirement using the estimated quality of service.

37. A method as claimed in claim 31 in which the steps are performed of:

choosing a virtual buffer of size smaller than the buffer size for the switch;

running a simulation of the aggregate of the current connections in the virtual buffer;

recording the quality of service; and

providing a refined effective bandwidth requirement.

38. A method as claimed in claim 31 in which each SCGF is replaced by a polygonal approximation.

39. A method as claimed in claim 31 in which each SCGF is replaced by a polygonal approximation and is iteratively updated each time a volume count of traffic is recorded so that when the volume count X_K in the k^th time block becomes available, the SCGF λ

(θ

,s) for a service rate s is replaced by

$\log \left(\frac{K<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{e<br><br>}}^{\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)}+{\mathrm{e<br><br>}}^{\mathrm{\theta <br><br>}<br><br>\left(X_k-{\mathrm{sT}}_k\right)}}{K+1}\right)$

where T_K is the length of the K^th time block.

40. A method as claimed in claim 31 in which the SCGF is iteratively updated and the starting value of the SCGF in the iterative updating is the predicted SCGF of the connection requesting admission based on the declared parameter of the connection.

41. A method as claimed in claim 31 in which:

a value θ

₀ of the parameter θ

is chosen; and

the calculated values of λ

(θ

,s) for values of θ

greater than θ

₀ are replaced by

λ

(θ

₀,s)+(p−

s)(θ

−

θ

₀),

where p is the Peak Cell-Rate (PCR) of the connection.

42. A method as claimed in claim 31 in which:

a value θ

₀ of the parameter θ

is chosen to be

$-\frac{\log <br><br>\left(\mathrm{target}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{QoS}\right)}{\mathrm{switch}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{buffer}<br><br>\text{-}<br><br>\mathrm{size}}$

43. A method as claimed in claim 31 of predicting the SCGF λ

(θ

,s) of a connection requesting admission from its declared parameter in which

λ

(θ

,s)=(p−

s)θ

where p is the declared Peak Cell-Rate (PCR).

44. A method as claimed in claim 31 of predicting the SCGF [λ

(θ

,s)] of a connection requesting admission from its declared parameter in which

$\mathrm{\lambda <br><br>}<br><br>\left(\mathrm{\theta <br><br>},s\right)=\{\begin{array}{cc}<br><br>\left(\mathrm{\sigma <br><br>}-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}\le <br><br>\frac{c}{\mathrm{\sigma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\tau <br><br>}},\\ <br><br>\frac{c}{\mathrm{\tau <br><br>}}<br><br>\left(1-\frac{t}{\mathrm{\tau <br><br>}}\right)+\left(t-s\right)<br><br>\mathrm{\theta <br><br>},& \mathrm{\theta <br><br>}><br><br>\frac{c}{\mathrm{\sigma <br><br>\tau <br><br>}}.\end{array}$

where p is its declared Peak Cell-Rate (PCR),

σ

is its declared Sustainable Cell-Rate (SCR),

τ

is its declared Intrinsic Burst Tolerance (IBT) and

c=−

log (target QoS).

45. A data network comprising:

a network switch behaving as a buffer of fixed size when transmitting a multiplex of current connections at a constant service rate;

a plurality of connectors feeding the switch;

means for recording the volume of traffic of current connections for each current connector to the switch over a block of time;

means for estimating the scaled cumulant generating function SCGF for each current connection recorded;

means for summing the estimated SCGFs to obtain an aggregate SCGF;

means for using the aggregate SCGF to obtain an estimated bandwidth requirement for the multiplex of current connections;

means for presenting a new current connection requesting admission to the network by providing a declared parameter of the connection requesting admission;

prediction means for providing a predicted SCGF for the new current connection requesting admission to the network from the declared parameter;

means for predicting the bandwidth requirement of the connection requesting admission from the predicted SCGF;

means for summing the estimated and predicted bandwidth requirements for the switch to produce a revised bandwidth requirement; and

control means for deciding to admit the connection requesting admission on the basis of the revised bandwidth requirement for the switch.

46. A network as claimed in claim 45 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time to control the duration of the block of time.

47. A network as claimed in claim 45 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time in a random fashion to vary the duration of each block of time.

48. A network as claimed in claim 45 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time having regard to the capacity of the remainder of the network to handle the computations.

49. A network as claimed in claim 46 in which the means for using the aggregate SCGF to obtain an estimated bandwidth requirement includes processing means for carrying out modelling of the current connections to obtain a refined effective bandwidth requirement.

50. A network as claimed in claim 45 in which the prediction means includes means for providing the predicted SCGF as a polygonal approximation.

51. A network management system for a multiplex of current connections providing a real time admission control over a connection requesting admission comprising:

a network switch capable of transmitting signals at a constant service rate;

means for providing a model of the switch in terms of a buffer of fixed size;

a plurality of connectors feeding the switch;

means for recording the volume of traffic of current connections for each current connector to the switch over a block of time;

means for estimating the scaled cumulant generating function SCGF for each current connection recorded;

means for summing the estimated SCGFs to obtain an aggregate SCGF;

means for using the aggregate SCGF to obtain an estimated bandwidth requirement for the multiplex of current connections;

means for presenting a new current connection requesting admission to the network by providing a declared parameter of the connection requesting admission;

prediction means for providing a predicted SCGF for the new current connection requesting admission to the network from the declared parameter;

means for predicting the bandwidth requirement of the connection requesting admission from the predicted SCGF;

means for summing the estimated and predicted bandwidth requirements for the switch to produce a revised bandwidth requirement; and

a control means for receiving the request of the new current connection requesting admission and the revised bandwidth requirement and for deciding to admit the connection requesting admission on the basis of the revised bandwidth requirement for the switch.

52. A network system as claimed in claim 51 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time to control the duration of the block of time.

53. A network as claimed in claim 51 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time in a random fashion to vary the duration of each block of time.

54. A network as claimed in claim 51 in which the means for recording the volume of traffic includes means for specifying the initial and final times for each block of time having regard to the capacity of the remainder of the network to handle the computations.

55. A network as claimed in claim 51 in which the means for using the aggregate SCGF to obtain an estimated bandwidth requirement includes processing means for carrying out modelling of the current connections to obtain a refined effective bandwidth requirement.

56. A network as claimed in claim 51 in which the prediction means includes means for providing the predicted SCGF as a polygonal approximation.