VC merging for ATM switch

[0002] This application is related to the following (all of which are incorporated herein by reference): U.S. patent application Ser. No. 08/891,232, entitled “ABR SERVER”, filed Jul. 11, 1997; U.S. patent application Ser. No. 08/890,758, entitled “HANDLING ATM MULTICAST CELLS”, filed Jul. 11, 1997; U.S. patent application Ser. No. 08/893,576, entitled “A DATA SHAPER FOR ATM TRAFFIC”, filed Jul. 11, 1997; U.S. patent application Ser. No. 08/893,479, entitled “VP/VC LOOK-UP FUNCTION”, filed Jul. 11, 1997.

[0003] 1. Field of Invention

[0004] This invention pertains to telecommunications, and particularly to the handling of cells in a switching node of a telecommunications network operating in the asynchronous transfer mode.

[0005] 2. Related Art and Other Considerations

[0006] The increasing interest for high band services such as multimedia applications, video on demand, video telephone, and teleconferencing has motivated development of the Broadband Integrated Service Digital Network (B-ISDN). B-ISDN is based on a technology know as Asynchronous Transfer Mode (ATM), and offers considerable extension of telecommunications capabilities.

[0007] ATM is a packet-oriented transfer mode which uses asynchronous time division multiplexing techniques. Packets are called cells and have a fixed size. An ATM cell consists of 53 octets, five of which form a header and forty eight of which constitute a “payload” or information portion of the cell. The header of the ATM cell includes two quantities which are used to identify a connection in an ATM network over which the cell is to travel, particularly the VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier). In general, the virtual is a principal path defined between two switching nodes of the network; the virtual channel is one specific connection on the respective principal path.

[0008] At its termination points, an ATM network is connected to terminal equipment, e.g., ATM network users. Between ATM network termination points are a plurality of switching nodes having ports which are connected together by physical transmission paths or links. In traveling from an origin terminal equipment to a destination terminal equipment, ATM cells forming a message may travel through several switching nodes.

[0009] A switching node has a plurality of ports, each of which is connected by via a link circuit and a link to another node. The link circuit performs packaging of the cells according to the particular protocol in use on the link. A cell incoming to a switching node may enter the switching node at a first port and exit from a second port via a link circuit onto a link connected to another node. Each link can carry cells for a plurality of connections, a connection being a transmission between a calling subscriber or party and a called subscriber or party.

[0010] The switching nodes each typically have several functional parts, a primary of which is a switch core. The switch core essentially functions like a cross-connect between ports of the switch. Paths internal to the switch core are selectively controlled so that particular ports of the switch are connected together to allow a message ultimately to travel from an ingress side of the switch to an egress side of the switch, and ultimately from the originating terminal equipment to the destination terminal equipment.

[0011] FIG. 1 shows a prior art ATM switching device 10 having a switch core 12, a plurality of ingress ports 14 (1)-14 (3), and a exemplary egress port 16. FIG. 1 shows, in broken lines, cells incoming to switch 10 on three channels, particularly a first channel VC-1 to port 14 (1), a second channel VC-2 to port 14 (2), and a third channel VC-3 to port VC-3. All cells on the same channel have the same VC or VCI, e.g., cells on the first channel all have a first VC denominated as VC-1.

[0012] In the illustration of FIG. 1, the incoming cells on all channels VC-1 through VC-3 happen to be switched through switch core 12 to the same egress port 16 for eventual output to channel VC-4. At egress port 16 the cells are all assigned a new VPI/VCI code. The switching of several incoming VC channels to a same outgoing VC channel is referred to as “VC merging”. The purpose of VC merging is to collect packets that shall be routed to the same destination into one single virtual channel, instead of using a separate VC between each source and the destination. This reduces the number of required virtual channels in the ATM network.

[0013] If the cells were all sent out in the order in which they arrived at the switch core 12, there would be no way of separating them at the end-point of channel VC-4. For this reason, VC merging can only work for channels carrying AAL-5 packets by storing complete packets at the egress port and sending them out packet-by-packet, i.e., the multiplexing is performed at the packet level.

