Combined unicast and multicast scheduling

• US 6,212,182 B1
• Filed: 06/27/1996
• Issued: 04/03/2001
• Est. Priority Date: 06/27/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McKeown, Nicholas W.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/673,216
• Time in Patent Office: 1,741 Days
• Field of Search: 370/355, 370/386, 370/388, 370/389, 370/390, 370/395, 370/398, 370/411, 370/412, 370/415, 370/416, 370/428, 370/429, 370/445, 370/447, 370/432, 359/117, 359/128, 359/135, 359/139, 709/213, 709/238, 709/240
• US Class Current: 370/390
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities

Abstract

The invention provides a method and system for combined unicast and multicast scheduling. Data cells are assigned at each input, to one unicast input queue for each output, or to a single multicast input queue. Each input makes two requests for scheduling to each output for which it has a queued data cell, one unicast request and one multicast request. Each output grants up to one request, choosing highest priority requests first, giving precedence to one such highest priority request using an output precedence pointer, either an individual output precedence pointer which is specific to that output for unicast data cells, or a group output precedence pointer which is generic to all outputs for multicast data cells. Each input accepts up to one grant for unicast data cells, or as many grants as possible for multicast data cells, choosing highest priority grants first, giving precedence to one such highest priority grant using an input precedence pointer. In a preferred embodiment, the individual output precedence pointers each implement a round-robin precedence technique, in which the most recent input to transmit a data cell has the lowest precedence; the pointer is incremented to point to a next input each time a data cell is transmitted from the pointed-to input. The input precedence pointers each preferably implement an identical precedence technique. However, the group output precedence pointer is not incremented until all outputs from the multicast data cell for the pointed-to input have been transmitted.

Claims

1. A system for scheduling unicast and multicast cells in a nonblocking switch having a plurality of inputs and a plurality of outputs, said cells each having a designated output and a priority, said system including

a plurality of unicast input queues at each input;

a multicast input queue at each input;

means for each one input to request service, at a scheduling time, from said designated outputs for cells queued at said one input;

means for each output to grant requests responsive to said priority and responsive to a grant precedence for said requests utilizing a pointer; and

means for each input to accept grants responsive to said priority and responsive to an accept precedence for said grant utilizing a pointer.

2. A system as in claim 1, wherein said cells are of substantially uniform size.

3. A system as in claim 1, wherein said means for each one input to request service is operative to make one said request for a unicast cell and one said request for a multicast cell.

4. A system as in claim 1, wherein said means to grant requests is operative to grant requests for a higher priority cell in preference to requests for a lower priority cell.

5. A system as in claim 1, wherein said grant precedence at each said output is responsive to an individual grant precedence pointer for unicast cells and responsive to a group grant precedence pointer for multicast cells.

6. A system as in claim 1, wherein said grant precedence is responsive to whether requests are for unicast cells or for multicast cells.

7. A system as in claim 1, wherein said grant precedence is operative to prefer unicast cells at a first set of times and is operative to prefer multicast cells at a second set of times.

8. A system as in claim 1, wherein said means to accept grants is operative to accept grants for a higher priority cell in preference to requests for a lower priority cell.

9. A system as in claim 1, wherein said accept precedence at each said input is responsive to an accept precedence pointer for unicast cells.

10. A system as in claim 1, wherein said means to accept grants at said one input is operative to accept substantially all grants for multicast cells to be transmitted by said one input.

11. A system as in claim 1, wherein said means to accept grants at said one input is operative to accept all grants for multicast cells to be transmitted by said one input, except only for higher priority grants for unicast cells.

12. A system as in claim 1, wherein said accept precedence is responsive to whether requests are for unicast cells or for multicast cells.

13. A system as in claim 1, wherein said accept precedence is operative to prefer unicast cells at a first set of times and is operative to prefer multicast cells at a second set of times.

14. A system as in claim 1, including

means for scheduling inputs having accepted grants and outputs associated with said accepted grants; and

means for retriggering said means to request service, said means to grant requests, and said means to accept grants, for inputs and outputs not already scheduled.

