Методи відновлення спотворених і загублених кадрів

Методи корекції помилок в КМ засновані на повторній передачі кадру даних, якщо кадр не доходить до адресата або приймач знайшов в ньому спотворення інформації. Для того, щоб переконатись у необхідності ретрансляції даних, відправник нумерує кадри, які надсилає і для кожного кадру очікує від приймачапозитивної квитанції - службового кадру, що сповіщає про те, що вихідний кадр був отриманий і дані в ньому коректні. Час такого чекання обмежений - при відправленні кожного кадру передавач запускає таймер, і, якщо його час сплинув і позитивна квитанція на отримана - кадр вважається загубленим. Приймач у випадку одержання кадру зі спотвореними даними може відправити негативну квитанцію - вказуючи, що даний кадр потрібно ретранслювати.

Є два підходи до організації процесу обміну квитанціями: із простоями і з організацією „вікна”.

Метод з простоями (Idle Source) потребує, щоб передавач, який надіслав кадр, чекав одержання квитанції (позитивної чи негативної) від приймача і лише після цього надсилав наступний кадр (або раетранслював спотворений). Якщо ж квитанція не приходить протягом тайм-ауту, то кадр (або квитанція) вважається загубленим і його передача повторюється. На рис. 4.10, а видно, що в цьому випадку продуктивність обміну даними істотно знижується, хоча передавач міг би надіслати наступний кадр відразу ж після відправлення попереднього, він зобов’язаний чекати приходу квитанції. Зниження продуктивності цього методу корекції особливо помітно на низькошвідкісних ЛЗ.

Другий метод називається методом „ковзного вікна” (sliding window). В цьому методі для підвищення коефіцієнта використання лінії джерелу дозволяється безперервно надсилати деяку кількість кадрів в максимально можливому для джерела темпі, без одержання позитивних відповідних квитанцій на ці кадри. Кількість кадрів, що дозволяється передавати таким чином, називається розміром вікна. Рис. 4.10, б ілюструє даний метод для вікна розміром у W кадрів.

У початковий момент, коли ще не надіслано жодного кадру, вікно визначає діапазон кадрів з номерами від 1 до W включно. Джерело починає передавати кадри та одержувати у відповідь квитанції. Для простоти припустимо, що квитанції надходять у тій же послідовності, що і кадри, яким вони відповідають. У момент t₁ при одержанні першої квитанції К1 вікно зрушується на одну позицію, визначаючи новий діапазон від 2 до (W+1). Процеси відправлення кадрів і одержання квитанцій відбуваються незалежно один від одного. Розглянемо довільний момент часу t_n, коли передавач отримав квитанцію на кадр з номером n. Вікно зрушиться вправо і визначить діапазон дозволених до передачі кадрів від (n+1) до (W+n).

Всю множину кадрів, що виходять із джерела, можна розділити на перераховані таки три групи (рис. 4.10, б) [1]:

- Кадри з номерами від 1 до n вже були надіслані і квитанції на них отримані, тобто вони перебувають ліворуч за межами вікна.

- Кадри, починаючи з номера (n+1) і закінчуючи номером (W+n), знаходяться у межах вікна і тому можуть бути надіслані не чекаючи приходу будь-якої квитанції. Цей діапазон може бути розділений ще на два піддіапазона:

- кадри з номерами від (n+1) до m, які вже відправлені, але квитанції на них ще не отримані;

- кадри з номерами від m до (W+n), які поки ще не відправлені, хоча заборони на це немає.

- Усі кадри з номерами, більшими за (W+ n), перебувають за межами вікна праворуч і тому поки ще не можуть бути відправлені.

Переміщення вікна уздовж послідовності номерів кадрів показане на рис. 4.10, в. Тут t₀ - вихідний момент, t₁ і t_n - моменти приходу квитанцій на перший і n-й кадр відповідно. Щоразу, коли приходить квитанція, вікно зрушується вліво, але його розмір не змінюється і дорівнює W. Зауважимо, що хоча в даному прикладі розмір вікна в процесі передачі залишається постійним, у реальних протоколах (наприклад, TCP) можна зустріти варіанти даного алгоритму з розміром вікна, що змінюється.

Отже, при відправленні кадру з номером n джерелу дозволяється передати ще W-1 кадрів до отримання квитанції на кадр n, так що у мережу останнім надійде кадр з номером (W+n-1). Якщо ж за цей час квитанція на кадр n так і не надійшла - процес передачі припиняється, і після закінчення деякого тайм-ауту кадр n (або квитанція на нього) вважається загубленим і він надсилається знову.

Якщо ж потік квитанцій надходить більш-менш регулярно, в межах допуску у W кадрів, то швидкість обміну досягає максимально можливої величини для даного каналу і прийнятого протоколу. Метод ковзного вікна складніший у реалізації, ніж метод із простоями, оскільки передавач повинен зберігати в буфері усі кадри, на які поки не отримав позитивні квитанції. Крім того, потрібно відслідковувати кілька параметрів алгоритму [1, 4]:

- розмір вікна W;

- номер кадру, на який отримана квитанція;

- номер кадру, який ще можна передати до одержання нової квитанції.

Приймач може не надсилати квитанції на кожен прийнятий коректний кадр. Якщо кілька кадрів прийшли майже одночасно, то приймач може надіслати квитанцію тільки на останній кадр. При цьому вважається, що усі попередні кадри також дійшли благополучно.

Деякі методи використовують негативні квитанції. Негативні квитанції бувають двох типів - групові і виборчі. Групова квитанція містить номер кадру, починаючи з якого потрібно повторити передачу усіх кадрів, відправлених передавачем у мережу. Виборча негативна квитанція потребує повторної передачі тільки одного кадру.

Метод ковзного вікна реалізований у багатьох протоколах: LLC2, LAP-B, X.25, TCP, Novell NCP Burst Mode.

Метод із простоями є окремим випадком методу ковзного вікна, коли розмір вікна дорівнює одиниці.

Метод ковзного вікна має два параметри, що можуть помітно впливати на ефективність передачі даних між передавачем і приймачем - розмір вікна і величина тайм-ауту очікування квитанції. У надійних мережах, коли кадри спотворюються і губляться рідко, для підвищення швидкості обміну даними розмір вікна потрібно збільшувати, оскільки при цьому передавач буде надсилати кадри з меншими паузами. У ненадійних мережах розмір вікна варто зменшувати, оскільки при частих втратах і спотвореннях кадрів значно зростає обсяг ретрансльованих мережею кадрів, а значить корисна пропускна спроможність мережі буде падати.

Вибір тайм-ауту залежить не від надійності мережі, а від затримок передачі кадрів мережею.

У багатьох реалізаціях методу ковзного вікна величина вікна і тайм-аут вибираються адаптивно, в залежності від поточного стану мережі.