Granted Patent B2

US 8,289,851 · App. 11/799,036 · Granted Oct 16, 2012

Abstract

Claims (219)

1. A method for controlling admission of new flows at a node in a network of nodes interconnected by links, the method comprising:

(a) for each of a plurality of incoming packets arriving at the node, each incoming packet corresponding to an active flow traversing the node:

(a1) randomly selecting a packet from an output buffer of the node;

(a2) determining whether the incoming packet is from the same active flow as the randomly-selected packet; and

(a3) updating an estimate of the number of active flows traversing the node based on the determination of step (a2); and

(b) determining whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein step (b) comprises:

(b1) calculating a drop probability p d using the equation

p

d

=

N

est

-

N

m

⁢

⁢

i

⁢

⁢

n

N

m

⁢

⁢

a

⁢

⁢

x

-

N

m

⁢

⁢

i

⁢

⁢

n

,

⁢

wherein:

N est represents the estimated number of active flows at the node; and

N min and N max represent lower and upper bounds, respectively, on the number of flows at the node; and

(b2) determining whether to admit or drop part or all of the new flow at the node based on the drop probability p d .

2. The method of claim 1 , wherein:

the new flow is admitted at the node only if a fractional buffer occupancy Q(t)/B exceeds a specified queue threshold q thresh ; B represents size of a buffer of the node; and Q(t) represents the number of packets in the buffer.

3. The method of claim 1 , wherein step (a2) comprises determining whether one or more fields of the incoming packet match one or more corresponding fields of the randomly-selected packet.

4. The method of claim 1 , wherein steps (a) and (b) are performed without using per-flow state information and without using a list of recently-seen flows.

5. The method of claim 1 , wherein:

the node provides two or more classes of service for network traffic;

steps (a1)-(a3) are performed for a plurality of packets of a specific class of service to estimate a number of flows of the specific class of service traversing the node; and

step (b) determines whether to admit or drop part or all of a new flow of the specific class of service using the estimated number of flows of the specific class of service traversing the node.

6. The method of claim 1 , wherein step (a3) comprises:

(a3i) updating a hit probability based on the determination of step (a2); and

(a3ii) updating the estimated number of active flows traversing the node based on the hit probability.

7. A method for controlling admission of new flows at a node in a network of nodes interconnected by links, the method comprising:

(a) for each of a plurality of incoming packets arriving at the node, each incoming packet corresponding to an active flow traversing the node:

(a1) randomly selecting a packet from an output buffer of the node;

(a2) determining whether the incoming packet is from the same active flow as the randomly-selected packet; and

(a3) updating an estimate of the number of active flows traversing the node based on the determination of step (a2); and (b) determining whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein: step (a3) comprises:

(a3i) updating a hit probability based on the determination of step (a2); and

(a3ii) updating the estimated number of active flows traversing the node based on the hit probability;

the hit probability p(t) is updated using the equation

p ( t )=(1−α) p ( t− 1)+α H ( t );

H(t) is set equal to 1 if the incoming packet belongs to the same flow as the randomly-selected packet, and 0 otherwise; and α is a weighting parameter.

8. A method for controlling admission of new flows at a node in a network of nodes interconnected by links, the method comprising:

(a) for each of a plurality of incoming packets arriving at the node, each incoming packet corresponding to an active flow traversing the node:

(a1) randomly selecting a packet from an output buffer of the node;

(a2) determining whether the incoming packet is from the same active flow as the randomly-selected packet; and

(a3) updating an estimate of the number of active flows traversing the node based on the determination of step (a2); and

(b) determining whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein:

step (a3) comprises:

(a3i) updating a hit probability based on the determination of step (a2); and

(a3ii) updating the estimated number of active flows traversing the node based on the hit probability;

the estimated number of active flows N est (t) is updated using the equation

N

est

⁡

(

t

)

=

(

1

-

α

)

⁢

N

est

⁡

(

t

-

1

)

+

α

⁢

⁢

B

p

⁡

(

t

)

⁢

Q

⁡

(

t

)

;

α is a weighting parameter; p(t) is the hit probability; B represents the buffer size of a buffer of the node; and Q(t) represents the number of packets in the buffer.

9. A method for controlling admission of new flows at a node in a network of nodes interconnected by links, the method comprising:

