นักวิจัยค้นพบสิ่งกีดขวางบนถนนที่สำคัญในการบรรเทาความแออัดของเครือข่าย

เมื่อผู้ใช้ต้องการส่งข้อมูลผ่านอินเทอร์เน็ตได้เร็วกว่าที่เครือข่ายสามารถจัดการได้ ความแออัดอาจเกิดขึ้นได้ เช่นเดียวกับการจราจรที่คับคั่งในช่วงเช้าเมื่อต้องเดินทางไปในเมืองใหญ่

คอมพิวเตอร์และอุปกรณ์ที่ส่งข้อมูลผ่านอินเทอร์เน็ตจะแบ่งข้อมูลออกเป็นแพ็กเก็ตที่เล็กกว่าและใช้อัลกอริธึมพิเศษเพื่อตัดสินใจว่าจะส่งแพ็กเก็ตเหล่านั้นเร็วแค่ไหน อัลกอริธึมการควบคุมความแออัดเหล่านี้พยายามค้นหาและใช้ความจุของเครือข่ายที่มีอยู่อย่างเต็มที่ในขณะที่แบ่งปันกับผู้ใช้รายอื่นอย่างยุติธรรมซึ่งอาจใช้เครือข่ายเดียวกัน อัลกอริธึมเหล่านี้พยายามลดความล่าช้าที่เกิดจากข้อมูลที่รอคิวในเครือข่ายให้น้อยที่สุด

ในช่วงทศวรรษที่ผ่านมา นักวิจัยในอุตสาหกรรมและสถาบันการศึกษาได้พัฒนาอัลกอริธึมหลายอย่างที่พยายามบรรลุอัตราที่สูงในขณะที่ควบคุมความล่าช้า บางส่วนเหล่านี้ เช่น อัลกอริทึม BBR ที่พัฒนาโดย Google ปัจจุบันมีเว็บไซต์และแอปพลิเคชันจำนวนมากใช้กันอย่างแพร่หลาย

แต่ทีมนักวิจัยของ MIT ได้ค้นพบว่าอัลกอริธึมเหล่านี้อาจไม่ยุติธรรมอย่างยิ่ง ในการศึกษาใหม่ พวกเขาแสดงให้เห็นว่าจะมีสถานการณ์เครือข่ายอยู่เสมอ โดยที่ผู้ส่งอย่างน้อยหนึ่งรายได้รับแบนด์วิดธ์แทบไม่มีเลยเมื่อเทียบกับผู้ส่งรายอื่น นั่นคือปัญหาที่เรียกว่าความอดอยากไม่สามารถหลีกเลี่ยงได้

“สิ่งที่น่าประหลาดใจจริงๆ เกี่ยวกับบทความนี้และผลลัพธ์ก็คือ เมื่อคุณคำนึงถึงความซับซ้อนในโลกแห่งความเป็นจริงของเส้นทางเครือข่ายและทุกสิ่งที่พวกเขาสามารถทำได้กับแพ็กเก็ตข้อมูล แทบเป็นไปไม่ได้เลยที่อัลกอริธึมการควบคุมความแออัดของการควบคุมความล่าช้าจะหลีกเลี่ยง ความอดอยากโดยใช้วิธีการในปัจจุบัน” Mohammad Alizadeh รองศาสตราจารย์ด้านวิศวกรรมไฟฟ้าและวิทยาการคอมพิวเตอร์ (EECS) กล่าว

แม้ว่า Alizadeh และผู้เขียนร่วมของเขาไม่พบอัลกอริธึมการควบคุมความแออัดแบบดั้งเดิมที่สามารถหลีกเลี่ยงความอดอยาก แต่อาจมีอัลกอริทึมในประเภทอื่นที่สามารถป้องกันปัญหานี้ได้ การวิเคราะห์ของพวกเขายังชี้ให้เห็นว่าการเปลี่ยนแปลงวิธีการทำงานของอัลกอริธึมเหล่านี้ เพื่อให้สามารถเปลี่ยนแปลงได้มากขึ้นในความล่าช้า สามารถช่วยป้องกันความอดอยากในบางสถานการณ์ของเครือข่ายได้

