ＭＥＤ欺騙與域間出口選擇

 收稿日期：2008-01-09；

修回日期：2008-03-20

基金項目：國家自然科學基金資助項目(60572082)



作者簡介：張衛(wèi)國(1973-)，男，黑龍江寶清人，博士研究生，主要研究方向為計算機網絡體系結構、路由協(xié)議（zwg@csnet1.cs.tsinghua.edu.cn)；

吳建平(1953-)，男，教授 博導，博士，主要研究方向為計算機網絡體系結構、高性能路由和交換、形式化協(xié)議一致性測試理論及其技術；

尹霞(1972-)，女，副教授，碩導，博士，主要研究方向為計算機網絡體系結構、形式化協(xié)議一致性測試理論及其技術.

(清華大學 計算機科學與技術系 北京 100084)

摘要：BGP（邊界網關協(xié)議）是目前用于廣域網中最主要的域間分布式動態(tài)路由協(xié)議，具有豐富的路由控制機制。BGP MED（multi-exit-disc）屬性的正確使用可以避免熱土豆路由和MED振蕩。提出了一種稱之為MED欺騙的路由策略技術，用于實現(xiàn)域間的出口選擇。詳細闡述了MED欺騙的原理與具體策略，并對其進行了優(yōu)化，最后利用仿真軟件加以驗證。

關鍵詞：熱土豆路由； 邊界網關協(xié)議； MED欺騙； 域間出口選擇； 仿真

中圖分類號：TP393

文獻標志碼：A

文章編號：1001-3695(2008)10-3136-03

MED cheat and inter-domain egress selection

ZHANG Wei-guo WU Jian-ping YIN Xia

(Dept. of Computer Science Technology Tsinghua University Beijing 100084 China)

Abstract:At present，border gateway protocol is a mostly dynamic distributed and inter-domain routing protocol used in WAN it has plenty of routing control mechanisms.The inappropriate using of the MED（multi-exit-disc） attribute commonly induces to hot-potato routing and the persistent MED oscillation．This paper presented a routing policy technology called MED cheat to realize the inter-domain egress selection. It explicitly expatiated on the principles and concrete policy of MED cheat and optimized the way of MED cheat. In conclusion validated the strategy by using the simulation software.

Key words：hot-potato routing; border gateway protocol(BGP); multi-exit-disc(MED) cheat; inter-domain egress selection; simulation

邊界網關協(xié)議（border gateway protocol，BGP）是目前因特網中惟一使用的域間路由協(xié)議。BGP采用復雜的路徑決策算法來決定最優(yōu)路徑并更新BGP RIB和IP RIB，這種決策算法依賴于BGP屬性和參數(shù)。BGP采用字典序的順序比較方式來比較這些屬性和參數(shù)，當排列在前面的屬性值等價時，BGP的路徑決策通常會依賴于域內路由的度量值，這就是所謂的最近出口（closest-exit）或者熱土豆選路，它是目前最普遍的域間選路模式。然而由于熱土豆路由具有局限性、分裂性和費解性等特性[1]，其引起的路由振蕩危害是非常普遍的。如何解決熱土豆路由問題，實現(xiàn)AS的最優(yōu)出口選擇一直是目前的研究熱點。

要解決熱土豆路由問題，目前提出了兩類方法，即改進機制法與更改策略法。改進機制法指的是改進BGP現(xiàn)有機制，去除熱土豆路由機制，依靠其他機制來實現(xiàn)BGP路徑決策算法；更改策略法指的是提出某些制定策略上的限制，使得制定出來的策略要么能夠完全消除熱土豆路由，要么能夠克服熱土豆路由的局限性。由于改進機制法要改進BGP的現(xiàn)有機制，實施難度大，難以大規(guī)模部署。而更改策略法由于不改變BGP的現(xiàn)有機制，只需要制定合理的策略，易于實現(xiàn)，是目前解決熱土豆路由的主要方法。 

