Sliding window protocol

Лизгачкиот прозорец е составен од пакети засновани на протоколот за пренос на податоци. Лизгачкиот прозорец се користи таму каде што е баран доверлив пренос на пакет, како во податочно ниво (OSI моделот) и TCP. Во концепт, секој дел од преносот (пакетите во повеќето податочни нивоа, но бајти во TCP) е назначен како уникатен број од низа, и примачот користи броеви за да ги распредели пакетите на точните позиции, отфрлајќи дуплицирање на пакети и идентификување на изгубените. Проблемот е во тоа што нема ограничување на должината на низата од бројки кои се пребаруваат. Со поставување на лимит на бројот на пакетите коишто се испраќаат или примаат во било кое време, лизгачкиот прозорец дозволува неограничен број на пакети да бидат доставени, преку користење на фиксна низа на броеви. За најголемото можно производство, важно е дека испраќачот не е принуден да престане да испраќа од страна на лизгачкиот прозорец порано од RTT. Ограничувањето на количеството на податоци што може да се пратат пред прекинот, за да чекаат за потврда треба да биде поголемо од протокот на комуникациската врска. А ако не, протоколот ќе го ограничи делотворниот проток на врската.

Мотивација

Во секој комуникациски протокол заснован на автоматско повторување за пребарување за контрола на грешки, примачот мора да го потврди примањето на пакетите. Ако испраќачот не добие потврда во разумен временски рок, ги препраќа податоците. Испраќачот што не добива потврда не може да знае дали примачот го примил пакетот; може пакетот да е изгубен во преносот (или оштетен, ако контролата за грешки пронајде грешка, пакетот е игнориран), или може потврдата е пратена ама изгубена. Во последниот случај примачот мора да го признае препраќањето, инаку мора да го игнорира. Исто така, примачот вообичаено е неизвесен за тоа дали потврдата е добиена или не.

Протокол

Содржински модули број 4, со w_r=1. Првично, n_t=n_r=0

Испраќачот и примачот си имаат секој од нив реден број n и n t r, соодветно. Исто така, секој од нив има и големина на прозорец W t и W r . Големината на прозорците може да се разликува, но за поедноставни имплементации таа е фиксна. Големината на прозорецот мора да биде поголема од нула, за каков било напредок да се направи. Кај обично имлементирање, n t е следниот пакет што треба да се пренесува т.е. редниот број на пакет што сè уште не е пренесен. Исто така, n r е првиот пакет којшто сè уште не е примен. Двете бројки се монотоно растечки. Примачот исто така може да има од највисоката секвенца од бројот којшто сè уште не е примен, променливата n и е уште една од низата на највисоко примени редни броеви. За едноставните примачи коишто прифаќаат само пакети во редослед (W r = 1), ова е исто како и n r, но може да биде и поголем, ако W r> 1. Воочете ја разликата дека: сите пакети подолу од n r се примени, погоре од ns не, а помеѓу n r и н с некои од пакетите се примени, некои не. Кога примачот ќе прими пакет, ја ажурира променливата соодветно и испраќа потврда со новиот n r . Испраќачот чува траги од највисоката потврда што ја има добиено (na). Испраќачот знае дека сите пакети сè до n a , но ќе бидат вклучени сите но не вклучувајќи го него, и неизвесно е за пакетите помеѓу n а и нс, т.е. n а≤ n r ≤ n с. Низата броеви секогаш го почитуваат правилото n a ≤ n r ≤ n s ≤ n t ≤ n a + w t . Тоа е: n a ≤ n r : Највисокото признание што го добива испраќачот не може да биде поголемо од n r признанието од примачот. n r ≤ n s : Распонот на целосно примените пакети не може да се прошири надвор од делумично примените пакети n s ≤ n t : Најголемиот примен пакет не може да биде поголем од најголениот испратен пакет. n t ≤ n a + w t : Најголемиот испратен пакет е ограничен од најголемата потврда и од големината на прозорецот.

Задача на испраќачот

Секогаш кога испраќачот има податоци за праќање, тој може да пренесува до wt пакетот во пресред на последната потврда n a. Исто така тој може да пренесува пакети со број n t сè додека n t < n a + w t . Во отсуство на комуникациска грешка, испраќачот наскоро ќе добие потврда за сите пакети коишто ги испратил, оставајќи n a да биде еднаков на n t . Ако тоа не се случи по разумно задоцнување тогаш испраќачот мора да ги препрати пакетите помеѓу n a и n t.

