Ji°φ Peterka

P°edstavte si skupinku lidφ (tedy nejmΘn∞ dva jedince) zav°en²ch v malΘ mφstnosti se Üpatnou akustikou. Tak Üpatnou, ₧e kdy₧ jeden mluvφ, slyÜφ to vÜichni, ale jakmile by zaΦalo mluvit vφce lidφ najednou, nikdo by u₧ niΦemu nerozum∞l.

Obdobnß situace nastßvß i u lokßlnφch poΦφtaΦov²ch sφtφ se sb∞rnicovou topologiφ (tedy nap°φklad u sφtφ typu Ethernet). Zde jsou vÜechny uzly napojeny na jedin² vφcebodov² spoj, a kdy₧ jeden uzel n∞co vysφlß, mohou jeho vysφlßnφ p°ijφmat vÜechny uzly souΦasn∞. Kdyby ovÜem zaΦalo najednou vysφlat vφce uzl∙, vÜichni by p°ijφmali jen jakousi dßle nerozliÜitelnou sm∞s.

V obou p°φpadech je tedy nutnΘ zavΘst a dodr₧ovat takovß pravidla Φi postupy, kterΘ zajistφ korektnφ zp∙sob komunikace - tedy takov², p°i kterΘm nebude mluvit vφce lidφ souΦasn∞, resp. souΦasn∞ vysφlat vφce uzl∙. V p°φpad∞ poΦφtaΦovΘ sφt∞ se t∞mto pravidl∙m °φkß p°φstupovß metoda (access method), jak jsme si ji₧ naznaΦili v minulΘm p°φsp∞vku tΘto rubriky.

JakΘ jsou principißlnφ mo₧nosti zajiÜt∞nφ korektnφho zp∙sobu komunikace ve v²Üe naznaΦenΘm smyslu? Uka₧me si to nejprve na p°φkladu skupinky lidφ: mezi nimi m∙₧e existovat jedna autoritativnφ osoba, kterou vÜichni ostatnφ respektujφ a kterß rozhoduje o tom, kdo bude mluvit. M∙₧e to d∞lat tak, ₧e se potencißlnφch zßjemc∙ postupn∞ dotazuje (zda majφ p°ipraveno n∞jakΘ sd∞lenφ, kterΘ by cht∞li p°ednΘst), nebo naopak Φekß na explicitnφ ₧ßdosti t∞ch, kte°φ cht∞jφ promluvit. V p°φpad∞ poΦφtaΦovΘ sφt∞ odpovφdß tato situace existenci uzlu, kter² vystupuje v roli arbitra a sßm rozhoduje o tom, kdo smφ vysφlat. Pokud se tento centrßlnφ arbitr sßm dotazuje ostatnφch uzl∙, jde o tzv. centrßlnφ p°id∞lovßnφ na zßklad∞ v²zvy. Alternativou je p°id∞lovßnφ na ₧ßdost, kdy arbitr Φekß, a₧ se mu ₧adatelΘ o prßvo vysφlat p°ihlßsφ sami.

Existence centrßlnφho arbitra je ovÜem v₧dy spojena s nebezpeΦφm jeho v²padku, kter² zanechßvß vÜechny ostatnφ v nezßvid∞nφhodnΘ situaci - sami se nedokß₧φ domluvit.

Jinß °eÜenφ existenci centrßlnφho arbitra nep°edpoklßdajφ a mφsto toho sßzφ na distribuovan² charakter rozhodovacφho mechanismu, tedy na schopnosti vÜech zßjemc∙ dohodnout se i bez existence rozhodΦφho. KonkrΘtnφ °eÜenφ m∙₧e b²t nap°φklad takovΘ (pou₧ijeme-li naÜe p°irovnßnφ ke skupince lidφ), ₧e mezi ·Φastnφky koluje "pr∙kazka mluvΦφho" a pouze jejφ dr₧itel je oprßvn∞n mluvit, zatφmco ostatnφ mohou pouze poslouchat. Pokud si ka₧d² dr₧itel ponechß pr∙kazku jen koneΦn∞ dlouhou dobu a je-li zajiÜt∞n spravedliv² "kolob∞h" p°edßvßnφ pr∙kazek, kter² nikoho nevynechß, je dokonce zaruΦeno, ₧e se ka₧d² dostane ke slovu. Dokonce to lze za°φdit i tak, ₧e nikdo nebude muset Φekat dΘle ne₧ urΦitou p°edem stanovenou dobu (k tomu staΦφ vhodn∞ omezit maximßlnφ dobu, po kterou si ka₧d² smφ pr∙kazku ponechat).

