Technical Reports

Thesis Papers

Authors Featured on this Page:

P. Bhagwat

O. Ercetin

K. Kar

I. Koutsopoulos

R. LaMaire

T. Salonidis

S. Sarkar

L. Tassiulas

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.

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.

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 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.

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.

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.

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.