Method and apparatus for allocating link bandwidth

0001The present invention relates generally to a method and system for allocating bandwidth over a shared link, and more particularly to such methods and systems that streamline protocol processing and maintain quality of service guarantees.

BACKGROUND

0002<figref idref="DRAWINGS">FIG. 1</figref> shows a typical switching system <b>10</b> for managing traffic of packets of information over a network backbone. The system <b>10</b> contains one or more input ingresses I<b>1</b>, I<b>2</b>, I<b>3</b>, one or more output egresses E<b>1</b>, E<b>2</b>, E<b>3</b>, and a switch or crossbar <b>12</b>. Three ingresses I<b>1</b>, I<b>2</b>, I<b>3</b> and three egresses E<b>1</b>, E<b>2</b>, E<b>3</b> are depicted in <figref idref="DRAWINGS">FIG. 1</figref>, although any number of ingresses and egresses can be connected in the switching system <b>10</b>. Packets of data enter the ingresses I<b>1</b>, I<b>2</b>, I<b>3</b> through traffic sources <b>14</b> and exit from the egresses E<b>1</b>, E<b>2</b>, E<b>3</b>, through traffic exits <b>16</b>. In typical operation, the switching system <b>10</b> can connect a given ingress to a given egress through the crossbar or switch <b>12</b> such that there is a one-to-one mapping between an ingress and egress, or it can connect a given ingress to one or more egresses such that there is a one-to-many mapping between ingresses and egresses. In other words, for every timeslot for transfer of data through the switching system <b>10</b>, each egress can only receive data from a single ingress. However, an ingress can send data to multiple egresses. Further, each ingress I<b>1</b>, I<b>2</b>, I<b>3</b>, contains a plurality of queues for storing packets of data and each egress E<b>1</b>, E<b>2</b>, E<b>3</b> contains a plurality of buffer FIFOS (First-In-First-Out). For each timeslot, a single queue within each ingress can be connected to one or more ports within one or more egresses. For example, during a given timeslot, queue Q<b>2</b> within ingress I<b>1</b> can be connected to buffer FIFO<b>1</b> within egress E<b>3</b>, queue Q<b>1</b> within ingress I<b>2</b> can be connected to buffer FIFO<b>1</b> within egress E<b>1</b>, and queue Q<b>1</b> within ingress I<b>3</b> can be connected to buffer FIFO<b>3</b> of egress E<b>2</b>.

0003Generally, one goal of a switching system, such as the system <b>10</b> of <figref idref="DRAWINGS">FIG. 1</figref>, is to maximize usage of the switch or crossbar <b>12</b> such that its valuable bandwidth (a so-called scarce resource) is used efficiently. A second goal of switching systems can be to service packets for customers depending on Quality-of-Service (QoS) guarantees. Another goal of switching systems can be to prevent certain packets from being queued in the switching system for unacceptably long periods of time prior to transmission through the system <b>10</b>. A need exists for accomplishing these goals with improved methods and systems.

0004The size of a timeslot for data transfer across the switch or crossbar <b>12</b> in the switching system <b>10</b> of <figref idref="DRAWINGS">FIG. 1</figref> generally determines the amount of data that can be sent in a single timeslot. Two methods are commonly used to select the size of a timeslot for data transfer in currently implemented switching systems, such as the system <b>10</b> of <figref idref="DRAWINGS">FIG. 1</figref>, where packet sizes vary considerably. The first method is to use a timeslot size that is sufficiently large so that most packets of information in the queues can be transmitted through the switch or crossbar <b>12</b> during a given timeslot. A problem with such a method, however, is low utilization of the system <b>10</b>. Portions of each timeslot will likely not be filled, and hence the available bandwidth, which is generally costly, will not be used.

0005The second method used to select timeslot size is to use a timeslot size that is smaller than that used in the first method. Then, however, packets that are larger than the timeslot must be broken into more than one segment so that each segment will fit through the switching system <b>10</b> in a single timeslot. This second method may reduce the low utilization problem associated with the first method discussed above; however, it requires that the packets be broken (segmented) into multiple segments at an ingress I<b>1</b>, I<b>2</b>, I<b>3</b> and then rebuilt (reassembled) at an egress E<b>1</b>, E<b>2</b>, E<b>3</b>. Such segmentation and reassembly can constrain the performance of the switching system <b>10</b>.

0006A need exists for a method and system for allocating bandwidth over a link that properly allocates the bandwidth to maximize utilization of bandwidth, ensure QoS guarantees, and prevent packets from being queued indefinitely in a switching system while, at the same time, ensuring that the method and system operate in a “fair” manner. Finally, a need exists for a method and system for maximizing utilization of a timeslot for data transfer without causing a segmentation and reassembly problem.

SUMMARY

0007One embodiment of the invention relates to a method for selecting a packet for transmission across a shared link. In this embodiment, the method features determining a priority for a first-out packet in each of a plurality of queues within each of a plurality of ingresses, for each group of first-out packets within the queues of each ingress which are destined for a particular egress, selecting a first-out packet having a first priority; for each subset of selected first-out packets having first priorities and being destined for the particular egress, selecting a first-out packet having a second priority; and transmitting from each ingress across the shared link the selected first-out packet having the second priority.

0008Another embodiment of the invention relates to a method for selecting a queue for service across a shared link. In this embodiment, the method features determining a priority for each queue within a plurality of ingresses, wherein the priority is instantaneous for a given timeslot for data transfer; for each group of queues within the plurality of ingresses having packets destined for a particular egress, selecting a queue having a first priority; and servicing the selected queue having the first priority for each group across the shared link in the given timeslot.

0009Another embodiment of the invention relates to a method for selecting a queue for service across a shared link. In this embodiment, the method features determining a priority for each queue within a plurality of ingresses, wherein the priority is instantaneous for a given timeslot for data transfer; for each group of queues within each ingress having packets destined for a particular egress, selecting a queue having a first priority; for each subset of selected queues having first priorities and having packets destined for the particular egress, selecting a queue having a second priority, and servicing the selected queue having the second priority for each subset across the shared link in the given timeslot

0010Another embodiment of the invention relates to a system for selecting a queue for service across a shared link. In this embodiment, the system features a metering module within an ingress to (a) determine a priority for each queue within the ingress, wherein the priority is instantaneous for a given timeslot for data transfer, and (b) for each group of queues within the ingress having packets destined for a particular egress, select a queue having a first priority, and an arbitration module to select a queue having a second priority from each subset of selected queues having first priorities and having packets destined for the particular egress, the selected queue having the second priority being the queue for service across the shared link in the given timeslot.

0011Another embodiment of the invention is a computer-readable medium storing instructions that direct a microprocessor to determine a priority for each queue within a plurality of ingresses, wherein the priority is instantaneous for a given timeslot for data transfer, for each group of queues within each ingress having packets destined for a particular egress, select a queue having a first priority, for each subset of selected queues having first priorities and having packets destined for the particular egress, select a queue having a second priority, and service the selected queue having the second priority for each subset across the shared link in the given timeslot.

0012Another embodiment of the invention relates to a system for selecting a queue for service across a shared link. In this embodiment, the system features an element for determining a priority for each queue within a plurality of ingresses, wherein the priority is instantaneous for a given timeslot for data transfer; an element for selecting a queue having a first priority for each group of queues within each ingress having packets destined for a particular egress; an element for selecting a queue having a second priority for each subset of selected queues having first priorities and having packets destined for the particular egress; and an element for servicing the selected queue having the second priority for each subset across the shared link in the given timeslot.

0013Another embodiment of the invention relates to a method for selection of a queue for service across a shared link, wherein each queue has a priority for data transfer that is instantaneous for a given timeslot. In this embodiment, the method features receiving from each ingress information regarding at least one queue having a first priority selected from each group of queues within each ingress having packets destined for a particular egress; selecting a queue having a second priority from each subset of selected queues having first priorities and having packets destined for the particular egress; and selecting the queue having the second priority for service across the shared link in the given timeslot.

0014Yet another embodiment of the invention relates to an apparatus for selection of a queue for service across a shared link, wherein each queue has a priority for data transfer that is instantaneous for a given timeslot. In this embodiment, the apparatus features a memory storing a program and a processor in communication with the memory; in which the processor is directed by the program to: receive from each ingress information regarding at least one queue having a first priority selected from each group of queues within each ingress having packets destined for a particular egress, select a queue having a second priority from each subset of selected queues having first priorities and having packets destined for the particular egress, and select the queue having the second priority for service across the shared link in the given timeslot.

0015Another embodiment of the invention relates to a computer-readable medium for selection of a queue for service across a shared link, wherein each queue has a priority that is instantaneous for a given timeslot for data transfer. The computer-readable medium in this embodiment stores instructions that direct a microprocessor to: receive from each ingress information regarding at least one queue having a first priority selected from each group of queues within each ingress having packets destined for a particular egress, select a queue having a second priority from each subset of selected queues having first priorities and having packets destined for the particular egress, and select the queue having the second priority for service across the shared link in the given timeslot.

0016Another embodiment of the invention is a method for selecting a queue for service across a shared link. In this embodiment, the method features determining a priority for each queue within a plurality of ingresses, wherein the priority is instantaneous for a given timeslot for data transfer. The method then features, within each ingress, for each group of queues having packets destined for a particular port of a particular egress, selecting a queue having a first priority. The queues in the group can have varying classes of service. Next, within an arbiter chip, for each subset of selected queues having first priorities and having packets destined for the same particular egress, selecting a queue having a second priority. This selection can be from queues having packets bound for different ports of the same particular egress. Next, within the arbiter chip, for each subset of selected queues from the plurality of ingresses having second priorities and having packets destined for the same particular egress, selecting a queue having a third priority. Finally, the method features servicing the selected queue having the third priority for each subset across the shared link in the given timeslot.

0017Another embodiment of the invention relates to a method for apportioning bandwidth across a shared link. In this embodiment, the method features maintaining queue metric information for each queue of a group of queues, calculating a guaranteed rate for each queue based on the queue metric information and a guaranteed bandwidth amount for the group of queues, adjusting a credit value associated with each queue by (a) adjusting the credit value of the queue by an appropriate amount if the queue is serviced in a given timeslot, and (b) adjusting the credit value of the queue by an amount based on the guaranteed rate after the given timeslot; and using queue state information selected from one or more of the group consisting of the credit value, partial packet information, a shaping limit, and an indication of whether the queue is empty, to determine a priority for the queue, the priority acting to apportion bandwidth.

0018Another embodiment of the invention relates to a method for guaranteeing bandwidth for an egress of a shared link system. In this embodiment, the method features maintaining information regarding a queue metric for each queue in a group of queues with packets destined for the egress, wherein the queues reside within one or more ingresses of the shared link system, calculating a guaranteed rate for each queue in the group of queues based on the queue metric information and a guaranteed bandwidth amount for the egress, and using the guaranteed rate to calculate a credit value for each queue in the group of queues, wherein the credit values are used to allocate bandwidth.

0019Another embodiment of the invention relates to a method for guaranteeing bandwidth for an ingress of a shared link system. In this embodiment, the method includes maintaining information regarding a queue metric for each queue in a group of queues within the ingress, wherein packets within the queues are destined for one or more egresses of the shared link system, calculating a guaranteed rate for each queue in the group of queues based on the queue metric information and a guaranteed bandwidth amount for the ingress, and using the guaranteed rate to calculate a credit value for each queue in the group of queues, wherein the credit values are used to allocate bandwidth.

0020Another embodiment of the invention relates to a method for determining a guaranteed rate for use in apportioning bandwidth across a shared link. In this embodiment, the method features maintaining information regarding a queue metric for each queue in a group of queues, calculating a guaranteed rate for each queue in the group of queues based on the queue metric information and a guaranteed bandwidth amount for the group of queues, and sending the guaranteed rate to an ingress associated with each queue, wherein the guaranteed rates are used to apportion bandwidth.

0021Another embodiment of the invention relates to an apparatus for determining a guaranteed rate for use in apportioning bandwidth across a shared link. In this embodiment, the apparatus includes a memory storing a program and a processor in communication with the memory; in which the processor is directed by the program to: maintain information regarding a queue metric for each queue in a group of queues; calculate a guaranteed rate for each queue in the group of queues based on the queue metric information and a guaranteed bandwidth amount for the group of queues; and send the guaranteed rate to an ingress associated with each queue, wherein the guaranteed rates are used to apportion bandwidth.

0022Another embodiment of the invention relates to a method for apportioning bandwidth across a shared link. In this embodiment, the method features determining information regarding a queue metric for each queue in a group of queues, transmitting the queue metric information to a bandwidth allocator module, receiving a guaranteed rate for each queue in the group from the bandwidth allocator module, adjusting a credit value associated with each queue by (a) decrementing the credit value of the queue by an appropriate amount if the queue is serviced in a given timeslot, and (b) incrementing the credit value of the queue by an amount based on the guaranteed rate of the queue after the given timeslot; and determining a priority for each queue in the group using the credit values, the priorities acting to allocate bandwidth.

