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.

Coming Soon ...

TCP Over Satellite Hybrid Networks: A Survey (not yet available) by Xiaoming Zhou, John S. Baras 192

Satellite is going to play an important role in the global information infrastructure. Satellite can provide direct to home Internet service (i.e. DirecPC from Hughes Network System) and it can also serve as traffic trunk in the middle of the network. About 98 percent of the Internet traffic is TCP traffic. TCP works well in the terrestrial fiber network. However, in the satellite hybrid networks, because of the long propagation delay, large bandwidth-delay product, high bit error rate and downstream/upstream bandwidth asymmetry, TCP performance degrades dramatically. This paper addresses the problems of TCP in satellite data networks and reviews the proposed solutions in the literature. For each solution, the advantages and disadvantages are pointed out. In addition, extensive simulations have been done for the proxy based scheme currently used in the industry to find out how and to what extent the enhancements, such as connection splitting, window scaling and selective acknowledgement, benefit the TCP throughput.

A Direct to Ground Architecture for Supporting Communications for the International Space Station (not yet available) 122

Available Now ...

TCP Traffic Modeling via Limit Theorems (CSHCN TR 2002-13) by Peerapol Tinnakornsrisuphap, Armand M. Makowski

Traditional TCP traffic modeling has focused on "micro-scale" modeling of TCP, i.e., detailed modeling of a single TCP flow. While micro-scale models of TCP are suitable for understanding the precise behavior of individual flows, they are not well suited to the situation when a large number of TCP flows interact with each other as is the case in realistic networks.

In this survey, we present several works which focus on "macro-scale" modeling of TCP, where the aggregate behavior of TCP traffic can be simplified by applications of limit theorems.

Using Commercial Satellites to Provide Communication Support for Space Missions (CSHCN TR 2002-12) by Michael Hadjitheodosiou, Alex T. Nguyen

NASA is interested in using commercial satellites to provide broadband communications support for future space missions. In this paper, we describe a large-scale simulation model that we plan to use for detailed performance studies of critical parameters. We focus on the unique challenges we face and how we plan to use simulations to investigate:

the feasibility of using proposed commercial constellations to carry various classes of traffic between ground terminals and near-earth spacecraft.
the performance optimization of such systems.

The research and scientific content in this material has been published in the proceedings from the GLOBECOM2000 Symposium on Satellite Communications for the New Millennium, San Francisco, Nov, 2000.

Using Commercial Communication Satellite Constellations for Supporting Traffic from NASA Missions (CSHCN TR 2002-11) by Michael Hadjitheodosiou, Alex T. Nguyen

NASA is interested in using commercial satellites to provide broadband communications support for the International Space Station and other space missions. We describe a large-scale simulation model that we plan to use for detailed performance studies of critical parameters such as QoS guarantees for specific services, traffic routing schemes, transport protocol support, dynamic bandwidth allocation methods, queuing disciplines, and handoff strategies. In this paper we focus on the unique challenges we face and how we plan to use simulations to investigate: · the feasibility of using proposed commercial constellations to carry mission telemetry, command and control, and tele-science traffic between ground terminals and near-earth spacecraft. · the end-to-end performance optimization of such systems.

The research and scientific content in this material has been published in the proceedings from the 18th AIAA International Conference on Satellite Systems & Communications, Oakland, CA, April 2000.

An Evolutionary Approach to the Multi-Level Capacitated Minimum Spanning Tree Problem (CSHCN TR 2002-10) by Ioannis Gamvros, S. Raghavan, Bruce Golden

Capacitated network design is a crucial problem to telecommunications network planners. In this paper we consider the Multi-Level Capacitated Minimum Spanning Tree Problem (MLCMST), a generalization of the well-known Capacitated Minimum Spanning Tree Problem. We present a genetic algorithm, based on the notion of grouping, that is quite effective in solving large-scale problems to within 10% of optimality.

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.

