Способ определения порядка передачи сообщений

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (g1)g G 06 F 9/46

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР ((ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4280903/24-24 (22) 08.07.87 (46) 15.03.90. Бюл. К - 10 (71) Институт электроники и вычислительной техники АН ЛатвССР (72) Р ..Ф. Баумгарт, Д. Х. Зибинь и С. Б. Трайнин (53) 681.325(088.8) (56) Патент США Р 4063220, кл . H 04 Q 9/00, 1979.

Локальные вычислительные сети.

Опыт международной стандартизации

МЦНТИ. — М,, 1984, вып. 27, с. 5358, 92-1 23. (54) СПОСОБ ОПРЕДЕЛЕНИЯ ПОРЯДКА ПЕРЕДАЧИ СООБЦЕНИ11 (57) Изобретение относится к вычислительной технике, в частности предназначено для использования в локальных вычислительных сетях с шинной тополоИзобретение относится к вычислительной технике и предназначено для использования в локальных вычислительных сетях с шинной топологией для управления передачей пакетов данных через общий канал..

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

На фиг. 1 показана диаграмма состояний и переходов; на фиг. 2 — временные диаграммы процессов столкновения передач; на фиг. 3 — временная диаграмма работы сети после столкновения передач °

На фиг. 1 показана диаграмма состояний и переходов для данного спо„„ЯО„, 1550516 А1

2 гией для управления передачей пакетов данных через общий канал. Цель изобретения — уменьшение времени разрешения конфликтных ситуаций. Способ определения порядка передачи сообщений заключается в том, что на каждой станции, осуществляющей передачу, измеряют длительность своей передачи от ее начала до прекращения передачи в случае обнаружения столкновения, интервал от начала первого столкновения до конца второго столкновения или до начала первой паузы, интервал от начала второго столкновения или от конца первой паузы до конца третьего столкновения или до начала второй паузы и т.д., сравнивают длительность 8 своей передачи с другими измеренными интервалами и на основании получечных результатов устанавливают очередность С передачи . 3 ил . соба и использованы следующие обозначения: ИСХ вЂ” исходное состояние; А0 нулевое активное состояние, Л! — первое активное состояние; А2 — второе активное состояние; ПД вЂ” передача. .На фиг. 2 показаны временные диаграммы процессов столкновений двух (а) и трех (б,в,г) передач. На них показаны временные интервалы: Т а первый измеряемый интервал, длительность передачи А; Т - — второй измеряемый интервал, длительность йередачи В; T — третий измеряемый интервал, длительность передачи С; Т> пауза между передачами В и С; Т> ошибочный интервал времени, если

1550516

Станция не может отличить передачи В

М С; t — интервал форсированного

Столкновения.

На фиг ° 3 — показана временная ди5 аграмма работы сети после столкновеНия трех передач. На ней обозначено:

hxBxC — столкновение трех передач (без детализации); А, В, С вЂ” успешные передачи станций А, В и С; Х— успешная передача новой активной станции Х; tp, — паузы между передаЧами (i = 1,2,3); Тп2 — пауза между ередачйми С и Х; Тхд — время ожидания доступа к общему каналу станций Х. 15

В локальной вычислительной сети с использованием множественного достуа с контролем несущей и обнаружением талкновений (МДКН/OC) все станции

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

8 нем пакета данных, проверяют его адрес назначения. Если адрес назначе— ния пакета совпадает с адресом данНой станции, то последняя принимает

Этот пакет. С учетом этих пояснений рассмотрим сущность заявляемого способа.

В исходном состоянии находятся

Ьсе пассивные станции (не имевшие гоO 0âoãî к передаче пакета данных). Они пибо ожидают пакет данных от своих верхних уровней, либо сами его форми35 руют. Они также слушают обший канал

8 определяют его состояние ("Свободен", "успешная передача", СтолкноВение ) è, åñëè íóæíî, ..÷îãóò прини мать их адресованные пакеты данных.

При появлении в станции готового к гередаче пакета данных, эта станция переходит в состояние А2 (переход 1 на фиг. 1).

Станции, находящиеся в состояниях

ИСХ и А2 формируют интервалы времени

Тп2 при каждом исчезновении несущей в общем канале. Дпя этих станций об.щий канал считается свободным не cpaS0 зу, а после истечения упомянутого интервала Тп2, если во время его формирования не появилась несущая новой передачи, Если же во время формирования Тп2 появляется несущая новой передачи, то формирование Тп2 прекраща- 55 ется, а общий канал для данной станции считается непрерывно занятым. В прототипе ТП2 = Тпо = 9,6 мкс. Это минимальная допустимая пауза между передачами в общем канале, необходимая для того, чтобы конец одной передачи не сливался с началом другой.

В предлагаемом способе обычно t 6

Тп2 2

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

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

Если же в состоянии ПД окажутся не менее двух станций, то каждая из них обнаружит чужие передачи (т-,е. обнаружит столкновение передач). Тогда станция фиксирует передачу (т.е. продолжает ее в течение заданного например, 3,2 мкс при скорости передачи 10 Мбит/с, т.е. четыре байта или 32 бита) и потом прекращает свою передачу (также, как в прототипе).

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

m 2) или Т, Т и Т, (при m 3) и т.д., чтобы получить необходимую для управления передачей информацию.

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

Аналогично измеряют четыре и более интервала в случае ш Ъ 4. Кроме того, вместо Т и Т во всех случаях можно мерить и использовать в дальнейшем, например, Тц = Т вЂ” t и/или

Y = Тр — t (фиг. 2а), если это удобнее при практической реализации, так как величина t небольшая и фикФ сированная и ее прибавление или вычи" тание не имеет существенного значения.

5 155

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

ПД начинают формирование двух интервалов времени — Тпо и Т 1, где Тпо минимальная пауза между передачами, а Тпl = t> (например, 51,2 мкс как в прототипе). Одновременно на каждой из этих станций сравнивают результаты своих измерений и устанавливают очередь, например, в порядке убывающих величин измеренных интервалов. Так, например, для процесса по фиг. 2в получается Т Тс ) Т, тем самым каждая станция определила свое место в очереди . Первая — станция А (так как Тд ) Т, T ), вторая — С (так как

Тц) Т„) Т ), а третья — В (так как Т, Т ) Т ) . Очередь можно устаа новить и в возрастаюшем порядке, т.е, Т р C Т с Т для этого же примера.

