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

1、數(shù)據(jù)中心(Data Center, DC)是云計(jì)算的基礎(chǔ)設(shè)施，一個(gè)龐大的數(shù)據(jù)中心能夠搭載成千上萬臺服務(wù)器通過網(wǎng)絡(luò)組成集群對外提供服務(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ā):對于IP多播轉(zhuǎn)發(fā)，在轉(zhuǎn)發(fā)過程中交換機(jī)需要記錄大量的多播組信息，而低端交換機(jī)的存儲空間是有限的，如果將多播轉(zhuǎn)發(fā)信息不存儲在交換機(jī)中而是

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

3、的輕量級布魯姆過濾器(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ā)樹的結(jié)點(diǎn)信息編碼存儲在嵌入包頭的輕量級布魯姆過濾器中，每一個(gè)中間交換機(jī)通過檢查包頭中的布魯姆過濾器來決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包，而邊界交換機(jī)通過

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

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

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