[0014] What is needed, therefore, and an object of the present invention, is method and apparatus for efficiently conducting a VC merging operation.

[0015] An Asynchronous Transfer Mode (ATM) switching device has a switch core connected to a plurality of incoming VC channels and an egress port connected to receive cells from the switch core. The egress port has both a plurality of pre-merge VC queues and a plurality of merge VC queues. Cells received from the switch core are stored in one of the plurality of pre-merge VC queues in accordance with their incoming VC channel. A merge controller determines when one of the pre-merge VC queues has a complete packet of cells, and enters the packet of cells into an appropriate one the merge VC queues.

[0016] In one embodiment, the plurality of pre-merge VC queues and the merge VC queues are each stored as separate linked lists in a common memory. The merge controller enters the completed packet of cells into the appropriate merge VC queue by linking the pre-merge linked list storing the packet to the linked list which forms the merge VC queue.

[0017] The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments as illustrated in the accompanying drawings in which reference characters refer to the same parts throughout the various views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

[0018] FIG. 1 is a schematic view of a prior art ATM switching device.

[0019] FIG. 2 is a schematic view of a ATM switching device according to an embodiment of the present invention.

[0020] FIG. 3 is a schematic diagram showing the relationship of FIG. 3A and FIG. 3B.

[0021] FIG. 3A and FIG. 3B are flowcharts showing operations performed in an egress port of the ATM switching device of FIG. 2 with respect to a pre-merge queue.

[0022] FIG. 4A-FIG. 4F are schematic views of the egress port of the ATM switching device of FIG. 2 showing cell population of a post-merge queue and pre-merge queues in accordance with an exemplary scenario.

[0023] FIG. 5A-FIG. 5F are schematic views of a memory of the egress port of the ATM switching device of FIG. 2 showing cell population in accordance with the exemplary scenario depicted by corresponding FIG. 4A-FIG. 4F.

[0024] In the following description, for purposes of explanation and not limitation, specific details are set forth such as particular architectures, interfaces, techniques, etc. in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. In other instances, detailed descriptions of well known devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail.

[0025] FIG. 2 is a schematic view of ATM switching device 100 according to an embodiment of the present invention, also simply referred to as the ATM switch. ATM switch has a switch core 112 to which are connected a plurality of ingress ports 114 (1)-114 (3) and egress port 116. For sake of simplification of illustration, only three ingress ports 114 and one egress port 116 are depicted, it being understood that in actuality there are many ingress ports and many egress ports.

[0026] In like manner with FIG. 1, FIG. 2 shows, in broken lines, cells incoming to switch 100 on three channels, particularly a first channel VC-1 to port 114 (1), a second channel VC-2 to port 114 (2), and a third channel VC-3 to port VC-3. All cells on the same channel have the same VC or VCI, e.g., cells or. the first channel all have a first VC denominated as VC-1.

[0027] Switch core 112 routes cells to many egress ports, of which egress port 116 is shown as one example. Egress port 116 is connected to an outgoing link 120 through an unillustrated link interface circuit. In the particular embodiment shown in FIG. 2, egress port 116 comprises a memory 130 and a merge controller 132. Memory 130 can be any suitable storage means, such as a random access memory (RAM). In the example of FIG. 2, merge controller 132 is a microprocessor.

[0028] Memory 130 of egress port 116 includes a plurality of VC merge queues and a plurality of pre-merge VC queues. For sake of simplicity, only one VC merge queue 140 and three pre-merge VC queues 144 (1) through 144 (3) are illustrated. Each pre-merge VC queue 144 corresponds to a paired one of the incoming VC channels. As a cell is received by egress port 116 from switch core 112, merge controller 132 directs the cell to one of the pre-merge VC queues 144 (1) through 144 (3) in accordance with the incoming VC of the cell. For example, cells received on channel VC-1 are directed by merge controller 132 to pre-merge VC queue 144 (1); cells received on channel VC-2 are directed by merge controller 132 to pre-merge VC queue 144 (2); and so forth.

