Guest Editorial

Mobile Networks and Applications -     

Scheduling Techniques for Media-on-Demand

Broadcasting popular media to clients is the ultimate scalable solution for media-on-demand. Recently, it was shown that if clients can receive data at a rate faster than what they need for playback and if they can store later parts of the media in their buffers, then much higher scalability may be obtained. This paper addresses scheduling problems arising from these new systems for media-on-demand. For given amount of bandwidth, we reduce the maximal start-up delay time for an uninterrupted playback. We achieve our results by introducing two techniques. In the first, the media is arranged on the channels such that clients gain from buffering later parts of the transmission before the actual start of the playback. In the second, segments of different media may be mixed together on the same channel. We introduce a simple class of recursive round-robin scheduling algorithms that implement both techniques. Our results improve the best known asymptotic results. Moreover, our scheduling algorithms outperform known results for practical values for number of media and number of broadcasting channels. For some specific small values, we present solutions that are better than those achieved by our algorithms. Finally, we show that our techniques are useful for models in which clients may not receive data from all the channels, and are applicable to media with different lengths and popularities. A preliminary version appeared in the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 791–800, 2003. Work of R.E. Ladner was partially supported by NSF grant No. CCR-0098012. Work of T. Tamir done while the author was at the University of Washington.     

Online Dynamic Programming Speedups