0023Another embodiment of the invention relates to a method for apportioning bandwidth across a shared link. In this embodiment, the method features calculating a guaranteed rate for each queue in at least one ingress based on queue metric information and a guaranteed bandwidth amount, calculating a priority for each queue to connect with the shared link in a given timeslot, the priority for each queue being instantaneous for the given timeslot and being based on the guaranteed rate for each queue, and determining at least one queue to service during the given timeslot based on the priority of each queue.

0024Another embodiment of the invention relates to a system for apportioning bandwidth across a shared link. In this embodiment, the system features a bandwidth allocator module to calculate a guaranteed rate for each queue in at least one ingress based on queue metric information and a guaranteed bandwidth amount, a metering module in each ingress to calculate a priority for each queue in the ingress to connect with the shared link in a given timeslot, the priority for each queue being instantaneous for the given timeslot and being based on the guaranteed rate for each queue, and an arbitration module to determine at least one queue to service during the given timeslot based on the priority of each queue.

0025Another embodiment of the invention relates to a system for apportioning bandwidth across a shared link. In this embodiment, the system features an ingress chip containing a plurality of queues and a metering module to calculate a priority for each queue in the ingress chip to connect with the shared link in a given timeslot, the priority for each queue being instantaneous for the given timeslot and being based on a guaranteed rate for each queue; and an arbiter chip containing: (a) a bandwidth allocator module to calculate the guaranteed rate for each queue within one or more ingress chips based on queue metric information and a guaranteed bandwidth amount, and (b) an arbitration module to determine at least one queue to service during the given timeslot based on the priority of each queue.

0026Another embodiment of the invention relates to a method for apportioning bandwidth across a shared link. In this embodiment, the method features maintaining information regarding a queue metric for each queue in a group of queues; calculating a guaranteed rate for each queue in the group of queues based on the queue metric information and a guaranteed bandwidth amount for the group of queues; sending the guaranteed rate for each queue to an ingress associated with each queue, wherein each ingress is capable of calculating a priority for each queue in the ingress using the guaranteed rate for the queue; receiving from each ingress information regarding at least one queue having a first priority selected from each group of queues within each ingress having packets destined for a particular egress; selecting a queue having a second priority for each subset of queues having first priorities and having packets destined for the particular egress; and selecting the queue having the second priority for service across the shared link in the given timeslot.

0027Another embodiment of the invention relates to a method for apportioning bandwidth across a shared link. In this embodiment, the method features determining information regarding a queue metric for each queue within an ingress; transmitting the queue metric information to a bandwidth allocator module; receiving a guaranteed rate for each queue from the bandwidth allocator module, the guaranteed rate calculated at least in part using the queue metric information; adjusting a credit value associated with each queue by (a) decrementing the credit value of the queue by an appropriate amount if the queue is serviced in a given timeslot, and (b) incrementing the credit value of the queue by an amount based on the guaranteed rate of the queue after the given timeslot; determining a priority for each queue within the ingress, wherein the priority is instantaneous for the given timeslot; for each group of queues within the ingress having packets destined for a particular egress, selecting at least one queue having a first priority, sending to an arbitration module information regarding each queue within the ingress having a first priority; and receiving from the arbitration module information regarding a queue having a second priority, wherein the queue having the second priority determines with which egress the ingress will communicate during the given timeslot.

0028Another embodiment of the invention relates to a method for servicing queues across a shared link. In this embodiment, the method features ascertaining the size of a first-out packet for each queue within an ingress, and if the size of the first-out packet in each queue is too large for transmission across the shared link in a single given timeslot for data transfer, maintaining a connection to the shared link when the queue having the first-out packet is selected for data transfer such that the entire first-out packet is transferred across the shared link in two or more timeslots for data transfer.

0029Yet another embodiment of the invention relates to a method for determining a priority for each queue of a plurality of queues in a system, wherein the priorities determine allocation of bandwidth across a shared link and the queue having the highest priority is served during a given timeslot. In this embodiment, the method involves, if the queue contains a partial packet, setting the priority to a maximum priority; if the queue is empty, setting the priority to a minimum priority; and if the queue has a credit value that is greater than zero, determining the priority to be a rounded number between the maximum priority and the minimum priority equal to the credit value divided by a scaling factor.

BRIEF DESCRIPTION OF THE DRAWINGS

0030<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of a prior art switching system.

0031<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of one embodiment of the system of the invention.

0032<figref idref="DRAWINGS">FIG. 3A</figref> is a block diagram of one embodiment of the arbiter chip, ingress chip, and queue manager of the invention.

0033<figref idref="DRAWINGS">FIG. 3B</figref> is a block diagram showing packets of data within queues of an ingress.

0034<figref idref="DRAWINGS">FIG. 4A</figref> is a flow chart showing one embodiment of the methods of the invention.

0035<figref idref="DRAWINGS">FIG. 4B</figref> is a flow chart showing one embodiment of the methods of the invention in greater detail than <figref idref="DRAWINGS">FIG. 4A</figref>.

0036<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart illustrating one embodiment of the calculation of bandwidth rates for three different types of bandwidth allocation.

0037<figref idref="DRAWINGS">FIG. 6A</figref> is a block diagram illustrating one embodiment of bandwidth allocation at a single egress.

0038<figref idref="DRAWINGS">FIG. 6B</figref> is a block diagram illustrating a second embodiment of bandwidth allocation at a single egress.

0039<figref idref="DRAWINGS">FIG. 7A</figref> is a block diagram illustrating one embodiment of bandwidth allocation at a single ingress.

0040<figref idref="DRAWINGS">FIG. 7B</figref> is a block diagram illustrating one embodiment of bandwidth allocation for a group of queues.

0041<figref idref="DRAWINGS">FIG. 8</figref> is a flow chart showing the adjustment of credit values used for bandwidth allocation in one embodiment of the invention.

0042<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram illustrating one embodiment of a queue selection scheme of the invention.

0043<figref idref="DRAWINGS">FIG. 10</figref> is a flow chart illustrating a second embodiment of a queue selection method.

0044<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of another embodiment of a queue selection scheme.

DETAILED DESCRIPTION

0000A. General Overview

0045The embodiments of the invention provide for configurable, weighted, and distributed scheduling methods and systems that can be used to implement QoS guarantees for data transfer and to fairly determine which queue to service during a given timeslot.

00001. System Architecture

0046<figref idref="DRAWINGS">FIG. 2</figref> shows a block diagram of a system <b>100</b> according to an embodiment of the invention. The system <b>100</b> of <figref idref="DRAWINGS">FIG. 2</figref> contains a number of modular components, which, in one embodiment, are chips. The system <b>100</b> of <figref idref="DRAWINGS">FIG. 2</figref> contains one or more ingress chips <b>102</b>, one or more egress chips <b>104</b>, an arbiter chip <b>106</b>, and a shared switch or crossbar chip or link <b>108</b> that can connect any ingress <b>102</b> to any egress <b>104</b> using pipelines <b>110</b>. In addition, each ingress <b>102</b> can have associated therewith a forwarding engine or queue manager <b>112</b>. Packets of data enter the ingresses <b>102</b> from traffic sources <b>114</b> and exit the egresses <b>104</b> to traffic outputs <b>116</b>. A plurality of ingresses <b>102</b> can be linked to a plurality of egresses <b>104</b> over the shared link <b>108</b>. For example, in one embodiment, sixty-four ingresses <b>102</b> can be linked to sixty-four egresses over the shared link <b>108</b>.

0047The embodiments described below operate in a shared link system, which is a system having a shared link <b>108</b> connecting one or more ingresses <b>102</b> to one or more egresses <b>104</b>. For every timeslot for transfer of data through the system <b>100</b>, each egress <b>104</b> can only be connected to a single ingress <b>102</b>, although a single ingress <b>102</b> can be connected to one or more egresses <b>104</b>. Throughout this specification, therefore, the term “shared link system” will be used to refer to a system through which one or more egresses can be connected to a single ingress to transfer data during a given timeslot. The term “shared link,” similarly, will be used throughout this specification to refer to the linking device, switch, or crossbar that is configurable for each timeslot for data transfer and is used in the shared link system to connect one or more egresses to a single ingress to transfer data.

0048In an embodiment using chips as the molecular components of the invention, each chip can be an integrated circuit chip having a signal processing unit and an interface unit. The signal processing unit can run at any speed sufficient to perform the operations described herein. In one embodiment, for example, a 1 GHz processor is used in the arbiter chip <b>106</b>. The functions of each module of the invention can be performed in software or in hardware. <figref idref="DRAWINGS">FIG. 3A</figref> depicts an ingress chip <b>102</b> having register files <b>158</b>, and such an ingress chip <b>102</b> can have hardware or firmware modules therein to perform the functions of the invention.

0049Each traffic source <b>114</b> connected to each ingress <b>102</b> and each traffic output <b>116</b> connected to each egress <b>104</b> has an associated bandwidth rate, such as 10 Gbps. In one embodiment, each pipeline <b>110</b> connecting an ingress <b>102</b> or an egress <b>104</b> to the shared link <b>108</b> has an associated bandwidth rate that is larger than the traffic source <b>114</b> bandwidth rate or traffic output <b>116</b> bandwidth rate. The pipelines <b>110</b>, therefore, can be high-speed links. For example, if the bandwidth rate of traffic source <b>114</b> into an ingress <b>102</b> is 10 Gbps, the pipeline associated therewith to connect to the shared link <b>108</b> can have a bandwidth rate of 10-20 Gbps. In such an embodiment, the system <b>100</b> of the invention is able to make bandwidth guarantees over the shared link <b>108</b> due in part to the fast pipelines <b>110</b> into and out of the link <b>108</b> compared to the bandwidth rates into the ingresses <b>102</b> or out from the egresses <b>104</b>. In other embodiments, the pipelines <b>110</b> have bandwidth rates that are the same as the traffic source <b>114</b> or traffic output <b>116</b> bandwidth rates.

0050<figref idref="DRAWINGS">FIG. 3A</figref> is a block diagram of one embodiment showing a single arbiter chip <b>106</b>, ingress chip <b>102</b>, and forwarding engine or queue manager <b>112</b> of the invention. In one embodiment, the arbiter chip <b>106</b> contains a bandwidth allocator module <b>150</b> and an arbitration module <b>152</b>. Depicted in <figref idref="DRAWINGS">FIG. 3A</figref> in the ingress <b>102</b> is a metering module <b>154</b>, which includes a priority computation module <b>156</b>, register files <b>158</b>, a metering update module <b>160</b>, and a queue length module <b>162</b>. In one embodiment, the bandwidth allocator module <b>150</b> and the arbitration module <b>152</b> reside within the ingress <b>102</b>, as can the queue manager <b>112</b>. In a system with multiple ingresses <b>102</b> attached to a shared link <b>108</b>, such as the system <b>100</b> of <figref idref="DRAWINGS">FIG. 2</figref>, it can be desirable to have the bandwidth allocator module <b>150</b> and the arbitration module <b>152</b> in a separate arbiter chip <b>106</b> such that a single arbiter chip <b>106</b> is used to service a plurality of ingresses <b>102</b>. The functions of each module are described in detail below.

0051The embodiment of <figref idref="DRAWINGS">FIG. 3A</figref> depicts a single ingress <b>102</b> and a single arbitrator chip <b>106</b>. More typically, however, a single arbitrator chip <b>106</b> is used in a system with multiple ingresses <b>102</b>, such as the system <b>100</b> of <figref idref="DRAWINGS">FIG. 2</figref>.

0052Each ingress <b>102</b> of the system <b>100</b> contains a plurality of buffer queues. <figref idref="DRAWINGS">FIG. 2</figref> depicts ingresses <b>102</b>, each having four queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b>, although any number of queues can be in each ingress <b>102</b>. In one embodiment, an ingress chip <b>102</b> contains 1024 queues. Associated with each queue is a class of service (COS) for that queue. Each COS refers to a different level of service for the packets in the queue associated with that COS. For example, queue Q<b>1</b> in each ingress <b>102</b> of <figref idref="DRAWINGS">FIG. 2</figref> has COS<b>1</b>, queue Q<b>2</b> has COS<b>2</b>, queue Q<b>3</b> has COS<b>3</b>, and queue Q<b>4</b> has COS<b>4</b>. COS<b>1</b> can be associated with a bandwidth rate of 1 gigabytes per second (Gbps), COS<b>2</b> can have a bandwidth rate of 0.25 Gbps, and so forth, such that the packets in queues with different COSs are serviced at different rates. As packets of data enter each ingress <b>102</b>, the packets are buffered in an appropriate queue corresponding to the COS for that packet. Each packet in a queue is destined for a particular, but not necessarily the same, egress (i.e., the packet contains data indicating that it desires to be sent to that egress). A forwarding engine <b>111</b> associated with each ingress <b>102</b> can route packets of data entering the ingress <b>102</b> to an appropriate queue within the ingress <b>102</b>.

0053Each egress <b>103</b> of system <b>100</b> generally contains a number of FIFO (First-In-FIrst-Out) buffers or ports to buffer packets received through the shared link <b>108</b> before the packets are sent out through the traffic outputs <b>116</b>. In one embodiment of the invention, a single chip can function as either an ingress <b>102</b> or as an egress <b>104</b>. Such a chip would contain an ingress side that could perform the functions of an ingress <b>102</b>, as described below, and an egress side with FIFOs to perform the functions of an egress <b>104</b>.

