The techniques describe effective detection of network connectivity issues for a cloud service operating in a distributed computing environment. To detect the network connectivity issues, a system first projects network traffic patterns at the tenant level (e.g., on a tenant-by-tenant basis) and compares a tenant’s current network traffic to the projected network traffic pattern. If the comparison yields that the current network traffic for the tenant is closely following the projected network traffic pattern, the tenant is deemed healthy. However, if the comparison yields that the current network traffic for the tenant is not closely following the projected network traffic pattern, the tenant is deemed unhealthy. Once the system has made these binary health determinations for various tenants on a tenant-by-tenant basis, the system is configured to aggregate the unhealthy determinations across a group of tenants to determine whether the cloud service is experiencing network connectivity issues.