Network Working Group                      Jeffrey Mogul
Request for Comments: 922    Computer Science Department
                                     Stanford University
                                            October 1984

Широковещательная рассылка дейтаграмм IP при наличии подсетей

BROADCASTING INTERNET DATAGRAMS IN THE PRESENCE OF SUBNETS

PDF

Статус документа

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

Этот документ содержит стандарт, предложенный сообществу ARPA-Internet, и служит запросом на обсуждение с целью совершенствования протокола. Документ может распространяться свободно.

Благодарности

Этот документ был создан в результате дискуссий с целой группой специалистов. Особенно отмечу вклад J. Noel Chiappa и Christopher A. Kent.

1. Введение

Использование широковещательной адресации (особенно в скоростных ЛВС) обеспечивает хорошую базу для множества приложений. Поскольку широковещательная адресация не рассматривается в базовой спецификации IP [12], не существует согласованного способа использования широковещательных адресов и разработчики не могут пользоваться такой адресацией (этот вопрос поднимался и ранее – например, в работе [6], но стандарт не был предложен).

В этой работе рассматривается только случай широковещательной рассылки дейтаграмм без гарантии доставки и использования порядковых номеров, а также с возможностью дублирования (вопросы широковещательной рассылки TCP рассматриваются в работе [10].) Широковещательная рассылка дейтаграмм достаточно эффективна [1], несмотря на отсутствие гарантий доставки и ограниченные размеры дейтаграмм.

Мы предполагаем, что канальный уровень локальной сети поддерживает эффективный механизм широковещания (например, Ethernet [7, 5], ChaosNet [9], token ring [2] и т. п.).

Никаких предположений о надежности широковещания не делается (этот вопрос может решаться на уровне протоколов, лежащих над IP). Гарантированная доставка широковещательных пакетов – дорогое удовольствие и взамен просто делается предположение, что хост будет получать большую часть переданных широковещательных пакетов. Важно избежать чрезмерного использования широковещания, поскольку все хосты будут тратить свои ресурсы на обработку каждого широковещательного пакета.

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

2. Терминология

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

Локальная сеть (Local Hardware Network)

Физическая сеть, к которой подключен хост.

Удаленная физическая сеть (Remote Hardware Network)

Физическая сеть, отделенная от хоста по крайней мере одним маршрутизатором.

Набор физических сетей (Collection of Hardware Networks)

Набор физических сетей, соединенных через маршрутизаторы.

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

Internet

Набор IP-сетей DARPA Internet.

Сеть IP (IP Network)

Одна или несколько физических сетей, имеющих общий номер IP.

Подсеть (Subnet)

Один из элементов набора физических сетей, составляющих сеть IP. Хосты подсети используют такие же номера сети IP, как и хосты других подсетей данной сети IP, но локальная часть адреса делится на номер подсети и номер хоста. Мы не делаем никаких предположений о делении локальной части адреса, поскольку способ деления может варьироваться в разных сетях.

Введение уровня подсетей в иерархию адресов является отклонением от спецификации IP [12], но, поскольку подсети используются все шире, схема широковещания должна поддерживать подсети. Дополнительную информацию о подсетях вы найдете в работе [8].

В этом документе термин «адрес хоста» относится к связанной с хостом локальной части адреса (номер хоста в подсети – host-on-subnet address) при использовании подсетей или всему локальному адресу (номер хоста в сети – host-part) в остальных случаях.

Сеть IP может состоять из одной или множества физических сетей – с точки зрения хостов других IP-сетей это не имеет значения.

3. Зачем нужно широковещание?

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

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

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

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

Более подробное рассмотрение широковещательных приложений приводится в работах [1, 3].

4. Классы широковещания

Существует несколько классов широковещания IP:

