Как найти максимальную пропускную способность сети

1. Определение максимальной пропускной способности сети

∙ 1
источник, 1 сток. Каждой дуге приписана
пропускная способность. d_ij
– пропускная способность дуги ij.
x_ij –
количество вещества, пропускаемого по
дуге ij в единицу времени

0≤
x_ij ≤ d_ij

∙ Для
любой вершины, кроме истока I и стока S,
количество поступающего вещества в эту
вершину, равно количеству вещества,
вытекающего из нее. В промежуточных
вершинах потоки не создаются и не
исчезают.

∙
Общее количество вещества, вытекающего
из истока I, совпадает с общим количеством
вещества, поступающего в сток S

∙
Задача о максимальном потоке
заключается в нахождении такого потока
по транспортной сети, что сумма потоков
из истока, или, что то же самое, сумма
потоков в сток максимальна.

∙
Каждое неориентированное ребро (u, v)
заменяем на пару ориентированных рёбер
(u, v) и (v, u).

∙
Для произвольной сети максимальная
величина потока из v_s в v_t
равняется минимальной пропускной
способности разреза, который отделяет
v_s от v_t

∙
Алгоритм Форда — Фалкерсона

1. Обнуляем
   все потоки. Остаточная сеть изначально
   совпадает с исходной сетью.

2. В
   остаточной сети находим любой путь из
   источника в сток. Если такого пути нет,
   останавливаемся.

3. Пускаем
   через найденный путь (он называется
   увеличивающим
   путём
   или увеличивающей
   цепью)
   максимально возможный поток:

   1. На
      найденном пути в остаточной сети ищем
      ребро с минимальной пропускной
      способностью
      
      .

   2. Для
      каждого ребра на найденном пути
      увеличиваем поток на

      ,
      а в противоположном ему — уменьшаем
      на

      .

   3. Модифицируем
      остаточную сеть. Для всех рёбер на
      найденном пути, а также для противоположных
      им рёбер, вычисляем новую пропускную
      способность. Если она стала ненулевой,
      добавляем ребро к остаточной сети, а
      если обнулилась, стираем его.

4. Возвращаемся
   на шаг 2.

1. Задача о
   потоке минимальной стоимости

Задача о потоке минимальной стоимости
состоит в нахождении самого дешёвого
способа передачи определённого количества
потока через транспортную сеть.

Алгоритм
поиска кратчайшего пути при наличии
дуг с отрицательной стоимостью – я
у него спросила про этот пункт, он сказал,
что, наверняка, уберет его)

G {E,V},
d_ij
стоимость перехода из I
в j

Найти путь из начальной вершины в
конечную с минимальной суммарной
стоимостью

N – множество непомеченных
вершин

П – множество помеченных вершин

Шаг 0. ε₀ т.к. мы находимся
в этой точке, то переход в нее =0

П=v₀

N={v₁:v_n}

Шаг 1.

Находим начальные дуги (I,j),
такие что

V_i
∊ П, v_j
∊ N
для каждой такой дуги определенное
число N_ij
= ε_i + d_ij

Шаг 2.

έ=min{h_ij}

Выделяем дуги, на которых этот минимум
достигается. Конечную вершину помечаем
ε_i =έ

Шаг 3.

Поверяем выполнение условия ε_i
+ d_ij≥
ε_d для всех
дуг, вершины которого ∊П
(V_i
∊ П, v_j
∊ П) –
проверка на то, не существует ли более
короткого пути, чем найденный

∙ если неравенство выполняется, то –
Шаг 5

∙ если неравенство не выполняется, то
– Шаг 4

Шаг 4.

ε_j* = ε_i
+ d_ij*

У дуги, на которой достигалась
старая ε пометка отменяется, помечается
новая дуга ij

Пусть

То
есть появляется более короткий путь.
Необходимо отменять пометку в мин (в
нач.) и отметить дугу

Шаг 5.

Определяем помечена ли последняя вершина
V_n ∊
П

Если v_n
– конечная вершина помечена, то
ответ

Если конечная вершина непомечена, то к
Шаг 1

Кратчайший путь ищется из конечной
вершины

Определение
кратчайшего пути (2 пункта)

Задача
о потоке минимальной стоимости

Расписаны в учебнике «Теория
игр. Исследование операций» Костевича
и Лапко

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

1. Статьи
2. Проектирование и монтаж систем безопасности
3. Пропускная способность в IP-сетях: расчет и выбор сетевого оборудования

Илья Назаров
Системный инженер компании “ИНТЕЛКОМ лайн”

После оценки требуемой пропускной способности на каждом из участков IP-сети необходимо определиться с выбором технологий сетевого и канального уровней OSI. В соответствии с выбранными технологиями определяются наиболее подходящие модели сетевого оборудования. Этот вопрос также непростой, поскольку пропускная способность напрямую зависит от производительности оборудования, а производительность, в свою очередь, – от программно-аппаратной архитектуры. Рассмотрим подробнее критерии и методы оценки пропускной способности каналов и оборудования в IP-сетях.

Критерии оценки пропускной способности

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

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

Для простого примера рассмотрим приложения небольшой корпоративной сети.

Пример расчета пропускной способности

