Method and Apparatus for Route Processing Asynchronous Transfer Mode Cells

This invention relates in general to telecommunication network systems and more particularly to a method and apparatus for route processing asynchronous transfer mode cells.

Conventional switching modules that process asynchronous transfer mode (ATM) cells require a determination of routing information for each ATM cell in order for proper message transmission. The determination of routing information for each ATM cell is performed through a full memory look up for obtaining the appropriate routing information. These full memory look ups take a significant amount of time to accomplish. Loss of packets and individual ATM cells which form specific packets can occur due to the delay time in determining routing information.

From the foregoing, it may be appreciated that a need has arisen for a method and device that determines route information for asynchronous transfer mode cells. A need has also arisen for a method and device that quickly retrieve route information without unnecessary memory access.

In accordance with the present invention, a method and apparatus for route processing asynchronous transfer mode (ATM) cells are provided which substantially eliminate or reduce disadvantages and problems associated with conventional ATM cell processing.

The present invention includes a route cell buffer that receives ATM cells corresponding to a beginning and end of a packet, wherein the packet is defined by a plurality of ATM cells. An ingress router determines routing information from the ATM cells received in the route cell buffer and generates a setup ATM cell and a teardown ATM cell containing the appropriate routing information for the packet. The ingress router accesses routing information from content addressable memory in response to ATM cells received by the route cell buffer. The routing information includes a routing label that determines an output port for packet transmission and a virtual circuit identifier that determines switching paths within a network to connect a source user to a destination.

The present invention provides for various technical advantages over conventional ATM cell routing processing systems. For example, one technical advantage is in storing and quickly accessing routing information for a particular packet. Another technical advantage is the ability to retrieve routing information without a full, time consuming memory access. Other technical advantages are readily apparent to one skilled in the art from the following figures, descriptions, and claims.

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings, wherein like reference numerals represent like parts, in which:

FIG. 1 illustrates a block diagram of a line processor within a broadband switching module for an integrated services digital network;

FIG. 2 illustrates a block diagram of an ingress processor within the line processor; and

FIG. 3 illustrates a block diagram of an ingress router used by the ingress processor.

FIG. 1 is a block diagram of a line processor 10 for a broadband switching module within an integrated services digital network. Line processor 10 includes an ingress line interface 12 receiving information off input ports 14. Ingress line interface 12 sends information to an ingress processor 16 that routes the information to an egress processor 18 through a cell bus 20. Information is transmitted from egress processor 18 through an egress line interface 22 onto output ports 24. A control processor (CP) 26 supervises operation of line processor 10. Though shown having single units, line processor 10 may have a plurality of ingress line interfaces 12, and egress line interfaces 22 coupled to cell bus 20 in order to handle a multitude of input ports 14 and output ports 24.

In operation, ingress line interface 12 performs a service adaptation function on the incoming traffic received from input ports 14. The incoming traffic may have any of several configurations, such as Frame Relay or Switched Multi-Megabit Data Service (SMDS) protocols. The incoming traffic is converted into asynchronous transfer mode (ATM) cells according to the service provided on a given input port 14. Each ATM cell typically comprises 53 bytes. Ingress processor 16 receives the ATM cells from ingress line interface 12 and performs protocol checks, determines routing paths for the ATM cells, and formats each ATM cell into a 64 byte block. Appendix A shows the 64 byte block of a formatted ATM cell with the shaded area identifying the 53 byte ATM cell placement. Appendix A also has descriptions of some of the fields within the formatted ATM cell. Further information on the content of ATM cells can be found in Bellcore specification TR-TSV-000772. Ingress processor 16 generates a setup ATM cell and a teardown ATM cell that carry routing information to open and close a transmission link, respectively, and transfers the setup ATM cell, and other formatted ATM cells, the teardown ATM cell to egress processor 18 through cell bus 20. Further information on setup and teardown cells can be found in copending U.S. patent application Ser. No. 08/188,559, entitled "Method of Transmitting Call Information Prior to Establishing a Connection Path", which is incorporated by reference herein.

Egress processor 18 identifies formatted ATM cells corresponding to a particular message and effectively places corresponding formatted ATM cells into a particular packet for output transmission. Egress line interface 22 receives each packet from egress processor 18 and converts the packets from formatted ATM cells into the appropriate service specific traffic according to the appropriate output port 24. Further information on egress processing can be found in copending U.S. patent application Ser. No. 08/339,301, entitled "Apparatus and Method for Processing Asynchronous Transfer Mode Cells", which is incorporated by reference herein. The present invention lies within ingress processor 18 and is discussed in detail as follows.

