Qos Multicast Routing For Content Distribution Using Optimization Techniques

Qos Multicast Routing For Content Distribution Using Optimization Techniques

Abstract

The requisite of various real-time interactive media applications in rapid networks prompt the necessity of QoS based multicast routing. For video streaming, audio, etc. content distribution is used for faster delivery by high- traffic websites. It saves data in local server and the process of transferring data from local server to clients is done using multicast routing. Multicast routing creates tree structure in which source (or server) sends data to group of receivers in which source sends only single copy but data gets replicated at router and distributed to the receivers. QoS multicast routing is a non-linear combinatorial optimization problem which has been proved to be NP-Complete. Using optimization technique we try to find multicast tree with minimized cost and also it should satisfy constraints such as bandwidth, cost, delay, and delay-jitter. This paper present some existing optimization techniques and explains how these were used to solve QoS multicast routing.

Keywords:Content distribution, Multicast Routing, Particle swarm optimization, Genetic algorithm, Honey bee algorithm, Memetic Algorithm Quality of services.

1. Introduction

   Routing is a process of selecting paths in the network along which the data packet is sent across the network traffic. The process of routing IP packets over the internet is connectionless, and is known as packet switching. In packet switching networks, routing directs packet forwarding, the transit of logically addressed packets from their source towards their ultimate destination through intermediate nodes which are typical hardware devices such asrouters, bridges, gateways, firewalls, or switches. Router finds a path and forwards the packet.

   1. Multicasting

      Multicasting [1] is the ability of a communication network to accept a single message from an application and to deliver copies of the message to multiple recipients at different locations. In multicast communication [2] sources send packet only, even if it is to be delivered to large number of receivers, using the network resources optimally. Router replicates the packet whenever necessary to send the large number of population. Each packet contains information about the IP address of the source and destination nodes, sequence numbers and some other information. IP address information in the packet is used to forward the packets towards the intended destination. Routers are the intelligent glue which are used to direct traffic from one point on the internet to other.

   2. Content distribution

      Content distribution [4] is the process of copying pages of website to geographically dispersed servers and when a client requests a page, the page is dynamically identified and served from the closest server, enabling faster delivery. In this process local servers are placed at each internet access points around the world and codes are used to redirect the clients webpage request to local server. At the same time, it may be possible that the request of many clients for the same webpage or video content is received and for that multicast routing is used to deliver the data from source to all the receivers.

   3. Quality of services

      Quality of Service [5] is the ability to provide different priority to different applications, users, or data flows. It also guarantees a certain level of performance to a data flow. For example, a required bit rate, delay, jitter, packet dropping probability and/or bit error rate may be guaranteed.The function of QoS is to ensure that all the applications are getting the necessary bandwidth to function at a desired level. QoS uses resource reservation control mechanisms to allow

      administrators to set a desired level of service for each traffic type on the network. The goal of QoS is to provide preferential delivery service for the applications that need it by ensuring sufficient bandwidth, controlling latency and jitter, and reducing data loss [3].

      If in multicasting a client wants to receive the multicast stream, it will contact the router. If router will accept, it will replicate the traffic to the client and others in the host group. If hosts want to receive certain packet sent to multicast group, it will send IGMP packets and one more protocol is used to coordinate the multicast routers throughout the internet, so that multicast packets are routed to their final destinations.

      SOURCE

      SOURCE

      FILE

      ROUTER

      CLIENT

      CLIENT

      COPY COPY COPY

      CLIENT

      CLIENT

      CLIENT

      CLIENT

      Figure 1: Multicast Network

      The task of optimization is determining the values of a set of parameters so that some measure of optimality is satisfied, subject to certain constraints.Optimization refers to both minimization and maximization of tasks, a task involving the maximization of the function f is equivalent to the task of minimizing f. Here, in multicast routing we use optimization techniques to find the optimal multicast tree, through which when data is sent to the user it will take less time to reach

      i.e. minimum delay. And the cost will be minimized if delay is minimized.

      As QoS multicast routing has been implemented using many optimization techniques. The aim of this paper is to consider fewexistingimplementedtechniques and explain how we can get optimal multicast tree and deliver data with less delay in gist.

      The rest of the paper is organized as follows. Section 2 describes process of content distribution in. The problem description and formulation is given in section 3. Section 4 contains steps to get optimal multicast tree using various optimization techniques. In section 5, we briefly describe how we can solve a network manually using PSO and GA. Finally, we draw some conclusion in section 6.