Предположим, в сети расположены 300 рабочих компьютеров и столько же IP-телефонов. Планируется использовать такие сервисы: электронная почта, IP-телефония, видеонаблюдение (рис. 1). Для видеонаблюдения применяются 20 камер, с которых видеопотоки передаются на сервер. Попытаемся оценить, какая максимальная пропускная способность потребуется для всех сервисов на каналах между коммутаторами ядра сети и на стыках с каждым из серверов.

Следует сразу отметить, что все расчеты нужно проводить для времени наибольшей сетевой активности пользователей (в теории телетрафика – ЧНН, часы наибольшей нагрузки), поскольку обычно в такие периоды работоспособность сети наиболее важна и возникающие задержки и отказы в работе приложений, связанные с нехваткой пропускной способности, неприемлемы. В организациях наибольшая нагрузка на сеть может возникать, например, в конце отчетного периода или в сезонный наплыв клиентов, когда совершается наибольшее количество телефонных вызовов и отправляется большая часть почтовых сообщений.

Электронная почта
Возвращаясь к нашему примеру, рассмотрим сервис электронной почты. В нем используются протоколы, работающие поверх TCP, то есть скорость передачи данных постоянно корректируется, стремясь занять всю доступную пропускную способность. Таким образом, будем отталкиваться от максимального значения задержки отправки сообщения – предположим, 1 секунды будет достаточно, чтобы пользователю было комфортно. Далее нужно оценить средний объем отправляемого сообщения. Предположим, что в пиках активности почтовые сообщения часто будут содержать различные вложения (копии счетов, отчеты и т.д.), поэтому для нашего примера средний размер сообщения возьмем 500 кбайт. И наконец, последний параметр, который нам необходимо выбрать, – максимальное число сотрудников, которые одновременно отправляют сообщения. Предположим, во время авралов половина сотрудников одновременно нажмут кнопку “Отправить” в почтовом клиенте. Тогда требуемая максимальная пропускная способность для трафика электронной почты составит (500 кбайт х 150 хостов)/1 с = 75 000 кбайт/с или 600 Мбит/с. Отсюда сразу можно сделать вывод, что для соединения почтового сервера с сетью необходимо использовать канал Gigabit Ethernet. В ядре сети это значение будет одним из слагаемых, составляющих общую требуемую пропускную способность.

Телефония и видеонаблюдение
Другие приложения – телефония и видеонаблюдение – в своей структуре передачи потоков схожи: оба вида трафика передаются с использованием протокола UDP и имеют более или менее фиксированную скорость передачи. Главные отличия в том, что у телефонии потоки являются двунаправленными и ограничены временем вызова, у видеонаблюдения потоки передаются в одном направлении и, как правило, являются непрерывными.

Чтобы оценить требуемую пропускную способность для трафика телефонии, предположим, что в пики активности количество одновременных соединений, проходящих через шлюз, может достигать 100. При использовании кодека G.711 в сетях Ethernet скорость одного потока с учетом заголовков и служебных пакетов составляет примерно 100 кбит/с. Таким образом, в периоды наибольшей активности пользователей требуемая пропускная способность в ядре сети составит 10 Мбит/с.

Трафик видеонаблюдения рассчитывается довольно просто и точно. Допустим, в нашем случае видеокамеры передают потоки по 4 Мбит/с каждая. Требуемая пропускная способность будет равна сумме скоростей всех видеопотоков: 4 Мбит/с х 20 камер = 80 Мбит/с.

Витоге осталось сложить полученные пиковые значения для каждого из сетевых сервисов: 600 + 10 + 80 = 690 Мбит/с. Это и будет требуемая пропускная способность в ядре сети. При проектировании следует также предусмотреть и возможность масштабирования, чтобы каналы связи могли как можно дольше обслуживать трафик разрастающейся сети. В нашем примере будет достаточно использования Gigabit Ethernet, чтобы удовлетворить требованиям сервисов и одновременно иметь возможность беспрепятственно развивать сеть, подключая большее количество узлов

Конечно же, приведенный пример является далеко не эталонным – каждый случай нужно рассматривать отдельно. В реальности топология сети может быть гораздо сложнее (рис. 2), и оценку пропускной способности необходимо производить для каждого из участков сети.

Нужно учитывать, что VoIP-трафик (IP-телефония) распространяется не только от телефонов к серверу, но и между телефонами напрямую. Кроме того, в разных отделах организации сетевая активность может различаться: служба техподдержки совершает больше телефонных вызовов, отдел проектов активнее других пользуется электронной почтой, инженерный отдел больше других потребляет интернет-трафик и т.д. В результате некоторые участки сети могут требовать большей пропускной способности по сравнению с остальными.

Полезная и полная пропускная способность

В нашем примере при расчете скорости потока IP-телефонии мы учитывали используемый кодек и размеры заголовка пакета. Это немаловажная деталь, которую нужно иметь в виду. В зависимости от способа кодирования (используемые кодеки), объема данных, передаваемых в каждом пакете, и применяемых протоколов канального уровня формируется полная пропускная способность потока. Именно полная пропускная способность должна учитываться при оценке требуемой пропускной способности сети. Это наиболее актуально для IP-телефонии и других приложений, использующих передачу низкоскоростных потоков в реальном времени, в которых размер заголовков пакета составляет существенную часть от размера пакета целиком. Для наглядности сравним два потока VoIP (см. таблицу). Эти потоки используют одинаковое сжатие, но разные размеры полезной нагрузки (собственно, цифровой аудиопоток) и разные протоколы канального уровня.

