Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2005-06-21
2005-06-21
Phan, Man U. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395430, C370S401000, C370S389000, C709S238000, C709S244000, C711S101000, C711S154000
Reexamination Certificate
active
06909695
ABSTRACT:
Embodiments of a routing system are disclosed, including a method for routing communications in a storage system. The storage system may include multiple nodes interconnected by an interconnection fabric that provides multiple independent paths between a source node and a destination node. Some nodes may be connected to one or more disk drives. The method may include receiving a communication to be sent from a source node to a destination node, selecting a communication path from the multiple independent paths, and sending the communication on the selected communication path. This process may be repeated so that multiple communications may be sent. Each communication path may be selected according to a preference assigned to it, so that a more preferred path is selected more often than a less preferred path. The preferences may be updated to reflect changed conditions in the interconnection fabric.
REFERENCES:
patent: 4862496 (1989-08-01), Kelly et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5101480 (1992-03-01), Shin et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5187671 (1993-02-01), Cobb
patent: 5592610 (1997-01-01), Chittor
patent: 5612897 (1997-03-01), Rege
patent: 5613069 (1997-03-01), Walker
patent: 5646936 (1997-07-01), Shah et al.
patent: 5682479 (1997-10-01), Newhall et al.
patent: 5689646 (1997-11-01), Thorson
patent: 5689661 (1997-11-01), Hayashi et al.
patent: 5701416 (1997-12-01), Thorson et al.
patent: 5720025 (1998-02-01), Wilkes et al.
patent: 5737628 (1998-04-01), Birrittella et al.
patent: 5781534 (1998-07-01), Perlman et al.
patent: 5862312 (1999-01-01), Mann et al.
patent: 5970232 (1999-10-01), Passint et al.
patent: 6016510 (2000-01-01), Quattromani et al.
patent: 6023753 (2000-02-01), Pechanek et al.
patent: 6055618 (2000-04-01), Thorson
patent: 6072774 (2000-06-01), Natarajan et al.
patent: 6101181 (2000-08-01), Passint et al.
patent: 6128277 (2000-10-01), Bruck et al.
patent: 6167502 (2000-12-01), Pechanek et al.
patent: 6483808 (2002-11-01), Rochberger et al.
patent: 6490287 (2002-12-01), Kilkki
patent: 6658478 (2003-12-01), Singhal et al.
patent: 6665730 (2003-12-01), Michelson et al.
patent: 6718428 (2004-04-01), Lee et al.
patent: 6792472 (2004-09-01), Otterness et al.
patent: 2002/0051458 (2002-05-01), Carvey et al.
patent: 2003/0023749 (2003-01-01), Lee et al.
patent: 439 693 (1991-08-01), None
patent: 550 853 (1992-12-01), None
patent: 646 858 (1994-08-01), None
patent: 669 584 (1995-02-01), None
patent: 0 785 512 (1997-07-01), None
patent: 92/06436 (1992-04-01), None
patent: 94/12939 (1994-06-01), None
patent: 99/17217 (1999-04-01), None
patent: 99/26429 (1999-05-01), None
patent: 99/63442 (1999-12-01), None
patent: 00/14932 (2000-03-01), None
patent: 02/50682 (2002-06-01), None
patent: 02/50683 (2002-06-01), None
International Search Report for PCT/US 02/14403, mailed Sep. 8, 2003.
G. Albertengo, et al., “Optimal Routing Algorithms for Bidirectional Manhattan Street Network,” IEEE, 1991, 3 pages.
Bradley Kuszmaul, Mercury Computer Systems, Inc., “The RACE Network Architecture,” (posted at www.mc.com/techlit/#tech_brief prior to this), 6 pages.
R.Y. Wang, T.E. Anderson and D.A. Patterson, “Virtual Log Based File Systems For a Programmable Disk,” Proc. Third Symposium on Operating Systems Design and Implementation, Feb. 1999 (Also appeared as University of California Technical Report CSD-98-1031, 16 pages.
Prasant Mohapatra, Wormhole Routing Techniques for Directly Connected Multicomputer Systems, ACM Computing Surveys, vol. 30, No. 3, Sep. 1998, 37 pages.
Christopher Glass and Lionel Ni, “The Turn Model for Adaptive Routing,” Journal of the Association for Computing Machinery, vol. 41, No. 5, Sep. 1994, pp. 874-902.
Reddy, Dept. of Computer & Information Sciences, “A Dynamically Reconfigurable WDM LAN Based on Reconfigurable Circulant Graph,” IEEE, 1996, 4 pages.
Various Abstracts beginning with Funahashi, Jouraku and Amano, “Adaptive Routing for Recursive Diagonal Torus,” Transactions of the Institute of Electronics, Information and Communication Engineers D-I, vol. J83D-I, No. 11, Nov. 2000, pp. 1143-1153.
Milan Kovacevic, Center for Telecommunications Research, “On Torus Topologies with Random Extra Links,” IEEE 1996, pp. 410-418.
Dally, et al., The Torus Routing Chip, Distributed Computing, Springer-Verlag 1986, pp. 187-196.
Susan Hinrichs, “A Compile Time Model for Composing Parallel Programs,” IEEE Parallel and Distributed Technology, 1995, 19 pages.
“CRAY T3D System Architecture Overview Manual,” ftp://ftp.cray.com/product-info/mpp/T3D_Architecture_Over/T3D.overview.html, Cray Research, 1993, 40 pages.
Marco Fillo, et al., “The M-Machine Multicomputer,” Laboratory for Computer Science, Massachusetts Institute of Technology, A.I. Memo No. 1532, Ann Arbor,. Mar. 1995, 14 pages.
Noakes, et al., “The J-Machine Multicomputer: An Architectural Evaluation,” Proceedings of the 20thInternational Symposium on Computer Architecture, May 1993, 12 pages.
Dally, et al., “Architecture of a Message-Driven Processor,” International Conference on Computer Architecture, Jun. 1987, pp. 189-196.
Dennison, Lee and Dally, “High-Performance Bidirectional Signalling in VLSI,” Massachusetts Institute of Technology, Oct. 12, 1992, 20 pages.
Dally, et al., “Architecture and Implementation of the Reliable Router,” Mass. Institute of Technology, Proceedings of Hot Interconnects II, Stanford CA, Aug. 1994, 12 pages.
Dally, et al., “The Reliable Router: A Reliable and High-Performance Communication Substrate for Parallel Computers,” Proceedings of the First International Parallel Computer Routing and Communication Workshop, Seattle WA, May 1994, 15 pages.
Dennison, et al., “Low-Latency Plesiochronous Data Retiming,” Mass. Institute of Technology, Proceedings of the 1995 Advanced Research in VLSI Conference, Chapel Hill NC, Mar. 1995, 12 pages.
Whay S. Lee, “Mechanism for Efficient, Protected Messaging,” Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Jan. 20, 1999, 147 pages.
Dennison, “Reliable Interconnect Networks for Parallel Computers,” Mass. Institute of Technology, Dept. of Electrical Engineering and Computer Science, Apr. 18, 1991, 79 pages.
Thucydides Xanthopoulos, “Fault Tolerant Adaptive Routing in Multicomputer Networks,” Dept. of Electrical Engineering and Computer Science , Mass. Institute of Technology, Jan. 20, 1995, 152 pages.
Dennison, “The Reliable Router: An Architecture for Fault Tolerant Interconnect,” Dept. of Electrical Engineering and Computer Science, Mass Institute of Technology, May 24, 1996, 145 pages.
“Introduction To Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,” F. Thomson Leighton, Morgan Kaufmann Publishers, 1992, pp. 1-831.
Christopher J. Glass and Lionel Ni, “Fault-Tolerant Wormhole Routing in Meshes,” Technical Report, MSU-CPS-ACS-72, Oct. 30, 1992 (revised May 25, 1993), 28 pages.
Stefan Savage and John Wilkes, “AFRAID—A Frequently Redundant Array of Independent Disks,” Proceedings of the 1996 USENIX Technical Conference, pp. 27-39, San Diego, CA, Jan. 1996, 13 pages.
Steve Ward, et al., “A Modular, Scalable Communications Substrate,” MIT Laboratory for Computer Science, Jul. 1993, 10 pages.
Christopher Glass and Lionel Ni, “The Turn Model for Adaptive Routing,” Technical Reports, MSU-CPS-ACS-44, Oct. 10, 1991 (revised Mar. 2, 1992), pp. 278-287 (numbered herein as 1-20).
Thomas Stricker, “Message Routing on Irregular 2D-Meshes and Tori,” School of Computer Science, Carnegie Mellon Univ., Jan. 15, 1991, pp. 170-177 (numbered herein as 1-19).
Dally, et al., “The J-Machine: A Restrospective,” in 25 Years of the International Symposia on Computer Architecture—Selec
Lee Whay S.
Rettberg Randall D.
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Phan Man U.
LandOfFree
Fault-tolerant, self-healing routing scheme for a multi-path... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fault-tolerant, self-healing routing scheme for a multi-path..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault-tolerant, self-healing routing scheme for a multi-path... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3474731