Ji°φ Peterka

Sta°φ ╪φmanΘ to m∞li jednoduchΘ - vÜechny cesty pr² tehdy vedly do ╪φma. Z°ejm∞ tedy tehdejÜφ silniΦnφ a dßlniΦnφ sφ¥ vykazovala Φist∞ hv∞zdicovitou topologii. DneÜnφ poΦφtaΦovΘ sφt∞ ovÜem takto idylicky nevypadajφ, a u₧ v∙bec ne celΘ soustavy vzßjemn∞ propojen²ch lokßlnφch a rozlehl²ch sφtφ. V²slednß topologie t∞chto spletit²ch konglomerßt∙ mnohdy p°ipomφnß spφÜe hodn∞ rafinovanΘ bludiÜt∞, ve kterΘm najφt cestu z jednΘ sφt∞ do druhΘ je znaΦn∞ netrivißlnφ.

OvÜem najφt cestu odn∞kud n∞kam je doslova ₧ivotnφ nezbytnostφ, majφ-li vzßjemn∞ propojenΘ sφt∞ fungovat tak, jak od nich jejich u₧ivatelΘ oΦekßvajφ. Jak by jinak vypadala nap°φklad takovß elektronickß poÜta, kdyby p°enosovß Φßst sφt∞ neum∞la najφt cestu od odesilatele k adresßtovi, a nebyla tudφ₧ schopna zajistit korektnφ doruΦenφ zprßvy?

Vlastnφ proces hledßnφ cesty z jednoho zadanΘho mφsta na jinΘ zadanΘ mφsto se oznaΦuje jako sm∞rovßnφ (anglicky: routing) - to proto, ₧e anglickΘ route znamenß cestu, resp. sm∞r. V²sledkem aplikace äsm∞rovacφho procesu" je pak bu∩ ·plnß informace o celΘ ätrase" a₧ k tou₧enΘmu cφli, nebo alespo≥ rozhodnutφ, kter²m sm∞rem poslat p°enßÜen² blok dat dßl, p°es dalÜφ p°estupnφ uzly, aby se poslΘze dostal a₧ ke svΘmu koneΦnΘmu cφli.

Proces sm∞rovßnφ je v₧dy zalo₧en na urΦitΘm algoritmu (sm∞rovacφm algoritmu), a v∞tÜinou takΘ vyu₧φvß znalosti topologie celΘ soustavy vzßjemn∞ propojen²ch sφtφ (Φi alespo≥ jejich Φßsti). V prvnφm p°iblφ₧enφ si lze p°edstavit, ₧e ka₧d² uzel mß k dispozici tabulky (tzv. sm∞rovacφ tabulky), ve kter²ch jsou obsa₧eny pot°ebnΘ podklady pro jeho rozhodovßnφ p°i sm∞rovßnφ. KonkrΘtnφ zp∙sob, jak²m tyto informace vyu₧ije, je ale zßvisl² na algoritmu sm∞rovßnφ, kter² se v danΘ soustav∞ vzßjem∞ propojen²ch sφtφ pou₧φvß.

Algoritmy sm∞rovßnφ, kterΘ se v praxi pou₧φvajφ, mohou b²t zalo₧eny na r∙zn²ch myÜlenkßch, p°φstupech i p°edpokladech. ExtrΘmnφm p°φpadem m∙₧e b²t algoritmus sm∞rovßnφ, oznaΦovan² p°φznaΦn∞ jako ämetoda horkΘ brambory" - je zalo₧en na tom, ₧e ka₧d² uzel se sna₧φ zbavit p°enßÜen²ch dat co nejrychleji, a tak je odeÜle tφm sm∞rem, kter² je momentßln∞ nejmΘn∞ zatφ₧en². Zcela jinΘ vlastnosti mß nap°φklad algoritmus tzv. zßplavovΘho sm∞rovßnφ, podle kterΘho jsou data souΦasn∞ rozesφlßna do vÜech mo₧n²ch sm∞r∙ - tφm sice vznikajφ ΦetnΘ duplikßty jedn∞ch a t²ch₧ dat, ale na druhΘ stran∞ tento algoritmus vykazuje maximßlnφ robustnost a dokß₧e doruΦit p°enßÜenß data i v situaci, kdy jednotlivΘ Φßsti sφt∞ nßhle p°estßvajφ b²t pr∙chodnΘ.

V b∞₧nΘ praxi se ale pou₧φvajφ spφÜe konzervativn∞jÜφ metody sm∞rovßnφ, kterΘ se sna₧φ vyu₧φvat informace o skuteΦnΘ topologii pon∞kud inteligentn∞ji. Nap°φklad tak, ₧e si ve sv²ch sm∞rovacφch tabulkßch pamatujφ kvantitativnφ ohodnocenφ (cenu) r∙zn²ch cest do r∙zn²ch uzl∙, a pak mezi nimi vybφrajφ tu nejlacin∞jÜφ. OvÜem co mß p°edstavovat ohodnocenφ, resp. cena n∞jakΘ cesty? Mß to b²t skuteΦnß äfinanΦnφ" cena, kterou n∞kdo platφ za p°enos dat? Nebo mß tato hypotetickß cena vychßzet spφÜe z p°enosovΘ rychlosti, a vyjad°ovat tak p°φmo Φi zprost°edkovan∞ schopnost danΘ cesty p°enßÜet data? Nebo mß b²t zalo₧ena na dob∞ kterou p°enos trvß, Φi na n∞Φem jeÜt∞ jinΘm?

ProblΘmem je i pr∙b∞₧nΘ udr₧ovßnφ obsahu sm∞rovacφch tabulek, neboli informacφ o skuteΦnΘ topologii sφt∞. Je to podstatnΘ hlavn∞ u on∞ch ächyt°ejÜφch" metod sm∞rovßnφ, kterΘ se sna₧φ rozumn∞ vyu₧φvat znalosti skuteΦnΘ topologie sφt∞, a takΘ reagovat na jejφ pr∙b∞₧nΘ zm∞ny. V praxi to m∙₧e vypadat nap°φklad tak, ₧e ka₧d² uzel pravideln∞ ävytrubuje do sv∞ta" informaci o tom, jakß je cena jeho spojenφ s nejbli₧Üφmi sousedy. Ostatnφ uzly pak tuto informaci vyu₧φvajφ k tomu, aby si pr∙b∞₧n∞ vypoΦφtßvaly cenu jednotliv²ch cest v sφti, a udr₧ovaly tak svΘ sm∞rovacφ tabulky v aktußlnφm stavu. Mß to ovÜem vÜechno mal² hßΦek - pokud se to neza°φdφ dostateΦn∞ Üikovn∞, pak takto pravideln∞ Üφ°en²ch aktualizaΦnφch informacφ bude straÜn∞ mnoho, a samy o sob∞ by mohly celou sφ¥ i zahltit. V praxi se tedy pou₧φvajφ r∙znß kompromisnφ °eÜenφ, ale o t∞ch snad a₧ n∞kdy p°φÜt∞.