Kompresja informacji w sieciach

Wraz z rosnącym zapotrzebowaniem na multimedialne usługi szerokopasmowe w przyspieszonym tempie narasta ruch pakietowy w sieciach telekomunikacyjnych. Coraz częściej także w Internecie, gdzie wzmaga się trafik związany z realizacją usług czasu rzeczywistego, wymagający odpowiedniego i gwarantowanego poziomu jakości (QoS). Sieci transportowe muszą więc zapewnić obsługę olbrzymiego ruchu IP, charakteryzującego się znacznie większą zmiennością niż zwykły przekaz głosowy. Realizacja tych wymagań bezpośrednio implikuje konieczność stopniowego podwyższania przepływności sieci transportowych na wszystkich poziomach komunikacji. Można to uzyskać poprzez fizyczne rozszerzanie pasma transmisji w sieci (istotny wzrost kosztów), dokonując kompresji transmitowanej przez sieć informacji bądś stosując obydwa te czynniki jednocześnie. Najprostszą, najtańszą i najbardziej skuteczną metodą jest zagęszczanie przesyłanej informacji, czyli stosowanie kompresji. Kompresja pozwala nawet dziesięciokrotnie zwiększyć przepływność istniejącej sieci telekomunikacyjnej, jednak pod warunkiem zastosowania metody o odpowiedniej skuteczności i z niewielkim opóźnieniem w procesie translacji. Zagęszczanie informacji jest metodą podwyższania przepływności użytkowej w sieciach teleinformatycznych i oczywiście jednym ze sposobów zwiększenia pojemności systemów serwerowych, bazodanowych, archiwizacyjnych itp.

Rodzaje kompresji

Operacja kompresji zmniejsza wielkość multimedialnych plików cyfrowych (głos, tekst, programy, pliki, grafika, wideo), przyczyniając się do bardziej efektywnego wykorzystania przestrzeni pamięciowej w serwerach. Dopuszcza się kompresję z częściową utratą informacji pierwotnej (kompresja stratna) dla sygnałów głosowych, dźwięku i obrazu lub bez straty informacji żródłowej (kompresja bezstratna) - w przekazach programów i zbiorów archiwizujących dane. Współczesne i popularne algorymy bezstratnej kompresji danych, takie jak PKZIP, RLE, LZW czy kodowanie Huffmana oraz pochodne, w niektórych przypadkach pozwalają na uzyskanie bezstratnej kompresji powyżej 80%.

Statystyczna metoda kompresji Huffmana opiera się na założeniu, że częstość występowania poszczególnych znaków w zbiorze danych nie jest jednakowa i niektóre pojawiają się częściej niż inne. Im częściej konkretny znak pojawia się w zbiorze, tym mniejszą liczbę bitów przypisuje się mu do jego zakodowania - skracając w ten sposób łączną liczbę bitów informacyjnych potrzebnych do rejestracji lub transmisji danych źródłowych przez sieć. Wadą tego sposobu kodowania jest wymagana znajomość rozkładu prawdopodobieństwa występowania symboli w całym zbiorze jeszcze przez jego kompresją. Niedogodność tę eliminuje kompresja kodowaniem adaptacyjnym typu Lempel-Ziv.

W pojęciu ogólnym kompresja informacji śródłowej może być stratna lub bezstratna. Bezstratna kompresja informacji redukuje objętość przesyłanego zbioru informacji w taki sposób, aby jej treść nie uległa żadnej zmianie po operacji dekompresji. Jej przeciwieństwem są algorytmy kompresji stratnej, które w wyniku przetworzenia informacji (kompresji i dekompresji) nie dają identycznego zbioru danych po stronie odbiorczej. Podczas kompresji stratnej z transmitowanego zbioru usuwa się pewne informacje - uznane przez mechanizm kompresji za zbędne - przy czym skasowane fragmenty danych śródłowych są nieodwracalnie stracone. Metody kompresji stratnej są użyteczne w procesie zmniejszania objętości większości plików dświękowych i obrazowych, dla których taka dokładność nie jest wcale potrzebna, nie można jej natomiast stosować w przekazach danych, plikach programowych czy w odniesieniu do ważnych aplikacji specjalistycznych (obrazy medyczne, mapy terenowe i inne).Większość algorytmów dotyczących kompresji obrazu, dświęku i głosu ma z natury charakter kompresji stratnej. Nie jest to wcale przeszkodą w rejestracji i odbiorze tak zmienionych sygnałów, gdyż czułość ludzkiego ucha i oka ma ograniczoną rozdzielczość, niewielkie straty w odbieranej informacji pozostają więc niezauważalne przez zmysły człowieka. Eliminowanie niedostrzegalnych dla oka i ucha elementów powoduje jednak, że sumaryczna wielkość przesyłanej informacji jest mniejsza, pasmo potrzebne do jej przesłania - węższe, a kanał transmisyjny potrzebny do jej przesłania jest wykorzystany bardziej efektywnie. W komunikacji multimedialnej (głos z danymi) przez sieci transportowe zwykle brak rozróżnienia, które elementy można przesyłać ze stratami, a które bez strat, co praktycznie oznacza, że podstawowym sposobem kompresji w sieciach pozostaje wyłącznie bezstratna kompresja informacji. Bezstratne technologie kompresji dzielą się obecnie na dwie kategorie, różniące się sposobem tworzenia tablic kompresji wg algorytmów kompresji statystycznej lub podstawieniowej.

