Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-05-20
2001-09-18
Yao, Kwang B. (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S429000
Reexamination Certificate
active
06292492
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication networks, and more specifically to a method and apparatus for allocating memory space shared by several connections in an asynchronous transfer mode (ATM) switch.
2. Related Art
Switches are commonly used in communication networks for providing connectivity between end-systems. A switch generally receives a packet of data on a port from another switch or an end-system and forwards the packet on another port to another switch or an end-system. The packet may thus be forwarded by a sequence of switches located between a source end-system and a destination end-system until the packet is received at the destination end-system. The packets forwarded can provide the basic frame-work for implementing different applications (such as data sharing, voice, video) on the end-systems connected to a communication network.
A network based on asynchronous transfer mode (ATM) standard is an example of such a communication network. The packets in an ATM network are defined to have a predetermined small size, and are generally termed as cells. By keeping the cell size small and forwarding different cells with different priorities, ATM networks generally provide a shared communication backbone for different types of applications. For example, cells related to voice and video applications may be forwarded with a low latency, while cells related to data network applications may be provided large bandwidths in bursts. In general, sharing of the communication backbone among several applications (and end-systems) leads to lower latency (for transmission of cells end-to-end), better utilization of the bandwidth on the communication network, and easier management of the communication network.
To communicate with another end-system, an end-system of an ATM network usually ‘opens a connection’. Opening a connection generally refers to determining a sequence of switches between the two end-systems such that the switches provide at least one communication path between the two end-systems with any specific service levels required for the communication. The service levels are generally defined by the quality of service (QoS) parameters as is well known in the relevant arts.
Once a connection is established, the end systems communicate with each other using cells over the established communication path. As noted above, the switches in the communication path receive cells on one port and forward the received cells on another port to support the connection. A switch is typically in the communication path of several connections, and accordingly receives cells on several connections. As should be readily appreciated, different connections may be set up with different QoS parameters.
A switch typically needs to buffer at least some of the received cells before forwarding the buffered cells on the corresponding ports. Cells may be buffered for several reason. For example, the cells destined on an output port may be received in a burst and sufficient bandwidth may not be available to immediately forward the received cells on the destined ports. In addition, a switch may need to transmit cells in an order different from the order in which the cells are received to service different connections according to different QoS parameters. As an illustration, a cell received on a high-bandwidth connection may need to be transmitted ahead of a cell received earlier on a low-bandwidth connection.
A switch may need to use a memory to buffer cells received on various connections. In general, the memory is shared by some or all connections. Without such sharing, unacceptably large memories may be required for buffering cells received in a switch.
However, sharing of memory by several connections can cause several problems. For example, a few connections may use all the available memory, leaving no memory space for other connections. The excessive memory use can be, for example, due to the high data transmission demands placed by an end application or even due to an end application transmitting data in error.
To prevent connections from using excessive memory space, a switch may set an upper limit (upper threshold) on the amount of memory a given connection can use. The upper threshold can be dynamically varied to facilitate effective sharing of the memory space. For example, the upper threshold may be decremented during periods of high congestion, and incremented during periods of less congestion.
Typically, the aggregate of the upper thresholds of all connections is usually much larger than the available memory space because only some of the connections may be using the maximum set thresholds. As a result, in spite of the upper threshold oln memory usage on each connection, it is possible that some of the active connections together will use all the available memory space, leaving limited or no memory space for cells received on other connections. At least in view of the possibility that some connections may use undue amounts of memory space, it may be desirable to guarantee a minimum amount of memory space for some type of connections.
In one scheme, a switch may reserve memory space equal to the aggregate minimum memory space required for the connections until all connections have been allocated (i.e., used or reserved) the corresponding minimum memory space. That is, assuming a queue (i) having a present length of Qi is maintained for each connection, and a minimum memory space of Min is to be allocated for each queue, a memory space equal to &Sgr;Min
i
(for all i) is reserved in the memory until Q
i
>=Min
i
, for all connections (i). Once the >=(greater than or equal to) condition is satisfied for all the queues (or i values), no memory space may be reserved for guaranteeing the minimum requirement.
One problem with the above described scheme is that the shared memory space may not be optimally utilized as some connections may already have been using more than the corresponding minimum memory space. Such sub-optimal use can be problematic at least in switches which handle a large number of connections because the remaining (unreserved) memory may not be sufficient to buffer (and process) the cells received on these connections.
In another scheme, a switch may reserve memory space equal to &Sgr;M
i
only for connections where Q
i
<Min
i
. That is, a memory space equal to Min
i
is reserved only if the corresponding connection has not used the minimum memory space. Such a scheme offers the advantage that a connection using more than the corresponding minimum memory space does not cause memory space to be reserved.
However, some of the connections using some memory space less than the corresponding minimum memory space cause a memory space equal to the minimum memory space to be reserved. As will be readily appreciated, such reservation also leads to sub-optimal utilization of the memory space and may be undesirable.
Therefore, what is needed is a method and apparatus which use memory space optimally while providing minimum memory space to any desired connection. In addition, the method and apparatus may need to limit the maximum amount of memory used by a connection. Further, the method and apparatus need to be scalable to switches serving several ports and/or several thousands of connections.
It if further desirable that the method and apparatus accurately and efficiently provide a guaranteed minimum memory space for multicast connections also. Multicasting typically refers to the ability of one end-station (source end station) to send a cell to several end-stations (target end-stations) without the source end-station having to retransmit the cell to the individual target end stations. Thus, a multicast connection may be viewed as a tree having several output branches corresponding to a single root or source. To process cells received on a multicast connection, a switch usually needs to forward each received cell on several ports.
Thus, what is also needed is a switch which accurately provides
Bonomi Flavio Giovanni
Evans William Stanley
Shetty Suhas Anand
Vu De Bao
CSI Zeitnet (A Cabletron Systems Company)
Law Firm of Naren Thappeta
Yao Kwang B.
LandOfFree
Efficient method and apparatus for allocating memory space... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient method and apparatus for allocating memory space..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient method and apparatus for allocating memory space... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2492354