Method and system for flexible network processor scheduler and data flow

• US 20070011223A1
• Filed: 05/18/2005
• Published: 01/11/2007
• Est. Priority Date: 05/18/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chang, Chih-jen, Wind, Daniel, Logan, Joseph, Verplanken, Fabrice, Calvignac, Jean
• Granted Patent: US 7,483,429 B2
• Time in Patent Office: Days
• US Class Current: 709/200
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 47/58 Changing or combining different scheduling modes, e.g. multimode scheduling

Abstract

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.

Claims

1. A network processor dataflow chip comprising:

a. a plurality of on-chip data transmission circuit structures; and

b. a plurality of scheduling circuit structures;

wherein one of the plurality of data transmission circuit structures is selected responsive to a data transmission selection indicator; and

wherein one of the plurality of scheduling circuit structures is selected responsive to a scheduling function selection indicator.

2. The dataflow chip of claim 1, wherein the plurality of on-chip data transmission circuit structures comprises:

a1. a plurality of selectable frame processing circuit structures; and

a2. a plurality of selectable data transmission circuit structures.

3. The dataflow chip of claim 2, further configured to select a frame processing circuit structure responsive to the selection of one of a plurality of ingress port channels.

4. The dataflow chip of claim 2, further configured to select a frame processing circuit structure for a data packet responsive to a bit information received within the data packet.

5. The dataflow chip of claim 2, wherein the plurality of selectable frame processing circuit structures comprises:

a1a. a cut and paste frame processing circuit structure;

a1b. a full dispatch frame processing circuit structure; and

a1c. a store and dispatch frame processing circuit structure.

6. The dataflow chip of claim 5, wherein:

the a1a. cut and paste frame processing circuit structure is configured to forward a frame header immediately to a processing unit while a body of a frame is received in a data store component and, after processing the frame, then reconnect a modified header to the body in the data store;

the a1b. full dispatch frame processing circuit structure is configured to forward a full frame immediately to a processing unit without receiving the full frame in the data store and, after processing the full frame, write a full modified frame in the data store; and

the a1c. store and dispatch frame processing circuit structure is configured to receive the full frame in the data store and dispatch an original frame header to the processing unit number and, after processing the full frame, write a modified frame header back to the data store, the modified frame header replacing the original frame header.

7. The dataflow chip of claim 2, wherein the plurality of scheduling circuit structures comprises:

b1a. a full internal scheduling circuit structure;

b1b. a calendar scheduling circuit structure in communication with an external scheduler chip; and

b1c. an external calendar scheduling circuit structure.

8. The dataflow chip of claim 7, wherein the b1a. full internal scheduling circuit structure comprises calendar and queue control circuit structures driven by the dataflow chip, and the calendar circuit structures are each defined by a plurality of dedicated physical memory areas located in data store blocks.

9. The dataflow chip of claim 8, wherein:

the b1a. full internal scheduling circuit structure comprises logic for internal calendar functions residing in a calendar page loader and a clock element, and the calendar circuit structures each comprise a plurality of calendar pages, each of the plurality of calendar pages comprising a plurality of calendar entries, wherein the dataflow chip is configured to read a calendar page for each clock element tick.

10. The dataflow chip of claim 9, wherein the dataflow chip scheduler circuit structure further comprises a guaranteed bandwidth scheduling circuit structure and a best effort scheduling circuit structure.

11. The dataflow chip of claim 7, wherein the external scheduler chip is selected from the group comprising a logic programmable FPGA chip, an ASIC fixed-logic chip, a high-speed processor, and a coprocessor.

12. The dataflow chip of claim 7, further comprising:

a. a plurality of dataflow and logic paths; and

b. a plurality of switches to select dataflow and logic paths;

wherein the scheduling circuit structure is selected responsive to positions of the plurality of switches.

13. The dataflow chip of claim 12, wherein the positions of the plurality of switches are selected dynamically responsive to data packet recognition.

14. The dataflow chip of claim 12, wherein internal or external flow queue handling management is selected responsive to a position of at least one of the plurality of switches.

15. The dataflow chip of claim 14, wherein guaranteed bandwidth flow queue scheduling is handled on the dataflow chip and best effort flow queue scheduling is performed by the external scheduler chip.

16. The dataflow chip of claim 14, wherein internal or external flow queue handling management is selected responsive to channel identification information in a data packet.

17. The dataflow chip of claim 7, wherein at least one of the plurality of switches comprises an arbitration element, the arbitration element switch configured to dynamically arbitrate between an internal data packet received from an on-chip flow control handler and an external data packet received from the external scheduling chip.

18. The dataflow chip of claim 7, further comprising internal enqueue logic structures, wherein the internal enqueue logic structures are utilized in best effort flow queue scheduling for data packets received from the external scheduling chip.

19. The dataflow chip of claim 10, further comprising a round-robin LIFO buffer having a plurality of memory blocks ranked from highest to lowest priority;

first weight accumulation logic for best effort bandwidth scheduling; and

second weight accumulation logic for best effort bandwidth scheduling;

wherein the data flow chip is configured to provide best effort dispatching by;

applying the first weight accumulation logic and the second weight accumulation logic to a data packet;

selecting a memory block and placing the data packet into the selected memory block in the LIFO buffer responsive to relative amounts of first weight and second weight characteristics, wherein packets with the higher first weight relative to the second weight and placed in higher priority memory blocks; and

dropping data packets from the lowest priority memory blocks.

20. The dataflow chip of claim 1, wherein the plurality of on-chip data transmission circuit structures comprises:

a low latency external processor interface circuitry configured to provide privileged access to dataflow chip resources; and

a normal latency external processor interface circuitry configured to provide non-privileged access to dataflow chip resources.

