BERKELEY UNIX 4.2下的EGP網關

1. 介紹

外部網關協議（外部網關協議）[ Rosen 82；Seamonson & Rosen 84; Mills 84a]
已經允許不同的網關體系的自主開發雖然國際互聯網絡路由選擇信息仍然保持全球性分布。
EGP為不同的自治網關系統交換經由他們可以達到的網絡的信息提供一些方法。。

本報告主要敘述在一VAX計算機上運行的Berkeley Unix 4.2操作系統上的當做一個用戶進
程工作的EGP的實現。
還對某些涉及局域自治系統配置相關的問題也進行了論述。

該EGP實現是試驗性的而不是Unix 4.2 BSD的一部分。 可以預料伯克來將來可能加入一
個EGP版本。

該程序是由C語言編寫。 EGP部分是以Liza Martin在麻省理工學院寫成的C - Gateway程
序代碼為基礎，而且路由管理部分以Unix 4.2 BSD路由管理守護進程" routed "為基礎。

除非特別聲明，該EGP功能與[ Mills 84a]的規范一致。

假定已具有在[ Seamonson & Rosen 84; Mills 84a]敘述的EGP知識。。

本章論述該工程的動機,第2章敘述網關設計，第3章為測試，第四章建議一些改進并且第5
章論述拓撲結構問題。

關于運行該EGP程序和該軟件說明的詳細資料刊登于ISI研究報告ISI/RR - 84 - 145 [ Kirton
84]。

該EGP程序的copies和文本的請求應該發送給Joyce Reynolds ( JKReynolds@_USC -
ISIF.ARPA)。沒有提供軟件支持。


1.1開發動機

與EGP的介紹相一致，internet網關被分成由Bolt, Beranek和Newman ( BBN)維護的"核心"
自治系統( AS)和許多由不同的組織維護的最少具有一個與一個核心AS網關共有的網絡的
"stub " AS。
該核心AS可能充當傳遞路由選擇信息的集線器

_______________

*
Unix is a trade mark of AT&T
* *
VAX是Digital Equipment Corporation的商標
不同的stub AS ' s以便它僅僅需要stub AS能與核心網關一起執行EGP。 更進一步的細節
在[ Rosen 82]中給出。

在本工程中，在internet中曾有28個" non - routing "網關。 Non - routing網關不能交換路
由選擇信息，但是需要在核心網關路由選擇表中的靜態的記錄。 1984年八月1日以后,
這些靜態表目已經刪除并且先前地non - routing網關被要求動態地經由EGP [ Postel 84]傳達
本消息給核心網關。

在該USC信息科學研究所( ISI)曾有一個non - routing網關去往處于Irvine網絡( UCI - ICS)
上的加利福尼亞大學。 由于從核心網關列表中消除了non - routing網關，必須通知該路由
到UCI - ICS的核心ISI網關使用EGP。

還有,萬一該核心ISI網關當機的話我們想要在ISI - NET和ARPANET之間具備一個備份網
關。 如此以來，網關可能需要經由EGP運輸路由選擇信息。 ISI網絡配置的細節在5.2節
進行論述。

Of the 28 non-routing gateways 23 were implemented by Unix systems, including
ISI's. 還有, ISI的被提議的備份網關是UNIX操作系統。因此存在局部和普遍的需要外部網
關協議實現運行在 Unix下面。 當前包括Department of Defense ( DoD)協議的UNIX操作系
統的版本是Berkeley Unix 4.2 ,所以它中選。


1.2外部網關協議綜述

本報告假定了解外部網關協議,然而為完整起見這里給出一個簡短概觀。為了解EGP背景詳
情請查閱[ Rosen 82], [ Seamonson & Rosen 84]提供了非正式的描述,并且[ Mills 84a]提供了
進一步格式說明和實現細節。

EGP通常在不同AS中的且具有有一個公用網絡的網關即鄰居網關之間傳輸。
公用網絡即鄰居網關。

EGP包含三個程序,鄰居獲得,鄰居可達性和網絡可達性。

鄰居獲得是一次雙向握手，在此過程中網關對通過交換請求和確認報文（包括最少Hello和
Poll間隔值）來進行傳導達成一致。 通過交換停止和停止確認報文終止獲取過程。

鄰居可達性是一個Hello commands和確保各網關正在運行的I - H -U ( I heard you)回應周期
式交換。。 當前30秒最小間隔被用于越過ARPANET。 只有一個網關必須發送一些命令,
其他的網關可以利用這些命令判斷可達性。
正發送可達性命令的網關叫做處于主動態,而正回答的網關叫做處于被動態。
網絡可達性由周期地發送Poll commands和接受表明該網絡經由一或多個在共享網絡上的網
關可以達到的更新應答來判斷。 當前２分鐘最小間隔被用于越過ARPANET。

2. 網關設計

EGP是一種具有松散定時約束的polling協議。 因此，唯一要求具有較高性能的功能是包轉
發。 Unix 4.2已經將包轉發技術嵌入到內核內核內部，在那里可以達到最佳性能。
在編寫Unix 4.2的時候，沒有為誤編路由的包發送ICMP ( Internet控制消息協議)重定向報
文。
這是一個必要ofinternet網關并且Berkeley以后將加入。

