BATON Overlay

เครือข่ายโอเวอร์เลย์แบบต้นไม้สมดุล( BATON ) เป็นโครงสร้างต้นไม้แบบกระจายที่ออกแบบมาสำหรับระบบแบบเพียร์ทูเพียร์ (P2P) แตกต่างจากโอเวอร์เลย์อื่นๆ ที่ใช้ ตารางแฮชแบบกระจาย BATON จัดระเบียบเพียร์ในรูปแบบต้นไม้แบบกระจายเพื่ออำนวยความสะดวกในการค้นหาช่วง BATON มีเป้าหมายที่จะรักษาระดับความสูงของต้นไม้ให้สมดุล คล้ายกับต้นไม้ AVLส่งผลให้ขอบเขตการค้นหาสำหรับการค้นหาแบบตรงตัวและการค้นหาแบบช่วง รวมถึงการดำเนินการอัปเดต (เข้าร่วม/ออกจากกลุ่ม) มี จำกัด${\displaystyle O(\log N)}$

BATON เป็นโครงสร้างข้อมูลแบบต้นไม้ไบนารี ในแต่ละระดับของต้นไม้ โหนดจะถูกตั้งชื่อตามตำแหน่งของโหนดนั้นในต้นไม้

แต่ละโหนดใน BATON จะเก็บลิงก์ไว้สี่ประเภท:

1. ลิงก์ไปยังโหนดแม่ (ยกเว้นโหนดราก)
2. เชื่อมโยงไปยังโหนดลูกได้สูงสุดสองโหนด
3. ลิงก์ไปยังโหนดที่อยู่ติดกันทางซ้ายและขวา
4. ลิงก์ไปยังโหนดเพื่อนบ้านที่เลือกไว้ซึ่งเก็บรักษาไว้ในตารางการกำหนดเส้นทางด้านซ้าย (LRT) และตารางการกำหนดเส้นทางด้านขวา (RRT) เมื่อรวมตารางเหล่านี้เข้าด้วยกัน จะได้ตารางการกำหนดเส้นทางขึ้นมา${\displaystyle RT:={LRT}\cup {RRT}}$

ระดับของโหนดใดๆ จะสูงกว่าระดับของโหนดแม่หนึ่งระดับ โหนดรากอยู่ที่ระดับ 0 สำหรับโหนดที่ตำแหน่งมันจะเติมตารางการกำหนดเส้นทางด้านซ้ายด้วยโหนดที่ตำแหน่งสำหรับค่าที่ถูกต้องใดๆและเติมตารางการกำหนดเส้นทางด้านขวาด้วยโหนดที่ตำแหน่งสำหรับค่าที่ถูกต้องใดๆโครงสร้างของตารางการกำหนดเส้นทางมีความคล้ายคลึงเล็กน้อยกับตารางนิ้วใน Chord ${\displaystyle p}$${\displaystyle p-2^{x}}$${\displaystyle x\geq 0}$${\displaystyle p+2^{y}}$${\displaystyle y\geq 0}$

ดังนั้นตามโครงสร้างตัวอย่าง โหนด2:1จะยังคงรักษาการเชื่อมโยงไปยัง

• 1:0 (ผู้ปกครอง)
• 3:2 (เด็ก)
• 0:0และ3:2 (ติดกัน)
• 2:0 , 2:2และ2:3 (เพื่อนบ้าน)

สมดุลความสูง

BATON จะถือว่าสมดุลก็ต่อเมื่อความสูงของต้นไม้ย่อยทั้งสองต้นที่โหนดใดๆ ในต้นไม้นั้นแตกต่างกันไม่เกินหนึ่ง หากโหนดใดตรวจพบว่าข้อจำกัดเรื่องความสมดุลของความสูงถูกละเมิด กระบวนการปรับโครงสร้างใหม่จะเริ่มต้นขึ้นเพื่อให้แน่ใจว่าต้นไม้ยังคงสมดุลอยู่

