Flexible scheme for admission control of multimedia streams on integrated networks

Claim 3

A method as recited in claim 1, wherein tile performance guarantee is predicted by determining whether the link can support the pseudo traffic without violating performance guarantees of the existing traffic on the link.

Claim 4

A method as recited in claim 1, wherein the performance guarantee is one of a delay guarantee and a loss guarantee.

Claim 5

An admission control method for admitting a connection request to a network, the network includes a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of the links, said method comprising the steps of: (a) inducing pseudo traffic into a plurality of the queues associated with the links, but not on the links themselves; (b) subsequently measuring performance parameters of the queues; and (c) determining whether to admit the connection request based on the measured performance parameters.

Claim 6

An admission control method for admitting a connection request to a network, the network includes a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of the links, said method comprising the steps of: (a) inducing pseudo traffic into a plurality of the queues associated with the links, but not on the links themselves; (b) subsequently measuring performance parameters of the queues; and (c) determining whether to admit the connection request based on the measured performance parameters.

Claim 7

A method as recited in claim 4, wherein tile connection request is a real-time connection request, and wherein the queues are real-time queues.

Claim 8

A method as recited in claim 5, wherein said method firther comprises the steps of: (d) determining, prior to step (c), the queues unable to handle the pseudo traffic and identifying the same as unavailable queues; and (e) removing the pseudo traffic from the unavailable queues.

Claim 9

A method as recited in claim 6, wherein said determining step (d) determines the queues unable to handle the pseudo traffic by determining the queues that can no longer continue to satisfy their performance guarantees to existing connections after the pseudo traffic is induced.

Claim 10

A method as recited in claim 6, wherein the connection request specifies at least an end-end performance bound, a traffic contract, and a destination network host, and wherein said determining step (c) comprises the steps of: (c1) distributing the measured performance parameters and information on the unavailable queues to a routing system; (c2) determining a proposed path for the connection request through the network from a source network host to the destination network host via only the queues that can handle the pseudo traffic; (c3) determine whether the sum of the performance parameter measurements through the queues in the proposed path is not greater than the end-end performance bound of the connection request; and (c4) deciding whether to admit the connecting request based on said determining step (c3).

Claim 11

A method as recited in claim 8, wherein the measured performance parameters are queue delays, and the end-end performance bound is an end-end delay bound.

Claim 12

A method as recited in claim 8, wherein the measured performance parameters are loss ratios, and tile end-end performance bound is an end-end loss bound.

Claim 13

A method as recited in claim 6, wherein the connection request specifies at least an end-end performance bound and a destination network host, wherein said method further comprises the step of (t) determining, prior to step (c), a maximum amount of pseudo traffic which each of the queues can take on while still satisfying their performance guarantees to existing connections, and wherein said determining step (c) comprises the steps of: (c1) distributing tile measured performance parameters and the maximum amounts of pseudo traffic to a routing system; (c2) determining a proposed path for the application request through the network from a source network host to the destination network host via only the links in which the queue associated therewith has sufficient bandwidth to support the connection request; and (c3) deciding whether to admit the connection request based on whether the sum of the performance parameter measurements through the links in the proposed path is less than or equal to the end-end performance bound of the application request.

Claim 14

A method as recited in claim 11, wherein the connection request further specifies a traffic contract defined by a token-bucket descriptor (r, b), and the maximum amount of pseudo traffic is defined by a token-bucket descriptor (R, B), and wherein step (c2) determines that the links have sufficient bandwidth to support the connection request when the token-bucket descriptor (r, b) of the connection request is less than or equal to the token-bucket descriptor (R, B) of the maximum amount of pseudo traffic.

Claim 15

A method as recited in claim 5, wherein said inducing step (a) induces a plurality of streams of the pseudo traffic into the queue associated with each of the links, wherein said method further comprises the step of (d) predicting a number of connection requests which each of the links can simultaneously admit to said network without violating performance commitments by said network to existing connections, and wherein said determining step (c) includes determining whether to admit simultaneous connection requests based on the numbers predicted in step (d).

Claim 16

A network node for an integrated network, comprising: a connection circuit for passing traffic by operatively connecting an incoming link to an outgoing link; a pseudo traffic controller for supplying pseudo traffic; a first queue, operatively connected to said connection circuit and said pseudo traffic controller, for queuing the pseudo traffic and real-time traffic; and a performance parameter prediction unit, operatively connected to said first queue, for predicting a performance parameter of said first queue, wherein said connection circuit transmits the real-time traffic output from said first queue and discards the pseudo traffic output from said first queue.

Claim 17

