Способ определения порядка передачи сообщений Советский патент 1990 года по МПК G06F9/50 G06F13/36 

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

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

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

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

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

ел

ел о

Oi

0

Станция не может отличить передачи В И С; tq, - интервал форсированного Столкновения.

На фиг. 3 - показана временная диаграмма работы сети после столкновения трех передач. На ней обозначено: АхВхС столкновение трех передач (без детализации); А, В, С - успешные передачи станций А, В и С; X - успешная передача новой активной Станции X; tp; - паузы между передачами (i 1,2,3); Тп2 - пауза между Передачами С и X; Тхд - время ожидания доступа к общему каналу станций X.

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

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

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

5

0

5

0

5

0

5

0

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

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

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

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

Хотя на фиг. 2 показаны случаи m 2 и m 3, предлагаемый способ не ограничивается этими примерами. Аналогично измеряют четыре и более интервала в случае тЬ 4. Кроме того, вместо Тд и Tj- во всех случаях можно мерить и использовать в дальнейшем, например, Тд Tq - tq, и/или

5

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

После измерения длительностей всех передач одного процесса столкновения, т.е. после окончания процесса столкновения, станции - участницы этого столкновения находящиеся в состоянии ПД начинают Формирование двух интервалов времени - Тпо и , где Тпо - минимальная пауза между передачами, a Tnl t5 (например, 5,2 икс как в прототипе). Одновременно на каждой из этих станций сравнивают результаты своих измерений и устанавливают очередь, например, в порядке убывающих величин измеренных интервалов. Так, например, для процесса по фиг. 2в получается Tq Тс Tg, тем самым каждая станция определила свое место в очереди. Первая - станция А (так как Та Tg, Tc), вторая - С (так как Та4тс т8 ) a третья - В (так как Т„, ТЛ TV). Очередь можно устаLa с ТЈ) новить и в возрастающем порядке, т.е.

Т g- Tt - Td для этого же примера.

Q

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

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

Если в это время появляется новая активная станция X, то она переходит в состояние А2 и ожидает освобождение общего канала. Но т.к. t„ Тп2 (i 1,2,3), то общий канал для ее занят до тех пор, пока все участники

0

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

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

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

Если же первая передача начинается и проходит нормально, то затем и вообще каждый раз, как только станция

в А1 обнаруживает успешную передачу в jo пеРвого столкновения,

общем канале, они повышают свое место в очереди (вторая станция становится первой, третья - второй, и т.д.), а новая первая станция переходит в состояние АО. После исчезновения в общем канале несущей очередная первая станция в АО снова формирует Тпо, а остальные станции (в А1) формируют Tnl и т.д.,, как уже изложеВозможные значения чиваются величинами 2t допустимо и Тп2 С но наиболее предпочтит ся величины t5 Тп2 6 образом, для разных ус тации можно установить ходящее значение Тп2,о либо лучшее заполнение

0

ты. Затем в общем канале появляется пауза Тп2 2ts, показывающая, что все участники столкновения уже передали свои пакеты, и поэтому станция X переходит в состояние ПД (начинает свою передачу).

Теперь введем условие Тп2 ts. Если все станции правильно определили свои места в очереди, то работа ЛВС ничем не отличается от уже изложенного, только пауза Тп2 короче. Но по причинам, которые ниже рассмотрены подробнее, может случиться, что какое-то место в очереди осталось пустым. Тогда соответствующая передача начинается и в общем канале появляется пауза. Как уже было сказано, как только эта пауза становится равной ts Tnl, станции из А1 начинают с передачу. В данном случае одновременно с ними начинает передачу и X, возникает столкновение и т.д., но теперь уже участвует и станция X, не ожидая пока закончат передачу все участники

5

0

пеРвого столкновения,

Возможные значения Тп2 не ограничиваются величинами 2t3 и t5, т.к. допустимо и Тп2 С также Тп2 2 ts, но наиболее предпочтительными являются величины t5 Тп2 6 2ts. Таким образом, для разных условий эксплуатации можно установить наиболее подходящее значение Тп2,обеспечивающее либо лучшее заполнение общего канала

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

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

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

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

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

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

5

0

5

0

5

0

5

0

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

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

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

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

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

в

tp

- т„

фиг.1

1ШШ

-г-ъ -

3

nz

Фм.г

т