# US 12,003,411 B2 · Systems and methods for on the fly routing in the presence of errors

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

- Number: US 12,003,411 B2
- Document ID: US12003411B2
- Status: Granted
- Kind: B2
- Application number: 17/594,712
- Filed: 2020-03-23
- Published: 2022-06-30
- Granted: 2024-06-04
- Earliest claimed: 2019-05-23
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Jonathan P. Beecroft; Edwin L. Froese
- Web page: https://patentgrep.com/patent/US12003411B2

## CPC

- G06F 13/1642: {with request queuing}
- G06F 9/5022: {Mechanisms to release resources}
- G06F 9/505: {considering the load}
- G06F 9/546: {Message passing systems or structures, e.g. queues}
- G06F 12/0862: with prefetch
- G06F 12/1036: for multiple virtual address spaces, e.g. segmentation (G06F12/1045 takes precedence)
- G06F 12/1063: {the data cache being concurrently virtually addressed}
- G06F 13/14: Handling requests for interconnection or transfer
- G06F 13/16: for access to memory bus (G06F13/28 takes precedence)
- G06F 13/1673: {using buffers}
- G06F 13/28: using burst mode transfer, e.g. direct memory access {DMA}, cycle steal (G06F13/32 takes precedence)
- G06F 13/385: {for adaptation of a particular data processing system to different peripheral devices}
- G06F 13/4022: {using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence)}
- G06F 13/4068: {Electrical coupling}
- G06F 13/4221: {being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus}
- G06F 13/4265: {on a point to point bus (G06F13/4247, G06F13/4282 take precedence)}
- G06F 15/17331: {Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]}
- H04L 1/0083: {Formatting with frames or packets; Protocol or part of protocol for error control}
- H04L 41/0893: Assignment of logical groups to network elements
- H04L 43/0876: Network utilisation, e.g. volume of load or congestion level
- H04L 43/10: Active monitoring, e.g. heartbeat, ping or trace-route
- H04L 45/02: Topology update or discovery
- H04L 45/021: Ensuring consistency of routing table updates, e.g. by using epoch numbers
- H04L 45/028: Dynamic adaptation of the update intervals, e.g. event-triggered updates
- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/125: based on throughput or bandwidth
- H04L 45/16: Multipoint routing
- H04L 45/20: {Hop count for routing purposes, e.g. TTL}
- H04L 45/22: {Alternate routing}
- H04L 45/24: Multipath
- H04L 45/38: {Flow based routing}
- H04L 45/42: Centralised routing
- H04L 45/46: {Cluster building}
- H04L 45/566: {Routing instructions carried by the data packet, e.g. active networks}
- H04L 45/70: {Routing based on monitoring results}
- H04L 45/745: Address table lookup; Address filtering
- H04L 47/11: Identifying congestion
- H04L 47/12: Avoiding congestion; Recovering from congestion
- H04L 47/122: by diverting traffic away from congested entities
- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 47/18: {End to end}
- H04L 47/20: Traffic policing
- H04L 47/22: Traffic shaping
- H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/2466: using signalling traffic
- H04L 47/2483: involving identification of individual flows
- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 47/323: {Discarding or blocking control packets, e.g. ACK packets}
- H04L 47/34: ensuring sequence integrity, e.g. using sequence numbers
- H04L 47/39: {Credit based}
- H04L 47/52: by attributing bandwidth to queues
- H04L 47/621: {Individual queue per connection or flow, e.g. per VC}
- H04L 47/6235: {Variable service order}
- H04L 47/626: {channel conditions}
- H04L 47/6275: based on priority
- H04L 47/629: Ensuring fair share of resources, e.g. weighted fair queuing [WFQ]
- H04L 47/76: using dynamic resource allocation, e.g. in-call renegotiation requested by the user or requested by the network in response to changing network conditions
- H04L 47/762: triggered by the network
- H04L 47/781: {Centralised allocation of resources}
- H04L 47/80: Actions related to the user profile or the type of traffic
- H04L 49/101: using crossbar or matrix
- H04L 49/15: Interconnection of switching modules
- H04L 49/30: {Peripheral units, e.g. input or output ports}
- H04L 49/3009: {Header conversion, routing tables or routing tags}
- H04L 49/3018: {Input queuing}
- H04L 49/3027: {Output queuing}
- H04L 49/90: Buffering arrangements
- H04L 49/9005: using dynamic buffer space allocation
- H04L 49/9021: {Plurality of buffers per packet}
- H04L 49/9036: {Common buffer combined with individual queues}
- H04L 49/9047: including multiple buffers, e.g. buffer pools
- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- H04L 69/22: Parsing or analysis of headers
- H04L 69/40: for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection (management of faults, events, alarms or notifications in data switching networks H04L41/06)
- G06F 13/1689: {Synchronisation and timing concerns (synchronisation on a memory bus G06F13/4234)}
- G06F 2212/50: Control mechanisms for virtual memory, cache or TLB
- G06F 2213/0026: PCI express
- G06F 2213/3808: Network interface controller
- H04L 12/4633: {Interconnection of networks using encapsulation techniques, e.g. tunneling}
- H04L 41/0895: Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
- H04L 45/28: using route fault recovery
- H04L 45/7453: using hashing
- H04L 69/28: Timers or timing mechanisms used in protocols
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Systems and methods are provided for “on the fly” routing of data transmissions in the presence of errors. Switches can establish flow channels corresponding to flows in the network. In response to encountering a critical error on a network link along a transmission path, a switch can generate an error acknowledgement. The switch can transmit the error acknowledgements to ingress ports upstream from the network link via the plurality of flow channels. By transmitting the error acknowledgement, it indicates that the network link where the critical error was encountered is a failed link to ingress ports upstream from the failed link. Subsequently, each ingress port upstream from the failed link can dynamically update the path of the plurality of flows that are upstream from the failed link such that the plurality of flows that are upstream from the failed link are routed in a manner that avoids the failed link.

