# US 2005/0097283 A1 · Method of selecting heuristic class for data placement

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2005/0097283 A1
- Document ID: US20050097283A1
- Status: Published application
- Kind: A1
- Application number: 10/698,182
- Filed: 2003-10-30
- Published: 2005-05-05
- Earliest claimed: 2003-10-30
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Magnus Karlsson; Christos Karamanolis
- Web page: https://patentgrep.com/patent/US20050097283A1

## CPC

- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/061: {Improving I/O performance}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An embodiment of a method of selecting a heuristic class for data placement in a distributed storage system begins by forming a general integer program which models the data placement and forming a specific integer program which models a heuristic class for the data placement. The general and specific integer programs each comprising an objective of minimizing a replication cost. The method continues with solving the general integer program which provides a general lower bound for the replication cost and solving the specific integer program which provides a specific lower bound for the replication cost. The method concludes with selecting the heuristic class if a difference between the general lower bound and the specific lower bound is within an allowable amount.

## Claims

### Claim 1

A method of selecting a heuristic class for data placement in a distributed storage system comprising the steps of:
forming an integer program for each of a plurality of heuristic classes, each of the integer programs comprising an objective of minimizing a replication cost;
solving each of the integer programs which provide the replication cost for each of the heuristic classes; and
selecting the heuristic class having a low replication cost.

### Claim 2

A method of selecting a heuristic class for data placement in a distributed storage system comprising the steps of:
forming a general integer program which models the data placement;
forming a specific integer program which models a heuristic class for the data placement, the general and specific integer programs each comprising an objective of minimizing a replication cost;
solving the general integer program which provides a general lower bound for the replication cost;
solving the specific integer program which provides a specific lower bound for the replication cost; and
selecting the heuristic class if a difference between the general lower bound and the specific lower bound is within an allowable amount.

### Claim 3 (depends on 2)

The method of claim 2 wherein inputs used in the steps of forming the general and specific integer programs comprise a system configuration, a workload, and a performance requirement.

### Claim 4 (depends on 3)

The method of claim 3 wherein the performance requirement comprises a bi-modal performance metric.

### Claim 5 (depends on 4)

The method of claim 4 wherein the bi-modal performance metric comprises a criterion and a ratio of successful attempts to total attempts.

### Claim 6 (depends on 3)

The method of claim 3 wherein the performance requirement comprises a data access latency.

### Claim 7 (depends on 3)

The method of claim 3 wherein the performance requirement comprises a data access bandwidth.

### Claim 8 (depends on 3)

The method of claim 3 wherein the performance requirement comprises a data update time.

### Claim 9 (depends on 3)

The method of claim 3 wherein the performance requirement comprises an average data access latency.

### Claim 10 (depends on 3)

The method of claim 3 wherein the performance requirement comprises a data availability requirement.

### Claim 11 (depends on 3)

The method of claim 3 wherein the general integer program comprises general constraints which model the data placement irrespective of the heuristic class for the data placement.

### Claim 12 (depends on 11)

The method of claim 11 wherein the general constraints comprise a performance constraint which models the performance requirement.

### Claim 13 (depends on 11)

The method of claim 11 wherein the specific integer program comprises the general constraints and a specific constraint.

### Claim 14 (depends on 12)

The method of claim 12 wherein the specific constraint comprises a storage constraint.

### Claim 15 (depends on 12)

The method of claim 12 wherein the specific constraint comprises a replica constraint.

### Claim 16 (depends on 12)

The method of claim 12 wherein the specific constraint comprises a routing knowledge constraint and further wherein the routing knowledge constraint models an extent to which a data storage node knows of replicas of data objects stored on other data storage nodes.

### Claim 17 (depends on 12)

The method of claim 12 wherein the specific constraint comprises an access knowledge constraint and further wherein the access knowledge constraint models an extent to which a data storage knows of access to replicas of data objects by clients accessing other data storage nodes.

### Claim 18 (depends on 12)

The method of claim 12 wherein the specific constraint comprises an activity history constraint.

### Claim 19 (depends on 12)

The method of claim 12 wherein the specific constraint comprises a reactive placement constraint.

### Claim 20 (depends on 3)

The method of claim 3 wherein the system configuration comprises a plurality of data storage nodes coupled by a plurality of network links.

### Claim 21 (depends on 20)

The method of claim 20 wherein the system configuration further comprises a plurality of clients coupled to the data storage nodes.

### Claim 22 (depends on 21)

The method of claim 21 wherein the workload comprises at least some of the clients requesting data objects stored on the data storage nodes.

### Claim 23 (depends on 22)

The method of claim 22 wherein the workload further comprises at least some of the clients storing some of the data objects on the data storage nodes.

### Claim 24

A method of selecting a heuristic class for data placement in a distributed storage system comprising the steps of:
forming a general integer program which models the data placement;
forming a plurality of specific integer programs which model a plurality of heuristic classes, the general and specific integer programs each comprising an objective of minimizing a replication cost;
solving the general integer program which provides a lower bound for the replication cost;
solving the specific integer programs which provides the replication cost for each of the heuristic classes; and
selecting a particular heuristic class correlated to a low replication cost if a difference between the lower bound and the low replication cost is within an allowable amount.

### Claim 25

A computer readable memory comprising computer code for implementing a method of selecting a heuristic class for data placement in a distributed storage system, the method of selecting the heuristic class comprising the steps of:
forming an integer program for each of a plurality of heuristic classes, each of the integer programs comprising an objective of minimizing a replication cost;
solving each of the integer programs which provide the replication cost for each of the heuristic classes; and
selecting the heuristic class having a low replication cost.

### Claim 26

A computer readable memory comprising computer code for implementing a method of selecting a heuristic class for data placement in a distributed storage system, the method of selecting the heuristic class comprising the steps of:
forming a general integer program which models the data placement;
forming a specific integer program which models a heuristic class for the data placement, the general and specific integer programs each comprising an objective of minimizing a replication cost;
solving the general integer program which provides a general lower bound for the replication cost;
solving the specific integer program which provides a specific lower bound for the replication cost; and
selecting the heuristic class if a difference between the general lower bound and the specific lower bound is within an allowable amount.

### Claim 27

A computer readable memory comprising computer code for implementing a method of selecting a heuristic class for data placement in a distributed storage system, the method of selecting the heuristic class comprising the steps of:
forming a general integer program which models the data placement;
forming a plurality of specific integer programs which model a plurality of heuristic classes, the general and specific integer programs each comprising an objective of minimizing a replication cost;
solving the general integer program which provides a lower bound for the replication cost;
solving the specific integer programs which provides the replication cost for each of the heuristic classes; and
selecting a particular heuristic class correlated to a low replication cost if a difference between the lower bound and the low replication cost is within an allowable amount.
