СПОСОБ ОПРЕДЕЛЕНИЯ ПОРЯДКА ПЕРЕДАЧИ СООБЩЕНИЙ Российский патент 1998 года по МПК G06F9/46 

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

Известен способ определения порядка передачи сообщений в вычислительной сети, заключающийся в том, что на каждой станции вычислительной сети контролируют занятость канала, измеряют интервал T.1 собственной передачи от ее начала до прекращения передачи в случае обнаружения столкновения и интервал T. 2 от момента прекращения собственной передачи до момента освобождения канала, а момент начала повторной передачи определяют по формуле
,
где
K - коэффициент загрузки канала, причем, если до истечения интервала T_v канал становится занятым, сдвигают момент начала повторной передачи на интервал ΔT+T*v

, где ΔT - время занятости канала, T*v=T_v-τ_v, , где τ_v -время от освобождения канала до его занятости.

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

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

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

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

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

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

В научно-технической литературе не найден способ с описанной совокупностью новых признаков. Это позволяет сделать вывод о соответствии технического решения критерию "существенные отличия".

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

На фиг. 1 показана диаграмма состояний и переходов для данного способа и использованы следующие обозначения: ИСХ - исходное состояние, АО - нулевое активное состояние, А1 - первое активное состояние, А2 - второе активное состояние, ПД - передача.

На фиг. 2 показаны временные диаграммы процессов столкновений двух (а) и трех (б) передач. На них показаны временные интервалы : ТА - первый измеряемый интервал, длительность бесконфликтной передачи А, ТВ - второй измеряемый интервал, длительность бесконфликтной передачи B, ТС - третий измеряемый интервал, длительность бесконфликтной передачи C, t_ф - интервал форсированного столкновения.

На фиг. 3 показана временная диаграмма работы сети после столкновения трех передач. На ней обозначено: A • B • C - столкновение трех передач (без детализации); A, B, C - успешные передачи станций; A, B и C, X - успешная передача новой активной станции; X, t_Pt - паузы между передачами (i = 1, 2, 3); ТП2 - пауза между передачами C и X; T_хд - время ожидания доступа к общему каналу станций X.

В локальной вычислительной сети с использованием множественного доступа с контролем несущей и обнаружением столкновений (МДКН/ОС) все станции подключены к одному общему ресурсу, через который передаются пакеты данных, в начале которых содержится адрес назначения и приоритет пакета данных. Станции непрерывно слушают общий канал и при появлении в нем пакета данных проверяют его адрес назначения. Если адрес назначения пакета совпадает с адресом данной станции, то последняя принимает этот пакет. С учетом этих пояснений рассмотрим сущность заявляемого способа.

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

Станции, находящиеся в состояниях ИСХ и А2, формируют интервалы времени ТП2 при каждом исчезновении несущей в общем канале. Для этих станций общий канал считается свободным не сразу, а после истечения упомянутого интервала ТП2, если во время его формирования не появилась несущая новой передачи. Если же во время формирования ТП2 появляется несущая новой передачи, то формирование ТП2 прекращается, а общий канал для данной станции считается непрерывно занятым. ТП2 - это минимальная допустимая пауза между передачами в общем канале, необходимая для того, чтобы конец одной передачи не сливался с началом другой.

Станция, попавшая в активное состояние А2, ожидает освобождение общего канала (если он занят) и немедленно переходит в состояние ПД (переход 2), т. е. начинает передачу (если общий канал свободен). В состоянии ПД обычно находится одна станция и она успешно передает свой пакет данных. Как обычно станция проверяет свою передачу и, если она идет успешно, то продолжает ее до передачи всего пакета данных и затем возвращается в исходное состояние (переход 3). Таким образом, при отсутствии столкновений операция процесса управления передачей данных в ЛВС не отличается от прототипа.

Если же в состоянии ПД окажутся не менее двух станций, то каждая из них обнаружит чужие передачи (т. е. обнаружит столкновение передач). Тогда станция фиксирует передачу (т.е. продолжает ее в течении заданного t_ф) и потом прекращает свою передачу.

На станции - участнице столкновения во время процесса с столкновения измеряют интервалы времени ТА и ТВ (при m = 2, m - число станций участниц столкновения, фиг. 2, а) или TA, TB, TC (при m = 3, фиг.2,б) и т.д., чтобы получить необходимую для управления передачей информацию (так же, как в прототипе).

