Směrování obecně

Link State

• směrovače zasílá informace o lince, na kterou je připojen
• směrovače získají kompletní topologii sítě (broadcast)
• následné počítání nejkratší cesty (např. Dijkstra)
• informace o svých sousedech všem
• rychlá konvergence, zvládá rozlehlé sítě
• složitější algoritmus, větší nároky na CPU a paměť
• http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm
• http://www.cse.yorku.ca/~aaw/HFHuang/DijkstraStart.html

Protokol OSPF (Open Shortest Path First)

• nejpoužívanější LS protokol
• metrika: cena (1–65535, podle šířky pásma)
• rozšíření: autentizace zpráv, směrovací oblasti (další úroveň hierarchie), load-balancing (více cest se stejnou cenou)

Link State vs. Distance Vector

	Distance Vector	Link State
složitost	změna ceny linky se propaguje jen nejbližšímu sousedovi a těm, které to ovlivní	změna ceny linky se propaguje na všechny uzly, O(nE) zpráv
rychlost konvergence	count-to-infinity problém (směrovací cykly), může být pomalejší než LS	algoritmus O(n^2), zasílá O(nE) zpráv, trpí na oscilace
robustnost	nesprávný výpočet je šířen sítí	špatný výpočet se šíří jen sousedům
použití	menší sítě	menší i rozsáhlé sítě

Hierarchie směrování

• každý uzel celý Internet
• každá brána zná celý Internet
• hierarchické členění Internetu: každá brána zdá svoji podsíť, páteřní brány znají celý Internet
• koncepce autonomních systémů

Autonomní systémy

• cíl: snížení směrovací režie, zjednodušení správy sítě
• každý autonomní systém (doména) má ASN (Autonomous System Number) – 16bitové id, které přiřazuje ICANN a popisuje ho RFC 1930
• domény – např. CESNET, PASNET
• děleny podle způsobu připojení do sítě

Stub AS

• připojen pouze jednomu AS
• hraniční směrovač – výchozí pro všechny sítě ostatní sítě

Multihomed

• připojen minimálně ke 2 dalším AS, ale neumožňuje přenos mezi nimi

Transit AS

• připojen minimálně ke 2 dalším AS a umožňuje přenos mezi

Směrování v AS

• intradoménové směrování – směrování uvnitř domény (Interior Gateway Protocols (IGP) např. RIP, OSPF)
• interdoménové směrování – směrování mezi doménami (Exterior Gateway Protocols (EGP) např. EGP, BGP-4)
• vnitřní a vnější protokoly musí spolupracovat
• interní a hraniční směrovače
• jádro musí znát cesty ke všem sítím
• unvitř AS hraje hlavní roli výkon
• mezi AS hrají hlavní roli politiky (peníze) a škálovatelnost
• směrovací pravidla mohou zakazovat směrování přes nějaký AS v přídě výpadku

Protokol EGP (Exterior Routing Protocol)

• Distance Vector přístup
• cílem je dosažitelnost nikoli efektivita
• navržen pro stromovou strukturu Internetu
• nepoužívá se, nepodporuje redundanci a neumí pracovat s cykly

Protokol BGP (Border Gateway Protocol)

• Path Vector směrování – posílají se celé cesty (detekuje cykly, umožňuje definici pravidel), preferuje kratší cesty, řeší pouze dostupnost - AS nemusí mít stejnou metriku
• umožňuje definici pravidel směrování
• pracuje nad TCP
• používá CIDR pro agregaci cest

Multicastové směrování - IP Multicasting

• vysíláme stejnou zprávu skupině příjemců
• nutnost replikace dat
• unicast (ke každému příjemci putují data zvlášť) × multicast (data se po cestě dělí)
• stream videa, data produkovaná přístrojem, videokonference,…

IP Multicast

• každým spojem jde nanejvýš jedna kopie dat
• hop-by-hop
• doručení nezaručeno
• rozsah šíření je omezen TTL
• identifikace skupiny pomocí multicastové adresy
• výhody: škálovatelnost, nezatěžování sítě kopiemi
• nevýhody: problematické účtování, problém se zajištěním doručení, snadný terč útoku (DoS, DDoS), nelze zjistit přijímající, všichni dostávají identickou kopii

Source Based Tree

• aktivita shora od zakládajícího
• periodický broadcast (- slabá stránka)
• ořezávání větví bez členů
• omezení šířky TTL
• pro úzce lokalizované skupiny
• protokoly: DVMRP (RIP), MOSPF (OSPF), PIM-DM

Shared Tree (Core Based Tree)

• ustanovené jádro - body setkání (meeting points - MP)
• zájemce o skupinu kontaktuje MP
• aktivita zdola od příjemce
• redukce broadcastu -> lepší škálování
• závislost na dostupnosti jádra
• protokoly: CBT, PIM-SM (protokolově nezávislé)

Protokoly

Internet Group Management Protocol (IGMP)

• správa skupiny v rámci LAN
• IGMP (RFC 1112), IGMPv2 (RFC 2236)
• správa členství
• přihlášení ke skupině, odhlášení ze skupiny, monitoring skupiny

Distance Vector Multicast Routing Protocol (DVMRP)

• rozšíření unicastového DV směrování, využívá informací získaných RIP protokolem
• 3 přístupy pro budování stromu:
  • Reverse Path Forwarding (RPF)
  • Reverse Path Broadcasting (RPB)
  • Reverse Path Multicasting (RPM)

Multicast Open Shortest Path First (MOSPF)

• rozšíření unicastového OSPF protokolu
• uzly počítají strom cest z kořene, kterým je zdroj multicastového vysílání

Protocol Independent Multicast - Dense Mode (PIM-DM)

• použití v prostředí, kde je pravděpodobné, že většina směrovačů se bude účastnit multicastu
• využívá RPF přístup
• podobný DVMRP, ale nevyžaduje RIP

Core-Based Tree (CBT)

• zdroj je kořen budovaného stromu
• Rendezvous Router – bod setkání, zvolen pro každý region AS
• uzly v případu zájmu kontaktují bod setkání (strom se buduje od listů)

Protocol Independent Multicast { Sparse Mode (PIM-SM)

• použití v prostředí, kde je málo pravděpodobné, že většina směrovačů se bude účastnit multicastu
• podobný CBT, ale vytváří záložní Randezvous Pointy pro případ výpadků
• v případě potřeby přepne do strategie Source-based Tree