Multi-service segmentation and reassembly device with a single data path that handles both cell and packet traffic Number:7,142,564 from the United States Patent and Trademark Office (PTO) owispatent A multi-service segmentation and reassembly (MS-SAR) integrated circuit is disposed on a line card in a router or switch. The MS-SAR can operate in an ingress mode so that it receives packet and/or cell format data and forwards that data to either a packet-based or a cell-based switch fabric. The MS-SAR can also operate in an egress mode so that it receives data from either a packet-based or a cell-based switch fabric and outputs that data in packet and/or cell format. The MS-SAR has a data path through which many flows of different traffic types are processed simultaneously. Each flow is processed by functional blocks along the data path in accordance with one of several application types, the application type for a flow being predetermined by the host processor of the router or switch. Segmentation, reassembly and partitioning techniques are disclosed that reduce costs and facilitate high-speed operation.<H segmentation, reassembly, Multi, service, s, 7142564.html, Patent, pto, 7142564

Title: Multi-service segmentation and reassembly device with a single data path that handles both cell and packet traffic

Abstract: A multi-service segmentation and reassembly (MS-SAR) integrated circuit is disposed on a line card in a router or switch. The MS-SAR can operate in an ingress mode so that it receives packet and/or cell format data and forwards that data to either a packet-based or a cell-based switch fabric. The MS-SAR can also operate in an egress mode so that it receives data from either a packet-based or a cell-based switch fabric and outputs that data in packet and/or cell format. The MS-SAR has a data path through which many flows of different traffic types are processed simultaneously. Each flow is processed by functional blocks along the data path in accordance with one of several application types, the application type for a flow being predetermined by the host processor of the router or switch. Segmentation, reassembly and partitioning techniques are disclosed that reduce costs and facilitate high-speed operation.

Patent Number: 7,142,564 Issued on 11/28/2006 to Parruck, et al.

Inventors: Parruck; Bidyut (Cupertino, CA), Ramakrishnan; Chulanur (Saratoga, CA)
Assignee: Cortina Systems, Inc. (Mountain View, CA)

Appl. No.: 09/976,522

Filed: October 12, 2001

Current U.S. Class: 370/474 ; 370/476

Current International Class: H04L 12/54 (20060101)

Field of Search: 370/395.5,395.51,395.52,400,401,474,476,469,360,386,389,465,466

References Cited [Referenced By]

U.S. Patent Documents


5666353	September 1997	Klausmeier et al.
5715250	February 1998	Watanabe
5742765	April 1998	Wong et al.
5764645	June 1998	Bernet et al.
5781549	July 1998	Dai
5787255	July 1998	Parlan et al.
5796736	August 1998	Suzuki
5802052	September 1998	Venkataraman
5802287	September 1998	Rostoker et al.
5809021	September 1998	Diaz et al.
5838915	November 1998	Klausmeier et al.
5859835	January 1999	Varma et al.
5867480	February 1999	Thomas et al.
5870394	February 1999	Oprea
5898688	April 1999	Norton et al.
5905725	May 1999	Sindhu et al.
5917820	June 1999	Rekhter
5917828	June 1999	Thompson
5920705	July 1999	Lyon et al.
5946313	August 1999	Allan et al.
5963541	October 1999	Koga et al.
5987034	November 1999	Simon et al.
6026086	February 2000	Lancelot et al.
6034945	March 2000	Hughes et al.
6052379	April 2000	Iverson et al.
6088355	July 2000	Mills et al.
6091725	July 2000	Cheriton et al.
6101188	August 2000	Sekine et al.
6111877	August 2000	Wilford et al.
6115373	September 2000	Lea
6134217	October 2000	Stiliadis et al.
6144662	November 2000	Colmant et al.
6147999	November 2000	Honda et al.
6154446	November 2000	Kadambi et al.
6157641	December 2000	Wilford
6160793	December 2000	Ghani et al.
6167027	December 2000	Aubert et al.
6169739	January 2001	Isoyama
6175570	January 2001	Cukier et al.
6185212	February 2001	Sakamoto et al.
6188671	February 2001	Chase et al.
6259699	July 2001	Opalka et al.
6330239	December 2001	Suzuki
6424662	July 2002	Miki et al.
6463063	October 2002	Bianchini et al.
6522667	February 2003	Oda et al.
6535513	March 2003	Kao et al.
6553030	April 2003	Ku et al.
6611522	August 2003	Zheng et al.
6615358	September 2003	Dowd et al.
6631128	October 2003	Lemieux
6680933	January 2004	Cheesman et al.
6741585	May 2004	Monoz et al.
6751224	June 2004	Parruck et al.
6795445	September 2004	Kabie et al.
6826196	November 2004	Lawrence
6963572	November 2005	Carr et al.
2002/0101263	August 2002	Endo
2002/0101871	August 2002	Takase et al.
2003/0128688	July 2003	Kim
2004/0015590	January 2004	Nagami et al.
2004/0028067	February 2004	Chong et al.

Foreign Patent Documents


WO 97/43869	Nov., 1997	WO
WO 99/17182	Apr., 1999	WO
WO 00/56012	Sep., 2000	WO

