الگوریتم‌هایی که برای اطمینان از اشتراک‌گذاری چند کاربر در یک شبکه طراحی شده‌اند، نمی‌توانند مانع از افزایش پهنای باند برخی از کاربران شوند. — ScienceDaily

محققان مدل ریاضی خود را به یک کامپیوتر داده، یک سری از الگوریتم‌های رایج کنترل تراکم را به آن دادند و از رایانه خواستند تا الگوریتمی را پیدا کند که بتواند با استفاده از مدل آنها از گرسنگی جلوگیری کند.

کنترل ازدحام

علیزاده این مقاله را با نویسنده اول و دانشجوی فارغ التحصیل EECS ونکات آرون و نویسنده ارشد، هاری بالاکریشنان، استاد علوم کامپیوتر و هوش مصنوعی فوجیتسو نوشت. این تحقیق در کنفرانس ACM Special Interest Group on Data Communications (SIGCOMM) ارائه خواهد شد.

در طول دهه گذشته، محققان در صنعت و دانشگاه الگوریتم‌های متعددی را توسعه داده‌اند که تلاش می‌کنند ضمن کنترل تاخیرها، به نرخ‌های بالا دست یابند. برخی از اینها مانند الگوریتم BBR توسعه یافته توسط گوگل، اکنون به طور گسترده توسط بسیاری از وب سایت ها و برنامه ها استفاده می شود.

“ما نتوانستیم این کار را انجام دهیم. هر الگوریتمی را که از آن آگاه بودیم و تعدادی الگوریتم جدید ساختیم. آرون می گوید.

حتی اگر یک الگوریتم کنترل تراکم تاخیر را به طور کامل اندازه گیری کند، نمی تواند تفاوت بین تاخیر ناشی از تراکم و تاخیر ناشی از جیتر را تشخیص دهد. تاخیر ناشی از جیتر غیرقابل پیش بینی است و فرستنده را سردرگم می کند. به دلیل این ابهام، کاربران شروع به تخمین تاخیر متفاوتی می کنند که باعث می شود بسته ها را با نرخ های نابرابر ارسال کنند. آرون توضیح می‌دهد که در نهایت، این منجر به وضعیتی می‌شود که در آن گرسنگی رخ می‌دهد و شخصی کاملاً بسته می‌شود.

مطالعه گرسنگی

آرون اضافه می‌کند که این واقعیت که چنین حالت‌های شکست ساده این الگوریتم‌های پرکاربرد برای مدت طولانی ناشناخته مانده بودند، نشان می‌دهد که درک الگوریتم‌ها تنها از طریق آزمایش تجربی چقدر دشوار است. این بر اهمیت یک پایه نظری محکم تأکید می کند.

برای کنترل تاخیرها، الگوریتم‌ها سعی کرده‌اند تغییرات تاخیر را در مورد تعادل مورد نظر نیز محدود کنند، اما هیچ اشکالی در ایجاد تغییرات تاخیر بیشتر برای اندازه‌گیری بهتر تاخیرهای احتقانی وجود ندارد. این فقط یک فلسفه طراحی جدید است که باید انجام دهید. بالاکریشنان اضافه می کند.

محققان از این نتیجه شگفت زده شدند، به ویژه از آنجایی که این الگوریتم ها به طور گسترده ای منصفانه هستند. آنها شروع به شک کردند که ممکن است امکان اجتناب از گرسنگی وجود نداشته باشد، شکلی شدید از بی عدالتی. این امر آنها را برانگیخت تا کلاسی از الگوریتم‌ها را تعریف کنند که آنها را «الگوریتم‌های تأخیر همگرا» می‌نامند که ثابت کردند تحت مدل شبکه‌شان همیشه از گرسنگی رنج می‌برند. همه الگوریتم‌های کنترل تراکم موجود که تاخیر را کنترل می‌کنند (که محققین از آن آگاه هستند) تاخیر-همگرا هستند.

وقتی کاربران بخواهند داده‌ها را سریع‌تر از توان شبکه از طریق اینترنت ارسال کنند، ازدحام می‌تواند رخ دهد — به همان شیوه‌ای که ازدحام ترافیک در رفت و آمد صبحگاهی به یک شهر بزرگ غوغا می‌کند.

منبع

