高速路由器的基本架構老師:林輝堂TermProject:SimulatefiveIPaddresslookupschemesP76921552林東俊P76921104蘇正建1:Introduction網際網路中的路由器(router)其主要的工作便是將所接收到的封包(packets)轉送至目的地或是下一個轉送點.當路由器接收到封包後便針對該封包標頭(IPheader)的目地位址欄位(destinationIPaddressfield)來和自己內部的路由表(routingtable)進行比對以確定該封包要往何處轉送,此一動作稱之為路由位址查詢(addresslookup).進幾年來由於網路快速的發展,骨幹網路路由器(backbonerouter)每秒所須處理的封包數目越來越多,如現今的OC-192便可傳送每秒高達10Gbit,所以骨幹網路的路由器便須有快速處理封包的能力,相對的路由器在做路由位址查詢(addresslookup)的處理速也必需滿足該鏈結的速度(linkspeed).此報告主要是針對近幾年來許多研究人員相繼的發表出許多的路由位址查詢演算法(addresslookupalgorithm)進行模擬,其中包含Binarytrie[1],Path-Compressiontrie[1],SmallForwardingTableforFastIPLookup[4],IPLookupUsingMultiwayandMulticolumnSearch[2],AfastIProutinglookupschemeforgigabitswitchingrouters[3]等五種方式.另外我們在網路上找到一個有關收集BGPtable的網站[5],從中取出三個大小不同的BGPtable(Mae-east:28878,Oix80k:89088,Oix120k:120635entries).利用此三個BGPtable對上述五個方式進行記憶體使用度,路由查詢時間進行的模擬.報告中的第二部分章節主要是利用該三個BGPtable分別對此五種路由查詢演算法進行模擬,第三部分章節主要是利用Oix120ktable分析此五種方式的優劣(因為現今的骨幹網路路由表所包含的entries數通常已高達數十萬筆),並且歸納出一些我們在實作上所遇到的一些問題和現今的一些文章皆比較沒探討到的路由表更新(update)問題.:SimulationABinaryTrieThebinarytrieisthebasicdatastructureusedinmostofIPlookupalgorithms.Thebinarytrieisinfactabinarysearchtreeusingthebitvalue(0or1)toguidethesearchmovingtowardtheleftortherightpartofthetree.Eachtrienodehastheleftandrightpointerspointingtoitsleftandrightsub-tree.Figure1showsabinarytrierepresentingasetofprefixesofaforwardingtable.P1*P20101*P3100*P41001*P510111Figure1:AbinarytrieforasetofprefixesP1P2P3P4P5P2inFig1isatlevel4andrepresentsalladdressbeginningwiththesequence0101.Thenodethatcorrespondtoprefixesareshowninadarkershade;thesenodeswillcontaintheforwardinginformation(next-hop).Inabinarytrie,prefixesarenotonlylocatedatleavesbutalsoatsomeinternalnode,thismeansthepacketdestinationIPaddressmaymatchmorethanoneprefixinthisforwardingtable(binarytrie).Forexample,ifapacketincomingwhichdestinationIPaddressis10011,itwillmatchP3(100*)andP4(1001*),butwejustchoicetheP4forthispacketlongestprefixmatching(LPM).E