FIG. 2 is a block diagram of ingress processor 16 within line processor 10 of the broadband switching module. Ingress processor 16 includes a cell loader 30 that receives ATM cell information from ingress line interface 12 and transmits formatted ATM cells to an ingress cell (ICELL) memory 32. Locations within ICELL memory 32 are accessed through the use of a free cell first in, first out (FIFO) buffer 34 and a used cell FIFO buffer 36. An ingress controller 38 supervises formatted ATM cell flow within ingress processor 16. Ingress controller 38 responds to state information stored within a call table 40. Ingress controller 38 processes each formatted ATM cell and sends appropriate formatted ATM cells to a route cell buffer 42 for determination of route information by an ingress router 44. Further information on route generation can be found in copending U.S. patent application Ser. No. 08/188,310, entitled "Method and Apparatus for Generating Route Information for Asynchronous Transfer Mode Cell Processing", which is incorporated by reference herein.

For transmission purposes, formatted ATM cells are retrieved from ICELL memory 32 and stored in a transmit agent cell buffer 46 prior to transmission by a transmit agent 48. A virtual circuit identifier (VCI) table 50 provides routing information to ingress router 44 and transmit agent 48. Transmit agent 48 may also receive transmit cells generated by control processor 26 through a transmit cell FIFO buffer 52. Control processor 26 may also perform testing functions on cell loader 30 through a test port 54.

In operation, ATM cells from ingress line interface 12 enter ingress processor 16 on an input bus IBUS at cell loader 30. Cell loader 30 also receives ingress and egress status in multiplex form over a status bus SBUS. A status select SSEL signal from cell loader 30 selects either ingress status or egress status. Cell loader 30 may also be used to load ATM cells received from cell bus 20 for egress processor 18. Further information on cell bus operation can be found in copending U.S. patent application Ser. No. 08/015,695, entitled "High-Speed Packet But", which is incorporated by reference herein.

Cell loader 30 checks the status bus data for ingress to see if an ATM cell is available from ingress line interface 12. If an ATM cell is available, cell loader 30 formats the ATM cell into the 64 byte block shown in Appendix B and transfers the formatted ATM cell to ICELL memory 32. Cell loader 30 constructs a `pseudo VCI` for placement within the formatted ATM cell from the message identification (MID) field of the ATM cell. The MID field identifies ATM cells belonging to a particular packet. The pseudo VCI is used to index state information within call table 40 and VCI table 50. Cell loader 30 also initializes the first four bits in the routing label field to specify a normal traffic cell type and the error code and next pointer fields are reset to zero. Cell loader 30 also generates an egress status signal to inform egress processor 18 of the availability of space on egress line interface 22.

Free cell FIFO buffer 34 and used cell FIFO buffer 36 carry cell locations of formatted ATM cells within ICELL memory 32 between cell loader 30 and ingress controller 38. Free cell FIFO buffer 34 provides pointers to free cell locations within ICELL memory 32 and used cell FIFO buffer 36 provides pointers to used cell locations within ICELL memory 32. Free cell FIFO buffer 34 receives a list of all free cell locations within ICELL memory 32 from ingress controller 38 as determined by control processor 26 upon initialization. In this manner, formatted ATM cells are stored in ICELL memory 32 in any available space and regardless of packet associations.

Ingress controller 38 processes formatted ATM cells within ICELL memory 32 through used cell FIFO buffer 36, route cell buffer 42, or an active chain as specified by state information within call table 40. An active chain is a group of cells that define a particular packet and indicate that a specific call is being processed through the system. Formatted ATM cells within a packet are chained together by reference to the next pointer field within each formatted ATM cell. The next pointer field within each formatted ATM cell points to a successive formatted ATM cell within the chain corresponding to a particular packet. Active chains have the highest priority, while formatted ATM cell locations from used cell FIFO buffer 36 have the lowest priority. Formatted ATM cells within route cell buffer 42 have a priority above used cell FIFO buffer 36 but below that of an active chain.

Call table 40 provides state information for ingress controller 38 as indexed by each pseudo VCI generated by cell loader 30 for the formatted ATM cells. State information included within call table 40 for each pseudo VCI generated by cell loader 30 includes the following:

State information (1 word) including,

Unlink bit (1 bit),

Link bit (1 bit),

Waiting for COM/EOM (1 bit),

Expected sequence number (4 bits),

Other elements (1 bit),

First cell number in the chain (i.e., head of chain) (1 word), and

Last cell number in the chain (i.e., tail of chain) (1 word).

