An enhanced, flooding-based link state routing protocol is described that provides pruning of link state data and, when needed, rate-controlled refresh of the pruned link state data from other routers of the flooding domain. A routing device comprises a network interface to send and receive packets over a layer-two (L2) communication medium. The routing device includes a control unit coupled to the network interface, and a flooding-based link state routing protocol executing on a processor of the control unit. The link-state routing protocol establishes an adjacency with a peer router. A database of the routing device includes entries that store a plurality of link state messages for a flooding domain of the link state routing protocol, wherein at least one of the entries in the database stores a partial link state message having a header portion and a payload having pruned link state data.