Działanie algorytmów kompresji bezstratnej polega na wyszukiwaniu i eliminowaniu z komprymowanego zbioru powtórzeń danych cyfrowych bądś ich zastępowaniu w procesie konwersji symbolami lub kodami reprezentującymi tę samą informację w sposób skrócony. Do najczęściej spotykanych sposobów kompresji bezstratnej zalicza się: redukcję liczby spacji; redukcję ciągu powtarzających się znaków jednym kodem z liczbą powtórzeń; kodowanie słowem kluczowym wg tablicy zawierającej najczęściej powtarzające się sekwencje danych (niekoniecznie znaków); kodowanie wg metody Huffmana oraz adaptacyjne kodowanie Lempel-Ziv. Programowe algorytmy bezstratnej kompresji danych wprowadzają opóśnienia, utrudniające prowadzenie transmisji w czasie rzeczywistym.

Najbardziej popularna do tej pory kompresja statystyczna oblicza w początkowej fazie kompresji (lub korzysta z gotowych szablonów wzorcowych) częstość występowania poszczególnych symboli znaków w zbiorze wejściowym, a następnie przypisuje im odpowiednio krótsze kody kompresji - ważne dla całego zbioru podlegającego kompresji. Liczba bitów konwersji przypisana poszczególnym komprymowanym znakom jest określana matematycznie na zasadzie prawdopodobieństwa ich występowania. Skuteczność tego rodzaju kompresji jest tym większa, im częściej w procesie kompresji pojawiają się znaki o przypisanych im krótszych kodach, niż miały one w oryginalnej postaci śródłowej. Współcześnie funkcjonują dwie odmiany kompresji statystycznej: kompresja realizowana wg algorytmów statycznych lub dynamicznych (czyli adaptacyjnych). W statycznej kompresji, takiej jak kompresja Huffmana, mamy do dyspozycji zdefiniowaną jedną tablicę dla całego pliku lub obiektu podlegającego kompresji. Nie zmienia się ona podczas procesu kompresji kompletnego zbioru danych.

Najstarszy algorytm bezstratnej kompresji podstawieniowej, wg metody Lempel-Ziv (standard LZ, 1977 r.), polega na zdefiniowaniu tablicy początkowej składającej się z pojedynczych znaków. W miarę pojawiania się w transmitowanym ciągu danych kolejnych nowych elementów do każdego znaku początkowej tablicy jest dołączana struktura drzewiasta, tworząca poszczególne gałęzie drzewa.Każde ramię drzewa identyfikuje i zastępuje krótkie słowo kodowe (wskaźnik) przesyłane w transmisji. Z upływem czasu do gałęzi drzewa kodowego są dodawane nowe węzły adaptacji kodowej i generowane kolejne wskaźniki skojarzone z węzłami.

