%0 Conference Paper
%B IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007
%D 2007
%T Caching in Mobile Environments: A New Analysis and the Mobile-Cache System
%A Frangiadakis,N.
%A Roussopoulos, Nick
%K Bandwidth
%K Broadcasting
%K cache storage
%K Cities and towns
%K FCC
%K hybrid push-pull solution
%K information dissemination
%K Intelligent networks
%K Land mobile radio
%K mobile communication
%K Mobile computing
%K mobile environment
%K mobile radio
%K mobile-cache system
%K multiple query answering
%K pull-push bandwidth ratio
%K Query processing
%K Road safety
%K road vehicles
%K ubiquitous wireless network
%K Vehicle safety
%X In the near future, we will be surrounded by ubiquitous wireless networks and so information dissemination for mobile users is a key issue. Hybrid push-pull constitutes a very effective and scalable solution. Our contribution is twofold. First we provide a new analysis that takes into account the user mobility. We argue that in a highly mobile setting, analysis and optimization goals discussed in past papers become irrelevant, since the most important aspect of the system is not delay, but rather the ability to answer as many queries as possible. As we show, the optimal pull-push bandwidth ratio depends on the mobility patterns of the users. Second, we use our findings to build Mobile-Cache, a system that can efficiently answer multiple queries over a wireless environment.
%B IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007
%I IEEE
%P 1 - 5
%8 2007/09/03/7
%@ 978-1-4244-1144-3
%G eng
%R 10.1109/PIMRC.2007.4394076
%0 Conference Paper
%B Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
%D 2005
%T Broadcasting on networks of workstations
%A Khuller, Samir
%A Kim,Yoo-Ah
%A Wan,Yung-Chun Justin
%K Approximation algorithms
%K Broadcasting
%K multicasting
%X Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message from one machine to another machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C time units. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of simultaneous communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending processor does not block for C time units when the message is in transit. Moreover, we assume that the messages are small and so the bottleneck is the latency.
%B Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
%S SPAA '05
%I ACM
%C New York, NY, USA
%P 279 - 288
%8 2005///
%@ 1-58113-986-1
%G eng
%U http://doi.acm.org/10.1145/1073970.1074017
%R 10.1145/1073970.1074017
%0 Journal Article
%J Operations Research Letters
%D 2004
%T Equivalence of two linear programming relaxations for broadcast scheduling
%A Khuller, Samir
%A Kim,Yoo-Ah
%K Approximation algorithms
%K Broadcasting
%K Linear programming
%K scheduling
%X A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.
%B Operations Research Letters
%V 32
%P 473 - 478
%8 2004/09//
%@ 0167-6377
%G eng
%U http://www.sciencedirect.com/science/article/pii/S016763770300169X
%N 5
%R 10.1016/j.orl.2003.11.012
%0 Conference Paper
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%D 2002
%T Dependent rounding in bipartite graphs
%A Gandhi,R.
%A Khuller, Samir
%A Parthasarathy,S.
%A Srinivasan, Aravind
%K Application software
%K Approximation algorithms
%K bipartite graph
%K bipartite graphs
%K broadcast channels
%K broadcast scheduling
%K Broadcasting
%K capacitated vertex cover
%K Character generation
%K computational complexity
%K Computer science
%K Delay
%K edge-sets
%K Educational institutions
%K fair scheduling
%K fractional vectors
%K graph theory
%K per-user fairness properties
%K pipage rounding technique
%K Processor scheduling
%K Random variables
%K random-graph models
%K randomized rounding approach
%K rounding method
%K scheduling
%K Scheduling algorithm
%K telecommunication computing
%K unrelated parallel machines
%X We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%I IEEE
%P 323 - 332
%8 2002///
%@ 0-7695-1822-2
%G eng
%R 10.1109/SFCS.2002.1181955
%0 Conference Paper
%B 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings
%D 2002
%T P5 : a protocol for scalable anonymous communication
%A Sherwood,R.
%A Bhattacharjee, Bobby
%A Srinivasan, Aravind
%K Broadcasting
%K communication efficiency
%K Computer science
%K cryptography
%K data privacy
%K Educational institutions
%K Internet
%K large anonymous groups
%K P5 protocol
%K packet-level simulations
%K Particle measurements
%K Peer to peer computing
%K peer-to-peer personal privacy protocol
%K privacy
%K Protocols
%K receiver anonymity
%K scalable anonymous communication
%K security of data
%K sender anonymity
%K sender-receiver anonymity
%K Size measurement
%K telecommunication security
%X We present a protocol for anonymous communication over the Internet. Our protocol, called P5 (peer-to-peer personal privacy protocol) provides sender-, receiver-, and sender-receiver anonymity. P5 is designed to be implemented over current Internet protocols, and does not require any special infrastructure support. A novel feature of P5 is that it allows individual participants to trade-off degree of anonymity for communication efficiency, and hence can be used to scalably implement large anonymous groups. We present a description of P5, an analysis of its anonymity and communication efficiency, and evaluate its performance using detailed packet-level simulations.
%B 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings
%I IEEE
%P 58 - 70
%8 2002///
%@ 0-7695-1543-6
%G eng
%R 10.1109/SECPRI.2002.1004362