2. Content distribution

   Commercial requirement and prompt service have been the guiding force in interactive media. The benchmarking and standardization of broadcast and telecommunication services have taken recourse to myriad ways owing to commercial compulsions and customers requirement. Recent developments in areas such as internet, mobile communications and broadcasting have led to a convergence of these traditional communities, in which content delivery has become a common ground.A content delivery networkis a large distributed system of servers deployed in multiple data centres in the Internet. The goal of a content delivery is to serve content to end-users with high availability and high performance. Content delivery serve a large fraction of the Internet content today, including web objects,downloadable objects, applications, live streaming media, on-demand streaming media, and social networks.

   Content Delivery, was evolved first in 1998, which replicate contents over several reverberated web servers strategically placed at massive worldwide network in order to deal with the flash crowds. Distributing the web servers facilities over local servers is a method commonly used by service providers to improve performance and scalability. Content delivery has some combination of a content-delivery infrastructure, a request-routing infrastructure, a distribution infrastructure and an accounting nfrastructure. Content delivery improves network performance by maximizing bandwidth, improving accessibility and maintaining correctness through content replication and thus offer fast and reliable applications and services by distributing content to the cache servers located close to users.

   In content delivery environment, web content based on user request are fetched from the origin sever and a user is served with the content from nearby replicated webserver. In multicasting, the sender or server sends only one copy of content via multicast and the content gets replicated when it is necessary.

3. Problem description and formulation

   The communication network is modelled as a weighted directed graph G (V, E), where V is set of vertices i.e. nodes and E is set of edges i.e. links. In multicasting, problem is to find tree T from graph G, such that tree covers all the vertices of multicast group M. Each edge (g, h) E in G has three weightsb (g, h), d (g, h) and c (g, h) which represents available bandwidth, the delay and the cost respectively. Let sV be the source node and

   M V-{s} is the multicast destinations.

   The cost (or weight) of a multicast tree is the sum of the costs of all the links in the multicast tree. A good multicast tree tries to minimize the cost. It is defined as:

   A multicast tree which satisfies these constraints and gives minimum cost is considered as optimal multicast tree through which data is send from source to all the receivers. When the source sends the data, the data is encoded in the multicast stream, and at the destination all the data are collected and decoded. This way, the receivers get their requested page or data in less time.

