VyÜlo v t²denφku: COMPUTERWORLD
╚φslo:23/92
RoΦnφk:1992
Rubrika/kategorie: Co je Φφm ... v poΦφtaΦov²ch sφtφch
Dφl:34
zp∞t do archivu Φlßnk∙ | rejst°φk | p°edchozφ dφl | nßsledujφcφ dφl

Ji°φ Peterka: Co je Φφm ... v poΦφtaΦov²ch sφtφch (34)

Sφ¥ovß vrstva - sm∞rovßnφ

Neexistuje-li v poΦφtaΦovΘ sφti p°φmΘ spojenφ mezi odesilatelem dat a jejich koncov²m p°φjemcem, je ·kolem sφ¥ovΘ vrstvy nalΘzt mezi nimi alespo≥ takovou cestu, kterß vede p°es n∞kterΘ jinΘ uzly sφt∞. Z p°edchozφch dφl∙ naÜeho serißlu ji₧ vφme, ₧e v p°φpad∞ tzv. virtußlnφch okruh∙ se takovßto cesta hledß jen jednou, a to na zaΦßtku komunikace obou koncov²ch ·Φastnφk∙ (v rßmci navazovßnφ spojenφ resp. z°izovßnφ virtußlnφho okruhu), zatφmco u tzv. datagramovΘ slu₧by se vhodnß cesta hledß pro ka₧d² jednotliv² paket (resp. datagram) poka₧dΘ znovu. Vφme ji₧ takΘ, ₧e problematika hledßnφ cest v sφti se obecn∞ oznaΦuje jako sm∞rovßnφ (routing). Co vÜak jeÜt∞ nevφme, je jak se takovß cesta vlastn∞ hledß.

Pro nalezenφ vhodnΘ cesty od odesilatele a₧ ke koncovΘmu p°φjemci existuje celß °ada algoritm∙ sm∞rovßnφ (routing algorithms), kterΘ jsou zalo₧eny na r∙zn²ch myÜlenkßch a principech, a vy₧adujφ r∙znΘ stupn∞ znalosti sφt∞, jejφ topologie a dalÜφch parametr∙ statickΘho i dynamickΘho charakteru. VÜechny algoritmy sm∞rovßnφ by ovÜem m∞ly b²t korektnφ, tedy dßvat jen takovΘ v²sledky, kterΘ jsou sprßvnΘ a pou₧itelnΘ, m∞ly by b²t co mo₧nß nejjednoduÜÜφ, nejsnßze implementovatelnΘ, a jejich re₧ie by m∞la b²t minimßlnφ. SouΦasn∞ s tφm by ale algoritmy sm∞rovßnφ m∞ly b²t i tzv. robustnφ, tedy schopnΘ vyrovnat se s nep°edvφdan²mi v²padky, poruchami Φi jin²mi nestandardnφmi situacemi. M∞ly by takΘ usilovat o optimßlnφ vyu₧itφ celΘ sφt∞ a jejφ p°enosovΘ kapacity, a p°itom nikoho nediskriminovat - tedy n∞komu hledat "lepÜφ" cesty, a n∞komu "horÜφ".

V²sledn²m efektem aplikace algoritm∙ sm∞rovßnφ by m∞lo b²t to, aby sφ¥ovß vrstva v ka₧dΘm z uzl∙ sφt∞ v∞d∞la, kudy poslat dßle takov² paket, kter² nenφ urΦen p°φmo jejφmu uzlu. KonkrΘtnφ pokyny pro sm∞rovßnφ paket∙ resp. datagram∙, kterΘ vznikajφ na zßklad∞ aplikace algoritm∙ sm∞rovßnφ, se pak v jednotliv²ch uzlech uchovßvajφ ve form∞ tzv. sm∞rovacφch tabulek (routing tables).

Adaptivnφ a neadaptivnφ sm∞rovßnφ

