Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-02-23
2001-07-31
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S390000, C370S395430
Reexamination Certificate
active
06269079
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communications networks and more particularly to communications networks using Asynchronous Transfer Mode (ATM).
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) networks have become increasingly popular for both wide area networks and local area networks. In an ATM network all information is transported through the network in relatively short blocks called cells. Information flow through the network is along paths called virtual channels which are set up as a series of pointers through the network. Cells on a particular virtual channel always follow the same path through the network and are delivered to the destination in the order in which they are received.
When communications are initiated in an ATM network a request is made for a connection. As part of the connection request, the quality of service (QoS) of the request is specified by the requester. Quality of service characteristics which may be specified in ATM include cell transfer delay (network latency), cell delay variation (jitter), cell transfer capacity (average and peak allowed rates), cell error ratio, cell loss ratio and cell misinsertion ratio. These QoS parameters are used by the ATM nodes to determine the route of the connection and in determining allowable node utilization.
Routing in an ATM network is performed by an ATM node which attempts to predict the route for a virtual connection from a source to a destination. An ATM connection is not set up unless and until the network determines that there is sufficient capacity for the new connection. This determination is based upon the characteristics of the network, the existing traffic on the network and the requested QoS for the connection. If the requested QoS cannot be provided then the requested connection is not accepted. The function in ATM which determines whether a connection request is accepted is referred to as call admission control (CAC). In ATM, the CAC function is typically carried out at two places; the entry point into the ATM network and at each node in the connection path.
At the entry point into the ATM network a process called Generic Call Admission Control (GCAC) determines a probable route for the connection request based on the QoS requested, and either accepts or rejects the request based on this determination. To perform the GCAC function, the entry point should have available information about the utilization of the other nodes in the ATM network. This information may then be utilized to determine if the nodes along the selected route can satisfy the QoS requirements of the requested connection.
At each node in a connection route, a local call admission control function, called an Actual Call Admission Control (ACAC), determines if the node will accept the connection request. This ACAC function utilizes the requested QoS and information about the existing connections through the node to determine if the requested QoS level may be achieved. If so, the connection request is accepted.
To have sufficient information to perform the GCAC function at each possible entry point, each node in the network broadcasts information about each connection at the node. This information typically includes information sufficient to determine the traffic envelope for a connection (i.e. the maximum amount of traffic a connection is allowed to send in time). Information sufficient to calculate the traffic envelope for a connection includes the peak data rate for the connection, the maximum burst size, the maximum sustained data rate and the guaranteed delay. From this information, the node may perform a “schedulability” to determine if the nodes in the proposed route will probably accept the requested connection.
While the GCAC function may provide increased performance in routing, one drawback is the increase in overhead associated with broadcasting connection information over the ATM network to each node for each connection. As the number of connections at a node increase the amount of overhead for broadcasting connection information increases. With a large number of connections, significant amounts of bandwidth of a network may be consumed with connection data transmissions from node to node.
In an effort to ensure that accepted connections provide the requested quality of service criteria for a connection, ATM nodes may utilize an Earliest Deadline First (EDF) scheduler to select the order in which cells are transmitted over a physical link of the network. The EDF scheduler prioritizes cells on a physical link based upon the time until the maximum delay time through the node of the cell expires. By transmitting the cells with the least time left until the maximum delay time expires, the likelihood of making the maximum delay criteria is increased. However, such scheduling may require significant processing. For example, all cells in the system may be queued but then all cells must be searched for the shortest deadline. Alternatively, maintenance of a single sorted queue of all the cells in the system would require log N operations to insert a cell in the queue, where N is the number of cells in the queue.
Whatever system of scheduling cells to meet the maximum delay requirements is utilized, congestion conditions may still result in the ATM network. In an ATM network, congestion control is provided by discarding cells until the congestion problem is relieved. To facilitate minimizing the disruption caused by such discarding of cells, a cell may be marked as a low priority cell. Low priority cells would be the first cells to be discarded to relieve a congestion problem.
FIG. 1
illustrates the configuration of a cell in ATM. As seen in
FIG. 1
, the cell loss priority bit (CLP) may be set to indicate that the cell may be discarded. This ability to prioritize cells to be discarded may further complicate an EDF scheduler as the scheduler should also take into account whether a cell with a short deadline is a low priority cell and whether higher priority cells are waiting to be transmitted.
In light of the above discussion, a need exists for improvements in the mechanisms for accepting connections and for scheduling transmission of cells for accepted connections in ATM networks.
SUMMARY OF THE INVENTION
In view of the above discussion, it is an object of the present invention to provide for decreased overhead in the determination of a CAC function in an ATM network.
Yet another object of the present invention is to reduce the number of broadcasts of data between ATM cells.
Still another object of the present invention is to disassociate the overhead of performing the CAC function from the number of connections through a node in the ATM network.
A further object of the present invention is to provide efficient utilization of ATM resources in scheduling cells for transmission.
Still another object of the present invention is to reduce the number of operations required to schedule cells in an earliest deadline first manner.
Another object of the present invention is to schedule cells for transmission such that congestion conditions do not disrupt the transmission of cells.
These and other objects of the present invention are provided by methods, systems and computer program products for distributing connection information between ATM nodes in a network by aggregating connection information for connections to an ATM node to provide a set of aggregate connection information for the ATM node. This set of aggregate connection information may then be distributed to other ATM nodes in the network. Preferably, the connection information includes peak data rate, maximum burst size and maximum sustainable data rate. An ATM node may determine whether to accept a requested connection based upon the aggregate connection information of the ATM node and the connection information of the requested connection.
The aggregation and distribution of connection information may be achieved by aggregating connection information for connections in each connection class of the ATM node so as to provide a
Marin Gerald A.
Onvural Raif O.
Roginsky Allen Leonid
Srinivasan Vijay
Elallam Ahmed
International Business Machines - Corporation
Kizou Hassan
Myers Bigel & Sibley & Sajovec
Woods, Esq. Gerald R.
LandOfFree
Systems, methods and computer program products for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems, methods and computer program products for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems, methods and computer program products for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450027