Upon receipt of each ATM cell, cell loader 30 places the formatted ATM cell in ICELL memory 32 in the cell location specified by free cell FIFO buffer 34. Cell loader 30 then places the cell location retrieved from free cell FIFO buffer 34 into used cell FIFO buffer 36. Ingress controller 38 access the formatted ATM cell from the cell location specified in used cell FIFO buffer 36 and verifies the MID against the segment type and the L2 payload length as specified in Bellcor specification TR-TSV-000772. For a beginning of message (BOM) cell, ingress controller 38 writes the BOM cell to route cell buffer 42 from ICELL memory 32. Ingress controller 38 sets the Link bit, Waiting For COM/EOM bit, the expected sequence number, and places the BOM cell location within the first and last cell number fields within call table 40 indexed by the pseudo VCI within the BOM cell as generated by cell loader 30. Ingress router 44 processes the BOM cell from route cell buffer 42 and generates a setup ATM cell, that includes route information determined by ingress router 44, for placement in route cell buffer 42 to be available for use by ingress controller 38. The setup ATM cell is used to establish a route for packet transmission.

For a continuation of message (COM) cell received at cell loader 30 and stored at ICELL memory 32, ingress controller 38 verifies the MID against the segment type and checks the L2 payload length and the Wait for COM/EOM bit. Ingress controller 38 compares the sequence number against the sequence number of the preceding formatted ATM cell, which could be a COM or BOM cell. Ingress controller 38 chains the COM cell to the preceding COM or BOM cell by writing this COM's cell location into the next pointer field of the preceding COM or BOM cell only if the Link bit is set. Ingress controller 38 updates call table 40 by writing the current COM cell location into the last cell number field and updates the expected sequence number in the corresponding field within call table 40. Since a route determination has been made with regard to the BOM cell, the COM cell need not be sent to route cell buffer 42 and remains in ICELL memory 32. If the Link bit is not set, the current COM cell is sent directly to transmit agent cell buffer 46.

For receiving an end of message (EOM) cell, ingress controller 38 verifies the MID against the segment type, checks the L2 payload length and the wait for COM/EOM bit, and compares the sequence number against the sequence number of the preceding formatted ATM cell, which can be a COM or BOM cell. Ingress controller 38 chains the EOM cell to the preceding COM or BOM cell by writing the EOM cell location to the next pointer field of the preceding COM or BOM cell. Ingress controller 38 also writes the EOM cell location to the last cell number field in call table 40. The Wait for COM/EOM bit within call table 40 is reset and writes the EOM cell to route cell buffer 42. Ingress router 44 processes the EOM cell from route cell buffer 42 and generates a teardown ATM cell for placement in route cell buffer 42 to be available for use by ingress controller 38. The teardown ATM cell includes route information determined by ingress router 44 for use in releasing a route after a packet has been sent.

When ingress router 44 completes route processing, a setup ATM cell is sent to ingress controller 38 through route cell buffer 42. Ingress controller 38 copies the setup ATM cell to transmit agent cell buffer 46. Ingress router 44 may or may not complete route processing before an EOM cell sets the Unlink bit, and resets the Link bit within call table 40 to establish an active chain. When the chain is active, linked formatted ATM cells can be sent directly to transmit agent cell buffer 46 without determining route information for each ATM cell within a packet.

Ingress controller 38 writes the BOM cell to transmit agent cell buffer 46 and obtains the next cell location from the next pointer field within the BOM cell and writes that cell location to the first cell number field in call table 40. The cell location of the BOM cell is now returned to free cell FIFO buffer 36 for use by newly received ATM cells at cell loader 30. Ingress controller 38 then writes the next COM cell to transmit agent cell buffer 46 and obtains the next cell location from the next pointer field of the COM cell and writes it to the first cell number field in call table 40. The cell location of the COM cell is returned to free cell FIFO buffer 36. This process repeats until ingress controller 38 writes the EOM cell to transmit agent cell buffer 46 and route cell buffer 42. When this occurs, ingress controller 38 resets the Unlink bit in call table 40, deactivating the chain, and returns the cell location of the EOM cell to free cell FIFO buffer 36. Ingress controller 38 then sends the teardown ATM cell generated by ingress router 44 to transmit agent cell buffer 46 and discards the BOM, COM, and EOM cells.

If ingress router 44 completes route processing before the EOM cell is handled by ingress controller 38, some formatted ATM cells corresponding to a packet may not be linked together because the link bit was reset upon generation of the setup ATM cell. In such an instance, unlinked formatted ATM cells are sent directly to transmit agent cell buffer 46 after processing by ingress controller 38. The unlinked formatted ATM cells corresponding to a specific packet then can be transmitted with the previously linked formatted ATM cells of the packet.

