Advertised routes are associated with a particular tag in a routing database in a second router. A first router subsequently sends one or more messages associated with a route withdraw operation that specifies the particular tag, such that second router can identify, based on the particular tag, a set including multiple routes, and remove those multiple routes from its routing database. For example, the tag may be a Border Gateway Protocol attribute, a Border Gateway Protocol communities attribute, or some other indication, numeric quantity, or opaque value.