Скорость передачи данных в чистом виде, без учета заголовков сетевых протоколов (в нашем случае – цифрового аудиопотока), есть полезная пропускная способность. Как видно из таблицы, при одинаковой полезной пропускной способности потоков их полная пропускная способность может сильно различаться. Таким образом, при расчете требуемой пропускной способности сети для телефонных вызовов в пиковые нагрузки, особенно у операторов связи, выбор канальных протоколов и параметров потоков играет значительную роль.

Выбор оборудования

Выбор протоколов канального уровня обычно не составляет проблемы (сегодня чаще стоит вопрос, какая пропускная способность должна быть у канала Ethernet), но вот выбор подходящего оборудования даже у опытного инженера может вызвать затруднения.

Развитие сетевых технологий одновременно с растущими потребностями приложений в пропускной способности сетей вынуждает производителей сетевого оборудования разрабатывать все новые программно-аппаратные архитектуры. Часто у отдельно взятого производителя встречаются на первый взгляд схожие модели оборудования, но предназначенные для решения разных сетевых задач. Взять, к примеру, коммутаторы Ethernet: у большинства производителей наряду с обычными коммутаторами, используемыми на предприятиях, есть коммутаторы для построения сетей хранения данных, для организации операторских сервисов и т.д. Модели одной ценовой категории различаются своей архитектурой, “заточенной” под определенные задачи.

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

Общая производительность оборудования

В документации к своему оборудованию производители часто указывают два значения максимальной пропускной способности: одно выражается в пакетах в секунду, другое – в битах в секунду. Это связано с тем, что большая часть производительности сетевого оборудования расходуется, как правило, на обработку заголовков пакетов. Грубо говоря, оборудование должно принять пакет, найти для него подходящий путь коммутации, сформировать новый заголовок (если нужно) и передать дальше. Очевидно, что в этом случае играет роль не объем данных, передаваемых в единицу времени, а количество пакетов.

Если сравнить два потока, передаваемых с одинаковой скоростью, но с разным размером пакетов, то на передачу потока с меньшим размером пакетов потребуется больше производительности. Данный факт следует учитывать, если в сети предполагается использовать, например, большое количество потоков IP-телефонии – максимальная пропускная способность в битах в секунду здесь будет гораздо меньше заявленной.

Понятно, что при смешанном трафике, да еще и с учетом дополнительных сервисов (NAT, VPN), как это бывает в подавляющем большинстве случаев, очень сложно рассчитать нагрузку на ресурсы оборудования. Часто производители оборудования или их партнеры проводят нагрузочное тестирование разных моделей при разных условиях и результаты публикуют в Интернете в виде сравнительных таблиц. Ознакомление с этими результатами сильно упрощает задачу выбора подходящей модели.

Подводные камни модульного оборудования

Если выбранное сетевое оборудование является модульным, то, кроме гибкой конфигурации и масштабируемости, обещанной производителем, можно получить и множество “подводных камней”.

При выборе модулей следует тщательно ознакомиться с их описанием или проконсультироваться у производителя. Недостаточно руководствоваться только типом интерфейсов и их количеством – нужно также ознакомиться и с архитектурой самого модуля. Для похожих модулей нередка ситуация, когда при передаче трафика одни способны обрабатывать пакеты автономно, а другие просто пересылают пакеты центральному процессорному модулю для дальнейшей обработки (соответственно для одинаковых внешне модулей цена на них может различаться в несколько раз). В первом случае общая производительность оборудования и, как следствие, его максимальная пропускная способность оказываются выше, чем во втором, поскольку часть своей работы центральный процессор перекладывает на процессоры модулей.

Кроме этого, модульное оборудование часто обладает блокируемой архитектурой (когда максимальная пропускная способность ниже суммарной скорости всех портов). Это связано с ограниченной пропускной способностью внутренней шины, через которую модули осуществляют обмен трафиком между собой. Например, если модульный коммутатор имеет внутреннюю шину с пропускной способностью 20 Гбит/с, то для его линейной платы с 48 портами Gigabit Ethernet при полной загрузке можно использовать только 20 портов. Подобные детали нужно также иметь в виду и при выборе оборудования внимательно читать документацию.

Общие рекомендации

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

1. Изучайте приложения, которые планируется использовать в сети, применяемые ими технологии и объемы передаваемого трафика. Пользуйтесь советами разработчиков и опытом коллег, чтобы учесть все нюансы работы этих приложений при построении сетей.
2. Детально изучайте сетевые протоколы и технологии, которые используются этими приложениями.
3. Внимательно читайте документацию при выборе оборудования. Чтобы иметь некоторый запас готовых решений, ознакомьтесь с продуктовыми линейками разных производителей.

В результате при правильном выборе технологий и оборудования можно быть уверенным, что сеть в полной мере удовлетворит требованиям всех приложений и, будучи достаточно гибкой и масштабируемой, прослужит долгое время.

Источник: Secuteck