Consider the dynamic program h(n)=min _1≤j≤n a(n,j), where a(n,j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i<n. The goal is to compute all h(n), for 1≤n≤N. It is well known that, if a(n,j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195–208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm. In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n=1,2,…,N when (i) we do not know the values of a(n′,j) for n′>n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n,j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n,j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. The research of the first author was partially supported by the NSF program award CNS-0626606; the research of the second and third authors was partially supported by Hong Kong RGC CERG grant HKUST6312/04E.     

Competitive On-Line Switching Policies

Consider the following problem. A switch connecting n input channels to a single output channel must deliver all incoming messages through this channel. Messages are composed of packets , and in each time slot the switch can deliver a single packet from one of the input queues to the output channel. In order to prevent packet loss, a buffer is maintained for each input channel. The goal of a switching policy is to minimize the maximum buffer size. The setting is on-line; decisions must be made based on the current state without knowledge of future events. This general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. Traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or assuming that the service rate is at least the aggregate of all the input rates. We use competitive analysis, avoiding any prior assumptions on the input. We show O(log n )-competitive switching policies for the problem and demonstrate matching lower bounds.     

Consensus algorithms with one-bit messages

Three main parameters characterize the efficiency of algorithms that solve the Consensus Problem: the ratio between the total number of processors and the maximum number of faulty processors (n andt, respectively), the number of rounds, and the upper bound on the size of any message. In this paper we present a trade-off between the number of faulty processors and the number of rounds by exhibiting a family of algorithms in which processors communicate by one-bit messages. Letk be a positive integer and lets=t ^1/k . The family includes algorithms where the number of processors is less than , and the number of rounds is less than . This family is based on a very simple algorithm with the following complexity: (2t+1)(t+1) processors,t+1 rounds, and one-bit message size. Amotz Bar-Noy received the B.A. degree in mathematics and computer science in 1981, and the Ph.D. degree in computer science in 1987, both from the Hebrew University of Jerusalem, Israel. He was a post-doctoral fellow at Stanford University, California, from October 1987 to September 1989. Since October 1989 he has been a visiting scientist at IBM T.J. Watson Research Center, Yorktown Heights, New York. His research interests include communication networks, distributed algorithms, parallel algorithms and fault-tolerant computing. Danny Dolev received a B.Sc. in physics from the Hebrew University, Jerusalem, in 1971, an M.Sc. in applied mathematics from the Weizmann Institute of Science, Israel, in 1973, and Ph.D. in computer science in 1979. After two years as a post doctoral fellow at Stanford and a year as a visiting scientist at IBM, he joined the Hebrew University, Jerusalem, in 1982, and IBM Almaden Research Center at 1987. His major research interests are distributed computing, reliability of distributed systems, and algorithms.A preliminary version of this paper appeared in the Aegean Workshop on Computing (AWOC), pp 380–390, 1988. This work was carried out while Dr. Bar-Noy was visiting Stanford University. Supported in part by a Weizmann fellowship, by contract ONR N00014-88-K-0166, and by a grant of Stanford's Center for Integrated Systems     

Approximate distributed Bellman-Ford algorithms

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (<3). We call these algorithms approximate DBF algorithms. The modifications proposed to the original algorithm are very simple and easy to implement. The message complexity of the first algorithm, called the multiplicative approximate DBF, is O(nmlog(nΔ)) where Δ is the maximum length over all edges of an n-nodes m-edges network. The message complexity of the second algorithm, called the additive approximate DBF, is O(δ/Δ nm) where δ is the minimum length over all edges in the network     

Tracking mobile users in wireless communications networks

Tracking strategies for mobile wireless networks are studied. A cellular architecture in which base stations that are interconnected by a wired network communicate with mobile units via wireless links is assumed. The cost of utilizing the wireless links for the actual tracking of mobile users is considered. A tracking strategy in which a subset of all base stations is selected and designed as reporting centers is proposed. Mobile users transmit update messages only upon entering cells of reporting centers, while every search for a mobile user is restricted to the vicinity of the reporting center to which the user last reported. It is shown that, for an arbitrary topology of the cellular network (represented by the mobility graph), finding an optimal set of reporting centers is an NP-complete problem. Optimal and near-optimal solutions for important special cases of the mobility graph are presented     

Pushing Dependent Data in Clients–Providers–Servers Systems

In satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by many clients. The providers are independent and therefore files may share information. The clients who access these files may have different patterns of access. Some clients may wish to access more than one file at a time in any order, some clients may access one file out of of several files, and some clients may wish to access a second file only after accessing another file. The goal of the server is to order the files in a way that minimizes the access time of the clients given some a-priori knowledge of their access patterns. This paper introduces a clients–providers–servers model that better represents certain environments than the traditional clients–servers model. Then, we show that a random order of the data files performs well, independent of the specific access pattern. Our main technical contribution is de-randomizing the procedure that is based on selecting a random order. The resulting algorithm is a polynomial-time deterministic algorithm that finds an order with the same performance bounds as those of the random order.     

One-bit algorithms

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two problems. The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube). The second problem is coloring a synchronous ring with three colors. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. Amotz Bar-Noy received his B.Sc. degree in Mathematics and Computer Science in 1981, and his Ph.D. degree in Computer Science in 1987, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1989 he was a post-doctoral fellow in the Department of Computer Science at Stanford University. He is currently a visiting scientist at the IBM Thomas J. Watson Research Center. His current research interests include the theoretical aspects of distributed and parallel computing, computational complexity and combinatorial optimization. Joseph (Seffi) Naor received his B.A. degree in Computer Science in 1981 from the Technion, Israel Institute of Technology. He received his M.Sc. in 1983 and Ph.D. in 1987 in Computer Science, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1988 he was a post-doctoral fellow at the University of Southern California, Los Angeles, CA. Since 1988 he has been a post-doctoral fellow in the Department of Computer Science at Stanford University. His research interests include combinatorial optimization, randomized algorithms, computational complexity and the theoretical aspects of parallel and distributed computing. Moni Naor received his B.A. in Computer Science from the Technion, Israel Institute of Technology, in 1985, and his Ph.D. in Computer Science from the University of California at Berkeley in 1989. He is currently a visiting scientist at the IBM Almaden Research Center. His research interests include computational complexity, data structures, cryptography, and parallel and distributed computation.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731Supported by contract ONR N00014-88-K-0166 and by a grant from Stanford's Center for Integrated Systems. This work was done while the author was a post-doctoral fellow at the University of Southern California, Los Angeles, CAThis work was done while the author was with the Computer Science Division, University of California at Berkeley, and Supported by NSF grant DCR 85-13926     

Broadcast Disks with Polynomial Cost Functions

In broadcast disks systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. Broadcast disks systems are particularly attractive in settings where the potential customers have a highly-asymmetric communication capabilities, i.e., receiving is significantly cheaper than transmitting. This is the case with satellite networks, mobile hosts in wireless networks, and Teletext system.The fundamental algorithmic problem for such systems is to determine the broadcast schedule based on the demand probability of items, and the cost incurred to the system by clients waiting. The goal is to minimize the mean access cost of a random client. Typically, it was assumed that the access cost is proportional to the waiting time. In this paper, we ask what are the best broadcast schedules for access costs which are arbitrary polynomials in the waiting time. These may serve as reasonable representations of reality in many cases, where the patience of a client is not necessarily proportional to its waiting time.We present an asymptotically optimal algorithm for a fractional model, where the bandwidth may be divided to allow for fractional concurrent broadcasting. This algorithm, besides being justified in its own right, also serves as a lower bound against which we test known discrete algorithms. We show that the Greedy algorithm has the best performance in most cases. Then we show that the performance of other algorithms deteriorate exponentially with the degree of the cost polynomial and approaches the fractional solution for sub-linear cost. Finally, we study the quality of approximating the greedy schedule by a finite schedule.