近年來(lái)，隨著互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，骨干網(wǎng)路由表?xiàng)l目數(shù)快速增長(zhǎng)，給路由表的存儲(chǔ)帶來(lái)了很大的壓力，一種有效的解決方案是采用路由表壓縮技術(shù)。同時(shí)，骨干網(wǎng)的鏈路速率也在不斷提高，對(duì)路由表查找速度提出了更高的要求。此外，各種新應(yīng)用使得互聯(lián)網(wǎng)的動(dòng)態(tài)特性增強(qiáng)，導(dǎo)致路由表更新越來(lái)越頻繁，而且呈現(xiàn)出突發(fā)性，這就要求路由表在實(shí)施壓縮和提高查找速度的同時(shí)，必須具有快速增量更新的能力。本文圍繞這三個(gè)問(wèn)題展開(kāi)研究，取得了如下成果： (1)針對(duì)一些路由器無(wú)法容納飛速增長(zhǎng)的路由表的問(wèn)題，采用社會(huì)學(xué)中種子選舉的思想，提出了兩種壓縮率高、壓縮速度快、增量更新快、重壓縮周期長(zhǎng)的路由表壓縮算法；針對(duì)前綴重疊給查找和更新帶來(lái)諸多困難的問(wèn)題，提出了一種構(gòu)建最優(yōu)的無(wú)重疊路由表的壓縮算法；針對(duì)已有路由表壓縮算法缺乏理論支持的問(wèn)題，提出了一套通用的數(shù)學(xué)分析證明方法。 已有的文獻(xiàn)大都在追求高壓縮率或快速查找的過(guò)程中犧牲了系統(tǒng)增量更新的性能，尚未看到可以很好兼顧這三個(gè)問(wèn)題的解決方案。不同級(jí)別的路由器對(duì)路由表查找的需求不同，本文針對(duì)下面三個(gè)典型的場(chǎng)景給出對(duì)應(yīng)的解決方案： (2)場(chǎng)景一：未來(lái)互聯(lián)網(wǎng)需要極高性能的路由器，可以容忍高硬件成本和高...

【文章頁(yè)數(shù)】：126 頁(yè)

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
Abstract
第1章 引言
    1.1 研究背景
        1.1.1 路由表關(guān)鍵技術(shù)和研究意義
        1.1.2 工業(yè)界和學(xué)術(shù)界的現(xiàn)狀和發(fā)展趨勢(shì)
    1.2 主要研究?jī)?nèi)容和難點(diǎn)
        1.2.1 研究?jī)?nèi)容
        1.2.2 研究難點(diǎn)
    1.3 主要研究成果和創(chuàng)新點(diǎn)
    1.4 論文組織結(jié)構(gòu)
第2章 相關(guān)工作綜述
    2.1 路由表背景知識(shí)
        2.1.1 RIB 與 FIB
        2.1.2 Trie 樹(shù)和最長(zhǎng)前綴匹配規(guī)則介紹
        2.1.3 TCAM 介紹
    2.2 路由表壓縮技術(shù)綜述
        2.2.1 路由表壓縮算法的前提和衡量指標(biāo)
        2.2.2 現(xiàn)有的路由表壓縮算法
    2.3 路由表查找技術(shù)綜述
        2.3.1 基于 Trie 樹(shù)的查找算法
        2.3.2 基于 TCAM 的查找技術(shù)
        2.3.3 基于 Bloom filter 的查找算法
        2.3.4 其他查找算法
    2.4 路由表更新算法綜述
    2.5 本章小結(jié)
