Electrical computers and digital processing systems: multicomput – Computer network managing
Reexamination Certificate
2007-06-26
2007-06-26
Lin, Wen-Tai (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer network managing
C370S217000, C370S238000, C370S391000
Reexamination Certificate
active
10290643
ABSTRACT:
A technique for verifying and reprovisioning an interconnect fabric design using integer programming techniques. Requirements for the interconnect fabric design to be reprovisioned may be referred to as flow requirements. The flow requirements may include, for example, source and terminal nodes for communication flows and communication bandwidth required for the flows. An existing interconnect fabric design specifies an arrangement of elements of the fabric, such as links and interconnect devices. The invention programmatically verifies whether the existing design satisfies the flow requirements using integer programming techniques. If the existing design does not satisfy the flow requirements, the invention may also be used to reprovision the existing design to satisfy the flow requirements. If any flow(s) cannot be accommodated by the existing design, the integer programming techniques may also be used to identify links that can be added to accommodate the flow(s) Further, a new portion of interconnect fabric may be designed and added to the existing design to accommodate unassigned flows.
REFERENCES:
patent: 4920487 (1990-04-01), Baffes
patent: 5107489 (1992-04-01), Brown et al.
patent: 5113496 (1992-05-01), McCalley et al.
patent: 5138657 (1992-08-01), Colton et al.
patent: 5245609 (1993-09-01), Ofek et al.
patent: 5307449 (1994-04-01), Keiley et al.
patent: 5329619 (1994-07-01), Pagé et al.
patent: 5426674 (1995-06-01), Nemirovsky et al.
patent: 5524212 (1996-06-01), Somani et al.
patent: 5581689 (1996-12-01), Slominski et al.
patent: 5598532 (1997-01-01), Liron
patent: 5634004 (1997-05-01), Gopinath et al.
patent: 5634011 (1997-05-01), Auerbach et al.
patent: 5649105 (1997-07-01), Aldred et al.
patent: 5651005 (1997-07-01), Kwok et al.
patent: 5793362 (1998-08-01), Matthews et al.
patent: 5805578 (1998-09-01), Stirpe et al.
patent: 5815402 (1998-09-01), Taylor et al.
patent: 5831996 (1998-11-01), Abramovici et al.
patent: 5835498 (1998-11-01), Kim et al.
patent: 5838919 (1998-11-01), Schwaller et al.
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5878232 (1999-03-01), Marimuthu
patent: 5970232 (1999-10-01), Passint et al.
patent: 5987517 (1999-11-01), Firth et al.
patent: 6003037 (1999-12-01), Kassabgi et al.
patent: 6031984 (2000-02-01), Walser
patent: 6038219 (2000-03-01), Mawhinney et al.
patent: 6047199 (2000-04-01), DeMarco
patent: 6052360 (2000-04-01), Rogers
patent: 6108782 (2000-08-01), Fletcher et al.
patent: 6141318 (2000-10-01), Miyao
patent: 6141355 (2000-10-01), Palmer et al.
patent: 6148000 (2000-11-01), Feldman et al.
patent: 6157645 (2000-12-01), Shobatake
patent: 6195355 (2001-02-01), Demizu
patent: 6212568 (2001-04-01), Miller et al.
patent: 6253339 (2001-06-01), Tse et al.
patent: 6331905 (2001-12-01), Ellinas et al.
patent: 6345048 (2002-02-01), Allen et al.
patent: 6363334 (2002-03-01), Andrews et al.
patent: 6418481 (2002-07-01), Mancusi et al.
patent: 6442584 (2002-08-01), Kolli et al.
patent: 6452924 (2002-09-01), Golden et al.
patent: 6526420 (2003-02-01), Borowsky et al.
patent: 6539027 (2003-03-01), Cambron
patent: 6539531 (2003-03-01), Miller et al.
patent: 6557169 (2003-04-01), Erpeldinger
patent: 6570850 (2003-05-01), Gutierrez et al.
patent: 6594701 (2003-07-01), Forin
patent: 6598080 (2003-07-01), Nagami et al.
patent: 6603769 (2003-08-01), Thubert et al.
patent: 6611872 (2003-08-01), McCanne
patent: 6614796 (2003-09-01), Black et al.
patent: 6625777 (2003-09-01), Levin et al.
patent: 6628649 (2003-09-01), Raj et al.
patent: 6633909 (2003-10-01), Barrett et al.
patent: 6650639 (2003-11-01), Doherty et al.
patent: 6668308 (2003-12-01), Barroso et al.
patent: 6675328 (2004-01-01), Krishnarnachari et al.
patent: 6687222 (2004-02-01), Albert et al.
patent: 6694361 (2004-02-01), Shah et al.
patent: 6697334 (2004-02-01), Klincewicz et al.
patent: 6697369 (2004-02-01), Dziong et al.
patent: 6697854 (2004-02-01), Glassen et al.
patent: 6701327 (2004-03-01), Jones et al.
patent: 6724757 (2004-04-01), Zadikian et al.
patent: 6744767 (2004-06-01), Chiu et al.
patent: 6757731 (2004-06-01), Barnes et al.
patent: 6766381 (2004-07-01), Barker et al.
patent: 6778496 (2004-08-01), Meempat et al.
patent: 6804245 (2004-10-01), Mitchem et al.
patent: 6857027 (2005-02-01), Lindeborg et al.
patent: 2002/0091804 (2002-07-01), Ward et al.
patent: 2002/0091845 (2002-07-01), Ward et al.
patent: 2002/0097680 (2002-07-01), Liu et al.
patent: 2002/0120770 (2002-08-01), Parham et al.
patent: 2002/0122421 (2002-09-01), Ambiehl et al.
patent: 2002/0156828 (2002-10-01), Ishizaki et al.
patent: 2002/0187770 (2002-12-01), Grover et al.
patent: 2002/0188732 (2002-12-01), Buckman et al.
patent: 2003/0144822 (2003-07-01), Peh et al.
patent: 2004/0010577 (2004-01-01), Yegenoglu
patent: 2005/0021583 (2005-01-01), Andrzejak et al.
patent: 2005/0021831 (2005-01-01), Andrzejak et al.
patent: 2005/0033844 (2005-02-01), Andrzejak et al.
patent: WO-96/17458 (1996-06-01), None
Ravindra K. Ahuja et al., Network Flows: Theory, Algorithms, and Applications, pp. 4-9, 649-686, 1993, Prentice-Hall, Upper Saddle River, NJ.
Julie Ward Drew et al., U.S. Appl. No. 10/290,760, filed Nov. 8, 2002.
Julie Ward Drew et al., U.S. Appl. No. 10/845,855, filed May 13, 2004.
Mathew Andrews et al., Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch, 1999. < http://cm.bell-labs.com/cm/ms/who/andrews/infocom99switch.ps>.
Viraphol Chaiyakul, Assignment Decision Diagram for High-Level Synthesis, 1992.
Andre Dehon, Notes on Coupling Processors with Reconfigurable Logic, MIT Transit Project, Transit Note #118, 1995.
Cathy Fulton et al., Impact Analysis of Packet-Level Scheduling On an ATM Shared-Memory Switch, Infocom, vol. 3 pp. 947-954, 1998, IEEE, New York, NY.
Hiroshi Inose, An Introduction to Digital Integrated Communication Systems, pp. 87-89, 1979, Peter Peregrinus Ltd., Stevenage, United Kingdom.
A. Richard Newton, Interface-Based Design; Introduction, University of Caifornia at Berkeley, Apr. 1999.
Derek C. W. Pao, A Congestion Control Algorithm for Multipoint-to-Multipoint ABR Service in ATM Network, Proceedings of the IEEE Conference on High Performance Switching and Routing, pp. 167-175, Jun. 26, 2000, IEEE Press, New York, NY.
Rainer Schoenen et al., Weighted Arbitration Algorithms with Priorities for Input-Queued Switches with 100% Thoughput, 1999, <http://www.iss.rwth-aachen.de/Projekte/Theo/papers/Schoenen99bssw.ps.gz>.
Oryal Tanir et al., Structural Reuse In The Design Of ATM Switch Fabrics, 1997.
I. Widjaja et al., Performance Issues in VC-Merge Capable ATM LSRs, RFC 2682, Sep. 1999, The Internet Society, Reston, VA.
Joachim P. Walser, Solving Linear Pseudo-Boolean Constraint Problems with Local Search, 1997, American Association for Artificial Intelligence, Menlo Park, CA.
D. Klingman et al. Netgen: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems, Management Science 20(5):814-821, 1974, The Institute Of Management Sciences, Providence, RI.
Dimitri P. Bertsekas, Linear Network Optimization: Algorithms and Codes, pp. 253-260, 1991, The MIT Press, Cambridge, MA.
Julie Ward et al., Storage Area Network Fabric Design, PowerPoint presentation given at the Math Sciences Research Institute for Combinatorial Design, Berkeley CA, Nov. 8, 2000.
Julie Ward et al., Storage Area Network (SAN) Fabric Design, PowerPoint presentation given at the INFORMS International Conference, Maui HI, Jun. 19, 2001.
Julie Ward et al., Storage Area Network (SAN) Fabric Design, PowerPoint presentation given at Berkeley, IEOR Department Seminar, Berkeley CA, Oct. 8, 2001.
Parameswaran Ramanathan et al., Resource Placement with Multiple Adjacency Constraints in k-ary n-Cubes, 1995.
Christodoulos A. Floudas et al., Quadratic Optimization, 1995.
U.S. Appl. No. 10/058,258, filed Jan. 25, 2002, Ward et. al.
U.S. Appl. No. 09/707,227, filed Nov. 6, 2000, Ward.
U.S. Appl. No. 09/968,437, filed Sep. 28, 2001, O'Sullivan et. al.
U.S. Appl. No. 10/027,564, filed Jun. 27, 2002, Ward et. al.
J. Ward, M. O'Su
Hewlett--Packard Development Company, L.P.
Lin Wen-Tai
LandOfFree
Integer programming technique for verifying and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Integer programming technique for verifying and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integer programming technique for verifying and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3834967