V prvnφm p°iblφ₧enφ si m∙₧eme rozd∞lit algoritmy sm∞rovßnφ na dv∞ velkΘ skupiny. Do prvnφ z nich budou pat°it takovΘ, kterΘ se sna₧φ pr∙b∞₧n∞ reagovat na skuteΦn² stav sφt∞, a brßt jej do ·vahy p°i svΘm hledßnφ nejvhodn∞jÜφ cesty. Dokß₧φ se tedy p°izp∙sobit okam₧itΘmu stavu sφt∞, a proto se obecn∞ oznaΦujφ jako adaptivnφ algoritmy (adaptive algorithms). Naproti tomu neadaptivnφ algoritmy (nonadaptive algorithms) nevyu₧φvajφ ₧ßdnΘ informace dynamickΘho charakteru - nap°. ·daje o okam₧itΘm zatφ₧enφ jednotliv²ch p°enosov²ch cest, v²padcφch, dΘlkßch Φekacφch front v jednotliv²ch uzlech apod. Svß rozhodnutφ stavφ pouze na informacφch statickΘho charakteru, kterΘ jsou p°edem znßmy. Dφky tomu lze neadaptivnφ algoritmy pou₧φt k nalezenφ vÜech pot°ebn²ch cest jeÜt∞ p°ed uvedenφm sφt∞ do provozu, a pot°ebnΘ informace pak jednorßzov∞ zanΘst do sm∞rovacφch tabulek jednotliv²ch uzl∙ sφt∞. Kv∙li statickΘmu charakteru v²chozφch ·daj∙ se pou₧itφ neadaptivnφch algoritm∙ n∞kdy oznaΦuje takΘ jako tzv. statickΘ sm∞rovßnφ (static routing). Je vhodnΘ tam, kde topologie sφt∞ je skuteΦn∞ nem∞nnß, kde prakticky nedochßzφ k v²padk∙m a kde se p°φliÜ nem∞nφ ani intenzita provozu resp. zßt∞₧ sφt∞.

CentralizovanΘ sm∞rovßnφ

Adaptivnφ algoritmus m∙₧e b²t koncipovßn tak, ₧e veÜkerΘ informace o aktußlnφm stavu celΘ sφt∞ se pr∙b∞₧n∞ shroma₧∩ujφ v jedinΘm centrßlnφm bod∞, tzv. sm∞rovacφm centru (RCC, Routing Control Center), kterΘ pak na jejich zßklad∞ samo p°ijφmß vÜechna pot°ebnß rozhodnutφ, a ostatnφm uzl∙m je oznamuje. Pak jde o tzv. centralizovanΘ sm∞rovßnφ (centralized routing). Jeho v²hodou je mo₧nost optimßlnφho rozhodovßnφ na zßklad∞ znalosti skuteΦnΘho stavu celΘ sφt∞. ProblΘm je ovÜem v tom, ₧e mß-li b²t centralizovanΘ sm∞rovßnφ opravdu adaptivnφ, tedy mß-li pr∙b∞₧n∞ reagovat na aktußlnφ stav sφt∞, musφ b²t vyhledßvßnφ nejvhodn∞jÜφch cest provßd∞no dostateΦn∞ Φasto. Vlastnφ hledßnφ cest je samo o sob∞ operacφ znaΦn∞ nßroΦnou na v²poΦetnφ kapacitu, a mß-li se Φasto opakovat, dokß₧e pln∞ zam∞stnat i velmi v²konn² poΦφtaΦ. Jsou zde vÜak jeÜt∞ i dalÜφ problΘmy - co nap°φklad d∞lat v p°φpad∞ v²padku sm∞rovacφho centra? Nezanedbatelnß nenφ ani zßt∞₧ p°enosov²ch cest, kterou p°edstavuje neustßl² p°φsun aktußlnφch informacφ o stavu sφt∞ do sm∞rovacφho centra, stejn∞ tak jako zp∞tnß distribuce v²sledk∙.

IzolovanΘ sm∞rovßnφ

