Multiplex communications – Wide area network – Packet switching
Patent
1995-10-10
1997-11-18
Lall, Parshotam S.
Multiplex communications
Wide area network
Packet switching
39520011, 3952001, 370 16, H04J 326
Patent
active
056896468
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. Likewise, if, while traveling in a direction within the second 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 of the second group of directions. A free hop mechanism is also taught for increased flexibility.
REFERENCES:
patent: 4868818 (1989-09-01), Madan et al.
patent: 4933933 (1990-06-01), Dally et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5031211 (1991-07-01), Nagai et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5157692 (1992-10-01), Horie et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5218601 (1993-06-01), Chujo et al.
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5280474 (1994-01-01), Nickolls et al.
patent: 5313628 (1994-05-01), Mendelsohn et al.
patent: 5331631 (1994-07-01), Teraslinna
patent: 5333279 (1994-07-01), Dunning
patent: 5347450 (1994-09-01), Nugent
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5440547 (1995-08-01), Easki et al.
patent: 5517497 (1996-05-01), Le Boudec et al.
patent: 5548639 (1996-08-01), Ogura et al.
patent: 5555542 (1996-09-01), Ogura et al.
"Deadlock-Free Routing Schemes on Multistage Interconnection Networks", IBM Technical Disclosure Bulletin, 35, 232-233 (Dec. 1992).
Robert Gallager, "Scale Factors for Distributed Routing Algorithms", NTC '77 Conference Record, 2 (1978).
Peter Nuth et al., "The J-Machine Network", IEEE, 420-423 (1992).
C.S. Yang et al., "Performance Evaluation of Multicast Wormhole Routing in 2D-Torus Multicomputers", IEEE, 173-178 (1992).
J. Yantchev et al., "Adaptive, low latency, deadlock-free packet routing for networks of processors", IEE Proceedings, 136, 178-186 (May 1989).
William Dally et al., "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, C-36, 547-553 (May 1987).
William Dally, "Performance Analysis of k-ary n-cube Interconnection Networks", IEEE Transactions on Computers, 39, 775-785 (Jun. 1990).
William Dally, "Virtual-Channel Flow Control", IEEE, 60-68 (1990).
C.R. Jesshope, P.R. Miller and J.P. Yantchev, High Performance Communications in Processor Networks, proc. 16th International Symposium on Computer Architecture at 150-157, May 1989.
D.H. Linder and J.C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary-n-cubes, I.E.E.E. Trans. on Computers, at 2-12, Jan. 1991.
W.J. Dally and H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, I.E.E.E. Transactions on Parallel and Distributed Systems, vol. 4, No. 4, at 466-475, Apr. 1993.
C.J. Glass and L.M. Ni, The Turn Model for Adaptive Routing, Proc. 19th International Symposium on Computer architecture, at 278-287, May 1992.
A.A. Chien and J.H. Kim, Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors, proc. 19th International. Symposium on Computer Architecture at 268-277, May 1992.
J. Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, I.E.E.E. Transactions on Parallel and Distributed Systems, vol. 4, No. 12, at 1320-1331, Dec. 1993.
Adve, V.S. and M.K. Vernon, "Performance Analysis of Mesh Interconnection Networks with Deterministic Routing," Transactions on Parallel and Distributed Systems, pp. 225-246, Mar. 1994.
Kevin Bolding, Non-Uniformities Introduced by Virtual Channel Deadlock Prevention, Technical Report 92-07-07, Department of Computer Science and Engineering, FR-35 University of Washington, Seattle, WA 98195, USA, Jul. 21, 1992.
S. Kirkpatrick, et al., Optimization by Simulated Annealing, SCIENCE, May 13, 1993, vol. 220, No. 4598, pp. 671-680.
Weilin Wang, et al., Trunk Congestion Control in Heterogeneous Circuit Switched Networks, IEEE TRansactions on Communications, vol. 40, No. 7, Jul. 1992, pp. 1156-1161.
Lawrence Snyder Introduction to the Configurable, Highly Parallel Computer, Jan. 1982, pp. 47-56.
D. Talia; "Message-Routing Systems for Transputer-Based Multicomputers", IEEE Micro; No. 3, pp. 62-72; (Jun. 13, 1993).
Cray Research Inc.
Lall Parshotam S.
Maung Zarni
LandOfFree
Configuring of networked system to permit replacement of failed does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Configuring of networked system to permit replacement of failed , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Configuring of networked system to permit replacement of failed will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1572851