在網路使用量暴增以及對多媒體資訊需求高漲的今天，串流服務（streaming service）的重要性與日遽增，如何利用網路技術提供串流服務所需要的服務品質（Quality of Service, QoS）需求，是一項重要的議題。串流服務所需要的服務品質包括了：頻寬（bandwidth）、延遲（delay）以及使用者間的資料傳輸延遲差異（delay variation）。其中，網路多媒體資訊的傳輸對於頻寬的需求相當驚人，因此以群播繞送（multicasting）取代一般的繞送方式是一個可以有效節省頻寬需求的方式。故我們提出一套群播繞送演算法（multicasting algorithm）暨服務品質機制來支援串流服務。
首先，我們提出的群播繞送演算法是一個分散式且共享群播繞送樹的演算法（distributed and shared-tree like algorithm）。這個演算法是針對頻寬、延遲以及使用者間的資料傳輸延遲差異所設計的演算法。由於設計一個確保能滿足如此多項服務品質需求的群播演算法是一個NP-complete的問題，因此我們提出的是一個試探演算法（heuristic algorithm）。首先，我們在使用者間所有的延遲最短路徑上搜尋合適的節點成為核心候選數對（core candidate pairs）構成一個集合QT，這些核心候選數對是由一個核心候選節點以及一個建樹相對最短延遲（relative tree-min-delay）所組成。我們由具有最大的建樹相對最短延遲的數對開始挑選，由其核心候選節點擔任群播繞送樹的根，進行建樹的過程。我們由到核心的最短路徑是一個合適的路徑成員節點透過這個路徑來加入樹中。所謂合適指的是滿足頻寬、延遲、延遲差異的需求。之後透過這棵建構中的樹上的節點對所有未加入樹中的成員做邀請的廣播，廣播中會包括相關的延遲及延遲差異的資訊，讓這些樹外的節點能夠決定透過到哪一個邀請者的最短路徑來加入這棵樹最能滿足延遲和延遲差異的需求。如果這一組核心候選人數對無法完成建樹的任務，則再由QT集合中挑出建樹相對延遲次大的數對來進行建樹的任務。由於這是一個分散式的演算法，節點間需透過控制訊息作溝通、並針對接收到的控制訊息最初反應。演算法的訊息複雜度（message complexity）是O(k |M|2 n |in|ave)，針對控制訊息做出反應的各個演算法程序中，所具有的最大時間複雜度（time complexity）是O(n2)，較其他類似演算法的複雜度來得小。我們也對這套演算法進行了模擬實驗，都有不錯的表現。在延遲差異方面，顯示出能夠滿足使用者的需求，也符合網路的特性，並遠遠贏過最短路徑樹（Shortest path tree）和最小展開樹（minimal spanning tree）；另外，在建立繞送樹的成功率方面，也有不錯的表現。
此外，我們利用由演算法所獲得的資訊搭配網路節點的佇列管理，直接對傳送中的串流資料做頻寬配置管理，以更精確的封包繞送排程來彌平使用者間延遲差異。我們使用適應性頻寬分配方法（Adaptive Bandwidth Allocation scheme, ABA）以及加權公平排程方法（Weighted Fair Queueing, WFQ）達到這個需求。

Today there are the great usage of network and strong necessary of multimedia, and how to provide
the needed Quality-of-Service (QoS) for streaming service is an important issue. These needed QoS for streaming service includes bandwidth, delay, and delay variation. Among these requirements, the needed bandwidth for network multimedia transmission is very large, and using multicasting to replace general routing is a good
choice to lower down the bandwidth-consumption. Therefore, we proposed a multicasting algorithm and adopted some QoS mechanisms for streaming service.

First, the multicasting algorithm we proposed is distributed and shared-tree like. This algorithm is aimed to satisfy the bandwidth, delay, and delay variation constraints. Since finding such a algorithm is a NP-complete problem, the method we proposed is a heuristic algorithm--a Delay, delay Variation and Bandwidth constrained Shared Tree Algorithm (DVBSTA). At the beginning, we build a set $Q_T$ to collect the core candidate pairs on
all the shortest paths between any two members. Each pair is constructed with a core candidate and its relative tree-min-delay. We start from the pair with the largest relative tree-min-delay, and let the core candidate as the tree root to maintain the tree construction. A member can join the core through the shortest path if this path is suitable. The so-called suitable path is a path satisfying the bandwidth, delay, and delay variation constraints. And then all the on-tree nodes will broadcast the invite messages to invite the non-tree members. These message contains needed information about delay and delay variation such that these non-tree members can
decide to join the tree through the shortest path to which invitor for satisfying delay and delay variation constraints. If the chosen pair fails in tree construction, the another pair in $Q_T$ with second largest relative tree-min-delay will be selected to complete the job. Since our algorithm is distributed, it needs some control messages to do negotiation among nodes, and each node will do reaction according the message it got. The message complexity of DVBSTA is $O(k cdot |M|^2 cdot n cdot |in|_{ave})$. Among the procedures for each type of message, the largest time complexity is $O(n^2)$, which is smaller than the complexity of the other similar researches. The simulation results of DVBSTA presents the good performance. For delay variation, the result shows that the user requirements can be satisfied under the conditions of the real network. Our performance is
much better than Shortest path tree and minimal spanning tree. Besides, we also do the good job on the success frequency of the tree construction.

