หลักสูตร/ปี พ.ศ. ปรัชญาดุษฎีบัณฑิต สาขาวิชาวิศวกรรมคอมพิวเตอร์ ปี พ.ศ. 2556
ภาคและปีการศึกษาที่สำเร็จการศึกษา ภาคปลาย ปีการศึกษา 2556
ประเภทโครงงาน
วิทยานิพนธ์
ชื่อโครงงานภาษาไทย
ขั้นตอนวิธีสำหรับการค้นหาแบบช่วงและการวางแผนการส่งข้อมูลสำหรับการส่งข้อมูลแบบกระแสบนเครือข่ายเพียร์ทูเพียร์
ชื่อโครงงานภาษาอังกฤษ
Algorithms for Range Queries and Content Delivery Planning for Peer-to-Peer Streaming
ผู้พัฒนา
48850267 จักริน ชวชาติ
อาจารย์ที่ปรึกษาหลัก
จิตร์ทัศน์ ฝักเจริญผล
อาจารย์ที่ปรึกษาร่วม
-
บทคัดย่อ
วิทยานิพนธ์นี้ศึกษาปัญหาสองปัญหาที่เกี่ยวข้องกับการส่งข้อมูลแบบกระแสบนเครือข่ายเพียร์ทูเพียร์ งานวิจัยส่วนแรกสนใจการวางแผนการส่งข้อมูลโดยมีเงื่อนไขว่าความสามารถในการส่งต่อข้อมูลขแงแต่ละเครื่องนั้นแตกต่างกันได้ งานวิจัยมีจุดประสงค์เพื่อออกแบบแผนการส่งข้อมูลที่ส่งข้อมูลจากเครื่อง่ต้นทางไปยังทุกเครื่องได้รวดเร็วที่สุด เราพิจารณาปัญหาในกรณีที่แบนด์วิดท์ของเส้นเชื่อมทุกเส้นมีค่าเป็นจำนวนเท่าของแบนตด์วิดท์ที่ต้องการและพิสูจน์ว่าในกรณีดังกล่าวมีแผนการส่งข้อมูลที่ดีที่สุดที่เป็นต้นไม้ เราลดรูปปัญหานี้ไปยังปัญหาการสร้างต้นไม้ทอดข้ามที่มีเส้นผ่านกลางที่ต่ำที่สุดและดีกรีมีขอบเขตในกรณีที่ดีกรีไม่เท่ากัน และเสนอขั้นตอนวิธีซึ่งเป็นส่วนขยายของขั้นตอนวิธีของ Kӧnemann et al. ซึ่งทำงานได้เฉพาะกรณีที่ขอบเขตของดีกรีเท่ากันทั้งหมด เราได้พิสูจน์ว่าคำตอบที่ได้เป็นแผนการส่งข้อมูลที่มีความล่าช้าไม่เกิน O(√(log n) ) เท่าของแผนการส่งข้อมูลที่ดีที่สุด เมื่อ เป็นจำนวนโนดในกราฟ
ในงานวิจัยส่วนที่สองเราพิจารณาการค้นหาแบบช่วง แม้ว่ในเครือข่ายเพียร์ทูเพียร์จะนิยมใช้ตารางแฮชแบบกระจายเพื่อเก็บและค้นหากุญแจ แต่การแฮชทำลายคุณสมบัติท้องถิ่นของกุญแจการค้นหาแบบช่วงจึงกระทำได้ลำบาก ในอีกแนวทางหนึ่งที่หลีกเลี่ยงการแฮชนั้น Ganesan et al. ได้นำเสนอวิธีการปรับดุลภาระของระบบที่เก็บและค้นหากุญแจบนระบบเพียร์ทูเพียร์ที่ทำงานบนปริภูมิกุญแจโดยตรง ขั้นตอนวิธีที่เสนอรับประกันว่าอัตราส่วนความไม่สมดุลจะมีค่าไม่เกิน 4.237 เมื่ออัตราส่วนความไม่สมดุลคืออัตราส่วนระหว่างภาระสูงสุดต่อต่ำสุดในเครือข่าย และมีค่าใช้จ่ายถัวเฉลี่ยในการดำเนินการเป็นค่าคงที่ อย่างไรก็ตามขั้นตอนวิธีดังกล่าวเป็นขั้นตอนวิธีแบบเรียกตัวเองซึ่งมีข้อจำกัดหลายประการเมื่อนำไปประยุกต์ใช้งานจริง เราเสนอขั้นตอนวิธีการปรับดุลภาระที่ง่ายขึ้นและไม่มีการเรียกตัวเอง ที่รับประกันอัตราส่วนความไม่สมดุลไม่เกิน 7.464 และมีค่าใช้จ่ายถัวเฉลี่ยในการดำเนินการเป็นค่าคงที่
Abstract
This thesis considers two important problems in Peer-to-Peer streaming. The first part of this thesis considers content delivery planning where peers in the network have diverse uplink bandwidths. The objective of this problem is to find a streaming scheme that minimizes the maximum delivery time from the source to any peers. We consider the special case of this problem where all bandwidths are multiples of the required bandwidth and prove that there exists an optimal solution which is a tree. Using this fact, the problem in this case naturally reduces to the Bounded Degree Minimum Dianeter Spanning Tree problem with Non-Uniform Degree Bounds. We propose an algorithm for this problem which is an extension of Kӧnemann et al.'s algorithm that works only uniform degree bounds. The solution obtained from our algorithm is a streaming scheme whose delays are at most O(√(log n) ) times the optimal delay where n is the number of nodes in the network.
In the second part, we consider range queries. Peer-to-Peer networks usually employ distributed hash tables to handle data queries. However, hashing destroys the locality property of object keys, the critical properties to range queries. Ganesan et al. avoid the hashing approach and introduce a load-balancing algorithm that works with a system that searches directly on the key space. Their algorithm guarantees an imbalance ratio of 4.237 where the imbalance ratio is the ratio between the maximum and minimum load in the network, while using only a constant amortized cost per operation. However, the proposed algorithm is recursive, which is undesirable in practical settings. We present a simpler and non-recursive load-balancing algorithm which guarantees an imbalance ratio of 7.464 with constant amortized costs per operation.
คำสำคัญ (Keywords)
-
เว็บไซต์โครงงาน
-
วีดีโอคลิปของโครงงาน
-
ที่เก็บเวอร์ชันซอร์สโค้ด
-
ผู้นำเข้าข้อมูลครั้งแรก
สุนันทา
ช้างทอง
(fengsntc)
แก้ไขครั้งสุดท้าย
เมื่อ Jan. 9, 2017, 12:52 p.m. โดย
สุนันทา
ช้างทอง
(fengsntc)
สถานะการอนุมัติ
รออนุมัติ