Flexible network processor scheduler and data flow

CROSS-REFERENCE TO RELATED APPLICATION

This application is a continuation of U.S. application Ser. No. 11/133,477, filed May 18, 2005.

FIELD OF THE INVENTION

The present invention generally relates to network processor structures and to communications on a network by a network processor and, more particularly, to novel data path and network processor interface structures that enable novel flexible data movement and scheduling capabilities.

BACKGROUND OF THE INVENTION

This invention relates to communication network apparatus such as is used to link together information handling systems or computers of various types and capabilities and to components of such apparatus. In particular, this invention relates to scalable network processor apparatus and components useful in assembling such apparatus. The description which follows presupposes knowledge of network data communications and switches and routers as used in such communications networks. For assistance in understanding the inventions here described, the following prior disclosure is relevant to the description which follows and is hereby incorporated by reference into this description as fully as if here repeated in full: U.S. Pat. No. 6,404,752 to Allen, Jr., et al., issued Jun. 11, 2002 for “Network Switch Using Network Processor and Methods.”

Typical prior art network processor data flow structures, such as those described in U.S. Pat. No. 6,404,752 incorporated above, include “fixed function placement” structural implementations that are necessarily limiting to overall system functionality and capacity. More specifically, the design of the prior art system structure can generally function in only one predefined frame processing mode. For example, a dataflow structure designed with a “store and dispatch” mode (wherein a packet header must be copied and dispatched for packet processing) is generally desirable for network processor systems that anticipate large accumulations of data in input queue structures.

However, this type of frame processing mode is not optimal where input queues have limited growth potential. A dataflow chip using a “cut and paste” frame processing mode (wherein a frame header may be forwarded immediately to a processing unit while the body of a frame is received in a data store component, and after processing the modified header reconnected to the body in data store) would be more appropriate in this case. Furthermore, for deep packet processing system requirements, a “full dispatch” frame processing mode, also known as “pipelined frame processing” (wherein a full frame is forwarded immediately to a processing unit without being received in data store, and after processing the full modified frame is written in data store) is preferred to optimize data store bandwidth.

And where a “scheduler” structure is provided, the dataflow chip designer must choose either to provide an on-chip internal scheduler structure, which must then accordingly be limited to providing simple scheduling functions, or provide for a port connection to a separate external dedicated hardware structure or an external scheduling software interface when more robust and complex scheduling functions are required or anticipated. Specifically, an embedded ingress scheduler has inherently fixed functionality and limited capacity in terms of data flow quantities. Although simple scheduling functions may be accomplished in prior art network processor devices with embedded hardware or software schedulers, complex scheduling functions typically require connection and interface to an external hardware scheduler structure. And where “scheduler” functions are instead accomplished through software environments, additional processor cycles are required to perform the scheduling functions, resulting in reduced efficiency and system speed.

Therefore, prior dataflow structures do not afford flexibility to the end-user with regard to frame processing modes or scheduler requirements; the resultant dataflow structure is only appropriate for one type of frame processing mode, and/or one type of scheduler structure and, accordingly, system design flexibility or multiple possibilities are greatly reduced or even absent with respect to prior art dataflow structures.

Prior art network processor dataflow structures also typically require limited designated predefined interface structures such as SPI4.2 links, NPF SI switches and NPF LA1 coprocessor interfaces. Accordingly, the number of system configurations possible for any given dataflow structure is constrained by the limited flexibility of its interface structures. Direct connection to external coprocessors, and segmentation and reassembly are typically not supported, and software has limited access to data and data structures.

The aforementioned prior art systems cannot adequately meet the increased demands arising for network processing systems, such as 10 GB per second and higher media speed performance requirements combined with software flexibility. What is needed is a network processor system and method that provides for flexible and multiple alternative frame processing modes to enable efficient data processing, full complex scheduling functions without requiring external components, and superior data transmission capabilities including direct data transmission from external coprocessors, segmentation and data transmission driven by software, and direct access by software to data and data structures, as demanded and required by end-use system requirements. What is also desired is the ability for a dataflow structure to selectively meet multiple frame processing, scheduling and interface requirements as determined and selected by an end-user.

SUMMARY OF THE INVENTION

A network processor dataflow chip and method for flexible dataflow are provided. The dataflow chip comprises a plurality of on-chip data transmission and scheduling circuit structures. The data transmission and scheduling circuit structures are selected responsive to indicators. Data transmission circuit structures may comprise selectable frame processing and data transmission functions. Selectable frame processing may comprise cut and paste, full dispatch and store and dispatch frame processing. Scheduling functions include full internal scheduling, calendar scheduling in communication with an external scheduler, and external calendar scheduling. In another aspect of the present invention, data transmission functions may comprise low latency and normal latency external processor interfaces for selectively providing privileged access to dataflow chip resources.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> is a plan diagrammatic view of a dataflow chip structure according to the present invention.

<figref idref="DRAWINGS">FIG. 2</figref> is the dataflow chip structure illustrated in <figref idref="DRAWINGS">FIG. 1</figref> with additional informational indicators.

<figref idref="DRAWINGS">FIG. 3</figref> is the dataflow chip structure illustrated in <figref idref="DRAWINGS">FIG. 1</figref> with additional informational indicators.

<figref idref="DRAWINGS">FIG. 4</figref> is the dataflow chip structure illustrated in <figref idref="DRAWINGS">FIG. 1</figref> with additional informational indicators.

