Systems and methods of software-defined wide area network (SDWAN) device routing are provided using a cloud-based overlay routing service that utilizes, a cloud-BGP service (CBS), and a path computation module (PCM), and overlay agents (OAs) implemented on the tenant side. The Oas, CBS, and PCM may interact with each other, e.g., publish/update local states, route prefixes, etc. to create/maintain routing in the SDWAN.