Traffic Grooming In All-optical Network Research

The rapid development of Internet has greatly promote the research progress of optical network.As the Wavelength-Division Multiplexing(WDM) technology matures gradually, the factors that restricting the capacities of optical network transmission is no longer the bandwidth of fiber,but the networks bottleneck caused by the processing speed of electronic equipments,such as routers,switches and multiplexers in networks.The emergence of traffic grooming technology has provided an effective approach to solve these problems.Recently,traffic grooming problem is one of the research frontiers and a hot topoic in optical network studies.Traffic grooming problem mainly studies how to pack lower rate traffic streams of different speeds and different types onto higher rate traffic streams and multiplex onto the available wavelengths,effectively.For instance,a lightpath of an OC-48 SONET ring can support up to 16 OC-3 simultaneous communication requests.In alloptical networks,WDM technology can transmit kinds of signals on single fiber,and each signal use distinct wavelength.Thus,Wavelength Assignment Problem is to find a path for a pair of requests for communication,and assign a wavelenth to it such that two paths sharing the same link have distinct wavelenth.In terms of graph-theoretic,Wavelength Assignment Problem can be viewed as assigning colors to given paths so that these paths sharing an edge have different colors.Generally,communication requests have a granularity g,known as grooming factor.A valid coloring paths should be colored so that at most g paths sharing a common edge may be colored with the same color.Given a valid coloring,an ADM(Add-Drop Multiplexer) can serve at most 2g paths colored with the same color.Obviously,the ADM minimization problems are special case of the traffic grooming problems(g=1).In 1998,O.Gerstel,R.Ramaswami and G.Sasaki etc.introduced the notion of traffic grooming for the ring topology networks.The problem was shown to be NP-complete for ring networks and a general g.In past,the study of traffic grooming problem was focus on ring topology by doing some related work on this problem and got some valuable results.In 2006,M.Shalom and S.Zaks etc.discussed an algorithm that has a preprocessing phase during which cycles of length at most l,and prove it has a performance guarantee.In the thesis,we mainly study the ADM minimization problems,and the traffic grooming problem for different topology networks.The thesis is divided into five chapters.Most of problems we discuss in this thesis are NP-hard,therefore we are mainly interested in approximation algorithms.In chapter 1,we briefly introduce the basic notion of all-optical networks,SONET/WDM rings and the traffic grooming problems.And we also list the work we do and the structure of the thesis.In chapter 2,we mainly discuss the ADM minimization problem,and we get a better performance guarantee by further improving the approximation algorithm with preprocessing phase.In chapter 3,we propose an algorithm with better approximation ratio for multicast traffic grooming in unidirectional SONET/WDM rings,and prove the relation between the lower bound of the number of ADMs and the number of nodes in the rings.In chapter 4,we mainly solve the traffic grooming problem in unidirectional SONET/WDM rings and the general topology networks by applying the algorithm which introduced in ring topology networks,and we get some similar results.In chapter 5,we make a conclusion for the whole thesis and propose some problems to be considered in the future.