Kompresja informacji w sieciach
- Adam Urbanek,
- 01.02.2004
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.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).
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.
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, zawiera-ją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.