更改策略法有兩種常用的實現(xiàn)方式，一種是采用冷土豆路由方式[2]，通過對EBGP鄰居設置不同的MED值來避免出現(xiàn)熱土豆路由現(xiàn)象；另一種是調整IGP度量值方式，這種方式不是主動地消除熱土豆路由現(xiàn)象，而是通過調整IGP的度量值來盡量減少熱土豆路由的局限性，典型的方法為固定優(yōu)先級路由和TIE路由[1，3]（the tunable interdomain egress selection mechanism）。因特網是由不同的AS組成并且運行著不同的路由策略。為了防止路由選擇振蕩，不同運營商的AS間常歸零BGP MED值，因此AS間即使設置了冷土豆路由，也常常無法生效。而調整IGP度量值方式涉及到網管系統(tǒng)的改進，一方面要求網管系統(tǒng)實時計算到不同出口的IGP度量值；另一方面還需要網管系統(tǒng)根據規(guī)則來動態(tài)地更改IGP度量值。實施較為復雜，并且只是在一定程度上避免了熱土豆路由的局限性，無法從根本上杜絕熱土豆路由的危害。

本文提出了一種新型的更改策略法來避免熱土豆路由現(xiàn)象。其核心思想是在AS內采用MED策略，即IBGP間通過設置不同的MED值來實現(xiàn)針對不同的前綴指定相對固定的自治系統(tǒng)出口，這種方式稱之為MED欺騙技術。MED欺騙技術實際上是一種AS內部的冷土豆路由方式，由于只在AS內部使用，簡單靈活，可以有效地避免熱土豆路由。

1域間出口選擇 

BGP域間出口選擇問題是路由器如何為每個目的地址前綴來選擇ASBR出口的問題。文獻[1，3] 列出了常用的三種方案：熱土豆路由、固定優(yōu)先級路由和TIE路由。

熱土豆路由是指不使用MED或其他屬性來選擇最佳出口路徑的路由策略。嚴格來說，熱土豆路由應是指在不采用MED屬性或MED值相等的情況下，BGP依靠IGP度量值來進行選路的方式，它是目前最常用的域間出口選擇技術。文獻[1，2，4~7]描述了熱土豆路由的原理、危害和解決方法。其中文獻[1]詳細討論了熱土豆路由的危害，指出了熱土豆路由具有一定的局限性、分裂性和費解性。局限性是指熱土豆路由機制只是規(guī)定了一種特殊的機制而沒有提供更多的功能選擇；分裂性是指有時IGP度量值很小的變化也會引起流量很大的變化，從而導致長時間的收斂延遲和大量的BGP更新消息；而費解性是熱土豆路由強制結合IGP和BGP兩種協(xié)議，違反了協(xié)議獨立性原則。采用MED屬性來避免熱土豆路由就稱為冷土豆機制，但冷土豆機制由于大部分AS普遍在ASBR（autonomous system border router）入口處實行BGP MED歸零策略而無法生效。

固定優(yōu)先級路由是指為每個路由器配置一個固定優(yōu)先級的路由出口，這樣對于每個目的路由，路由器就會選擇具有最高優(yōu)先級的路由出口。固定優(yōu)先級路由要求建立所有入口路由器到出口路由器的隧道，如利用MPLS LSP方式建立隧道。網絡管理者靜態(tài)地指定這些隧道的優(yōu)先級，每個入口路由器選擇出口路由器依賴于靜態(tài)設置的優(yōu)先級，而不受內部網絡事件的影響。這種方式可以避免熱土豆的路由振蕩問題，但其實現(xiàn)方式不靈活，需要入口與出口間配置專用隧道，而且需指定不同的優(yōu)先級。在極端情況下，當出口不可達路由器時會切換到次優(yōu)先級的出口。

TIE路由是指一種介于熱土豆路由與固定優(yōu)先級路由之間的可調參數(shù)路由。傳統(tǒng)的熱土豆路由機制完全依靠IGP度量值的大小來決定出口；而TIE機制通過調整參數(shù)來改變出口選擇變化的尺度，只有當IGP度量值變化到一定程度時才會改變出口。ITE路由機制靈活，能夠有效減少熱土豆路由的影響，但實現(xiàn)較為復雜，需要修改網管軟件，拓撲變化時需要實時地計算參數(shù)并動態(tài)地調整路由器。

2MED欺騙技術

