Traducere de Onacă Daniel (meph@infoiasi.ro).
Documentul original : RFC 904

Specificaţii formale pentru Exterior Gateway Protocol

0.   Statusul acestui memo

Prezentul RFC reprezintă specificaţia pentru Exterior Gateway Protocol (EGP). Acest document constituie o completare a RFC 827 şi RFC 888 şi specifică un standard pentru comunitatea DARPA. Interacţiunile dintre gateway-urile diferitelor sisteme autonome din cadrul ARPA-Internet trebuie să urmeze acest protocol.

1.   Introducere

Documentul de faţă reprezintă specificaţia formală pentru Exterior Gateway Protocol (EGP), folosit pentru schimbarea de informaţii despre accesibilitatea în reţea între diferite gateway-uri aparţinând unor sisteme autonome, de acelaşi tip sau diferite. Specificaţia de faţă intenţionează să fie utilizată ca un ghid de referinţă în vederea implementării, testării şi verificării, şi conţine sugestii privind parametrii algoritmici potriviţi pentru operaţii peste o mulţime vastă de configuraţii, inclusiv ARPANET şi multe tehnologii de reţea ce fac acum parte din sistemul Internet.

În mod specific excluse din acest document sunt discuţiile privind contextul, modul de aplicare şi restricţiile EGP, care au fost deja tratate (RFC 827, RFC 888). Dacă EGP va evolua, aşa cum este de aşteptat, astfel încât să includă structuri nerestricţionate la cele de tip arbore şi să încorporeze posibilităţi de rutare complete, această specificaţie va fi fie revizuită, fie declarată depăşită. Totuşi, este de aşteptat ca, pe măsură ce noi caracteristici sunt adăugate la EGP, mecanismele de bază ale protocolului descrise aici să rămână neschimbate substanţial, având schimbat doar formatul şi interpretarea mesajului de tip Update (a se vedea mai jos).

Secţiunea 2 a acestui document descrie nomenclatura utilizată, în timp ce Secţiunea 3 descrie modelul maşinii de stare, incluzând evenimente, acţiuni, parametri şi tranziţii de stare. Secţiunea 4 conţine o descriere formală a operaţiilor maşinii, împreună cu proceduri şi algoritmi specifici. Anexa A descrie formatele mesajelor EGP, în timp ce Anexa B conţine un rezumat al diferenţelor minore dintre acestea şi formatele descrise în RFC 888. Anexa C prezintă o analiză a accesibilităţii, incluzând un tabel al tranziţiilor de stare compuse pentru un sistem de două gateway-uri EGP ce comunică.

1.1.   Rezumat şi trecere în revistă

EGP există pentru a transporta informaţii legate de accesibilitate între gateway-uri vecine, care pot fi în sisteme autonome diferite. Protocolul conţine mecanisme pentru a descoperi vecini, a monitoriza accesibilitatea vecinilor şi pentru a schimba informaţii privind accesiblilitatea în reţea sub forma mesajelor Update. Protocolul este bazat pe interogare periodică folosind schimburi de mesaje de forma Hello/I-Heard-You (I-H-U) pentru a monitoriza accesibilitatea vecinilor şi comenzi Poll pentru a solicita răspunsuri de tip Update.

Specificarea pentru EGP este bazată pe un model formal constând dintr-un automat finit cu evenimente definite, tranziţii de stare şi acţiuni. Diagrama următoare arată o reprezentare grafică simplificată a acestei maşini (vezi Secţiunea 3.4 pentru un tabel detaliat al tranziţiilor de stare).

În continuare urmează un mic rezumat si o trecere în revistă a operaţiilor pe un gateway după stări, aşa cum este determinat de acest model.

Starea Idle (0)

În această stare gateway-ul nu are nici o resursă (spaţiu pentru tabele) pentru vreun vecin şi nici o activitate de protocol de nici un fel nu este în desfăşurare. Răspunde numai la o comandă Request (cerere) sau la un eveniment de tip Start (sistemul sau un operator este iniţializat) şi ignoră orice altă comandă sau răspuns. Gateway-ul mai poate returna, opţional, un răspuns Cease-ack la o comandă Cease în această stare.

După recepţionarea unei comenzi Request gateway-ul iniţializează variabilele de stare aşa cum este descris în Secţiunea 3.1, trimite un răspuns Confirm (confirmare) şi face o tranziţie către starea Down, dacă alocările resurselor o permit, sau, dacă nu, trimite un răspuns Refuse (refuz) şi se întoarce în starea Idle (repaus). În momentul recepţionării unui eveniment de Start trimite o comanda Request si tranziţii catre starea Acquisition (procurare).