<figref idref="DRAWINGS">FIG. 5</figref> is a detailed view of some of the components of the dataflow chip structure illustrated in <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 6</figref> is the dataflow chip structure illustrated in <figref idref="DRAWINGS">FIG. 1</figref> with additional informational indicators.

DESCRIPTION OF EMBODIMENTS OF THE INVENTION

The present invention provides for new and novel structures defined in data path and interface areas of network processor structures that supply flexible data movement and scheduling capabilities. Scheduling flexibility is accomplished through the provision of several elementary scheduling functions. Data movement flexibility is accomplished through novel structures, such as a “second port” that enables connection to external media or coprocessor structures.

Referring now to <figref idref="DRAWINGS">FIG. 1</figref>, a dataflow chip (DF) <b>100</b> and embedded processor chip (EPC) <b>101</b> structure according to the present invention are illustrated. As is well known in the art, the dataflow chip <b>100</b> and embedded processor chip <b>101</b> are component parts of a larger network processor logical structure and architecture. Also as is well known in the art, dataflow chips are designed to move data through the system, receiving data packets from a network line or switch in transmitting those data packets to another network line or switch. The dataflow chip also typically interfaces with an external memory structure which holds the data packets in a queue structure before they can be transmitted. When the packets are transmitted, the dataflow chip structure reads the packets from the memory structure and sends the packets to the outgoing link

Configurable Frame Processing Modes

What is new in the present invention is the “configurable frame processing mode” functionality provided by the dataflow chip <b>100</b>. In the present embodiment, three separate frame processing modes are enabled by the same dataflow chip <b>100</b>: (a) cut and paste, (b) full dispatch, and (c) store and dispatch modes. Thus, an end-user may select which of these three frame processing modes are most appropriate for his particular system requirements, and the singular dataflow chip structure <b>100</b> may be programmed by the user to select any one of the three modes needed. In another aspect of the invention, the frame processing mode may be selected by dataflow management software interface with the dataflow chip <b>100</b>.

In the present embodiment, the choice of frame processing mode is made by selecting an appropriate ingress port channel to the dataflow structure <b>100</b>. The BUS <b>1</b> ingress port <b>110</b> represents a physical interface connection to an external chip or external network link or line, and may be channelized. In one embodiment of the present invention, 16 channels are supported at the BUS <b>1</b> ingress port <b>110</b>. In another embodiment, 64 channel connections are supported. However, it should be understood that the specific number of channels supported is not limited to the embodiments described herein, and more or less channels may be supported by the ingress port according to the present invention. One skilled in the art will realize that the choice of 16 or 64 channels by the embodiments described thus far is not limiting to the invention described herein.

The channels are each designated for one of the three dispatch modes, and the system designer or data management software accordingly selects the channel based upon the desired dispatch mode. And then responsive to the appropriate channel selection in the BUS <b>1</b><b>110</b> control logic residing in the RCV PCB frame receive control block module <b>112</b> will select the appropriate dispatch structures and mode on the dataflow chip <b>100</b>.

The control block module <b>112</b> comprises a plurality of port control blocks for data frame management. In the present embodiment, one port control block is provided within the control block module <b>112</b> for each channel in the BUS <b>1</b> frame switch ingress port <b>110</b> and the BUS <b>2</b> scheduler FPGA/coprocessor ingress port <b>111</b>. For example, if BUS <b>110</b> and BUS <b>111</b> each have 16 channels, then the control block module <b>112</b> has 32 port control blocks. As is well known in the art, each port control block will thus control the data management on a data packet received at the appropriate ingress port <b>110</b> or <b>111</b> until the data packet is transmitted out of the dataflow chip <b>100</b>.

In the present embodiment, the appropriate frame processing mode for any given data packet is indicated by bit information within the port control block. For example, for an eight or 16-bit size data port control packet for a given data frame, two bits of information would be reserved for indicating the appropriate dispatch mode, and the logic residing in the control block module <b>112</b> selects the appropriate dispatch mode for the data frame responsive to the two bits.

The EPC control block module <b>114</b> has a similar structure and function as the control block module <b>112</b>, but with respect to data received from the embedded processor chip <b>101</b> instead of through the BUS <b>110</b> and <b>111</b>. Therefore, it also comprises a plurality of port control blocks for data frame management for data packets received from the EPC and transmitted out of the dataflow chip <b>100</b>.

In another aspect of the present invention, the dataflow chip structure <b>100</b> provides ingress and egress data flow functions, where ingress data flow is defined as handling traffic from an external network through an external switch or network node that interconnects several data flow chips within a system, and egress data flow is defined as handling traffic to an external switch. Accordingly, egress BUS ports <b>120</b> and <b>122</b> are provided to interface to external switches and frame/scheduler FPGA/coprocessor interfaces, respectively.

Cut and paste. As illustrated in <figref idref="DRAWINGS">FIG. 2</figref>, in cut-and-paste mode, a frame header may be forwarded immediately to a processing unit <b>102</b> while the body of a frame is received in a data store component <b>104</b>. After processing, the modified header is reconnected to the body in data store <b>104</b>. In this way, the present invention optimizes data store bandwidth in systems for which input queue has limited growth.

Full dispatch. Referring now to <figref idref="DRAWINGS">FIG. 3</figref>, in full dispatch mode, a full frame is forwarded immediately to the processing unit <b>102</b> without being received in data store <b>104</b>. After processing, the full modified frame is written in data store <b>104</b>. In this way, the present invention optimizes data store bandwidth for systems oriented to deep packet processing.

