溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
寫了兩篇命題作文后，一發不可收拾了...要北京出差，走之前再搞兩篇！(寫于2015/03/21晚，次日進京)
我在描述數據包分類Dimension
Tree結構的時候，大量使用了二叉樹結構，這就意味著我必須不斷的左拐右拐，而到底哪里拐，免不了的是比較。我需要免除比較操作，這怎么可能？當然有可
能，空間換時間。并且，空間占用不能太大，以利于Cache的利用率。于是我想到了索引，就是類似MMU頁表那樣的。不可避免地，我再次遇到了空間復雜度
的問題...
如果能夠直接索引區間，那么區間就可以用數組表示，進而，該區間上覆蓋的規則則可以是一個位圖，對于16bit的域來講，直接做索引也不過2^16條索引項，每個索引項指向一個索引，即區間數組下標。整個結構如下圖所示：
這幾乎就是Dimension Tree并行模式的內部實現，而且特別適合硬件實現，它足夠規則和簡單。
非常直觀，以至于沒必要解釋什么！然而這個結構是如何構建的呢？位圖的構建非常簡單，不必多講，關鍵是索引表的構建，也不難，按照區間分割情況一個一個將
65535個表項填充，就像構建頁目錄，頁表那樣。然而值得解釋的是，這里的每個匹配域只有16bit，如果再多的話，占用內存將會瘋漲！比如如何匹配
32bit的IP地址！這確實是一個問題。
這是我一直考慮的問題，而在近日，我找到了方案！這要歸功于我發現了上面的索引/位圖匹配結構。
雖然這個結構只能匹配16bit的域大于16bit將會造成巨量內存占用...)，但是它包含了很多的思想。其中最重要的就是，數據如何通過第三張表來進
行壓縮，即實現數據共享，這好像是數據庫的范疇，但是思想是普遍的。如果解決了這個問題，我幾乎就可以設計出一個新的IPv4路由查找表的結構了。我真的
設計出了，但這是下一篇文章的內容。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
