A cloud provider provides services to tenants over a network. Each cloud-based service is configured according to a respective service deployment scheme. The cloud provider maintains, for each service, classification information, including: a scheme type; a three-tuple cloud identifier including a cloud identifier, a service identifier, and a tenant identifier; and one or more scheme-specific service identifiers. The cloud provider distributes the classification information within the cloud provider, including to the services, to enable a respective tenant to exchange Internet Protocol (IP) packets with, and thereby access, a respective service and components of the service based on the classification information. The IP packet includes, for the respective service, the scheme type, the cloud identifier, the service identifier, the tenant identifier of the respective tenant, and the one or more scheme-specific service identifiers.