Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
2006-08-14
2010-06-01
Chan, Wing F (Department: 2441)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S212000, C709S224000, C709S214000
Reexamination Certificate
active
07730186
ABSTRACT:
A high-performance queueing method to implement a shared queue for collaborative clusters of servers, where each cluster of servers maintains a local queue, and those queues are networked to form a unified (or shared) queue for all those servers in clusters. Requests in an overcrowded queue are forwarded to some other queues, with a randomized algorithm and a message-exchange algorithm between the networked queues. Requests may be forwarded between clusters multiple times. A request is to be accepted with a higher probability by a cluster if the cluster is visited earlier in the order and if the cluster itself has a higher probability to accept the received request. This technique ensures that the requests are forwarded to a queue that has a shorter length (thus a shorter waiting time for first-in-first-out queues) and is closer to the original cluster with a higher probability.
REFERENCES:
patent: 6128642 (2000-10-01), Doraswamy et al.
patent: 6173322 (2001-01-01), Hu
patent: 7062556 (2006-06-01), Chen et al.
patent: 2003/0110232 (2003-06-01), Chen et al.
Ian Foster, et al., “Computational Grids”, Chapter 2 ofThe Grid: Blueprint for a New Computing Infrastructure,Morgan-Kaufman, 1999.
Ian Foster, et al., “Globus: A Metacomputing Infrastructure Toolkit”,Int'l Journal of Supercomputer Applications,11(2):115-128, 1997.
Karl Czajkowski, et al., “A Resource Management Architecture for Metacomputing Systems”Proceedings of the IPPS/SPDP '98 Workshop on Job Scheduling Strategies for Parallel Processingpp. 62-82, 1998.
Shoji Ogura, et al., “Evaluation of the inter-cluster data transfer on Grid environment”,Proceedings of the 3rdIEEE/ACM Int'l Symposium on Cluster Computing and the Grid,IEEE Computer Science, 2003.
Sang-Min Park, et al., “Chameleon: A Resource Scheduler in A Data Grid Environment”Proceedings of the 3rdIEEE/ACM Int'l Symposium on Cluster Computing and the Grid,IEEE Computer Science, 2003.
L. Kleinrock, M/M/m: The m-Server Case, Chapter 3 ofBirth-Death Queueing Systems in Equilibrium,pp. 102-111, vol. 1, Wiley, New York, 1975.
Peterson Davie, “Queuing Disciplines”, Chapter 6 ofComputer Networks: A System Approach,pp. 457-464, Morgan Kaufmann, San Francisco, 2000.
Bertsekas, et al., “Queuing Models-Little's Theorem”, “M/M/l queuing system”, and “M/M/m, M/M/∞, M/M/m/m, and other Markov systems”, Chapter 3 ofData Networks,pp. 152-179, 2ndEd. Prentice Hall, New Jersey, 1992.
S. Keshave, “Scheduling”, Chapter 9 ofAn engineering Approach to Computer Network,pp. 209-263, Addison-Wesley, 1997.
Ravindran, et al., “Queueing Models”, Chapter 7 ofOperations Research: Principles and Practice,pp. 305-341, 2ndEd., John Wiley & Sons, Inc., 1987.
Theorore Johnson, “Designing a Distributed Queue”,Proceedings of the 7thIEEE Symposium on Parallel and Distributed Processing,pp. 304-311, San Antonio, Texas, Oct. 1995.
G. Coulouris, et al., “Distributed Operating Systems—Communication and invocation”, Section 6.5 inDistributed Systems: Concepts and Design,pp. 182-190, 2ndEd. Addison- Wesley, 1994.
A. Geist, et al., PVM: Parallel Virtual Machine, MIT Press, 1994.
Samir Djilali, “P2P-RPC: Programming Scientific Applications on Peer-to-Peer Systems with Remote Procedure Call”,Proceedings of the 3rdIEEE/ACM Int'l Symposium on cluster Computing and the Grid(CCGRID '03), IEEE Computer Society, 2003.
Remzi H. Arpaci-Dusseau, “The Distributed Queue”, Chapter 5 ofPerformance Availability for Networks of Workstations.PhD dissertation, University of California, Berkeley, 1999.
Sanjay Ghemawat, et al., “The Google File System”,Proceedings of the 19thACM Symposium on Operating System Principles,Oct. 2003, Bolton Landing, New York, USA.
Douglas Thain, et al., “Distributed Computing in Practice: The Condor Experience”,Concurrency: Practice Experience,2004; 0:0-20, John Wiley & Sons, Ltd., 2004.
D.H.J. Epema, et al., “A Worldwide Flock of Condors: Load Sharing among Workstation Clusters”,Journal on Future Generations of Computing Systems,vol. 12, 1996.
B.Clifford Neuman, et al., “The Prospero Resource Manager: A Scalable Framework for Processor Allocation in Distributed Systems”,Concurrency: Practice and Experience,6(4); pp. 339-355, Jun. 1994.
Jon B. Weissman, “Gallop: The Benefits of Wide-Area Computing for Parallel Processing”,Journal of Parallel and Distributed Computing,54(2), Nov. 1998.
Andrew S. Grimshaw, et al., “Legion: The next logical step toward the world-wide virtual computer”,Communications of the ACM,Jan. 1997, Association for Computing Machinery, Inc.
Larry Rudolph, et al., “A Simple Load Balancing Scheme for Task Allocation in Parallel Machines”,Processing of the 3rdACM symposium on Parallel algorithms and architectures,pp. 237-245, 1991, Association for Computing Machinery, Inc.
Valeria Cardellini, et al., “Dynamic Load Balancing on Web-Server Systems”,IEEE Internet Computing,pp. 28-39, May-Jun. 1999.
Kai Shen, et al., “Cluster Load Balancing for Fine-grain Network Services”,Proceedings of the Int'l Parallel and Distributed Processing Symposium,2002, IEEE Computer Society.
Chan Wing F
Fuji 'Xerox Co., Ltd.
Sughrue & Mion, PLLC
Zong Ruolei
LandOfFree
Networked queuing system and method for distributed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Networked queuing system and method for distributed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Networked queuing system and method for distributed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4165432