TRANSACTION SELECTOR EMPLOYING TRANSACTION QUEUE GROUP PRIORITIES IN MULTI-PORT SWITCH
First Claim
1. An apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the apparatus comprising:
- a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to;
a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and
selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators.
4 Assignments
0 Petitions
Accused Products
Abstract
An apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch. The apparatus includes a group indicator, for each of the queues, for indicating which one of a plurality of groups of the queues the queue belongs to. The apparatus also includes a group priority indicator, for each group of the plurality of groups, for indicating a priority of the group, the priority indicating a priority for transmitting transactions of the queues of the group relative to other groups of the plurality of groups. The apparatus includes selection logic, coupled to the group indicators and the priority indicators, configured to select a queue of the queues, for transmitting out of the port a transaction thereof, based on the group indicators and the group priority indicators.
136 Citations
76 Claims
-
1. An apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the apparatus comprising:
-
a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to; a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A method for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the method comprising:
-
grouping the plurality of transaction queues into a plurality of groups; specifying a transmit priority for each of the plurality of groups; and selecting for transmitting one of the plurality of transaction queues from one of the plurality of groups having a highest of the transmit priorities that includes at least one of the plurality of transaction queues having a transmittable transaction, in response to said grouping and said specifying the transmit priorities. - View Dependent Claims (23, 24, 25)
-
-
26. A port in a switch for transmitting transactions from a plurality of transaction queues in a prioritized but fair manner, comprising:
-
a port interface, configured to transmit transactions; and a transaction selector, coupled for selecting the plurality of transaction queues for transaction transmission, said transaction selector comprising; a group indicator, for each transaction queue of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transaction queues said transaction queue belongs to; a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out the port a transaction thereof, based on said group indicators and said group priority indicators. - View Dependent Claims (27, 28, 29, 30)
-
-
31. A computer program product for use with a computing device, the computer program product comprising:
a computer usable storage medium, having computer-readable program code embodied in said medium, for providing an apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, said computer-readable program code comprising; first program code for providing a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to; second program code for providing a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and third program code for providing selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators.
-
32. A method for providing an apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the method comprising:
-
providing computer-readable program code describing the switch core, the program code comprising; first program code for providing a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to; second program code for providing a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and third program code for providing selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators; and transmitting the computer-readable program code as a computer data signal on a network.
-
-
33. A switch, comprising:
-
a network; and a plurality of ports, each coupled to receive transactions from other of said plurality of ports via said network, each of said ports comprising; a port interface, configured to transmit said transactions to a device coupled to said port; a plurality of transaction queues, configured to receive said transactions from said network wherein each of said plurality of transaction queues belongs to a group of one of a plurality of groups wherein each of said plurality of groups has a priority for transmitting transactions relative to other groups of said plurality of groups; and a transaction selector, coupled to said port interface and to said plurality of transaction queues, configured to select a transaction queue of the plurality of transaction queues for transmitting out the port a transaction thereof based on said groups and said priorities. - View Dependent Claims (34, 35, 41, 42, 43, 44, 45, 68, 69, 70)
-
-
36. An apparatus for selecting one of N transaction queues from which to transmit a transaction out of a port of a switch, the N transaction queues each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, the apparatus comprising:
-
G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N transaction queues, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, said input vector having a single bit true corresponding to a last one of the N transaction queues selected for transmitting in a corresponding one of the G groups; N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select for output one of said G inputs specified by the corresponding transaction queue'"'"'s group; and selection logic, coupled to receive a transaction from each of the N transaction queues and to select for transmitting out the port one of said N transactions corresponding to one of the N transaction queues having a transmit value greater than or equal to any of the N transaction queues left thereof in said N-bit input vectors; wherein said transmit value of each of the N transaction queues comprises a least-significant bit equal to said corresponding G-input mux output, a most-significant bit that is true if said corresponding transaction is transmittable, and middle bits comprising the priority of the transaction queue'"'"'s group. - View Dependent Claims (37, 38, 39, 40)
-
-
46. A method for selecting one of N transaction queues from which to transmit a transaction out of a port of a switch, the N transaction queues each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, the method comprising:
-
generating G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N transaction queues, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, the input vector having a single bit true corresponding to a last one of the N transaction queues selected for transmitting in a corresponding one of the G groups; for each of the N transaction queues, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as a round-robin bit one of the G received corresponding one of the N bits of each of the G round-robin vectors specified by the corresponding transaction queue'"'"'s group; and receiving a transaction from each of the N transaction queues, and selecting for transmitting out the port one of the N transactions corresponding to one of the N transaction queues having a transmit value greater than or equal to any of the N transaction queues left thereof in the N-bit input vectors; wherein the transmit value of each of the N transaction queues comprises a least-significant bit equal to the round-robin bit of the transaction queue, a most-significant bit that is true if the corresponding transaction of the transaction queue is transmittable, and middle bits comprising the priority of the transaction queue'"'"'s group. - View Dependent Claims (47)
-
-
48. A switch port for transmitting transactions from N transaction queues, each of the N transaction queues being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N transaction queues may have a transmittable transaction in a selection cycle, the port configured to transmit transactions of the N transaction queues in a round-robin fashion within each of the G groups independent of the other G groups, comprising:
-
G round-robin circuits, each for generating an N-bit round-robin vector for a corresponding one of the G groups, wherein said N-bits correspond to the N transaction queues, each of said G round-robin circuits comprising; a first input, for receiving a first corresponding N-bit value specifying which of the N transaction queues was last selected in said group to transmit a transaction; a second input, for receiving a second corresponding N-bit value, each of said N bits being false if said corresponding transaction queue has a transmittable transaction and is in said group; a barrel incrementer, coupled to receive said first and second inputs, configured to 1-bit left-rotatively increment said second value by said first value to generate a sum; and combinational logic, coupled to said barrel incrementer, configured to generate from said sum and said second value said N-bit round-robin vector specifying which of the N transaction queues is selected next from which to transmit a transaction; N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select one of said G inputs specified by the group of the corresponding transaction queue as a round-robin bit for said associated transaction queue; and selection logic, coupled to said N G-input muxes, configured to select one of the N transaction queues for transmitting a transaction thereof out of the port, wherein said selection logic selects said one of the N transaction queues having said round robin bit set, having a transmittable transaction, and being in a group having said priority a highest of the P priorities having one of the plurality of transaction queues with a transmittable transaction. - View Dependent Claims (71, 72, 73)
-
-
49. A method for generating a round-robin bit for use in selecting one of N transaction queues for transmitting a transaction out a port of a switch, the N transaction queues each being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N transaction queues may have a transmittable transaction in a selection cycle, the method comprising:
-
generating G N-bit round-robin vectors each for a corresponding one of the G groups, wherein the N-bits correspond to the N transaction queues, said generating each of the G N-bit round-robin vectors comprising; receiving a first corresponding N-bit value specifying which of the N transaction queues was last selected in the group to transmit a transaction; receiving a second corresponding N-bit value, each of the N bits being false if the corresponding transaction queue has a transmittable transaction and is in the group; 1-bit left-rotatively incrementing the second value by the first value to generate a sum; and generating from the sum and the second value the N-bit round-robin vector specifying which of the N transaction queues is selected next to transmit a transaction; and for each of the N transaction queues, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as the round-robin bit for the corresponding transaction queue one of the G received bits specified by the group of said transaction queue. - View Dependent Claims (74, 75, 76)
-
-
50. A bifurcated selector for transmitting transactions out a port of a switch from a plurality of transaction queues, the selector comprising:
-
a transaction scheduler, configured to transmit transactions of the plurality of transaction queues out the port; a policy manager, for prescribing a scheduling policy of the plurality of transaction queues; and an interface, coupling said policy manager to the transaction scheduler, said interface comprising; first signals, for said transaction scheduler to receive from said policy manager a group indicator for each of the plurality of transaction queues for indicating one of a plurality of groups to which the transaction queue belongs; and second signals, for said transaction scheduler to receive from said policy manager a priority for each of said plurality of groups, wherein said transaction scheduler transmits said transactions out of the port based on said group priorities and said group indicators; and third signals, for said policy manager to receive transaction transmission information for each of the plurality of transaction queues, wherein said policy manager updates said group indicators based on said transaction transmission information, wherein said transaction transmission information comprises an indication of which of the plurality of transaction queues a transaction was transmitted from. - View Dependent Claims (51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65)
-
-
66. A method for transmitting transactions out a port of a switch from a plurality of transaction queues, the method comprising:
-
signaling, during a first clock cycle, by a policy manager to a transaction scheduler a group indicator for each of the plurality of transaction queues for indicating one of a plurality of transaction queue groups to which the transaction queue belongs, and a group scheduling priority for each of the plurality of groups; transmitting a transaction out the port, during a second clock cycle, by the transaction scheduler from one of the plurality of transaction queues, in response to said signaling the group indicators and the group scheduling priorities; and signaling, during a third clock cycle subsequent to the first clock cycle, by the transaction scheduler to the policy manager an indication whether the transaction scheduler transmitted a transaction from each of the plurality of transaction queues. - View Dependent Claims (67)
-
Specification