Лекция 3. Коммуник. протоколы. Протокол раздвижного окна. Принципы обоснования корректности

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 3.Êîììóíèêàöèîííûå ïðîòîêîëû.Îøèáêè, âîçíèêàþùèå ïðè ïåðåäà÷å ñîîáùåíèé.Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà.Óñòðîéñòâî ïðîòîêîëà ðàçäâèæíîãî îêíà.Ïðèíöèïû îáîñíîâàíèÿ êîððåêòíîñòè ïðîòîêîëîâÎáîñíîâàíèå êîððåêòíîñòè ïðîòîêîëà ðàçäâèæíîãî îêíà.Ìîäèôèêàöèè ïðîòîêîëà.Êîììóíèêàöèîííûå ïðîòîêîëûÎñíîâíîå íàçíà÷åíèå êîììóíèêàöèîííîãî ïðîòîêîëà ïåðåäà÷à äàííûõ , ò.å. ïîëó÷åíèå èíôîðìàöèè îò îäíîãî óçëàñåòè è äîñòàâêà åå ïî íàçíà÷åíèþ äðóãîìó óçëó ñåòè.Ïðè ïåðåäà÷å äàííûõ âîçìîæíû îøèáêè (ïîòåðÿ,äóáëèðîâàíèå, èñêàæåíèå).Ýòè îøèáêè íóæíî îáíàðóæèâàòü è èñïðàâëÿòü.Äëÿ ýòîãî â ïðîòîêîëå âåäåòñÿ ó÷åò ñîñòîÿíèÿ èíôîðìàöèè.Äëÿ èñïîëüçîâàíèÿ ñîñòîÿíèÿ èíôîðìàöèè ïðèìåíÿåòñÿóïðàâëåíèå ñîåäèíåíèåì èíèöèàëèçàöèÿ è àííóëèðîâàíèåñîñòîÿíèÿ èíôîðìàöèè.Èíèöèàëèçàöèÿ íàçûâàåòñÿ óñòàíîâëåíèåì ñîåäèíåíèÿ, ààííóëèðîâàíèå çàâåðøåíèåì ñîåäèíåíèÿ.Êîììóíèêàöèîííûå ïðîòîêîëûÌû ðàññìîòðèì îäèí èç òàêèõ ïðîòîêîëîâ (Balanced Sliding WindowProtocol).Îí ïðåäíàçíà÷åí äëÿ îáìåíà äàííûìè ìåæäó äâóìÿ óçëàìèñåòè, êîòîðûå èìåþò ïðÿìîå ôèçè÷åñêîå ñîåäèíåíèå(íàïðèìåð, ïî îïòîâîëîêîííîìó êàáåëþ).Ýòî âïîëíå àñèíõðîííûé ïðîòîêîë, îòíîñÿùèéñÿ ê óðîâíþóïðàâëåíèÿ ïåðåäà÷åé äàííûõ âòîðîìó óðîâíþ ýòàëîííîéìîäåëè OSI.Ìû íå áóäåì ðàññìàòðèâàòü óïðàâëåíèå ñîåäèíåíèåì äëÿ ýòîãîïðîòîêîëà.

Ïðåäïîëàãàåòñÿ, ÷òî ôèçè÷åñêîå ñîåäèíåíèå îáû÷íîôóíêöèîíèðóåò íåïðåðûâíî â òå÷åíèå î÷åíü äîëãîãî âðåìåíè, àíå óñòàíàâëèâàåòñÿ è çàâåðøàåòñÿ ïåðèîäè÷åñêè.ñèììåòðè÷íûéïðîòîêîë ðàçäâèæíîãî îêíàÎøèáêè, âîçíèêàþùèå ïðè ïåðåäà÷åñîîáùåíèéÏðè ôèçè÷åñêîì ñîåäèíåíèè ñîîáùåíèÿ íå ìîãóò îáãîíÿòü äðóãäðóãà, è îíè òàêæå íå ìîãóò äóáëèðîâàòüñÿ. Ïîýòîìóðàññìàòðèâàþòñÿ òîëüêî îøèáêè ïîòåðè ñîîáùåíèÿ.Ñîäåðæàíèå ñîîáùåíèÿ, ïåðåäàâàåìîãî ïî ôèçè÷åñêîìó êàíàëóñâÿçè, ìîæåò áûòü ïîâðåæäåíî.

