# A Novel Hybrid Ant Colony Optimization for a Multicast Routing Problem
## 4 ACO&CM Algorithm
### Memory Detection Search Strategy  
Many literatures provide heuristic algorithms for constrained tree construction. These heuristic algorithms mainly include two types. The first type is to build a spanning tree with minimum-cost. Then, to make it satisfy the corresponding requirements, the tree structure should be pruned. The second type is to separately generate the constrained routing path starting from a source to every destination. After that, one main path is determined as the main fame tree, and other paths should be integrated into the tree. When the paths are constructed from a source node to destinations, there are two types of forward and backward path construction. The forward path construction starts the path search from a source and ends at the destination. The backward path construction proceeds  
Figure 2: Diagram of the Cloud. from destinations to a source. To avoid forming loops, we adopt a memory detection search (MDS) strategy, and embed it into the process of tree construction. The MDS strategy adopts the second category to construct trees and we use the forward path construction. The MDS strategy can ensure the search towards any feasible path considering QoS constraints. To avoid the generation of loops influencing on feasible multicast path construction, we adopt a memory detection search (MDS) strategy that uses two kinds of data memory structures: the current list (\(CL\)) and the path list (\(PL\)). The \(CL\) records nodes, which the current path routing reaches during the depth-first search process to impede the self-loop generation, while the \(PL\) stores all the built routing paths to avoid the generation of the inter-loop. Figure 3 illustrates the process for avoiding generating the self-loop. The network graph has nine nodes, in which node 0 is a source node, and \(M=\{d_{1},d_{2},d_{3}\}\) represents the destinations. At the beginning of the path construction, the search process starts from source node 0 and selects the next nodes based on the proposed ACO algorithm mechanism. When there are no given destinations to choose from, the search process will not continue going with a deeper search without returning nodes in \(CL\), and the search progress should be traced back to one level before starting another search branch. Meanwhile, the MDS strategy records visited nodes in \(CL\) during the current path construction. In Figure 3a, assume the path process arrives at node 1. Then, all the nodes \(\{0,4,5,3,1\}\) on the current path have been recorded in \(CL\). Because node 4 and node 0 have been recorded in \(CL\), the two nodes are not accessible to avoid the self-cross loop. There are no other nodes from the current node 1, so the traceback operation is executed by considering nodes in \(CL\) till the routing path process returns to node 5 as given in Figure 3b,c. When tracing back to node 5, the path process searches for destination node \(d_{3}\), completes the path search, and records the path in \(PL\), i.e., \(PL=\{\{0,4,5,d_{3}\}\}\) as illustrated in Figure 3d. We adopt the MDS strategy for avoiding the generation of the inter-loop using \(PL\). Figure 4a shows an example, in which a path \(\{0,4,5,d_{3}\}\) has been built. The \(CL\) records visited nodes in the process of the current path construction. Before starting a next path, store \(CL\) to \(PL\) and set \(CL=\emptyset\). The \(PL\) stores the nodes constituting all previously built paths, \(PL=\{\{0,4,5,d_{3}\}\}\). We can begin with  
Figure 3: An instance of producing the self-loop. the next path. Suppose in Figure 4a that the routing process begins the path search from a source and moves to node 2. In the scenario, because node 4 is recorded in \(PL\), it is not accessible to avoid forming the inter-loop, which is formed by the current path and the completed paths. Next, the path construction process points to node \(d_{1}\) directly, one of the destinations, which has not added to the multicast route paths as shown in Figure 4c, and then a current routing path \(CL=\{0,2,d_{1}\}\) has been built.