• Широковещательная рассылка дейтаграмм с конкретным адресом получателя через локальную сеть IP – дейтаграммы направлены конкретному адресату, но передающий хост использует широковещание на канальном уровне (возможно, для того, чтобы избежать маршрутизации). Поскольку такое широковещание не относится к IP, уровень IP не участвует в широковещательной рассылке (за исключением того, что он обеспечивает отбрасывание дейтаграмм без уведомления).
• Широковещательная рассылка всем хостам локальной сети IP – в качестве номера хоста используется специальное значение¹. Принимающий уровень IP должен распознавать такой адрес, как свой собственный.
  Однако, на вышележащих уровнях может быть полезно различие между широковещательными и обычными дейтаграммами (особенно на маршрутизаторах). Этот вариант широковещания наиболее полезен – он позволяет хостам детектировать шлюзы (маршрутизаторы) без использования протоколов преобразования адресов, а также обеспечивает возможность работы с серверами имен, серверами времени и другими службами без использования явного адреса.
• Широковещательная рассылка всем хостам удаленной сети IP – в некоторых случаях такая рассылка может оказаться полезной (например, для поиска последней версии базы данных с именами хостов, удаленной загрузки или мониторинга сетевой службы точного времени). Этот случай совпадает с широковещательной рассылкой в локальной сети – дейтаграмма передается обычным путем, пока она не попадет на маршрутизатор, подключенный к сети-адресату, который и организует широковещательную рассылку в своей локальной сети. Этот класс называется направленным широковещанием (directed broadcasting) или letter bomb [1].
• Широковещательная рассылка всем хостам сети IP, разделенной на подсети (мультисегментное широковещание – Multi–subnet broadcasts) – для обозначения всех подсетей (all subnets) используется специальный адрес IP². Широковещательная рассылка всем хостам удаленной сети IP, разбитой на подсети, осуществляется с использованием направленного широковещания для отдельных подсетей.
• Широковещательная рассылка в масштабе Internet: такая рассылка вряд ли полезна и, во всяком случае, нежелательна.

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

5. Методы широковещания

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

Вопросы оптимизации широковещательной рассылки подробно рассмотрены в работах [1, 3, 4, 13, 14]. Поскольку мы предполагаем, что эта проблема уже решена на канальном уровне, хост IP, желающий передать широковещательную дейтаграмму в локальную или удаленную сеть (directed broadcast), должен лишь указать подходящий адрес получателя и передать дейтаграмму обычным путем. Изощренные алгоритмы обработки широковещания требуются только шлюзам.

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

• Формат дейтаграмм IP не должен изменяться.
• Должна обеспечиваться разумная эффективность с учетом числа избыточных копий и стоимости выбора пути.
• Минимальные изменения для шлюзов (как для кода, так и для пространства данных).
• Высокая вероятность доставки дейтаграмм.

Лучшим вариантом представляется метод RPF (Reverse Path Forwarding – рассылка по обратному пути) [4]. Хотя алгоритм RPF не совсем оптимален с точки зрения стоимости и надежности доставки, он достаточно хорош и очень прост в реализации, а также не требует дополнительного пространства данных на шлюзах.

6. Шлюзы и рассылка широковещательных дейтаграмм

Основная сложность поддержки широковещания ложится на шлюзы. Если шлюз получает directed broadcast для сети, к которой он не подключен непосредственно, такая дейтаграмма просто пересылается с использованием обычных механизмов. Если же широковещательная дейтаграмма адресована в одну из подключенных к маршрутизатору сетей, требуется выполнение дополнительных операций.

6.1. Локальное широковещание

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

• Основным правилом предотвращения петель является следующее: «никогда не пересылать дейтаграмму в широковещательном режиме в физическую сеть, из которой она была принята». Достаточно сложно избежать повтора дейтаграмм, которые шлюз принял от себя. Это правило позволяет избавиться от повтора дейтаграмм, которые шлюз принял от самого себя; сохраняется возможность возникновения петель при наличии нескольких шлюзов в одной физической сети.
• Если дейтаграмма получена из физической сети, в которую она адресована, такую дейтаграмму не следует пересылать. Однако, шлюзу следует рассматривать себя как получателя таких дейтаграмм (например, они могут использоваться при рассылке маршрутных обновлений).
• В остальных случаях, если дейтаграмма адресована в физическую сеть, к которой подключен шлюз, она должна быть передана в эту сеть с использованием широковещательной адресации на канальном уровне. Шлюз в этом случае также должен рассматривать себя, как получателя дейтаграммы.

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

