第八章解復(fù)用(專業(yè)版)
【正文】 ? Pathfinder的每個(gè)節(jié)點(diǎn)用于匹配包頭中的一個(gè)域 Pathfinder 推廣了 Trie ? Trie是一種前綴樹： ? 每個(gè)節(jié)點(diǎn)包含一個(gè) value, pointer數(shù)組， pointer指向一個(gè) subtrie ? 鍵并不保存在節(jié)點(diǎn)中，而是作為查找節(jié)點(diǎn)數(shù)組的索引 ? 在 Trie上查找一個(gè)關(guān)鍵字： ? 將關(guān)鍵字劃分成字符；從樹根開始，用第 i 個(gè)字符作為索引查找路徑上第 i 個(gè)節(jié)點(diǎn)的數(shù)組，得到指向第（ i+1）個(gè)節(jié)點(diǎn)的指針。 ? pathfinder結(jié)構(gòu)是 Trie的推廣 ： ? 在每個(gè)節(jié)點(diǎn)上，包頭域代替了要查找的字符，哈希表代替了數(shù)組。 ? 根節(jié)點(diǎn)實(shí)現(xiàn)為一個(gè)哈希表，每個(gè) 哈希 表項(xiàng)包含一個(gè)值和一個(gè)指針，指針指向下一個(gè)要查找的節(jié)點(diǎn)。 Pathfinder的技術(shù)細(xì)節(jié) ? Pathfinder的最基本單位稱為一個(gè) cell ? 一個(gè) cell描述了包頭中的一個(gè)域（用 offset、 length、 mask表示）、一個(gè)比較值和一個(gè)指針 ? 舉例： ? 檢查 IP protocol是否為 TCP， cell = (9, 1 ,0xff, 6, Ptr)： ? 9：相對于 IP頭部起始位置偏移 9個(gè)字節(jié)處 ? 1：讀取一個(gè)字節(jié)的內(nèi)容 ? 0xff：提取整個(gè)字節(jié)作為比較關(guān)鍵字 ? 6：將提取的關(guān)鍵字與 6（ TCP協(xié)議號）進(jìn)行比較 ? Ptr：若匹配，沿指針查找下一個(gè) cell Line 和 pattern ? 將一組 cell用指針鏈在一起，構(gòu)成一個(gè) line。 低效！ Pathfinder的設(shè)計(jì)思想 ?合并 N個(gè)
語文相關(guān)推薦
鄂ICP備17016276號-1