Packet processing service configuration change propagation management

A system, comprising:

• one or more computing devices;
• wherein the one or more computing devices include instructions that upon execution on or across the one or more computing devices cause the one or more computing devices to:
• establish, by one or more control plane resources of a packet processing service of a provider network, a plurality of data plane cells of the packet processing service, wherein a data plane cell of the plurality of data plane cells comprises a first collection of fast-path packet processing nodes and a second collection of exception-path packet processing nodes, wherein a fast-path packet processing node of the first collection is configured to implement respective packet processing rules on packet flows of one or more packet processing applications, wherein the respective packet processing rules are obtained at the fast-path packet processing node from one or more of the exception-path packet processing nodes of the second collection;
• assign, by the one or more control plane resources, a particular data plane cell of the plurality of data plane cells to process packets flowing between a first set of communicating entities and a second set of communicating entities of a first packet processing application, wherein at least one communicating entity of the first set comprises a compute instance of a virtualized computing service of the provider network;
• provide, by the one or more control plane resources to individual ones of a plurality of routing intermediaries associated with the first packet processing application, a respective destination list assigned to the routing intermediary, wherein, with respect to a particular routing intermediary, the destination list indicates one or more fast-path packet processing nodes of the particular data plane cell, and wherein the particular routing intermediary is configured to transmit a packet originating at a communicating entity of the first set to a fast-path packet processing node of the destination list for implementation of a packet processing rule of the first packet processing application;
• determine, by the one or more control plane resources, that an additional fast-path packet processing node of the particular data plane cell is to be included in the destination lists of the plurality of routing intermediaries;
• identify, by the one or more control plane resources, a first gradual-update-propagation interval;
• and
• cause, by the one or more control plane resources, the destination lists of the plurality of routing intermediaries to be updated to include the additional fast-path packet processing node such that:
• (a) during an initial portion of the first gradual-update-propagation interval selected for the first packet processing application, the number of routing intermediaries whose destination lists are updated is smaller than the number of routing intermediaries whose destination lists have not been updated, and a first group of packet flows is directed to the additional fast-path packet processing node, and
• (b) during a subsequent portion of the first gradual-update-propagation interval, the number of routing intermediaries whose destination lists have been updated is greater than the number of routing intermediaries whose destination lists have not been updated, and a second group of packet flows is directed to the additional fast-path packet processing node, wherein the second group is larger than the first group.