Technical Reports

Thesis Papers

Papers resulting from CSHCN-related research are periodically added to the Institute for Systems Research Technical Report Database where they can be browsed by year or searched by author or keywords.

Here is a preview of recent CSHCN thesis submissions that will be available in the database soon:

Routing and Quality of Service in Mobile Adhoc Networks with TORA/INORA (CSHCN MS 2002-1)

Author: Dinesh Dharmaraju

Advisor: John S. Baras

Mobile Adhoc NETworks(MANETs) are characterized by bandwidth constrained links, multiple hops and dynamic topologies. Routing and providing quality of service in these networks is a highly challenging task. In this thesis, we discuss the unicast routing in MANETs with enhancements to the Temporally Ordered Routing Algorithm(TORA) and quality of service at the network layer with INORA.

Temporally Ordered Routing Algorithm (TORA) is a highly distributed, scalable routing protocol for MANETs. We discuss the improvements in the performance of TORA by Query Localization. We also discuss the improvements to TORA to remove a specific traffic instability problem in TORA. We also describe the proactive operation of TORA and show by simulations that it is generally a good idea to have the gateway nodes in a MANET proactively perform route building and route maintenance.

We propose INORA, a network layer QoS support mechanism in adhoc networks, which makes use of the INSIGNIA in-band signaling mechanism and TORA. We present an effective coupling between TORA and INSIGNIA to get routes that are "best-able" to provide QoS requirements for a flow. INORA also provides congestion control. We present two schemes called "Coarse feedback scheme" and "Fine feedback scheme" under the INORA frame work. We show that under heavily loaded conditions, the INORA schemes perform better than when the signaling protocol and the routing protocol operate without feedback.

Reliable Multicasting Based on Air Caching for Flat Hierarchy Networks (CSHCN MS 2002-2)

Author: Kyriakos Manousakis

Advisor: John S. Baras

The evolution of satellite networks in the commercial and military world has pushed the research community towards the solution of important problems related to this kind of networks, which are characterized from the lack of physical hierarchy. One of those important problems is how to design an efficient reliable multicasting protocol for one-hop (flat) networks where the link may present characteristics like high propagation delay and high BER. The existing reliable multicasting protocols are inefficient when applied to flat networks, since those are based on intermediate receivers and local recovery techniques. We introduce the Air Cache, which serves as a fast access memory that is realized on the air and contains packets for the recovery of corrupted or erroneous data packets at the receivers. In this thesis we present two classes of reliable multicasting protocols, which are based on the combination of FEC and ARQ with air caching. The non-adaptive class of protocols (UDPAC, RDPAC, PPAC) is characterized by the static nature of the Air Cache in term of size and content and the second class of protocols (ACDAC, ASPAC, HADAC) is characterized by the dynamic nature of the Air Cache. The objective is to achieve better performance than the existing reliable multicasting protocols in flat hierarchy networks. We evaluate the proposed protocols in terms of the delay, robustness, scalability and the hardware requirements that they pose. The results that we collected prove the effectiveness of air caching when it is combined with traditional techniques like FEC and ARQ.

Performance Management in ATM Networks (CSHCN PhD 2002-3)

Author: Anubhav Arora

Advisor: John S. Baras

ATM is representative of the connection-oriented resource provisioning class of protocols. The ATM network is expected to provide end-to-end QoS guarantees to connections in the form of bounds on delays, errors and/or losses. Performance management involves measurement of QoS parameters, and application of control measures (if required) to improve the QoS provided to connections, or to improve the resource utilization at switches. QoS provisioning is very important for realtime connections in which losses are irrecoverable and delays cause interruptions in service. QoS of connections on a node is a direct function of the queueing and scheduling on the switch. Most scheduling architectures provide static allocation of resources (scheduling priority, maximum bu er) at connection setup time. Endto- end bounds are obtainable for some schedulers, however these are precluded for heterogeneously composed networks. The resource allocation does not adapt to the QoS provided on connections in real time. In addition, mechanisms to measure the QoS of a connection in real-time are scarce. In this thesis, a novel framework for performance management is proposed. It provides QoS guarantees to real time connections. It comprises of in-service QoS monitoring mechanisms, a hierarchical scheduling algorithm based on dynamic priorities that are adaptive to measurements, and methods to tune the schedulers at individual nodes based on the end-to-end measurements. Also, a novel scheduler is introduced for scheduling maximum delay sensitive trac. The worst case analysis for the leaky bucket constrained trac arrivals is presented for this scheduler. This scheduler is also implemented on a switch and its practical aspects are analyzed. In order to understand the implementability of complex scheduling mechanisms, a comprehensive survey of the state-of-the-art technology used in the industry is performed. The thesis also introduces a method of measuring the one-way delay and jitter in a connection using in-service monitoring by special cells.