Other References

US. Appl. No. 09/528,802, filed Mar. 20, 2000, "Circuits for Combining ATM and Packet Data on an Optical Fiber and Methods Therefor," by Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,479, filed Mar. 30, 2000, "Devices for Aggregating ATM Cells and Packets for Transmission Over the Same Channel," by Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,306, filed Mar. 30, 2000, "Devices for Employing SONET Frames for Transporting both ATM Cells and Packets Over in the Same Channel in an Optical Fiber," by Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,478, filed Mar. 30, 2000, "Methods and Apparatus for Dynamically Allocating Bandwidth Between ATM Cells and Packets," by Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,461, filed Mar. 30, 2000, "Routers for Switching ATM Cells in a Packet-like manner Using a Packet Switch," by Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,476, filed Mar. 30, 2000, "Processor-based Architecture for Facilitating Integrated Data Transfer between both ATM and Packet Traffic with a Packet Bus or Packet Link, Including Bidirectional ATM-to-Packet Functionality for ATM Traffic," Parruck, Nguyen, Ramakrishnan. cited by other .
U.S. Appl. No. 09/539,477, filed Mar. 30, 2000, "Integrated ATM/Packet Segmentation-and-Reassembly Engine for Handling both Packet and ATM Input Data and for Outputting both ATM and Packet Data," by Parruck, Nguyen, Ramakrishnan. cited by other .
"Is the Bloom Off Jasmine" and other pages from `Light READING` web site "www.lightreading.com", 2 pages (printed Mar. 26, 2001). cited by other .
Chapter 3, Frame Relay Architecture, from "Frame Relay Technology and Practice" textbook, by Jeff T. Buckwalter, (copyright 2000). cited by oth- er .
Chapter 5, MPLS Core Protocols, from "MPLS Technology and Applications" textbook, by Bruce Davie and Yakov Rekhter, (copyright 2000). cited by other .
"GenFlow Family of Traffic Management Co-Processors" and other pages from Acorn Networks' web site "www.Acorn-Networks.com", 5 pages (printed Mar. 30, 2001). cited by other .
White Paper entitled "Wire-Speed Traffic Management Solutions Based On Coprocessors", by Joe Adler and Tam-Anh Chu, Acorn Networks, 14 pages (copyright 2000). cited by other .
S19202 Advanced Summary Datasheet for "Ganges STS-192 POS/ATM Sonet/SDH Mapper", Applied Micro Circuits Corporation, revision 1.6, 2 pages (Jun. 2000). cited by other .
"Product Guide--Ganges (S19202)" and other pages from Applied Micro Circuits Corporation's web site, 3 pages (printed Feb. 27, 2001). cited by other .
"ZettaCom--Powering Tomorrow's Network", pages from ZettaCom's web site "www.zetta.com/products", 2 pages (downloaded Jan. 31, 2001). cited by other .
Ocular Networks' Metro Business Access Architecture, pages from Ocular Networks' web site "www.ocularnetworks.com/architecture", two pages (downloaded Jan. 31, 2001). cited by other.

Primary Examiner: Vu; Huy D.
Assistant Examiner: Duong; Duc

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit under 35 U.S.C. .sctn. 120 of U.S. patent application Ser. No. 09/851,565, filed May 8, 2001, and is a divisional thereof. This application also claims the benefit under 35 U.S.C. .sctn. 120 of U.S. patent application Ser. No. 09/823,667, filed Mar. 30, 2001, of which U.S. patent application Ser. No. 09/851,565 is a continuation-in-part. This application also claims the benefit under 35 U.S.C. .sctn. 120 of U.S. application Ser. No. 09/779,381, filed Feb. 7, 2001 of which U.S. patent application Ser. No. 09/851,565 is also a continuation-in-part.

Claims

What is claimed is:

1. A multi-service segmentation and reassembly (MS-SAR) integrated circuit, comprising: a first bus interface; lookup circuitry; segmentation circuitry; reassembly circuitry; a second bus interface; and a data path extending from the first bus interface to the lookup circuitry, and from the lookup circuitry to the segmentation circuitry, and from the segmentation circuitry to the reassembly circuitry, and from the reassembly circuitry to the second bus interface, wherein both cell-protocol traffic and packet-protocol traffic pass over the data path from the first bus interface, through the lookup circuitry, through the segmentation circuitry, through the reassembly circuitry and out of the integrated circuit from the second bus interface, the lookup circuitry analzying the cell-protocol traffic and outputting information that causes the cell-protocol traffic to be processed in a first way by the segmentation circuitry and the reassembly circuitry, the lookup circuitry analyzing the packet-protocol traffic and outputting information that causes the packet-protocol traffic to be processed in a second way by the segmentation circuitry and the reassembly circuitry.

2. The integrated circuit of claim 1, wherein the integrated circuit is operable in a first ingress mode such that traffic is output from the integrated circuit to a cell-based switch fabric via the second bus interface, and wherein the integrated circuit is operable in a second ingress mode such that traffic is output from the integrated circuit to a packet-based switch fabric via the second bus interface.

