Data link layer - Flow control — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Протокол скользящего окна.)
 
(не показано 9 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
Для надежной передачи данных на канальном уровне необходимо решить следующую проблему:
 +
 +
Если мы попробуем передавать данные сразу как только они у нас появляются, то
 +
в случае когда отправитель работает быстрее, чем получатель может обрабатывать поступающую информацию, произойдет переполнение буфера и мы начнем терять данные.
 +
 +
Чтобы это предотвратить, нам необходимо осуществлять управление потоком.
 +
Управление потоком позволяет получателю контролировать скорость передачи данных, чтобы предотвратить чрезмерную загрузку в случае более быстрого отправителя.
 +
 +
Канальный уровень не отвечает за само [https://en.wikipedia.org/wiki/Network_congestion#Congestion_control переполнение] (что делать, когда буфер переполнился), эта проблема решается на более высоких уровнях.
 
Управление потоком передачи даных выполняется  [[Data link layer - LLC | LLC]] подуровнем.  
 
Управление потоком передачи даных выполняется  [[Data link layer - LLC | LLC]] подуровнем.  
  
Управление потоком позволяет получателю контролировать скорость передачи данных, чтобы предотвратить чрезмерную загрузку в случае более быстрого отправителя. Канальный уровень не отвечает за само переполнение, эта проблема решается на более высоких уровнях.
 
  
 
Управление потоком можно выполнить двумя способами:  
 
Управление потоком можно выполнить двумя способами:  
 
* Получать обратную связь от приемника.  
 
* Получать обратную связь от приемника.  
 
* Статически ограничить скорость передачи.  
 
* Статически ограничить скорость передачи.  
Второй способ реализуют вышележащими уровнями, поэтому здесь будем рассматривать протоколы использующие обратную связь.  
+
Второй способ реализуют вышележащими уровнями, поэтому рассмотрим протоколы передачи данных, в которых используется обратная связь для информирования отправителя о состоянии дел у получателя.  
  
 
==Stop-and-wait==
 
==Stop-and-wait==
Строка 12: Строка 20:
 
Отправитель шлет следующий кадр только после получения подтверждения.  
 
Отправитель шлет следующий кадр только после получения подтверждения.  
 
Если не получаем ACK по тайм-ауту, автоматически отправляем кадр повторно.
 
Если не получаем ACK по тайм-ауту, автоматически отправляем кадр повторно.
При повторных отправках кадра возникает проблема с возможными дубликатами: если был потерян ACK, то получателю кадр придет дважды. Поэтому нам нужно добавить информацию, чтобы различать кадры. Т.к. мы не начинаем отправку следующего кадра, пока не будет получен ACK по предыдущему, нам достаточно чтобы 2 последовательных кадра имели разный номер. Для этого нужен всего один бит. Номера нужно добавить и в кадры с данными, и в кадры с подтверждениями.  
+
При повторных отправках кадра возникает проблема с возможными дубликатами: если был потерян ACK, то получателю кадр придет дважды. Поэтому нам нужно добавить информацию, чтобы различать кадры. Так как мы не начинаем отправку следующего кадра, пока не будет получен ACK по предыдущему, нам достаточно, чтобы 2 последовательных кадра имели разный номер. Для этого нужен всего один бит. Номера нужно добавить и в кадры с данными, и в кадры с подтверждениями.  
На полученный дубликат нужно тоже выслать подтверждение (чтобы не было бесконечной переотправки) и проигнорировать сам дубликат.  
+
На полученный дубликат нужно тоже выслать подтверждение (чтобы не было бесконечной переотправки), но проигнорировать сам дубликат.  
+
 
 +
[[Файл:Stop-wait-sender.jpeg]] [[Файл:Stop-wait-receiver.jpeg]]
 +
 
 
Проблема этого протокола в том, что мы неэффективно используем канал. Всегда занимаемся передачей только одного кадра, во время ожидания ACK ничего не делаем.
 
Проблема этого протокола в том, что мы неэффективно используем канал. Всегда занимаемся передачей только одного кадра, во время ожидания ACK ничего не делаем.
  
==Протокол скользящего окна. ==
+
==Протокол скользящего окна==
 
Каждый исходящий кадр содержит свой порядковый номер.  
 
Каждый исходящий кадр содержит свой порядковый номер.  
 
На этот номер отводится поле размером ''n'' бит.  
 
На этот номер отводится поле размером ''n'' бит.  
 
Соответственно количество различных номеров ''N'' = <math>2^n</math>
 
Соответственно количество различных номеров ''N'' = <math>2^n</math>
  
В каждый момент времени отправитель и получатель работают с кадрами, которые попадают в их  окно (посылающее и принимающее). Окна у отправителя и получателя могут быть разных размеров. [[Файл:Sliding-window-1.jpg|right|thumb]]
+
В каждый момент времени отправитель и получатель работают с кадрами, которые попадают в их  окно (посылающее и принимающее). Окна у отправителя и получателя могут быть разных размеров.  
  
  
Строка 29: Строка 39:
 
Если не получаем ACK по таймеру, высылаем заново кадры в окне.  
 
Если не получаем ACK по таймеру, высылаем заново кадры в окне.  
 
Поэтому все кадры попадающие в окно, должны оставаться в буфере у отправителя.  
 
Поэтому все кадры попадающие в окно, должны оставаться в буфере у отправителя.  
 +
[[Файл:Sliding-send.jpg|center]]
  
 
Получатель также работает с принимающим окном, которое указывает, какие кадры в данный момент может принять получатель. Когда приходит кадр с номером соответствующим нижней границе окна - она сдвигается, высылается ACK в котором указывается новая нижняя граница принимающего окна, кадр выдается сетевому уровню.  
 
Получатель также работает с принимающим окном, которое указывает, какие кадры в данный момент может принять получатель. Когда приходит кадр с номером соответствующим нижней границе окна - она сдвигается, высылается ACK в котором указывается новая нижняя граница принимающего окна, кадр выдается сетевому уровню.  
Кадры не попадающие в окно - удаляются. Но при этом мы все равно отправляем ACK с текущей нижней границей.  
+
Кадры, не попадающие в окно, - удаляются. Но при этом мы все равно отправляем ACK с текущей нижней границей.  
 +
[[Файл:Window-receive.jpg|center]]
 +
 
 +
Номера кадров ''x'' берутся по модулю ''N''.
 +
Ширина окна может варьироваться. Не трудно заметить, что нет смысла делать принимающее окно размера большего чем посылающее окно.
 +
При этом размер посылающего окна ''w'' должен быть ограничен и удовлетворять неравенству ''N >= 2w''. Ограничение возникает из-за того, что получателю нужно различать новые кадры, и кадры повторно отправленные.
 +
 
  
 
====Протокол однобитового окна====  
 
====Протокол однобитового окна====  
Строка 43: Строка 60:
 
* Возврат на n - игнорируем все кадры с номером выше поврежденного
 
* Возврат на n - игнорируем все кадры с номером выше поврежденного
 
* Выборочный повтор - буферизуем нормальные кадры.  
 
* Выборочный повтор - буферизуем нормальные кадры.  
** (a) Высылаем максимальный ACK (номер новой нижней границы), ждем что по истечении таймера отправитель не получив ACK вышлет потерянный пакет заново.  
+
** (a) Высылаем максимальный ACK (номер новой нижней границы), ждем, что по истечении таймера отправитель, не получив ACK, вышлет потерянный пакет заново.  
 
** (b) Высылаем NAK - запрос на повторную отправку конкретного пакета
 
** (b) Высылаем NAK - запрос на повторную отправку конкретного пакета
[[Файл:Sliding-window-2.jpg]]
+
[[Файл:Sliding-window-2.jpg|center]]
 
 
Номера кадров ''x'' берутся по модулю ''N''.
 
Ширина окна может варьироваться. Не трудно заметить, что нет смысла делать принимающее окно размера большего чем посылающее окно.
 
При этом размер посылающего окна ''w'' должен быть ограничен и удовлетворять неравенству ''N >= 2w''. Ограничение возникает из-за того, что получателю нужно различать новые кадры, и кадры повторно отправленные.
 
  
 
==Ссылки==
 
==Ссылки==

Текущая версия на 16:59, 12 декабря 2016

Для надежной передачи данных на канальном уровне необходимо решить следующую проблему:

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

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

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


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

  • Получать обратную связь от приемника.
  • Статически ограничить скорость передачи.

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

Stop-and-wait[править]

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

Stop-wait-sender.jpeg Stop-wait-receiver.jpeg

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

Протокол скользящего окна[править]

Каждый исходящий кадр содержит свой порядковый номер. На этот номер отводится поле размером n бит. Соответственно количество различных номеров N = [math]2^n[/math]

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


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

Sliding-send.jpg

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

Window-receive.jpg

Номера кадров x берутся по модулю N. Ширина окна может варьироваться. Не трудно заметить, что нет смысла делать принимающее окно размера большего чем посылающее окно. При этом размер посылающего окна w должен быть ограничен и удовлетворять неравенству N >= 2w. Ограничение возникает из-за того, что получателю нужно различать новые кадры, и кадры повторно отправленные.


Протокол однобитового окна[править]

В случае если на номер отводится 1 бит, и ширина окна w = 1, протокол скользящего окна соответствует протоколу Stop And Wait.


Протокол с возвратом на n[править]

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

  • Возврат на n - игнорируем все кадры с номером выше поврежденного
  • Выборочный повтор - буферизуем нормальные кадры.
    • (a) Высылаем максимальный ACK (номер новой нижней границы), ждем, что по истечении таймера отправитель, не получив ACK, вышлет потерянный пакет заново.
    • (b) Высылаем NAK - запрос на повторную отправку конкретного пакета
Sliding-window-2.jpg

Ссылки[править]

flash демо - наглядный эмулятор sliding window.

Sliding Window Protocol