基于負(fù)載均衡結(jié)構(gòu)的高速交換技術(shù)研究.pdf

1、數(shù)十年來(lái)，Internet在高速發(fā)展的同時(shí)也面臨著越來(lái)越多的挑戰(zhàn)。自2005年以來(lái)，業(yè)界逐漸意識(shí)到下一代Internet需要從根本上對(duì)當(dāng)前的Internet體系結(jié)構(gòu)進(jìn)行革新，其中包括全新的概念模型、功能組織以及相關(guān)支撐技術(shù)?；谶@一現(xiàn)狀，本論文以下一代Internet體系結(jié)構(gòu)研究為背景，以國(guó)家自然科學(xué)基金資助的下一代Internet體系結(jié)構(gòu)項(xiàng)目“單層用戶(hù)數(shù)據(jù)交換平臺(tái)體系結(jié)構(gòu)”為依托，重點(diǎn)研究下一代Internet的支撐技術(shù)之一--能夠適

2、應(yīng)自相似業(yè)務(wù)流的高速交換技術(shù)。
　　相對(duì)于傳統(tǒng)的交換結(jié)構(gòu)而言，張正尚教授等人提出的負(fù)載均衡結(jié)構(gòu)LB-BvN(Load Balanced Birkhoff-von Neumann switch architecture)在滿(mǎn)足未來(lái)的高速交換需求和對(duì)自相似業(yè)務(wù)流的適應(yīng)性上都具有突出優(yōu)勢(shì)。該結(jié)構(gòu)由兩級(jí)crossbar組成和必要的緩沖組成。其兩級(jí)crossbar均采用確定的、周期性連接模式，這種O(1)復(fù)雜度的crossbar連接模式排除

3、了算法調(diào)度時(shí)間對(duì)時(shí)槽長(zhǎng)度的影響，在數(shù)據(jù)包長(zhǎng)度一定的情況下，時(shí)槽長(zhǎng)度僅與端口速率有關(guān)，這意味著端口速率可以提高到微電子乃至光傳輸技術(shù)的極限，從而為高速數(shù)據(jù)轉(zhuǎn)發(fā)提供了可能。此外，其第1級(jí)crossbar能夠?qū)⒌竭_(dá)交換結(jié)構(gòu)的業(yè)務(wù)流均勻散布到中間緩存，使之能夠較好地適應(yīng)自相似業(yè)務(wù)流。
　　雖然負(fù)載均衡結(jié)構(gòu)能夠較好地滿(mǎn)足未來(lái)的交換需求，但數(shù)據(jù)包在其輸出端可能出現(xiàn)失序現(xiàn)象。數(shù)據(jù)包失序會(huì)導(dǎo)致TCP報(bào)文不必要的重傳和擁塞窗口不必要的縮減，從而導(dǎo)致

4、傳輸帶寬的浪費(fèi)和網(wǎng)絡(luò)利用率的下降。國(guó)內(nèi)外研究機(jī)構(gòu)對(duì)這一問(wèn)題展開(kāi)了廣泛的研究，然而現(xiàn)有解決失序問(wèn)題的方案或者復(fù)雜度較高，或者性能不夠理想。一方面，如果為解決數(shù)據(jù)包失序問(wèn)題的復(fù)雜度高于O(1)，則必然會(huì)使整個(gè)交換流程遲滯，從而損害了負(fù)載均衡結(jié)構(gòu)原本的高速交換能力；另一方面，若片面地為實(shí)現(xiàn)以O(shè)(1)復(fù)雜度解決失序問(wèn)題而付出過(guò)高的性能代價(jià)也是不可取的。
　　考慮到負(fù)載均衡交換結(jié)構(gòu)的優(yōu)良特性，本論文將其作為研究方向，重點(diǎn)研究能以全流程O(píng)(1

5、)復(fù)雜度解決數(shù)據(jù)包失序問(wèn)題且具有更優(yōu)交換性能的解決方案。
　　論文主要研究?jī)?nèi)容和結(jié)論如下：
　　(1)提出一種全流程復(fù)雜度均為O(1)的負(fù)載均衡交換結(jié)構(gòu)SLBA(Smart LoadBalanced switch Architecture)，SLBA通過(guò)引入crossbar的反向通信模式和“智能維序”的重排序機(jī)制使數(shù)據(jù)包在“恰好”不失序的時(shí)刻“離開(kāi)”交換機(jī)，從而以O(shè)(1)復(fù)雜度解決數(shù)據(jù)包失序問(wèn)題。理論分析和仿真實(shí)驗(yàn)均表明SL

6、BA是穩(wěn)定的且在低負(fù)載時(shí)(<80％)其時(shí)延性能優(yōu)于Byte-Focal。
　　(2)由于SLBA對(duì)各種時(shí)延戳的處理較為復(fù)雜且在交換結(jié)構(gòu)和線卡之間需要額外的通信，這使得在超大規(guī)模和多機(jī)柜交換環(huán)境中可能產(chǎn)生長(zhǎng)往返時(shí)間(Round Trip Time，RTT)問(wèn)題。為此，本文將Flow Splitter和Byte-Focal相結(jié)合分別提出CFSB(Combine Flow Splitter with Byte-Focal)和LB-IFS