Итак, вы только что получили сервер с гарантированным выделенным каналом на 1Гбит/с (или более) и были неприятно удивлены, обнаружив относительно медленный трансфер файлов. Прежде чем писать в техподдержку и искать неполадки в сети, оцените реальную пропускную способность TCP от одного хоста до другого.

Следует выделить два наиболее важных фактора для успешной передачи данных по протоколу TCP:

• размер TCP-окна — количество байт, которое одна из сторон готова принять без подтверждения;
• круговая задержка (латентность) передачи-приема — время, затраченное на отправку пакета и подтверждение его доставки.

Если вы знаете оба этих показателя, то с легкостью рассчитаете максимально возможную пропускную способность между двумя хостами вне зависимости от ширины полосы пропускания.

Пропускная способность TCP (бит/с) = Размер TCP-окна (бит) / Круговая латентность (с)

Разберем на простом примере. Имеется гигабитный Ethernet-канал между серверами с круговой задержкой 30 мс. Необходимо отправить большой файл с одного сервера на другой сервер по протоколу FTP. На какую реальную пропускную способность можно рассчитывать?

Сначала необходимо перевести размер TCP-окна из байтов в биты. В данном случае будет задействовано стандартное TCP-окно Windows-машины размером 64 КБ = 65 536 Б = 65 536 * 8 = 524 288 бит.

Затем необходимо взять размер TCP-окна в битах и разделить его на круговую латентность канала, выраженную в секундах. Для целей данных расчетов 30 мс превращается в 0.030 с.

Максимальная пропускная способность TCP = 524 288 бит / 0.030 с = 17 476 266 бит/с = 17.4 Мбит/с

Таким образом, несмотря на тот факт, что между двумя серверами имеется гигабитная Ethernet-связь, при передаче файлов нельзя рассчитывать более чем на 17 Мбит/с.

Как можно сделать сеть быстрее? Ответ очевиден: увеличить размер TCP-окна и/или сократить задержку сигнала.

Для того чтобы согласовать больший размер TCP-окна, требуется индивидуальная ручная настройка каждого сервера. Это, в свою очередь, приводит к следующему вопросу: какой размер TCP-окна можно считать оптимальным? Чтобы выяснить это, необходимо провести обратные вычисления, опираясь на ширину полосы пропускания.

Формула для расчета оптимального размера TCP-окна

Размер TCP-окна (байт) = Размер TCP-окна (бит) / 8 = Пропускная способность (бит/с) * Круговая латентность (с) / 8

В вышеобозначенном примере для гигабитного Ethernet-маршрута между серверами с круговой задержкой 30 мс, получается следующее значение:

1 000 000 000 бит/с * 0.030 с = 30 000 000 бит / 8 = 3 750 000 байтов.

Иными словами, если сконфигурировать оба сервера на TCP-окно в 3 750 КБ, FTP-соединение полностью заполнит полосу пропускания и достигнет пропускной способности в 1 Гбит/с.

Следует знать, что увеличение размера TCP-окна имеет свои недостатки.

Во-первых, это потребует больше памяти для буферизации серверов, которая необходима для хранения неподтвержденных данных на случай их повторной отправки.

Во-вторых, увеличенный размер TCP-окна может повлечь за собой большее количество потерянных пакетов, которые, в свою очередь, требуют повторной передачи всего окна. Это может негативно сказаться на производительности. Для решения этой проблемы в стеке TCP/IP сервера может быть активирована опция «выборочные подтверждения», которая по умолчанию выключена.

Один из вариантов решения проблемы — размещение WAN-акселераторов — ускорителей глобальной сети на каждом конце линии. Они:

• открывают увеличенное TCP-окно;
• предоставляют возможность тонкой оптимизации протокола TCP (например, выборочные подтверждения только между акселераторами);
• не требуют специальной настройки серверов или дополнительной буферной памяти;
• могут использовать особые функции прикладного уровня модели OSI (Layer 7 — доступ к сетевым службам) для сокращения круговой задержки.

Латентность

Уменьшить задержку сигнала? Возможно ли это в принципе? Мы не в состоянии преодолеть скорость света, а, значит, никак не можем повлиять на время прохождения сигналом заданного расстояния.

Оптимальный способ оптимизации, опять же, заключается в установке WAN-ускорителя на каждом конце линии, который передает полученные TCP-пакеты локальному серверу, тем самым «обманывая» его на предмет реальной скорости трансфера данных. Локальный сервер принимает моментальные подтверждения ускорителя вместо того, чтобы ждать заторможенный отклик удаленного сервера. Это избавляет нас от необходимости корректировки размера TCP-окна на самих серверах.

Пара WAAS-устройств используют увеличенный размер TCP-окна и выборочные подтверждения на всем участке линии между ними.

Кроме того, WAAS эффективно очищают TCP-поток от избыточных резервных данных, обеспечивая чрезвычайно высокий уровень компрессии (сжатия). Каждый акселератор запоминает ранее просмотренные данные. Если дублирующий фрагмент возникает повторно, он удаляется и заменяется крошечной 2-байтовой меткой. Эта миниатюрная метка распознается удаленным ускорителем, который вставляет вместо нее оригинальный фрагмент данных перед отправкой трафика на локальный сервер.

Подтвержденный на практике результат оптимизации — более высокая пропускная способность линии между серверами без какой-либо специальной TCP-настройки локальных серверов.