6.2. Широковещание во множество подсетей

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

Этот алгоритм можно усовершенствовать, если маршрутизаторы (все или часть) будут обмениваться между собой дополнительной информацией (этот обмен можно сделать совершенно прозрачным с точки зрения хостов и даже других шлюзов). Дополнительную информацию о таком усовершенствовании можно найти в работах [4, 3].

6.3. Псевдо-код алгоритма маршрутизации

На рисунке 1 показан псевдо-код алгоритма, который следует использовать шлюзам. Ниже приведены определения использованных при описании алгоритма терминов.

RouteLink(хост)

Функция, принимающая адрес хоста в качестве параметра и возвращающая канал для первого интервала пути от шлюза к хосту.

RouteHost(хост)

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

ResolveAddress(хост)

Эта функция возвращает аппаратный адрес хоста по адресу IP.

IncomingLink

Канал, на который прибывает пакет.

OutgoingLinkSet

Набор каналов, в которые пакет должен следует передать.

OutgoingHardwareHost

Аппаратный адрес хоста, которому передается пакет.

Destination.host

Связанная с хостом часть адреса получателя (номер хоста).

Destination.subnet

Номер подсети в адресе получателя.

Destination.ipnet

Номер сети IP в адресе получателя.

BEGIN
   IF Destination.ipnet IN AllLinks THEN
   BEGIN
      IF IsSubnetted(Destination.ipnet) THEN
      BEGIN
         IF Destination.subnet = BroadcastSubnet THEN
         BEGIN /* используется алгоритм RPF */
            IF IncomingLink = RouteLink(Source) THEN
            BEGIN IF Destination.host = BroadcastHost THEN
               OutgoingLinkSet <- AllLinks -
               IncomingLink;
               OutgoingHost <- BroadcastHost;
               Проверка возможности внутреннего использования пакета;
            END
            ELSE /* отбрасывание дубликатов от других шлюзов */
               Discard;
         END
         ELSE
            IF Destination.subnet = IncomingLink.subnet THEN
            BEGIN /* пересылка будет порождать петлю */
               IF Destination.host = BroadcastHost THEN
                  Проверка возможности внутреннего использования пакета;
               Discard;
            END
            ELSE BEGIN /* пересылка в (возможно локальную) подсеть */
               OutgoingLinkSet <- RouteLink(Destination);
               OutgoingHost <- RouteHost(Destination);
            END
         END
         ELSE BEGIN /* пакет адресован в одну из локальных сетей */
            IF Destination.ipnet = IncomingLink.ipnet THEN
               BEGIN /* пересылка будет порождать петлю */
                  IF Destination.host = BroadcastHost THEN
                     Проверка возможности внутреннего использования пакета;
                  Discard;
               END
               ELSE BEGIN /* может быть широковещательным */
                  OutgoingLinkSet <- RouteLink(Destination);
                  OutgoingHost <- RouteHost(Destination);
               END
            END
         END
         ELSE BEGIN /* пересылка в удаленную сеть IP */
            OutgoingLinkSet <- RouteLink(Destination);
            OutgoingHost <- RouteHost(Destination);
         END
         OutgoingHardwareHost <- ResolveAddress(OutgoingHost);
      END

Рисунок 1: Код Pseudo-Algol для алгоритма маршрутизации широковещательных дейтаграмм.

7. Соглашение о широковещательных адресах IP

Для совместимости реализаций IP они должны поддерживать специальный номер для обозначения всех хостов сети (all hosts) и всех подсетей (all subnets).

Поскольку сетевой уровень локальной сети всегда отображает адреса IP на адреса канального уровня, выбор «широковещательного номера хоста» IP является в какой-то степени произвольным. Для простоты этот номер не должен совпадать ни с одним из реальных номеров хостов. Номер, содержащий только «1», удовлетворяет этому требованию; использование таких номеров для широковещания было впервые предложено в работе [6]. Такие номера достаточно редко применяются для реальных хостов, поэтому использование этого номера для широковещательной рассылки, скорей всего, не потребует каких-либо изменений в конфигурации сети.

