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.

[img] Text
final accepted paper.pdf - Accepted version Manuscript
Restricted to Repository staff only until 20 June 2017.
Available under License : See the attached licence file.

Download (1MB)
[img]
Preview
Text (licence)
SRI_deposit_agreement.pdf
Available under License : See the attached licence file.

Download (33kB) | Preview

Abstract

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 :
AuthorsEmailORCID
Zhang, YUNSPECIFIEDUNSPECIFIED
Xu, MUNSPECIFIEDUNSPECIFIED
Wang, NUNSPECIFIEDUNSPECIFIED
Li, JUNSPECIFIEDUNSPECIFIED
Chen, PUNSPECIFIEDUNSPECIFIED
Liang, FUNSPECIFIEDUNSPECIFIED
Date : 20 July 2016
Identification Number : 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 http://creativecommons.org/licenses/by-nc-nd/4.0/
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 : 01 Jul 2016 16:12
URI: http://epubs.surrey.ac.uk/id/eprint/811090

Actions (login required)

View Item View Item

Downloads

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