Ji°φ Peterka

Ko°eny Ethernetu je t°eba hledat v jednΘ velmi atraktivnφ Φßsti sv∞ta - na Havajsk²ch ostrovech. ZdejÜφ p°φrodnφ krßsa a existence mnoha mal²ch ostrov∙ vÜak velmi ztφ₧ila prßci t∞m, kte°φ dostali za ·kol vybudovat zde fungujφcφ poΦφtaΦovou sφ¥, kterß by tyto ostrovy propojovala. Mφsto nßroΦnΘho kladenφ podmo°sk²ch kabel∙ nakonec doÜlo na myÜlenku vyu₧φt p°enosy äΘterem", konkrΘtn∞ soustavou pozemnφch rßdiov²ch vysφlaΦ∙. Hlavnφm problΘmem, kter² zde bylo nutnΘ vy°eÜit, byla otßzka koordinace vysφlßnφ: kdo mß kdy zφskat prßvo vysφlat ädo Θteru"? Bude-li vysφlat vφce uzl∙ najednou, bude se jejich vysφlßnφ vzßjemn∞ ruÜit - tak₧e majφ se potencißlnφ zßjemci o vysφlßnφ mezi sebou n∞jak²m zp∙sobem koordinovat, a pokud ano, jak? Auto°i nakonec zvolili pon∞kud netradiΦnφ °eÜenφ: ka₧d² nech¥ vysφlß tehdy, kdy to pova₧uje za pot°ebnΘ (ve smyslu: a¥ se v∙bec neohlφ₧φ na ostatnφ). Takov²to zcela nekoordinovan² p°φstup samoz°ejm∞ m∙₧e vΘst ke kolizφm, kdy se v Θteru sejde vφce p°enos∙ a vzßjemn∞ se negativn∞ ovlivnφ - proto byl d∙raz polo₧en i na zp∞tnΘ potvrzovßnφ. Uzel, kter² odeslal n∞jakß data, si poΦkal na potvrzenφ o tom, ₧e jeho data doÜla v po°ßdku. Pokud takovΘto potvrzenφ v urΦitΘm p°edem stanovenΘm Φase nedoÜlo, vysφlßnφ opakoval. No a prßv∞ to jsou hlavnφ myÜlenky sφt∞, kterß dostala p°φznaΦnΘ jmΘno Aloha.

