In one embodiment, a method comprises generating, by a network device in a network, a Bloom filter bit vector representing services provided by service provider devices in the network; and the network device executing a service discovery operation based on identifying, relative to the Bloom filter bit vector, whether an identified service in a received message is executed in the network.