4.5 Article

Compressing IP Forwarding Tables: Towards Entropy Bounds and Beyond

期刊

IEEE-ACM TRANSACTIONS ON NETWORKING
卷 24, 期 1, 页码 149-162

出版社

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2014.2357051

关键词

Data compression; IP forwarding table lookup; prefix tree

资金

  1. [OTKA/PD-104939]

向作者/读者索取更多资源

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state of the art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we redesign the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode an FIB comprising more than 440 K prefixes to just about 100-400 kB of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

Article Engineering, Electrical & Electronic

Signaling Free Localization of Node Failures in All-Optical Networks

Janos Tapolcai, Lajos Ronyai, Eva Hosszu, Laszlo Gyimothi, Pin-Han Ho, Suresh Subramaniam

IEEE TRANSACTIONS ON COMMUNICATIONS (2016)

Article Computer Science, Hardware & Architecture

Diversity Coding in Two-Connected Networks

Peter Babarczi, Janos Tapolcai, Alija Pasic, Lajos Ronyai, Erika R. Berczi-Kovacs, Muriel Medard

IEEE-ACM TRANSACTIONS ON NETWORKING (2017)

Article Computer Science, Hardware & Architecture

Optimal Rule Caching and Lossy Compression for Longest Prefix Matching

Ori Rottenstreich, Janos Tapolcai

IEEE-ACM TRANSACTIONS ON NETWORKING (2017)

Article Computer Science, Information Systems

A novel m-trail allocation method for SRLG fault localization in all-optical networks

Mohammed L. Ali, Pin-Han Ho, Janos Tapolcai

OPTICAL SWITCHING AND NETWORKING (2017)

Article Computer Science, Hardware & Architecture

Node Virtualization for IP Level Resilience

Mate Nagy, Janos Tapolcai, Gabor Retvari

IEEE-ACM TRANSACTIONS ON NETWORKING (2018)

Article Engineering, Electrical & Electronic

Scalable and Efficient Multipath Routing via Redundant Trees

Janos Tapolcai, Gabor Retvari, Peter Babarczi, Erika R. Berczi-Kovacs

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS (2019)

Article Computer Science, Hardware & Architecture

Minimum Cost Survivable Routing Algorithms for Generalized Diversity Coding

Alija Pasic, Peter Babarczi, Janos Tapolcai, Erika R. Berczi-Kovacs, Zoltan Kiraly, Lajos Ronyai

IEEE-ACM TRANSACTIONS ON NETWORKING (2020)

Article Computer Science, Hardware & Architecture

The Earth is nearly flat: Precise and approximate algorithms for detecting vulnerable regions of networks in the plane and on the sphere

Balazs Vass, Laszlo Nemeth, Janos Tapolcai

NETWORKS (2020)

Article Computer Science, Hardware & Architecture

Fast Enumeration of Regional Link Failures Caused by Disasters With Limited Size

Janos Tapolcai, Lajos Ronyai, Balazs Vass, Laszlo Gyimothi

IEEE-ACM TRANSACTIONS ON NETWORKING (2020)

Article Computer Science, Information Systems

Adaptive Protection of Scientific Backbone Networks Using Machine Learning

Ferenc Mogyorosi, Alija Pasic, Richard Cziva, Peter Revisnyei, Zsolt Kenesi, Janos Tapolcai

Summary: This article proposes a new protection scheme for backbone networks that utilizes Machine Learning to implement network intelligence and achieve a proactive approach to service availability without the need for reserved backup network resources. By reallocating unused capacity as protection bandwidth, the scheme aims to improve availability without affecting operational connections or the over-provisioning of network bandwidth.

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT (2021)

Article Engineering, Electrical & Electronic

Probabilistic Shared Risk Link Groups Modeling Correlated Resource Failures Caused by Disasters

Balazs Vass, Janos Tapolcai, Zalan Heszberger, Jozsef Biro, David Hay, Fernando A. Kuipers, Jorik Oostenbrink, Alessandro Valentini, Lajos Ronyai

Summary: The paper introduces a stochastic model for estimating hazards to an optical backbone network and understanding the complex correlation between possible link failures. It also presents standard data structures and a pre-computation process for efficient computation of cumulative failure probabilities of network elements.

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS (2021)

Article Computer Science, Hardware & Architecture

Enumerating Maximal Shared Risk Link Groups of Circular Disk Failures Hitting k Nodes

Balazs Vass, Janos Tapolcai, Erika R. Berczi-Kovacs

Summary: The paper proposed a limited geographic information failure model, which allows for the design of an algorithm that can efficiently compute the set of links that are expected to be close in a network. Under realistic assumptions, the obtained list of SRLGs is short, with approximately 1.2n and 2.2n elements for k = 0 and k = 1, respectively.

IEEE-ACM TRANSACTIONS ON NETWORKING (2021)

Article Computer Science, Information Systems

Bloom Filter With a False Positive Free Zone

Sandor Z. Kiss, Eva Hosszu, Janos Tapolcai, Lajos Ronyai, Ori Rottenstreich

Summary: This article discusses the importance of Bloom filters and their variants in networking applications, and introduces a new data structure called EGH filter that guarantees false positive-free operations. The EGH filter supports Bloom filter operations and ensures real-time false positive-free operations within a limited universe and restricted number of elements stored.

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT (2021)

Article Computer Science, Information Systems

eFRADIR: An Enhanced FRAmework for DIsaster Resilience

Alija Pasic, Rita Girao-Silva, Ferenc Mogyorosi, Balazs Vass, Teresa Gomes, Peter Babarczi, Peter Revisnyei, Janos Tapolcai, Jacek Rak

Summary: This paper introduces a new framework focusing on resilience against natural disasters, targeting network planning, failure modeling, and survivable routing. It proposes a two-stage approach to optimize availability upgrade cost by upgrading a sub-network to achieve the targeted availability threshold. The framework also includes a new integer linear program for disaster-resilient network planning and an efficient heuristic scheme to reduce running time.

IEEE ACCESS (2021)

暂无数据