Network addresses are dynamically allocated to devices based on demand. It is determined that a quantity of virtualized machine instances executed on a plurality of computing devices has changed. An updated network address allocation is dynamically assigned to a subdivision of a network in response to the quantity of virtualized machine instances. The subdivision includes the plurality of computing devices. A router for the subdivision is reconfigured to implement the updated network address allocation.