A control-plane component of a virtualization-based packet processing service determines (a) a performance goal for a first category of packet processing operations to be implemented using compute instances of a virtual computing service and (b) one or more packet processing rules. The control-plane component assigns one or more compute instances as nodes of a packet processing cluster designated to perform the requested operations. The control-plane component provides metadata to the client, to be used to establish connectivity between the cluster and one or more sources of the traffic whose packets are to be processed.