Degree Type

Thesis

Date of Award

2011

Degree Name

Master of Science

Department

Electrical and Computer Engineering

First Advisor

Arun Somani

Abstract

A cycle could support a Synchronous optical networking (SONET) ring, or a reliable multicast, or a multipoint to multipoint traffic request, or a p-cycle protecting connections between any two-node pair that belong to the cycle. Determining a cycle passing through a specific set of nodes is a complex process. This paper presents a novel heuristic algorithm to find a least cost possible simple or non-simple cycle with multiple must-include nodes. In case the required cycle must be a simple cycle only, then it is apparent that our problem is similar to a Travelling Salesman Problem, in which the objective is to find the least cost simple cycle with all the nodes in a given travel network. In our algorithm, we allow complex cycles in the sense that links are allowed to be used only once, whereas a node may appear multiple times. This kind of cycle is called a nonsimple cycle and it can increase the success rate of finding the cyclic route with desired set of nodes. The heuristic algorithm in this paper utilizes Breadth First Search and Tree construction algorithms to find a least cost and shortest route between nodes. The experimental results show that our algorithm has lower failure rate of requests than existing heuristic algorithms like Optimized

Collapsed Ring (OCR) and Enumeration. The fault-tolerance for single link failure can be achieved by routing the traffic in both the directions of the cycle

Copyright Owner

Suresh Sankaran

Language

en

Date Available

2012-04-06

File Format

application/pdf

File Size

55 pages

Share

COinS