Vrßtφme-li se k poΦφtaΦov²m sφtφm, odpovφdß tato strategie distribuovanΘ p°φstupovΘ metod∞, kterß spadß do kategorie tzv. °φzen²ch metod. ╪φzen²ch proto, ₧e neobsahujφ ₧ßdn² prvek nßhodnosti a jejich aplikace v₧dy vede k p°edem odhadnutelnΘmu v²sledku. P°φkladem m∙₧e b²t p°φstupovß metoda, kterß se pou₧φvß v sφtφch Token Ring a Token Bus, kde "pr∙kazkou mluvΦφho" je tzv. token (do ΦeÜtiny p°eklßdan² obrazn∞ jako peÜek, s menÜφ mφrou p°edstavivosti jen jako oprßvn∞nφ). Token je ve skuteΦnosti zvlßÜtnφm druhem rßmce (paketu), kter² nenese ₧ßdnß data, ale oprav≥uje svΘho p°φjemce k nßslednΘmu vysφlßnφ.

Alternativou k °φzen²m metodßm jsou metody ne°φzenΘ, kterΘ v n∞jakΘ form∞ uplat≥ujφ nßhodn² prvek, a v d∙sledku toho nemusφ b²t jejich v²sledek predikovateln². Ne°φzenß p°φstupovß metoda obvykle nezaruΦuje, ₧e se zßjemce o vysφlßnφ skuteΦn∞ dostane ke slovu v koneΦnΘm Φase - mφsto toho zajiÜ¥uje ka₧dΘmu ₧adateli p°φstup v koneΦnΘm Φase jen s urΦitou pravd∞podobnostφ, kterß sice b²vß dosti vysokß, ale nenφ stoprocentnφ.

ProΦ se ale takovΘto ne°φzenΘ metody v∙bec pou₧φvajφ, kdy₧ mφsto jistoty nabφzφ jen urΦitou pravd∞podobnost? Jejich v²hodou oproti °φzen²m metodßm je v∞tÜφ jednoduchost, snazÜφ implementovatelnost, ale p°edevÜφm menÜφ re₧ie v situaci, kdy sφ¥ je mßlo zatφ₧ena (tj. kdy₧ po₧adavk∙ na vysφlßnφ je relativn∞ mßlo). Naopak p°i velkΘm zatφ₧enφ sφt∞ jsou ne°φzenΘ p°φstupovΘ metody mΘn∞ efektivnφ ne₧ metody °φzenΘ a obvykle neumo₧≥ujφ vyu₧φt teoretickou p°enosovou kapacitu sφt∞ na pln²ch 100 procent (ale nap°. jen na 60 a₧ 80 procent).

Nejznßm∞jÜφm p°φkladem ne°φzenΘ metody je p°φstupovß metoda sφtφ typu Ethernet (viz minulΘ vydßnφ tΘto rubriky). OznaΦuje se zkratkou CSMA/CD, kterß v sob∞ skr²vß t°i zßkladnφ principy, na kter²ch je zalo₧ena.

Prvnφ dv∞ pφsmena, CS, jsou od anglickΘho Carrier Sense (Φesky: p°φposlech, detekce nosnΘ). Znamenajφ to, ₧e kdy₧ n∞kter² uzel chce vysφlat, nejprve poslouchß, zda nevysφlß n∞kdo jin² - sna₧φ se detektovat signßl (tzv. nosnou) pochßzejφcφ od vysφlßnφ jinΘho uzlu.

