Канальный уровень - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:14Z

rollbackEdits.php mass rollback

103.251.167.21 в 05:04, 1 сентября 2022

2022-09-01T05:04:49Z

Gromak: /* Протоколы */

2015-04-03T13:44:36Z

‎Протоколы

Gromak: /* Протоколы с выборочным повтором */

2015-04-03T13:43:39Z

‎Протоколы с выборочным повтором

Gromak: /* Протоколы с возвратом на N */

2015-04-03T13:41:48Z

‎Протоколы с возвратом на N

Gromak: /* Общие объявления */

2015-04-03T13:39:42Z

‎Общие объявления

Gromak в 13:37, 3 апреля 2015

2015-04-03T13:37:20Z

Внесённые изменения

Gromak: Новая страница: «== Сервисы, подуровни == TODO == Протоколы == На канальном уровне нужно передавать данные с се...»

2015-04-03T13:19:04Z

Новая страница: «== Сервисы, подуровни == TODO == Протоколы == На канальном уровне нужно передавать данные с се...»

Новая страница

== Сервисы, подуровни ==
TODO

== Протоколы ==
На канальном уровне нужно передавать данные с сетевого уровня. При этом требуется, чтобы кадры не дублировались, и сохранялся порядок. Ниже представлены протоколы с различными допущениями о канале от самого простого случая (с идеальным каналом) к более сложным. Сначала даётся краткое словесное описание, затем сишный псевдокод, из которого всё понятно.

TODO: хорошо бы эти картиночки заменить на текст, но мне пока как-то не хочется этим заниматься.

=== Общие объявления ===
[[Файл: Networks Link Layer Protocols Definitions.png]]

[[Файл: Networks 1.5 Definitions.png]]

=== Неограниченный симлексный протокол ===
Данные передаются в одном направлении. Время обработки равно нулю, буфер бесконечен, канал идеальный. Отправитель просто постоянно шлёт данные, получатель постоянно читает.

[[Файл: Networks 1.5 Protocol1.png]]

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

[[Файл: Networks 1.5 Protocol2.png]]

=== Симплексный протокол для замушлённых каналов ===
Теперь перестаём верить в идеальный канал, кадры могут теряться и искажаться (в том числе служебные). Проверку искажения кадра будем проводить уровнем ниже (сверять checksum). Чтобы обнаружить потерю кадра, запустим таймер и будем ждать подтверждение. Если подтверждения нет, а наступил таймаут, то кадр считаем потраченным и посылаем заново. Есть проблема: может потеряться подтверждение, в таком случае произойдёт дублирование кадра. Для этого добавим порядковый номер кадра и подтверждения. В этом случае принимающий будет знать, какой порядковый номер он ждёт, и игнорировать кадры с неправильным номером. Нетрудно понять, что для порядкового номера хватит одного бита.

[[Файл: Networks 1.5 Protocol3.1.png]]

[[Файл: Networks 1.5 Protocol3.2.png]]

=== Протоколы скользящего окна ===
Симплексные протоколы — это плохо, потому что данные хотим посылать в обе стороны, а если сделать два отдельных канала, то получится дороже. В случае с дуплексными протоколами в обе стороны могут ходить и обычные кадры, и служебные (ACK). В заголовке кадра будем хранить kind, чтобы различать типы кадров. Есть техника piggybacking: если мы хотим послать подтверждение и обычный кадр, то пошлём их вместе (подтверждение положим в поле ACK в заголовке кадра). В таком варианте нужно заводить отдельный таймер на тот случай, когда от нас ждут подтверждение, а мы не хотим посылать обычный кадр (в этом случае мы просто пошлём кадр с подтверждением). То есть, если нам пришло сообщение, то мы либо довольно скоро захотим сами что-то послать и приложим подтверждение, либо просто пошлём подтверждение по тику таймера.

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

Это всё общая идея, перейдём к конкретным реализациям.

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

[[Файл: Networks 1.5 Protocol4.1.png]]

[[Файл: Networks 1.5 Protocol4.2.png]]

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

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

