面向數(shù)據(jù)中心的高效以太網(wǎng)轉(zhuǎn)發(fā)算法研究.pdf

1、數(shù)據(jù)中心(Data Center, DC)是云計(jì)算的基礎(chǔ)設(shè)施，一個(gè)龐大的數(shù)據(jù)中心能夠搭載成千上萬(wàn)臺(tái)服務(wù)器通過(guò)網(wǎng)絡(luò)組成集群對(duì)外提供服務(wù)。按照轉(zhuǎn)發(fā)方式的不同，數(shù)據(jù)中心網(wǎng)絡(luò)(Data Center Network，DCN)中數(shù)據(jù)包的轉(zhuǎn)發(fā)可以分為IP多播(Multicast)轉(zhuǎn)發(fā)和MAC單播(Unicast)轉(zhuǎn)發(fā):對(duì)于IP多播轉(zhuǎn)發(fā)，在轉(zhuǎn)發(fā)過(guò)程中交換機(jī)需要記錄大量的多播組信息，而低端交換機(jī)的存儲(chǔ)空間是有限的，如果將多播轉(zhuǎn)發(fā)信息不存儲(chǔ)在交換機(jī)中而是

2、編碼存儲(chǔ)在數(shù)據(jù)包的包頭中，又會(huì)帶來(lái)額外的流量開(kāi)銷(xiāo)，降低帶寬的利用率，IP多播轉(zhuǎn)發(fā)面臨可伸縮性挑戰(zhàn);對(duì)于MAC單播轉(zhuǎn)發(fā)，由于MAC地址不像IP地址那樣易于匯聚，虛擬化技術(shù)的應(yīng)用使得MAC地址轉(zhuǎn)發(fā)表項(xiàng)爆炸性地增長(zhǎng)，并且虛擬機(jī)的開(kāi)關(guān)和遷移又導(dǎo)致MAC地址的更新非常頻繁，低端交換機(jī)有限的存儲(chǔ)空間導(dǎo)致DCN中MAC單播轉(zhuǎn)發(fā)面臨轉(zhuǎn)發(fā)表空間壓縮問(wèn)題。
　　本文針對(duì)IP多播轉(zhuǎn)發(fā)面臨的可伸縮性挑戰(zhàn)，提出兩種高效可伸縮的IP多播轉(zhuǎn)發(fā)算法:基于嵌入包頭

3、的輕量級(jí)布魯姆過(guò)濾器(in-packet Lightweight Bloom Filter，in-packet LBF)的IP多播轉(zhuǎn)發(fā)算法和基于嵌入包頭的比特位圖(in-packet bitmap，in-packet BMP)的IP多播轉(zhuǎn)發(fā)算法?；趇n-packet LBF的IP多播轉(zhuǎn)發(fā)算法將多播轉(zhuǎn)發(fā)樹(shù)的結(jié)點(diǎn)信息編碼存儲(chǔ)在嵌入包頭的輕量級(jí)布魯姆過(guò)濾器中，每一個(gè)中間交換機(jī)通過(guò)檢查包頭中的布魯姆過(guò)濾器來(lái)決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包，而邊界交換機(jī)通過(guò)

4、檢查一張存儲(chǔ)在交換機(jī)中的哈希表轉(zhuǎn)發(fā)數(shù)據(jù)包到本地服務(wù)器。相比于BF，LBF編碼存儲(chǔ)到包頭的節(jié)點(diǎn)更少，并且最后一跳轉(zhuǎn)發(fā)采用簡(jiǎn)單的哈希表查找比布魯姆過(guò)濾器更快。實(shí)驗(yàn)結(jié)果表明:與傳統(tǒng)的嵌入包頭的布魯姆過(guò)濾器(in-packet BloomFilter，in-packet BF)相比，LBF在流量泄露上減少了39.3％，在轉(zhuǎn)發(fā)信息的編碼長(zhǎng)度上減少了38.8％，在吞吐率上提高了98.7％;基于in-packet BMP的IP多播轉(zhuǎn)發(fā)算法將多播轉(zhuǎn)發(fā)樹(shù)

5、中交換機(jī)的端口編碼到嵌入包頭的比特位圖中，每一個(gè)交換機(jī)通過(guò)檢查數(shù)據(jù)包頭的比特位圖來(lái)決定是否從某個(gè)端口轉(zhuǎn)發(fā)數(shù)據(jù)包。相比于BF，BMP精確的轉(zhuǎn)發(fā)避免了假陽(yáng)性轉(zhuǎn)發(fā)帶來(lái)的額外流量開(kāi)銷(xiāo)，并且高效的布谷鳥(niǎo)哈希查找使得轉(zhuǎn)發(fā)吞吐率也有了明顯的提升。實(shí)驗(yàn)結(jié)果表明:與BF相比，BMP在流量泄漏率和編碼長(zhǎng)度上平均能夠減少4-6倍，并且轉(zhuǎn)發(fā)吞吐率也優(yōu)于BF。
　　針對(duì)MAC單播轉(zhuǎn)發(fā)面臨的轉(zhuǎn)發(fā)表空間壓縮問(wèn)題，本文提出了一種支持快速更新的可重用固定長(zhǎng)度編碼(

6、Reusable Fixed Length Coding，RFLC)，該編碼方法對(duì)不同規(guī)模的MAC轉(zhuǎn)發(fā)表選擇不同的固定長(zhǎng)度參數(shù)，該固定長(zhǎng)度參數(shù)對(duì)應(yīng)了固定長(zhǎng)度編碼集合，不同的MAC地址表項(xiàng)重用該集合中的編碼，從而使得這種編碼方法能夠選擇合適的固定長(zhǎng)度參數(shù)縮短編碼的長(zhǎng)度，并且這種方法使用布谷鳥(niǎo)哈希來(lái)提高轉(zhuǎn)發(fā)速率。實(shí)驗(yàn)結(jié)果表明:這種編碼方式相比于傳統(tǒng)的固定長(zhǎng)度編碼和聯(lián)合哈夫曼編碼，在編碼長(zhǎng)度上平均減少了1.03％-27.53％，在轉(zhuǎn)發(fā)數(shù)據(jù)包的