Store and dispatch. Referring now to <figref idref="DRAWINGS">FIG. 4</figref>, the store and dispatch mode of frame processing according to the present invention is illustrated. Here a full frame is received in data store <b>104</b> and a frame header is dispatched to the processing unit number <b>102</b>. After processing, the modified frame header is written back in data store for <b>104</b>, replacing the original frame header. In this way, the present invention enables accommodation of very large accumulations of data in input queues.

Scheduling Modes

In another aspect of the present invention, a number of alternative scheduling modes are enabled by scheduling chip structures <b>400</b> implemented in the dataflow chip <b>100</b>. <figref idref="DRAWINGS">FIG. 5</figref> provides a detailed view of the scheduling chip structures <b>400</b>. In the present embodiment, the scheduling chip structures <b>400</b> are incorporated on the same circuit board or physical structure of the dataflow chip <b>100</b> and embedded processor chip <b>101</b>, although it is apparent that they may reside on separate chips and be interconnected through wiring or other circuit structures. In the present embodiment, three different scheduling modes are available: (i) full internal scheduling functions performed in the dataflow chip structure <b>100</b>; (ii) calendar in an external scheduler, and (iii) external full-scale functions, including external FPGA, ASIC and external processor scheduler functions.

Is well known in the art to provide scheduling functions within dataflow chip structures through “calendar” structures to decide which packets are to be scheduled first for dispatch. The calendar structures also manage queue control blocks (QCB's) for management of the order of queue access and flow of data from output queues from which a packet is being dequeued, as well as transmission to “target channel queues” (TCQ's). TCQ's are utilized for data packets that are being forwarded to a target channel or port. Therefore, the scheduler structures provide calendar functions and QCB manipulation functions.

Full internal scheduling function (“Scheduling Mode <b>1</b>”). In the first available scheduling mode, full scheduling functions may be provided internally by the scheduler chip <b>400</b> structures and the logic residing therein. In this mode, no external scheduling structures or logic are required. The calendar and QCB control functions are driven by the dataflow chip <b>100</b>, and the actual calendar structures are dedicated physical memory areas <b>402</b> located in the data store blocks <b>104</b>. The dedicated calendar memory areas <b>402</b> are reserved for calendar functions. They do not handle actual data traffic and thus do not buffer or store the data packets being handled by the dataflow chip <b>100</b>, but instead hold scheduling calendar data. The “dequeue” data flow functions are generally contained and defined by the dequeue chip structures and logic <b>411</b>, and the enqueue dataflow functions are generally contained and defined by the enqueue chip structures and logic <b>415</b> structures, which, in turn, comprises an enqueue flow queue module <b>418</b> and enqueue TCQ module <b>419</b>.

The full internal scheduling function also comprehends internal flow queue control and flow QCB management through internal structures, for both full internal and external scheduling moments. Full scheduling functions on the dataflow chip <b>100</b> are intended to be on a small-scale, thereby minimizing the number of calendar memory areas <b>402</b> dedicated to the calendar structure in the data store <b>104</b>, since this dedication necessarily reduces the amount of data store <b>104</b> memory capacity for data handling. The actual number of offers required for calendar memory areas <b>402</b> is determined by the size of bandwidth handled by the dataflow chip <b>100</b>, and also determined by the speed of the particular memory structures used in the data store areas <b>104</b>. Accordingly, the faster the memory structures, the smaller the calendar memory area <b>402</b> bandwidth requirements.

The logic for the internal calendar functions resides in the “Flat Cal Page Loader” module <b>404</b>. The process takes place in real-time, as indicated by the “Tick” clock element <b>406</b>. For each time tick, an entire “Page” of calendar entries is read. In one embodiment of the invention, each calendar Page has eight calendar entries, each entry being 32 bits large.

The dataflow chip scheduler structure <b>400</b> provides further efficiency advantages within the scheduling function by providing two different scheduling procedures: (1) “guaranteed” bandwidth, and (2) “Best effort” scheduling, without the requirement of external components. As is well known in the art, guaranteed and best effort scheduling represent two different levels of scheduling commitment. In guaranteed modes, it is intended that all data will be transmitted; this type of mode is generally desirable for multimedia and voice data traffic. A “reserved bandwidth” is provided within system resources in order to enable the scheduling of each anticipated flow in the anticipated packet size. In contrast, in best effort modes, the system makes available bandwidth left over from guaranteed traffic requirements to make an attempt to transmit all data, but if too many demands are made upon system resources, some data might be dropped. The logic for controlling the guaranteed bandwidth and best effort scheduling is contained in the “flow QCB handler” <b>420</b>. The logic for guaranteed bandwidth scheduling is provided by the “red flow QCB handler” <b>422</b>, and includes typical guaranteed bandwidth scheduling steps <b>423</b>, such as a first step of “credit accumulation bandwidth scheduling” to determine packet transmission order; then the packets are transmitted and flow queues “dequeued” according to the determination made in the credit accumulation step, and lastly the dequeue counter management step is performed to make sure that the correct number of packets have been transmitted.

The logic for best effort bandwidth scheduling is provided by the “blue flow QCB handler” <b>424</b>. In the present embodiment in best effort flow, QCB handler <b>424</b> includes the afore-mentioned guaranteed bandwidth scheduling steps <b>423</b>, and further includes weighting best effort logic steps <b>425</b>. In some embodiments of the present invention, best effort decisions incorporate “round-robin” packet dispatching, wherein the remainder of the bandwidth available for packet dispatching after guaranteed bandwidth allocations is managed on a “last in-first out” (LIFO) basis.

