Балансировка каналов — два провайдера, AS, BGP, NAT

Спасибо Хабру, много полезного тут для себя нашел. Думаю, пора «отдавать долги».
Хочу описать алгоритм, который работает больше года на моем шлюзе для балансировки каналов (Гбит трафика, 8k клиентов, 2 провайдера, AS на 1k адресов, большинство клиентов за NAT). Возможно, кому-то пригодится. Во всяком случае, ничего похожего не встречал и когда специально искал — не нашел. Так что полностью мое детище.
Конечно, указанный алгоритм нельзя считать универсальным, подойдет только в подходящих условиях.

Итак, исходные:
— Шлюз на Linux (Debian 6). Используется пакет quagga (бывший zebra).
— Два провайдера (пусть будут ТТК и РТК). Каждый дает канал определенной толщины, «лишнее» режет.
— AS на 1k адресов (пусть будет 1.1.144.0/22). AS0000.
— Большинство клиентов имеют серые адреса (пусть будет 192.168.0.0/16), «клиентские» сети 192.168.1-99.0/24, на шлюзе натятся.
— Небольшая часть клиентов имеют белые адреса в пространстве моей AS.

Задача:
Обеспечить равномерную загрузку каналов ТТК и РТК входящим трафиком для исключения перегрузки каналов.

Упрощение.
Не буду тут говорить о настройках шейпера. Будем считать что это уже настроено и работает. При этом, шейпится общий канал, без учета ТТК / РТК.
Не будем балансировать исходящий. В большинстве случаях это не актуально (исходящего много меньше), да и решается довольно просто.

Теория.
1. BGP позволяет управлять вероятностью (предпочтением). Т.е. указать предпочтительный входящий маршрут для определенной сети. Используется для этого искусственное «удлинение» маршрута — при анонсировании своего маршрута соседу можно несколько раз повторить номер своей AS. При этом, каждому соседу можно «удлинять» маршрут по-разному. Предпочтительным оказывается более короткий маршрут.
2. BGP позволяет делать описания отдельных частей AS. Т.е. в RIPE наша AS описана как 1.1.144.0/22, никто не мешает дополнительно в BGP описать (т.е. анонсировать) 1.1.144.0/24, 1.1.145.0/24, 1.1.146.0/24 и 1.1.147.0/24.
Совет — не убирайте анонс всей AS (1.1.144.0/22). Некоторые шлюзы не принимают маршруты с маской 24. Лучше немного удлинить общий маршрут.
3. Напомню алгоритм выбора маршрута при BGP-маршрутизации из нескольких имеющихся.
— Выбирается маршрут с большей маской. Если не выбрано, то далее.
— Выбирается более короткий маршрут (меньше промежуточных AS). Если не выбрано, то далее.
— Выбирается маршрут, объявленный раньше (считается более надежный). Если не выбрано, то далее.
— Однозначный псевдо-случайный выбор.

Капля дегтя.
К сожалению, «управление предпочтением» совсем не значит «управление вероятностью». На деле оборачивается тем, что почти весь трафик начинает идти по предпочитаемому маршруту. Т.е. используя удлинения маршрутов, плавно регулировать потоки не получится. Это скорее «переключатель», чем «регулятор».

Идея.
Большинство наших клиентов имеют серые IP. Соответственно, на нашем шлюзе натятся. И это основной по объему трафик. Ну и как их натить (т.е. какой внешний IP задать), — в нашей власти.
Всю нашу AS можно разбить на 4 части (1.1.144.0/24, 1.1.145.0/24, 1.1.146.0/24 и 1.1.147.0/24) и использовать их по-разному. Например, первые две для клиентов с «белыми» IP, третья — предпочтение РТК и четвертая — предпочтение ТТК. Именно так сделано у меня.
На уровне iptables принимать решение какие адреса использовать для NAT.
Если адрес клиента 192.168.1-N.0/24, то для NAT использовать 1.1.146.0/24. Иначе — 1.1.147.0/24.
Таким образом, изменяя N, можно плавно балансировать входящий трафик двух каналов.

Реализация.
Прошу считать эту реализацию просто как пример. Далеко не все тут оптимально, кому-то удобнее делать на перле / питоне, кому-то удобнее организовать единым демоном. Главная цель этого примера — показать возможность реализации идеи. Ни и ее работоспособность

1. Для проверки принадлежности IP клиента к 192.168.1-N.0/24, использовать модуль ipset, в правилах набор «rtk».
Цепочка «NAT_AS», которая у меня натит:

:NAT_AS — [0:0]
#Для старых соединений, чтобы не «бросать» их с одного внешнего на другой
-A NAT_AS -m state -s 192.168.0.0/16 —state ESTABLISHED,RELATED -j SNAT —to-source 91.235.146.0-91.235.147.255 —persistent
#Для новых соединений выбираем как натить.
#РТК
-A NAT_AS -m state -m set —set rtk src —state NEW -j SNAT —to-source 1.1.146.0-1.1.146.255 —persistent
#ТТК
-A NAT_AS -m state -m set! —set rtk src —state NEW -j SNAT —to-source 1.1.147.0-1.1.147.255 —persistent

Обратите внимание, -j SNAT используется с параметром —persistent. Это чтобы клиент использовал постоянный внешний IP. Без этого у клиента могут быть проблемы на многих сервисах в интернете.
Ну и где-то в NAT / POSTROUTING

# eth1, eth3 — интерфейсы которые «смотрят» на ТТК и РТК
-A POSTROUTING -s 192.168.0.0/16 -o eth1 -j NAT_AS
-A POSTROUTING -s 192.168.0.0/16 -o eth3 -j NAT_AS

2. Подготавливаем набор ipset «rtk»
Файл, в котором я храню все параметры (используется в нескольких скриптах)
cat param_rtk_set:

#Подсети клиентов, которыми будем управлять
export rtk_start=1
export rtk_min=1
export rtk_max=99

#Максимальные трафики (что дал провайдер, точнее что от него можно получить без потерь). Подбирается.
# РТК
export shp_rtk_max=547
# ТТК
export shp_ttk_max=535

#Относительная точность регулирования
export scale=50

#файл, где хранится текущее значение N. Лучше где-то на tmpfs.
export f_set_end=/lib/init/rw/rtk_set_end

Непосредственно создание и обновление набора rtk. Можно (и нужно) запускать регулярно.
cat create_rtk_set

#! /bin/sh

# Если не существует, то создается набор rtk
/usr/sbin/ipset -N rtk nethash -q
# Временный набор. Чтобы «на горячюю» не изменять рабочий набор
/usr/sbin/ipset -N temp_rtk nethash -q
/usr/sbin/ipset -F temp_rtk -q

. ./param_rtk_set

# В некоторых версиях sh, переменную надо объявить до цикла или условия. Чтобы потом использовать.
rtk_set_end=0

# Если это первый запуск (нет старого значения N, то создадим среднее от min и max. И сохраним.
if [ -f $f_set_end ]; then
read rtk_set_end < $f_set_end
else
rtk_set_end=$(($rtk_min + $rtk_max))
rtk_set_end=$(($rtk_set_end / 2))
echo $rtk_set_end > $f_set_end
fi

# заполним временный набор
net=$rtk_start
while [ $net -lt $rtk_set_end ]; do
/usr/sbin/ipset -A temp_rtk 192.168.${net}.0/24 -q
net=$(($net + 1))
done

# скопируем временный набор в рабочий
/usr/sbin/ipset -W temp_rtk rtk
# удалим временный набор
/usr/sbin/ipset -X temp_rtk -q

ОК, «управляющее воздействие» есть. Т.е. изменяя N (у меня значение хранится в /lib/init/rw/rtk_set_end), можно плавно изменять соотношения входящих трафиков ТТК и РТК. Теперь осталось настроить автоматику.

Автоматизация.
cat rtk-ttk:

# Получим текущие значения счетчиков на интерфейсах
ttk=$(/sbin/ifconfig eth1 | grep -Eo «RX bytes:[0-9]*» | grep -Eo "[0-9]*")
if [ "$ttk" = "" ]; then
echo «No TTK ifconfig»
exit
fi
rtk=$(/sbin/ifconfig eth3 | grep -Eo «RX bytes:[0-9]*» | grep -Eo "[0-9]*")
if [ "$rtk" = "" ]; then
echo «No RTK ifconfig»
exit
fi

# Каталог, где будем хранить прошлые значения
work_dir="/lib/init/rw/"

# Найдем разницу, сохраним текущее значение, если текущее меньше прошлого, то на выход.
read ttk_old < ${work_dir}shp_ttk_old
read rtk_old < ${work_dir}shp_rtk_old

echo $ttk > ${work_dir}shp_ttk_old
echo $rtk > ${work_dir}shp_rtk_old

if [ $ttk -le $ttk_old ]; then
echo «TTK RX smoll»
exit
fi

if [ $rtk -le $rtk_old ]; then
echo «TTK RX smoll»
exit
fi

ttk_cur=$(($ttk — $ttk_old + 1))
rtk_cur=$(($rtk — $rtk_old + 1))

# прочитаем параметры
. ./param_rtk_set

# Максимальное изменение N за одну итерацию. Подбирается.
max_delta=5

# Найдем отклонение.
p=$( echo «scale=10; $scale * ($shp_rtk_max / $shp_ttk_max) / ($rtk_cur / $ttk_cur) + 100.5» | /usr/bin/bc )
p=${p%%.*}
p=$(( $p — 100 ))

# Увеличиваем N
n_for=1
while [ $scale -lt $p ]; do
#echo "$p add"
p=$(( $p — 1 ))
n_for=$(( $n_for + 1 ))
if [ $max_delta -lt $n_for ]; then
break
fi
./add_rtk
done

# Уменьшаем N
n_for=1
while [ $p -lt $scale ]; do
#echo "$p del"
p=$(( 1 + $p ))
n_for=$(( $n_for + 1 ))
if [ $max_delta -lt $n_for ]; then
break
fi
./del_rtk
done

Осталось сделать скрипты add_rtk для увеличения N и del_rtk для уменьшения. Скрипты эти должны читать текущее N из /lib/init/rw/rtk_set_end, уменьшать / увеличивать и сохранять. Не буду их приводить, это просто.

Настройка BGP.
Для того, чтобы все изложенное могло управлять входящим трафиком, надо подготовить BGP.