A Direct to Ground Architecture for Supporting Communications for the International Space Station (CSHCN MS 2002-5 - Thesis is from 2001.)

Author: Alex T. Nguyen

Advisor: John S. Baras

The deployment of the International Space Station (ISS) has opened new opportunities for research in space, providing a unique platform for tele-science, microgravity experiments, human physiology studies, and earth observation. In order to control, gain data from, and interact with these activities from the ground, a communications system that can support this broad range of applications needs to be established. In this thesis, three communications architectures for the ISS are discussed: 1) using NASA’s Tracking Data Relay Satellite System (TDRSS), 2) using emerging broadband commercial satellite systems to relay data to the ground, and 3) communicating directly to the ground (“DTG”). The thesis will focus on the latter option, DTG, and establish a methodology for determining the optimum placement of ground terminals for this type of service. A simulation model is developed for a large image file download application, and a detailed coverage analysis of the ISS communicating directly to these ground facilities is performed. In addition, a bottom-up cost estimate of this architecture is developed and compared to the costs of the other two architectures. The results show that the direct to ground architecture cost is competitive with that of the other architectures, and offers scalability for non-real-time applications. Coverage provided by commercial Ka-band satellite systems is about the same as that achieved by direct to ground, but its services will likely not be tailored to the needs of the ISS. The TDRS system provides complete coverage, and is therefore good for real-time applications such as videoconferencing.

Intelligent Distributed Fault and Performance Management for Communication Networks (CSHCN PhD 2002-2)

Author: Honjun Li

Advisor: John S. Baras

This dissertation is devoted to the design of an intelligent, distributed fault and performance management system for communication networks. The architecture is based on a distributed agent paradigm, with belief networks as the framework for knowledge representation and evidence propagation.

The dissertation consists of four major parts. First, we choose the mobile code technology to help implement a distributed, extensible framework for supporting adaptive, dynamic network monitoring and control. The focus of our work is on three aspects. First, there is the design of the standard infrastructure, or Virtual Machine, based on which agents could be created, deployed, managed and initiated to run. Second, there is the collection API for our delegated agents to collect data from network elements. Third, there is the callback mechanism through which the functionality of the delegated agents or even the native software could be extended. We propose three system designs based on such ideas.

Second, we propose a distributed framework for intelligent fault management purpose. The managed network is divided into several domains and for each domain, there is an intelligent agent attached to it, which is responsible for this domain's fault management tasks. Belief networks are embedded in such an agent as the probabilistic fault models, based on which evidence propagation and decision making processes are carried out.

Third, we address the problem of parameter learning for belief networks with fixed structure. Based on the idea of Expectation-Maximization (EM), we derive a uniform learning algorithm under incomplete observations. Further, we study the rate of convergence via the derivation of Jacobian matrices of our algorithm and provide a guideline for choosing step size. Our simulation results show that the learned values are relatively close to the true values. This algorithm is suitable for both batch and on-line mode.

Finally, when using belief networks as the fault models, we identify two fundamental questions: (1) When can I say that I get the right diagnosis and stop? (2) If right diagnosis has not been obtained yet, which test should I choose next?

The first question is tackled by the notion of right diagnosis via intervention, and we solve the second problem based on a dynamic decision theoretic strategy. Simulation shows that our strategy works well for the diagnosis purpose. This framework is general, scalable, flexible and robust.

Authenticated Key Agreement in Dynamic Groups (CSHCN TR 2002-1 -- MS thesis)

Author: Arvind Mani

Advisor(s): John S. Baras

