TY - CONF
T1 - Caching in Mobile Environments: A New Analysis and the Mobile-Cache System
T2 - IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007
Y1 - 2007
A1 - Frangiadakis,N.
A1 - Roussopoulos, Nick
KW - Bandwidth
KW - Broadcasting
KW - cache storage
KW - Cities and towns
KW - FCC
KW - hybrid push-pull solution
KW - information dissemination
KW - Intelligent networks
KW - Land mobile radio
KW - mobile communication
KW - Mobile computing
KW - mobile environment
KW - mobile radio
KW - mobile-cache system
KW - multiple query answering
KW - pull-push bandwidth ratio
KW - Query processing
KW - Road safety
KW - road vehicles
KW - ubiquitous wireless network
KW - Vehicle safety
AB - 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.
JA - IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007
PB - IEEE
SN - 978-1-4244-1144-3
M3 - 10.1109/PIMRC.2007.4394076
ER -
TY - CONF
T1 - Broadcasting on networks of workstations
T2 - Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
Y1 - 2005
A1 - Khuller, Samir
A1 - Kim,Yoo-Ah
A1 - Wan,Yung-Chun Justin
KW - Approximation algorithms
KW - Broadcasting
KW - multicasting
AB - 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.
JA - Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
T3 - SPAA '05
PB - ACM
CY - New York, NY, USA
SN - 1-58113-986-1
UR - http://doi.acm.org/10.1145/1073970.1074017
M3 - 10.1145/1073970.1074017
ER -
TY - JOUR
T1 - Equivalence of two linear programming relaxations for broadcast scheduling
JF - Operations Research Letters
Y1 - 2004
A1 - Khuller, Samir
A1 - Kim,Yoo-Ah
KW - Approximation algorithms
KW - Broadcasting
KW - Linear programming
KW - scheduling
AB - 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.
VL - 32
SN - 0167-6377
UR - http://www.sciencedirect.com/science/article/pii/S016763770300169X
CP - 5
M3 - 10.1016/j.orl.2003.11.012
ER -
TY - CONF
T1 - Dependent rounding in bipartite graphs
T2 - The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
Y1 - 2002
A1 - Gandhi,R.
A1 - Khuller, Samir
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - Application software
KW - Approximation algorithms
KW - bipartite graph
KW - bipartite graphs
KW - broadcast channels
KW - broadcast scheduling
KW - Broadcasting
KW - capacitated vertex cover
KW - Character generation
KW - computational complexity
KW - Computer science
KW - Delay
KW - edge-sets
KW - Educational institutions
KW - fair scheduling
KW - fractional vectors
KW - graph theory
KW - per-user fairness properties
KW - pipage rounding technique
KW - Processor scheduling
KW - Random variables
KW - random-graph models
KW - randomized rounding approach
KW - rounding method
KW - scheduling
KW - Scheduling algorithm
KW - telecommunication computing
KW - unrelated parallel machines
AB - 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.
JA - The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
PB - IEEE
SN - 0-7695-1822-2
M3 - 10.1109/SFCS.2002.1181955
ER -
TY - CONF
T1 - P5 : a protocol for scalable anonymous communication
T2 - 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings
Y1 - 2002
A1 - Sherwood,R.
A1 - Bhattacharjee, Bobby
A1 - Srinivasan, Aravind
KW - Broadcasting
KW - communication efficiency
KW - Computer science
KW - cryptography
KW - data privacy
KW - Educational institutions
KW - Internet
KW - large anonymous groups
KW - P5 protocol
KW - packet-level simulations
KW - Particle measurements
KW - Peer to peer computing
KW - peer-to-peer personal privacy protocol
KW - privacy
KW - Protocols
KW - receiver anonymity
KW - scalable anonymous communication
KW - security of data
KW - sender anonymity
KW - sender-receiver anonymity
KW - Size measurement
KW - telecommunication security
AB - 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.
JA - 2002 IEEE Symposium on Security and Privacy, 2002. Proceedings
PB - IEEE
SN - 0-7695-1543-6
M3 - 10.1109/SECPRI.2002.1004362
ER -