0054<figref idref="DRAWINGS">FIG. 3B</figref> shows a detailed view of packets within queues of ingress <b>102</b>. <figref idref="DRAWINGS">FIG. 3B</figref> shows a single ingress <b>102</b> having queues Q<b>1</b>, Q<b>2</b>, and Q<b>3</b>, although, as noted above, a larger number of queues may reside within an ingress <b>102</b>. As <figref idref="DRAWINGS">FIG. 3B</figref> depicts in simplified visual form, each queue Q<b>1</b>, Q<b>2</b>, Q<b>3</b> contains a number of packets buffered within the queue. For instance, queue Q<b>1</b> contains packets <b>170</b>, <b>172</b>, and <b>173</b>, queue Q<b>2</b> contains packets <b>174</b>, <b>176</b>, <b>178</b>, and <b>180</b>, and queue Q<b>3</b> contains packets <b>182</b>, <b>184</b>, <b>186</b>, <b>188</b>, <b>190</b>, and <b>192</b>. At the head of queue Q<b>1</b> is packet <b>170</b>, at the head of queue Q<b>2</b> is packet <b>174</b>, and at the head of queue Q<b>3</b> is packet <b>182</b>. In accordance with this embodiment, in each timeslot in which data will be sent over the shared link <b>108</b> of the system <b>100</b> of the invention, only the packet or packets at the head of each queue (a first-out packet or packets) that fit within a single timeslot are eligible to contend for access to the shared link <b>108</b>. For the next timeslot, for the depiction of <figref idref="DRAWINGS">FIG. 3B</figref>, therefore, only packets <b>170</b>, <b>174</b>, and <b>182</b> are available to contend for access to the shared link <b>108</b>. A timeslot is a fixed unit of time, and in each timeslot the shared link <b>108</b> can be configured for data transfer. In one embodiment, the timeslot can be set to about 200-650 nanoseconds, although the timeslot size can vary in different embodiments. Approximately 460-1,500 bytes of data can be transferred over the shared link <b>108</b> in a 200-650 nanoseconds timeslot in the illustrated embodiment.

0055<figref idref="DRAWINGS">FIG. 3B</figref> also illustrates in block form that packets within the queues of an ingress <b>102</b> can be of varying size, and the size of the queues within an ingress <b>102</b> can also vary in size. For example, packet <b>170</b> in queue Q<b>1</b> has a packet size that is larger than packet <b>174</b> in queue Q<b>2</b>, and also larger than packet <b>182</b> in queue Q<b>3</b>. In addition, packet <b>182</b> in queue Q<b>3</b> is also larger in size than packet <b>174</b> in queue Q<b>2</b>. Such packet sizes can be measured in bytes or in bits. <figref idref="DRAWINGS">FIG. 3B</figref> also shows the size of a single timeslot, in this embodiment, for data transfer across the shared link <b>108</b>. Packet <b>170</b> is larger in size than a single timeslot, while packet <b>174</b> and packet <b>182</b> both appear to be smaller than or equal to the size of a single timeslot. Finally, <figref idref="DRAWINGS">FIG. 3B</figref> depicts the size of each queue (Qlength), at a particular instant in time, within the ingress <b>102</b>. For example, queue Q<b>1</b> has QlengthQ<b>1</b> that is larger than QlengthQ<b>2</b> for queue Q<b>2</b>, but smaller than QlengthQ<b>3</b> for queue Q<b>3</b>. <figref idref="DRAWINGS">FIG. 3B</figref> depicts a simplified ingress <b>102</b> where only a small number of packets reside within each queue, but the concept of Qlengths is illustrated. A Qlength is a measure of the size of the data stored at a particular instant in time within a given queue, and can therefore be measured in bytes. Note that in the embodiment illustrated in <figref idref="DRAWINGS">FIG. 3B</figref>, each queue has the same total length (capacity) available for buffering of packets, although in other embodiments, these lengths may also vary.

00002. Overview of System Operation

0056<figref idref="DRAWINGS">FIG. 4A</figref> is a flow chart showing one embodiment of the operation of the invention. Generally, the invention involves calculating a guaranteed rate for each queue based on queue metric information for the queue (block <b>200</b>), calculating a priority for each queue during a given timeslot (block <b>202</b>) based on the guaranteed rate for the queue, and determining a queue to service during a given timeslot based on the priority of each queue (block <b>204</b>).

0057As used throughout this specification, a “guaranteed rate” generally refers to an update rate for a queue that is used to allocate bandwidth in a system The unit of such a guaranteed rate may be, for instance, Gbps. The guaranteed rates control the bandwidth available to each queue since they are used to control the rate at which a credit value associated with each queue increases with time. Each queue of each ingress has a credit value associated with it, and the guaranteed rate for each queue can be used to increase the credit value for the queue if the queue is not serviced during a given timeslot. The credit values, in turn, can be used to update a priority for each queue in the system. As used throughout this specification, a “priority” refers to the desire of a given queue to communicate with a given egress during a timeslot for data transfer. Generally, therefore, the queue to be serviced during each timeslot is determined based on the priorities calculated for each queue during each timeslot. Queues having high priorities for communication with a given egress, for instance, will be serviced before queues having lower priorities for communication with that same egress. The shared link <b>108</b> of <figref idref="DRAWINGS">FIG. 2</figref> is reconfigured for each timeslot based on the priorities to assign a one-to-one mapping between ingresses and egresses. The guaranteed rates, therefore, indirectly control how often each queue is serviced or, alternatively, how often a subset of queues is serviced.

0058The bandwidth allocator module <b>150</b> is used, in this embodiment, to calculate the guaranteed rate for each queue in the system <b>100</b> (block <b>200</b> of <figref idref="DRAWINGS">FIG. 4A</figref>). The guaranteed rates are calculated according to a number of methods using some queue metric information received from the queue length module <b>162</b> or the queue manager <b>112</b>. The queue metric information used to calculate the guaranteed rates is information about the queue, such as, but not limited to, the Qlength of the queue (i.e., bytes) or the arrival rate (i.e., bytes per second) of data to the queue. The queue manager <b>112</b> can calculate or track arrival rate information of data to the queue, and the queue length module <b>162</b> can calculate the current length or size of the queue. Some methods for calculation of guaranteed rates are discussed in greater detail below in connection with <figref idref="DRAWINGS">FIGS. 5-7B</figref>. Generally, to calculate a guaranteed rate, the queue length module <b>162</b> (or the queue manager <b>112</b>) of <figref idref="DRAWINGS">FIG. 3A</figref> measures and sends queue metric information for each queue of the corresponding ingress <b>102</b> to the bandwidth allocator module <b>150</b>. <figref idref="DRAWINGS">FIG. 3A</figref>, for instance, depicts the Qlengths <b>50</b> for the queues being sent to the bandwidth allocator module <b>150</b>. Using the bandwidth allocation methods discussed below, the bandwidth allocator module <b>150</b> then calculates a guaranteed rate for each queue of each ingress <b>102</b> of the system <b>100</b>, and sends the guaranteed rates <b>52</b> to the corresponding ingress <b>102</b>. These guaranteed rates can be calculated periodically (i.e., not necessarily each timeslot) and then periodically communicated to the corresponding ingress <b>102</b>.

0059The meter update module <b>160</b> of the metering module <b>154</b> of each ingress <b>102</b>, in this embodiment, then uses the guaranteed rates to update a credit value for each queue in the ingress <b>102</b>. The meter update module <b>160</b>, on one embodiment, updates a credit value for each queue during every timeslot for data transfer across the shared link <b>108</b>. <figref idref="DRAWINGS">FIG. 3A</figref> depicts the meter update module <b>160</b> receiving the guaranteed rates <b>52</b> from the bandwidth allocator module <b>150</b> through the register files <b>158</b>, and then transmitting the updated credit values <b>54</b> to the register files <b>158</b>. The credit values <b>54</b> or other information about the queues are used to calculate priorities for service of each queue in this embodiment. The credit values can be updated in the meter update module <b>160</b> according to a number of methods. Generally, the credit value for a given queue is increased if the queue after each timeslot. The increase of the credit value increases the corresponding priority for the queue, thus incrementing the priority of the queue over a number of timeslots so that the queue will eventually be serviced. In this embodiment, if the queue is serviced during a given timeslot, the credit value for the queue is decreased so that the connection to the shared link <b>108</b> will not be maintained indefinitely (i.e., the priority for the queue is decreased). A number of methods can be used to update credit values for queues, and one such method is discussed below in greater value in connection with <figref idref="DRAWINGS">FIG. 8</figref>.

0060In this embodiment, the priority computation module <b>156</b> of the metering module <b>154</b> of the ingress <b>102</b> uses the credit values or other information about the queues to calculate a priority (block <b>202</b> of <figref idref="DRAWINGS">FIG. 4A</figref>) with which each queue desires to be serviced over the shared link <b>108</b>. <figref idref="DRAWINGS">FIG. 3A</figref> depicts the priority computation module <b>156</b> receiving the credit values <b>54</b> for the queues of the ingress <b>102</b> from the register files <b>158</b> and then sending priorities <b>56</b> to the arbitration module <b>152</b>. The priority for each queue can be, in one embodiment, the same value as the credit value for each queue. In other embodiments, however, the priority is a scaled version of the credit value for each queue, and the priority can also be modified beyond a simple scaling depending on other characteristics, as is discussed further below.

0061Certain of the priorities <b>56</b> from a given ingress <b>102</b> are sent to the arbitration module <b>152</b> in this embodiment, as shown in <figref idref="DRAWINGS">FIG. 3A</figref>. In addition, each egress <b>104</b> sends information on the fullness state of its FIFOs to the arbitration module <b>152</b>. The arbitration module <b>152</b> then determines the ingress <b>102</b> that will be connected to each egress <b>104</b> during a given timeslot (block <b>204</b> of <figref idref="DRAWINGS">FIG. 4A</figref>). The arbitration module <b>152</b> sends an output <b>58</b> back to the priority computation module <b>156</b>, as seen in <figref idref="DRAWINGS">FIG. 3A</figref>. Output <b>58</b> can simply be a designation of which egress <b>104</b> the ingress <b>102</b> will have access to during a given timeslot. The metering module <b>154</b> can then determine which queue in the ingress <b>102</b> to service, based on the egress <b>104</b> to which the ingress <b>102</b> has access during the timeslot.

0062The selection of an ingress <b>102</b> for each egress <b>104</b> in the arbitration module <b>152</b> is based on priorities, and this selection process can be referred to as arbitration. Generally, the priorities <b>56</b> determine which ingress <b>102</b> to connect to which egress <b>104</b> during a given timeslot, and which queue within an ingress to service during that timeslot. In one embodiment, the ingress <b>102</b> with a queue that desires a given egress <b>104</b> with the greatest priority is chosen for connection to the given egress <b>104</b> during a timeslot. In addition, a queue within that selected ingress <b>102</b> that desires the egress <b>104</b> and has the greatest priority is the queue within that ingress <b>102</b> that is serviced during the timeslot. Some methods used for queue selection in various embodiments of the invention are discussed further below in connection with <figref idref="DRAWINGS">FIGS. 9-11</figref>. In any event, configuration of the shared link <b>10</b> for the timeslot in accordance with the ingress <b>102</b> to egress <b>104</b> mappings follows arbitration. A message containing instructions (not shown in Figures) is therefore sent to the shared link <b>108</b> each timeslot to indicate the mapping between ingress and egress that the shared link <b>108</b> should produce. The shared link <b>108</b> then establishes a connection between ingresses and egresses for the timeslot in accordance with the instructions.

0063In one embodiment of the invention, a maximum priority level is reserved for a queue with a packet contained therein that is larger than a single timeslot. <figref idref="DRAWINGS">FIG. 3B</figref>, for example, shows that packet <b>170</b> has a size that is larger than a given timeslot. In one embodiment of the invention, a connection over the shared link <b>108</b> of the system <b>100</b> is maintained for a sufficient period of time such that an entire packet that is larger than a single timeslot can be transferred continuously over the shared link <b>108</b> without interruption. Such a maintained connection ensures that a packet need not be segmented into multiple packets in an ingress <b>102</b> and then reassembled at an egress <b>104</b> after all of the segments of the packet are transmitted over the link <b>108</b>. Such a system maximizes utilization of the shared link <b>108</b> by allowing the size of a timeslot to be set at an appropriate length of time. That is, the timeslot size for data transfer is set at a low enough level such that utilization of the shared link <b>108</b> is high. This method of the invention, however, also solves the segmentation and reassembly problem by maintaining single or multiple connections over the shared link <b>108</b> to transfer packets larger than a single timeslot.

0064A partial packet variable can be used by the system of the invention to denote such a packet that is too large for transfer across the shared link in a single timeslot Such a partial packet variable indicates that the current packet to be serviced in the queue is too large to be serviced in a single timeslot, and that a connection should be maintained over the shared link <b>108</b> for a sufficient number of timeslots to transfer the entire packet. The maximum priority level, therefore, can be allocated to a queue if such a partial packet variable is associated with the queue at a given time.