EGP和路由更新功能作為一個用戶進程實現。 因為只有微小的更改需要加入Unix內核，
這簡化了開發和分配。 這個方法與基于Xerox NS路由信息協議（ Routing Information
Protocol [ Xerox 81]）的Unix路由分配程序" routed " [ Berkeley 83]的方法是類似的。


2.1路由表

一個路由由一個目的網絡號組成,相鄰網關的地址用在直接相連的網絡上，而且用到達目的
網絡的網關站數作為距離的公制。

存在兩組路由表,內核列表（被用于包轉發技術）和EGP進程表。 該內核已經為主機和網
絡目的地設立了獨立的列表。 EGP進程僅維護網絡路由表。 當接到EGP更新報文時EGP
列表被更新。 當一個路由被更改時核心網絡列表通過SIOCADDRT和SIOCDELRT ioctl
系統調用被更新。 在初始化時為了保持一致性，內核網絡路由表由內核存儲映象文件
/dev/kmem讀取并被拷貝到EGP列表中。

此EGP的實現被設計成在網關（也是一個主機）上運行。
因為用polling獲得路由更新相對較慢，在通過EGP通知EGP進程之前主機通過ICMP重
定向收到路由變更的通告是可能的. 重定向直接更新內核列表。 EGP進程在一個生疏的插
座上偵聽重定向報文并且更新它的路由表以維護它們與內核的一致性。

EGP進程和路由表被當做兩個單獨的列表進行維護,一個為外部路由( via different AS網關)
而一個為內部路由(通過此AS的網關)。 外部路由表通過EGP更新報文更新。 內部路由
表當前是靜態的并且在初始化時設定。 它包括全部直接連接的網絡，通過SIOCGIFCONF
ioctl系統調用和任何內部非routing網關讀自外部網關協議初始化文件, EGPINITFILE來確
定。 將來內部路由表可以被內部網關協議( IGP)動態地更新.

為外部和內部路由維護單獨的列表簡化了僅包含內部路由選擇信息[ Mills 84b]的傳出更新
報文的準備。 在內部路由失敗情況下，還允許選擇作為內部路由備份保存的外部路由進行
替換。
候選路由標記以RTS_NOTINSTALL從而表明該內核路由將不會被更新。 在當前的實現中
候選路由不被使用。

2.1.1輸入更新

EGP更新用來更新外部路由表,如果滿足下列中的一個:

-不存在目的網絡的路由表項而且公制表明該路由是可以達到的。

-被報告的網關與當前路由相同。

-被報告的距離公制小于當前公制。

當前路由比全部已經獲取的EGP鄰居極限輪詢間隔舊。 簡而言之,該路由被來自上次
的更新所忽略。

除了省缺路由之外，如果任一外部路由表項在４分鐘或３次最大輪詢間隔（任何一個較大的）
時間內沒有被EGP更新，該外部路由表項被刪除。

如果獲得了多個EGP鄰居,對來源于他們的更新報文按照接收的先后順序做相同的處理。

在最壞的情況中,即一個路由變成時間比較久的路由而且該較舊的路由最初沒有被公布為不
可達時,可以使用兩個輪詢間隔去更新一個路由。 With the current poll interval this could be 4
minutes. 在Unix 4.2 BSD下，TCP連接(傳輸控制協議)在空閑６分鐘之后被自動地關閉。 所
以最壞的情況也不會導致TCP連接自動結束。o

2.1.2輸出更新

輸出更新包括來自內部路由表的直接地和靜態網絡，除了與 EGP鄰居共享的網絡之外。。

允許在更新中被通知的網絡可以在初始化時用EGPINITFILE規定。 這些允許精確的路由以
排除來自（可能的)路由回路情況下的外部更新。 其它必須有這個選項的情況是,非路由網
關屬于一個不同的AS而這個AS還沒有實現EGP時。 它的路由可能需要被歸入核心路由
表但是他們沒有被允許在輸出更新中被告知。

如果內部路由表包括其他的在與 EGP鄰居共享的網絡上的內部網關，它們將被作為他們所
連網絡的合適初站而包含在更新中。

到網絡的距離按照內部路由表進行設置，除非路由標志為down，而在這樣情況下距離設置
為255。 目前路由僅在輸出接口當機時才被標記為down。 為了給各輸出更新做準備，預
先用SIOCGIFFLAGS ioctl系統調用校驗所有接口的狀態。

未經請求的更新不予發送。


2.2鄰居獲取

EGPINITFILE列出了可信賴的EGP鄰居網關的地址，在初始化時讀取。 這些通常是核心
網關，因為只有核心網關提供完整的internet路由選擇信息。 編寫的時候在阿帕網上存在
三個核心網關支持EGP CSS - GATEWAY, ISI - GATEWAY和PURDUE - CS - GW,而且兩個
在MILNET, BBN - MINET - A - GW和AERONET - GW上。

EGPINITFILE還包含每次所能獲得的網關的最大值。 期望值通常為一。 如果這個網關被
宣布為down，另一個列表中的網關于是在充分的時間內將被自動地獲取以確保當前路由不
超時。

