Первое достижение

Чтож, вот они, последствия усиленных образовательных усилий :)

В общем, задача стоит примерно следующая: обеспечить балансировку нагрузки на два канала к одному провайдеру используя динамические внешние IP адреса и статическую маршрутизацию у провайдера. То есть, если каждый из интерфейсов получает некий внешний адрес, то через конкретный интерфейс, снаружи доступен только адрес этого интерфейса. При чем все это необходимо обеспечить исключительно на клиентской стороне.

Для начала, я поднял у себя на компутере Dynamips + Dynagen. Очень удобная штуковина для тестирования всякого рода технологий в пределах одной машины. Огромное спасибо автору сего творения. Просто супер, всем очень рекомендую.
Понятное дело что для решения данной проблемы необходимо использовать NAT. Кроме того, использовать per-packet балансировку нет резона,поскольку в случае одной TCP сессии обратный трафик будет все равно возвращаться на тот интерфейс, IP адрес которого указан в поле SRC. Посему я решил сделать per-destination балансировку. При чтении документации выяснилось что метод форвардинга CEF по умолчанию использует именно такой тип балансировки. Значит, часть проблемы решена, для обеспечения правильного типа балансировки достаточно включить CEF.
После этого в тестовой лаборатории была собрана примерная конфигурации - грубо говоря два маршрутизатора, соединенных двумя каналами. Один представлял собой сторону TELCO, а второй, собственно меня.
Сначала настраивал NAT на двух исходящих интерфейсах. Простой метод описаный тут, с использованием статической трансляции и access-list'а для выбора интерфейса, в IP адрес которого оная трансляция будет производиться не подошел. Эксперименты показали, что если access-list'ы имеют одинаковые условия для одного и второго внешнего интерфейса, то все попадания происходят только в один из них. И по этому оказывается, что трансляция происходит только в один из внешних адресов, хотя per-destination форвардинг и работает. Таким образом выходит, что пакеты уходят в правильные интерфейсы но с неправильным внешним адресом. Соответственно назад они возвращаются всегда через один и тот же интерфейс. Решением стало использование route-map, в котором для выбора внешнего адреса для трансляции используется не только адреса транслируемых сетей, но и исходящий интерфейс, через который пакет будет выкинут наружу. Выглядит это примерно так:

route-map CHAN1 permit 10
match ip address PERMIT_NAT
match interface Serial1/1
!
route-map CHAN2 permit 10
match ip address PERMIT_NAT
match interface Serial1/2

В результате этого внешний адрес стал выбираться правильно, и - вуаля. ВСЕ РАБОТАЕТ!

Вот куски конфига :)

ip route 0.0.0.0 0.0.0.0 Serial1/1
ip route 0.0.0.0 0.0.0.0 Serial1/2

ip nat inside source route-map CHAN1 interface Serial1/1 overload
ip nat inside source route-map CHAN2 interface Serial1/2 overload

route-map CHAN1 permit 10
match ip address PERMIT_NAT
match interface Serial1/1
!
route-map CHAN2 permit 10
match ip address PERMIT_NAT
match interface Serial1/2

ip access-list extended PERMIT_NAT
permit ip 10.0.0.0 0.255.255.255 any

Следующим шагом будет, я думаю, настройка QOS для всего этого счастья. Но сначала нужно изучить предметную область :).