Transmit agent 48 receives ATM cells from either transmit agent cell buffer 46 or transmit cell FIFO 52. Transmit cell FIFO buffer 52 receives ATM cells generated by control processor 26 and sends control processor 26 generated ATM cells to transmit agent 48 for transmission onto transmitters TxA and TxB to cell bus 20. For transmission of ATM cells from transmit agent cell buffer 46, transmit agent 48 retrieves the pseudo VCI from each formatted ATM cell to index VCI table 50. VCI table 50 contains routing information determined by ingress router 44. Routing information within VCI table 50 includes a routing label indicating the output board destination of the formatted ATM cell and a VCI indicating the switching path through switching modules within the transmission network. Transmit agent 48 places the routing information from VCI table 50 into each ATM cell received from transmit agent cell buffer 46 before transmission onto transmitters TxA and TxB. The VCI and routing label initially placed within each formatted ATM cell by ingress controller 38 are merely default values and thus must be replaced by routing information from VCI table 50. There is no substitution and no use of VCI table 50 when transmitting ATM cells from transmit cell FIFO buffer 52.

FIG. 3 is a block diagram of ingress router 44 and its connection to other components of ingress processor 16. Ingress router 44 includes a router controller 60 operating under instructions from a program memory 62 and a mailbox memory 64. Program memory 62 receives code from control processor 26 over a transceiver 66 and interrupts from a timer 68. A universal asynchronous receiver transmitter (UART) 70 provides a serial port for debugging and a general purpose parallel input/output port. Routing information is stored in a content addressable memory 72 and route cache associative memory 73 for access by router controller 60.

CAM 72 includes information corresponding to destination and source addresses found in the payload section of each formatted ATM cell. Due to the limited size of CAM 72, typically a 64 bit width, an abbreviated version of the destination and source address is stored within CAM 72. Route cache associative memory 73 includes a full version of the destination and source addresses plus the routing label and the VCI for a variety of possible CAM entries accessing route cache associative memory 73. Though shown as two separate memories, CAM 72 and route cache associative memory 73 may be within a single memory having the features of a content addressable memory.

Upon receiving a BOM/EOM cell at route cell buffer 42, router controller 60 compares destination and source address information within the BOM/EOM cell with similar information within CAM 72. Upon finding a match, CAM 72 generates a cache entry which is used to index route cache associative memory 73. A bit compare of the information located within route cache associative memory 73, as accessed by the cache entry generated by CAM 72, with the BOM/EOM cell is performed to verify the correct cache entry. Upon verification, the routing label and VCI are retrieved from route cache associative memory 73 and stored within the BOM/EOM cell and VCI table 50 as indexed by the pseudo VCI generated by cell loader 30. If verification fails, a skip bit is set at the location in CAM 72 generating the cache entry and a new search is performed with CAM 72 from identifying the same location having the same cache entry to allow a search through remaining locations within CAM 72. Ordinarily, CAM 72 will not have more than one identical accessible location but the skip bit allows for this possibility to occur. If no match is found, router controller 60 must request routing information from control processor 26.

In operation, router controller 60 performs packet and route processing. Formatted ATM cells that are either BOM or EOM cells are sent to router controller 60 from ingress controller 38 through route cell buffer 42. Router controller 60 looks up the route in CAM 72 and route cache associative memory 73 corresponding to the formatted ATM cell in route cell buffer 42 and generates a setup or teardown cell for placement in route cell buffer 42 in order to be processed by ingress controller 38. Transceiver 66 downloads program code from control processor 26 into program memory 62 when ingress router 44 is initialized by control processor 26. Further communication between router controller 60 and the control processor 26 is performed through mailbox memory 64. Once routing information is determined for a particular BOM cell, VCI table 50 is appropriately updated and remaining cells within the packet associated with the BOM cell need not be sent through ingress router 44. Transmit agent 48 can access routing information from VCI table 50 for all cells within a particular packet.

In summary, routing information for a particular packet can be determined from the BOM cell of the packet. An ingress router receives the BOM cell from an ingress cell memory through a route cell buffer as controlled by an ingress controller. A router controller within the ingress router searches through a content addressable memory and a route cache associative memory to determine the routing information corresponding to the particular BOM cell. The routing information is placed within a setup ATM cell generated by the router controller and also placed in a VCI table in order to update all cells within a particular packet. A transmit agent transmits the setup cell, the BOM cell, and all remaining cells of a particular packet linked together by the ingress controller. The transmit agent can access the VCI table to ensure that all cells within the packet receive appropriate routing information. In this fashion, a determination of routing information for every ATM cell within a packet is not required.