Scale Invariance Properties in the Simulated Annealing Algorithm (CSHCN TR 2002-8) by Mark Fleischer, Sheldon Jacobson

The Boltzmann distribution used in the steady-state analysis of the simulated annealing algorithm gives rise to several scale invariant properties. Scale invariance is first presented in the context of parallel independent processors and then extended to an abstract form based on lumping states together to form new aggregate states. These lumped or aggregate states possess all of the mathematical characteristics, forms and relationships of states (solutions) in the original problem in both first and second moments. These scale invariance properties therefore permit new ways of relating objective function values, conditional expectation values, stationary probabilities, rates of change of stationary probabilities and conditional variances. Such properties therefore provide potential applications in analysis, statistical inference and optimization. Directions for future research that take advantage of scale invariance are also discussed.

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.

The Effect of Positive Correlations on Buffer Occupancy: Comparison and Lower Bounds via Supermodular Ordering (CSHCN TR 2002-4) by Sarut Vanichpun

We use recent advances from the theory of multivariate stochastic orderings to formalize the "folk theorem" to the effect that positive correlations leads to increased buffer occupancy and larger buffer levels at a discrete time multiplexer queue of infinite capacity. We do so by comparing input sequences in the supermodular (sm) ordering and the corresponding buffer contents in the increasing convex (icx) ordering, respectively.

Three popular classes of (discrete-time) traffic models are considered here, namely, the fractional Gaussian noise (FGN) traffic model, the on-off source model and the M|G|infinity traffic model. The independent version of an input process in each of these classes of traffic models is a member of the same class. We show that this independent version is smaller than the input sequence itself and that the corresponding buffer content processes are ordered in the same direction. For each traffic model, we show by simulations that the first and second moments of buffer levels are ordered in agreement with the comparison results.

The more general version of the folk theorem, namely "the larger the positive correlations of input traffic, the higher the buffer occupancy levels" is established in some cases. For the FGN traffic models, we show that the process with higher Hurst parameter is larger than the process with smaller Hurst parameter. In the case of the M|G|infinity model, the effect of session-duration variability is discussed and the comparison result is obtained in the bivariate case.

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.

INORA- A Unified Signaling cum Routing Mechanism for QoS Support in Mobile Adhoc Networks (CSHCN TR 2002-2) by Dinesh Dharmaraju, Pedram Hovareshti, Ayan Roy-Choudhary

Mobile Adhoc Networks are characterized by bandwidth constrained wireless links, multiple hops and highly dynamic topologies. Thus, providing QoS support in MANETs is a challenging task. This paper presents the design, implementation and evaluation of a network layer QoS support mechanism which makes use of the INSIGNIA inband signaling mechanism and TORA routing protocol for MANETs. TORA provides multiple routes between a given source and destination. 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 combines congestion control with routing.

Authenticated Key Agreement in Dynamic Groups (CSHCN TR 2002-1) by Arvind Mani

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.

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 New Protocol for Scheduling TDMA Transmissions in Mobile Ad Hoc Networks (CSHCN TR 2001-19) by Chenxi Zhu, M. Scott Corson

A new protocol for scheduling TDMA transmission in a mobile ad hoc network is developed. With this protocol, nodes reserve time slots for unicast, multicast or broadcast transmission. The protocol uses contention for nodes to reserve transmission time slots, its operation is distributed and concurrent; therefore it is independent of the network size and can be used in large or dynamic networks. Its performance is studied with simulation and compared with IEEE 802.11 protocol.

QoS Routing for Mobile Ad Hoc Networks (CSHCN TR 2001-18) by Chenxi Zhu, M. Scott Corson

A Quality-of-Service (QoS) routing protocol is developed for mobile ad hoc networks. It can establish QoS routes with reserved bandwidth in a network employing TDMA. An efficient algorithm for calculating the end-to-end bandwidth on a path is developed and used together with the route discovery mechanism of AODV to setup QoS routes. Simulations show that the QoS routing protocol can produce higher throughput and lower delay than its best-effort counterpart.