В реализации есть ещё одно нововведение: у сетевого уровня не всегда есть данные для передачи, поэтому он будет генерить событие, когда хочет что-то передавать. Также его можно выключить, чтобы он ничего не генерил, если у нас заполнено всё окно.
[[Файл: Networks 1.5 Protocol5.1.png]]

[[Файл: 2015-04-02-14-00-07_selection.png]]

[[Файл: Networks 1.5 Protocol5.3.png]]

[[Файл: Networks 1.5 Protocol5.4.png]]

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

Также можно посылать отрицательное подтверждение (NAK), в этом случае отправитель перепошлёт потерянный кадр до истечения таймаута.

[[Файл: Networks 1.5 Protocol6.1.png]]

[[Файл: Networks 1.5 Protocol6.2.png]]

[[Файл: Networks 1.5 Protocol6.3.png]]

[[Файл: Networks 1.5 Protocol6.4.png]]

=== Верификация протоколов ===
Нам про это очень мало рассказывали.

==== Конечные автоматы ====
Состояние процесса будет хранить в себе значения всех переменных в программе. Также будет состояние канала (какой кадр передаётся и передаётся ли). Множество переходов — все возможные переходы между состояниями вследствие каких-либо событий. Также пометим начальные состояния. Получим автомат, в котором можно анализировать достижимость различных состояний. Возможны следующие ошибки:
* состояние, в котором нельзя определить, куда переходить (неполнота протокола)
* состояние, из которого нет выхода (тупик)
* состояние с переходом по событию, которое никогда не может произойти (лишний переход).

Анализ достижимости позволяет обнаружить такие проблемы.

==== Сети Петри ====
Нам про это два слова сказали, так что вряд ли понадобится. Есть в Таненбауме, если очень нужно.

== Контроль и исправление ошибок ==

== Мосты ==

← Предыдущая		Версия 16:26, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Сервисы, подуровни ==		== Сервисы, подуровни ==
	TODO		TODO

← Предыдущая		Версия 05:04, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Сервисы, подуровни ==		== Сервисы, подуровни ==
	TODO		TODO

@@ Строка 4: / Строка 4: @@
 == Протоколы ==
 На канальном уровне нужно передавать данные с сетевого уровня. При этом требуется, чтобы кадры не дублировались, и сохранялся порядок. Ниже представлены протоколы с различными допущениями о канале от самого простого случая (с идеальным каналом) к более сложным. Сначала даётся краткое словесное описание, затем сишный псевдокод, из которого всё понятно.
 === Общие объявления ===

@@ Строка 369: / Строка 369: @@
 Также можно посылать отрицательное подтверждение (NAK), в этом случае отправитель перепошлёт потерянный кадр до истечения таймаута.
-[[Файл: Networks 1.5 Protocol6.1.png]]
+<code>
-[[Файл: Networks 1.5 Protocol6.2.png]]
+         case frame_arrival:	/* a data or control frame has arrived */
+                 from_physical_layer(&r);	/* fetch incoming frame from physical layer */
-[[Файл: Networks 1.5 Protocol6.3.png]]
+                 if (r.kind == data) {
+                         /* An undamaged frame has arrived. */
-[[Файл: Networks 1.5 Protocol6.4.png]]
+                         if ((r.seq != frame_expected) && no_nak)
 === Верификация протоколов ===

@@ Строка 266: / Строка 266: @@
 В реализации есть ещё одно нововведение: у сетевого уровня не всегда есть данные для передачи, поэтому он будет генерить событие, когда хочет что-то передавать. Также его можно выключить, чтобы он ничего не генерил, если у нас заполнено всё окно.
-[[Файл: 2015-04-02-14-00-07_selection.png]]
+<code>
-[[Файл: Networks 1.5 Protocol5.3.png]]
+ #define MAX_SEQ 7	/* should be 2^n - 1 */
-[[Файл: Networks 1.5 Protocol5.4.png]]
+   while (true) {
 ==== Протоколы с выборочным повтором ====

@@ Строка 8: / Строка 8: @@
 === Общие объявления ===
-[[Файл: Networks Link Layer Protocols Definitions.png]]
+<code>
-[[Файл: Networks 1.5 Definitions.png]]
+ typedef enum {false, true} boolean;	/* boolean type */
 === Неограниченный симлексный протокол ===