An apparatus includes a memory configured to store labels of virtual private networks (VPNs) in a first local label space. The apparatus also includes a processor to assign a first label block identifier (LBI) to a first block of labels in the first local label space and assign a first tuple to a first VPN. The first tuple includes the first LBI and a first label index (LI) that indicates a location of a first label of the first VPN within the first block of labels. The apparatus also includes a transceiver configured to provide the first tuple to routers that allocate second blocks of labels from second local label spaces based on the first tuple. The second routers store the first label at locations in the second label spaces indicated by the first LI.