Networking and Distributed Computing Papers

"On a simple deadlock recovery problem," Information Processing Letters, 16 (1983), 175-178.

A polynomial time algorithm is given for determining a minimum cost recovery from a deadlock situation resulting from a new request by a single task in a deadlock free system of tasks. The algorithm is obtained by reducing this deadlock recovery problem to a particular network flow problem.

"Minimal shared information for concurrent reading and writing", Proceedings 5th International Workshop on Distributed Algorithms (WDAG) (1991), LNCS 579, Editors: S. Toueg, P. Spirakis, and L. Kirousis (with P. Jayanti and A. Sethi), 212-228

While there have been many register construction algorithms in recent years, results establishing the intrinsic complexity of such constructions are scarce. In this paper, the minimum shared memory necessary to construct an atomic single-writer, single-reader, N-bit register A from single-writer, single-reader, single bit safe registers is established. Here, the write operation on A is wait-free, but the read operation is not. Constructions that match the lower bounds are also provided.

"On the Complexity of Link Scheduling in Multi-hop Radio Networks", in Proc. 26th Conference on Information Sciences and Systems, Princeton University, (1992), 491-495 (with S. Ramanathan)

The problem of efficiently scheduling the links of a multi-hop radio network is studied using a graph theoretic representation. The main result is an involved proof that link scheduling is NP-complete even when restricted to planar graphs. An alternative link scheduling algorithm to that described in the next reference is also given.

"Scheduling algorithms for multihop radio networks," IEEE/ACM Transactions on Networking, 1(1993), 166-177 (with S. Ramanathan) (Conference version: Proceedings of the 1992 ACM SIGCOMM Conference, 211-222)

New algorithms for transmission scheduling in multi-hop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. Theoretically, it is shown that tree networks can be scheduled optimally, and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree times optimum. Since the thickness is typically several orders of the magnitude less than the maximum node degree, the algorithms presented here represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.

Note: For this paper, S. Ramanathan received the Best Student Paper Award (for a paper authored or coauthored by a student).

"Efficient distributed algorithms for channel assignment in multihop radio networks," Journal of High Speed Networks, 2(1993), 405-423 (with R. Ramanathan)

In this paper, efficient distributed algorithms for link and broadcast scheduling are provided. These algorithms require the transmission of only O(v log v + ke) unit-length messages in the worst case (k is a network dependent constant). Further, no message requires more than two hops. In the worst case, these algorithms have a performance that is comparable to the performance of the centralized algorithms that are described in the paper just prior to this one. Experimentally, these distributed algorithms have performance that is only slightly worse than that of the best centralized methods. And, the performance is roughly 7 to 10% better than that of methods other than those noted above. Further, these algorithms are parameterized in a way that allows for the selection of a tradeoff between the number of (distributed) passes over the network by the scheduling algorithm and the quality of the schedule that is produced. Finally, the distributed algorithms that are given here are not only efficient, but are quite easy to implement. This is in sharp contrast to certain of the centralized algorithms.

"Experimental results on broadcast scheduling in radio networks," Proceedings of 1st AdvancedTelecommunications Information Distribution Research Program Conference (ATIRP) (1997) (with X. Ma ), 325-329.

In this paper we describe an experimental study of algorithms for broadcast scheduling in multi-hop radio networks. These algorithms include earlier methods, as well as three new algorithms. These new algorithms are aimed at avoiding the sandwich effect that causes larger than desirable schedules in earlier methods. Our experimental results establish that each of the three algorithms that we introduce outperforms the earlier methods by a significant degree, with schedules that are experimentally close to the optimal.

"An incremental algorithm for broadcast scheduling in packet radio networks," Proceedings of MILCOM 98 (1998) (with X. Ma), 5 pages on CD-ROM. A preliminary version appeared in: "Practical adaptive algorithms for channel assignment in multihop packet radio networks," Proceedings of 2nd Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (1998) (with X. Ma), 60-64.

