Dissertation > Excellent graduate degree dissertation topics show

Routing in Counter Rotated SONET Ring with Load Restriction

Author: GuoXiaoJiang
Tutor: FangQiZhi
School: Ocean University of China
Course: Operational Research and Cybernetics
Keywords: SONET ring Routing Rounding technology Polynomial time algorithm Approximation Algorithms
CLC: TN929.1
Type: Master's thesis
Year: 2008
Downloads: 30
Quote: 0
Read: Download Dissertation

Abstract

As the Internet and multimedia data communications transmission rapid development of Synchronous Optical Network (SONET) as a faster, more efficient and lower cost of the transmission technology is now gradually more network service providers use. Synchronous Optical Network (SONET) the basic structure of SONET rings, it is mounted on the links through the subtraction point multiplexer (ADMs) to send, receive and relay information. The multiplexer determines the SONET ring capacity of the actual bandwidth, which is usually the case, there is a ring for each SONET bandwidth limit (capacity) C, such that each link on the ring is not able to transfer more than the demand for C Unit . The SONET ring design and application of the emergence of many challenging issues, such as ring load problem, counter-rotating ring load balancing and node routing problems ring road capacity is limited by the problem. These issues are essentially classical combinatorial optimization integer multi-commodity flow problem is NP-hard in general, but in some special cases are solved in polynomial time accurately. When the SONET ring is undirected ring, cut criterion in problem solving, and the design of approximation algorithms play a key role; when there is a SONET ring to ring, this criterion loses effectiveness at this time, based on linear programming rounding techniques become an important method of algorithm design in reverse rotation SONET ring load balancing algorithm for the problem in this approach to get some good results. In this paper, considering the application process SONET ring presented a combinatorial optimization problem: In the reverse load limit on the rotating ring, given a set of information transmission requirements, each requirement can be closed along its starting point and between the two points one possible path (clockwise or counterclockwise) for transmission, we need to identify a route plan, which determine what needs to be transmitted, and which direction the transmission, so as to satisfy ring capacity limit and the number that needs to be transmitted (through amount) of the maximum. We call this problem is called a load limit of reverse rotation SONET ring routing problem (abbreviated as LRRR). By rounding linear programming techniques sophisticated applications, we give SONET ring LRRR issue a polynomial time algorithm. The algorithm ring up beyond the capacity of a unit under the premise, I get a demand not less than optimal value through routing scheme. Further modifications of this method, the problem can be LRRR a performance ratio of 1? C2 1 approximation algorithm, the results meet the requirements of the application. To our knowledge, there is little research on LRRR problem. According to the characteristics of the problem, we are in algorithm design techniques to existing algorithms made many changes and promotion, and the use of undirected ring some skills. These improvements in the communication network algorithm in both theory and practical applications will have good sense.

Related Dissertations

CLC: > Industrial Technology > Radio electronics, telecommunications technology > Wireless communications > Lightwave communications, laser communications
© 2012 www.DissertationTopic.Net Mobile