Starea Acquisition (1)

În această stare gateway-ul retransmite periodic comenzi Request. După primirea unui răspuns Confirm iniţializează variabilele de stare şi face o tranziţie către starea Down. După primirea unui răspuns Refuse se întoarce în starea Idle. Gateway-ul nu trimite alte comenzi sau răspunsuri în această stare, având în vedere că nu au fost iniţializate toate variabilele de stare.

Starea Down (2)

În această stare gateway-ul a primit o comandă Request sau un răspuns Confirm a fost primit în urma trimiterii unui Request anterior. Protocolul privind accesibilitatea în reţea a declarat vecinul ca fiind inactiv. În această stare gateway-ul procesează comenzi tip Request, Cease sau Hello şi răspunde în concordanţă. Trimite periodic comenzi Hello dacă îi este permis. Nu procesează comenzi Poll si nici nu le trimite, dar poate, opţional, să proceseze o indicaţie Update nesolicitată.

Starea Up (3)

În această stare protocolul despre accesibilitatea în reţea a declarat vecinul ca fiind activ. În această stare gateway-ul procesează şi răspunde la toate comenzile. Retransmite periodic comenzi Hello, dacă sunt permise, şi comenzi Poll.

Starea Cease (4)

Un eveniment Stop face să fie trimisă o comandă Cease şi o tranziţie către starea Cease. În această stare gateway-ul retransmite periodic comanda Cease şi se întoarce în starea Idle în urma primirii unui răspuns Cease-ack sau a unui alt eveniment Stop. Tranziţiile de stare definite sunt proiectate pentru a asigura că vecinul primeşte cu probabilitate maximă comanda Cease şi opreşte protocolul.

În următoarele secţiuni ale acestui document este descrisă o maşină de stare care poate servi ca model pentru implementare. Se poate întâmpla ca programatorii să devieze de la acest model, conformându-se specificaţiilor protocolului; totuşi, pentru a verifica conformitatea cu specificaţia, modelul maşinii de stări este intenţionat ca model de referinţă.

Deşi nu se menţionează specific în acest document, ar trebui înţeles că toate gateway-urile din Internet trebuie să includă suport pentru Internet Control Message Protocol (ICMP), în special mesajele ICMP Redirect şi ICMP Destination Unreachable.

2.   Nomenclatură

Următoarele tipuri de mesaje EGP sunt recunoscute în acest document. Formatul fiecăruia dintre ele este descris în Anexa A.

Mesajele EGP sunt clasificate ca şi comenzi care cer o acţiune, răspunsuri, care sunt trimise pentru a indica statusul acelei acţiuni, şi indicaţii, care sunt similare răspunsurilor, dar pot fi trimise tot timpul. În continuare este o listă de comenzi şi răspunsurile lor posibile.
 

Mesajele de Update şi Error sunt clasificate ca fiind atât răspunsuri cât şi indicaţii. Atunci când sunt trimise în răspuns la o comandă anterioară, fiecare dintre ele este un răspuns. În unele circumstanţe un mesaj Update nesolicitat poate fi trimis, caz în care este o indicaţie. Utilizarea mesajului Error în alte situaţii decât în cazul unui răspuns pentru o comandă anterioară este subiect pentru studiu viitor.

3.   Maşina de stare

Această secţiune descrie modelul maşinii de stare pentru EGP, incluzând variabile şi constante care stabilesc starea în orice moment, evenimentele care pot cauza tranziţii de stare, acţiunile care rezultă în urma acestor tranziţii şi tabelul tranziţiilor de stare care defineşte comportamentul.

3.1.   Variabile de stare

Modelul maşinii de stare include un număr de variabile de stare care stabilesc starea protocolului dintre gateway şi fiecare dintre vecinii săi. Prin urmare, un gateway ce menţine EGP cu un număr de vecini trebuie să menţină o mulţime separată a acestor variabile de stare pentru fiecare vecin. Starea curentă, evenimente şi acţiuni ale maşinii de stare se aplică separat pentru fiecare vecin.

Acest model presupune că resursele sistemului, incluzând mulţimea de variabile de stare, sunt alocate atunci când masina de stare părăseşte starea Idle, fie din cauza primirii unui Request specificând o noua adresă a unui vecin, fie din cauza unui eveniment Start specificând o adresă a unui vecin nou. Când oricare dintre aceste evenimente are loc valorile variabilelor de stare sunt iniţializate după cum este indicat mai jos. După întoarcere în starea Idle, toate resursele, incluzând variabilele de stare, sunt dealocate şi returnate sistemului. Programatorii pot, bineînteles, să aleagă să aloce resursele şi variabilele de stare permanent.

