2025-05-07
【學術亮點】LEPRE: An Updatable Database-Dependent Range Encoding Algorithm
字體大小
小
中
大
Intelligent Detection: Smart Agriculture Detection System【Department of Computer Science and Engineering / Pi-Chung Wang / Professor】
智慧檢測：智慧農業檢測系統【資工系王丕中教授】
上架日期2025/1/13
智慧檢測：智慧農業檢測系統【資工系王丕中教授】
| 論文篇名 | LEPRE: An Updatable Database-Dependent Range Encoding Algorithm |
| 期刊名稱 | IEEE Journal on Selected Areas in Communications |
| 發表年份, 卷數, 起迄頁數 | 2025, 43(2), 551-562 |
| 作者 | Z Hsin-Tsung Lin, Wei-Cheng Chen, Pi-Chung Wang(王丕中)* |
| DOI | 10.1109/JSAC.2025.3528816 |
| 中文摘要 | 由於AI農業計畫中會有大量的遠端資料傳輸，數據包分類是一種關鍵機制，用於將傳入的數據包分類為流，從而實現軟體定義網路以及各種網路服務。 目前，三態內容可尋址記憶體（TCAM）被廣泛應用於高速、低延遲的數據包分類。 然而，對於基於TCAM的數據包分類來說，範圍擴展和更新性能是兩個基本問題。 一個包含範圍的規則，在將其範圍轉換為前綴或三態字串后，可能會被複製為多個規則，從而佔用多個TCAM條目。 為了緩解或避免範圍擴展的問題，已經提出了許多範圍編碼演算法。 這些演算法可以分為資料庫無關（DI）和資料庫相關（DD）兩類。 資料庫無關的演算法可以在不重新編碼已有範圍的情況下容納新的範圍，但可能仍會引起規則複製。 相比之下，資料庫相關的演算法可以通過自適應地編碼範圍來避免規則複製，但新的範圍可能會導致已有範圍的更新。 因此，這兩類演算法都可能增加TCAM更新的成本。 在本文中，我們提出了一種DD範圍編碼演算法——最長包圍前綴範圍編碼（LEPRE），該演算法可以確保任何新的範圍都不會引起規則複製和已有範圍的重新編碼。 LEPRE利用原始欄位作為範圍編碼的一部分，從而顯著減少了範圍編碼所需的額外位數。 實驗結果表明，LEPRE可以最大化TCAM的存儲效率，並完全支援增量更新，從而最小化TCAM更新的延遲。 |
| 英文摘要 | Packet classification is a key mechanism that classifies incoming packets into flows to enable software-defined networking as well as a variety of networking services. Currently, ternary content addressable memory (TCAM) has been widely used for high-speed and low-latency packet classification. However, both range expansion and update performance are the fundamental issues for TCAM-based packet classification. A rule containing ranges could be replicated to multiple rules after converting its ranges into prefixes or ternary strings to occupy more than one TCAM entry. Many range encoding algorithms have been proposed to alleviate or avoid the problem of range expansion. These algorithms can be classified into database-independent (DI) and database-dependent (DD). While database-independent algorithms can accommodate new ranges without re-encoding the existing ranges, they may still cause rule replication. In contrast, database-dependent algorithms could avoid rule replication by adaptively encoding ranges, but new ranges may result in updates of the existing ranges. Accordingly, both types of algorithms may multiply the cost of TCAM updates. In this paper, we propose a DD range-encoding algorithm, Longest Enclosure Prefix Range Encoding (LEPRE), which can ensure that any new range does not cause any rule replication and re-encoding of the existing ranges. LEPRE employs the original fields as a part of range encoding to significantly decrease the requirements of extra bits for range encoding. Our experiment results show that LEPRE can maximize the TCAM storage efficiency. LEPRE also fully supports incremental updates to minimize the latency of TCAM updates. |
| 發表成果與AI計畫研究主題相關性 | 由於AI農業計畫中會有大量的遠端資料傳輸，以無人機應用為例，由於無人機無法負荷AI運作，必須將資料回傳至邊緣伺服器，為增加佈署彈性，邊緣伺服器亦可能分散於不同地點，為使用協同運算降低計算時間，資料需要在不同邊緣伺服器間進行傳輸，因而需要高速網路協同運作，我們在研究中針對資料傳輸的議題中提出了高效能的封包處理機制。 |
