Ðåôåðàò: Ðàñïðåäåëåííûå àëãîðèòìû
Ðåôåðàò: Ðàñïðåäåëåííûå àëãîðèòìû
Ïðîëîã 6
1 Ââåäåíèå: ðàñïðåäåëåííûå ñèñòåìû 7
1.1 ×òî òàêîå ðàñïðåäåëåííàÿ ñèñòåìà? 7
1.1.1 Ìîòèâàöèÿ 8
1.1.2 Êîìïüþòåðíûå ñåòè 10
1.1.3 Ãëîáàëüíûå ñåòè 11
1.1.4 Ëîêàëüíûå ñåòè 13
1.1.5 Ìíîãîïðîöåññîðíûå êîìïüþòåðû 16
1.1.6 Âçàèìîäåéñòâóþùèå ïðîöåññû 19
1.2 Àðõèòåêòóðà è ßçûêè 22
1.2.1 Àðõèòåêòóðà 22
1.2.2 Ññûëî÷íàÿ Ìîäåëü OSI 24
1.2.3 OSI Ìîäåëü â ëîêàëüíûõ ñåòÿõ: IEEE Ñòàíäàðòû 26
1.2.4 Ïîääåðæêà ßçûêà 27
1.3 Ðàñïðåäåëåííûå Àëãîðèòìû 29
1.3.1 Ðàñïðåäåëåííûé ïðîòèâ Öåíòðàëèçîâàííûõ Àëãîðèòìîâ 30
1.3.2 Ïðèìåð: Ñâÿçü ñ îäèíî÷íûì ñîîáùåíèåì 32
1.3.3 Îáëàñòü èññëåäîâàíèÿ 37
1.3.4 Èåðàðõè÷åñêàÿ ñòðóêòóðà êíèãè 37
2 Ìîäåëü 40
2.1 Ñèñòåìû ïåðåõîäà è àëãîðèòìû 41
2.1.1 Ñèñòåìû ïåðåõîäîâ 42
2.1.2 Ñèñòåìû ñ àñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé 43
2.1.3 Ñèñòåìû ñ ñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé 45
2.1.4 Ñïðàâåäëèâîñòü 47
2.2 Äîêàçàòåëüñòâî ñâîéñòâ ñèñòåì ïåðåõîäà 47
2.2.1 Ñâîéñòâà áåçîïàñíîñòè 48
2.2.2 Ñâîéñòâà æèâîñòè 50
2.3 Êàóçàëüíûé ïîðÿäîê ñîáûòèé è ëîãè÷åñêèå ÷àñû 51
2.3.1 Íåçàâèñèìîñòü è çàâèñèìîñòü ñîáûòèé 52
2.3.2 Ýêâèâàëåíòíîñòü èñïîëíåíèé: âû÷èñëåíèÿ 54
2.3.3 Ëîãè÷åñêèå ÷àñû 57
2.4 Äîïîëíèòåëüíûå äîïóùåíèÿ, ñëîæíîñòü 60
2.4.2 Ñâîéñòâà êàíàëîâ 62
2.4.3 Äîïóùåíèÿ ðåàëüíîãî âðåìåíè 64
2.4.4 Çíàíèÿ ïðîöåññîâ 64
2.4.5 Ñëîæíîñòü ðàñïðåäåëåííûõ àëãîðèòìîâ 66
3 Ïðîòîêîëû Ñâÿçè 66
3.1 Ñáàëàíñèðîâàííûé ïðîòîêîë ñêîëüçÿùåãî îêíà 68
3.1.1 Ïðåäñòàâëåíèå ïðîòîêîëà 68
3.1.2 Äîêàçàòåëüñòâî ïðàâèëüíîñòè ïðîòîêîëà 71
3.1.3 Îáñóæäåíèå ïðîòîêîëà 73
3.2 Ïðîòîêîë, îñíîâàííûé íà òàéìåðå 75
3.2.1 Ïðåäñòàâëåíèå Ïðîòîêîëà 78
3.2.2 Äîêàçàòåëüñòâî êîððåêòíîñòè ïðîòîêîëà 81
3.2.3 Îáñóæäåíèå ïðîòîêîëà 85
Óïðàæíåíèÿ ê ãëàâå 3 88
Ðàçäåë 3.1 88
Ðàçäåë 3.2 89
4 Àëãîðèòìû ìàðøðóòèçàöèè 89
4.1 Àäðåñàò-îñíîâàííàÿ ìàðøðóòèçàöèÿ 91
4.2 Ïðîáëåìà êðîò÷àéøèõ ïóòåé âñåõ ïàð 95
4.2.1 Àëãîðèòì Ôëîéäà-Óîøàëà 95
4.2.2 Àëãîðèòì êðîò÷àéøåãî ïóòè.(Toueg) 98
4.2.3 Îáñóæäåíèå è Äîïîëíèòåëüíûå Àëãîðèòìû 102
4.3 Àëãîðèòì Netchange 106
4.3.1 Îïèñàíèå àëãîðèòìà 107
4.3.2 Êîððåêòíîñòü àëãîðèòìà Netchange 112
4.3.3 Îáñóæäåíèå àëãîðèòìà 113
4.4 Ìàðøðóòèçàöèÿ ñ Êîìïàêòíûìè Òàáëèöàìè ìàðøðóòèçàöèè 114
4.4.1 Ñõåìà ðàçìåòêè äåðåâüåâ 115
4.4.2 Èíòåðâàëüíàÿ ìàðøðóòèçàöèÿ 118
4.4.3 Ïðåôèêñíàÿ ìàðøðóòèçàöèÿ 125
4.5 Èåðàðõè÷åñêàÿ ìàðøðóòèçàöèÿ 127
4.5.1 Óìåíüøåíèå êîëè÷åñòâà ðåøåíèé ìàðøðóòèçàöèè 128
Óïðàæíåíèÿ ê ×àñòè 4 130
Ðàçäåë 4.1 130
Ðàçäåë 4.2 131
Ðàçäåë 4.3 131
Ðàçäåë 4.4 131
Ðàçäåë 4.5 132
5 Áåñòóïèêîâàÿ êîììóòàöèÿ ïàêåòîâ 132
5.1 Ââåäåíèå 133
5.2 Ñòðóêòóðèðîâàííûå ðåøåíèÿ 134
5.2.1 Áóôåðíûå Ãðàôû 135
5.2.2 Îðèåíòàöèè G 138
5.3 Íåñòðóêòóðèðîâàííûå ðåøåíèÿ 141
5.3.1 Êîíòðîëëåðû ñ ïðÿìûì è îáðàòíûì ñ÷åòîì 141
5.3.2 Êîíòðîëëåðû ñ îïåðåæàþùèì è îòñòàþùèì ñîñòîÿíèåì 142
5.4 Äàëüíåéøèå ïðîáëåìû 144
5.4.1 Òîïîëîãè÷åñêèå èçìåíåíèÿ 145
5.4.2 Äðóãèå âèäû òóïèêîâ 146
5.4.3 Ëàéôëîê (livelock) 147
Óïðàæíåíèÿ ê Ãëàâå 5 149
Ñòðàíèöû: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