Multicast security poses interesting challenges in the area of key management. Designing a good protocol for key agreement in dynamic multicast groups involves a thorough understanding of the trade-offs that exist among storage, communication and computation overhead. The contribution of this thesis is a verifiable protocol for authenticated key agreement based on a distributed key generation scheme. The underlying key generation scheme has shown promise in being natural for collaborative group applications. The protocol can then be tailored to particular applications once we understand the communication, storage and computation constraints specific to the application. To handle group membership changes in dynamic groups, an auxiliary key agreement protocol is introduced. The auxiliary protocol re-uses contributions to the key in the previous round, to form the new key. The key shares of the members contributing fresh values in the current round are more susceptible to discovery by colluding group members (not outsiders). The auxiliary protocol does not introduce any other security weakness. A protocol that starts from the scratch on membership change is going to be expensive, slow and unsuitable for most applications. We use the well-known Logical Key Tree (LKH) structure to allow the key management (distribution) part of the protocol to scale to large groups. The key tree structure helps to localize the effect of membership change and as a result, reduces the communication overhead to form the new session key.

Medium Access Control and Quality-of-Service Routing for Mobile Ad Hoc Networks (CSHCN PhD 2001-3)

Author: Chenxi Zhu

Advisor: John S. Baras

A mobile ad hoc network is an autonomous system consisting solely of mobile terminals connected with wireless links. This type of network has received considerable interest in recent years due to its capability to be deployed quickly without any fixed infrastructure. Nodes self-organize and re-configure as they join, move, or leave the network. How to design distributed protocols capable of handling the dynamic nature of these networks is an interesting but difficult topic.

When TDMA is used, distributed protocols are needed to generate transmission schedules. An important issue is how to produce a schedule quickly. This is critical when the network is large or the network changes frequently. Here we develop two fully distributed protocols for generating or updating TDMA schedules. Contention is incorporated into the scheduling protocols for them to work independently of the network size. The schedule can be generated at multiple parts of the network simultaneously. In the Five-Phase Reservation Protocol (FPRP), a broadcast schedule is produced when nodes contend among themselves using a new five-phase message exchange mechanism. In the Evolutionary-TDMA scheduling protocol (E-TDMA), schedules are updated when nodes contend to reserve transmission slots of different types (unicast, multicast, broadcast). Both are scalable protocols suitable for large or dynamic networks. Another issue related to medium access control is transmission power control. Our contribution to power control is to develop a channel probing scheme for networks applying power control, which allows a node to probe a channel and estimate the channel condition. It can be used for dynamic channel allocation in a TDMA or FDMA system, or admission control in a DS/CDMA system. It is a fully distributed scheme which requires little communication overhead. Multiple links can probe a channel simultaneously and each makes individual yet correct decisions. The last topic is Quality-of-Service routing. An efficient distributed scheme is developed to calculate the end-to-end bandwidth of a route. By incorporating this scheme with the AODV protocol, we developed an on-demand QoS routing protocol which can support CBR sessions by establishing QoS routes with reserved bandwidth. It repairs a route when it breaks. Load balancing and route redundancy are also achieved. It is applicable for small networks or short routes under relatively low mobility.

Error Control for Multicasting in Satellite and Hybrid Communication Networks (CSHCN PHD 2001-2)

Author: Daniel E. Friedman

Advisor: Anthony Ephremides

A problem inherent in ARQ multicasting over a broadcast channel is that a retransmission typically benefits only a minority of destinations while all others wait unproductively. This results in poor throughput to each receiving station in the network, with the throughput diminishing as the number of receivers grows.

If point-to-point links between the transmitter and each receiver were also available, then conceivably retransmissions could be sent over such secondary links. This would reduce the frequency of retransmissions interrupting the flow of new packets on the roadcast link. That is, a hybrid satellite-terrestrial network architecture would allow greater throughput for multicasting than a pure-satellite network.

This work examines ARQ multicasting in such a network, and confirms by analysis and simulation that, within limits, such a throughput advantage can be realized. A detailed discussion of implementation aspects for point-to-point and point-to-multipoint ARQ protocols in both pure-satellite and hybrid networks is presented as well. This work also considers partitioning a fixed amount of bandwidth to maximize throughput, possibly subject to a cost constraint, and the effect of a "poor listener" upon performance in both pure-satellite and hybrid networks.