0065The queue manager <b>112</b> of <figref idref="DRAWINGS">FIG. 3A</figref> generally services the queues and sends updated messages regarding the state of the queues depending on the event(s) that takes place during a given timeslot. The queue manager <b>112</b>, for example, sends a dequeue notification <b>64</b> to the meter update module <b>160</b> when a packet is sent from a queue. This is a dequeue event. The queue manager <b>112</b> also sends an enqueue notification <b>62</b> to the meter update module <b>160</b> when a packet is received and buffered within a given queue. This is an enqueue event <figref idref="DRAWINGS">FIG. 3A</figref> also depicts a dequeue request <b>60</b> being sent from the priority computation module <b>156</b> to the queue manager <b>112</b>. This dequeue request <b>60</b> indicates the queue to be serviced in a given timeslot based on the arbitration process. The queue manager <b>112</b>, therefore, can service the queue in accordance with the dequeue request <b>60</b>.

0066An event generated by the queue manager <b>112</b>, therefore, begins the series of computations discussed above, and causes an update of the credit value and possibly Qlength for a queue. A priority for each queue is then determined based on the credit value or other information, such as a partial packet variable, associated with the queue. A priority with which each ingress desires each egress is determined using the priority computation module <b>156</b> and arbitration module <b>152</b>. These priorities generally determine an ingress to be associated with each egress for a given timeslot.

0067In an embodiment in which the functions of the metering module <b>154</b> and queue manager <b>112</b> are performed in hardware, the timing of the functions described above can be as follows for a timeslot size of about 200 nanoseconds. Arbitration and configuration of the link <b>108</b> are both performed on the basis of the fixed timeslots. Arbitration, however, preferably precedes configuration of the link <b>108</b> by a small number of timeslots due to latencies in the system. Thus, the arbitration module <b>152</b> can perform arbitration for about the first 100 nanoseconds of a timeslot, and then a message can be sent to each ingress <b>102</b> indicating the egress <b>104</b> with which it will communicate for a particular timeslot, which can be about 300-500 nanoseconds after the message is sent. Each ingress <b>102</b> will then respond to the arbiter chip <b>106</b> with updated priority information. In addition, each egress <b>104</b> can send information on the fullness state of its FIFOs. <figref idref="DRAWINGS">FIG. 2</figref>, for instance, depicts connections between the egresses <b>104</b> and the arbiter chip <b>106</b> over which such fullness state information may be sent. The actual configuration of the link <b>108</b> and transfer of packets takes place, therefore, a short time (300-500 nanoseconds in this embodiment) after the message containing the egress, for an ingress, is received by the ingress <b>102</b>.

0068In one embodiment of the invention, the priorities for each queue are updated every timeslot and the guaranteed rates for each queue are updated less frequently. For example, the guaranteed rates can be updated every 100 timeslots. QoS guarantees for a system are determined over some discernable period of time that consists of more than one timeslot, so bandwidth allocation, which is controlled using the guaranteed rates, needs to be adequate on average over a given plurality of timeslots and not for a single or even a few timeslots.

0069<figref idref="DRAWINGS">FIG. 3A</figref> depicts data that flows between the modules of the system <b>100</b> during operation in accordance with one embodiment of the invention. The data will be messages or signals representing the information described above. The messages sent between the modules as described above contain only updated information from information sent in previous timeslots, thus eliminating duplicative data transfers and reducing the amount of information that is transferred between modules. In addition, a single message containing Qlengths <b>50</b> and priorities <b>56</b> will be sent to the arbitrator chip <b>106</b> from the ingress <b>102</b>, rather than the separate messages shown in <figref idref="DRAWINGS">FIG. 3A</figref>. In addition, a single message containing an output egress <b>58</b> and updated guaranteed rates <b>52</b> can be sent from the arbitrator chip <b>106</b> to the ingress <b>102</b>, rather than the separate messages shown in <figref idref="DRAWINGS">FIG. 3A</figref>.

0070To review, <figref idref="DRAWINGS">FIG. 4B</figref> is a flow chart showing one embodiment of the operation of the invention in greater detail than <figref idref="DRAWINGS">FIG. 4A</figref>. In this embodiment, the bandwidth allocator <b>150</b> receives Qlength information at block <b>402</b>. At block <b>404</b>, the bandwidth allocator <b>150</b> determines guaranteed rates for the queues and sends these guaranteed rates to the ingress chip <b>102</b>. The guaranteed rate for each queue may be calculated in the bandwidth allocator <b>150</b> and sent to the ingress chip <b>102</b> once in every 100 timeslots in this embodiment At block <b>406</b>, the meter update module <b>160</b> uses the guaranteed rate for each queue to update a credit value for the queue. This updating of credit values can take place every timeslot in this embodiment. At block <b>408</b>, the priority computation module <b>156</b> calculates a priority based on the credit value or other information about the queue, such as whether a partial packet is present. This priority calculation can also take place every timeslot. At block <b>410</b>, the priority computation module <b>156</b> determines a priority with which the ingress desires to communicate with each egress of the system or, in other embodiments, the priority computation module <b>156</b> selects a plurality of queues that might have the largest priority for each egress. In either event, information is sent to the arbitration module <b>152</b> indicating these priorities. This act can also take place each timeslot. At block <b>412</b>, the arbitration module <b>152</b> uses the priorities to determine an ingress for each egress, and such a determination is performed every timeslot. At block <b>414</b>, the priority computation module <b>156</b> sends a dequeue request to the queue manager <b>112</b> every timeslot in accordance with the egress selected for the ingress, and the queue manager services the appropriate queue. At block <b>416</b>, the queue manager <b>112</b> sends enqueue/dequeue information to the meter update module <b>160</b>, and then the process beginning at block <b>402</b> is repeated.

0000B. Methods for Calculating Guaranteed Rates

0071A number of methods can be used within the scope of the invention to calculate the guaranteed rates for the queues of the ingresses <b>102</b> of the system <b>100</b>. Generally, the guaranteed rates are used to allocate bandwidth and, therefore, maintain QoS guarantees. Discussed herein are four methods for guaranteeing bandwidth: (1) guaranteeing bandwidth for a single queue, (2) guaranteeing bandwidth for an egress, (3) guaranteeing bandwidth for an ingress, and (4) guaranteeing bandwidth for a group of queues. <figref idref="DRAWINGS">FIG. 5</figref> depicts the first three of these methods for guaranteeing bandwidth.

00001. Guaranteeing Queue Bandwidth

0072To guarantee bandwidth for a particular queue Q within an ingress, the guaranteed rate for the queue is set to an appropriate value g_q, which can remain constant for a number of timeslots. Such a constant value g_qguarantees that over any reasonably long period of time, the average bandwidth the queue obtains is g_q, provided that the flow into the queue has an arrival rate that is at least equal to g_q. In one example, for instance, the value g_qcan be set to a value of 0.25 Gbps to allocate a bandwidth rate of 0.25 Gbps to the queue over a reasonably long period of time. <figref idref="DRAWINGS">FIG. 5</figref> depicts the act of setting the value g_qin block <b>502</b>.

0073In one embodiment that calculates guaranteed rates in hardware, the bandwidth allocator module <b>150</b> simply sets appropriate values in the rate registers to guarantee bandwidth for any given queue. The bandwidth allocator module <b>150</b> can limit the value of the rate g_qto be no higher than the arrival rate for the particular queue, which ensures that an idle queue does not accumulate unreasonably large credit and possibly waste bandwidth.

00002. Guaranteeing Bandwidth at an Egress

0074<figref idref="DRAWINGS">FIG. 6A</figref> exemplifies one embodiment of guaranteeing bandwidth for a particular egress E<b>1</b>. In such an embodiment, bandwidth for the single egress E<b>1</b> is guaranteed so that packets from any of one or more ingresses I<b>1</b>, I<b>2</b> can be transmitted to the egress E<b>1</b>. Ingress I<b>1</b> of <figref idref="DRAWINGS">FIG. 6A</figref> contains three queues, queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, and each queue is associated with a given COS and a given egress. For example, packets are, in this embodiment, buffered in queues depending not only on the COS for the packet, but also on the egress for which the packet is destined. Queue Q<b>1</b> of <figref idref="DRAWINGS">FIG. 6A</figref>, for instance, is associated with egress E<b>1</b> and has COS<b>1</b>. Queue Q<b>2</b> is associated with egress E<b>2</b> and has COS<b>2</b>, and queue Q<b>3</b> is associated with egress E<b>3</b> and has COS<b>3</b>. Ingress I<b>2</b> and I<b>3</b> are similarly set up with three queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b> having the same associations as the queues within ingress I<b>1</b>.

0075To calculate guaranteed rates in this embodiment of the invention, the queues associated with the same egress E<b>1</b> and having the same COS communicate Qlengths to the bandwidth allocator module <b>150</b>. In <figref idref="DRAWINGS">FIG. 6A</figref>, for example, queues Q<b>1</b> in ingresses I<b>1</b>, I<b>2</b>, and I<b>3</b> each communicate Qlengths to the bandwidth allocator module <b>150</b>. Guaranteed rates for these three queues are then determined as a single subset or group. In order to determine the guaranteed rate for the queue, the guaranteed rate for queue Q in ingress i (that is, ingress I<b>1</b>, I<b>2</b> or I<b>3</b>) destined for egress j (that is, egress E<b>1</b>, E<b>2</b> or E<b>3</b>) is denoted as gⁱ_j,q. This rate gⁱ_j,qcan change with time. The method can guarantee bandwidth for an egress link by guaranteeing, for some egress j, bandwidth equaling F_j,q=Σ_i:inputsgⁱ_j,q(t) averaged over a period of time. In this example, i can vary over all ingresses or over a subset of ingresses. Each gⁱ_j,q(t) corresponds to the bandwidth allocated at time t to an associated queue Q with data destined for egress j, and including each queue Q, if any, in each of ingresses i. The system guarantees that F_j,qworth of egress bandwidth which, at any given time, will be distributed over the different ingresses (that is, allocated to the queues Q within each ingress).

0076The Qlength for a queue Q in ingress i and destined for egress j can be denoted as Lⁱ_j,q(t). The values of these Qlengths are periodically communicated to the bandwidth allocator module <b>150</b>. If F_j,qis the bandwidth guaranteed at egress j for the COS corresponding to queue Q, then the guaranteed rates gⁱ_j,q(t)s can be initially set to be F_j,q/N, where N is the number of ingresses having such a queue Q (in this embodiment, there is one queue within each ingress bound for the egress and having the COS, although in other embodiments more than one queue Q with data bound for the egress and having the COS can be used). The guaranteed rates gⁱ_j,q(t)s can be reset or re-calculated depending on Qlengths Lⁱ_j,q(t) measured in subsequent timeslots as follows:

0077<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mo>(</mo><mrow><mrow><msubsup><mi>L</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>×</mo><msub><mi>F</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow></msub></mrow><mo>)</mo></mrow><mrow><msub><mo>∑</mo><mrow><mi>k</mi><mo>:</mo><mi>inputs</mi></mrow></msub><mo>⁢</mo><mrow><msubsup><mi>L</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>k</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mfrac></mrow></math></maths><img file="US7415477B2_D0001.tif" />

0078The inputs in this example are the number of ingresses N. If Σ_k:inputsL^k_j,q(t) is 0 (that is, all queues Q are empty), the guaranteed rates gⁱ_j,q(t)s are set to F_j,q/N for all ingresses i having a queue Q. Each updated guaranteed rate gⁱ_j,q(t) is then communicated back to the corresponding ingress i. In a hardware embodiment, the rate registers for queues Q are then updated. In a software embodiment, guaranteed rate variables gⁱ_j,q(t) for the queues Q are updated.

0079As a particular example using the embodiment of <figref idref="DRAWINGS">FIG. 6A</figref>, assume the Qlength Lⁱ_j,q(t) for queue Q<b>1</b> in ingress I<b>1</b> is 200 bytes, the bandwidth rate F_j,qfor the egress is 0.2 Gbps, and there are three ingresses with queues having a total Qlength Σ_k:inputsL^k_j,q(t) equaling 2000 bytes. In this example, the guaranteed rate gⁱ_j,q(t) for the queue Q<b>1</b> is:

0080<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><mo>(</mo><mrow><mn>200</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi><mo>*</mo><mn>0.2</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Gbps</mi></mrow><mo>)</mo></mrow><mrow><mn>2000</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi></mrow></mfrac><mo>=</mo><mrow><mn>0.02</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mi>Gbps</mi><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><img file="US7415477B2_D0002.tif" />

0081<figref idref="DRAWINGS">FIG. 5</figref> depicts an act of setting the guaranteed rates to equal values in block <b>506</b> for each ingress if the Σ_k:inputsL^k_j,q(t) is 0 as tested at block <b>504</b>. Block <b>508</b> depicts an act of setting the guaranteed rates to an individual calculated value for each ingress if Σ_k:inputsL^k_j,q(t) is not 0.

0082In an alternative embodiment, depicted in <figref idref="DRAWINGS">FIG. 6B</figref>, more than one queue within each ingress has a given COS and has data bound for the same egress. Queue Q<b>1</b> of <figref idref="DRAWINGS">FIG. 6B</figref>, for instance, is associated with egress E<b>1</b> and has COS<b>1</b>. Queue Q<b>5</b> is a second queue within ingress I<b>1</b> that is associated with egress E<b>1</b> and has COS<b>1</b>. Ingress I<b>2</b> is similarly set up with five queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b>, Q<b>5</b> having the same associations as the queues within ingress I<b>1</b>. In such a case, the number N above will be the number of queues having a given COS and being bound for the same egress. For instance, in <figref idref="DRAWINGS">FIG. 6B</figref>, four queues have COS<b>1</b> and are bound for egress E<b>1</b> (two in ingress I<b>1</b> and two in ingress I<b>2</b>). In such an embodiment, N=4 (the number of queues having the desired parameters) and not N=2 (the number of ingresses).

0083<figref idref="DRAWINGS">FIG. 6B</figref> also shows that an ingress I<b>1</b>, I<b>2</b> can have queues with packets bound for the same egress, but having different COSs. <figref idref="DRAWINGS">FIG. 6B</figref>, for instance, shows that queue Q<b>1</b> and queue Q<b>2</b> are both bound for (have pockets destined for) egress E<b>1</b>, but have different COSs—COS<b>1</b> for queue Q<b>1</b> and COS<b>2</b> for queue Q<b>2</b>. Only information from queues having the same COS is used in the calculations above. The number N of inputs in the calculations (Σ_k:inputsL^k_j,q(t)) for queues destined for egress E<b>1</b>, with COS<b>1</b>, in <figref idref="DRAWINGS">FIG. 6B</figref>, is therefore <b>4</b>—i.e., queues Q<b>1</b> and Q<b>5</b> in each of ingresses I<b>1</b> and I<b>2</b>. Queue Q<b>2</b> in each ingress I<b>1</b>, I<b>2</b> is not used for the calculations above due to the different COS. The egress output bandwidth F_j,qis therefore associated with COS<b>1</b> as well, and a separate egress output bandwidth amount can be associated with COS<b>2</b>.

0084The methods discussed above used Qlengths in order to calculate guaranteed rates. It should be noted that arrival rates can also be used to calculate guaranteed rates. In such an embodiment, arrival rate variables would be substituted in the equations and calculations above for Qlength variables in order to calculate guaranteed rates. Arrival rate information can be sent from the queue manager <b>112</b> (<figref idref="DRAWINGS">FIG. 3A</figref>) to the arbiter chip <b>106</b> in such an embodiment.

00003. Guaranteeing Bandwidth at an Ingress

0085<figref idref="DRAWINGS">FIG. 7A</figref> exemplifies one embodiment of guaranteeing bandwidth for a particular ingress I<b>1</b>. In such an embodiment, bandwidth for the single ingress I<b>1</b> is guaranteed so that packets from the queues within ingress I<b>1</b> can be communicated to any of the egresses E<b>1</b>, E<b>2</b>, E<b>3</b>. Ingress I<b>1</b> of <figref idref="DRAWINGS">FIG. 7A</figref> contains six queues, queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b>, Q<b>5</b>, Q<b>6</b>, and each queue is associated with a given COS. Queue Q<b>1</b> of <figref idref="DRAWINGS">FIG. 7A</figref>, for instance, is associated with COS<b>1</b>. Queue Q<b>2</b> is associated with COS<b>2</b>, and so forth. In this embodiment of guaranteeing bandwidth, the queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b> of each ingress I<b>1</b>, I<b>2</b>, I<b>3</b> need not be associated with a single egress. For instance, queue Q<b>1</b> having COS<b>1</b> can have packets destined for any egress of the system. <figref idref="DRAWINGS">FIG. 7A</figref> depicts a packet in queue Q<b>1</b> that is bound for egress E<b>1</b>, but the next packet in queue Q<b>1</b> could be destined for a different egress. In another embodiment, however, a queue Q may be associated with a given egress so that all of the packets buffered in the queue Q are destined for that egress.

0086In this embodiment, the system and method guarantee bandwidth for a particular ingress. In this case, bandwidth equaling Eⁱ_q=Σ_j:outputsgⁱ_j,q(t) averaged over some time t is guaranteed for the ingress i (or a subset of queues within the ingress having a given COS). In this embodiment, bandwidth equaling Eⁱ_qis guaranteed for an ingress and such bandwidth Eⁱ_qcan be distributed uniformly or non-uniformly over the different egresses j. The guaranteed rates gⁱ_j,q(t)s for the corresponding queues cannot be set to be constants which sum Eⁱ_q, because at any given time, a particular queue may or may not have packets of data that are destined for an egress. In <figref idref="DRAWINGS">FIG. 7A</figref>, queues Q<b>1</b>, Q<b>3</b>, and Q<b>5</b>, which all have COS<b>1</b>, send Qlengths to the bandwidth allocator module <b>150</b>, and rates for each of these queues are then determined as a group or subset and sent back to the ingress I<b>1</b>.

0087In this embodiment, guaranteed rates are set based on Qlengths, as in the egress bandwidth embodiment. The Qlength Lⁱ_j,q(t) is determined for each queue Q in a given COS corresponding to egress j in a given ingress I<b>1</b>. In this embodiment, each of these Lⁱ_j,q(t)s can be locally available within a single ingress, unlike in the method for guaranteeing egress bandwidth. The guaranteed rates gⁱ_j,q(t)s can be initialized to Eⁱ_q/M, where M is the number of queues having the given COS. In one embodiment, multiple queues within a single ingress can exist that are each associated with a given egress and have a given COS. In another embodiment, only a single queue Q can exist within an ingress that is associated with a given egress and has a given COS. In still other embodiments, the queues within an ingress can each have an associated COS, but the queues may not be associated with a particular egress. In any event, the guaranteed rates gⁱ_j,q(t)s can be reset or calculated depending on Qlengths Lⁱ_j,q(t) in subsequent timeslots as follows:

0088<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mo>(</mo><mrow><mrow><msubsup><mi>L</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>×</mo><msubsup><mi>E</mi><mi>q</mi><mi>i</mi></msubsup></mrow><mo>)</mo></mrow><mrow><msub><mo>∑</mo><mrow><mi>k</mi><mo>:</mo><mi>outputs</mi></mrow></msub><mo>⁢</mo><mrow><msubsup><mi>L</mi><mrow><mi>k</mi><mo>,</mo><mi>q</mi></mrow><mi>k</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mfrac></mrow></math></maths><img file="US7415477B2_D0003.tif" /><br /> for all j

0089If Σ_k:outputsLⁱ_k,q(t) is 0, gⁱ_j,q(t) is set to Eⁱ_q/M for all of the queues. Each updated guaranteed rate gⁱ_j,q(t) is then communicated back to the corresponding ingress i. In a hardware embodiment, the rate registers for the queues Q are then updated. In a software embodiment, guaranteed rate variables gⁱ_j,q(t) for the queues Q are updated.

0090As a particular example, for the embodiment of <figref idref="DRAWINGS">FIG. 7A</figref>, assume the Qlength Lⁱ_j,q(t) is 100 bytes, the bandwidth rate for the ingress is 0.5 Gbps, and the three queues having COS<b>1</b> in ingress I<b>1</b> have a total Qlength Σ_k:inputsL^k_j,q(t) equaling 1000 bytes. In this example, the guaranteed rate gⁱ_j,q(t) for the queue Q is:

0091<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mrow><mi>j</mi><mo>,</mo><mi>q</mi></mrow><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><mo>(</mo><mrow><mn>100</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi><mo>*</mo><mn>0.5</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Gbps</mi></mrow><mo>)</mo></mrow><mrow><mn>1000</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi></mrow></mfrac><mo>=</mo><mrow><mn>0.05</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mi>Gbps</mi><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><img file="US7415477B2_D0004.tif" />

0092In this example using <figref idref="DRAWINGS">FIG. 7A</figref>, ingress I<b>1</b> has three queues Q<b>1</b>, Q<b>3</b>, Q<b>5</b> having COS<b>1</b>, although each queue Q<b>1</b>, Q<b>3</b>, Q<b>5</b> is associated with a different egress. Queue Q<b>1</b>, for instance, is associated with egress E<b>1</b>, and queue Q<b>3</b> is associated with egress E<b>2</b>. In another embodiment, however, ingress I<b>1</b> could have multiple queues having the same COS and being associated with the same egress. In still another embodiment, the queues within ingress I<b>1</b> may not be associated with a particular egress, but may have an associated COS.

0093<figref idref="DRAWINGS">FIG. 5</figref> depicts an act of setting the guaranteed rates to equal values in block <b>512</b> for each egress if the Σ_k:outputsLⁱ_k,q(t), tested at block <b>510</b>, is 0. Block <b>514</b> depicts an act of setting the guaranteed rates to an individual calculated value for each queue if Σ_k:outputsLⁱ_k,q(t) is not 0.

0094The methods discussed above used Qlengths in order to calculate guaranteed rates. It should be noted that arrival rates can also be used to calculate guaranteed rates. In such an embodiment, arrival rate variables would be substituted in the equations and calculations above for Qlength variables in order to calculate guaranteed rates. Arrival rate information can be sent from the queue manager <b>112</b> (<figref idref="DRAWINGS">FIG. 3A</figref>) to the arbiter chip <b>106</b> in such an embodiment.

00004. Guaranteeing Bandwidth for a Group of Queues

0095<figref idref="DRAWINGS">FIG. 7B</figref> exemplifies one embodiment of guaranteeing bandwidth for a group of queues, which can be any arbitrary group of queues. In such an embodiment, bandwidth can be guaranteed for a group of queues, where the queues can be in different ingresses and can have packets destined for different egresses. In addition, the queues in the group can have the same COS or different COSs. The total bandwidth amount can be apportioned to the queues based on the Qlengths of the queues or, in other embodiments, based on the arrival rate of data to the queues.

0096Referring to <figref idref="DRAWINGS">FIG. 7B</figref> as an example of this embodiment, a group of queues for which bandwidth is guaranteed includes queues Q<b>1</b> and Q<b>3</b> in ingress I<b>1</b> and queues Q<b>1</b>, Q<b>4</b>, and Q<b>6</b> in ingress I<b>2</b>. The queues in this group are not bound for the same egress and do not have the same COS. Queue Q<b>1</b> in ingress I<b>1</b>, for example, contains data bound for port <b>1</b> of egress E<b>1</b> and has COS<b>1</b>, and queue Q<b>3</b> in ingress I<b>1</b> contains data bound for port <b>1</b> of egress E<b>2</b> and has COS<b>3</b>. Queue Q<b>1</b> in ingress I<b>2</b> contains data bound for port <b>1</b> of egress E<b>1</b> and has COS <b>1</b>. Queues Q<b>4</b> and Q<b>6</b> in ingress I<b>2</b>, which are also in the group of queues, also have arbitrary characteristics in this embodiment.

0097To calculate guaranteed rates in this embodiment of the invention, the queues associated with the arbitrary group of queues communicate Qlengths to the bandwidth allocator module <b>150</b>. In <figref idref="DRAWINGS">FIG. 7B</figref>, for example, queues Q<b>1</b> and Q<b>3</b> in ingress I<b>1</b> and queues Q<b>1</b>, Q<b>4</b>, and Q<b>6</b> in ingress I<b>2</b> each communicate Qlengths to the bandwidth allocator module <b>150</b>. Guaranteed rates for these five queues are then determined as a single subset or group. In order to determine the guaranteed rate for each queue, the guaranteed rate for queue Q in the group of N queues is denoted as gⁱ_q. This rate gⁱ_qcan change with time. The method can guarantee bandwidth for the group of queues by guaranteeing bandwidth equaling F_ARB=Σ_i:inputsgⁱ_q(t) averaged over a period of time. In this example, i varies over each of the queues in the group of N queues. Each gⁱ_q(t) corresponds to the bandwidth allocated at time t to an associated queue Q. The system guarantees F_ARBworth of bandwidth which, at any given time, will be distributed over the different queues in the group of N queues.

0098The Qlength for a queue Q in the group of N queues can be denoted as Lⁱ_q(t). The values of these Qlengths are periodically communicated to the bandwidth allocator module <b>150</b>. If F_ARBis the bandwidth guaranteed for the group of N queues, then the guaranteed rates gⁱ_q(t)s can be initially set to be F_ARB/N, where N is the number of queues in the group of queues. The guaranteed rates gⁱ_q(t)s for each queue can be reset or re-calculated depending on Qlengths Lⁱ_q(t) measured in subsequent timeslots as follows:

0099<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mi>q</mi><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mo>(</mo><mrow><mrow><msubsup><mi>L</mi><mi>q</mi><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>×</mo><msub><mi>F</mi><mi>ARB</mi></msub></mrow><mo>)</mo></mrow><mrow><msub><mo>∑</mo><mrow><mi>i</mi><mo>:</mo><mi>inputs</mi></mrow></msub><mo>⁢</mo><mrow><msubsup><mi>L</mi><mi>q</mi><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mfrac></mrow></math></maths><img file="US7415477B2_D0005.tif" /><br /> for each queue