An Evolutionary-TDMA Scheduling Protocol (E-TDMA) for Mobile Ad Hoc Networks (CSHCN TR 2001-17) by Chenxi Zhu and M. Scott Corson

A new single channel, time division multiple access (TDMA) scheduling protocol, termed "Evolutionary-TDMA", is presented for mobile ad hoc networks. The protocol allows nodes in an ad hoc network to reserve conflict-free TDMA slots for transmission to their neighbors. Two topology-dependent schedules are generated and maintained by the protocol: a broadcast schedule suitable for network control traffic and a mixed schedule which combines unicast, multicast and broadcast transmissions for user data traffic. The schedules are frequently updated in an evolutionary manner to maintain conflict-free transmissions. The protocol executes across the entire network simultaneously in a fully-distributed and parallel fashion. Traffic prioritization and Quality of Service (QoS) can be supported. Simulations have shown that the performance of the E-TDMA protocol is close to that of centralized algorithms, while being insensitive to network size in terms of scheduling quality and scheduling overhead. It is a scalable protocol suitable for very large networks, and networks of varying size.

On Satellite Multicast to Heterogeneous Receivers (CSHCN TR 2001-16) by Apinun Tunpan, M. Scott Corson

We propose a framework for single-source, satellite-based multicast dissemination of bulk files. The framework trades off between reception delay and bandwidth usage and coexists with terrestrial background network traffic; specifically TCP traffic utilizing a short-term congestion control mechanism. The framework consists of two major components: 1) a multicast rate scheduling mechanism that uses long-term, end-to-end multicast packet survival statistics in order to deal with the bandwidth-delay trade-off issue, and 2) a fair queueing algorithm that regulates the points where multicast traffic from the satellite meets terrestrial background traffic. We show through simulation the performance of this framework under a number of scenarios.

The research content in this material will appear in IEEE ICC 2001.

Update Propagation Strategies for Improving the Quality of Data on the Web (CSHCN TR 2001-15) by Alexandros Labrinidis, Nick Roussopoulos

Dynamically generated web pages are ubiquitous today but their high demand for resources creates a huge scalability problem at the servers. Traditional web caching is not able to solve this problem since it cannot provide any guarantees as to the freshness of the cached data. A robust solution to the problem is web materialization, where pages are cached at the web server and constantly updated in the background, resulting in fresh data accesses on cache hits. In this work, we define Quality of Data metrics to evaluate how fresh the data served to the users is. We then focus on the update scheduling problem: given a set of views that are materialized, find the best order to refresh them, in the presence of continuous updates, so that the overall Quality of Data (QoD) is maximized. We present a QoD-aware Update Scheduling algorithm that is adaptive and tolerant to surges in the incoming update stream. We performed extensive experiments using real traces and synthetic ones, which show that our algorithm consistently outperforms FIFO scheduling by up to two orders of magnitude.

Adaptive WebView Materialization (CSHCN TR 2001-14) by Alexandros Labrinidis, Nick Roussopoulos

Dynamic content generation poses huge resource demands on web servers, creating a scalability problem. WebView Materialization, where web pages are cached and constantly refreshed in the background, has been shown to ameliorate the scalability problem without sacrificing data freshness. In this work we present an adaptive online algorithm to select which WebViews to materialize, that realizes the trade-off between Quality of Service and Quality of Data. Our algorithm performs very close to the static, off-line optimal algorithm, and, under rapid workload changes, it outperforms the optimal.

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.

Efficient Resource Utilization through Carrier Grouping for Half-Duplex Communication in GSM-based MEO Mobile Satellite Networks (CSHCN TR 2001-11) by Iordanis Koutsopoulos, Leandros Tassiulas