該網關將僅接受來自在可信賴列表中鄰居的獲取，而且如果它已經獲得它的最大量限額就不
會接受他們。 這個防止接受來自可能不可靠的來源的更新。

因為不是所有核心網關都運行EGP，所以不包含獲得核心網關不在信任列表中的但是已經
通過更新報文間接地獲悉的核心網關的功能。

新的獲取請求被發給鄰居，為了使他們出現在EGPINITFILE中。 新的請求如果不大于還
有待于獲得的鄰居的最大數的話就被立即發送。 許多突發請求用32秒間隔最多重傳５次，
這時候獲取重發間隔增加到４分鐘。 只要已經獲得了最大數量的鄰居,具有突出的請求的
unacquired鄰居被發送到Ceases。 這方法提供一種快速響應妥協，當鄰居沒有最初響應而
且期望最小化一個可能是已發出一個確認但還沒收到證實的停止的鄰居。 如果該指定的鄰
居的最大數沒能獲得，請求被無窮地重傳輸到全部unacquired鄰居。
2.3 Hello和Poll輪詢間隔

請求和確認信息包含Hello和Poll間隔的最小值。 由他和核心網關告知的最小數當前分別
是30和120秒。
收到的間隔要檢查上界以便防止其值無意義。 當前上界是分別定在120和480秒。 假使
某鄰居超出上界，則被認為是非法的并且不再發送要求達一小時。 這個允許去改正這種情
況，在另一處的網關正常運行直到那個網關自動地重新恢復而不必產生過多不必要的網絡信
息流通量。


實際的Hello與Poll間隔由第一次選擇由網關與它的對等網關報告的間隔的極值決定?？紤]
到可能網絡時延變化２秒容差被加到Hello間隔上，Poll間隔增加為Hello間隔的整數倍。
這導致32秒Hello與128秒Poll間隔。

如果一個響應Poll的更新沒有被收到,至多發送一個repoll (順序號碼相同)代替下一個已經安
排的Hello。
2.4鄰居中止

