Some embodiments of the invention provide a method for enabling inter-gateway connectivity in an SD-WAN (software-defined wide area network) that connects multiple sites. The method deploys to the SD-WAN a floating hub gateway router that that (1) connects to multiple gateway routers each of which is deployed in a cloud and connects to at least one edge router in at least one site, and (2) does not connect to edge routers at any site. The method provides a network address associated with the floating hub gateway router to the multiple gateway routers deployed in one or more clouds for the SD-WAN. The method configures the floating hub gateway router to establish a tunnel with each gateway router in the multiple gateway routers to enable inter-gateway connectivity between the multiple gateway routers.