Это всего лишь изменяет порядок станций в очереди, что не имеет никакого значения. Главное, чтобы был какой-тс один общий для всех станций порядок.

После определения своего места в очереди станция, получившая первое место„-переходит в состояние АС, а все остальные (не первые) станции . переходят в состояние Al (переход 6).

B АО станция продолжает формировать интервал Хпо, а в Al — интервал Тпl.

По истечении Тпо данная станция из

АО переходит в состояние ПД, т.е. начинает передачу. Если по причинам, рассмотренным ниже, первая передача не начинается, то по истечении Тпl станции из Al переходят в состояние

ПД, т.е. начинают передачи. В случае

m = 2 такая станция только одна, поэтому она успешно передает свой пакет.

В случае m 3 последует повторное столкновение °

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

55 первого столкновения.

Возможные значения Тп2 не ограничиваются величинами 2t и t» т.к. допустимо и Тп2 (t z» также Тп2 > 2 Т но наиболее предпочтительными являются величины t+ (Тп2 2 э. Таким образом, для разных условий эксплуатации можно установить наиболее подходящее значение Тп2,обеспечивающее либо лучшее заполнение общего канала

0516 но, пока все станции по порядку перейдут из Al в ЛО и потом в ПД, т.е. пока все участники столкновения не передадут свои пакеты данных.

Рассмотрим работу ЛВС с применением предлагаемого способа управления передачами и при условии Тп2 = 2й ., Как уже сказано, при малой нагрузке, пока нет столкновений, работа ЛВС происходит также, как в прототипе, поэтому начнем со столкновения, например, трех передач ВхВхС (фиг. 3).

После измерения интервалов Т, ТБ и

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

Если в это время появляется новая

2р активная станция Х, то она переходит в состояние А2 и ожидает освобождение общего канала. Но т.к. t c Тп2 (i — 1,2,3), то общий канал для ее занят до тех пор, пока все участники столкновения не передадут свои пакеты. Затем в общем канале появляется пауза Тп2 = 2t» показывающая, что все участники столкновения уже передали свои пакеты, и поэтому станция

Х переходит в состояние ПД (начинает свою передачу).

Теперь введем условие Тп2 .Если все станции правильно определили свои места в очереди, то работа

ЛВС ничем не отличается от уже изложенного, только пауза Тп2 короче. Но по причинам, которые ниже рассмотрены подробнее, может случиться, что какое-то место в очереди осталось

40 пустым. Тогда соответствующая передача начинается и в общем канале появляется пауза. Как уже было сказано, как только эта пауза становится равной t = Тпl, станции из Al начинают

45 передачу ° В данном случае одновременно с ними начинает передачу и Х, возникает столкновение и т,д., но теперь уже участвует и станция Х, не ожидая пока закончат передачу все участники

1550516 передачами, либо меньшее среднее вре- мя ожидания доступа Тхд.

Наконец, рассмотрим некоторые ча- с Гные случаи в работе ЛВС.

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

К к только станции обнаруживают равенство Тс, = Т, они переходят в исх эдное состояние и прекращают попытк передачи данного пакета.

Другой частный случай показан на ф г. 2г, когда на входе станции A конец передачи В совпадает с началом 25 передачи С. Тогда станция А не может различить интервалы Тр и Тс и измеряе г один общий интервал Т . В результате этого в очереди может оказаться лИбо две первые, либо две вторые стан- ЗО ц и. Кроме того, какое † место в очереди может оказаться пустым.

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

35 встречаться очень редко.

С увеличением нагрузки увеличивается и число m участников столкновения. Соответственно, число измеряемых 4О интервалов времени также увеличивается, а вероятность появления их равенства и других частных случаев также увеличивается, что могло бы ухудшить работу.ЛВС. Это можно легко устранить например, если m -> N гпе М вЂ” максимальное число участников столкновения, с которым аппаратура может справиться, то все m участники этого . столкновения переводятся в исходное

5О состояние также, как в грототипе после заданного максимального числа (16) неудачных попыгок передачи. Другими словами, часть входной нагрузки сбрасывается, за то остальная часть обслуживается качественно и эффективно, т.е. устраняется возможное ухудшение работы ЛВС при перегрузке.

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

ЛВС с использованием МДКН/ОС.

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

Формула и з обретения

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

15505! 6

1550516

Составитель M. Сорочан

Редактор Л. Пчолинская Техред M.Äèäûê Корректор Л. Бескид

Заказ 274 Тираж 567 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035,„ Москва, И-35, Раушская наб., д. 4/5 .

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101