Sdílení přístupu ke společnému kanálu

Deterministické vs. nedeterministrické metody sdílení přístupu

• zpoždění při nízké zátěži
• efektivita využití kanálu při vysoké zátěži

Metody náhodného přístupu ke sdílenému kanálu

Aloha

• původně na rádiové síti univerzity na Havajských ostrovech
• netestuje se obsazenost média
• dodnes použití pro rádiové a družicové sítě, kde velké zpoždění signálu nebo konstrukce anténních obvodů zamezují příposlechu vlastního vysílání

1) Prostá aloha

• stanice vysílají bez ohledu na cokoliv
• časový limit pro potvrzení, při vypršení náhodné pozdržení (aby nedošlo k synchronizaci a opakované kolizi) a opakování pokusu.

• udává, kolik času se nejvýše ztratí na nevyužití kanálu vlivem kolize
• dvojnásobek t0, protože rámec bude zarušen koncem jiného rámce, pokud ten začne v předchozím timeslotu, nebo začátkem rámce, pokud začne v aktuálním timeslotu

Poznámky:

• maximální využití kapacity kanálu 18.4% [G=1/2, S=1/2e=0.184],
• rámec opakován průměrně 3x.
• pokles průchodnosti pro rostoucí celkový tok

2) Taktovaná aloha (slotted aloha)

• vysílat se smí začít jen v okamžicích začátků časových úseků pro odeslání jednoho rámce
• kolizní slot je poloviční, efektivita dvojnásobná (37%)
  

• exponenciální závislost, malý vzrůst zátěže může významně zvýšit počet opakování a snížit průchodnost kanálu
• při překročení určité mezní zátěže: zablokovaný stav, pravděpodobnost přenosu nepoškozeného rámce klesá k  nule => nezbytná explicitní modifikace parametrů sítě (řízení)

3) Řízená aloha

• řízená změna intenzity opakování podle okamžitého zatížení sítě
  (vyšší intenzita opakování => rychlejší předání rámce, při blížícími se zablokování se však intenzita sníží)
• Změna intenzity opakování heuristická, obvykle backoff (ustupování), intenzita klesá s počtem neúspěšných pokusů.
• Příklad:
  Ethernet: exponential backoff, prodloužení střední doby prodlevy po každém pokusu na dvojnásobek.
  
  
• Případně sledování provozu na kanále (poměru neobsazených slotů) a nastavování intenzity, aby celková zátěž kanálu nepřesáhla G=1
  

Carrier Sense Multiple Access (CSMA)

• dokonalá slyšitelnost stanic
• malé zpoždění signálu

1) Naléhající CSMA (1-persistant CSMA)

• před odesláním rámce se testuje stav kanálu
• je-li kanál obsazen, odloží se vysílání na okamžik jeho uvolnění
• riziko kolize stanic čekajících na uvolnění kanálu
• při kolizi čekání náhodnou dobu před dalším pokusem
  

2) Nenaléhající CSMA (non-persistant CSMA)

• při detekci obsazeného kanálu se počká náhodnou dobu, pak opět test obsazení.
• čekací doba se obvykle volí jako k-násobek doby průchodu signálu sdíleným médiem
  

3) p-naléhající CSMA (p-persistant CSMA)

• při potřebě vysílání se počká na okamžik uvolnění kanálu (nebo byl volný okamžitě)
• s pravděpodobností p začne vysílat, s pravděpodobností (1-p) se počká 1 timeslot a opakuje se do úspěšného odeslání rámce
• pokud mezitím začala vysílat jiná stanice, počká se náhodnou dobu (jako při kolizi)
• volbou p lze nastavit optimální využití kanálu pro danou zátěž
• pro p=1 jde o naléhající CSMA
• pro velmi malá p značně narůstá průměrná doba doručení paketu
  

4) CSMA/CD (CSMA with Collision Detection)

• před vysíláním musí být na médiu klid po dobu kolizního slotu
• jinak postup odpovídá naléhající CSMA
• okamžité ukončení vysílání po detekci kolize - kanál se zbytečně nezaplňuje rámcem, který je stejně zkolidován
• závislost maximální délky segmentu na rychlosti šíření signálu; vztah s dobou vysílání rámce a minimální délkou rámce

• dvojnásobek doby šíření signálu mezi nejvzdálenějšími stanicemi  (2t):
• stanice A začne vysílat, po době t (těsně před přijetím signálu od A) začne vysílat B, A zjistí kolizi až po dalším t, dohromady 2t