W dynamicznej kompresji statystycznej zawartość tablicy szablonów kodowych może być modyfikowana. Na zmianę zawartości tablicy kodowej wpływa przede wszystkim rzeczywista częstotliwość występowania takich samych znaków lub symboli w transmitowanym zbiorze, adaptacja tablicy zaś w dużym stopniu zależy od kontekstowej treści zbioru śródłowego - nawet w obrębie jednego języka narodowego (archaiczny, współczesny, techniczny, inne). Za pomocą kompresji statystycznej z dynamicznym kodowaniem kontekstowym opartym na wyrażeniach (takim jak PPM czy kodowanie arytmetyczne) uzyskuje się wyższy stopień kompresji niż podczas kodowania algorytmami statycznymi ze stałą tablicą. Ten sposób kodowania przynosi lepsze zbliżenie do granicy kompresji wyznaczonej prawem Shannona. Patrząc od strony szybkości przetwarzania, nie jest to jednak najbardziej optymalny sposób kompresji, gdyż czas potrzebny do przeliczania tablic algorytmów kodowania kontekstowego rośnie wykładniczo wraz z liczbą kontekstów. Wada ta pomniejsza korzyści wynikające ze skuteczności kompresji i powoduje, że ta kompresja nie jest stosowana praktycznie w aplikacjach czasu rzeczywistego. Potwierdza się w ten sposób ogólna zasada, że im bardziej skuteczna kompresja informacji, tym więcej wymaga czasu, aby uzyskać mniejszą zajętość kanału transmisyjnego.

Drugą kategorię bezstratnej kompresji informacji stanowią algorytmy kompresji podstawieniowej, operujące na ciągach znaków lub symboli danych znajdujących się w strumieniu informacji śródłowej. Algorytmy kompresji podstawieniowej działają na innej zasadzie niż oparte na prawdopodobieństwie powtarzania się pojedynczego znaku w zbiorze. Algorytm podstawieniowy wyszukuje ciąg identycznych sekwencji elementów w strumieniu danych i zastępuje je pojedynczym odnośnikiem lub specjalnym żetonem - identyfikującym powtarzającą się wielokrotnie sekwencję w strumieniu. Zamiast obliczania prawdopodobieństwa występowania pojedynczego znaku w zbiorze (wymagającego odpowiednio długiego czasu przetwarzania), algorytm podstawieniowy zastępuje zidentyfikowane długie sekwencje prostym odnośnikiem wskazującym konkretny szablon w tablicy kompresji. Ponieważ detekcja szablonów jest szybsza niż kontekstowe obliczanie prawdopodobieństwa w algorytmach dynamicznej kompresji, algorytmy te są współcześnie stosowane do kompresji pasma w sieciach z aplikacjami czasu rzeczywistego.

Większość współczesnych metod kompresji bezstratnej w sieci używa algorytmów podstawieniowych, które przy niewielkiej mocy przetwarzania dają zadowalający współczynnik kompresji. Mimo ciągłego ulepszania, tradycyjne rozwiązania kompresji podstawieniowej mają znaczące ograniczenia i nie mogą sprostać rosnącym wymaganiom aplikacji we współczesnym środowisku sieciowym.

Cechy kompresji

Jednym z wyróżników między wieloma sposobami kompresji jest położenie powtarzających się elementów w zbiorze. Identyczne symbole zdarzają się wielokrotnie wewnątrz każdego pliku, obiektu czy sesji transmisyjnej, lecz ich liczba wewnątrz pojedynczego pakietu (średnio w obrębie 1460 bajtów dla sieci pakietowych) jest niestety stosunkowo mała. Ponadto, w wyniku fragmentacji informacji w sieciach pakietowych WAN, pakiety są zwykle transmitowane w trybie bezpołączeniowym - w otoczeniu innych pakietów pochodzących od wielu użytkowników. Powoduje to dalszy wzrost dystansu między powtarzającymi się elementami w pliku oraz istotnie komplikuje algorytm przeszukiwania powtarzających się wzorców kompresji konkretnego zbioru. Dodatkową trudność stanowi wzrost szybkości łącza WAN (więcej nowych aplikacji i większa liczba innych użytkowników). W wyniku takiego agregowania informacji z wielu śródeł jeszcze bardziej wzrasta dystans między poszukiwanymi wzorcami zbioru, istotnie pogarszając proces kompresji.

Drugą cechą odróżniającą kompresję w sieci IP od kompresji plików danych jest działanie online w aplikacjach czasu rzeczywistego, czułych na opóśnienia (latency) informacji - czyli inaczej niż w operacjach offline dla plików. W tych aplikacjach układ kompresji nie może sobie pozwolić na wielokrotne przeglądanie zbioru w celu uzyskania lepszej skuteczności kompresji, gdyż w kolejce zwykle oczekują następne pakiety do obróbki. Kompresja w sieci powinna być zatem jednorazowa, skuteczna i szybka, a pogodzenie tych sprzecznych wymagań wcale nie jest łatwe. Można to osiągać jedynie przez używanie niektórych algorytmów kompresji - istotnie lepszych niż te stosowane w operacjach offline z wielokrotnym przeszukiwaniem zbioru.

