Koniec problemów z Wi-Fi?

[KopalniaWiedzy.pl 314]

Grupa naukowców poprawiła przepustowość łączy bezprzewodowych o cały rząd wielkości. Dokonano tego za pomocą zmiany algorytmów na takie, które eliminują z obróbki sygnału polecenia ponownego przesyłania zagubionych pakietów. Dzięki nowemu podejściu do uzupełniania utraconych danych udało się znakomicie polepszyć przepustowość.

Szczegóły technologii, opracowanej przez specjalistów z MIT-u, Harvard University, California Institute of Technology, portugalskiego Universidade do Porto oraz Universytetu z Monachium, nie zostały ujawnione. Wiadomo, że nową techniką, nazwaną kodowanym TCP, zainteresowały sie już liczne firmy.

Naukowcy przeprowadzili jej testy w pociągu z Nowego Jorku do Bostonu, który jest znany z problemów z łącznością. Profesor Muriel Medard z MIT-u, która stoi na czele grupy badawczej, mówi, że wraz ze swoim zespołem mogła bez najmniejszych problemów obejrzeć film z YouTube'a, podczas gdy inni pasażerowie mieli problemy z nawiązaniem jakiegokolwiek połączenia.

Testy laboratoryjne, przeprowadzone na kampusie MIT-u pokazały, jak przydatna będzie nowa technologia. Na wspomnianym kampusie średni odsetek gubionych pakietów wynosi 2%. Medard i jej koledzy wykazali, że połączenie korzystające ze standardowo dostępnych technologii i osiągające na kampusie przepustowość rzędu 1 megabita na sekundę, po włączeniu kodowanego TCP zwiększa przepustowość do... 16 Mb/s. Jeszcze większe zyski osiąga się, gdy ilość traconych pakietów wzrasta do 5%, a jest to sytuacja typowa dla szybko poruszającego się pociągu. Wówczas prędkość połączenia wzrasta po włączeniu kodowanego TCP z 0,5 Mb/s do 13,5 Mb/s.

Tam, gdzie nie dochodzi do utraty pakietów nowa technologia nie przynosi żadnych korzyści. Jednak połączenia bezprzewodowe bez utraty pakietów to niezwykle rzadkie zjawisko.

Profesor Medard mówi, że kodowane TCP spisze się jeszcze lepiej, gdy algorytmy zostaną zaimplementowane bezpośrednio w nadajnikach i ruterach. Jej zdaniem, technologia ta może zostać użyta do połączenia danych napływających z Wi-Fi i sieci komórkowych w jeden kanał, dzięki czemu smartfony i inne urządzenia nie będą musiał bez przerwy przełączać się pomiędzy różnymi częstotliwościami.

O nowej technologii wiadomo, że zmienia ona sposób przesyłania danych. Wysyła równania opisujące serie pakietów. Jeśli jakiś pakiet zostanie zgubiony, to urządzenie, zamiast prosić o jego ponowne przesłanie, rozwiązuje równania i uzupełnia brakujące informacje. Jako, że równania są bardzo proste i liniowe, dodatkowe obciążenie procesora jest tak małe, że praktycznie pomijalne.

Na razie nie wiadomo, jak nowa technologia sprawdzi się na szeroką skalę. Jednak eksperci są pełni optymizmu. Sheau Ng, wiceprezes ds. badawczo-rozwojowych w NBC Universal mówi: Jeśli w laboratorium uzyskamy marginalnie lepsze wyniki, to inżynierowie będą sceptyczni [co do korzyści w warunkach rzeczywistych - red.]. Jednak patrząc na to, co oni osiągnęli w laboratorium - a mamy tu do czynienia z poprawą o cały rząd wielkości - nowa technologia jest bardzo obiecująca.

Kodowane TCP może trafić pod strzechy w ciągu najbliższych 2-3 lat.

[Jajcenty 314]

Wysyła równania opisujące serie pakietów. Jeśli jakiś pakiet zostanie zgubiony, to urządzenie, zamiast prosić o jego ponowne przesłanie, rozwiązuje równania i uzupełnia brakujące informacje. Jako, że równania są bardzo proste i liniowe, dodatkowe obciążenie procesora jest tak małe, że praktycznie pomijalne.

 

