# US 2026/0113274 A1 · Optimizing tree-based collective communication operations by load-balancing network endpoints

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0113274 A1
- Document ID: US20260113274A1
- Status: Published application
- Kind: A1
- Application number: 18/922,388
- Filed: 2024-10-22
- Published: 2026-04-23
- Earliest claimed: 2024-10-22
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Mohammad Saifee DOHADWALA; Daniel SANTOS FERREIRA ALVES; Michael Konstantinos PAPAMICHAEL; David Andreas SIDLER; Zhipeng ZHAO
- Web page: https://patentgrep.com/patent/US20260113274A1

## CPC

- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 41/12: Discovery or management of network topologies
- H04L 45/02: Topology update or discovery
- H04L 45/48: Routing tree calculation
- H04L 45/484: using multiple routing trees
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The present disclosure generally relates to optimizing load-balancing of network endpoints using tree collectives representing a logical network communication topology for the network endpoints. Systems and methods described herein eliminate the previously restrictive conditions imposed on tree-based communication collectives by generating collective trees with any arity and representing any number of physical network endpoints. The resulting collective trees ensure that each represented network endpoint has a number of outgoing flows and a number of incoming flows that are no more than the arity of the collective tree. In this way, the described systems and methods inject significant efficiencies into communication collectives within networked compute nodes by eliminating communication bandwidth latencies and bottlenecks.

## Claims

### Claim 1

A method for optimizing load-balancing of a plurality of network endpoints comprising:
generating a collective tree representing a logical network communication topology for the plurality of network endpoints by:
identifying a plurality of nodes representing the plurality of network endpoints,
generating a first subtree of the collective tree as a breadth-first search subtree comprising the plurality of nodes according to an arity of the collective tree,
generating additional subtrees such that a total number of subtrees is equal to the arity of the collective tree by rotating the plurality of nodes from the first subtree such that any node in the plurality of nodes is a non-leaf node once across all subtrees of the collective tree, and
combining the first subtree and the additional subtrees; and
applying the logical network communication topology represented by the collective tree to the plurality of network endpoints to balance network communications such that each network endpoint has a number of outgoing flows no greater than the arity of the collective tree and a number of incoming flows no greater than the arity of the collective tree.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein generating the collective tree further comprises, prior to generating the first subtree and the additional subtrees, setting aside a subset of the plurality of nodes based on the arity of the collective tree.

### Claim 3 (depends on 2)

The method as recited in claim 2, wherein generating the collective tree further comprises, while generating the first subtree and the additional subtrees, inserting the subset of the plurality of nodes back into the first subtree and the additional subtrees by replacing existing leaves in the first subtree and the additional subtrees with the subset of the plurality of nodes and adding any replaced leaves back into the first subtree and the additional subtrees as children of the subset of the plurality of nodes.

### Claim 4 (depends on 1)

The method as recited in claim 1, wherein generating the collective tree further comprises:
identifying a root node from the plurality of nodes based on a type of the collective tree; and
excluding the root node from generating the first subtree and the additional subtrees,
wherein combining the first subtree and the additional subtrees utilizes the root node.

### Claim 5 (depends on 4)

The method as recited in claim 4, wherein the type of the collective tree comprises a reduce collective.

### Claim 6 (depends on 4)

The method as recited in claim 4, wherein the type of the collective tree comprises a broadcast collective.

### Claim 7 (depends on 1)

The method as recited in claim 1, wherein a number of steps to complete a collective among the plurality of network endpoints after the logical network communication topology represented by the collective tree is applied comprises two times a logarithm of a number of the plurality of network endpoints.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein the arity of the collective tree is user-defined.

### Claim 9

A system comprising:
at least one processor;
memory in electronic communication with the at least one processor; and
instructions stored in the memory, the instructions being executable by the at least one processor to:
generate a collective tree representing a logical network communication topology for a plurality of network endpoints by:
identifying a plurality of nodes representing the plurality of network endpoints,
generating a first subtree of the collective tree as a breadth-first search subtree comprising the plurality of nodes according to an arity of the collective tree,
generating additional subtrees such that a total number of subtrees is equal to the arity of the collective tree by rotating the plurality of nodes from the first subtree such that any node in the plurality of nodes is a non-leaf node once across all subtrees of the collective tree, and
combining the first subtree and the additional subtrees; and
apply the logical network communication topology represented by the collective tree to the plurality of network endpoints to balance network communications such that each network endpoint has a number of outgoing flows no greater than the arity of the collective tree and a number of incoming flows no greater than the arity of the collective tree.