3. The integrated circuit of claim 1, wherein the integrated circuit is operable in a first egress mode such that traffic is received onto the integrated circuit from a cell-based switch fabric via the first bus interface, and wherein the integrated circuit is operable in a second egress mode such that traffic is received onto the integrated circuit from a packet-based switch fabric via the first bus interface.

4. The integrated circuit of claim 1, wherein the cell-protocol traffic is ATM traffic, and wherein the packet-protocol traffic is MPLS traffic.

5. The integrated circuit of claim 1, further comprising: memory manager circuitry, wherein the data path extends from the segmentation circuitry to the reassembly circuitry via the memory manager circuitry.

6. The integrated circuit of claim 1, wherein the cell-protocol traffic involves an ATM cell, and wherein the packet-protocol traffic involves a packet, the ATM cell being temporarily stored in one of a plurality of buffers of a memory, all of the buffers being of equal size, the packet being segmented into a plurality of chunks, and each of the chunks being temporarily stored into a corresponding one of the buffers.

Description

TECHNICAL FIELD

This invention relates to multi-service network communications, such as, for example, line card circuitry disposed within routers and switches.

BACKGROUND INFORMATION

FIG. 1 (Prior Art) is a diagram of a part of the Internet 1. The Internet, loosely defined, is a collection of networks that are interconnected by devices called "routers". In the illustration, the Internet 1 involves seven networks N1 N7 and five routers R1 R5. A protocol called the Internet Protocol (IP) is used to communicate a message from a source device (a node) on one network to a destination device (a node) on another network. The message is broken up into pieces and each of these pieces is packaged into what is called an "IP packet". These packets may be of varying lengths. The IP packets of the message are then sent from the source to the destination from one network to the next via the routers. The various IP packets can take different paths to get from the source to the destination. When all the IP packets arrive at the destination, they are reassembled to recreate the original message.

This high level IP message can be transported across an individual network using any one of many lower level protocols. Some of the protocols are packet-based protocols, whereas others of the protocols are cell-based protocols. One packet-based protocol used to transport IP is called Multi-Protocol Label Switching (MPLS). In MPLS, each packet is encapsulated with an MPLS label by the first MPLS device it encounters as it enters an MPLS network. The MPLS device is called an MPLS edge router. The MPLS edge router analyses the contents of the IP header and selects an appropriate MPLS label with which to encapsulate the packet. MPLS packets therefore have varying lengths in the same way that IP packets do. At all the nodes within the network subsequent to the edge router, the MPLS label (and not the IP header) is used to make the forwarding decisions for the packet. Paths through particular nodes in the network are setup from edge to edge, the label defining the particular path its packet will take. Finally, as an MPLS labeled packet leaves the network via an edge router, the edge router removes the MPLS label.

One cell-based lower level protocol used to transport IP over a network is the Asynchronous Transfer Mode (ATM) protocol. In ATM, all packets are of equal length. They are therefore called "cells". A large IP packet is transported over an ATM network by segmenting the large IP packet into a plurality of smaller pieces. Each of the smaller pieces is packaged to become an ATM cell. The ATM cells are then transported across the ATM network. When the ATM cells reach the edge of the ATM network, their payloads are reassembled to reform the large IP packet. In FIG. 1, networks N1, N5 and N3 are cell-based ATM networks. Networks N2, N6, N4 and N7 are packet-based MPLS networks.

In the example of FIG. 1, networks N3 and N4 are OC-192 high-speed networks adapted to carry traffic over long distances. Router R2 at one end of network N3 may, for example, be located in San Francisco whereas router R4 at the other end of network N3 may be located in New York. Such high-speed long distance networks are often called the "backbone" of the Internet.

In the example of FIG. 1, individual users U1 U10 are coupled to the Internet via local area networks. Networks N1, N2 and N7 are local area networks. In one example where the network is a corporate network serving an office building, the users are corporate employees in a building. In an example where the network is a network operated by an Internet Service Provider (ISP), the users are individual customers that pay the ISP to gain access to the Internet.

Consider the situation where users on networks N1 and N2 issue IP messages that are destined to go to destinations to the right side of the backbone such that the messages should go through one of the two back bone networks N3 and N4. In such a case, the IP traffic from networks N1 and N2 is aggregated and supplied to the router access point on the appropriate backbone network. A portion of the Internet called the "Metropolitan Area" performs this function. In the illustration, the metro area includes a router R1 used for aggregating traffic from networks N1 and N2, and for routing that information to the appropriate one of backbone networks N3 and N4.

