Компрессия данных при организации удаленного доступа к компьютерным сетям


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Компрессия данных при организации
удаленного доступа к компьютерным сетям

Введение

Число удаленных локальных сетей подразделений, связанных по различным телекоммуникационным каналам с информационно-вычислительными сетями центральных офисов своих корпораций, растет быстрыми темпами. В США, согласно прогнозам, в 1997 г. 94% всех ЛВС будут оснащены средствами удаленного доступа (в 1993 г. этот показатель составлял около 40%). Соответственно, быстрыми темпами растет и рынок оборудования для обеспечения связи локальных (LAN) и территориально-распределенных (WAN) сетей: в 1994 г. в мире было продано около 370 тысяч маршрутизаторов удаленного доступа [1].

В то же время по мере увеличения потребности в удаленном доступе к компьютерным сетям пользователи все чаще сталкиваются с проблемами, связанными с недостаточной пропускной способностью линий связи LAN-WAN, ведь чаще всего для этой цели используются обычные коммутируемые телефонные каналы, обеспечивающие скорость передачи данных до 28.8 Кбит/с.

Увеличение пропускной способности каналов удаленного доступа необходимо для сетевых приложений еще и потому, что при организации удаленного узла ЛВС часть полосы пропускания канала LAN-WAN оказывается занятой пересылкой служебных пакетов. Так, например, поскольку при разработке сетевой ОС NetWare фирмой Novell, вопросы экономии полосы пропускания стояли далеко не на первом месте, то использование семейства протоколов IPX/SPX оказалось крайне неэффективным при организации удаленного доступа по медленным каналам связи. Вызвано это тем, что серверы, маршрутизаторы, сетевые принтеры и другие объекты ЛВС постоянно "сообщают" о своем присутствии в сети, генерируя пакеты протоколов SAP (Service Advertising Protocol) и RIP (Routing Informationаl Protocol) и, кроме того, в сетях, работающих под управлением ОС NetWare, сервер генерирует в сеть так называемые "watchdog"-запросы, чтобы определить, продолжает ли тот или иной пользователь работать в сети. Положение усугубляется еще и тем, что в сетях Ethernet существуют ограничения на минимальную длину пакета, поэтому для передачи даже одного байта информации длина сетевого пакета все равно составит 64 байта.

Возможно, что ситуацию может исправить переход на новые каналы связи с большей пропускной способностью. Сегодня многие зарубежные коммуникационные компании предлагают пользователям в аренду различные виды высокопроизводительных линий:

* цифровые сети с интегральным сервисом - ISDN, с пропускной способностью от 64 Кбит/с до 1.5 Мбит/с;

* каналы Т1 и Е1 производительностью 1.536 и 2 Мбит/с соответственно, а также линии Т3, обеспечивающие скорость передачи данных до 44.736 Мбит/с;

* оптоволоконные линии связи SONET (Synchronous Optical NETwork), чья пропускная способность составляет от 51.84 Мбит/с до 13 Гбит/с.

В то же время, несмотря на то, что стоимость услуг телефонных компаний постоянно снижается, цена использования скоростных каналов остается достаточно высокой. Так, в США услуги по аренде линии Т1 компании AT&T на расстояние в 225 миль (около 365 км) обходятся пользователям в 4 159 долл. в месяц, а во Франции, например, ежемесячная плата за пользование линией Е1 на расстояние в те же 225 миль достигает 14 440 долл. США [2]. При этом цена пользования специальными линиями существенно возрастает с увеличением расстояния между удаленными сегментами ЛВС: аренда линии Т1 на расстояние между восточным и западным побережьями США составляет уже около 14 000 долл. в месяц. Стоимость аренды линий Т3 в 6-10 раз выше, чем линий Т1.

Поскольку аренда высокоскоростных каналов для передачи данных на большие расстояния доступна лишь за высокую арендную плату, фирмы разработчики аппаратных средств и программного обеспечения постоянно ищут решения, направленные на повышение эффективности использования обычных телефонных линий. Сегодня эта проблема решается по двум основным направлениям.

Первое из них связано с развитием технологии клиент-сервер в сетевых приложениях. Реализация такого подхода позволяет существенно уменьшить интенсивность сетевого трафика за счет того, что обработка запросов и операции с базами данных, массивами и др. производятся непосредственно на сервере, а по сети на рабочую станцию передаются лишь результаты обработки запроса.

Второй способ - сжатие (компрессия) данных при их передаче по низкоскоростным каналам. Именно компрессия позволяет значительно увеличить пропускную способность линий при относительно небольших затратах на приобретение специального оборудования и ПО. При этом "прозрачная" работа удаленного пользователя в сети корпорации может быть обеспечена даже при передаче данных по обычным аналоговым телефонным линиям. Помимо несомненного выигрыша в скорости передачи больших объемов данных на большие расстояния, компрессия также является дополнительной мерой обеспечения защиты конфиденциальной информации при попытке ее несанкционированного перехвата во время передачи по каналам WAN.

