Samy Mahmoud
Abstract
The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled by means of an average message delay constraint. The objective is to allocate copies of information files to network nodes and capacities to network links so that a minimum cost is achieved subject to network delay and file availability constraints. A model for solving the problem is formulated and the resulting optimization problem is shown to fall into a class of nonlinear integer programming problems. Deterministic techniques for solving this class of problems are computationally cumbersome, even for small size problems. A new heuristic algorithm is developed, which is based on a decomposition technique that greatly reduces the computational complexity of the problem. Numerical results for a variety of network configurations indicate that the heuristic algorithm, while not theoretically convergent, yields practicable low cost solutions with substantial savings in computer processing time and storage requirements. Moreover, it is shown that this algorithm is capable of solving realistic network problems whose solutions using deterministic techniques are computationally intractable.
- 1 BAL,F, E. An additive algorithm for solving linear programs with zero-one variables. Oper. Re~. 13, 4 (July-Aug. 1965), 517-549.Google Scholar
- 2 BALINISKI, M.L. Integer programming: Methods, uses, computations. Manag, Sci. 15, 3 (Nov. 1965), 253-313.Google Scholar
- 3 CAS~y, R.G. Allocation of copies of files in an information network. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 617-625.Google Scholar
- 4 CAsEY, R.G. Design of tree networks for distributed data. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 341-348.Google Scholar
- 5 CrIu, W.W. Optimal file allocation in a multiple computer system. IEEE Trans. on Computers, C-18, 10 (Oct. 1969), pp. 885-889.Google ScholarDigital Library
- 6 DE MERCADO, J.B., AND SPYRATOS, N. A capacity allocation problem in distributed networks. Networks (to appear).Google Scholar
- 7 ESWAR~N, K.P. Placement of records in a file and file allocation in a computer network. IFIP Conference Proceedings, Stockholm, Sweden, Aug. 1974, pp. 304-307.Google Scholar
- 8 FULTZ, G.L. Adaptive routing techniques for message switching computer-communication networks. ENG-7252, Comput. Sci. Dep., U. of California, Los Angeles, Calif., July 1972.Google Scholar
- 9 G~RLA, M. The design of store and forward networks for computer communications. Tech. Rep. UCLA-ENG-F319, Comput. Sci. Dep., U. of California, Los Angeles, Calif., Jan. 1972.Google Scholar
- 10 Hammer, P. A B-B-B method for linear and nonlinear bivalent programming. Mimeograph Ser. No. 48, Oper. Res., Statist. and Economics, israel Inst. of Technology, Haifa, Israel.Google Scholar
- 11 KARP, R.M. Reducibility Among Combinatorial Problems, Complexity o} Computations, Plenum Press, New York, 1972.Google ScholarCross Ref
- 12 KLEINROCK, L. Stochastic Message Flow and Delay. Dover, New York, 1972. Google ScholarDigital Library
- 13 MAHMOUD, S.A. Resource allocation and file access control in distributed information networks. Ph.D. Diss., Systems Eng. Dep., Carleton U., Ottawa, Ontario, Canada, 1975.Google Scholar
- 14 TARA, H.A. A Balasian-based algorithm for 0-1 polynomial programming. Res. Rep. No. 70-2, U. of Arkansas, Fayetteville, Ark., May 1970.Google Scholar
- 15 WrIITNEr, V.K.M. A study of optimal file assignment and communication network configuration in remote-access computer message processing and communications systems. SEL Tech. Rep. No. 48, U. of Michigan, Ann Arbor, Mich., Sept. 1970.Google Scholar
- 16 WILKOV, R., wT. AL. Exact calculations of computer network reliability. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. I, AFIPS Press, Montvale, N.J., pp. 49-54.Google Scholar
Index Terms
- Optimal allocation of resources in distributed information networks
Recommendations
Optimal allocation of resources in distributed information networks
The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled through an average message delay constraint. The objective is to allocate copies ...
Optimal topological design for distributed estimation over sensor networks
The topological structure of sensor network possesses distinctive and interesting characteristics that are important for many applications. In the previous work by Liu et al. (Y. Liu, C. Li, W.K.S. Tang, Z. Zhang, Distributed estimation over complex ...
Comments