跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.80) 您好!臺灣時間:2024/12/08 23:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張益銘
研究生(外文):Chang, Yi Ming
論文名稱:軟體定義網路中藉由建立初始路由規則樹有效率減少路由規則使用之演算法
論文名稱(外文):An Algorithm of Construction of Default Rule Tree for Efficient Utilization of Routing Table in Software-Defined Network
指導教授:蔡明哲蔡明哲引用關係
指導教授(外文):Tsai, Ming Jer
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:104
語文別:英文
論文頁數:19
中文關鍵詞:路由規則樹有效率路由規劃
外文關鍵詞:Default Rule TreeEfficient Routing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:226
  • 評分評分:
  • 下載下載:32
  • 收藏至我的研究室書目清單書目收藏:0
由於在軟體定義網路中路由規則表是個相當珍貴的資源,導致如何解省其使用是許
多人研究的方向。 文章當中,我們藉由建立一棵新的路由規則樹取代舊的最短路
徑路由規則樹來幫助減少我們設計一個減少路由規則表使用的路由演算法。 我們
演算法針對的對象是在資料中心中小流量的資料傳遞 (佔總體資料流比例85%),並
且可將釋放出來的路由表空間提供給大流量資料流使用,以提升整體網路效能。
我們設計此樹的設計理念是能夠讓此樹當成高速公路做路由規劃, 使用此樹所走得
路徑不需要增加多的路由規則來傳遞封包。 最後既然大家都能藉由此樹來做封包
傳遞, 也有可能造成其傳遞路徑的變長,因此最後我們將增加使用者的路由長度限
制。
關鍵字:路由規則樹, 有效率路由規劃
Efficient utilization of routing table is an major issue in software-defined network(SDN)
due to the high price of the lookup routing table. In this paper, we focus on mini-
mizing the usage of TCAM of mice flows (85 percentage overall) in the data center.
The liberated spaces of the routing table by the algorithm could be use for increasing
the throughput of the network by other traffic engineering functions. First of all, we
provide a routing policy is to reuse the default rule as many as possible in order to
decrease the TCAM table size. Next, different from the original default tree, which
is built as a shortest path tree, we construct a new default rule tree called CDRT
tree which could efficiently reuse by the routing policy. Further more, the tree is con-
structed by using linear optimization model. At last, we evaluate the performance of
CDRT using Bcube topology, and compare with two routing policy. One is shortest
path routing, which is the original routing policy for mice flows, the other is to reuse
shortest path tree for routing. At last, avoiding the routing path overstretch because
of the reuse of the routing method, we would set length limitation on the routing
path.
Keywords: Default Rule Tree, Efficient Routing.
Contents
Contents ii
List of Figures iv
List of Tables v
1 Introduction 1
2 Related Work 5
3 Construction of Default Rule Tree Problem 6
4 The Algorithm
4.1 The Integer Program . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
8
10
5 Simulations
5.1 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Results for CDRT without traverse limitation . . . . . . . . . . . . .
5.3 Results for CDRT with Routing Limitation L . . . . . . . . . . . . . 12
12
12
16
6 Conclusion 17
Bibliography
[1] B. experience with a globally-deployed software defined wan, “Sushant jain,” in
SIGCOMM, Proceedings of the ACM SIGCOMM 2013, 2013.
[2] X.-N. Nguyen, D. Saucez, C. Barakat, and T. Turletti, “Optimizing rules place-
ment in openflow networks: trading routing for better efficiency,” in ACM
HotSDN, 2014, pp. 127–132.
[3] N. Bitar, S. Gringeri, and T. J.Xia, “Technologies and protocols for data center
and cloud networking,” IEEE Communications Magazine, vol. 51, no. 9, pp.
24–31, 2013.
[4] R. Cohen, L. Lewin-Eytan, J. S. Naor, and D. Raz, “On the effect of forwarding
table size on sdn network utilization,” in INFOCOM, 2013 Proceedings IEEE.
IEEE, 2014, pp. 1734–1742.
[5] N. Kang, Z. Liu, J. Rexford, and D. Walker, “Optimizing the ”one big switch”
abstraction in software-defined networks,” in ACM CoNEXT, 2013 Proceedings
of the ACM conference, 2013, pp. 13–24.
[6] X.-N. Nguyen, D. Saucez, C. Barakat, and T. Turletti, “Officer: A general op-
timization framework for openflow rule allocation and endpoint policy enforce-
ment,” in INFOCOM, 2015 Proceedings IEEE. IEEE, 2015, pp. 478–486.
[7] S. Agarwal, M. Kodialam, and T. V. Lakshman, “Traffic engineering in software
defined networks,” in INFOCOM, 2013 Proceedings IEEE. IEEE, 2013, pp.
2211–2219.
[8] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data
centers in the wild,” in IMC ’10 Proceedings of the 10th ACM SIGCOMM con-
ference on Internet measurement. ACM, 2010, pp. 267–280.
[9] Garg, Naveen, Knemann, and Jochen, “Sdn and openflow for dynamic flex-grid
optical access and aggregation networks,” IEEE, pp. 864–870, 2014.
[10] S. Luo, H. Yu, , and L. M. Li, “Fast incremental flow table aggregation in
sdn,” in 2014 International Conference on Computer Communication and Net-
works(ICCN), 2014, pp. 1–8.
[11] H. G. BADR and S. PODAR, “An optimal shortest-path routing policy for net-
work computers with regular mesh- connected topologies,” IEEE Transactions
on Computers, vol. 38, pp. 1362 – 1371, 1989.
[12] C. W. Ahn and R. S. Ramakrishna, “A genetic algorithm for shortest path rout-
ing problem and the sizing of populations,” IEEE Transactions on Evolutionary
Computation, vol. 6, pp. 566–579, 2002.
[13] J.-R. Jiang, H.-W. Huang, J.-H. Liao, and S.-Y. Chen, “Extending dijkstra’s
shortest path algorithm for software defined networking,” in IEEE Network Op-
erations and Management Symposium, 2014, pp. 1–4.
[14] S. Cicerone, G. DAngelo, G. D. Stefano, and D. Frigioni, “Partially dynamic ef-
ficient algorithms for distributed shortest paths,” Theoretical Computer Science,
vol. 411, pp. 1013–1037, 2010.
[15] N. Kang, Z. Liu, J. Rexford, and D. Walker, “Application-aware aggregation
and traffic engineering in a converged packet-circuit network,” in National Fiber
Optic Engineers Conference 2011, 2011.
[16] Y. Kanizo, D. Hay, and I. Keslassy, “Palette: Distributing tables in software-
defined networks,” in INFOCOM, 2013 Proceedings IEEE. IEEE, 2013, pp.
545–549.
[17] R. E. Tarjan, “Finding optimum branchings,” Networks, vol. 7, pp. 25–35, 1977.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top