The present embodiment provides a modified round-robin LIFO approach by giving reference to some data packets over other data packets. Accordingly, “blue weight accumulation” and “green weight accumulation” logic steps <b>425</b> are performed, in which 16 shallow calendar 4-LIFO's <b>428</b> scheduling structures are configured wherein three calendar entries are pointing to a LIFO-linked list of QCB's associated with flows that did not exceed their maximum rate, and the fourth entry points to a LIFO of QCB's associated with flows that exceeded their maximum rate.

Calendar in external scheduler, flow queue handling in dataflow (“Scheduling Mode <b>2</b>”). The dataflow chip <b>100</b> also provides a second scheduling mode wherein an external scheduling chip <b>410</b> handles more complex scheduling functions, such as for example hierarchical scheduling, while still providing internal flow queue control and flow QCB management by the scheduler chip <b>400</b> internal structures. Hierarchical scheduling is a very important feature in some networks, particularly in wide-area networks, in which the network structure itself relies on some form of hierarchical of links. However, hierarchical scheduling functions are relatively complex and require more system resources than can be efficiently allocated from on-chip structures. For example, in a two-level hierarchy, with multiple virtual channels (VCs) in a single virtual path (VP), regular scheduling functions have to be performed on a VP (thereby managing the aggregate bandwidth of this VP), and also on each of the VCs multiplexed in the VP. This means that at a given point in time, a VP should be provided with some amount of best effort bandwidth available on a physical port (for example, a 100 Mbps physical port) shared with other VPs, and also shared between the VCs of the VP according to their relative “fair share” of the 100 Mbps bandwidth.

Hierarchical scheduling, therefore, may require more system resources for calendar functions than can be efficiently allocated from on-chip resources and, accordingly, an external scheduling chip <b>410</b> may be required. This is necessary in order to provide capabilities to review more than one calendar Page at a time for any given data packet scheduling function. Rather than looking at only one calendar Page and scheduling accordingly, the present invention looks at multiple pages and considers their hierarchy weightings and determines which pages have higher importance and should be scheduled first over lesser important pages for each data packet. For example, in a four-level hierarchical scheme, for each packet transmission, rather than reading just one calendar page, the present invention considers four calendar pages, wherein each calendar page is needed to manage the bandwidth of a level in the hierarchy of the network. And, accordingly, where the dataflow logic recognizes and applies best effort scheduling to this four-level hierarchical scheme data packet, and system resources are limited, then the best effort configuration will give priority to be highest ranked of the four hierarchy level packet categories and where packets must be dropped due to limited resources, then the present invention will drop the lowest hierarchy of levels first.

Full external scheduling and flow queue management (“Scheduling Mode <b>3</b>”). In the third option provided by the present embodiment of the invention, full scheduling functions and flow queue management functions are performed by an external structure. The number of scheduled flows is defined by the size of control memory supported by the external scheduler, which obviously can be as large as desired, without any dataflow chip <b>100</b> structural restrictions.

In the present embodiment, the external structure is a logic programmable FPGA chip <b>410</b> capable of handling complex scheduling functions. It is to be understood that “external scheduling chip” is a generic phrase, and those skilled in the art will understand the external chip may be embodied by any number of external structures. Exemplary alternative embodiments many use other structures, such as ASIC fixed-logic chip structures, high-speed processors such as pico-processors, or other coprocessor structures. One skilled in the art will recognize that the specific nature of the external chip component <b>410</b> is not critical to the invention. What is important is that the external chip component <b>410</b> has the ability to perform the scheduling and flow queue control management functions required by the dataflow chip <b>100</b>. Also of importance is that the external scheduling chip <b>410</b> has the capacity to support a much larger number of data flows and, accordingly, a much larger number of flow queues, relative to the dataflow chip <b>100</b> capacities.

Each “flow queue” is to be understood as corresponding to each logical flow that the network processor is handling. It is a list of packets that must be maintained by descriptors or data control blocks. Each control block is defined for each flow queue, wherein the control block contains data information, including a pointer to point to the first packet in a queue, another pointer to point to the last packet in a queue, and a queue count which reflects the number of packets in the queue. Accordingly, where high-volume dataflow may require millions of flow queues and queue control blocks, more robust external scheduling structure <b>410</b> memory capacity is required to hold the MB of memory demanded.

What is new in the present invention is the ability to use the dataflow chip <b>100</b> structures to provide all three of the above described scheduling modes. This is established by providing multiple dataflow and logic paths within the dataflow chip <b>100</b>, and by providing switches to select the appropriate path and logic for the scheduling mode required. The switch positions may be fixed and selected by an end-user in the initial incorporation of the dataflow chip <b>100</b> into a circuit design. Or the switches may be dynamic and subject to subsequent reprogramming, or even activation/deactivation and scheduling mode changes through on-the-fly data management processes responsive to packet recognition or changing system requirements.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates six switches <b>510</b>, <b>520</b>, <b>530</b>, <b>540</b>, <b>550</b> and <b>560</b> for selection of any one of the scheduling modes performed by the present embodiment. Switch <b>510</b> provides the first decision point. When switch <b>510</b> is toggled left to node <b>512</b>, then calendar pages exported by the calendar page loader <b>404</b> through the prefetch stack <b>405</b> are routed directly to the internal scheduler logic and structure <b>420</b> and handled pursuant to Scheduling Mode <b>1</b>. Alternatively, when switch <b>510</b> is toggled to right node <b>514</b>, the pages are instead received from external scheduling chip <b>410</b> through the BUS <b>411</b> and routed through the second switch <b>520</b> for dispatching through either Scheduling Mode <b>2</b> or Scheduling Mode <b>3</b>. Therefore, where scheduling functions are performed by the external scheduling chip <b>410</b> in Scheduling Mode <b>2</b> and Scheduling Mode <b>3</b>, the results of the external scheduling chip <b>410</b> scheduling functions are sent back to the dataflow chip <b>100</b> for management according to the present invention.