hm, Wygląda jak rozwinięcie pomysłu na bity kontrolne. Bardzo fajnie, że działa bo ja od razu mam wizję a co jeśli zaginie równanie lub choć jeden jego współczynnik. Zamiast modulować częstotliwość można wysyłać szereg Fouriera opisujący tę modulację ale bym się nie spodziewał, że takie podejście będzie szybsze od samej modulacji. A tu proszę. Brawa dla MIT.

[Jarek Duda 129]

Dla mnie to jest raczej kolejna nauczka jak kiepskie są podstawowe używane algorytmy, szczególnie w teorii informacji - nakazywanie ponownego przesyłania zagubionych pakietów jest żałośnie prymitywnym rozwiązaniem.

Zamiast tego można praktycznie darmo dołożyć korekcję błędów, która i tak tam powinna być tam włączona - zgubienie pakietu jest dosłownie najprostszym możliwym scenariuszem uszkodzenia: w przeciwieństwie do standardowego Binary Symmetric Channel w którym nie znamy pozycji uszkodzeń, tym razem wiemy które bity należy odtworzyć (Erasure Channel) i do tego są one równomiernie rozłożone - w tym scenariuszu bardzo łatwo podejść dowolnie blisko granicy Shannona, czyli w naszym przypadku: używamy praktycznie wszystkich nieuszkodzonych bitów.

Jeśli wiemy że 5% pakietów jest średnio uszkodzonych, przesyłanie powiedzmy 1.06 bitów/oryginalny bit spokojnie wystarczy żeby odtwarzać oryginalną wiadomość z tych które dotrą.

Na przykład dzielimy wiadomość na bloki n bitowe i wysyłamy w n pakietach, z których k-ty jest zbudowany z k-tych bitów oraz dodatkowy (lub kilka) pakiet tej samej długości - zawierający po 1 bicie kontrolnym na blok. Po utracie ostatniego pakietu nic się nie dzieje, natomiast gdy jest to jeden z wcześniejszych, przeglądając drzewo możliwości prawie na pewno uda nam się odtworzyć oryginalną wiadomość: http://arxiv.org/pdf/1204.5317

 

Ale największym marnotrawstwem jest tutaj używanie sumy kontrolnej na cały pakiet, czyli mimo że po uszkodzeniu pojedynczego bitu pakiet dalej zawiera prawie całą informację, w tym podejściu idzie on śmietnik - wrzucenie korekcji błędów zamiast pojedynczej weryfikacji, jak rozsmarowanie sumy kontrolnej jednorodnie na cały pakiet, powoduje że z uszkodzonego odzyskujemy prawie całą informację.

 

Z kwantowej teorii informacji - która prawdopodobnie nigdy nie znajdzie prawdziwego zastosowania, mamy w Polsce dziesiątki światowej sławy specjalistów ... natomiast z tej praktycznej: klasycznej, która jest podstawą całego przesyłania/zapisywania informacji, pomimo szkół/wydziałów telekomunikacji, na przykład gdy szukałem recenzentów do pierwszego doktoratu (z asymetrycznych systemów liczbowych - prostszej alternatywy kodowania arytmetycznego), okazało się że straszna bida ...

Ta sytuacja jest dla mnie jednym z symboli kryzysu w nauce - zamiast pracy nad tym co ważne, nauka stała się jakimś ślepym pędem za publikacjami z tego co modne ... rezultat: zajmuję się klasyczną teorią informacji od kilku lat i gdzie nie spojrzę to widzę podstawowe braki koncepcyjne ... tyle że nikogo to nie interesuje.

[jotunn 1]

@Jarek Duda

Nie jestem przekonany, że to słabość algorytmów jest problemem, lecz raczej to, że masowo zaimplementowane są standardy opracowane dziesiątki lat temu. Nie wyobrażam sobie zmiany jakiegokolwiek elementu już istniejącej infrastruktury - wystarczy spojrzeć ile czasu (14 lat od RFC) zajęła implementacja standardu IPv6, który jest _tylko_ drobnym rozszerzeniem istniejącej funkcjonalności nie mającym wpływu na całokształt infrastruktury.

[Jarek Duda 129]

@jotunn,

Wymiana na IPv6 to trochę bardziej skomplikowana konsekwencja kilku dekad rozwoju, wzrostu rozmiarów sieci ... natomiast Wi-Fi jest czymś w miarę świeżym - przynajmniej od strony protokołu można by zrobić raz a porządnie, tyle że

- telekomunikacją zajmują się głównie inżynierzy - z względnie przeciętnym podłożem matematycznym ... zrobi rzetelnie żeby działało, ale optymalność jest zwykle dość odległym kryterium,

