Determining placement of distributed application onto...

Details Determining placement of distributed application onto... Determining placement of distributed application onto...

2003-07-25

2008-09-16

Jaroenchonwanit, Bunjob (Department: 2152)

Electrical computers and digital processing systems: multicomput

Computer-to-computer protocol implementing

Computer-to-computer data transfer regulating

C709S223000, C709S226000, C709S230000, C709S232000

Reexamination Certificate

active

07426570

ABSTRACT:
A method of determining a placement of services of a distributed application onto nodes of a distributed resource infrastructure comprises first, second, and third steps. The first step forms communication constraints between node pairs. The communication constraints ensure that a sum of transport demands between a particular node pair does not exceed a transport capacity between the particular node pair. Each term of the sum comprises a product of a first placement variable, a second placement variable, and the transport demand between the services associated with the first and second placement variables. The second step forms an objective. The communication constraints and the objective comprise an integer program. The third step employs a local search solution to solve the integer program, which determines the placement of the services onto the nodes.

REFERENCES:
patent: 5511167 (1996-04-01), Kawano et al.
patent: 5734825 (1998-03-01), Lauck et al.
patent: 5878224 (1999-03-01), Smith
patent: 5918021 (1999-06-01), Aditya
patent: 5993038 (1999-11-01), Sitbon et al.
patent: 6031984 (2000-02-01), Walser
patent: 6032188 (2000-02-01), Mairs et al.
patent: 6052712 (2000-04-01), Badovinatz et al.
patent: 6125397 (2000-09-01), Yoshimura et al.
patent: 6125400 (2000-09-01), Cohen et al.
patent: 6167029 (2000-12-01), Ramakrishnan
patent: 6366931 (2002-04-01), Borowsky et al.
patent: 6473801 (2002-10-01), Basel
patent: 6507844 (2003-01-01), Leymann et al.
patent: 6526420 (2003-02-01), Borowsky et al.
patent: 6574669 (2003-06-01), Weaver
patent: 6782527 (2004-08-01), Kouznetsov et al.
patent: 6834310 (2004-12-01), Munger et al.
patent: 6928482 (2005-08-01), Ben Nun et al.
patent: 6978394 (2005-12-01), Charny et al.
patent: 7089299 (2006-08-01), Chetuparambil et al.
patent: 2003/0005132 (2003-01-01), Nguyen et al.
patent: 2003/0055868 (2003-03-01), Fletcher et al.
Sven Graupner, Vadim Kotov, Artur Andrsejak, Holger Trinks, Control Architecture for Service Grids in a Federation of Utility Data Centers, HP Labs Technical Report HPL-2002-235, Hewlett-Packard Company, Palo Alto, 2002. <http://www.hpl.hp.com/techreports/2002/HPL-2002-235.pdf>.
Artur Andrzejak, Sven Graupner, Vadim Kotov, Holger Trinks, Algorithms for Self-Origanization and Adaptive Service Placement in Dynamic Distributed Systems, HP Labs Technical Report, HPL-2002-259, Hewlett-Packard Company, Palo Alto, Sep. 2002. <http://www.hpl.hp.com/techreports/2002/HPL-2002-259.pdf>.
Ciprianpo Santos, Xiaoyun Zhu, Harlan Crowder, A Mathematical Optimization Approach for Resource Allocation in Large Scale Data Centers, HP Labs Technical Report, HPL-2002-64R1, Hewlett-Packard Company, Palo Alto, 2002. <http://www.hpl.hp.com/techreports/2002/HPL-2002-64R1.pdf>.
Parameswaran Ramanathan, Suresh Chalasani, Resource Placement with Multiple Adjacency Constraints in K-ary n-Cubes, IEEE transactions on Parallel & Distributed Systems, May 1995, vol. 6, No. 5, pp. 511-519, IEEE Press, Los Alimitos, 1995.
Sven Graupner, Vadim Kotov, Holger Trinks, Resource-Sharing and Service Deployment in Virtual Data Centers, The 22nd International Conference on Distributed Computing Systems Workshops, Vienna Austria, Jul. 2-5, 2002, pp. 666-671, IEEE Computer Society, Los Alamitos, 2002.
Christodoulous A. Floudas, V. Visweswaran, Quadratic Optomization, Handbook of Global Optimization, pp. 217-269, Kluwer Academic Publishers, Boston, 1995.
Joachim P. Walser, Solving Linear Pseudo-Boolean Constraint Problems with Local Search, Proceedings of the Fourteenth National Conference on Artificial Intelligence and the Ninth Innovative Applications of Artificial Intelligence Conference, Jul. 27-31, 1997, Providence, Rhode Island, pp. 269-274, AAAI Press, Menlo Park, 1997.
Bart Selman, Hector Levesque, David Mitchell, A New Method for Solving Hard Satisfiability Problems, Proceedings of the Tenth National Conference on Artificial Intelligence Jul. 12-16, 1992, San Jose, California, pp. 440-446, AAAI Press, Menlo Park, 1992.
David Abramson, Henry Dang, Mohan Krishnamoorthy, A Comparison of Two Methods for Solving 0-1 Integer Programs Using a General Purpose Simulated Annealing Algorithim, Annals of Operations Research, v. 63, pp. 129-150, Baltzer Science, Amsterdam, Netherlands, 1996.
Joachim Paul Walser, Domain-Independent Local Search for Linear Integer Optomization, Dissertation, Progamming Systems Lab, Universitat de Saarlandes, Saarbrucken, Germany, Oct. 1998.
Bart Selman, Greedy Local Search in MIT Encyclopedia of the Cognitive Sciences, MIT Press, Cambridge, 1999.
Bart Selman, Henry A. Kautz, Bram Cohen, Local Search Strategies for Satifiabily Testing Presented at the Second DIMACS Challenge on Cliques, Coloring, and Satisfiability, Oct. 11-13, 1993 Piscataway, New Jersey.
Bart Selman, Henry A. Kautz, Bram Cohen, Noise Strategies for Improved Local Search, Proceedings of the Twelfth National Conference on Artificial Intelligence, Aug. 1-4, 1994, Seattle, Washington, pp. 337-343, AAAI Press, Menlo Park, 1994.

Affiliated with

Also associated with

Rating

Determining placement of distributed application onto... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining placement of distributed application onto..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining placement of distributed application onto... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3983188