Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Multicast services have been used in modern network applications to allow direct communication between a source node and a set of receivers, referred to as multicast destinations [2, 13]. In recent years, the number of applications of multicasting has increased steadily, following the rapid advances in the availability and use of the Internet as well as intranets in the corporate world. Multicast networks are known to provide robust and efficient data delivery for a wide spectrum of applications, including video-on-demand, groupware, and data streaming, among others [14, 22].

A number of algorithmic issues, however, remain as a major problem for the wide adoption of multicasting networks. For example, routing is an issue that has not been completely resolved on such systems due to the high computational cost of exact algorithms. While for traditional unicast systems the routing problem can be solved in polynomial time using well-known methods such as the Dijkstra’s algorithm [3], multicast routing is better modeled by the Steiner tree problem, which is one of the basic NP-hard problems [7, 17].

Given the inherent complexity of exact approaches to the DCMRP, a large number of heuristics have been proposed to find good, if non-optimal, solutions that can be calculated in polynomial time [2, 6, 10, 11, 14]. However, many of these local search methods proposed in the telecommunications engineering literature suffer from a lack of optimality guarantees and may be easily trapped into local optima [19–21, 23]. As such, these methods are indicated only for application to small- to medium-scale instances. On the other hand, applications of the DCMRP become even more challenging for instances with a large number of multicast members, since the efficient use of resources turns into a critical factor for the success of such network implementations.

In this paper we propose a metaheuristic solution for the delay constrained multicast routing problem. In particular, we propose a new method for computing routing trees for multicast networks using a hybridization of greedy randomized adaptive search procedure (GRASP) and variable neighborhood search (VNS). The strategy here is to improve the performance of the algorithm by avoiding spending too much time exploring suboptimal solutions and their solution spaces.

At the same time, our contribution may be extended to the general application of a hybrid GRASP metaheuristic. By combining the general structure of GRASP with VNS, the result is a novel search algorithm that may be used to produce fast implementations for several related problems.

The paper is organized as follows. In the next section (Sect. 2), we provide a detailed definition for the DCMRP, using graph theoretical concepts as well as a mathematical programming model. Then, in Sect. 3 we develop a GRASP metaheuristic for the DCMRP, followed by a description of the VNS strategy employed. We present computational results for our approach in Sect. 4, and finally some concluding remarks are provided in Sect. 5.

2 Delay-Constrained Multicast Routing

Multicast networks have been designed with the explicit goal of allowing fast data transmission from a source node to a set of destinations, while using a single send operation. This is made possible by sending data only once over a network link whenever one or more destinations have requested the same content. A set of nodes interested in a particular piece of data is called a multicast group. The main task faced in the operation of a multicast network consists of delivering the requested data to all members of a multicast group. To accomplish this goal, the system needs to determine a set of routes connecting sources to destinations.

Let G = (V, E) be a graph where V is the set of nodes and E a set of links connecting adjacent nodes. The source is denoted by s with destinations \(D =\{ d_{1},\ldots,d_{k}\}\), such that D ⊂ V. The cost function c: E → Z + represents link costs and the delay function τ: E → Z + returns the time τ(e) elapsed when traversing edge e ∈ E. We also denote by c(E′) the cost associated with a set of edges E′ ⊆ E, that is, c(E′) = ∑ e ∈ E′ c(e). Similarly, we denote the time delay for path \(\mathcal{P}\) in G as \(\tau (\mathcal{P}) =\sum _{e\in \mathcal{P}}\tau (e)\).

The DCMRP asks for a set of edges E′ ⊆ E such that s is connected to every node d ∈ D on G′ = (V, E′), and the maximum acceptable delay Δ d at destination d is a constant, i.e.,

$$\displaystyle{\sum _{e\in \mathcal{P}_{d}}\tau (e) \leq \varDelta _{d},\quad \mbox{ for every destination $d \in D$,}}$$

where \(\mathcal{P}_{d}\) is the path induced by E′ in G, connecting s to d. Moreover, we require that the total cost ∑ e ∈ E′ c(e) of the subset E′ be minimum.

