Method and apparatus for supplying requests to a scheduler in an input buffered multiport switch

• US 6,160,812 A
• Filed: 05/04/1998
• Issued: 12/12/2000
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Anderson, Eric T., Bauman, James A.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/072,147
• Time in Patent Office: 953 Days
• Field of Search: 370/229, 370/230, 370/412, 370/415, 370/418, 370/419, 370/395, 370/398, 370/422, 370/428, 370/429, 710/36, 710/39, 710/40, 710/49, 710/50
• US Class Current: 370/416
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/352 Gigabit ethernet switching [GBPS]
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus for supplying new requests to a scheduler in an input-buffered multiport switch involve selecting a request that does not target output channels that conflict with output channels targeted by requests that are already accessible to the scheduler. Specifically, target output channels of requests that are presently accessible to the scheduler are identified and compared to target output channels of requests that are included in a queue of next-in-line requests. The queue of next-in-line requests is reviewed and the highest priority request having no conflicting output channels is supplied to the scheduler. By supplying the scheduler with a new request that targets non-conflicting output channels, the scheduler is presented with a wider range of requested output channels from which to choose in each arbitration cycle. In a first embodiment, one, two, or eight ports are connected to each one of four input/output controllers in a switch having a four-channel switch fabric. To supply the scheduler with new requests, secondary arbitration is performed on a channel-specific basis in order to supply channel-specific requests to the scheduler. The method of supplying requests to the scheduler can be scaled to include multiple channels and multiple packet priority designations.

Claims

1. A method of supplying requests to a scheduler of a multiport switch having a plurality of outputs, said scheduler having access to a plurality of first output requests, said method comprising the steps of:

maintaining a queue of second output requests that are not accessible by said scheduler, each second output request being indicative of at least one target output;

determining which outputs are target outputs of said first output requests that are accessible by said scheduler;

selecting a highest priority request of said second output requests at least partially based on identifying a particular second output request for which indicated target outputs are mutually exclusive with said target outputs of said first output requests; and

providing access of said highest priority request to said scheduler.

2. The method of claim 1 further comprising steps of:

arbitrating between said first output requests that are accessible by said scheduler;

issuing grants to said first output requests when targeted outputs are available; and

forwarding packets that are related to granted first output requests through said multiport switch.

3. The method of claim 1 wherein said step of selecting a highest priority request includes a step of assigning a continuum of time-based priority indicators to each said second output request such that a second output request having an oldest time-based priority indicator has a highest priority and a second output request having a youngest time-based priority indicator has a lowest priority.

4. The method of claim 1 wherein said step of selecting further includes a step of sequencing a priority indicator among said second output requests.

5. The method of claim 1 wherein said step of selecting said highest priority request includes a step of assigning said highest priority to a request when said request is the oldest request of said second output requests and said request is for multiple outputs even if one of said target outputs is not mutually exclusive with said target outputs of said first output requests.

6. The method of claim 1 wherein said step of selecting said highest priority request includes additional steps of determining if there are more than one request from a same input that are requesting overlapping outputs and that are being bridged, and assigning said highest priority, in succession, to said requests from said same input even if one of said target outputs is not mutually exclusive with said target outputs of said first output requests.

7. A multiport packet switching system having a multi channel switch fabric, a data path multiplexer and a scheduler, wherein said scheduler grants requests for forwarding packets through said multiport packet switching system comprising:

means for queuing second output channel requests that are inaccessible by said scheduler;

means for determining which output channels are target output channels of first output channel requests that are accessible by said scheduler;

means for determining a highest priority request maintained in said queuing means that is indicative of only target output channels that are different than said target output channels of said first output channel requests; and

means for delivering said highest priority request to a location that is accessible by said scheduler when said scheduler is free to access a new request.

8. The system of claim 7 wherein each switch fabric channel is operatively associated with an independent arrangement of said means for queuing, said means for determining requested output channels, said means for determining a highest priority request, and said means for delivering.

9. The system of claim 7 wherein said meains for queuing includes a separate request queue for each input port in said multiport packet switching system.

10. The system of claim 9 wherein said means for determining a highest priority request is responsive to more than one of said separate request queues.

11. The system of claim 7 wherein said means for determining which output channels are target output channels of said first output channel requests is responsive to a multilevel request buffer that is connected in parallel to said scheduler.

12. The system of claim 7 wherein said means for queuing includes separate request buffers for requests that are prioritized by application type.

13. A method of supplying requests to a scheduler in a multiport switch that has a switch fabric with a plurality of switching channels and output ports associated with said switching channels comprising the steps of:

identifying output channels targeted by any first requests from a particular switching channel that are available to said scheduler for arbitration;

comparing said identified output channels to output channels that are targeted by second requests from said particular switching channel that are not available to said scheduler for arbitration; and

making available to said scheduler a second request that does not target an output channel that is the same as one of said identified output channels targeted by any of said first requests, said second request being one of said second requests from said particular switching channel that are not available to said scheduler for arbitration before being made available to said scheduler.

14. The method of claim 13 where said step of making available includes identifying and accessing a highest priority request from said requests.

15. The method of claim 14 wherein said step of identifying and accessing said highest priority request includes a step of determining said highest priority request based on comparing time indicators related to said second requests.

16. The method of claim 13 wherein said step of making available is preceded by:

determining if the number of said first requests meets a minimum request threshold;

if said minimum request threshold is not met and if there are no second requests that target only output channels that are different from said identified output channels, making available to said scheduler a highest priority second request even if said highest priority second request targets an output channel that is the same as one of said identified output channels; and

overriding said step of making available to said scheduler a second request that does not target an output channel that is the same as one of said identified output channels.

17. The method of claim 13 wherein said step of making available is preceded by a step of receiving an indication that said scheduler is free to access a new request.

18. The method of claim 13 wherein said step of identifying output channels includes a step of accessing said first requests from a multi-level request queue in which said queue is connected in parallel to said scheduler.

19. The method of claim 18 further including steps of:

arbitrating between said first requests from said multi-level request queue;

issuing grants on a priority basis to said first requests from said multi-level request queue when requested output channels are available; and

forwarding packets that are related to granted first requests through said multiport switch.

20. The method of claim 13 further including a step of maintaining a request queue for each port of said multiport switch and wherein said step of comparing includes a step of arbitrating between second requests from all queues related to ports of said particular switching channel.