Реферат: Распределенные алгоритмы
Передача сообщений может быть выполнена с использованием мониторов или каналов, и это естественные средства для систем коммуникации, которые используются в аппаратуре распределенных систем (без разделяемой памяти). В самом деле, языки OCCAM и ADA были разработаны с идеей использования их для физически распределенных приложений.
Рис 1.4 Слоеная сетевая архитектура
Программное обеспечение для выполнения компьютерных сетей связей очень усложнено. В этом разделе объяснено, как это программное обеспечение обычно структурируется в ациклически зависимых модулях названных уровнями (Подраздел 1.2.1). Мы обсуждаем два стандарта с сетевой архитектурой, а именно, модель МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО СТАНДАРТИЗАЦИИ Соединения Открытых систем, стандарт для глобальных сетей, и дополнительного стандарта IEEE для локальных сетей (Подразделы, 1.2.2 и 1.2.3). Также языки, используемые для программирования распределили системы, кратко обсуждены (Подраздел 1.2.4).
Сложность задач, выполняемых подсистемой связи распределенной системы требует, чтобы эта подсистема была разработана высоко структурированным способом. К этому моменту, сети всегда организовываются как совокупность модулей, каждое выполнение очень специфическая функция и основывающаяся на услугах, предлагаемых другими модулями. В сетевых организациях имеется всегда строгая иерархия между этими модулями, потому что каждый модуль исключительно использует услуги, предлагаемые предыдущим модулем. Модули названы уровнями или уровнями в контексте сетевой реализации; см. 1.4 Рисунок. Каждый уровень осуществляет часть функциональных возможностей, требуемых для реализации сети и полагается на уровень только ниже этого. Услуги, предлагаемые i уровнем i + 1 уровню точно описаны в интерфейсе i уровня и i + 1 уровня (кратко, i / (i + 1) интерфейс). При проектировании сети, в первую очередь, нужно определить число уровней и интерфейсов между последующими уровнями.
Функциональные возможности каждого уровня должны быть выполнены распределенным алгоритмом, таким, что алгоритм для i уровня решает "проблему", определенную i / (i + 1) интерфейсом, согласно "предположениям", определенным в (i — l) /i интерфейсе. Например, (i — 1) /i интерфейс может определять, что сообщения транспортируются из узла p к узлу q, но некоторые сообщения могут быть потеряны, в то время как i / (i + 1) интерфейс определяет, что сообщения передаются от p до q надежно. Алгоритмическая проблема для i уровня затем - выполнить надежное прохождение сообщения, используя ненадежное прохождение сообщения, что обычно делается с использованием подтверждения и перепередачи потерянных сообщений (см. Подраздел, 1.3.1 и Главу 3). Решение этой проблемы определяет тип сообщений, обменянных процессами i уровня и значение этих сообщений, т.е., как процессы должны реагировать на эти сообщения. Правила и соглашения, используемые в "сеансе связи" между процессами i уровня упоминаются как layer-i протокол. Самый низкий уровень иерархии (уровень 0 на Рисунке 1.4) - всегда аппаратный уровень. Интерфейс 0/1 описывает процедуры, которыми уровень i может передать необработанную информацию через соединяющие провода, и описание уровня непосредственно определяет то, какие типы провода используются, сколько вольт представляют единицу или ноль, и т.д. Важное наблюдение - то, что изменение в реализации уровня 0 (замена проводов другими проводами или спутниковыми подключениями) не требует, чтобы интерфейс 0/1 был изменен. Те же самые условия в более высоких уровнях: интерфейсы уровня служат экраном от реализация уровня для других уровней, и реализация может быть изменена без того, чтобы воздействовать на другие уровни. Под сетевой архитектурой мы понимаем совокупность уровней и сопровождающих описаний всех интерфейсов и протоколов. Поскольку сеть может содержать узлы, произведенные различными изготовителями, программируемые программным обеспечением, написанным различными компаниями, важно, чтобы изделия различных компаний являлись совместимыми. Важность совместимости была признана во всем мире и следовательно стандартные сетевые архитектуры были разработаны. В следующем подразделе два стандарта обсуждаются, что получило "официальное" статус, потому что они приняты влиятельными организациями (МЕЖДУНАРОДНАЯ ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ, и Институт Электрических и Электронных Инженеров, IEEE). Протокол управления передачей / internet протокол (TCP/IP) - совокупность протоколов, используемых в Internet. TCP/IP - не официальный стандарт, но используется настолько широко, что стал фактическим стандартом. Семейство протоколов TCP/IP (см. Davidson [Dav88] для введения) структурирован согласно уровням OSI модели, обсужденной в следующем подразделе, но протоколы могут использоваться в глобальных сетях также как в локальных сетях.
Более высокие уровни содержат протоколы для электронной почты (простой протокол передачи почты - SMTP), передача файлов (протокол передачи файлов, FTP), и двунаправленная связь для удаленного входа в систему (Telnet).
МЕЖДУНАРОДНАЯ ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ установила стандарт для компьютерных изделий(программ) для работы с сетями типа тех, которые используются (главным образом) в глобальных сетях. Их стандарт для сетевой архитектуры назван Соединением открытых систем (OSI) ссылочной моделью, и будет описан кратко в этом подразделе. Потому что стандарт не полностью соответствующий для использования в локальных сетях, дополнительные стандарты IEEE для локальных сетей обсуждены в следующем подразделе. Модель ссылки OSI состоит из семи уровней, а именно физического, связи данных, сети, транспорта, сеанса, представления, и уровней прикладной программы. Ссылочная модель определяет интерфейсы между уровнями и обеспечивает, для каждого уровня, один или большее количество стандартных протоколов (распределенные алгоритмы, чтобы выполнить уровень).
Физический (1) уровень. Цель физического уровня состоит в том, чтобы передать последовательности битов по каналу связи. Поскольку имя уровня предполагает, что эта цель достигнута посредством физического подключения между двумя узлами, типа телефонной линии, волоконно-оптического подключения, или спутникового подключения. Проект уровня непосредственно - вполне вопрос для инженеров - электриков, в то время как интерфейс 1/2 определяет процедуры, которыми следующий уровень вызывает услуги физического уровня. Обслуживание физического уровня не надежно; поток битов может быть попорчен в течение передачи.
Канальный уровень (2). Цель канального уровня состоит в том, чтобы маскировать ненадежность физического уровня, то есть обеспечивать надежную связь с более высокими уровнями. Уровень связи данных только осуществляет надежное подключение между узлами, которые непосредственно связаны физической связью, потому что он сформирован непосредственно над физическим уровнем. (Связь между несмежными узлами выполнена в сетевом уровне.) Чтобы достигнуть цели, уровень делит поток битов на части фиксированной длины, названные кадрами. Приемник кадра может проверять(отмечать), был ли кадр получен правильно, проверяя контрольную сумму, которая является некоторой избыточной информацией, добавленной к каждому кадру. Имеется обратная связь от приемника до отправителя, чтобы сообщить отправителю относительно правильно или неправильно полученного кадра; эта обратная связь происходит посредством сообщений подтверждения.
Отправитель пошлет кадр снова, если оказалось, что он получен неправильно или полностью потерян. Общие принципы, объясненные в предыдущем параграфе могут быть усовершенствованы к ряду различных протоколов связи данных. Например, сообщение подтверждения может быть послано для кадров, которые получены (положительные подтверждения) или для кадров, которые отсутствуют из совокупности полученных кадров (отрицательные подтверждения). Окончательная ответственность за правильную передачу всех кадров может быть на отправителе или стороне приемника. Подтверждения могут быть посланы для одиночных кадров или блоков кадров, кадры могут иметь числа последовательности или не иметь, и т.д.
Сетевой уровень (3). Цель сетевого уровня состоит в том, чтобы обеспечить средства связи между всеми парами узлов, не только связанных физическим каналом. Этот уровень должен выбрать маршруты через сеть, используемую для связи между не-смежными узлами и должен управлять загрузкой движения в каждом узле и канале. Выбор маршрутов обычно основан на информации относительно сетевой топологии, содержащейся в маршрутизации таблиц, сохраненных в каждом узле. Сетевой уровень содержит алгоритмы, чтобы модифицировать таблицы маршрутизации, если топология сети изменилась (вследствие сбоя канала или восстановления). Такой сбой или восстановление обнаруживается канальным уровнем связи. Хотя канальный уровень обеспечивает надежное обслуживание у сетевого уровня, обслуживание, предлагаемое сетевым уровнем не надежно. Сообщения (названные пакетами в этом уровне) посланные от одного узла до другого могут следовать различными путями, вызывая опасность, что одно сообщение настигнет другое. Вследствие сбоев узла сообщения могут быть потеряны (узел может накрыться во время хранения cообщения), и вследствие лишних сообщений перепередач могут даже быть дублированы. Уровень может гарантировать ограниченному пакету срок службы; то есть, существует константа c такая, что каждый пакет или передается в узел адресата в течение с секунд, или теряется.
Транспортный уровень (4). Цель транспортного уровня состоит в том, чтобы маскировать ненадежность, представленную сетевым уровнем, то есть, обеспечивать надежную связь между любыми двумя узлами. Проблема была бы подобна той решенной канальным уровнем, но это еще усложнено возможностью дублирования и переупорядочения сообщений. Это делает невозможным использовать циклические числа последовательности, если ограничение на срок службы пакета не гарантируется сетевым уровнем.
Алгоритмы, используемые для управления передачи в транспортном уровне используют подобные методы для алгоритмов в канальном уровне: числа последовательности, обратная связь через подтверждения, и перепередачи.
Уровень сеанса (5). Цель уровня сеанса состоит в том, чтобы обеспечить средства для поддержания подключений между процессами в различных узлах. Подключение может быть открыто и закрыто и между открытием, и закрытием подключение может использоваться для обмена данных, используя адрес сеанса скорее, чем повторение адреса удаленного процесса с каждым сообщением. Уровень сеанса использует надежную непрерывную связь, предлагаемую транспортным уровнем, но структурирует передаваемые сообщения в сеансы. Сеанс может использоваться для передачи файла или удаленного входа в систему. Уровень сеанса может обеспечивать механизмы для восстановления, если узел терпит крах в течение сеанса и для взаимного исключения, если критические операции не могут выполняться на обоих концах одновременно.
Уровень представления (6). Цель уровня представления состоит в том, чтобы выполнить преобразование данных, где представление информации в одном узле отличается от представления в другом узле или не подходящее для передачи. Ниже этого уровня (то есть, при интерфейсе 5/6) данные находятся в передавабельной и стандартизированной форме, в то время как выше этого уровня (то есть, при интерфейсе 6/7) данные находятся в пользовательско - или компьютерно - специфической форме. Уровень выполняет сжатие данных и декомпрессию, чтобы уменьшить количество данных, переданных через более низкие уровни. Уровень выполняет шифрование данных и расшифровку, чтобы гарантировать конфиденциальность и целостность в присутствии злонамеренных сторон, которые стремятся получать или разрушать переданные данные.
Уровень прикладной программы (7). Цель уровня прикладной программы состоит в том, чтобы выполнять конкретные требования пользователя типа передачи файла, электронной почты, информационных табло, или виртуальных терминалов. Широкое разнообразие возможных прикладных программ делает невозможным стандартизировать полные функциональные возможности этого уровня, но для некоторых из прикладных программ, перечисленных здесь, стандарты были предложены.
1.2.3 OSI Модель в локальных сетях: IEEE Стандарты
На проект ссылочной модели OSI влияют в большой степени архитектуры существующих глобальных сетей. Технология, используемая в локальных сетях налагает различные программные требования, и из-за этих требований некоторые из уровней могут почти совсем отсутствовать в локальных сетях. Если сетевая организация полагается на общую шину, общедоступную всеми узлам (см. Подраздел 1.1.4), то сетевой уровень почти пуст, потому что каждая пара узлов связана непосредственно через шину. Проект транспортного уровня очень упрощен ограниченным количеством недетерминизма представленного шиной, по сравнению с промежуточной двухточечной сетью. Напротив, канальный уровень усложнен фактом, что к той же самой физической среде обращается потенциально большое количество узлов. В ответе на эти проблемы IEEE одобрил дополнительные стандарты, покрывая только более низкие уровни OSI иерархии, для использования в локальных сетях (или, если быть более точным, во всех сетях, которые являются структурированными шиной скорее, чем двухточечными соединениями). Потому что никакой одиночный стандарт не мог бы быть достаточно общий, чтобы охватить все сети уже широко использующиеся, IEEE одобрил три различных, несовместимых стандарта, а именно МНОЖЕСТВЕННЫЙ ДОСТУП С ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ КОНФЛИКТОВ, маркерную шину , и эстафетное кольцо. Канальный уровень заменен двумя подуровнями, а именно управление доступом к среде и подуровни управления логическим соединением.
Физический (1) уровень. Цель физического уровня в стандартах IEEE подобна таковому первоначального стандарта МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО СТАНДАРТИЗАЦИИ, а именно передавать последовательности битов. Фактические стандартные описания (тип монтажа и т.д.), однако, радикально различны, вследствие того, что вся связь происходит через общедоступную среду, а не через двухточечные подключения.
Medium-access-control подуровень (2a). Цель этого подуровня состоит в том, чтобы решить конфликты, которые возникают между узлами, которые хотят использовать общедоступную среду связи. Статичный подход раз и навсегда планировал бы интервалы времени, в течение которых каждому узлу позволяют использовать среду. Этот метод теряет много пропускной способности, однако, если только несколько узлов имеют данные, чтобы передавать, и все другие узлы тихи, среда остается в простое в течение времен, планируемых для тихих узлов. В шинах маркера и эстафетных кольцах доступ к среде находится по карусельному принципу: узлы циркулируют привилегию, названную маркером, среди них, и узлу, задерживающему этот маркер, позволяют использовать среду. Если узел, задерживающий маркер, не имеет никаких данных, чтобы передать, он передает маркер к следующему узлу. В эстафетном кольце циклический порядок, в котором узлы получают их право хода, определен физической топологией подключения (который, действительно, кольцо), в то время как в шине маркера, циклический порядок определен динамически основываясь на порядке адресов узлов. В стандарте МНОЖЕСТВЕННОГО ДОСТУПА С ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ КОНФЛИКТОВ узлы наблюдают, когда среда неактивна, и если так, то им позволяют послать. Если два или больше узла запускают посылку (приблизительно) одновременно, имеется проверка на пересечение, которое обнаруживается, что заставляет каждый узел прерывать передачу и пытаться снова в более позднее время.
Logical-link-control подуровень (2b). Цель этого уровня сравнима с целью канального уровня в OSI модели, а именно: управлять обменом данными между узлами. Уровень обеспечивает управление ошибками и управление потоком данных, используя методы, подобные тем использованных в OSI протоколах, а именно числа последовательности и подтверждения. Видящийся с точки зрения более высоких уровней, logical-link-control подуровень появляется подобно сетевому уровню OSI модели. Действительно, связь между любой парой узлов происходит без того, чтобы использовать промежуточные узлы, и может быть обработана непосредственно logical-link-control подуровнем. Отдельный сетевой уровень не следовало бы выполнять в локальных сетях; вместо этого, транспортный уровень сформирован непосредственно на верхней части logical-link-control подуровня.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
