A method of maintaining routing information for a distributed service provided by a plurality of service instances, comprising: providing an address table including a set of entries, wherein: the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of the distributed service; and adding a new service instance to the address table by: obtaining, by a network device controller (144, 650), an assignable index value to assign to the new service instance by 1) identifying an existing, unassigned, index value in the set of provisioned index values, or by 2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value; identifying, by the network device controller, an assigned index value that is a companion index value to the obtained index value; dividing, by the network device controller, a packet source address set associated with the companion index value into a first address subset and a second address subset; and assigning, by the network device controller, the first address subset to the service instance entry in the address table associated with the assigned companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance. providing an address table including a set of entries, wherein: the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of the distributed service; and the address table has a number of entries less than or equal to a number of index values in a set of provisioned index values, and wherein each of the entries is assigned to a respective provisioned index value and an instance of the distributed service; and adding a new service instance to the address table by: obtaining, by a network device controller (144, 650), an assignable index value to assign to the new service instance by 1) identifying an existing, unassigned, index value in the set of provisioned index values, or by 2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value; identifying, by the network device controller, an assigned index value that is a companion index value to the obtained index value; dividing, by the network device controller, a packet source address set associated with the companion index value into a first address subset and a second address subset; and assigning, by the network device controller, the first address subset to the service instance entry in the address table associated with the assigned companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance. obtaining, by a network device controller (144, 650), an assignable index value to assign to the new service instance by 1) identifying an existing, unassigned, index value in the set of provisioned index values, or by 2) increasing the number of index values in the set of provisioned index values and selecting a newly provisioned index value; identifying, by the network device controller, an assigned index value that is a companion index value to the obtained index value; dividing, by the network device controller, a packet source address set associated with the companion index value into a first address subset and a second address subset; and assigning, by the network device controller, the first address subset to the service instance entry in the address table associated with the assigned companion index value and the second address subset to an entry in the address table associated with the obtained index value and the newly added service instance.