Распределенные алгоритмы (стр. 6 из 85)
Передача сообщений может быть выполнена с использованием мониторов или каналов, и это естественные средства для систем коммуникации, которые используются в аппаратуре распределенных систем (без разделяемой памяти). В самом деле, языки 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 такая, что каждый пакет или передается в узел адресата в течение с секунд, или теряется.