Overlay Multicast Routing Based On Cayley Graph

In recent years, with the development of distributed computing, grid computing,pervasive computing and mobile computing platforms, the multi-point multicastcommunication has received an increasing demand. Virtual overlay network builds virtuallogical network on physical network. Resource and nodes are mapped into the same identifierspace based on the specific topology using distributed hash function. Based on the overlaynetwork topology, virtual overlay multicast routing aims at low-latency, high throughput anddeterministic simple routing. Overlay network topology determines the level of efficiency ofmulticast routing, good topology can improve the certainty of multicast routing and simplifymulticast routing. In addition, there are several issues which show a direct impact on theavailability and efficiency of virtual overlay network multicast routing, the research on themhas not only theoretical significance, but also has pracical value.Firstly, after mapping into overlay network, the physical adjacent nodes are notnecessarily adjacent to each other, considering physical approximation when building a virtualoverlay network can further enhance the efficiency of multicast routing. Secondly, most ofthe existing researches simply use network coding technology to improve the throughput ofoverlay multicast network, but do not make full use of the relationship between networkcoding and overlay network topology. Finally, in wireless sensor network, in order to achievelow power consumption publish/subscribe model, existing research does not consider thecombination of interconnection network topology into data-centric deterministic routingprotocols. To solve the above problems,this paper mainly discusses how to make full use ofalgebraic graph theory to construct interconnection network topology, and provide solutionsfor multicast routing strategy in several specific application environments. The main researchwork and innovations are as follows:1. By using semidirect method in algebraic graph theory, we construct two regularstructured overlay topology based on Cayley graph, i.e.,5-regular Cayley Γqand Borel Cayley.Regard them as the basic topology model, we meet the requirements of self-organization andscalability of overlay multicast. These two models are simple, and have vertex-transitive andsymmetric feature, which can reduce the complexity of multicast routing and improve systemfault tolerance and query efficiency. In addition, these two models are contant-degree, whichcan keep node load does not increase with the size of the system in large-scale multicastsystem. Moreover, the relationshiop between nodes and links is computable in the models,which will make multicast routing certainty. 2. By using5-regular cayley graph Γq, a location-aware structured overlay network Psuhas been designed. Based on Psu, overlay multicast strategy COLM has been designed andsimulated. A multicast tree with maximum height of2q has been built based on5-regularcayley graph Γq. Because overlay multicast strategy COLM uses node physicalapproximation, it has advantages in relative delay loss, node stress and link stress comparedwith ALM-CAN, which also is constant degree.3. After building structured overlay topology based on Borel Cayley graph, we transformthe problem of streaming multicast with network coding into subgraph decompositionproblem. The method of using edge-disjoint subgraph decomposition to decrease thedimension of encoding vector has been proposed, which can simplify the network codingstrategy in streaming multicast. Meanwhile, in heterogeneous network, it transforms theproblem of streaming multicast into the problem of finding out edge-disjoint paths amongsender-receiver pairs. When receivers joining into each layer to build topology of each layer,we let the paths of different receivers overlapping as much as possible, thus, more encodeddata will be transferred on these paths, then bandwidth will be saved. Experimental resultsshow that combining network coding and graph topology together to solve the problem ofstreaming multicast can save bandwidth and reduce delay.4. In wireless sensor network,5-regular cayley graph Γqand Borel cayley graph havebeen used into data-centric routing of wireless sensor network. A Cross-Layer DirectedDiffusion（CLDD）with graph embedding method based on Cayley graph model is presented.Comparative performance results show that the proposed cross-layer routing protocoloutperforms previous plain directed diffusion and Omniscient Multicast. Meanwhile, based onBorel cayley graph, a deterministic data-centric storage and multicast routing strategy hasbeen proposed. Compared with the existing work, there exists certain advantages on averagequery length, routing table size,the average end-to-end delay and energy dissipation, whichhave vital reference value on extending the life of sensor network nodes.