Přepínání • Směrování určeno pro velké sítě – velká režie • vyměňovaných dat • konstrukce směrovacích tabulek • vlastního směrování (prohledávání tabulek) • Síť tvořena fyzickými spoji propojujícími jednotlivé prvky – přepínání: mezistupeň mezi fyzickým přenosem a rozlehlou sítí Stavební prvky • Lokální sítě na sdíleném médiu (podrobněji v následující přednášce) – omezený počet uzlů (kolize) – omezená největší vzdálenost uzlů – výkonnost (sdílené médium) • Řešení: propojení takovýchto lokálních sítí Přemostění • Můstky (bridges) – transparentní propojení sítí • Vlastnosti – všechen provoz prochází můstkem – oddělí sdílené média (kolize se nepřenáší) – může mít více jak dvě připojení Backward learning algorithm • Zasílání (forwarding) – můstek se „učí“ umístění (vzhledem k připojeným sítím) nasloucháním na médiu – sleduje zdrojové adresy – zasílá podle cílové adresy – informace „stárne“ (pokud z daného zdroje nevidí po nějakou dobu data, údaj o umístění zapomene – v řádu desítek sekund) Složitější sítě • Pomocí můstků lze vytvořit sítě s cykly • Jak v takovém prostředí nalézt správnou cestu (obdoba směrování) • Spanning Tree algorithm (výpočet kostry) – nezávislý na předchozím backward learning algoritmu Výpočet kostry • Distribuovaný algoritmus na hledání kostry – robustnost proti výpadkům – nevyžaduje centrální organizaci Náčrt algoritmu • Cílem je některé porty můstků nepoužívat • Volba kořenového vrcholu stromu (nejnižší adresa) • Postupný růst stromu -- nejkratší vzdálenost od kořene (preference mají uzly s nižší adresou, pokud více možností) • Nalezené „nejlepší“ cesty (definují aktivní porty můstků) • Vypnout všechny ostatní porty Algoritmus – pokračování • Každý můstek posílá periodické zprávy – vlastní adresa, adresa kořenového můstku, vzdálenost od kořene • Když dostane zprávu od souseda, upraví definici „nejlepší“ cesty – preferuje kořen s menší adresou – preferuje menší vzdálenosti – při stejných vzdálenostech preferuje nižší adresu Algoritmus – inicializace • Na začátku si každý můstek myslí, že je kořenem – pošle konfigurační informaci na všechny porty • Následně můstky posílají jen „nejlepší“ konfigurace (cesty) – přičti 1 k vzdálenosti, pošli na porty kde stále je „nejlepší“ cesta – vypni zasílání dat na všech ostatních portech Algoritmus – příklad • Formát zprávy: – • Příklady zpráv jdoucích přes B3 • B3 pošle můstkům B2 a B5 • B3 dostane a , přijme B2 coby kořen • B3 pošle můstku B5 • B3 dostane a , přijme B1 coby kořen • B3 chce poslat , ale to není nejlepší cesta • B3 dostane znovu a -- stabilita – vypne posílání dat na síť A Algoritmus – upřesnění • Informace „stárne“ – selhání kořene vede eventuálně k volbě nového kořene • Rekonfigurace neprobíhá okamžitě (je tlumena) – prevence vzniku dočasných cyklů Přepínače (switches) • V principu se jedná o více portové můstky – v současné době nejpoužívanější forma propojení lokálních sítí – lze připojovat buď samostatné stroje nebo podsítě (kaskáda přepínačů) • Tzv. L2 směrování – založeno na adresách sítě, nikoliv IP adresách – z IP pohledu uniformní prostředí Omezení • Vhodné pouze pro malé sítě – skutečně funkční „plug and play“ • Nevhodné pro velké sítě – přepínací tabulky rostou s počtem uzlů (koncových stanic, ne můstků) – přílišný automatismus (důsledek „plug and play“ – minimální kontrola nad cestami) – netvoří hranice pro broadcastový provoz – pomalé – limitováno použitým algoritmem hledání kostry – neumožňuje logické oddělení lokálních sítí Přepínání okruhů • Dvě fáze: – vytvoření spojení (okruhu) – vlastní přenos dat • Životnost virtuálního okruhu – permanentní, nastaven administrátorem (PVC) – dočasný, vytvořen na žádost (SVC) Kódování pro přenos dat • Data a signál • Analogový versus digitální • Základní funkce Signál • Elektromagnetický signál – časování – frekvence • Analogový a digitální signál – čas • Spektrum a jeho šířka – různé frekvence – interval frekvencí Analogový vs. digitální • Nosná veličina – spojitá změna – diskrétní změna (pulsy) • Kódování a dekódování – hodnota amplitudy, frekvence, fáze – generování a detekce pulsů • Defekty – přenosový šum, útlum, nelinearity – detekovatelné, odfiltrovatelné • Zesilování – kumulace defektů – „pouze“ opakuje signál Defekty signálů Vysílač (P[1][W])—> —> —>(P[2][W]) Přijímač • Útlum • Zmenšení amplitudy signálu – 10 log[10] (P[1]/P[2]) [dB] – zesílení – 10 log[10] (P[2]/P[1]) [dB] • Zkreslení – různá rychlost průchodu médiem • nutná mezera mezi přenášenými symboly Defekty signálů – Šum • zeslabení až rušení signálu • kvantifikace SNR (Signal to Noise Ratio) S/N[dB] = 10 log[10] S/N kde S je výkon signálu a N výkon šumu • velká SNR výhodou • klasifikace šumu – přeslech – impulsní šum – teplotní (bílý) šum Kódování • Ovlivnění kvality přijímaného signálu – šířka pásma • počet přenášených harmonických složek – S/N • zvýšená hodnota snižuje chybovost přenosu – rychlost dat • zvýšená hodnota zvyšuje chybovost přenosu • Snaha nalézt optimální kvalitu přijímaného signálu Analogový signál a data • Vlastní signál – nosný signál, g(t) • většinou sinusový průběh – modulační signál, m(t) • vlastní kódování (amplituda, frekvence, pásmo) • Analogová data – s(t) = (c+k m(t) g(t)) – amplitudová modulace • Digitální data – modulátor-demodulátor (modem) – modulační signál ekvivalentem digitálních dat Charakteristiky signálu • Periodicita: s(t+T) = s(t) • Frekvence: f = 1/T – 1/sec (Hz); počet opakování za sekundu • Amplituda: s(t) – okamžitá hodnota signálu („síla“) • Fáze: Φ – míra relativní pozice v čase v rámci periody signálu – s(t) = A.sin(2πf t); s(t) = A.sin(2πf t + p), fázový posun Digitální signál a data • Digitální signál – pulsy • Analogová data – periodické vzorkování analogového signálu (delta t) spojené s kódováním naměřené veličiny do pulsů – coder-decoder (codec) • Digitální data Digitální přenos • Dva diskrétní signály: vysoký-nízký • Non-return to zero, NRZ – chybí oddělení mezi jednotlivými stavy • pohyb základní linie (baseline wander) • desynchronizace hodin (clock recovery) • Non-return to zero inverted, NRZI – řešení pro 1, problém zůstává pro řetězce 0 • Manchester – 0 je „low-to-high“, 1 je „high-to-low“ Kódovací strategie Kódování 4B/5B 4B 5B 4B 5B 0000 11110 1000 10010 0001 01001 1001 10011 0010 10100 1010 10110 0011 10101 1011 10111 0100 01010 1100 11010 0101 01011 1101 11011 0110 01110 1110 11100 0111 01111 1111 11101 Bauds vs. bity za sekundu • Baudová rychlost – počet změn signálu za sekundu • Bitová rychlost – počet přenesených bitů za sekundu • NRZ: 1bd = 1b • Manchester: 2bd = 1b • Je možný i opačný poměr, tj. bitová>baudová Digitální data a analogový signál • Modulace – amplitudy – fáze – frekvence nosného signálu. Převod digitálních dat na analogový signál • Demodulace Detekce chyb • Zjištění chyby – případně i její korekce • Založena na redundanci (pošleme více bitů než je nezbytně třeba) – vysílač přidá bity, jejichž hodnota je funkcí přenášených dat – přijímač spočte stejnou funkci a v případě rozdílu hodnoty detekuje chybu • Oprava – opakováním vysílání Parita • Paritní bit – lichá parita: lichý počet jedniček – sudá parita: sudý počet jedniček • Detekuje chybu v jednom bitu – vhodné pro bílý šum (náhodné chyby) – nevhodné pro blokové (související) chyby • Podélná (běžnější) a vertikální parita CRC • Cyclic redundancy check • zpráva n bitů, přidá se k bitů, n>>k – typicky n=12000 (1500byte), k=32 • Zpráva reprezentuje polynom M(x) stupně n-1 • k je stupeň vhodného dělícího polynomu C(x) • Garantuje silnou kontrolu – detekce všech jednobitových chyb – možné i všechny dvoubitové chyby – většina dávkových chyb CRC II • Ke zprávě n+1 bitů (M(x)) se přidá k bitů – P(x) • P(x) musí být beze zbytku dělitelné C(x) • Postup: ^– T(x) = M(x)*x^k – Rem= T(x)/C(x) – P(x) = T(x)-Rem • Snadná implementovatelnost: XOR a posuv Vlastnosti C(x) • Detekuje všechny jednobitové chyby, má-li nenulový první a poslední bit (x^k a x^0) • Detekuje všechny dvojbitové chyby, pokud má alespoň 3 jedničkové koeficienty po sobě • Detekuje lichý počet chyb, obsahuje-li x+1 • Detekuje skupinu chyb (burst), je-li kratší než k Varianty polynomu C(x) CRC-8 x^8+x^2+x+1 CRC-10 x^10+x^9+x^5+x^4+x+1 CRC-12 x^12+x^11+x^3+x^2+1 CRC-16 x^16+x^15+x^2+1 CRC-CCITT x^16+x^12+x^5+1 CRC-32 x^32+x^26+x^23+x^22+x^16+x^12+ x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1 Detekce versus korekce • Počet „zbytečně“ poslaných bitů/znaků • Režie spojená s detekčními a korekčními kódy • Běžné linky (nízká chybovost) – detekce • Linky s vysokou chybovostí (např. bezdrátové) – korekce • EC v sítích – Forward error correction, FEC Multiplexory • Jeden spoj, více vysílačů/přijímačů • Synchronní – (S)TDM (time division) • Frekvenční – FDM (frequency division) • Statistický multiplexing Bezdrátové sítě • IEEE 802.11 • Šířka pásma: 1, 2, 5.5 a 11 Mb/s – radiové vlny kolem 2,4 GHz – difúzní infračervené světlo • Rozprostřené (spread) pásmo – Frequency hopping: 79 pásem 1 MHz – n-bit chipping: 11-bitový chipping Bezdrátové sítě – kolize • Pohyb zdrojů – viditelnost není transitivní • MACA – Multiple Access with Collision Avoidance – handshake před vlastními daty – Request to Send (RTS) a Clear to Send (CTS) – Kdo vidí CTS nesmí vysílat – Finální ACK ukončí přenos Bezdrátové sítě – přístup • Ad hoc sítě • Organizované sítě – Přístupové body (Access Point) • Scanning – Uzel pošle Probe – Všechny slyšící AP pošlou Probe Response – Uzel vybere jeden a pošle Association Request – Příslušný AP odpoví Association Response Teorie přenosu dat • Míra informace – I(z) = - log p(z) – Méně pravděpodobná zpráva nese více informace • Entropie – H(z) = -å p(z) log p(z) – vážené množství informace – maximum: H[max](z) = log n Abeceda • Množina m prvků (znaků) • Používá se pro kódování zprávy • Je možné definovat apriorní pravděpodobnost výskytu znaku ve zprávě • Maximální entropie zprávy délky n H[max] = n log m Kódování • Změna mohutnosti abecedy • Utajení • Komprese (lepší využití kapacity kanálu) • Digitální representace spojitých dat Příklady příkladů písemky • Rozdíl mezi „dense“ a „sparse“ módem při šíření multicastu • Popište základní princip CRC • Uveďte příklady spojovaných a nespojovaných služeb • Čím se liší TCP a UDP? • Srovnejte princip přenosu paketů v IP sítích s přenosem buněk v ATM sítích Příklady příkladů písemky • Vyberte si nějaký intradoménový (interdoménový) směrovací protokol a popište jeho vlastnosti • V čem vidíte hlavní rozdíl mezi směrováním a přepínáním? • Srovnejte přepínání v paketových a ATM sítích • Co je CSMA/CD a jaké jsou principy jeho funkce?