Methods and apparatus for Internet-scale routing using small-scale border routers and IP tunneling are described. Each border router is directly connected to a transit provider. Routing protocol peerings may be passed via the border routers through tunnels to a routing service; the routing service and the transit provider router(s) appear to be directly adjacent routing peers. The routing service receives routing data from the transit provider(s), maintains the routing data in a routing table, and processes the routing data in the routing table to select best paths. A mapping service may be informed, by the routing service, of a best exit point (or points) for each Internet prefix of each packet to be routed on the Internet. Outbound packets from devices on the network to the Internet, and inbound packets from the Internet to the network devices, may be encapsulated and passed through tunnels as directed by the mapping service.