Resource Allocation in Ka-band Satellite Systems (CSHCN MS 2001-1)

Author: Youyu Feng

Advisor: John S. Baras

The Ka-band satellite system is of increasing interest around the world due to its huge bandwidth. Rain fading is one of the primary factors affecting performance and availability of the Ka-band system. Extra power on the satellite can provide compensation for rain attenuation. In this thesis, we study the rain fade compensation problem for downlink transmission in the Ka-band satellite by dynamic resource allocation. The resources we consider include power and antennas onboard the satellite. The goal is to maximize the aggregate priority of packets arriving at all downlink spots as well as maintain fairness among downlinks. We formulate the problem mathematically in the framework of Knapsack Problems (KP). In particular, we show the resource allocation problem is equivalent to a Multi-choice Multiple Knapsack Problem (MCMKP), which, in general, is very hard to solve in a reasonable time. By introducing the seeding theory into the antenna scheduling, we decompose the original MCMCP into a sequence of Multiple-choice Knapsack Problems (MCKP), which are easier to solve. The effectiveness of our approach is demonstrated through simulations in OPNET. Comparison with the Multiple Knapsack Problem (MKP) approach proposed by Birmani is also provided.

Routing and Scheduling Algorithms in Resource-Limited Wireless Multi-hop Networks (CSHCN PhD 2001-1)

Author: Anastassios Michail

Advisor: Anthony Ephremides

Abstract: The recent advances in the area of wireless networking present novel opportunities for network operators to expand their services to infrastructure-less wireless systems. Such networks, often referred to as ad-hoc or multi-hop or peer-to-peer networks, require architectures which do not necessarily follow the cellular paradigm. They consist of entirely wireless nodes, fixed and/or mobile, that require multiple hops (and hence relaying by intermediate nodes) to transmit their messages to the desired destinations. The distinguishing features of such all-wireless network architectures give rise to new trade-offs between traditional concerns in wireless communications (such as spectral efficiency, and energy conservation) and the notions of routing, scheduling and resource allocation. The purpose of this work is to identify and study some of these novel issues, propose solutionsin the context of network control and evaluate the usual network performance measures as functions of the new trade-offs. To these ends, we address first the problem of routing connection-oriented traffic with energy efficiency in all-wireless multi-hop networks. We take advantage of the flexibility of wireless nodes to transmit at different power levels and define a framework for formulating the problem of session routing from the perspective of energy expenditure. A set of heuristics are developed for determining end-to-end unicast paths with sufficient bandwidth and transceiver resources, in which nodes use local information in order to select their transmission power and bandwidth allocation. We propose a set of metrics that associate each link transmission with a cost and consider both the cases of plentiful and limited bandwidth resources, the latter jointly with a set of channel allocation algorithms. Performance is measured by call blocking probability and average consumed energy and a detailed simulation model that incorporates all the components of our algorithms has been developed and used for performance evaluation of a variety of networks. In the sequel, we propose a "blueprint" for approaching the problem of link bandwidth management in conjunction with routing, for ad-hoc wireless networks carrying packet-switched traffic. We discuss the dependencies between routing, access control and scheduling functions and propose an adaptive mechanism for solving the capacity allocation (at both the node-level and the flow-level) and the route assignment problems, that manages delays due to congestion at nodes and packet loss due to error prone wireless links, to provide improved end-to-end delay/throughput. The capacity allocations to the nodes and flows and the route assignments are iterated periodically and the adaptability of the proposed approach allows the network to respond to random channel error bursts and congestion arising from bursty and new flows.

Some papers in the Technical Report Database are available for viewing in Portable Document Format (PDF). To view and print PDF files, you must have Adobe Acrobat Reader installed on your computer. If you do not have Acrobat Reader, you can download it by visiting the Adobe web site.

Other papers are available in Postscript (PS) format. To view and print Postscript files, you must have Ghostscript/GSview. Alternately, you can use Adobe Acrobat Distiller to convert the PS file to a PDF.

In addition, the University of Maryland College Park subscribes to ProQuest Digital Dissertations. Faculty, staff, and students have online access to citations and abstracts for every title in the database. Titles published since 1997 are available in PDF.