File allocation in distributed systems

ABSTRACT

The problem of allocating files in a computer network is a complex combinatorial problem due to the number of integer design parameters involved. These parameters include system cost, number of copies of each file to be stored, and sites at which the copies should be stored. The tradeoffs between these parameters are discussed. The design problem is formulated as an integer programming problem. A branch and bound algorithm is proposed to solve the problem. A linear programming formulation which ignores integer restrictions (and allows a fraction of a file to reside at a site) is shown to yield integer solutions in most cases. In other words integer restrictions are satisfied automatically. A near-optimal heuristic is presented, along with computational results. An efficient method to solve the file allocation problem for medium-scale networks is proposed.

REFERENCES

• 1: Casey, R. G., "Allocation of copies of a file in an information network", Proc. SJCC, pp. 617-625 (1972).
• 2: A. Doig and A. H. Land, "An automatic method for solving discrete programming problems", Econometrica, Vol. 28, p. 497 (1960).
• 3: C. V. Ramamoorthy , K. M. Chandy, Optimization of Memory Hierarchies in Multiprogrammed Systems, Journal of the ACM (JACM), v.17 n.3, p.426-445, July 1970 [doi>10.1145/321592.321596]
• 4: P. P.-S. Chen, "Optimal file allocation in a multi-level storage system", Proc. NCC (1973).
• 5: Chu, W. W., "Optimal file allocation in a computer network", in Computer Communication Networks, (ed. N. Abramson and F. F. Kuo), Prentice-Hall (1973).
• 6: K. D. Levin and H. L. Morgan, "Optimizing distributed data bases—A framework for research", Proc. NCC, Vol. 44, pp. 473-478.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Performance

Keywords:
Analytic solution techniques, Branch and bound algorithms, Computer networks and distributed subsystems, Data base management system and subsystem, Decomposition of linear programs, Integer programming, Linear programming, Memory hierarchies