L05-СетиТК(L2-аспекты)
.pdfКанальный уровень
11/18/2013 |
1 |
Содержание
1. |
Управление потоком |
(Flow Control) |
|
|
a. |
Stop-and-Wait |
(остановка-и-ожидание) |
|
b. Sliding-Window |
(скользящее окно) |
|
2. |
Обнаружение ошибок |
(Error Detection) |
|
|
a. |
Parity Check |
(проверка четности) |
b.CRC
3.Исправление ошибок
a. Stop-and-Wait ARQ (остановка-и-ожидание ARQ)
b. |
Go-Back-N ARQ |
(возвращение на N) |
c. |
Selective-Reject ARQ |
(селективный отказ / |
|
|
выборочный неприем) |
4.High-Level Data Link (HDLC)
5.Другие Data Link Control Protocols
11/18/2013 |
2 |
Управление каналом передачи данных
Логика или процедуры, используемые для преобразования необработанного потока бит физического уровня в "надежное” соединение
Требования и Цели:
Кадровая синхронизация |
(Frame synchronization) |
Управление потоком данных |
(Flow control) |
Управление ошибками |
(Error control) |
Адресация |
(Addressing) |
Мультиплексирование данных и управления соединением
|
(Multiplexing data and control |
|
on connection) |
Управление линией |
(Link management) |
11/18/2013 |
3 |
Управление потоком (1)
•Схема должна гарантировать, что передатчик не перегружает получателя данными, избегать буферного переполнения
•Передача одного кадра
Tf |
- время передачи кадра источником |
Tprop - время распространения кадра
Tproc - время обработки кадра приемником, маленькая задержка (обычно игнорируемая, если не указанна)
Tproc может игнорироваться если не указан
11/18/2013
Source Destination
Tf
Tprop
Tproc
time
4
Управление потоком (2)
Source Destination
frame 1 |
|
frame 2 |
frame 1 |
|
|
frame 3 |
frame 2 |
|
|
frame 4 |
frame 3 |
|
|
|
frame 4 |
time |
|
Безошибочная передача
Модели передачи кадра
Source Destination
frame 1 |
|
|
frame 2 |
|
frame 1 |
|
|
|
frame 3 |
losses |
frame 2 |
|
||
frame 4 |
|
frame 3 |
|
|
|
|
error |
frame 4 |
time |
|
|
Передача с потерей (losses) (кадр 2) и ошибкой (кадр 4)
Адресат (Destination) имеет ограниченное буферное место. Как источник (Source) будет знать, что адресат готов получить следующий кадр?
В случае ошибок или потери кадра, источнику необходимо повторно передать кадр - то есть копии переданных кадров должны сохраняться. Как источник будет знать, когда отказаться от копий старых кадров?
И т.д.
11/18/2013 |
5 |
Протокол с остановкой и ожиданием «Stop-and-Wait»
•Протокол:
Источник передает кадр
Адресат получает кадр и посылает положительное подтверждение (квитанцию) ACK
Источник, после получения квитанции ACK, может послать следующий кадр
•Получатель может остановить Передатчик, отказывая в ACK
•Простой протокол
•ОБРАТИТЕ ВНИМАНИЕ: ТОЛЬКО один кадр может быть передан в любой данный момент времени
11/18/2013 |
6 |
Stop-and-Wait Protocol:
Эффективность (1)
•После каждого кадра, источник должен ждать положительное подтверждение Следовательно, время распространения по линии связи существенно.
•Полное время для одного кадра:
T_total = Tf + 2Tprop + Tproc + Tack
если игнорировать Tproc and Tack (обычно очень маленькие)
T_total = Tf + 2Tprop
• Использование линии связи, U равно:
U = Tf / (T_total), or
= 1 / (1+2 ( Tprop / Tf) ) = 1 / (1 + 2 a)
где a = Tprop/Tf = длина линии в битах
(вроде лучше сказать - в кадрах)
•If a < 1 (i.e. Tf > Tprop – when 1st transmitted bit reaches destination, source will still be transmitting U is close 100%
•If a > 1 (i.e. Tf < Tprop – frame transmission is completed before 1st bit reaches destination U is low
•Это показано на следующем слайде
11/18/2013
Source Destination
Tf
Tprop
Tproc
Tprop
Tack
time
7
Stop-and-Wait Protocol:
Эффективность (2)
•Вспомним: a = Tprop/Tf = длина линии в битах
Если a < 1 (т.е. Tf > Tprop)
– когда 1-й переданный бит достигает адресата, а источник будет все еще предавать U близко к
100%
Если a > 1 (т.е. Tf < Tprop –
передача кадра закончена прежде, чем 1-й бит достигает адресата U низок
Stop-and-Wait эффективен для связей, где a << 1 (длина кадра в сравнении с временем распространения)
11/18/2013 |
8 |
Протокол скользящего окна
(Sliding Window Protocol)
•Stop-and-Wait не эффективен при a > 1
•Поэтому используется Sliding Window Protocol (протокол скользящего окна):
предполагается полнодуплексная линия
Источник “А” и Адресат “Б” имеют буфера, каждый размером W кадров
В заголовке кадра “к” бит используется для последовательной нумерации кадров
Кадры нумеруются: 0, 1, 2, …, 2k-1, 0, 1, … (по модулю 2k)
ACKs (RRs) нумеруются: 0, 1, 2, …, 2k-1, 0, 1, … (по модулю 2k)
Источник “А” может передать до w кадров, не ожидая подтверждений АСК.
“B” может принять до W последовательных кадров
Посланный “B” ACK J (или RR J), где 0 <= J <= 2k-1,означает, что “B” принял кадры до
кадра J-1 и готов принять кадр J
“B” может также послать RNR J, что означает: “B” принял все кадры до J-1 и не готов получить больше
Размер окна W, может быть меньше или равняться 2k-1
11/18/2013 |
9 |
Протокол скользящего окна(2)
• Пример Sliding-Window-Protocol: k = 3 бита, W = 7
Observations:
“A” с Tx W = 7 передает кадры (F0, F1, …, F6)
После передачи F0, F1, и F2 окно сокращено (то есть не может передать кроме F3, F4, …, F6)
Когда “B” посылает RR3, “А” понимает, что “В” получил F0, F1 и F2 и готов принять
F3
и “А” продвигает окно к покрытию 7 кадров (начинающийся с F3 до F1)
и “A” посылает F3, F4, F5, & F6
“B” отвечает RR4, когда F3 получен – продвигает окно приема на одну позициею, чтобы включить F2
11/18/2013
W
W
W
W
W |
|
W = расстояние между первым неподтвержденным кадром и |
10 |
|
|||
|
|
||
|
|
и последним кадром, который можно послать не ожидая подтверждения |
|
|
|
|
|