Виды компрессии данных

Разнообразные продукты для сжатия данных в системах коммуникаций LAN-WAN можно подразделить на два больших класса: программное обеспечение и аппаратные средства.

Объем продаж программных продуктов сжатия данных до последнего времени значительно отставал от объема продаж аппаратных средств, однако, по мере широкого распространения таких популярных программ, как, например, DoubleSpace, Stacker, а также утилит серии PkZip, Arc, Arj и др., на этом сегменте рынка начался настоящий бум. В связи с этим аналитики предсказывают существенный рост объемов продаж программных средств сжатия данных: с 25 млн.долл. в 1993 г. до 160 млн.долл. в 1997 г. [3]. В то же время, программные продукты сжатия данных используются в основном для экономии места на магнитных носителях и не пригодны для работы в сети в режиме on-line. Такое программное обеспечение используется в режиме off-line - по кабельным линиям передаются уже предварительно сжатые данные.

Аппаратные устройства сжатия данных обычно обеспечивают менее высокую степень компрессии, и их стоимость зачастую значительно выше стоимости программных продуктов. Кроме того, существенным недостатком большинства аппаратных устройств является их ориентация на работу только с каким-либо одним видом приложений или типом данных. Однако, на сегодняшний день только устройства аппаратного сжатия данных могут обеспечить работу в приложениях реального времени, когда компрессия и передача данных по сети происходит практически одновременно. Широкое применение аппаратные средства компрессии находят также в области передачи видео- и аудиосигналов (например, различные виды плат обработки видеоизображения).

Исходя из способности сохранять целостность данных, все виды алгоритмов сжатия можно подразделить на те, которые обеспечивают компрессию без потери информации, и те, в результате применения которых часть исходной информации теряется.

Методы сжатия данных с потерей части информации обладают наивысшей степенью сжатия данных и высокой скоростью компрессии. Они находят применение в тех областях, где потеря незначительной части информации не является критичной - например, при передаче видеоизображения или звука. Примерами таких алгоритмов являются JPEG и MPEG, обеспечивающие коэффициенты сжатия до 20:1.

Для сжатия аудиосигнала, например, компания Gandalf разработала высокоэффективный алгоритм CELP (Codebook Excited Linear Prediction), являющийся комбинацией волновых (waveform) методов и методов кодирования источника (source coding). Суть волновых методов состоит в цифровом кодировании амплитуды аналогового сигнала, а кодирование источника заключается в использовании двух типов генераторов звуковых сигналов и меняющегося во времени фильтра. Звуковой сигнал разбивается на блоки, для каждого из которых определяется набор параметров: установки фильтра, амплитуда и т.д. Являясь достаточно эффективным с точки зрения степени сжатия, кодирование источника в то же время обеспечивает худшее качество сигнала по сравнению с волновыми методами. Алгоритм CLEP, объединяя возможности обоих методов, позволяет достичь высокой производительности при сохранении хорошего качества сигнала. В технологии CLEP применяется также таблица образцов звуковых сигналов (codebook), записанных в цифровом виде, которые сравниваются с входящим звуковым сигналом. Наиболее подходящий образец сигнала затем и пересылается на удаленный узел сети.

Для доступа в режиме on-line потеря или изменение в процессе сжатия даже одного бита информации приводит к "фатальным" последствиям: невозможности прочесть файл, зависанию или некорректной работе программного обеспечения и т.д. В связи с этим в большинстве приложений, в том числе и в компьютерных сетях, используются методы компрессии без потери информации, краткий обзор которых мы и дадим ниже. (Читателю, желающему получить более фундаментальные представления об алгоритмах сжатия информации, рекомендуем обратиться к работам [4, 5, 6]).

Основные методы компрессии

Теоретические основы методов сжатия информации были заложены в конце сороковых годов, когда была опубликована статья Клода Шеннона (Claude Shannon) "Математическая теория коммуникаций". В ней впервые было сформулировано положение о том, что энтропия любого блока информации равна вероятности его появления во всем массиве данных. Соответственно, наиболее часто повторяющиеся блоки являются и наиболее "избыточными" (redundant) и могут быть представлены в более сжатом виде. На сегодняшний день существует множество различных алгоритмов сжатия данных, подразделяющихся на несколько основных групп:

* алгоритмы кодирования повторов;
* вероятностные методы;
* арифметические методы;
* "метод словарей" (dictionary).

Не вдаваясь глубоко в математические подробности, рассмотрим основные принципы и особенности каждого вида алгоритмов.