Packet radio networks hold great promise for providing easy to use, mobile military communications services. However, supporting mobility with packet radio networks poses many technical challenges. One of these challenges, to dynamically and quickly adjust schedules for fixed channel access by way of TDMA/FDMA/CDMA in a large dynamic network, is the focus of this paper. In such broadcast scheduling it is required that the transmission of a given station be received collision free by all of the stations that are within its transmission range. The goal in broadcast scheduling is to produce a conflict free static schedule of minimum length in which each station is given a chance, a time slot in TDMA for example, to broadcast its packets. Unfortunately, all of the existing broadcast scheduling algorithms are off-line. As such, whenever a change occurs in the topology of the network, these algorithms recompute the schedule for the entire network. As radio networks evolve in the direction of thousands of stations spread over a broad geographical area and operating in an unpredictable dynamic environment (imagine a battlefield) the cost of full schedule recomputation whenever the network topology changes (by even a single node) is unacceptable. In this situation, incremental algorithms are needed. Such algorithms accommodate topological changes by adapting the existing schedule, rather than rebuilding the schedule from scratch. The twin objectives of incremental algorithms are much faster execution (than an off-line algorithm) and the production of a high quality schedule. In this paper we establish the feasibility of simultaneously meeting these twin objectives, by presenting an incremental algorithm for broadcast scheduling.

"A distributed protocol for adaptive broadcast scheduling in packet radio networks," Workshop record of the 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications ACM/IEEE (DIAL M for Mobility), 1998 (with X. Ma), 10 pages. Also appeared as "Distributed broadcast scheduling," Proceedings of 3rd Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (1999) (with X. Ma), 115-119.

A fully distributed protocol for adaptive broadcast scheduling in multi-hop packet radio networks is presented. This method requires neither a central computing site nor individual stations to maintain global information other than that of a global clock. A station determines its actions solely on information that concerns the transmission status of its one-hop and two-hop neighbors. This fact allows a fully distributed implementation (the first such for broadcast scheduling), and makes the method highly adaptive. The protocol that we describe is comprehensive in: having each station determine its own slot(s) in the schedule; allowing multiple stations to simultaneously run the scheduler portion of the protocol; allowing stations in non local portions of the network to remain operating even while other stations are joining or leaving the network; allowing stations to utilize otherwise empty slots; and, from a theoretical viewpoint, having a constant competitive ratio.

"Throughput/Delay of Broadcast Scheduling in Multihop Packet Radio Networks ," Proceedings of the 4th Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (2000), 239-244, (with X. Ma).

The most frequently used medium access method in one hop packet radio networks (PRNs) is that of random access (such as slotted ALOHA). Here, stations transmit without mutual coordination, and if a collision occurs, then stations retransmit. An alternative to random access is scheduling access to the channel so that collisions among transmissions are guaranteed to not occur. While a variety of papers have studied this broadcast scheduling approach, the tradeoffs between the advantage of no collisions and the disadvantage of limited transmissions have remained essentially unexplored. In this paper, we take an embedded Markov-chain approach in determining the steady state throughput-delay characteristics for broadcast scheduling and for an ALOHA based random access method (M-ALOHA) that is adapted for use in a broadcast multihop PRN. Comparing the analyses establishes that at the individual node level, broadcast scheduling has superior throughput and delay performance than does M-ALOHA.

"Adaptive Algorithms for Broadcast Scheduling in Multihop Packet Radio Networks," Submitted to IEEE/ACM Transactions on Networking (with X. Ma).

For multi-hop packet radio networks, all existing broadcast scheduling algorithms are off-line algorithms, and as such, they require a priori knowledge about the topology of the entire network. However, radio networks are evolving in the direction of hundreds or even thousands of stations spread over a broad geographical area and operating in an unpredicatable dynamic environment. In this situation, adaptive algorithms are needed. Such algorithms provide rapid schedule updates whenever the network changes due to stations joining or leaving. In this paper, we present four adaptive algorithms for broadcast scheduling. We show that our algorithms are theoretically strong, having constant approximation factors and very good running times. Significantly, experiments establish that the algorithms produce schedules only slighter weaker than those of the best off-line algorithms.

"Evaluation of a Distributed Broadcast Scheduling Protocol for Multihop Radio Networks," Proceedings of MILCOM 2001 (with X. Ma), 5 pages on CD-ROM.

