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

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

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

【文章目錄】：
摘要
Abstract
第1章 引言
    1.1 研究背景
        1.1.1 路由表關(guān)鍵技術(shù)和研究意義
        1.1.2 工業(yè)界和學(xué)術(shù)界的現(xiàn)狀和發(fā)展趨勢
    1.2 主要研究內(nèi)容和難點(diǎn)
        1.2.1 研究內(nèi)容
        1.2.2 研究難點(diǎn)
    1.3 主要研究成果和創(chuàng)新點(diǎn)
    1.4 論文組織結(jié)構(gòu)
第2章 相關(guān)工作綜述
    2.1 路由表背景知識
        2.1.1 RIB 與 FIB
        2.1.2 Trie 樹和最長前綴匹配規(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 樹的查找算法
        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 示意圖的符號意義
        3.2.2 選舉算法的社會學(xué)思想
        3.2.3 EAR 算法的一個(gè)簡單例子
        3.2.4 EAR 算法的原子模型
    3.3 兩種次優(yōu)壓縮算法
        3.3.1 次優(yōu)壓縮算法的社會學(xué)思想
        3.3.2 EAR-slow 算法模型
        3.3.3 EAR-Fast 算法模型
    3.4 增量更新算法
        3.4.1 多原象問題
        3.4.2 更新算法的幾個(gè)定理
        3.4.3 根節(jié)點(diǎn)更新問題
        3.4.4 增量更新算法描述
    3.5 ONRTC 算法
        3.5.1 ONRTC 算法描述
        3.5.2 ONRTC 算法的快速更新算法
    3.6 四種算法的復(fù)雜度分析
    3.7 壓縮算法的理論依據(jù)
        3.7.1 符號約定與定義
        3.7.2 最長前綴匹配群
        3.7.3 選舉和代表模型
        3.7.4 數(shù)學(xué)證明的應(yīng)用
    3.8 壓縮算法的性能評價(jià)
        3.8.1 實(shí)驗(yàn)數(shù)據(jù)來源與系統(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 新動態(tài)冗余機(jī)制
        4.2.5 系統(tǒng)性能下限
        4.2.6 新的增量更新機(jī)制
    4.3 TDDBF：一種基于 Bloom filter 的查找算法
        4.3.1 Bloom filter 簡介
        4.3.2 TDDBF 算法的由來
        4.3.3 TDDBF 算法描述
        4.3.4 TDDBF 算法的幾種改進(jìn)方案
        4.3.5 Bloom filter 的增量更新機(jī)制
    4.4 查找算法的性能評價(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)算法的由來
        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)算法對查找速度的影響
        5.4.2 盲點(diǎn)算法更新復(fù)雜度分析
    5.5 盲點(diǎn)算法性能評價(jià)
        5.5.1 實(shí)驗(yàn)數(shù)據(jù)來源與系統(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è)人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果



本文編號：3860156