2004 · 15 citations · 13 references
ComputingComputational DesignComputer NetworksDigital CommunicationGenetic EngineeringGenetic AlgorithmsNetwork OptimizationRoutingRouting AlgorithmsGenetic Algorithm OptimizationMulticast CommunicationMulticast RoutingMulticast TopologyMutationNode DegreeQuality Of Service RoutingSteiner Tree Problem
Due to the advent of many new multimedia applications that have QoS (quality of service) requirements in high-speed networks, the issue of multicast routing has become more and more important. The multicast routing problem is also known as the Steiner tree problem which has been shown to be NP-complete. Previous research works just take delay, delay jitter, loss rate, bandwidth and cost into consideration and not view multicasting ability of router as a constrained factor. Limiting degree of switch or router can save information delivering/copying time and keep load balance. Delay-constrained is a crucial factor in QoS. This paper takes delay and also degree constraints into account and proposes a new multicast routing algorithm based on genetic algorithm (GA) to construct degree-delay constrained least-cost multicast routing tree (DDCT). Algorithms adopt prufer coding and decoding which is very suitable for crossover and mutation operation and can save runtime, pruning and grafting techniques are employed to adjust node degree and repair tree structure. Two repairing tree structure methods are proposed and named as DDCTI and DDCT2. Simulations were conducted on a random graph to evaluate the performance of the proposed algorithm. Experimental result shows proposed algorithms perform well than other similar multicasting algorithm such as CSPT and Wang/spl I.bar/GA.
13
Routing of multipoint connections
Bernard M. Waxman · IEEE Journal on Selected Areas in Communications · 1988 · 2.9K citations
Genetic Algorithms and Engineering Design
David W. Coit · The Engineering Economist · 1998 · 1.2K citations
Architecture, Industrial Engineering, Design Optimization +14
A fast algorithm for Steiner trees
Lawrence T. Kou, George Markowsky, L. Berman · Acta Informatica · 1981 · 1.2K citations