Printre variabilele de stare sunt incluse următoarele, ce determină tranziţiile de stare ale modelului. Valorile iniţiale pentru toate variabilele exceptând trimiterea numărului de ordine S sunt setate în timpul schimbului iniţial Request/Confirm. Valoarea iniţială pentru S este arbitrară.

Variabile de stare adiţionale ar putea fi necesare pentru a oferi suport pentru numeroase temporizatore şi funcţii interne de întreţinere similare. Funcţiile şi managementul variabilelor citate sunt discutate în Secţiunea 4.

3.2.   Parametri fixaţi

Această secţiune defineşte mai mulţi parametri ce caracterizează funcţiile gateway-ului. Sunt incluse valori sugerate pentru fiecare parametru, bazate pe implementări experimentale în sistemul Internet. Aceste valori pot fi sau nu adecvate pentru configuraţii individuale.

Urmează o listă de parametri de intervale de timp care controlează retransmisii şi alte funcţii dependente de timp.

Parametrii P4 şi P5 sunt utilizaţi numai atunci când este implementată opţiunea temporizator de anulare. Parametrul P4 stabileşte cât de mult va rămâne maşina în stările Down şi Up în absenţa comenzilor sau răspunsurilor şi ar fi setat în mod obişnuit pentru a susţine informaţiile de stare în timp ce vecinul este părăsit sau restartat, de exemplu. Parametrul P5 stabileşte cât de mult va rămâne maşina în stările Acquisition sau Cease în absenţa răspunsurilor, şi ar fi setat în mod obişnuit în aceeaşi ordine ca si valorile aşteptate pentru variabilele T3.

Urmează o listă de alţi parametri de interes.

Parametrii j şi k stabilesc "imunitatea la zgomot" a protocolului de accesibilitate a vecinilor ce va fi descris mai târziu. Valorile din coloana "Activ" sunt sugerate dacă gateway-ul alege să facă hello polling, în timp ce valorile din coloana "Pasiv" sunt sugerate în cazul contrar.

3.3.   Evenimente

Urmează o listă de evenimente care pot cauza tranziţii de stare în model.

Este un eveniment special, numit indicaţie a accesibilităţii vecinului, care are loc când:

1.        Gateway-ul operează în modul activ (modul hello polling activat) şi fie o comandă Confirm, I-H-U sau un răspuns Update a fost primit.

2.        Gateway-ul operează în modul pasiv, (modul hello polling dezactivat) şi fie o comandă Poll sau Hello a fost primită cu codul "Starea Up" în câmpul Status.

3.4.   Tabelul tranziţiilor de stare

Următorul tabel rezumă tranziţiile de stare ce pot avea loc ca răspuns la evenimentele enumerate anterior. Tranziţiile sunt arătate în forma n/a, unde n este starea următoare şi a reprezintă acţiunea.

Nota * : Tranziţia se aplică în cazul în care cererea de achiziţionare de vecin este acceptată. Tranziţia "0/Refuse" se aplică pentru cazul în care cererea a fost refuzată.
Nota ** : Acţiunea Cease în aceste cazuri este opţională.

3.5.   Tranziţii de stare şi acţiuni

Următorul tabel descrie în amănunt tranziţiile maşinii de stare şi acţiunile invocate.

4.   Descrierea funcţională

Această secţiune conţine descrieri detaliate ale numeroaselor proceduri şi algoritmi folosiţi pentru managementul protocolului.

4.1.   Administrarea variabilelor de stare

Variabilele de stare care caracterizează protocolul sunt rezumate în Secţiunea 3.1. Această secţiune descrie administrarea detaliată a acestor variabile, incluzând numerele de ordine, intervale de interogare şi temporizatoare.

4.1.1.   Numere de ordine

Toate comenzile şi răspunsurile EGP conţin un număr de ordine. Variabila de stare R înregistrează ultimul număr de ordine primit într-o comandă de la respectivul vecin.  Valoarea curentă a lui R este utilizată ca număr de ordine pentru toate răspunsurile şi indicaţiile trimise vecinului până când o comandă cu un număr de ordine diferit este primită de la vecinul respectiv.

Programatorii sunt liberi să administreze numerele de ordine ale comenzilor trimise; totuşi, este sugerat să fie menţinută o variabilă de stare pentru trimitere S separată pentru fiecare vecin EGP şi ca valoarea acesteia să fie incrementată înainte de a fi trimisă o comandă Poll şi la nici un alt timp.  Acţiunile care trebuie urmate în momentul primirii unui răspuns sau indicaţie cu un număr de ordine diferit de valoarea lui S nu sunt specificate; totuşi, este recomandat să fie ignorate.

