Araştırmacılar ağ tıkanıklığını azaltmada önemli bir engel keşfetti | MİT Haberleri

Kullanıcılar internet üzerinden ağın kaldırabileceğinden daha hızlı veri göndermek istediğinde tıkanıklık meydana gelebilir – trafik sıkışıklığının sabah işe giderken büyük bir şehre girmesi gibi.

İnternet üzerinden veri ileten bilgisayarlar ve cihazlar, verileri daha küçük paketlere böler ve bu paketlerin ne kadar hızlı gönderileceğine karar vermek için özel bir algoritma kullanır. Bu tıkanıklık kontrol algoritmaları, aynı ağı paylaşıyor olabilecek diğer kullanıcılarla adil bir şekilde paylaşırken mevcut ağ kapasitesini tam olarak keşfetmeye ve kullanmaya çalışır. Bu algoritmalar, ağda kuyruklarda bekleyen verilerin neden olduğu gecikmeyi en aza indirmeye çalışır.

Son on yılda, endüstri ve akademideki araştırmacılar, gecikmeleri kontrol ederken yüksek oranlara ulaşmaya çalışan birkaç algoritma geliştirdiler. Google tarafından geliştirilen BBR algoritması gibi bunlardan bazıları artık birçok web sitesi ve uygulama tarafından yaygın olarak kullanılmaktadır.

Ancak MIT araştırmacılarından oluşan bir ekip, bu algoritmaların son derece adaletsiz olabileceğini keşfetti. Yeni bir çalışmada, her zaman en az bir göndericinin diğer göndericilere kıyasla neredeyse hiç bant genişliği almadığı bir ağ senaryosu olacağını gösteriyorlar; yani açlık olarak bilinen bir problemin önüne geçilemez.

“Bu makale ve sonuçlar hakkında gerçekten şaşırtıcı olan şey, ağ yollarının gerçek dünyadaki karmaşıklığını ve veri paketlerine yapabilecekleri her şeyi hesaba kattığınızda, gecikme kontrollü tıkanıklık kontrol algoritmalarından kaçınmanın temelde imkansız olmasıdır. mevcut yöntemleri kullanarak açlıktan ölme,” diyor elektrik mühendisliği ve bilgisayar bilimi (EECS) doçenti Mohammad Alizadeh.

Alizadeh ve ortak yazarları, açlığı önleyebilecek geleneksel bir tıkanıklık kontrol algoritması bulamamış olsa da, farklı bir sınıfta bu sorunu önleyebilecek algoritmalar olabilir. Analizleri ayrıca, bu algoritmaların çalışma şeklini değiştirmenin, böylece gecikmede daha büyük değişikliklere izin vermenin, bazı ağ durumlarında açlığın önlenmesine yardımcı olabileceğini öne sürüyor.

Alizadeh makaleyi ilk yazar ve EECS yüksek lisans öğrencisi Venkat Arun ve Fujitsu Bilgisayar Bilimi ve Yapay Zeka Profesörü kıdemli yazar Hari Balakrishnan ile birlikte yazdı. Araştırma, ACM Veri İletişimi Özel İlgi Grubu (SIGCOMM) konferansında sunulacak.

Tıkanıklığı kontrol etme

Tıkanıklık kontrolü, araştırmacıların 1980’lerden beri çözmeye çalıştıkları ağ oluşturmada temel bir sorundur.

Bir kullanıcının bilgisayarı, ağ bağlantısının kalitesi veya ağı kullanan diğer göndericilerin sayısı gibi bilgilerden yoksun olduğundan, ağ üzerinden veri paketlerini ne kadar hızlı göndereceğini bilemez. Paketlerin çok yavaş gönderilmesi, mevcut bant genişliğinin yetersiz şekilde kullanılmasına neden olur. Ancak bunları çok hızlı göndermek ağı bunaltabilir ve bunu yaparken paketler düşmeye başlar. Bu paketlerin yeniden gönderilmesi gerekir, bu da daha uzun gecikmelere yol açar. Gecikmeler, uzun süre kuyruklarda bekleyen paketlerden de kaynaklanabilir.

Tıkanıklık kontrol algoritmaları, tıkanıklık sonucunu çıkarmak ve verinin ne kadar hızlı gönderileceğine karar vermek için paket kayıplarını ve gecikmeleri sinyal olarak kullanır. Ancak internet karmaşıktır ve ağ tıkanıklığıyla ilgili olmayan nedenlerle paketler gecikebilir ve kaybolabilir. Örneğin, veriler yol boyunca bir kuyrukta tutulabilir ve daha sonra diğer paketlerin bir patlamasıyla serbest bırakılabilir veya alıcının onayı gecikebilir. Yazarlar, tıkanıklıktan kaynaklanmayan gecikmelere “titreşim” diyorlar.