In the near future, existing terrestrial radio networks are envisioned to integrate with satellite systems to provide global coverage. In order to enable communication for both non-hand-held and hand-held User Terminals (UTs), the radio link design must allow the UT to operate in full- and half-duplex mode respectively, where the latter is desirable when radiation power restrictions are imposed. In addition, sophisticated resource management and diversity provisioning will enhance system capacity and reliability. However, propagation delay caused by the satellite link may lead to inefficient resource allocation and problematic diversity provisioning.

In this paper, we address and study the resource allocation problem pertaining to a Medium-Earth-Orbit (MEO) satellite system with half-duplex communication capabilities. Such a system is characterized by large propagation delays, large intra-beam delay variations and inherently poor resource utilization.

We propose a channel classification scheme, where the available carriers are partitioned into classes and each class is associated with a certain range of propagation delays to the satellite. The suggested infrastructure results in higher channel utilization, reduced call blocking rate and efficient diversity provisioning and can be implemented with low signaling load.

Extending IP Services to Future Space Missions (CSHCN TR 2001-10) by Michael Hadjitheodosiou, Alex T. Nguyen

We outline the first steps of an effort to start defining the communication architecture for the next generation of space missions that will support NASA's "faster, better, cheaper" concept and will enable new types of collaborative science, where investigators can access their data from space "anytime, anywhere" via direct communication with the instruments on the spacecraft.

We discuss the building blocks for a conceptual design of a network architecture that could support and take advantage of IP-capable spacecraft.

We show that access from a large number of ground stations (that could be directly connected to the existing Internet infrastructure) could increase spacecraft availability time by a significant factor.

We discuss possible multiple access techniques that could enable the transition to an on-demand operation, where spacecraft share space spectrum dynamically. We can also discuss the particular requirements of a next generation of missions consisting of constellations of several small spacecraft and introduce a number of new complex network control, scheduling, routing, data management and communication problems that need to be addressed for this topology.

Routing Session Traffic in Fixed All-Wireless Networks under Energy and Bandwidth Limitations (CSHCN TR 2001-9) by Anastassios Michail and Anthony Ephremides

In this paper we study the effects of limited bandwidth resources in the development of energy-efficient routing algorithms for connection-oriented traffic in fixed wireless ad-hoc networks. A frequency division multiple access scheme is considered, in which nodes must schedule their transmissions by selecting frequency channels from a limited set in an interference-free fashion.

In our earlier work, we had developed a set of algorithms for determining end-to-end unicast paths based on link metrics. We argue that in order to address the effects of limited frequency resources, such algorithms must be coupled with channel allocation mechanisms for providing conflict free frequency assignments over selected routing paths.

To these ends, we propose a set of link metrics for selecting candidate routing paths and a set of heuristics for frequency allocation. We evaluate their performance using our detailed simulation model.

Energy-efficient Routing for Connection-Oriented Traffic in Wireless Ad-hoc Networks (CSHCN TR 2001-8) by Anastassios Michail and Anthony Ephremides

We address the problem of routing connection-oriented traffic in wireless ad-hoc networks with energy efficiency. We outline the trade-offs that arise by 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 captured by call blocking probability and average consumed energy. A detailed simulation model has been developed and used to evaluate the algorithms for a variety of networks.

Queue Dynamics of RED Gateways under Large Number of TCP Flows (CSHCN TR 2001-7) by Peerapol Tinnakornsrisuphap, Armand M. Makowski

We consider a stochastic model of a RED gateway under competing TCP-like sources sharing the capacity. As the number of competing flows becomes large, the queue behavior of RED can be described by a two-dimensional recursion. We confirm the result by simulations and discuss their implications for the network dimensioning problem.

Bounding On-Off Sources -- Variability Ordering and Majorization to the Rescue (CSHCN TR 2001-6) by Armand M. Makowski

We consider the problem of bounding the loss rates of the aggregation of on-off sources in a bufferless model by the loss rates associated with the aggregation of i.i.d. on-off sources. We use well-known results from the theory of variability orderings to establish a conjecture of Rasmussen et. al., a recent upper bound of Mao and Habibi, and to discuss a new conjectured upper bound by these authors.

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.