Koncepce sφt∞ Aloha se na prvnφ pohled m∙₧e zdßt pon∞kud zvlßÜtnφ a neefektivnφ. Na druhΘ stran∞ mß ale i svΘ p°ednosti (krom∞ toho, ₧e jinΘ °eÜenφ tehdy moc nep°ipadalo v ·vahu): je nap°φklad velmi jednoduchß na implementaci. P°i velmi malΘ zßt∞₧i (jednotky procent teoretickΘ vyu₧itelnosti äΘteru") je pak i docela efektivnφ - pravd∞podobnost kolizφ je zde velmi malß, a velmi p°φzniv∞ se naopak projevuje to, ₧e samotnß p°φstupovß metoda sφt∞ Aloha nevykazuje ₧ßdnou vlastnφ re₧ii (zßjemce o vysφlßnφ jednoduÜe zaΦne ihned vysφlat).

Jinak tomu ale bude v p°φpad∞ vyÜÜφ zßt∞₧e - jakmile intenzita po₧adavk∙ na p°enosy dosßhne urΦitΘ hladiny (a ta je äposazena" pom∞rn∞ nφzko, pod dvaceti procenty teoretickΘ vyu₧itelnosti), zaΦne se Aloha chovat nev²hodn∞ - roste poΦet kolizφ i nßsledn² poΦet opakovan²ch vysφlßnφ, a celkovß efektivnφ propustnost sφt∞ dokonce zaΦne klesat.

Metody CSMA

Jednφm z d∙le₧it²ch moment∙ celΘ koncepce sφt∞ Aloha bylo to, ₧e se jednotlivΘ uzly nesna₧φ monitorovat, zda prßv∞ neprobφhß n∞jakΘ vysφlßnφ (tak aby p°φpadn∞ äneskßkaly do °eΦi" jin²m uzl∙m). V reßlnΘ praxi takovßto mo₧nost m∙₧e, ale takΘ nemusφ existovat - nap°φklad u dru₧icov²ch p°enos∙, kde zpo₧d∞nφ mezi odeslßnφm a p°φjmem dosahuje hodnoty stovek milisekund, by snaha o äp°φposlech" byla zbyteΦnß - jednotlivΘ uzly by dostupnost Φi obsazenost p°enosovΘho kanßlu zjistily a₧ s p°φsloveΦn²m äk°φ₧kem po funuse", v dob∞ kdy u₧ faktickß situace bude ·pln∞ jinß. U nejr∙zn∞jÜφch äpozemnφch" p°enosov²ch cest vÜak p°enosovΘ zpo₧d∞nφ nenφ zdaleka tak velkΘ, a äp°φposlech" u nich p°ipadß v ·vahu. Samoz°ejm∞ ale zßle₧φ na tzv. p°φstupovΘ metod∞ (tj. metod∞, kterß reguluje p°φstup jednotliv²ch uzl∙ ke spoleΦn∞ sdφlenΘmu p°enosovΘmu mΘdiu), zda tuto mo₧nost vyu₧ije. P°φstupovß metoda Aloha ji nevyu₧φvala.

Existuje ovÜem celß Ükßla p°φstupov²ch metod, kterΘ mo₧nost äp°φposlechu" vyu₧φvajφ, a dosahujφ lepÜφch v²sledk∙ ne₧ jednoduÜÜφ metoda Aloha. Obecn∞ se takovΘto metody oznaΦujφ jako ämetody CSMA", kde CS znamenß prßv∞ Carrier Sense, neboli mo₧nost äp°φposlechu nosnΘ". DalÜφ dv∞ pφsmena, MA, od Multiple Access, pak vyjad°ujφ celkov² charakter p°enosovΘho mΘdia, kterΘ je sdφlenΘ a p°φstup k n∞mu majφ vÜechny uzly souΦasn∞ (a je tedy mo₧nΘ, by¥ ne₧ßdoucφ, i souΦasnΘ vysφlßnφ vφce uzl∙).

Zajφmavou otßzkou ale je, jak se u metod CSMA mß zachovat uzel, kter² dφky p°φposlechu nosnΘ zjistφ ₧e äΘter" je prßv∞ obsazen². Mo₧nostφ je n∞kolik - jednou z nich je ta, ₧e si zßjemce o vysφlßnφ poΦkß na skonΦenφ prßv∞ probφhajφcφho p°enosu, a ihned potΘ zaΦne vysφlat sßm. OvÜem s rizikem, ₧e v dob∞ kdy Φekß na konec probφhajφcφho p°enosu, pojme stejn² ·mysl i jin² uzel, resp. jinΘ uzly, a takΘ ony zaΦnou Φekat na konec - pak ovÜem s nejv∞tÜφ pravd∞podobnostφ dojde ke kolizi, bezprost°edn∞ po skonΦenφ prßv∞ probφhajφcφho p°enosu.

Alternativou je to, aby uzel, kter² detekuje prßv∞ probφhajφcφ vysφlßnφ, nebyl ve svΘm sna₧enφ a₧ tak moc vytrval² (Φi: nalΘhav², angl.: persistent), v tom smyslu aby vytrvale Φekal na konec vysφlßnφ a pak okam₧it∞ uplatnil sv∙j po₧adavek na p°enos. Mφsto toho p°φsluÜn² uzel m∙₧e i se sv²m po₧adavkem chvilku poseΦkat (odmlΦet se, na vhodn∞ zvolenou dobu), a pak postupovat znovu od zaΦßtku, tj. znovu zjiÜ¥ovat jestli je äΘter" voln² nebo nikoliv. Tφm se sice v²razn∞ omezφ poΦet kolizφ äsoub∞₧n²ch Φekatel∙", ale na druhΘ stran∞ se tφm nep°φjemn∞ prodlou₧φ pr∙m∞rnß doba, kterou zabere Φekßnφ jednotliv²ch uzl∙ na mo₧nost n∞co skuteΦn∞ odvysφlat. NaÜt∞stφ existujφ i r∙znΘ kompromisnφ metody, p°i kter²ch zßjemci o prßvo vysφlat v p°φpad∞ obsazenosti p°enosovΘho kanßlu s urΦitou pravd∞podobnostφ p vytrvajφ a poΦkajφ si na skonΦenφ prßv∞ probφhajφcφho p°enosu, a s opaΦnou pravd∞podobnostφ (tj. 1-p) to vzdajφ a odmlΦφ se (a pak zaΦφnajφ uplat≥ovat sv∙j po₧adavek od zaΦßtku).

Srovnßnφ variant metody CSMA s r∙znou "persistentnostφ"

O ₧ßdnΘ z krajnφch ani kompromisnφch variant nelze °φci, ₧e by byla jednoznaΦn∞ nejv²hodn∞jÜφ - ka₧dß mß v n∞Φem svΘ p°ednosti a v n∞Φem svΘ nev²hody. ZajφmavΘ je nap°φklad statistickΘ chovßnφ jednotliv²ch metod p°i rostoucφ zßt∞₧i, kterΘ ukazuje dneÜnφ obrßzek (Φφselnß hodnota v nßzvu metody zde odpovφdß hodnot∞ pravd∞podobnosti p ve smyslu p°edchozφho odstavce). Ani toto chovßnφ vÜak neposkytuje ucelen² obrßzek o praktickΘ v²hodnosti, proto₧e nap°φklad 0,01-persistentnφ metoda CSMA, kterß v tomto ohledu vychßzφ nejlΘpe, vykazuje zase ne·nosn∞ dlouhou pr∙m∞rnou dobu od vzniku po₧adavku do jeho uskuteΦn∞nφ.

Ethernet je 1-persistentnφ

Auto°i Ethernetu, inspirovanφ praktick²m ·sp∞chem sφt∞ Aloha, se z°ejm∞ rozhodovali mezi jednotliv²mi variantami metod CSMA, a nakonec zvolili 1-persistentnφ metodu CSMA. D∙vodem z°ejm∞ nebyla pouhß äv²t∞₧nost" metody p°i rostoucφ zßt∞₧i (kde prßv∞ 1-persistentnφ metoda vychßzφ dle obrßzku pom∞rn∞ Üpatn∞), ale jist∞ takΘ jejφ vlastnosti p°i menÜφ zßt∞₧i. Zde je naopak 1-persistentnφ metoda nejv²hodn∞jÜφ v tom, ₧e dφky svΘ vytrvalosti dßvß zßjemci o vysφlßnφ Üanci uplatnit sv∙j po₧adavek co mo₧nß nejd°φve. Pokud je toti₧ provoz v sφti relativn∞ mal², je Üance ₧e zßjemce o vysφlßnφ narazφ na prßv∞ probφhajφcφ p°enos takΘ pom∞rn∞ malß. A pokud se tak stane, je op∞t relativn∞ malß pravd∞podobnost, ₧e p°i jeho Φekßnφ na konec p°enosu dojde k soub∞hu s obdobn²m po₧adavkem jinΘho uzlu.

D∙le₧itΘ je znovu si zd∙raznit, ₧e celß tato strategie je zam∞°ena na ämalΘ" vytφ₧enφ Ethernetu (v °ßdu jednotek a₧ n∞kolika mßlo desφtek procent), a v takovΘto situaci je takΘ vcelku optimßlnφ. Jakmile ale zaΦne stoupat intenzita po₧adavk∙ jednotliv²ch uzl∙ na vysφlßnφ, zaΦne se mnohem markantn∞ji uplat≥ovat vliv negativnφch faktor∙ - zaΦne r∙st poΦet kolizφ, a objevuje se dokonce i nebezpeΦφ ä°et∞zov²ch" (zavleΦen²ch) kolizφ. Z dneÜnφho obrßzku je dokonce z°ejmΘ i to, ₧e p°i p°ekroΦenφ urΦitΘ limitnφ hodnoty (intenzity po₧adavk∙ na p°enos) vliv negativnφch vlastnostφ 1-persistentnφ metody CSMA p°eroste nad jejφmi klady, a s dalÜφm zvyÜovßnφm intenzity po₧adavk∙ se chovßnφ metody zaΦne dokonce zhorÜovat.

Varianta metody CSMA, pou₧itß v Ethernetu, se samoz°ejm∞ sna₧φ posunout zmφn∞n² äzlomov² bod" co mo₧nß nejdßle (resp. nejv²Üe). Vyu₧φvß k tomu i skuteΦnosti, ₧e krom∞ äp°φposlechu nosnΘ" je mo₧nΘ rozpoznat i jednotlivΘ kolize, a toho pak vyu₧φt k nasazenφ dalÜφch opat°enφ sni₧ujφcφch negativnφ d∙sledky kolizφ. VÜak takΘ tomu vd∞Φφ konkrΘtnφ varianta p°φstupovΘ metody Ethernetu za poslednφ dv∞ pφsmenka ve svΘm nßzvu: jde o metodu CSMA/CD, kde CD znamenß äCollision Detection" (detekce kolize).

OvÜem jak²m konkrΘtnφm zp∙sobem se mo₧nost detekce kolize v Ethernetu vyu₧φvß, si musφme nechat a₧ do p°φÜtφho dφlu.