Method of transmitting data

• US 7,599,296 B2
• Filed: 08/30/2002
• Issued: 10/06/2009
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Tartarelli, Sandra, Banchs, Albert
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US10/232,321
• Publication Number:
  US 20030086413A1
• Time in Patent Office: 2,594 Days
• Field of Search: 370/229, 370/230, 370/235, 370/252, 370/253, 370/389, 370/386, 370/428, 370401-402, 370/232, 370/235.1, 370/395.41, 370/395.42, 370/395.5, 370/395.52, 370/231, 370/233, 370/237, 370/289, 370/412, 370/230.1, 370/248, 370/234, 370/395.21
• US Class Current: 370/235.1
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method of transmitting data from customers (C1, C2, C3, C4, C5, C6, C7, C8, C9, C10) over a computer network, in particular over the Internet, where the data to be sent is split into packets, in particular into IP packets, where each packet is marked by one of at least two states (IN, OUT) and where the states (IN, OUT) determine which packets are dropped first, if packets are dropped during transmission, is, with regard to optimizing the drop rate of the packets, characterized in that the marking of the packet with a state of high drop precedence (OUT) is based on a random probability (p).

Claims

1. A method of transmitting data from customers over a computer network in packets, the method comprising:

marking each of said packets by a first state or a second state by a network device;

wherein said first state has a high drop precedence and is based on a random probability (p) calculated with reference to a previous random probability and a previous token bucket occupancy;

wherein the packet is marked by a first state if a length of the packet is above a token bucket occupancy of a token bucket; and

wherein the probability (p) at a given step is expressed as

p=k1×

(b_ref−

b)−

k2×

(b_ref−

b_old)+p_old

and that at a next step p_old is set equal to p and b_old is set equal to b, wherein p_old and b_old are values that are respectively the values p and b had at a previous update time,

b_ref is a desired token bucket occupancy,

b is a total bucket size,

k1 is a constant, and

k2 is a constant.

2. The method of claim 1, wherein the marking of the packet with a high drop precedence is based on a single random probability.

3. The method of any of claims 1 or 2, wherein the probability (p) is measured for the traffic of each of said customer.

4. The method of any of claims 1 or 2, wherein the computers of the network are linked with each other.

5. The method of claim 4, wherein several of said customers share at least parts of a link.

6. The method of claim 4, wherein the links have maximum bandwidths or the customers have been provided an assigned maximum bandwidth for the purpose of data transmission.

7. The method of claim 6,wherein the traffic of at least one of said the customers is measured.

8. The method of claim 6, wherein a packet is dropped when an assigned maximum bandwidth is exceeded during the transmission or the maximum bandwidth of the connection is not sufficient to transmit the packets.

9. The method of claim 6, wherein the marking of the packet is based on the comparison of the current bandwidth with the assigned maximum bandwidth.

10. The method of claim 9, wherein the comparison of the current bandwidth with the assigned maximum bandwidth is based on a token bucket.

11. The method of claim 6, wherein the packet is marked with a high drop precedence if the current bandwidth is higher than the assigned maximum bandwidth.

12. The method of any of claims 1 or 2, further comprising transmitting said data via a TCP transport protocol.

13. The method of any of claims 1 or 2, wherein the packets are forwarded in a DiffServ environment.

14. The method of any of claims 1 or 2, wherein the marking is done by means of two states.

15. The method of any of claims 1 or 2, wherein the probability (p) is compared to a random number (u) evenly distributed between 0 and 1.

16. The method of claim 15, wherein the packet is marked with a high drop precedence if the probability (p) is greater than the random number (u).

17. The method of any of claims 1 or 2, wherein the packets are put into a buffer assigned to a core node.

18. The method of any of claims 1 or 2, wherein, in case of packet congestion during transmission, the packets are marked with a high drop precedence are discarded.

19. The method of any of claims 1 or 2, further comprising stabilizing the token bucket occupancy by linearizing the change in a TCP window size, wherein the change in the TCP window size (w) is expressed as

$\stackrel{.}{w}=\frac{1}{R\; <li></li>\left(t\right)}-\frac{W<br><br>\left(t\right)·<br><br>W<br><br>\left(t-R<br><br>\left(t\right)\right)}{2·<br><br>R<br><br>\left(t-R<br><br>\left(t\right)\right)}<br><br>p<br><br>\left(t-R<br><br>\left(t\right)\right),$

wherein

R(t) is a round trip time as a function of time, and

W(t) is a TCP window size as function of time.

20. The method of any of claims 1 or 2, further comprising stabilizing the token bucket occupancy by linearizing the change in a token bucket occupancy, wherein the change in the token bucket occupancy (b) is expressed as

$\stackrel{.}{b}=-\frac{W}{}$

( t ) R ⁢

( t ) ⁢

N ⁢

( t ) + C ,

wherein

N(t) is a number of TCP sources of the customer as a function of time,

W(t) is a TCP window size as function of time,

R(t) is the round trip time as a function of time, and

C is an assigned maximum bandwidth.

21. The method of claim 19, wherein the change in a TCP window size (W) is linearized in an operation point, preferably at constant round trip time (R_o) or constant number of TCP sources (N) expressed as

$\begin{array}{c}\delta \end{array}$

⁢

W . = N R 0 2 ⁢

C ⁢

( δ

⁢

⁢

W + δ

⁢

⁢

W ⁡

( t - R 0 ) ) - R 0 ⁢

C 2 2 ⁢

