Method and system for managing admission to a network

• US 20030058792A1
• Filed: 09/21/2001
• Published: 03/27/2003
• Est. Priority Date: 09/21/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Ya-Qin, Shao, Huai-Rong, Qiu, Jian-Ming, Zhu, Wenwu
• Granted Patent: US 7,177,271 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/826 Involving periods of time

Abstract

A method and system for managing admission to a network considers the packet delay of the network in making an admission decision. The packet delay of the network is periodically probed. To avoid disturbing or impairing the traffic of the network, a sequence of probing packets is sent to the network at an irregular interval. Responses to the probing packets are analyzed to obtain delay information of the network. If the delay information is insufficient to make an admission decision, then the packet loss rate of the network is measured and considered.

Claims

1. A method for managing the admission of data to a network, the method comprising:

receiving a request for a flow of data to be admitted to the network;

determining the amount of delay being experienced by the network;

determining the rate at which data is being lost in the network; and

deciding whether or not to grant the request based on the determined amount of delay and on the determined data loss rate.

2. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. The method of claim 1, further comprising:

transmitting packets to a remote node over the network; and

receiving from the remote node responses to the transmitted packets,

wherein the step of determining the amount of delay being experienced by the network comprises determining, based on at least some of the responses, the amount of delay being experienced by the network,

and wherein the step of determining the rate at which data is being lost by the network comprises determining, based on at least some of the responses, the rate at which data is being lost by the network.

4. The method of claim 1, further comprising estimating the amount of additional delay that the network will experience if the flow of data is admitted to the network, wherein the step of determining whether or not to grant or deny the request is further based on the estimated amount of additional delay.

5. The method of claim 1, further comprising:

if the delay being experienced by the network exceeds a maximum acceptable delay and the rate at which data is being lost in the network exceeds a maximum acceptable rate, denying the request.

6. The method of claim 1, further comprising:

comparing the delay being experienced by the network with an upper limit and with a lower limit;

if the delay being experienced by the network is above the upper limit, denying the request;

if the delay being experienced by the network is below the lower limit, granting the request; and

if the delay being experienced by the network is between the upper and lower limit, performing the steps of;

determining whether the loss rate of data by the network is above an acceptable limit; and

if the loss rate is above the acceptable limit, deny the request;

if the loss rate is below the acceptable limit, granting the request.

7. A method for managing the admission of data to a network, the method comprising:

transmitting a plurality of groups of probing packets to a remote node in the network;

receiving responses to at least some of the probing packets in at least some of the plurality of groups, the responses being echoed versions of the probing packets;

calculating an average queuing delay for each group of packets, the average queuing delay representing the average amount of time that the packets in the group and the echoed versions thereof had to spend queued at intermediate nodes in the network on their way to and on their way back from the remote node;

determining a minimum queuing delay time for each group of transmitted packets, the minimum queuing delay time representing the minimum amount of time that any of the packets in the group and the echoed versions thereof had to spend queued at intermediate nodes in the network on their way to and on their way back from the remote node;

calculating a plurality of delay shapes, including a delay shape for each group of probing packets sent over the time interval, the delay shape representing the difference between the average delay time and the minimum delay time for the group;

creating a first cumulative probability plot from the calculated delay shapes, the first cumulative probability plot representing the cumulative probability of achieving various delay shape values when the network is relatively loaded;

creating a second cumulative probability plot from the calculated delay shapes, the second cumulative probability plot representing the cumulative probability of achieving various delay shape values when the network is relatively unloaded;

juxtaposing the first and second plots so that the first and second plots intersect at an intersection, the intersection corresponding to a delay shape value; and

determining whether or not to admit a data flow to the network based on the delay shape value corresponding to the intersection.

8. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 7.

9. The method of claim 7, wherein the step of creating a first cumulative probability plot further comprises:

creating the first cumulative probability plot from delay shapes that are calculated based on probing packet groups transmitted when the network has a packet loss rate below one percent; and