4.1.2.   Intervale de interogare

 Ca parte a schimbului Request/Confirm este stabilită o mulţime de intervale, incluzând T1, care stabileşte intervalul dintre retransmiterile comenzilor de tip Hello, şi T2, care stabileşte intervalul dintre retransmiterile comenzilor de tip Poll.

Fiecare configuraţie a gateway-ului este caracterizată de o mulţime fixă de parametri, incluzând P1, care specifică intervalul minim de interogare în care se va răspunde la comenzi de tipul Hello, şi P2, care specifică intervalul minim în care se va răspunde la comenzi Poll. P1 şi P2 sunt inserate în câmpurile Intervalul Hello (S1) şi Intervalul Poll (S2) ale comenzilor Request şi, respectiv, ale răspunsurilor Confirm.

Un gateway care primeşte o comandă Request sau un răspuns Confirm utilizează câmpurile S1 şi S2 în mesaj pentru a calcula variabilele sale de stare T1, respectiv T2. Programatorii sunt liberi să facă aceste calcule în mod arbitrar; totuşi, următoarele constrângeri trebuie observate:

1.      Dacă T1<S1 atunci vecinul poate ignora comenzile de tip Hello. Dacă T2<S2, vecinul poate ignora comenzile de tipul Poll.

2.      Intervalul de timp T3, în care indicaţiile despre accesibilitatea vecinilor sunt numărate, depinde de T1. În cazul în care doi vecini selectează valori foarte diferite pentru variabilele lor de stare T3, algoritmul pentru accesibilitatea vecinilor ar putea să nu funcţioneze bine. Acest lucru poate fi evitat dacă T1>max(P1, S1).

3.      Dacă atât S1, cât şi S2, sunt inacceptabile dintr-un motiv oarecare (de exemplu limitele utile sunt depăşite), vecinul poate trimite fie un răspuns de tip Refuse, fie să declare un eveniment Stop, în funcţie de stare.

Este sugerat ca T3 să fie calculat ca de patru ori valoarea lui T1, pentru a permite o fereastră pentru patru indicaţii de accesibilitate a vecinilor, fapt găsit adecvat în implementările experimentale. Progamatorii pot alege să facă T3 un parametru fixat în acele cazuri în care drumul dintre vecini are caracteristici bine cunoscute.

A se nota că, dacă un gateway încearcă să trimită comenzi de tipul Hello aproape de rata max(P1, S1) sau comenzi Poll aproape de rata max(P2, S2), vecinul ar putea considera, datorită aglomeraţiei din reţea, că sosirile lor succesive încalcă restricţiile pentru interogare. Din acest motiv, gateway-ul ar trebui să încerce să trimită la rate mai mici decât acestea. Cât de mult sub aceste rate este potrivit, depinde de mulţi factori ce depăşesc scopul acestei specificaţii.

4.1.3.   Modul Hello Polling

Algoritmul pentru testarea accesibilităţii în reţea poate fi folosit atât în modul activ cât şi în cel pasiv. În modul activ comenzi de tip Hello sunt trimise periodic împreună cu comenzi Poll, cu accesibilitatea determinată de răspunsurile I-H-U şi Update corespunzătoare. În modul pasiv comenzile Hello nu sunt trimise şi răspunsurile I-H-U nu sunt aşteptate. Accesibilitatea este determinată din câmpul Status al comenzilor Hello sau Poll primite sau al răspunsurilor Update.

Variabila de stare M specifică dacă gateway-ul operează în modul activ sau pasiv. Cel puţin unul dintre cei doi vecini care împart protocolul trebuie să opereze în modul activ; totuşi, protocolul pentru accesibilitatea vecinilor este proiectat să funcţioneze chiar dacă ambii vecini sunt în modul activ. Valoarea lui M este determinată din câmpul Status al unei comenzi Request sau al unui răspuns Confirm. Expeditorul setează valoarea acestui câmp dacă implementarea suportă modul activ, modul pasiv sau pe amândouă:

Destinatarul inspectează acest câmp şi setează valoarea lui M în funcţie de propriile capabilităţi, după cum urmează:

În cazul "*" modul este determinat comparând numerele sistemelor autonome ale vecinilor. Vecinul cu cel mai mic asemenea număr este presupus a fi în modul activ, în timp ce toţi ceilalţi sunt presupuşi a fi în modul pasiv. În cazul "**" vecinul poate fie să trimită un răspuns Refuse fie să declare un eveniment de tip Stop, în funcţie de stare.

4.1.4.   Temporizatoare

