Load balancer for parallel link networks using weighted round robin scheduling

Patent metadata

Field	Value
Publication number	US-12309076-B1
Application number	US-202318397072-A
Country	US
Kind code	B1
Filing date	Dec 27, 2023
Priority date	Dec 27, 2023
Publication date	May 20, 2025
Grant date	May 20, 2025

Abstract

Approaches disclosed herein provide for the use of load balancers to perform tasks such as to queue traffic. In at least one embodiment, a plurality of parallel links queue traffic by, at least in part, representing a weight of the plurality of parallel links as a plurality of bit strings, where the plurality of bit strings are converted to a plurality of sparse bit strings, and where the plurality of sparse bit strings to be used to generate a representative vector of sequentially interleaved bits of the plurality of sparse bit strings. The traffic for the plurality of parallel links can be queued according to the representative vector. The load balancer may be used in a computer network to manage traffic between nodes connected by parallel links.

First claim

What is claimed is:

1. A processor, comprising one or more circuits to:
map individual weights of a plurality of parallel links to a plurality of bit strings;
transform the plurality of bit strings into a plurality of sparse bit strings;
cause a vector to be generated representing bits interleaved sequentially from the plurality of sparse bit strings; and
schedule, based at least in part on the vector, assignments for the plurality of parallel links.

2. The processor of claim 1 , wherein the one or more circuits are further to:
determine, based at least in part on the assignments to be scheduled, the individual weights of the plurality of parallel links.

3. The processor of claim 1 , wherein a combined number of bits having a shared value of individual bit strings of the plurality of bit strings equal the individual weights of the individual bit strings, the shared value being assigned to indicate the weight.

4. The processor of claim 1 , wherein the one or more circuits are further to:
identify two or more available links connecting a scheduled origin and two or more intermediary as the plurality of parallel links.

5. The processor of claim 4 , wherein the two or more intermediary comprise any two nodes connected to the scheduled origin node by parallel links.

6. The processor of claim 1 , wherein the vector is generated using a pre-configured mapping function.

7. The processor of claim 6 , wherein the pre-configured mapping function comprises a randomizer or linear-feedback shift register (LFSR) machine.

8. The processor of claim 1 , wherein the one or more circuits are further to:
determine a plurality of ports of the plurality of parallel links having more capacity than at least one other port; and
send the scheduled assignments using the plurality of ports.

9. The processor of claim 1 , wherein the plurality of parallel links are configured to be scheduled assignments according to a weighted round-robin schedule.

10. The processor of claim 1 , wherein the assignments comprise one or more packets to be scheduled from at least one switch connected to the plurality of parallel links.

11. A method, comprising:
mapping individual weights of a plurality of parallel links to a plurality of bit strings;
transforming the plurality of bit strings into a plurality of sparse bit strings;
generating a vector representing bits interleaved sequentially from the plurality of sparse bit strings; and
scheduling, based at least in part on the vector, assignments for the plurality of parallel links.

12. The method of claim 11 , further comprising:
determining, based at least in part on the assignments to be scheduled, the individual weights of the plurality of parallel links.

13. The method of claim 11 , wherein a combined number of bits having a shared value of individual bit strings of the plurality of bit strings equal the individual weights of the individual bit strings, the shared value being assigned to indicate the weight.

14. The method of claim 11 , further comprising:
identify two or more available links connecting a scheduled origin and two or more intermediary as the plurality of parallel links.

15. The method of claim 11 , further comprising:
determining a plurality of ports of the plurality of parallel links having more capacity than at least one other port; and
sending the scheduled assignments using the plurality of ports.

16. The method of claim 11 , wherein the plurality of parallel links are configured to be scheduled assignments according to a weighted round-robin schedule.

17. A system, comprising:
one or more processors to queue traffic for a plurality of parallel links by, at least in part, representing a weight of the plurality of parallel links as a plurality of bit strings, wherein the plurality of bit strings are converted to a plurality of sparse bit strings, the plurality of sparse bit strings to be used to generate a representative vector of sequentially interleaved bits of the plurality of sparse bit strings, the traffic for the plurality of parallel links to be queued according to the representative vector.

18. The system of claim 17 , wherein a combined number of bits having a shared value of individual bit strings of the plurality of bit strings equal the individual weights of the individual bit strings, the shared value being assigned to indicate the weight.

19. The system of claim 17 , wherein the plurality of bit strings are converted using thermometer coding.

20. The method of claim 17 , wherein the plurality of parallel links are queued traffic using a weighted round-robin scheduler.

Assignees

• Mellanox Technologies Ltd

Inventors

• Beracha Eran Gil
• Mund Tal
• Mey-Tal Gil

Classifications

• H04L45/24

  Multipath · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title

• H04L47/6225

  Fixed service order, e.g. Round Robin · CPC title

• H04L47/623 Primary

  Weighted service order · CPC title