QoS-Based Parallel GRASP Algorithm for RP Selection in PIM-SM Multicast Routing and Mobile IPv6


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


On account the progress of network multimedia technology, more and more real-time multimedia applications arrive with the need to transmit information using multicast IP communication. These applications are more important with arrival of mobile IPv6 protocol with mobile members and require a multicast routing protocol which has packets arriving to members within a specified QoS guaranteed and a quick recovery mechanism. Multicast IP is a bandwidth-conserving technology that reduces traffic by simultaneously delivering a single stream of information to a group members. Internet research community has proposed many multicast routing protocols to support efficient multimedia application, expect that they were developed for multicast parties whose members are topologically stationary. The mobility of multicast receivers or senders may lead to serious problems, when a receiver or sender moves, the quality of full multicast tree may degrade hens multicast datagrams cannot be forwarded efficiently.D2V-RPM (delay and delay variation RP Manager) problem consist of choosing an optimal multicast router in the network as the root of the Shared RP Tree within a specified delay and delay variation bound, and recovering this RP if it’s off optimal. This NP hard problem needs to be solved through a heuristic algorithm. In this paper we propose a new RP Management algorithm based on PGRAS Procedure. 2DV-PGRASP-RPM selects and recovers the RP by considering cost, delay and delay variation functions and can be easily integrated to bootstrap RP protocol used by PIM-SM protocol. Simulation results show that good performance is achieved in multicast cost.
Copyright © 2014 Praise Worthy Prize - All rights reserved.

Keywords


2DV-PGRASP-RPM; PIM-SM; Multicast IP; SRPT; RP; GRASP; BootStrap RP; Mobile IPv6

Full Text:

PDF


References


S. E. Deering, “Multicast Routing in Internetworks and Extended LANs,” Stanford University, Stanford, CA, USA, Août 1988.

D. Johnson, C. Perkins, and J. Arkko, RFC 3775:Mobility Support in IPv6. 2004.

N. Reyes, J. Mahnke, I. Miloucheva, K. Jonas, Multicast Retransmission Strategies for Content Delivery in Heterogeneous Mobile Internet Environments, (2006) International Review on Computers and Software (IRECOS), 1. (2), pp. 137 - 145.

B. Fenner, M. Handley, H. Holbrook, and I. Kouvelas, Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised). IETF, 2006.

M. Ramalho, “Intra- and Inter-Domain Multicast Routing Protocols: A Survey and Taxonomy,” IEEE Commun. Surv. Tutor., vol. 3, no. 1, pp. 2–25, 2000.

G. N. Rouskas and I. Baldine, “Multicast Routing with End-to-End Delay and Delay Variation Constraints,” North Carolina State University at Raleigh, Raleigh, NC, USA, 1995.

D. Zappala, A. Fabbri, and V. M. Lo, “An Evaluation of Shared Multicast Trees with Multiple Cores,” Telecommun. Syst., vol. 19, no. 3–4, pp. 461–479, 2002.

P.-R. Sheu and S.-T. Chen, “A Fast and Efficient Heuristic Algorithm for the Delay- and Delay Variation Bound Multicast Tree Problem,” in Proceedings of the The 15th International Conference on Information Networking, Washington, DC, USA, 2001, p. 611–.

K. L. Calvert, E. W. Zegura, and M. J. Donahoo, “Core selection methods for multicast routing.,” in ICCCN, 2004, p. 638.

T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” J. Glob. Optim., vol. 6, pp. 109–133, 1995.

K. Mehlhorn, “A faster approximation algorithm for the Steiner problem in graphs,” Inf Process Lett, vol. 27, no. 3, pp. 125–128, Mar. 1988.

A. Karaman and H. Hassanein, “Core-selection algorithms in multicast routing - comparative and complexity analysis,” Comput Commun, vol. 29, no. 8, pp. 998–1014, 2006.

H. F. Salama, “Multicast routing for real-time communication of high-speed networks,” North Carolina State University, 1996.

D. Zappala and A. Fabbri, “An Evaluation of Shared Multicast Trees with Multiple Active Cores,” in ICN ’01: Proceedings of the First International Conference on Networking-Part 1, London, UK, 2001, pp. 620–629.

L. Wei and D. Estrin, “The Trade-offs of Multicast Trees and Algorithms,” 1994.

D. GRAD, “Diffusion et Routage : Outils de Modélisation et de Simulation,” in Actes du CNRIUT97, Congrès National de la Recherche en IUT, 10 pages, Toulouse, 1997.

J. Moy, Multicast Extensions to OSPF. United States: RFC Editor, 1994.

D. Farinacci, T. Li, S. Hanks, D. Meyer, and P. Traina, Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised). 2005.

D. Waitzman, C. Partridge, and S. E. Deering, RFC 1075: Distance Vector Multicast Routing Protocol. 1988.

A. Ballardie, Core Based Trees (CBT version 2) Multicast Routing – Protocol Specification –. United States: RFC Editor, 1997.

N. Bhaskar, A. Gall, J. Lingard, and S. Venaas, Bootstrap Router (BSR) Mechanism for Protocol Independent Multicast (PIM). IETF, 2008.

