Nodes within existing P2P networks typically exchange periodic keep-alive messages in order to maintain network connections between neighbours. Keep-alive messages serve a dual purpose, they're used to detect node failures and to prevent idle connections from being expired by NAT devices. However despite being widely used, the interval between messages are typically fixed below the timeout value of most NAT devices based upon crude rules of thumb.
Furthermore, although many studies have been conducted to traverse NAT devices and other studies seek to improve failure detection in P2P overlay networks; the limitations of NAT devices have received little research attention. This paper explores algorithms which allow nodes to adapt to the timeout values of individual NAT devices and investigates the resulting trade-offs.