берчун

Кадр LLC уровня передается на МАС-уровень, где инкапсулируется в кадр соответствующей технологии данного уровня. При этом флаги кадра LLC отбрасываются. Технология Ethernet предусматривает четыре формата кадров: 802.3/LLC, Raw 802.3/Novell 802.3, Ethernet DIX/Ethernet II, Ethernet SNAP

Рассмотрим основной тип Ethernet DIX/Ethernet II

Perambule (Перамбула) - используется для синхронизации, состоит из 8 байт.

DA (Destination Address) - mac адрес узла назначения, состоит из 8 байт.

SA (Source Address) - mac адрес узла источника, состоит из 8 байт.

Type/Length - длину или тип, числовое значение этого поля определяет его смысл: если значение меньше

1500, то это поле длины, а если больше это тип.

Data — данные, могут быть от 46 до 1500 байт.

FCS (Frame Check Sequence) - контрольная сумма, состоит из 4-х байтов, служит для обнаружения ошибок в полученном кадре, использует алгоритм проверки на основе циклического кода.

63. Алгоритм Дейкстры

Известнo, что все цены неотрицательны. Найти наименьшую стоимость проезда 1->i

для всех i=1..n за время O(n2).

В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:

для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

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

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

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

При самом бесхитростном способе хранения множества выделенных городов (в булевском векторе) добавление одного города к числу выделенных требует времени O(n).

Схема алгоритма Дейкстры

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив S содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие расстояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний A[i,k] задает длины дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое число Б, равное "машинной бесконечности".

1 (инициализация). В цикле от 1 до N заполнить нулями массив S; заполнить числом i массив C; перенести i-ю строку матрицы A в массив B,

S[i]:=1; C[i]:=0 (i - номер стартовой вершины)

2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для

которых S[k]=0); пусть минимум достигается на индексе j, т. е.

B[j]<=B[k]

Затем выполняются следующие операции:

S[j]:=1;

если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)

(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj

Vk).

(Если все S[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).

3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)

3.1.z:=C[k];

3.2.Выдать z;

3.3.z:=C[z]. Если z = О, то конец,

иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).

Отыскании кратчайшего пути имеет естественную интерпретацию в терминах матриц.

Пусть A - матрица цен одной аваиакомпании, а B - матрица цен другой. (Мы считаем, что диагональные элементы матриц равны 0.) Пусть мы хотим лететь с одной пересадкой, причем сначала самолетом компании A, а затем - компании B. Сколько нам придется заплатить, чтобы попасть из города i в город j?

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

Обычное (не модифицированное) умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть не все рейсы (как в следующем разделе), а только некоторые, a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый элемент.

Он равен числу различных способов попасть из i в j за k рейсов.

Случай, когда есть не все рейсы, можно свести к исходному, введя фиктивные рейсы с бесконечно большой (или достаточно большой) стоимостью.

67. Таблица IP-маршрутизации

Обновлено: Апрель 2011 г.

Назначение: Windows Server 2003, Windows Server 2003 R2, Windows Server 2003 with SP1, Windows Server 2003 with SP2

Таблица IP-маршрутизации

Каждый компьютер, использующий протокол TCP/IP, принимает решения по маршрутизации. Эти решения основываются на таблице IP-маршрутизации. Чтобы вывести на экран таблицу IP-маршрутизации на компьютере с операционной системой Windows Server 2003, введите в командной строке командуroute print.

В следующей таблице показан пример таблицы IP-маршрутизации. Этот пример соответствует компьютеру с Windows Server 2003, Стандартный выпуск, имеющему одну сетевую плату с пропускной способностью до 10 Мбит/с и следующую конфигурацию:

IP-адрес: 10.0.0.169

Маска подсети: 255.0.0.0

Основной шлюз: 10.0.0.1

Примечание

Описания, приведенные в первом столбце этой таблицы, не выводятся командой route print.

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

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

Поскольку маршрутизатор, соответствующий основному шлюзу, имеет информацию об идентификаторах сети других IP-подсетей в более крупной сети, он перенаправляет датаграмму другим маршрутизаторам; этот

процесс продолжается до тех пор, пока датаграмма не достигнет IP-маршрутизатора, подключенного к узлу назначения или к подсети, в которой находится этот узел.

В следующих разделах описаны все столбцы выводимой на экран таблицы IP-маршрутизации: «Сетевой адрес», «Маска», «Адрес шлюза», «Интерфейс» и «Метрика».

Сетевой адрес

Сетевые адреса используются совместно с масками для определения IP-адреса назначения. Сетевой адрес может находиться в диапазоне от 0.0.0.0 (маршрут по умолчанию) до 255.255.255.255 (адрес ограниченной широковещательной рассылки, используемый для отправки сообщений всем узлам данного сегмента сети).

Маска сети