Sunt trei temporizatoare definite în maşina de stare: t1, utilizat  pentru a controla retransmisiile comenzilor Request, a mesajelor Hello sau Cease, t2, utilizat pentru a controla retransmisiile comenzilor de tip Poll, şi t3, care este folosit ca un mecanism de temporizator de anulare în caz că protocolul stagnează indefinit. Temporizatoarele sunt setate la valorile specificate la intrarea în fiecare stare şi decrementate până la zero.

În cazul lui t1 şi t2 evenimente dependente de stare sunt declarate când temporizatorul ajunge la zero, după care temporizatorul este resetat la valoare specificată şi decrementat în continuare. În cazul lui t3, un eveniment de tip Stop este declarat atunci când temporizatorul ajunge la valoarea zero. Progamatorii pot alege să nu implementeze t3 sau, dacă nu,  pot alege să îl implementeze numai în anumite cazuri, cu efectul că ar putea fi retransmise indefinit comenzi de tip Request, Hello şi/sau Cease.

Următorul tabel arată valorile iniţiale pentru fiecare temporizator în fiecare stare. O valoare lipsă indică faptul că temporizatorul nu este folosit în acea stare. A se nota că temporizatorul t3 este setat la valoarea P4, în urma primirii indicaţiei de accesibilitate a vecinului, atunci cînd se află în starea Down sau Up.

4.2.   Pornirea şi oprirea protocolului

Evenimentele de Start şi Stop sunt intrinseci mediului sistemului gateway-ului. Ele pot fi declarate ca şi rezultatul pornirii sau opririi de către operator a gateway-ului, de exemplu. Un eveniment de tip Start  are înţeles numai în anumite stări; totuşi, un eveniment Stop are înţeles în toate stările.

În toate stările cu excepţia stării de Idle, temporizatorul t3 este presupus că rulează. Acest temporizator este iniţializat la P5 secunde în urma intrării în orice stare şi la P4 secunde după primirea unei indicaţii despre accesibilitatea vecinului în stările Down şi Up. Dacă expiră, un eveniment Stop este declarat. Un eveniment de tip Stop poate fi declarat şi de o acţiune intrinsecă a sistemului, cum ar fi o problemă legată de resurse sau o comandă a operatorului.

Dacă temporizatorul de anulare nu este implementat, un eveniment de tip Stop poate fi iniţializat manual şi utilizat pentru oprirea protocolului. Dacă acest lucru este făcut în starea Down sau Up, maşina va face o tranziţie către starea Cease şi va transmite o comandă de tip Cease. Dacă vecinul nu răspunde la această comandă maşina va rămâne în starea Cease un timp nedefinit; totuşi, un al doilea eveniment Stop poate fi utilizat în această stare pentru a forţa tranziţia în starea Idle.

O comandă de tip Cease primită în orice stare va cauza ca gateway-ul să trimită imediat un răspuns Cease-ack şi să facă o tranziţie către starea Idle. Aceasta face ca protocolul să fie stopat şi toate resursele sistemului trimise procesului gateway pentru a fi eliberate. Intervalul de timp dintre momentul când gateway-ul intră în starea Idle ca rezultat al primirii unei comenzi Cease şi momentul când trimite o comandă Request pentru a continua protocolul nu este specificat; totuşi, este recomandat ca acest interval să fie cel puţin P5 secunde.

Se poate întâmpla ca răspunsul Cease-ack să fie pierdut în reţea, făcând vecinul să trimită comenzi de tip Cease un timp nedefinit, cel puţin dacă nu are implementată opţiunea temporizatorului de anulare. Pentru a reduce posibilitatea ca acest lucru să se întample este sugerat ca un gateway în starea Idle să fie pregătit să răspundă la o comandă Cease cu un răspuns Cease-ack oricând este posibil.

4.3.   Determinarea accesibilităţii vecinului

Scopul algoritmului de determinare a accesibilităţii vecinului este de a confirma că vecinul poate fi considerat cu siguranţă operaţional şi capabil să furnizeze informaţii despre accesibilitatea în reţea care să fie de încredere. Un alt scop la fel de important este să filtreze informaţiile despre accesibilitate care sunt incorecte sau corupte înainte de a le trimite mai departe la restul gateway-urilor din sistemul Internet, evitând astfel schimbări inutile de accesibilitate.

După cum a fost descris mai sus, un gateway care operează în modul activ trimite periodic comenzi de tip Hello şi ascultă pentru răspunsuri I-H-U pentru a determina indicaţii despre accesibilitatea vecinilor. Un gateway care operează în modul pasiv determină indicaţii de accesibilitate utilizând câmpul Status din comenzile Hello primite. Comenzile Poll şi răspunsurile Update pot fi folosite în locul comenzilor Hello, respectiv răspunsurilor I-H-U, având în vedere că au aceleaşi informaţii în câmpul Status.

