Flow admission control for a router

Claim 3

The method of claim 1 wherein the step of attempting to fit the envelope A(t) within F(t) comprises performing a stability test using A(t) and F(t).

Claim 4

The method of claim 1 wherein the network component is a component which receives and forwards packets.

Claim 7

The method of claim 4 wherein the network component is selected from the group consisting of a switch, a router, a bridge, and a gateway.

Claim 8

The method of claim 4 wherein the step of fitting comprises finding a minimum t d for which A(t-t d )≦F(t) for all t.

Claim 9

The method of claim 6 wherein A(t) is an n-rate function, wherein n is a positive integer.

Claim 10

The method of claim 7 wherein n is equal to one.

Claim 11

The method of claim 7 wherein n is equal to two.

Claim 12

The method of claim 4 wherein ##EQU46## , wherein c is a rate characterizing the total capacity of the network component, t is time, N is an integer, A* i (t) is a function characterizing a flow i which the network component has accepted, and t i is a maximum delay that the network component has guaranteed for the flow i.

Claim 13

The method of claim 4 further comprising defining a plurality of discrete time values, and wherein the step of fitting the envelope A(t-t d ) comprises constraining a certain characteristic of A(t-t d ) to fall on one of the discrete time values.

Claim 14

The method of claim 11 wherein said certain characteristic of A(t-t d ) is a flex point.

Claim 15

The method of claim 11 wherein the step of defining a plurality of discrete time values comprises defining the time values at equal intervals.

Claim 16

The method of claim 11 wherein the step of defining a plurality of discrete time values comprises defining the time values at unequal intervals.

Claim 17

The method of claim 3 further comprising defining a plurality of discrete time values; and defining an envelope A°(t) based on the received information characterizing the proposed flow of packets, such that A°(t)≧A(t) for all t and a certain characteristic of A°(t-t d ) falls on one of the discrete time values; and wherein ##EQU47## wherein c is a rate characterizing the total capacity of the network component, t is time, N is an integer, A° i (t) is a function characterizing a flow i which the network component has accepted, and t i is a maximum delay that the network component has guaranteed for the flow i.

Claim 18

The method of claim 15 wherein said certain characteristic of A°(t-t d ) is a flex point.

Claim 19

The method of claim 15 wherein the step of defining a plurality of discrete time values comprises defining the time values at equal intervals.

Claim 20

The method of claim 15 wherein the step of defining a plurality of discrete time values comprises defining the time values at unequal intervals.

Claim 21

The method of claim 4 wherein the network component uses an Early Deadline First scheduling policy to schedule the packets.

Claim 22

The method of claim 19, wherein the Early Deadline First scheduling policy is one of preemptive and non-preemptive Early Deadline First scheduling policies.

Claim 23

The method of claim 4 wherein the network component is a component which receives and forwards packets.

Claim 24

A network component which receives and forwards packets, the network component comprising: a queue which temporarily stores received packets prior to forwarding them; a central processing unit; a computer readable medium; and a program stored in the computer readable medium, wherein said program when executed by the central processing unit causes the central processing unit to: provide a function F(t) which characterizes resources available at the network component; define an envelope A(t) based on received information characterizing a proposed flow of packets; fit an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and based on t d , guarantee a maximum delay that any packet from the proposed flow will experience in the queue.

Claim 25

A network component which receives and forwards packets, the network component comprising: a queue which temporarily stores received packets prior to forwarding them; a central processing unit; a computer readable medium; and a program stored in the computer readable medium, wherein said program when executed by the central processing unit causes the central processing unit to: provide a function F(t) which characterizes resources available at the network component; define an envelope A(t) based on received information characterizing a proposed flow of packets; fit an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and based on t d , guarantee a maximum delay that any packet from the proposed flow will experience in the queue.

Claim 26

A network component which receives and forwards packets, the network component comprising: a queue in which received packets are stored prior to for warding them; means for providing a function F(t) which characterizes resources available at the network component; means for receiving information characterizing a proposed flow of packets; means for defining an envelope A(t) based on the received information characterizing the proposed flow of packets; means for fitting an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and means for guaranteeing, based on t d , a maximum delay that any packet from the proposed flow will experience in the queue.

Claim 27

A network component which receives and forwards packets, the network component comprising: a queue in which received packets are stored prior to for warding them; means for providing a function F(t) which characterizes resources available at the network component; means for receiving information characterizing a proposed flow of packets; means for defining an envelope A(t) based on the received information characterizing the proposed flow of packets; means for fitting an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and means for guaranteeing, based on t d , a maximum delay that any packet from the proposed flow will experience in the queue.

Claim 28

A program stored on a computer readable medium, wherein said program when executed by a central processing unit causes the central processing unit to: provide a function F(t) which characterizes resources available at a network component; define an envelope A(t) based on received information characterizing a proposed flow of packets; fit an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and based on t d , guarantee a maximum delay that any packet from the proposed flow will experience in the network component.

Claim 29

A program stored on a computer readable medium, wherein said program when executed by a central processing unit causes the central processing unit to: provide a function F(t) which characterizes resources available at a network component; define an envelope A(t) based on received information characterizing a proposed flow of packets; fit an envelope A(t-t d ) within F(t) so that A(t-t d )≦F(t) for all t>0, wherein t d represents a delay for the proposed flow; and based on t d , guarantee a maximum delay that any packet from the proposed flow will experience in the network component.