초록 ▼

A centralized arbitration mechanism provides that a router switch fabric is configured in a consistent fashion. Remotely distributed packet forwarding modules determine which data chunks are ready to go through the optical switch and communicates this to the central arbiter. Each packet forwarding

A centralized arbitration mechanism provides that a router switch fabric is configured in a consistent fashion. Remotely distributed packet forwarding modules determine which data chunks are ready to go through the optical switch and communicates this to the central arbiter. Each packet forwarding module has an ingress ASIC containing packet headers in roughly four thousand virtual output queues. Algorithms choose at most two chunk requests per chunk period to be sent to the arbiter, which queues up to roughly 24 requests per output port. Requests are sent through a Banyan network, which models the switch fabric and scales on the order of NlogN, where N is the number of router output ports. Therefore a crossbar switch function can be modeled up to the 320 output ports physically in the system, and yet have the central arbiter scale with the number of ports in a much less demanding way. An algorithm grants at most two requests per port in each chunk period and returns the grants to the ingress ASIC. Also for each chunk period the central arbiter communicates the corresponding switch configuration control information to the switch fabric.

대표청구항 ▼

What is claimed is: 1. A router system incorporating a router switch fabric and a single active central arbiter, said single active central arbiter comprising: an optical crossbar switch provided as the router switch fabric; a logic network that models said router switch fabric; an input logic bloc