15. A system as in claim 14, wherein said means for retriggering is operative a selected number of times.

16. A system as in claim 14, wherein said means for retriggering is operative until a selected time.

17. A method for scheduling unicast and multicast cells in a nonblocking switch having a plurality of inputs and a plurality of outputs, said cells each having a designated output and a priority, said method including the steps of, at a scheduling time,

requesting service for each one input from said designated outputs for unicast and multicast cells queued at said one input;

granting requests for each output responsive to said priority and responsive to a grant precedence pointer for said requests; and

accepting grants for each input responsive to said priority and responsive to an accept precedence pointer for said grant.

18. A method as in claim 17, wherein said cells are of substantially uniform size.

19. A method as in claim 17, wherein said step of requesting service is operative to make one said request for a unicast cell and one said request for a multicast cell, to each one output.

20. A method as in claim 17, wherein said step of granting requests is operative to grant requests for a higher priority cell in preference to requests for a lower priority cell.

21. A method as in claim 17, wherein said grant precedence at each said output is responsive to an individual grant precedence pointer for unicast cells and responsive to a group grant precedence pointer for multicast cells.

22. A method as in claim 17, wherein said grant precedence is responsive to whether requests are for unicast cells or for multicast cells.

23. A method as in claim 17, wherein said grant precedence is operative to prefer unicast cells at a first set of times and is operative to prefer multicast cells at a second set of times.

24. A method as in claim 17, wherein said step of accepting grants is operative to accept grants for a higher priority cell in preference to requests for a lower priority cell.

25. A method as in claim 17, wherein said accept precedence at each said input is responsive to an accept precedence pointer for unicast cells.

26. A method as in claim 17, wherein said step of accepting grants at said one input is operative to accept substantially all grants for multicast cells to be transmitted by said one input.

27. A method as in claim 17, wherein said accept precedence is responsive to whether requests are for unicast cells or for multicast cells.

28. A method as in claim 17, wherein said accept precedence is operative to prefer unicast cells at a first set of times and is operative to prefer multicast cells at a second set of times.

29. A method as in claim 17, including the steps of

scheduling inputs having accepted grants and outputs associated with said accepted grants; and

reperforming said step of requesting service, said step of granting requests, and said step of accepting grants, for inputs and outputs not already scheduled.

30. A method as in claim 29, wherein said step of reperforming is operative a selected number of times.

31. A method as in claim 29, wherein said step of reperforming is operative until a selected time.

32. In an input-queued system for scheduling unicast and multicast cells in a nonblocking switch having a plurality of inputs and a plurality of outputs, said cells each having a designated output and a priority, a memory including

a plurality of unicast input queues at each input;

a multicast input queue at each input;

at each said input, an accept precedence pointer indicative of one of said outputs;

at each said output, an individual grant precedence pointer indicative of one of said inputs; and

a group grant precedence pointer indicative of one of said inputs.

33. A memory as in claim 32, further including at each one input a request for service from said designated outputs for cells queued at said one input.

34. A memory as in claim 33, including one said request for a unicast cell and one said request for a multicast cell.

35. A memory as in claim 33, further including at each output a grant of service, said grant of service having been generated responsive to said priority and responsive to said individual grant precedence pointer and said group grant precedence pointer.

36. A memory as in claim 35, said grant of service having been generated responsive to said individual grant precedence pointer for unicast cells and responsive to said group grant precedence pointer for multicast cells.

37. A memory as in claim 35, said grant of service having been generated responsive to whether requests are for unicast cells or for multicast cells.

38. A memory as in claim 35, further including at each input an acceptance of grant, said acceptance of grant having been generated responsive to said priority and responsive to said accept precedence pointer.

39. A memory as in claim 38, including one said acceptance of grant for substantially all grants for multicast cells to be transmitted by said one input.

40. A memory as in claim 38, said acceptance of grant having been generated responsive to said accept precedence pointer for unicast cells.

41. A memory as in claim 38, said acceptance of grant having been generated responsive to whether requests are for unicast cells or for multicast cells.