### Claim 10 (depends on 9)

The system as recited in claim 9, further storing instructions being executable by the at least one processor to further generate the collective tree by, prior to generating the first subtree and the additional subtrees, setting aside a subset of the plurality of nodes based on the arity of the collective tree.

### Claim 11 (depends on 10)

The system as recited in claim 10, further storing instructions being executable by the at least one processor to further generate the collective tree by, while generating the first subtree and the additional subtrees, inserting the subset of the plurality of nodes back into the first subtree and the additional subtrees by replacing existing leaves in the first subtree and the additional subtrees with the subset of the plurality of nodes and adding any replaced leaves back into the first subtree and the additional subtrees as children of the subset of the plurality of nodes.

### Claim 12 (depends on 9)

The system as recited in claim 9, further storing instructions being executable by the at least one processor to further generate the collective tree by:
identifying a root node from the plurality of nodes based on a type of the collective tree; excluding the root node from generating the first subtree and the additional subtrees;
wherein combining the first subtree and the additional subtrees utilizes the root node.

### Claim 13 (depends on 12)

The system as recited in claim 12, wherein the type of the collective tree comprises a reduce collective.

### Claim 14 (depends on 12)

The system as recited in claim 12, wherein the type of the collective tree comprises a broadcast collective.

### Claim 15 (depends on 12)

The system as recited in claim 12, wherein a number of steps to complete a collective among the plurality of network endpoints after the logical network communication topology represented by the collective tree is applied comprises two times a logarithm of a number of the plurality of network endpoints.

### Claim 16 (depends on 12)

The system as recited in claim 12, wherein the arity of the collective tree is user-defined.

### Claim 17

A non-transitory computer-readable medium comprising instructions that when executed by one or more processors causes one or more computing devices to:
generate a collective tree representing a logical network communication topology for a plurality of network endpoints by:
identifying a plurality of nodes representing the plurality of network endpoints,
generating a first subtree of the collective tree as a breadth-first search subtree comprising the plurality of nodes according to an arity of the collective tree,
generating additional subtrees such that a total number of subtrees is equal to the arity of the collective tree by rotating the plurality of nodes from the first subtree such that any node in the plurality of nodes is a non-leaf node once across all subtrees of the collective tree, and
combining the first subtree and the additional subtrees; and
apply the logical network communication topology represented by the collective tree to the plurality of network endpoints to balance network communications such that each network endpoint has a number of outgoing flows no greater than the arity of the collective tree and a number of incoming flows no greater than the arity of the collective tree.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium as recited in claim 17, further comprising instructions that when executed by the one or more processors causes the one or more computing devices to further generate the collective tree by:
prior to generating the first subtree and the additional subtrees, setting aside a subset of the plurality of nodes based on the arity of the collective tree; and
while generating the first subtree and the additional subtrees, inserting the subset of the plurality of nodes back into the first subtree and the additional subtrees by replacing existing leaves in the first subtree and the additional subtrees with the subset of the plurality of nodes and adding any replaced leaves back into the first subtree and the additional subtrees as children of the subset of the plurality of nodes.

### Claim 19 (depends on 17)

The non-transitory computer-readable medium as recited in claim 17, further comprising instructions that when executed by the one or more processors causes the one or more computing devices to further generate the collective tree by:
identifying a root node from the plurality of nodes based on a type of the collective tree;
excluding the root node from generating the first subtree and the additional subtrees;
wherein combining the first subtree and the additional subtrees utilizes the root node.

### Claim 20 (depends on 17)

The non-transitory computer-readable medium as recited in claim 17, wherein a number of steps to complete a collective among the plurality of network endpoints after the logical network communication topology represented by the collective tree is applied comprises two times a logarithm of a number of the plurality of network endpoints.