What is claimed is: 1. A router system incorporating a router switch fabric and a single active central arbiter, said single active central arbiter comprising: an optical crossbar switch provided as the router switch fabric; a logic network that models said router switch fabric; an input logic block connected with an input terminal of said logic network; an output logic block connected to an output terminal of said logic network, wherein said output logic block is different from said input logic block; a plurality of request queues, each said request queue interconnected with said input logic block through a request pool; and a line shelf containing a plurality of router output ports and multiple packet forwarding modules, said packet forwarding modules being interconnected with said central arbiter through arbiter interfaces, wherein each of said packet forwarding modules contains multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor. 2. The router system of claim 1 wherein said central arbiter further comprises an ASIC, said ASIC incorporating said logic network. 3. The router system of claim 1 wherein said logic network contains a number of logic gates that scales no greater than NlogN, where N is the number of input ports of said logic network. 4. The router system of claim 3 wherein said logic network is a network. 5. The router system of claim 1 wherein said logic network is partitioned into a plurality of subplanes. 6. The router system of claim 1 wherein said central arbiter further comprises a switch configuration interface interconnected with said input logic block. 7. The router system of claim 1 wherein said router switch fabric comprises an optical crossbar switch, controlled by multiple arbiter interface ASICs, with the multiple arbiter interface ASICs controlled by said central arbiter. 8. The router system of claim 1 wherein said packet forwarding modules are interconnected with said arbiter interfaces through optical fiber cables. 9. The router system of claim 1 wherein said packet forwarding module contains aging counters interconnected with multiple virtual output queues. 10. The router system of claim 1 wherein said highest priority request selection processor comprises a round robin indicator. 11. The router system of claim 1 wherein said highest priority request selection processor comprises a scramble table configured to map said router output ports onto said multiple virtual output queues. 12. The router system of claim 11 wherein said highest priority request selection processor comprises an unscramble table configured to reverse the mapping of said scramble table. 13. The router system of claim 1 wherein said highest priority request selection processor comprises a chunk build instructions structure. 14. The router system of claim 1 wherein said highest priority request selection processor comprises a rate meter. 15. The router system of claim 1 wherein said virtual output queues are organized into guaranteed bandwidth quality of service (QOS) queues and best effort QOS queues. 16. The router system of claim 15 wherein said virtual output queues are organized such that 12 of said queues are allocated to each of said plurality of router output ports. 17. The router system of claim 16 wherein said router system comprises 320 of said router output ports. 18. The router system of claim 15 wherein said virtual output queues are organized such that 6 of said queues are allocated to each of said plurality of router output ports. 19. The router system of claim 18 wherein said router system comprises 640 of said router output ports. 20. The router system of claim 1 wherein each said packet forwarding module comprises an ASIC, said ASIC incorporating said virtual output queues and said highest priority request selection processor. 21. A router system incorporating an optical crossbar switch provided as a router switch fabric and a line shelf, said line shelf comprising a plurality of router output ports and multiple packet forwarding modules, each of said packet forwarding modules containing multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor, wherein aging counters are interconnected with multiple virtual output queues. 22. The router system of claim 21 wherein said highest priority request selection processor comprises a round robin indicator. 23. The router system of claim 21 wherein each said packet forwarding module comprises an ASIC, said ASIC incorporating said virtual output queues and said highest priority request selection processor. 24. The router system of claim 21 wherein said router switch fabric comprises an optical crossbar switch, controlled by multiple arbiter interface ASICs, with the multiple arbiter interface ASICs controlled by said central arbiter. 25. A router system incorporating an optical crossbar switch provided as a router switch fabric and a line shelf, said line shelf comprising a plurality of router output ports and multiple packet forwarding modules, each of said packet forwarding modules containing multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor, wherein said highest priority request selection processor comprises a scramble table configured to map said router output ports onto said multiple virtual output queues. 26. The router system of claim 25 wherein said highest priority request selection processor comprises an unscramble table configured to reverse the mapping of said scramble table. 27. A router system incorporating an optical crossbar switch provided as a router switch fabric and a line shelf, said line shelf comprising a plurality of router output ports and multiple packet forwarding modules, each of said packet forwarding modules containing multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor, wherein said highest priority request selection processor comprises a chunk build instructions structure. 28. A router system incorporating an optical crossbar switch provided as a router switch fabric and a line shelf, said line shelf comprising a plurality of router output ports and multiple packet forwarding modules, each of said packet forwarding modules containing multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor, wherein said highest priority request selection processor comprises a rate meter. 29. A router system incorporating an optical crossbar switch provided as a router switch fabric and a line shelf, said line shelf comprising a plurality of router output ports and multiple packet forwarding modules, each of said packet forwarding modules containing multiple virtual output queues, each said virtual output queue being connected to a highest priority request selection processor, wherein said virtual output queues are organized into guaranteed bandwidth quality of service (QOS) queues and best effort QOS queues. 30. The router system of claim 29 wherein said virtual output queues are organized such that 12 of said queues are allocated to each of said plurality of router output ports. 31. The router system of claim 30 wherein said router system comprises 320 of said router output ports. 32. The router system of claim 29 wherein said virtual output queues are organized such that 6 of said queues are allocated to each of said plurality of router output ports. 33. The router system of claim 32 wherein said router system comprises 640 of said router output ports. 34. A method of router central arbitration for a router having a router switch fabric and a plurality of output ports, said method comprising: a. providing an optical crossbar switch provided as the router switch fabric; b. storing incoming information packet address pointers in multiple virtual output queues; c. determining the priority of packet information in said multiple virtual output queues for requesting passage through said router switch fabric; d. based on said determining, sending requests for said passage to a central arbiter; e. buffering said requests at the input to said central arbiter; f. selecting buffered requests for arbitration by said central arbiter; g. passing said selected requests through a network that models said router switch fabric; h. accepting said passed requests in accordance with predetermined criteria; I. iterating steps 37-f, 37-g, and 37-h through the duration of a chunk period; and j. generating and delivering grant information based on a predetermined set of arbitration rules. 35. The method of claim 34, further comprising prior to said storing, mapping said packet address pointers randomly onto said multiple virtual output queues using a scramble table. 36. The method of claim 35, further comprising prior to sending said requests, reversing said mapping of said packet address pointers using an unscrambling table. 37. The method of claim 36, further comprising after delivering said grant information, mapping said packet address pointers onto said multiple virtual output queues using said scramble table. 38. The method of claim 34 wherein said multiple virtual output queues are organized into a plurality of guaranteed bandwidth quality of service (QOS) queues each having an allocated bandwidth and a plurality of best effort QOS queues. 39. The method of claim 38 wherein 12 best effort QOS queues of said plurality of best effort QOS queues represent packets destined for each of said plurality of output ports of said router system. 40. The method of claim 39 wherein said router system comprises 320 of said router output ports. 41. The method of claim 38 wherein said virtual output queues are organized such that 6 of said queues are allocated to each of said plurality of router output ports. 42. The method of claim 41 wherein said router system comprises 640 of said router output ports. 43. The method of claim 38 wherein said determining comprises: k. ensuring that a maximum allowable outstanding requests limit to said central arbiter is not exceeded; l. for the duration of a chunk period, ensuring that a maximum number of issued requests limit is not exceeded; m. for a guaranteed bandwidth queue, if said queue has content and has not exhausted its allocated bandwidth, then issuing a request to said central arbiter; and n. iterating steps 51-k, 51-l, and 51-m until the first to occur of exceeding maximum allowable outstanding requests limit, exceeding maximum number of issued requests limit, or iterating through all said guaranteed bandwidth queues. 44. The method of claim 43 wherein a maximum limit of 24 outstanding requests are allowable at any time. 45. The method of claim 43 wherein a maximum limit of two issued requests per chunk period are allowable. 46. The method of claim 43 wherein said allocated bandwidth is controlled by rate metering. 47. The method of claim 43 wherein said determining further comprises: o. if all guaranteed bandwidth queues have been iterated without exceeding said maximum allowable outstanding requests limit or said maximum number of issued requests limit, then for a best effort queue, if the packets within said best effort queue fill an information chunk, issuing a request; p. if said best effort queue has reached a time out limit, then issuing a request; and q. iterating steps 55-o and 55-p, until the first to occur of exceeding maximum allowable outstanding requests limit, exceeding maximum number of issued requests limit, or iterating through all said best effort queues. 48. The method of claim 47 wherein said information chunk is filled with approximately 400 bytes of packet information. 49. The method of claim 47 wherein said best effort queues are subdivided into first best effort queues, second best effort queues, and third best effort queues in order of decreasing priority, and wherein said iterating step 55-q is performed sequentially on all said first best effort queues, then on all said second best effort queues, and last on all said third best effort queues. 50. The method of claim 49 wherein said time out limit differs between respective first, second, and third best effort queues. 51. The method of claim 34 wherein said router switch fabric comprises an optical crossbar switch, controlled by multiple arbiter interface ASICs, with the multiple arbiter interface ASICs controlled by said central arbiter. 52. The method of claim 34 wherein said virtual output queues are contained in packet forwarding modules within said router system. 53. The method of claim 52 wherein said virtual output queues are contained in ASICs, which are incorporated into said packet forwarding modules. 54. The method of claim 53 wherein said information packet address pointers point to addresses of information packets stored in a RAM external to said ASICs. 55. The method of claim 34 wherein said sending of said requests to said central arbiter comprises transmitting said requests through an optical fiber cable. 56. The method of claim 34 wherein said buffering comprises dynamically filling a request pool to a predetermined capacity of stored requests. 57. The method of claim 56 wherein said predetermined capacity is on the order of eight stored requests. 58. The method of claim 56 wherein said selecting comprises extracting from each request pool of a plurality of such request pools no more than a request pool maximum limit of buffered requests, provided that no more than a network limit of buffered requests are extracted overall from said plurality of request pools, said selecting being performed at each iteration of an arbitration algorithm. 59. The method of claim 58 wherein said request pool maximum limit is two said buffered requests. 60. The method of claim 58 wherein passing said selected requests comprises passing said selected requests through a logic network having NlogN logic gates, wherein N is the number of said output ports. 61. The method of claim 60 wherein said logic network is a Banyan network. 62. The method of claim 61 wherein said Banyan network is partitioned into a plurality of subplanes, and wherein said network limit of buffered requests is one request per each said subplane. 63. The method of claim 62 wherein said plurality of subplanes comprises six subplanes. 64. The method of claim 58 wherein said plurality of request pools comprises five request pools. 65. The method of claim 58 wherein said selecting of said buffered requests is performed sequentially on said buffered requests in a request pool in the order in which said respective request was received in said request pool. 66. The method of claim 56 wherein said predetermined set of arbitration rules include selecting a maximum limit of requests for an entire request chunk period. 67. The method of claim 66 wherein said maximum limit is two requests per request pool for an entire chunk period. 68. The method of claim 34 wherein said predetermined criteria include availability of physical connection to said router switch fabric for a requested switch configuration and no more than two requests per chunk period destined for a single said output port. 69. A method of central arbitration for a router having a router switch fabric and a plurality of output ports, said method comprising: a. providing an optical crossbar switch provided as the router switch fabric; b. sending requests to a central arbiter for passage through said router switch fabric of data packets destined for each of said plurality of output ports; c. buffering said requests at the input to said central arbiter; d. selecting buffered requests for arbitration by said central arbiter; e. passing said selected requests through a network that models said router switch fabric; f. accepting said passed requests in accordance with predetermined criteria; g. iterating steps 72-d, 72-e, and 72-f through the duration of a chunk period; and h. generating and delivering grant information based on a predetermined set of arbitration rules. 70. The method of claim 69 wherein said router switch fabric comprises an optical crossbar switch, controlled by multiple arbiter interface ASICs, with the multiple arbiter interface ASICs controlled by said central arbiter. 71. The method of claim 69 wherein said sending of said requests to said central arbiter comprises transmitting said requests through an optical fiber cable. 72. The method of claim 69 wherein said buffering comprises dynamically filling a request pool to a predetermined capacity of stored requests. 73. The method of claim 72 wherein said predetermined capacity is on the order of eight stored requests. 74. The method of claim 72 wherein said selecting comprises extracting from each request pool of a plurality of such request pools no more than a request pool maximum limit of buffered requests, provided that no more than a network limit of buffered requests are extracted overall from said plurality of request pools, said selecting being performed at each iteration of an arbitration algorithm. 75. The method of claim 74 wherein said request pool maximum limit is two said buffered requests. 76. The method of claim 74 wherein passing said selected requests comprises passing said selected requests through a logic network having NlogN logic gates, wherein N is the number of said output ports. 77. The method of claim 76 wherein said logic network is a Banyan network. 78. The method of claim 77 wherein said Banyan network is partitioned into a plurality of subplanes, and wherein said network limit of buffered requests is one request per each said subplane. 79. The method of claim 78 wherein said plurality of subplanes comprise six subplanes. 80. The method of claim 74 wherein said plurality of request pools comprises five request pools. 81. The method of claim 74 wherein said selecting of said buffered requests is performed sequentially on said buffered requests in a request pool in the order in which said respective request was received in said request pool. 82. The method of claim 72 wherein said predetermined set of arbitration rules include selecting a maximum limit of requests for an entire request chunk period. 83. The method of claim 82 wherein said maximum limit is two requests per request pool for an entire chunk period. 84. The method of claim 69 wherein said predetermined criteria include availability of physical connection to said router switch fabric for a requested switch configuration and no more than two requests per chunk period destined for a single said output port. 85. A method of central arbitration for an optical crossbar switch provided as a router having a router switch fabric, a plurality of packet forwarding modules, and a plurality of output ports, said method comprising a first stage of distributed arbitration on said packet forwarding modules and a second stage of global arbitration on a central arbiters such that said first stage issues requests to said second stage for grants to pass data chunks through said router switch fabric, wherein arbitration congestion in said second stage is limited in said first stage by an algorithm using information from the time delay between the issue of a request in said first stage and the receipt in the first stage of a corresponding grant from said second stage. 86. A method of central arbitration for an optical crossbar switch provided as a router having a router switch fabric, a plurality of packet forwarding modules, and a plurality of output ports, said method comprising a first stage of distributed arbitration on said packet forwarding modules and a second stage of global arbitration on a central arbiter, such that said first stage issues requests to said second stage for grants to pass data chunks through said router switch fabric, wherein said first stage further comprises storing information packet headers in a plurality of virtual output queues (VOQs). 87. The method of claim 86 wherein arbitration congestion in said second stage due to synchronization is reduced in said first stage by mapping said plurality of output ports onto said VOQs using a scramble table. 88. The method of claim 86 wherein a portion of said information packet headers are stored in preprovisioned guaranteed bandwidth (GB) VOQs that are rate limited thereby providing guaranteed bandwidth requests. 89. The method of claim 88 wherein a portion of said information packet headers are stored in best effort (BE) VOQs, thereby providing best effort requests. 90. The method of claim 89 wherein requests for said GB data chunks are allowed to pass ahead of requests for said BE chunks in said second stage. 91. The method of claim 89 wherein said issued requests are processed iteratively through subplanes in said second stage, such that if physical routing resources are consumed by first request, if a second request for said routing resources is non-accepted in a subsequent request, and a logic block in said second stage knows an alternate routing path that would allow said non-accepted request to be accepted, then said logic block can return said non-accepted request with a hint specifying which of said subplanes would allow said non-accepted request to be accepted. 92. The method of claim 91 wherein said hinted indicator is used as the highest priority criterion in processing of said requests through said second stage. 93. The method of claim 89 further comprising maintaining a first count of all outstanding requests to said second stage, an independent second count of outstanding best effort requests only, and a third count of outstanding guaranteed bandwidth requests only. 94. The method of claim 93 wherein said first stage further comprises: a. ensuring that a maximum allowable outstanding requests limit to said second stage is not exceeded; b. for the duration of a chunk period, ensuring that a maximum number of issued requests limit to said second stage is not exceeded; c. for a guaranteed bandwidth queue, if said queue has content and has not exhausted its allocated bandwidth, then issuing a request to said second stage; and d. iterating steps 96-a, 96-b, and 96-c until the first to occur of exceeding said maximum allowable outstanding requests limit, exceeding maximum number of issued requests limit, or iterating through all said guaranteed bandwidth queues. 95. The method of claim 94 wherein said first stage further comprises: e. if all guaranteed bandwidth queues have been iterated without exceeding said maximum allowable outstanding requests limit or said maximum number of issued requests limit, then for a best effort queue, if the packets within said best effort queue fill an information chunk, issuing a request; f. if said best effort queue has reached a time out limit, then issuing a request; and g. iterating steps 97-e and 97-f until the first to occur of exceeding said maximum allowable outstanding requests limit, exceeding said maximum number of issued requests limit, or iterating through all said best effort queues. 96. The method of claim 95 wherein said best effort queues are subdivided into first best effort queues, second best effort queues, and third best effort queues in order of decreasing priority, and wherein said iterating step 97-g is performed sequentially on all said first best effort queues, then on all said second best effort queues, and last on all said third best effort queues, such that requests issued by said best effort queues in order of decreasing priority are respectively first, second, and third best effort requests. 97. The method of claim 96 wherein said time out limit differs between respective first, second, and third best effort queues. 98. The method of claim 96 wherein said issued requests in said second stage are stored in a plurality of request pools, such that best effort requests in the same request pool with the same source and destination are assigned priorities to be processed in said second stage in the order received in said request pool, provided that if a higher priority best effort request is newly received in said request pool already containing a previously received lower priority best effort request, then the priority of said previously received best effort request is increased to the priority level of said higher priority newly received best effort request. 99. A method of central arbitration for a router having an optical crossbar switch provided as a router switch fabric, a plurality of packet forwarding modules, and a plurality of output ports, said method comprising a first stage of distributed arbitration on said packet forwarding modules and a second stage of global arbitration on a central arbiter, such that said first stage issues requests to said second stage for grants to pass data chunks through said router switch fabric, wherein up to a predetermined maximum number of multi-chunk requests are processed concurrently in said second stage, each said multi-chunk request corresponding to a packet exceeding a data capacity of a single chunk. 100. A method of central arbitration for a router having an optical crossbar switch provided as a router switch fabric, a plurality of packet forwarding modules, and a plurality of output ports, said method comprising a first stage of distributed arbitration on said packet forwarding modules and a second stage of global arbitration on a central arbiter, such that said first stage issues requests to said second stage for grants to pass data chunks through said router switch fabric, wherein said second stage models a higher order network with iterating on a lower order network.