Technical Reports

Thesis Papers

Authors Featured on this Page:

A. Arora

J.S. Baras

V.G. Bharadwaj

M. Hadjitheodosiou

Y. Jiang

J.-S. Jou

P. Keleher

H. Li

M. Liu

A.T. Nguyen

S.M. Payne

R. Poovendran

R. Srinivasan

F.W. Sun

R. Vaidyanathan

H. Xi

S.-A. Yang

C. Zhang

X. Zhou

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.

Alternative Network Architectures for Supporting Communications from the International Space Station (CSHCN TR 2002-9) by Alex T. Nguyen, M. Hadjitheodosiou, J.S. Baras

In order to support the communications needs of the International Space Station (ISS), alternative communications architectures to provide broadband support need to be considered. We address three communications options and evaluate an architecture for the direct to ground option, which could serve as an intermediary solution to satisfy near term communications needs of commercial experiments and payloads on the ISS and overcome certain limitations of the current ISS communications infrastructure. We focus on a particular user’s requirements, and examine the system’s communications links, and coverage availability. These parameters, along with high-level cost estimates, are compared to using commercial relay satellites, and an enhanced TDRSS. The direct to ground option is viable for store-and-forward applications and cost comparable to commercial constellations, but TDRSS is the choice for real-time or continuous data applications.

On QoS Provisioning in ATM Networks (CSHCN TR 2002-7) by Anubhav Arora, John S. Baras

ATM is representative of the connection-oriented resource provisioning class of protocols. An 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 real-time connections in which losses are irrecoverable and delays cause interruptions in service. Most scheduling disciplines provide static allocation of resources at connection setup time. End-to-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 to connections in real-time. In addition, mechanisms to measure the QoS of a connection in real-time are scarce.

A novel framework for QoS management is proposed in this paper to provide 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 endto- end measurements.

A Direct-to-Ground Architecture for Supporting Commercial Communications from the International Space Station (CSHCN TR 2002-6) by Alex T. Nguyen, X. Zhou, M. Hadjitheodosiou, J. Baras

We outline the first steps of an effort to start defining a communications architecture for supporting broadband data communications from the International Space Station. We address three communications options and focus on a direct-to-ground architecture, which could serve as an intermediary solution to satisfy near term communications needs of commercial experiments and payloads on the ISS and overcome certain limitations of the current ISS communications infrastructure. A high-level analysis of the architecture for the direct to ground option is performed, focusing on a particular user’s requirements, communications links, and coverage availability. We also discuss system, mobility support and protocol issues that need to be addressed for this solution to be a feasible alternative.

A Multilevel ON/OFF Model for Multifractal Internet Traffic (CSHCN TR 2002-5) by Jia-Shiang Jou, John S. Baras

In this paper, an open-loop multilevel ON/OFF model is proposed to capture the multifractal behavior of the HTTP traffic on the Internet. It is assumed that the life time of a TCP session and the active time of a burst within a TCP session have a heavy-tail type distribution. The aggregate traffic of this model is shown to be multifractal. We analyze its second and higher order statistics by the wavelet analysis and develop a simple method to estimate the model parameters from a real Internet trace. We show that real and synthesized traffic produce the same Logscale Diagram with accuracy, for proper selection of the model parameter. Finally, we compare using the NS-2 simulator the queueing behavior of FIFO queues fed by real and synthetic traffic demands.

Negotiating Access Control Policies Between Autonomous Domains (CSHCN TR 2002-3) by Vijay G. Bharadwaj, John S. Baras

Autonomous policy domains often need to share resources to accomplish a common task. To do this they must negotiate a common access control policy to the shared resources. We use mathematical techniques from game theory to show that the outcome of such negotiations can often be predicted from the distribution of power among the participants, independent of the actual mechanics of negotiation. We discuss the axiomatic derivation of some game theoretic solution concepts, and illustrate our techniques with examples.

Performance Evaluation of Run-to-Run Control Methods in Semiconductor Processes (CSHCN TR 2001-20) by Chang Zhang and John S. Baras

