以Tabu-search近似演算法處理多址傳播影音串流的最佳傳送問題

Solving multicast stream-transmitting problem with tabu-search based algorithm

楊文霖(Wen-Lin Yang)

《網際網路技術學刊》 4卷1期 (2003/01) Pp. 9-18

https://doi.org/10.6138/JIT.2003.4.1.02

摘要

近年來寬頻網路已逐漸普及至各階層的使用者，寬頻多媒體服務也將繼Internet應用風潮之後成為下一波熱門的網路服務，蘊藏有無限的商機，而其中又以隨選視訊服務最受歡迎，也最具經營效益的電子商務。在隨選視訊網路中，影音伺服器傳送一個節目，即是在網路上產生一個影音串流，若有多個影音串流同時存在於網路中，如何利用中間節點的交換器(switch)來分配傳送這些影音串流？其目標是希望在有限的網路頻寬限制下，能滿足最多的客戶數的收視需求，以創造最大經濟效益，這是本論文的主要研究目地。這個影音串流分配傳送問題是個NP-complete問題，一個隨選視訊伺服器若所提供的影片數目相當多，其全域最佳解將難以獲得。因此，本研究提出一個以tabu-search為基礎的近似演算法，能夠有效率地處理大型網路為它找到高品質的近似解，以符合實際需要。根據實驗的證明，對於無迴圈的有向圖，我們的tabu-search演算法所求得的近似解與由branch-and-bound演算法所求的正確解的平均誤差在0.5%左右。然而在伺服器所提供的節目數稍微增多時，branch-and-bound演算法就無法在合理時間內求得正確解，反觀我們的tabu-search法卻是仍能在極短時間內搜尋到高品質的近似解，因此它是一個高效率且表現相當穩定的演算法。至於含簡單迴圈的有向圖，就近似解的品質而言，我們的tabu-serch演算法的表現亦優於以branch-and-bound為基礎的近似演算法。

關鍵字

視訊網路 ； 影音串流 ； 多址傳播 ； tabu-search ； branch-and-bound ； 寬頻網路

並列摘要

The broadband network has been getting popular in recent years. The video on demand (VOD) service is the most exciting e-commerce business offered by the broadband network. For a VOD system, there are usually many customers demanding on the same video program provided by the VOD server. In addition, there are many video multicasting streams flowing on the network. Since the network bandwidth is fixed, it may not possible to supply all the video streams to all the customers. Therefore, it is important to learn how to distribute these multicasting streams to the interconnected nodes (i.e., the switches) n the net, such that the maximum number of customers connected to switches can be served. Since this is a NP-complete problem, an efficient algorithm is needed . In the past, branch-and-bound based heuristic algorithm has been proposed. However, this algorithm is only good for a small-scale network with a small number of video programs.

In this study, we propose a tabu-search based heuristic algorithm to solve this steam-distributing problem. For the acyclic directed graphs, the experimental results show that our approach in much more efficient and stable than the branch-and-bound based exact algorithm. As for the general directed graphs with a simple cycle, the solutions found by our algorithm are also better than the heuristic algorithm based on branch-and-bound method.