Номер «все подсети» (all subnets) также содержит только 1 – это означает, что хост, желающий передать дейтаграмму всем хостам удаленной сети IP может ничего не знать о подсетях удаленной сети. Например, 36.255.255.255 может указывать на все хосты одной физической сети или все хосты разделенной на подсети IP-сети (например, 1 байт содержит поле подсети, а 2 байта – номер хоста; возможно и любое другое разделение на подсети).

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

Таким образом, хост сети с номером 36 (например) может:

• рассылать дейтаграммы своим непосредственным соседям по локальной сети, используя адрес 255.255.255.255;
• рассылать широковещательные дейтаграммы по всей сети 36, используя адрес 36.255.255.255,

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

Если «все единицы» в поле адреса IP используются для широковещания, значение «все нули» можно использовать для неуказанного адреса. Возможно это является причиной появления таких значений в поле отправителя дейтаграмм ICMP Information Request. Однако в соответствии с соглашением о нотации такие адреса (все нули) используются для обозначения сетей³. Например, 36.0.0.0 означает “сеть номер 36″, а 36.255.255.255 – широковещательный адрес «все хосты сети 36”.

7.1. Широковещательные адреса и серверы ARP

Протокол преобразования адресов ARP, описанный в [11], может при некорректной реализации порождать проблемы, связанные с использованием широковещания в сетях, где не все хосты понимают, какой адрес является широковещательным. Возникает искушение изменить сервер ARP так, чтобы он мог обеспечивать отображение широковещательных адресов IP в широковещательные аппаратные адреса. Этому искушению не следует поддаваться. Серверу ARP никогда не следует давать отклики на запросы, в которых получатель задан широковещательным адресом. Такие запросы могут исходить только от хостов, которые не распознают этот адрес в качестве широковещательного (это легко приводит к возникновению петель в пересылке). Если имеется N таких хостов в физической сети, тогда дейтаграмма, переданная со значением TTL = T, может привести к генерации T^N повторных широковещательных дейтаграмм.

8. Литература

1. David Reeves Boggs. Internet Broadcasting. Ph.D. Th., Stanford University, January 1982.

2. D.D. Clark, K.T. Pogran, and D.P. Reed. “An Introduction to Local Area Networks”. Proc. IEEE 66, 11, pp1497-1516, November 1978.
3. Yogan Kantilal Dalal. Broadcast Protocols in Packet Switched Computer Networks. Ph.D. Th., Stanford University, April 1977.
4. Yogan K. Dalal and Robert M. Metcalfe. “Reverse Path Forwarding of Broadcast Packets”. Comm. ACM 21, 12, pp1040-1048, December 1978.
5. The Ethernet, A Local Area Network: Data Link Layer and Physical Layer Specifications. Version 1.0⁴, Digital Equipment Corporation, Intel, Xerox, September 1980.
6. Robert Gurwitz and Robert Hinden. IP – Local Area Network Addressing Issues. IEN-212⁵, BBN, September 1982.
7. R.M. Metcalfe and D.R. Boggs. “Ethernet: Distributed Packet Switching for Local Computer Networks”⁶. Comm. ACM 19, 7, pp395-404, July 1976. Also CSL-75-7, Xerox Palo Alto Research Center, reprinted in CSL-80-2.
8. Jeffrey Mogul. Internet Subnets. RFC 917, Stanford University, October 1984.
9. David A. Moon. Chaosnet. A.I. Memo 628, Massachusetts Institute of Technology Artificial Intelligence Laboratory, June 1981.
10. William W. Plummer. Internet Broadcast Protocols. IEN-10⁸, BBN, March 1977.
11. David Plummer. An Ethernet Address Resolution Protocol. RFC 826, Symbolics, September 1982.
12. Jon Postel. Internet Protocol. RFC 791, ISI, September 1981.
13. David W. Wall. Mechanisms for Broadcast and Selective Broadcast. Ph.D. Th., Stanford University, June 1980.

14. David W. Wall and Susan S. Owicki. Center-based Broadcasting. Computer Systems Lab Technical Report TR189, Stanford University, June 1980.

---

Перевод на русский язык

Николай Малых

nmalykh@protokols.ru