[0029] Merge controller 132 knows the incoming VC channel of a cell output to egress port 116 from switch core 112. Each cell carries a channel identifier, e.g., 16 bits that are prepended to the actual ATM cell. In this regard, the ingress port prepends each cell with routing information (e.g., to which egress port the cell shall be switched in the switch core) and the channel identifier which is used by the egress port to identify the cell. The channel identifier is derived from the VPI and VCI field of the incoming cell.

[0030] Cells are collected in their respective pre-merge queues 144 until merge controller 132 determines that an entire packet has been assembled in the pre-merge queue 144. When a completed packet has been assembled in a pre-merge queue 144, that completed packet is moved into the merge VC queue 140.

[0031] As demonstrated hereinafter with respect to FIGS. 5A-5F, the merge VC queue 140 is a linked list in memory 130 and the plurality of pre-merge VC queues are each separate linked lists in memory 130. Merge controller 132 enters a completed packet of cells in a selected one of the pre-merge VC queues 144 into merge VC queue 140 by linking the linked list of the selected one of the pre-merge VC queues 144 to the linked list which forms the VC queue 140.

[0032] Each pre-merge VC queue 144 and VC queue 140 have a set of control words associated therewith. These control words are also stored in memory 130, as indicated in FIG. 2. For example, merge VC queue 140 has set 150 of control words and pre-merge VC queues 144 (1)-144 (3) have corresponding sets 154 (1)-154 (3) of control words. The control words included in set 154 for each pre-merge VC queue 144 are explained by Table 1. The control words included in set 150 for merge VC queue 140 are explained by Table 2.

[0033] Each cell in the pre-merge queues 144 and in the merge VC queue 140 has a pointer “Next” associated therewith. The pointer “Next” is or points to an address of the next cell which follows the cell in the corresponding queue.

[0034] In the above regard, FIG. 5A-FIG. 5F show contents, at differing times, of a portion of memory 130 in accordance with an example scenario of operation of the present invention. In each of FIG. 5A-FIG. 5F, memory 130 is shown as segmented into cell storage locations, such as a first storage location LO, a second storage location L1, and so forth. Each storage location is depicted as having, in its lower right hand corner, the associated “Next” pointer. Reference letter N is employed in FIG. 5A to indicate the “Next” pointer for the cell C1 stored at location L2. The “Next” pointer for cell C1 shows that cell C1 is followed in the linked list by the cell having location L4, i.e., cell C2.

[0035] FIG. 3A and FIG. 3B depict basic steps performed by egress port 116 in accordance with the present invention. Step 3-1 shows egress port 116 obtaining a cell from switch core 112. When a cell is obtained from switch core 112, the cell also contains an indication of its incoming channel number (e.g., whether VC-1, VC-2, etc) and whether the cell is the last cell of a packet. Based on the incoming channel number, at step 3-2 merge controller 132 selects an appropriate pre-merge VC queue 144.

[0036] With an appropriate one of the pre-merge VC queues 144 having been selected at step 3-2, at step 3-3 a free location in memory 130 where the cell can be written is determined. Memory 130 is common to all queues, and all unused positions are linked into an idle queue. When a cell arrives, it is placed in the first buffer in this idle queue, and then linked into the right pre-merge VC queue (and linked out from the idle queue).

[0037] At step 3-4 the cell just written into the free location in memory 130 is linked to the selected pre-merge queue 144. At step 3-5 the location of the just-written cell is indicated by the Tail_in pointer.

[0038] At step 3-6 merge controller 132 determines whether the selected pre-merge VC queue 144 was formerly empty (i.e., empty for writing of the just-written cell). This is done by reading the Count in value. If the determination at step 3-6 is affirmative, at step 3-7 merge controller 132 sets the Head_in pointer (see the control words of sets 154 in FIG. 2) of the selected pre-merge queue 144 to the position (e.g. location) of the cell just written. Thus, step 3-7 essentially sets the beginning of the selected pre-merge VC queue at the location occupied by the just-written cell.

