Simple fairness protocols for daisy chain interconnects
A method for transmitting packets, including forwarding a first set of upstream packets and a first set of local packets by inserting at least one of the first set of local packets between subsets of the first set of upstream packets according to a first insertion rate; calculating a second insertion rate after forwarding a predetermined number of upstream packets generated by a single upstream source, by dividing a cardinality of the first set of upstream packets by a greatest common divisor of the predetermined number and the cardinality of the first set of upstream packets; and forwarding a second set of upstream packets and a second set of local packets from the local switch to the downstream switch by inserting at least one of the second set of local packets between subsets of the second set of upstream packets according to the second insertion rate.
1. A method for transmitting packets, comprising:
forwarding a first set of upstream packets from a local switch to a downstream switch;
modifying, in the local switch, an upstream packet window counter (UPWC), wherein the UPWC is a 3-bit hardware counter that specifies how many back-to-back upstream packets can be forwarded, an upstream packet counter (UPC), and a plurality of upstream switch packet counters (USPCs) in response to forwarding the first set of upstream packets, wherein at least one of the plurality of USPCs equals a predetermined value after forwarding the first set of upstream packets;
forwarding a local packet from the local switch to the downstream switch after forwarding the first set of upstream packets;
setting a UPC register to a sum of the plurality of USPCs, setting a UPWC register to the sum after performing a plurality of bitwise right shift operations on the sum, and setting the plurality of USPCs to zero;
forwarding, after setting the plurality of USPCs to zero, a second set of upstream packets from the local switch to the downstream switch;
modifying the UPWC, the UPC, and the plurality of USPCs in response to forwarding the second set of upstream packets, wherein each of the plurality of USPCs is less than the predetermined value after forwarding the second set of upstream packets;
restoring the UWPC to a value of the UPWC register after forwarding the second number of packets; and
forwarding, after restoring the UWPC, a third set of upstream packets from the local switch to the downstream switch.
2. The method of claim 1 , further comprising:
decrementing the UPC and the UPWC in response to forwarding each of the first set of upstream packets.
3. The method of claim 1 , further comprising:
decrementing the UPC and the UPWC in response to forwarding each of the second set of upstream packets, wherein the UPWC is zero after forwarding the second set of upstream packets.
4. The method of claim 1 , further comprising:
dividing the UPC register by a greatest common divisor of the predetermined value and the sum before forwarding the second plurality of upstream packets.
5. The method of claim 1 , further comprising:
decrementing a local packet counter (LPC) in response to forwarding the local packet; and
setting a LPC register to the predetermined value before forwarding the second set of upstream packets.
6. The method of claim 5 , further comprising:
dividing the LPC register by a greatest common divisor of the predetermined value and the sum before forwarding the second set of upstream packets.
7. The method of claim 5 , further comprising:
setting the LPC to the predetermined value before forwarding the second set of upstream packets.
8. The method of claim 7 , further comprising:
dividing the LPC by a greatest common divisor of the predetermined value and the sum before forwarding the second set of upstream packets.
9. The method of claim 5 , further comprising:
restoring the UPC to a value of the UPC register before forwarding the third set of upstream packets; and
restoring the LPC to a value of the LPC register before forwarding the third set of upstream packets,
wherein the UPC is zero and the LPC is zero after forwarding the second set of upstream packets.
10. The method of claim 1 , further comprising:
setting, before forwarding the second set of upstream packets, the UPC to the sum; and
setting, before forwarding the second set of upstream packets, the UPWC to the sum after performing the plurality of bitwise right shift operations on the sum.
11. The method of claim 10 , further comprising:
dividing the UPC by a greatest common divisor of the predetermined value and the sum before forwarding the second plurality of upstream packets.
12. The method of claim 1 , wherein the predetermined value is 8 and the plurality of bitwise right shift operations has a cardinality of 3.
13. The method of claim 1 , wherein at least one selected from a group consisting of the first set of upstream packets, the second set of upstream packets, and the third set of upstream packets has a cardinality of 1.
14. The method of claim 1 , wherein an upstream packet of the first set of upstream packets is generated by an upstream source operatively connected to the local switch, and wherein the upstream packet comprises a memory request for a data item in a memory associated with the downstream switch.
15. The method of claim 1 , wherein the local switch and the downstream switch are located on a single chip.
16. The method of claim 1 , further comprising:
storing the sum in an aggregate upstream packet counter (AUPC); and
setting the AUPC to zero before forwarding the second set of upstream packets.