# US 12,764,070 B2 · Dynamic maximum throughput capacity-based load balancing for adaptive routing in high-performance networks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,764,070 B2 - Document ID: US12764070B2 - Status: Granted - Kind: B2 - Application number: 18/810,394 - Filed: 2024-08-20 - Published: 2025-02-13 - Granted: 2026-10-13 - Earliest claimed: 2021-06-25 - Assignees: Cornelis Networks, Inc. - Applicants: Cornelis Networks, Inc. - Inventors: Gary Muntz - Web page: https://patentgrep.com/patent/US12764070B2 ## CPC - H04L 47/125: by balancing the load, e.g. traffic engineering - H04L 49/25: Routing or path finding in a switch fabric - H04L 49/90: Buffering arrangements - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A switch is provided for routing packets in an interconnection network. The switch includes a plurality of egress ports to transmit packets and one or more ingress ports to receive packets. The switch also includes a network capacity circuit for obtaining network capacity for transmitting packets via the plurality of egress ports. The switch also includes a port sequence generation circuit configured to generate a port sequence that defines a pseudo-randomly interleaved sequence of a plurality of path options via the plurality of egress ports, based on the network capacity. The switch also includes a routing circuit for routing one or more packets, received from the one or more ingress ports, towards a destination, based on the port sequence. ## Claims ### Claim 1 A switch for routing packets in an interconnection network, the switch comprising: a plurality of egress ports to transmit packets; one or more ingress ports to receive packets; a network capacity circuit configured to obtain network capacity for transmitting packets via the plurality of egress ports, wherein the network capacity indicates a dynamic maximum throughput capacity of each egress port to carry new traffic, wherein the dynamic maximum throughput capacity is distinct from current utilization and represents a maximum amount of additional traffic each egress port can accommodate, wherein the dynamic maximum throughput capacity is variable over time as a direct result of changes in utilization of each egress port, and wherein the dynamic maximum throughput capacity is for being calculated based on a difference between a fixed physical bandwidth of each egress port and the current utilization; a port sequence generation circuit configured to generate a port sequence that defines a pseudo-randomly interleaved sequence of a plurality of path options via the plurality of egress ports, based on the network capacity; and a routing circuit configured to route one or more packets, received from the one or more ingress ports, towards a destination, based on the port sequence. ### Claim 2 (depends on 1) The switch of claim 1, wherein: the port sequence generation circuit is configured to: generate a plurality of port sequences, wherein each port sequence pseudo-randomly interleaves the plurality of path options, via the plurality of egress ports, according to the network capacity, wherein each port sequence corresponds to (i) a respective virtual lane of a plurality of virtual lanes and (ii) a respective next switch of a plurality of next switches, and wherein each virtual lane has dynamic bandwidth; and generate a dynamic port table of egress port identifiers, wherein each row of the dynamic port table corresponds to a respective next switch of a plurality of next switches, wherein each column of the dynamic port table corresponds to a respective virtual lane of a plurality of virtual lanes, and wherein each egress port identifier corresponds to a respective port sequence of the plurality of port sequences; and the routing circuit is configured to: route a plurality of packets, received from one or more ingress ports, to the plurality of next switches, based on the dynamic port table. ### Claim 3 (depends on 2) The switch of claim 2, wherein the port sequence generation circuit is configured to update the dynamic port table, based on the plurality of port sequences, after the routing circuit routes a packet of the plurality of packets. ### Claim 4 (depends on 2) The switch of claim 2, wherein: the interconnection network includes a plurality of dimensions; the network capacity includes information regarding capacity of the interconnection network to transmit packets towards the destination via the switch and using the plurality of dimensions; each port sequence further corresponds to a respective dimension of the plurality of dimensions; the dynamic port table includes a plurality of sub-tables of egress port identifiers, each sub-table corresponding to a respective dimension; and the routing circuit is configured to route the plurality of packets by selecting a dimension from the plurality of dimensions, based on comparing network capacities for the interconnection network to transmit packets towards the destination using each dimension. ### Claim 5 (depends on 4) The switch of claim 4, wherein the routing circuit is configured to: in accordance with a determination that network capacity for the interconnection network to transmit packets towards the destination via a first dimension of the plurality of dimensions, does not meet a predetermined threshold, forgo selecting the first dimension for routing the plurality of packets. ### Claim 6 (depends on 4) The switch of claim 4, wherein the routing circuit is configured to: in accordance with a determination that network capacity for the interconnection network to transmit packets towards the destination, via a first dimension or via second dimension of the plurality of dimensions, meets a predetermined threshold, spread the plurality of packets over the first dimension and the second dimension. ### Claim 7 (depends on 4) The switch of claim 4, wherein the routing circuit is configured to: prior to routing the plurality of packets, for each packet: (i) extract subfields in a header of the packet, and (ii) index a static lookup table for each dimension using the subfields to select a row in a respective sub-table for the dimension. ### Claim 8 (depends on 1) The switch of claim 1, wherein the plurality of path options includes non-minimal routes via a corresponding intermediate switch, in addition to minimal routes without any intermediate switches. ### Claim 9 (depends on 1) The switch of claim 1, wherein the routing circuit is configured to: prioritize path options that include minimal routes over path options that include non-minimal routes, when routing the one or more packets. ### Claim 10 (depends on 8) The switch of claim 8, wherein the routing circuit is configured to: in accordance with a determination that path options that include minimal routes do not meet a threshold network capacity, select other path options that include non-minimal routes for routing the one- or more packets. ### Claim 11 (depends on 1) The switch of claim 1, wherein the network capacity includes buffer capacity at the plurality of egress ports. ### Claim 12 (depends on 1) The switch of claim 1, wherein the network capacity includes bandwidth of the plurality of egress ports. ### Claim 13 (depends on 1) The switch of claim 1, wherein the port sequence generation circuit is configured to: use each path option in a fraction of time slots of the port sequence such that a probability of a corresponding egress port appearing in the port sequence is proportional to the network capacity through the corresponding egress port. ### Claim 14 (depends on 1) The switch of claim 1, wherein the network capacity corresponds to capacity of the interconnection network to transmit packets to a plurality of destinations via the switch. ### Claim 15 (depends on 1) The switch of claim 1, wherein the port sequence generation circuit is configured to: generate a plurality of port sequences, wherein each port sequence defines a pseudo-randomly interleaved sequence of the plurality of path options, via the plurality of egress ports, according to the network capacity, and wherein each port sequence corresponds to a respective next switch of a plurality of next switches. ### Claim 16 (depends on 1) The switch of claim 1, wherein the port sequence generation circuit is configured to: generate a plurality of port sequences, wherein each port sequence defines a pseudo-randomly interleaved sequence of the plurality of path options, via the plurality of egress ports, according to the network capacity, and wherein each port sequence corresponds to a respective virtual lane of a plurality of virtual lanes. ### Claim 17 (depends on 1) The switch of claim 1, wherein the network capacity circuit is further configured to: measure real-time port usage for each of the plurality of egress ports, the real-time port usage including an aggregate bandwidth. ### Claim 18 (depends on 1) The switch of claim 1, wherein the network capacity circuit is further configured to: determine the current utilization for each egress port based on a rate of packets being transmitted through the respective egress port; and update the dynamic maximum throughput capacity for each egress port over time in response to changes in the current utilization of the respective egress port. ### Claim 19 (depends on 1) The switch of claim 1, wherein the network capacity circuit is configured to: obtain a configured buffer value for each egress port; measure the current utilization of each egress port; and calculate the dynamic maximum throughput capacity for each egress port by subtracting the current utilization from the configured buffer value of the respective egress port. ### Claim 20 (depends on 1) The switch of claim 1, wherein the network capacity circuit is configured to: receive telemetry data from one or more next switches coupled to the plurality of egress ports, the telemetry data including buffer capacity information for the one or more next switches; and adjust the dynamic maximum throughput capacity of each egress port based on the received telemetry data.