A. Graph-with-ve-clients and V. , i}, two possible locations H = {s, j} and two types of servers for each location. b) The modied graph where each link represents the round-trip minimum cost routes, satisfying the delay constraint between a client and a possible location. Cost functions f s (s) and f j (y) of the possible locations. c) The resulting graph. Servers have been placed at the appropriate locations, p.109

C. Adjih, E. Baccelli, T. Clausen, P. Jacquet, and G. Rodolakis, Fish eye OLSR scaling properties, Special Issue on Mobile Ad Hoc Wireless Networks, 2004.
DOI : 10.1109/JCN.2004.6596835

URL : https://hal.archives-ouvertes.fr/hal-00654544

G. Rodolakis, S. Siachalou, and L. Georgiadis, Replicated server placement with QoS constraints, IEEE Transactions on Parallel and Distributed Systems, vol.17, issue.10, 2006.
DOI : 10.1007/978-3-540-30573-6_16

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1048

P. Jacquet, A. M. Naimi, and G. Rodolakis, Routing on asymptotic delays in IEEE 802.11 wireless ad hoc networks, First Workshop on Resource Allocation in Wireless NETworks, 2005.

P. Jacquet and G. Rodolakis, Multicast Scaling Properties in Massively Dense Ad Hoc Networks, 11th International Conference on Parallel and Distributed Systems (ICPADS'05), 2005.
DOI : 10.1109/ICPADS.2005.201

G. Rodolakis and P. Jacquet, An analytical evaluation of autocorrelations in TCP trac, AINTEC, 2005.

G. Rodolakis, S. Siachalou, and L. Georgiadis, Replicated server placement with QoS constraints, 3rd International Workshop on QoS in Multiservice IP Networks, 2005.
DOI : 10.1007/978-3-540-30573-6_16

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1048

C. Adjih, P. Jacquet, G. Rodolakis, and N. Vvedenskaya, Performance of multiple TCP ows: an analytical approach, INRIA research report RR-5417, 2004.

P. Jacquet, A. M. Naimi, and G. Rodolakis, Asymptotic Delay Analysis for Cross-Layer Delay-Based Routing in Ad Hoc Networks, Advances in Multimedia, vol.2007
DOI : 10.1109/TWC.2003.814353

G. Rodolakis, A. M. Naimi, and A. Laouiti, Multicast overlay spanning tree protocol for ad hoc networks, under submission

G. Rodolakis, S. Siachalou, and L. Georgiadis, Replicated server placement with QoS constraints
DOI : 10.1007/978-3-540-30573-6_16

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1048

C. Adjih, L. Georgiadis, P. Jacquet, and W. Szpankowski, Is the Internet fractal: The multicast power law revisited, SODA, 2002.
URL : https://hal.archives-ouvertes.fr/inria-00072466

C. Adjih, P. Jacquet, and L. Viennot, Computing connected dominating set with multipoint relays, 2002.

C. Adjih, P. Jacquet, and N. Vvedenskaya, Performance evaluation of a single queue under multi-user TCP, 2002.
URL : https://hal.archives-ouvertes.fr/inria-00072110

R. Andonov and S. Rajopadhye, A sparse knapsack algo-tech-cuit and its synthesis, Proceedings of IEEE International Conference on Application Specific Array Processors (ASSAP'94), 1994.
DOI : 10.1109/ASAP.1994.331794

URL : https://hal.archives-ouvertes.fr/inria-00074411

S. Arora-arya, N. Garg, R. Khandekar, K. Munagala, and V. Pandit, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems Local search heuristics for k-median and facility location problems, Proceedings of the 33rd ACM Symposium on Theory of Computing, pp.753782-2129, 1998.

F. Baccelli, K. Tchoumatchenko, and S. Zuyev, Markov paths on the Poisson- Delaunay graph with applications to routing in mobile networks, Adv. Appl. Probab, vol.32, issue.1, p.118, 2000.
URL : https://hal.archives-ouvertes.fr/inria-00073269

H. Badis and K. Agha, Quality of service for ad hoc optimized link state routing protocol (QOLSR), internet draft, 2006.

H. Badis, A. Munaretto, K. Agha, and G. Pujolle, Optimal path selection in a link state QoS routing protocol, 2004 IEEE 59th Vehicular Technology Conference. VTC 2004-Spring (IEEE Cat. No.04CH37514), 2004.
DOI : 10.1109/VETECS.2004.1391386

D. Bertsimas and G. Van-ryzin, An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability, Operations Research Letters, vol.9, issue.4, p.223231, 1990.
DOI : 10.1016/0167-6377(90)90066-E

G. Bianchi, Perfomance analysis of the IEEE802.11 distributed coordination function, IEEE journal on selected areas in Communcations, vol.18, issue.3, 2000.

A. Broido, E. Basic, and K. C. Clay, Invariance of the Internet RTT spectrum. global RTT analysis, 2002.

T. Bu and D. Towsley, On distinguishing between Internet power law topology generators, INFOCOM, 2002.

Y. Chen, R. Katz, and J. Kubiatowicz, Dynamic Replica Placement for Scalable Content Delivery, First International Workshop on Peer-to-Peer Systems, p.306318, 2002.
DOI : 10.1007/3-540-45748-8_29

Y. Chen, R. Katz, and J. Kubiatowicz, SCAN: A dynamic scalable and ecient content distribution network, First International Conference on Pervasive Computing, 2002.

J. C. , -. Chuang, and M. A. Sirbu, Pricing multicast communication: A cost-based approach, Telecommunication Systems, vol.17, issue.3, p.281297, 2001.

F. Chudak and D. Shmoys, Improved Approximation Algorithms for the Uncapacitated Facility Location Problem, SIAM Journal on Computing, vol.33, issue.1, p.125, 2003.
DOI : 10.1137/S0097539703405754

F. Chudak and D. Williamson, Improved approximation algorithms for capacitated facility location problems, Integer Programming and Combinatorial Optimization, 1999.

T. Clausen, Combining temporal and spatial partial topology for manet routing merging OLSR and FSR, WPMC, 2003.

E. Cohen and S. Shenker, Replictation strategies in unstructured peer-to-peer networks, ACM SIGCOMM, 2002.

C. Cordeiro, H. Gossain, and D. Agrawal, Multicast over wireless mobile ad hoc networks: present and future directions, IEEE Network, vol.17, issue.1, 2003.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2001.

S. Corson and J. Macker, Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations, RFC 2501, 1999.

M. De-berg, O. Schwarzkoph, M. Van-kreveld, and M. Overmars, Computional Geometry: Algorithms and Applications, 2000.

D. Z. Du and F. K. Hwang, A proof of Gilbert-Pollak's conjecture on the steiner ratio, Algorithmica, vol.45, p.121135, 1992.

R. Braden, Requirements for Internet hosts -communication layers, RFC 1122, 1989.

K. Fall and K. Varadhan, The ns manual

W. Fenner, Internet Group Management Protocol, 1997.

D. R. Figueiredo, B. Liu, V. Misra, and D. Towsley, On the autocorrelation structure of TCP trac, 2002.

P. Flajolet, X. Gourdon, and P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoretical Computer Science, vol.144, issue.1-2, p.358, 1995.
DOI : 10.1016/0304-3975(95)00002-E

URL : https://hal.archives-ouvertes.fr/inria-00074307

P. Flajolet and A. M. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math, vol.3, p.216240, 1990.
URL : https://hal.archives-ouvertes.fr/inria-00075725

P. Flajolet and R. Sedgewick, Analytic combinatorics
DOI : 10.1017/CBO9780511801655

URL : https://hal.archives-ouvertes.fr/inria-00072739

S. Floyd and T. Henderson, The NewReno modication to TCP's fast recovery algorithm, RFC 2582, 1999.

K. Fukuda, H. Takayasu, M. Takayasu, J. Garcia-luna-aceves, and E. L. Madruga, Origin of critical behavior in ethernet trac The core-assisted mesh protocol, Physica A Journal on Selected Areas in Communications, issue.8, p.1713801294, 1999.

M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory on NP-Completeness, W. H. FREEMAN AND COMPANY, 1979.

M. Gerla, X. Hong, and G. Pei, Fisheye state routing protocol (FSR) for ad hoc networks, 2002.

R. Guerin and A. Orda, QoS based routing in networks with inaccurate information: theory and algorithms, Proceedings of INFOCOM '97, p.350364, 1999.
DOI : 10.1109/INFCOM.1997.635116

P. Gupta and P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, p.46388404, 2000.
DOI : 10.1109/18.825799

M. T. Hajiaghavi, M. Mahdian, and V. S. Mirrokni, The facility location problem with general cost functions, Networks, vol.42, issue.1, p.4247, 2003.

R. Hassin, Approximation Schemes for the Restricted Shortest Path Problem, Mathematics of Operations Research, vol.17, issue.1, p.3642, 1992.
DOI : 10.1287/moor.17.1.36

V. Jacobson, Congestion avoidance and control, ACM SIGCOMM, 1988.

V. Jacobson, R. Braden, and D. Borman, TCP extensions for high performance, RFC 1323, 1992.

P. Jacquet, Eléments de théorie analytique de l'information, modélisation et évaluation de performances, INRIA research report RR-3505, 1998.

P. Jacquet, Geometry of information propagation in massively dense ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing , MobiHoc '04, 2004.
DOI : 10.1145/989459.989479

URL : https://hal.archives-ouvertes.fr/inria-00071586

P. Jacquet, A. Laouiti, P. Minet, and L. Viennot, Performance analysis of OLSR multipoint relay ooding in two ad hoc wireless network models, RSRCP, Special issue on Mobility and Internet, 2001.

P. Jacquet, A. Laouiti, P. Minet, and L. Viennot, Performance evaluation of multipoint relaying in mobile ad hoc networks, Networking, 2002.

K. Jain and V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, vol.48, issue.2, p.274296, 2001.
DOI : 10.1145/375827.375845

S. Jamin, C. Jiu, A. Kurc, D. Raz, and Y. Shavitt, Constrained mirror placement on the Internet, Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213), p.3140, 2001.
DOI : 10.1109/INFCOM.2001.916684

J. Jetcheva and D. B. Johnson, Adaptive demand-driven multicast routing in multihop wireless ad hoc networks, Proceedings of the Second Symposium on Mobile Ad Hoc Networking and Computing, 2001.

X. Jia, X. Hu, D. Li, W. Wu, and D. Du, Placement of Web-Server Proxies with Consideration of Read and Update Operations on the Internet, The Computer Journal, vol.46, issue.4, 2003.
DOI : 10.1093/comjnl/46.4.378

X. Jia, D. Li, X. Hu, and D. Du, Optimal placement of proxies of replicated Web servers in the Internet, Proceedings of the First International Conference on Web Information Systems Engineering, p.329339, 2001.
DOI : 10.1109/WISE.2000.882375

H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, 2004.
DOI : 10.1007/978-3-540-24777-7

M. Korupolu, C. Plaxton, and R. Rajaraman, Analysis of a Local Search Heuristic for Facility Location Problems, Journal of Algorithms, vol.37, issue.1, p.146188, 2000.
DOI : 10.1006/jagm.2000.1100

R. Krishnan, D. Raz, and Y. Shavitt, The cache location problem, IEEE/ACM Transactions on Networking, vol.8, issue.5, p.568582, 2000.
DOI : 10.1109/90.879344

A. Laouiti, A. Qayyum, and L. Viennot, Multipoint relaying: An ecient technique for ooding in mobile wireless networks, 35th Annual Hawaii International Conference on System Sciences, 2001.

S. Lee, W. Su, and M. Gerla, On demand multicast routing protocol in multihop wireless mobile networks, Baltzer Mobile Networks and Applications, special issue on Multipoint Communication in Wireless Mobile Networks, 2000.

W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, On the selfsimilar nature of ethernet trac (extended version), IEEE/ACM Transactions on Networking, vol.2, issue.1, p.115, 1994.

B. Li, M. Golin, G. Italiano, and X. Deng, On the optimal placement of web proxies in the Internet, IEEE INFOCOM, 1999.

D. H. Lorenz and D. Raz, A simple ecient approximation scheme for the restricted shortest path problem, Operations Research Letters, vol.28, issue.5, p.213221, 2001.

M. Mahdian, E. Markakis, A. Saberi, and V. Varizani, Greedy facility location algorithms analyzed using dual tting with factor-revealing LP, Journal of the ACM, vol.50, issue.6, p.795824, 2003.

A. Median, A. Lakhina, I. Matta, J. Byers, R. Metcalfe et al., BRITE: Universal Topology Generation from a User's Perspective Ethernet: Distributed packet switching for local computer networks, Communications of the ACM, vol.19, issue.5, p.395405, 1976.

P. Van-mieghem, H. De-neve, and F. Kuipers, Hop-by-hop quality of service routing, Computer Networks, vol.37, issue.3-4, p.407423, 2001.
DOI : 10.1016/S1389-1286(01)00222-5

J. Moy, OSPF version 2, RFC 2328, 1998.

A. M. Naimi, Délai et routage dans les réseaux ad hoc 802, Thèse de Doctorat -Université de Versailles Saint-Quentin-En-Yvelines, 2005.

D. Q. Nguyen and P. Minet, QoS support and OLSR routing in a mobile ad hoc netowrk

M. Pal, I. Tardos, and T. Wexler, Facility location with nonuniform hard capacities, Proceedings 2001 IEEE International Conference on Cluster Computing, p.329, 2001.
DOI : 10.1109/SFCS.2001.959907

K. Park and W. Willinger, Self-similar tracs, 2000.

C. Perkins, E. Belding-royer, and S. Das, Ad hoc on-demand distance vector (AODV) routing, 2003.
DOI : 10.17487/rfc3561

G. Phillips, S. Shenker, and H. Tangmunarunkit, Scaling of multicast trees: Comments on the Chuang-Sirbu scaling law, SIGCOMM, p.4151, 1999.

L. Qiu, V. Padmanabhan, and G. Voelker, On the placement of web server replicas, IEEE INFOCOM, p.15871596, 2001.

E. Royer and C. Perkins, Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing, IETF, Intemet Draft: draft-ietf-manet-maodv-00, 2000.

H. Sallay and O. Festor, A highly distributed dynamic IP multicast accounting and management framework, IFIP/IEEE Eighth International Symposium on Integrated Network Management, 2003.
URL : https://hal.archives-ouvertes.fr/inria-00099751

M. Sayal, Y. Breitbart, P. Scheuermann, and R. Vingralek, Selection algorithms for replicated Web servers, Workshop on Internet Server Performance, 1998.
DOI : 10.1145/306225.306238

S. Siachalou and L. Georgiadis, Efficient QoS routing, Computer Networks, vol.43, issue.3, pp.351-367, 2003.
DOI : 10.1016/S1389-1286(03)00286-X

M. Steele, Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges, The Annals of Probability, vol.16, issue.4, p.17671787, 1988.
DOI : 10.1214/aop/1176991596

A. S. Tanenbaum, Computer Networks, Fourth Edition, 2003.

X. Tang and S. T. Chanson, The minimal cost distribution tree problem of recursive expiration-based consistency management, IEEE Transactions on Parallel and Distributed Systems, vol.15, issue.3, p.214227, 2004.

X. Tang and S. T. Chanson, Minimal cost replication of dynamic web contents under at update delivery, IEEE Transactions on Parallel and Distributed Systems, vol.15, issue.5, p.431439, 2004.

X. Tang and J. Xu, On replica placement for QoS-aware content distribution, IEEE INFOCOM, 2004.

O. Tickoo and B. Sikdar, Queueing analysis and delay mitigation in IEEE 802.11 random access MAC based wireless networks, IEEE INFOCOM 2004, 2004.
DOI : 10.1109/INFCOM.2004.1357025

S. Toumpis and A. J. Goldsmith, Performance bounds for large wireless networks with mobile nodes and multicast trac, Inter. Workshop on Wireless Ad Hoc Networks, 2004.

V. Vazirani, Approximation Algorithms, 2001.
DOI : 10.1007/978-3-662-04565-7

J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, On the construction of energy-ecient broadcast and multicast trees in wireless networks, INFOCOM, p.585594, 2000.

H. Zhai and Y. Fang, Performance of wireless LANs based on IEEE 802.11 MAC protocols, 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003., 2003.
DOI : 10.1109/PIMRC.2003.1259194