Multiserver scheduling system and method for a fast switching element

• US 20020176431A1
• Filed: 01/28/2002
• Published: 11/28/2002
• Est. Priority Date: 02/17/2001
• Status: Active Grant

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Yang, Mei, Damm, Gerard, Cankaya, Hakki Candan, Xiong, Yijun, Blanton, John, Verchere, Dominique, Golla, Prasad N.
• Granted Patent: US 7,023,840 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• 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/3045 Virtual queuing
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance

Abstract

A scheduling system and methodology for use in a network switch element having multiserver, multiple-arbiter architecture. Ingress ports and egress ports coupled to the cross-connect fabric of the network element are provided with multiple ingress and egress arbiters, respectively, for effectuating an iterative arbitration strategy such as RGA or RG. Arbiter architectures include singe-arbiter-per-port; single-arbiter-per-server; multiple-arbiters-per-port; and multiple-arbiters-per-server arrangements, wherein the arbiters can be implemented using RRA, BTA, Flexible Ring, or any other arbiter technology. Depending on the iteration strategy, ingress arbiter architecture and egress arbiter architecture, a variety of iterative, multiserver-capable scheduling algorithms can be obtained, which scheduling algorithms can also be implemented in QoS-aware network nodes.

Claims

1. A network element having a switching apparatus for switching information between a plurality of ingress ports and a plurality of egress ports via a cross-connect matrix disposed therebetween, comprising:

a plurality of ingress servers associated with each of said ingress ports, said ingress servers operating to serve a plurality of virtual output queues (VOQs) supported by a corresponding ingress port;

a plurality of egress servers associated with each of said egress ports, each of said egress servers operating to serve outgoing traffic supported by a corresponding egress port;

at least one ingress arbiter associated with each of said ingress ports and at least one egress arbiter associated with each of said egress ports, said at least one ingress arbiter and egress arbiter for effectuating a particular type of arbitration; and

a scheduler operating to configure said cross-connect matrix for transporting a plurality of transmission units from at least one of said ingress ports to at least one of said egress ports during each time slot associated with said cross-connect matrix, wherein said scheduler effectuates a particular scheduling mechanism based at least in part upon an ingress arbiter architecture, an egress arbiter architecture and a predetermined arbitration iteration strategy.

2. The network element as set forth in claim 1, wherein said ingress arbiter architecture comprises a single arbiter per port arrangement.

3. The network element as set forth in claim 1, wherein said ingress arbiter architecture comprises a multiple arbiters per port arrangement.

4. The network element as set forth in claim 1, wherein said egress arbiter architecture comprises a single arbiter per port arrangement.

5. The network element as set forth in claim 1, wherein said egress arbiter architecture comprises a multiple arbiters per port arrangement.

6. The network element as set forth in claim 1, wherein said at least one ingress arbiter comprises a binary tree arbiter.

7. The network element as set forth in claim 6, wherein said binary tree arbiter is a reverting binary tree arbiter.

8. The network element as set forth in claim 6, wherein said binary tree arbiter is a non-reverting binary tree arbiter.

9. The network element as set forth in claim 1, wherein said at least one ingress arbiter comprises a round robin arbiter.

10. The network element as set forth in claim 1, wherein said at least one ingress arbiter comprises a flexible ring arbiter.

11. The network element as set forth in claim 1, wherein said at least one egress arbiter comprises a binary tree arbiter.

12. The network element as set forth in claim 11, wherein said binary tree arbiter is a reverting binary tree arbiter.

13. The network element as set forth in claim 11, wherein said binary tree arbiter is a non-reverting binary tree arbiter.

14. The network element as set forth in claim 1, wherein said at least one egress arbiter comprises a round robin arbiter.

15. The network element as set forth in claim 1, wherein said at least one egress arbiter comprises a flexible ring arbiter.

16. The network element as set forth in claim 1, wherein said predetermined arbitration iteration strategy includes a Request-Grant (RG) iteration strategy.

17. The network element as set forth in claim 1, wherein said predetermined arbitration iteration strategy includes a Request-Grant-Accept (RGA) iteration strategy.

18. The network element as set forth in claim 1, wherein requests associated with said VOQs are classified based on an internal priority condition.

19. The network element as set forth in claim 18, wherein said internal priority condition includes an age alarm.

20. The network element as set forth in claim 18, wherein said internal priority condition includes a “

queue full”

alarm.

21. The network element as set forth in claim 1, wherein said VOQs are classified based on a predetermined number of levels of a Quality of Service (QoS)-related priority condition.

22. The network element as set forth in claim 21, wherein each of said plurality of ingress servers and each of said plurality of egress servers are associated with a predetermined number of ingress arbiters and egress arbiters, respectively, said predetermined number of ingress and egress arbiters equaling said predetermined number of levels of said QoS-based priority condition.

23. The network element as set forth in claim 21, wherein each of said plurality of ingress ports and each of said plurality of egress ports are associated with a predetermined number of ingress arbiters and egress arbiters, respectively, said predetermined number of ingress and egress arbiters equaling said predetermined number of levels of said QoS-based priority condition.

24. The network element as set forth in claim 1, wherein each of said plurality of ingress servers is associated with a corresponding ingress arbiter and each of said plurality of egress servers is associated with a corresponding egress arbiter, said network element further including means to desynchronize initialization of said ingress arbiters and said egress arbiters at the beginning of each time slot.