Trzecim wyróżnikiem kompresji w sieciach jest inny sposób komunikacji między układami kompresji i dekompresji podczas ich pracy. W klasycznej kompresji pliku danych na poziomie aplikacji lub lokalnego systemu operacyjnego skomprymowana informacja jest rejestrowana bezpośrednio na dysku, z którego póśniej jest odtwarzana na tym samym poziomie przez operację dekompresji. W kompresji sieciowej (warstwa IP) dane po kompresji są przesyłane do odległego dekompresora w kapsułkowanych pakietach transmisji bezpołączeniowej, transportowanych w strumieniu innych pakietów. W takiej sytuacji nie ma pewności odbierania pakietów w kolejności ich nadawania, nie mówiąc o tym, że mogą nawet nigdy nie dotrzeć do dekompresora po stronie odbiorczej. To jedna z podstawowych przyczyn znacznego skomplikowania algorytmów kompresji w sieciach i niewielkiej ich skuteczności.

Tradycyjne sposoby kompresji w sieci

Większość używanych dotąd tradycyjnych sposobów kompresji pasma w sieciach można podzielić na dwie kategorie: działające na podstawie bezstanowych okien algorytmu LZ (Lempel and Ziv), które mają wiele zmodernizowanych wersji, takich jak: LZ-STAC, V.42bis czy kompresja faksowa, lub algorytmy kompresji predykcyjnej Predictor - z przewidywaniem występowania następnych elementów w strumieniu danych.

jedynie dane umieszczone wewnątrz bezstanowego okna Lempel-Ziv podlegają kompresji sieciowej w strumieniu danych: im okno jest szersze, tym efektywność kompresji podstawieniowej jest lepsza, lecz czas kompresji dłuższy. Informacje znajdujące się poza wyznaczonym oknem LZ są bezpowrotnie stracone dla procesu kompresji.

Algorytm LZS. Idea kompresji wg podstawieniowego algorytmu LZ77 (1977 r.) przetrwała do dzisiaj w rozwiązaniu STAC compressor, oznaczanym obecnie jako kompresja LZS lub LZ-STAC, która operuje na programowo definiowanym bezstanowym oknie danych podlegających kompresji. Parametry tej kompresji ściśle zależą od rozmiaru okna: im jest ono szersze, tym skuteczność kompresji wyższa (więcej takich samych elementów znajduje się w komprymowanym zbiorze), lecz jednocześnie wzrasta pojemność bufora, rosną koszty układu i łączny czas przetwarzania (wzrost opóśnienia kompresji). Stosunkowo niski stopień kompresji bądś duże opóśnienia w przetwarzaniu okien o większych rozmiarach powodują, że ten sposób kompresji praktycznie nie nadaje się do operowania w szybkich sieciach komunikacyjnych. Nie nadaje się również do kompresji w sieciach z łączami współdzielonymi przez wielu użytkowników. Nawet użycie silnych procesorów sygnałowych zainstalowanych w dedykowanych urządzeniach z kompresją prowadzi do nieakceptowalnych opóśnień, wykluczających stosowanie kompresji z oknem bezstanowym typu LZ w sieciach.

Algorytm Predictor. Dla sieci o większych przepustowościach bardziej korzystnym rozwiązaniem jest kompresja podstawieniowa z przewidywaniem a priori następnych elementów (znaków, wyrażeń, słów, sekwencji, zdań) w strumieniu danych. Jedną z nich jest kompresja predykcyjna Predictor, która - korzystając z tworzonych dynamicznie tablic wskaśników predykcyjnych dla powtórek - pozwala zgadywać dalszą kolejność elementów w często powtarzanych sekwencjach, zastępując je jednym wskaśnikiem (lub kilkoma wskaśnikami) predykcji. Każdy poprawnie odgadnięty kolejny znak wzmacnia skuteczność kompresji zbioru, ale z drugiej strony znak z negatywnie przewidzianym wynikiem generuje dodatkową sygnalizację, pogarszającą cały proces kompresji. Liczba wejść do odnośników w tablicy predykcyjnej jest ograniczona, gdyby tak nie było kompresja stałaby się nieskuteczna (w wyniku kompresji można byłoby otrzymać nawet rozszerzenie ciągu danych w stosunku do informacji śródłowej). Tablica predykcyjna algorytmu Predictor jest więc niewielka, a sposób kompresji stosunkowo szybki jedynie w małym oknie sprawdzanych danych. Kompresja typu Predictor nigdy nie osiąga skuteczności porównywalnej z algorytmem LZ, ponieważ powtarzające się elementy w tej kompresji muszą znajdować się niedaleko siebie, co nie zdarza się często. Z kolei nadmierne rozszerzanie rozmiarów tablicy wskaśników predykcyjnych powoduje pogorszenie wszystkich parametrów kompresji w sieci. Algorytm kompresji predykcyjnej jest efektywny jedynie podczas komprymowania elementów, które w zbiorze następują bezpośrednio po sobie lub powtarzają się w bliskiej odległości od siebie w strumieniu danych. I tylko wtedy szybkość kompresji predykcyjnej rośnie (mniejsze są opóśnienia, dane można szybciej przesyłać przez sieć). Zawsze dzieje się to kosztem mniejszej skuteczności kompresji, jaką uzyskuje się w klasycznych metodach Lempel-Ziv. Zaletą kompresji z predykcją jest jednak większa szybkość przetwarzania, nawet bez potrzeby stosowania dedykowanych procesorów przeliczeniowych, dla wielu szybszych aplikacji sieciowych stanowi więc jedyny sposób kompresji przesyłanej informacji.