Alternativou k centralizovanΘmu sm∞rovßnφ je tzv. izolovanΘ sm∞rovßnφ (isolated routing), zalo₧enΘ na myÜlence, ₧e rozhodovat o nejvhodn∞jÜφ cest∞ si bude ka₧d² uzel sßm za sebe, a to na zßklad∞ takov²ch informacφ, kterΘ dokß₧e zφskat sßm, bez spoluprßce s ostatnφmi uzly. Jednou z mo₧nostφ realizace je algoritmus, nazvan² p°φznaΦn∞ algoritmem horkΘ brambory (hot potato algorithm). Jak jeho nßzev dßvß tuÜit, sna₧φ se uzel zbavit ka₧dΘho paketu resp. datagramu co mo₧nß nejrychleji. Sleduje proto poΦet paket∙, kterΘ Φekajφ ve front∞ na odeslßnφ jednotliv²mi sm∞ry, a nov² paket za°adφ do tΘ fronty, kterß je momentßln∞ nejkratÜφ. Uzel se tedy nerozhoduje podle adresy, ani nehledß nejkratÜφ cestu pro p°enos paketu, pouze se jej sna₧φ co nejrychleji zbavit ve vφ°e, ₧e po jistΘ dob∞ p°eci jen dojde ke svΘmu cφli. V praxi se ovÜem algoritmus horkΘ brambory spφÜe kombinuje s jin²mi algoritmy resp. metodami - nejΦast∞ji je pou₧φvßn jako jejich dopln∞k, kter² se uplatnφ a₧ v okam₧iku, kdy poΦet paket∙ v n∞kterΘ front∞ p°ekroΦφ urΦitou ·nosnou mez.

Zp∞tnΘ uΦenφ

Jin²m p°φkladem izolovanΘho sm∞rovßnφ je tzv. metoda zp∞tnΘho uΦenφ (backward learning). P°edpoklßdß, ₧e ka₧d² uzel si do sv²ch sm∞rovacφch tabulek pr∙b∞₧n∞ poznamenßvß, ze kterΘho sm∞ru dostßvß pakety, pochßzejφcφ od jin²ch uzl∙. Tφm se postupn∞ "uΦφ", ve kterΘm sm∞ru se tyto uzly nalΘzajφ. Kdy₧ pak sßm pot°ebuje odeslat n∞jak² paket jinΘmu uzlu, vyÜle jej tφm sm∞rem, ze kterΘho d°φve p°ijal paket, pochßzejφcφ od tΘho₧ uzlu.

ProblΘmem je ovÜem vrozen² optimismus metody zp∞tnΘho uΦenφ. Dojde-li k v²padku urΦitΘ p°enosovΘ cesty, kterou se jednotlivΘ uzly ji₧ "nauΦily", v∙bec ji nezaznamenajφ. Prakticky jedin²m mo₧n²m °eÜenφm je pak pravidelnΘ "zapomφnßnφ".

ZßplavovΘ sm∞rovßnφ

ExtrΘmnφ formou izolovanΘho sm∞rovßnφ je tzv. zßplavovΘ sm∞rovßnφ (flooding). P°edpoklßdß, ₧e p°ijat² paket je znovu odeslßn vÜemi sm∞ry krom∞ toho, odkud sßm p°iÜel.

Z°ejmou v²hodou je maximßlnφ robustnost, dφky kterΘ se zßplavovΘ sm∞rovßnφ dokß₧e vyrovnat prakticky s jak²mkoli v²padkem. ZaruΦuje takΘ, ₧e ka₧d² paket je v₧dy doruΦen tou nejkratÜφ mo₧nou cestou. Nev²hodou je ale vznik velkΘho mno₧stvφ duplicitnφch paket∙, kterΘ v²razn∞ zvyÜujφ zßt∞₧ existujφcφch p°enosov²ch cest, a kterΘ je t°eba nßsledn∞ ruÜit.