Техники за дефинирање на разумно одложување може да биде исклучително сложено, но тие само влијаат на ефикасноста; основната сигурност на протокол лизгачки прозорец не зависи од деталите.

Задача на примачот

Секој пат кога еден нумериран пакет x е примен, примачот проверува дали ќе падне во добиениот прозорец, n r ≤ x < n s + w r. (Наједноставните примачи само треба да чуваат една вредност n r = n s.) Ако е во рамките на прозорецот, примачот ги прифаќа. Ако е нумериран на n r, тогаш добиениот број се зголемува за 1, можеби и повеќе ако следните последователни пакети биле претходно добиени и чувани. Ако x ˃ nr пакетот е зачуван сè додека претходните пакети да се сочуваат. Ако x ≥ n второспоменатиот е c=x+1 Ако бројот на пакетот не е во добиениот прозорецот, примачот го отфрла и не ги изменува nr ни ns. Без разлика дали пакетот е прифатен или не, примачот праќа потврда која го содржи тековното nr. (Потврдата исто може да содржи информации за дополнителни пакети коишто се примени помеѓу nr и ns, но тоа само ја зголемува ефикасноста) Но внимавајте, не постои точка каде „испраќачкиот прозорец“ wr е поголем „примачкиот прозорец“ wt, бидејќи нема потреба од загриженост за добивање на пакет којшто нема никогаш да биде пренесен; рангот е 1≤ wr ≤wt.

Ранг

Низата броеви е по модул 4, со wr=1. Прво, nt=nr=0. Засега, протоколот ќе биде опишан како низа од броеви кои се со неограничена големина, која постојано се зголемува. Сепак, наместо да се предава целосно редниот број x во пораки, можно е да се емитуваат само x mod N, за конелно N. На пример, испраќачот ќе прими потврда само во рангот од na до nt. Бидејќи тоа гарантира дека nt – na ≤ wt, постојат wt+1 можни низа од броеви кои би можеле да пристигнат во било кое време. Така, испраќачот недвосмислено ја дешифрира низата на броеви сè додека N > wt. Ограничувањето е засилено од страна на примачот. Работењето на протоколот зависи од примачот кој треба да биде во состојба да направи доверлива разлика меѓу преносот на нови пакети (кои треба да бидат прифатени и преработени) и стари пакети (кои треба да бидат отфрлени, а последната потврда да се препрати.) Ова може да се направи со давање на знаење за големината на прозорецот. По добивањето на пакетот нумериран како x, примачот знае дека x <na+wt, па na> x – wt. Така, пакетите нумерирани како x-wt никогаш повеќе нема да бидат препраќани. Најнискиот реден број што некогаш ќе го добијат во иднина е ns – wt. А највисокиот реден број што може да се добие е nr+wt≤ns+wt Значи, има два различни распореди на броевите коишто се примени во било кое време. Според тоа, мора N≥2wt. Сепак, вистинската граница е пониска.

На дополнителен увид е тоа што примачот не мора да прави разлика меѓу низата броеви кои се премали или преголеми. Во секој случај, примачот ги игнорира пакетите освен оние кои се за препраќање за потврда. Така, потребно е само N≥wt+wr. Така, вообичаено е да се има wr< wt (пример види Go Back N), кое дозволува поголемо wt ограничено со фиксно N.

ПРИМЕРИ

Наједноставниот пример: Иако најчесто се разликува од протоколот лизгање на прозорец, стоп и чекај протоколот е всушност наједноставната негова имплементација. Испраќачкиот прозорец е 1 пакет, и примачкиот прозорец е 1 пакет. Така, n=1+1=2 се можни низи на броеви кои се задолжителни. Двосмислен пример

Испраќачот наизменично праќа пакет означени како „непарен“ и „парен“. Потврдите се исто така означени како „непарен“ и „парен“. Да претпоставиме дека испраќачот, има испратено непарен број на пакети, не чека потврда со непарен број, и веднаш испраќа парен број на пакет. Тогаш може да добиеме порака која гласи „очекувавме непарен пакет “. Ова ќе направи недоумица за испраќачот: дали примачот го примил пакетот или не?

Go-Back-N

