Патент на изобретение №2355128
|
||||||||||||||||||||||||||
(54) СПОСОБ И УСТРОЙСТВО ДЛЯ АГРЕГИРОВАНИЯ ВХОДЯЩИХ ПАКЕТОВ В ОПТИЧЕСКИЕ ПАЧКИ ДЛЯ СЕТИ С КОММУТАЦИЕЙ ОПТИЧЕСКИХ ПАЧЕК
(57) Реферат:
Изобретение относится к технике связи. Технический результат состоит в агрегировании входящих пакетов в оптические пачки в краевом узле сети с коммутацией оптических пачек. Способ содержит следующие этапы: сохранение входящих пакетов для формирования оптической пачки, ассоциирование каждого входящего пакета с генерируемой случайной двоичной цифрой с некоторой вероятностью для первого и второго значения двоичной цифры, причем пакет с двоичной цифрой, имеющей первое значение, указывает переход между оптическими пачками; и отсылка оптической пачки с агрегированными пакетами, если первое значение указывает переход. 3 н. и 14 з.п. ф-лы, 4 ил.
В сетях с коммутацией оптических пачек или так называемых сетях OBS, пакеты, например пакеты протокола Интернет (IP), элементы данных режима асинхронной передачи (АТМ) или блоки данных протокола (PDU) агрегируются в оптические пачки для передачи по сети OBS или соответствующей оптической сети. Преобразование пакетов в оптические пачки осуществляется в краевых узлах сети OBS в соответствии с определенной стратегией агрегирования. Известные в настоящее время решения предусматривают две главные стратегии агрегирования: стратегия агрегирования с таймаутами и стратегия агрегирования с ограничением буфера. Ниже рассмотрена стратегия агрегирования с таймаутами. Схематичный пример представлен на фиг.1. В этой схеме пакеты 102 добавляются или заполняются в пачку 104, которая формируется в буфере 106 до тех пор, пока не истечет определенное время таймера. Затем пачка 108 отсылается. Вторая стратегия агрегирования с ограничением буфера описана ниже со ссылкой на фиг.2. В этой схеме пакеты 202 добавляются или заполняются в пачку 204, которая формируется в буфере 206 до тех пор, пока буфер не заполнится. Затем пачка 208 отсылается. После того как пакеты преобразованы в пачки и посланы в сеть OBS, они передаются в сети OBS через ряд оптических коммутаторов в определенное место назначения. В лучшем случае, эти оптические коммутаторы имеют ограниченные возможности хранения, например, реализованные на волоконных линиях задержки, а в худшем случае обычно совсем не имеют возможностей хранения. Поэтому между оптическими пачками возникают коллизии. Основными параметрами производительности сетей OBS поэтому являются вероятность блокирования пачек, пропускная способность и задержка. Две основные стратегии агрегирования с таймаутами и с ограничением буфера имеют недостатки, заключающиеся в некоторой вероятности блокирования и ограничении достижимой пропускной способности. Задачей изобретения является снижение вероятности блокирования и увеличение пропускной способности сети OBS. Указанная задача решается признаками пунктов 1, 4 и 8 формулы изобретения. Новая усовершенствованная стратегия агрегирования основана на следующем широко распространенном предположении для мультиплексированного в высокой степени трафика (для базовых сетей): процесс частоты прихода пакетов определяется в соответствии с пуассоновским распределением. При таком предположении идея состоит в учете свойства случайного выбора в любом пуассоновском процессе, чтобы получить пуассоновский процесс с низкой частотой прихода. Этот низкоскоростной пуассоновский процесс будет маркировать начало новой оптической пачки или конец оптической пачки. Так, имеется возможность гарантировать, что процесс посылки и прихода пачек является пуассоновским. Кроме того, интервалы времени между моментами прихода пачек будут распределены по отрицательной экспоненте, как интервалы между моментами прихода в любом пуассоновском процессе. Можно видеть, что преимущества изобретения заключаются в следующем: – Обеспечивается низкая вероятность блокирования в оптических коммутаторах, по сравнению со стандартными стратегиями агрегирования. – Обеспечивается возможность прогнозирования вероятности блокирования. Вероятность блокирования может быть вычислена по формуле эрланг-В. В то же время, для других стратегий агрегирования не известны аналитические формулы. – Ввиду более низкой вероятности блокирования, достигается более высокая пропускная способность в оптических коммутаторах сети OBS. – Обеспечивается прогнозируемость пропускной способности. Пропускная способность, в отличие от известных стратегий, может быть вычислена по формуле эрланг-В. – Упрощается вычисление времен ожидания для пачек и заголовков пачек. – Снижается время ожидания для заголовков оптических пачек в оптических коммутаторах. – Если доступна буферизация пачек, например, за счет использования волоконных линий задержки, в оптических коммутаторах реализуется меньшее время ожидания для пачек. Другие варианты осуществления изобретения представлены в зависимых пунктах формулы изобретения. Приведенный для примера вариант осуществления изобретения описан ниже со ссылками на чертежи, на которых показано следующее: Фиг.1 – рассмотренный выше предшествующий уровень техники. Фиг.2 – рассмотренный выше предшествующий уровень техники. Фиг.3 – схематичный пример процесса агрегирования и случайного выбора. Фиг.4 – график вероятности блокирования как функция нагрузки для различных стратегий агрегирования. Фиг.3 показывает две связанные временные оси Р и В. На первой временной оси Р пакеты РА, изображенные линиями со стрелками, принимаются в хронологическом порядке, например, IP-пакеты, АТМ-элементы данных, или PDU-блоки. Каждый пакет связан с генерируемой случайным образом двоичной цифрой. Двоичная цифра имеет первое и второе значение, например 1 для первого значения и 0 для второго значения, или наоборот. Таким образом, каждый пакет связан либо с 1, либо с 0. Случайные двоичные цифры могут генерироваться генератором случайных чисел Бернулли, согласно распределению вероятностей Бернулли. Вероятность для каждого значения случайной двоичной цифры, то есть, вероятность (р) для единиц («1») и вероятность (1-р) для нулей («0») определяется некоторым распределением вероятностей, например, р(1)=0,01 и р(0)=0,99. Эти пакеты агрегируются в буфере для накопления оптической пачки. Пакет со связанным с ним первым значением, например 1, указывает переход между оптическими пачками, например, начало новой пачки. На фиг.3 это обозначено символом ВА. Хронологически последний пакет с 0 перед пакетом с 1 представляет собой последний пакет пачки, обозначенный на фиг.3 символом LPB. На второй временной оси В на фиг.3 показаны результирующие пачки В1, В2 и В3. Разность Z во времени между началом двух последовательных пачек определяется как интервал между моментами времени прихода. Задержка агрегирования представляет собой задержку, испытываемую пакетом в краевом узле, до тех пор, пока пачка, к которой он принадлежит, не будет завершена. После появления пакета со значением 1 начинается новая пачка, и старая пачка посылается в сеть OBS. Используемое распределение вероятностей определяет среднее число пакетов на пачку. Например, среднее число пакетов на пачку равно 1/р(1). Например, если р(1)=0,01, то среднее число пакетов на пачку равно 1/р(1)=100 пакетов на пачку. Способ также может быть реализован таким образом, что второе значение указывает переход между оптическими пачками. Также первое значение может указывать, вместо начала новой пачки, конец агрегированных пакетов и, тем самым, конец агрегированной пачки. Основная идея состоит в том, что генерируемое случайное число с некоторой вероятностью указывает начало или конец пачки, которая состоит из агрегированных пакетов, например из IP-пакетов. Изобретение может быть реализовано посредством следующих этапов/алгоритма: – Каждый раз, когда краевой узел принимает пакет, например IP-пакет, он посылает его в буфер. – Затем краевой узел считывает генерируемую ассоциированную случайную двоичную цифру/случайное число, соответствующее следующему пакету. – Если ассоциированная случайная двоичная цифра/случайное число для следующего пакета имеет первое значение, например 1, то накопленная пачка отсылается. – В противном случае ничего не делается. Было проведено математическое моделирование с использованием программы Matlab® для вычисления вероятности блокирования в оптическом коммутаторе без преобразования длины волны, как функция нагрузки. Результаты представлены на фиг.4. На фиг.4 АТ обозначает стратегию агрегирования с таймером агрегирования, АВ означает стратегию агрегирования с буфером агрегирования, Erl B обозначает теоретически возможную нагрузку в соответствии с формулой эрланг-В, и RS обозначает соответствующую изобретению стратегию агрегирования со случайным выбором. Можно видеть, что соответствующая изобретению стратегия агрегирования со случайным выбором приводит к самой низкой вероятности блокирования и, кроме того, согласуется с прогнозами по формуле эрланг-В.
Формула изобретения
1. Способ агрегирования входящих пакетов в оптические пачки в краевом узле сети с коммутацией оптических пачек, содержащий этапы сохранения входящих пакетов для формирования оптической пачки, ассоциирования каждого входящего пакета с генерируемой случайной двоичной цифрой с некоторой вероятностью для первого и второго значения двоичной цифры, при этом пакет с двоичной цифрой, имеющей первое значение, указывает переход между оптическими пачками, посылки оптической пачки с агрегированными пакетами, если первое значение указывает переход. 2. Способ по п.1, отличающийся тем, что переход представляет собой начало новой оптической пачки. 3. Способ по п.1, отличающийся тем, что переход представляет собой конец оптической пачки. 4. Способ по любому из пп. 1-3, отличающийся тем, что оптическая пачка посылается через сеть с коммутацией оптических пачек. 5. Способ по любому из пп. 1-3, отличающийся тем, что случайная двоичная цифра генерируется в соответствии с распределением вероятностей Бернулли. 6. Способ по п.4, отличающийся тем, что случайная двоичная цифра генерируется в соответствии с распределением вероятностей Бернулли. 7. Способ по любому из пп. 1-3, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 8. Способ по п.4, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 9. Способ по п.5, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 10. Способ по п.6, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 11. Способ агрегирования входящих пакетов в оптические пачки в краевом узле сети с коммутацией оптических пачек, в котором каждый раз принятый входящий пакет сохраняется, и случайная двоичная цифра, с некоторой вероятностью для первого и второго значения двоичной цифры, генерируется и сравнивается с первым значением двоичной цифры, и, в случае равенства, сохраненные пакеты посылаются в виде оптической пачки. 12. Способ по п.11, отличающийся тем, что оптическая пачка посылается через сеть с коммутацией оптических пачек. 13. Способ по любому из пп. 11 и 12, отличающийся тем, что случайная двоичная цифра генерируется в соответствии с распределением вероятностей Бернулли. 14. Способ по любому из пп. 11 и 12, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 15. Способ по п.13, отличающийся тем, что в качестве входящих пакетов используются IP-пакеты. 16. Устройство краевого узла сети с коммутацией оптических пачек для агрегирования входящих пакетов в оптические пачки, содержащее буфер для накопления входящих пакетов в виде оптической пачки, генератор случайных чисел для генерирования последовательности двоичных цифр с некоторой вероятностью для первого и второго значения двоичной цифры, так что каждый входящий пакет ассоциируется с генерируемой двоичной цифрой, 17. Устройство по п.16, отличающееся тем, что генератор случайных чисел является генератором случайных чисел Бернулли, который генерирует последовательность двоичных цифр в соответствии с распределением вероятностей Бернулли.
РИСУНКИ
MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 07.08.2009
Извещение опубликовано: 27.07.2010 БИ: 21/2010
|
||||||||||||||||||||||||||
595
