Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Patent
1996-06-25
1998-07-14
Kizou, Hassan
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
39520073, H04L 1228
Patent
active
057815461
ABSTRACT:
A method and apparatus for establishing deadlock free routing in a bi-directional, multi-stage, inter-connected, cross-point based packet switch, particularly, though not exclusively employed within a high speed packet network of a massively parallel processing system. Specifically, a group of sets of restricted routes traversing a source, intermediate and destination switch chip are determined by establishing a number of route restrictions from each source switch in the network and determining a number of routes restricted between each source-destination pair of switch chips therein, such that the standard deviation for the number of routes left unrestricted between all source-destination pairs of switch chips for the packet network is minimized. The group of sets of restrictions is created by analyzing a first portion of the network to determine deadlock free route restrictions that comply with the established per switch restrictions and the determined source-destination pair restrictions therefore and then incrementally adding each remaining switch chip for the network and repeating the analysis. Any number of sets from the resultant group of sets of route restrictions may be implemented within the network in accordance with determined link usage and intermediate switch chip usage balancing techniques.
REFERENCES:
patent: 4763247 (1988-08-01), Borovski et al.
patent: 5088091 (1992-02-01), Schroeder et al.
patent: 5140583 (1992-08-01), May et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5224100 (1993-06-01), Lee et al.
patent: 5313649 (1994-05-01), Hsu et al.
patent: 5321813 (1994-06-01), McMillen et al.
patent: 5444701 (1995-08-01), Cypher et al.
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5471623 (1995-11-01), Napolitano, Jr.
patent: 5513322 (1996-04-01), Hou
patent: 5546391 (1996-08-01), Hochschild et al.
Cheng, T.D. et al., "Function and Performance Enhancement for a Dynamic Routing Network", IBM Technical Disclosure Bulletin, vol. 34, No. 4A, Sep. 1991, pp. 428-429.
Konstantinidou, S. et al., "Deadlock-Free Routing Schemes on Multi-stage Interconnection Networks", IBM Technical Disclosure Bulletin, vol. 35, No. 7, Dec. 1992, pp. 232-233.
Gravano, L. et al., "Adaptive Deadlock-Free Worm-Hole Routing with all Minimal Paths in K-Dimensional Tori", Research Disclosure, No. 338, Kenneth Mason Publications Ltd, England, Jun. 1992.
Brimouma A.
Ehrlich Marc A.
International Business Machines - Corporation
Kizou Hassan
LandOfFree
Route restrictions for deadlock free routing with increased band does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route restrictions for deadlock free routing with increased band, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route restrictions for deadlock free routing with increased band will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1890456