4. QoS multicast routing using optimization techniques

   1. Particle swarm optimization

      PSO [6] is a heuristic global optimization method put forward originally by Dr. Kennedy and Eberhart in 1995.The PSO [7] [8] [9] is a stochastic

      C (T (s, M))=

      ( g ,h)T ( s,M )

      c(g, h)

      (1)

      algorithm that does not need gradient information derived from the error function.The particles are placed in the search space ofsome problem or

      The total delay of the path P(s, v) in T is simply the sum ofthe delay of all links along P(s, v) where vM, i.e.

      function, and each evaluates the objective function atits current location.Thevalue of the best function result[10]so far is stored in a variable that can be called pbesti(for previous best), for comparison

      on later iterations. The gbest topology (for global

      D (P (s, v)) =

      ( g ,h)P( s,v)

      d (g, h)

      (2)

      best), was one where the best neighbour in the entire population influenced the target particle.

      The total delay of the tree T (s, M) is defined as

      the maximum value of the delay on the paths from source to destination

      D (T (s, M))=max (D (P (s, v)), v M (3)

      The bottleneck bandwidth of the tree is defined as the minimumvalue of the bandwidth of all the links along path P (s, v)

      B (P(s, M)) = min {B (g, h), (g, h) P(s, v)} (4)

      The delay-jitter is defined as the average difference of the delay on the paths from source to destination node.

      DJ (T (s, M)) =

      1. QMR using PSO

         PSO[3] [23]moves towards the global optimal solution by taking into consideration the local solutions of the particle. After generating multicast trees and considering them as particles, we will calculate the fitness function of each particle. And then using concept of pbest and gbest we will get optimal solution for the problem.

         Step 1: From the graph G (V, E), we compute all the possible and existing paths from source to multicast destinations by creating routing table for each individual destination, and arranging all the paths in increasing order of their delay.

         (D(P(s, v)) (delay _ avg))2

         vM

         (5)

         Step 2: Considered route number 0 of each destination from routing table. And initial tree is constructed.

         The problem is to find the multicast tree which minimizes the cost function subjected to the following conditions:

         The tree must satisfy the following QoS constraints:

         D (T (s, M)) end-to-end delay (6) B (P (s, v)) minimum bandwidth (7) DJ (T (s, M)) jitter delay constraint (8)

         Step 3: The parameters for each tree of network is calculated based on the equations (1), (2), (3), (4),

         (5) and the constraints (6), (7), (8) checked.

         Step 4: Fitness is calculated for each tree. Fitness functionality used is:

         f (T (s, M )) Cost(T (s, M )) 1 min{ D(T (s, M )), 0}

         2 min{ DJ (T (s, M )), 0}

         (9)

         where 1, 2are constants.

         Here fitness function is used as minimization function.

         Step 5: Update pbest and gbest values.

         Each particle is associated with pbest and gbest values. The pbest value represents the best fitness value obtained by the particle. And gbest value stores the best fitness value obtained among the pbest values of all particles.

         Step 6: New particles (trees) are obtained by using adjustment operator i.e. velocity is calculated taking into consideration the pbest and gbest value. Particle represents possible route from source to destination, after applying adjustment operator adjust (i, n). If particle + n is less than route number then we will consider particle + n and if it is greater or equal we will take mod(particle).A velocity value is associated with each particle, which is calculated as:

         vnew= w* vold +c1* rand () * (pbest-curr) +c2* rand ()

         * (gbest-curr) (10)

         wherew, c1, c2 are constants, voldis old value of velocity, rand () generates random value, pbest is personal best of a particle, gbest is global best, curr is current particle value.

         New particle is calculated as:

         xnew = xold + V (11)

         Step 7: Repeated the steps 3-6 until all the particles converge towards the gbest.

         .

         The tree obtained is the most efficient network from source to multicast destination to send data.

   2. Genetic algorithm

      The GA [11] [12] [13] [14] is a stochastic global search methodthat mimics the metaphor of natural biological evolution. GA operates on a population of potential solutions applying the principle of survival of the fittest to produce (hopefully) better and better approximations to a solution. At each generation, a new set of approximations is created by the process of selecting individuals according to their level of fitness in the problem domain andbreeding them together using operators borrowed from natural genetics. This process leads to the evolution of population of individuals that are better suited to their environment thanthe individuals that they were created from, just as in natural adaptation.GAis different from traditional method as GA search a population of points in

      parallel, not a single point. It also do not require derivative information or other auxiliary knowledge, only the objective function and corresponding fitness levels influence the directions of search. It uses probabilistic transition rules, not deterministic ones. GAs work on an encoding of the parameter set rather than the parameter set itself.

      1. QMR using GA

         Network [15] [23] is represented as a directed acyclic graph. Each node is associated with delay, delay jitter and bandwidth. Multicast trees are created and the fitness functions are calculated, and using GA selection operator all the fittest treesis selected. After that crossover between particles is performed and new particles are generated. Then the fitness for the new particlesare calculated.From all the particles the fittest tree is selected as the optimal multicast tree.

         Step1: Network under consideration is represented as a graph and the different trees are recorded as the solution set using particle encoding. From routing table trees are constructed.

         Step 2: The solution set is represented as string set. And then some rando strings are selected from the string set. Uniform selection is used in this process.

         Step 3: The parameters for each tree of network is calculated based on the equations (1), (2), (3), (4),

         (5) and the constraints (6), (7), (8) checked.

         Step 4: The fitness value of string is calculated using the equation:

         f (T (s, M )) Cost(T (s, M )) 1 min{ D(T (s, M )), 0}

         2 min{ DJ (T (s, M )), 0}

         (12)

         Where 1, 2 are constants

         The function is directly proportional to delay, delay jitter and loss probability and inversely proportional to bandwidth. For optimal multicast tree, delay, delay jitter, loss probability should be less and bandwidth should increase. Here, fitness function is the minimization function. If we want we can consider or include other parameters such as queuing delay, buffer space.

         Step 5: Crossover probability taken here is 80%. Crossover performed here is either scattered crossover or two-point crossover.

         Step 6: The probability of mutation is about 0.001. We change a part of the string to emulate the behaviour of genetic algorithm.

         Step 7: Repeat the steps 3-4 for each child tree. And check whether child tree is more fit than parent tree or not. If yes, replace, otherwise next step.

         Step 8: Repeat the steps 2-8 until optimal multicast tree is found.

         4.3 Honey bee algorithm

         The Bee Colony [16] [17]a meta-heuristic belongs to the class of Nature-Inspired Algorithms which are inspired by various biological and natural processes observed in honeybee. HBO is the SI system where the low level agent to the system is the bee. HBO is the name given to the collective food foraging behaviour of honey bee. The bee system is a standard example of organized team work, well-coordinated interaction, coordination, labour division, simultaneous task performance, specialized individuals, and well-knit communication. In a typical bee colony there are different types of bees. There is aqueen bee, many male drone bees and thousands of worker bees. Each artificial bee generates one solution to the problem. HBO [18] iswidelybeing used to solve problems belonging to diverse domains.

         4.3.1 QMR using HBO

         Step 1: Created trees randomly and calculated parameters (1), (2), (3), (4), (5) and constraints

         checked (6), (7), (8) and then fitness function for each tree is calculated.

         Step 2: Fitness function is calculated using:

         Step 7: Repeated the steps 3-7 until optimal multicast tree is obtained.

         4.4 Memetic algorithm

         The concept of meme [19] [20] [21]was created by Richard Dawkins in 1976 to explain how cultureevolves. Dawkins made a parallel comparison between biological evolution and cultural evolution and the result was the concept of meme. Dawkins defines a memeas a unitof cultural evolution that needs refinement.

         The first generation of MA refers hybrid algorithm, a marriage between a population-based global searches coupled with a cultural evolutionary stage. Multimeme are referred as second generation of MA exhibiting the principles of memetic transmission and selection.MAs are intrinsically concerned with exploitingall available knowledgeabout the problem under study; this is somethingthat was neglected in EAs. Each individual represents a tentative solution for the problemunder consideration. These solutions are subject to processes of competitionand mutual cooperation in a way that resembles the behavioural patterns ofliving beings from a same species.The unique aspect of the MAs algorithm is that all chromosomes and offsprings are allowed gaining some experience, through a local search, before being involved in the evolutionary process.

         4.4.1 QMR using MA

         Memetic algorithm[22] is used in multicast routing to reduce the time and to obtain optimal multicast tree with minimal cost.

         Step 1: Random population of solution is generated. Then, initial network node for each chromosome is selected.

         B(T (s, M )) * B min * Bavg

         B(G(V , E)) B max B max

         Step 2: For all links, bandwidth constraint is

         F (T (s, M )) (1/ k)* C(T (s, M ))

         C(G(V , E))

         D(T (s, M ))

         D(G(V , E))

         checked. Any link, that is not satisfying equation

         (8) is deleted.

         (13)

         Step 3: The total population is divided into elite groups of 25%, 35%, and 40% of fitness value.

         Step 4: The group with highest fitness values are considered and neighbours are searched, if replacing any existing node with neighbour node increases fitness then replace the node.

         Step 5: Repeated the step 4 for each group.

         Step 6: Calculated the fitness for each new population generated in each group.

         Step 3: Fitness function is calculated for each individual in population. And for each individual local search is performed.

         Step 4: Two individuals are selected randomly and crossover is performed. And for child local search is done.

         Step 5: On child, mutation is performed and then local search is performed.

         ROUTE NUMBER	ROUTE LIST
         0	0-2-6-7
         1	0-2-5-7
         2	0-1-4-7
         3	0-2-6-3-7
         4	0-1-3-7
         5	0-2-5-6-7
         6	0-1-3-6-7

         ROUTE NUMBER	ROUTE LIST
         0	0-2-6-7
         1	0-2-5-7
         2	0-1-4-7
         3	0-2-6-3-7
         4	0-1-3-7
         5	0-2-5-6-7
         6	0-1-3-6-7

         Step 6: Fitness function for each individual is calculated and checked whether child is better than any other individual in the population or not. If yes, replace the individual with child.

         Step 7: Repeat thesteps 1-7 until optimal multicast tree is obtained.

5. Network as an illustration

   The figure below gives a brief example of how to solve the network and get optimal multicast tree. The network topology is shown in Fig. 2. For multicast routing, we denote 0 as source and 3,

   6, 7 as multicast destinations. Each link has 3 weights bandwidth, delay and cost respectively.

   In this problem, we set = 10, = 1, = 5. Initial tree T(s, M) is constructed using route number 0 from routing table of each destination. And resultant tree is:

   (2, 2, 2)

   0 2

   (2, 2, 2)

   0 2

   (7, 1, 7)

   (2, 2, 2)

   (3, 3, 2)

   1 (8, 2, 10)

   3

   (7, 1, 7)

   6

   (3, 3, 2)

   (8, 2, 10)

   1

   (4, 2, 3)

   (4, 2, 1)

   3

   (1, 3, 2)

   (3, 3, 1)

   6

   (2, 2, 3)

   5

   (3, 1, 5)

   (2, 2, 3)

   7

   4

   (2, 3, 7) 7

   Figure 2: A given network topology G(V, E)

   Now, creating routing table for individual destination and arranging in order of the increasing delay:

   Table I: Routing table for destination 3:

   ROUTE NUMBER	ROUTE LIST
   0	0-1-3
   1	0-2-6-3
   2	0-2-5-6-3
   3	0-2-5-7-6-3
   4	0-2-5-7-3

   Table II: Routing table for destination 6:

   ROUTE NUMBER	ROUTE LIST
   0	0-2-6
   1	0-1-3-6
   2	0-2-5-6
   3	0-2-5-7-6
   4	0-2-5-7-3-6 /td>
   5	0-1-3-7-6

   Table III: Routing table for destination 7:

   Figure 3: Initial Tree T(s, M)

   The delay, delay-jitter, bandwidth and cost are calculated according to the equations (1), (2), (3),

   (4), (5).

   And we get, D (T (s, M)) = 5, B (P (s, M)) = 1,

   delay_avg = 4.3, DJ(T (s, M)) = 1.63

   And putting these values in either equation (9) or equation (12), we get fitness value 28.185.

   For PSO, to get next particle i.e. tree, we will use theadjustment operator.

   For destination 3, i = 0, n =0, i.e. 0+4=0<5.

   For destination 6, i = 0, n = 2, i.e. 0+1=2<6

   For destination 7, i = 0, n = 5, i.e. 0+4=5<7

   So, we take route number 0, 2, 5 from three routing tables respectively. And resultant tree is:

   (2, 2, 2)

   0 2

   (3, 3, 2)

   (2, 2, 2)

   To perform GA two-point crossover, we select two trees for e.g. fig. 3 and fig. 5.

   0-1-3 0-2-5-7-3

   (8, 2, 10)

   1 3

   (3, 3, 1) 5

   6

   (2, 2, 3)

   7

   0-2-6 0-2-5-7-3-6

   0-2-6-7 0-2-5-7

   We consider chromosomes from each string and select two points and perform two point crossovers.

   0-2-6-7

   Figure 4: Tree T (s, M)

   The delay, delay-jitter, bandwidth and cost are calculated according to the equations (1), (2), (3),

   (4), (5).

   And we get, D (T (s, M)) = 9, B (P (s, M)) = 2,

   delay_avg = 7, DJ(T (s, M)) = 2.82

   And putting these values in equation (9), we get fitness value 21.59.

   Update pbest for each iteration and from the pbest

   0-2-5-7-3-6

   and the child chromosomes are:0-2-5-7,

   0-2-6-7-3-6 but in this chromosome we discard the genes, because destination 6 is repeated

   So, 0-2-6

   And resulting tree is:

   (2, 2, 2)

   0 2

   update gbest.

   Likewise, steps are repeated till we get optimal multicast tree.

   For GA, like we have constructed initial tree, other trees will be created from routing table randomly.

   (3, 3, 2)

   (8, 2, 10)

   1 3

   (7, 1, 7)

   6

   7

   (2, 2, 2)

   5

   (3, 1, 5)

   (2, 2, 2)

   0

   3 (4, 2, 1)

   (1, 3, 2)

   2

   (2, 2, 2)

   6 5

   (3, 1, 5)

   7

   Figure 6: New tree T (s, M) after crossover

   Likewise, we calculate the fitness for the tree in fig. 6.

   And steps are repeated until we get fittest or optimal multicast tree.

6. Conclusion

Figure 5: Tree T (s, M)

The delay, delay-jitter, bandwidth and cost are calculated according to the equations (1), (2), (3),

(4), (5).

And we get, D (T (s, M)) = 10, B (P (s, M)) = 1,

delay_avg = 7.6, DJ(T (s, M)) = 3.56

And putting these values inequation (12), we get fitness value 12.72.

QoS multicast routing problems are over complex, therefore there solutions can be considered as a very good indicator for the potential of the nature inspired algorithms. The capability of PSO, GA, HBO and MA are applied to QMR to evolve the optimal multicast tree. Many techniques are studied and small networks have been solved manually to check their performance. These techniques can be applied to big networks or even small networks. Content distribution helps the client to get the requested page or video within fraction of time. For content distribution one-to-many multicast is more relevant. And QMR helps to broadcast the data to

multiple destinations at a time with minimal cost. Many other techniques can be applied to QMR for more optimal results.

Reference:

1. Sahasrabuddhe LH, Mukherjee B. Multicast routingalgorithmsand protocols: a tutorial. IEEE Network. 2000:90102

2. Wang Z, Sun X, Zhang D. A PSO based multicast routing algorithm. IEEE Third International Conference on Natural Computation (ICNC), 2007: 664-667

3. Mala C and RajagopalanN.Simulated study of QoS multicast routing using Particle Swarm Optimization, World Applied Programming, vol (1), No (3).August 2011: 176-182

4. http://whatis.techtarget.com

5. http://en.wikipedia.org/wiki/Quality_of_service

6. Kennedy J and Eberhart R. Particle Swarm Optimization. IEEE 1995: 1942-1948

7. Lazinica A. Particle swarm optimization. In-Tech.

   January 2009

8. Bergh F V D. An analysis of particle swarm optimizers. University of Pretoria etd. , F. 2006

9. Bai Q. Analysis of particle swarm optimization algorithm. Computer and information science. February 2010, vol. 3, No. 1, 180-184.

10. Poli R, Kennedy J, Blackwell T. Particle swarm optimization: an overview: Springer science: August 2007: 1: 33-57.

11. Genetic Algorithm Toolbox Users Guide

12. Weise T. Global optimization algorithms: theory and application. Version: 2009-06-26.

13. Srinivas M, Patnaik L.M, Genetic Algorithms: a survey: June 1994, Vol 27, Issues: 6, 17-26.

14. An introduction to genetic algorithms: Melanie Mitchell

15. Mala C, A. Anurag Mahesh, Aravind R. ,P. Rajgopal, Narendran Rajagopalan and B. Nithya, Simulated study of QoS Multicast Routing using Genetic Algorithm. World Applied Programming, vol (2), Issue (5), May 2012, 342-348

16. Teodorovic D.,Davidovic T. and Selmic M. Bee Colony Optimization: The Applications Survey.ACM Transactions on Computational Logic, 2011: 120.

17. Kaur A. and Goyal S. A survey on the Applications of Bee Colony Optimization Techniques.International Journal on Computer Science and Engineering (IJCSE), Vol. 3 No. 8 August 2011: 3037- 3046

18. Mohammad TayebTaher and Amir Masoudrahmani, Multicast Routing in Computer Networks considering Quality of Services (QoS) based on Honey BeeAlgorithm.International Journal of Computer Applications (0975-8887) vol.58, No.2, November 2012.

19. Moscato, Pablo. On Evolution, Search, Optimization Genetic Algorithms andMartial Arts: Memetic Algorithms. California Institute of Technology, Pasadena California, USA. 1989.

20. Neri F., Cotta C. Memetic algorithms and memetic computing optimization: A literature review. Swarm and evolutionary computation, Elsevier Science Publishers.

Volume 2, February 2012: 1-14

1. Zhang Q, Wang Z, Zhang D. QoS multicast routing optimization based on memetic algorithm. IEEE computer society. 2008: 441-444

2. Abdel-kader RF. Hybrid discrete PSO with GA operators for efficient QoS multicast routing. Ain Shams Engineering Journal (2011); 2:21-31