Naukowcy odkrywają główne wąskie gardło w łagodzeniu przeciążenia sieci | Aktualności MIT

Gdy użytkownicy chcą przesyłać dane przez Internet szybciej, niż jest w stanie obsłużyć sieć, mogą wystąpić zatory – w taki sam sposób, w jaki zatory uliczne w godzinach porannych dojeżdżają do dużego miasta.

Komputery i urządzenia przesyłające dane przez Internet dzielą je na mniejsze pakiety i używają specjalnego algorytmu, aby określić, jak szybko te pakiety mogą być przesyłane. Te algorytmy kontroli przeciążenia starają się odkryć i w pełni wykorzystać dostępną przepustowość sieci, jednocześnie sprawiedliwie dzieląc ją z innymi użytkownikami, którzy mogą współdzielić tę samą sieć. Algorytmy te starają się zmniejszyć opóźnienie spowodowane oczekiwaniem na dane w kolejkach w sieci.

W ciągu ostatniej dekady naukowcy z przemysłu i środowisk akademickich opracowali wiele algorytmów, które próbują osiągnąć wysokie wskaźniki przy jednoczesnym kontrolowaniu opóźnień. Niektóre z tych algorytmów, takie jak algorytm BBR opracowany przez Google, są obecnie szeroko stosowane w wielu witrynach i aplikacjach.

Jednak zespół naukowców z MIT odkrył, że te algorytmy mogą być bardzo niesprawiedliwe. W nowym badaniu pokazują, że zawsze będzie istniał scenariusz sieciowy, w którym co najmniej jeden nadajnik nie otrzyma prawie żadnej przepustowości w porównaniu z innymi nadajnikami; Oznacza to, że nie da się uniknąć problemu zwanego głodem.

„To, co jest naprawdę zaskakujące w tym artykule i wynikach, to fakt, że biorąc pod uwagę realistyczną złożoność ścieżek sieciowych i wszystkie rzeczy, które można zrobić z pakietami danych, zasadniczo niemożliwe jest uniknięcie algorytmów kontroli przeciążenia w celu kontrolowania opóźnienia ”, mówi Mohammad Alizadeh, profesor nadzwyczajny elektrotechniki i informatyki (EECS): „Głodzenie przy użyciu obecnych metod”.

Chociaż Alizadeh i współpracownicy nie byli w stanie znaleźć tradycyjnego algorytmu kontroli przeciążenia, który mógłby uniknąć głodu, mogą istnieć algorytmy z innej klasy, które mogą zapobiec temu problemowi. Ich analiza sugeruje również, że zmiana sposobu działania tych algorytmów, pozwalająca na większe zmiany opóźnień, może pomóc w zapobieganiu głodowi w niektórych sytuacjach sieciowych.

Alizadeh napisała artykuł z pierwszym autorem i absolwentem EECS Venkatem Arunem oraz starszym autorem Harrym Balakrishnanem, profesorem informatyki i sztucznej inteligencji Fujitsu. Wyniki badań zostaną zaprezentowane na konferencji ACM Special Interest Group Conference on Data Communications (SIGCOMM).

kontrola zatorów

Kontrola przeciążenia to podstawowy problem sieciowy, którym badacze próbują rozwiązać od lat 80. XX wieku.

Komputer użytkownika nie wie, jak szybko pakiety danych są przesyłane przez sieć, ponieważ brakuje mu informacji, takich jak jakość połączenia sieciowego czy liczba innych nadawców korzystających z sieci. Zbyt wolne wysyłanie pakietów powoduje niewłaściwe wykorzystanie dostępnej przepustowości. Ale wysyłanie go zbyt szybko może przeciążyć sieć, a tym samym zacznie odrzucać pakiety. Pakiety te powinny zostać wysłane ponownie, co skutkuje dłuższymi opóźnieniami. Opóźnienia mogą również wystąpić z powodu pakietów oczekujących w kolejce przez długi czas.

Algorytmy kontroli przeciążenia wykorzystują utratę pakietów i opóźnienia jako sygnały do ​​wywnioskowania przeciążenia i określenia szybkości transmisji danych. Jednak Internet jest złożony, a pakiety mogą być opóźnione i utracone z przyczyn niezwiązanych z przeciążeniem sieci. Na przykład dane mogą być przechowywane w kolejce po drodze, a następnie uwalniane z grupą innych pakietów lub potwierdzenie odbiorcy może być opóźnione. Autorzy nazywają opóźnienia, które nie są spowodowane zatorem, „drżeniem”.