如果EGP進程通過Kill命令發送一SIGTERM信號,全部已經獲得的鄰居都發送Cease (停止）
命令。 Ceases在hello間隔內至多重復傳輸3次。 一旦全部具有任一個具有Cease - acks
的響應或者已發送三重復傳輸的Ceases，該進程終止。
2.5鄰居可達性

只有當前可達性判定被實現。 它的行為與在[中Mills 84a]推薦的有微小的變化。

應答移位寄存器被維護。 關于各個Poll or Hello命令發送一個零變換為移位寄存器。 如果
一個響應( I - H - U,更新或錯誤)得到正確的序號反應，零被一替代。 各個新命令發送之前
可達性通過檢查上移位寄存器四項判斷。如果該鄰居是可以達到的并且收到的響應< = 1,該
鄰居被認為不可達。 如果該鄰居被認為不可達并且收到的應答> =３,現在被認為可以達到
的。

一個鄰居后獲取之后被立即認為可以達到的,所以第一個來源于一個核心網關(一旦它認為
這個網關可以達到的)poll用一個更新回答。Polls不發送除非一個鄰居已經認為可以達到的
并且它沒有在它的最后的Hello I - H - U或Poll報文中建議它認為這個網關不可達。 這個
防止第一個Poll在一個down/up轉換以后被丟棄。這是重要的因為輪詢用于可達性判定。
遵循至少一獲取報文必須被接到,在第一個輪詢發送之前。 這將決定同位體不認為這個網關
停機。在第一個poll之前通常要求至少發送一個Hello。這段落的討論不同于[ Mills 84a],它
建議一個同位體按照獲取被認為停機并且一旦同位體被認為開機Polls就可能發送。這是唯
一偏離[ Mills 84a]的重要的之處。
由被認為不可達的同位體收到的Polls發送一個錯誤反應，它允許他們的可達性判定正確地
改進。
此舉是一個[Mills 84a]選項。

當一個鄰居變成不可達，利用它的全部路由從該路由表上刪掉。如果知道不能獲得鄰居的話
該不可達網關被停止并且嘗試獲得一個新鄰居。
如果知道已經獲得的全部鄰居，可達性判定延長30分鐘( [ Mills 84a]建議60分鐘)，在定時
不可達鄰居中止以后并且reacquisition每4分鐘嘗試一次。
目的在于減少不必要的網絡信息流通量。

如果三個連續的輪詢沒有收到正確的更新應答該鄰居被停止并且在４分鐘內嘗試獲得或
reacquisition一個替換。本規定防備鄰居發送不正確的更新數據格式。這些情況一度在測試
過程中出現。


2.6序號

序號是如同在[ Mills 84a]中推薦的方式處理。為各個鄰居維護單獨的發送和接收順序號。 發
送序列號被賦初值零并且在各個新Poll (非repoll)發送與不在其他的時間之前加１。發送序
列號用于全部命令。 接收順序號通過拷貝上次來源于一個鄰居的請求、Hello或Poll命令
維護。
本序號用于輸出更新。全部應答(包含錯誤應答)返回該剛才收到的報文的序號。


2.7過多命令的處理

如果在任一８分鐘之內從一個鄰居收到多于20命令，該鄰居被認為非法的,中止并且
reacquisition一小時。

在poll interval期滿之前(小于４秒網絡時延變化性容量)最多收到一一個repoll (相同順序號
碼)，用一個更新答復,其它則發送一個錯誤反應。當在響應中發送一個更新到的repoll時,
unsolicited [未經請求的位]沒有被設定,它不同于在[ Mills 84a]中的建議。

2.8不適當的Messages

如果證實從任一網關(巳知的或未知)收到Hello、I - H - U、Poll或更新也就是說進入
unacquired狀態,同步大概由于某種原因被淹沒。發送中止(協議違規)報文以避免與減少不必
要的網絡信息流通量。此舉是一個[Mills 84a]選項。


2.9缺省網關

缺省網關在EGPINITFILE中詳細說明。缺省路由(在Unix 4.2 BSD中的net 0)用于內核包轉
發，如果目的網絡沒有具體的路由。如果全部巳知的EGP鄰居不可達時，它提供結局級備
份。如果僅存在一個可用的EGP EGP鄰居時這個尤其有用,象在5.2.2節的ISI情況中那樣。

缺省路由在初始化時安裝并且在一個正確的EGP更新報文收到之后被刪除.如果全部已經獲
得的鄰居并無一個可以達到的那么它被重新安裝,如果在進程終止前路由超時而不存在已經
獲得并且可以達到的EGP鄰居。

因為缺省網關不會知道比通過EGP獲悉的更多路由選擇信息，所以一個正確的EGP更新報
文收到后它被刪除。 如果沒被刪除,全部轉到不可達網絡的通信量可能發送給Unix 4.2轉發
策略下面的缺省網關。

缺省網關將設置成一個標準地全路由核心網關而不是巳知的萬一所有的EGP gateways同時
停機時提供另一個備份的EGP鄰居網關。

⒊測試

在此簡短地描述一些在測試期間發生的有趣的情況。

不同的實現者對序號有不同的解釋。因此一些實現拒收具有不正確的序號的報文,導致對等
網關被宣布停機。
難題要點是該規格完全是文字報告式的，容易產生不一致、含糊和不完善的。[ Mills 84a]
的更多的格式說明已經除去這個含糊。

當測試響應發給一個鄰居網關不在同一網絡的接口的包的時候，回路產生了，因為兩個網關
重復地交換指出一個非法接口的錯誤報文。 該難題在于兩個網關在檢查地址之后，EGP消
息類型被之前發送錯誤應答。 通過不發送錯誤響應除非可以確信該報文不是一個錯誤響應
本身來糾正。

曾經一個核心網關在更新報文中具有某種形式的數據錯誤引起他們被拒絕即使可達性正在
令人滿意地傳導。這導致全部路由超時。 解決方案是去計算不導致收到正確的更新的連
續的輪詢的數目，如果這號碼達到３去中止EGP，努力獲得一個替換網關。

由Mike Karels在伯克來報告的另一個使發生興趣的特性,由在MILNET和ARPANET具有多
網關兩者之間引起。每個ARPANET主機具有一個給定的gateway去用于訪問MILNET。如
果該EGP gateway是一個主機又是一個網關, EGP更新報文可能指出一個不同的
MILNET/ARPANET網關從該給定的一個。當host/gateway發生通過EGP報告的網關路由的
一個包時,它將收到一個去往它的給定的網關的重定向。 因此該MILNET網關能夠在由EGP
報告的網關和指派的網關兩者之間保持是交換式的。 當使用去其他的通過
MILNET/ARPANET gateways達到的網絡時類似東西出現了。
⒋將來的改進
4.1多獨立系統

當前獲得一個來自一個信賴的列表EGP鄰居的最大數的方式暗示全部鄰居位于同一個AS
中。 意思是他們全部隸屬于核心AS。更新路由表時,更新被獨立地對待沒有區別被建議路
由是對等體的AS的內部還是外部。 并且,路由選擇公制沒有參考源AS進行比較。

如果EGP用附加的除核心AS之外AS的管理，需要獲得列表上的全部鄰居以確保來自兩個
AS的網關總是能獲得。這導致一個不必要的額外的EGP通信量，如果為安全性獲取眾多的
鄰居。一個更可取的方法將是為每個AS持有單獨的被信賴的EGP gateways列表和獲得的
最大數。路由登記項需要持有源AS以便將優先權能夠給與來源于自己的AS的信息(看5.1.2
節)。

4.2接口監控

目前接口狀態僅在一個響應Poll的更新發送前檢查。 接口狀態應能夠更經常的進行監控并
且探測到一個變化時發送一個未經請求的更新。 這時改善EGP輪詢響應緩慢的一個方面。
這對于通過dial - in線路連接網絡具有特殊的重要性。
當上述的一個網絡撥入時,它的相關的接口將被標記為up但是直到該變化已經通過EGP傳
送之前它不會收到包。這對于未經請求的更新報文的情況將有所幫助，但是對于其他的非核
心網關為新路由選擇信息去輪詢核心EGP網關時依舊存在延遲。

開始認為這個情況可能對于內核EGP的實現有所幫助 但是該內核目前不通過中斷加入新
設備傳遞接口狀態改變。
如果這樣做，當一個接口狀態改變時可能象提供一個用戶級信號一樣簡單。


4.3網絡級狀態信息

目前網絡級狀態報告諸如IMP目的地不可達報文、不用來探測在EGP鄰居或其他的鄰居網
關的可達性方面變化。這個信息應該用于改善響應時間改變。


4.4內部網關協議接口

目前所有的AS內部路由選擇信息都是是靜態的，而且都是從初始化文件中選讀。內部路由
管理職能已經編寫以便它合理地便于動態內部路由更新連接一個IGP。通過分離的外部和內
部路由表這個變得更為方便。

輸出EGP Updates通過rt_NRnets ()正確地為內部路由表做好準備，不管是靜態的或動態內
部路由。
函數也提供檢查、增加、改變和刪除內部路由, i.e.，那就是說分別是rt_int_lookup (), rt_add (),
rt_change () and rt_delete ()。

一個IGP用當前數據結構的交互作用基本上包括三個功能∶用一個類似于...的rt_NRupdate ()
的函數更新內部路由表，制定輸出內部更新類似于去rt_NRnets (),超時interior routes類似于
rt_time)。