เมื่อโหนดใหม่ต้องการเข้าร่วมเครือข่ายใน BATON คำขอเข้าร่วมจะถูกส่งต่อไปยังโหนดปลายสุดเสมอ จากนั้นโหนดปลายสุดจะตรวจสอบว่าตารางเส้นทางเต็มหรือไม่ หากตารางเต็ม แสดงว่าระดับนั้นมีโหนดเต็มแล้ว และโหนดปลายสุดสามารถรับโหนดใหม่เป็นโหนดลูกเพื่อสร้างโหนดระดับใหม่ได้ หากตารางไม่เต็ม โหนดปลายสุดจะต้องส่งต่อโหนดใหม่เพื่อรับตำแหน่งว่างตำแหน่งใดตำแหน่งหนึ่ง

ในทางกลับกัน เมื่อโหนดต้องการออกจากเครือข่าย โหนดนั้นจะต้องอัปเดตตารางการกำหนดเส้นทางของโหนดแม่โหนดลูกโหนดที่อยู่ติดกัน และโหนดกำหนดเส้นทาง หากโหนดที่ออกจากเครือข่ายเป็นโหนดใบ โหนดนั้นก็สามารถออกจากเครือข่ายได้อย่างปลอดภัย อย่างไรก็ตาม หากไม่ใช่โหนดใบ โหนดนั้นจะต้องหาโหนดใบอื่นมาแทนที่

ใน BATON แต่ละโหนดจะรักษาพื้นที่คีย์ต่อเนื่องกัน เมื่อโหนดใหม่เข้าร่วมเป็นโหนดลูก โหนดนั้นจะแบ่งพื้นที่คีย์ของตนและจัดสรรครึ่งหนึ่งให้กับโหนดลูก วิธีการแบ่งส่วนนี้ช่วยให้สามารถสำรวจโครงสร้างต้นไม้ได้ตามลำดับจากน้อยไปมาก หากเราสำรวจต้นไม้ตามลำดับที่ถูกต้อง นี่คือเหตุผลที่ BATON รองรับการค้นหาแบบช่วง (range queries)

ในการดำเนินการค้นหาช่วงข้อมูล q นั้น BATON จะค้นหาขอบเขตด้านซ้ายก่อน คือ q.low จากนั้นกระบวนการค้นหาจะเดินทางไปตามโครงสร้างต้นไม้ตามลำดับ (โดยใช้ลิงก์ที่อยู่ติดกัน) จนกว่าจะถึงขอบเขตบน คือ q.up สำหรับการค้นหาคีย์เดียว BATON ใช้กลยุทธ์การกำหนดเส้นทางที่คล้ายกับChordโดยคำขอจะถูกส่งไปยังโหนดกำหนดเส้นทางที่ไกลที่สุดที่ไม่เกินคีย์นั้นก่อน หากไม่มีโหนดกำหนดเส้นทางดังกล่าวอยู่ ก็จะใช้ลิงก์หลัก ลิงก์ย่อย หรือลิงก์ที่อยู่ติดกันแทน

เมื่อโหนด x รับโหนด y เข้ามาเป็นลูก และตรวจพบว่าสมดุลของต้นไม้ถูกละเมิด มันจะเริ่มกระบวนการปรับโครงสร้างใหม่ โดยไม่เสียความเป็นทั่วไป เราจะสมมติว่าการปรับโครงสร้างนี้เป็นการปรับไปทางด้านขวา สมมติว่า y เข้าร่วมเป็นลูกซ้ายของ x เพื่อปรับสมดุลระบบ x จะแจ้งให้ y เข้ามาแทนที่ตำแหน่งของตน และแจ้งให้โหนดข้างเคียงทางขวา z ทราบว่า x จะเข้ามาแทนที่ตำแหน่งของ z จากนั้น z จะตรวจสอบโหนดข้างเคียงทางขวา t เพื่อดูว่าลูกซ้ายของมันว่างอยู่หรือไม่ ถ้าว่างอยู่ และการเพิ่มลูกให้กับ t ไม่ส่งผลกระทบต่อสมดุลของต้นไม้ z จะรับตำแหน่งของลูกซ้ายของ t เป็นตำแหน่งใหม่ และกระบวนการปรับโครงสร้างจะหยุดลง ถ้าลูกซ้ายของ t เต็ม หรือ t ไม่สามารถรับ x เป็นลูกซ้ายได้โดยไม่ละเมิดคุณสมบัติสมดุล z จะเข้ามาแทนที่ตำแหน่งของ t ในขณะที่ t ต้องหาตำแหน่งใหม่ให้กับตัวเองโดยการตรวจสอบโหนดข้างเคียงทางขวาต่อไป