Формула для расчета максимальной допустимой задержки для заданной пропускной способности

Пример. На участке между двумя удаленными серверами необходимо гарантировать пропускную способность FTP 10 Гбит/с, используя стандартный размер TCP-окна (64 КБ). Какая максимальная задержка сигнала допустима?

Круговая латентность (мс) = Размер TCP-окна (бит) / Требуемая пропускная способность (бит/с)

524 288 бит / 10 000 000 000 бит/с = 52.4 микросекунды

Что делать?

В принципе, вы можете и не увеличивать TCP-окно и не устанавливать WAN-ускорители. Просто используйте многопоточность и вы сможете использовать канал на 100% его пропускной способности!

Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered over physical or logical links, or through network nodes. Throughput is usually measured in bits per second (bit/s or bps), and sometimes in data packets per second (p/s or pps) or data packets per time slot.

The system throughput or aggregate throughput is the sum of the data rates that are delivered to all terminals in a network.^[1] Throughput is essentially synonymous to digital bandwidth consumption; it can be determined numerically by applying the queueing theory, where the load in packets per time unit is denoted as the arrival rate (λ), and the drop in packets per unit time is denoted as the departure rate (μ).

The throughput of a communication system may be affected by various factors, including the limitations of the underlying analog physical medium, available processing power of the system components, end-user behavior, etc. When taking various protocol overheads into account, the useful rate of the data transfer can be significantly lower than the maximum achievable throughput; the useful part is usually referred to as goodput.

Maximum throughput[edit]

Users of telecommunications devices, systems designers, and researchers into communication theory are often interested in knowing the expected performance of a system. From a user perspective, this is often phrased as either “which device will get my data there most effectively for my needs?”, or “which device will deliver the most data per unit cost?”. Systems designers are often interested in selecting the most effective architecture or design constraints for a system, which drive its final performance. In most cases, the benchmark of what a system is capable of, or its “maximum performance” is what the user or designer is interested in. The term maximum throughput is frequently used when discussing end-user maximum throughput tests.  

Maximum throughput is essentially synonymous to digital bandwidth capacity.

Four different values are relevant in the context of “maximum throughput”, used in comparing the ‘upper limit’ conceptual performance of multiple systems. They are ‘maximum theoretical throughput’, ‘maximum achievable throughput’, and ‘peak measured throughput’ and ‘maximum sustained throughput’. These values represent different quantities, and care must be taken that the same definitions are used when comparing different ‘maximum throughput’ values. Each bit must carry the same amount of information if throughput values are to be compared. Data compression can significantly alter throughput calculations, including generating values exceeding 100% in some cases. If the communication is mediated by several links in series with different bit rates, the maximum throughput of the overall link is lower than or equal to the lowest bit rate. The lowest value link in the series is referred to as the bottleneck.

Maximum theoretical throughput[edit]

This number is closely related to the channel capacity of the system,^[2] and is the maximum possible quantity of data that can be transmitted under ideal circumstances. In some cases this number is reported as equal to the channel capacity, though this can be deceptive, as only non-packetized systems (asynchronous) technologies can achieve this without data compression. Maximum theoretical throughput is more accurately reported taking into account format and specification overhead with best case assumptions. This number, like the closely related term ‘maximum achievable throughput’ below, is primarily used as a rough calculated value, such as for determining bounds on possible performance early in a system design phase.

Asymptotic throughput[edit]

The asymptotic throughput (less formal asymptotic bandwidth) for a packet-mode communication network is the value of the maximum throughput function, when the incoming network load approaches infinity, either due to a message size as it approaches infinity,^[3] or the number of data sources is very large. As other bit rates and data bandwidths, the asymptotic throughput is measured in bits per second (bit/s), very seldom bytes per second (B/s), where 1 B/s is 8 bit/s. Decimal prefixes are used, meaning that 1 Mbit/s is 1000000 bit/s.

Asymptotic throughput is usually estimated by sending or simulating a very large message (sequence of data packets) through the network, using a greedy source and no flow control mechanism (i.e., UDP rather than TCP), and measuring the network path throughput in the destination node. Traffic load between other sources may reduce this maximum network path throughput. Alternatively, a large number of sources and sinks may be modeled, with or without flow control, and the aggregate maximum network throughput measured (the sum of traffic reaching its destinations). In a network simulation model with infinite packet queues, the asymptotic throughput occurs when the latency (the packet queuing time) goes to infinity, while if the packet queues are limited, or the network is a multi-drop network with many sources, and collisions may occur, the packet-dropping rate approaches 100%.

A well known application of asymptotic throughput is in modeling point-to-point communication where (following Hockney) message latency T(N) is modeled as a function of message length N as T(N) = (M + N)/A where A is the asymptotic bandwidth and M is the half-peak length.^[4]

As well as its use in general network modeling, asymptotic throughput is used in modeling performance on massively parallel computer systems, where system operation is highly dependent on communication overhead, as well as processor performance.^[5] In these applications, asymptotic throughput is used in Xu and Hwang model (more general than Hockney’s approach) which includes the number of processors, so that both the latency and the asymptotic throughput are functions of the number of processors.^[6]

Peak measured throughput[edit]