⒌拓撲問題
5.1拓撲約束和路由回路
5.1.1背景

EGP不是一個路徑選擇算法。 它僅僅能使外部鄰居去交換路由選擇信息，很可能需要通過
一個路徑選擇算法。 它不能傳遞充分的信息去防止路由回路，如果循環存在于拓撲之中
[ Rosen 82].

路由回路可能出現當兩個網關認為通過彼此存在達到一個第三網關的候選路由時。當第三網
關停機時，他們結束彼此指向，形成路由路由一個路由回路。 當前核心系統內部,回路通過
從零數到無限(國際互聯網絡網關站數直徑)解除。 這個(通常)工作的令人滿意因為GGP傳
送變化十分迅速，一旦變化出現路由選擇更新就被發送。
國際互聯網絡直徑是相當小的( 5)而且使用一個通用的距離公制,段數,。但是這個將來可能有
所改變。

用EGP,改變被遲緩地傳送。 雖然單個未經請求的NR報文可能發送,但是它不必要地直接地
傳遞給其他的需要間接收聽的網關。 還有,不同的AS的距離公制是完全獨立的，因此從零
數到無限不能總是時適用。

初始的提議將通過限制AS的拓撲成為樹狀結構以便不存在通過候選AS的多路由來防止路
由回路。 相同AS內部多路由被允許，如果內部路由選擇策略負責控制回路。

[ Mills 84b]注意到即使樹狀構形約束, "我們必須假定短暫的回路有時可能在核心系統內部
形成而且這個信息可能逃到其他的系統;然而,人們預期這個回路不會持續良久而且在核心系
統內部不久將被解除。因此一個非核心系統間回路可能持續直到第一個更新報文圓發送給其
他的系統之后全部回路探測已經被清除或直到可達性信息頁表超時,無論那一個首先出現"。

用初始簡單stub EGP systems，樹狀構形約束能夠達到目地。但是對于長期這個不提供充分
的強度。

[ Mills 83]建議一個方法，通過方法AS能夠動態地重新配置他們自己因此拓撲約束總是滿
足,沒有對單個" core " AS的需要。 一個AS擁有一個共享網絡而且它的鄰居AS用自己傳
導EGP。屬主將間接地傳遞上述的信息，象核心系統現在所做。如果擁有AS被定義去接近
于該樹狀構形根,所有的不規則的互連能夠形成一個適當的樹狀結構拓撲。 通過路由拓撲我
依照在路由選擇中通知的理解拓撲。存在其他物理連接是可能的，但是如果他們未被報告則
不會用于路由。每個AS最多只能用一個擁有共享網絡的AS傳導EGP。所有的不通過另一
個AS擁有的網絡傳導EGP的AS是子樹的根。它可能用擁有一個共享網絡的其他的AS傳
導EGP。這個"附件"將兩個子樹組合變成單個子樹，因此整個拓撲還是一個樹。 拓撲違規
能夠判斷，因為兩個不同的AS拓撲違規將報告他們能夠達到相同網絡。

上述的動態樹,可能有較佳的備份連接。在此情況下必須監視器失敗的連接以便路由能夠被
改回到較佳的連接，當服務被恢復時。

另一方面考慮是探測路由回路的可能性然后中斷他們。包生存時間( TTL)期滿可用于做這件
事情。如果一個診斷程序包懷疑有一個回路,諸如ICMP echo,能夠通過發送可疑的路由去證
實它是否是一個回路。如果探測到一個回路，可以通過該路由發送一個特殊的路由包，它指
示每個網關轉發該包之后去刪除該路由。新路由選擇信息的接受可能需要被推遲一段停工檢
修時間。 這方法需要為初始TTL做出明智的選擇。但是許多主機并沒有這么做。

5.1.2現行政策

鑒于總趨勢是增加網絡互連而且替換long - haul networks諸如ARPANET、WBNET (寬帶衛
星網絡)和公用數據網的有效性，樹狀拓撲約束通常是不受歡迎的。當前推薦的是限制的較
少的拓撲。
以下取自[ Mills 84b]。

