On algorithms for efficient data migration

ABSTRACT

The data migration problem is the problem of computing an efficient plan for moving data stored on devices in a network from one configuration to another. Load balancing or changing usage patterns could necessitate such a rearrangement of data. In this paper, we consider the case where the objects are fixed-size and the network is complete. The direct migration problem is closely related to edge-coloring. However, because there are space constraints on the devices, the problem is more complex. Our main results are polynomial time algorithms for finding a near-optimal migration plan in the presence of space constraints when a certain number of additional nodes is available as temporary storage, and a 3/2-approximation for the case where data must be migrated directly to its destination.

REFERENCES

• 1: E. Borowsky, R. Golding, A. Merchant, L. Schreier, E.Shriver, M.Spasojevic, and J. Wilkes. Using attribute-managed storage to achieve QoS. In Presented at 5th Intl. Workshop on Quality off Service, Columbia Univ., New York, June 1997.
• 2: Bezalel Gavish , Olivia R. Liu Sheng, Dynamic file migration in distributed computer systems, Communications of the ACM, v.33 n.2, p.177-189, Feb. 1990 [doi>10.1145/75577.75583]
• 3: M. K. Goldberg. Edge-coloring of multigraphs: Recoloring technique. J. Graph Theory, 8:121-137, 1984.
• 4: L. Golubchik , S. Khanna , S. Khuller , R. Thurimella , A. Zhu, Approximation algorithms for data placement on parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 09-11, 2000, San Francisco, California, United States
• 5: Dorit S Hochbaum , Takao Nishizeki , David B Shmoys, A better than “best possible” algorithm to edge color multigraphs, Journal of Algorithms, v.7 n.1, p.79-104, March 1986 [doi>10.1016/0196-6774(86)90039-8]
• 6: I. J. Hoyer. The NP-completeness of edge coloring. SIAM J. Comput., 10:718-720, 1981.
• 7: C. E. Shannon. A theorem on colouring lines of a network. J. Math. Phys., 28:148-151, 1949.
• 8: V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Anal., 3:25-30, 1964.
• 9: J. Wolf, The placement optimization program: a practical solution to the disk file assignment problem, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-10, May 23-26, 1989, Oakland, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory, Verification