Although broadcast scheduling has been widely studied in packet radio networks (PRNs) the first fully distributed algorithm (FDAS) was developed only recently. In FDAS: 1) No global information is required, either in central or individual sites. Rather, a station schedules itself after collecting information from it's one-hop and two-hop neighbors. and, 2) The method is fully distributed. Thus, multiple stations can simultaneously run the scheduler portion of the protocol, and stations in non local portions of the network can transmit normally even while stations are joining or leaving the network. In this paper we analyze the performance of FDAS relative to non-distributed broadcast scheduling algorithms and to an ALOHA based channel access method. Both analytical and simulation results are presented. The analyses establish that FDAS has superior throughput and medium access delay performance at both the node and system levels. This fact makes FDAS especially appealing for military situations where communication can be guaranteed even under very heavy loads and where the network configuration is dynamically changing.

"A Distributed Protocol For Adaptive Link Scheduling in Ad-hoc Networks," Proceedings IASTED International Conference on Wireless and Optical Communications (WOC2001) (2001), 43-48, (With R. Liu).

A fully distributed protocol for adaptive link scheduling in multi-hop packet radio networks (PRN) is presented. The distributed and adaptive nature of PRNs makes any centralized algorithms inappropriate in practice. In this protocol, there is no global information (except for synchronized time) required at any station. Incremental changes in the network topology are handled locally without involving or affecting stations that are geographically removed from the change. The performance of the protocol is evaluated by using experimental techniques.

"Algorithmic aspects of topology control problems for ad hoc networks," Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2002), 123-134 (with M. Marathe, R. Ramanathan, S.S. Ravi, and R. Liu).

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

"Analysis of Queuing Delay in Multimedia Gateway Call Routing," Proceedings of the Third International Conference on Internet Computing (IC2002) (2002), 193-198 (with Q. Huang). PDF version

The recent emergence of multimedia applications has led to the deployment of various telecommunication technologies (e.g. IP, wireless) in addition to traditional PSTN (Public Switched Telephone Network) circuit switched networks. In this heterogeneous telecommunication world, users make calls without regard to the fact that the originating network may differ from the terminating network, and the call may be routed through one or more intermediate networks. For instance, users from two different PSTN networks may communicate through an IP network using Voice over IP (VoIP) technology. In this framework, multimedia gateways perform call routing, call signaling conversions and media format conversions among different networks. This paper investigates algorithms and queuing delays on multimedia gateways in regard to call routing aimed at minimizing the expected call delay. Both centralized and distributed queuing models are considered, and performance measures are derived.

"Broadcast scheduling for TDMA in Wireless Multi-Hop Networks," Handbook of Wireless Networks and Mobile Computing, Ivan Stojmenovic, Editor, John Wiley and Sons, Inc. (2002), 347-370.

In wireless multi-hop networks, broadcast scheduling by way of TDMA is an effective approach to making use of the limited channel bandwidth. This chapter explores the computational and algorithmic complexity of broadcast scheduling. Since the problem is NP-complete, even for restricted classes of networks, the emphasis is on the development of approximation algorithms, including bounds on the quality of the schedules produced by those algorithms. Both off-line and adaptive approaches, and centralized and distributed algorithms, are described. A brief overview is given of related topics including experimental results, link scheduling, additional graph models, and a unified scheduling framework.

"Performance analysis of cost optimization algorithms in multimedia gateway call routing," Conference on Design, Analysis, and Simulation of Distributed Systems (DASD 2003), 2003, 147-154 (with Q. Huang). .doc version

Multimedia gateways are a recently emerged next generation telecommunication product that provides real-time, multi-way communications among different media networks, such as Public Switched Telephone Networks (PSTN), IP networks and wireless networks. When a call arrives at a multimedia gateway from a local media network, that gateway must route the call to one of the non-local media networks to reach the destination. In additional to call delay, which is measured by delay cost, calls routed to different media incur varying media cost. This paper investigates algorithms on multimedia gateways in regard to call routing aimed at minimizing the expected routing cost, which is the media cost plus the delay cost. We assume that calls have Poisson arrival rate and exponentially distributed length. Both centralized and distributed queuing models are considered, and performance measures are derived.