EGP拓撲學模型∶

-一個獨立系統包含一組通過網絡連接的網關。 在該系統中的每個網關對于在它的系統
中的每個其他的網關必須是可以達到的，路徑僅包含在該系統中的網關。

-系統中的一個網關可以與在任一其他的系統中的網關一起運行EGP，只要通過的那個
EGP的路徑在第三系統中不包含一個它自己運行EGP的網關。

-"核心系統"不同于其它核心系統，由于只有它被允許去分布關于系統而不是它自己的可
達性信息。

-在每個系統中至少一個網關必須具有一個和在核心系統中的網關一樣的網絡。

-除了上面那些暗示不存在拓撲的或連通性約束。

一個網關將使用來源于它的配置(直接連接網絡)、它的系統的IGP、調用在下文中的S、(內
部網絡)與EGP (內部和外部網絡的鄰居系統)去構造它的路由表。信息如果與一個特殊的網
絡N出現沖突,他們將被如同下述那樣解決：

如果N直接連接到該網關,全部關于N的IGP與EGP報告被忽略不計。

如果N被IGP報告為S內部，被EGP報告為另一系統的外部或者內部，則該IGP報告
優先處理。

-如果N被EGP通告作為一個系統內部和另一系統外部,該內部report占主導地位。

- If N被使用EGP的相同系統的兩個或更多網關作為內部,該報告指定的最小的站數占主
導地位。

-在全部其他的情況中，最近的收到的報告占主導地位。

舊的信息可能來源于表的過時信息。

該臨時的模型提供一個可接受的自組織程度。
短暫的路由回路可能出現在系統之間,但是這些最后被舊的可達性信息中斷，因為這些信息
從列表中過時。 短暫的回路可能由于臨時的核心系統回路出現，由于當地的網絡位于多系
統該附加的回路可能存在看起來不會增加太大的危險性。

5.2當前ISI配置

一個ISI網絡配置的精簡版本顯示在圖表5 - 1中。
ISI - Hobgoblin能為在ARPANET和ISI - NET之間的核心ISI -網關夠提供一個備份網關功
能。ISI - Hobgoblin是一個運行Berkeley Unix 4.2.的VAX 11/750，該描述於這些報告EGP
實現運行在ISI - Hobgoblin上。

ISI - Troll屬于加利福尼亞大學古生物博物館在irvine網絡( UCI - ICS)上的一個分離網關。
完全的邏輯的網關包含ISI - Troll,該9600波特連接和UCI - 750A [ Rose 84]。ISI Troll運行
Berkeley Unix 4.1a由此不能運行EGP程序。 所以它是一個非路由網關。 UCI - ICS網絡的
存在必須通過ISI - Hobgoblin被通知給核心AS。 通過在EGPINITFILE中包含一個適當的
登錄項便可做到。

在ISI - NET上主機,包含ISI - Troll,具有靜態路由登錄項以指出ISI - Gateway作為除了UCI -
ICS和ISI - NET的全部網絡的第一個站點。

-------------------------------------------------
/ \
/ ARPANET \
\ 10 /
\ /
-------------------------------------------------
| | |
| | |
| | |
+-------------+ +-------------+ +---------------+
| ISI-PNG11 | | | | |
| Arpanet | | ISI-GATEWAY | | ISI-HOBGOBLIN |
| Address | | | | Vax 11/750 |
| logical | | Core EGP | | Unix 4.2 |
| multiplexer | | | | |
+-------------+ +-------------+ +---------------+
| | |
| | |
| | |
--------------- ----------------------------
/ \ / \
/ 3 Mb/s Ethernet \ / ISI-NET \
\ net 10 / \ 128.9 /
\ / \ /
--------------- ----------------------------
|
|
|
+--------------+
| ISI-TROLL |
| Vax 11/750 |
| Unix 4.1a |
| Non-routing |
| | |
| | 9600 | ISI-TROLL, UCI-750A
| | baud | and the link form a
| | link | single logical gateway
| | |
| UCI-750A |
| Vax 11/750 |
| Unix 4.2 |
+--------------+
|
|
|
----------------------
/ \
/ UCI-ICS \
\ 192.5.19 /
\ /
----------------------


Figure 5-1: Simplified ISI Network Configuration

EGP或者用ISI - Gateway或者ISI - NET越過ARPANET傳導。

5.2.1 EGP越過阿帕網

ISI - Hobgoblin即將通知ISI - Gateway越過ARPANET,由此該核心系統能夠達到ISI - NET
和UCI - ICS。

發自AS的外部到ISI與駛往UCI - ICS的包可能通過ISI Gateway、ISI - Hobgoblin與ISI -
Troll路由。 通過ISI - Gateway (或其他的核心EGP網關)額外的路程段是因為核心網關當前
不傳遞地址在他們的IGP報文中的間接鄰居外部網關
網關去網間連接協議)。 發源于UCI - ICS駛往外部AS的包可能通過ISI - Troll與ISI
Gateway路由。 因此該輸入與輸出包路徑是不同的。

發源于作為一個主機的ISI - Hobgoblin駛往外部AS的包可能通過在阿帕網上適當的網關路
由。

