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