Pokud uzel zjistφ, ₧e nikdo prßv∞ nevysφlß, m∙₧e zaΦφt vysφlat sßm. Sb∞rnicovß topologie, v jejφm₧ rßmci jsou vÜechny uzly p°φmo p°ipojeny na jedin² vφcebodov² spoj, to umo₧≥uje ka₧dΘmu a p°φmo. Je tedy mo₧n² tzv. vφcenßsobn² p°φstup (Multiple Access, odsud druhß dv∞ pφsmena, MA), kter² znamenß nejen souΦasnΘ fyzickΘ p°ipojenφ vφce uzl∙ na jedno spoleΦnΘ p°enosovΘ mΘdium, ale i mo₧nost souΦasnΘho p°φjmu vφce uzly, a dokonce i mo₧nost souΦasnΘho vysφlßnφ vφce uzly. TΘto poslednφ mo₧nosti je t°eba sprßvn∞ rozum∞t: je samoz°ejm∞ ne₧ßdoucφ, ale dφky technickΘmu °eÜenφ sφtφ typu Ethernet nezp∙sobφ souΦasnΘ vysφlßnφ vφce uzl∙ ₧ßdnou technickou zßvadu Φi poÜkozenφ p°enosovΘho mΘdia nebo v²stupnφch obvod∙ (tzv. budiΦ∙) jednotliv²ch uzl∙. Projevφ se vÜak zm∞nou parametr∙ elektrick²ch signßl∙ na p°enosovΘm mΘdiu, a tuto zm∞nu je mo₧nΘ jednoznaΦn∞ detektovat.

Dφky p°φposlechu (detekci nosnΘ) nedochßzφ k tomu, ₧e by jeden uzel zahßjil vysφlßnφ v dob∞, kdy₧ ji₧ n∞jakou dobu probφhß vysφlßnφ jinΘho uzlu (i kdy₧ technicky by mohl, dφky vφcenßsobnΘmu p°φstupu). M∙₧e vÜak dojφt k tomu, ₧e v tΘto dob∞ projevφ zßjem o vysφlßnφ vφce uzl∙. VÜechny sice spo°ßdan∞ poΦkajφ, a₧ prßv∞ probφhajφcφ vysφlßnφ skonΦφ, ale pak se doslova "utrhnou ze °et∞zu" a zaΦnou vysφlat vÜechny najednou. Pak dochßzφ k tzv. kolizi (collision), kterß je ale jednoznaΦn∞ rozpoznatelnß (viz v²Üe). Ka₧d² uzel, kter² zaΦal vysφlat, m∙₧e kolizi rozpoznat a z nφ si pak odvodit, ₧e nezaΦal vysφlat sßm. Dokonce je povinen to d∞lat, jak mu p°ikazujφ poslednφ dv∞ pφsmena v nßzvu p°φstupovΘ metody CSMA/CD - CD neboli Collision Detect (detekce kolizφ).

Zajφmavß je pak otßzka, jak se majφ zachovat z·Φastn∞nΘ uzly potΘ, co ke kolizi doÜlo.

Pravidlo je takovΘ, ₧e ka₧d² uzel, kter² detektuje kolizi, se na urΦitou dobu odmlΦφ, a teprve pak m∙₧e znovu usilovat o svΘ vysφlßnφ (tedy nejprve poslouchat, zda n∞kdo ji₧ nevysφlß atd.). Kdyby se ovÜem vÜechny uzly, z·Φastn∞nΘ na kolizi odmlΦely na stejn∞ dlouhou dobu, doÜlo by po uplynutφ tΘto doby ke kolizi novΘ. NejlepÜφ by bylo, kdyby se z·Φastn∞nΘ uzly vhodn∞ domluvily a ka₧d² si zvolil jinou dobu, na kterou by se odmlΦel. To vÜak nenφ mo₧nΘ za°φdit - jednotlivΘ uzly toti₧ nemajφ ₧ßdnou mo₧nost zjistit, kolik se jich v kolizi seÜlo, ani kterΘ uzly to jsou (mohou si odvodit pouze to, ₧e jsou nejmΘn∞ dva). Nemohou se tedy ₧ßdn²m zp∙sobem vzßjemn∞ zkoordinovat. Proto se prßv∞ v tΘto situaci uplat≥uje nßhodn² prvek a ka₧d² uzel si dΘlku svΘho odmlΦenφ volφ sßm a nezßvisle na ostatnφch jako nßhodnΘ Φφslo z urΦitΘho intervalu. Dφky tomu se v obecnΘm p°φpad∞ ka₧d² uzel odmlΦφ na r∙zn∞ dlouhou dobu a ten, kter² se "probere" jako prvnφ, v∞tÜinou ji₧ na kolizi nenarazφ. Nenφ to ale zaruΦenΘ a novou k olizi nelze vylouΦit.