Кодирование повторов (Run-Length Encoding)

Этот метод, являющийся одним из старейших и наиболее простых, сегодня используется в основном для сжатия графических файлов: одним из самых распространенных форматов, организованных при помощи этого типа компрессии, является формат PCX.

"Классический" вариант этого метода предусматривает замену последовательности повторяющихся символов на строку, содержащую сам этот символ, и число, показывающее, сколько раз этот символ повторяется. Например, строка 'AAAAAACCCCCEEEFFFFFF' будет записана в виде: '6A5C3E6F'. В то же время применение этого метода для сжатия текстовых или исполняемых (EXE, COM) файлов оказывается неэффективным.

Вероятностные методы сжатия

К вероятностным методам относятся алгоритмы Шеннона-Фэно (Shannon-Fano) и Хаффмана (Huffman). В основе этих алгоритмов лежит идея построения "дерева", положение символа на "ветвях" которого определяется частотой его появления в файле. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления символа в файле. Рассмотрим пример использования метода Шэннона-Фэно:

Пусть имеется слово METHOD. Допустим, что частота появления символов определяется в виде (табл. 1). Здесь мы используем произвольные значения вероятности появления символов исходя из того, что наиболее часто встречающиеся буквы английского языка - E, O, H. В каждом реальном массиве данных частота появления символов может отличаться от приведенной нами, однако это не влияет на принцип работы метода.

Симвoл Частота Код

M 2 011

E 8 00

T 3 010

H 4 110

O 6 10

D 1 111

Таблица. 1. Коды символов в строке "METHOD" (алгоритм Шеннона-Фэно).

Разделим строку "METHOD" на две части так, чтобы суммы частот появления символов в них были приблизительно равны:

2(M)+8(E)+3(T)*4(H)+6(O)+1(D). Теперь начнем строить "дерево" по схеме: на каждой "ветви" порции символов с большей частотой будет присваиваться двоичный ноль, а с меньшей - двоичная единица (рис. 2). В результате, каждый из символов получает свой код, по которому к нему можно добраться с вершины "дерева", при этом чем чаще встречается символ в файле, тем ближе он к вершине дерева и, значит, тем короче его адресный код.

Метод Хаффмана очень похож на метод Шеннона-Фэно, но строительство "дерева" в нем начинается не с "вершины", а с "корней" (рис. 3). Сумма частот появлений двух самых редко встречающихся символов (D и М) равна 3, символов Н и Т - 7. Далее, присваивая ветвям дерева двоичные нули и единицы, так же, как и в предыдущем методе, поднимаемся к "вершине", получая код для каждого символа.

Существуют две разновидности статистических методов, различающихся способом определения вероятности появления каждого символа в файле:
- статические (static), использующие фиксированную таблицу частоты появления символов в файле, рассчитываемую перед началом процесса сжатия;
- адаптивные (adaptive), в которых частота появления символов все время меняется - по мере считывания нового блока данных из файла происходит перерасчет начальных значений частот.

Статистические методы, характеризующиеся хорошим быстродействием и не требующие значительных ресурсов оперативной памяти, нашли широкое применение в многочисленных программах-архиваторах, например, ARC, PkZip и др.

Арифметические методы

Основные принципы арифметического кодирования были разработаны в конце 70-х годов. Арифметическое кодирование, так же как и вероятностные методы, использует в качестве основы технологии сжатия вероятность появления символа в файле, однако сам процесс арифметического кодирования имеет принципиальные отличия. В результате арифметического кодирования символьная последовательность (строка) заменяется действительным числом больше нуля и меньше единицы.

Рассмотрим процесс арифметического кодирования слова "REDUNDANCE" (избыточность). Частота появления каждой буквы в этом слове равна 0.1 за исключением букв E, D и N, которые встречаются дважды, и, соответственно, вероятность их появления равна 0.2. Далее каждой букве присваивается интервал вероятности (range), длина которого рассчитывается исходя из вероятности их появления в слове (табл. 2).

Буква Вероятность Интервал

A 0.1 0.0-0.1

C 0.1 0.1-0.2

D 0.2 0.2-0.4

E 0.2 0.4-0.6

N 0.2 0.6-0.8

R 0.1 0.8-0.9

U 0.1 0.9-1.0

Таблица 2. Интервалы вероятности для символов в слове Redundance.