7、(Load Balanced switch based on Implicit Flow Splitter)結(jié)構(gòu)。CFSB用顯式的Flow Splitter和VCQ(Virtual Central Queuing)緩沖模式替代Byte-Focal中的DTS(Dynamic Threshold Scheme)策略和VOQ(Virtual Output Queuing)緩沖模式，在線卡和交換結(jié)構(gòu)之間無(wú)需額外通信的前提下實(shí)現(xiàn)了全流程O(píng)(1)復(fù)

8、雜度且獲得了比Byte-Focal更優(yōu)的交換性能。但CFSB無(wú)法保證數(shù)據(jù)包離開(kāi)第1級(jí)crossbar時(shí)保持先入先出特性，這使得CFSB的第3級(jí)交換時(shí)延在某些流量環(huán)境中可能會(huì)惡化，同時(shí)相對(duì)于Byte-Focal，CFSB需要更大容量的重排序緩存。為解決這一問(wèn)題，本文提出基于隱式Flow Splitter和雙緩沖模式(Double-Buffering Mode，DBM)的負(fù)載均衡交換結(jié)構(gòu)LB-IFS，LB-IFS在保證全流程復(fù)雜度為O(1)

9、的前提下，避免了CFSB的這一問(wèn)題，同時(shí)獲得了更優(yōu)的時(shí)延性能。
　　(3)基于反饋機(jī)制的FTSA(Feedback-based Two-stage Switch Architecture)結(jié)構(gòu)是迄今為止理論性能最優(yōu)的負(fù)載均衡結(jié)構(gòu)，但其缺陷在于調(diào)度算法復(fù)雜度較高且要求算法在極短的時(shí)間內(nèi)完成。因此本論文從“開(kāi)源”和“節(jié)流”兩個(gè)角度來(lái)解決FTSA結(jié)構(gòu)所存在的問(wèn)題。所謂“開(kāi)源”方案即拓展調(diào)度算法的時(shí)域空間，使得調(diào)度算法能夠獲得更大的時(shí)間區(qū)

10、間；所謂“節(jié)流”方案即盡可能降低算法的復(fù)雜度，從而在降低算法耗時(shí)的同時(shí)，提高交換結(jié)構(gòu)的高速交換能力和可擴(kuò)展性。基于這種思想，本文首先提出“開(kāi)源”方案DFTS(Double-Feedback-based Two-stage Switch architecture)，DFTS通過(guò)“二次反饋”的方法使得調(diào)度算法與信元傳輸并行工作，從而有效拓展了調(diào)度算法的時(shí)域空間。
　　(4)為降低FTSA結(jié)構(gòu)現(xiàn)有算法的計(jì)算復(fù)雜度，本文通過(guò)將嵌入式系統(tǒng)中

11、的優(yōu)先級(jí)位圖算法PBA(Priority Bitmap Algorithm)與FTSA所采用的EDF(Earliest Departure First)算法相結(jié)合提出“節(jié)流”方案PB-EDF(PriorityBitmap-based Earliest Departure First)算法。PB-EDF算法繼承了PBA的兩個(gè)優(yōu)良特性：O(1)復(fù)雜度和確定的調(diào)度耗時(shí)。引入PB-EDF算法一方面能夠有效降低調(diào)度耗時(shí)，另一方面，更為重要的是在性

12、能優(yōu)異的反饋制交換結(jié)構(gòu)上實(shí)現(xiàn)了全流程O(píng)(1)復(fù)雜度。
　　(5)DFTS的算法調(diào)度特征使得PB-EDF無(wú)法與之協(xié)同工作，基于這一原因，本文提出交換性能略有降低但能與PB-EDF協(xié)同工作的FFTS(Front-Feedback-based Two-stage Switch architecture)結(jié)構(gòu)，F(xiàn)FTS采用“前置反饋”的方法有效拓展了算法的時(shí)域空間。作為這一思想的延伸，本文隨后通過(guò)引入一種2-錯(cuò)列對(duì)稱(chēng)(2-Staggere

13、d Symmetry connection pattern，2-SS)的crossbar連接模式提出改進(jìn)的交換結(jié)構(gòu)FTSA-2-SS(FTSA using2-Staggered Symmetry connection pattern)。FTSA-2-SS在獲得與FFTS等價(jià)交換性能的前提下可為調(diào)度算法拓展更大的時(shí)域空間。FFTS和FTSA-2-SS均可與PB-EDF算法協(xié)同工作，從而可同時(shí)在“開(kāi)源”和“節(jié)流”兩個(gè)角度協(xié)同解決FTSA所存