如果ISI - Troll、ISI - Hobgoblin與ISI - Gateway全部開機，UCI - ICS只得與外部AS通信。
依賴ISI - Gateway可能被淘汰，if ISI - Troll通過ISI - Hobgoblin路由包勝于ISI - Gateway。
然而,因為ISI - Hobgoblin主要地是一個主機而不是一個網關，當可能時寧愿ISI - Gateway
路由包。

ISI - Hobgoblin可能提供一個備分網關功能給ISI - Gateway因為它可能自動地轉到一個替換
核心EGP對等，如果ISI - Gateway goes down停機。
即使ISI - Hobgoblin正常地訪問核心系統，它可能達到ISI - NET，因為核心通過ISI - Gateway
優先權運用它的內部擁有路由。
為了在ISI - NET上hosts正確地路由輸出包，他們需要靜態的從ISI - Gateway到ISI -
Hobgoblin網關登錄項變化。 目前這些人工地完成。如果ISI - Gateway將要停機很長一段
時間時，這樣做才是適當的。

5.2.2 EGP越過ISI - NET

ISI - Hobgoblin即將通知ISI - Gateway越過它的間接相鄰ISI NET, ISI - Troll，由此該核心系
統能夠達到ISI - NET和UCI - ICS。

全部UCI - ICS外部分組路由選擇將通過雙向沒有站數ISI - Gateway通過ISI - Hobgoblin。
發源于作為一個主機ISI Hobgoblin駛往外部AS的包將通過ISI - Gateway雙向路由,而非
ARPANET接口,因此處理一個附加的路程段。

UCI - ICS只得與exterior AS通信，如果ISI - Troll與ISI - Gateway正在運行而且ISI -
Hobgoblin已經報告UCI - ICS的ISI - Gateway路由。 如果ISI - Hobgoblin停機,通信還是可
能的因為ISI - gateway (及其他核心網關)不會超時到其他鄰居的路由。
如果ISI - Gateway隨后停機，當它出現時它需要通過UCI - ICS路由的ISI - Hobgoblin重
新讀入。

通過ISI - NET而非ARPANET傳導EGP將為UCI - ICS提供更為可靠的服務，因為下列理
由∶ISI - Gateway被明確地設計為一個網關,它的運行時間應該多于ISI - Hobgoblin,除去可
能的額外路由站點是可取的, ISI - hobgoblin停機之后外部路由選擇信息將持續。 如果
ISI - Hobgoblin用于備份模式，新網關路由被人工地安裝在該主機之后EGP可能越過
ARPANET重新啟動。
所以, EGP越過ISI - NET被選為較佳的運行方式。

5.2.3潛在路由回路

因為ISI - Gateway和ISI - Hobgoblin他們兩個共同提供在ARPANET和ISI NET間的路由，
所以存在一個潛在路由回路。這些拓撲事實上違反初期的樹狀結構約束。所提供的ISI
Hobgoblin不同時與ISI - Gateway通過ISI NET和ARPANET傳導EGP,該網關甚至僅了解來
自共享EGP網絡的替換路由，來自其他網絡的則不知道。 因此一個回路不可能出現。 舉
例來說,如果EGP通過ISI - NET傳導, ISI - Gateway和ISI - Hobgoblin將知道通過彼此從ISI
NET到ARPANET的替換路由,但是他們不會知道該網關在ARPANET上的地址，所以不能
從ARPANET進入ISI - NET。 因此他們沒有充足的路由選擇數據在他們自己間去路由包。


5.3可能的未來配置
5.3.1去往UCI - ICS的網關

向UCI ICS提供的服務在安全性和性能方面的一個改進可以通過移動從ISI Troll到ISI -
Hobgoblin的UCI ICS接口完成。安全性將改善，因為該連接僅要求ISI - Hobgoblin和它的
ARPANET接口正在運行；性能將改善，因為額外的網關路程段可能的被除去。

這些還有將允許EGP越過ARPANET傳導，提供對運行EGP的替換核心網關的訪問。這些
將增加總是可靠地獲得一個EGP鄰居的機會。它也將為發源于作為一個主機的Hobgoblin
的駛往外部網絡的包去除這些額外的路程段,

這些配置變化會在將來的某一天完成。 最初沒有這樣做，因為ISI - Hobgoblin是試驗性的
而且停機比ISI -Troll更頻繁。
5.3.2動態轉到備份網關

ISI - Hobgoblin能為在ARPANET和ISI - NET之間的核心ISI -網關夠提供一個備份網關功
能，這在5.2.1節以注明。上述的備份網關可以變成一個公共的方法去提供更大的安全性。

目前對備份網關的改變是要求新的網關路由被人工地加入到ISI - NET的主機上。本節描述
一個當原始網關停機時為動態地完成這些轉換時所用的可能方式。

目標是能夠探測原始網關什么時候停機，用最低附加網絡通信量將在該局部網絡上的全部主
機轉換為備份網關。當它又出現時，主機應該還原為原始網關。

倡議的方式是僅為備份網關監控該原始網關狀態，當存在一個改變時為它通知全部新網關地
址主機。
5.3.2.1常用的操作