Additionally, real-world instances of the DCMRC problem frequently have extra requirements on the kind of paths that can be used to connect sources and destinations [2]. For example, the model may require that a minimum capacity be available for each edge selected in the final solution. We will consider variations of this problem in the next sections. First, let us define a formal MIP model for the problem.

2.1 MIP Model for the DCMRP

A mixed integer programming (MIP) model for the DCMRP can be described as follows. Let x i  ∈ { 0, 1}, for i ∈ { 1… | E | }, be a decision variable that is 1 whenever an edge is part of the routing tree and 0 otherwise. Then, the objective function can be written as a minimization problem over the vector x, while considering the cost of each edge:

$$\displaystyle{\min \sum _{e_{i}\in E}x_{i}c(e_{i}),}$$

where \(c: E \rightarrow \mathbb{R}\) is the cost function as described above. Then, we need a set of constraints that guarantee the connectedness of the solution set \(\{(u,v) \in E: x_{j}=1\}\):

$$\displaystyle{\sum _{e_{i}=(v,w)\in U\times V }x_{i} \geq 1\qquad \mbox{ $\forall $ partitions $U,W$ s. t. $\vert (S \cup D) \cap U\vert $ is odd. }}$$

That is, there is at least one link connecting each partition of V where the number of sources and destinations is different. Next, we have constraints that indicate the boundedness of the delay.

$$\displaystyle{\sum _{e_{i}\in E}y_{i}^{v}\tau (e_{ i}) \leq \varDelta _{v}\qquad \mbox{ for $v \in D$}}$$

where y i v for e i  ∈ E is an indicator variable with value 1 whenever the edge e i is part of a path from source to destination v ∈ D. The variables y i can be 1 only if link e i is part of the solution, so we also have

$$\displaystyle{y_{i} \leq x_{i}\qquad \mbox{ for all $e_{i} \in E.$}}$$

Finally, we need to apply the standard integrality constraints to our model variables:

$$\displaystyle{y_{i} \in \{ 0,1\}\qquad \mbox{ for $e_{i} \in E$}}$$
$$\displaystyle{x_{i} \in \{ 0,1\}\qquad \mbox{ for $e_{i} \in E$}}$$

2.2 DCMRP and the Steiner Problem

The minimum routing cost problem as described above has close connections to the minimum cost Steiner tree problem. In graph theory, a tree that connects a set of required nodes, while using other nodes only if necessary, is called a Steiner tree [8, 16]. Thus, we can restate the problem as that of finding a minimum cost Steiner tree such that maximum delay restrictions are also satisfied.

In the Steiner problem, one is given a graph G = (V, E) together with a cost function c: E → Z +, and a set R ⊂ V of required nodes. The nodes in V ∖ R are called Steiner nodes. The objective is to find a tree T linking the nodes in D, passing through Steiner nodes (V ∖ R) if necessary, such that the cost ∑ e ∈ T c(e) is minimized. The Steiner problem on graphs is well known to be NP-hard [7].

Consider the following transformation from instances of the Steiner problem to the DCMRP. Given an instance of the minimum cost Steiner tree problem, let us construct an instance of DCMRP using the same underlying graph. Select a node among the required nodes to become the source and let the remaining required nodes be destinations. Then, set Δ d  ← ∞, for all d ∈ D. As can be easily confirmed, an optimal solution to the transformed problem will also be a solution to the original instance of the Steiner problem. Conversely, an optimal solution for the original instance will give an optimal solution for the transformed instance. This argument shows that the DCMRP is also NP-hard.

Given the computational complexity of the DCMRP, it is extremely difficult to solve general large-scale instances of the problem. However, our goal is to devise algorithms that can provide near optimal solutions for typical instances of the problem. Moreover, we want such algorithms to perform efficiently, returning feasible solutions quickly and avoiding getting stuck in local optima.

3 GRASP Approach for DCMRP

Most modern metaheuristic techniques are based on finding solutions close to the global optimum with the help of gradient methods combined with randomization rules, which are designed to avoid local optima. Metaheuristics main contribution is on the development of intelligent strategies for mixing existing non-optimal techniques and algorithms. Such metaheuristics use similar principles in slightly different ways. A conceivable goal for the algorithm designer is, therefore, to borrow techniques from different metaheuristics, in order to create algorithms that better reflect the characteristics of the problem at hand. In this paper we use some of the techniques proposed by GRASP metaheuristic as well as by the variable neighborhood search metaheuristic (VNS) to efficiently solve the DCMRP.