Nawet jeśli algorytm kontroli przeciążenia mierzy opóźnienie całkowicie, nie może odróżnić opóźnienia wywołanego przeciążeniem od opóźnienia wywołanego jitterem. Opóźnienie spowodowane jitterem jest nieprzewidywalne i dezorientuje nadawcę. Z powodu tej niejednoznaczności użytkownicy zaczynają inaczej szacować opóźnienie, co powoduje, że wysyłają pakiety z nierówną szybkością. Ostatecznie, wyjaśnia Aaron, prowadzi to do sytuacji, w której następuje głód i człowiek zostaje całkowicie zamknięty.

„Rozpoczęliśmy projekt, ponieważ brakowało nam teoretycznego zrozumienia zachowania kontroli tłumu w obecności napięcia. Aby postawić go na bardziej stabilnych podstawach teoretycznych, zbudowaliśmy model matematyczny, który był wystarczająco prosty do przemyślenia, ale był w stanie uchwycić niektóre zawiłości Internetu. Bardzo satysfakcjonujące było dla Ciebie opowiadanie nam o matematyce o rzeczach, o których nie wiedzieliśmy, a które mają praktyczne znaczenie” – mówi.

Studium głodu

Naukowcy przesłali swój model matematyczny do komputera, przekazali mu serię powszechnie stosowanych algorytmów kontroli zatłoczenia i poprosili komputer o znalezienie algorytmu, który mógłby uniknąć głodu przy użyciu ich modelu.

„Nie mogliśmy tego zrobić. Wypróbowaliśmy każdy algorytm, który znaliśmy, i kilka nowych algorytmów, które wymyśliliśmy. Nic nie działało. Komputer zawsze znajdował sytuację, w której niektórzy ludzie uzyskują pełną przepustowość, a przynajmniej jedna osoba nic nie otrzymuje”. mówi Aron.

Naukowcy byli zaskoczeni tym odkryciem, zwłaszcza że algorytmy te są powszechnie uważane za dość sprawiedliwe. Zaczęli podejrzewać, że nie da się uniknąć głodu, skrajnej formy niesprawiedliwości. To skłoniło ich do zdefiniowania klasy algorytmów, które nazywają „zbieżnymi algorytmami opóźnienia”, które, jak udowodnili, zawsze będą głodować w ich modelu sieciowym. Wszystkie obecne algorytmy kontroli przeciążenia, które kontrolują opóźnienie (którego badacze są świadomi) są zbieżne.

Aaron dodaje, że fakt, iż proste tryby awarii tych szeroko stosowanych algorytmów przez tak długi czas pozostawały nieznane, pokazuje, jak trudno jest zrozumieć algorytmy wyłącznie na podstawie testów empirycznych. Podkreśla znaczenie solidnych podstaw teoretycznych.

Ale nadzieja jest wciąż stracona. Chociaż wszystkie testowane algorytmy zawiodły, mogą istnieć inne niekonwergentne algorytmy, które mogą być w stanie uniknąć głodu.Sugeruje to, że jednym ze sposobów rozwiązania problemu może być zaprojektowanie algorytmów kontroli przeciążenia, które zmieniają szerzej zakres opóźnienia. zasięg jest większy niż jakiekolwiek opóźnienie, które może wystąpić z powodu niestabilności sieci.

„Aby kontrolować opóźnienia, algorytmy próbowały również skorelować różnice opóźnień wokół pożądanego balansu, ale nie ma nic złego w tworzeniu większego kontrastu opóźnienia, aby uzyskać lepsze pomiary opóźnienia zastoinowego. To po prostu nowa filozofia projektowania, którą musisz przyjąć ”, dodaje Balakrishnan.

Teraz naukowcy chcą dalej naciskać, aby sprawdzić, czy uda im się znaleźć lub zbudować algorytm, który wyeliminuje głód. Chcą również zastosować to podejście modelowania matematycznego i dowodów obliczeniowych do innych drażliwych nierozwiązanych problemów w systemach gridowych.

„W coraz większym stopniu polegamy na systemach komputerowych w sprawach krytycznych i musimy oprzeć ich niezawodność na solidniejszych podstawach koncepcyjnych. Pokazaliśmy niesamowite rzeczy, które można odkryć, gdy poświęci się czas na opracowanie tej formalnej specyfikacji tego, co tak naprawdę jest problem” – mówi Alizadeh.