Molekularna kompresja - MSR

Trudności z komprymowaniem danych w sieciach szkieletowych WAN o większych szybkościach doprowadziły do opracowania bardziej wydajnych algorytmów kompresji w sieciach rozległych. Zdecydowany postęp w redukowaniu informacji w czasie rzeczywistym uzyskano dopiero niedawno za pomocą cząstkowej kompresji sekwencji MSR (Molecular Sequence Reduction), współcześnie wdrażanej w szybkich sieciach szkieletowych i transportowych. Opatentowany przez firmę Peribit algorytm kompresji cząstkowej MSR stanowi inteligentną i samouczącą się maszynę transkodującą, operującą na nieznanym jej trafiku sieciowym. Jej pierwowzorem były algorytmy do analizowania sekwencji genów DNA (molekuły A, C, G, T), adaptowane do procesów kompresji. Jedyny w swoim rodzaju samouczący algorytm maszyny MSR pozwala na najszybszą z możliwych dotąd detekcję i kompresję powtarzających się elementów w ciągu bezstanowych danych, bez jakiegokolwiek ograniczania odległości między pojawiającymi się powtórkami symboli, z pełną szybkością spływu do 45 Mb/s (T3) i ze stosunkowo niewielkim opóśnieniem translacji.

Podstawą działania algorytmu kompresji MSR w sieci jest kompletna tablica cząstkowa, zawierająca 256 znaków, czyli wszystkie możliwe bajty informacyjne (podobnie jak molekularnych cząstek A, C, G, T biologicznego łańcucha genów DNA). Translacja między tablicą cząstkową a bieżącą informacją w strumieniu danych jest wielowątkowa, z uwzględnieniem kilku zależności językowych (rodzaj języka narodowego, częstość występowania liter/wyrażeń/zwrotów, konstrukcja języka, frazy, gramatyka, wyjątki, inne). Proces translacji zbiorów w kompresji MSR ma adaptacyjną naturę, a zastosowany w nim algorytm działa jednocześnie w sposób ciągły i inkrementalny na sekwencyjnie nadchodzących danych wejściowych, automatycznie dążąc do optymalizacji długości postaci wynikowej. Algorytmiczna wiedza procesu kompresji ulega w trakcie działania rozszerzaniu (proces samouczenia), dostosowując się do rzeczywistych sekwencji śródłowych. Ârednia wartość kompresji pasma może sięgać 70-90%, co oznacza, że właściwie dobrana kompresja może nawet dziesięciokrotne podwyższyć przepływność sieci transportowej IP. Nabyta i uaktualniana na bieżąco wiedza o przebiegu procesu kompresji klasy MSR jest rejestrowana w systemie, co przyczynia się do szybkiej i skutecznej kompresji - niezależnie od odległości między powtarzającymi się elementami w komprymowanym zbiorze. Cecha ta istotnie wpływa na użytkowe parametry kompresji, ponieważ wówczas nie zależą one ani od zastosowanej metody transmisji pakietów (przekazy bezpołączeniowe), ani od przyjętego sposobu agregowania łączy transmisyjnych w sieciach rozległych (multipleksowanie TDM), ani od podwyższania szybkości sieci. Taki typ kompresji stanowi obecnie najlepsze rozwiązanie do redukowania danych przesyłanych w czasie rzeczywistym przez sieci transportowe WAN.