Optimization of resource location in hierarchical computer networks. (English) Zbl 0692.68044
Summary: The goal of topological design of computer networks is to achieve a specified performance at minimum cost. In the future, complex computer networks will be designed using hierarchical structures. There are proposals for hierarchical control and management of networks, hierarchical routing of messages, and hierarchical distribution of directory information and computer resources. It is important to be able to formulate and solve these problems. We solve the optimization of resource location in hierarchical computer networks using a modification of simulate annealing (SA), and a greedy heuristic.
Simulated annealing has gained popularity in recent years because it is a new technique based on the generate-and-test paradigm of artificial intelligence. SA has been successfully applied to the solution of such NP-hard problems as VLSI design, circuit placement, scheduling, and the famous traveling salesman problem in operations research. This paper is the first one that has attempted to solve computer network design problems using SA.
We provide an integer programming formulation of the problem, and present two approximate algorithms to solve it. One involves a simulated annealing-linear programming hybrid algorithm, and the other is a greedy second best heuristic. Computational results show that these approximate algorithms perform better than a Lagrangian relaxation of the problem.
Simulated annealing has gained popularity in recent years because it is a new technique based on the generate-and-test paradigm of artificial intelligence. SA has been successfully applied to the solution of such NP-hard problems as VLSI design, circuit placement, scheduling, and the famous traveling salesman problem in operations research. This paper is the first one that has attempted to solve computer network design problems using SA.
We provide an integer programming formulation of the problem, and present two approximate algorithms to solve it. One involves a simulated annealing-linear programming hybrid algorithm, and the other is a greedy second best heuristic. Computational results show that these approximate algorithms perform better than a Lagrangian relaxation of the problem.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C10 | Integer programming |
| 68T99 | Artificial intelligence |
| 90C90 | Applications of mathematical programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
hierarchical resource location problem (HRLP); simulate annealing; greedy heuristic; computer network design; algorithmsReferences:
| [1] | Tanenbaum, A. S., Computer Networks (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [2] | Akinc, U.; Khumawala, B. M., An efficient branch-and-bound algorithm for the capacitated warehouse location problem, Mgmt Sci., 23, 585-594 (1977) · Zbl 0348.90157 |
| [3] | Lo, C-C.; Kershenbaum, A., A two-phase algorithm for the star-star concentration location problem, (IEEE Infocom. Proc. (1988)), 946-955 |
| [4] | Mirzaian, A., Lagrangian relaxation for the star-star concentrator location problem: approximation algorithm and bounds, Networks, 15, 1-20 (1985) · Zbl 0579.94031 |
| [5] | Chen, P.; Akoka, J., Optimal design of distributed information systems, IEEE Trans. Comput., C-29, 617-625 (1980) |
| [6] | Fisher, M. L.; Hochbaum, D. S., J. ACM, 27, 718-735 (1980) · Zbl 0445.68071 |
| [7] | Gavish, B.; Pirkul, H., Computer and database location in distributed computer systems, IEEE Trans. Comput., C-35, 583-590 (1986) |
| [8] | Morgan, H. L.; Levin, K. D., Optimal program and data locations in computer networks, Commun. ACM, 20, 315-321 (1977) · Zbl 0353.68019 |
| [9] | Mesarovic, M.; Macko, D.; Takahara, Y., Theory of Hierarchical Multi-Level Systems (1970), Academic Press: Academic Press New York · Zbl 0206.14501 |
| [10] | Anandalingam, G., A mathematical programming model of decentralised multi-level systems, J. Opl Res. Soc., 39, 1021-1033 (1988) · Zbl 0657.90061 |
| [11] | Kleinrock, L.; Kamoun, F., Hierarchical routing for large networks, Computer Networks, 1, 155-174 (1977) |
| [12] | Buttle, T. C.; Chow, A. C.; Garrett, P. A., Datapac network management, (IEEE Int. Commun. Conf., 1 (1986)), 579-583 |
| [13] | Diller, D. E.; Merski, R. F., An architecture for providing universal access to network equipment from distributed support centers, IEEE Infocom., 245-250 (1987) |
| [14] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [15] | Collins, W. E.; Eglese, R. W.; Golden, B. L., Simulated annealing an annotated bibliography, (Working Paper Series No. Ms/S 87-02 (1987), College of Business and Management, University of Maryland: College of Business and Management, University of Maryland Baltimore, MD) · Zbl 0669.65047 |
| [16] | Hajek, B., Cooling schedules for optimal annealing, Math. Opns Res., 13, 311-321 (1988) · Zbl 0652.65050 |
| [17] | Lundy, M.; Mees, A., Convergence of an annealing algorithm, Math. Programm., 34, 111-124 (1986) · Zbl 0581.90061 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
