Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Tassiulas, LeandrosSubject: search.filters.subject.algorithms

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Push-Based Information Delivery in Two Stage Satellite-Terrestrial Systems
    (2000) Ercetin, Ozgur; Tassiulas, Leandros; ISR; CSHCN
    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.
  • Thumbnail Image
    Item
    Fair Allocation of Discrete Bandwidth Layers in Multicast Networks
    (1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR
    We study fairness when receivers in a multicast network can not subscribeto fractional layers. This case arises whenthe source hierarchically encodes its signal and the hierarchical structureis predetermined. Unlike the case of the fractional layer allocation,which has been studied extensively in a previous work, bandwidth canbe allocated in discrete chunks only. Fairness issues becomevastly different. Computation of lexicographically optimal rateallocation becomes NP-hard in this case, while lexicographicallyoptimal rate allocation is polynomial complexity computablewhen fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case.We introducea new notion of fairness, maximal fairness.We propose a polynomialcomplexity algorithm for computation of maximally fair ratesallocated to various source-destination pairs. Even though, maximal fairnessis a weaker notion of fairness, itcoincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. So the algorithmfor computing maximally fair rate allocation computes maxmin fairrate allocation, when the latter exists.
  • Thumbnail Image
    Item
    Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees
    (1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR
    We study fairness in arbitrary networks with multicast capabilities.Multicast traffic in internet and ATM provides a motivationfor studying these networks. A study of fairness in multicastnetworks poses several interesting problems e.g., the issueof {it intra-session} fairness in addition to thatof {it inter-session} fairness in unicastnetworks. We develop a mathematical frameworkto model the fair allocation of bandwidth in multicast networkswith minimum and maximum rate constraints. We presentdistributed algorithms for computation of maxmin fair ratesallocated to various source-destination pairs.