Òåì íå ìåíåå ìîæíîïðåäïîëàãàòü, ÷òî ïðîöåññ-ïîëó÷àòåëü ñïîñîáåí îáíàðóæèâàòüèñêàæåíèÿ ñîîáùåíèé, íàïðèìåð, ïðè ïîìîùè ñ÷åò÷èêîâ÷åòíîñòè èëè êîäèðîâàíèÿ ñ èñïðàâëåíèåì îøèáîê (êîäûÕýììèíãà, Ðèäà-Ìàëëåðà è äð.).Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàÏîñòàíîâêà çàäà÷è.inpABCD..YZp?inq à á â . . þ ÿ. . . . . . .

. . Q. p. . . . . . . . . . . .. . . . . . . . . . Q. q. . . . . . . . . . -.?outpoutq?q?Ïðîöåññàì p è q òðåáóåòñÿ ïåðåäàòü ïîòîêè äàííûõ inp è inqäðóã äðóãó è çàïèñàòü ïîëó÷åííûå äàííûå â ìàññèâû outp è outq . êàíàëå ñâÿçè âîçìîæíû ïîìåõè, ïðèâîäÿùèå ê ïîòåðå ñîîáùåíèé.Îáùàÿ èäåÿ àëãîðèòìàÎáùàÿ èäåÿ àëãîðèòìàIÂõîäíûå äàííûå îäíîãî ïðîöåññà ñëóæàò äëÿïîäòâåðæäåíèÿ ïîëó÷åíèÿ ñîîáùåíèé îò äðóãîãî ïðîöåññà.Îáùàÿ èäåÿ àëãîðèòìàIIÂõîäíûå äàííûå îäíîãî ïðîöåññà ñëóæàò äëÿïîäòâåðæäåíèÿ ïîëó÷åíèÿ ñîîáùåíèé îò äðóãîãî ïðîöåññà.Ñîîáùåíèÿ ýòî íàáîðû âèäà h , w , ii, ãäåw ,àiïàêåòà.ïàêåòûèíôîðìàöèîííîå ñëîâîpackïîðÿäêîâûé íîìåðÎáùàÿ èäåÿ àëãîðèòìàIIÂõîäíûå äàííûå îäíîãî ïðîöåññà ñëóæàò äëÿïîäòâåðæäåíèÿ ïîëó÷åíèÿ ñîîáùåíèé îò äðóãîãî ïðîöåññà.Ñîîáùåíèÿ ýòî íàáîðû âèäà h , w , ii, ãäåw ,àiïàêåòà.Ïàêåò h , w , ii, îòïðàâëåííûé ïðîöåññîì p , ïåðåäàåòñëîâî w = inp [i] ïðîöåññó q è ïîäòâåðæäàåò óñïåøíîåïîëó÷åíèå ðÿäà ïàêåòîâ, îòïðàâëåííûõ ïðîöåññîì q .ïàêåòûèíôîðìàöèîííîå ñëîâîIpackpackïîðÿäêîâûé íîìåðÎáùàÿ èäåÿ àëãîðèòìàIIÂõîäíûå äàííûå îäíîãî ïðîöåññà ñëóæàò äëÿïîäòâåðæäåíèÿ ïîëó÷åíèÿ ñîîáùåíèé îò äðóãîãî ïðîöåññà.Ñîîáùåíèÿ ýòî íàáîðû âèäà h , w , ii, ãäåw ,àiïàêåòà.Ïàêåò h , w , ii, îòïðàâëåííûé ïðîöåññîì p , ïåðåäàåòñëîâî w = inp [i] ïðîöåññó q è ïîäòâåðæäàåò óñïåøíîåïîëó÷åíèå ðÿäà ïàêåòîâ, îòïðàâëåííûõ ïðîöåññîì q .Ïðîöåññ p ìîæåò ¾îïåðåæàòü¿ ïðîöåññ q íà íåêîòîðîåçàäàííîå ÷èñëî ïàêåòîâ `p , åñëè ìû ïîñòàíîâèì, ÷òîîòïðàâëåíèå ïàêåòà h , w , ii ïðîöåññîì p ïîäòâåðæäàåòïîëó÷åíèå ñëîâ ñ íîìåðàìè 0, 1, .

. . , (i − `p ) îò ïðîöåññà q .ïàêåòûèíôîðìàöèîííîå ñëîâîIIpackpackpackïîðÿäêîâûé íîìåðÎáùàÿ èäåÿ àëãîðèòìàIIÂõîäíûå äàííûå îäíîãî ïðîöåññà ñëóæàò äëÿïîäòâåðæäåíèÿ ïîëó÷åíèÿ ñîîáùåíèé îò äðóãîãî ïðîöåññà.Ñîîáùåíèÿ ýòî íàáîðû âèäà h , w , ii, ãäåw ,àiïàêåòà.Ïàêåò h , w , ii, îòïðàâëåííûé ïðîöåññîì p , ïåðåäàåòñëîâî w = inp [i] ïðîöåññó q è ïîäòâåðæäàåò óñïåøíîåïîëó÷åíèå ðÿäà ïàêåòîâ, îòïðàâëåííûõ ïðîöåññîì q .Ïðîöåññ p ìîæåò ¾îïåðåæàòü¿ ïðîöåññ q íà íåêîòîðîåçàäàííîå ÷èñëî ïàêåòîâ `p , åñëè ìû ïîñòàíîâèì, ÷òîîòïðàâëåíèå ïàêåòà h , w , ii ïðîöåññîì p ïîäòâåðæäàåòïîëó÷åíèå ñëîâ ñ íîìåðàìè 0, 1, .

. . , (i − `p ) îò ïðîöåññà q .Êîíñòàíòû îïåðåæåíèÿ `p è `q èçâåñòíû ïðîöåññàì p è q .ïàêåòûèíôîðìàöèîííîå ñëîâîIIpackpackIpackïîðÿäêîâûé íîìåðÎáùàÿ èäåÿ àëãîðèòìàÒàêèì îáðàçîì, â ïðîòîêîëå ñîáëþäàþòñÿ äâà ïðèíöèïà:Îáùàÿ èäåÿ àëãîðèòìàÒàêèì îáðàçîì, â ïðîòîêîëå ñîáëþäàþòñÿ äâà ïðèíöèïà:1. Ïðîöåññ p ìîæåò îòïðàâèòü ñëîâî inp [i] (â ïàêåòåh, inp [i], ii) òîëüêî ïîñëå òîãî, êàê áóäóò çàíåñåíû âïàìÿòü âñå ñëîâà, íà÷èíàÿ ñ outp [0] è îêàí÷èâàÿoutp [i − `p ] , ò.å.

êîãäà áóäåò âûïîëíÿòüñÿ íåðàâåíñòâîi < sp + `p , ãäå sp = min{j : outp [j] = udef } .packÎáùàÿ èäåÿ àëãîðèòìàÒàêèì îáðàçîì, â ïðîòîêîëå ñîáëþäàþòñÿ äâà ïðèíöèïà:1. Ïðîöåññ p ìîæåò îòïðàâèòü ñëîâî inp [i] (â ïàêåòåh, inp [i], ii) òîëüêî ïîñëå òîãî, êàê áóäóò çàíåñåíû âïàìÿòü âñå ñëîâà, íà÷èíàÿ ñ outp [0] è îêàí÷èâàÿoutp [i − `p ] , ò.å. êîãäà áóäåò âûïîëíÿòüñÿ íåðàâåíñòâîi < sp + `p , ãäå sp = min{j : outp [j] = udef } .2. Êàê òîëüêî p ïîëó÷àåò ïàêåò h , w , ii, îòïàäàåòíåîáõîäèìîñòü â ïîâòîðíîé ïåðåäà÷å ñëîâ, íà÷èíàÿ ñ inp [0]è îêàí÷èâàÿ inp [i − `q ] .packpackÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàvarSpsp , apinpoutp:: array of word: array of word: { ap ≤ i < sp + `p }Rp: {hinitinitbegin}send hpackreceive(*endelse}, w , ii ∈ QpQp := Qp \ hpack, w , iipackbeginto qend;èãíîðèðîâàòü ïîâòîðíîå ïîëó÷åíèå ïàêåòà *)end: {h, inp [i], ii;;Lp0, 0, w , ii ∈ Qphpack, w , iiif outp [i] = udef thenbegin outp [i] := wap := max (ap , i − `q + 1)sp := min {j| outp [j] = udef }packbegin;(* Data to be sent *) ;udef , udef , .

. . ;integer{}endÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà1. Äåéñòâèå p îñóùåñòâëÿåò îòïðàâëåíèå i -ãî âõîäíîãîñëîâà ïðîöåññà p ,S2. ÄåéñòâèåRpîñóùåñòâëÿåò ïðèåì ñëîâà ïðîöåññîì p ,3. Äåéñòâèå p ìîäåëèðóåò ïîòåðþ ïàêåòà, àäðåñàòîìêîòîðîãî ÿâëÿåòñÿ ïðîöåññ p .LÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàvarSpsp , apinpoutp:: array of word: array of word: { ap ≤ i < sp + `p }Rp: {hinitinitbegin}send hpackreceive(*endelse}, w , ii ∈ QpQp := Qp \ hpack, w , iipackbeginto qend;èãíîðèðîâàòü ïîâòîðíîå ïîëó÷åíèå ïàêåòà *)end: {h, inp [i], ii;;Lp0, 0, w , ii ∈ Qphpack, w , iiif outp [i] = udef thenbegin outp [i] := wap := max (ap , i − `q + 1)sp := min {j| outp [j] = udef }packbegin;(* Data to be sent *) ;udef , udef , . . . ;integer{}endÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà: { ap ≤ i < sp + `p }send h , inp [i], ii to qÄàííûå äëÿ îòïðàâëåíèÿ âûáèðàþòñÿ èç ðàçäâèæíîãî îêíàSpbeginpackap ≤ i < sp + `pendÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà: { ap ≤ i < sp + `p }send h , inp [i], ii to qÄàííûå äëÿ îòïðàâëåíèÿ âûáèðàþòñÿ èç ðàçäâèæíîãî îêíàSpbeginpackendap ≤ i < sp + `pÏðåäïîëàãàåòñÿ, ÷òîËåâàÿ ñòâîðêà : ap = min{i : outp [i + `q ] = udef } íàèìåíüøèé íîìåð òîãî ýëåìåíòà â ìàññèâå inp ,ïîëó÷åíèå êîòîðîãî åùå íå ïîäòâåðäèë ïðîöåññ q .Çíà÷èò, inp [ap ] åùå íóæíî îòïðàâëÿòü.Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà: { ap ≤ i < sp + `p }send h , inp [i], ii to qÄàííûå äëÿ îòïðàâëåíèÿ âûáèðàþòñÿ èç ðàçäâèæíîãî îêíàSpbeginpackendap ≤ i < sp + `pÏðåäïîëàãàåòñÿ, ÷òîËåâàÿ ñòâîðêà : ap = min{i : outp [i + `q ] = udef } íàèìåíüøèé íîìåð òîãî ýëåìåíòà â ìàññèâå inp ,ïîëó÷åíèå êîòîðîãî åùå íå ïîäòâåðäèë ïðîöåññ q .Çíà÷èò, inp [ap ] åùå íóæíî îòïðàâëÿòü.Ïðàâàÿ ñòâîðêà : sp + `p − 1 , ãäå sp = min{j : outp [j] = udef } íàèìåíüøèé íîìåð òîãî ýëåìåíòà â ìàññèâå outp ,â êîòîðûé åùå íå çàïèñàíû ïîëó÷åííûå äàííûå.Çíà÷èò, inp [sp + `p ] åùå ðàíî îòïðàâëÿòü âêà÷åñòâå ïîäòâåðæäåíèÿ î ïîëó÷åíèè äàííûõ.Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàRp:{hbegin}, w , ii ∈ Qphpack, w , iiif outp [i] = udef thenbegin outp [i] := wap := max (ap , i − `q + 1)sp := min {j| outp [j] = udef }packreceive;;(*endendelse;èãíîðèðîâàòü ïîâòîðíîå ïîëó÷åíèå ïàêåòà *)Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàRp:{hbegin}, w , ii ∈ Qphpack, w , iiif outp [i] = udef thenbegin outp [i] := wap := max (ap , i − `q + 1)sp := min {j| outp [j] = udef }packreceive;;(*endelse;èãíîðèðîâàòü ïîâòîðíîå ïîëó÷åíèå ïàêåòà *)endÏîëó÷èâ ñîîáùåíèå, ïðîöåññ âíà÷àëå ïðîâåðÿåò, íå áûëî ëèèäåíòè÷íîå ñîîáùåíèå ïîëó÷åíî ðàíåå (â ýòîì ñëó÷àå ïðîöåññèìååò äåëî ñ ïîâòîðíûì ïîëó÷åíèåì ñîîáùåíèÿ).Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàRp:{hbegin}, w , ii ∈ Qphpack, w , iiif outp [i] = udef thenbegin outp [i] := wap := max (ap , i − `q + 1)sp := min {j| outp [j] = udef }packreceive;;(*endelse;èãíîðèðîâàòü ïîâòîðíîå ïîëó÷åíèå ïàêåòà *)endÏîëó÷èâ ñîîáùåíèå, ïðîöåññ âíà÷àëå ïðîâåðÿåò, íå áûëî ëèèäåíòè÷íîå ñîîáùåíèå ïîëó÷åíî ðàíåå (â ýòîì ñëó÷àå ïðîöåññèìååò äåëî ñ ïîâòîðíûì ïîëó÷åíèåì ñîîáùåíèÿ).Åñëè ýòî íå òàê, òî ñëîâî, ñîäåðæàùååñÿ â ñîîáùåíèè,çàïèñûâàåòñÿ â âûõîäíîé ìàññèâ, è ïðè ýòîì çíà÷åíèÿïåðåìåííûõ ap è sp èçìåíÿþòñÿ.Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàLp:{h}, w , ii ∈ QpQp := Qp \ hpack, w , iipackbegin{}endÑèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíàLp:{h}, w , ii ∈ QpQp := Qp \ hpack, w , iipackbegin{}endÌîäåëèðîâàíèå ïîòåðè ñîîáùåíèÿ ïðîâîäèòñÿ ïóòåì óäàëåíèÿïðîèçâîëüíîãî ñîîáùåíèÿ èç ìíîæåñòâà ñîîáùåíèé Qp ,ïðåáûâàþùèõ íà ýòàïå ïåðåñûëêè îò ïðîöåññà q ê ïðîöåññó p .Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà×òî ïëîõîãî ìîæåò ñëó÷èòüñÿ?Ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà×òî ïëîõîãî ìîæåò ñëó÷èòüñÿ?1.