Examples relate to establishing a network fault detection session. In one example, a routing device may receive a request to initiate a bidirectional forwarding detection (BFD) session with a second routing device; transmit a first echo frame to the second routing device; receive a first response frame; determine that a response time does not meet a response time threshold; in response to the determination, determine that a BFD failure threshold has not been met; after the determination that the BFD failure threshold has not been met, transmit a second echo frame to the second routing device; receive a second response frame; determine whether a second response time meets the BFD response time threshold; and in response to determining that the second response time meets the BFD response time threshold, provide a notification that a BFD session has been established between the routing device and the second routing device.