An enhanced, flooding-based routing protocol is described that provides burst-rate and average-rate flow control. A routing device comprises a network interfaces configured to send and receive packets over a layer-two (L2) communication medium. A flooding-based link state routing protocol executes on a processor of the routing device to maintain network topology information for a network and establish an adjacency with a peer router over the layer-two (L2) communication medium. A database of the routing device stores a minimum packet interval and a credit specified by the peer router for the adjacency. When sufficient credit has been allocated to the L2 communication medium, a scheduler of the router dequeues link state messages from an outbound packet queue and floods each of the link state messages to the L2 communication medium while maintaining at least the specified minimum packet interval between each of the plurality of link state messages.