System and method for assigning data collection agents to storage area network nodes in a storage area network resource management system

• US 7,526,540 B2
• Filed: 04/22/2003
• Issued: 04/28/2009
• Est. Priority Date: 04/22/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gopisetty, Sandeep Kumar, Sarkar, Prasenjit, Merbach, David Lynn
• Primary Examiner(s): Donaghue; Larry D
• Assistant Examiner(s): Gillis; Brian J
• Application Number:
  US10/421,220
• Publication Number:
  US 20040215904A1
• Time in Patent Office: 2,198 Days
• Field of Search: 709/223, 709/224, 718/105, 455/453, 715/734, 715/735, 715/736
• US Class Current: 709/223
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Data collection agents are assigned to storage area network nodes in a storage area network resource management system, such that the bandwidth and cost of data collection are equitably distributed among data collection agents. Data collection overlaps and load imbalances are eliminated across the data collection agents, creating approximately equal partitions of bandwidth and data collection for each data collection agent. Graph partitioning is used to accomplish load balancing. The assignment of data collection agents to storage area network nodes equitably distributes the bandwidth and processing costs among the data collection agents and ensures a load balance.

Claims

1. In a storage area network, a processor-implemented method of allocating a load among a plurality of data collection agents, the method comprising:

representing the plurality of data collection agents using a first group of nodes;

representing a plurality of physical entities from which the plurality of data collection agents collect data using a second group of nodes;

generating a graph, G, wherein the first group of nodes are joined to the second group of nodes using a plurality of edges, each of the edges representing a connection between a data collection agent and a physical entity on the storage area network;

wherein G is denoted as (V, E), where V is a set of vertices of the graph and E is a set of the plurality of edges, and where each vertex element, v, in set V is either a member of A, which comprises the set of data collection agents represented by the first group of nodes, or a member of N, which comprises the set of physical entities represented by the second group of nodes such that there does not exist an element v in V that is a member of both A and N;

wherein each member v in V has a load function, L(v), that denotes the cost of data collection at V;

mathematically optimizing a correspondence between the first group of nodes and the second group of nodes, and allocating the load among a plurality of data collection agents represented by the first group of nodes, wherein the load comprises the plurality of physical entities from which the plurality of data collection agents collect data, and the load is allocated among the first group of nodes by;

partitioning the graph into a plurality of sub-graphs, (P(i)), wherein i represents a partition counter, each of the sub-graphs comprising a mutually exclusive subset of the first group of nodes;

iteratively partitioning the plurality of sub-graphs, P(i), into subpartitions, P(2i) and P(2i+1), and allocating the load into approximately balanced distributed loads among the first group of nodes until the following constraints of load and data collection agent are simultaneously satisfied;

Load(P(2i))<

Load(Pi)/2; and

;

Agents(P(2i))<

Agents(Pi)/2 and;

determining whether a data collection agent has failed and using a largest sub-graph of the plurality of sub-graphs to reassign the load among the first group of nodes by using information from the iteratively partitioning, wherein a partition level, L, is defined such that L contains partitions in accordance with the following expression;

[P(2<sup>L−

1</sup>) . . . P(2^L−

1)];

and a level L_fail is chose such that L_fail contains every element in [P(2<sup>Lfail−

1</sup>) . . . P(2^Lfail−

1)], and every element in L_fail has a minimum number of data collection points that satisfy a predetermined fail-safe criterion.

2. The method of claim 1, wherein the iteratively partitioning and allocating further comprises randomly selecting a vertex, v, in a first partition P(i), selecting an unvisited vertex, w, in a second partition P(2i), and performing a breadth first search from the unvisited vertex w selected in the second partition P(2i).

3. The method of claim 2, further comprising adding a plurality of vertices to the first partition P(i) until the constraints of load and data collection agent are simultaneously satisfied.

4. The method of claim 1, further comprising assigning a plurality of vertices in the graph to the second partition P(2i).

5. The method of claim 1, wherein in the event a given data collection agent, a, in a given partition, p, in L_fail suffers a failure, one or more alternate data collection agents are available for selection within p to collect information from the physical entities managed by data collection agent a, and wherein in the event a given data collection agent, a, in a given partition, p, does not report on a given physical entity, n, in partition p, one or more alternate data collection agents in the same partition p are available to verify the physical entity n.