Using Multicore to Accelerate Network Routing Protocols

The number of Internet users and connected devices has grown considerably over the past decade with approximately one in every three people on the globe an Internet user. The number of websites and web servers has also grown into the millions. With mobile computing becoming more pervasive, we will soon be exhausting all the available IPv4 addresses and moving into the IPv6 era. The Internet backbone is under tremendous performance pressure to keep up with this exponentially increasing usage. Network Processors form the heart of the physical Internet infrastructure, and improving their performance can go a great deal toward providing better connectivity, bandwidth and an overall better Internet user experience.;Border Gateway Protocol (BGP) has become a critical routing application, as it forms the primary protocol that is used for packet routing across different Autonomous Systems on the Internet backbone. Good performance of BGP on network processors directly translates to better convergence time for route changes on the Internet, leading to reduced data loss and better network reliability. As BGP is the ubiquitous routing protocol on the Internet core, analyzing its performance and exploring avenues for speeding it up can greatly help in improving the responsiveness and scalability of the Internet.;In the past, BGP routers have benefited from the increasing single thread performance of processors to keep up with its growing performance requirements. However, the microprocessor industry has now shifted its focus to multicore processors to maintain their performance growth according to Moore's law. Thus, it is imperative to change the BGP software architecture to reap the benefits provided by multicore processors.;In this thesis, we investigate the use of multicore as the compute platform for routing protocols, using BGP as a representative routing application. We propose a multithreaded BGP implementation called PBTS that focuses on improving the update processing functionality which forms the critical path of the BGP implementation, and gives a speedup of 5.5x on a multicore processor with 16 cores. Subsequently, we analyze the performance of both serial and parallel BGP implementations on a fully configurable multicore simulation environment based on the Simics virtual system simulator and the GEMS memory model. We identify several bottlenecks in the parallel BGP software and the underlying multicore architecture that limit performance and scalability. Finally, we propose a canonical multicore architecture that can mitigate or remove these bottlenecks and give better thread scaling for parallel BGP implementations. The analysis and proposed schemes in this work would greatly help in understanding the behavior of BGP, thereby assisting in the design and development of next generation network processors.