IPv6高速并行路由查找算法的研究.pdf

1、隨著Internet的發(fā)展，路由信息不斷增加，路由表不斷膨脹，路由查找問(wèn)題越來(lái)越成為影響網(wǎng)絡(luò)通信速度的瓶頸。未來(lái)IPv6的應(yīng)用將會(huì)使這一問(wèn)題更加明顯。而當(dāng)前已有的算法并不能夠很好地解決IPv6的路由查找問(wèn)題。 本文在詳細(xì)分析了已有的路由算法的基礎(chǔ)上，對(duì)當(dāng)前IPv6骨干路由器的路由表的特點(diǎn)進(jìn)行分析總結(jié)，從而根據(jù)IPv6路由表的特點(diǎn)設(shè)計(jì)了一套適合IPv6的并行查找框架。該框架由四路組成，其中三路是由占了路由前綴數(shù)量90％以上的長(zhǎng)度為

2、32，35，48的前綴組成，第四路采用TCAM，其中存放了除長(zhǎng)度為32，35，48外的其他前綴，TCAM為硬件實(shí)現(xiàn)，其查洵速度很快，不會(huì)影響并行框架的整體性能。對(duì)于32，35，48三路，本文設(shè)計(jì)了段表加偏移量表的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)了相應(yīng)的hash函數(shù)。由于該三路只要考慮確定長(zhǎng)度的路由前綴，避免了最長(zhǎng)前綴匹配問(wèn)題。該三路的路由查找只需要最多兩次的存儲(chǔ)器訪問(wèn)操作，并且可以在常量時(shí)間內(nèi)實(shí)現(xiàn)路由更新，存儲(chǔ)器的需求不到1Mbytes，且該需求受路由