Switch <b>520</b> provides the next decision point. When switch <b>520</b> is toggled left to node <b>522</b>, then the forwarded calendar pages are managed according to either Scheduling Mode <b>1</b> or Scheduling Mode <b>2</b>, and the flow queue functions are handled by the flow QCB handler <b>420</b>. Alternatively, when switch <b>520</b> is toggled right to node <b>524</b>, the pages are instead managed according to Scheduling Mode <b>3</b> and routed through the BUS <b>417</b> to the external scheduling chip <b>410</b>.

Switches <b>530</b>, <b>540</b>, <b>550</b> and <b>560</b> are utilized in the present invention to select internal or external flow queue handling management. Referring now to switches <b>530</b> and <b>540</b>, in another aspect of the present invention, guarantee bandwidth scheduling and best effort bandwidth scheduling may be bifurcated between the dataflow chip <b>100</b> and the external scheduling chip <b>410</b>. Specifically, in the present embodiment, guaranteed bandwidth flow queue scheduling may be handled on the dataflow chip <b>100</b>, while best effort flow queue scheduling may be performed by the external chip <b>410</b>.

The present embodiment is designed to handle <b>16</b> target queue channels through on-chip best effort flow control. If this provides sufficient bandwidth for circuit design requirements, then the internal on-chip flow scheduling structures will be selected. Accordingly, when switch <b>530</b> is toggled right to node <b>532</b> and switch <b>540</b> toggled left to node <b>542</b>, best effort flow queue scheduling is handled on the dataflow chip <b>100</b>. Alternatively, if network requirements necessitate substantially more bandwidth capacity than 16 target queue channels, best effort flow queue scheduling will be handled by the additional TCQ resources residing on the external scheduling chip <b>410</b> and, accordingly, switch <b>530</b> is toggled left to node <b>534</b> and switch <b>540</b> toggled right to node <b>544</b>.

