Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-06-19
2001-11-20
Patel, Ajit (Department: 2738)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S417000
Reexamination Certificate
active
06320864
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
NOT APPLICABLE
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
NOT APPLICABLE
BACKGROUND OF THE INVENTION
The present invention relates to computer networking and more particularly to a method and apparatus for performing logical multicasting in a computer network.
Telecommunications networks deliver data by routing data units, such as Asynchronous Transfer Mode (“ATM”) cells, from source to destination through switches. Each switch includes input/output (“I/O”) ports through which the ATM cells are received and transmitted, respectively. The switch determines the appropriate output port to be employed for transmission of the cell based upon an address in the received cell header, such as the VPI/VCI address within the cell header of a received ATM cell.
Depending on the destination indicated in the cell header, it may be desirable to transmit the cell from multiple ports on the switch. Cells which enter a switch through one port and exit through one port are referred to as unicast cells. Cells which enter the switch through a single port and exit through multiple ports are known as multicast cells. While most existing switches are configured to handle unicast cells, not all switches are capable of multicast operation.
Two types of multicasting are known in the art; namely spatial multicasting and logical multicasting. Spatial multicasting involves the receipt of a cell at one input port of a network switch and the forwarding of copies of the cell out of plural output ports of the network switch. Each copy of the cell which is forwarded out of an output port in a spatial multicasting operation is provided with a unique VPI/VCI address. Logical multicasting involves the receipt of a cell at an input port of a network switch and the forwarding of plural copies of the cell out of a single output port of the network switch. Each of the leaves of the logical multicast cell is transmitted from the output port with a unique VPI/VCI address.
While many switches are capable of spatial multicast operation (transmission of single copies of a cell through multiple output ports), not all multicast switches are capable of logical multicast operation (transmission of multiple copies of a cell through a single output port). Logical multicast switches are known, but are more complex and costly than typical spatial-only multicast switches.
One technique for performing logical multicast of cells within a network switch is disclosed in U.S. patent application Ser. No. 08/710,673 filed Sep. 18, 1996 and assigned to the predecessor in interest of the present application. Tile technique therein disclosed provides a first copy of the cell to the desired output port. A second copy of the cell is provided to a dedicated loop back output port which causes the cell to be looped back to an input port dedicated to loop back. The cell provided to the loop-back input port is subsequently directed to the desired output port such that the first and second copies of the cell are serially transmitted from the single desired output port. The cell may be repeatedly provided to the loop-back port to permit the cell to be transmitted in a serial fashion from the desired output as many times as desired. This technique disadvantageously requires the dedication of one input port and one output port to the logical multicasting function.
Accordingly, it would be desirable to be able to handle logical multicast operation without specifically allocating input or output ports for the support of multicast operation. Additionally, it would be useful to provide multicast type capability in switches which do not support multicast operation by design.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for performing logical multicasting in a first network device are disclosed so as to permit a downstream network device to forward cells in a manner which resembles spatial multicasting. A multicast cell which is received at a network switch is converted into a plurality of cells, each having a unique VPI/VCI address. The cells are then transmitted out of a single physical port to a downstream network node. The downstream node can then switch the cells out of different physical output ports based upon the received incoming VPI/VCI addresses transmitted by the upstream node.
More specifically, an internal cell header is prepended to an ATM multicast cell within the input port prior to forwarding the cell to the output port from which the logical multicast is to occur. The internal cell header includes a multicast identifier (MID) which is converted to a local connection identifier (CID) via a table look up within the respective output port. The local connection identifier serves as an offset value. The multicast cell is stored in one of a plurality of queues within the respective output port along with the internal cell header.
The multicast cell is retrieved from the respective queue based upon a scheduling algorithm which may employ strict priority scheduling algorithm, a weighted priority scheduling algorithm or any other suitable scheduling technique. When the multicast cell is retrieved from the respective queue, it is placed in one of a plurality of Output Cell Buffers associated with the respective output port. Each Output Cell Buffer stores a single cell for transmission over the communications link.
At call setup, a plurality of tables are configured which are employed in the presently disclosed logical multicasting technique. A first table contains VPI/VCI addresses and a chaining bit in each record entry and is indexed by the local connection identifier. A second table contains the next offset value to be employed and is likewise indexed by the local connection identifier offset. A third table contains a number of entries for cell statistics and is also indexed by the local connection identifier offset.
Logical multicasting proceeds in the following manner. The outgoing VPI/VCI address to be employed in the first outgoing cell of a series of outgoing logical multicast cells is read from the first table using the local connection identifier (CID) in the internal cell header as an offset into the table. The VPI/VCI address from the indexed location is inserted into the cell header for the outgoing cell within the applicable Output Cell Buffer and the cell is transmitted out of the respective output port. The first table also includes a chaining bit for each indexed record. If the chaining bit is set, such indicates that the cell is to be logically multicast and a further leaf of the logical multicast cell exists for transmission. Thus, if the chaining bit is set, the cell is maintained within the respective Output Cell Buffer for the duration of the logical multicast sequence.
In the event a further cell is queued for transmission, a second cell is read from one of the queues in accordance with the specified scheduling algorithm and the cell is stored in a second one of the plurality of Output Cell Buffers. The local connection identifier within the internal cell header is employed as an index into the first table to locate the outgoing VPI/VCI address for the additional cell.
When a chaining bit is set in the respective record, an additional lookup is performed in the second table using the same index value as was employed to locate the VPI/VCI address for the prior cell in the logical multicast sequence. The lookup yields a new offset which replaces the local connection identifier within the internal cell header. The new offset is employed for the next VPI/VCI lookup in the logical multicast sequence. In the foregoing manner, a linked list or chain of offsets may be generated to locate the outgoing VPI/VCI addresses for the cells to be logically multicast from the respective port. The chain terminates when the chaining bit is not set, At this point, the respective Output Cell Buffer is available to receive another cell specified by the Scheduler.
Cells are transmitted from the plurality of Output Cell Buffers in a round robin sequence so long as cells are present
Goss Gregory S.
Hebb Andrew T.
Ascend Communications, Inc.
Patel Ajit
Weingarten, Schurgin. Gagnebin & Hayes LLP
LandOfFree
Logical multicasting method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Logical multicasting method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logical multicasting method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2618431