The continuous growth of the routing tables sizes in backbone routers is one of the most compelling scaling problems affecting the Internet. Beside the deriving waste of memory, the main problem posed by this phenomena is a general increase of the tables lookup time during the routing of the IP datagrams. Thus, a considerable research effort has been devoted in the design of algorithms for fast lookups and for compressing existing tables. However, the envisaged close enhancement of the current version of the IP protocol to IPv6 and the introduction of the so called Network Address Translators (NATs) urgently require the solution of the IP routing tables minimization problem in a new and more effective way, that is by performing addresses reassignments. In such a setting, we first give an algorithm with an asymptotically optimal running time that assigns addresses so as to minimize the size of a single routing table. We then show that minimizing the sum of the sizes of n routing tables is an intractable problem, i.e. NP-hard, and present a 3h-approximation algorithm, where h is the length of the IP addresses.