FIG. 2 (Prior Art) is a more detailed view of router R1. Router R1 includes line cards 2 3 for interfacing to ATM networks, other line cards 4 and 5 for interfacing to MPLS networks, and a switch fabric 11. ATM line card 3 is coupled to ATM network NS such that router R1 can communicate with backbone network N3 via network N5. Similarly, MPLS line card 5 is coupled to MPLS network N6 such that router R1 can communicate with backbone network N4 via network N6. ATM line card 2 is coupled to ATM network N1 via OC-12 fiber optic link 6, SONET multiplexer 7, higher speed OC-48 fiber optic link 8, and SONET multiplexer 9. MPLS line card 4 is coupled to MPLS network N2 via OC-12 fiber optic link 10, SONET multiplexer 7, higher speed OC-48 fiber optic link 8, and SONET multiplexer 9. SONET multiplexer 7 performs time division multiplexing (TDM) to modulate both ATM traffic from network N1 as well as packet MPLS traffic from network N2 onto the same wavelength channel transmitted over the same fiber optic link 8. SONET multiplexer 9 performs the inverse function of time demultiplexing the signal on fiber optic link 8 to extract and separate the ATM traffic from the MPLS traffic.

Router R1, when it receives an IP message from one of networks N1 or N2, determines whether to forward the message on the message's "next hop" to router R2 or R3. In this way IP network information from the users is aggregated in the metro area and is directed to the correct backbone network for communication across long distances to the destination.

A problem may exist if one of the local area networks coupled to router R1 is disconnected or if the type of traffic on that network is changed from MPLS packet traffic to ATM cell traffic or visa versa. Consider the situation in which ATM network N1 ceases business operations. In that case, the operator of router R1 will likely want to disconnect network N1 from its SONET multiplexer 7 and to couple in the network of another paying customer. For example, the operator may want to disconnect ATM network N1 and to connect in its place MPLS network N7. If this is done, however, MPLS traffic would be received on ATM line card 2. ATM line card 2 is not suitable for coupling to an MPLS network. Consequently, ATM line card 2 may have to be disconnected and a suitable MPLS line card substituted in its place. With the expansion of the Internet and with advances in IP switching technology, it appears that the proportion of packet networks to ATM networks is increasing. Accordingly, as more and more of the networks coupled to a router such as router R1 migrate from one type of traffic to the other, more and more of the line cards of the router will have to replaced. This is undesirable. A solution is desired whereby a smooth and easy migration from one type of traffic to the next is possible without the removal of line cards or the physical manipulation of the router.

FIG. 3 is a diagram of one possible approach to the problem involving a line card 12 that handles both ATM and packet traffic. Line card 12 is coupled to a switch fabric of a router by interface 13. Cell and packet traffic received from fiber optic cable 14 and transmitted on fiber optic cable 15 are time division multiplexed/demultiplexed by TDM device 16. Cell traffic is handled by integrated circuit device 17. Packet traffic is handled by integrated circuit device 18. As the relative amounts of cell traffic to packet traffic change, the same line card can be used.

SUMMARY

Although the line card set forth in FIG. 3 is satisfactory for some applications, the general approach of FIG. 3 involves substantial cost. The non-recurring engineering costs associated with developing an integrated circuit can be quite high. Even though the development of a particular integrated circuit may make technical sense for a given application, it may be economically unreasonable to do so where production volumes of the integrated circuit would be low. For each line card of FIG. 3, there is one integrated circuit for handling ATM traffic and one integrated circuit for handling packet traffic. Developing a single integrated circuit having the functionality of both the ATM device and the packet device might involve less non-recurring engineering costs than developing two different integrated circuits, but the integration would likely result in an undesirably large integrated circuit. Parts of such a single integrated circuit may see little use in certain circumstances. Consider the situation in which the mix of ATM traffic to packet traffic shifts to where there is little or no ATM traffic. The single integrated circuit would involve a data path and associated circuitry for handling ATM traffic that is underutilized or is not used at all. Providing this extra unnecessary circuitry on the single integrated circuit would constitute an unnecessary expense. It would therefore make the line card solution afforded by the single integrated circuit unnecessarily expensive. It would be preferable to get more use out of the circuitry provided on the integrated circuit in order to reduce costs.

Not only might some circuitry be underutilized, but also so might other circuitry become overburdened. In the above situation, for example, more and more processing responsibilities would be required of the packet handling circuitry. If the processing capability of the packet handling circuitry is sized to accommodate a particular load, then increasing the load beyond that load by more and more of the traffic shifting to packet traffic may result in the line card being inadequate to handle the required traffic.

In one novel aspect, the same circuitry on a single Multi-Service Segmentation And Reassembly (MS-SAR) integrated circuit handles both cell traffic and packet traffic. Rather than there being a first data path through the integrated circuit for cell processing, and another data path through the integrated circuit for packet processing, functional blocks along a single data path process cell and/or packet information that passes through the integrated circuit though the single data path. Individual flows passing through the single data path are processed in accordance with the traffic type of the individual flow. Any mix of cell to packet traffic can be accommodated, thereby enabling a smooth migration from one traffic type to another. The MS-SAR can handle dynamic changes in the relative amounts of cell and packet traffic. Production costs associated with the integrated circuit are reduced because the same functional blocks are used, albeit in different ways, to process different types of flows.