On a Random Sum Formula for the Busy Period of the M|G|Infinity Queue with Applications (CSHCN TR 2001-4) by Armand M. Makowski

A random sum formula is derived for the forward recurrence time associated with the busy period length of the M|G|infinity queue. This result is then used to (1) provide a necessary and sufficient condition for the subexponentiality of this forward recurrence time, and (2) establish a stochastic comparison in the convex increasing (variability) ordering between the busy periods in two M|G|infinity queues with service times comparable in the convex increasing ordering.

Optimal Cache Allocation Policies in Competitive Content Distribution Networks (CSHCN TR 2001-3) by Ozgur Ercetin, Leandros Tassiulas

Exponential expansion in network dimensionality and user traffic has created substantial traffic congestion on the Internet. This congestion causes increased delays perceived by the users while downloading web pages. Users have considerably short patience, and when they do not start receiving information in a short while, they stop browsing the requested web page.

As the commercial value of the Internet has become prevalent, the importance of keeping users at a site started to have direct translation into business value.

Proxy caching can alleviate problems caused by increased user traffic. In this paper, we consider the effects of real-world non-cooperative behavior of the network agents (servers and proxy caches) in overall network performance. Specifically, we consider a system where the proxy caches sell their caching space to the servers, and servers invest in these caches to provide lower latency to their users to keep them browsing their web pages and in turn to increase their revenues.

We determine optimal strategies of the agents that maximize their benefits. We show that such a system has an equilibrium point when no agent can increase its benefit by unilaterally updating its strategy. We show that under certain conditions this equilibrium leads to optimal cache allocation. We also show that an algorithm derived from this analysis is superior to currently implemented caching algorithms.

Optimization Based Rate Control for Multipath Sessions (CSHCN TR 2001-2) by Koushik Kar, Saswati Sarkar, Leandros Tassiulas

In this paper, we consider the rate control problem for multipath sessions with the objective of maximizing the total user (session) utility. This problem provides a framework in which flow control and routing are jointly optimized.

We consider two cases of this problem, and develop two different rate control algorithms for these two cases. The first algorithm is an end-to-end rate control algorithm which requires, on the part of the user, explicit knowledge of the paths that the user uses. The second algorithm is a hop-by-hop rate control algorithm which does not require the user to keep track of the paths it uses.

Both the algorithms are distributed and do not require the network to know the user utility functions. We analyze the convergence properties of these algorithms, and discuss how they can be implemented in a real network. Both of these algorithms are computationally simple, and have very low communication overhead.

Proximity Awareness and Ad Hoc Network Establishment in Bluetooth (CSHCN TR 2001-1) by Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas, Richard LaMaire

In recent years, wireless ad hoc networks have been a growing area of research. While there has been considerable research on the topic of routing in such networks, the topic of topology creation has not received due attention. This is because almost all ad hoc networks to date have been built on top of a single channel, broadcast-based wireless media, such as 802.11 or IR LANs. For such networks the distance relationship between the nodes implicitly (and uniquely) determines the topology of the ad hoc network.

Bluetooth is a promising new wireless technology that enables portable devices to form short-range wireless ad hoc networks and is based on a frequency hopping physical layer. This fact implies that hosts are not able to communicate unless they have previously discovered each other by synchronizing their frequency hopping patterns. Thus, even if all nodes are within direct communication range of each other, only those nodes which are synchronized with the transmitter can hear the transmission.

To support any-to-any communication, nodes must be synchronized so that the pairs of nodes (which can communicate with each other) together form a connected graph.

Using Bluetooth as an example, this paper first provides deeper insights into the issue to link establishment in frequency hopping wireless systems. It then introduces the Bluetooth Topology Costruction Protocol (BTCP), an asynchronous distributed protocol for constructing scatternets which starts with nodes that have no knowledge of their surroundings and terminates with the formation of a connected network satisfying all connectivity constraints posed by the Bluetooth technology.