Run-to-Run (RtR) control plays an important role in semiconductor manufacturing processes. In this paper, RtR control methods are classified and evaluated. The set-valued RtR controllers with ellipsoid approximation are compared with two typical RtR controllers: the Exponentially Weighted Moving Average (EWMA) controller and the Optimizing Adaptive Quality Controller (OAQC) by simulations according to the following criteria: A good RtR controller should be able to compensate for various disturbances, such as small drifts, step disturbances and model errors; moreover, it should be able to deal with bounds, cost requirement and multiple targets that are often encountered in semiconductor processes. Based on our simulation results, suggestions on selection of a proper RtR controller for a semiconductor process are given as conclusions.

A Framework for Supporting Intelligent Fault and Performance Management for Communication Networks (CSHCN TR 2001-13) by Hongjun Li, John S. Baras

In this paper, we present a framework for supporting intelligent fault and performance management for communication networks. Belief networks are taken as the basis for knowledge representation and inference under evidence. When using belief networks for diagnosis, we identify two questions: When can I say that I get the right diagnosis and stop? If right diagnosis has not been obtained yet, which test should I choose next?

For the first question, we define the notion of right diagnosis via the introduction of intervention networks. For the second question, we formulate the decision making procedure using the framework of partially observable Markov decision processes. A heuristic dynamic strategy is proposed to solve this problem and the effectiveness is shown via simulation.

On System Designs of Distributed, Extensible Framework for Network Monitoring and Control (CSHCN TR 2001-12) by Hongjun Li, Shah-An Yang, and John S. Baras

In this paper, we present a distributed, extensible framework for supporting adaptive, dynamic network monitoring and control. We borrow the paradigm of management by delegation [8] and distribute some processing intelligence to network elements. The functionality of the delegated agents, and even that of the native software processes, could be extended dynamically without recompilation. Such procedure is called change of logic and we explain it in the framework of communicating finite state machines for extending native process functionality. We use Java technology and C/C++ dynamic linkage mechanism to achieve the standard hosting infrastructure for these agents and our system designs span a wide scope of applications.

A New Adaptive Aggregation Algorithm for Infinite Horizon Dynamic Programming (CSHCN TR 2001-5) by Chang Zhang and John S. Baras

Dynamic programming suffers the "curse of dimensionality" when it is employed for complex control systems. State aggregation is used to solve the problem and accelerate computation by looking for a sub-optimal policy. In this paper, a new method, which converges much faster than conventional aggregated value iteration based on TD(0), is proposed for computing the value functions of the aggregated system. Preliminary results show that the new method increases the speed of convergence impressively. Aggregation introduces errors inevitably. An adaptive aggregation scheme employing the new computation method is also proposed to reduce the aggregation errors.

A Hierarchical Structure For Finite Horizon Dynamic Programming Problems (CSHCN TR 2000-19) by Chang Zhang, J.S. Baras

In dynamic programming (Markov decision) problems, hierarchical structure (aggregation) is usually used to simplify computation. Most research on aggregation of Markov decision problems is limited to the infinite horizon case, which has good tracking ability. However, in real life, finite horizon stochastic shortest path problems are often encountered.

In this paper, we propose a hierarchical structure to solve finite horizon stochastic shortest path problems in parallel. In general, the approach reduces the time complexity of the original problem to a logarithm level, which has significant practical meaning.

Systems Designs for Adaptive, Distributed Network Monitoring and Control (CSHCN TR 2000-16) by Hongjun Li, Shah-An Yang, Haifeng Xi, John S. Baras

In this paper we present systems designs for adaptive, distributed network monitoring and control. The ideas are to distribute some processing intelligence to network elements, in order to efficiently utilize bandwidth and balance the computation load, and design a dynamic interface such that the delegated agents could be managed remotely by the manager. The functionality of the delegated agents, and even that of the native software processes, could be extended dynamically without recompilation. The creation, deployment, operation, and management of the delegated agents require a standard infrastructure on each system where these agents need to be hosted. We use Java technology and a C/C++ dynamic linkage mechanism to fulfill such a requirement under different situations and our systems designs span a wide scope of applications.