備份網關運行一個進程，它每30秒發送可達性-探針報文,諸如ICMP echoes,給原始網關而且
運用該應答去判斷EGP可達性。 如果該原始網關goes down一個
指出該備份網關地址的"網關-地址信息"被廣播
(更可取地多點傳送)給全部主機。 當該原始網關出現另一個指出該原始網關地址網關報文
時，它被廣播。
這些廣播應該在30秒間隔內進行四次，為了避免確認和宿主機地址的消息的需要。

每個主機將運行一個進程，傾聽網關-地址信息。如果一個不同的網關為了新地址建議改變
缺省網關項。
5.3.2.2主機初始化

當一個主機出現時，原始網關可能停機，所以它需要能夠決定它是否將要使用該備份網關。
該主機可能從一個靜態的初始化文件中讀取原始和備份網關地址。
它于是將設定它的缺省網關為原始網關而且發送一個
"網關-請求消息"給備份網關，請求當前網關地址。該備份網關將以一個網關-地址信息響應。
如果無應答被接到，該網關-請求應該在30秒間隔內重復傳輸三次。 如果無應答被收到，
該備份網關被假定停機而且該原始網關保持作為默認網關。

每當該備份網關出現，它廣播以一個網關-地址信息響應。

換句話說,一個廣播(或多點傳送)網關-請求消息可能
被定義為僅被網關響應。 備份網關-地址信息需要指出它是備份網關以便將來的請求不必廣
播。三次重傳應該被用。 但是該原始網關也需要廣播它的地址，每當它出現。
5.3.2.3什么時候原始而且備份兩者都停機

如果原始網關停機而且備份知道它停機,它將要廣播網關-地址信息指出該原始網關，萬一原
始網關出現。

除了備份可能不加警告停機外，而且原始在它之前出現。如果原始網關當它出現時廣播一個
網關-地址信息，是不可能的問題。否則,當主機使用備份網關時，他們每10分鐘應該發送
一個網關-請求消息。 如果無應答被收到它應該在30秒間隔內重復傳輸３次而且如果仍然
無應答該備份被假定停機而且原始網關被還原。

因此當原始網關在出現和正在被用時不發送網關-地址信息時，主機需要周期地發送消息。
有時候,諸如在ISI,原始網關通過不同的組織管理而且實驗特性沒能隨時增加。

5.3.2.4 Unix 4.2 BSD

一個難點是不存在規定internet廣播或多點傳送地址的標準方法。多點傳送地址是更可取的,
因為只有他們需要處理該報文(具有硬件多點傳送檢測接口是可用的)。至于Unix 4.2 BSD一
個Internet地址具有零本機地址是被指定為internet廣播地址。
然而,普通Internet地址政策是使用一個全1去指出一個播送功能。

在Unix 4.2 BSD systems上,網關和主機進程兩者都可能運行在用戶級以便不要求修改內核。

用戶數據報協議( UDP)套按字可能專留作主機-備份-網關通信。

超級用戶為發送和收到ICMP Echo報文訪問raw套按字需要稍微修改國際互聯網絡-族協議
轉換表。
⒍致謝

我向所有對本工程提供幫助的人們致以誠摯的感謝,特別是：提出的該工程Dave Mills，Jon
Postel的討論和鼓勵, Liza Martin提供初始EGP代碼, Berkeley提供" routed代碼, Mike Brescia
協助測試、Telecom Australia為我提供資金和ISI提供設備。
⒎參考資料
[Berkeley 83] "Unix Programmer's Manual", Vol. 1, 4.2 Berkeley Software
Distribution, University of California, Berkeley.

[Kirton 84] Kirton, P.A., "EGP Gateway Under Berkeley Unix 4.2", University
of Southern California, Information Sciences Institute,
Research Report ISI/RR-84-145, to be published.

[Mills 83] Mills, D.L., "EGP Models and Self-Organizing Systems" Message
to EGP-PEOPLE@BBN-UNIX, Nov. 1983.

[Mills 84a] Mills, D.L., "Exterior Gateway Protocol Formal Specification",
Network Information Center RFC904, April 1984.

[Mills 84b] Mills, D.L., "Revised EGP Model Clarified and Discussed",
Message to EGP-PEOPLE@BBN-UNIX, May 1984.

[Postel 84] Postel, J., "Exterior Gateway Protocol Implementation Schedule"
Network Information Center RFC890, Feb. 1984.

[Rose 84] Rose, M.T., "Low-Tech Connection into the ARPA-Internet: The
Raw-Packet Split Gateway", Department of Information and
Computer Science, University of California, Irvine, Technical
Report 216, Feb. 1984.

[Rosen 82] Rosen, E.C., "Exterior Gateway Protocol", Network Information
Center RFC827, Oct. 1982.

[Seamonson & Rosen 84]
Seamonson, L.J. and Rosen, E.C., "Stub Exterior Gateway
Protocol", Network Information Center RFC0, Jan. 84.

[Xerox 81] "Internet Transport Protocols", Xerox System Integration
Standard XSIS 028112, Dec. 1981.

RFC911——EGP GATEWAY UNDER BERKELEY UNIX 4.2 BERKELEY UNIX 4.2下的EGP網關