чтобы шлюз был отказусточивым - должно быть два компьютера шлюза а не 1,
автопереключение с провайдера на провайдер это лиш частичная мера по отказоустойчивости.
миграция ип адресов между шлюзами - средствами keepalived
NAT - посредством iptables
проверка доступности интернета через провайдеров и переключение - небольшие баш скирпты в крон, или циклом в фон если раз в минуту слишком медленно.
Также для общего развития читайте LARTC
https://www.opennet.ru/docs/RUS/LARTC/