V praxi se proto pou₧φvß spφÜe tzv. selektivnφ zßplavovΘ sm∞rovßnφ (selective flooding), p°i kterΘm nenφ ka₧d² paket znovu vysφlßn vÜemi sm∞ry, ale pouze t∞mi, kterΘ jsou alespo≥ p°ibli₧n∞ orientovßny ke koneΦnΘmu p°φjemci paketu.

DistribuovanΘ sm∞rovßnφ

Metody izolovanΘho sm∞rovßnφ stavφ na p°edpokladu, ₧e jednotlivΘ uzly nebudou zat∞₧ovat p°enosovΘ cesty vzßjemnou v²m∞nou informacφ o stavu sφt∞. To je ale n∞kdy zbyteΦn∞ p°φsn²m omezenφm.

Pokud jej odstranφme, dostaneme tzv. distribuovanΘ sm∞rovßnφ (distributed routing). To p°edpoklßdß, ₧e jednotlivΘ uzly si pravideln∞ vym∞≥ujφ informace o stavu sφt∞, a podle nich si pak samy volφ p°φsluÜnΘ cesty.

Jakmile umo₧nφme v²m∞nu stavov²ch informacφ mezi jednotliv²mi uzly sφt∞, m∙₧eme vcelku efektivn∞ implementovat distribuovanou verzi algoritmu hledßnφ nejkratÜφch cest v sφti, kter² bychom z°ejm∞ pou₧φvali v p°φpad∞ centralizovanΘho sm∞rovßnφ a jedinΘho sm∞rovacφho centra. NaznaΦme si nynφ myÜlenku tohoto distribuovanΘho algoritmu.

Nejprve si vÜak musφme ujasnit, co vlastn∞ bude pro nßs m∞°φtkem "dΘlky" n∞jakΘ cesty. M∙₧e to b²t nap°φklad poΦet meziuzl∙, kter²mi cesta prochßzφ. Tφm vÜak dßvßme ka₧dΘmu existujφcφmu spoji mezi dv∞ma uzly stejnou jednotkovou vßhu resp. dΘlku. RealistiΦt∞jÜφ je p°i°adit vhodnΘ ohodnocenφ (dΘlku) ka₧dΘmu p°φmΘmu spoji mezi dv∞ma uzly, a dΘlku v²slednΘ cesty pak chßpat jako souΦet dΘlek jejφch jednotliv²ch Φßstφ. DΘlka spoje p°itom m∙₧e odrß₧et jeho p°enosovou rychlost, cenu za jednotku p°enesen²ch dat, zpo₧d∞nφ p°i p°enosu, dΘlku v²stupnφch front apod.

P°edstavme si nynφ sφ¥ dle obrßzku 34.1. a/, vΦetn∞ "dΘlek" jednotliv²ch p°φm²ch spoj∙. Ka₧d² uzel p°edem znß svou "vzdßlenost" od vÜech sv²ch soused∙, a tak si ji ve svΘ sm∞rovacφ tabulce vyznaΦφ. Svou vzdßlenost (dΘlku nejkratÜφ cesty) od ostatnφch uzl∙ vÜak jeÜt∞ neznß, a tak ji zatφm pova₧uje za nekoneΦnou (na obrßzku naznaΦeno vyÜrafovßnφm). PoΦßteΦnφ stav tabulek ukazuje obrßzek 34.1. b/.

Vlastnφ algoritmus distribuovanΘho v²poΦtu pak probφhß v opakujφcφch se krocφch. V ka₧dΘm z nich se ka₧d² uzel dotß₧e sv²ch bezprost°ednφch soused∙, jakΘ jsou jejich vzdßlenosti od ostatnφch uzl∙, a podle toho si pak odvozuje i svΘ vlastnφ vzdßlenosti od t∞chto uzl∙.