Besides, we manage the bandwidth allocation on each network node and use the collected information from DVBSTA to control the streaming traffic flow directly such that the tree delay variation can be shortened with the more
precise packet routing scheduling. We use the Adaptive Bandwidth Allocation scheme (ABA) and the Weighted Fair Queueing (WFQ) to complete this task.

Bin Wang and J. C. Hou, "Multicast routing and its QoS extension: problems, algorithms, and protocols," IEEE Network, vol. 14, no. 1, pp. 22-36, Jan. / Fab. 2000.

Z. Wang and J. Crowcroft, "Quality of service routing for supporting multimedia applications," IEEE Journal on Selected Areas in Communications, vol. 14, no. 7, pp. 1228-1234, Sep. 1996.

Mong-Fong Horng, and Yau-Hwang Kuo, "Adaptive bandwidth allocation to synchronize delivery delay of multicast streaming services in DiffServ Router," submitted to IEEE Transection on Multimedia

A. Parekh, "A generalized processor sharing approach to flow control in integrated services networks," PhD dissertation, MIT, Fab. 1992.

G. N. Rouskas, and I. Baldine, "Multicast routing with end-to-end delay and delay variation constraints," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, Apr. 1997.

G. N. Rouskas, and B. K. Haberman, "Cost, delay, and delay variation conscious multicast routing," Tech. Report, TR-97-03, Dep. of Computer Science, North Carolina State University, 1st Mar. 1996.

Qing Zhu, Mehrdad Parsa, and J. J. Garcia-Luna-Aceves, "A source-bases algorithm for delay-constrained minimum-cost multicasting," Proc. IEEE INFOCOM '95, pp. 377-385, 1995.

Xiaohua Jia, "A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks," IEEE/ACM Transactions on Networking, vol. 6, no. 6, pp. 828-837, Dec. 1998.

S. Chen, and K. Nahrstedt, "Distributed QoS routing," Tech. Report, UIUCDCS-R-97-2017, Dep. of Computer Science, UIUC, Jul. 1997.

S. Chen, and K. Nahrstedt, "Distributed quality-of-service routing in high-speed networks based on selective probing," Tech. Report, Dep. of Computer Science, UIUC, 1998.

Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest, "Introduction to algorithms," The MIT Press, Cambridge, Massachusetts, pp. 463-578, 1998.

David W. Wall, "Mechanisms for broadcast and selective broadcast," PhD thesis, Stanford University, California, U. S. A., Jun. 1980.

B. M. Waxman, "Routing of multipoint connections," IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

Tom Billhartz, J. Bibb Cain, Ellen Farrey-Goudreau, Doug Fieg, and Stephen Gordon Batsell, "Performance and resource cost comparisons for the CBT and PIM multicast routing protocols," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 304-315, Apr. 1997.

D. Waltzman, S. Deering, and C. Partridge, "Distance vector multicast routing
protocol," RFC 1075, Nov. 1988.

J. Moy, "Multicast extensions to OSPF," RFC 1584, Mar. 1994.

A. Ballardie, "Core based trees multicast routing architecture," RFC 2201, Sep. 1997.

A. Ballardie, "Core based trees (CBT version 2)multicast routing protocol specification," RFC 2189, Sep. 1997.

D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, and L. Wei, "Protocol independent multicast-sparse mode (PIM-SM): protocol specification," RFC 2362, Jun. 1998.

K. L. Calvert, E. W. Zegura, and M. J. Donahoo," Core selection methods for multicast routing," Proc. Int. Conf. Computer Communications and Networks, pp. 638-642, Jul. 1995.

David G. Thaler, and Chinya V. Ravishankar, "Distributed center-location algorithms," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 291-303, Apr. 1997.

Seok J. Koh, Myung K. Shin, Jong H. Yi, Jin H. Hahm, and Chee H. Park, "Non-core based shared tree architecture for IP multicasting," Electronics Letters, vol. 35, no. 11, 27th May 1999.

David R. Kosiur, and Dave Kosiur, "IP multicasting: the complete guide to interactive corporate networks," John Wiley & Sons, 1998.

D. Bertsekas, and R. Gallager, "Data Network," Prentice Hall, Englewood Cliffs, New Jersey, 1987.

Eugene L. Lawler, "Combinatorial optimization : networks and matroids," Holt, Rinehart and Winston, U.S.A., pp. 98-108, 1976.