The performance of packet forwarding mainly relies on the routing lookup (RL) in high-speed routers and switches. Due to the network topology change and the limited resource on aerospace devices, the RL strategy for low Earth orbiting (LEO) constellation backbone networks should be specifically designed. Targeting lower resource consumption, we first propose the perfect hash-based RL, including a perfect hash function (PHF) for metarule space compression plus random access for the output interface. A satellite perfect hash function (SPHF) algorithm is proposed to generate efficient hash functions with limited storage. For 10 000 randomized keys, the SPHF algorithm constructs 50-Kb PHFs in 3.05 ms with 538 Kb storage. Then, we design the routing-oriented hash function (RHF) algorithm by fusing the perfect hash and RL, and optimize RHF toward the hardware implementation. The RHF algorithm is robust to different RL scenarios. In the field programmable gate array (FPGA) (xc7k70t-fbv900-1) experiment with 10 000 32-bit metarules and four output interfaces, a typical RHF algorithm (RHF1) costs only 13.2 ns and 1429 equivalent look-up-table (LUTs) to lookup each packet under 312.5 MHz clock frequency. Compared with most advanced ternary content addressable memory (TCAM)-based implementations, RHF1 reduces the storage and logic resources by at least an order of magnitude while keeping comparable lookup latency in the same FPGA Chip. This article provides a design mentality for the RL of low Earth orbiting constellation backbone networks.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Perfect Hash-Based Routing Lookup for LEO Constellation Backbone Network


    Contributors:
    Zhang, Keran (author) / Tang, Lei (author) / Zhao, Chao (author) / Zhong, Sheng (author) / Luo, Hangzai (author)


    Publication date :

    2023-10-01


    Size :

    3333751 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    NETWORK TRAFFIC ENGINEERING WITH MULTI-VIRTUAL ROUTING AND FORWARDING LOOKUP

    SELLAPPA SRIRAM / JOSHI ANIL | European Patent Office | 2023

    Free access

    FTS-Based Link Assignment and Routing in GNSS Constellation Network

    Zhang, Tian-yu / Ye, Gang-qiang / Li, Jing et al. | British Library Conference Proceedings | 2017


    Advanced routing in interplanetary backbone network [6795-38]

    Xu, G. / Sheng, M. / Wu, C. et al. | British Library Conference Proceedings | 2007


    Maximum Persistence Routing in Satellite Constellation Networks

    Donner, Anton / Zamorano, Raul / Costache, Mihai | AIAA | 2004


    Precomputed Routing in a Store and Forward Satellite Constellation

    Cruz-Sanchez, Hugo / Franck, Laurent / Beylot, Andre-Luc | IEEE | 2007