From 4d04187465fdeb3fb755b4d01ec640bbe0e36eb9 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Fri, 19 Jan 2001 20:30:08 +0000
Subject: Added paper for my talk about BIRD at SLT 2001.

---
 doc/slt2001/slt.tex | 275 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 275 insertions(+)
 create mode 100644 doc/slt2001/slt.tex

(limited to 'doc/slt2001/slt.tex')

diff --git a/doc/slt2001/slt.tex b/doc/slt2001/slt.tex
new file mode 100644
index 00000000..fb948586
--- /dev/null
+++ b/doc/slt2001/slt.tex
@@ -0,0 +1,275 @@
+\magnification=\magstep1
+\input epsf.tex
+\input mjmac.tex
+
+\language=\czech
+\chyph
+
+\hsize=160truemm	% A4 with 25mm margins
+\vsize=247truemm
+\parindent=2em
+\nopagenumbers
+
+\def\hdr#1{\medskip\leftline{\bf #1}\smallskip}
+\def\\{\hfil\break}
+\def\BIRD{{\sc Bird}}
+
+\def\inititemize{\vskip 1pt\begingroup
+\parskip=1pt plus 0.3pt minus 0.1pt
+\advance\leftskip by 3em
+\advance\rightskip by 3em
+\parindent=0pt
+}
+
+%%% �vod a historie projektu
+\hdr{Na po��tku bylo vejce aneb �vodem}
+
+\noindent Internet i UNIX jsou na sv�t� ji� p�kn�ch p�r p�tk�. Po��ta�e pracuj�c�
+pod nep�ebern�m mno�stv�m unixovsk�ch syst�m� od nepam�ti funguj� jako
+internetov� po�tovn� servery, name-servery a men�� routery. Skoro by se zd�lo, �e
+si tyto dva sv�ty u� nemaj� co nov�ho ��ci. V~posledn�ch letech ov�em
+v�razn� vzrostl v�kon b�n�ch PC-�ek a objevily se pro n� karty podporuj�c�
+nejr�zn�j�� s��ov� technologie, a~tak se tyto po��ta�e staly vhodn�mi
+kandid�ty i~pro funkci router�. Na~mnoha m�stech tak star�� PC-�ko
+s~voln� �i�iteln�m softwarem p�edstihlo sv�ho star��ho a dra���ho
+komer�n�ho sourozence. A�koliv podpora routingu, firewallingu a inteligentn�
+queue management v~j�drech t�chto~OS (a~zejm�na Linuxu) je ji� velice
+vysp�l�, je�t� ned�vno byly notn� zanedb�v�ny protokoly pro dynamick�
+routing, tradi�n� unixovskou koncepc� um�st�n� do~u�ivatelsk�ho prostoru
+v~podob� routovac�ch daemon�.
+
+Tento nedostatek se pokou�ela mezi jin�mi napravit tak� skupina nad�enc�
+na~pra�sk� Matematicko-fyzik�ln� fakult� UK, kter� se rozhodla jako sv�j
+studijn� projekt vytvo�it nov�ho routovac�ho daemona, kter� by se stal
+n���m v�c ne� jen d�stojn�m konkurentem komer�n�ch router� -- nejen
+kop�roval u� zn�m� �e�en�, ale tak� p�isp�l n���m nov�m; na~jedn� stran�
+b�t stabiln�m a efektivn�m programem pro praxi, na~stran� druh� ov�em
+i~laborato�� pro snadn� experimentov�n� s~nov�mi my�lenkami. A~tak se
+narodil projekt {\it BIRD Internet Routing Daemon} (zkr�cen� \BIRD\footnote{$^0$}{Projekt
+si samoz�ejm� vyslou�il nejr�zn�j�� p�ezd�vky -- od Pt��ete a� po~Pt�kovinu.}).
+
+P�vodn� pl�ny byly sm�l� a rozhodn�: Vytvo�it nejlep��ho routovac�ho
+daemona na sv�t�, kter� by fungoval na~v�ech platform�ch, vy�adoval
+minimum strojov�ho �asu a pam�ti, podporoval v�echny routovac� protokoly
+atd., zkr�tka sen, jak� m� b�t. P�esko�me nyn� dva roky v�voje\footnote{$^1$}{b�hem nich�
+z~n�kter�ch po�adavk� samoz�ejm� se�lo -- nap��klad logem projektu
+se nakonec nestal pt��ek nesouc� v~zob��ku sn�tku byliny �e�en� routa \dots}
+a pod�vejme se, co z~toho vze�lo.
+
+%%% Sv�t routingu
+%% v~ti�t�n� verzi p�esko��me
+
+%%% Co BIRD dok�e
+\hdr{Kdy� pt��ka lapaj�, p�kn� mu zp�vaj� aneb Feature list}
+
+\noindent \BIRD\ dostal od sv�ch sudi�ek do~v�nku mnoh� dary:
+
+\def\icirc{\raise0.2ex\hbox{$\circ$}} % Signs frequently used for \itemize
+
+\itemize\ibull
+\:Schopnost komunikovat protokoly IPv4 i IPv6.
+\:Podporu v�ech z�kladn�ch routovac�ch protokol�:
+  \itemize\icirc
+    \:RIPv2 (Routing Information Protocol, viz RFC 1723 a 2080)\\
+      Ur�en pro intern� routing, dnes v�znamu sp��e historick�ho.\\
+      Algoritmus: distance vector (Bellman-Ford).\\
+      Velmi pomal� konvergence, pou�itel� pouze pro mali�k� s�t�.
+    \:OSPFv2 (Open Shortest Path First, viz RFC 2328)\\
+      Ur�en pro intern� routing, v~sou�asn� dob� asi nejb�n�j��.\\
+      Algoritmus: link state (Dijkstra).\\
+      Rychl� konvergence, ale velice komplikovan�.\\
+      Zat�m podporujeme pouze pro IPv4.
+    \:BGP4 (Border Gateway Protocol, viz RFC 1771 a 2283)\\
+      Standardn� protokol pro extern� routing mezi AS.\\
+      Rychl� konvergence, mo�nost administrativn� filtrace.\\
+      Algoritmus: path vector (upraven� Bellman-Ford).
+  \endlist
+\:Propojov�n� protokol� a v�m�nu dat mezi nimi.
+\:Schopnost uplat�ovat routing policy -- ur�ovat, kter� routovac� informace
+  budou od~kter�ch protokol� p�ij�m�ny a do~kter�ch protokol� vys�l�ny.
+\:Snadnou konfiguraci a �dr�bu, ale o~tom a� pozd�ji.
+\:Modul�rn� architekturu umo��uj�c� snadn� dopl�ov�n� nov�ch protokol�,
+  filtr� i jednoduch� portov�n� na~dal�� syst�my. (Interface k~routovac�m
+  slu�b�m j�dra je bohu�el i mezi jednotliv�mi unixovsk�mi syst�my natolik
+  r�znorod�, �e dokonce i~Linux 2.0 a Linux 2.2 jsou naprogramov�ny jako dva
+  odli�n� porty.)
+\:A v~neposledn� �ad� kvalitn� dokumentaci jak u�ivatelskou, tak
+  program�torskou (to je v�tan� d�sledek byt� �koln�m projektem).
+\endlist
+
+%%% A jak to v�echno propojit
+\hdr{Sv�t z~pta�� perspektivy aneb Jak to v�echno d�t dohromady?}
+
+\noindent Hlavn�m probl�mem ov�em nen� ani tak v�echny tyto vymo�enosti naprogramovat
+a popropojovat, n�br� ud�lat to tak, aby z~toho nevznikl neudr�ovateln�
+a neefektivn� zmatek\footnote{$^2$}{N�dhern�m p��kladem je Mendel�v pes,
+jak ho kdysi nakreslil pan Kantorek.}. Z~toho se zrodil modul�rn� pohled
+na~sv�t routingu a n�sledn� i cel� modul�rn� architektura programu:
+
+\bigskip
+
+\centerline{\epsfxsize=0.9\hsize\epsfbox{../slides/obr5.eps}}
+
+\medskip
+
+Z�kladem pohledu na~Internet z~na�� \uv{pta�� perspektivy} je routovac�
+tabulka. Na~n� jsou p�ipojeny jednotliv� routovac� protokoly -- jak
+protokoly re�ln�, tak i n�kolik virtu�ln�ch, jako je nap��klad protokol
+Kernel zaji��uj�c� synchronizaci tabulky s~tabulkou j�dra nebo protokol
+Static generuj�c� podle sv� konfigurace statick� sm�rov�n�. Ka�d� z~protokol�
+pos�l� do~tabulky polo�ky pro v�echny routy, kter� se na~z�klad� sv�ch informac�
+o~topologii s�t� dozv�d�. Tabulka pro ka�dou s�� vyb�r� na z�klad� preferenc�
+jednotliv�ch protokol� a jejich metrik optim�ln� sm�r a ten oznamuje
+zp�t protokol�m. V~cest� ov�em v~obou sm�rech stoj� filtry, kter� mohou
+tok dat regulovat -- n�kter� polo�ky odm�tat, jin� upravovat (nap��klad
+jim p�enastavovat metriky �i tagy; to se dokonce vztahuje i~na
+atributy dopl�ovan� c�lov�m protokolem, proto�e nejprve c�lov� protokol
+nastav� implicitn� hodnoty sv�ch atribut�, pokud je ji� polo�ka neobsahovala,
+a teprve pak dojde k~filtrov�n�).
+
+Routovac�ch tabulek m��e dokonce existovat v�cero a pomoc� protokolu Pipe
+si mohou p�epos�lat vybran� polo�ky. T�m m��eme zajistit nap��klad
+routing z�visl� na~zdrojov� adrese �i vstupn�m interfacu: u~Linuxu 2.2
+�i nov�j��ho nakonfigurujeme j�dru v�ce routovac�ch tabulek a ka�dou
+z~nich p�ipoj�me na~jednu tabulku na�i.
+
+\hdr{Pta�� zp�v aneb User interface}
+%%% User interface: konfigurace, logging a filtry. Remote control.
+
+\noindent S�� se m�n� a s~n� se mus� m�nit i konfigurace s��ov�ch
+komponent. Ta se pozvolna stala tradi�n�m kamenem �razu v�t�iny router�.
+U~tohoto kamene se toti� sch�zej� dva odv�c� nep��tel�:
+snaha o~snadnost a flexibilitu konfigurace a snaha o~nep�etr�it�
+provoz s�t�. A~jednou slev� ten, podruh� onen -- auto�i n�kter�ch
+router� vsadili na~s�lu textov�ch konfigura�n�ch soubor� za~cenu
+toho, �e se po~ka�d� zm�n� konfigurace mus� router restartovat
+a po~n�jakou dobu neroutuje, jin� zase pod��dili non-stop provozu
+v�e ostatn� a stvo�ili konfigurov�n� nep�ebern�m mno�stv�m online
+p��kaz�, pomoc� nich� se n�kter� v�ci prov�d�j� snadno, jin�,
+na~kter� auto�i speci�ln� p��kaz nevymysleli, u� obt��n�ji a je�t� jin�
+vy�aduj� do~v�sledn�ho stavu dosp�t postupn�m proveden�m mnoha zm�n,
+co� m� obvykle za~d�sledek daleko del�� v�padek ne� jak� by byl vznikl
+reloadem cel�ho routeru.
+
+\BIRD\ se sna�� dos�hnout oboj�ho: pou��v� textov� konfigura�n� soubory,
+u�ivateli tak d�v� mo�nost vytv��et konfiguraci v�cem�n� libovoln�m
+zp�sobem -- a� ji� ru�n�m editov�n�m, interaktivn�mi programy �i
+automatick�m generov�n�m pomoc� script�. Po~zm�n� konfigurace je
+ov�em schopen si novou verzi souboru p�e��st, porovnat s~pr�v�
+pou��vanou konfigurac� a zm�n�m se za b�hu p��zp�sobit (pokud
+jsou zm�ny p��li� velk�, m��e to zp�sobit restart
+n�kter�ho z~protokol�, ale provoz t�ch, kter�ch se zm�na
+net�kala, to nijak neohroz�).
+
+Konfigurace ka�d�ho protokolu (l�pe �e�eno ka�d� jeho instance --
+protokoly mohou b�t spu�t�ny n�kolikr�t na~r�zn�ch rozhran�ch
+�i nad r�zn�mi tabulkami) vypad� p�ibli�n� takto:
+
+\verbatim{   protocol bgp TestBGP {               # instanci si m��eme nazvat
+      local as 65000;			# n� AS
+      neighbor 195.39.3.64 as 5588;	# sousedn� AS
+      export all;			# pos�lat budeme v�echno
+      import filter {                   # na vstupu n�kter� odm�tneme
+         if !(bgp_path ~ / ? 5588 ? /) then reject;
+         if net ~ [ 10.0.0.0/8+, 192.168.0.0/16+ ] then reject;
+         preference = 101;              # zbyl�m nastav�me preferenci
+         accept;                        # a p�ijmeme je
+      };
+   }}
+\noindent V�dy popisuje protokol, jeho parametry, p�ipojen� k~tabulk�m
+(v~na�em p��pad� pou��v�me tabulku implicitn�) a nastaven� vstupn�ch
+i~v�stupn�ch filtr�.
+
+Filtry jsou popisov�ny jednoduch�m procedur�ln�m programovac�m jazykem,
+kter� m� k~dispozici v�echny informace o~pr�v� zpracov�van� polo�ce, m��e
+se podle nich rozhodovat a libovoln� je m�nit. D�ky tomu je mo�n� jednodu�e
+zad�vat i velice slo�it� pravidla, definovat si podprogramy sd�len�
+filtry pat��c�mi k~v�ce protokol�m, i~po��tat metriky pro jeden protokol
+na z�klad� metrik protokol� ostatn�ch.
+
+V�tan�m pomocn�kem p�i odhalov�n� probl�m� v~s�t�ch je rovn� voliteln�
+logov�n� d�le�it�ch ud�lost� a trasov�n� �innosti protokol�: zde si je
+mo�no pro ka�d� protokol vy��dat prakticky cokoliv po��naje z�kladn�mi informacemi o~b�hu
+protokolu (p�ipojov�n� a odpojov�n� soused� apod.), p�es v�m�nu polo�ek
+mezi protokolem, filtry a jeho tabulkou, a kon�e detailn�m v�pisem v�ech
+p�ijat�ch i odeslan�ch paket�.
+
+Mimo to \BIRD\ disponuje \uv{d�lkov�m ovl�d�n�m} -- jednoduch�m p��kazov�m
+rozhran�m, p�es kter� se mohou p�ipojovat r�zn� klienti a vyd�vat jak
+n�kter� ��d�c� p��kazy (restarty protokol�, reload konfigurace, p�ep�n�n�
+trasov�n�, \dots), tak po�adavky na~vypisov�n� stavu routovac�ch tabulek
+a protokol�. U~t�chto p��kaz� je mo�no vyu��vat pln� s�ly filtrovac�ho
+jazyka, tak�e chceme-li nap��klad zn�t v�echny routy sm�rovan� pomoc�
+BGP na jednoho konkr�tn�ho souseda, sta�� polo�it dotaz typu
+
+\verbatim{   bird> show route where source=RTS_BGP && gw=62.168.0.1}
+
+\noindent a dozv�me se ihned v�e, co jsme pot�ebovali. Lad�n� filtr�
+nav�c usnadn� i~to, �e se m��eme zeptat na~obsah routovac� tabulky
+z~pohledu n�kter�ho z~b��c�ch protokol�.
+
+%%% BIRD uvnit�
+%\hdr{Pta�� anatomie}
+%% existuje progdoc
+
+%%% Netradicni pouziti
+\hdr{Cesty ta�n�ch pt�k� aneb Za hranicemi v�edn�ch dn�}
+
+\noindent Hotov� modul�rn� implementace routovac�ho daemona samoz�ejm�
+sv�d� i k~m�n� tradi�n�mu vyu�it�. Zde se fantazii meze nekladou, autory
+sam� b�hem v�voje napadly nap��klad tyto triky:
+
+\itemize\ibull
+\:{\I multirouter} -- \uv{schizofrenn�} za��zen� pracuj�c� na r�zn�ch
+  skupin�ch interfac� jako r�zn� routery ��d�c� se r�zn�mi pravidly,
+  le��c� t�eba i v~r�zn�ch autonomn�ch syst�mech. To je mo�no za��dit
+  pat�i�n�m nastaven�m j�dra a bu�to v�ce b��c�mi \BIRD{}y nebo dokonce
+  jedn�m pracuj�c�m s~n�kolika r�zn�mi routovac�mi tabulkami. Tak by
+  mohl nap��klad cel� pra�sk� NIX b�et na jedin�m routeru (pravda,
+  b�n� PC by na to nesta��lo), a p�esto by si ka�d� provider mohl s�m
+  ur�ovat a konfigurovat svou vlastn� routovac� politiku.
+\:{\I �ed� eminence} -- \BIRD\ by ani nemusel b�et p��mo na~stroji, kter�
+  pakety routuje, mohl by tak� hotov� routovac� tabulky diktovat
+  n�jak�mu dedikovan�mu routeru disponuj�c�m v�konn�j��m hardwarem,
+  a tak skloubit �pi�kovou propustnost \uv{velk�ho �eleza}
+  s~flexibilitou routeru be��c�ho pod unixovsk�m syst�mem.
+\:{\I inteligentn� mirror} -- aplikace se nemus� zastavovat u~routingu
+  jako takov�ho, mnohdy je mo�no informace z�skan� z~provozu routeru
+  vyu��vat k~dal��m ��el�m, nap��klad k~inteligentn�mu p�esm�rov�v�n�
+  klient� na~nejbli��� mirror va�eho archivu.
+\endlist
+
+%%% A co dal?
+\hdr{�as pt��at aneb Co d�l?}
+
+P�esto�e po~�sp�n�m obh�jen� projektu a prvn�ch n�kolika des�tk�ch
+spokojen�ch u�ivatel� (a samoz�ejm� i~p�r opraven�ch chyb�ch) nyn� v�voj
+sp��e stagnuje, auto�i ji� sp��daj� pl�ny do~budoucnosti, kter�
+by m�ly \BIRD{}ovi p�in�st mimo jin� tak� routov�n� multicast�, agregaci
+s��ov�ch prefix�, OSPFv3 pro IPv6, on-demand linky a porty na~dal�� syst�my.
+
+%%% Reference na n�s a ostatn� routery
+\hdr{Sn��ka odkaz� na z�v�r}
+
+\noindent {\sc Bird Team} pod veden�m RNDr. Libora Forsta ({\I forst@cuni.cz}) tvo�ili:
+$$\vbox{\halign{#\hfil & \quad \it # \hfil & \quad \it # \hfil\cr
+Ond�ej Filip&feela@ipex.cz&http:/$\!$/feela.ipex.cz/\cr
+Martin Mare�&mj@ucw.cz&http:/$\!$/atrey.karlin.mff.cuni.cz/\char126mj/\cr
+Pavel Machek&pavel@ucw.cz&http:/$\!$/atrey.karlin.mff.cuni.cz/\char126pavel/\cr}}$$
+Dom�c� str�nku projektu najdete na {\it http:/$\!$/bird.network.cz/,} odtamtud ji�
+vedou odkazy na~aktu�ln� verzi, online dokumentaci i mailing list
+u�ivatel�.
+V�echna zmi�ovan� RFC i mnoho dal��ch naleznete na {\it http:/$\!$/www.rfc-editor.org/},
+prvn� my�lenky o~vyu��v�n� ptactva v~Internetu sahaj� a� k~RFC~1149.
+\BIRD\ nen� na~sv�t� s�m, m� i~p��buzn�; mezi nimi za zm�nku stoj�
+daemoni {\sc GateD} ({\I http:/$\!$/www.gated.org/}), \hbox{\sc Zebra} ({\I http:/$\!$/www.zebra.org/})
+a {\sc Mrtd} ({\I http:/$\!$/www.mrtd.net/}).
+O~IPv6 se bohu�el zat�m jen p��e, na~jeho celointernetov� nasazen� se st�le
+�ek� a mezit�m p�ib�v� address-translator� a dal��ch zv�rstev. Snad jedin�
+v�t�� s�� pou��vaj�c� tento protokol je experiment�ln� virtu�ln� s�� 6-bone
+(viz {\it http:/$\!$/www.6bone.net/} a odkazy odtamtud).
+
+Dotazy a p�ipom�nky pos�lejte bu�to autorovi nebo cel�mu {\sc Bird Team}u na~adresu
+{\I bird@bird.network.cz}.
+
+\bye
-- 
cgit v1.2.3

