Файл: Методы кодирования данных (Задача кодирования).pdf

Для неслучайного сетевого кодирования можно использовать стандартные способы защиты от помех и искажений, используемых для простой передачи информации по сети. Однако, как отмечено в статье «LDPC coding schemes for error», пакеты, восстанавливаемые из линейных комбинаций, имеют большую вероятность быть принятыми с ошибкой, так как на них влияет вероятность ошибки сразу в двух пакетах, используемых для восстановления информации.

Рассматривая сеть «бабочка», можно показать, что для первого получателя вероятность принять пакет  A без ошибок больше, чем для пакета  B, даже если предположить одинаковые, но отличные от нуля вероятности ошибок в принятых получателем пакетах  A и A B. Для того, чтобы уменьшить подобный эффект авторы предлагают модифицировать способ итеративного декодирования пакетов A и B (например, при использовании LDPC-кодирования), когда итерации декодирования пакетов проводятся одновременно и декодеры обмениваются между собой об информации о вероятностях ошибок в конкретных битах пакетов. Для полного избавления от данного эффекта авторы предлагают также разбить исходные пакеты на несколько частей и передавать их различными путями. Как показал численный эксперимент, это действительно уравнивает вероятности декодирования пакетов.

Методы, используемые для декодирования в случайном сетевом кодировании, рассматривают все принятые пакеты как единый объект (часто – матрицу), построенной из принятых пакетов-строк. Если первая часть пакета представляет собой битовое поле, то операции с матрицей сводятся во-первых, к приведению левой её части к диагональному виду (с помощью метода Гаусса), а во-вторых к исправлению ошибок в правой части матрицы.

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

2.4. Способы коммутации

В традиционных телефонных сетях, связь абонентов между собой выполняется с помощью коммутации каналов связи. В начале коммутация телефонных каналов связи выполнялась вручную, далее коммутацию выполняли автоматические телефонные станции (АТС).

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

Коммутация — это процесс соединения различных абонентов коммуникационной сети через транзитные узлы. Коммуникационные сети должны обеспечивать связь своих абонентов между собой. Абонентами могут выступать ЭВМ, сегменты локальных сетей, факс-аппараты или телефонные собеседники.

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

Рассмотрим три основных наиболее распространенных способа коммутации абонентов в сетях:

• коммутация каналов (circuit switching);
• коммутация пакетов (packet switching);
• коммутация сообщений (message switching).

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

Время передачи сообщения при этом определяется пропускной способностью канала, длинной связи и размером сообщения.

Коммутаторы, а также соединяющие их каналы, должны обеспечивать одновременную передачу данных нескольких абонентских каналов. Для этого они должны быть высокоскоростными и поддерживать какую-либо технику мультиплексирования абонентских каналов.

Достоинства коммутации каналов:

• постоянная и известная скорость передачи данных;
• правильная последовательность прихода данных;
• низкий и постоянный уровень задержки передачи данных через сеть.

Недостатки коммутации каналов:

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

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

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

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

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

При коммутации пакетов все передаваемые пользователем сети сообщения разбиваются в исходном узле на сравнительно небольшие части, называемые пакетами. Необходимо уточнить, что сообщением называется логически завершенная порция данных - запрос на передачу файла, ответ на этот запрос, содержащий весь файл, и т. п. Сообщения могут иметь произвольную длину, от нескольких байт до многих мегабайт. Напротив, пакеты обычно тоже могут иметь переменную длину, но в узких пределах, например от 46 до 1500 байт (EtherNet). Каждый пакет снабжается заголовком, в котором указывается адресная информация, необходимая для доставки пакета узлу назначения, а также номер пакета, который будет использоваться узлом назначения для сборки сообщения.

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

Достоинства коммутации пакетов:

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

Недостатки коммутации пакетов:

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

Cпособы передачи пакетов в сетях:

• Дейтаграммный способ – передача осуществляется как совокупность независимых пакетов. Каждый пакет двигается по сети по своему маршруту и пользователю пакеты поступают в произвольном порядке.

Достоинства: простота процесса передачи.

Недостатки: низкая надежность за счет возможности потери пакетов и необходимость программного обеспечения для сборки пакетов и восстановления сообщений.

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

Достоинства: сохраняется естественная последовательность данных; устойчивые пути следования трафика; возможно резервирование ресурсов.

Недостатки: сложность аппаратной части.

Глава 3.Программное кодирование

3.1. Исходный код

Исходный код (также исходный текст)  – текст компьютерной программы на каком-либо языке программирования или языке разметки, который может быть прочтён человеком.

В обобщённом смысле  – любые входные данные для транслятора. Исходный код транслируется в исполняемый код целиком до запуска программы при помощи компилятора или может исполняться сразу при помощи интерпретатора. Исходный код либо используется для получения объектного кода, либо выполняется интерпретатором. Изменения выполняются только над исходным, с последующим повторным преобразованием в объектный. Другое важное назначение исходного кода – в качестве описания программы. По тексту программы можно восстановить логику её поведения. Для облегчения понимания исходного кода используются комментарии. Существуют также инструментальные средства, позволяющие автоматически получать документацию по исходному коду – т. н. генераторы документации. Кроме того, исходный код имеет много других применений. Он может использоваться как инструмент обучения; начинающим программистам бывает полезно исследовать существующий исходный код для изучения техники и методологии программирования. Он также используется как инструмент общения между опытными программистами благодаря своей лаконичной и недвусмысленной природе. Совместное использование кода разработчиками часто упоминается как фактор, способствующий улучшению опыта программистов.

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

3.2. Организация

Исходный код некоторой части ПО (модуля, компонента) может состоять из одного или нескольких файлов. Код программы не обязательно пишется только на одном языке программирования. Например, часто программы, написанные на языке Си, из соображений оптимизации, содержат вставки кода на языке ассемблера. Также возможны ситуации, когда некоторые компоненты или части программы пишутся на различных языках, с последующей сборкой в единый исполняемый модуль при помощи технологии, известной как компоновка библиотек (library linking).