Greedy Randomized Adaptive Search Algorithm (GRASP), proposed by Feo and Resende [4], aims at finding near optimal solutions for combinatorial optimization problems. It is composed of a number of iterations, where a new solution is picked from the available feasible set, using a greedy construction algorithm. The initial solution is subsequently improved using some local search method. GRASP has been very successful in a number of applications such as QAP [15], Frequency Assignment [9], Satisfiability, and many others [5]. The steps of standard GRASP are summarized in Algorithm 1.

Algorithm 1 Generic GRASP algorithm

The GRASP algorithm is a multi-start method, where a new solution is constructed, and subsequently improved. In the construction phase, at each iteration the algorithm tries to add a new element using a randomized greedy strategy. The second phase is concerned with improving the current solution. Its goal is to achieve a local optimum state by performing a local search, which is usually based on a gradient decent strategy. In the next sections, we describe the approach used in the GRASP implementation for DCMRP.

Algorithm 2 Generic GRASP constructor

3.1 GRASP Constructor

The construction phase of the GRASP algorithm is responsible for creating a new solution, using a greedy randomized strategy. The basic idea behind greedy randomization is to add elements to the solution according to a greed criterion. However, the element that is chosen at each step to compose the new solution is not necessarily the best available element. Instead, the selection is taken randomly from a subset of best available elements, which have been previously sorted using a greedy objective. The general algorithm is displayed in Fig. 2. In the algorithm, the subset of best elements is called a restricted candidate list (RCL). The RCL is created and used to track the best elements available to be added to the current solution.

3.2 Speeding Up the GRASP Constructor

To be effective as the construction phase in a GRASP algorithm, it is desirable that the construction method be very fast. A construction algorithm that is not quick enough may become a bottleneck for the whole algorithm, since it needs to be executed every time a new solution is desired. While the traditional approach for GRASP construction works well, it requires the maintenance of an additional data structure, which needs time to build, and as a result it can waste computational resources. Instead, we use the following observation proved in [14].

Observation 1

Let \(x_{1},\ldots,x_{n}\) be an unordered sequence, and \(y_{1},\ldots,y_{n}\) the corresponding ordered sequence. Then, to find a random element among the \(y_{1},\ldots,y_{\alpha }\) , for 0 < α ≤ n is on average equivalent to selecting the best of α random elements of \(x_{1},\ldots,x_{n}\) .

The observation above gives a very efficient way of implementing the RCL test, which gives us, on average, the same results. Start with the full set C of candidate elements. Then, at each step generate a value of α, and pick at random \(k = 1/\alpha\) elements of C. From the picked elements, store only the one that is the best fit for the greedy function. This method is shown in Algorithm 3.

Algorithm 3 Improved construction phase for GRASP

A clear advantage in terms of computational complexity is achieved by the proposed construction method for GRASP. The greatest advantage is that, while in the original technique the candidate elements must be sorted, this is not necessary in the proposed algorithm. Moreover, the complexity of traditional construction is dependent on the number of candidate elements. In our method, the complexity is constant for a fixed value of α. For example, if alpha is n∕2, then we need just two iterations to find an element in the RCL, with high probability.

Theorem 1 ([14]).

The complexity of selecting elements from the RCL in the modified construction algorithm is nlog n.

3.3 GRASP Construction Phase for DCMRC

We proceed to describe how to find a solution for the DCMRP that will be used in the construction phase of the GRASP algorithm. The construction algorithm is composed of several steps, in which we build a spanning tree that contains all the nodes in the required set of sources and destinations, along with other nodes required as intermediaries.

The first part of the construction phase is to compute paths connecting the source to each of the destinations d ∈ D. This is done using a randomized version of Dijkstra’s algorithm, which finds shortest paths from a source to a single destination. The adaptation necessary here is such that the shortest path is updated only with high probability p. This guarantees that the solution found in any two executions of the algorithm will be close to the optimum, but still with random differences that make the result useful for our stochastic optimization methods. The randomized shortest path is then used to create an initial solution as shown in Algorithm 4.