Хотя на фиг. 2 показаны случаи m = 2 и m = 3, предлагаемый способ не ограничивается этими примерами. Аналогично измеряют четыре и более интервалов в случае m > 3.

После измерения длительностей всех передач одного процесса столкновения, т.е. после окончания процесса столкновения, станции - участницы этого столкновения, находящиеся в состоянии ПД, начинают формирование двух интервалов времени - Тп0 и Тп1 для переходов станций соответственно из состояний А0 и А1 в состояние ПД. Одновременно на каждой из этих станций рассчитывают текущий приоритет передачи как:
P_T = P_П + K • T_i (i = 1...m),
где
P_T - текущий приоритет пакета;
P_П - первоначальный приоритет пакета;
k - коэффициент весомости временного параметра;
T_i - время успешной передачи i-й станции участницы конфликта.

В общем случае первоначальный приоритет пакета определяется не только временным, но и другими параметрами функционирования ЛВС.

После расчета текущих приоритетов пакетов их сравнивают и устанавливают очередь в порядке возрастания приоритетов, например P_ta P_tb P_tc.

После определения своего места в очереди станция, получившая первое место, переходит в состояние АО, а все остальные (не первые) станции переходят в состояние A1 (переход 6). В АО станция продолжает формировать интервал Тп0, а в А1 интервал Тп1. По истечении ТП0 данная станция из АО переходит в состояние ПД, т.е. начинает передачу. Если первая передача не начинается, то по истечении Тп1 станция из А1 переходит в состояние ПД, т.е. начинают передачи. В случае m = 1 такая станция только одна, поэтому она успешно передает свой пакет. В случае m = 2 последует повторное столкновение.

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

Если в это время появится новая активная станция X, то она переходит в состояние А2 и ожидает освобождение общего канала. Но так как t_pi Тп2(i= 1,2,3), то общий канал для нее занят до тех пор, пока все участники столкновения не передадут свои пакеты. Затем в общем канале появляется пауза Тп2 (фиг. 3), показывающая, что все участники столкновения уже передали свои пакеты, и поэтому станция X переходит в состояние ПД (начинает свою передачу).

Если две станции начинают передачу строго одновременно и пакеты, передаваемые ими, имеют одинаковый первоначальный приоритет, то может оказаться, что P_та= P_тв. Тогда в очереди могут оказаться две первые (или две вторые) станции. Это приведет к повторному столкновению, к новым измерениям и т.д.. Тогда из-за разных задержек в аппаратуре и в абонентских линиях и т.п. уже после одной-двух таких повторных столкновений окажется P_та=P_тв и последуют две успешные передачи. Возможно и другое решение. Как только станции обнаруживают равенство P_та=P_тв, они переходят в исходное состояние и прекращают попытки передачи данного пакета.

С увеличением нагрузки увеличивается и число m участников столкновения. Соответственно число рассчитываемых текущих приоритетов также увеличивается, а вероятность появления их равенства и других частных случаев также увеличивается, что могло бы ухудшить работу ЛВС. Это можно легко устранить например, если m = M, где M - максимальное число участников столкновения, с которыми аппаратура может справится, то все m участники этого столкновения переводятся в исходное состояние так же, как в прототипе после заданного максимального числа неудачных попыток передачи. Другими словами, часть входной нагрузки сбрасывается, но остальная часть обслуживается качественно и эффективно, т.е. устраняется возможное ухудшение работы ЛВС при перегрузке.

Для реализации предлагаемого способа каждая станция должна иметь стандартные средства для определения состояния общего канала (свободен, успешная передача, столкновение), для формирования, хранения, приема и передачи пакетов данных; для кодирования, декодирования, синхронизации и проверки передаваемых битов данных и другие (такие, которые имеются или могут быть в стандартных или других ЛВС с использованием МДКН/ОС).

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

Таким образом, в предлагаемом способе при возникновении конфликтных ситуаций учитывается приоритет сообщений станций участниц конфликта, что позволяет в среднем снизить ущерб, причиняемый ЛВС конфликтом.

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

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

Устройство для определения порядка передачи сообщений (см фиг. 4) содержит блоки счета 1.1-1.С (С - число передающих станций); блок анализа приоритетов 2; элемент ИЛИ-НЕ 3; блок синхронизации 4; элемент задержки 5; первую 6.1-6.С и вторую 7.1.-7.С группы информационных входов устройства; ответный вход 8 устройства; первую 9.1-9.С и вторую 10.1-10.С группы управляющих входов устройства; группу выходов 11.1-11.С, внутренние связи 12-16 устройства.