0100The inputs in this example vary over the number N of queues in the group. If Σ_{i: inputs}/Lⁱ_q(t) is 0 (that is, all queues Q in the group are empty), the guaranteed rates gⁱ_q(t)s are set to F_ARB/N for all queues in the group. Each updated guaranteed rate gⁱ_q(t) is then communicated back to the ingress corresponding to the queue, as depicted in <figref idref="DRAWINGS">FIG. 7B</figref>. In a hardware embodiment, the rate registers for queues Q are then updated. In a software embodiment, guaranteed rate variables gⁱ_q(t) for the queues Q are updated.

0101As a particular example using the embodiment of <figref idref="DRAWINGS">FIG. 7B</figref>, assume the Qlength Lⁱ_q(t) for queue Q<b>1</b> in ingress I<b>1</b> is 800 bytes, the bandwidth rate F_ARBfor the group of queues is 0.8 Gbps, and there are five queues in the group having a total Qlength Σ_i:inputsLⁱ_q(t) equaling 2000 bytes. In this example, the guaranteed rate gⁱ_q(t) for the queue Q<b>1</b> in ingress I<b>1</b> is:

0102<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mrow><msubsup><mi>g</mi><mi>q</mi><mi>i</mi></msubsup><mo>⁡</mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mrow><mo>(</mo><mrow><mn>800</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi><mo>*</mo><mn>0.8</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Gbps</mi></mrow><mo>)</mo></mrow><mrow><mn>2000</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>bytes</mi></mrow></mfrac><mo>=</mo><mrow><mn>0.32</mn><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mi>Gbps</mi><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><img file="US7415477B2_D0006.tif" />

0103The methods discussed above used Qlengths in order to calculate guaranteed rates. It should be noted that arrival rates can also be used to calculate guaranteed rates. In such an embodiment, arrival rate variables would be substituted in the equations and calculations above for Qlength variables in order to calculate guaranteed rates. Arrival rate information can be sent from the queue manager <b>112</b> (<figref idref="DRAWINGS">FIG. 3A</figref>) to the arbiter chip <b>106</b> in such an embodiment.

0000C. Methods for Updating Credit Values

0104One method for updating credit values for a given queue is depicted in block form in <figref idref="DRAWINGS">FIG. 8</figref> for one embodiment of the invention. As described above, credit values generally increase for queues that are not serviced after each timeslot, therefore increasing the priority for those queues. Similarly, a serviced queue has an associated credit value decreased after the timeslot in which it is serviced so that the priority for that queue will decrease. In one embodiment, an initial value of each credit value, before operation of the invention, can be 0. The credit values for each queue of an ingress are generally updated each timeslot. After a queue is serviced, therefore, the credit value can be decreased from its current value (initially 0, but after operation begins, the current value of the credit value can be a large positive number or a negative number of large magnitude). The credit values can be updated in the meter update module <b>160</b> of the metering module <b>154</b> using the guaranteed rates <b>52</b> for the queues received from the bandwidth allocator module <b>150</b>. In a steady-state system, the credit values for all of the queues add up to 0, which indicates that the queues are, on average, receiving desired bandwidth rates.

0105<figref idref="DRAWINGS">FIG. 8</figref> depicts three possible events <b>800</b> that can occur, in one embodiment of the invention, during a given timeslot for a single queue within an ingress. An enqueue event can take place, meaning that a packet of data enters the queue. A dequeue event can take place, meaning that the queue has been serviced and a packet has been sent from the queue to the shared link. The third event is an increment event, which takes place during each timeslot in this embodiment. During a single timeslot, each of the three events in <figref idref="DRAWINGS">FIG. 8</figref> can occur for a queue. For an increment event in this embodiment, the credit value is incremented by adding the guaranteed rate for the queue to the current credit value, as denoted by block <b>802</b> in <figref idref="DRAWINGS">FIG. 8</figref>. As denoted by blocks <b>804</b> and <b>806</b>, if the new credit value is greater than a maximum limit for the queue (which can be based on the COS for the queue), the credit value is reset to the maximum limit for the queue. In one embodiment, an increment event occurs during each timeslot, so that each queue is incremented after each timeslot by its associated credit value.

0106Maximum limits on the credit values for queues prevents the credit values for queues having low COSs from growing too large. The priority for these queues can therefore also be capped. This ensures that the queues having low COSs will not be serviced at the same rate as queues having larger COSs.

0107If an event is a dequeue event, in this embodiment, the Qlength for the queue becomes smaller, and the Qlength for the queue can therefore be updated, as denoted by block <b>810</b>. A new packet or packets will be at the head of the queue for service, and the size of the packet or packets can be updated, as denoted by block <b>812</b>. In addition, if the new packet is larger than a given timeslot, a partial packet variable will be updated, as denoted by block <b>814</b>. The partial packet variable indicates that, once started, communication to the shared link <b>108</b> should be maintained for the queue so that a packet larger than a single timeslot can be transferred across the shared link <b>108</b> without interruption. The credit value for the queue can then be decreased, as indicated by block <b>816</b>. In one embodiment, the credit value is decreased by a function of the number of packets sent (that is, if more than one packet is sent during a timeslot) or bytes sent during the timeslot. In another embodiment, the credit value can be decreased by the amount of data (that is, in bytes or bits) that can be sent in a single timeslot. As such, the credit value is appropriately decreased so that bandwidth can be re-allocated for the other queues. In this embodiment, an increment event will also occur after the timeslot, such that the credit value is decreased for the dequeue event by the number of bytes that can be sent during a single timeslot (for example), and then increased by the guaranteed rate for the queue for the increment event. If the updated credit value is smaller than a minimum limit for the queue, which can be based on the COS for the queue, as tested at block <b>818</b>, the credit value is reset to the minimum limit for the queue at block <b>820</b>.

0108A minimum credit value is used to insure that a priority for a queue having a certain COS does not become too small. This prevents the queue from not being serviced frequently enough.

0109If an event is an enqueue event, a determination is made whether the Qlength for the queue was indicated as being zero (block <b>830</b>). If the current Qlength of the queue is zero, then no packet existed within the queue during the previous timeslot. Because a packet entered the queue during the enqueue event, the packet size for the queue will need to be updated along with the partial packet variable for the queue (blocks <b>832</b> and <b>834</b>). If the Qlength is not zero, a packet exists at the head of the queue (and existed in the previous timeslot as well), and a packet size and partial packet variable were already set during a previous timeslot. Block <b>836</b> of <figref idref="DRAWINGS">FIG. 8</figref> indicates an act of updating the Qlength based on the enqueued packet of data. An increment event can also occur during the same timeslot as an enqueue event, as may a dequeue event.

0000D. Methods for Determining Queue Priorities

0110After credit values are updated for the queues, a priority for each queue in each ingress indicating a need to connect to an egress can be determined. As described above and below in more detail, these priorities can be used to compute a mapping of the shared link <b>108</b> between ingresses and egresses.

0111In one embodiment, priorities for queues can be scaled on a sixteen point level between 0 and 15. In this embodiment, the priorities for queues are determined from the credit values for the queues on this scaled level. For instance, if the credit value for a given queue has accrued to the level of 1 Gbps, a priority for the queue can be set to a level of 5, and if the credit value for a second queue is 2 Gbps, a priority for the second queue can be set to a level of 10. In this embodiment, a negative credit value will be set to a low priority, such as 0 or 1. In such an embodiment, a queue having a greatest priority is the queue that will be serviced during a given timeslot. The conversion of credit values to priorities can minimize the amount of data that will be sent from an ingress <b>102</b> to the arbiter chip <b>106</b>. A credit value, for instance, can be over 1,000,000,000 in size, while a corresponding priority for such a credit value can be 10. If a priority is scaled on a sixteen point scale, a four-bit register can be used for the priority in a hardware embodiment.

0112As described above in connection with updating credit values, credit values for certain queues can be limited depending on a COS for the queues. For example, a queue with COS<b>1</b> can be limited to a certain minimum credit value that can correspond to a minimum priority level of 5 on a sixteen point scale. Similarly, a queue with COS<b>8</b> can be limited to a certain maximum credit value that can correspond to a maximum priority level of 12 on a sixteen point scale.

0113In one embodiment using a sixteen point priority scale from 0 to 15, a priority of 0 is reserved for a queue that is empty and hence has no packet to transfer over the shared link <b>108</b>. Similarly, a maximum priority of 15 can be reserved for partial packets. As explained above, if a packet is too large for transfer over the shared link <b>108</b> in a single timeslot, a partial packet variable is associated with the queue. When the queue having the packet eventually obtains a connection to the shared link <b>108</b>, a maximum priority will be set for that queue in the next timeslot such that the queue will continue to be connected to the shared link <b>108</b> and the packet can be continuously transferred over the shared link <b>108</b> without segmentation and reassembly.

0114Table 1 below indicates another embodiment of the conversion from a credit value to a priority for a queue. In this embodiment, the conversion from a credit value to a priority can involve more than a simple scaling from a credit value to a priority. Other queue information, such as whether the queue is empty and whether the queue has been serviced too much, can also be considered. Table 1, therefore, includes a number of conditions along with a priority that can be assigned to a queue if one of those conditions is met. In this embodiment, each queue has a credit value C(q) associated with it, as described above. The scaling factor S is a constant used to scale larger credit values into smaller priorities.

0115<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="168pt" align="left" /><colspec colname="2" colwidth="49pt" align="left" /><thead><row><entry namest="1" nameend="2" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row><row><entry /><entry>PRIORITY</entry></row><row><entry>CONDITION</entry><entry>FOR QUEUE</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1. If the packet is a partial packet from the previous</entry><entry>MAXPRI</entry></row><row><entry>  timeslot (that is, the queue has a partial packet</entry></row><row><entry>  variable associated with it).</entry></row><row><entry>2. If the queue is an expedited forwarding queue AND</entry><entry>MAXPRI − 1</entry></row><row><entry>  the credit value C(q) for the queue is greater than 0.</entry></row><row><entry>3. If the queue is not an expedited forwarding queue</entry><entry>MIN [(C(q)/S),</entry></row><row><entry>  AND the credit value C(q) for the queue is greater</entry><entry>MAXPRI − 1]</entry></row><row><entry>  than 0.</entry></row><row><entry>4. If the queue is not empty AND if the condition</entry><entry>1</entry></row><row><entry>  below is not met, a minimum priority that can be set</entry></row><row><entry>  (that is, the priority can be larger as determined</entry></row><row><entry>  above).</entry></row><row><entry>5. If the queue is empty, OR</entry><entry>0</entry></row><row><entry>  if C(q) &lt; S_limit</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0116As condition 1 in Table 1 indicates, in this embodiment, the priority for a queue is set to a maximum priority MAXPRI if the packet in the queue is a partial packet from the previous timeslot. On a sixteen point scale from 0 to 15, MAXPRI is 15. Such a partial packet that is assigned MAXPRI in one embodiment, has a partial packet variable associated with it. Conversely, a queue that is empty is assigned a priority of 0, as condition 5 in Table 1 indicates. This is a minimum priority that will ensure that a queue having the priority of 0 will not be serviced during the given timeslot.

0117Condition 5 in Table 1 has a second condition that, if met, sets the priority to 0 (or a minimum priority). If the credit value C(q) is less than a shaping limit S_limitfor the queue, the priority will be set to 0. The shaping limit S_limitis a parameter used to scale the priority so that a queue doesn't receive too much bandwidth over a period of time. A guaranteed rate is, for instance, the minimum rate F_minthat a queue should receive. A maximum rate F_max, on the other hand, can be the maximum rate that a queue should receive. Of course, the bandwidth received over a discernable length of time greater than a single timeslot should be measured to determine if these rates are achieved. For instance, a time period of 50 microseconds can be the time period over which a minimum rate F_minshould be achieved and a maximum rate F_maxshould not be exceeded. A time period of 50 microseconds can equal, for instance, 100 timeslots of 500 nanoseconds each. In this embodiment, the shaping limit S_limitcan be set to be: <br /><i>S</i>_limit=(<i>F</i>_min<i>−F</i>_max)*time period.

0118Because F_minwill be smaller than F_max, the shaping limit S_limitwill generally be a negative number. A credit value becomes negative only when its queue has been serviced recently and the queue, therefore, has already received more than its guaranteed bandwidth at that point in time. The larger in magnitude that a negative credit value becomes, the more the corresponding queue has been serviced, and the more that queue has exceeded its guaranteed bandwidth. In such cases, the priority for the queue can be forced to be 0 by using the shaping limit S_limit, as indicated in condition 5 in Table 1. If the credit value C(q), converted to bytes per time period, is less than the shaping limit S_limit, the priority will be set to 0 in this embodiment, thus ensuring that the queue will not be serviced in a subsequent timeslot. If the converted credit value C(q) is less than the shaping limit S_limit, the queue has already exceeded the maximum bandwidth that will be allowed over the time period, and hence the priority will be set to 0. In this manner, the maximum bandwidth that can be achieved for a queue can be restricted over a certain time period. If, however, it is desired to allow a queue to exceed its maximum bandwidth over a period of time, the credit value for the queue can be periodically set to 0 so that a negative credit value that is large in magnitude will not keep the queue from being serviced frequently.