- teoria informacji jest strasznie zaniedbaną dziedziną,

- istotne może być też że jak w "spisku żarówkowym", opłaca się robić a nie zrobić - producenci my na tych wymianach sprzętu niemało zarabiają ...

[nuivall 0]

IPv6 to nie tylko drobna modyfikacja (czyli dłuższe adresy), ale także wiele innych rzeczy i część z nich wymaga właśnie zmiany sprzętu. Standardy wifi natomiast zmieniają się bardzo często i pewnie tego typu modyfikacja ukaże się pod postacią nowej literki w 802.11.

[Skotos 3]

@Jarek Duda

Możliwe że właśnie ta zmienność i szybkie wdrażanie przez różnych producentów nowinek w WiFi to przeszkoda. W ciągu ostatnich 2 lat pojawiło się (i upadło) co najmniej kilka koncepcji. Czekam na połączenie MIMO i "radiówek dwukierunkowych" - to będzie skok prędkości, do tego ta technologia.

Możliwe, że bardziej opłaca się sprzedawać je po kolei - teraz MIMO się sprzedaje, potem nowe nadajniki, następnie nowe algorytmy, tak co dwa lata.

[Jarek Duda 129]

@Skotos,

Piszesz o rozwoju sprzętu (kanału informacyjnego), natomiast tutaj twierdzą że już samą wymianą protokołu (obsługi danego kanału) poprawiają transmisję o rzędy wielkości - nie ma problemu zrobić blisko optimum, co oznacza że poprzednie rozwiązania były koszmarnym marnotrawstwem z perspektywy teorii informacji ... co zdążyło przestać mnie dziwić.

[Przemek Kobel 65]

Może to zaniedbanie, a może po prostu wybór. Większość urządzeń sieciowych i tak ma zdolność przetwarzania poniżej teoretycznej przepustowości używanego standardu. Rozwiązywanie jakichś równań na procesorze, który bez wspomagania nie jest w stanie routować szybciej niż 10 mbps to marny pomysł.

[Jajcenty 314]

Może to zaniedbanie, a może po prostu wybór. Większość urządzeń sieciowych i tak ma zdolność przetwarzania poniżej teoretycznej przepustowości używanego standardu. Rozwiązywanie jakichś równań na procesorze, który bez wspomagania nie jest w stanie routować szybciej niż 10 mbps to marny pomysł.

 

Nie rozumiem. Nie umiemy wysyłać szybciej niż X bps Więc traćmy pasmo na ponowne przesyłanie błędnych pakietów?

Z tego co pisze Jarek Duda, wynika że zespół projektowy składał się ze sprzętowców dla których zbocza napięcia itp. pierdółki były ważniejsze.

[Przemek Kobel 65]

Może od początku: cały ten wynalazek działa na poziomie protokołu. Sprzęt, standard, modulacja, częstotliwości itp zostają praktycznie bez zmian (w zasadzie to samo można też wykorzystać po kablu). Problem w tym, że obecny sprzęt ma niewielką moc obliczeniową i spora część operacji wykonywana jest w specjalizowanych układach obsługujących daną część standardowego protokołu (np. sprzętowy NAT). Jeśli zmieniamy protokół, musimy zrezygnować z tych specjalizowanych układów i użyć procesora ogólnego. W tym momencie router zamiast 40 mbit/s zaczyna przerzucać tylko 3 - czyli przejście na lepszy standard się nie opłaca.

 

Aby użyć mechanizmów opisywanych w newsie, trzeba albo nowych specjalizowanych układów, albo podkręcić zegar systemu w standardowym urządzonku. Jesli podkręcimy zegar, trzeba będzie dodać większy zasilacz i wentylator. Jeśli dodamy wentylator, zacznie toto wyć ludziom po nocach. Jeśli będzie większy zasilacz - (czyli też pobór mocy - zieloni się ucieszą) - trzeba będzie użyć droższych podzespołów do produkcji urządzenia (płytki, przetwornic wewnętrznych, użyć bardziej wymagających norm do projektowania układu) Itd, itp.

 

