Increasingly minimal bias routing
AssigneeHewlett Packard Enterprise Development LP
InventorsAbdulla Bataineh, Thomas Court, Duncan Roweth
Life of this patent
Estimating the term…
Abstract
A system and algorithm configured to generate diversity at the traffic source so that packets are uniformly distributed over all of the available paths, but to increase the likelihood of taking a minimal path with each hop the packet takes. This is achieved by configuring routing biases so as to prefer non-minimal paths at the injection point, but increasingly prefer minimal paths as the packet proceeds, referred to herein as Increasing Minimal Bias (IMB).
Claims35
A processor interconnect network for providing communication pathways between a plurality of processor nodes within a multiprocessor computer system, the interconnect network comprising:
- a plurality of routers to dynamically route a data packet along a network path from a source node to a destination node, wherein the source node is one of the plurality of processor nodes and the destination node is one of the plurality of processor nodes, wherein the network path comprises a sequence of hops involving a subset of the plurality of routers, with each of the routers within the sequence of hops are configured to select a next hop based upon network congestion information from neighboring routers and a routing table comprising biases;
- wherein a first hop in the sequence of hops is selected by a first router using the congestion information provided to the first router and a first bias which is a non-minimal bias having the ability to increase the probability that the first hop is a non-minimal hop;
- and
- wherein a subsequent hop in the sequence of hops is selected by a subsequent router using the congestion information provided to the subsequent router and a subsequent bias which is a bias toward minimal routing having the ability to increase the probability that the subsequent hop is a minimal hop.
A multiprocessor computer system including a processor interconnect network, the multiprocessor computer system comprising:
- a plurality of routers configured to dynamically route a data packet along a network path across the processor interconnect network, the network path made up of a sequence of hops from a source node to a first one of the plurality of routers and then to at least a subsequent one of the plurality of routers until the data packet reaches a destination node, each router in the sequence of hops being configured to select a next hop from among a plurality of possible hops based on network congestion information from neighboring routers and a routing table comprising biases;
- wherein a first hop from the source node to a first one of the plurality of routers is selected as a function of said congestion information and the application of a first bias which will promote the use of a non-minimal routing methodology, and
- wherein a subsequent hop within the network path is selected as a function of said congestion information and the application of a bias towards minimal routing, wherein the bias toward minimal routing will increase the likelihood of selecting a minimal routing methodology.
A method of operating a multiprocessor computer system, comprising:
- dynamically routing a data packet through a plurality of routers which form a plurality of network paths from a source node to a destination node as a function of a plurality of routing tables contained within the plurality of routers, with each routing table comprising biases, wherein each of the plurality of routers making routing decisions based on network congestion information from neighboring routers;
- wherein each said network path consists of a sequence of hops, and wherein a first hop from the source node to a first said router is selected based upon said congestion information and a non-minimal routing said bias which promotes the selection of a non-minimal hop, and wherein a subsequent hop in the network path is selected based upon the said congestion information and a bias towards minimal routing which increases the probability that a minimal hop will be selected.
Dependencies are inferred from the claim text.