To the best of our knowledge, the work presented in this paper is the first attempt at building Bluetooth scatternets using distributed logic and is quite "practical" in the sense that it can be implemented using the communication primitives offered by the Bluetooth 1.0 specifications.

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.

A Low-Overhead Rate Control Algorithm for Maximizing Aggregate Receiver Utility for Multirate Multicast Sessions (CSHCN TR 2000-18) by Koushik Kar, Saswati Sarkar, Leandros Tassiulas

In multirate multicasting, different users (receivers) within the same multicast group could receive service at different rates, depending on user requirements and network congestion level. Compared to unirate multicasting, this provides more flexibility to the user, and allows more efficient usage of network resources.

In this paper, we address the rate control problem for multirate multicast sessions, with the objective of maximizing the total receiver utility. This aggregate utility maximization problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives.

We propose an algorithm for this problem and show, through analysis and simulation, that it converges to the optimal rates.

In spite of the non-separability of the problem, the solution that we develop is completely decentralized, scalable and does not require the network to know the receiver utilities. Moreover, the algorithm requires very simple computations both for the user and the network, and also has very low overhead of network congestion feedback.

Bandwidth Calculation in a TDMA-based Ad Hoc Network (CSHCN TR 2000-17) by Chenxi Zhu, M. Scott Corson

Bandwidth calculation for Quality-of-Service (QoS) routing in an ad hoc network employing Time-Division-Multiple-Access (TDMA) is studied.

Certain constraints of TDMA transmission in a wireless network requires careful scheduling among the nodes in order to achieve conflict-free operations. These constraints also make the calculation of the end-to-end bandwidth along a path non-trivial. These calculations are essential for QoS routing which requires a certain amount of bandwidth available on a route.

We prove the problem of calculating the maximal end-to-end bandwidth along a given a path in a TDMA network is NP-complete, and develop an efficient bandwidth calculation scheme. We also show how the bandwidth calculation scheme can be used with the Ad-hoc On-demand Distance Vector protocol (AODV) to perform QoS routing.

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.

Integrating NASA Missions into the Internet using Commercial Satellite Constellations: Implementation of ATM-Based Cell-Relay Protocol Providing Support for Mission Integration (CSHCN TR 2000-9) by Sreenivas Ramaswamy

Near-earth spacecraft are considered to be very LEO satellites. The commercial constellations to be tested range from high-density LEOs to GEOs. We have presently developed a complete baseline simulation model that uses basic algorithms for all of the test parameters. We are working now on developing individual test modules for each parameter, which will then be plugged onto the baseline model and evaluated for each satellite system. The baseline model itself will be reinforced with the Opnet ATM suite to replace the current quasi-MAC protocol.

Following the successful implementation of basic algorithms for each of these test cases (shortest path routing, hard handoff, beacon monitoring, file transfer, deterministic packet transmission, single-priority FIFO queueing), we are currently working on replacing the MAC protocol with the ATM suite. The advantages of this approach are two-fold: first, it allows us greater flexibility in including multiple service classes, traffic types and priority schemes. Also it creates a well-defined network/switching layer upon which TCP/IP and UDP/IP can be evaluated.

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.

A Primal Algorithm for Optimization Based Rate Control for Unicast Sessions (CSHCN TR 2000-7) by Koushik Kar, Saswati Sarkar, Leandros Tassiulas

In this paper, we consider the rate control problem with the objective of maximizing the total user utility. It takes into account the possible differences in user requirements, and also provides a framework for achieving a wide range of fairness objectives.

We propose a simple algorithm for achieving the optimal rates for this problem. The algorithm can be implemented in a distributed way and does not require the network to know the user utility functions.

In our algorithm, the network communicates to the user the number of congested links on the user's path, and the user (end-host) adjusts its rate accordingly, taking into account its utility function and the network congestion feedback.

We show through analysis and experimentation that our algorithm converges to the optimum rates.

