Software Engineering || Net-Centric Computing || Postdoc & Visiting Scholars
A
GENETIC ALGORITHM APPROACH TO NETWORK ROUTING
Multicasting is the simultaneous transmission of data to multiple destinations. Multicast routing is to find a multicast tree rooted from a source node and containing all multicast destinations. The optimization goals of multicast routing are: 1) minimizing average path delay (DT) where path delays are delays from the source to each of the destinations in the multicast group, and 2) minimizing cost of the multicast tree (CT) where the cost of the multicast tree is the sum of the costs on the edges in the multicast tree. Minimizing average path delay can be solved by shortest path algorithm with O(n2) time. However minimizing cost of the multicast tree is a NP-complete problem and good heuristic algorithms are of practical interest.
The multimedia multicast routing problem is to determine a multicast tree connecting the source node to every destination node such that the total cost of this tree is minimal while the total delay from the source node to any destination node is smaller than D , where the value of D depends on the QoS requirements of the applications. It is considered as a NP-complete problem. And there are several heuristic algorithms proposed to solve the multicast routing problem. However, most of the proposed algorithms either works too slowly or can not minimize the costs of delay-constrained multicast trees.
Recently, methods based on neural networks or genetic computations have been proposed to solve multimedia multicast routing problems. Compared to traditional heuristic approaches, these new methods can achieve better results with smaller running time for relative large networks.
However, in the real world of multimedia multicast applications, a common situation is that nodes can dynamically join and leave the multicast group. So Dynamic Multicast Routing is a more practical problem than static multicast routing, and also a more challenging one. A simple approach to completely rebuild multicast trees after each node joining or leaving request, would be unrealistic.
So, our research is planned as two steps:
- Propose new methods to efficiently solve static multimedia multicast routing problem by combining genetic algorithm with experimental design methods; and
- Develop new technique (based on genetic algorithm) for dynamic multimedia multicast routing
International Center for Software Engineering
Iowa State Univerisity, Department of Computer Science
226 Atanasoff Hall, Ames, IA 50011
1-515-294-4377 (Office) 1-515-294-0258(Fax) E-mail: chang@cs.iastate.edu
Copyright © 2002, Prof. Carl K. Chang