Alizadeh เขียนบทความร่วมกับผู้เขียนคนแรกและนักศึกษาระดับบัณฑิตศึกษาของ EECS Venkat Arun และผู้เขียนอาวุโส Hari Balakrishnan ศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์และปัญญาประดิษฐ์ของ Fujitsu งานวิจัยนี้จะนำเสนอในการประชุม ACM Special Interest Group on Data Communications (SIGCOMM)

ควบคุมความแออัด

การควบคุมความแออัดเป็นปัญหาพื้นฐานในการสร้างเครือข่ายที่นักวิจัยพยายามแก้ไขมาตั้งแต่ปี 1980

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

อัลกอริธึมการควบคุมความแออัดใช้การสูญเสียแพ็กเก็ตและความล่าช้าเป็นสัญญาณเพื่อสรุปความแออัดและตัดสินใจว่าจะส่งข้อมูลได้เร็วแค่ไหน แต่อินเทอร์เน็ตนั้นซับซ้อน และแพ็กเก็ตอาจล่าช้าและสูญหายได้ด้วยเหตุผลที่ไม่เกี่ยวข้องกับความแออัดของเครือข่าย ตัวอย่างเช่น ข้อมูลอาจถูกจัดเก็บไว้ในคิวระหว่างทางแล้วปล่อยพร้อมกับแพ็กเก็ตอื่นๆ จำนวนมาก หรือการรับรู้ของผู้รับอาจล่าช้า ผู้เขียนเรียกความล่าช้าที่ไม่ได้เกิดจากความแออัด “กระวนกระวายใจ”

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

“เราเริ่มโครงการนี้เนื่องจากเราขาดความเข้าใจเชิงทฤษฎีเกี่ยวกับพฤติกรรมการควบคุมความแออัดเมื่อเกิดความกระวนกระวายใจ เพื่อวางไว้บนพื้นฐานทางทฤษฎีที่แน่นแฟ้นยิ่งขึ้น เราได้สร้างแบบจำลองทางคณิตศาสตร์ที่ง่ายพอที่จะคิดได้ แต่สามารถจับภาพความซับซ้อนบางอย่างของอินเทอร์เน็ตได้ เป็นเรื่องที่คุ้มค่ามากที่คณิตศาสตร์บอกเราถึงสิ่งที่เราไม่รู้และมีประโยชน์ในทางปฏิบัติ” เขากล่าว

เรียนความหิว

นักวิจัยได้ป้อนแบบจำลองทางคณิตศาสตร์ของพวกเขาไปยังคอมพิวเตอร์ ให้ชุดของอัลกอริธึมควบคุมความแออัดที่ใช้กันทั่วไป และขอให้คอมพิวเตอร์ค้นหาอัลกอริทึมที่สามารถหลีกเลี่ยงความอดอยากโดยใช้แบบจำลองของพวกเขา

“เราไม่สามารถทำมันได้ เราได้ลองทุกอัลกอริธึมที่เรารู้จัก และอัลกอริธึมใหม่ๆ ที่เราสร้างขึ้น ไม่มีอะไรทำงาน คอมพิวเตอร์มักพบสถานการณ์ที่บางคนได้รับแบนด์วิดท์ทั้งหมดและอย่างน้อยหนึ่งคนไม่ได้รับอะไรเลย” อรุณกล่าว

