Повторна передача і ковзне вікно - студопедія
У тих випадках, коли інші методи забезпечення надійності не спрацьовують і пакети губляться, застосовують методи повторної передачі пакетів. Ці мето-ди вимагають використання протоколів, орієнтованих на з'єднання.
Щоб переконатися в необхідності повторної передачі даних, відправник ну-мерует відправляються кадри і для кожного кадру очікує від приймача так на-зване позитивної квитанції (Positive Acknowledgment, АСК) - слу-жебного кадру, який подаватиметься про те, що вихідний кадр отриманий і дані в ньому коректні. Для того щоб організувати таку нумерацію, і потрібна процедура логічного з'єднання - вона дає точку відліку, з якої починається нумера-ція. Час очікування квитанції обмежена - при відправці кожного кадру пе-редатчік запускає таймер, і, якщо після закінчення заданого часу поклади-кові квитанція на отримана, кадр вважається загубленим. Приймач у разі отримання кадру з перекрученими даними може відправити негативну квитанцію (Negative Acknowledgment, NACK) - явне вказівку на те, що дано-ний кадр потрібно передати повторно.
Існує два методи організації процесу обміну квитанціями: метод про- стоячи джерела і метод ковзного вікна.
Метод простою джерела вимагає, щоб джерело, що послав кадр, очікував по-лучения квитанції (позитивної або негативної) від приймача і тільки після цього посилав наступний кадр (або повторював спотворений). Якщо ж квитанція не спадає протягом тайм-ауту, то кадр (або квитанція) вважається загубленим і його передача повторюється. На рис. 6.6, а видно, що в цьому випадку продуктивність обміну даними нижче потенційно можливої, - хоча пе-редатчік і міг би послати наступний кадр відразу ж після відправки попе-
ного, він зобов'язаний чекати приходу позитивної квитанції. (Далі, де це не спотворює істота розглянутого питання, позитивні квитанції для стислості будуть називатися просто «квитанціями».)
123 n + 1 ww + 1 w + n Номеракадров
Мал. 6.6. Методи відновлення спотворених і втрачених кадрів
Недоліки цього методу корекції особливо помітні на низькошвидкісних ка-налах зв'язку, тобто в територіальних мережах.
Другий метод називається методом ковзного вікна (sliding window). У цьому методі для підвищення швидкості передачі даних джерела дозволяється пере-дати кілька кадрів в безперервному режимі, тобто в максималь-но можливе для джерела темпі без отримання на ці пакети квитанцій. Ко-личество пакетів, які дозволяється передавати таким чином, називається розміром вікна. Малюнок 6.6, б ілюструє застосування даного методу для вікна розміром W пакетів.
У початковий момент, коли ще не послано жодного пакета, вікно визначає діапазон пакетів з номерами від 1 до W включно. Джерело починає пере-давати пакети і отримувати у відповідь квитанції. Для простоти припустимо, що квитанції надходять в тій же послідовності, що і пакети, яким вони
відповідають. У момент tt при отриманні першої квитанції До вікно зсувається на одну позицію, визначаючи новий діапазон від 2 до (W + 1).
Процеси відправки пакетів і отримання квитанцій йдуть досить неза-мо один від одного. Розглянемо довільний момент часу tn. коли джерело отримує квитанцію на пакет з номером п. Вікно зсувається вправо і визначає діапазон дозволених до передачі пакетів від (п + 1) до (W + п). Всі безліч пакетів, що виходять із джерела, можна розділити на перераховані нижче групи (див. Рис. 6.6, б).
# 9633; Пакети з номерами від 1 до п вже були відправлені і квитанції на них напів-чени, тобто вони знаходяться за межами вікна зліва.
# 9633; Пакети, починаючи з номера (п + 1) і закінчуючи номером (W + п), знаходяться в межах вікна і тому можуть бути відправлені, не чекаючи приходу ка-кой-яких квитанції. Цей діапазон може бути розділений ще на два піддамся-пазона:
Про пакети з номерами від (п + 1) до m вже відправлені, але квитанції на них ще не отримані;
Про пакети з номерами від m до (W + п) поки не відправлені, хоча заборони на це немає.
# 9633; Всі пакети з номерами, більшими або рівними (W + п + 1), знаходяться за межами вікна праворуч і тому поки не можуть бути відправлені.
Переміщення вікна уздовж послідовності номерів пакетів ілюструє рис. 6.6, в. Тут t0 - вихідний момент, tt і tn - моменти приходу квитанцій на перший і п-й пакет відповідно. Кожен раз, коли приходить квитанція, вікно зсувається вліво, але його розмір при цьому не змінюється і залишається рівним W.
При відправці пакета в джерелі встановлюється тайм-аут. Якщо за цей час квитанція на відправлений пакет не прийде, пакет (або квитанція на нього) вва-жається втраченим, і пакет передається знову.
Якщо ж потік квитанцій надходить регулярно в межах допуску в W пакетів, то швидкість обміну досягає максимально можливої величини для даного каналу і прийнятого протоколу.
У деяких реалізаціях ковзного вікна від приймача не потрібно поси-лать квитанції на кожен прийнятий коректний пакет. Якщо серед тих, хто прийшов пакетів немає «прогалин», то приймача достатньо надіслати квитанцію тільки на останній прийнятий пакет, і ця квитанція буде свідчити відправите-лю про те, що всі попередні пакети також дійшли благополучно.
В інших методах використовуються негативні квитанції. Негативні кві-танці бувають двох типів - групові та виборчі. Групова квитанція містить номер пакета, починаючи з якого потрібно повторити передачу всіх па-кетів, відправлених передавачем в мережу. Виборча негативна кві-танці вимагає повторної передачі тільки одного пакета.
Метод змінного вікна має два параметри, які можуть істотно впли-ять на ефективність передачі даних між передавачем і приймачем, - це розмір вікна і величина тайм-ауту очікування квитанції. Вибір тайм-ауту за-висить немає від надійності мережі, а від затримок передачі пакетів мережею.
В надійних мережах, в яких пакети спотворюються і губляться рідко, для вище-ня швидкості обміну даними розмір вікна потрібно збільшувати, так як при цьому передавач буде посилати пакети з меншими паузами. У ненадійних мережах розмір вікна слід зменшувати, так як при частих втратах й викривлення Пакегі тов різко зростає обсяг вдруге через мережу пакетів, а значить, пропускна здатність мережі багато в чому витрачається вхолосту, і корисна пропускна здатність мережі падає.
Розмір вікна може бути постійним параметром алгоритму ковзного вікна. У цьому випадку він вибирається при встановленні з'єднання і не змінюється в ті-чення сеансу. Існують також адаптивні версії алгоритму, коли розмір вікна змінюється протягом сеансу відповідно до поточним станом мережі і вузла призначення.
Надійність мережі в подібних алгоритмах визначається за такими ознаками як і втрат пакетів, як закінчення тайм-ауту для позитивної квитанції або при-хід дубліката квитанції на певний пакет. Дублікат говорить про те, що в вузлі призначення закінчився тайм-аут очікування чергового пакета, і вузол запраші-кість відправку цього пакета вдруге. При настанні таких подій вузол від-правитель зменшує розмір вікна, намагаючись знайти оптимальний режим передачі даних.
Розмір вікна може бути також змінено вузлом призначення. Причиною уменьше-ня розміру вікна є перевантаження вузла призначення, який не встигає об-працювати вступники пакети. Ми повернемося до цієї проблеми пізніше, в розділі «Зворотній зв'язок» глави 7, коли будемо вивчати методи боротьби з перевантаженнями.
Існують також реалізації методу ковзного вікна, в яких в якості розміру вікна використовується не кількість пакетів, а кількість байтів. Наибо-леї відомим прикладом такого підходу є протокол TCP.
У загальному випадку метод ковзного вікна складніший в реалізації, ніж метод простою джерела, так як передавач повинен зберігати в буфері все пакети, на які поки не отримані позитивні квитанції. Крім того, при викорис-танні даного методу потрібно відстежувати кілька параметрів алгоритми-ма: розмір вікна W, номер пакета, на який отримана квитанція, номер пакета, який ще можна передати до отримання нової квитанції.