In another novel aspect, production volumes may be increased in order to realize economies of scale and to reduce per part cost. To allow production volumes to be increased, the very same MS-SAR integrated circuit is usable not only both as an ingress device and an egress device, but also with either a packet-based switch fabric or a cell-based switch fabric. By providing a single MS-SAR integrated circuit that functions as either an ingress device or an egress device as compared to a device that can function as just one or the other, the number of applications for the MS-SAR integrated circuit is increased. By providing a single MS-SAR integrated circuit that can work with either a packet-based switch fabric or a cell-based switch fabric, the number of applications for the single MS-SAR integrated circuit is increased as compared to the same device that could only function with one type of switch fabric.

In another novel aspect, a single MS-SAR integrated circuit involves a lookup block, a segmentation block, and a reassembly block, wherein traffic flows through a single data path through the lookup block, and then through the segmentation block, and then through the reassembly block. By using two identical such MS-SAR devices, one in an ingress mode and another in an egress mode, information received onto the ingress MS-SAR in either ATM or packet format can be communicated through either a packet-based or a cell-based switch fabric, and can be output from the egress MS-SAR in either ATM or packet format. Information communicated in AAL5 adaptation cells received onto the ingress MS-SAR can be reassembled and output in packet format on the egress MS-SAR. Packet format information received onto the ingress MS-SAR Can be segmented and output in the form of AAL5 adaptation cells from the egress MS-SAR. The versatility of the single MS-SAR to handle many different traffic types using the same circuitry further increases the number of applications for which the integrated circuit can be used.

In another novel aspect, individual flows are processed in different ways by an egress MS-SAR. An indication of the type of egress processing to be done by an MS-SAR on a flow is embedded into the flow that is received from a switch fabric onto the egress MS-SAR. The egress MS-SAR reads the embedded indication and performs the type of egress processing indicated. In one embodiment, the indication of the type of egress processing is contained in a switch header (the switch header can be either a switch header for a cell-based switch fabric or for a packet-based switch fabric), the switch header being added by a first MS-SAR functioning in an ingress mode, the first MS-SAR and the second MS-SAR being substantially identical integrated circuits. In one embodiment, information on how to locate the indication of the type in the information coming into the egress MS-SAR is provided to the egress MS-SAR for each logical input port of the egress MS-SAR. The egress MS-SAR uses: 1) the input port number of the flow, and 2) the information on how to locate the indication for a given input port, to locate the indication in the information coming in from the switch fabric.

In accordance with known ATM adaptation layer protocols, packet data can be transmitted over an ATM network by segmenting the packet into smaller pieces and then transmitting each smaller piece over the ATM network in the form of an ATM cell. After transmission across the ATM network, the data payloads of the individual ATM cells are recovered and are reassembled into the original packet. This segmentation and reassembly process has been traditionally performed on a line card by reassembling packets as the individual ATM cells are received onto the line card. A reassembly context is maintained for each packet being reassembled. This reassembly context may, for example, include a composite cyclic redundancy check (CRC) value that is modified as each ATM cell carrying a portion of the packet is received and processed. The CRC value calculated on the data portions received is checked against a CRC transmitted in a trailer of the last ATM cell to verify that the data carried by the numerous ATM cells has not been corrupted in the segmentation and reassembly process. Once a packet has been checked and reassembled, is it buffered into a payload memory on the line card. If, for example, the line card were to support the simultaneous reassembly of one million packets, then the line card would have to be able to store one million reassembly contexts. This would involve a large amount of memory.

In another novel aspect, packets to be reassembled on the line card in such an adaptation layer process are not reassembled before being buffered on the line card. Rather, the payloads of the individual cells are buffered in payload memory as cells. The line card does not maintain a reassembly context for each such packet being buffered. When the buffered packet information is to be output from the line card, the cell payloads corresponding to the packet are read out of payload memory and the cell payloads are reassembled to form the packet. In this way, a large number of packets being received onto the line card do not need to be simultaneously reassembled, but rather the number of packets being simultaneously reassembled can be set to have a smaller maximum. In one embodiment, one million flows to be reassembled can be received at one time onto a line card, but only one packet per active line card output port is reassembled at a time. By reducing the maximum number of packets being simultaneously reassembled, the maximum number of reassembly contexts to be stored on the line card is reduced. Reducing the number of reassembly contexts to be stored reduces the amount of memory necessary and thereby reduces line card costs.

Not only is a reassembly context involved the reassembly process, but a segmentation context is also traditionally involved in the segmentation process. Traditionally, packets to be segmented on a line card in accordance with an adaptation layer process are received and stored into payload memory as packets. When a packet is to be output, it is retrieved from payload memory and is segmented into segments such that each of the segments forms the data payload of an ATM cell. To be able to check the integrity of the data when the segments are reassembled, a CRC is calculated on the packet at the time of segmentation and is transmitted in a trailer that is included in the last ATM cell. For each such segmentation process that is going on at the same time, a segmentation context including a partial CRC value is maintained. If a large number such as a million simultaneous output flows is to be supported by the line card, then the large number of segmentation contexts must be stored on the line card. This involves a lot of memory and consequently increases line card cost.

