Scalable routing service

A method, comprising:

• performing, by one or more computing devices:
• receiving, at a routing service from a particular routing device of the provider network, a message formatted in accordance with a set of application programmatic interfaces (APIs) implemented using a stateless application-layer protocol that includes, as part of the stateless application layer protocol, application-layer message ordering information within a body of messages, wherein the message includes a sequence number within a body portion of the message, the sequence number indicative of an ordering of the message relative to other messages comprising routing information sent by the particular routing device to the routing service, wherein the message indicates a route to a particular network destination, wherein the same routing service is configured to receive routing information from a plurality of routing devices, and wherein the routing service provides a central source and destination of routing information for the plurality of routing devices in the provider network;
• modifying, in accordance with the message, a particular routing information base (RIB) stored at a persistent data store for the routing service that is accessible from a plurality of nodes of the routing service;
• generating, at the routing service, based at least in part on said modifying the particular RIB, an entry of a forwarding information base (FIB) associated with the particular RIB;
• and
• transmitting, from the routing service to one or more routing devices within the provider network including the particular routing device, an indication of the entry of the FIB.

A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implements a node of a routing service of a provider network, wherein the node is configured to:

• receive, from a particular routing device of the provider network, a message formatted in accordance with a set of application programmatic interfaces (APIs) implemented using a stateless application-layer protocol that includes, as part of the stateless application layer protocol, application-layer message ordering information within the body of messages, wherein a body of the message includes a sequence number within a body portion of the received message, the sequence number indicative of an ordering of the message relative to other messages comprising routing information sent by the particular routing device to the routing service, wherein the set of APIs is defined by the routing service for use within the provider network, wherein the message indicates a route to a particular network destination associated with a particular RIB (routing information base) stored at a persistent data store for the routing service that is accessible by the routing service, wherein the same routing service is configured to receive routing information from a plurality of routing devices, and wherein the routing service provides a central source and destination of routing information for the plurality of routing devices in the provider network;
• modify, in accordance with the message, the particular RIB;
• generate, based at least in part on said modifying the particular RIB, an entry of a forwarding information base (FIB) associated with the particular RIB;
• and
• transmit, to one or more routing devices within the provider network including the particular routing device, a representation of the entry of the FIB.