Volume 9 Number 6 (Jun. 2014)
Home > Archive > 2014 > Volume 9 Number 6 (Jun. 2014) >
JSW 2014 Vol.9(6): 1619-1625 ISSN: 1796-217X
doi: 10.4304/jsw.9.6.1619-1625

Model checking the convergence property of BGP networks

Ping Yin1, Yinxue Ma2, Zhe Chen2
1School of Science, Jiangnan University, Wuxi 214122, China
2College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China


Abstract—The Border Gateway Protocol (BGP) is an important inter-domain routing protocol, which is widely used in Internet. It allows independent policies to be designed for each Autonomous System (AS). However, the flexibility in designing independent policies causes the convergence problem, i.e., a BGP network may constantly send routing information between ASes and cannot reach a stable state. In this paper, we propose an approach for model checking the convergence property of BGP networks. We firstly establish a formal model of BGP networks and define its convergence property. Then we use the Promela language to describe this model and analyze its convergence. The model is generic enough, thus different instances of BGP networks can be simulated and verified by only modifying parameters and policies. Finally, as examples, we simulate and verify some typical instances of BGP networks by using the SPIN model checker.

Index Terms—border gateway protocol, BGP, model checking, verification, formal methods, SPIN

[PDF]

Cite: Ping Yin, Yinxue Ma, Zhe Chen, "Model checking the convergence property of BGP networks," Journal of Software vol. 9, no. 6, pp. 1619-1625, 2014.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly (2006-2019); Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Dec 06, 2019 News!

    Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec)   [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Dec 15, 2020 News!

    The papers published in Vol 16, No 1 have all received dois from Crossref    [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Dec 15, 2020 News!

    Vol 16, No 1 has been published with online version     [Click]