Блок синхронизации 4 (см. фиг. 5) содержит делитель 17 и генератор тактовых импульсов 18.

Блок счета 1 (см. фиг. 6) содержит первый 19, второй 22 и третий 27 регистры; умножитель 20; сумматор 21; первый 23 и второй 31 элементы задержки; счетчик 24; первый 25, второй 28 и третий 39 групповые элементы И; групповой элемент ИЛИ 26; элемент НЕ 29; первый 30 и второй 34 элементы И; дешифратор 32; триггер 33.

Блок анализа приоритетов 2 (см. фиг. 7) содержит матрицу триггеров 35.11-35. МС; группу элементов И 36.21-36. МС; группу элементов задержки 37.21-37.МС; группу элементов ИЛИ 38.1-38.С.

В соответствии с приведенным описанием способа, устройство для определения порядка передачи сообщений работает следующим образом.

Перед началом работы триггеры 33, 35.11-35.МС, счетчик 24, регистры 19, 22, 27 устанавливаются в исходное (нулевое) состояние (входы установки в исходное состояние условное не показаны).

После этого по группе входов второй группы информационных входов 7 устройства в каждой блок счета 2 поступает код, соответствующий коэффициенту K весомости временного параметра, который записывается в первый регистр 19 каждого блока счета 1. Аналогично по группе входов первой группы информационных входов 6 устройства перед началом передачи пакета соответствующей станцией через групповой элемент ИЛИ 26 в третий регистр 27 записывается первоначальный приоритет соответствующего пакета информации. Одновременно с началом успешной передачи i-й станцией на вход 9_i поступает импульс, который устанавливает триггер 33 в единичное состояние и потенциал единичного уровня с его единичного выхода открывает элемент И 34 для прохождения тактовых импульсов с генератора 18 тактовых импульсов блока 4 синхронизации по связи 12 устройства на счетный вход счетчиков 24. Счетчик 24 осуществляет подсчет тактовых импульсов и выдает свои значения на первую группу входов умножителя 20, на вторую группу входов которого поступает код коэффициента весомости временного параметра. Полученный результат умножения поступает на первую группу входов сумматора 21, на вторую группу входов которого поступает код первоначального приоритета из регистра 27. В результате суммирования этих величин на выходе сумматора 21 появляется код, соответствующий текущему приоритету пакета в данный момент времени.

Делитель 17 блока синхронизации 4 представляет собой счетчик, который осуществляет счет определенного числа тактовых импульсов с генератора 18, после чего он автономно устанавливается в исходное состояние и на его выходе появляется импульс опроса. Импульс опроса по связи 13 устройства поступает в каждый блок счета 1, где он проходит через открытый элемент И 30 и устанавливает регистр 27 в исходное состояние. Этот же импульс опроса поступает на управляющий вход группового элемента И 39, в результате чего значение сумматора 21 записывается в регистр 22. Время срабатывания элемента И 30 выбирается несколько большим, чем время срабатывания группового элемента И 39. Поэтому в регистр 22 будет записан текущий приоритет пакета, а регистр 27 будет установлен в исходное состояние. Кроме того, импульс опроса задерживается в элементе задержки 31 на время Т.31 и с его выхода поступает на управляющий вход группового элемента И 25. В результате текущий приоритет пакета из регистра 22 через групповые элементы И 25, ИЛИ 26 поступает в регистр 27. Импульс опроса с выхода элемента задержки 31 поступает на элемент задержки 23, где задерживается на время Т.23, после чего устанавливает регистр 22 в исходное состояние. После этого цикл работы блока счета 1 повторяется снова с поступлением нового импульса опроса по связи 13 устройства. Для правильной работы блока счета 1 необходимо соблюдение следующих неравенств:
T.31>T.27.0.+T.30
T.23>T.27.1+T.25+T.26,
где T.31 - время задержки элемента задержки 31;
T.23 - время задержки элемента задержки 23;
T.27.0 - время установки в исходное состояние регистра 27;
T.27.1 - время записи информации в регистр 27;
T.30 - время срабатывания элемента И 30;
T.25 - время срабатывания элемента И 25;
T.26 - время срабатывания элемента ИЛИ 26.