Algoritmul rulează încontinuu cât timp gateway-ul se află în stările Down şi Up şi operează după cum urmează. Defineşte o fereastră, care se mişcă în timp, pornind în prezent şi extinzându-se înapoi pentru t secunde. Apoi numără numărul n de indicaţii de accesibilitate a vecinilor care s-au întamplat în acel timp. Dacă n creşte până la j, atunci declară un eveniment de tip Up. Dacă n scade până la k, atunci declară un eveniment de tip Down. Numărul n este setat la zero ca urmare a intrării în starea Down din orice altă stare în afară de starea Up.

Fereastra de timp t în acest algoritm este definită ca T3 secunde, valoarea care a fost sugerată a fi de patru ori T1, el însuşi determinat în timpul schimbului Request/Confirm. Pentru funcţionarea corectă a algoritmului doar o singură informaţie de accesibilitate este semnificativă într-o fereastră de T1 secunde şi toate celelalte sunt ignorate. A se nota că singura modalitate prin care n poate creşte este ca rezultat al unei indicaţii de accesibilitate a vecinilor şi singura modalitate prin care n poate descreşte este ca rezultat al unei vechi indicaţii de accesibilitate care iese din fereastră.

Comportamentul algoritmului descris mai sus şi care utilizează parametrii fixaţi sugeraţi j şi k diferă în funcţie de modul în care operează gateway-ul, adică modul activ sau pasiv. În modul activ (j = 3, k = 1 şi T3/T1 = 4), odată ce un vecin a fost declarat inactiv, va fi forţat inactiv pentru încă cel puţin două intervale T1 şi, odată ce a fost declarat activ, va fi forţat activ pentru încă cel puţin două intervale T1. Nu va schimba starea decât dacă cel puţin trei din ultimele patru determinări de accesibilitate primite indicau această schimbare.

În modul pasiv (j = 1, k = 4 şi T3/T1 = 4), vecinul va fi considerat activ de prima oară când un câmp Status sau o comandă Hello sau Poll sau răspuns Update indică starea "Up" până când patru intervale T1 au trecut fără o astfel de indicaţie. Proiectarea, sugerată de altele asemănătoare utilizate în ARPANET, s-a dovedit eficientă în implementările experimentale, dar ar putea avea nevoie de ajustări pentru alte configuraţii.

Este convenabil pentru un gateway activ să trimită comenzi Hello la o rată de una la fiecare T1 secunde şi să înlocuiască o comandă Hello cu una Poll aproximativ la fiecare T2 secunde, cu indicaţia de accesibilitate generată de comandă I-H-U corespunzătoare sau răspunsuri Update. Vecinii lui pasivi generează indicaţii de accesibilitate folosind câmpul Status al comenzilor Hello şi Poll primite şi al răspunsurilor Update.

Programatorii pot găsi acest model util pentru a înţelege şi implementa acest algoritm. Fie un registru de deplasare de n-biţi care deplasează un bit la dreapta la fiecare interval de T1 secunde. Dacă o indicaţie de accesibilitate a fost primită în intervalul de T1 secunde precedent un bit cu valoarea 1 este deplasat în registru la finalul intervalului; altfel un bit cu valoarea 0 este deplasat. Un tabel cu 2^n intrări indexat după conţinutul registrului poate fi folosit pentru a calcula numărul de biţi cu valoarea 1, care poate fi la rândul lui utilizat pentru a declara evenimentul corespunzător în maşina de stare. O valoare a lui n egală cu 4 a fost găsită utilă în implementările experimentale.

4.4.   Determinarea accesibilităţii în reţea

Informaţia despre accesibilitatea în reţea este codată în mesajele de tip Update sub forma unor liste de reţele şi gateway-uri. Câmpul Ip Source Address din comanda Poll este utilizat pentru a specifica o reţea comună pentru sistemele autonome ale fiecărui vecin, ceea ce e obişnuit, dar nu necesar, reţeaua comună însuşi vecinilor. Răspunsul Update include o listă de gateway-uri de pe reţeaua comună. Asociată cu fiecare gateway este o listă de reţele accesibile de la gateway împreună cu numărul corespunzător de hop-uri.

Este important de înţeles că, la stadiul actual de dezvoltare, aşa cum este descris în RFC 827 şi RFC 888, modelul arhitectural al EGP restrânge implementarea "accesibilităţii" în acest context. Această consideraţie, la fel ca şi restricţiile de topologie implicite, sunt în afara scopului discuţiei de faţă. Cititorul este îndrumat către RFC-uri pentru mai multe detalii.

