Počítačové sítě a operační systémy Jaromír Plhák, 18.4.2016PB169 Počítačové sítě a operační systémy Jaromír Plhák xplhak@fi.muni.cz Řízení přístupu k médiu PB169 Počítačové sítě a operační systémy Snímek 2 z 48 Řízení přístupu k médiu (1) • Media Access Control (MAC) • Přístupové metody dovolují předávat data mezi libovolnými stanicemi, aniž by jejich spojení bylo rušeno vysíláním jiné stanice – Jedná se o strategii, kterou používají stanice na síti pro přístup k přenosovému médiu • Více zařízení sdílí jednu komunikační linku • Zařízení chtějí nezávisle komunikovat – A posílat data skrze sdílenou linku PB169 Počítačové sítě a operační systémy Snímek 3 z 48 Řízení přístupu k médiu (2) • Řízení přístupu k médiu je založeno na metodách multiplexu, které umožňují sdílet kapacitu média – Multiplex je poskytován na fyzické úrovni • Dalšími metodami jsou řízené a neřízené přístupy stanic k médiu • Cílem je eliminace kolizí (konfliktů) při vysílání PB169 Počítačové sítě a operační systémy Snímek 4 z 48 Způsoby přístupu k médiu (1) • Řízený (deterministický) přístup: – Uzly získávají přístup k přenosovému médiu v předem určeném pořadí – Je zaručeno, že každý uzel získá přístup do sítě v časovém intervalu dané délky (obvykle několik mikrosekund až milisekund) • Stanice si rezervují časový díl PB169 Počítačové sítě a operační systémy Snímek 5 z 48 Způsoby přístupu k médiu (2) • Řízený (deterministický) přístup (pokr.): – Dále se dělí podle lokalizace řídící autority: • Centralizovaný = pořadí, ve kterém stanice získávají přístup je dáno serverem • Decentralizovaný = pořadí je dáno fyzickým popř. logickým uspořádáním uzlů PB169 Počítačové sítě a operační systémy Snímek 6 z 48 Způsoby přístupu k médiu (3) • Neřízený (náhodný, pravděpodobnostní, soupeřivý) přístup: – Může být použitý pouze v sítích, kde jsou přenosy rozesílány všem, takže každý uzel dostane informace přibližně ve stejný okamžik – Pokud uzel chce vysílat, zkontroluje linku • Jestliže je linka obsazená, nebo pokud přenos uzlu koliduje s nějakým jiným přenosem, je přenos zrušen – Uzel pak čeká náhodně dlouhou dobu, než zkusí přístup znovu PB169 Počítačové sítě a operační systémy Snímek 7 z 48 Způsoby přístupu k médiu (4) • Protože v případě deterministických přístupových metod dostává každý uzel možnost přístupu k síti v mezích pevně daného časového intervalu, jsou tyto metody mnohem efektivnější v sítích s náročným provozem • Uzly používající náhodné přístupové metody na zatížené síti ztrácí mnoho času pokusy získat přístup a poměrně málo času vlastním vysíláním dat PB169 Počítačové sítě a operační systémy Snímek 8 z 48 Způsoby přístupu k médiu (5) • Multiplexově-orientované přístupy – Zpřístupnění multiplexingu fyzické vrstvy vrstvě datového spoje – SDMA (Space-Division Media Access) • Sdílený prostor – FDMA (Frequency-Division Media Access) • Ve frekvenčním prostoru – TDMA (Time-Division Media Access) • Sdílený čas – CDMA (Code Division Media Access) • V kódovém prostoru • Nebo kombinací předchozích metod dohromady PB169 Počítačové sítě a operační systémy Snímek 9 z 48 Multiplexing (1) • MUX/DEMUX PB169 Počítačové sítě a operační systémy Snímek 10 z 48 Multiplexing (2) • Technika sdílení dostupné přenosové kapacity přenosového média souběžnými komunikacemi • Cílem je efektivnější využití média – Uplatnění zejména u optických vláken a bezdrátu • Pro analogové signály: – Frequency-Division Multiplexing (FDM) – Wave-Division Multiplexing (WDM) • Pro digitalní signály: – Time-Division Multiplexing (TDM) PB169 Počítačové sítě a operační systémy Snímek 11 z 48 Multiplexing – příklady • Frekvenční prostor – Telefonie – 4 kHz pro jeden hovor – Seskupení hovorů mezi ústřednami – 12 hovorových kanálů po 4 kHz – pásmo 60-108 kHz • (Geo) prostor – Auta na dálnicích ve více pruzích • Časový prostor – Auta na dálnici v jednom pruhu – každé v jednom čase na jiném místě využívá celou kapacitu pruhu PB169 Počítačové sítě a operační systémy Snímek 12 z 48 Frekvenční multiplexing (1) • Využitelná šířka pásma média je větší než požadovaná šířka pásma daného signálu PB169 Počítačové sítě a operační systémy Snímek 13 z 48 Frekvenční multiplexing (2) • Každý přenášený signál je modulován samostatným nosným signálem s unikátní nosnou frekvencí • Modulované nosné signály se kombinují do nového signálu, který se přenáší spojem – Multiplexory • Například pro telefonní spoje mezi ústřednami PB169 Počítačové sítě a operační systémy Snímek 14 z 48 Frekvenční multiplex (3) • Při přenosu vzduchem netřeba fyzicky realizovat multiplexory/demultiplexory, stanice mohou vysílat na odlišných frekvencích • Vhodné pro analogové signály – Je typický pro současný přenos různých typů analogových informací (rozhlas, televize) • Nevýhody – Pokud se nevysílá souvisle, plýtvá se šířkou pásma – Jsou nutné ochranné odstupy frekvenčních pásem PB169 Počítačové sítě a operační systémy Snímek 15 z 48 Frekvenční multiplex (4) PB169 Počítačové sítě a operační systémy Snímek 16 z 48 Dělení vlnové délky • Wave division multiplexing • Varianta FDM pro optické signály (optická vlákna) • Použití více světelných paprsků na různých frekvencích – Paprsky se rozkládají v hranolu • Každá barva světla (vlnová délka, frekvence) reprezentuje jeden kanál • Lze využít i polarizace PB169 Počítačové sítě a operační systémy Snímek 17 z 48 Časový multiplexing (1) • Dosažitelná rychlost přenosu dat v médiu je větší než požadovaná rychlost přenosu dat daného signálu PB169 Počítačové sítě a operační systémy Snímek 18 z 48 Časový multiplexing, TDMA (2) • V libovolném okamžiku kanál využívá výhradně jeden vysílající (po jistou dobu) • Vysoká propustnost i při mnoha vysílajících • Nutnost precizní synchronizace vysílače a přijímače • Pro digitální i analogové signály • Každý účastník má přidělen časový úsek (slot) jehož trvání závisí na počtu účastníků, kteří potřebují vysílat a na prioritě účastníka jemuž je časový slot přidělen PB169 Počítačové sítě a operační systémy Snímek 19 z 48 Časový multiplexing, TDMA (3) • Typická u LAN PB169 Počítačové sítě a operační systémy Snímek 20 z 48 Časově-frekvenční multiplexing • Kombinace FDM a TDM • Komunikační kanál dostane jisté frekvenční pásmo na určitou dobu – GSM, FHSS • Lepší ochrana proti odposlechu • Ochrana proti interferenci frekvencí • Nutná precizní synchronizace PB169 Počítačové sítě a operační systémy Snímek 21 z 48 Prostorový multiplex, SDMA • Prostor se segmentuje pomocí směrových antén (GSM) PB169 Počítačové sítě a operační systémy Snímek 22 z 48 Kódový multiplex, CDMA (1) • Založeno na teorii kódování, všechny stanice používají šířku pásma současně, každá vysílaný signál unikátně kóduje • Každý signál kódován unikátním kódem – Přijímač vše ostatní vnímá jako šum – V reálné praxi např. 128 bitů – Kódový prostor je proti frekvenčnímu prostoru obrovský (např. 232) PB169 Počítačové sítě a operační systémy Snímek 23 z 48 Kódový multiplex, CDMA (2) • Signály používají stejnou frekvenci • Efektivní využití šířky pásma • Není potřeba precizní synchronizace • Dobrá ochrana proti odposlechu • Nižší rychlosti • Složitější regenerace signálu PB169 Počítačové sítě a operační systémy Snímek 24 z 48 Kódový multiplex, CDMA (3) PB169 Počítačové sítě a operační systémy Snímek 25 z 48 Přístupy k médiu (připomenutí) • Řízený (deterministický) přístup: – Uzly získávají přístup k přenosovému médiu v předem určeném pořadí – Centralizovaný (polling) – Decentralizovaný (token passing) • Neřízený (náhodný, pravděpodobnostní, soupeřivý) přístup: – Pokud uzel chce vysílat, zkontroluje linku. Jestliže je linka obsazená, nebo pokud přenos uzlu koliduje s nějakým jiným přenosem, je přenos zrušen – CSMA/CA, CSMA/CD PB169 Počítačové sítě a operační systémy Snímek 26 z 48 Polling (1) • Metoda, při které se v předem daném pořadí neustále testují jednotlivé počítače v síti • Toto testování je prováděno formou výzev, kdy každý počítač je vyzván, zda-li vyžaduje pozornost (potřebuje vysílat) • Počítač může přistoupit k síti pouze je-li k tomu vyzván PB169 Počítačové sítě a operační systémy Snímek 27 z 48 Polling (2) • Zasílání výzev provádí zpravidla jeden centrální počítač (server), který také bývá označován jako controller popř. poller • Jedná se o metodu používanou zejména v sítích s jedním centrálním počítačem a k němu připojenými terminály PB169 Počítačové sítě a operační systémy Snímek 28 z 48 Token passing (1) • Přístupová metoda, která využívá speciální paket, tzv. token (pešek), k tomu, aby uzly v síti byly informovány o tom, že mohou vysílat • Vysílat může pouze uzel, který obdržel peška • Pešek je vytvořen při inicializaci sítě • Za jeho vytvoření je obvykle zodpovědný server či nějaká předem určená stanice PB169 Počítačové sítě a operační systémy Snímek 29 z 48 Token passing (2) • Vygenerováním peška jsou následně zahájeny síťové operace • V této metodě je pešek předáván z uzlu na uzel podle předem dané sekvence (logické nebo fyzické) • Pešek je v libovolném okamžiku: – Idle (dostupný) – Busy (používaný) PB169 Počítačové sítě a operační systémy Snímek 30 z 48 Token passing (3) A B C A B C A B C A B C A B C A B C idle token busy token datový packet PB169 Počítačové sítě a operační systémy Snímek 31 z 48 Token passing (4) • Proces předávání peška: – Uzel, který obdrží idle peška a chce vysílat, jej označí jako busy a pošle peška s připojeným datovým paketem dalšímu uzlu – Datový paket společně s peškem je předáván z uzlu na uzel dokud nedosáhne svého adresáta – Příjemce (adresát) potvrdí přijatý datový paket zasláním peška (příp. peška společně s datovým paketem) zpět odesílateli – Odesílatel uvede peška opět do stavu idle a předá jej dalšímu síťovému uzlu PB169 Počítačové sítě a operační systémy Snímek 32 z 48 Token passing (5) • Sítě pracující na principu předávání peška většinou vlastní mechanismy pro nastavení priorit získání peška • Sítě využívající předávání peška rovněž vyžadují přítomnost tzv. aktivního monitoru (AM) a jednoho nebo více pohotovostních monitorů (SM) • Úlohu aktivního monitoru plní zpravidla uzel, který peška vygeneroval PB169 Počítačové sítě a operační systémy Snímek 33 z 48 Token passing (6) • AM dále sleduje stav peška a v případě, že dojde k jeho ztrátě nebo poškození (po jistou dobu AM neobdrží korektního peška), vygeneruje peška nového a obnoví tak provoz na síti • SM kontrolují, zda AM provádí svou činnost a pokud dojde k jeho výpadku, tak jeden z SM se stává novým AM a síť se tak stává opět funkční PB169 Počítačové sítě a operační systémy Snímek 34 z 48 Aloha • Stanice vysílá kdykoliv ma připravený rámec • Kolize detekovány nepřijetím potvrzení o přijetí v definovaném časovém intervalu • Po kolizi náhodnou dobu vyčká a zkusí vysílat znovu • Neefektivní PB169 Počítačové sítě a operační systémy Snímek 35 z 48 Carrier Sense Multiple Access (1) • Upravená Aloha – Stanice vysílá, když je klid v komunikačním médiu • Protokol naslouchání signálu s vícenásobným přístupem (a detekcí kolizí) • Slouží k přenosu dat mezi uzly využitím souběžného všesměrového vysílání PB169 Počítačové sítě a operační systémy Snímek 36 z 48 Carrier Sense Multiple Access (2) • Může docházet ke kolizím – dvě stanice začnou vysílat zároveň • I kvůli tomu je omezená fyzická délka spojení • Pokud dojde ke kolizi, musí se data poslat znovu (prodleva je náhodná) • Počet kolizí se redukuje, ale ne zcela – CSMA se vždy používá ve variantě CD nebo CA PB169 Počítačové sítě a operační systémy Snímek 37 z 48 Carrier Sense Multiple Access (3) • Kdy stanice může přistupovat k médiu? • Co může stanice dělat, když je médium obsazené? • Jak stanice pozná, zda došlo či nedošlo ke kolizi? • Co může stanice dělat, když došlo ke kolizi? PB169 Počítačové sítě a operační systémy Snímek 38 z 48 CSMA/CD • V případě metody CSMA/CD (… with Collision Detection) získává přístup k sítí uzel, kterému se jako prvnímu podaří přistoupit k nečinné síti • Uzel, který chce vysílat informace do sítě, nejprve poslouchá, zda je na síti nějaký provoz (elektrická aktivita) • Vyslaný paket se šíří ke všem zbývajícím stanicím připojeným do sítě – Uzel dále pokračuje ve sledování sítě (sleduje, zda-li je na síti právě to, co tam poslal) PB169 Počítačové sítě a operační systémy Snímek 39 z 48 Typy CSMA/CD • Non-persistent (nenaléhající) CSMA – Síť volná – uzel začne vysílat – Síť obsazená – uzel náhodně dlouhou dobu počká a poté opět provede kontrolu obsazení sítě • Persistent (naléhající) CSMA – Síť volná – uzel začne vysílat – Síť obsazená – uzel neustále poslouchá provoz na síti a v okamžiku, kdy dojde k jejímu uvolnění začne ihned vysílat • P-persistent (p-naléhající) CSMA – Síť volná – uzel začne s pravděpodobností p ihned vysílat a s pravděpodobností 1-p počká jednu časovou jednotku, po níž znovu testuje obsazení sítě – Síť obsazená – uzel neustále poslouchá dokud se síť neuvolní a poté postupuje stejně jako v případě, kdy je síť volná PB169 Počítačové sítě a operační systémy Snímek 40 z 48 CSMA/CD – kolize (1) • Je možné, že dva (nebo více) uzlů na lince detekují nepřítomnost aktivity současně a začnou vysílat v téměř stejný okamžik. Toto má za následek vznik tzv. kolize • Kolize je detekována tak, že uzly, které vyslaly své pakety a sledují síť, zjistí, že na přenosovém médiu se vyskytují jiné informace, než ty, které tam vyslaly PB169 Počítačové sítě a operační systémy Snímek 41 z 48 CSMA/CD – kolize (2) • Každý uzel, který detekoval kolizi zruší svůj přenos vysláním rušícího signálu – jam signal • Poté počká náhodně dlouhou dobu a pokusí se k síti přistoupit znovu • Náhodně dlouhá doba (u každého uzlu jiná) zaručuje poměrně vysokou pravděpodobnost, že nedojde znovu ke kolizi mezi stejnými uzly PB169 Počítačové sítě a operační systémy Snímek 42 z 48 CSMA/CD – přijetí paketu • V sítích s CSMA/CD každý uzel poslouchá každý paket: – Uzel nejprve zkontroluje, zda-li se nejedná o fragment způsobený kolizí – Pokud ano, tak jej ignoruje – Nejedná-li se o fragment, uzel zkontroluje jeho cílovou adresu a pokud nastane jeden z následujících případů tak jej zpracuje • Cílová adresa je adresou tohoto uzlu • Jedná se o broadcast nebo multicast PB169 Počítačové sítě a operační systémy Snímek 43 z 48 CDMA/CD zhodnocení • CSMA/CD podává nejlepší výsledky, je-li síťová aktivita pouze mírná • Naopak nejhorších výsledků dosahuje, jestliže se síťový provoz skládá z množství malých zpráv • Tato přístupová metoda je využívána např. v sítích typu: – Ethernet (FastEthernet - vyjma 100BaseVG) – EtherTalk, G-Net, AT&T’s StarLAN PB169 Počítačové sítě a operační systémy Snímek 44 z 48 CSMA/CA • Metoda CSMA/CA (… with Collision Avoidance) je podobná jako CSMA/CD metoda, s tím rozdílem, že je zde snaha o vyhnutí se kolizím • Je nutné dodržovat vždy tzv. minimální rozestup mezi následujícími pakety (přibližně 200 mikrosekund) PB169 Počítačové sítě a operační systémy Snímek 45 z 48 Principy CSMA/CA (1) • Pokud uzel chce vysílat, poslouchá zda-li je na síti nějaká aktivita • Pokud ano, počká náhodně dlouhou dobu a po té se pokusí k síti přistoupit znovu • Pokud je síť nečinná (je na ní volno), pošle uzel signál RTS (Request To Send) PB169 Počítačové sítě a operační systémy Snímek 46 z 48 Principy CSMA/CA (2) • V případě, že se nejedná o broadcast: – RTS je adresován konkrétnímu uzlu – Vysílající uzel čeká na signál CTS (Clear To Send), kterým adresát odpoví na RTS – Signály RTS a CTS musí být poslány během předdefinovaného časového intervalu v opačném případě odesílatel předpokládá kolizi – Pokud odesílatel obdrží CTS, provede se přenos, pokud ne (RTS nebo CTS se poškodily), přenos se odloží PB169 Počítačové sítě a operační systémy Snímek 47 z 48 Principy CSMA/CA (3) • V případě broadcastu: – RTS je adresován na speciální adresu, která značí broadcast (255) – Nečeká se na CTS a okamžitě začíná přenos – RTS tedy slouží více jako prostředek k upoutání pozornosti, než jako žádost PB169 Počítačové sítě a operační systémy Snímek 48 z 48 CDMA/CA zhodnocení • Vyhýbání se kolizím vyžaduje méně složité obvody než detekce kolizí • Kolizím se však nelze vyhnout vždy – Pokud se objeví jsou řešeny programově • Využití v bezdrátových sítích • Využívána v sítích firmy Apple MacIntosh