(a) for each of a plurality of incoming packets arriving at the node, each incoming packet corresponding to an active flow traversing the node:

(a1) randomly selecting a packet from an output buffer of the node;

(a2) determining whether the incoming packet is from the same active flow as the randomly-selected packet; and

(a3) updating an estimate of the number of active flows traversing the node based on the determination of step (a2); and

(b) determining whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein:

step (a3) comprises:

(a3i) updating a hit probability based on the determination of step (a2); and

(a3ii) updating the estimated number of active flows traversing the node based on the hit probability; and

step (a3i) comprises:

comparing a fractional buffer occupancy Q(t)/B to a specified queue threshold q thresh , wherein B represents the buffer size of a buffer of the node, and Q(t) represents the number of packets in the buffer; and updating the hit probability based on the comparison.

10. A system comprising:

a network of nodes interconnected by links, the network configured to:

(a) for each of a plurality of incoming packets arriving at a node of the network:

(a1) randomly select a packet from an output buffer of the node, each packet from an active flow traversing the node;

(a2) determine whether the incoming packet is from the same active flow as the randomly-selected packet; and

(a3) update an estimate of the number of active flows traversing the node based on the determination of step (a2); and

(b) determine whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein step (b) comprises:

(b1) calculating a drop probability p d using the equation

p

d

=

N

est

-

N

m

⁢

⁢

i

⁢

⁢

n

N

m

⁢

⁢

a

⁢

⁢

x

-

N

m

⁢

⁢

i

⁢

⁢

n

,

⁢

wherein:

N est represents the estimated number of active flows at the node; and

N min and N max represent lower and upper bounds, respectively, on the number of flows at the node; and

(b2) determining whether to admit or drop part or all of the new flow at the node based on the drop probability p d .

11. The system of claim 10 , wherein step (a) is implemented at the node, and step (b) is implemented at a network controller of the network.

12. An apparatus comprising:

a node for a network of nodes interconnected by links, wherein, for each of a plurality of incoming packets arriving at the node, each packet from an active flow traversing the node, wherein:

the node is configured to randomly select a packet from an output buffer of the node;

the node is configured to determine whether the incoming packet is from the same active flow as the randomly-selected packet; and

the node is configured to update an estimate of the number of active flows traversing the node based on the determination, wherein the node is enabled to determine whether to admit or drop part or all of a new flow at the node based on the estimated number of active flows traversing the node, wherein the step of updating comprises: the node calculating a drop probability p d using the equation

p

d

=

N

est

-

N

m

⁢

⁢

i

⁢

⁢

n

N

m

⁢

⁢

a

⁢

⁢

x

-

N

m

⁢

⁢

i

⁢

⁢

n

,

⁢

wherein:

N est represents the estimated number of active flows at the node; and

N min and N max represent lower and upper bounds, respectively, on the number of flows at the node; and the node determining whether to admit or drop part or all of the new flow at the node based on the drop probability p d .

13. The apparatus of claim 12 , wherein:

the new flow is admitted at the node only if a fractional buffer occupancy Q(t)/B exceeds a specified queue threshold q thresh ; B represents size of a buffer of the node; and Q(t) represents the number of packets in the buffer.

14. The apparatus of claim 12 , wherein the node determining whether the incoming packet is from the same active flow as the randomly-selected packet comprises the node determining whether one or more fields of the incoming packet match one or more corresponding fields of the randomly-selected packet.

15. The apparatus of claim 12 , wherein:

the node provides two or more classes of service for network traffic;

the steps of (i) randomly selecting a packet from an output buffer of the node, (ii) determining whether the incoming packet is from the same active flow as the randomly-selected packet, and (iii) updating an estimate of the number of active flows traversing the node based on the determination are performed for a plurality of packets of a specific class of service to estimate a number of flows of the specific class of service traversing the node; and wherein the node is enabled to determine whether to admit or drop part or all of a new flow at the node by determining whether to admit or drop part or all of a new flow of the specific class of service using the estimated number of flows of the specific class of service traversing the node.

16. The apparatus of claim 12 , wherein updating an estimate of the number of active flows traversing the node comprises: updating a hit probability based on the determination of whether the incoming packet is from the same active flow as the randomly-selected packet; and updating the estimated number of active flows traversing the node based on the hit probability.

Assignments (15)