Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-20
2002-04-02
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C706S010000, C706S046000, C703S002000, C710S011000
Reexamination Certificate
active
06366931
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer storage systems and pertains more particularly to an apparatus for and a method of non-linear constraint optimization in a storage system configuration.
2. Discussion of the Prior Art
Storage systems for computer networks can contain a large number of storage devices having a wide variety of characteristics and a nearly arbitrary interconnection scheme. The configuration and management of the storage system is central to the functioning of the computer network. In very large networks, the inherent difficulties in configuring and managing the storage system are compounded by the sheer scale of the network. The situation has reached the point where the time needed to configure a new storage system can be several months and the cost of managing the storage system can be several times the purchase cost.
Large computer networks can contain a large number of host computers connected to the storage system. In such networks, many application programs may be running concurrently on one or more of the host computers and each application program has a certain level of service that it requires from the storage system in order to run well. The storage allocation problem is to optimally lay out data accessed by the application programs on the optimal set of storage devices in the storage system. A solution to the problem is referred to as an assignment plan.
The optimality of the resulting overall assignment plan is evaluated based on an objective function. For example, an objective function may be to minimize the cost of the storage system. An objective function may be to maximize the performance of the storage system. Other objective functions include balancing the load, maximizing the availability, and minimizing the physical footprint. One of ordinary skill in the art will realize that there are many other possible objective functions and that, often, multiple and competing objective functions will have to be balanced.
A specific piece of data is referred to as a workload unit. Associated with every workload unit are a set of standards. Standards include both the workload unit characteristics and the application program access characteristics. For example, a standard may be the size of the workload unit. A standard may be the access speed or the access frequency of the application program. Other standards include request size, request rate, run count, phasing behavior, on time, off time, and maximum amount of data loss. One of ordinary skill in the art will realize that there are many other possible standards.
Likewise, associated with every storage device are a set of characteristics. Characteristics include both performance measures and physical descriptions. For example, a characteristic may be the quantity of storage available on or the access speed of the storage device. A characteristic may be the size or the weight of the storage device. Other characteristics include position time, transfer rate, cost, outage frequency, outage length, and data loss rate. One of ordinary skill in the art will realize that there are many other possible characteristics.
For the storage allocation problem, the questions of whether the various workload unit standards are compatible with the various storage device characteristics serve as constraints on the solution. Often, the constraints are linear inequalities, that is, expressions of the form
∑
w
i
∈
W
a
i
w
i
<
f
(
d
)
Eq
.
(
1
)
where the values of a
i
and f(d) are constants for a given storage device, for example, quantity of storage, outage frequency, and data loss rate. However, some of the constraints are non-linear, for example, access speed and utilization. Further, some of the constraints are not inequalities, for example, existence of proper interconnect cabling. This mixture of constraints serves to further complicate the matter because if one could assume that all of the constraints were of one type, then one could tailor the solution to that type of constraint. In particular, there are a number of good solutions if the constraints were all linear. Unfortunately, that is not necessarily the case here.
So, the storage allocation problem can be viewed on at least two levels. First, whether a particular workload unit can be assigned to a particular storage device, that is, whether the constraints are met. Second, whether a particular workload unit should be assigned to a particular storage device given the resulting overall assignment plan, that is, whether the objective function is optimized.
There exist many standard optimization problems that are similarly structured to the storage allocation problem. However, none of them are an exact match. As a result, none of them provide a model upon which to reach a solution.
One standard optimization problem similar to the storage allocation problem is the classic bin packing problem. In the classic bin packing problem, the challenge is to fit a set of n items, I={i
1
, i
2
, . . . i
n
}, having fixed sizes, S={s
1
, S
2
, . . . S
n
}, into a set of m bins, B={b
1
, b2, . . . b
m
}, having fixed capacities, C={c
1
, c
2
, . . . c
m
}. The objective function is to use the minimum number of bins possible given the constraint that the sum of the sizes of a set of items in a bin must be less then or equal to the capacity of the bin. So, in the classic bin packing problem, there is only one objective function and one constraint. In the storage allocation problem, however, there may be multiple objective functions and multiple constraints. As a result, solutions to the classic bin packing problem cannot be used directly to solve the storage allocation problem.
Another standard optimization problem similar to the storage allocation problem is the integer knapsack problem. In the integer knapsack problem, the challenge is to fit a set of n items, I={i
1
, i
2
, . . . i
n
}, having a fixed size, S={s
1
, s
2
, . . . s
n
}, and a defined value, V={v
1
v
2
, . . . v
n
}, into a knapsack having a fixed size k. The objective function is to maximize the value of a set of items placed into the knapsack given the constraint that the sum of the sizes of the set of items in the knapsack must be less then or equal to the capacity of the knapsack. Again, in the integer knapsack problem, there is only one objective function and one constraint. Alternatively, there is a variant of the integer knapsack problem called the multidimensional knapsack problem which takes into account multiple capacity dimensions. An example solution is given in MANAGEMENT SCENCE by Yoshiaki Toyoda (Toyoda) in an article entitled “A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems.” Even so, both of the knapsack problems differ from the storage allocation problem in two significant ways. First, the knapsack problems assume that the capacity dimensions can be captured as linear constraints. However, as noted above, this may not always be the case in the storage allocation problem and cannot be assumed. Second, the knapsack problems assume a fixed number of knapsacks. However, in the storage allocation problem, an objective function to choose the best set of storage devices may require that storage devices be added or that storage devices remain unused. As a result, solutions to the knapsack problems cannot be used directly to solve the storage allocation problem.
One computer specific optimization problem similar to the storage allocation problem is the standard file allocation problem. In the standard file allocation problem, the challenge is to place a set of n files, F={f
1
, f
2
, . . . f
n
}, having a fixed size, S={s
1
, s
2
, . . . s
n
}, and a set of m tasks, T={t
1
, t
2
, . . . t
m
}, onto a set of k nodes, N={n
1
, n
2
, . . . n
k
}, having a fixed capacity,
Borowsky Elizabeth
Jacobson Pat
Merchant Arif
Breene John
Hewlett--Packard Company
Pham Khanh
LandOfFree
Apparatus for and method of non-linear constraint... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for and method of non-linear constraint..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for and method of non-linear constraint... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857329