Degree Type

Dissertation

Date of Award

2011

Degree Name

Doctor of Philosophy

Department

Electrical and Computer Engineering

First Advisor

Ahmed Kamal

Abstract

A large number of network applications today allow several users to interact together using the many-to-many service mode. In many-to-many communication, also referred to as group communication, a session consists of a group of users (we refer to them as members), where each member transmits its traffic to all other members in the same group. This dissertation addresses the problem of many-to-many traffic grooming in optical WDM mesh networks. In this problem, a set of many-to-many session requests, each with an arbitrary sub-wavelength traffic demand, are given and the objective is to provision the sessions on the optical WDM network with the minimum network cost. The cost of an optical WDM network is dominated by the cost of higher layer electronic ports (we refer to them as transceivers). Therefore, our objective is to minimize the total number of transceivers used, while also keeping the number of wavelengths used low, which is an NP-complete problem.

Based on different optical WDM node architectures, we propose four different WDM networks for many-to-many traffic grooming. One is the non-splitting opaque network, where the nodes are opaque and do not support optical splitting. In this network, a lightpath can only span a single physical link. Another one is the non-splitting transparent network, where the nodes are transparent but do not support optical splitting. In this network, a lightpath may span multiple physical links. The last two networks are the splitting hubbed and the splitting all-optical networks, where the nodes are transparent and support optical splitting. In these two networks, lightpaths and light-trees that may span multiple physical links are supported. In the splitting hubbed network, all members in a many to-many session transmit their traffic to a designated hub node chosen from the set of nodes in the network. Using the technique of network coding, the hub then linearly combines the traffic units received together with its own traffic units (if it is a member) and sends back to the members a set of linear combinations using light-tree(s). In the splitting all-optical network, each member in a many to-many session transmits its traffic directly to all other members in the same session using a light-tree.

In this dissertation, we introduce the following contributions for the static many-to-many traffic grooming problem. First, we obtain the optimal solution for the problem in each of the proposed WDM networks using Mixed Integer Linear Program (MILP) formulations. Second, based on observations from the optimal solutions in two of the networks, we restrict the solution space of the corresponding MILPs to obtain near-optimal solutions in a much shorter time. Third, we introduce heuristic algorithms for the many-to-many traffic grooming problem in each of the four WDM networks. A comprehensive comparison between the four networks reveals that each of the networks is the most cost-effective choice for a certain range of traffic granularities. Fourth, we derive lower and upper bounds on the number of transceivers needed and also develop two novel approximation algorithms for one of the networks. For the case of the dynamic many-to-many traffic grooming problem, we introduce online provisioning algorithms for three of the networks with the objective of minimizing blocking probability of arriving sessions.

Copyright Owner

Mohammad Ahmad Salem Saleh

Language

en

Date Available

2012-04-06

File Format

application/pdf

File Size

125 pages

Share

COinS