Краем уха слышал о динамической маршрутизации и ее протоколах. Имел дело с iproute 2, pf (FreeBSD), iptables, но с динамической не сталкивался. Это здесь никак не может помочь?
Вполне может, если сопрягаемые маршрутизаторы поддерживают какой-либо из протоколов динамической маршрутизации (RIP, OSPF, IS-IS, EIGRP, BGP) Правда что из этого кроме RIP поддерживается в Linux я не знаю. Как-то не было интереса.
Правда тут ещё нужно учитывать как именно пропадает связь с внешним миром, а том может и cisco не сразу просекает, что беда.
Моё мнение, что протоколы динамической маршрутизации стоит использовать в локальных сетях с удалёнными подсетями, где в процессе формирования структуры сети участвуют все элементы.
А в Вашем случае более чётко работают пингалки.
Но это лично моё мнение, возможно будут и оппоненты.