0119With regarding to condition 2 in Table 1, an ingress can be set up with a queue that is an expedited forwarding queue. Such a queue is a queue that is serviced before other queues of the ingress regardless of credit value. An expedited forwarding queue can be used in an ingress to ensure that certain packets are transferred as quickly as possible. In such a case, the packet will be buffered in the expedited forwarding queue. As Table 1 indicates for condition 2, a priority of MAXPRI-1 is set to such an expedited forwarding queue if it contains a packet (that is, if the queue is not empty). A priority of MAXPRI-1 ensures that the queue will likely be serviced as long as no queue desiring the same egress has a priority of MAXPRI. Similarly, two queues may have MAXPRI-1, in which case a tie between the two queues will need to be broken, as described below. On a sixteen point scale from 0 to 15, MAXPRI-1 is 14.

0120Condition 3 in Table 1 indicates the typical condition in which the credit value is scaled into a priority. Generally, if a queue does not have a partial packet, the queue is not an expedited forwarding queue, and the credit value C(q) for the queue is not negative, then the priority for the queue can be calculated by dividing the credit value C(q) for the queue by the scaling factor S. The priority can be a rounded version of the credit value C(q) divided by the scaling factor, so that a number of 6.4 would be rounded to a priority of 6. The use of a scaling factor S implies a linear scaling. The scaling, however, need not be linear, but can be nonlinear as well. In addition, a look-up table or a series of “if, then” determinations can be used to determine a priority based on a credit value. In order to keep the priority within the bounds of an established scale (such as a 0 to 15 scale), the priority for the queue can be set to a maximum level of MAXPRI-1 if it does not contain a partial packet. Condition 3 in Table 1, therefore, indicates taking the smaller of MAXPRI-1 or C(q)/S for the priority for such a queue.

0121Condition 4 in Table 1 indicates that a priority for a queue will be a minimum priority if the queue is not empty and if condition 5 does not apply (that is, the credit value C(q) is not less than the shaping limit S_limit). Table 1 indicates this minimum priority as being 1. The priority for the queue can, of course, be larger if the credit value C(q) is positive, as indicated by condition 3. If the queue is not empty and if condition 5 does not exist, however, condition 4 indicates that a minimum priority is set.

0122The credit value of a queue can vary widely. It could be as large as tens of millions or a negative quantity whose magnitude is tens of millions. As an example of the conversion from a credit value to a priority, assume the guaranteed rate for a queue is 0.0005 Gbps, or 500,000 bytes per second (bps). With each passing timeslot for which the queue is not serviced, therefore, the credit value associated with the queue increases by 500,000 bps. The scaling factor S, in this example, is 1,000,000. If the credit value for the queue grows to a value of 12,000,000, therefore, the priority for the queue will be set to 12 (assuming the queue is not an expedited forwarding queue and the queue does not contain a partial packet). If the credit value for the queue is-5,000,000, the priority for the queue will be set to 1 (unless condition 1, 2 or 5 applies from Table 1).

0000E. Methods for Queue Service Selection

0123After a priority for each queue has been determined, the plurality of priorities is used to compute a mapping over the shared link <b>108</b> between the ingresses and egresses for a timeslot. <figref idref="DRAWINGS">FIG. 9</figref> illustrates one simplified embodiment of selecting queues for service during a given timeslot <figref idref="DRAWINGS">FIG. 9</figref> depicts two ingresses I<b>1</b>, I<b>2</b>, each of which has four queues. Depicted within each queue Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b> is a COS for the queue and a packet at the head of the queue. Each of the packets at the head of the queues contend for access to the shared link <b>108</b> during any given timeslot. In <figref idref="DRAWINGS">FIG. 9</figref>, for example, a packet destined for egress E<b>1</b> is at the head of each queue Q<b>1</b>, a packet destined for egress E<b>1</b> is also at the head of each queue Q<b>2</b>, and packets destined for egress E<b>2</b> are at the head of each of queues Q<b>3</b> and Q<b>4</b>.

0124<figref idref="DRAWINGS">FIG. 9</figref> shows that priorities P<b>11</b>, P<b>12</b>, P<b>21</b>, and P<b>22</b> have been computed for each of the queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b>. In one embodiment, priority computation and queue selection take place every timeslot. At any given moment, therefore, a priority for a packet (or packets) at the head of a queue is akin to a priority for the queue itself because only the packet (or packets) at the head of the queue contends for access to the shared link <b>108</b> during a given timeslot. Throughout this specification, therefore, the instantaneous priority for a queue can be considered to be synonymous with a priority for a packet (or packets) at the head of the queue. In addition, a priority that is “instantaneous” refers to a priority for a given timeslot, which is an instant in time having some finite duration, and this priority may or may not change in timeslots that follow the given timeslot.

0125In <figref idref="DRAWINGS">FIG. 9</figref>, two ingresses I<b>1</b> and I<b>2</b>, each having four queues Q<b>1</b>, Q<b>2</b>, Q<b>3</b>, Q<b>4</b> are connectable to egresses E<b>1</b> and E<b>2</b> over the shared link <b>108</b>. A two-level process for selection of a mapping between ingress and egress can be used as follows. In a first level a first instantaneous priority is selected for each group of queues in each ingress bound for a particular egress. This first level of selection can be performed within an ingress by the priority computation module <b>156</b> (<figref idref="DRAWINGS">FIG. 3A</figref>). For ingress I<b>1</b> in <figref idref="DRAWINGS">FIG. 9</figref>, for instance, queue Q<b>1</b> and queue Q<b>2</b> both contain packets bound for egress E<b>1</b>. Based on the priority of these two queues Q<b>1</b>, Q<b>2</b>, one of these queues, having a first priority, is selected. In one embodiment, for instance, the queue having the higher priority associated therewith is selected. Similarly, in ingress I<b>2</b>, queues Q<b>1</b> and Q<b>2</b> both contain packets bound for egress E<b>1</b>, and a queue having a first priority from these two queues is also selected. It is worth noting that for queue selection, the COS for the queue can, in one embodiment, be ignored. The COS for the queue has, presumably, already been used to determine the priority for the queue. <figref idref="DRAWINGS">FIG. 9</figref> also depicts the selection of a queue (having a first priority) having a packet destined for egress E<b>2</b> in each ingress I<b>1</b>, I<b>2</b>. An indication of the queue number, ingress number, and priority level for each selected queue having a first priority in the first level is sent to the arbitration module <b>152</b> of the arbiter chip <b>106</b>, as depicted in <figref idref="DRAWINGS">FIG. 9</figref>.

0126The second level of the queue selection in the two-level process takes place within the arbitration module <b>152</b>. In this second level, a queue having a second priority is selected from the subset of queues having the first priorities received from the ingresses I<b>1</b>, I<b>2</b>. This second level of selection reviews the priority with which each ingress desires to connect with each egress and selects an egress for each ingress. As an example, using <figref idref="DRAWINGS">FIG. 9</figref>, assume queue Q<b>1</b> has a priority P<b>11</b>=12 in ingress I<b>1</b> and is selected within ingress I<b>1</b> in a first level of selection for egress E<b>1</b>. Similarly, assume queue Q<b>2</b> has a priority P<b>12</b>=7 in ingress I<b>2</b> and is selected within ingress I<b>2</b> in a first level of selection for egress E<b>1</b>. These two queues, priorities, and desired egresses are communicated to the arbitration module <b>152</b>. In the second level of queue selection, the arbitration module <b>152</b> selects from these queues (which both contain packets destined for egress E<b>1</b>) a queue having a second priority. In one embodiment, for instance, the queue having the highest priority is selected for the egress. In this example, for instance, queue Q<b>1</b> from ingress I<b>1</b> has a higher priority for egress E<b>1</b> than does queue Q<b>2</b> from ingress I<b>2</b> (i.e., a priority of 12 is higher than a priority of 7). This second level, therefore, determines the egress to which each ingress is connected during a given timeslot.

0127A N×M matrix of priorities can therefore be used in the arbitration module <b>152</b>, where N is the number of ingresses and M is the number of egresses. For instance, the arbitrator module <b>152</b> can receive from each ingress the maximum priority with which the ingress desires each egress, as determined in the first level of selection. These priorities then fill the N×M matrix so that an ingress can be selected for each egress in the second level of selection. As depicted in <figref idref="DRAWINGS">FIG. 9</figref>, a message is sent to each ingress notifying that ingress of the egress, if any, to which it will have access during the timeslot. The ingress can then connect the queue it selected for the determined egress to the shared link <b>108</b> for packet transfer.

0128During the second level of queue selection, it should be noted that a single ingress can contain more than one queue having packets destined for different egresses and that have the highest priority for those egresses. Because, in some embodiments, a single queue of an ingress can only be connected to a single egress during a timeslot (a physical limitation in this embodiment of the invention), each of these queues will not be selected for access to the shared link <b>108</b>. In such a situation, the queue having the highest priority is selected from the queues within the ingress and the egress for that queue is determined according to that highest priority. The ingress will then be unavailable for at least that timeslot for connection to other egresses, and the priorities from that ingress can be ignored for the remainder of the queue selections in the second level of selection for this timeslot. As an example from <figref idref="DRAWINGS">FIG. 9</figref>, assume queue Q<b>1</b> from ingress I<b>1</b> has priority P<b>11</b>=12 and is the highest priority for egress E<b>1</b> for all of the ingresses within the arbitration module <b>152</b>. Further, assume queue Q<b>3</b> from ingress I<b>1</b> has priority P<b>21</b>=10 and is the highest priority for egress E<b>2</b> for all of the ingresses. In this example, queue Q<b>1</b> from ingress I<b>1</b> has a greater priority than queue Q<b>3</b> from ingress I<b>1</b> (I<b>2</b> is greater than 10), and hence queue Q<b>1</b> from ingress I<b>1</b> will be selected for access to egress E<b>1</b>. The remaining queues from ingress I<b>1</b> will not be available for connection to the shared link <b>108</b> during that given timeslot. Queue Q<b>3</b> from ingress I<b>1</b> will therefore not be available for the given timeslot, and a different queue from a different ingress will have to be selected for egress E<b>2</b>.

0129A tie-breaking method may be needed when two or more priorities are equal in either an ingress or in the arbitration module <b>152</b>. Such tie-breaking can be done using a random selection, a round robin selection or, in other embodiments, using the least recently serviced queue. As an example using <figref idref="DRAWINGS">FIG. 9</figref>, assume queue Q<b>1</b> within ingress I<b>1</b> has priority P<b>11</b>=10 for egress E<b>1</b> and queue Q<b>2</b> within ingress I<b>1</b> also has priority P<b>12</b>=10 for egress E<b>1</b>. In a tie-breaking procedure using a least recently serviced queue, the queue Q<b>1</b> or Q<b>2</b> that has been serviced least recently will be chosen. A similar procedure can be followed within the arbitration module <b>152</b> for tie-breaking of priorities from ingresses for egresses. In such a case, for instance, the ingress that has been least recently connected to the egress will be serviced or, in another embodiment, the queue from either ingress that has been least recently serviced will be selected.

0130<figref idref="DRAWINGS">FIG. 9</figref> depicts a message containing the state of the FIFOs within each egress E<b>1</b>, E<b>2</b> being sent over lines <b>110</b><i>a </i>to the arbiter chip <b>106</b>. The state of the FIFOs, which can be an indication of how full the FIFOs of an egress are, can be used within the arbitration module <b>152</b> to map ingresses with egresses. A priority for a queue can be reduced if the FIFO within the egress to which the queue wishes to communicate is full. In other words, if the FIFO of an egress is full, no packet will be sent to that FIFO, and if all of the FIFOs of an egress are full, a packet will not be sent to the egress in the timeslot, and the priority of a queue having a packet desiring that egress will be correspondingly reduced so that the queue will not gain access to the shared link <b>108</b> during the next timeslot. In this embodiment, the priority for queues bound for an egress with full FIFOs can be reduced within the arbitration module <b>152</b> on the arbiter chip <b>106</b>, although the FIFO states can also be sent to the ingresses in other embodiments. In another embodiment, priorities are not actually reduced for queues having packets bound for an egress with full FIFOs, but instead the FIFO state can simply be used to ensure that no packets are sent to the egress while the FIFOs of the egress are full. In other words, an egress with full FIFOs is disregarded, and a FIFO port of an egress that is full is also disregarded. In this embodiment, no ingress gains access to the egress with full FIFOs during the given timeslot.

0131Another embodiment for selecting the queue to service can involve a three-level process for selection of a mapping between ingress and egress. The three-level process of queue selection can be used where packets of data specify an egress and a port within the egress with which connection is desired. <figref idref="DRAWINGS">FIG. 9</figref>, for instance, depicts ports FIFO<b>1</b> and FIFO<b>2</b> within each of egresses E<b>1</b> and E<b>2</b>. Packets of data within the ingresses can each specify a particular egress and also a particular port within that egress with which communication is desired.