Optimization Based Rate Control for Multirate Multicast Sessions (CSHCN TR 2000-6) by Koushik Kar, Sasawati Sarkar, Leandros Tassiulas

Multirate multicasting, where the receivers of a multicast group can receive service at different rates, is an efficient mode of data delivery for many real-time applications.

In this paper, we address the problem of achieving rates that maximize the total receiver utility for multirate multicast sessions. This problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose two algorithms and prove that they converge to the optimal rates for this problem.

The algorithms are distributed and scalable, and do not require the network to know the receiver utilities. We discuss how these algorithms can be implemented in a real network, and also demonstrate their convergence through simulation experiments.

Bulk Data Multicast Rate Scheduling for Hybrid Heterogeneous Satellite-Terrestrial Networks (CSHCN TR 2000-5) by Apinun Tunpan, M. Scott Corson

We study a long-term, end-to-end rate scheduling problem of multicasting a large bulk file over a hybrid satellite-terrestrial network to a set of heterogeneous receivers. With selected receivers periodically reporting their long-term packet survival probabilities at each of the sender's transmission rates, our goal is to create a system which is both capable of trading off bandwidth consumption and receiver latency through a control parameter, and proactively maintaining a certain degree of reliable delivery. To increase bandwidth efficiency, we assume forward error correction (FEC) in the form of the Reed Solomon Erasure (RSE) coding. As an exact solution is computationally costly, we develop a rate scheduling algorithm based on a Gaussian approximation and study its performance by simulations.

WebView Materialization (CSHCN TR 2000-4) by Alexandros Labrinidis, Nicholas Roussopoulos

A WebView is a web page automatically created from base data typically stored in a DBMS. Given the multi-tiered architecture behind database-backed web servers, we have the option of materializing a WebView inside the DBMS, at the web server, or not at all, always computing it on the fly (virtual). Since WebViews must be up to date, materialized WebViews are immediately refreshed with every update on the base data.

In this paper we compare the three materialization policies (materialized inside the DBMS, materialized at the web server and virtual) analytically, through a detailed cost model, and quantitatively, through extensive experiments on an implemented system. Our results indicate that materializing at the web server is a more scalable solution and can facilitate an order of magnitude more users than the virtual and materialized inside the DBMS policies, even under high update workloads.

An Approach to Fixed/Mobile Converged Routing (CSHCN TR 2000-3) by M. Scott Corson, Alan O'Neill

We consider a family of routing protocols for networks in which the core topology is essentially fixed by where the end systems may be mobile. We refer to this form of routing as Fixed/Mobile Converged (FMC) routing.

This is a mixture of the traditional prefix-routed scenario fo the fixed Internet, and the classical edge mobility scenario that is today supported by cellular networks, primarily as part of the cellular technology elements (GSM, GPRS, etc.).

We outline a general architecture for the support of such edge mobility, and present an approach to FMC routing that fits within this architecture. We then present initial simulation results illustrating the potential scalability and routing efficiency of this approach.

Push-Based Information Delivery in Two Stage Satellite-Terrestrial Systems (CSHCN TR 2000-2) by Ozgur Ercetin, Leandros Tassiulas

Satellite broadcast data delivery has inherent advantages in providing global access to information to everyone. However, users of satellite communications need expensive and cumbersome equipment to receive and transmit satellite signals. Furthermore, as the amount of information being broadcast increases, average user latency increases as well. In many situations, users in a locality may have similar interests and hence they can be better served by a local broadcast schedule. A two stage satellite-terrestrial wireless broadcast system can provide more efficient service. In such a system, main server broadcasts information via satellite to the geographically distributed local ground stations. Every station has limited buffer capacity to store the items broadcast by the satellite. According to their cache content, and the interests of their users, local stations deliver the information to their users via terrestrial wireless channel. We develop novel methods for the joint cache management and scheduling problem encountered in these systems. Our results demonstrate that two stage systems can provide more efficient data delivery compared to the single stage systems.

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.