Thesis (Ph. D.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2007. / Wardi, Yorai, Committee Member ; Abler, Randy, Committee Member ; Copeland, John, Committee Member ; Owen, Henry, Committee Chair ; Ahamad, Mustaque, Committee Member.

Thesis (Ph. D.)--University of Washington, 2005. / Vita. Includes bibliographical references (p. 123-135).

Habilitation - Technische Universität, Berlin. / Includes bibliographical references (p. [223]-237) and index.

Thesis (Ph. D.)--University of Texas at Austin, 2005. / Supervisor: Simon S. Lam. Vita. Includes bibliographical references.

Thesis (M.S.)--Brigham Young University. Dept. of Computer Science, 2006. / Includes bibliographical references (p. 45-48).

Reliable routing using alternate paths is investigated in this dissertation. We propose precalculated alternate paths as a method for fast recovery from link and node failures in IP networks. We demonstrate that path switching time, and thus failure recovery time are, as expected, considerably faster than the standard method of recalculating a new path on the fly. However, to be effective, the alternate paths should share a minimal set of links and nodes - preferably none - with the failed path. As shared links are considered in this work, we give a reliability model for this situation (non-disjoint alternate paths) and develop estimates of reliability as a function of the number of shared links. Alternate path finding algorithms to calculate suitable alternate paths subject to predefined constraints are also developed. Implementation of these techniques for improving routing reliability is shown to be straightforward for explicit routing protocols such as Multi-Protocol Label Switching (MPLS) with Explicit Routing mode. This mode is expected to be the protocol of choice for applications requiring guaranteed Quality of Service (QoS) carried on the coming generation of wavelength-switched networks (Internet II, CA Net III, etc.) We propose a Reliable MPLS (R-MPLS) protocol by applying alternate path routing to MPLS, using our new algorithms to precalculate appropriate alternate paths. Simulation results show that R-MPLS can achieve fast recovery from failures. We also address reliability issues for the problem of optimal Service Level Agreement (SLA) admission control. To achieve reliable admission control, we apply alternate path routing to an existing SLA-based admission controller called SLAOpt. In the existing Utility Model, SLA admission control is mapped to the Multiple-Choice Multi-Dimension Knapsack Problem (MMKP), where the aim is to maximize system utility (i.e., revenue). However, SLAOpt is static in terms of network topology and does not consider reliability. Motivated by this, we propose a Reliable SLAOpt (R-SLAOpt), in which utility optimization is subject to the additional constraint of reliability. A new algorithm was also developed to calculate multiple groups of alternate paths that meet the desired QoS demands and reliability requirement. After QoS adaptation, R-SLAOpt selects an appropriate path group containing two or three paths for each admitted session and performs resource reservation on all paths in the group. In the event of node or link failure, a session can be quickly switched to one of the alternate paths, maintaining the guaranteed QoS without having to run the full admission algorithm again. In this way, we have obtained a unified treatment of routing reliability and optimal SLA admission control. Finally, simulations are presented which investigate R-SLAOpt's impact on system performance and the gains made in reliability. / Graduate

No description available.

To be effective, applications such as streaming multimedia require both a more stable and more reliable service than the default best effort service from the underlying computer network. To guarantee steady data transmission despite the unpredictability of the network, a single reserved path for each traffic flow is used. However, a single dedicated path suffers from single link failures. To allow for continuous service inexpensively, unreserved backup paths are used in this thesis. While there are no wasted resources using unreserved backup paths, recovery from a failure may not be perfect. Thus, a goal for this approach is to design algorithms that compute backup paths to mask the failure for all traffic, and failing that, to maximize the number of flows that can be unaffected by the failure. Although algorithms are carefully designed with the goal to provide perfect recovery, when using only unreserved backup paths, re-routing of all affected flows, at the same service quality as before the failure, may not be possible under some conditions, particularly when the network was already fully loaded prior to the failure. Alternate strategies that trade off service quality for continuous traffic flow to minimize the effects of the failure on traffic should be considered. In addition, the actual backup path calculation can be problematic because finding backup paths that can provide good service often requires a large amount of information regarding the traffic present in the network, so much that the overhead can be prohibitive. Thus, algorithms are developed with trade-offs between good performance and communication overhead. In this thesis, a family of algorithms is designed such that as a whole, inexpensive, scalable, and effective performance can be obtained after a failure. Simulations are done to study the trade-offs between performance and scalability and between soft and hard service guarantees. Simulation results show that some algorithms in this thesis yield competitive or better performance even at lower overhead. The more reliable service provided by unreserved backup paths allows for better performance by current applications inexpensively, and provides the groundwork to expand the computer network for future services and applications. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Reachability analysis is one of the earliest and most common techniques for protocol validation. It is well suited to checking the protocol syntactic properties since they are a direct consequence of the structure of the reachability tree. However, validations of unbounded protocols via reachability analysis always lead to the "state explosion" problem. To overcome this, a new approach in reachability analysis has been proposed by Vuong et al [Vuong 82a, 83a]. While not loosing any information on protocol syntactic properties, the Teachability tree constructed by the new approach for all non-FIFO and for a particular set of FIFO protocols (called well-ordered protocols) will become finite. This thesis is concerned with the implementation of an integrated package called VALIRA (VALIdation via Reachability Analysis) which bases on both the proposed technique and the conventional technique. Details and implementation of the various approaches used in VALIRA are presented in order to provide an insight to the package. Various features of the package are demonstrated with examples on different types of protocols, such as the FIFO, the non-FIFO, and the priority protocols. The use of VALIRA was found to be practical in general, despite some limitations of the package. Further enhancements on the VALIRA are also suggested. / Science, Faculty of / Computer Science, Department of / Graduate

With the increasing need for distributed processing and computer networking, the demand for open systems interconnection (OSI) has also increased. In [Davis-88], Davis et al propose a new generation portable protocol tester that will be able to provide conformance testing for OSI protocol implementations. In this thesis report, a specialized programmable hardware module, called protocol decoding accelerator (PDA), is designed to be used as the PDU decoder engine being defined in the Davis architecture. PDU decoding is the process of parsing the PDU header fields into a data structure that can be more readily used by other processes. Decoding can be time consuming because there is a large variety of PDU fields and formats. Conventional approach to PDU decoding is often implemented as software program designed for general purpose processor architecture. However, most general purpose processors do not handle PDU decoding efficiently. There are other VLSI protocol controllers, but they all have limited programmability and flexibility. The PDA is developed based on a simple instruction set with dedicated hardware to optimize important functions. Using selected PDU types and decoding programs from OSI layer 2 to 4 protocols, the resulting PDA design shows a minimum of 16 times faster average execution time and about five times smaller program size when compared to a 68000 system. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate