In one embodiment, a method includes identifying a mobile service provider network (SPN) and a geographic location of an online social network user and accessing a service-provider table associated with the identified mobile SPN and with the geographic location. The service-provider table indexes a reliability score and a sampling amount for multiple messaging-service providers in the geographic location. The method further determines, based on the service-provider table, whether any of the messaging-service providers has a sampling amount below a threshold sampling amount and sends messaging traffic via the determined messaging-service provider until the sampling amount is greater than or equal to the threshold sampling amount. The messaging traffic is used to update the reliability score for the messaging-service provider. The method further includes selecting a messaging-service provider based on the updated reliability scores of the messaging-service providers and sending a message to the user via the selected messaging service-provider.