A method and system of enabling communication between peers in a peer-to-peer (P2P) network in the presence of network address translators (NAT). The method includes: assigning a unique peer identifier to each one of the plurality of peers in the P2P network; establishing an overlay topology connecting each peer to a subset of the plurality of peers in a structured connection pattern based on the unique peer identifier of each peer, each one of the plurality of peers having more connections to close peers and fewer connections to distant peers; and routing messages between peers through the established overlay topology.