Algorithm 4 GRASP construction for DCMRP

The first part of Algorithm 4 guarantees that the solution created is connected, by finding a separate path from the source to each destination d ∈ D. At the end of this phase, we will have a solution where separate paths may result in cycles. Therefore, the second phase of the construction algorithm aims at removing such cycles. At each step, it finds the two highest cost edges contained in a cycle. Then, the algorithm removes one of them in an arbitrary way. The goal is to reduce the cost of the final solution, while at the same time allowing for randomized results. The resulting solution is returned at the end of Algorithm 4 to be later used by GRASP.

3.4 Variable Neighborhood Search

Once a feasible solution has been created by GRASP, the next step of our algorithm is to try to improve its quality using a local search procedure. Traditionally, local search has been performed using gradient descent techniques, which try to incrementally improve a solution until a local minimum is reached. The disadvantage of such methods, however, is that they can quickly become stuck in a local neighborhood, hindering the computational effort employed during the search phase. We try to avoid this behavior by using instead an alternative search technique based on variable neighborhood search (VNS).

VNS is a metaheuristic programming technique that has be successfully used to solve several combinatorial optimization problems [12]. Its main approach is to perform local search using successively larger neighborhoods, until no more improvements can be found by increasing the neighborhood size up to a given parameter. The advantage of VNS is that it will not stop once the first local optimum has been found. Instead, it will continue to build better solutions by reaching more distant neighborhoods in a organized fashion, until it cannot find any additional improvements. By reaching these more distant neighborhoods, VNS can more easily avoid being trapped in the same optimal solution, therefore yielding better results than standard local search.

The VNS algorithm for the DCMRP tries to replace existing sub-paths in the current solution by using alternate paths that have the potential for improving the objective function. This is done by arbitrarily selecting a pair of nodes occurring in the existing solution and replacing its induced sub-path by a new path, found using a shortest path algorithm. For this purpose, one can use a method such as Dijkstra’s shortest-path procedure, which will hopefully provide a local improvement to the existing solution.

It is also possible to use randomized shortest-paths, similarly to how these paths are calculated in the GRASP constructor, where the best path is updated according to a probability distribution, so that the best path is not always selected. In that case, possible improvements will come from the exploration of the neighborhood of the existing solution, although the local-optimality of this improvement is not guaranteed in the same form as when using a completely greedy procedure.

The difference between VNS compared to other local search strategies resides in the ability to change the underlying neighborhood structure as a new local minimum is found. In our case, the neighborhood is changed by increasing a reach parameter, so that larger subpaths are substituted by the algorithm. This kind of change will happen until the maximum of N, defined by the parameter K, is reached. The general approach used in our VNS implementation is provided in Algorithm 5.

Algorithm 5 Variable neighborhood search

The algorithm starts by defining the parameter N, which is interpreted as the distance between nodes for which a new path will be searched. For the first iteration, this parameter is set to value 1, and in this case only nodes that are neighbors in the current solution are substituted by new paths. This process is repeated as long as we are able to perform improvements in the existing solution. A limit of δ moves without improvement is allowed before the inner part of the algorithm is interrupted. Then, the parameter N is increased by one and the process restarts.

The search is completed only when N reaches the previously defined upper limit K. At this point, the algorithm has systemically investigated all paths that might improve the current solution by replacement of paths occurring between pairs of nodes. When that happens, we return to the upper-level GRASP process the best solution found during all iterations, which will be used as the new optimum solution.

3.5 Path Relinking

GRASP has the advantage of being easy to develop, since it is composed of relatively independent procedures (the constructor and local search phases). It is well suited for applications with existing heuristic algorithms, that can be combined with GRASP to find a better solution.

However, one of the weaknesses of GRASP is its incapacity to integrate good solutions found previously into the current search iteration. Since each iteration will create a completely different solution, there is no information added to the system when a good solution is found.

