Direction order priority routing of packets between nodes in a networked system
US5533198A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Nov 30, 1992 |
| Grant date | Jul 2, 1996 |
| Priority date | — |
| Expiry date | Nov 30, 2012 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F11/202
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method of routing messages within an n-dimensional network topology. Two directions are associated with each dimension in the n-dimensional network, for a total of 2n directions. A direction order is assigned which prioritizes the order in which a packet is routed across the 2n possible directions. Such an approach provides deadlock-free, fault tolerant wormhole routing in networks without wrap-around channels. For networks with wrap-around channels, the above method of wormhole routing is enhanced by placing a first direction from each of the n dimensions within a first group of directions. The second direction from each dimension is placed within a second group of directions. A packet to be routed from a source node to a destination node is routed in all relevant directions in the first group of directions in any order before being routed in the second group of directions. If, while traveling in a direction within the first group of directions, the packet is routed across a wrap-around channel, all further routing in that direction must be completed before moving in another direction. Routing then proceeds, if necessary, in the other directions of that first group of directions…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.