Маска — это маска подсети, накладываемая на IP-адрес назначения для сравнения его с сетевым адресом. Если маску записать как двоичное число, то два бита сравниваемых адресов, для которых соответствующий бит маски имеет значение «1», должны совпадать, а те два бита, которым соответствует нулевой бит маски, совпадать не обязаны. Например, маршрут по умолчанию использует маску сети 0.0.0.0, которая преобразуется в двоичное значение 0.0.0.0, то есть не требует совпадения битов. Маршрут к узлу (маршрут, совпадающий с IP-адресом) использует маску сети 255.255.255.255, которая преобразуется в двоичное значение

11111111.11111111.11111111.11111111, то есть требует совпадения всех битов.

Адрес шлюза

Адрес шлюза — это IP-адрес, который локальный узел использует для перенаправления IP-датаграмм в другие IP-сети. Это может быть либо IP-адрес локальной сетевой платы, либо IP-адрес IP-маршрутизатора (например, адрес основного шлюза) в локальном сегменте сети.

Интерфейс

Интерфейс — это IP-адрес локального сетевого интерфейса, который используется для перенаправления IPдатаграмм в сети.

Метрика

Метрика показывает стоимость использования маршрута, обычно выражаемую числом прыжков до IP-адреса назначения. Вся локальная подсеть считается одним прыжком, а каждый проходимый маршрутизатор добавляет один дополнительный прыжок. Если к одному и тому же месту ведут несколько маршрутов с различными метриками, то выбирается маршрут с наименьшей метрикой.

Сведения о добавлении маршрутов в таблицу IP-маршрутизации см. в разделе Добавление статического IPмаршрута. Сведения об удалении маршрутов из таблицы IP-маршрутизации см. в разделе Удаление статического IP-маршрута.

Узлы с несколькими сетевыми интерфейсами

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

Сетевая плата 1 (10 МБ)

IP-адрес: 10.0.0.169

Маска подсети: 255.0.0.0

Основной шлюз: 10.0.0.1

Сетевая плата 2 (100 МБ)

IP-адрес: 192.168.0.200

Маска подсети: 255.255.0.0

Основной шлюз: 192.168.0.1

Примечание

Описания, приведенные в первом и втором столбцах этой таблицы, не выводятся командой route print.

Сведения о включении перенаправления IP-датаграмм на компьютере с несколькими сетевыми интерфейсами и операционной системой Windows Server 2003 см. в разделе Включение службы маршрутизации и удаленного доступа.

Примечания

Настраивая основной шлюз для каждой сетевой платы, вы тем самым создаете маршрут 0.0.0.0 для каждой сетевой платы. Однако в действительности используется только один маршрут по умолчанию. В предыдущем примере IP-адрес 10.0.0.169 является адресом первой сетевой платы в привязке TCP/IP, поэтому будет использоваться маршрут по умолчанию для сетевой платы 1. Так как используется только один основной шлюз, его настройка требуется только для одной сетевой платы. Такой подход позволяет избежать путаницы и добиться нужных результатов.

Если IP-маршрутизатор является сервером под управлением Windows Server 2003 и не имеет интерфейса с нужной сетью, ему требуется маршрут к этой сети. В таком случае можно воспользоваться либо

68. Формат заголовка IP-дейтаграммы

IP-дейтаграмма состоит из заголовка и данных.

Заголовок дейтаграммы состоит из 32-разрядных слов и имеет переменную длину, зависящую от размера поля «Options», но всегда кратную 32 битам. За заголовком непосредственно следуют данные, передаваемые в дейтаграмме.

Формат заголовка:

Значения полей заголовка следующие.

Ver (4 бита) – версия протокола IP, в настоящий момент используется версия 4, новые разработки имеют номера версий 6-8.

IHL (Internet Header Length) (4 бита) – длина заголовка в 32-битных словах; диапазон допустимых значений от 5 (минимальная длина заголовка, поле «Options» отсутствует) до 15 (то есть может быть максимум 40 байт опций).

TOS (Type Of Service) (8 бит) – значение поля определяет приоритет дейтаграммы и желаемый тип маршрутизации. Структура байта TOS:

Три младших бита («Precedence») определяют приоритет дейтаграммы: 111 управление сетью 110 межсетевое управление

101 CRITIC-ECP

100 более чем мгновенно

011 мгновенно

010 немедленно

001 срочно

000 обычно

Биты D, T, R, C определяют желаемый тип маршрутизации: D (Delay) – выбор маршрута с минимальной задержкой,

T (Throughput) – выбор маршрута с максимальной пропускной способностью, R (Reliability) – выбор маршрута с максимальной надежностью,

C (Cost) – выбор маршрута с минимальной стоимостью.

В дейтаграмме может быть установлен только один из битов D, T, R, C. Старший бит байта не используется. Реальный учет приоритетов и выбора маршрута в соответствии со значением байта TOS зависит от

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

Total Length (16 бит) – длина всей дейтаграммы в октетах, включая заголовок и данные, максимальное значение 65535, минимальное – 21 (заголовок без опций и один октет в поле данных).

ID (Identification) (16 бит), Flags (3 бита), Fragment Offset (13 бит) используются для фрагментации и сборки дейтаграмм и будут подробнее рассмотрены ниже в п. 2.4.1.