D. W. Wall, “Mechanisms for Broadcast and Selective Broadcast,” Stanford University, Stanford, CA, USA, 1980.

I. Romdhani, M. Kellil, H.-Y. Lach, and A. Bouabdallah, “IP mobile multicast: Challenges and solutions.,” IEEE Commun. Surv. Tutor., vol. 6, no. 1, pp. 18–41, 2004.

S. Thomson, T. Narten, and T. Jinmei, “IPv6 Stateless Address Autoconfiguration,” RFC Editor, Fremont, CA, USA, RFC 4862, Sep. 2007.

C. Jelger and T. NoËl, “Supporting Mobile SSM Sources for IPv6,” Globecom02 IEEE Glob. Commun., vol. 2, pp. 1693–1697, Nov. 2002.

A. O’Neill, “Mobility Management and IP Multicast,” IETF, Internet Draft – work in progress (expired) 01, Jul. 2002.

S. B. Shukla, E. B. Boyer, and J. E. Klinker, “Multicast Tree Construction in Network Topologies with Asymmetric Link Loads,” 1994.

W. Hua, M. Xiangxu, Z. Min, L. Yanlong, and others, “Tabu search algorithm for RP selection in PIM-SM multicast routing,” Comput Commun, vol. 33, no. 1, pp. 35–42, Jan. 2010.

F. Glover, “Tabu Search - Part II,” Inf. J. Comput., vol. 2, no. 1, pp. 4–32, 1990.

Y. Baddi and M. D. E. Kettani, “GRAS-RP: Greedy Randomized Adaptive Search algorithm for RP selection in PIM-SM multicast routing,” in SEVENTH INTERNATIONAL CONFERENCE ON IN℡LIGENT SYSTEMS : THEORIES AND APPLICATIONS (SITA’12), Mohammedia, Morocco, 2012.

Y. Baddi and M. D. E. Kettani, VNS-RP algorithm for RP selection in multicast routing protocol PIM-SM. Tangier, Morocco, 2012.

Y. Baddi and M. D. E. Kettani, VND-CS: A Variable Neighborhood Descent Algorithm for Core selection Problem in multicast routing protocol. Dubai, India, 2012.

P. Hansen and N. Mladenovic, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 449–467, May 2001.

P. Hansen, N. Mladenović, and L. C. D. Gerad, “Variable neighborhood search: Methods and recent applications,” in In Proceedings of MIC’99, 1999, pp. 275–280.

M. Kim, Y.-C. Bang, and H. Choo, “On Core Selection Algorithm for Reducing Delay Variation of Many-to-Many Multicasts with Delay-Bounds.,” in NETWORKING, 2004, vol. 3042, pp. 200–210.

S. Ahn, M. Kim, and H. Choo, “Efficient Algorithm for Reducing Delay Variation on Delay-Bounded Multicast Trees in Heterogeneous Networks,” in WCNC 2008, IEEE Wireless Communications and Networking Conference, March 31 2008 - April 3 2008, Las Vegas, Nevada, USA, Conference Proceedings, 2008, pp. 2741–2746.

S. P. Sahoo and M. R. Kabat, “Tabu Search Algorithm for Core Selection in Multicast Routing,” in Proceedings of the 2011 International Conference on Communication Systems and Network Technologies, Washington, DC, USA, 2011, pp. 17–21.

Y. BADDI and M. Da. E.-C. El KETTANI, “Parallel GRASP Algorithm with Delay and Delay Variation for Rendezvous Point Selection in PIM-SM Multicast Routing,” J. Theor. Appl. Inf. Technol., vol. 57, no. 2, 2013.

M. G. C. Resende and C. C. Ribeiro, Parallel Greedy Randomized Adaptive Search Procedures. 2004.

D. G. Thaler and C. V. Ravishankar, “Distributed Center-Location Algorithms,” IEEE J. Sel. Areas Commun., vol. 15, p. pages 291–303, 1997.

L. M. de Assumpcao Drummond, L. S. Vianna, M. B. da Silva, and L. S. Ochi, “Distributed parallel metaheuristics based on GRASP and VNS for solving the traveling purchaser problem,” in Parallel and Distributed Systems, 2002. Proceedings. Ninth International Conference on, Dec., pp. 257–263.

Y. Marinakis, A. Migdalas, and P. M. Pardalos, “Expanding Neighborhood GRASP for the Traveling Salesman Problem,” Comput Optim Appl, vol. 32, no. 3, pp. 231–257, Dec. 2005.

P. M. Pardalos, L. Pitsoulis, and M. G. C. Resende, “A parallel GRASP for MAX-SAT problems,” in Lecture Notes in Computer Science, 1184.

T. Issariyakul and E. Hossain, Introduction to Network Simulator NS2, 1st ed. Springer Publishing Company, Incorporated, 2008.

T. Ernst, MobiWan: A ns-2.1b6 Simulation Platform for Mobile IPv6 in Wide Area Networks. Gif-sur-Yvette, France, 2001.

H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, “Network Topologies, Power Laws, and Hierarchy,” 2001.

B. M. Waxman, “Routing of multipoint connections,” Sel. Areas Commun. IEEE J. On, vol. 6, no. 9, pp. 1617–1622, Aug. 2002.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize