A protocol and methods for peer network device discovery is presented. The peer discovery protocol includes a peer discovery marker than can be used with an existing networking protocol such as Transmission Control Protocol (“TCP”) to discover peer network devices. The peer discovery protocol also includes a peer discovery table to record network addresses of peer network devices and their associated host network devices. The peer discovery method allows a first peer network device such as an edge router, to send out a peer discovery request with the peer discovery protocol to other peer network devices as the peer network device is sending data packets for a host network device. Once a second peer network device receives a peer discovery request, the second peer network device attempts to establish a two-way, peer-to-peer data-flow to the first peer network device that sent the peer discovery requests. The peer discovery protocol and methods allow error correction, encryption, compression and other “intelligent” services to be added to peer network devices such as edge routers. The peer discovery protocol and peer discovery methods may enhance performance, reliability and security of data transmitted over the Internet to and from Autonomous Systems, subnets, or other computer networks.