A traffic engineering approach for placement and selection of network services

ABSTRACT

Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We divide the problem into two subproblems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering.

REFERENCES

• 1: Sumi Choi , Yuval Shavitt, Proxy Location Problems and Their Generalizations, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.898, May 19-22, 2003
• 2: Peter B. Danzig , Richard S. Hall , Michael F. Schwartz, A case for caching file objects inside internetworks, Conference proceedings on Communications architectures, protocols and applications, p.239-248, September 13-17, 1993, San Francisco, California, United States
• 3: H. Jamjoom, S. Jamin, and K. Shin, Self Organizing Network Services, 1999, University Michigan CSE-TR-407-99.
• 4: Abdelsalam Heddaya , Sulaiman Mirdad, WebWave: Globally Load Balanced Fully Distributed Caching of Hot Published Documents, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.160, May 27-30, 1997
• 5: S. Michel, "Adaptive web caching: Towards a new caching architecture," in Proc. 3rd Int. Caching Workshop, Jun. 1998, pp. 2041-2046.
• 6: P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
• 7: R. Prasad and H. Wu, "Minimum-cost gateway deployment in cellular WI-FI networks," in Proc. IEEE Consumer Commun. Netw. Conf., Las Vegas, NV, Jan. 2006, vol. 2, pp. 706-710.
• 8: D. Awduche , A. Chiu , A. Elwalid , I. Widjaja , X. Xiao, Overview and Principles of Internet Traffic Engineering, RFC Editor, 2002
• 9: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: Y. Vardi, "Network tomography: Estimating source-destination traffic intensities from link data," J. Amer. Statistical Assoc., pp. 365-377, 1996.
• 11: B. Li et al., "On the optimal placement of Web proxies in the Internet," in Proc. IEEE INFOCOM, New York, NY, Mar. 1999, pp. 1282-1290.
• 12: X.-H. Jia , D.-Y. Li , X.-D. Hu , H.-J. Huang , D.-Z. Du, Optimal Placement of Proxies of Replicated Web Servers in the Internet, Proceedings of the First International Conference on Web Information Systems Engineering (WISE'00)-Volume 1, p.55, June 19-20, 2000
• 13: S. Jamin et al., "Constrained mirror placement on the Internet," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 31-40.
• 14: L. Qiu, V. Padmanabhan, and G. Voelker, "On the placement of web server replicas," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, vol. 3, pp. 1587-1596.
• 15: P. Radoslavov, R. Govindan, and D. Estrin, "Topology-informed Internet replica placement," Comput. Commun., pp. 384-392, 2001.
• 16: Yanif Ahmad , Uğur Çetintemel, Network-aware query processing for stream-based applications, Proceedings of the Thirtieth international conference on Very large data bases, p.456-467, August 31-September 03, 2004, Toronto, Canada
• 17: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom, Operator placement for in-network stream query processing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065199]
• 18: T. Nakano and T. Suda, "Self-organizing network services with evolutionary adaptation," IEEE Trans. Neural Netw., vol. 16, no. 5, pp. 1269-1278, Sep. 2005.
• 19: K. Papagiannaki, N. Taft, Z. Zhang, and C. Diot, "Long-term forecasting of Internet backbone traffic: Observations and initial models," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 2003.
• 20: Z. Jianping, L. Keqin, and W. Zhimei, "Selection algorithms for any-cast relay routing," in IEEE Int. Conf. Perform., Comput. Commun., Phoenix, AZ, Apr. 2004, pp. 21-27.
• 21: Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. H. Ammar, "A novel server selection technique for improving the response time of a replicated service," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 1998, pp. 783-791.
• 22: Ellen W. Zegura , Mostafa H. Ammar , Zongming Fei , Samrat Bhattacharjee, Application-layer anycasting: a server selection architecture and use in a replicated Web service, IEEE/ACM Transactions on Networking (TON), v.8 n.4, p.455-466, Aug. 2000 [doi>10.1109/90.865074]
• 23: Y. Hou et al., "On energy provisioning and relay node placement for wireless sensor networks," IEEE Trans. Wireless Commun., vol. 4, no. 5, pp. 2579-2590, Sep. 2005.
• 24: X. Kenan, H. Hassanein, and G. Takahara, "Relay node deployment strategies in heterogeneous wireless sensor networks: Multiplehop communication case," in Proc. Sensor Ad Hoc Commun. Netw., Sep. 2005, pp. 575-585.
• 25: A. Kashyap, S. Fangting, and M. Shayman, "Relay placement for minimizing congestion in wireless backbone networks," in Proc. Wireless Commun. Netw. Conf., Apr. 2006, vol. 1, pp. 159-164.
• 26: R. Cohen and G. Nakibly, "On the computational complexity and effectiveness of N-hub shortest path routing," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 27: R. M. Karp, Online Algorithms Versus Offline Algorithms: How Much is it Worth to Know the Future? International Computer Science Institute, 1992, Technical Report TR-92-044.
• 28: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 29: Yossi Azar , Oded Regev, Strongly Polynomial Algorithms for the Unsplittable Flow Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.15-29, June 13-15, 2001
• 30: B. Awerbuch , Y. Azar , S. Plotkin, Throughput-competitive on-line routing, Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, p.32-40, November 03-05, 1993 [doi>10.1109/SFCS.1993.366884]
• 31: K. Kar, M. Kodialam, and T. Lakshman, "Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications," in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp. 884-893.
• 32: Subhash Suri , Marcel Waldvogel , Priyank Ramesh Warkhede, Profile-Based Routing: A New Framework for MPLS Traffic Engineering, Proceedings of the Second International Workshop on Quality of Future Internet Services, p.138-157, September 24-26, 2001
• 33: A. Barabasi, R. Albert, and H. Jeong, "Scale-free characteristics of random networks: the topology of the world-wide web," Physica A: Statistical Mechanics and Its Applications, vol. 281, pp. 69-77, Jun. 2006.
• 34: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.346, August 15-18, 2001
• 35: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 36: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 37: M. Berkelaar, Lp_solve Software [Online]. Available: ftp.es.tue.nl/pub/ lp_solve
• 38: J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in Proc. ATNAC, 1995, pp. 95-116.
• 39: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 40: D. Katz , K. Kompella , D. Yeung, Traffic Engineering (TE) Extensions to OSPF Version 2, RFC Editor, 2003
• 41: A. Srinivasan, Approximation Algorithms via Randomized Rounding: A Survey. Lectures on Approximation and Randomized Algorithms. Warszawa, PWN: Polish Scientific, 1999.
• 42: "Multiprotocol Label Switching Architecture (MPLS)," RFC 3031, Jan. 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Management, Performance

Keywords:
load balancing, network services, routing, traffic engineering