Ова е протокол на лизгачки прозорец со wt>1, но фиксно wr=1. Примачот одбива да го прими било кој следен пакет од низата. Ако еден пакет е изгубен во испраќањето, следните пакети се игнорирани сè додека изгубениот пакет не биде препратен, со минимално губење од еден кружен пат. Заради оваа причина, не е делотворен, бидејќи другите пакети страдаат заради честа загуба.

Двосмислен пример

Да претпоставиме дека користиме 3-битна низа, типична за HDLC. Така n=2*2*2=8. Како што wr=1, лимитот е wt≤7. Ова е затоа што, по испраќењето на 7 пакети, постојат 8 можни резултати: било кои од 0 до 7 пакети ќе бидат примени успешно. Има 8 можности, и на испраќачот му се потребни информации во потврдата за да ги разликува. Ако испраќачот испрати 8 пакет без да чека потврда за нив, може да се најде во недоумица слична на стоп и чекај протоколот: дали потврдата значи дека сите пакети се примени или ниеден од нив.

Селективно повторување

Ова е најопшт случај на лизгачкиот прозорец. Бара многу повеќе способни примачи, кои ќе ги примат пакетите со низа поголема од сегашната nr и да ги чува сè додека јазолот се пополнува. Предност, сепак е дека не е потребно да ги отфрли сите точни податоци пред испраќачот да биде информиран дека препраќањето е потребно. Ова се претпочита за врските со ниска сигурност и/или голем опсег на задоцнување на производот.

Големинта на прозорецот wr треба да биде поголема од бројот на последователни загуби кои можат да бидат толерирани. Така, малите вреднoсти се популарни; wr=2 е честа појава.

Двосмислен пример

Екстремно популарниот HDLC протокол користи 3-битни низи од броеви, и има опција за селективно повторување. Сепак, ако селективното повторување се користи, условот nt + nr ≤ 8 мора да се исполни; ако wr се зголеми за 2, wt мора да се намали за 6. Да претпоставиме дека wr=2, но немодифицираниот испраќач користи wr=7, како што обично се користи со Go back N варијанта на HDLC. Понатаму претпоставуваме дека примачот започнува со nr = ns =0. Претпоставуваме дека примачот ги гледа следните серии пакети: 0 1 2 3 4 5 6 (пауза) Бидејќи wr=2, примачот ќе го прифати и чува финалниот пакет 0 (мислејќи дека тоа е пакетот 8 во серијата), сè додека е барањето за препраќањето за пакетот 7. Како и да е, можно е испраќачот да не успее да добие никаква потврда и да мора да го препрати пакетот 0. Во вториот случај, примачот ќе прими погрешен пакет како пакет 8. Решението за испраќачот е да се ограничи wt≤6. Со ова ограничување, примачот знае дека после примањето на пакетот 6, што на испраќачот му е а ≥ 1, на тој начин следниот пакет нумериран како 0 мора да е пакетот 8. Ако сите потврди се загубени, тогаш испраќачот ќе мора после 5 пакет да престане со испраќање.

Проширување

Постојат многу начини на кои протоколот може да биде проширен: За горенаведените примери претпоставуваме дека пакетите никогаш не се прераспоредени во преносот; тие може да се изгубат во испраќањето, (откривањето на грешката прави корупција еквивалентна на загуба), но никогаш нема да се појават надвор од редот. Протоколот може да биде продолжен за да поддржи реорганизација на пакетите, доколку растојанието може да се надмине; а редниот број N мора да се зголеми.

Можно е да не се потвдрди секој пакет, доколку потврдата е пратена а не се добиваат никакви пакети за некое време. На пример, TCP нормално, признава секој втор пакет.

Вообичаено е да се информира испраќачот ако е откриена празнина во низата. HDLC има посебен REJ(отфрлувачки) пакет за ова. Големината на испраќачкиот и примачкиот прозорец може да се менува за време на комуникацијата, сè додека сумата останува во границите на N. За да ја намали големината на прозорецот треба да го успори преносот на натпреварот за брзина на врските избегнувајќи пренатрупување или метеж.

Една од начестите поедноставувања на протоколот селектирај-повтори е т.н SREJ-REJ ARQ. Овој протокол работи со wr=2 и ги прифаќа следните пакети, но овозможува само еден изгубен пакет; ако вториот пакет е изгубен , нема повеќе баферирани пакети. (т.е. wr=1 ) Ова му дава најголем дел од придобивките за ефикасноста на селектирај-повтори протоколот, со едноставна примена.