นักวิจัยรู้สึกประหลาดใจกับผลลัพธ์นี้ โดยเฉพาะอย่างยิ่งเนื่องจากอัลกอริธึมเหล่านี้เชื่อกันอย่างกว้างขวางว่ามีความยุติธรรมพอสมควร พวกเขาเริ่มสงสัยว่าอาจเป็นไปไม่ได้ที่จะหลีกเลี่ยงความอดอยาก ซึ่งเป็นรูปแบบที่ไม่เป็นธรรมอย่างสุดโต่ง สิ่งนี้กระตุ้นให้พวกเขากำหนดคลาสของอัลกอริธึมที่พวกเขาเรียกว่า “อัลกอริธึมการบรรจบกันที่ล่าช้า” ซึ่งพวกเขาพิสูจน์แล้วว่าจะต้องทนทุกข์ทรมานจากความอดอยากภายใต้โมเดลเครือข่ายของพวกเขา อัลกอริธึมการควบคุมความแออัดที่มีอยู่ทั้งหมดที่ควบคุมความล่าช้า

ความจริงที่ว่าโหมดความล้มเหลวอย่างง่ายของอัลกอริธึมที่ใช้กันอย่างแพร่หลายเหล่านี้ยังไม่เป็นที่ทราบมานานแล้วแสดงให้เห็นว่าการเข้าใจอัลกอริธึมนั้นยากเพียงใดผ่านการทดสอบเชิงประจักษ์เพียงอย่างเดียว Arun กล่าวเสริม เน้นย้ำถึงความสำคัญของรากฐานทางทฤษฎีที่มั่นคง

แต่ความหวังทั้งหมดจะไม่สูญหาย แม้ว่าอัลกอริธึมทั้งหมดที่พวกเขาทดสอบจะล้มเหลว อาจมีอัลกอริธึมอื่นที่ไม่เกิดการลู่เข้า-มาบรรจบกันที่อาจหลีกเลี่ยงความอดอยากได้ ซึ่งแสดงให้เห็นว่าวิธีหนึ่งในการแก้ไขปัญหาคือการออกแบบอัลกอริธึมการควบคุมความแออัดที่แปรผันช่วงการหน่วงให้กว้างขึ้น ดังนั้นช่วงจึงมากกว่าการหน่วงเวลาใดๆ ที่อาจเกิดขึ้นเนื่องจากความกระวนกระวายใจในเครือข่าย

“เพื่อควบคุมความล่าช้า อัลกอริธึมได้พยายามผูกมัดการเปลี่ยนแปลงในความล่าช้าเกี่ยวกับสมดุลที่ต้องการ แต่ก็ไม่มีอะไรผิดปกติที่อาจสร้างรูปแบบการหน่วงเวลาที่มากขึ้นเพื่อให้ได้การวัดที่ดีขึ้นของความล่าช้าที่แออัด มันเป็นเพียงปรัชญาการออกแบบใหม่ที่คุณต้องยอมรับ” Balakrishnan กล่าวเสริม

ตอนนี้ นักวิจัยต้องการที่จะผลักดันต่อไปเพื่อดูว่าพวกเขาสามารถค้นหาหรือสร้างอัลกอริธึมที่จะขจัดความอดอยากได้หรือไม่ พวกเขายังต้องการใช้แนวทางของการสร้างแบบจำลองทางคณิตศาสตร์และการพิสูจน์การคำนวณกับปัญหาอื่นๆ ที่ยุ่งยากและยังไม่ได้แก้ไขในระบบเครือข่าย

“เราพึ่งพาระบบคอมพิวเตอร์มากขึ้นสำหรับสิ่งที่มีความสำคัญอย่างยิ่ง และเราจำเป็นต้องวางความน่าเชื่อถือของระบบคอมพิวเตอร์ไว้บนรากฐานของแนวคิดที่แน่นแฟ้นยิ่งขึ้น เราได้แสดงสิ่งที่น่าประหลาดใจที่คุณสามารถค้นพบได้เมื่อคุณใช้เวลาเพื่อสร้างข้อกำหนดที่เป็นทางการเหล่านี้ว่าปัญหาคืออะไร” Alizadeh กล่าว

หน้าแรก