A method of connecting a network forwarding element may include transmitting a first connection request from the forwarding element to a first network controller. After transmitting the first connection request, a rejection message may be received from the first network controller at the network forwarding element, with the rejection message being responsive to the first connection request and with the rejection message including an address of a second network controller. Responsive to receiving the rejection message, a second connection request may be transmitted from the network forwarding element to the second network controller. Related forwarding elements and controllers are also discussed.