Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-03-16
2001-03-06
Vu, Huy D. (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S351000, C370S395430, C370S418000
Reexamination Certificate
active
06198725
ABSTRACT:
CROSS REFERENCE TO RELATED APPLCIATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The disclosed invention relates generally to resource allocation in network elements of a communications network, and more specifically to a system for allocating resources to virtual connections in a network switch.
Communications networks interconnect end stations through paths including multiple devices or systems referred to as network elements. Network elements may include devices known as switches, bridges and routers. It is sometimes necessary to ensure a maximum end to end delay and a maximum end to end delay variation for data units transferred along a path between two end stations. For example, when a user at a first end station (end station A) requests that a virtual connection be established with a second end station (end station B), the request may include certain Quality of Service (QoS) parameters specifying performance levels that must be met by any resulting connection. In an Asynchronous Transfer Mode (ATM) environment, such QoS parameters include “Maximum Cell Transfer Delay” (Max CTD), and “Maximum Cell Delay Variation” (Max CDV). The Max CTD parameter defines an upper limit for total delay permitted for cells transmitted over the requested connection. The Max CDV parameter defines the maximum permitted variation between cell transfer delays over the requested connection.
In the above example, end station A will attempt to establish a path to end station B on which sufficient resources are available in each network element along the path to support the QoS parameters associated with a given request. If such resources are available, then each network element along the path reserves resources for the connection, and the connection is established.
The various kinds of delay that may be experienced by a data unit may be thought of as falling into three categories: 1) link propagation delay (LPD), 2) switching delay (SD), and 3) queuing delay (QD). The end to end LPD for a given path is the sum of the delays encountered by a data unit on the links for a given path. The end to end LPD does not include the time a data unit may be delayed within a network element. Switching delay is the time required to pass a data unit between an input port and an output port within a switch, assuming no queuing delays due to traffic congestion. Accordingly, switching delay is a function of the inherent speed of a particular switch. Queuing delay is the delay resulting from a data unit being stored in an input or output queue within a network element, and is dependant on the congestion being experienced by that network element at a specific point in time. Thus, actual delay and delay variation reflect both resource capacity and utilization at each network element that is traversed by a data unit within a given path through a network.
In existing systems, when a network element receives a request to establish a connection, the network element will reserve resources to be used to support the connection if the connection request is granted. However, existing systems test potential paths using a mechanism which passes only the maximum permitted delay, maximum permitted delay variation, and accumulated delay to each of the network elements in the path as the path is being tested. While these parameters are sufficient to determine whether a path should be eliminated from consideration due to insufficient resources, such systems fail to provide adequate information for each network element in the path to reserve resources accurately in order to meet the specific needs of a given connection. As a result, resources may be under or over allocated to a connection because the network elements cannot accurately determine the amount of resources that should be allocated.
For the reasons stated above, it would be desirable to have a system for allocating resources to a virtual connection along a path through a communications network which more accurately provides information to network elements along the path, such that resources are not over or under allocated. The system should permit network elements along the path to satisfy a connection request by accurately allocating resources in response to characteristics of the path being tested. The system should further be convenient to implement and compatible with existing systems.
SUMMARY OF THE INVENTION
In accordance with the present invention, a system for allocating resources at network elements along a path through a communications network is disclosed which addresses the aforementioned shortcomings of previous systems. The disclosed system is applicable to various types of network elements including switches, routers, bridges, and other devices. In the disclosed system, resources are allocated at a network element along a path between a first end station and a second end station in response to a message that is received by that network element. The message includes information elements indicating target end to end cell delay, accumulated cell delay variation, and accumulated cell transfer delay, as well as the Max CDV and Max CTD QoS parameters from a connection request associated with the received message. The network element determines a delay budget by determining a minimum of a calculated cell transfer delay and a calculated cell delay variation. The calculated cell transfer delay value is determined by finding a difference between the target end to end cell delay and an accumulated cell delay, and then dividing that difference by a number of network elements remaining in the path between the network element and the end of the path. To determine the calculated cell delay variation, the network element first finds a difference between the Max CDV QoS parameter and the sum of the accumulated cell delay variation and the switching delay for the network element. The calculated cell delay variation is then equal to that difference divided by the number of network elements remaining in the path between the network element and the end of the path.
The target end to end cell delay is for example determined by the first network element in the path. The target end to end cell delay may be determined as equal to the Max CTD QoS parameter minus the end to end link propagation delay for the path and the link propagation delay for the incoming link to the first network element over which the message was received. The first network element then generates and forwards a modified connection request message including the determined target end to end cell delay value.
The number of network elements remaining in the path may be determined in response to the contents of the connection request message. In one embodiment the message includes a list of network elements remaining in the path. Alternatively, the network element receiving the message could determine the number of network elements remaining in the path based on topology information within that network element.
Following calculation of the delay budget, the network element allocates resources for the associated virtual connection sufficient to process received cells on that connection without exceeding the delay budget. Such resources potentially include buffers to store cells associated with that connection, as well as switch fabric bandwidth to forward such cells from an incoming port to an outgoing port.
REFERENCES:
patent: 5483523 (1996-01-01), Nederlof
patent: 5689499 (1997-11-01), Hullett et al.
patent: 5796719 (1998-08-01), Peris et al.
patent: 5933414 (1999-08-01), Georgiadis et al.
patent: 5933425 (1999-08-01), Iwata
patent: 5953337 (1999-09-01), Almay
Affidavit of Thomas A. Manning executed on Aug. 16, 1999 with Exhibits A-H.
Affidavit of Mark Bernasconi executed on Dec. 13, 1999 with Exhibits A-E.
Affidavit of Jerome Neff executed on Dec. 16, 1999 with Exhibit A.
Abu-Ayyash Salma
Constantin Robert
Hammond David E.
Manning Thomas A.
Peck David N.
Fujitsu Network Communications, Inc.
Phan M.
Vu Huy D.
Weingarten, Schurgin Gagnebin & Hayes LLP
LandOfFree
Network element delay allocation for efficient use of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network element delay allocation for efficient use of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network element delay allocation for efficient use of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2533507