Bir tıkanıklık kontrol algoritması gecikmeyi mükemmel bir şekilde ölçse bile, tıkanıklıktan kaynaklanan gecikme ile titreşimin neden olduğu gecikme arasındaki farkı söyleyemez. Titreşimin neden olduğu gecikme tahmin edilemez ve gönderenin kafasını karıştırır. Bu belirsizlik nedeniyle, kullanıcılar gecikmeyi farklı şekilde tahmin etmeye başlarlar ve bu da paketleri eşit olmayan oranlarda göndermelerine neden olur. Arun, sonunda bunun açlığın meydana geldiği ve birinin tamamen dışlandığı bir duruma yol açtığını açıklıyor.

“Projeyi başlattık çünkü titreşim varlığında tıkanıklık kontrolü davranışına dair teorik bir anlayıştan yoksunduk. Bunu daha sağlam bir teorik temele oturtmak için, düşünülebilecek kadar basit, ancak internetin bazı karmaşıklıklarını yakalayabilecek bir matematiksel model oluşturduk. Matematiğin bize bilmediğimiz ve pratik önemi olan şeyleri anlatması çok faydalı oldu” diyor.

Açlık eğitimi

Araştırmacılar matematiksel modellerini bir bilgisayara beslediler, ona bir dizi yaygın olarak kullanılan tıkanıklık kontrol algoritması verdiler ve bilgisayardan modellerini kullanarak açlığı önleyebilecek bir algoritma bulmasını istediler.

“Yapamadık. Bildiğimiz her algoritmayı denedik ve bazı yenilerini oluşturduk. Hiçbir şey işe yaramadı. Bilgisayar her zaman bazı kişilerin tüm bant genişliğini aldığı ve en az bir kişinin temelde hiçbir şey alamadığı bir durum buldu” diyor Arun.

Araştırmacılar, özellikle bu algoritmaların oldukça adil olduğuna inanıldığından, bu sonuca şaşırdılar. Aşırı bir adaletsizlik biçimi olan açlıktan kurtulmanın mümkün olmayabileceğinden şüphelenmeye başladılar. Bu onları, ağ modellerinde her zaman açlıktan zarar göreceklerini kanıtladıkları “gecikme-yakınsak algoritmalar” olarak adlandırdıkları bir algoritma sınıfını tanımlamaya motive etti. Gecikmeyi kontrol eden (araştırmacıların farkında olduğu) mevcut tüm tıkanıklık kontrol algoritmaları, gecikme yakınsamasıdır.

Arun, yaygın olarak kullanılan bu algoritmaların bu kadar basit başarısızlık modlarının bu kadar uzun süre bilinmemesi gerçeğinin, algoritmaları yalnızca deneysel testlerle anlamanın ne kadar zor olduğunu gösterdiğini ekliyor. Sağlam bir teorik temelin önemini vurgular.

Ama tüm umutlar kaybolmaz. Test ettikleri tüm algoritmalar başarısız olsa da, açlıktan kaçınabilecek gecikme yakınsaması olmayan başka algoritmalar olabilir. bu nedenle aralık, ağdaki titreşim nedeniyle meydana gelebilecek herhangi bir gecikmeden daha büyüktür.

“Gecikmeleri kontrol etmek için, algoritmalar istenen bir denge ile ilgili gecikmedeki varyasyonları da sınırlamaya çalıştılar, ancak tıkanıklık gecikmelerinin daha iyi ölçümlerini elde etmek için potansiyel olarak daha büyük gecikme varyasyonu yaratmada yanlış bir şey yok. Bu sadece benimsemeniz gereken yeni bir tasarım felsefesidir” diye ekliyor Balakrishnan.

Şimdi, araştırmacılar açlığı ortadan kaldıracak bir algoritma bulup bulamayacaklarını veya oluşturabileceklerini görmek için zorlamaya devam etmek istiyorlar. Ayrıca, bu matematiksel modelleme ve hesaplamalı ispat yaklaşımını ağ bağlantılı sistemlerdeki diğer zorlu, çözülmemiş problemlere uygulamak istiyorlar.

“Çok kritik şeyler için bilgisayar sistemlerine giderek daha fazla güveniyoruz ve güvenilirliklerini daha sağlam bir kavramsal temele oturtmamız gerekiyor. Sorunun gerçekte ne olduğuna dair bu resmi özellikleri bulmak için zaman ayırdığınızda keşfedebileceğiniz şaşırtıcı şeyleri gösterdik” diyor Alizadeh.

.