Avoiding natd overhead

[Brett Glass]

I'm working with a FreeBSD-based router that's using IPFW for 
policy routing, traffic shaping, and transparent proxying and natd 
for network address translation. IPFW does these things pretty well 
(in fact, I don't know if another firewall, like pf, could even do 
some of these things I'm doing with IPFW), but natd is by far the 
most CPU-intensive process on the system and is causing it to 
crumple like a wet towel under heavy loads. How can I replace just 
the functionality of natd without moving to an entirely new 
firewall? Can I still select which packets are routed to the NAT 
engine, and when this occurs during the processing of the packet?

--Brett Glass