## Claims

### Claim 1

A method of routing a plurality of data transmissions in a network having a plurality of switches, the method comprising:
establishing a plurality of flow channels corresponding to each of a plurality of flows comprising the plurality of data transmissions;
adaptively routing the plurality of flows through the network having a plurality of switches;
determining a critical error is encountered on a network link along a transmission path
in response to encountering the critical error on the network link along the transmission path, generating an error acknowledgement for each of a subset of the plurality of flows that are active on the network link;
transmitting the error acknowledgements to ingress ports upstream from the network link via the subset of the plurality of flow channels, wherein the error acknowledgement indicates the network link where the critical error was encountered as a failed link to ingress ports upstream from the failed link; and
at each ingress port upstream from the failed link, dynamically updating the transmission paths of the plurality of flow channels that are upstream from the failed link to route the subset of the plurality of flows that are upstream from the failed link in a manner that avoids the failed link.

### Claim 2 (depends on 1)

The method of claim 1, wherein dynamically updating the path comprises dynamically the updating routing tables.

### Claim 3 (depends on 2)

The method of claim 2, comprising:
at each ingress port along the transmission paths, updating routing tables to route new flows received at the ingress ports in a manner that avoids the network link.

### Claim 4 (depends on 1)

The method of claim 1, wherein dynamically updating the transmission paths comprises removing the failed link as eligible for use in routing minimally.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
in response to further encountering a critical error on the network link along the transmission path, providing a measure of the rate and type of errors on the link.

### Claim 6 (depends on 5)

The method of claim 5, wherein adaptive routing comprises:
utilizing the plurality of flow channels to select a path for a first packet in a flow for each of the plurality of flows.

### Claim 7 (depends on 6)

The method of claim 6, wherein adaptive routing further comprises:
utilizing the plurality of flow channels to force subsequent packets in a flow to follow the same path taken by the first packet to maintain an ordering of the packets throughout the data transmission.

### Claim 8 (depends on 7)

The method of claim 7, wherein adaptive routing further comprises dynamically rerouting a flow in a direction away from a point of congestion in the network.

### Claim 9 (depends on 1)

The method of claim 1, wherein updating the path comprises:
indicating the failed link as congested; and
avoiding the failed link using adaptive routing that employs congestion based rerouting.

### Claim 10 (depends on 9)

The method of claim 9, wherein the congestion based rerouting routes the subset of the plurality of flows to an alternative transmission path to avoid the transmission path including the failed link.

### Claim 11 (depends on 9)

The method of claim 9, wherein indicating the failed link as congested is based on a congestion acknowledgement.

### Claim 12 (depends on 11)

The method of claim 11, where the congestion acknowledgement signals upstream that the flow is experiencing congestion.

### Claim 13 (depends on 1)

The method of claim 1, wherein each of the plurality of flow channels corresponds to a source port and destination port pair for the respective flow.

### Claim 14 (depends on 1)

The method of claim 1, wherein adaptive routing comprises executing routing decisions at each of the ingress ports.

### Claim 15

A switch, comprising:
an application-specific integrated circuit (ASIC) to:
establish a plurality of flow channels corresponding to each of a plurality of flows comprising a plurality of data transmissions;
adaptively routing the plurality of flows through a network having a plurality of switches;
determine a critical error is encountered on a network link along a transmission path;
in response to encountering the critical error on the network link along the transmission path, generate an error acknowledgement for each of a subset of the plurality of flows that are active on the link; and
transmitting the error acknowledgements to ingress ports upstream from the network link via each of the plurality of flow channels of the subset of the plurality of flows, wherein the error acknowledgement indicates the network link where the critical error was encountered as a failed link to ingress ports upstream from the failed link.

### Claim 16 (depends on 15)

The switch of claim 15, wherein the error acknowledgements effectuates, at each ingress port upstream from the failed link, dynamically updating the path of the plurality of flows that are upstream from the failed link to route the plurality of flows that are upstream from the failed link in a manner that avoids the failed link.

### Claim 17 (depends on 15)

The switch of claim 15, wherein establishing the plurality of flow channels corresponding to each of the plurality of flows comprising the plurality of data transmissions comprises:
establishing the plurality of flow channels for the plurality of flows, each of the plurality of flows comprising a data transmission of the plurality of data transmissions, wherein each flow channel of the plurality of flow channels corresponds to a flow of the plurality of flows.

### Claim 18

A method of routing a plurality of data transmissions in a network having a plurality of switches, the method comprising:
determining a critical error is encountered on a network link along a transmission path;
in response to encountering the critical error on the network link along the transmission path, at each ingress port upstream from the network link, receiving an error acknowledgement via each of a plurality of flow channels of a plurality of flows that are active on the network link, wherein the error acknowledgement indicates the network link where the critical error was encountered as a failed link to the ingress ports upstream from the failed link; and
at each ingress port upstream from the failed link, dynamically updating the transmission path of the plurality of flows that are upstream from the failed link to route the plurality of flows that are upstream from the failed link in a manner that avoids the failed link.

### Claim 19 (depends on 1)

The method of claim 1, wherein establishing the plurality of flow channels corresponding to each of the plurality of flows comprising the plurality of data transmissions comprises:
establishing the plurality of flow channels for the plurality of flows, each of the plurality of flows comprising a data transmission of the plurality of data transmissions, wherein each flow channel of the plurality of flow channels corresponds to a flow of the plurality of flows.

### Claim 20 (depends on 19)

The method of claim 19, wherein adaptively routing the plurality of flows through the network comprises selecting a transmission path through the plurality of switches for each of the plurality of flow channels.