Дальнейшую процедуру арифметического сжатия поясним с помощью табл. 3. Первая буква слова - 'R' - получает интервал с нижней границей 0.8 и с верхней - 0.9. Нижняя граница интервала и становится первой значащей цифрой кода. Затем производится расчет границ подинтервалов для каждой последующей буквы по алгоритму: нижняя граница нового интервала равна предыдущей нижней границе (для буквы Е это 0.8) плюс произведение предыдущего интервала (для буквы Е это будет интервал 0.9-0.8=0.1) и нижней (для расчета верхней границы интервала - верхней) границы интервала для буквы Е (эти значения соответственно равны 0.4 и 0.6; их берем из табл. 2). В результате, последовательность символов 'REDUNDANCE' заменяется числом 0.8478570048. Таким образом, вместо 10 байт необходимых для хранения символьной строки нам потребуется всего 4 байта для записи числа.

Символ Нижняя граница Верхняя граница

R 0.8 0.9

E 0.84 0.86

D 0.844 0.848

U 0.8476 0.848

N 0.84784 0.84792

D 0.847856 0.847872

A 0.8478560 0.848

N 0.84785696 0.84785728

C 0.847856992 0.847857024

E 0.8478570048 0.8478570432

Таблица 3. Пошаговое представление строки REDUNDANCE методом арифметического кодирования.

Арифметическое кодирование позволяет обеспечить высокую степень сжатия данных, особенно в случаях, когда мы имеем дело с данными, где частота появления различных символов сильно отличается друг от друга. В то же время сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся в сетевых приложениях из-за медленной работы алгоритма и, соответственно, существенного времени задержки при передаче пакета. Лишь появление мощных моделей RISC-процессоров позволило создать эффективные устройства арифметического сжатия данных.

Метод словарей

Алгоритм "метод словарей" был впервые описан в работах А.Лемпеля и Дж. Зива (Abraham Lempel, Jacob Ziv) в 1977-78 гг., поэтому этот метод часто называется Lempel-Ziv или сокращенно LZ. Hа сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение по сравнению с другими методами компрессии. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в файле ссылками на "образцы", хранящиеся в специально создаваемой таблице (словаре). Так, например, создав словарь, содержащий 65536 наиболее употребительных слов, можно представить текстовые файлы в виде последовательности 16-битовых ссылок на "место" данного слова в словаре.

На практике, конечно, мы имеем дело не с фиксированными словарями, а с таблицами, заполняемыми по мере сканирования файла. При этом уже просмотренная часть файла используется как словарь. Алгоритм основывается на движении по потоку данных скользящего "окна", состоящего из двух частей: большей по объему, в которой содержатся уже обработанные данные, и меньшей, в которую по мере просмотра помещается вновь считанная информация. Во время считывания каждой новой порции информации происходит проверка, и если оказывается, что такая строка уже помещена в словарь ранее, то она заменяется ссылкой на нее.

Множество модификаций метода LZ: LZW, LZ77, LZSS и др., активно используется в различных приложениях. Так, например, метод LZW применяется для сжатия данных в модемах категории V.42bis; LZ77-в утилитах PkZip, Stacker и DoubleSpace, а также во многих системах аппаратного сжатия данных.

Перспективы преодоления несовместимости

Многообразие методов (а также различных вариантов и модификаций каждого из методов) позволяет производителям аппаратных устройств сжатия данных выбрать оптимальный, исходя из требований, предъявляемых к работе в конкретных приложениях.

В то же время серьезной проблемой становится обеспечение совместимости различных моделей коммуникационного оборудования. Во многих случаях, приобретя один раз оборудование, пользователь оказывается "привязанным" к продукции именно этого производителя. В связи с этим возникла необходимость выработки единых стандартных программных и аппаратных методов сжатия информации. На выработку стандартных алгоритмов компрессии направлены усилия Консорциума производителей устройств CSU/DSU (Channel Service Unit/Data Service Unit).

----------------------------------------------------

Планируется, что будут разработаны два основных стандарта:

Стандартный алгоритм компрессии для синхронной передачи данных по коммутируемым или выделенным линиям со скоростями до 64 Кбит/с, в частности, по сетям протоколов Х25, System Network Architecture и др.
Стандарт сжатия данных для работы в сетях ISDN, T1/E1, а также в сетях с асинхронной передачей данных.

Литература

Remote Compression Bridges. A report from National Software Testing Laboratories Inc.//Communication Analyst. Datapro on CD-ROM, March, 1995
Peter Heywood Leased-Line Forecast: Deeper Price Cuts// Data Communications, February 1995, pp. 55-56D
M.K. Stillman - The market for Data Compression Products// San Jose: Electronic Trend Publications, 1994
Д.Мастрюков - Сжатие по Хаффмену// "Монитор", NN 7 - 8, 1993
Д.Мастрюков - Алгоритмы сжатия информации. Части 2-5// "Монитор", NN 1 - 4, 1994
Marc Nelson - The Data Compression Book// New York: M&T Books, 1992

При подготовке статьи использовался материал компании Gandalf "Data Compression. White paper"// Gandalf Technologies Inc., February 1995, 10 p.

Дмитрий Ведев