[0039] When the selected pre-merge VC queue 144 was not previously empty (indicated by counter value=0), at step 3-8 merge controller 132 determines whether the just-written cell is the last cell in a packet. The last cell of each packet has its PTI-field coded to 001 or 011. The PI field is bits 2-4 in the fourth octet of the ATM cell header bits number 1-8, bit 8 being transmitted first).

[0040] If the just-written cell does not complete a packet, steps 3-9 and 3-10 are executed before merge controller 132 awaits receipt of another cell at step 3-1. At step 3-9, merge controller 132 sets the Tail_in pointer for the selected pre-merge VC queue to the location of the cell just written. At step 3-10, the cell counter Count_in for the selected pre-merge VC queue is incremented to take into consideration inclusion of the just-written cell.

[0041] The steps of FIG. 3B are executed when merge controller 132 has determined that a packet has been completely assembled in the selected pre-merge VC queue 144. At step 3-11, for the selected pre-merge VC queue 144 the merge controller 132 uses the Out-VC pointer value to determine to which of the plurality of VC merge queues the new packet should be linked. In this regard, while only one VC merge queue 140 has been shown, in actuality there are many such VC merge queues. The value of the Out_VC pointer for a particular pre-merge VC queue determines to which of the plurality of VC merge queues the packets are destined.

[0042] At step 3-12 merge controller 132 determines whether the length of the merge VC queue 140 is zero. This determination is accomplished by checking the value of control word Length in set 150 (see FIG. 2). If the determination of step 3-12 is affirmative, at step 3-13 merge controller 132 sets the Head_out pointer of merge VC queue 140 equal to the Head_in pointer of the selected pre-merge VC queue 144.

[0043] Assuming merge VC queue 140 is not empty, at step 3-14 merge controller 132 sets the “Next” pointer for the cell which is currently the last cell in merge VC queue 140 equal to the value of the Head_in pointer for pre-merge VC queue 144. The currently last cell is found by reading the value of the Tail-out pointer. Step 3-14 effectively links the completed packet in the pre-merge VC queue to merge VC queue, by having the “Next” pointer of what was formerly the last cell in merge VC queue 140 set to point to the first cell of the completed packet in the selected pre-merge VC queue 144.

[0044] Upon completion of either step 3-14 or step 3-13, at step 3-15 merge controller 132 sets the Tail_out pointer of merge VC queue 140 to the location of the cell just written in the selected pre-merge VC queue 144. Step 3-15 effectively indicates that the end of merge VC queue 140 is now at the end of the selected pre-merge VC queue 144.

[0045] At step 3-16 merge controller 132 adds the cell counter (Count_in) for the selected pre-merge VC queue 144 to the length counter (Length) for merge VC queue 140, thereby updating the length counter (Length) for merge VC queue 140. Then, at step 3-17, merge controller 132 clears the cell counter (Count-In) for the selected pre-merge VC queue 144, since reading out of the completed packet from the selected pre-merge VC queue 144 empties the selected pre-merge VC queue 144. With the completed packet thus having been merged into merge VC queue 140, at step 3-18 merge controller 132 then awaits a further cell from switch core 112.

[0046] As appropriate, the steps of FIG. 3A and/or FIG. 3B are performed by merge controller 132 for each cell obtained from switch core 112. Which pre-merge VC queue 144 is the “selected” pre-merge VC queue 144 for any particular cell for which the steps of FIG. 3A and FIG. 3B are executed depends, as explained previously, on the incoming VC channel for the cell.

[0047] FIG. 4A-FIG. 4F illustrate an example scenario of operation of ATM switch 110 of the present invention in accordance with the steps of FIG. 3A and FIG. 3B as above described. FIG. 4A-FIG. 4F, showing portions of egress port 116, are correlated with FIG. 5A-FIG. 5F, respectively, which show portions of memory 130 of egress port 116. At a first time shown in FIG. 4A and FIG. 5A, merge VC queue 140 has cells C1 and C2 stored therein, and pre-merge VC queues 144 (2) and 144 (3) have cells C3 and C4, respectively, stored therein. As mentioned previously, the “Next” pointer N of cell C1 points to the location of cell C2, i.e., location L4, by which merge VC queue 140 is formed by a linking of cell C2 to cell C1.

