The fair bandwidth allocation is an important issue in the multicast network to serve each multicast traffic at a fair rate commensurate with the receiver’s capabilities and the capacity of the path of the traffic. The lexicographically fair bandwidth allocation problem is considered and formulated as a nonlinear integer programming problem. A nonincreasing convex function of the bandwidth of the virtual sessions is employed to maximize the bandwidth of each virtual session from the smallest.
To solve the fairness problem a genetic algorithm (GA) based on the fitness function, ranking selection and the shift crossover and a tabu search based on the intensification and diversification are developed. Outstanding performance is obtained by the proposed Tabu Search in various multicast networks. The effectiveness of the Tabu Search becomes more powerful as the network size increases.
인터넷과 네트웍은 급속히 발전하고 있고 이에 맞추어 화상회의, 원격강의, 주문형 비디오 등과 같은 새로운 서비스가 등장하고 있다. 이러한 일대다 또는 다대다 통신에서 멀티캐스트는 자원의 효율적인 운영방법을 제공한다. 멀티캐스트는 네트웍을 고유하게 되므로 각 서비스간에 자원을 공정하게 할당할 필요가 있다. 그리고 네트웍의 이질성(Network heterogeneity)으로 인해 각 가입자들 간에도 공정성이 유지되어야 한다. 멀티캐스트 서비스의 가입자들은 자신이 원하는 서비스의 종류와 지불 요금에 따라서 서로 다른 수준의 서비스 품질을 기대하게 되고 이에 비례하게 자원이 할당되어야 한다. 현실적인 관점에서 자원은 이산적으로 할당되는 것을 가정하였다.
본 논문에서는 공정성의 개념에 대해 정의하고 그 중에서 lexicographic optimality를 공정성의 개념으로 채택하여 자원을 할당하는 문제를 정식화 하였다. 그리고 이 문제를 해결하는 방법으로 genetic algorithm과 tabu search를 제시하고 있다. 결과에 의하면 모든 문제에 대하여 이 논문에서 제시된 genetic algorithm과 tabu search에 의한 해는 기존의 algorithm보다 더 공정한 해를 제공해 주고 있으며 또한 제시된 두 개의 algorithm중에서 tabu search가 가장 좋은 해를 제공해 주고 있다.