N 2 ⁢

δ

⁢

⁢

p ⁡

( t - R 0 ) , δ

⁢

b . = - N R 0 ⁢

δ

⁢

⁢

W ,

where

δ

w=w−

w_o

δ

b=b−

b_o

δ

p=p−

p_o,

C is an assigned maximum bandwidth, b is a token bucket occupancy,

W is a TCP window size, and

w_o, b_o, and p_o are determined by setting W=0 and b=0.

22. The method of any of claim 1 or 2, wherein the token bucket occupancy (b) is stabilized by way of a controller whose transfer function is expressed as

$C$

( s ) = K ⁢

s z + 1 s ,

wherein

C(s) is a controller transfer function,

s is a LaPlace parameter,

z is a zero of the controller, and

K is a constant.

23. The method of claim 22,

wherein a zero of the controller is to

$z={\omega }_{}$

g = 0.1 ⁢

2 ⁢

⁢

N - R + 2 ⁢

C

in order to have the controller dominate the closed-loop behavior,

wherein

ω

_g is a maximum frequency,

N−

is a minimum in a range for a number of TCP sources where N≧

N−

,

R+ is a maximum range of round-trip time (R_o) where R_o≦

R+, and

C is an assigned maximum bandwidth.

24. The method of claim 22, wherein especially by invoking a Nyquist criterion a gain (K) in the controller is set to

$K=0.007$

( 2 ⁢

N - ) 3 ( 2 ⁢

R + ⁢

C 2 ) 2 ,

wherein

N−

is a minimum in a range for a number of TCP sources where N≧

N−

,

R+ is a maximum range of round-trip time (R_o) where R_o≦

R+, and

C is an assigned maximum bandwidth.

25. The method of claim 1, wherein k1 is computed by a bilinear transformation expressed as

$\mathrm{k1}=K$

( T 2 + 1 ω

g ) ,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

26. The method of claim 1, wherein a k2 is computed by a bilinear transformation expressed as

$\mathrm{k2}=-K$

( T 2 - 1 ω

g ) ,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

27. The method of claim 1, wherein the computers of the network are linked with each other.

28. The method of claim 5, wherein the links have maximum bandwidths or the customers have been provided an assigned maximum bandwidth for the purpose of data transmission.

29. The method of claim 7, wherein the links have maximum bandwidths or the customers have been provided the assigned maximum bandwidth for the purpose of data transmission.

30. The method of claim 7, wherein the marking of the packet is based on the comparison of the current bandwidth with the assigned maximum bandwidth.

31. The method of claim 8, wherein the marking of the packet is based on the comparison of the current bandwidth with the assigned maximum bandwidth.

32. The method of claim 7, wherein the packet is marked with a high drop precedence if the current bandwidth is higher than the assigned maximum bandwidth.

33. The method of claim 8, wherein the packet is marked with a high drop precedence if the current bandwidth is higher than the assigned maximum bandwidth.

34. The method of claim 9, wherein the packet is marked with a high drop precedence if the current bandwidth is higher than the assigned maximum bandwidth.

35. The method of claim 10, wherein the packet is marked with a high drop precedence if the current bandwidth is higher than the assigned maximum bandwidth.

36. The method of claim 20, wherein the change in the token bucket occupancy (b) is linearized in an operation point, preferably at constant round trip time (R_o) or constant number of TCP sources (N) expressed as

$\delta$

⁢

W . = N R 0 2 ⁢

C ⁢

( δ

⁢

⁢

W + δ

⁢

⁢

W ⁡

( t - R 0 ) ) - R 0 ⁢

C 2 2 ⁢

N 2 ⁢

δ

⁢

⁢

p ⁡

( t - R 0 ) , δ

⁢

⁢

b = - N R 0 ⁢

δ

⁢

⁢

W ,

where

δ

w=w−

w_o

δ

b=b−

b_o

δ

p=p−

p_o″

, and

C is an assigned maximum bandwidth, W is a TCP window size and

wo, bo, and po are determined by setting W=0 and b=0.

37. The method of claim 23, wherein by invoking a Nyquist criterion a gain (K) in the controller is set to

$K=0.007$

( 2 ⁢

N - ) 3 ( 2 ⁢

R + ⁢

C 2 ) 2 ⁢

•

,

wherein

N−

is a minimum in a range for a number of TCP sources where N≧

N−

,

R+ is a maximum range of round-trip time (R_o) where R_o≦

R+, and

C is an assigned maximum bandwidth.

38. The method of claim 23, wherein a k1 is computed by a transformation expressed as

$k$

⁢

1 = K ⁡

( T 2 + 1 ω

g ) ⁢

•

,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

39. The method of claim 24, wherein k1 is computed by a transformation expressed as

$k$

⁢

1 = K ⁡

( T 2 + 1 ω

g ) ⁢

•

,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

40. The method of claim 23, wherein k2 is computed by a transformation expressed as

$k$

⁢

2 = - K ⁡

( T 2 - 1 ω

g ) ⁢

•

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

41. The method of claim 24, wherein k2 is computed by a transformation expressed as

$k$

⁢

2 = - K ⁡

( T 2 - 1 ω

g ) ⁢

•

,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.

42. The method of claim 25, wherein k2 is computed by a preferably bilinear transformation expressed as

$k$

⁢

2 = - K ⁡

( T 2 - 1 ω

g ) ⁢

•

,

wherein

K is a constant,

T is a sampling time, and

w_g is an inverse of a control constant.