Optik ağlarda rejeneratör konumlandırılması

ABSTRACTREGENERATOR PLACEMENT IN OPTICALNETWORKSüoOnur OzkükM.S. in Industrial EngineeringSupervisor: Assist. Prof. Dr. Oya Ekin KaraşansJanuary, 2004Increase in the number of users and resources consumed by modern applicationsresults in an explosive growth in the traffic on the Internet. Optical networkswith higher bandwidths offer faster and more reliable transmission of data andallows transmission of more data. Fiber optical cables have these advantages overthe traditional copper wires. So it is expected that optical networks will have awide application area.However, there are some physical impairments and optical layer constraintsin optical networks. One of these is signal degradation which limits the range ofoptical signals. Signals are degraded during transmission and below a thresholdthe signals become useless. In order to prevent this, regenerators which arecapable of re-amplifying optical signals are used. Since regeneration is a costlyprocess, it is important to decrease the number of regenerators used in an opticalnetwork.To increase the reliability of the network, two edge-disjoint paths betweeneach terminal on the network are to be constructed. So the second path couldbe used in case of a failure in transmitting data on an edge of the first path.Considering these requirements, selecting the nodes on which regenerators are tobe placed is an important decision.In this thesis, we discuss the problem of placing signal regenerators on opticalnetworks with restoration. An integer linear program is formulated for this prob-lem. Due to the huge size and other problems of the formulation, it is impracticalto use it on large networks. For this reason, a fast heuristic algorithm is proposedto solve this problem. Three methods are proposed to check the feasibility whena fixed set of regenerators are placed on specific nodes. Additionally, a branchand bound algorithm which employs the proposed heuristic is developed to findiiiivthe optimal solution of our problem. Performance of both the heuristics andthe branch and bound method are evaluated in terms of number of regeneratorsplaced and solution times of the algorithms.Keywords: optical networks, regenerator placement, branch and bound algorithm,working and restoration path design.