A method and apparatus for network connection and maintenance having reduced connection time, increased probability of successful connection, and increased reliability once connected. A second communication protocol is added to network devices, so that two connection-related operations are performed during overlapping periods of time, thereby reducing required connection time while increasing probability of successful connection. Once a device is connected to the network, network maintenance messages, including re-keying requests and “keep-alive” messages, may be sent via the second communication protocol during periods of network congestion, increasing network reliability.