Browse Prior Art Database

Efficient Load Sharing Scheme With Pruning

IP.com Disclosure Number: IPCOM000120834D
Original Publication Date: 1991-Jun-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Related People

Yu, PS: AUTHOR

Abstract

This article proposes a computationally efficient transaction routing strategy to address shared nothing cluster with a large number of nodes. The transactions in this environment have reference localities which imply that certain processing nodes can be identified as being more preferred than others. Response time measure can strike a balance between sharing the load and capturing the transaction affinity to the heterogeneous processing nodes. In -*-, an MRT strategy is proposed and demonstrated to lead to superior performance. In the MRT approach, each transaction is routed to the node which minimizes its estimated response time. This is achieved by estimating the response time of an incoming transaction to each node in the cluster and selecting the node with the minimum estimated response time.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient Load Sharing Scheme With Pruning

      This article proposes a computationally efficient
transaction routing strategy to address shared nothing cluster with a
large number of nodes.  The transactions in this environment have
reference localities which imply that certain processing nodes can be
identified as being more preferred than others.  Response time
measure can strike a balance between sharing the load and capturing
the transaction affinity to the heterogeneous processing nodes. In
-*-, an MRT strategy is proposed and demonstrated to lead to superior
performance.  In the MRT approach, each transaction is routed to the
node which minimizes its estimated response time.  This is achieved
by estimating the response time of an incoming transaction to each
node in the cluster and selecting the node with the minimum estimated
response time.  The response time estimate is obtained through an
approximation based on Bard-Schweitzer.  The computational cost can
be prohibitive as the number of nodes in the cluster becomes large.
Here we propose a strategy to reduce the number of times the
Bard-Schweitzer algorithm is invoked and make it independent of the
number of nodes in the cluster.
THE PROPOSED PRUNING STRATEGY

      To improve the computational efficiency of the routing
strategy, we want to prune the number of nodes considered in each
routing decision. Secondly, we want to reduce the number of times we
need to go through the selection process of minimum response times.

      In addition to the information maintained in the original MRT
algorithm, we now maintained at the front-end for each node an
estimate of its remaining work.  This is denoted as Nwk.  Each time a
routing decision is made, we update this vector based on the work
generated by the incoming transaction to each node.  When a
transaction departs, this vector is again updated subtracting the
work associated with it at each node.  Fu...