本章提出了一種新的域間出口選擇技術，其主要思想是綜合冷土豆路由和固定優(yōu)先級出口路由兩種技術來實現(xiàn)域間出口的選擇。傳統(tǒng)冷土豆路由是在AS間設置不同的EBGP MED值，而MED欺騙技術利用入口與出口ASBR間配置IBGP MED的路由策略來實現(xiàn)固定優(yōu)先級出口的選擇。

MED是不可傳遞的BGP屬性，AS間設置不同的MED值，可以影響相鄰AS的路由策略，多用于出口。由于MED屬性可在IBGP間傳遞，在BGP等價情況下可以在入口與出口ASBR間設置不同的MED值來實現(xiàn)固定優(yōu)先級出口的選擇。本文采用與文獻[1]相同的例子，如圖1所示。對于正常情況下的路徑P來說，AS0選擇A出口。當鏈路CD出現(xiàn)故障時，熱土豆路由則會選擇B出口；固定優(yōu)先級路由則仍然會選擇A出口。而TIE路由則會依賴于可調參數(shù)的設置，這里設置可調參數(shù)為2，如果拓撲變化后與變化前的鏈路度量值之比≤2，則會依然選擇原出口；如果比值≥2，則會選擇新的出口。此例由于（5+4）/2 ≥2，選擇新的出口B。

如果采用MED欺騙技術，需要在入口與出口ASBR間運行IBGP并設置不同的MED值。此例中，設置MEDAC=100，而MEDBC=200，由于MEDAC

2.1MED欺騙策略

與傳統(tǒng)的固定優(yōu)先級路由相比，MED欺騙由于不用設置相應的隧道及指定隧道度量值，只需在入口與出口ASBR間設置相應的MED值，實現(xiàn)較為簡單。但是如果出口數(shù)目較大時，就會帶來MED值如何選擇的問題。因此需要從全局的角度來設計MED欺騙策略。

設路徑P的AS出口有M個，符號Ni表示出口節(jié)點的第i個出口節(jié)點，則這些出口可用N1，N2，…，Nm表示。對于路徑P實現(xiàn)固定優(yōu)先級出口，可設N1為主出口，N2為第二備份出口，N3為第三備份出口，依此類推，Nm為第m備份出口。總的MED欺騙策略規(guī)劃如下：N1出口對其余的m-1個出口作MED欺騙，設置MED為10，表示為MED(N1)=10；N2出口對其余出口作MED欺騙，設置MED為20；表示為MED(N2)=20；依此類推，Nm出口對其余出口作MED欺騙，設置MED為m×10，表示為MED(Nm-1)= (m-1)×10。由于N1的MED值最小，N1節(jié)點為第一主出口，依此類推，Nm為第m備份出口。MED欺騙策略實現(xiàn)了固定優(yōu)先級出口的選擇，達到了主備分明、順序備份的作用。

2.2MED欺騙策略優(yōu)化

MED欺騙策略需要每個出口配置m-1個路由圖，m個出口共需要配置m×(m-1)個路由圖，配置較為繁瑣，需要進一步簡化。

考慮兩個出口Ni和Nj，i

3仿真實驗

3.1仿真環(huán)境

本文利用仿真軟件對熱土豆路由、MED欺騙策略進行了對比仿真。仿真環(huán)境如圖2所示，AS1~AS3為過渡AS，AS0、AS4之間運行對時延敏感的重負載視頻業(yè)務，AS0通告100條BGP路由，AS4通過過渡AS2、AS3學到這些路由。AS1中節(jié)點10、11、12、13、14、15為ASBR路由器，與外部AS0、AS2、AS3采用EBGP連接，內部采用IBGP連接，并在AS內部啟用OSPF協(xié)議作為IGP。

3.2運行仿真

首先采用熱土豆路由策略進行仿真，仿真條件設置為60 s時依次中斷AS1內部幾條主要鏈路，100 s時恢復中斷鏈路。其次，在完全相同的仿真情況下分別進行MED欺騙及其優(yōu)化仿真。

在AS4的ASBR路由器設置仿真探針，分別采集三種情況下的BGP報文流量和收斂時間等數(shù)據。

3.3仿真結果分析

圖3為AS4內BGP路由器在熱土豆路由、MED欺騙及MED欺騙優(yōu)化三種情況下的BGP仿真結果。從此結果可以看出：

