A design of minimum cost multicast routing algorithm

การออกแบบวิธีการหาเส้นทางการส่งข้อมูลแบบมัลติคาสก์ที่มีค่าใช้จ่ายน้อย

Name: Somonsak Thojun

LCSH: Algorithms

LCSH: Multicasting (Computer networks) -- Design and construction

Abstract: This research aims to design a delay-constrained minimum cost multicast routing algorithm used to support the real-time multimedia multicast application. My process of developing the model for my Delay Constrained Multicast Routing (DCMR) is separated into two parts. The first part is designed for finding a multicast tree with minimum cost, whereas the second part is mainly to discover the process of iterative path switching. It aims to find new paths within the delay bound by iteratively replacing the old ones with new ones. The computation complexity of this approach is moderate, in the order of O(n3log(n)). After designing the DCMR algorithm, we initially test the work with some fixed graphs. We further perform the experiment with the Random Graph based on Waxman’s algorithm with 9 graph sizes at 10, 15, 20, 25, 30, 60, 90, 120 and 150 nodes. Each size consists of 100 different forms of network graphs, with one randomly selected source node and four destination nodes. The results obtained from DCMR are then compared with another approach  Bounded Shortest Multicast Algorithm. First, as to the cost issue, the cost of the trees obtained from DCMR algorithm is approximately 20% higher. Secondly, as to the issue of delay, DCMR is much less efficient, however, in some cases, the results are just the opposite, depending on the delayed bound, the graph structures, and the positions of both source and destination nodes. Finally, as to the computation time, the DCMR algorithm is about 2-4 times faster simply because it requires fewer iterations. In conclusion, my Delay-Constrained Multicast Routing algorithm is suitable for real-time multimedia multicast applications because it generates multicast trees that requires less computation time than any other algorithms and most likely cost less for an equal level of performance.

Abstract: งานวิจัยครั้งนี้เป็นการออกแบบวิธีการหาเส้นทางสำ หรับการส่งข้อมูลแบบมัลติคาสก์ โดย มีเป้าหมายให้มีค่าใช้จ่ายน้อย และมีค่าของดีเลย์อยู่ภายใต้ค่าดีเลย์ที่กำ หนดไว้ ซึ่งเป็นวิธีหนึ่งใน การจำ แนกประเภทของวิธีการหาเส้นทางการส่งข้อมูล เพื่อต้องการให้สนับสนุนกับงานที่ต้องการ ความรวดเร็วในการส่งข้อมูล โดยสามารถนำ ไปประยุกต์ใช้กับงานมัลติคาสก์ที่ต้องการส่งอย่างทัน ทีทันใด (real-time multicast application) ในการออกแบบอัลกอริทึ่มสำ หรับหาเส้นทางการส่งข้อมูลที่ชื่อว่า Delay Constrained Multicast Routing ซึ่งเรียกสั้นๆว่า DCMR นี้ ในส่วนแรกจะทำ การหาเส้นทางการส่งข้อมูลให้ ค่าใช้จ่ายน้อยก่อน หลังจากนั้นจึงทำ การวนซํ้าเพื่อหาเส้นทางใหม่มาแทนเส้นทางเก่าเพื่อให้ค่าของ ดีเลย์ไม่เกินค่าที่กำ หนดไว้ โดยที่ความซับซ้อนของการคำ นวณของ DCMR อยู่ที่ O(n3log(n)) เมื่อออกแบบ DCMR แล้ว ได้ทำ การทดลองกับรูปกราฟบางรูปก่อนซึ่งได้ผลที่ดี จากนั้น จึงได้ทดลองโดยใช้ Random Graph เพื่อเป็นเครื่องมือในการสร้างรูปกราฟที่มีขนาดแตกต่างกัน 9 ขนาดคือ 10 15 20 25 30 60 90 120 และ 150 จุด แต่ละขนาดมีรูปกราฟที่แตกต่างกัน 100 รูปแบบ และได้สุ่มเลือกจุดต้นทาง 1 จุด และจุดปลายทาง 4 จุด ผลการทดลองในเชิงเปรียบเทียบระหว่าง DCMR กับงานวิจัยที่ชื่อ Bounded Shortest Multicast Algorithm (BSMA) ในประเด็นแรกในเรื่องของค่าใช้จ่ายโดยรวมพบว่า DCMR จะสร้างเส้นทางการส่งข้อมูลที่มีค่าใช้จ่ายสูงกว่า BSMA แต่จะไม่เกินร้อยละ 20 ในประเด็นที่ สองในเรื่องของดีเลย์พบว่า เส้นทางการส่งข้อมูลที่ได้จาก DCMR จะมีประสิทธิภาพด้อยกว่า BSMA แต่บางกรณี DCMR ก็สามารถสร้างเส้นทางการส่งมูลได้มีประสิทธิภาพดีกว่า BSMA ทั้งนี้ ขึ้นอยู่กับการกำ หนดค่าดีเลย์ (Δ) ในประเด็นสุดท้ายในเรื่องของเวลาการคำ นวณหาเส้นทาง การส่งข้อมูล จะพบว่า DCMR จะใช้เวลาการคำ นวณน้อยกว่า BSMA เสมอ โดยใช้เวลาน้อย กว่า 2 – 4 เท่า จึงสรุปได้ว่า DCMR จะเหมาะกับการใช้งานมัลติคาสก์ที่เป็นมัลติมีเดียที่ต้องการ ส่งข้อมูลอย่างทันทีทันใด

Mahidol University

Address: NAKHON PATHOM

Email: liwww@mahidol.ac.th

Name: Supachai Tangwongsan

Role: Thesis Advisors

Created: 2003

Modified: 2553-02-24

Issued: 2010-01-05

วิทยานิพนธ์/Thesis

application/pdf

ISBN: 9740439837

CallNumber: TH S956ds 2003

eng

DegreeName: Master of Science

Level: Master's Degree

Descipline: Computer Science

Grantor: Mahidol University

©copyrights Mahidol University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	4037541.pdf	1008.83 KB	21	2023-12-15 15:58:40

ใช้เวลา

-0.743549 วินาที