The above values are theoretical or calculated. Peak measured throughput is throughput measured by a real, implemented system, or a simulated system. The value is the throughput measured over a short period of time; mathematically, this is the limit taken with respect to throughput as time approaches zero. This term is synonymous with instantaneous throughput. This number is useful for systems that rely on burst data transmission; however, for systems with a high duty cycle, this is less likely to be a useful measure of system performance.

Maximum sustained throughput[edit]

This value is the throughput averaged or integrated over a long time (sometimes considered infinity). For high duty cycle networks, this is likely to be the most accurate indicator of system performance. The maximum throughput is defined as the asymptotic throughput when the load (the amount of incoming data) is very large. In packet switched systems where the load and the throughput always are equal (where packet loss does not occur), the maximum throughput may be defined as the minimum load in bit/s that causes the delivery time (the latency) to become unstable and increase towards infinity. This value can also be used deceptively in relation to peak measured throughput to conceal packet shaping.

Channel utilization and efficiency[edit]

Throughput is sometimes normalized and measured in percentage, but normalization may cause confusion regarding what the percentage is related to. Channel utilization, channel efficiency and packet drop rate in percentage are less ambiguous terms.

The channel efficiency, also known as bandwidth utilization efficiency, is the percentage of the net bit rate (in bit/s) of a digital communication channel that goes to the actually achieved throughput. For example, if the throughput is 70 Mbit/s in a 100 Mbit/s Ethernet connection, the channel efficiency is 70%. In this example, effective 70 Mbit of data are transmitted every second.

Channel utilization is instead a term related to the use of the channel, disregarding the throughput. It counts not only with the data bits, but also with the overhead that makes use of the channel. The transmission overhead consists of preamble sequences, frame headers and acknowledge packets. The definitions assume a noiseless channel. Otherwise, the throughput would not be only associated with the nature (efficiency) of the protocol, but also to retransmissions resultant from the quality of the channel. In a simplistic approach, channel efficiency can be equal to channel utilization assuming that acknowledge packets are zero-length and that the communications provider will not see any bandwidth relative to retransmissions or headers. Therefore, certain texts mark a difference between channel utilization and protocol efficiency.

In a point-to-point or point-to-multipoint communication link, where only one terminal is transmitting, the maximum throughput is often equivalent to or very near the physical data rate (the channel capacity), since the channel utilization can be almost 100% in such a network, except for a small inter-frame gap.

For example, the maximum frame size in Ethernet is 1526 bytes: up to 1500 bytes for the payload, eight bytes for the preamble, 14 bytes for the header, and 4 bytes for the trailer. An additional minimum interframe gap corresponding to 12 bytes is inserted after each frame. This corresponds to a maximum channel utilization of 1526 / (1526 + 12) × 100% = 99.22%, or a maximum channel use of 99.22 Mbit/s inclusive of Ethernet datalink layer protocol overhead in a 100 Mbit/s Ethernet connection. The maximum throughput or channel efficiency is then 1500 / (1526 + 12) = 97.5%, exclusive of the Ethernet protocol overhead.

Factors affecting throughput[edit]

The throughput of a communication system will be limited by a huge number of factors. Some of these are described below:

Analog limitations[edit]

The maximum achievable throughput (the channel capacity) is affected by the bandwidth in hertz and signal-to-noise ratio of the analog physical medium.

Despite the conceptual simplicity of digital information, all electrical signals traveling over wires are analog. The analog limitations of wires or wireless systems inevitably provide an upper bound on the amount of information that can be sent. The dominant equation here is the Shannon-Hartley theorem, and analog limitations of this type can be understood as factors that affect either the analog bandwidth of a signal or as factors that affect the signal-to-noise ratio. The bandwidth of wired systems can be in fact surprisingly narrow, with the bandwidth of Ethernet wire limited to approximately 1 GHz, and PCB traces limited by a similar amount.

Digital systems refer to the ‘knee frequency’,^[7] the amount of time for the digital voltage to rise from 10% of a nominal digital ‘0’ to a nominal digital ‘1’ or vice versa. The knee frequency is related to the required bandwidth of a channel, and can be related to the 3 db bandwidth of a system by the equation:^[8]
Where Tr is the 10% to 90% rise time, and K is a constant of proportionality related to the pulse shape, equal to 0.35 for an exponential rise, and 0.338 for a Gaussian rise.

• RC losses: wires have an inherent resistance, and an inherent capacitance when measured with respect to ground. This leads to effects called parasitic capacitance, causing all wires and cables to act as RC lowpass filters.
• Skin effect: As frequency increases, electric charges migrate to the edges of wires or cable. This reduces the effective cross-sectional area available for carrying current, increasing resistance and reducing the signal-to-noise ratio. For AWG 24 wire (of the type commonly found in Cat 5e cable), the skin effect frequency becomes dominant over the inherent resistivity of the wire at 100 kHz. At 1 GHz the resistivity has increased to 0.1 ohms/inch.^[9]
• Termination and ringing: For long wires (wires longer than 1/6 wavelengths can be considered long) must be modeled as transmission lines and take termination into account. Unless this is done, reflected signals will travel back and forth across the wire, positively or negatively interfering with the information-carrying signal.^[10]
• Wireless Channel Effects: For wireless systems, all of the effects associated with wireless transmission limit the SNR and bandwidth of the received signal, and therefore the maximum number of bits that can be sent.