Thus, it is apparent that there has been provided, in accordance with the present invention, a method and apparatus for route processing of asynchronous transfer mode cells that satisfy the advantages set forth above. Although the preferred embodiment has been described in detail, it should be understood that various changes, substitutions, and alterations can be made herein without departing from the spirit and scope of the present invention as defined by the following claims.

Reserved--There are two 1-octet fields, one in the header and one in the trailer of the L3.sub.-- PDU, that are reserved. These fields are populated with zeros by both CPE and the SS.

BEtag--There are two 1-octet fields, one in the header and one in the trailer of the L3.sub.-- PDU, that contain a beginning-end tag. These fields are populated with a binary encoded value ranging from 0 through 255. These two tags are used to form an association between the first and last segments of an L3.sub.-- PDU.

BAsize--This 2-octet field gives the length, in octets, of the portion of the L3.sub.-- PDU that extends from the beginning of the Destination Address field up to and including the CRC32 field, if present.

Destination Address--This 8-octet field contains two subfields, Address-Type and Address.

The Address.sub.-- Type subfield occupies the 4 most significant bits of the field. The Address.sub.-- Type contains the value 1100 when using an individual 60-bit address and the value 1110 for a 60-bit group address. All other values are not recognized by the SS..sup.1

The 60-bit Address subfield contains the SMDS address for which the L3.sub.-- PDU is intended. For initial availability of SMDS, the address uses 10 digits, following a prefix of "1." The four most significant bits of the Address subfield are populated with the prefix value 0001..sup.2 The 40 bits which follow these four most significant bits contain the BCD encoded values of the 10 digits. The remaining 16 least significant bits are populated with 1s. Future addresses used for SMDS may require all 60 bits of this field, for example, for international addressing.

Source Address--This 8-octet field also has two subfields, Address-Type and Address. The Address-Type subfield occupies the 4 most significant bits of the field. The Address.sub.-- Type contains the value 1100 for an individual 60-bit address. All other values are not recognized by the SS. The Address subfield has the same format as the Address subfield in the Destination Address field.

Higher Layer Protocol Identifier (HLPI)--This 6-bit field is present to ensure alignment of the SIP format with the DQDB protocol format.

PAD Length (PL)--This 2-bit field indicates the number of octets in the PAD field to make the entire L3.sub.-- PDU 32-bit aligned. The PAD Length may be found from the expression:

PAD Length=3--((number of Information octets+3)(mod4))

Quality of Service (QOS)--This 4-bit field is present to ensure alignment of the SIP format with the DQDB protocol format.

CRC32 Indication Bit (CIB)--This one-bit field indicates the presence or absence of the CRC32 field. If the CRC32 has been generated and is present, this bit is set to 1. Otherwise, this bit is set to 0.

Header Extension Length (HEL)--This 3-bit field indicates the number of 32-bit words in the Header Extension field, and is populated with the value 011 by both CPE and the SS..sup.3

Bridging--This 2-octet field is present to ensure alignment of the SIP format with the DQDB protocol format.

Header Extension (HE)--This is a 12-octet field. Octets not used for Header Extension elements as defined below are filled with extra octets, HE PAD, such that the overall Header Extension field is 12-octets.

Element Length--This one-octet field contains the combined lengths of the Element Length, Element Type, and Element Value fields specified in octets for the element.

Element Type--This one-octet field contains a binary encoded value which indicates the type of information found in the Element Value field. Section 4.2.1.1.1 specifies Element Types and formats.

Element Value--The content of this variable-length field depends upon the Element Type and its intended function.

HE PAD--This field can range from 0-9 octets in length. It is sized to make the overall Header Extension field 12 octets. If the HE PAD is present (greater than zero octets in length) it shall follow all Header Extension elements and begins with at least one octet of all zeros.

Information--This is a variable-length field that contains the user's information (or Level 3 SDU) and can be up to 9188 octets in length.

Payload--This field can range from 0 to 3 octets in length and contains zeros. It is sized to make the entire L3.sub.-- PDU 32-bit aligned for each of processing, as indicated by the PAD Length field.

Payload CRC32--This 4-octet field may be present or absent, as indicated by the CRC32 Indication Bit. The CRC32 performs error detection for the L3.sub.-- PDU fields from the Destination Address through the CRC32. If the CRC32 is generated by the CPE, it is performed according to Section 6.5.1.6 of the IEEE 802-6 Standard.sup.(1). The SS delivers unchanged the value placed in the CRC32 field by the user, if any.

Length--This 2-octet field contains the same length as that found in the BAsize field.