第八章解復(fù)用(編輯修改稿)
2024-08-28 13:18 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 e =IP和 IP protocol =TCP，只是 TCP端口對(duì)不同。 ? 如果用 BPF實(shí)現(xiàn)： ? 用到來(lái)的包與每個(gè)過(guò)濾器匹配，需比較 500次Ether type 和 500次 IP protocol。 重復(fù)！ ? 用包的端口號(hào)與 500個(gè)過(guò)濾器的端口號(hào)逐個(gè)比較，類(lèi)似于通過(guò)線(xiàn)性查找進(jìn)行精確匹配。 低效！ Pathfinder的設(shè)計(jì)思想 ?合并 N個(gè)包過(guò)濾器為一個(gè)復(fù)合過(guò)濾器： ?將在同一個(gè)包頭域上進(jìn)行的比較放在一個(gè)節(jié)點(diǎn)中： ? 比如，將對(duì) Ether type的查找放在一個(gè)節(jié)點(diǎn)中 ?每個(gè)節(jié)點(diǎn)實(shí)現(xiàn)為一個(gè)哈希表，用哈希查找代替線(xiàn)性查找 Pathfinder的數(shù)據(jù)結(jié)構(gòu)示例 ? 根節(jié)點(diǎn)對(duì)應(yīng)以太幀的type域 ， 包含過(guò)濾器集合中描述的所有Ether type值 。 ? 根節(jié)點(diǎn)實(shí)現(xiàn)為一個(gè)哈希表，每個(gè) 哈希 表項(xiàng)包含一個(gè)值和一個(gè)指針，指針指向下一個(gè)要查找的節(jié)點(diǎn)。 ? Pathfinder的每個(gè)節(jié)點(diǎn)用于匹配包頭中的一個(gè)域 Pathfinder 推廣了 Trie ? Trie是一種前綴樹(shù)： ? 每個(gè)節(jié)點(diǎn)包含一個(gè) value, pointer數(shù)組， pointer指向一個(gè) subtrie ? 鍵并不保存在節(jié)點(diǎn)中，而是作為查找節(jié)點(diǎn)數(shù)組的索引 ? 在 Trie上查找一個(gè)關(guān)鍵字： ? 將關(guān)鍵字劃分成字符；從樹(shù)根開(kāi)始，用第 i 個(gè)字符作為索引查找路徑上第 i 個(gè)節(jié)點(diǎn)的數(shù)組，得到指向第（ i+1）個(gè)節(jié)點(diǎn)的指針。 ? pathfinder結(jié)構(gòu)是 Trie的推廣 ： ? 在每個(gè)節(jié)點(diǎn)上，包頭域代替了要查找的字符，哈希表代替了數(shù)組。
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1