Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1996-12-04
2001-01-16
Vu, Huy D. (Department: 2735)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S230000, C370S235000, C370S463000, C370S420000
Reexamination Certificate
active
06175570
ABSTRACT:
FIELD OF THE INVENTION
This invention deals with problems of traffic control in the fixed length cells switching high speed networks and more particularly with a shaping method and apparatus to be implemented in an ATM network node.
BACKGROUND OF THE INVENTION
The basic advantage of the new high bandwidth, low delay, fixed length cell based transfer mode techniques, such as Asynchronous Transfer Mode (ATM), is to allow multiplexing and switching of different types of information over the same network: data, voice, image, video, while optimizing the bandwidth and resources utilization.
To that end, the various network user's traffic are split into fixed and/or variable length data packets (or blocks) which are then split into fixed length cells in an ATM type network. The basic problem is to conveniently orient these cells within the network bearing in mind that thousands of users connected to the same network shall share the same network link. In a high speed transmission environment, and with users operating essentially in burst mode and at different speed from one another, one may easily understand that conflicts and congestions can occur within the network.
Congestion control inside these networks is one of the major problems to be resolved. As the cells are short, no space is allocated in their headers to enable error recovery for the cell payload (i.e. users data). If one cell of the block has been lost or discarded by the network in case of network congestion, error recovery is performed at the higher-level by recovery protocols retransmitting the user data block. The error rate being extremely low in the internode links, cells lost because of random errors is not a potential problem. However, when a node discards cells for reason of traffic congestion, it is unlikely that these cells will come from a small number of logical data blocks. Discarding 1000 cells, if the average user data blocks length is 2KBytes (a low estimate), sent as 43 cells, may cause the network to absorb a retransmission of 43,000 cells! This case indeed is the worse case when the 1000 messages come from 1000 different connections. That is why the protocols need to be efficient enough to minimize congestion problems in this type of networks.
In the ATM connection-oriented networks, the end-to-end traffic of data for one user, between the source and the destination, is represented by a Virtual Connection (VC); several Virtual Connections may be grouped in a Virtual Path (VP) that can be switched as a unit. The bandwidth is allocated dynamically, based on predefined conditions and agreements with each user, as part of a connection setup signalling procedure that precedes end-to-end information exchange. At call admission time, the source user provides, in addition to the destination point, a set of parameters, called the traffic descriptors, which attempt to describe the traffic that will be generated onto the links. For instance, a mandatory descriptor is the peak cell rate of the connection, R. If this parameter is sufficient to fully describe Constant Bit Rate (CBR) connections, i.e., periodic stream of cells such as uncompressed voice, further parameters are necessary to describe Variable Bit Rate (VBR) connections such as those for video traffic. The burst of traffic is measured by the average cell rate and the average duration of an emission at the peak rate R in most of the high speed networks literature. As indicated above, in ATM networks, cells may be lost or unacceptable delays can be induced in case of traffic congestion. Depending on the type of traffic conveyed over the ATM network, the first or the second just mentioned behavior of the network, in case of congestion, may damage the quality of traffic over the virtual connections: for voice traffic, cells can be lost but a delay in transmission is unacceptable. When pure data is transferred on the virtual connection, the delay can be acceptable but not the cell loss. That's why the network guarantees a Quality of Service (QoS). The QoS guaranteed by a network is, in most cases, expressed in terms of cell loss probability and maximum end-to-end delay for a cell, independently of network topologies and protocols. One can note that the end-to-end delay between two users is increased if the end-to-end connection crosses different network entities (private or public carrier networks) which have their own protocols and traffic management.
In order to meet the QoS, the network nodes have to control the traffic congestion both at connection admission time and once the connection is established.
At connection admission time the access node has to decide if it can accept the connection or not: its decision is based on the actual load of the links, and its analyzis of the traffic parameters of the connection. Moreover, it has also to compute a path table to carry this overload of traffic through the different nodes. If no path is found, the call is rejected. It is important to note that the decision to accept a new call has to be taken not only if the network node estimates that the QoS for the connection will be met but also if it is sure that the added traffic will not have a significant impact on the QoS of all the connections already established.
A first control on traffic congestion, once the connection is established, is performed by the policing function implemented in a device, the policer, of the network access node adapter. The policer will detect and penalize the violation of the peak cell rate on the current traffic compared to the one required at call set up.
Instead of the peak cell rate, another descriptor the Sustainable Cell Rate, (SCR) can be used as a criterion for the policing function. Accordingly, any reference to the peak cell rate can be replaced by SCR. The policing function is also referred to, in the ATM literature, as the Network Parameter Control (NPC) or the Usage Parameter Control (UPC) depending on whether the source unit is a Network Node or a Customer Premise Node (or port). Indeed, an efficient policing function should be transparent as long as the traffic characteristics provided by the source at call setup are met. This means that the policing algorithm should discard or tag as discardeable, user cells unless the cell loss probability is less than or equal to the one defined by the QoS. On the other hand, the policing function will also discard or tag the cells that are in excess versus the peak cell rate provided at call set up.
A second control of traffic congestion consists in shaping the output network node traffic by spacing the cells departures in such a way that the time between two departures of cells for the same connection shall never be below the minimal value negotiated at connection setup time. It has been shown that, on the average, the multiplexing of spaced cells tends to decrease the ‘burstiness’ of the aggregate traffic and then allows a better utilization of the network resources. This invention shall essentially focus on this second aspect of traffic congestion, and accordingly shall be implemented within (or combined with) the shaping device (shaper).
FIG. 1
shows the shaping principle applied to the input cells stream
1
. The shaded cells have been sent by a first user and the cells marked with a cross have been sent by a second user. The result of shaping is shown with the output cells stream
2
: the cells marked with = have been moved and the departure time between two cells has become more regular. The spacing of the cells is done according to the bandwidth sharing required by the users: in the output cell stream, the departure time between two cells is smaller for the cells of the first user than for the second user's cells, because the first user has required a greater bandwidth share than the second user. Moreover, in the output stream the bursts of traffic have decreased: one can note that the groups of two cells belonging to the same connection of the input stream
1
have disappeared in the output stream
2
.
The policing function is implemented in th
Cukier Maurice
Gallezot Rene
Jaumes Jocelyne
Roman Thierry
Wind Daniel
Cesari and McKenna
Cisco Technology Inc.
Harper Kevin C.
Vu Huy D.
LandOfFree
Method and an apparatus for shaping the output traffic in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and an apparatus for shaping the output traffic in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and an apparatus for shaping the output traffic in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484636