University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Compressing IP Forwarding Tables with Small Bounded Update Time

Zhang, Y, Xu, M, Wang, N, Li, J, Chen, P and Liang, F (2016) Compressing IP Forwarding Tables with Small Bounded Update Time Computer Networks, 106. pp. 77-90.

final accepted paper.pdf - Accepted version Manuscript
Available under License : See the attached licence file.

Download (1MB) | Preview
Text (licence)
Available under License : See the attached licence file.

Download (33kB) | Preview


With the fast development of the Internet, the size of Forwarding Information Base (FIB) maintained at backbone routers is experiencing an exponential growth, making the storage support and lookup process of FIBs a severe challenge. One effective way to address the challenge is FIB compression, and various solutions have been proposed in the literature. The main shortcoming of FIB compression is the overhead of updating the compressed FIB when routing update messages arrive. Only when the update time of FIB compression algorithms is small bounded can the probability of packet loss incurred by FIB compression operations during update be completely avoided. However, no prior FIB compression algorithm can achieve small bounded worst case update time, and hence a mature solution with complete avoidance of packet loss is still yet to be identified. To address this issue, we propose the Unite and Split (US) compression algorithm to enable fast update with controlled worst case update time. Further, we use the US algorithm to improve the performance of a number of classic software and hardware lookup algorithms. Simulation results show that the average update speed of the US algorithm is a little faster than that of the binary trie without any compression, while prior compression algorithms inevitably seriously degrade the update performance. After applying the US algorithm, the evaluated lookup algorithms exhibit significantly smaller on-chip memory consumption with little additional update overhead

Item Type: Article
Subjects : Communication
Divisions : Faculty of Engineering and Physical Sciences > Electronic Engineering > Centre for Communication Systems Research
Authors :
Zhang, Y
Xu, M
Wang, N
Li, J
Chen, P
Liang, F
Date : 20 July 2016
DOI : 10.1016/j.comnet.2016.06.015
Copyright Disclaimer : © 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Uncontrolled Keywords : FIB Compression, FIB update, IP address lookup, tries, longest prefix matching
Depositing User : Symplectic Elements
Date Deposited : 01 Jul 2016 16:12
Last Modified : 20 Jun 2017 02:08

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800