Articles via Databases
Articles via Journals
Online Catalog
E-books
Research & Information Literacy
Interlibrary loan
Theses & Dissertations
Collections
Policies
Services
About / Contact Us
Administration
Littman Architecture Library
This site will be removed in January 2019, please change your bookmarks.
This page will redirect to https://digitalcommons.njit.edu/dissertations/691 in 5 seconds

The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title: Quality-of-service provisioning in high speed networks : routing perspectives
Author: Cheng, Gang
View Online: njit-etd2005-064
(xii, 135 pages ~ 5.8 MB pdf)
Department: Department of Electrical and Computer Engineering
Degree: Doctor of Philosophy
Program: Electrical Engineering
Document Type: Dissertation
Advisory Committee: Ansari, Nirwan (Committee chair)
Karvelas, Dionissios (Committee member)
Papavassiliou, Symeon (Committee member)
Widjaja, Indra (Committee member)
Zhou, MengChu (Committee member)
Date: 2005-05
Keywords: Network
Routing
Quality of service
Availability: Unrestricted
Abstract:

The continuous growth in both commercial and public network traffic with various quality-of-service (QoS) requirements is calling for better service than the current Internet's best effort mechanism. One of the challenging issues is to select feasible paths that satisfy the different requirements of various applications. This problem is known as QoS routing. In general, two issues are related to QoS routing: state distribution and routing strategy. Routing strategy is used to find a feasible path that meets the QoS requirements. State distribution addresses the issue of exchanging the state information throughout the network, and can be further divided into two sub-problems: when to update and how to disseminate the state information.

In this dissertation, the issue of when to update link state information from the perspective of information theory is addressed. Based on the rate-distortion analysis, an efficient scheme, which outperforms the state of the art in terms of both protocol overhead and accuracy of link state information, is presented. Second, a reliable scheme is proposed so that, when a link is broken, link state information is still reachable to all network nodes as long as the network is connected. Meanwhile, the protocol overhead is low enough to be implemented in real networks. Third, QoS routing is NP-complete. Hence, tackling this problem requires heuristics. A common approach is to convert this problem into a shortest path or k-shortest path problem and solve it by using existing algorithms such as Bellman-Ford and Dijkstra algorithms. However, this approach suffers from either high computational complexity or low success ratio in finding the feasible paths. Hence, a new problem, All Hops k-shortest Path (AHKP), is introduced and investigated. Based on the solution to AHKP, an efficient self-adaptive routing algorithm is presented, which can guarantee in finding feasible paths with fairly low average computational complexity. One of its most distinguished properties is its progressive property, which is very useful in practice: it can self-adaptively minimize its computational complexity without sacrificing its performance. In addition, routing without considering the staleness of link state information may generate a significant percentage of false routing. Our proposed routing algorithm is capable of minimizing the impact of stale link state information without stochastic link state knowledge. Fourth, the computational complexities of existing s-approximation algorithms are linearly proportional to the adopted linear scaling factors. Therefore, two efficient algorithms are proposed for finding the optimal (the smallest) linear scaling factor such that the computational complexities are reduced. Finally, an efficient algorithm is proposed for finding the least hop(s) multiple additive constrained path for the purpose of saving network resources.


If you have any questions please contact the ETD Team, libetd@njit.edu.

 
ETD Information
Digital Commons @ NJIT
Theses and DIssertations
ETD Policies & Procedures
ETD FAQ's
ETD home

Request a Scan
NDLTD

NJIT's ETD project was given an ACRL/NJ Technology Innovation Honorable Mention Award in spring 2003