第3章 路由表壓縮技術(shù)研究
    3.1 路由表壓縮技術(shù)的難點(diǎn)
    3.2 EAR 壓縮算法
        3.2.1 示意圖的符號(hào)意義
        3.2.2 選舉算法的社會(huì)學(xué)思想
        3.2.3 EAR 算法的一個(gè)簡(jiǎn)單例子
        3.2.4 EAR 算法的原子模型
    3.3 兩種次優(yōu)壓縮算法
        3.3.1 次優(yōu)壓縮算法的社會(huì)學(xué)思想
        3.3.2 EAR-slow 算法模型
        3.3.3 EAR-Fast 算法模型
    3.4 增量更新算法
        3.4.1 多原象問(wèn)題
        3.4.2 更新算法的幾個(gè)定理
        3.4.3 根節(jié)點(diǎn)更新問(wèn)題
        3.4.4 增量更新算法描述
    3.5 ONRTC 算法
        3.5.1 ONRTC 算法描述
        3.5.2 ONRTC 算法的快速更新算法
    3.6 四種算法的復(fù)雜度分析
    3.7 壓縮算法的理論依據(jù)
        3.7.1 符號(hào)約定與定義
        3.7.2 最長(zhǎng)前綴匹配群
        3.7.3 選舉和代表模型
        3.7.4 數(shù)學(xué)證明的應(yīng)用
    3.8 壓縮算法的性能評(píng)價(jià)
        3.8.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源與系統(tǒng)配置
        3.8.2 六種壓縮算法的壓縮實(shí)驗(yàn)結(jié)果
        3.8.3 六種壓縮算法的更新實(shí)驗(yàn)結(jié)果
        3.8.4 ONRTC 算法的壓縮實(shí)驗(yàn)結(jié)果
        3.8.5 ONRTC 算法的更新實(shí)驗(yàn)結(jié)果
    3.9 本章小結(jié)
第4章 路由表查找技術(shù)研究
    4.1 引言
    4.2 CLUE：一種并行 TCAM 查找算法
        4.2.1 CLUE 的設(shè)計(jì)思想
        4.2.2 CLUE 的分區(qū)算法
        4.2.3 并行查找機(jī)制
        4.2.4 新動(dòng)態(tài)冗余機(jī)制
        4.2.5 系統(tǒng)性能下限
        4.2.6 新的增量更新機(jī)制
    4.3 TDDBF：一種基于 Bloom filter 的查找算法
        4.3.1 Bloom filter 簡(jiǎn)介
        4.3.2 TDDBF 算法的由來(lái)
        4.3.3 TDDBF 算法描述
        4.3.4 TDDBF 算法的幾種改進(jìn)方案
        4.3.5 Bloom filter 的增量更新機(jī)制
    4.4 查找算法的性能評(píng)價(jià)
        4.4.1 CLUE 實(shí)驗(yàn)結(jié)果
        4.4.2 TDDBF 實(shí)驗(yàn)結(jié)果
    4.5 本章小結(jié)
第5章 路由表更新技術(shù)研究
    5.1 引言
    5.2 盲點(diǎn)算法
        5.2.1 盲點(diǎn)算法的由來(lái)
        5.2.2 盲點(diǎn)算法描述
    5.3 盲點(diǎn)算法的應(yīng)用
        5.3.1 應(yīng)用范圍
        5.3.2 應(yīng)用到 Lulea 算法
        5.3.3 應(yīng)用到 LC-trie 算法
    5.4 數(shù)學(xué)分析
        5.4.1 盲點(diǎn)算法對(duì)查找速度的影響
        5.4.2 盲點(diǎn)算法更新復(fù)雜度分析
    5.5 盲點(diǎn)算法性能評(píng)價(jià)
        5.5.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源與系統(tǒng)配置
        5.5.2 盲點(diǎn)特性實(shí)驗(yàn)結(jié)果
        5.5.3 應(yīng)用到 Lulea 算法的實(shí)驗(yàn)結(jié)果
        5.5.4 應(yīng)用到 LC-Trie 算法的實(shí)驗(yàn)結(jié)果
    5.6 本章小結(jié)
第6章 總結(jié)和展望
    6.1 工作總結(jié)
    6.2 工作展望
參考文獻(xiàn)
致謝
個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果



本文編號(hào)：3860156