Пример моего bgp.conf (естественно, настоящие IP и номера изменены под исходные данные:

!
hostname AS0000
password ****
enable password ****
log file /var/log/quagga/bgpd.log
!
router bgp 0000
no synchronization
bgp router-id [наш любой внешний IP]
network 1.1.144.0/22
network 1.1.144.0/24
network 1.1.145.0/24
network 1.1.146.0/24
network 1.1.147.0/24
!
neighbor [IP шлюза РТК] remote-as [AS РТК (только номер, например 12345)]
neighbor [IP шлюза РТК] update-source [наш внешний IP РТК]
neighbor [IP шлюза РТК] route-map MY-OUT-RTK out
neighbor [IP шлюза РТК] route-map INTER_NET in
!
neighbor [IP шлюза ТТК] remote-as [AS ТТК (только номер, например 12345)]
neighbor [IP шлюза ТТК] update-source [наш внешний IP ТТК]
neighbor [IP шлюза ТТК] route-map MY-OUT-TTK out
neighbor [IP шлюза ТТК] route-map INTER_NET in
!
ip prefix-list upstream-out seq 10 permit 1.1.144.0/22
!
ip prefix-list up144 seq 10 permit 1.1.144.0/24
!
ip prefix-list up145 seq 10 permit 1.1.145.0/24
!
ip prefix-list up146 seq 10 permit 1.1.146.0/24
!
ip prefix-list up147 seq 10 permit 1.1.147.0/24
!
!=========================
!— MY-OUT-TTK
route-map MY-OUT-TTK permit 10
match ip address prefix-list up144
!set as-path prepend 0000 0000
!
route-map MY-OUT-TTK permit 20
match ip address prefix-list up145
!set as-path prepend 0000 0000
!
route-map MY-OUT-TTK permit 30
match ip address prefix-list up146
set as-path prepend 0000
!
route-map MY-OUT-TTK permit 40
!match ip address prefix-list up147
!set as-path prepend 0000 0000
!
!route-map MY-OUT-TTK deny 200
!=========================
!
route-map MY-OUT-TTK permit 100
match ip address prefix-list upstream-out
!set as-path prepend 0000 0000 0000
!
route-map MY-OUT-TTK deny 200
!
!— конец MY-OUT-TTK
!=========================
!— MY-OUT-RTK
route-map MY-OUT-RTK permit 10
match ip address prefix-list up144
set as-path prepend 0000
!
route-map MY-OUT-RTK permit 20
match ip address prefix-list up145
set as-path prepend 0000
!
route-map MY-OUT-RTK permit 30
match ip address prefix-list up146
!set as-path prepend 0000 0000 0000
!
route-map MY-OUT-RTK permit 40
match ip address prefix-list up147
set as-path prepend 0000
!
!=========================
!
route-map MY-OUT-RTK permit 100
match ip address prefix-list upstream-out
set as-path prepend 0000 0000
!
route-map MY-OUT-RTK deny 200
!
!— конец MY-OUT-RTK
!=========================
!—- Local nets
ip prefix-list local_ seq 15 permit 192.168.0.0/16
ip prefix-list local_ seq 18 permit 0.0.0.0/8
ip prefix-list local_ seq 19 permit 127.0.0.0/8
ip prefix-list local_ seq 20 permit 10.0.0.0/8
ip prefix-list local_ seq 21 permit 172.16.0.0/12
ip prefix-list local_ seq 22 permit 169.254.0.0/16
ip prefix-list local_ seq 23 permit 224.0.0.0/4
ip prefix-list local_ seq 24 permit 240.0.0.0/4
! Тут надо добавить свои «белые» сети
!
route-map INTER_NET deny 10
match ip address prefix-list local_
!
!
route-map INTER_NET permit 200
set local-preference 500
!
line vty
!

Напомню, что здесь «0000» — номер моей AS, «1.1.» — начало моих IP. Все остальное подписано.

Настройка, тюнинг.
Во-первых, надо настроить все «set as-path prepend» в bgp.conf.
Задача — чтобы если все натить исходящим 1.1.146.0/24 (это условно, конечно), то получить большой перекос в сторону РТК.
И наоборот, если все натить исходящим 1.1.147.0/24, то получить сильный перекос в сторону ТТК.

Во-вторых, надо указать максимально-доступные трафики от ТТК и РТК в файле param_rtk_set (shp_rtk_max и shp_ttk_max). Не рекомендую указывать значение «из договора». Укажите максимальное, которое вы когда-либо получали. Имейте ввиду, что этим вы задаете желаемое соотношение входящих трафиков.

Третье.
Указать желаемую точность регулирования (значение «scale» в параметрах). Чем больше, тем меньше «мертвая зона», тем сильнее управляющее воздействие (сильнее изменяется N). Слишком большое значение может вызвать «биения» (резонанс).

Четвертое.
Укажите максимальное изменение N за одну итерацию. Слишком большое значение может вызвать «биения», т.е. резонанс. Происходит это от того, что реакция на управляющее воздействие появляется не сразу, а с некоторой задержкой. Ну а слишком маленькое значение не позволит успевать за жизненными реалиями.

Ну вот и все. Осталось сделать задание в cron, для выполнения rtk-ttk каждую минуту. Или сделать какой-то демон, которые будет запускать rtk-ttk периодически.

Добавлю, что указанный алгоритм работает у меня больше года. Иногда приходится вмешиваться — поправлять настройки BGP (set as-path prepend). Что-то в Интернете меняется, приходится реагировать.

Приму любые замечания или советы, отвечу в комментариях.