In another novel aspect, packets to be segmented in accordance with an adaptation layer protocol are segmented on a per input port basis as they are received onto the line card and prior to being buffered on the line card. The packets are not buffered on the line card, but rather segments are buffered. Because only one segmentation is performed at a time for a given line card input port, the maximum number of simultaneous segmentations is limited to the number of input ports. By limiting the maximum number of simultaneous segmentations to be performed, the memory required to store the associated segmentation contexts is reduced. In one embodiment, one million simultaneous flows can be processed, but there are only sixty-four input ports. The amount of memory required for storing segmentation contexts is therefore significantly reduced.

In another novel aspect, an MS-SAR involves a data path such that data received onto the MS-SAR passes through the data path and to a memory manager that stores the data into payload memory. The data is then read out of the payload memory and passes through the remainder of the data path to be output from the MS-SAR. How and when the data is read out of payload memory is controlled by control circuitry. The control circuitry controls the memory manager so that the memory manager retrieves data from payload memory so that it will be output from the MS-SAR in a manner controlled by the control circuitry. In one novel aspect, the MS-SAR is partitioned into two integrated circuits such that the data path circuitry is disposed on one integrated circuit and such that the control circuitry is disposed on another integrated circuit. Partitioning the MS-SAR in this way facilitates future increasing of data throughput rates without redesigning the MS-SAR. To increase data throughput, for example from OC-192 rates to OC-768 rates, multiple data path integrated circuits are disposed in parallel, each of the data path integrated circuits being controlled by the same control integrated circuit. The control integrated circuit has multiple control interfaces, one such interface for coupling to and controlling each of the data path integrated circuits.

In another novel aspect, a router involves a first line card and a second line card. Each of the first and second line cards involves an MS-SAR operating in the ingress mode and an MS-SAR operating in the egress mode. The egress MS-SAR on the second line card can become endangered of being overloaded if, for example, the ingress MS-SAR on the first line card continues to send network information for a flow to the egress MS-SAR on the second line card, but the egress MS-SAR on the second line card is prevented from outputting that information, for example due to congestion at the framer. Consequently, more and more of the network information for the flow will end up having to be buffered by the egress MS-SAR of the second line card. In one novel aspect, the ingress and egress MS-SAR devices of the first line card are linked by a serial bus on the first line card, and the ingress and egress MS-SAR devices of the second line card are linked by a serial bus on the second line card. If the egress MS-SAR of the second line card is in danger of becoming overloaded, then the egress MS-SAR of the second line card sends an indication of this situation to the ingress MS-SAR of the second line card via the serial bus on the second line card. The ingress MS-SAR of the second line card relays that information to the first line card by outputting a special status switch cell. The special status switch cell is transported across the switch fabric to the egress MS-SAR of the first line card. The egress MS-SAR of the first line card detects the special status switch cell, and relays the indication of the situation to the ingress MS-SAR of the first line card via the serial bus on the first line card. In response to receiving this indication from the serial bus, the ingress MS-SAR on the first line card slows or stops outputting the information that is overburdening the egress MS-SAR on the second line card.

In another novel aspect, an integrated circuit includes a reassembly circuit, wherein in an ingress mode the reassembly circuit uses a flow ID to lookup a switch header in an memory, and wherein in an egress mode the reassembly circuit uses a flow ID to lookup a network protocol header (for example, ATM header or MPLS header) in the memory.

These are but some of the novel aspects. Other novel structures and methods are disclosed in the detailed description below. This summary does not purport to define the invention. The invention is defined by the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 (Prior Art) illustrates a part of the Internet where different traffic types are aggregated.

FIG. 2 (Prior Art) is a diagram of a router in the part of the Internet illustrated in FIG. 1.

FIG. 3 is a diagram illustrative of an approach to solving a problem associated with the network structure of FIG. 1. Although the line card as illustrated may and is intended to reflect a product designed by or being designed by Northern Telecom Ltd., adequate details about this line card are not available to the inventors or the assignee to state here in this patent document that what is shown in FIG. 3 is prior art.

FIG. 4 is a diagram of a switching device (in this case a router) in accordance with an embodiment of the present invention.

FIG. 5 is a diagram of a line card in the router of FIG. 4.

FIG. 6 is a diagram that sets forth various application types that the router of FIG. 4 (involving a pair of MS-SAR devices, one operating in an ingress mode, and the other operating in an egress mode) can carry out.

FIG. 7 is a diagram illustrating ingress and egress application types involving a cell-based switch fabric. These application types can be carried out by the router of FIG. 4.

FIG. 8 is a diagram illustrating ingress and egress application types involving a packet-based switch fabric. These application types can be carried out by the router of FIG. 4.

FIG. 9 is a diagram of an example in accordance with an embodiment of the present invention wherein a first flow is processed in accordance with ingress application type 3 and egress application type 11, and wherein a second flow is processed in accordance with ingress application type 0 and egress application type 8.

FIG. 10 is a diagram illustrating an MS-SAR and associated memories in accordance with an embodiment of the present invention.

FIG. 11 is a simplified representation of an MPLS packet of flow #1 in the example of FIG. 9.

FIG. 12 is a simplified diagram of chunks of flow #1 that are output by the incoming SPI-4 interface block in the example of FIG. 9.