Două tipuri de liste de gateway-uri pot fi incluse în răspunsurile Update, formatul lor fiind descris în Anexa A. Ambele liste includ numai acele gateway-uri care sunt direct legate la reţeaua specificată în câmpul Ip Source Network al ultimei comenzi de tip Poll primite. Lista internă include unele sau toate gateway-urile din acelaşi sistem autonom ca şi expeditorul, împreună cu reţelele care sunt accesibile din aceste gateway-uri, cu gateway-ul care trimite lista primul. O reţea este accesibilă în acest context dacă există un drum către acea reţea incluzând numai gateway-urile din sistem. Lista externă include acele gateway-uri care sunt în alte sisteme autonome cunoscute de expeditor. Este important de realizat că numărul de hop-uri nu reprezintă o măsură pentru rutare şi sunt comparabile între diferite gateway-uri numai dacă acele gateway-uri aparţin aceluiaşi sistem autonom; adică sunt în lista internă.

Conform modelului arhitectural curent al sistemului numai gateway-uri aparţinând unui sistem desemnat, numit sistemul nucleu (system core), pot include lista externă în răspunsurile lor de tip Update. Toate celelalte gateway-uri pot include numai acele gateway-uri care aparţin aceluiaşi sistem şi pot cere accesibilitatea pentru o anumită reţea numai dacă acea reţea este accesibilă în acelaşi sistem.

Intervalul dintre două comenzi Poll consecutive, T2, este determinat în timpul schimbului Request/Confirm. Totuşi, specificaţia permite cel mult o indicaţie Update nesolicitată între comenzi Poll succesive primite de la vecin. Este intenţia modelului ca o indicaţie Update să fie trimisă (a) după intrarea în starea Up şi (b) când o schimbare în baza de date a accesibilităţii este detectată, subiect al acestei limitări.

Ocazional se poate întâmpla ca o comandă Poll sau un răspuns Update să fie pierdut în reţea cu urmarea că informaţia despre accesibilitatea în reţea s-ar putea să nu fie disponibilă decât după încă un interval de T2 secunde. Ca o posibilitate de implementare, gateway-ul care trimite o comandă Poll şi nu primeşte un răspuns Update după T1 secunde poate să trimită încă o comandă Poll. Un gateway care primeşte o comandă de tip Poll poate (a) să trimită un răspuns Update dacă nu a primit deloc o comandă Poll pentru acel interval, (b) să trimită un al doilea răspuns Update (care e considerat indicaţie Update nesolicitată, după cum a fost menţionat în paragraful anterior) sau (c) să trimită un răspuns Error sau să nu răspundă deloc în celelalte cazuri.

4.5.   Mesaje de eroare

Mesajele de eroare pot fi utilizate pentru a comunica probleme, după cum sunt descrise în Anexa A, legate de formatul mesajului de tip Error răspuns/indicaţie. În general, un mesaj de tip Error este trimis după primirea unei alte comenzi sau răspuns cu un format invalid, conţinut sau ordonare, dar niciodată în răspuns la alt mesaj Error. Primirea unui mesaj de tip Error ar trebui să fie considerată consultativă şi nu trebuie să aibă ca urmare schimbarea de stare, exceptând posibil invocarea unui eveniment de tip Stop.

Anexa A.   Formatul mesajelor EGP

Formatul numeroaselor tipuri de mesaje EGP sunt descrise în această secţiune. Toate mesajele EGP includ un header de zece octeţi cu şase câmpuri, care poate fi urmat de câmpuri adiţionale, depinzând de tipul mesajului. Formatul header-ului este arătat mai jos, împreună cu o descriere a câmpurilor sale.

În continuare este o descriere a fiecărui format de mesaj. A se nota că descrierea de mai sus se aplică la toate formatele şi nu va fi repetată.

          A.1   Mesaje de achiziţionare de vecini

A se nota: câmpurile care conţin intervalele de tip Hello şi Poll sunt prezente numai în mesajele de tip Request şi Confirm.

          A.2   Mesaje pentru accesibilitatea vecinilor

          A.3   Comanda Poll

          A.4   Indicaţia/Răspunsul Update

          A.5   Indicaţia/Răspunsul Error

Anexa B.   Comparare cu RFC 888

Sunt necesare minore dezvoltări în formatul mesajelor RFC 888 pentru a suporta anumite caracteristici ale modelului maşinii de stare, în special capabilitatea de a cere unui vecin să suprime comenzi Hello. În plus, modelul sugerează o mapare între stările sale şi anumite indicaţii de status şi eroare care clarifică şi generalizează interpretarea.