TTL (Time To Live) (8 бит) – «время жизни» дейтаграммы. Устанавливается отправителем, измеряется в секундах. Каждый маршрутизатор, через который проходит дейтаграмма, переписывает значение TTL, предварительно вычтя из него время, потраченное на обработку дейтаграммы. Так как в настоящее время скорость обработки данных на маршрутизаторах велика, на одну дейтаграмму тратится обычно меньше секунды, поэтому фактически каждый маршрутизатор вычитает из TTL единицу. При достижении значения TTL=0 дейтаграмма уничтожается, при этом отправителю может быть послано соответствующее ICMP-сообщение. Контроль TTL предотвращает зацикливание дейтаграммы в сети.

Protocol (8 бит) – определяет программу (вышестоящий протокол стека), которой должны быть переданы данные дейтаграммы для дальнейшей обработки. Коды некоторых протоколов приведены в табл. 2.4.1.

Таблица 2.4.1

Header Checksum (16 бит) – контрольная сумма заголовка, представляет из себя 16 бит, дополняющие биты в сумме всех 16-битовых слов заголовка. Перед вычислением контрольной суммы значение поля «Header Checksum» обнуляется. Поскольку маршрутизаторы изменяют значения некоторых полей заголовка при обработке дейтаграммы (как минимум, поля «TTL»), контрольная сумма каждым маршрутизатором пересчитывается заново. Если при проверке контрольной суммы обнаруживается ошибка, дейтаграмма уничтожается.

Source Address (32 бита) – IP-адрес отправителя. Destination Address (32 бита) – IP-адрес получателя.

Options – опции, поле переменной длины. Опций может быть одна, несколько или ни одной. Опции определяют дополнительные услуги модуля IP по обработке дейтаграммы, в заголовок которой они включены. Подробнее опции рассматриваются в пп. 2.4.3, 2.4.4.

Padding – выравнивание заголовка по границе 32-битного слова, если список опций занимает нецелое число 32битных слов. Поле «Padding» заполняется нулями.

69. Краткий обзор.

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

Internet.

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

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

Внутренние — группа сетей, которые являются объектом трансляции.

Внешние — все другие адреса. Обычно это легальные адреса, локализованные в Internet.

Внутренний локальный IP-адрес — IP-адрес, назначенный хосту (host) во внутренней сети. Такой адрес либо глобальный уникальный (но устаревший, распределенный из области RFC 1918), либо только что выбранный из ThinAir. Такой адрес может быть или не быть глобально маршрутизируемым; но если он глобально маршрутизируемый, он может фактически принадлежать другой организации.

Внутренний глобальный IP-адрес — IP-адрес внутреннего хоста, который оказывается во внешнем мире. Такой адрес распределялся из области глобальных уникальных адресов, обычно предоставляется провайдером услуг Internet (ISP).

Простой трансляционный элемент — трансляционный элемент, который преобразует один IPадрес в другой.

Расширенный трансляционный элемент — трансляционный элемент, который преобразует один IP-адрес и порт в другие.

Основные функции.

Трансляция статических адресов — Telnet 207.33.94.1.

Пользователь может задать взаимно однозначное соответствие между внутренними локальными и глобальными адресами.

Трансляция адресов динамического источника.

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

Трансляция динамического порта.

Пользователь может хранить адреса в глобальном адресном пуле путем трансляции исходных портов в соединениях TCP (Протокол управления передачей) или в диалоговом режиме протокола UDP (Протокол пользовательских дейтаграмм). Различные локальные адреса будут преобразовываться в те же самые глобальные адреса с помощью трансляции порта, обеспечивающей необходимую уникальность. Когда появляется необходимость в трансляции, новый номер порта выбирается из того же интервала, что и первоначальный, на основе стандарта Беркли (BSD): (1->511, 512->1023, 1024->4999, 5000->65535)

Ротационная трансляция адресов пунктов назначения.

Для трафика "внешние к внутренним" можно сконфигурировать динамическую трансляцию адресов пунктов назначения. Когда соответствие установлено, адрес пункта назначения, соответствующий одному из адресов списка доступа, будет заменяться на адрес из ротационного пула. Назначение производится по циклическому (карусельному) принципу и выполняется только в том случае, если открывается новое соединение из "внешних к внутренним". Весь не TCPтрафик пропускается без трансляции (если не задействованы другие трансляторы).

Поддерживаемые типы трафика.

Следующие протоколы/приложения поддерживаются Cisco IOS NAT:

Любой протокол на базе TCP, который не содержит IP-адрес источника или пункта назначения в блоке данных сегмента. Сюда входят протоколы: ICMP, HTTP, BSD rcmd (rcp, rsh, rlogin), SMTP и другие.

Любой протокол на базе UDP, который не содержит IP-адрес источника или пункта назначения в блоке данных сегмента. Сюда входят протоколы: TFTP, NTP и другие.

Telnet (RFC 854)

ICMP (RFC 1256) Протокол управляющих сообщений Internet.

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