Krótko mówiąc: w ramach istniejących urządzeń powtarzanie gubionych pakietów było rozsądnym kompromisem. Mówienie o zboczach i napięciach jest tu nieporozumieniem, ponieważ całe WiFi (im nowsze tym bardziej) to zaawansowana technologia sygnałowa i bez porządnych podstaw matematycznych nic tam nie zadziała (tak jak SATA nie zadziałałoby gdyby używano metod z czasów RS-232). Obecnie procesory embedded są już na tyle wydajne, że można bawić się na wyższym poziomie, to i ludzie się bawią, jak widać w artykule.

[Jarek Duda 129]

Przemek, masz dużo racji - rzeczywiście porządna korekcja jest dość kosztowna - dopiero w WiMaxie włączają współczesne metody: Turbo Codes i Low Density Parity Check (w dość oszczędnych wersjach) ... jednak gdy mówimy o utracie pakietów to jest najprostszy możliwy scenariusz do korekcji: Erasure z regularnie rozmieszczonymi uszkodzeniami - do tego od dawna istnieją szybkie prawie optymalne metody jak LT Codes ( http://en.wikipedia...._transform_code ) ...

 

... a jak chcielibyśmy nie wyrzucać uszkodzonych pakietów tylko wycisnąć z nich ile się da, trzeba jednak solidną korekcję - myślę że tutaj lepiej niż TC i LDPC pasują Correction Trees (podobne do splotowych, ale po kilku istotnych ulepszeniach) - dla małych szumów korekcja jest pełna i praktycznie darmo (a dla dużych, obciążając procesor można wyciągnąć więcej niż z pozostałych: https://dl.dropbox.c.../comaprison.jpg ).

 

Kolejną sprawą jest nie wysyłanie ponownie całych pakietów, tylko w razie potrzeby dodatkowych bloków "bitów parzystości" - wstępnie przesyłasz wiadomość (np. 10 bloków) plus powiedzmy jeden taki blok dodatkowej redundancji ... a jeśli w danym czasie nie dostaniesz potwierdzenia rekonstrukcji, przesyłasz dodatkowy (inny) itd...

[Przemek Kobel 65]

Do dzisiaj sprzedaje się urządzenia WiFi, które mają zegar - uwaga - 160 MHz i 8 MB pamięci RAM, z czego większość zabiera system. Ile pakietów można tu zmieścić? Jakakolwiek operacja na pakiecie poza jego przerzuceniem i prostą segregacją po nagłówkach ma katastrofalny skutek dla wydajności. Jeśli chodzi o wzrost wydajności poprzez przesłanie kawałka pakietu - teoretycznie tak, ale trzeba pamiętać o różnych dziwnych przypadłościach niektórych standardów. Na przykład przed każdym pakietem trzeba puścić "pilota" (preambuła), który w tym wypadku zajmie bardzo dużo miejsca w stosunku do danych. Nie każdy standard pozwala łączyć krótkie pakiety, a jeśli już pozwala, to zanim zostanie przesłany burst, można na niego chwilę poczekać. Powstały całe rodziny chipsetów, które sobie liczą odległości do podłączonych stacji i na tej podstawie regulują wszystkie zależności czasowe w transmisji. W takim wypadku zmiana zachowania stacji wymaga przeprojektowania sporego kawałka chipsetu.

 

Tak że wszystko pięknie, ale też nie wszystko jest takie proste.

[Jarek Duda 129]

160MHz i 8MB rzeczywiście brzmi ograniczająco dla solidnej korekcji trudnych kanałów: BSC (czy AWGN - z dodatkową "soft information") ... ale dla Erasure do radzenia sobie ze zgubionymi pakietami jest zdecydowanie wystarczające. Dodatkowo może używać zasobów sprzętu którego jest częścią - wysyłać mu trudniejsze przypadki, tak że o przepustowości decyduje też główny procesor i wybrany przez użytkownika poziom jego wykorzystania.

 

Nie mówię że jest proste, tylko że jednak może być bardziej optymalnie - że płacimy za zaniedbywanie podstawowej dziedziny dzisiejszego światu informacji: (niekwantowej!) teorii informacji.

Na przykład: jakie są ograniczenia dla hashowania? Podczas gdy używa się przynajmniej kilkanaście bitów na element, kilka miesięcy temu okazało się że do rozróżniania elementów wystarczy ok. 2.33 bita/element (slajdy i źródła: http://dl.dropbox.com/u/12405967/hashsem.pdf ).

[antykwant 7]

Jarek bardzo podoba mi się twój sposób wypowiedzi. Najbardziej to, że słowa podpierasz odnośnikami do szczegółowych informacji. Oby taki nawyk miało więcej osób.