الگوریتم افزایش جمعی/کاهش ضربی: چگونه کنترل تراکم TCP از نظر ریاضی کارایی را فدای عدالت میکند
اینترنت برای جلوگیری از گرهخوردگیهای فاجعهبار ترافیکی، به یک قانون ریاضی غیرمتمرکز متکی است. اگرچه الگوریتم AIMD پایداری شبکه را تضمین میکند، اما ذاتاً کاربران را بر اساس فاصله جغرافیایی جریمه میکند.
به قلم یاسر یوسفی
این خبر را به اشتراک بگذارید
- سنتگرایان پروتکل
- استدلال میکنند که سادگی AIMD و تضمین ریاضی پایداری شبکه، آن را به تنها پیشفرض امن برای یک اینترنت غیرمتمرکز تبدیل میکند.
- بهینهسازان عملکرد
- معتقدند که AIMD برای شبکههای مدرن و پرسرعت منسوخ شده است و از الگوریتمهای مبتنی بر تاخیر مانند BBR که ظرفیت واقعی را اندازهگیری میکنند، حمایت میکنند.
- تحلیلگران عدالت شبکه
- بر سوگیریهای ساختاری پروتکلهای شبکه تمرکز دارند و برجسته میکنند که چگونه الگوریتمهایی مانند AIMD از نظر ریاضی کاربران را بر اساس فاصله جغرافیایی جریمه میکنند.
دیدگاههایی که این گزارش پوشش نداده
- کاربران اینترنت پهنباند روستایی که به طور نامتناسبی تحت تاثیر جریمههای تاخیر قرار میگیرند
- ارائهدهندگان اینترنت ماهوارهای که محیطهایی با زمان رفتوبرگشت (RTT) بسیار بالا را مدیریت میکنند
نکات کلیدی
- اینترنت با استفاده از الگوریتم غیرمتمرکز AIMD، بدون نیاز به کنترلکننده مرکزی از گرهخوردگی ترافیک جلوگیری میکند.
- الگوریتم AIMD برای یافتن ظرفیت، سرعت انتقال را به آرامی افزایش میدهد و با از دست رفتن بستهها، سرعت را به نصف کاهش میدهد.
- اثباتهای ریاضی از سال ۱۹۸۹ نشان میدهند که AIMD تنها فرمولی است که هم کارایی و هم عدالت شبکه را تضمین میکند.
- از آنجا که این الگوریتم به زمان رفتوبرگشت متکی است، به طور ساختاری پهنای باند کمتری را به کاربرانی که از نظر فیزیکی از سرور دورتر هستند اختصاص میدهد.
- شبکههای مدرن با استفاده از شبکههای توزیع محتوا و الگوریتمهای جدیدتر مبتنی بر تاخیر مانند BBR گوگل، این جریمه جغرافیایی را دور میزنند.
شبکههای ترافیک بزرگراهی از طریق کنترلکنندههای مرکزی - مانند چراغهای راهنمای ورودی و توزیعکنندگان متمرکزی که کل سیستم را زیر نظر دارند و تعیین میکنند چه کسی و چه زمانی وارد شود - از گرهخوردگی جلوگیری میکنند. در مقابل، اینترنت بدون هیچ مرجع مرکزی کار میکند، اما حجم بسیار بیشتری از ترافیک را بدون فروپاشی مدیریت میکند. تنها وجه تمایز اینترنت با یک بزرگراه فیزیکی این است که کنترل ترافیک آن کاملاً غیرمتمرکز است و به یک قانون ریاضی متکی است که در هر دستگاه متصل تعبیه شده است: الگوریتم افزایش جمعی/کاهش ضربی (AIMD).[6]
ما استدلال میکنیم که AIMD موفقترین الگوریتم توزیعشده در تاریخ بشر است، اما موفقیت آن بر یک مصالحه ساختاری و شفاف استوار است. این الگوریتم از نظر ریاضی کارایی مطلق شبکه را فدا میکند تا تعریف خاصی از عدالت را تضمین کند. با این حال، همانطور که تحلیل ما از تاخیرهای ناهمگون شبکه نشان میدهد، این تعریف از عدالت ذاتاً کاربرانی را که از نظر فیزیکی از سرور دورتر هستند، مجازات میکند.[2][7]
برای درک اینکه چرا این مصالحه ضروری است، باید به گزینههای جایگزین نگاه کرد. در اکتبر ۱۹۸۶، اینترنت اولیه یک فروپاشی فاجعهبار ناشی از تراکم را تجربه کرد. با اشباع شدن شبکه، مسیریابها شروع به دور انداختن بستههای داده کردند. نقاط پایانی با این فرض که بستهها در مسیر گم شدهاند، فوراً آنها را دوباره ارسال کردند و دادههای بیشتری را به شبکهای که از قبل غرق در ترافیک بود سرازیر کردند. توان عملیاتی در یک پیوند ۳۲ کیلوبیت بر ثانیهای بین آزمایشگاه ملی لارنس برکلی و دانشگاه کالیفرنیا، برکلی به تنها ۴۰ بیت بر ثانیه سقوط کرد؛ یعنی یک افت ۹۹٫۸ درصدی.[4]
راهحلی که توسط پژوهشگری به نام ون جاکوبسون در سال ۱۹۸۸ معرفی شد، این بود که نقاط پایانی را نسبت به وضعیت شبکه پاسخگو کند، بدون اینکه نیازی باشد شبکه آن وضعیت را به صراحت مخابره کند. پیادهسازی جاکوبسون از کنترل تراکم TCP، بر از دست رفتن بسته به عنوان یک سیگنال ضمنی از تراکم متکی بود. وقتی بستهای دور انداخته میشود، فرستنده فرض میکند که شبکه پر است و سرعت خود را کاهش میدهد.[4][6]
مکانیسمی که بر این شتابگیری و کاهش سرعت حاکم است، همان AIMD است. فاز «افزایش جمعی» عملکرد اکتشافی الگوریتم است. به ازای هر زمان رفتوبرگشت (RTT) که بدون از دست رفتن بسته سپری میشود، فرستنده پنجره انتقال خود را دقیقاً به اندازه ۱ حداکثر اندازه قطعه افزایش میدهد. این امر منجر به افزایش کند و خطی در استفاده از پهنای باند میشود و شبکه را به آرامی برای یافتن ظرفیت خالی جستجو میکند.[4]
فاز «کاهش ضربی» ترمز اضطراری الگوریتم است. به محض اینکه بستهای گم میشود، فرستنده صرفاً یک قطعه از پنجره خود کم نمیکند؛ بلکه نرخ انتقال خود را دقیقاً ۵۰ درصد کاهش میدهد. این واکنش تهاجمی و غیرخطی همان چیزی است که از خرابیهای زنجیرهای سال ۱۹۸۶ جلوگیری کرده و صفهای متراکم مسیریابها را فوراً تخلیه میکند.[4][6]
انتخاب AIMD بر سایر ترکیبات ریاضی - مانند افزایش جمعی/کاهش جمعی (AIAD) یا افزایش ضربی/کاهش ضربی (MIMD) - تصادفی نبود. در یک مقاله جریانساز در سال ۱۹۸۹، پژوهشگرانی به نامهای داه-مینگ چیو و راج جین از نمودارهای فضای فاز استفاده کردند تا ثابت کنند AIMD تنها تابع کنترلی است که از نظر ریاضی همگرایی به سمت کارایی و عدالت را در میان جریانهای داده رقیب تضمین میکند.[3]
انتخاب AIMD بر سایر ترکیبات ریاضی - مانند افزایش جمعی/کاهش جمعی (AIAD) یا افزایش ضربی/کاهش ضربی (MIMD) - تصادفی نبود.
کارایی در این زمینه به این معناست که از ظرفیت کل شبکه به طور کامل استفاده میشود. عدالت به این معناست که ۲ نقطه پایانی که یک پیوند گلوگاهی مشترک دارند، در نهایت به سهم برابری از پهنای باند همگرا میشوند، فارغ از اینکه سرعت اولیهشان چقدر بوده است. همانطور که سند RFC 2914، سند بنیادین کارگروه مهندسی اینترنت در مورد کنترل تراکم، خاطرنشان میکند: «کنترل تراکم پیشنیاز ضروری برای عملکرد پایدار اینترنت است.»[1]
با این حال، قویترین استدلال متقابل در برابر نبوغ AIMD در تعریف آن از عدالت نهفته است. این الگوریتم زمان را بر اساس RTT اندازهگیری میکند؛ یعنی زمانی که طول میکشد تا یک بسته به مقصد برسد و تاییدیه آن بازگردد. از آنجا که «افزایش جمعی» در هر RTT یک قطعه اضافه میکند، جریانی با RTT کوتاهتر، سرعت خود را بسیار سریعتر از جریانی با RTT طولانیتر افزایش میدهد.[2][4]
این امر یک جریمه جغرافیایی ساختاری ایجاد میکند. بر اساس تحقیقات منتشر شده توسط موسسه پلیتکنیک فدرال لوزان (EPFL)، زمانی که ۲ جریان با RTTهای ناهمگون برای یک گلوگاه مشترک رقابت میکنند، الگوریتم AIMD پهنای باند را به نسبت معکوس تاخیر آنها تخصیص میدهد. کاربری در فاصله ۵۰۰۰ مایلی که به سروری در نیویورک متصل میشود، از نظر ریاضی توسط یک کاربر محلی که به همان سرور متصل است، از پهنای باند محروم خواهد شد.[2]
پژوهشگران EPFL خاطرنشان میکنند: «عدالت در AIMD به شدت نسبت به زمان رفتوبرگشت حساس است» و نشان میدهند که همگرایی نظری این الگوریتم تنها زمانی صادق است که تمام جریانهای رقیب فواصل جغرافیایی یکسانی داشته باشند. در دنیای واقعی، این بدان معناست که پروتکل به طور ساختاری ترافیک محلی را بر ترافیک جهانی ترجیح میدهد.[2]
این سوگیریِ تاخیر، پیامدهای عمیقی برای معماری شبکههای مدرن دارد. از آنجا که اینترنت برای پشتیبانی از ویدیوهای با کیفیت بالا و رایانش ابری درنگزمان گسترش یافته است، محدودیتهای AIMD به یک گلوگاه تبدیل شدهاند. سند RFC 6077 که مسائل پژوهشی باز در کنترل تراکم اینترنت را تشریح میکند، به صراحت بر چالش حفظ عدالت در محیطهای پرسرعت و با تاخیر بالا تاکید میکند.[5]
برای جبران جریمه جغرافیایی AIMD، صنعت فناوری میلیاردها دلار برای استقرار شبکههای توزیع محتوا (CDN) هزینه کرده است. شبکههای توزیع محتوا با ذخیره دادهها در فاصله فیزیکی نزدیکتر به کاربر نهایی، به طور مصنوعی RTT را کاهش میدهند و به فاز «افزایش جمعی» اجازه میدهند سریعتر شتاب بگیرد و سوگیری ساختاری الگوریتم را دور بزند.[6][7]
علاوه بر این، مهندسان شبکه به طور فزایندهای در حال کنار گذاشتن AIMD خالص به نفع الگوریتمهای مبتنی بر تاخیر هستند. الگوریتم BBR گوگل (پهنای باند گلوگاه و زمان انتشار رفتوبرگشت) که در سال ۲۰۱۶ معرفی شد، به جای تکیه بر از دست رفتن بسته به عنوان شاخصی برای تراکم، تلاش میکند ظرفیت واقعی شبکه را مدلسازی کند. الگوریتم BBR با اندازهگیری دقیق نرخ تحویل، میتواند توان عملیاتی بالایی را حتی در پیوندهای طولانیمدت حفظ کند.[6]
با این حال، علیرغم این نوآوریها، AIMD همچنان مکانیسم پیشفرض کنترل تراکم برای بخش اعظم زیرساخت اینترنت است. سادگی آن - که نیازی به محاسبات پیچیده یا هماهنگی متمرکز ندارد - آن را به طرز شگفتانگیزی مستحکم میکند. این گواهی بر قدرت الگوریتمهای توزیعشده است که چند خط کد نوشته شده در سال ۱۹۸۸، امروز همچنان از فروپاشی یک شبکه ارتباطی جهانی جلوگیری میکند.[4][6]
داستان AIMD درسی در ریاضیاتِ مصالحه است. این داستان ثابت میکند که در یک سیستم غیرمتمرکز، نمیتوانید همه چیز را بهینهسازی کنید. معماران اینترنت با انتخاب اولویت دادن به بقای شبکه بر عدالت مطلق جغرافیایی، سیستمی ساختند که آنقدر انعطافپذیر بود که از چند هزار رایانه دانشگاهی به میلیاردها دستگاه در سراسر جهان گسترش یابد.[1][7]
اصطلاحات کلیدی
- AIMD
- افزایش جمعی/کاهش ضربی؛ الگوریتمی که سرعت انتقال دادهها را به آرامی افزایش میدهد تا پهنای باند در دسترس را پیدا کند و در صورت تشخیص تراکم، آن را نصف میکند.
- زمان رفتوبرگشت (RTT)
- کل زمانی که طول میکشد تا یک بسته داده از فرستنده به گیرنده برسد و تاییدیه آن بازگردد.
- از دست رفتن بسته
- زمانی که دادهها به مقصد نمیرسند، معمولاً به این دلیل که یک مسیریاب در طول مسیر غرق در ترافیک شده و مجبور است ترافیک ورودی را دور بیندازد.
- نمودار فضای فاز
- یک نمودار ریاضی که توسط پژوهشگران استفاده میشود تا ثابت کنند جریانهای مختلف داده در نهایت به سهم برابری از پهنای باند همگرا خواهند شد.
بررسی عمیق دیدگاهها
سنتگرایان پروتکل
استدلال میکنند که سادگی AIMD پایه و اساس انعطافپذیری اینترنت است.
برای معماران شبکه و سنتگرایان پروتکل، نبوغ AIMD در غیرمتمرکز بودن مطلق آن نهفته است. الگوریتم AIMD با تکیه بر از دست رفتن بسته - یک واقعیت فیزیکی از یک شبکه پر - به عنوان تنها سیگنال مورد نیاز خود، به هیچ ارتباط پیچیدهای بین مسیریابها و رایانهها نیاز ندارد. این گروه استدلال میکنند که اگرچه این الگوریتم ممکن است هر پیوند پرسرعتی را به طور کامل بهینه نکند، اما تضمین ریاضی آن در برابر فروپاشی ناشی از تراکم، تنها دلیلی است که اینترنت با موفقیت از یک پروژه کوچک دانشگاهی به یک ابزار جهانی گسترش یافت.
بهینهسازان عملکرد
معتقدند که الگوریتمهای مبتنی بر از دست رفتن بسته اساساً برای شبکههای فیبر نوری مدرن نامناسب هستند.
مهندسانی که بر به حداکثر رساندن عملکرد شبکههای مدرن تمرکز دارند، استدلال میکنند که AIMD یادگاری از دهه ۱۹۸۰ است. از آنجا که AIMD نیاز دارد تا یک بسته دور انداخته شود تا بفهمد شبکه پر است، عمداً گلوگاه ایجاد میکند. علاوه بر این، در پیوندهای جهانی پرسرعت، بازیابی از یک کاهش سرعت ۵۰ درصدی زمان زیادی میبرد و مقادیر عظیمی از پهنای باند را بلااستفاده میگذارد. این گروه از الگوریتمهای مبتنی بر تاخیر مانند BBR حمایت میکنند که سرعت واقعی تحویل دادهها را اندازهگیری کرده و بدون انتظار برای خرابی شبکه، به نرمی تنظیم میشوند.
تحلیلگران عدالت شبکه
برجسته میکنند که چگونه ریاضیات AIMD به طور ساختاری کاربران دورافتاده و روستایی را در مضیقه قرار میدهد.
پژوهشگرانی که تاثیر اجتماعی پروتکلهای شبکه را بررسی میکنند، خاطرنشان میسازند که اتکای AIMD به زمان رفتوبرگشت (RTT) یک جریمه جغرافیایی اجتنابناپذیر ایجاد میکند. از آنجا که این الگوریتم سرعت را بر اساس سرعت بازگشت تاییدیهها افزایش میدهد، کاربرانی که از نظر فیزیکی به مراکز داده نزدیکتر هستند، هنگام رقابت با کاربران دورتر، از نظر ریاضی اکثریت پهنای باند موجود را مصرف خواهند کرد. این گروه استدلال میکنند که تعریف پروتکل از «عدالت» ذاتاً سوگیرانه است و شرکتها را مجبور میکند تا شبکههای توزیع محتوای گرانقیمتی بسازند تا فواصل را به طور مصنوعی کوتاه کرده و شرایط را برابر کنند.
چرا مهم است
هر بار که ویدیویی تماشا میکنید یا صفحهای را بارگذاری میکنید، یک فرمول ریاضی ۳۸ ساله دقیقاً تعیین میکند که مجاز به استفاده از چه مقدار پهنای باند هستید. درک نحوه کارکرد این الگوریتم نشان میدهد که چرا فاصله فیزیکی هنوز هم سرعت دیجیتال را دیکته میکند و چرا اینترنت زیر بار تقاضای دادههای مدرن فرو نپاشیده است.
منابع
پوشش منابع
7 منبع
3 دیدگاه شناساییشده
- [1]IETF Datatrackerسنتگرایان پروتکل
RFC 2914 - Congestion Control Principles
مطالعه در IETF Datatracker → - [2]Infoscience - EPFLتحلیلگران عدالت شبکه
Global fairness of additive–increase and multiplicative–decrease with heterogeneous round–trip times
مطالعه در Infoscience - EPFL → - [3]ResearchGateتحلیلگران عدالت شبکه
A Note on the Fairness of Additive Increase and Multiplicative Decrease
مطالعه در ResearchGate → - [4]UC Berkeleyسنتگرایان پروتکل
Congestion Control Design
مطالعه در UC Berkeley → - [5]IETF Datatrackerسنتگرایان پروتکل
RFC 6077: Open Research Issues in Internet Congestion Control
مطالعه در IETF Datatracker → - [6]Wikipediaبهینهسازان عملکرد
TCP congestion control
مطالعه در Wikipedia → - [7]تیم سردبیری کوهستانتحلیلگران عدالت شبکه
تحلیل تیم سردبیری کوهستان
مطالعه در تیم سردبیری کوهستان →
نظرات
بیشتر در دیدگاهها
مشاهده همه →پروتکلهای اجماع
الزام 3f+1: چرا اجماع توزیعشده از نظر ریاضی به بیش از دو سوم نودهای صادق نیاز دارد
7 منبع
علوم شناختی
بوتاسترپینگ دیالکتیکی: چگونه تحمیل اختلافنظر درونی، قضاوت فردی را به لحاظ ریاضی بهبود میبخشد
4 منبع
سیاست فناوری مدارس
موج جهانی مدارس بدون موبایل: شواهد درباره پیامدهای تحصیلی و اجتماعی چه میگویند؟
3 منبع
تجارت جهانی
آیا فروپاشی هیئت استیناف سازمان تجارت جهانی رسماً به نظام تجارت جهانی مبتنی بر قانون پایان داده است؟
3 منبع
هر زاویه. هر روز.
دریافت دیدگاهها اخبار همراه با پوشش کامل منابع و تحلیل دیدگاهها، مستقیم در صندوق ورودی شما.