• kanál se dá modelovat jako taktovaná aloha s délkou kolizního intervalu 2t
• problém v případě dlouhých dob šíření a krátkých rámců => stanovuje se minimální délka rámce

• Při detekci kolize stanice vysílá kolizní signál (jam), aby kolizi rozpoznaly všechny kolidující stanice
  => uvolnění media do doby trvání jam posloupnosti + 2t
• O opakování se stanice po kolizi pokusí až po náhodné časové prodlevě, stabilitu metody nutno zajistit řízením intenzity opakování.
• Prodleva po kolizi určena algoritmem Binary exponential backoff:
• Po kolizi čas rozdělen do slotů 2*t, pro nejdelší délku (2,5 km + 4 repeatery) je slot 51.2 usec, tj. 512 bitových intervalů
• Po k-té kolizi se čeká náhodný počet slotů z intervalu <0 , 2^k-1) (max. 1023), po 16 pokusech se to vzdá.
  

Metody sdílení s omezenými kolizemi (pro informaci, užívané zřídka)

Deterministický přístup ke sdílenému kanálu

• Centralizované řízení
• Distribuované řízení
  

Centralizované řízení

• jedna stanice vyhrazena jako řídící (master), ta přiděluje kapacitu kanálu ostatním (podřízeným) stanicím.
• výhodou efektivita, ale nutnost obětovat část kapacity kanálu pro komunikaci s masterem.
• závislost sítě na řídící stanici.

Centralizované řízení - přidělování na výzvu

Centralizované řízení - přidělování na výzvu - cyklická výzva

• vyzývaná stanice buď vyšle rámec, nebo odmítne výzvu, příp. neodpoví
• použitelné pro malé zpoždění na kanále.
• rozumné pro vysoké využití kanálu většinou stanic, pro malé zatížení a velký počet stanic neefektivní
  

Centralizované řízení - přidělování na výzvu - binární vyhledávání

• Stanice se zorganizují do stromu podle jednotlivých bitů adres.
• Řídící stanice postupně vyzývá skupiny stanic, aktivní stanicee vyzvané skupině odpoví signálem na sdíleném kanále.
• Pokud stanice zjistí, že je jediná, která odpovídá, může začít vysílat; jinak se výzva posune o jednu úroveň dolů ve stromu.
• Podmínkou je kanál, u kterého může stanice rozpoznat, zda vysílá jedna nebo více stanic.

Centralizované řízení - přidělování na žádost

• žádosti od stanic přicházejí k řídící stanici po vyhrazenych kanálech
• řídící stanice arbitruje požadavky a přiděluje kanál (typicky na společném downstream kanále)
• použití v rádiových sítích, pro žádosti se využívá vyhrazeného nízkorychlostního podkanálu časového multiplexu

Distribuované řízení

• nezávislé na řídící stanici
• zpravidla složitější implementace

Distribuované řízení - Rezervace kanálu

• pověřenou stanicí periodicky generován rezervační rámec
  (charakter bitové mapy, sloty o délce aspoň 2*t, počet slotů odpovídá počtu zúčastněných stanic)
  
• ve svém slotu může každá stanice požádat o přidělení slotu v datovém kanále
• datové sloty následují podle za rezervačním rámcem (jen vyžádané)
• neefektivní pro velký počet stanic na rozlehlé síti s malou zátěží
• na prázdném kanále neustálé opakování rezervačních slotů

Distribuované řízení - Binární vyhledávání

• stanice nejprve (synchronizovaně) postupně vysílají bity své adresy (od nejvyššího řádu)
• vysílané bity se na sběrnici logicky sčítají (OR)
• jakmile stanice vysílá 0 a čte 1, chce vysílat někdo s vyšší prioritou a stanice musí umlknout
  => režie pouze log2(N), srov. s rezervačním rámcem o N bitech (N je počet stanic)
  

Distribuované řízení - Logický kruh

• Adresy stanic stanic tvoří cyklickou posloupnost, každá stanice zná svou adresu a adresu následníka.
• Mezi stanicemi se cyklicky předává právo k vysílání (token).
• Stanice vlastnící token smí vysílat, do určité doby však musí předat token následníkovi.

Distribuované řízení - Virtuální logický kruh

Metody přístupu u kruhových sítí

• Newhallův kruh (Token Ring)
• Piercův kruh (cirkulující minipakety)
• Vkládání rámců (vkládání/odepínání posuvného registru s rámcem do bitového toku na kruhu)