A method that has been used lately to overcome this problem is called path relinking (PR) [1, 18]. In PR, a subset of the best solutions found is kept in a separate memory, called the elite set. At each iteration, one of the solutions s will be selected, and a process of comparing the current solution with s will start. Each component of the solution will be changed to the corresponding value on s, and after this a local search will be initiated to check for local optimality.

The disadvantage of PR is the large time it takes to run, in comparison with the rest of the GRASP algorithm. This, in practice, has been a restricting factor in the use of PR on practical applications. Although PR brings a relative boost in solution quality on each iteration, the effect can be negative since the number of iterations may be reduced due to the added complexity. Therefore, we need to use experimental data to determine the best trade-off between computational time and quality of results produced by path relinking.

The path relinking implementation used to solve the DCMRP is described in Algorithm 6. The first step of path relinking is to create a set of elite elements, denoted by \(\mathcal{E}\). The maximum size of this set is given by ε, therefore for the first ε iterations we simply run the existing GRASP algorithm and add the resulting to solution to the elite set.

Algorithm 6 Path relinking improvement phase

When the elite set is complete, we start using it to perform improvements to the solution generated by GRASP. This is depicted in the second while loop in Algorithm 6. The termination criterion is usually based on number of iterations, time, or the distance to a known lower bound. The first step of the loop is to create a new solution using GRASP. Then, an element of \(\mathcal{E}\) is arbitrarily selected and subsequently used during the path relinking process. For each path \(\mathcal{P}\in s\) going from source to destination, the algorithm will try to replace the edges of the existing solutions with the edges of the same path in the elite solution. This is performed in the following way: first, we calculate the union of the two edge sets. Then, we proceed to remove redundant edges in a greedy fashion. That is, for each high cost edge, we check if we can remove it while maintaining a connected solution. This process continues until there are no cycles in the resulting solution.

The last step of the algorithm loop is to update the elite set. For this purpose, we retrieve the worst solution γ in the elite pool. If the current solution s improves on the cost of γ, then we replace γ with s in the elite set. These steps are then performed until a predefined termination criterion is satisfied.

4 Computational Results

To test the quality of the proposed metaheuristic, we designed a set of DCMRP instances. The instances range in size from 40 to 100 nodes, which is representative of medium-size problems occurring in large companies or in clusters of medium-sized organizations. Edges have been added to these test networks with costs that are uniformly distributed between 1 and 10. The distances are assumed to be Euclidian, but can be easily adapted to other metrics such as Manhattan distances (Fig. 1).

Fig. 1
figure 1

Drawing of an instance with 40 nodes depicting node positions and costs between nodes

Full size image

We run the proposed algorithm 10 times for each of the tested instances. We report on the average of these executions, to account for random fluctuations between different runs. The results are illustrated in Table 1. In this table, the first two columns give the number of nodes and edges in the network. The next three columns display the average best solution found by the GRASP without enhancements, the GRASP plus VNS strategy, and finally the GRASP with VNS enhanced with the PR method.

Table 1 Experimental results of the GRASP and VNS metaheuristic implementation for the DCMRC
Full size table

An area that we tested in the GRASP implementation just shown was the relative contribution of having two improvement methods (traditional local search and VNS) as components of the metaheuristic. As can be seen from the results, VNS is able to improve the quality of results in most of the cases, which shows that the use of multiple neighborhoods can provide a boost in efficiency for the algorithm.

5 Concluding Remarks

In this paper, we presented a metaheuristic approach to solve the DCMRP, a problem arising on multicast routing systems, where the goal is to provide quick and accurate routing services to a set of source and destination points. Due to its occurrence in the design of telecommunication networks, the DCMRP has become the focus of intense research in the last few years. Our main contribution is the use of a fast construction algorithm along with an improvement method based on variable neighborhood search. The VNS has been used to enhance GRASP results, making it possible to explore existing solutions even faster.

The results of our experiments show that this method provides high quality solutions for realistic instances of the problem. The elegance of the method used also means that it can be easily incorporated to other algorithms for the DCMRP and related problems. In future research, it would be interesting to investigate the use of other intensification strategies for the proposed algorithm, such as improving the basic path relinking scheme used in this paper.