26. The scheduling system as set forth in claim 25, wherein said L1 scheduler partition includes a plurality of ingress arbiters, each corresponding to a particular QoS priority level.

27. The scheduling system as set forth in claim 26, wherein each of said ingress servers per said ingress port is associated with said plurality of ingress arbiters.

28. The scheduling system as set forth in claim 26, wherein each of said ingress ports is associated with said plurality of ingress arbiters.

29. The scheduling system as set forth in claim 26, wherein said ingress arbiters are comprised of round robin arbiters.

30. The scheduling system as set forth in claim 26, wherein said ingress arbiters are comprised of binary tree arbiters.

31. The scheduling system as set forth in claim 25, wherein said L2 scheduler partition includes a plurality of egress arbiters, each corresponding to a particular QoS priority level.

32. The scheduling system as set forth in claim 31, wherein each of said egress servers per said egress port is associated with said plurality of egress arbiters.

33. The scheduling system as set forth in claim 31, wherein each of said egress ports is associated with said plurality of egress arbiters.

34. The scheduling system as set forth in claim 31, wherein said egress arbiters are comprised of round robin arbiters.

35. The scheduling system as set forth in claim 31, wherein said egress arbiters are comprised of binary tree arbiters.

36. The scheduling system as set forth in claim 25, wherein said L1 scheduler partition includes means for prioritizing said requests based on an internal subpriority condition.

37. The scheduling system as set forth in claim 36, wherein said internal subpriority condition includes an age alarm.

38. The scheduling system as set forth in claim 36, wherein said internal subpriority condition includes a “

queue full”

alarm.

39. The scheduling system as set forth in claim 25, wherein said arbitration iteration strategy comprises a Request-Grant (RG) iteration strategy.

40. The scheduling system as set forth in claim 25, wherein said arbitration iteration strategy comprises a Request-Grant-Accept (RGA) iteration strategy.

25. A scheduling system for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queue groups (VOQ groups), each of said VOQ groups having sub-queues therein based on a Quality of Service (QoS) priority level, said scheduling system comprising:

a first level (L1) scheduler partition operable to generate requests in accord with an arbitration iteration strategy used in computing matches between said ingress servers and said egress servers, said requests being organized based on said QoS priority level; and

a second level (L2) scheduler partition operating, in response to said requests assembled by said first level scheduler partition, to generate a scheduling matrix at each slot time associated with said cross-connect fabric, said scheduling matrix identifying matches between at least a portion of said ingress servers and a portion of said egress servers.

41. A scheduling methodology for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queues (VOQs), said scheduling methodology comprising the steps:

for each matrix cycle associated with said cross-connect fabric, initializing a scheduling matrix and a request matrix, said request matrix for building requests associated with an arbitration iteration strategy used in computing matches between said ingress servers and egress servers;

performing an arbitration iteration to obtain a current match matrix;

updating said request matrix and said scheduling matrix based on said current match matrix;

if all of said plurality of ingress servers associated with a particular ingress port are matched, removing requests, issuing from said particular ingress port, from said request matrix;

if all of said plurality of egress servers associated with a particular egress port are matched, removing requests, directed to said particular egress port, from said request matrix;

resetting said current match matrix and performing next arbitration iteration using said updated request matrix; and

upon encountering a particular stop condition, terminating further iterations and forwarding said updated scheduling matrix to a controller for configuring at least one connection path in said cross-connect fabric based on said updated scheduling matrix so as to effectuate transfer of transmission units between matched ingress and egress servers.

42. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration strategy comprises a Request-Grant (RG) iteration strategy.

43. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration strategy comprises a Request-Grant-Accept (RGA) iteration strategy.

44. The scheduling methodology as set forth in claim 41, wherein said particular stop condition includes determining if no new matches were found in said next arbitration iteration.

45. The scheduling methodology as set forth in claim 41, wherein said particular stop condition includes determining if said updated request matrix is a null matrix.

46. The scheduling methodology as set forth in claim 41, wherein said particular stop condition includes determining if a predetermined maximum number of iterations has been reached.

47. The scheduling methodology as set forth in claim 41, wherein said particular stop condition includes determining if an iteration timeout has been reached.

48. The scheduling methodology as set forth in claim 41, wherein said requests are prioritized based an internal priority condition.

49. The scheduling methodology as set forth in claim 48, wherein said internal priority condition includes an age alarm.

50. The scheduling methodology as set forth in claim 48, wherein said internal priority condition includes a “

queue full”

alarm.

51. The scheduling methodology as set forth in claim 41, wherein said requests are classified based on a predetermined number of levels of a Quality of Service (QoS)-related priority condition.

52. The scheduling methodology as set forth in claim 41, wherein said transmission units include variable length Internet Protocol (IP) packets.

53. The scheduling methodology as set forth in claim 41, wherein said transmission units include fixed length cells.

54. The scheduling methodology as set forth in claim 41, wherein said transmission units include protocol data units (PDUs).

55. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration is performed in accord with a multiserver, iterative SLIP algorithm.

56. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration is performed in accord with a multiserver, iterative Ping Pong algorithm.

57. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration is performed in accord with a multiserver, iterative dual round robin algorithm.

58. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration is performed in accord with a multiserver, flexible ring dual round robin algorithm.

59. The scheduling methodology as set forth in claim 41, wherein said arbitration iteration is performed in accord with a multiserver, prioritized dual round robin algorithm.