Optimization of concentrator locations and station assignments in an FDDI dual ring of trees topology - Manzano, Enrique M. (1994)
There are many LANs in competition today with standards ranging from CSMA/CD, Token Bus, Timed Token Ring,and others. Ethernets are a popular choice, ATMS are promising. Fiber Distributed Data Interface (FDDI) boasts of a performance that exceeds Ethernets, an OSI architecture that assures multi-vendor interoperability, and availability and cheap technology compared to ATMs. The most versatile FDDI topology is the dual ring of trees. The backbone is composed of dual attachment concentrators that form a dual counter-rotating ring. The local access is composed of concentrators that cascade down from the ring. Stations can be connected to any concentrator (ring, or local access). The purpose of this thesis is to develop an algorithm for a dual ring of trees topological optimization. It combines several published algorithms with the author's innovations. The program generated uses three major procedures. The first optimizes the ring, a problem similar to the Traveling Salesman Problem (TSP), an NP complete problem; the second optimizes the spanning forests of concentrators; and the third optimally assigns the stations to the installed concentrators. The main program that conducts the three mentioned procedures plus some minor procedures is an algorithm that this author calls a drop within a drop algorithm. Software is provided in a window friendly environment very similar to the Borland's Turbo Pascal in which it was developed. As a test case, the U.P. Diliman campus FDDI network is constructed. The author sees the importance of this work not only in the 100Mb/s, 500 station FDDI dual ring of trees but to larger future networks like the FFOL (FFDI Follow-On LAN) which is on the drawing board that may boast of 2 gigabits/s bandwidth (plus an increase in stations) and other networks that may choose to adopt the dual ring of trees topology.