L05-СетиТК(L2-аспекты)

Sliding Window Protocol –

перенос данных

•При использовании протокола скользящего окна в полнодуплексных соединениях :

Узел A поддерживает свое собственное окно передачи

Узел B поддерживает свое собственное окно приема

Кадр содержит поля: управление + данные + ACK

В поле управления содержится: порядковый номер передаваемого кадра (номер I-кадра), порядковый номер ожидаемого кадра (номер АСК)

11/18/2013

11

Sliding Window Protocol -

эффективность

 Обратитесь к приложению A

 Когда размер окна равен W (и безошибочная передача), использование линии связи, U, определяется как

	1 W (2a 1)
U	W		W (2a 1)	(1)
	2a 1

где a = Tprop/Tf или длина линии связи в битах

Sliding window protocol может достигнуть 100% -го использования если W >= (2a + 1)

11/18/2013

12

Обнаружение ошибок

1 2 3 4

…

… F-2 F-1 F

1 0 1 0 1 0 0 0 1 0 1 0 … 0 0 1

Prob [1st bit in error] = BER

Prob [1st bit correct] = 1-BER

Prob [2nd bit in error] = BER Prob [2nd bit correct] = 1-BER

Prob [Fth bit in error] = BER Prob [Fth bit correct] = 1-BER

Следовательно, для кадра из F бит,

Prob [кадр правильный] =

Prob [кадр ошибочный] =

(1-BER)F

1 - (1-BER)F

11/18/2013

13

Обнаружение ошибок (2)

E биты добавлены в конец к полю данных

Rx вычисляет его собственное E-поле для сравнения с полученным

11/18/2013

14

Контроль четности

Самая простая схема обнаружения ошибок

Добавление в конец дополнительного бита:

Проверка на четность: добавит в конец такой бит (0 или 1), чтобы общее количество 1’s было четным

Проверка на нечетность: добавит в конец такой бит (0 или 1), чтобы общее количество 1’s было нечетным

Если проверка на четность используется, Приемник проверит, является ли общее количество 1’s четным. Если это не так, значит ошибка (error)

11/18/2013

15

Cyclic Redundancy Check (CRC)

Циклический контроль избыточности

k-bit block of data (M(x))
		n-bit file check sequence (F(x))

Processing: compute FCS (for some GIVEN an n+1 bit polynomial P)

Обработка: вычислите FCS (для некоторых УЧИТЫВАЯ n+1 разрядный полиномиальный P)

k-bit block of data	N-bit file check sequence

k+n bit frame to be transmitted denoted by T

•Модуль 2 арифметики (подобно XOR) используется, чтобы генерировать FCS:

0 ± 0 = 0; 1 ± 0 = 1; 0 ± 1 = 1; 1 ± 1 = 0

1 X 0 = 0; 0 X 1 = 0; 1 X 1 = 1

11/18/2013

16

Исправление ошибок

•Типы ошибок:

	Потерянный кадр	(Lost frame)
	Поврежденный кадр	(Damaged frame)

• Техника исправления ошибок:

 Обнаружение ошибки (ранее рассматривали:)

	Контроль четности	(Parity Check)
	CRC	(Cyclic Redundancy Check)
 Положительное подтверждение		(Positive Acknowledgment )
 Повторная передача по таймауту		(Retransmission after timeout)

 Отрицательное подтверждение и повторная передача

(Negative Acknowledgment and retransmission)

Все эти механизмы известны как ARQ (Automatic Repeat Request,

Автоматический Повторный Запрос) процедуры: достигается эффект преобразования ненадежной связи в надежную

 Stop-and-wait	(остановка и ожидание)
 Go-back-N	(возврат на N)
 Selective-reject	(выборочный отказ)

11/18/2013

17

Исправление ошибки

1.Повторная передача

Протоколы управления потоком и ошибками

2.Прямое управление ошибками (Forward Error Correction (FEC)

require more redundancy bits

should locate the invalid bit or bits

n-bit code word contains m data bits + r redundancy bits

n=m+r

 m+r+1 bits discoverable by r bits

2r m r 1

Example:

 For m=5 data bits can r be 3?

11/18/2013

18

Коды Хэмминга

Например: 7-bit ASCII code + 4 bit redundancy

Each r bit is the parity bit for one combination of data bits:

r1: bits: 1, 3, 5, 7, 9, 11 r2: bits: 2, 3, 6, 7, 10, 11 r3: bits 4, 5, 6, 7

r4: bits 8, 9, 10, 11

11/18/2013

19

Коды Хэмминга(продолжение)

Example of redundancy bit calculation

11/18/2013

20