21. The dataflow chip of claim 20 wherein the low latency interface is configured to enable control of data movement by software in scheduling, segmentation and reassembly processes directly from an external coprocessor.

22. The dataflow chip of claim 20 wherein the low latency interface circuitry uses normal latency interface circuitry transmit control logic but bypasses a main transmit data path from a data store to an output port.

23. A method for network processor dataflow processes, comprising the steps of:

providing a dataflow chip having a plurality of data transmission circuit structures and a plurality of scheduling circuit structures; and

selecting one of the plurality of data transmission circuit structures responsive to a data transmission selection indicator;

or

selecting one of the plurality of scheduling circuit structures responsive to a scheduling function selection indicator.

24. The method of claim 23, wherein the plurality of on-chip data transmission circuit structures comprises:

a plurality of selectable frame processing circuit structures; and

a plurality of selectable data transmission circuit structures.

25. The method of claim 24, further comprising the step of selecting a frame processing circuit structure responsive to the selection of one of a plurality of ingress port channels.

26. The method of claim 24, further comprising the step of selecting a frame processing circuit structure for a data packet responsive to a bit information received within the data packet.

27. The method of claim 24, wherein the plurality of selectable frame processing circuit structures comprises:

a cut and paste frame processing circuit structure;

a full dispatch frame processing circuit structure; and

a store and dispatch frame processing circuit structure.

28. The method of claim 27, further comprising the steps of:

the cut and paste frame processing circuit structure forwarding a frame header immediately to a processing unit while a body of a frame is received in a data store component and, after processing the frame, then reconnecting a modified header to the body in the data store;

the full dispatch frame processing circuit structure forwarding a full frame immediately to a processing unit without receiving the full frame in the data store an after processing the full frame, writing a full modified frame in the data store; and

the store and dispatch frame processing circuit structure receiving the full frame in the data store and dispatching an original frame header to the processing unit number and, after processing the full frame, writing a modified frame header back to the data store, the modified frame header replacing the original frame header.

29. The method of claim 24, wherein the plurality of scheduling circuit structures comprises:

a full internal scheduling circuit structure;

a calendar scheduling circuit structure in communication with an external scheduler chip; and

an external calendar scheduling circuit structure.

30. The method of claim 29, wherein the full internal scheduling circuit structure comprises calendar and queue control circuit structures, further comprising the steps of:

a plurality of dedicated physical memory areas located in data store blocks defining the calendar circuit structures; and

the dataflow chip driving the calendar and queue control circuit structures.

31. The method of claim 30, further comprising the steps of:

the full internal scheduling circuit structure comprising logic for internal calendar functions residing in a calendar page loader and a clock element,

the calendar circuit structures each comprising a plurality of calendar pages,

each of the plurality of calendar pages comprising a plurality of calendar entries; and

the dataflow chip reading a calendar page for each clock element tick.

32. The method of claim 31, further comprising the steps of:

the dataflow chip scheduler circuit structure providing a guaranteed bandwidth scheduling circuit structure; and

the dataflow chip scheduler circuit structure providing a best effort scheduling circuit structure.

33. The method of claim 29, further comprising the step of selecting the external scheduler chip from the group comprising a logic programmable FPGA chip, an ASIC fixed-logic chip, a high-speed processor, and a coprocessor.

34. The method of claim 29, further comprising the steps of:

providing a plurality of dataflow and logic paths; and

providing a plurality of switches to select dataflow and logic paths;

selecting the scheduling circuit structure responsive to positions of the plurality of switches.

35. The method of claim 34, further comprising the steps of:

dynamically selecting the positions of the plurality of switches responsive to data packet recognition.

36. The method of claim 34, further comprising the steps of:

selecting internal or external flow queue handling management responsive to a position of at least one of the plurality of switches.

37. The method of claim 36, further comprising the steps of:

the dataflow chip handling guaranteed bandwidth flow queue scheduling on-chip; and

the external scheduler chip performing best effort flow queue scheduling.

38. The method of claim 36, further comprising the step of selecting internal or external flow queue handling management responsive to channel identification information in a data packet.

39. The method of claim 29, further comprising the steps of:

a first of the plurality of switches comprising an arbitration element; and

the first switch arbitration element dynamically arbitrating between an internal data packet received from an on-chip flow control handler and an external data packet received from the external scheduling chip.

40. The method of claim 29, further comprising the step of utilizing internal enqueue logic structures in best effort flow queue scheduling for data packets received from the external scheduling chip.

41. The method of claim 32, further comprising the steps of:

providing a round-robin LIFO buffer having a plurality of memory blocks;

ranking the LIFO buffer memory blocks from highest to lowest priority; and

the data flow chip providing best effort dispatching by the steps of;

applying a first weight accumulation logic to a data packet to determine a first weight characteristic;

applying a second weight accumulation logic to the data packet to determine a second weight characteristic;

selecting one of the LIFO memory block responsive to relative amounts of first weight and second weight characteristics; and

placing the data packet into the selected memory block in the LIFO buffer, wherein data packets with higher first weight relative to the second weight are placed in higher priority memory blocks; and

dropping data packets from the lowest priority memory blocks.

42. The method of claim 23, wherein the plurality of on-chip data transmission circuit structures comprising a low latency external processor interface circuitry and a normal latency external processor interface circuitry:

the low latency external processor interface circuitry providing privileged access to dataflow chip resources; and

the normal latency external processor interface circuitry providing non-privileged access to dataflow chip resources.

43. The method of claim 42, further comprising the step of the low latency interface enabling control of data movement by software in scheduling, segmentation and reassembly processes directly from an external coprocessor.

44. The method of claim 42 further comprising the steps of:

the low latency interface circuitry using normal latency interface circuitry transmit control logic; and

the low latency interface circuitry bypassing a main transmit data path from a data store to an output port.