第八章解復(fù)用-在線瀏覽
2024-09-11 13:18本頁面
【正文】 的查找放在一個(gè)節(jié)點(diǎn)中 ?每個(gè)節(jié)點(diǎn)實(shí)現(xiàn)為一個(gè)哈希表，用哈希查找代替線性查找 Pathfinder的數(shù)據(jù)結(jié)構(gòu)示例 ? 根節(jié)點(diǎn)對應(yīng)以太幀的type域 ， 包含過濾器集合中描述的所有Ether type值 。 ? 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的技術(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。 ? 在最簡單的情形中，用一個(gè) pattern =hdrlen,
語文相關(guān)推薦
鄂ICP備17016276號-1