IC hardware considerations[edit]

Computational systems have finite processing power, and can drive finite current. Limited current drive capability can limit the effective signal to noise ratio for high capacitance links.

Large data loads that require processing impose data processing requirements on hardware (such as routers). For example, a gateway router supporting a populated class B subnet, handling 10 × 100 Mbit/s Ethernet channels, must examine 16 bits of address to determine the destination port for each packet. This translates into 81913 packets per second (assuming maximum data payload per packet) with a table of 2^16 addresses this requires the router to be able to perform 5.368 billion lookup operations per second. In a worst-case scenario, where the payloads of each Ethernet packet are reduced to 100 bytes, this number of operations per second jumps to 520 billion. This router would require a multi-teraflop processing core to be able to handle such a load.

• CSMA/CD and CSMA/CA “backoff” waiting time and frame retransmissions after detected collisions. This may occur in Ethernet bus networks and hub networks, as well as in wireless networks.
• Flow control, for example in the Transmission Control Protocol (TCP) protocol, affects the throughput if the bandwidth-delay product is larger than the TCP window, i.e., the buffer size. In that case, the sending computer must wait for acknowledgement of the data packets before it can send more packets.
• TCP congestion avoidance controls the data rate. A so-called “slow start” occurs in the beginning of a file transfer, and after packet drops caused by router congestion or bit errors in for example wireless links.

Multi-user considerations[edit]

Ensuring that multiple users can harmoniously share a single communications link requires some kind of equitable sharing of the link. If a bottleneck communication link offering data rate R is shared by “N” active users (with at least one data packet in queue), every user typically achieves a throughput of approximately R/N, if fair queuing best-effort communication is assumed.

• Packet loss due to network congestion. Packets may be dropped in switches and routers when the packet queues are full due to congestion.
• Packet loss due to bit errors.
• Scheduling algorithms in routers and switches. If fair queuing is not provided, users that send large packets will get higher bandwidth. Some users may be prioritized in a weighted fair queuing (WFQ) algorithm if differentiated or guaranteed quality of service (QoS) is provided.
• In some communications systems, such as satellite networks, only a finite number of channels may be available to a given user at a given time. Channels are assigned either through preassignment or through Demand Assigned Multiple Access (DAMA).^[11] In these cases, throughput is quantized per channel, and unused capacity on partially utilized channels is lost.

Goodput and overhead[edit]

The maximum throughput is often an unreliable measurement of perceived bandwidth, for example the file transmission data rate in bits per seconds. As pointed out above, the achieved throughput is often lower than the maximum throughput. Also, the protocol overhead affects the perceived bandwidth. The throughput is not a well-defined metric when it comes to how to deal with protocol overhead. It is typically measured at a reference point below the network layer and above the physical layer. The most simple definition is the number of bits per second that are physically delivered. A typical example where this definition is practiced is an Ethernet network. In this case, the maximum throughput is the gross bit rate or raw bit rate.

However, in schemes that include forward error correction codes (channel coding), the redundant error code is normally excluded from the throughput. An example in modem communication, where the throughput typically is measured in the interface between the Point-to-Point Protocol (PPP) and the circuit-switched modem connection. In this case, the maximum throughput is often called net bit rate or useful bit rate.

To determine the actual data rate of a network or connection, the “goodput” measurement definition may be used. For example, in file transmission, the “goodput” corresponds to the file size (in bits) divided by the file transmission time. The “goodput” is the amount of useful information that is delivered per second to the application layer protocol. Dropped packets or packet retransmissions, as well as protocol overhead, are excluded. Because of that, the “goodput” is lower than the throughput. Technical factors that affect the difference are presented in the “goodput” article.

Other uses of throughput for data[edit]

Integrated circuits[edit]

Often, a block in a data flow diagram has a single input and a single output, and operate on discrete packets of information. Examples of such blocks are Fast Fourier Transform modules or binary multipliers. Because the units of throughput are the reciprocal of the unit for propagation delay, which is ‘seconds per message’ or ‘seconds per output’, throughput can be used to relate a computational device performing a dedicated function such as an ASIC or embedded processor to a communications channel, simplifying system analysis.

Wireless and cellular networks[edit]

In wireless networks or cellular systems, the system spectral efficiency in bit/s/Hz/area unit, bit/s/Hz/site or bit/s/Hz/cell, is the maximum system throughput (aggregate throughput) divided by the analog bandwidth and some measure of the system coverage area.

Over analog channels[edit]

Throughput over analog channels is defined entirely by the modulation scheme, the signal-to-noise ratio, and the available bandwidth. Since throughput is normally defined in terms of quantified digital data, the term ‘throughput’ is not normally used; the term ‘bandwidth’ is more often used instead.

See also[edit]

References[edit]

Further reading[edit]

