Graphical processing unit-based parallelization of the Open Shortest Path First and Border Gateway Protocol routing protocols

• Published in: Concurrency and computation 2015-01, Vol.27 (1), p.237-251
• Main Authors: Dundjerski, Dejan, Tomašević, Milo
• Format: Article
• Language: English
• Subjects: BGP; Computation; Computer networks; CUDA; Devices; GPGPU computing; Networks; OSPF; Parallel processing; Routers; Routing (telecommunications); routing protocols; Shortest-path problems
• ISSN: 1532-0626; 1532-0634
• DOI: 10.1002/cpe.3223

SUMMARY Exponentially growing number of devices on Internet incurs an ever‐increasing load on the network routers in executing network protocols. Parallel processing has recently become an unavoidable means to scale up the router performance. The research effort elaborated in this paper is focused on exploiting the modern trends of general‐purpose computing on graphics processing unit computing in speeding up the execution of network protocols. An additional benefit is off‐loading the CPU, which can now be fully dedicated to the packet processing and forwarding. To this end, the Shortest Path First algorithm in the Open Shortest Path First protocol and the choice of the best routes in the Border Gateway Protocol are parallelized for efficient execution on Compute Unified Device Architecture platform. An evaluation study was conducted on three different graphics processing units with representative network workload for a varying number of routes and devices. The obtained speedup results confirmed the viability and cost‐effectiveness of such an approach. Copyright © 2014 John Wiley & Sons, Ltd.