[0048] FIG. 4B and FIG. 5B show cell C5 entering from switch core 112 and, in view of its incoming VC, being stored in pre-merge VC queue 144 (1). It just so happens that the free list pointer in memory 130 points to location L0, with the result that cell C5 is stored in location L0 of memory 130.

[0049] FIG. 4C and FIG. 5C show reception and storage in pre-merge VC queue 144 (1) of a further cell C6. Cell C6 is stored in a next free location in memory 130, i.e., location L1. So that cell C6 is linked into pre-merge VC queue 144 (1), in accordance with step 3-5 of FIG. 3A the “Next” pointer for cell C5 is loaded with the location of cell C6, i.e., location L1.

[0050] FIG. 4D and FIG. 5D show reception and storage in pre-merge VC queue 144 (2) of a further cell C7. Cell C7 is stored in a free location in memory 130, i.e., location L3, the free location being determined in accordance with the idle list. Cell C7 was stored in pre-merge VC queue 144 (2) since it had an incoming VC corresponding to VC channel VC-2. Thus, it is seen that cells received from switch core 112 are not necessarily all consecutively stored in the same pre-merge VC queue 144. So that cell C7 is linked into pre-merge VC queue 144 (2), the “Next” pointer for cell C3 is loaded with the location of cell C7, i.e., location L3.

[0051] FIG. 4E and FIG. 5E show reception and storage in pre-merge VC queue 144 (1) of a further cell C8. Cell C8 is stored in a next free location in memory 130, i.e., location L5. So that cell C8 is linked into pre-merge VC queue 144 (1), the “Next” pointer for cell C6 is loaded with the location of cell C8, i.e., location L5.

[0052] As also shown in FIG. 4E, it is determined by merge controller 132 that an entire packet P consisting of cells CS, C6, and C8 has been assembled in pre-merge VC queue 144 (1). Accordingly, as depicted by FIG. 4F and FIG. 5F, merge controller 132 links pre-merge VC queue 144 (1) to merge VC queue 140.

[0053] The linkage of pre-merge VC queue 144 (1) to merge VC queue 140 is shown in FIG. 4F by inclusion of cells C5, C6, and C8 in merge VC queue 140, and in FIG. 5F by e.g., loading the location of the first cell in queue 144 (1), i.e., location L0, into the “Next” pointer of what formerly was the last cell in queue 140, i.e., cell C2.

[0054] After the cells have been stored in the right one of the plurality of merge VC queues, e.g., VC merge queue 140 in the present illustration, a scheduler or selector may take one cell from each of the merge VC queues at a time (e.g., in round-robin fashion) and send the cells out onto an outgoing link. When doing so, a new VPI/VCI value is assigned to the cells, the same value being assigned for all cells from a particular merge VC queue. Alternatively, the new VPI/VCO value may be provided by the ingress port and already inserted in to the cell when it arrives at the egress port. When the cell has been sent out, the corresponding position in memory 130 is returned to the idle queue, i.e., setting the Next pointer of the previously last cell in the idle queue to point to it.

[0055] In accordance with the present invention, cell arriving from switch core 112 is put into an appropriate one of the plurality of pre-merge VC queues 144 based on its incoming internal channel number (VC). When the last cell of a packet has been received in a pre-merge VC queue 144, as indicated by a specified bit in the cell header, merge controller 132 moves the completed packet to merge VC queue 140 for output from egress port 116. There is one merge VC queue 140 for each outgoing channel, so that for any outgoing channel the cells are sent out in the order in which they are stored in the merge VC queue 140 for that channel, i.e., one complete packet at a time.

[0056] While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various alterations in form and detail may be made therein without departing from the spirit and scope of the invention.