Toate câmpurile din header cu excepţia celui de Status (care se numeşte câmp de Informaţie în unele părţi ale RFC 888) rămân neschimbate. Următorul tabel rezumă schimbările de format sugerate pentru numeroasele mesaje după clasa (Tip, Cod).

Schimbările faţă de RFC 888 sunt următoarele:

1.        Codurile de status au fost combinate în două clase, una pentru acele mesaje implicate în pornirea şi oprirea protocolului şi cealaltă pentru acel mesaje mesaje implicate în menţinerea protocolului şi schimbarea de informaţii despre accesibilitate. Unele mesaje din orice clasă nu pot utiliza toate codurile de status asignate.

2.        Codurile de status pentru Request şi Confirm indică dacă expeditorul operează în mod activ sau pasiv. În RFC 888 acest câmp trebuie să fie zero; totuşi, RFC 888 nu specifică nici un mecanism pentru a decide cum ar trebui vecinii să se interogheze unul pe altul.

3.        Codurile de status pentru Cease, Refuse şi Cease-ack au aceeaşi interpretare. Aceasta dă o indicaţie clară şi neambiguă atunci când protocolul este terminat ca urmare a unei situaţii neprevăzute, de exemplu dacă NOC repartiţionează dinamic ARPANET-ul. Codurile asignate nu sunt consistente cu RFC 888, cum codurilor pentru Refuse şi Cease le-au fost asignate valori conflictuale; totuşi, diferenţele sunt minore şi nu ar trebui să cauzeze probleme semnificative.

4.        Codurile de status pentru Hello, I-H-U, Poll, Update şi Error au aceeaşi interpretare. Codurile de la 0 la 2 sunt exclusive mutual şi sunt alese doar pe baza stării expeditorului. În cazul lui Update (şi posibil Error) unul dintre aceste coduri poate fi combinat cu bitul "nesolicitat" care corespunde codului 128. În RFC 888 acest câmp nu este folosit pentru Poll şi Error şi poate conţine doar zero sau 128 pentru Update, deci cazul obişnuit este să se presupună că accesibilitatea reciprocă nu poate fi determinată de aceste mesaje.

5.        Unele dintre codurile de accesibilitate definite în RFC 888 au fost scoase din cauza lipsei de aplicabilitate.

Anexa C.   Analiza accesibilităţii

Următorul tabel arată tranziţiile de stare care se pot realiza într-un sistem de două gateway-uri EGP vecine. În afara utilităţii pentru proiectare şi verificare, tabelul este folositor şi pentru implementare şi testare.

Sistemul de două gateway-uri EGP vecine este modelat ca un automat finit construit ca un produs cartezian a două maşini de stare, aşa cum au fost definite mai sus. Fiecare stare a acestei maşini este reprezentată ca [i, j], unde i şi j sunt stările maşinii de stare iniţiale. Fiecare linie din tabel arată o tranziţie de stare a maşinii în forma următoare:

[i₁, j₁] → [i₂, j₂] E A

care specifică faptul că maşina în starea [i₁, j₁] în prezenţa evenimentului E face o tranziţie în starea [i₂, j₂] şi generează acţiunea A. Acţiuni multiple sunt separate de simbolul "/". Simbolul special "*" reprezintă o mulţime de linii unde toate "*" din linie iau aceleaşi valori 0 - 4 pe rând.

Tabelul arată numai acele tranziţii care se pot produce ca rezultat al sosirii unor evenimente la unul dintre cei doi vecini. Tabela completă conţine şi o mulţime duplicată de linii pentru fiecare vecin, cu fiecare linie derivată dintr-o linie a tabelului de mai jos utilizând ransformarea:

[i₁,j₁] ® [i₂,j₂] E A Þ  [j₁,i₁] Þ [j₂,i₂] E A

În modelul maşinii de stare definit în acest document toate stările maşinii de mai sus sunt accesibile; totuşi, unele sunt accesibile numai în cazuri extreme când un vecin "moare", de exemplu. În cazul comun unde numai unul dintre vecini iniţializează şi termină protocolul şi nimeni nu "moare", de exemplu, nu toate stările sunt accesibile. În continuare este o matrice care arată stările care pot fi accesate în acest caz, unde vecinul care porneşte şi opreşte protocolul este numit gateway activ şi celălalt gateway pasiv.

În matricea de mai sus intrările goale înseamnă stări inaccesibile, iar cele marcate "instabil" reprezintă stări trecătoare care nu pot persista pentru mult timp, datorită retransmiterii mesajelor de tip Hello şi Request, de exemplu.