FIG. 13 is a diagram that illustrates information flow into an ingress MS-SAR in the example of FIG. 9.

FIG. 14 is a representation of a port table in the lookup engine.

FIGS. 15A 15C are diagrams of the building of a per flow queue for flow #1 in the example of FIG. 9.

FIG. 16 is a diagram of a dequeue memory location (stores the header pointer) for one FID.

FIGS. 17 and 18 are diagrams of the first and second enqueue memory 32 locations (store the tail pointer) for one FID.

FIG. 19 is a diagram of a memory location (stores a pointer to a buffer in the body of a queue) for an intermediate BID in a linked list.

FIG. 20 is a diagram of an ATM cell of flow #2 in the example of FIG. 9.

FIG. 21 is a diagram of a 56-byte chunk of flow #2 as output from the incoming SPI-4 interface block of the ingress MS-SAR in the example of FIG. 9.

FIG. 22 is a diagram of a 64-byte chunk of flow #2 as output from the segmentation block of the ingress MS-SAR in the example of FIG. 9.

FIG. 23 is a diagram of a per flow queue for flow #2 of the example of FIG. 9.

FIG. 24 is a diagram of the port calendar in the reassembly block in the MS-SAR.

FIGS. 25 and 26 are diagrams of the port empty and port full registers in the reassembly block in the MS-SAR.

FIG. 27 is a diagram that illustrates information flow from payload memory out of the ingress MS-SAR in the example of FIG. 9.

FIG. 28 is a diagram that illustrates the three switch cells of flow #1 in the example of FIG. 9.

FIG. 29 is a diagram of the switch cell for flow #2.

FIG. 30 is a diagram that illustrates the general flow of information into egress MS-SAR 200 in the example of FIG. 9.

FIG. 31 is a diagram of the first switch cell for flow #1 in the example of FIG. 9.

FIG. 32 is a diagram that illustrates the general flow of information out of egress MS-SAR 200 in the example of FIG. 9.

FIG. 33 is a diagram that illustrates the format of one FID entry in the header table of the MS-SAR.

FIG. 34 illustrates three 64-byte chunks of flow #1 as the chunks pass from reassembly block 205 to outgoing SPI-4 interface block 206 in the example of FIG. 9.

FIG. 35 illustrates the MPLS packet of flow #1 as output from framer 142 in the example of FIG. 9.

FIG. 36 illustrates the ATM cell of flow #2 as output from reassembly block 205 in the example of FIG. 9.

FIG. 37 illustrates the ATM cell of flow #2 as output form outgoing SPI-4 interface block 206 of egress MS-SAR 200 in the example of FIG. 9.

FIG. 38 illustrates an example of application types 5, 6, 14 and 13.

FIG. 39 illustrates the processing of flow #1 in accordance with ingress application type 5 in the example of FIG. 38.

FIG. 40 illustrates the processing of flow #2 in accordance with ingress application type 6 in the example of FIG. 38.

FIG. 41 illustrates the processing of flow #1 in accordance with egress application type 14 in the example of FIG. 38.

FIG. 42 illustrates the processing of flow #2 in accordance with egress application type 13 in the example of FIG. 38.

FIG. 43 illustrates an example wherein a flow is processed on an ingress MS-SAR in accordance with ingress application type 1 and is processed on an egress MS-SAR in accordance with egress application type 9.

FIG. 44 illustrates an example wherein a flow is processed on an ingress MS-SAR in accordance with ingress application type 2 and is processed on an egress MS-SAR in accordance with egress application type 10.

FIG. 45 illustrates an example wherein a flow is processed on an ingress MS-SAR in accordance with ingress application type 4 and is processed on an egress MS-SAR in accordance with egress application type 14.

FIG. 46 illustrates an example wherein a flow is processed on an ingress MS-SAR in accordance with ingress application type 6 and is processed on an egress MS-SAR in accordance with egress application type 12.

FIG. 47 illustrates an example wherein a flow is processed on an ingress MS-SAR in accordance with ingress application type 6 and is processed on an egress MS-SAR in accordance with egress application type 14.

FIG. 48 is a diagram of an embodiment wherein MS-SAR functionality is partitioned into two integrated circuit chips (a data path integrated circuit and a control integrated circuit) such that multiple data path integrated circuits chips can be used with one control integrated circuit chip to increase data path throughput.

FIG. 49 is a diagram of a packet as it is output from the distribution integrated circuit of FIG. 48.

FIGS. 50 and 51 are diagrams that illustrate the building of a packet queue in connection with the operation of the embodiment of FIG. 48.

FIG. 52 is a diagram that illustrates a technique for accessing certain information stored in external memory in a reduced amount of time in connection with the embodiment of FIG. 48.

FIG. 53 is a diagram that illustrates a serial bus that couples an egress MS-SAR of a line card to an ingress MS-SAR of the same line card. The egress MS-SAR can use the serial bus to backpressure the sending ingress MS-SAR.

FIG. 54 is a block diagram on one particular embodiment of incoming SPI-4 interface block 201 of FIG. 10.

FIG. 55 is a diagram of input control block 801 of FIG. 54.