0132<figref idref="DRAWINGS">FIG. 10</figref> is a decision tree block diagram illustrating levels of selection in a three-level process for queue selection. In the three-level process for queue selection, a first level of selection involves selecting, within each ingress, a queue from each group of queues bound for a particular port of a particular egress. In other words, a queue having a first priority is selected from those queues within an ingress bound for the same port of the same egress, and the first priority can be the highest priority for the group of queues. This selection can be from among queues having different COSs.

0133<figref idref="DRAWINGS">FIG. 10</figref> depicts two ingresses I<b>1</b>, I<b>2</b>, each having four queues, with each queue in this depiction having packets bound for the same egress. Within ingress I<b>1</b>, for example, block <b>1002</b> indicates that queue Q<b>1</b> has priority P<b>1</b> and seeks to communicate with port <b>1</b> of egress E<b>1</b>. Similarly, block <b>1004</b> indicates that and queue Q<b>2</b> has priority P<b>2</b> and also seeks to connect with port <b>1</b> of egress E<b>1</b>. Note that queues Q<b>1</b> and Q<b>2</b> can have different COSs associated therewith. <figref idref="DRAWINGS">FIG. 10</figref>, for instance, depicts COS<b>1</b> for queue Q<b>1</b> and COS<b>2</b> for queue Q<b>2</b>. In this example, queue Q<b>1</b> or queue Q<b>2</b> (which are both bound for the same port of the same egress) is selected in the first level of selection at block <b>1018</b>. Specifically, in this embodiment, the queue having the highest priority is selected at this first level—queue Q<b>1</b> in <figref idref="DRAWINGS">FIG. 10</figref> (block <b>1026</b> shows this selection). <figref idref="DRAWINGS">FIG. 10</figref> depicts a similar decision tree in which queue Q<b>4</b> in ingress I<b>1</b> is selected at block <b>1028</b> from between queue Q<b>3</b> and queue Q<b>4</b> (block <b>1020</b>), both of which seek to communicate with port <b>2</b> of the same egress. A similar decision tree is depicted in <figref idref="DRAWINGS">FIG. 10</figref> within ingress I<b>2</b>. Specifically, queues Q<b>2</b> and Q<b>3</b> are selected at blocks <b>1030</b> and <b>1032</b> in the first level within ingress I<b>2</b>.

0134A second level of selection in a three-level process involves selecting, within each ingress or within the arbitration module <b>152</b>, a queue having a second priority from among the queues selected in the first level—that is, from the queues having first priorities. In other words, the second level involves selecting a queue for each ingress from those queues that seek to communicate with different ports of the same egress. If this second level is performed within the arbitration module <b>152</b>, the fullness state of the FIFOs can be used so that a queue seeking connection to a full FIFO will not be selected. <figref idref="DRAWINGS">FIG. 10</figref> shows for ingress I<b>1</b> the selection in the first level of queue Q<b>1</b> bound for port <b>1</b> (block <b>1026</b>) and queue Q<b>4</b> bound for port <b>2</b> (block <b>1028</b>) of the same egress. The system then selects between these two queues in the second level at block <b>1034</b>, based on the priorities of these queues, and <figref idref="DRAWINGS">FIG. 10</figref> depicts the selection of queue Q<b>1</b> bound for port <b>1</b> in this second level at block <b>1038</b>. Specifically, queue Q<b>1</b> is selected because priority P<b>1</b> for queue Q<b>1</b> is higher than priority P<b>4</b> for queue Q<b>4</b>. Similarly, queue Q<b>3</b> within ingress I<b>2</b> is selected at block <b>1040</b> in the second level from a comparison between queue Q<b>2</b> and queue Q<b>3</b> at block <b>1036</b>.

0135The third and final level of selection in a three-level process involves selecting an ingress (from queues having second priorities) for each egress such that no egress is connected to more than one ingress. Such a third level is performed in the arbitration module <b>152</b> and not within an ingress such that priorities with which each ingress desires each egress may be present. In other words, for each group of queues having second priorities and being bound for a particular egress, a queue is selected such that each egress is connected to only a single ingress. In one embodiment, the queue having the highest priority is selected.

0136Referring to <figref idref="DRAWINGS">FIG. 10</figref>, queue Q<b>1</b> within ingress I<b>1</b> and queue Q<b>3</b> within ingress I<b>2</b> were selected in the second level at blocks <b>1038</b> and <b>1040</b>. A selection is made based on a comparison of the priorities (priority P<b>1</b> and priority P<b>3</b>) of these two queues at block <b>1042</b>. In <figref idref="DRAWINGS">FIG. 10</figref>, queue Q<b>3</b> has been selected in this third level at block <b>1044</b>. Because queue Q<b>3</b> is within ingress I<b>2</b>, ingress I<b>2</b> is connected to the egress in this embodiment, and queue Q<b>3</b> is the queue that is serviced. It should be noted that <figref idref="DRAWINGS">FIG. 10</figref> depicts a simplified procedure in which only two ingresses are present and all of the depicted queues are bound for the same egress. More generally, at the third level of selection, for instance, ingresses are selected for each of a plurality of egresses. Also, because a single ingress can have two or more queues with the highest priority for two or more egresses, the queue from this ingress having the highest priority will be chosen for communication to the egress, leaving the other queues within that ingress to contend for communication in subsequent timeslots.

0137<figref idref="DRAWINGS">FIG. 10</figref> also shows the information that can be used to break a tie at any of the three levels of selection. Each queue of <figref idref="DRAWINGS">FIG. 10</figref> has associated therewith a least recently used (LRU) number. The LRU number is a variable that indicates a length of time since the queue was last serviced or a scaled number that generally indicates how long the queue has gone since being serviced. The LRU number can also represent the position in a total ordering of the queues, where the ordering is based on increasing lengths of time since each queue was last serviced. For instance, queue Q<b>1</b> of ingress I<b>1</b> has LRU<b>1</b> (block <b>1002</b>) and queue Q<b>2</b> has LRU<b>2</b> (block <b>1004</b>). If the priority P<b>1</b> of queue Q<b>1</b> is the same as the priority P<b>2</b> of queue Q<b>2</b> at block <b>1018</b>, the LRU numbers can be used to break the tie in that level of selection. Thus, if a comparison between LRU<b>1</b> from queue Q<b>1</b> and LRU<b>2</b> from queue Q<b>2</b> in block <b>1018</b> indicates that queue Q<b>1</b> has gone longer since being serviced, queue Q<b>1</b> will be selected in the first level of selection. The LRU number can also be sent with each queue and priority selected in the second level from an ingress to the arbitration module <b>152</b> so that ties can be broken in the arbitration module <b>152</b> using the least recently used (LRU) information. The arbitration module <b>152</b> can also store its own LRU information regarding which egress port was selected and when each ingress was connected to each egress.

0138<figref idref="DRAWINGS">FIG. 11</figref> illustrates another embodiment of a queue selection procedure using a block diagram of the system <b>100</b> in accordance with one embodiment of the invention. In this embodiment of the invention, a queue within an ingress can be reserved for packets that are bound for more than one egress. Such packets are referred to as “multicast” packets throughout this specification, and queues containing these packets can be referred to as “multicast” queues. Queue Q<b>2</b> in each of ingresses I<b>1</b>, I<b>2</b>, and I<b>3</b> in <figref idref="DRAWINGS">FIG. 11</figref>, for instance, is bound for egresses E<b>1</b>, E<b>2</b>, and E<b>3</b>. Packets queued in queue Q<b>2</b>, therefore, will be bound for two or more of egresses E<b>1</b>, E<b>2</b>, and E<b>3</b>. One packet in queue Q<b>2</b> can be bound for egresses E<b>1</b>, E<b>2</b>, and E<b>3</b>, while another packet in queue Q<b>2</b> can be bound for egresses E<b>1</b> and E<b>3</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 11</figref>, if a queue having a packet that is bound for more than one egress is selected for communication over the shared link <b>108</b>, that queue can be connected to more than one egress during a single timeslot. The shared link <b>108</b>, therefore, can map a single ingress in a timeslot to more than one egress in this embodiment. If the number of ingresses is the same as the number of egresses, at least one of the ingresses would not be connected to the shared link <b>108</b> in that timeslot.

0139The selection scheme can vary when multicast queues are used. In one embodiment, a queue in an ingress having multicast packets is only selected for communication across the shared link <b>108</b> when the queue has the maximum priority for each egress associated with the multicast queue. In such an embodiment, for instance, queue Q<b>2</b> in ingress I<b>1</b> of <figref idref="DRAWINGS">FIG. 11</figref> can have the maximum priority for egress E<b>1</b> and E<b>2</b>, and still not be selected for communication across the shared link <b>108</b> because queue Q<b>2</b> does not have the maximum priority for egress E<b>3</b>. In another embodiment, only the packet at the head of the queue is reviewed to map ingresses to egresses. For instance, if queue Q<b>2</b> in ingress I<b>1</b> of <figref idref="DRAWINGS">FIG. 11</figref> contains a packet at the head of the queue that is bound for only egresses E<b>1</b> and E<b>2</b>, then queue Q<b>2</b> win be selected if it has the maximum priority for egress E<b>1</b> and E<b>2</b> regardless of whether queue Q<b>2</b>'s priority for egress E<b>3</b> is the maximum priority. Another embodiment can be where a multicast queue is selected for information transfer if it has the maximum priority for only a single egress. This embodiment may, however, not use bandwidth efficiently because the queue would be selected for multiple egresses without having the maximum priority for each egress.

0140Referring to <figref idref="DRAWINGS">FIG. 11</figref>, an example of a queue selection scheme using multicast packets can be described. In <figref idref="DRAWINGS">FIG. 11</figref>, two or three rounds of selection can be used as described above in connection with <figref idref="DRAWINGS">FIGS. 9 and 10</figref>. In a three-level selection scheme, the first level of selection can be performed within each ingress, the second level can be performed within each ingress or within the arbitration module <b>152</b>, and the third level of selection can be performed within the arbitration module <b>152</b>. Each ingress I<b>1</b>, I<b>2</b>, I<b>3</b> of <figref idref="DRAWINGS">FIG. 11</figref> contains the same type of queues. Within each ingress, a first level of selection can choose a queue from each group of queues bound for a particular port of a particular egress. Within the arbitration module <b>152</b>, a second level of selection can involve choosing a queue for each ingress from those queues that seek to communicate with different ports of the same egress. A third and final level of selection, performed within the arbitration module <b>152</b>, can then involve selecting an ingress for each egress.

0141<figref idref="DRAWINGS">FIG. 11</figref> depicts a two-level selection scheme. For ingress I<b>1</b> of <figref idref="DRAWINGS">FIG. 11</figref>, queues Q<b>1</b>, Q<b>2</b>, and Q<b>3</b> can each contain packets bound for egress E<b>1</b>. A queue having a maximum priority is therefore chosen from these three queues. Similarly, queues Q<b>2</b>, Q<b>3</b>, and Q<b>4</b> can contain packets bound for egress E<b>2</b>, and so a queue having a maximum priority is selected from these queues. In addition, queues Q<b>3</b> and Q<b>5</b> can contain packets destined for egress E<b>3</b>, and so a maximum priority is selected from these queues. Similar selections are performed for each of ingresses I<b>2</b> and I<b>3</b>. The arbitration module <b>152</b> can then select an ingress for each egress. In one embodiment, for instance, ingress I<b>1</b> can be selected for each of egress E<b>1</b>, E<b>2</b>, and E<b>3</b>. If this is the case, ingresses I<b>1</b> and I<b>2</b> will be idle during the given timeslot. Queue Q<b>2</b> or Q<b>3</b> in ingress It can therefore be connected to each of egresses E<b>1</b>, E<b>2</b>, and E<b>3</b> in this embodiment. In a second embodiment, ingress I<b>1</b> can be connected to egresses E<b>1</b> and E<b>2</b>, ingress I<b>2</b> can be idle, and ingress I<b>3</b> can be connected to egress E<b>3</b> during a given timeslot.

0142In one embodiment, a multicast queue can send the packet or packets to each of the queues with which it is associated when the multicast queue is selected for communication, regardless of whether the packet or packets are destined for each of the egresses. For instance, in <figref idref="DRAWINGS">FIG. 11</figref>, queue Q<b>3</b> of ingress I<b>2</b> can be selected for information transfer to each of the egresses E<b>1</b>, E<b>2</b>, and E<b>3</b>. One packet in queue Q<b>3</b> of ingress I<b>2</b>, however, may only be bound for egresses E<b>1</b> and E<b>2</b>. In one embodiment, this packet would be sent to each of the three egresses E<b>1</b>, E<b>2</b>, and E<b>3</b>, and then egress E<b>3</b> would disregard the packet because the packet would not contain header information indicating that it belongs in egress E<b>3</b>.

0143Any references to greater and lessor, front and back, right and left, top and bottom, upper and lower, and horizontal and vertical are intended for convenience of description, not to limit the present invention or its components to any one relational, positional or spatial orientation. All dimensions of the components in the attached Figures may vary with a potential design and the intended use of an embodiment of the invention without departing from the scope of the invention.

0144While the present invention has been described with reference to several embodiments thereof, those skilled in the art will recognize various changes that may be made without departing from the spirit and scope of the claimed invention. Accordingly, the invention is not limited to what is shown in the drawings and described in the specification, but only as indicated in the appended claims.