Uva₧me p°φklad uzlu E. Ten se v prvnφm kroku od svΘho souseda C dozvφ, ₧e jeho vzdßlenost od uzlu B je 2. K nφ si uzel E p°ipoΦte svou vzdßlenost od uzlu C, tj. 1, a do svΘ sm∞rovacφ tabulky si poznaΦφ, ₧e cesta do uzlu B vede p°es uzel C a mß dΘlku 3. Zatφm vÜak neznß vÜechny mo₧nΘ cesty do uzlu B, a tak nevφ, zda je to cesta nejkratÜφ. Proto se bude v dalÜφch krocφch znovu ptßt vÜech sv²ch soused∙, zde p°es n∞ nevede cesta jeÜt∞ kratÜφ.

Obecn∞ si ka₧d² uzel v₧dy volφ minimum z toho, co "ji₧ umφ" on sßm (tj. z cesty, kterou ji₧ mß poznaΦenu ve svΘ sm∞rovacφ tabulce), a co "umφ" jeho sousedΘ (samoz°ejm∞ s uvß₧enφm svΘ vzdßlenostφ od t∞chto soused∙). P°φkladem m∙₧e b²t op∞t uzel E, kter² si ji₧ na poΦßtku do svΘ sm∞rovacφ tabulky zanese, ₧e jeho vzdßlenost od uzlu D je 5 (co₧ je dΘlka jejich p°φmΘho spojenφ, viz obr. 34.1 a/). Ji₧ v prvnφm kroku vÜak od svΘho souseda C zjistφ, ₧e jeho vzdßlenost od uzlu D je jen 2. Kdy₧ si k tomu p°ipoΦφtß svou vzdßlenost od uzlu C (tj. 1), vyjde mu, ₧e cesta do uzlu D, vedenß p°es uzel C, je kratÜφ. Tuto skuteΦnost si pak poznaΦφ do svΘ sm∞rovacφ tabulky (viz obrßzek 43.1 b/ a c/, tabulka uzlu E, polo₧ka D).

Obrßzek 34.1.Obrßzek 34.2.
Obr. 34.1.: P°edstava distribuovanΘho v²poΦtu sm∞rovacφch tabulek
a/ topologie sφt∞ a dΘlky spoj∙
b/ poΦßteΦnφ stav sm∞rovacφch tabulek
c/ stav sm∞rovacφch tabulek po prvnφm kroku
d/ "ustßlen²" stav sm∞rovacφch tabulek
Na obrßzku 34.1. d/ je pak stav tabulek po n∞kolika krocφch distribuovanΘho algoritmu, kdy ji₧ nedochßzφ k ₧ßdn²m zm∞nßm ve sm∞rovacφch tabulkßch. Zde by algoritmus mohl konΦit, v praxi se vÜak budou jeho kroky neustßle opakovat, aby obsah sm∞rovacφch tabulek mohl reagovat na pr∙b∞₧nΘ zm∞ny v sφti.

Prßv∞ naznaΦen² algoritmus distribuovanΘho sm∞rovßnφ byl pou₧φvßn v sφti ARPA (zßkladu dneÜnφ sφt∞ Internet), a jednotlivΘ kroky algoritmu zde probφhaly s intervalem 640 milisekund. Ukßzalo se vÜak, ₧e re₧ie je p°eci jen p°φliÜ vysokß - ₧e vzßjemnΘ p°edßvßnφ informacφ mezi sousednφmi uzly (kterΘ vlastn∞ p°edstavuje p°edßvßnφ cel²ch sm∞rovacφch tabulek) ne·nosn∞ zat∞₧ovalo dostupnΘ p°enosovΘ cesty na ·kor "u₧iteΦn²ch" dat. Proto byl uveden² algoritmus distribuovanΘho sm∞rovßnφ v sφti ARPA nahrazen jin²m - o n∞m si ale budeme povφdat pozd∞ji.

zp∞t do archivu Φlßnk∙ | rejst°φk | p°edchozφ dφl | nßsledujφcφ dφl
Tento Φlßnek m∙₧e b²t voln∞ Üφ°en, pokud se tak d∞je pro studijnφ ·Φely, na nev²d∞leΦnΘm zßklad∞ a se zachovßnφm tohoto dov∞tku. Podrobnosti hledejte zde, resp. na adrese http://archiv.czech.net/copyleft.htm