Ka₧d² uzel, kter² se opakovan∞ dostane do kolize, si zdvojnßsobφ interval, ze kterΘho si nßhodn∞ volφ dΘlku svΘho odmlΦenφ. R∙zn²mi simulacemi se toti₧ ukßzalo, ₧e prßv∞ p°i takovΘmto postupu bude nßsledn²ch kolizφ nejmΘn∞. Op∞t ale nenφ zaruΦeno, ₧e se konkrΘtnφ uzel nebude neustßle dostßvat do kolizφ s jin²mi uzly, a tak se tento uzel vlastn∞ nikdy nedostane k vysφlßnφ (pravidla p°φstupovΘ metody CSMA/CD °φkajφ, ₧e po 16 ne·sp∞Ün²ch pokusech to mß "vzdßt"). I kdy₧ pravd∞podobnost tohoto p°φpadu je velmi malß, nenφ nulovß, a p°φstupovß metoda CSMA/CD prßv∞ z tohoto d∙vodu nenφ schopna zaruΦit p°φstup ke sb∞rnici (prßvo vysφlat) v koneΦnΘm Φase.

P°φstupovou metodu CSMA/CD lze tedy p°irovnat k sout∞₧i (v angliΦtin∞ se v tΘto souvislosti pou₧φvß termφn: contention), ve kterΘ neexistuje centrßlnφ rozhodΦφ, a v nφ₧ jednotlivφ ·Φastnφci p°φsn∞ dodr₧ujφ p°edem stanovenß pravidla. Tato pravidla jsou ve svΘ podstat∞ implementacφ distribuovanΘho algoritmu, a korektnost celΘ sout∞₧e je pak zajiÜt∞na korektnostφ tohoto algoritmu a disciplφnou jednotliv²ch ·Φastnφk∙, kte°φ pravidla skuteΦn∞ dodr₧ujφ.

Vzhledem k existenci nßhodnΘho prvku (nßhodn∞ volenΘ doby, na kterou se uzel po kolizi odmlΦφ) je p°φsluÜn² distribuovan² algoritmus nedeterministick². Z n∞j vychßzejφcφ sout∞₧ je pak korektnφ v tom smyslu, ₧e nem∙₧e mφt vφce ne₧ jednoho vφt∞ze, ale na druhΘ stran∞ nemusφ mφt takΘ vφt∞ze ₧ßdnΘho. Dφky tomu pak takΘ nenφ zaruΦeno, ₧e se ka₧d² zßjemce o vysφlßnφ dostane ke slovu v koneΦnΘm Φase. Pravd∞podobnost tΘto situace je velmi malß, ale nelze ji v principu vylouΦit. Zda to je, Φi nenφ na zßvadu, zßle₧φ hlavn∞ na konkrΘtnφm zp∙sobu vyu₧itφ lokßlnφ sφt∞. Kdyby nap°φklad m∞la sφ¥ s p°φstupovou metodou CSMA/CD slou₧it k °φzenφ jadernΘ elektrßrny, m∞l by tento jejφ nedostatek z°ejm∞ naprosto zßsadnφ v²znam. Kdy₧ je ale pou₧φvßna v b∞₧nΘm kancelß°skΘm prost°edφ, je tato jejφ vlastnost zcela nepodstatnß.