FIG. 56 is a diagram of output control block 803 of FIG. 54.

FIG. 57 is a block diagram of one particular embodiment of segmentation block 203 of FIG. 10.

FIG. 58 is a block diagram of one particular embodiment of memory manager block 204 of FIG. 10. FIGS. 58A and 58B together form a more detailed version of FIG. 58.

FIG. 59 is a block diagram of one particular embodiment of reassembly block 205 of FIG. 10. FIGS. 59A 59D together form a more detailed version of FIG. 59.

FIGS. 60A 60D are diagrams that illustrate reassembly types carried out by the reassembly block of FIG. 59. The function of the reassembly block in each of these reassembly types can be described at the functional level in Verilog, and hardware circuitry realized from the Verilog using hardware synthesis software.

FIG. 61 is a diagram of one particular embodiment of outgoing SPI-4 interface block 206 of FIG. 10. FIGS. 61A and 61B together form a more detailed version of FIG. 61.

FIG. 62 is a diagram of CPU interface block 211 of FIG. 10.

DETAILED DESCRIPTION

FIG. 4 is a simplified diagram of a router 100 in accordance with an embodiment of the present invention. Router 100 includes a plurality of line cards 101 104, a switch fabric 105 and a central processing unit (CPU) 106. The line cards 101 104 are coupled to switch fabric 105 by parallel buses 107 114. In the present example, each of parallel buses 107 114 is a 16-bit SPI-4, Phase II, LVDS parallel bus operating at 400 MHz at a double data rate (DDR). CPU 106 is coupled to line cards 101 104 by another parallel bus 131. In the present example, parallel bus 131 is a 32-bit PCI bus. In this example, each of the line cards can receive network communications in multiple formats. For example, line card 101 is coupled to a fiber optic cable 115 such that line card 101 can receive from cable 115 network communications at OC-192 rates in packets, ATM cells, and/or AAL5 cells. AAL5 cells are considered a type of ATM cell.

Line card 101 is also coupled to a fiber optic cable 116 such that line card 101 can output onto cable 116 network communications at OC-192 rates in packets, ATM cells, and/or AAL5 cells. The fiber optic cables 117 and 118 across which line card 103 communicates are also labeled in the diagram. All the line cards 101 104 in this example have substantially identical circuitry.

FIG. 5 is a more detailed diagram of representative line card 101. Line card 101 includes OC-192 optical transceiver modules 119 and 120, two serial-to-parallel devices (SERDES) 121 and 122, a framer integrated circuit 123, a IP classification engine 124, two multi-service segmentation and reassembly devices (MS-SAR devices) 125 and 126, static random access memories (SRAMs) 127 and 128, and dynamic random access memories (DRAMs) 129 and 130. MS-SAR devices 125 and 126 are identical integrated circuit devices, one of which (MS-SAR 125) is configured to be in an "ingress mode", the other of which (MS-SAR 126) is configured to be in an "egress mode". Each MS-SAR device includes a mode register that is written to by CPU 106 via bus 131. When router 100 is configured, CPU 106 writes to the mode register in each of the MS-SAR devices on each of the line cards so as to configure the MS-SAR devices of the line cards appropriately.

Router and Line Card:

Fiber optic cable 115 of FIG. 4 can carry information modulated onto one or more of many different wavelengths (sometimes called "colors"). Each wavelength can be thought of as constituting a different communication channel for the flow of information. Accordingly, optics module 119 converts optical signals modulated onto one of these wavelengths into analog electrical signals. Optics module 119 outputs the analog electrical signals in serial fashion onto a high-speed analog bus 132. Serdes 121 receives this serial information and outputs it in parallel form to framer 123 via high-speed parallel bus 133. Framer 123 receives the information from bus 133, frames it, and outputs it to classification engine 124 via another SPI-4 bus 134. Classification engine 124 performs IP classification and outputs the information to the ingress MS-SAR 125 via another SPI-4 bus 135. The ingress MS-SAR 125 processes the network information in various novel ways (explained below), and outputs the network information to switch fabric 105 (see FIG. 4) via SPI-4 bus 107. All the SPI-4 buses of FIGS. 4 and 5 are separate SPI-4, phase II, 400 MHz DDR buses having sixteen bit wide data buses.

Switch fabric 105, once it receives the network information, supplies that information to one of the line cards of router 100. Each of the line cards is identified by a "virtual output port" number. Router 100 can include up to 256 line cards. Accordingly, the virtual output port number has a range of from 0 to 255.

In the example of FIG. 4, switch fabric 105 may supply network information received on fiber optic cable 115 to any one of fiber optic cables 116, 118, 136 or 137. It is one of the primary functions of router 100 to determine, based on the certain information such as the intended destination of the network information, how to route the information. In the case where the network information is in the IP packet format, the router makes its decision on where to route the network information based on an intended IP destination address present in the IP header of each packet. In the case where the network information is in the ATM cell format, the router makes its decision on where to route the network information based on a virtual path identifier and virtual channel identifier (VPI/VCI) information in the ATM header of each ATM cell.

If, for example, the network info