In another aspect of the present invention, the flow control of the target channels are managed through the use of target control queues (TCQ's). A TCQ contains data packets dequeued from flow queues as decided by the scheduling function. Due to system inefficiencies, such as the burstiness inherent in the data traffic and management processes, scheduling decisions forced by the scheduler cannot meet the physical rates supported by each of the 16 target channels. Therefore, the data packets are enqueued in the TCQ's until they may be successfully transmitted to the target channels according to the scheduling functions.

The present embodiment provides for 16 TCQ's <b>440</b>, one for each of the 16 channels. However, the 16 target channels provided by the present embodiment represent a limited channel capacity. By nature, the queues are very shallow and cannot accommodate many data packets. Accordingly, another novel aspect of the present invention is the additional flexibility of selecting internal or external TCQ queue structures and management. If the 16 TCQs <b>440</b> are sufficient to handle the anticipated flow queue handling requirements, then switch <b>550</b> is toggled left to node <b>552</b> and switch <b>560</b> is toggled left to node <b>562</b>, and the on-chip internal enqueue logic structure <b>415</b> and the 16 TCQ's <b>440</b> are utilized in the flow queue scheduling.

Alternatively, if network requirements necessitate substantially more bandwidth capacity than 16 target queue channels, best effort flow queue scheduling will be handled by the additional TCQ resources residing on the external scheduling chip <b>410</b>. As will be readily apparent to one skilled in the art, the external chip structure <b>410</b> may be provided with many more target channels than the 16 TCQ's <b>440</b> on chip. For example, in some applications more than 1,000 TCQ's may be provided in an external chip structure <b>410</b>. Accordingly, switch <b>550</b> is toggled right to node <b>554</b> and switch <b>560</b> toggled right to node <b>564</b>, and TCQ management and scheduling decisions handled by logic residing on the external chip <b>410</b>.

In general, the decisions embodied by the switches <b>510</b> through <b>560</b> of the present embodiment are static decisions. They are made by the circuit design when the network systems is assembled, and are not made “on-the-fly” responsive to packet identification. However, alternative embodiments may make these switch decisions dynamically, and the present invention is not to be limited to static switch selection structures, as one skilled in the art will recognize that the modes selected may be altered dynamically through interaction with the network processing system. For example in one alternative embodiment, the internal enqueue logic structure <b>415</b> and the 16 TCQ's <b>440</b> may be selected responsive to dynamic data packet characteristics and requirement changes, and communications through the BUS lines <b>417</b> and <b>411</b>, or from the on-chip flow control QCB handler <b>420</b>, may dynamically change switch <b>550</b> and/or <b>560</b> settings responsive to said changes.

Accordingly, target channel information contained in a packet communicated to switch <b>560</b> from the on-chip flow control QCB handler <b>420</b> through output “FCBA BCNT TC” BUS <b>450</b> may include channel identification information as well as internal/external TCQ management selection information. Where the information indicates the address of TCQ-<b>0</b> through TCQ-<b>15</b>, then switch <b>550</b> is toggled left to node <b>552</b> and switch <b>560</b> is toggled left to node <b>562</b> and the on-chip internal enqueue logic structure <b>415</b> and the 16 TCQ's <b>440</b> are utilized in the best effort flow queue scheduling. However, if the information instead indicates the address of TCQ-<b>16</b> through TCQ-<b>1</b>,<b>000</b>, then switch <b>560</b> may responsively be toggled right to node <b>564</b> and send the packet through BUS <b>417</b> to external chip <b>410</b> logic and TCQ utilization in the best effort flow queue scheduling.

Also, the switch <b>550</b> may dynamically arbitrate between packet target channel information received at node <b>552</b> from the on-chip flow control QCB handler <b>420</b> and packet target channel information received at node <b>554</b> from the external scheduling chip <b>410</b> from BUS <b>411</b>, wherein these two different information inputs may arrive simultaneously at the switch <b>550</b>. A buffer structure can be provided at the node <b>554</b> bus <b>411</b> interface, and arbitration priority may be given to packets arriving from the on-chip flow control QCB handler <b>420</b> at node <b>552</b>.

In another aspect of the present invention, even where external scheduling chip <b>410</b> TCQ's are selected, the internal enqueue logic structure <b>415</b> and the 16 TCQ's <b>440</b> are still utilized in best effort flow queue scheduling. The TCQ operations are the last data handling operations prior to transmission of the data by the dataflow chip <b>100</b> to its network destination. As each of the 16 multiplex channels may include as many as 128 channels, keeping the data packets on chip whenever possible by utilizing the internal enqueue logic structure <b>415</b> and the 16 TCQ's <b>440</b> provides for improved speed and inefficiencies in the data transmission process even where external chip <b>410</b> TCQ resources are required.

In further aspects of the present embodiment of the invention, calendar functions may be implemented in the EPC and then to be driven by software. This is enabled when switch <b>570</b> is toggled down to node <b>574</b>. And switch <b>580</b> enables the configuration of the Q<b>2</b> QDR memory <b>624</b> as a repository for additional FCBs (when switch <b>580</b> is toggled up to node <b>582</b>), or alternatively enables the use of the Q<b>2</b> QDR memory <b>624</b> for network management counters (when switch <b>580</b> is toggled down to node <b>584</b>). This provides a complement to the scheduling mode flexibility features according to the present invention. When flow queues are managed by the dataflow chip <b>100</b>, the Q<b>2</b> QDR memory <b>624</b> can be used to store additional QCBs. And when the external scheduler scheduling mode is selected, the Q<b>2</b> QDR memory <b>624</b> can be used for other purposes, since an external scheduler will typically comprise its own larger memory resources enabling external storage of many QCBs.

Flexibility in Data Movement

The present invention also provides for improved flexibility features in data movement. Referring now to <figref idref="DRAWINGS">FIG. 6</figref>, aspects of flexible data movement features of the invention are illustrated with particularity in dataflow chip <b>100</b>. Main data path components are configured for a plurality of frame processing modes. And alternative data path connections are provided to enable bypassing of main on-chip transmit structures for direct transmission of data from the EPC <b>101</b> to chip output ports.

EPC low latency access. In one aspect of the invention, the EPC <b>101</b> processing unit is provided with privileged high bandwidth/low latency access to control store <b>610</b> and data store <b>104</b> elements. This enables implementation by software in the EPC <b>101</b> of data movement functions such as scheduling, simulation and reassembly. In contrast, prior art implementations require hardware structures to perform scheduling, simulation and reassembly functions. Hardware implementations are necessarily static; they cannot be altered either dynamically on a packet-by-packet basis or through subsequent software reprogramming. By enabling software code to run these functions, the present invention greatly increases the flexibility of the dataflow chip <b>101</b> structures, thus enabling EPC <b>101</b> pico code processors, or the dataflow chip <b>101</b> software-defined calendar structures discussed above, to perform software-based functions that may be reprogrammed or redefined as required by changing dataflow requirements.

In the EPC low latency access mode according to the present invention, the EPC <b>101</b> is given direct access to memory resources. In prior art systems, such direct access is typically reserved for on-chip dataflow chip resources. This allows the EPC <b>101</b> complete access and ability to manipulate data packets.

In the present embodiment, QDR (“quad data rate”) frame control blocks <b>620</b> and QDR buffer control blocks <b>622</b> are defined in the dataflow chip <b>101</b> for control store functions. QS<b>0</b><b>620</b> is a QDR static random access memory (SRAM) component utilized in the present invention to contain frame control blocks. QS<b>1</b><b>622</b> is a QDR SRAM component utilized in the present invention to contain buffer control blocks. Q<b>2</b><b>624</b> is a QDR SRAM component utilized in the present invention to contain counters. What is new in the present invention is the provision of direct read/write control bus <b>632</b> and direct write data bus <b>692</b> for direct access of the buffer control blocks, frame control blocks and counters in QS<b>1</b><b>622</b>, QS<b>0</b><b>620</b> and Q<b>2</b><b>624</b>, respectively, for control store data manipulation.

The software logic for enabling the direct access and manipulation of the data are found in the associated arbitration blocks. FCB QDR ARB <b>640</b> is associated with QS<b>0</b><b>620</b>; BCB QDR ARB <b>642</b> is associated with QS<b>1</b><b>622</b>; and Q<b>2</b> QDR ARB <b>644</b> is associated with Q<b>2</b> QDR <b>624</b>. The FCB QDR ARB <b>640</b>, BCB QDR ARB <b>642</b> and Q<b>2</b> QDR ARB <b>644</b> are accessed by the direct control bus <b>632</b> and direct data bus <b>630</b>. Direct frame control block access enables the EPC <b>101</b> to remove packets directly from dataflow chip <b>101</b> queues, or alter them or manipulate them. Direct buffer control block access enables the EPC <b>101</b> to actually split packets into smaller packets by manipulating their chain references, as will be apparent to one skilled in the art.

Data is returned to the EPC <b>101</b> through the DS direct read data component <b>636</b> through 128 bit return bus <b>638</b>. The DS direct component <b>636</b> receives return data from the QDR blocks <b>620</b>, <b>622</b> and <b>624</b> through QDR buses <b>634</b> and <b>635</b>, and also through the DS bus <b>633</b>.

As is well known in the art, “read” access latency is more important in overall system performance than “write” latency. Write operations are much simpler in that the EPC <b>101</b> may direct a write operation and thus consider the operation complete with the issuance of the instruction. In contrast, read operations require actual data manipulation and system resource commitment until the operation is complete. The present invention provides for low latency data store access by the EPC <b>101</b>.

In another aspect of the present invention, an additional dataflow chip <b>101</b> access means for the EPC <b>101</b> is provided, a primitive “normal latency” EPC interface structure <b>674</b>. The normal latency interface <b>674</b> allows for an additional data path into the EPC <b>101</b> from the dataflow chip <b>100</b>, which enables additional system efficiencies and performance advantages.

In another aspect of the present invention, a plurality of “read request queues” (RRQ's) <b>660</b> are provided in the structure of the dataflow chip <b>100</b> itself. The RRQ's <b>660</b> contain small amounts of information necessary to identify corresponding read accesses performed on the two data store components, the DSH <b>104</b> and DSL <b>105</b>, at the smallest granularity required to perform a read access on the data store components <b>104</b> and <b>105</b>. Exemplary granularities would be 16 or 32 bytes for data “burst” access. Each burst read request is posted in one of the RRQ's <b>660</b>. Read operations are then performed on the data store high DSH <b>104</b> as arbitrated by the DSH arbitration module <b>661</b>, and on the data store low DSL <b>105</b> as arbitrated by the DSH arbitration module <b>662</b>, and every data flows upward towards a plurality of transmit preparation area queues <b>663</b>. This is enabled by a dedicated RRQ <b>664</b> which is reserved to provide direct read request queue functions by the EPC <b>101</b>.

Data given back from the memory modules DSH <b>104</b> and DSL <b>105</b> through the read operation is intercepted and sent back directly to the EPC <b>101</b> through the DS bus <b>633</b> through the operation of control delay components <b>665</b> and <b>666</b>. They function as shallow buffers that match the delay of the read operation completion, to account for the time delay between read request and actual delivery of the data requested. In order to provide for low latency, the arbitration module's <b>661</b> and <b>662</b> are given highest priority by the dedicated RRQ <b>664</b>.

What is new in the present invention is that each EPC <b>101</b> processor resource <b>670</b> has a “low latency” interface <b>672</b>, which provides privileged access to the dataflow chip <b>100</b> resources, and a “normal latency” non-privileged access interface <b>674</b>. Low latency accesses enable control of data movement by software in scheduling, segmentation and reassembly processes. Data manipulation and transmission may occur directly from an external coprocessor allowing full access by external structures and elements to data, including the ability to change and create data in the dataflow chip datastores. Segmentation and data transmission may be driven by software. And the present invention enables direct access by software to data and data structures without requiring routing through buffering points, such as for example the data store <b>104</b>.

Flexibility features are implemented by specific data paths in the dataflow chip <b>100</b>. A main data path is configured by software for various frame processing modes. Internal paths are configured between the logic islands of the internal scheduler and BUS<b>2</b>, allowing connection of an external scheduler or coprocessor. Thus, reuse of main data path functions with additional by-passes for flexible data movement is enabled. An additional transmit data path reuses transmit control logic, but bypasses the main transmit data path from data store <b>104</b> to output ports. This enables direct transmission of data from the processing unit to output ports.

In the present embodiment of the dataflow chip <b>101</b>, the selection of data movement mode is made dynamically on a packet-by-packet basis. No end-user configuration or programming is required, although it will be readily apparent to one skilled in the art that this type of option selection may be provided. As the dataflow chip <b>101</b> transmits, a data packet information within each of the data packets will cause a responsive selection of the appropriate data movement path.

Referring now to <figref idref="DRAWINGS">FIG. 6</figref>, a block diagram schematic of the data flow chip <b>100</b> is illustrated, providing additional detail not shown in previous views of the dataflow chip <b>100</b> illustrated in <figref idref="DRAWINGS">FIGS. 1 through 5</figref>. Additionally, for the sake of clarity, some elements present in <figref idref="DRAWINGS">FIGS. 1 through 5</figref> are not shown in <figref idref="DRAWINGS">FIG. 6</figref>. It is to be understood that the dataflow chip <b>100</b> embodiment shown in <figref idref="DRAWINGS">FIGS. 1 through 6</figref> includes all of the elements shown in any of the various individual figures, and if a numbered element is not found in any one view, it may be found in another.

As described above, the QS<b>0</b> QDR (“quad data rate”) frame control blocks <b>620</b> contain frame control blocks, the QS<b>1</b> QDR buffer control blocks <b>622</b> contain buffer control blocks and Q<b>2</b> QDR <b>624</b> contains counters. The software logic for enabling the direct access and manipulation of the data are found in the associated arbitration blocks FCB QDR ARB <b>640</b>, BCB QDR ARB <b>642</b> and Q<b>2</b> QDR ARB <b>644</b>, which are accessed by the direct control bus <b>632</b> and direct data out bus <b>630</b>. And as described above, direct frame control block access enables the EPC <b>101</b> to remove packets directly from dataflow chip <b>101</b> queues, or alter them or manipulate them. Direct buffer control block access enables the EPC <b>101</b> to actually split packets into smaller packets by manipulating their chain references, as will be apparent to one skilled in the art.

The direct control bus <b>632</b> is accessed by an access control MUX <b>631</b>, and the direct data out bus <b>630</b> is accessed by a data out MUX <b>637</b>. The data out MUX <b>637</b> and the access control MUX <b>631</b> provide interface to EPC <b>101</b> low latency data access resources wherein multiple EPC <b>101</b> processor resources <b>670</b> are provided access to each of the access control MUX <b>631</b> and data out MUX <b>637</b>.

Low latency. The low latency interface <b>672</b> communicates through ACC ID <b>673</b>, ADDR <b>684</b> and CTL <b>675</b> data buses with the access control MUX <b>631</b> through a low latency bus <b>682</b>. The ACC ID <b>673</b> is for high level “access identification” memory address information for data access and manipulation, and address and control information for the target data is sent by the EPC <b>101</b> processor resource <b>670</b> through the ADDR <b>684</b> and CTL <b>675</b> data buses, respectively.

For data write operations, QDR direct write data is sent by the EPC <b>101</b> processor resource <b>670</b> through the arbitration blocks FCB QDR ARB <b>640</b>, BCB QDR ARB <b>642</b> and Q<b>2</b> QDR ARB <b>644</b> on the direct data out bus <b>630</b> through the data out MUX <b>637</b>. For read operations, the read data address locations are returned to the EPC <b>101</b> processor resource <b>670</b> and data is read from the QS<b>0</b> QDR frame control blocks <b>620</b> and QS<b>1</b> QDR buffer control blocks <b>622</b> on the QDR direct read data buses <b>634</b> and <b>635</b>, and data store data is read from the data stores <b>104</b> and <b>105</b> on the DS direct read data bus <b>633</b>. Read data is transmitted from the DS direct read data bus <b>633</b> and the QDR direct read data buses <b>634</b> and <b>635</b> through a DS direct read data mux <b>636</b> to the EPC <b>101</b> processor resource <b>670</b>. Thus, direct access to data store data by software is enabled for manipulation of the data stored data.

According to the present invention, two data accesses are provided. The first data access provided is “DS Direct Read”. The ACC ID <b>673</b> points to the appropriate data store high <b>104</b> or data store low <b>105</b>. The read request will flow from the CTL <b>675</b> data bus along the direct control bus <b>632</b> to a DS direct read control bus <b>690</b> to generate a special data store read request, which is queued in the special EPC direct read request queue <b>664</b> located in the block of read request queues <b>660</b>. The EPC direct read request queue <b>664</b> is similar to the ordinary read request queues <b>665</b> located in the read request queue block <b>660</b>, except for the priority granted to it by the data store high read arbitrator <b>661</b> and data store low read arbitrator <b>662</b> in accessing the data store high <b>104</b> and data store low <b>105</b>, respectively. A read operation will responsibly occur on the data store high <b>104</b> and/or data store low <b>105</b>, and data will return to the EPC <b>101</b> processor resource <b>670</b> on the DS direct read data bus <b>633</b>.

The second data access provided is “direct transmit” data access, wherein the EPC <b>101</b> may transmit data directly through the dataflow chip <b>100</b> without the requirement of first storing the data in the data store structures <b>104</b> or <b>105</b>. This is accomplished by using the ACC ID <b>673</b> to point to a specific transmit port <b>694</b> within the transmit ports block <b>633</b>. The ADDR <b>684</b> bus is used to communicate with the XMT PCB structure <b>691</b> through the direct write data bus <b>692</b> to cause the XMT PCB <b>691</b> to create a “pseudo read request” that will be dequeued in the read request queues <b>665</b> in the read request queue block <b>660</b>. The specific pseudo read request will be dequeued into the data store high control delay block <b>665</b> or the data store low control delay block <b>666</b>, and will be recognized as a special read request that does not require read/write of the transmitted data to the data stores <b>104</b> and <b>105</b>, but instead will steer the transmitted data directly to the BUS <b>2</b> (A) output port <b>122</b> or the BUS <b>1</b> (B) output port <b>120</b>. In the present embodiment of the invention, data directly transmitted through the BUS <b>2</b> (A) output port <b>122</b> moves onto a framer, a scheduler FPGA or a coprocessor, and data directly transmitted through the BUS <b>1</b> (B) output port <b>120</b> moves on to a framer or a switch.

Normal latency. The present invention also provides for “normal latency”, or non-privileged dataflow chip <b>100</b> access by the EPC <b>101</b>. Non-privileged data store <b>104</b> and <b>105</b> read data access travels along the read more from DS bus <b>698</b> through a data-in mux <b>699</b> into a data-in bus <b>701</b> to an EPC <b>101</b> processor resource <b>670</b> through the “normal latency” interface <b>674</b>. The read more from DS bus <b>698</b> is novel in that it relies completely on the normal data flow chip <b>100</b> structures described thus far but without benefiting from the low latency capabilities described above. The external software scheduler mode described above is enabled by the schedule return bus <b>700</b>, which also enters the data-in mux <b>699</b>.

While embodiments of the invention have been described herein, variations in the design may be made, and such variations may be apparent to those skilled in the art of computer architecture, systems and methods, as well as to those skilled in other arts. The present invention is by no means limited to the specific hardware implementations illustrated above, and other software and hardware implementations will be readily apparent to one skilled in the art. The scope of the invention, therefore, is only to be limited by the following claims.