Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Multicasting in All-Optical WDM Networks

    Thumbnail
    View/Open
    umi-umd-5782.pdf (873.9Kb)
    No. of downloads: 1102

    Date
    2008-09-26
    Author
    Rawat, Anuj
    Advisor
    Shayman, Mark
    Metadata
    Show full item record
    Abstract
    n this dissertation, we study the problem of (i) routing and wavelength assignment, and (ii) traffic grooming for multicast traffic in Wavelength Division Multiplexing (WDM) based all-optical networks. We focus on the 'static' case where the set of multicast traffic requests is assumed to be known in advance. For the routing and wavelength assignment problem, we study the objective of minimizing the number of wavelengths required; and for the traffic grooming problem, we study the objectives of minimizing (i) the number of wavelengths required, and (ii) the number of electronic components required. Both the problems are known to be hard for general fiber network topologies. Hence, it makes sense to study the problems under some restrictions on the network topology. We study the routing and wavelength assignment problem for bidirected trees, and the traffic grooming problem for unidirectional rings. The selected topologies are simple in the sense that the routing for any multicast traffic request is trivially determined, yet complex in the sense that the overall problems still remain hard. A motivation for selecting these topologies is that they are of practical interest since most of the deployed optical networks can be decomposed into these elemental topologies. In the first part of the thesis, we study the the problem of multicast routing and wavelength assignment in all-optical bidirected trees with the objective of minimizing the number of wavelengths required in the network. We give a 5/2-approximation algorithm for the case when the degree of the bidirected tree is at most 3. We give another algorithm with approximation ratio 10/3, 3 and 2 for the case when the degree of the bidirected tree is equal to 4, 3 and 2, respectively. The time complexity analysis for both these algorithms is also presented. Next we prove that the problem is hard even for the two restricted cases when the bidirected tree has (i) depth 2, and (ii) degree 2. Finally, we present another hardness result for a related problem of finding the clique number for a class for intersection graphs. In the second part of the thesis, we study the problem of multicast traffic grooming in all-optical unidirectional rings. For the case when the objective is to minimize the number of wavelengths required in the network, given an 'a'-approximation algorithm for the circular arc coloring problem, we give an algorithm having asymptotic approximation ratio 'a' for the multicast traffic grooming problem. We develop an easy to calculate lower bound on the minimum number of electronic components required to support a given set of multicast traffic requests on a given unidirectional ring network. We use this lower bound to analyze the worst case performance of a pair of simple grooming schemes. We also study the case when no grooming is carried out in order to get an estimate on the maximum number of electronic components that can be saved by applying intelligent grooming. Finally, we present a new grooming scheme and compare its average performance against other grooming schemes via simulations. The time complexity analysis for all the grooming schemes is also presented.
    URI
    http://hdl.handle.net/1903/8763
    Collections
    • Electrical & Computer Engineering Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility