Сетевое кодирование — раздел теории информации, изучающий вопрос оптимизации передачи данных по сети с использованием техник изменения пакетов данных на промежуточных узлах.
Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»[1]. Рассмотрим сеть, показанную на рисунке, в которой есть один или два источника, генерирующего пакеты A и B, поступающих на вход сети «бабочка». Первые узлы, отвечающие за передачу информации, передают по одному пакету (A слева и B справа) на вход конечным узлам получателям. Также они передают эти пакеты промежуточному узлу, который, вместо передачи двух пакетов по очереди (и потере времени) комбинирует эти пакеты, например, с помощью операции XOR и передаёт далее.
Узлы-получатели имеют возможность восстановить исходные пакеты из информации об одном полученном пакете и их комбинации. В результате увеличивается пропускная способность сети — по два пакета может быть передано двум получателям одновременно (за каждый такт), хотя минимальное сечение сети содержит всего три канала передачи данных.
В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве[2]. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах.
В качестве основного способа рассматривается включение в передаваемый пакет дополнительной информации, идентифицирующей пакет в рамках некоторой сессии (считается, что комбинироваться могут пакеты, принадлежащие только одной сессии). Например, это может быть простое битовое поле. Для рассмотренной выше сети «бабочка» данное битовое поле может состоять из двух бит для каждого пакета:
Первый получатель получит два пакета с битовыми полями «1 0» и «1 1», второй получатель — «0 1» и «1 1». Используя это поле как информацию о коэффициентах линейного уравнения для пакетов, получатель может восстановить исходные пакеты, если они были переданы без ошибок.