An Optimal Station Allocation Policy for Tree Local Area Networks

Abstract

This paper reports on the simulation results of a heuristic solution to the station allocation problem in a tree topology Local Area Network (LAN). A local network is a data communication network where communication remains confined within a moderate sized area, such as a plant site, an office building or a university campus. Tree LANs with collision avoidance switches and multiple broadcast facility have, recently, become popular due to their suitability for high speed light wave communications. Given a tree LAN with fanout F and given the total number of stations N to be connected, a combinatorial optimization problem arises regarding how to allocate the stations to the leaf nodes so that the total system availability (a network performance criteria) is maximized. This is known as the optimal station assignment problem. In this paper, it is formulated as a non-linear optimization problem which can be solved by the Lagrangean relaxation and the subgradient optimization techniques. A simple heuristic is developed based on these techniques. The simulation studies show that the proposed heuristic is relatively fast operating only in a subspace of the complete solution space.