Одна из проблем, возникающая в работе сети с коммутацией пакетов - перегрузка её отдельных участков, которая в свою очередь может парализовать работу всей сети. Повышения надежности можно достичь, равномерно распределив нагрузку на каналы и узлы сети. В том случае, когда нагрузка распределена равномерно на все узлы и каналы, будет достигнут максимальный резерв производительности.
Каждый канал в сети характеризуется своей пропускной способностью qij. Тогда загрузка определяется как , где - поток по соответствующей дуге, а - средняя длина пакета. Если в сети M каналов, то средняя загрузка сети, имеет вид:
.
Для обеспечения равномерной загрузки каналов нужно минимизировать дисперсию загрузки каждого канала относительно средней загрузки. То есть:
здесь N- количество узлов в сети, - множество входящих в xi дуг ( - множество исходящих из xi дуг).
Для обеспечения равномерной загрузки узлов достаточно представить каждый узел xij в виде пары узлов и . Узлу будут инцидентны все входящие дуги узла xij, а узлу - все исходящие. Дуге соединяющей узлы и нужно назначить пропускную способность, соответствующую производительности узла . Теперь задача обеспечения равномерной загрузки узлов сведена к обеспечению равномерной загрузки каналов.
При балансировке трафика по каналам необходимо соблюсти требования сохранения потоков в сети и ограничение трафика пропускной способностью канала. Условие ограничения трафика пропускной способностью описывается неравенствами вида:
Обозначим через Ki и Li- соответственно, трафик, порожденный i-м узлом и трафик, предназначенный i-му узлу. Тогда условие сохранения потока будет иметь вид:
Если взять поток по несуществующим каналам равным нулю
,
то задача принимает вид системы:
(1)
(2)
(3)
Решив эту систему, мы получим значения потоков по каждому из каналов ( ), которые обеспечат равномерную загрузку сети и позволят использовать весь резерв производительности.