Таким образом, в конце каждого цикла опроса в регистре 27 соответствующего блока счета 1 хранится текущий приоритет пакета соответствующей станции.

При обнаружении конфликта между станциями (в последующем после успешной передачи пакета станцией участницей конфликта) на ответный вход устройства поступает ответный импульс, который подтверждает нулевое состояние триггеров 35 блока анализа приоритета 2 (в последующем устанавливает их в нулевое состояние). Ответный импульс задерживается в элементе задержки 5 на время срабатывания блока анализа приоритетов 2 и затем по связи 14 поступает в каждый блок счета 1. Поступая на управляющий вход группового элемента И 28 со связи 14, импульс опроса открывает его, в результате чего на выходах элемента И 28 появляется код текущего приоритета пакета, который дешифрируется в дешифраторе 32 и по группе связей 15 поступает на входы элементов задержки 37 соответствующего столбца блока анализа приоритетов 2. Причем величина задержки элементов задержки 37 блока анализа приоритетов 2 определяется из соотношения: t_3ij=jit^*+t*ε

, где t^* время срабатывания триггера матрицы анализа приоритетов 2, суммарное время срабатывания элементов ИЛИ 38, ИЛИ-НЕ 3 и элемента И 36. Благодаря таким величинам задержек, увеличивающимся слева направо и сверху вниз в блоке анализа приоритетов 2, происходит переброс в единичное состояние только одного триггера 35 блока анализа приоритетов 2. В результате на его единичном выходе появляется потенциал, который проходит через соответствующий элемент ИЛИ 38 и появляется на одном из выходов 11 устройства. Этот потенциал свидетельствует о том, что в данный момент времени необходимо обслуживать то приоритетное направление, на соответствующем выходе которого присутствует разрешающий потенциал. Нулевой потенциал с выхода элемента ИЛИ-НЕ 3 подается на третьи входы элементов И 36 блока анализа приоритетов 2, что препятствует переходу в единичное состояние всех других триггеров блока анализа приоритетов 2.

При одновременном появлении сигналов на соседних элементах задержки 37 любой строки блока анализа приоритетов 2 быстрее в единичное состояние перебросится триггер с меньшим порядковым номером за счет меньшей его одноименной задержки. Запрещающим потенциалом с нулевого выхода этого триггера закроется элемент И 36 соседнего триггера с большим порядковым номером, в результате появляется потенциал только на одном из выходов устройства, соответствующем станции, которой в данный момент времени предоставлено право занятия общего ресурса.

Таким образом, предлагаемое устройство реализует способ определения порядка передачи сообщений.

Изобретение относится к вычислительной технике и предназначено для использования в локальных вычислительных сетях с шинной топологией для управления передачей пакетов данных через общий канал. Техническим результатом является повышение эффективности функционирования локальной вычислительной сети за счет учета приоритета пакетов сети при их столкновении. Технический результат достигается тем, что при способе определения порядка передачи сообщений в вычислительной сети на каждой станции вычислительной сети контролируют занятость канала и начинают передачу, если канал свободен, при этом каждому пакету началом его передачи в сети присваивают первоначальный приоритет, на каждой станции измеряют время бесконфликтной передачи и по измеренным результатам определяют текущий приоритет по формуле: P_т = P_п + k T_i, где P_т - текущий приоритет пакета; P_п - первоначальный приоритет пакета; k - коэффициент весомости временного параметра; T_i - время бесконфликтной передачи i-й станции участницы конфликта, на основании которого устанавливают очередность передачи пакетов, причем в случае повторной передачи пакета в качестве его первоначального приоритета используют текущий приоритет. 1 з.п. ф-лы, 7 ил.

1. Способ определения порядка передачи сообщений, заключающийся в том, что на каждой станции вычислительной сети контролируют занятость канала, отличающийся тем, что начинают передачу сообщения пакетами, каждому из которых перед началом передачи в сети присваивают первоначальный приоритет, измеряют время бесконфликтной передачи на каждой станции, рассчитывают текущий приоритет передачи на каждой станции участницы конфликта и осуществляют сравнение текущего приоритета станций, после чего определяют очередность их обслуживания. 2. Способ по п.1, отличающийся тем, что в случае повторной передачи пакета в качестве его первоначального приоритета используют текущий приоритет.