Intelligent Distributed Fault Management for Communication Networks (CSHCN TR 2000-15) by Hongjun Li, John S. Baras

In this paper, we present an intelligent, distributed fault management system for communication networks using belief networks as fault model and inference engine. The managed network is divided into domains and for each domain, there is an intelligent agent called Domain Diagnostic Agent attached to it, which is responsible for this domain's fault management. Belief network models are embedded in such an agent and under symptoms observation, the posterior probabilities of each candidate fault node being faulty is computed. We define the notion of right diagnosis, describe the diagnosis process based on this concept, and present a strategy for generation of test sequence.

On the True Cramer-Rao Lower Bound for the DA Joint Estimation of Carrier Phase and Timing Offsets (CSHCN TR 2000-14) by Y. Jiang, F.W. Sun, John S. Baras

The Cramer-Rao lower bound (CRB) plays a pivotal role in
parameter estimation theory, such as timing, frequency and
phase synchronization. Therefore, it receives considerable
attention in the literature. This paper concerns the CRB for
data-aided (DA) timing and/or phase recovery, i.e. the
parameter synchronization is aided by a training sequence
known to the receiver.

For DA parameter synchronization, the CRB typically varies
with the training sequence. This indicates that different training
sequences offer fundamental different performance.
Therefore, it is very important to be able to compute the
CRB for any particular training sequence to understand the
fundamental limit that a particular training sequence has.
However, in the literature, the closed-form CRB for an
arbitrary training sequence is not available. In principle, it is
possible to use brute-force numerical approach to compute
CRB for any given training sequence. Such brute-force
computation involves evaluation of derivatives numerically
and matrix inversion. Besides the computational complexity,
brute-force approach does not provide any insight on the
interaction between training sequence and the resultant CRB.

In the literature, the widely cited close-form data-aided CRB for timing and phase recovering was derived under the assumption that the training sequence is independently identical distributed (i.i.d.) and the length of the training sequence is sufficiently long. We found that the CRB for a particular training sequence can be significantly lower than that with the long i.i.d. assumption. Therefore, the widely cited data-aided CRB actually does not give the fundamental limit for a particular training sequence.

In this manuscript, we derive a closed-form formula for data-aided CRB for timing and phase synchronization with respect to arbitrary training sequence. The bound illustrates the close relation between the training sequence and the fundamental limit on timing and phase synchronization. This bound provides additional insights on the sequence design.

2000 IEEE International Conference on Communications

Maximum Likelihood Slow Frequency-Selective Fading Channel Estimation Using Frequency Domain Approach (CSHCN TR 2000-13) by Y. Jiang, John S. Baras

This paper addresses the channel estimation problem for slow frequency-selective fading channel using training sequence and maximum likelihood (ML) approach.

Traditional works assumed symbol period spaced delay-tapped line model and additive white Gaussian noise (AWGN). Because of pre-filtering in the receiver front end, if the sampling rate is larger than one sample per symbol or sampling epoch is unknown (i.e., timing information is not available), AWGN model is not valid anymore.

A more general ML channel estimation method using discrete Fourier transform (DFT) is derived with the assumption of colored Gaussian noise and over sampling. Similar idea can be adopted to derive the ML joint timing and phase estimation algorithm.

Globecom 2000

A Decision-Process Analysis of Implicit Coscheduling (CSHCN TR 2000-12) by R. Poovendran, P. Keleher, John S. Baras

This paper presents a theoretical framework based on Bayesian decision theory for analyzing recently reported results on implicit coscheduling of parallel applications on clusters of workstations. Using probabilistic modeling, we show that the approach presented can be applied for processes with arbitrary communication mixes. We also note that our approach can be used for deciding the additional spin times in the case of spin-yield. Finally, we present arguments for the use of a different notion of fairness than assumed by prior work.

