said by Da Geek Kid:software, no software... the table grows exponentially. unless you can create an algorithm for it like CEF and place an ASIC than yeah it should be quick, but I am sure Juniper/Cisco/Brocade have thought of that Billions of times...
enter the cavium on the asa, qfp on asr1k, and hardware assisted nat on c6k.
these are platforms that nat is nearly (or all) optimised in hardware with little to no impact on the control-plane aspect of the router/firewall.
there is still a limitation on the storage for these entries in tcam -- but thats no different than a routing table limitation on said platforms either.
q.