BATON ใช้กลยุทธ์การกระจายภาระสองแบบ เมื่อโหนด n ตรวจพบว่ามีภาระมากเกินไป

1. หากโหนดที่อยู่ติดกันทางซ้ายหรือขวามีภาระงานเบา โหนดนี้จะถ่ายโอนข้อมูลบางส่วนไปยังโหนดที่อยู่ติดกันเพื่อลดภาระงานของตนเอง
2. หากโหนดข้างเคียงไม่สามารถแบ่งเบาภาระได้ โหนดนั้นจะเรียกใช้กระบวนการเพื่อค้นหาโหนดที่มีภาระงานเบาแบบสุ่มในเครือข่าย โหนดที่มีภาระงานเบาจะออกจากตำแหน่งเดิมและเข้าร่วมเป็นโหนดลูกของโหนดที่มีภาระงานมากเกินไปเพื่อรับช่วงต่อข้อมูลบางส่วน กระบวนการปรับโครงสร้างอาจถูกเรียกใช้

• BATON* - เครือข่ายโอเวอร์เลย์แบบต้นไม้ m-ary ที่สมดุล: ส่วนขยายของ BATON ที่เป็นต้นไม้ค้นหาแบบ m-ary ที่สมดุลความสูง พร้อมด้วยลิงก์เพิ่มเติมเพื่อเพิ่มประสิทธิภาพ ความทนทานต่อข้อผิดพลาด และการกระจายภาระงานอย่างสมดุล
• nBATON* - เครือข่ายโอเวอร์เลย์แบบต้นไม้ m-ary ที่สมดุลแบบ null: ส่วนขยายของ BATON* ที่เป็นต้นไม้ค้นหา m-ary ที่สมดุลแบบ null ซึ่งมีประสิทธิภาพดีขึ้นสูงสุดถึง 50% เมื่อเทียบกับจำนวนฮอปการกำหนดเส้นทางที่จำเป็น

• คอร์ด
• สามารถ
• ขนมอบ

• HV Jagadish ; Beng Chin Ooi; Quang Hieu Vu; Rong Zhang และ Aoying Zhou (2006). "VBI-Tree: กรอบงานแบบ Peer-to-Peer สำหรับรองรับรูปแบบการจัดทำดัชนีหลายมิติ" (PDF) . รายงานการประชุมวิศวกรรมข้อมูลนานาชาติครั้งที่ 22.หน้า 34. ISBN 0-7695-2570-9.
• HV Jagadish ; Beng Chin Ooi; Kian-Lee Tan; Quang Hieu Vu และ Rong Zhang (2006). "การเร่งความเร็วการค้นหาในเครือข่ายแบบ Peer-to-Peer ด้วยโครงสร้างต้นไม้แบบหลายทาง" (PDF) . รายงานการประชุมนานาชาติ ACM SIGMOD ว่าด้วยการจัดการข้อมูล ปี 2006.หน้า  1–12 . ISBN 1-59593-434-0.
• Shiyuan Wang; Beng Chin Ooi; Tung, AKH และ Lizhen Xu (2007). "การประมวลผลการค้นหา Skyline ที่มีประสิทธิภาพบนเครือข่าย Peer-to-Peer" (PDF) . รายงานการประชุมวิศวกรรมข้อมูลนานาชาติครั้งที่ 22.หน้า  1126–1135 . ISBN 978-1-4244-0803-0.
• A. Gonzalez-Beltran; P. Milligan & P. ​​Sage (2008). "การค้นหาช่วงบนกราฟต้นไม้ข้าม" (PDF) . Computer Communications . หน้า  358– 374. ISSN  0140-3664 .
• Peter Detzner; Jana Gödeke & Steffen Bondorf (2021). "การค้นหาต้นทุนต่ำในโอเวอร์เลย์ P2P โครงสร้างแบบต้นไม้: ประโยชน์ของสมดุลศูนย์" (ลิงก์)การประชุมเครือข่ายคอมพิวเตอร์ท้องถิ่นครั้งที่ 46 (LCN ) หน้า  358–374

• เว็บไซต์ของโครงการ BestPeer ถูกเก็บถาวรเมื่อวันที่ 19 มกราคม 2008 ที่Wayback Machine