This paper describes an IP-layer anonymizing infrastructure, called ANON, which allows server addresses to be hidden from clients and vice versa. In providing address anonymity, ANON uses a network resident set of IP-layer anonymizing forwarders that can forward IP packets with nested encryption and decryption applied to their source and destination addresses. To prevent adversaries from compromising the anonymity by learning the forwarding path, ANON incorporates a suite of countermeasures, including non-malleable, semantically secure link encryption and link padding. To lower the bandwidth cost of padding traffic, two novel algorithms are suggested: on-demand link padding and probabilistic link padding. To prevent inband denial of service (DoS) attacks through the anonymizing infrastructure itself, ANON uses rate limiting. Finally, ANON makes use of fault-tolerant transport networks to enhance its resilience against failures and outband attacks.