• Rappaport, Theodore S. Wireless Communications, Principles and Practice second edition, Prentice Hall, 2002, ISBN 0-13-042232-0
• Blahut, Richard E. Algebraic Codes for Data Transmission Cambridge University Press, 2004, ISBN 0-521-55374-1
• Li, Harnes, Holte, “Impact of Lossy Links on Performance of Multihop Wireless Networks”, IEEE, Proceedings of the 14th International Conference on Computer Communications and Networks, Oct 2005, 303 – 308
• Johnson, Graham, High Speed Digital Design, a Handbook of Black Magic, Prentice Hall, 1973, ISBN 0-13-395724-1
• Roddy, Dennis, Satellite Communications third edition, McGraw-Hill, 2001, ISBN 0-07-137176-1

Расчет пропускной способности сети связи

Максимальная скорость передачи данных потока E1 составляет 2,048 Мбит/с. Рассчитаем месячный объем телетрафика, пропускаемого системой при условии максимальной загруженности системы:

где

T – время работы системы, в нашем случае, при условии работы системы 24 часа в сутки, 30 дней в месяц:

Однако максимальная пропускная способность не может быть достигнута в силу неравномерности распределения нагрузки в течение дня, а так же из-за неполного использования трафика (часть его используется для передачи служебной информации состояния и синхронизации).

Расчет пропускной способности телефонного сегмента

Требуется определить:

величину поступающего на УТС телетрафика;

максимально возможное количество абонентских телефонов при вероятности блокировок .

При расчете с целью упрощения будем полагать, что при полной занятости каналов для телефонного трафика настройками мультиплексора гарантированно отводится треть имеющихся ресурсов (что в стандарте ИКМ-30 соответствует N = 10 каналам), а для передачи данных ЛВС – две третьих.

Решение:

Объем поступающего трафика рассчитаем по формуле:

(5.1)

где

M – количество абонентских телефонов = 500 (согласно выданного варианта),

k – среднее количество звонков в час (полагаем равным 5),

tВ – средняя продолжительность разговоров 2 мин = 120 сек,

T – время обслуживания (полагаем равным 24 часам – усредняем на период суток)

Найдем максимально возможное количество абонентских телефонов при вероятности блокировок .

По таблице в приложении 1 определяем допустимый объем поступающего телетрафика (в таблице B – вероятность блокировок, N – количество соединительных линий).

В нашем случае, при B=40 и N=3, получили A=3,47Эрл. Теперь вычислим количество абонентов:

Телефонный сегмент проектируемой сети ЛВС может обслужить 500 абонентов.

Проектирование ЛВС

Основные требования, предъявляемые к проектируемой ЛВС:

в сети не встречается пути между двумя устройствами, содержащего более 5 повторителей;

в сети не более 1024 станций (повторители не считаются);

сеть содержит только компоненты, соответствующие стандарту IEEE 802.3, а хост-модули, концентраторы и трансиверы используют только кабели AUI, 10Base-T, FOIRL, 10Base-F, 10Base-5 или 10Base-2;

в сети отсутствуют соединения, превышающие предельно допустимую длину (см. таблицу 6.1);

пути, содержащие 3, 4 или 5 повторителей, должны удовлетворять перечисленным ниже дополнительным требованиям.

Ограничения для путей с 3 повторителями

Если самый длинный путь содержит 3 повторителя, должны выполняться следующие требования:

между повторителями не должно быть оптических соединений длиной более 1000 метров;

между повторителями и DTE не должно быть оптических соединений длиннее 400 метров;

не должно быть соединений 10Base-T длиной свыше 100 метров.

Ограничения для путей с 4 повторителями

При 4 повторителях в самом длинном пути, должны выполняться следующие требования:

между повторителями не должно быть оптических соединений длиной более 500 метров;

не должно быть соединений 10Base-T длиной свыше 100 метров;

в сети не должно быть более 3 коаксиальных сегментов с максимальной длиной кабеля.

Ограничения для путей с 5 повторителями

Если в самом длинном пути находится 5 повторителей, вводятся следующие ограничения:

должны использоваться только оптические (FOIRL, 10Base-F) соединения или 10Base-T;

не должно быть медных или оптических соединений с конечными станциями длинной более 100 метров;

общая длина оптических соединений между повторителями не должна превышать 2500 метров (2740 для 10Base-FB);

не должны использоваться кабели снижения AUI длиной более 2 метров.

Рассчитаем одну из возможных конфигураций сети: в соответствии с выданным вариантом задания ЛВС должна состоять из 4-х сегментов, со средней длиной отводящих линий – 50 м, общее количество компьютеров – 40 шт.

Рис. 1.12 – Структурная схема ЛВС.

При проектировании сетей Ethernet, реализуемых с помощью хабов, применяют 2 модели:

Модель 1 применима для сетей, работающих с элементами одного стандарта, например 10 Base T. Данная модель базируется на правиле «4-х хабов» для сетей Ethernet на основе витой пары. Согласно этому правилу, при построении ЛВС только на концентраторах между двумя любыми оконечными узлами сети должно быть не более 4-х концентраторов (хабов). Это обусловлено ограничениями на время двойного оборота (PDV) между двумя самыми удаленными друг от друга станциями, на снижение величины межкадрового интервала (PVV) и на длину каждого сегмента сети. В проектируемой нами сети правило «4-х хабов» выполняется.

Модель 2 основывается на строгом расчете величины PDV (время двойного оборота между двумя самыми удаленными друг от друга станциями) для различных пар удаленных устройств. В стандарте Ethernet время PDV не должно превосходить 575 bt.