رایانه‌ها و دستگاه‌هایی که داده‌ها را از طریق اینترنت انتقال می‌دهند، داده‌ها را به بسته‌های کوچک‌تر تقسیم می‌کنند و از یک الگوریتم ویژه برای تصمیم‌گیری درباره سرعت ارسال آن بسته‌ها استفاده می‌کنند. این الگوریتم‌های کنترل تراکم به دنبال کشف و استفاده کامل ظرفیت شبکه در دسترس هستند و در عین حال آن را به طور منصفانه با سایر کاربرانی که ممکن است همان شبکه را به اشتراک بگذارند به اشتراک بگذارند. این الگوریتم ها سعی می کنند تاخیر ناشی از انتظار داده ها در صف های شبکه را به حداقل برسانند.

در حالی که علیزاده و همکارانش نتوانستند یک الگوریتم سنتی کنترل تراکم را پیدا کنند که بتواند از گرسنگی جلوگیری کند، ممکن است الگوریتم‌هایی در کلاس دیگری وجود داشته باشد که بتواند از این مشکل جلوگیری کند. تجزیه و تحلیل آنها همچنین نشان می‌دهد که تغییر نحوه عملکرد این الگوریتم‌ها، به طوری که تغییرات بزرگ‌تری در تاخیر ایجاد کنند، می‌تواند به جلوگیری از گرسنگی در برخی موقعیت‌های شبکه کمک کند.

کنترل تراکم یک مشکل اساسی در شبکه است که محققان از دهه 1980 سعی در حل آن داشتند.

اما تیمی از محققان MIT کشف کرده‌اند که این الگوریتم‌ها می‌توانند عمیقاً ناعادلانه باشند. در یک مطالعه جدید، آنها نشان می دهند که همیشه سناریوی شبکه ای وجود دارد که در آن حداقل یک فرستنده تقریباً هیچ پهنای باندی در مقایسه با سایر فرستنده ها دریافت نمی کند. یعنی مشکلی که به عنوان گرسنگی شناخته می شود قابل اجتناب نیست.

اکنون، محققان می‌خواهند به تلاش ادامه دهند تا ببینند آیا می‌توانند الگوریتمی را بیابند یا بسازند که گرسنگی را از بین ببرد. آنها همچنین می‌خواهند این رویکرد مدل‌سازی ریاضی و اثبات محاسباتی را برای سایر مسائل حل‌نشده و پیچیده در سیستم‌های شبکه‌ای اعمال کنند.

الگوریتم‌های کنترل ازدحام از تلفات و تأخیرهای بسته به عنوان سیگنال‌هایی برای استنباط ازدحام و تصمیم‌گیری درباره سرعت ارسال داده‌ها استفاده می‌کنند. اما اینترنت پیچیده است و بسته ها می توانند به دلایلی غیرمرتبط با ازدحام شبکه به تاخیر بیفتند و گم شوند. به عنوان مثال، داده ها ممکن است در یک صف در طول مسیر نگه داشته شوند و سپس با انبوهی از بسته های دیگر منتشر شوند، یا ممکن است تایید گیرنده به تأخیر بیفتد. نویسندگان تأخیرهایی را که به دلیل ازدحام ایجاد نمی‌شوند «جیت» می‌نامند.

اما تمام امید از بین نرفته. در حالی که همه الگوریتم‌هایی که آزمایش کردند شکست خوردند، ممکن است الگوریتم‌های دیگری وجود داشته باشند که همگرا با تاخیر نیستند که می‌توانند از گرسنگی جلوگیری کنند. بنابراین محدوده بزرگتر از هر تاخیری است که ممکن است به دلیل لرزش در شبکه رخ دهد.

ما این پروژه را شروع کردیم زیرا درک نظری از رفتار کنترل تراکم در حضور جیتر نداشتیم. برای قرار دادن آن در یک پایه نظری محکم تر، یک مدل ریاضی ساختیم که به اندازه کافی ساده بود که بتوان درباره آن فکر کرد، در عین حال می توانست برخی از موارد را به تصویر بکشد. پیچیدگی‌های اینترنت بسیار لذت بخش بوده است که ریاضی چیزهایی را به ما می‌گوید که نمی‌دانستیم و ارتباط عملی دارند.»

رایانه کاربر نمی داند با چه سرعتی بسته های داده را از طریق شبکه ارسال کند، زیرا فاقد اطلاعاتی مانند کیفیت اتصال شبکه یا تعداد فرستنده های دیگر است که از شبکه استفاده می کنند. ارسال بسته ها به آرامی باعث استفاده ضعیف از پهنای باند موجود می شود. اما ارسال خیلی سریع آنها می تواند شبکه را تحت الشعاع قرار دهد و با انجام این کار، بسته ها شروع به حذف می کنند. این بسته ها باید دوباره ارسال شوند که منجر به تاخیرهای طولانی تری می شود. تاخیر همچنین می تواند ناشی از انتظار بسته های طولانی مدت در صف باشد.