creating the second cumulative probability plot from delay shapes that are calculated based on probing packet groups transmitted when the network has a packet loss rate above one percent.

10. The method of claim 7, wherein each point of the first cumulative probability distribution plot is associated with a delay shape on a first axis and with a probability on a second axis, the probability being equal to a cumulative total of one minus the probability of the occurrence of each of the preceding delay shapes on the first axis.

11. The method of claim 7, wherein each point of the second probability distribution plot is associated with a delay shape on a first axis and with a probability on a second axis, the probability being equal to a cumulative total of probability of the occurrence of each of the preceding delay shapes on the first axis.

12. The method of claim 7, wherein the transmitting step is performed on a periodic basis, and wherein the step of determining whether or not to admit a data flow to the network is performed in response to a request to have a data flow be admitted to the network.

13. The method of claim 7, wherein the delay shape value to which the intersection corresponds is a delay shape threshold value, the method further comprising:

computing a delay shape-high value, the delay shape-high value representing an acceptable upper limit for the delay shape;

comparing the delay shape calculated from the most recently transmitted group of probing packets with the delay shape-high value; and

if the delay shape calculated from the most recently transmitted group of probing packets is higher than the delay shape-high value, denying admission of the flow of data to the network.

14. The method of claim 13, wherein the delay shape-high value is equal to a product of the delay shape threshold and a numerical value, the numerical value representing an acceptable balance between efficient resource utilization and the quality of service required by the a program that is requesting that the data be admitted to the network.

15. The method of claim 7, wherein the delay shape value to which the intersection corresponds is a delay shape threshold value, the method further comprising:

comparing the delay shape calculated from the most recently transmitted group of probing packets with the delay shape threshold value; and

if the delay shape calculated from the most recently transmitted group of probing packets is higher than the delay shape threshold value, denying admission of the flow of data to the network.

16. The method of claim 7, wherein the delay shape value to which the intersection corresponds is a delay shape threshold value, the method further comprising:

computing a delay shape-low value, the delay shape-low value representing ceiling for delay shape values that a automatically acceptable;

comparing the delay shape calculated from the most recently transmitted group of probing packets with the delay shape-low value; and

if the delay shape calculated from the most recently transmitted group of probing packets is lower than the delay shape-low value, admitting the flow of data to the network.

17. The method of claim 16, wherein the delay shape-low value is equal to a product of the delay shape threshold and a numerical value, the numerical value representing an acceptable trade-off between making a quick decision regarding admission of data to the network and making a correct decision.

18. The method of claim 7, wherein the delay shape value to which the intersection corresponds is a delay shape threshold value, the method further comprising:

computing a delay shape-low value, the delay shape-low value representing ceiling for delay shape values that a automatically acceptable and being equal to about 0.8 times the delay shape threshold value;

comparing the delay shape calculated from the most recently transmitted group of probing packets with the delay shape-low value; and

if the delay shape calculated from the most recently transmitted group of probing packets is lower than the delay shape-low value, admitting the flow of data to the network.

19. A system for managing the admission of data to a network, the system comprising:

a computer executing modules comprising;

a delay analysis module that compiles statistical data regarding how long packets are taking to travel on the network;

a loss rate analysis module that compiles statistical data regarding the rate of loss of packets that are sent out to the network; and

an admission control module that receives requests for the admission of data flows to the network, and decides whether to admit or reject the requests based on the statistical data compiled by the delay analysis module and the loss rate analysis module,

wherein the admission control module;

rejects the requests if the current packet delay of the network is higher than an upper limit;

grants the requests if the current packet delay of the network is less than the expected delay rate of the network; and

if the current packet delay is between the upper limit and the expected value, relies on the packet loss rate of the network to determine whether or not to grant the requests.

20. The system of claim 19, wherein the computer further executes a probing and testing module for sending and receiving packets to and from the network to obtain packet delay measurements for the network and the packet loss rate measurements for the network.