International Conference on Parallel and Distributed Computing

Fair Bandwidth Allocation and Buffer Management in Hybrid Network Gateways (CSHCN TR 2000-11) by Roshni Srinivasan, Ravichander Vaidyanathan, John S. Baras

In this paper, we present an efficient and fair resource allocation scheme for scheduling and buffer management in a bottleneck hybrid satellite-terrestrial network gateway with per-flow TCP queues.

Our first contribution is the use of Fair Queueing in conjunction with Probabilistic Fair Drop, a new buffer management policy to allocate bandwidth and buffer space in the gateway, to ensure that all TCP flows threading the gateway achieve high end-to-end throughput and fair service.

Our second contribution is to introduce the concept of buffer dimensioning to alleviate the inherent bias of the TCP algorithm towards connections with large Round Trip Time.

In support of each of these contributions, we report on extensive simulation results. Our scheme outperforms other resource allocation schemes reported in the literature and in particular, demonstrates significant improvements in fairness to long RTT connections in the hybrid network framework.

Reliable Multicasting via Satellite: Delay Considerations (CSHCN TR 2000-10) by Stephen M. Payne, John S. Baras

Many different reliable multicast protocols have been proposed and analyzed in the current literature. Since satellites are naturally a braodcast medium, multicast communications have the potential to greatly benefit from their wide-scale deployment. The performance of reliable multicast protocols needs to be studied and become better understood over networks including satellite links. Most of the analysis performed on these protocols has dealt with bandwidth usage, buffer requirements, and processing delay. Very few studies address the transmission delay incurred from using reliable multicast protocols. Hybrid error control protocols have been studied in terms of bandwidth and delay. The effects of different estimation schemes coupled with autoparity usage are investigated and results are compared. Simple adaptive mechanisms used with a local recovery scheme are found to offer the best overall results in terms of reducing recovery latency and satellite bandwidth usage.

Hierarchical Modeling for Network Performance Evaluation (CSHCN TR 2000-8) by Mingyan Liu, John S. Baras

In this paper we present a hierarchical network model to estimate the connection blocking for large hierarchical networks.

As networks grow in size, nodes tend to form clusters geographically and hierarchical routing schemes are more commonly used, and it is important that network modeling methods have scale-up capabilities. Loss networks and reduced load/fixed point models are often used to approximate call blocking probabilities and hence throughput in a circuit switched network. We use the same idea for estimating connection blocking in a data network with certain QoS routing schemes. However so far most work being done in this area is for flat networks with flat routing schemes.

We aim at developing a more efficient approximation method for networks that have a natural hierarchy and/or when some form of hierarchical routing policy is used. We present hierarchical models in detail for fixed hierarchical routing and dynamic hierarchical routing policies, respectively, via the notion of network abstraction, route segmentation, traffic segregation and aggregation. Computation is done separately within each cluster (local) and among clusters (global), and the fixed point is obtained by iteration between local and global computations. We present results from both numerical experiments and discrete event simulations.

Hierarchical Loss Network Model for Performance Evaluation (CSHCN TR 2000-1) by Mingyan Liu, John S. Baras

In this paper we present a hierarchical loss network model for estimating the end-to-end blocking probabilities for large networks.

As networks grow in size, nodes tend to form clusters geographically and hierarchical routing schemes are more commonly used. Loss network and reduced load models are often used to approximate end-to-end call blocking probabilities, and hence, throughput. However so far all work being done in this area is for flat networks with flat routing schemes.

We aim at developing a more efficient approximation method for networks that have a natural hierarchy and/or when some form of hierarchical routing policy is used. We present two hierarchical models in detail for fixed hierarchical routing and dynamic hierarchical routing policies, respectively, via the notion of network abstraction, route segmentation, traffic segregation and aggregation. Computation is done separately within each cluster (local) and among clusters (global), and the fixed point is obtained by iteration between local and global computations. We also present numerical results for the first case.

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.