Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-09-28
2002-05-28
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395700, C370S397000, C370S395100
Reexamination Certificate
active
06396838
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
None
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The present invention is related to the field of Asynchronous Transfer Mode (ATM) networks, and more specifically to the use of a Virtual Connection Parameter Table (VCPT) in an ATM switch in which operational parameters are stored on a per-connection basis.
During the operation of an ATM switch, it is necessary for the switch to perform specific actions in response to receiving a cell at a given input or ingress port. Most notably, the switch must forward the cell to the correct output or egress port. The switch typically performs a variety of other functions as well, such as for example monitoring subscriber data rates to enforce a maximum subscribed rate, and collecting various statistics of network operation to be used by network management software.
For many functions, it is necessary for the switch to store sets of parameters, each set being associated with a given connection. For example, the switch may employ an internal connection identifier (CID) used by components within the switch to forward a cell to the correct egress port. Other per-connection parameters can include such things as a maximum allowed data rate for a connection, and one or more counters used to track some aspect of the connection's operation, such as cell error rate.
The network-wide connections in an ATM are referred to as “virtual” connections. There are two broad classes of virtual connections: “virtual path connections” or VPCs, and “virtual channel connections” or VCCs. VPCs in ATM are specified by an 8-bit field appearing in an ATM cell called the Virtual Path Identifier (VPI). There may be several channels within a VPC; these are specified by a separate 16-bit field called the Virtual Channel Identifier (VCI). All of the channels within a VPC share some operational parameters, including the CID used for forwarding the cells within the switch. The other type of connection, the VCC, is specified by both a VPI and a VCI. In general, there may be multiple VCCs using the same VPI value. The group of VCCs having a given VPI are referred to herein as the “set” of VCCs for that VPI. Different VCCs generally employ different parameters within a switch, including VCCs in the same set.
In order to create the desired association between VPIs/VCIs and their associated parameters within a switch, a table is used that is indexed in some fashion by VPI and VCI values. When a cell arrives at a port, the VPI and VCI from the cell are used to look up the parameters in the table. In the description below, such a table is referred to as a “virtual connection parameter table” or VCPT. A VCPT resides on each line card within a switch, so that it may be accessed quickly and efficiently upon the arrival of a cell at a line card port. The VCPT can be shared among multiple ports on a line card. If that is done, a port identifier is also used as part of the index into the VCPT to distinguish connections having the same VPI and VCI values but appearing on different ports.
As mentioned above, the channels within a given VPC use a common set of parameters. Thus for each VPC on a port only one entry in the VCPT is needed, and this entry can be indexed by the corresponding VPI value alone. Each VCC also requires an entry, which means that for a given VPI there will be a set of VCPT entries, each entry corresponding to a different VCC within the set as identified by the VCI. The maximum number of VCCs in a set that share a given VPI is variable depending on network configuration. VCC set sizes are specified on a per-port and per-VPI basis by specifying the maximum number of VCI bits that may be used to identify a VCC within the set. Thus for example the maximum number of VCI bits may be specified as 10, which corresponds to a net size of 1024 VCCs. Because the number of VCCs within a set is variable, the number of entries that may be needed in the VCPT for a given set of VCCs is also variable. Thus the VCPT must be configured and accessed in a manner that accommodates the differences between VPCs and VCCs, and also accommodates the variability of the sizes of the VCC sets,
Conceptually the VCPT could be directly addressed by concatenating the port identifier and the VPI and VCI from a received cell. Among other impracticalities, such a scheme would be very wasteful of memory, because (1) typically not every VPI and VCI are in active use at a given time on a port, and (2) for VPCs, only one of the block of locations covered by each VPI would be needed. Therefore it would be preferable for the VCPT to be structured so that its storage capacity can be assigned flexibly and re-assigned dynamically in response to the creation and deletion of network connections.
One problem that can arise in dynamic re-assignment schemes is fragmentation of storage space, in which allocated areas are separated by “holes”, or empty locations that result from the deletion of connections. If fragmentation is not managed properly, the effective storage capacity of the table may be reduced dramatically, resulting in a reduction in the maximum number of active connections that a switch can handle.
It is desirable to minimize performance-reducing effects such as fragmentation of the VCPT. In general, it is desirable for VCPT space to be allocated and de-allocated in a manner that makes efficient use of VCPT storage capacity, so that the ability of the switch to respond to demand for connections is maximized.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, a technique is disclosed for managing free space in a virtual connection parameter table (VCPT) that enables the flexible assignment of storage capacity to either VPCs or sets of VCCs. For VCCs, VCPT locations are allocated in variable-sized “chunks”. Storage efficiency is enhanced by tailoring the size of each allocated chunk to the configured maximum number of VCCs in a set, rather than to the absolute maximum number (2
16
) of VCCs which in practice might seldom or never be used. Also, VCPT locations that become empty as a result of the deletion of connections are reused and/or recycled into larger chunks in a manner that reduces any tendency of the VCPT toward fragmentation.
In the disclosed technique, a VCC pointer and a VPC pointer are maintained which respectively define VCC and VPC areas at opposite ends of the VCPT. The VCC and VPC areas expand into the central area of the VCPT as the pointers are advanced. A number of “free lists” are used to hold the addresses of either single locations (for VPCs) or chunks of locations (for sets of VCCs) that have been de-allocated and are available for re-allocation. There are different free lists for different VCC set sizes that can be configured, i.e., for sets configured to use different maximum numbers of VCI bits. In one embodiment there are separate free lists for set sizes of all powers of 2 between 64 and 16K.
When a new VPC is created, so that a corresponding VPC entry in the VCPT is required, it is first determined whether the VPC free list contains an entry, and if so the VCPT location identified by the entry is allocated as a VPC entry to hold parameters for the new VPC. If the VPC free list does not contain an entry, it is determined whether the VPC pointer can be advanced to expand the VPC area into the central area of the VCPT. If so, the VPC pointer is advanced and a location in the expanded part of the VPC area is allocated. De-allocation of a VPC entry proceeds in reverse order, i.e., if possible the VPC area is shrunk by backing up the VPC pointer, and if not the entry is placed on the VPC free list to be available for a subsequent allocation.
When a new VCC is created, an allocation process similar to the VPC allocation process is carried out if the new VCC is the first VCC being created for a given port and VPI. For each allocation, the appropriate VCC free list is used based on the configured set size. For example, if a given port and VPI are configured t
Ascend Communications, Inc.
Kizou Hassan
Spafford Tim
Weingarten Schurgin Gagnebin & Hayes
LandOfFree
Management of free space in an ATM virtual connection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Management of free space in an ATM virtual connection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Management of free space in an ATM virtual connection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2821962