a）BGP路由穩(wěn)定時（0~60 s），BGP流量非常小。

b）路由拓撲發(fā)生變化時（60~100 s），導致AS1內OSPF和BGP路由振蕩，即引起熱土豆路由效應，從而影響其他AS振蕩。本實驗中AS4內BGP路由器收到大量的BGP流量，三種情況下BGP報文最大流量都在100 bps以上。

c）MED欺騙雖然可以實現(xiàn)固定出口，但與熱土豆路由相比，并沒有加速BGP收斂，其BGP流量反而有所增大。如圖3顯示，熱土豆路由最高速率為108.3 bps，MED欺騙為120.6 bps，MED欺騙優(yōu)化則為102.2 bps。這是因為MED欺騙使用了MED屬性增加了新的開銷。而MED欺騙優(yōu)化由于優(yōu)化而減少了BGP開銷，既做到了固定出口、減少路由振蕩，又達到了資源優(yōu)化和配置簡化的目的。

MED欺騙實現(xiàn)了固定域間優(yōu)先級出口選擇機制，可以明顯地改善熱土豆路由問題；同時MED欺騙機制還可以實現(xiàn)負載均衡，為某些路由設置一些主備域間出口，為另一些路由設置另外一些主備域間出口，這樣就可以達到主備分明、順序備份、負載均衡的目的。雖然MED欺騙機制可以明顯地改善網絡性能，但

是其也有一定局限性，具體表現(xiàn)為：與熱土豆路由機制相比，MED

欺騙選擇的固定域間出口可能是次優(yōu)路徑，極端情況下，當主出口失效、重新選擇域間出口時，仍然引起B(yǎng)GP路由振蕩。

4結束語

本文在分析BGP域間出口選擇問題的三種機制的基礎上，提出了一種新型的域間出口選擇技術——MED欺騙。其主要思想是綜合冷土豆路由和固定優(yōu)先級出口路由兩種技術來實現(xiàn)域間出口的選擇。詳細地闡述了MED欺騙的原理與具體策略，并針對其配置繁瑣問題進行了MED欺騙策略優(yōu)化。本文還利用仿真軟件對熱土豆路由、MED欺騙及其優(yōu)化進行了仿真對比分析，驗證了該策略的正確性。

但使用MED欺騙會導致次優(yōu)路由的產生，因此如何綜合考慮IGP、MED欺騙來實現(xiàn)基于MED欺騙的最優(yōu)出口選擇是筆者下一步研究的方向。

參考文獻：

[1]TEIXEIRA R，GRIFFIN T，RESENDE M，et al.TIE breaking:tunable inter-domain egress selection[J].IEEE/ACM Trans on Networking，2007，15(4):761-774.

[2]TEIXIRA R SHAIKH A GRIFFIN T，et al.Dynamics of hot-potato routing in IP networks[J]. ACM SIGMETRICS Performance-Evaluation Review 2004，32(1):307-319.

[3]LIU Ya-ping GONG Zheng-hu ZHAO Feng. RTF_TIE: a tunable interdomain in-egress selection algorithm robust to transient link fai-lures[C]//Proc of Workshop on High Performance Switching and Routing.Poznan:IEEE，2006:279-286.

[4]GRIFFIN T G SHEPHERD F B WILFONG G. Analysis of the MED oscillation problem in BGP[C]//Proc of the 10th IEEE International Conference on Network Protocols. Washington DC: IEEE Computer Society 2002:90-99.

[5]CERAV-ERBAS S，DELCOURT O.The interaction of IGP weight optimization with BGP[C]//Proc of International Conference on Internet Surveillance and Protection. Washington DC: IEEE Computer Society 2006:91-99.

[6]AGARWAL S NUCCI A BHATTACHARYYA S. Controlling hot potatoes in intradomain traffic engineering Report RR04-ATL-070677[R].[S.l.]:Sprint ATL，2004.

[7]TEIXEIRA R，SHAIKH A，GRIFFIN T et al. Network sensitivity to hot-potato disruptions[C]//Proc of Conference on Applications Technologies Architectures and Protocols for Computer. New York: ACM Press 2004:231-244.