A network node for an integrated network, comprising: a connection circuit for passing traffic by operatively connecting an incoming link to an outgoing link; a pseudo traffic controller for supplying pseudo traffic; a first queue, operatively connected to said connection circuit and said pseudo traffic controller, for queuing the pseudo traffic and real-time traffic; and a performance parameter prediction unit, operatively connected to said first queue, for predicting a performance parameter of said first queue, wherein said connection circuit transmits the real-time traffic output from said first queue and discards the pseudo traffic output from said first queue.

Claim 18

A network node as recited in claim 14, wherein said network node further comprises admission means for determining whether to admit a connection request to the network based on the predicted performance parameter.

Claim 19

A network node as recited in claim 14, wherein said network node further comprises means for distributing the performance parameter predicted to a routing system.

Claim 20

A network node as recited in claim 14, wherein said node further comprises a second queue for queuing best-effort traffic, and wherein said connection circuit transmits the real-time traffic and the best-effort traffic.

Claim 21

A network node as recited in claim 17, wherein said connection circuit transmits the best-effort traffic in place of the pseudo traffic.

Claim 22

A network node as recited in claim 17, wherein tile traffic comprises packets of data, and wherein said node further comprises: a comparator for comparing a header of each packet of the traffic exiting said first queue with a predetermined pseudo traffic identifier; and a selector for selecting a packet exiting said first queue for transmission by said connection circuit when said comparator indicates that the packet exiting said first queue is from the real-time traffic and for selecting a packet of the best-effort traffic from said second queue for transmission by said connection circuit when said comparator indicates that the packet exiting said first queue is from the pseudo traffic.

Claim 23

A network node as recited in claim 14, wherein said node comprises a plurality of said first queues for each of the links, each of said first queues corresponding to a different traffic class.

Claim 24

An admission control system for controlling admission of an additional connection to an integrated network, a connection request for the admission of the additional connection to the integrated network includes an end-to-end performance bound requirement, the integrated network having a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of its outgoing links, said system comprising: link-level admission control means for monitoring available network resources, said link-level admission control means including at least means for inducing pseudo traffic into the queue of each of the outgoing links, but not on the links themselves, means for measuring a performance parameter of the queue for each of the outgoing links, and means for determining whether each of the outgoing links can handle the additional connection based on the measured performance parameters; and network-level admission control means for deciding whether to accept or reject the additional connection, said network-level admission control means including at least means for determining a potential path for the connection request in accordance with the measured performance parameters and the end-to-end performance bound requirement of the connection request, means for determining a sum of the measured performance parameters for each of the outgoing link in the potential path, and means for accepting the additional connection along the potential path when the sum of the measured performance parameters is not more than the end-to-end performance bound requirement of the connection request.

Claim 25

An admission control system for controlling admission of an additional connection to an integrated network, a connection request for the admission of the additional connection to the integrated network includes an end-to-end performance bound requirement, the integrated network having a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of its outgoing links, said system comprising: link-level admission control means for monitoring available network resources, said link-level admission control means including at least means for inducing pseudo traffic into the queue of each of the outgoing links, but not on the links themselves, means for measuring a performance parameter of the queue for each of the outgoing links, and means for determining whether each of the outgoing links can handle the additional connection based on the measured performance parameters; and network-level admission control means for deciding whether to accept or reject the additional connection, said network-level admission control means including at least means for determining a potential path for the connection request in accordance with the measured performance parameters and the end-to-end performance bound requirement of the connection request, means for determining a sum of the measured performance parameters for each of the outgoing link in the potential path, and means for accepting the additional connection along the potential path when the sum of the measured performance parameters is not more than the end-to-end performance bound requirement of the connection request.

Claim 26

An integrated network, comprising: a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of the links for temporarily storing real-time traffic for the respective link; means for inducing pseudo traffic into the queues associated with each of the links, but not on the links themselves; and congestion detection means for measuring performance of the queues to proactively predict congestion of the links.

Claim 27

An integrated network, comprising: a plurality of nodes interconnected by links, each of the nodes having at least one queue associated with each of the links for temporarily storing real-time traffic for the respective link; means for inducing pseudo traffic into the queues associated with each of the links, but not on the links themselves; and congestion detection means for measuring performance of the queues to proactively predict congestion of the links.

Claim 28

An integrated network as recited in claim 22, wherein said network provides performance commitments to connections admitted to said network, and wherein said congestion detection means measures a performance parameter for each of the queues after the pseudo traffic has been induced and then predicts whether said network can continue to satisfy the performance commitments provided to connections already admitted to said network if a connection request is admitted to said network.

Claim 29

A method as recited in claim 4, wherein said inducing and said measuring occur before a connection request is received, and said determining occurs after the connection request is received.