вариант+начала

вариант, оборонительный — см. вариант, защитный

технология коммутации
-
[Интент]

Современные технологии коммутации
[ http://www.xnets.ru/plugins/content/content.php?content.84]

Статья подготовлена на основании материалов опубликованных в журналах "LAN", "Сети и системы связи", в книге В.Олифер и Н.Олифер "Новые технологии и оборудование IP-сетей", на сайтах www.citforum.ru и опубликована в журнале "Компьютерные решения" NN4-6 за 2000 год.

• Введение
• Коммутация первого уровня.
• Коммутация второго уровня.
• Коммутация третьего уровня.
• Коммутация четвертого уровня.
• Критерии выбора оборудования, физическая и логическая структура сети
• Качество обслуживания (QoS) и принципы задания приоритетов
• Заключение

Введение

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

Бросив взгляд назад - увидим, что развитие активного оборудования сетей шло в соответствии с требованиями к полосе пропускания и надежности. Требования, предъявляемые к большей надежности, привели к отказу от применения в качестве среды передачи коаксиального кабеля и перевода сетей на витую пару. В результате такого перехода отказ работы соединения между одной из рабочих станций и концентратором перестал сказываться на работе других рабочих станций сети. Но увеличения производительности данный переход не принес, так как концентраторы используют разделяемую (на всех пользователей в сегменте) полосу пропускания. По сути, изменилась только физическая топология сети - с общей шины на звезду, а логическая топология по-прежнему осталась - общей шиной.

Дальнейшее развитие сетей шло по нескольким путям:

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

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

Большую эффективность в работе сети принесло сегментирование сетей с использованием технология коммутации пакетов. Коммутация наиболее действенна в следующих вариантах:

Вариант 1, именуемый связью "многие со многими" – это одноранговые сети, когда одновременно существуют потоки данных между парами рабочих станций. При этом предпочтительнее иметь коммутатор, у которого все порты имеют одинаковую скорость, (см. Рисунок 1).

Вариант 2, именуемый связью "один со многими" – это сети клиент-сервер, когда все рабочие станции работают с файлами или базой данных сервера. В данном случае предпочтительнее иметь коммутатор, у которого порты для подключения рабочих станций имеют одинаковую небольшую скорость, а порт, к которому подключается сервер, имеет большую скорость,(см. Рисунок 2).

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

Проблемы с трафиком, связанные с маршрутизацией, проявляются наиболее остро в средних и крупных компаниях, а также в деятельности операторов Internet, так как они вынуждены иметь дело с большими объемами IP-трафика, причем этот трафик должен передаваться своевременно и эффективно.

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

Рассмотрению технологий коммутации и посвящена данная статья.

Коммутация первого уровня

Термин "коммутация первого уровня" в современной технической литературе практически не описывается. Для начала дадим определение, с какими характеристиками имеет дело физический или первый уровень модели OSI:

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

Смысл коммутации на первом уровне модели OSI означает физическое (по названию уровня) соединение. Из примеров коммутации первого уровня можно привести релейные коммутаторы некоторых старых телефонных и селекторных систем. В более новых телефонных системах коммутация первого уровня применяется совместно с различными способами сигнализации вызовов и усиления сигналов. В сетях передачи данных данная технология применяется в полностью оптических коммутаторах.

Коммутация второго уровня

Рассматривая свойства второго уровня модели OSI и его классическое определение, увидим, что данному уровню принадлежит основная доля коммутирующих свойств.

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

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

С технологической точки зрения, коммутатор локальных сетей представляет собой устройство, основное назначение которого - максимальное ускорение передачи данных за счет параллельно существующих потоков между узлами сети. В этом - его главное отличие от других традиционных устройств локальных сетей – концентраторов (Hub), предоставляющих всем потокам данных сети всего один канал передачи данных.

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

Коммутаторы локальных сетей в своем основном варианте, ставшем классическим уже с начала 90-х годов, работают на втором уровне модели OSI, применяя свою высокопроизводительную параллельную архитектуру для продвижения кадров канальных протоколов. Другими словами, ими выполняются алгоритмы работы моста, описанные в стандартах IEEE 802.1D и 802.1H. Также они имеют и много других дополнительных функций, часть которых вошла в новую редакцию стандарта 802.1D-1998, а часть остается пока не стандартизованной.

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

Существует 3 варианта архитектуры коммутаторов:
 

• переключение (cross-bar) с буферизацией на входе,
• самомаршрутизация (self-route) с разделяемой памятью
• высокоскоростная шина.

На рисунке 3 показана блок-схема коммутатора с архитектурой, используемой для поочередного соединения пар портов. В любой момент такой коммутатор может обеспечить организацию только одного соединения (пара портов). При невысоком уровне трафика не требуется хранение данных в памяти перед отправкой в порт назначения - такой вариант называется коммутацией на лету cut-through. Однако, коммутаторы cross-bar требуют буферизации на входе от каждого порта, поскольку в случае использования единственно возможного соединения коммутатор блокируется (рисунок 4). Несмотря на малую стоимость и высокую скорость продвижения на рынок, коммутаторы класса cross-bar слишком примитивны для эффективной трансляции между низкоскоростными интерфейсами Ethernet или token ring и высокоскоростными портами ATM и FDDI.

Коммутаторы с разделяемой памятью имеют общий входной буфер для всех портов, используемый как внутренняя магистраль устройства (backplane). Буферизагия данных перед их рассылкой (store-and-forward - сохранить и переслать) приводит к возникновению задержки. Однако, коммутаторы с разделяемой памятью, как показано на рисунке 5 не требуют организации специальной внутренней магистрали для передачи данных между портами, что обеспечивает им более низкую цену по сравнению с коммутаторами на базе высокоскоростной внутренней шины.

На рисунке 6 показана блок-схема коммутатора с высокоскоростной шиной, связывающей контроллеры ASIC. После того, как данные преобразуются в приемлемый для передачи по шине формат, они помещаются на шину и далее передаются в порт назначения. Поскольку шина может обеспечивать одновременную (паралельную) передачу потока данных от всех портов, такие коммутаторы часто называют "неблокируемыми" (non-blocking) - они не создают пробок на пути передачи данных.

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

Коммутация третьего уровня

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

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

Коммутация на третьем уровне - это аппаратная маршрутизация. Традиционные маршрутизаторы реализуют свои функции с помощью программно-управляемых процессоров, что будем называть программной маршрутизацией. Традиционные маршрутизаторы обычно продвигают пакеты со скоростью около 500000 пакетов в секунду. Коммутаторы третьего уровня сегодня работают со скоростью до 50 миллионов пакетов в секунду. Возможно и дальнейшее ее повышение, так как каждый интерфейсный модуль, как и в коммутаторе второго уровня, оснащен собственным процессором продвижения пакетов на основе ASIC. Так что наращивание количества модулей ведет к наращиванию производительности маршрутизации. Использование высокоскоростной технологии больших заказных интегральных схем (ASIC) является главной характеристикой, отличающей коммутаторы третьего уровня от традиционных маршрутизаторов. Коммутаторы 3-го уровня делятся на две категории: пакетные (Packet-by-Packet Layer 3 Switches, PPL3) и сквозные (Cut-Through Layer 3 Switches, CTL3). PPL3 - означает просто быструю маршрутизацию (Рисунок_7). CTL3 – маршрутизацию первого пакета и коммутацию всех остальных (Рисунок 8).

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

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

Наиболее "коммутаторная" версия высокоскоростной маршрутизации выглядит следующим образом (рисунок 9). Пусть коммутатор третьего уровня построен так, что в нем имеется информация о соответствии сетевых адресов (например, IP-адресов) адресам физического уровня (например, MAC-адресам) Все эти МАС-адреса обычным образом отображены в коммутационной таблице, независимо от того, принадлежат ли они данной сети или другим сетям.

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

Это описание носит схематический характер и не раскрывает способов решения возникающих при этом многочисленных проблем, например, проблемы построения таблицы соответствия IP-адресов и МАС-адресов

Примерами коммутаторов третьего уровня, работающих по этой схеме, являются коммутаторы SmartSwitch компании Cabletron. Компания Cabletron реализовала в них свой протокол ускоренной маршрутизации SecureFast Virtual Network, SFVN.

Для организации непосредственного взаимодействия рабочих станций без промежуточного маршрутизатора необходимо сконфигурировать каждую из них так, чтобы она считала собственный интерфейс маршрутизатором по умолчанию. При такой конфигурации станция пытается самостоятельно отправить любой пакет конечному узлу, даже если этот узел находится в другой сети. Так как в общем случае (см. рисунок 10) станции неизвестен МАС-адрес узла назначения, то она генерирует соответствующий ARP-запрос, который перехватывает коммутатор, поддерживающий протокол SFVN. В сети предполагается наличие сервера SFVN Server, являющегося полноценным маршрутизатором и поддерживающего общую ARP-таблицу всех узлов SFVN-сети. Сервер возвращает коммутатору МАС-адрес узла назначения, а коммутатор, в свою очередь, передает его исходной станции. Одновременно сервер SFVN передает коммутаторам сети инструкции о разрешении прохождения пакета с МАС-адресом узла назначения через границы виртуальных сетей. Затем исходная станция передает пакет в кадре, содержащем МАС-адрес узла назначения. Этот кадр проходит через коммутаторы, не вызывая обращения к их блокам маршрутизации. Отличие протокола SFVN компании Cabletron от - описанной выше общей схемы в том, что для нахождения МАС-адреса по IP-адресу в сети используется выделенный сервер.

Протокол Fast IP компании 3Com является еще одним примером реализации подхода с отображением IP-адреса на МАС-адрес. В этом протоколе основными действующими лицами являются сетевые адаптеры (что не удивительно, так как компания 3Com является признанным лидером в производстве сетевых адаптеров Ethernet) С одной стороны, такой подход требует изменения программного обеспечения драйверов сетевых адаптеров, и это минус Но зато не требуется изменять все остальное сетевое оборудование.

При необходимости передать пакет узлу назначения другой сети, исходный узел в соответствии с технологией Fast IP должен передать запрос по протоколу NHRP (Next Hop Routing Protocol) маршрутизатору сети. Маршрутизатор переправляет этот запрос узлу назначения, как обычный пакет Узел назначения, который также поддерживает Fast IP и NHRP, получив запрос, отвечает кадром, отсылаемым уже не маршрутизатору, а непосредственно узлу-источнику (по его МАС-адресу, содержащемуся в NHRP-запросе). После этого обмен идет на канальном уровне на основе известных МАС-адресов. Таким образом, снова маршрутизировался только первый пакет потока (как на рисунке 9 кратковременный поток), а все остальные коммутировались (как на рисунке 9 долговременный поток).

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

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

Рассмотрим этот подход на примере технологии NetFlow компании Cisco, реализованной в ее маршрутизаторах и коммутаторах. Для каждого пакета, поступающего на порт маршрутизатора, вычисляется хэш-функция от IP-адресов источника, назначения, портов UDP или TCP и поля TOS, характеризующего требуемое качество обслуживания. Во всех маршрутизаторах, поддерживающих данную технологию, через которые проходит данный пакет, в кэш-памяти портов запоминается соответствие значения хэш-функции и адресной информации, необходимой для быстрой передачи пакета следующему маршрутизатору. Таким образом, образуется квазивиртуальный канал (см. Рисунок 11), который позволяет быстро передавать по сети маршрутизаторов все последующие пакеты этого потока. При этом ускорение достигается за счет упрощения процедуры обработки пакета маршрутизатором - не просматриваются таблицы маршрутизации, не выполняются ARP-запросы.

Этот прием может использоваться в маршрутизаторах, вообще не поддерживающих коммутацию, а может быть перенесен в коммутаторы. В этом случае такие коммутаторы тоже называют коммутаторами третьего уровня. Примеров маршрутизаторов, использующих данный подход, являются маршрутизаторы Cisco 7500, а коммутаторов третьего уровня — коммутаторы Catalyst 5000 и 5500. Коммутаторы Catalyst выполняют усеченные функции описанной схемы, они не могут обрабатывать первые пакеты потоков и создавать новые записи о хэш-функциях и адресной информации потоков. Они просто получают данную информацию от маршрутизаторов 7500 и обрабатывают пакеты уже распознанных маршрутизаторами потоков.

Выше был рассмотрен способ ускоренной маршрутизации, основанный на концепции потока. Его сущность заключается в создании квазивиртуальных каналов в сетях, которые не поддерживают виртуальные каналы в обычном понимании этого термина, то есть сетях Ethernet, FDDI, Token Ring и т п. Следует отличать этот способ от способа ускоренной работы маршрутизаторов в сетях, поддерживающих технологию виртуальных каналов — АТМ, frame relay, X 25. В таких сетях создание виртуального канала является штатным режимом работы сетевых устройств. Виртуальные каналы создаются между двумя конечными точками, причем для потоков данных, требующих разного качества обслуживания (например, для данных разных приложений) может создаваться отдельный виртуальный канал. Хотя время создания виртуального канала существенно превышает время маршрутизации одного пакета, выигрыш достигается за счет последующей быстрой передачи потока данных по виртуальному каналу. Но в таких сетях возникает другая проблема — неэффективная передача коротких потоков, то есть потоков, состоящих из небольшого количества пакетов (классический пример — пакеты протокола DNS).

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

По такой схеме работает ставшая уже классической технология IP Switching компании Ipsilon. Для того чтобы сети коммутаторов АТМ передавали бы пакеты коротких потоков без установления виртуального канала, компания Ipsilon предложила встроить во все коммутаторы АТМ блоки IP-маршрутизации (рисунок 12), строящие обычные таблицы маршрутизации по обычным протоколам RIP и OSPF.

Компания Cisco Systems выдвинула в качестве альтернативы технологии IP Switching свою собственную технологию Tag Switching, но она не стала стандартной. В настоящее время IETF работает над стандартным протоколом обмена метками MPLS (Multi-Protocol Label Switching), который обобщает предложение компаний Ipsilon и Cisco, а также вносит некоторые новые детали и механизмы. Этот протокол ориентирован на поддержку качества обслуживания для виртуальных каналов, образованных метками.

Коммутация четвертого уровня

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

Некоторые производители заявляют, что их системы могут работать на втором, третьем и даже четвертом уровнях. Однако рассмотрение описания стека TCP/IP (рисунок 1), а также структуры пакетов IP и TCP (рисунки 2, 3), показывает, что коммутация четвертого уровня является фикцией, так как все относящиеся к коммутации функции осуществляются на уровне не выше третьего. А именно, термин коммутация четвертого уровня с точки зрения описания стека TCP/IP противоречий не имеет, за исключением того, что при коммутации должны указываться адреса компьютера (маршрутизатора) источника и компьютера (маршрутизатора) получателя. Пакеты TCP имеют поля локальный порт отправителя и локальный порт получателя (рисунок 3), несущие смысл точек входа в приложение (в программу), например Telnet с одной стороны, и точки входа (в данном контексте инкапсуляции) в уровень IP. Кроме того, в стеке TCP/IP именно уровень TCP занимается формированием пакетов из потока данных идущих от приложения. Пакеты IP (рисунок 2) имеют поля адреса компьютера (маршрутизатора) источника и компьютера (маршрутизатора) получателя и следовательно могут наряду с MAC адресами использоваться для коммутации. Тем не менее, название прижилось, к тому же практика показывает, что способность системы анализировать информацию прикладного уровня может оказаться полезной — в частности для управления трафиком. Таким образом, термин "зависимый от приложения" более точно отражает функции так называемых коммутаторов четвертого уровня.

Тематики

• сети вычислительные

EN

• switching technology

технология коммутации
-
[Интент]

Современные технологии коммутации
[ http://www.xnets.ru/plugins/content/content.php?content.84]

Статья подготовлена на основании материалов опубликованных в журналах "LAN", "Сети и системы связи", в книге В.Олифер и Н.Олифер "Новые технологии и оборудование IP-сетей", на сайтах www.citforum.ru и опубликована в журнале "Компьютерные решения" NN4-6 за 2000 год.

• Введение
• Коммутация первого уровня.
• Коммутация второго уровня.
• Коммутация третьего уровня.
• Коммутация четвертого уровня.
• Критерии выбора оборудования, физическая и логическая структура сети
• Качество обслуживания (QoS) и принципы задания приоритетов
• Заключение

Введение

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

Бросив взгляд назад - увидим, что развитие активного оборудования сетей шло в соответствии с требованиями к полосе пропускания и надежности. Требования, предъявляемые к большей надежности, привели к отказу от применения в качестве среды передачи коаксиального кабеля и перевода сетей на витую пару. В результате такого перехода отказ работы соединения между одной из рабочих станций и концентратором перестал сказываться на работе других рабочих станций сети. Но увеличения производительности данный переход не принес, так как концентраторы используют разделяемую (на всех пользователей в сегменте) полосу пропускания. По сути, изменилась только физическая топология сети - с общей шины на звезду, а логическая топология по-прежнему осталась - общей шиной.

Дальнейшее развитие сетей шло по нескольким путям:

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

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

Большую эффективность в работе сети принесло сегментирование сетей с использованием технология коммутации пакетов. Коммутация наиболее действенна в следующих вариантах:

Вариант 1, именуемый связью "многие со многими" – это одноранговые сети, когда одновременно существуют потоки данных между парами рабочих станций. При этом предпочтительнее иметь коммутатор, у которого все порты имеют одинаковую скорость, (см. Рисунок 1).

Вариант 2, именуемый связью "один со многими" – это сети клиент-сервер, когда все рабочие станции работают с файлами или базой данных сервера. В данном случае предпочтительнее иметь коммутатор, у которого порты для подключения рабочих станций имеют одинаковую небольшую скорость, а порт, к которому подключается сервер, имеет большую скорость,(см. Рисунок 2).

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

Проблемы с трафиком, связанные с маршрутизацией, проявляются наиболее остро в средних и крупных компаниях, а также в деятельности операторов Internet, так как они вынуждены иметь дело с большими объемами IP-трафика, причем этот трафик должен передаваться своевременно и эффективно.

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

Рассмотрению технологий коммутации и посвящена данная статья.

Коммутация первого уровня

Термин "коммутация первого уровня" в современной технической литературе практически не описывается. Для начала дадим определение, с какими характеристиками имеет дело физический или первый уровень модели OSI:

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

Смысл коммутации на первом уровне модели OSI означает физическое (по названию уровня) соединение. Из примеров коммутации первого уровня можно привести релейные коммутаторы некоторых старых телефонных и селекторных систем. В более новых телефонных системах коммутация первого уровня применяется совместно с различными способами сигнализации вызовов и усиления сигналов. В сетях передачи данных данная технология применяется в полностью оптических коммутаторах.

Коммутация второго уровня

Рассматривая свойства второго уровня модели OSI и его классическое определение, увидим, что данному уровню принадлежит основная доля коммутирующих свойств.

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

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

С технологической точки зрения, коммутатор локальных сетей представляет собой устройство, основное назначение которого - максимальное ускорение передачи данных за счет параллельно существующих потоков между узлами сети. В этом - его главное отличие от других традиционных устройств локальных сетей – концентраторов (Hub), предоставляющих всем потокам данных сети всего один канал передачи данных.

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

Коммутаторы локальных сетей в своем основном варианте, ставшем классическим уже с начала 90-х годов, работают на втором уровне модели OSI, применяя свою высокопроизводительную параллельную архитектуру для продвижения кадров канальных протоколов. Другими словами, ими выполняются алгоритмы работы моста, описанные в стандартах IEEE 802.1D и 802.1H. Также они имеют и много других дополнительных функций, часть которых вошла в новую редакцию стандарта 802.1D-1998, а часть остается пока не стандартизованной.

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

Существует 3 варианта архитектуры коммутаторов:
 

• переключение (cross-bar) с буферизацией на входе,
• самомаршрутизация (self-route) с разделяемой памятью
• высокоскоростная шина.

На рисунке 3 показана блок-схема коммутатора с архитектурой, используемой для поочередного соединения пар портов. В любой момент такой коммутатор может обеспечить организацию только одного соединения (пара портов). При невысоком уровне трафика не требуется хранение данных в памяти перед отправкой в порт назначения - такой вариант называется коммутацией на лету cut-through. Однако, коммутаторы cross-bar требуют буферизации на входе от каждого порта, поскольку в случае использования единственно возможного соединения коммутатор блокируется (рисунок 4). Несмотря на малую стоимость и высокую скорость продвижения на рынок, коммутаторы класса cross-bar слишком примитивны для эффективной трансляции между низкоскоростными интерфейсами Ethernet или token ring и высокоскоростными портами ATM и FDDI.

Коммутаторы с разделяемой памятью имеют общий входной буфер для всех портов, используемый как внутренняя магистраль устройства (backplane). Буферизагия данных перед их рассылкой (store-and-forward - сохранить и переслать) приводит к возникновению задержки. Однако, коммутаторы с разделяемой памятью, как показано на рисунке 5 не требуют организации специальной внутренней магистрали для передачи данных между портами, что обеспечивает им более низкую цену по сравнению с коммутаторами на базе высокоскоростной внутренней шины.

На рисунке 6 показана блок-схема коммутатора с высокоскоростной шиной, связывающей контроллеры ASIC. После того, как данные преобразуются в приемлемый для передачи по шине формат, они помещаются на шину и далее передаются в порт назначения. Поскольку шина может обеспечивать одновременную (паралельную) передачу потока данных от всех портов, такие коммутаторы часто называют "неблокируемыми" (non-blocking) - они не создают пробок на пути передачи данных.

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

Коммутация третьего уровня

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

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

Коммутация на третьем уровне - это аппаратная маршрутизация. Традиционные маршрутизаторы реализуют свои функции с помощью программно-управляемых процессоров, что будем называть программной маршрутизацией. Традиционные маршрутизаторы обычно продвигают пакеты со скоростью около 500000 пакетов в секунду. Коммутаторы третьего уровня сегодня работают со скоростью до 50 миллионов пакетов в секунду. Возможно и дальнейшее ее повышение, так как каждый интерфейсный модуль, как и в коммутаторе второго уровня, оснащен собственным процессором продвижения пакетов на основе ASIC. Так что наращивание количества модулей ведет к наращиванию производительности маршрутизации. Использование высокоскоростной технологии больших заказных интегральных схем (ASIC) является главной характеристикой, отличающей коммутаторы третьего уровня от традиционных маршрутизаторов. Коммутаторы 3-го уровня делятся на две категории: пакетные (Packet-by-Packet Layer 3 Switches, PPL3) и сквозные (Cut-Through Layer 3 Switches, CTL3). PPL3 - означает просто быструю маршрутизацию (Рисунок_7). CTL3 – маршрутизацию первого пакета и коммутацию всех остальных (Рисунок 8).

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

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

Наиболее "коммутаторная" версия высокоскоростной маршрутизации выглядит следующим образом (рисунок 9). Пусть коммутатор третьего уровня построен так, что в нем имеется информация о соответствии сетевых адресов (например, IP-адресов) адресам физического уровня (например, MAC-адресам) Все эти МАС-адреса обычным образом отображены в коммутационной таблице, независимо от того, принадлежат ли они данной сети или другим сетям.

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

Это описание носит схематический характер и не раскрывает способов решения возникающих при этом многочисленных проблем, например, проблемы построения таблицы соответствия IP-адресов и МАС-адресов

Примерами коммутаторов третьего уровня, работающих по этой схеме, являются коммутаторы SmartSwitch компании Cabletron. Компания Cabletron реализовала в них свой протокол ускоренной маршрутизации SecureFast Virtual Network, SFVN.

Для организации непосредственного взаимодействия рабочих станций без промежуточного маршрутизатора необходимо сконфигурировать каждую из них так, чтобы она считала собственный интерфейс маршрутизатором по умолчанию. При такой конфигурации станция пытается самостоятельно отправить любой пакет конечному узлу, даже если этот узел находится в другой сети. Так как в общем случае (см. рисунок 10) станции неизвестен МАС-адрес узла назначения, то она генерирует соответствующий ARP-запрос, который перехватывает коммутатор, поддерживающий протокол SFVN. В сети предполагается наличие сервера SFVN Server, являющегося полноценным маршрутизатором и поддерживающего общую ARP-таблицу всех узлов SFVN-сети. Сервер возвращает коммутатору МАС-адрес узла назначения, а коммутатор, в свою очередь, передает его исходной станции. Одновременно сервер SFVN передает коммутаторам сети инструкции о разрешении прохождения пакета с МАС-адресом узла назначения через границы виртуальных сетей. Затем исходная станция передает пакет в кадре, содержащем МАС-адрес узла назначения. Этот кадр проходит через коммутаторы, не вызывая обращения к их блокам маршрутизации. Отличие протокола SFVN компании Cabletron от - описанной выше общей схемы в том, что для нахождения МАС-адреса по IP-адресу в сети используется выделенный сервер.

Протокол Fast IP компании 3Com является еще одним примером реализации подхода с отображением IP-адреса на МАС-адрес. В этом протоколе основными действующими лицами являются сетевые адаптеры (что не удивительно, так как компания 3Com является признанным лидером в производстве сетевых адаптеров Ethernet) С одной стороны, такой подход требует изменения программного обеспечения драйверов сетевых адаптеров, и это минус Но зато не требуется изменять все остальное сетевое оборудование.

При необходимости передать пакет узлу назначения другой сети, исходный узел в соответствии с технологией Fast IP должен передать запрос по протоколу NHRP (Next Hop Routing Protocol) маршрутизатору сети. Маршрутизатор переправляет этот запрос узлу назначения, как обычный пакет Узел назначения, который также поддерживает Fast IP и NHRP, получив запрос, отвечает кадром, отсылаемым уже не маршрутизатору, а непосредственно узлу-источнику (по его МАС-адресу, содержащемуся в NHRP-запросе). После этого обмен идет на канальном уровне на основе известных МАС-адресов. Таким образом, снова маршрутизировался только первый пакет потока (как на рисунке 9 кратковременный поток), а все остальные коммутировались (как на рисунке 9 долговременный поток).

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

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

Рассмотрим этот подход на примере технологии NetFlow компании Cisco, реализованной в ее маршрутизаторах и коммутаторах. Для каждого пакета, поступающего на порт маршрутизатора, вычисляется хэш-функция от IP-адресов источника, назначения, портов UDP или TCP и поля TOS, характеризующего требуемое качество обслуживания. Во всех маршрутизаторах, поддерживающих данную технологию, через которые проходит данный пакет, в кэш-памяти портов запоминается соответствие значения хэш-функции и адресной информации, необходимой для быстрой передачи пакета следующему маршрутизатору. Таким образом, образуется квазивиртуальный канал (см. Рисунок 11), который позволяет быстро передавать по сети маршрутизаторов все последующие пакеты этого потока. При этом ускорение достигается за счет упрощения процедуры обработки пакета маршрутизатором - не просматриваются таблицы маршрутизации, не выполняются ARP-запросы.

Этот прием может использоваться в маршрутизаторах, вообще не поддерживающих коммутацию, а может быть перенесен в коммутаторы. В этом случае такие коммутаторы тоже называют коммутаторами третьего уровня. Примеров маршрутизаторов, использующих данный подход, являются маршрутизаторы Cisco 7500, а коммутаторов третьего уровня — коммутаторы Catalyst 5000 и 5500. Коммутаторы Catalyst выполняют усеченные функции описанной схемы, они не могут обрабатывать первые пакеты потоков и создавать новые записи о хэш-функциях и адресной информации потоков. Они просто получают данную информацию от маршрутизаторов 7500 и обрабатывают пакеты уже распознанных маршрутизаторами потоков.

Выше был рассмотрен способ ускоренной маршрутизации, основанный на концепции потока. Его сущность заключается в создании квазивиртуальных каналов в сетях, которые не поддерживают виртуальные каналы в обычном понимании этого термина, то есть сетях Ethernet, FDDI, Token Ring и т п. Следует отличать этот способ от способа ускоренной работы маршрутизаторов в сетях, поддерживающих технологию виртуальных каналов — АТМ, frame relay, X 25. В таких сетях создание виртуального канала является штатным режимом работы сетевых устройств. Виртуальные каналы создаются между двумя конечными точками, причем для потоков данных, требующих разного качества обслуживания (например, для данных разных приложений) может создаваться отдельный виртуальный канал. Хотя время создания виртуального канала существенно превышает время маршрутизации одного пакета, выигрыш достигается за счет последующей быстрой передачи потока данных по виртуальному каналу. Но в таких сетях возникает другая проблема — неэффективная передача коротких потоков, то есть потоков, состоящих из небольшого количества пакетов (классический пример — пакеты протокола DNS).

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

По такой схеме работает ставшая уже классической технология IP Switching компании Ipsilon. Для того чтобы сети коммутаторов АТМ передавали бы пакеты коротких потоков без установления виртуального канала, компания Ipsilon предложила встроить во все коммутаторы АТМ блоки IP-маршрутизации (рисунок 12), строящие обычные таблицы маршрутизации по обычным протоколам RIP и OSPF.

Компания Cisco Systems выдвинула в качестве альтернативы технологии IP Switching свою собственную технологию Tag Switching, но она не стала стандартной. В настоящее время IETF работает над стандартным протоколом обмена метками MPLS (Multi-Protocol Label Switching), который обобщает предложение компаний Ipsilon и Cisco, а также вносит некоторые новые детали и механизмы. Этот протокол ориентирован на поддержку качества обслуживания для виртуальных каналов, образованных метками.

Коммутация четвертого уровня

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

Некоторые производители заявляют, что их системы могут работать на втором, третьем и даже четвертом уровнях. Однако рассмотрение описания стека TCP/IP (рисунок 1), а также структуры пакетов IP и TCP (рисунки 2, 3), показывает, что коммутация четвертого уровня является фикцией, так как все относящиеся к коммутации функции осуществляются на уровне не выше третьего. А именно, термин коммутация четвертого уровня с точки зрения описания стека TCP/IP противоречий не имеет, за исключением того, что при коммутации должны указываться адреса компьютера (маршрутизатора) источника и компьютера (маршрутизатора) получателя. Пакеты TCP имеют поля локальный порт отправителя и локальный порт получателя (рисунок 3), несущие смысл точек входа в приложение (в программу), например Telnet с одной стороны, и точки входа (в данном контексте инкапсуляции) в уровень IP. Кроме того, в стеке TCP/IP именно уровень TCP занимается формированием пакетов из потока данных идущих от приложения. Пакеты IP (рисунок 2) имеют поля адреса компьютера (маршрутизатора) источника и компьютера (маршрутизатора) получателя и следовательно могут наряду с MAC адресами использоваться для коммутации. Тем не менее, название прижилось, к тому же практика показывает, что способность системы анализировать информацию прикладного уровня может оказаться полезной — в частности для управления трафиком. Таким образом, термин "зависимый от приложения" более точно отражает функции так называемых коммутаторов четвертого уровня.

Тематики

• сети вычислительные

EN

• switching technology

линейное программирование
—
[ http://www.iks-media.ru/glossary/index.html?glossid=2400324]

линейное программирование
Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны ограничения типа или в так называемой канонической форме, к которой можно привести все три указанных случая Требуется найти неотрицательные числа xj (j = 1, 2, …, n), которые минимизируют (или максимизируют) линейную форму Неотрицательность искомых чисел записывается так: Таким образом, здесь представлена общая задача математического программирования с теми оговорками, что как ограничения, так и целевая функция — линейные, а искомые переменные — неотрицательны. Обозначения можно трактовать следующим образом: bi — количество ресурса вида i; m — количество видов этих ресурсов; aij — норма расхода ресурса вида i на единицу продукции вида j; xj — количество продукции вида j, причем таких видов — n; cj — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m1, от m1 + 1 до m2 и от m2 + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — «не больше», во втором — «столько же», в третьем — «не меньше»; Z — в случае максимизации, например, объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т.п. Добавим еще одно обозначение, оно появится несколько ниже; vi — оптимальная оценка i-го ресурса. Слово «программирование» объясняется здесь тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно в совокупности определяют программу (план) работы некоторого экономического объекта. Слово, «линейное» отражает факт линейной зависимости между переменными. При этом, как указано, задача обязательно имеет экстремальный характер, т.е. состоит в отыскании экстремума (максимума или минимума) целевой функции. Следует с самого начала предупредить: предпосылка линейности, когда в реальной экономике подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задач Л.п. оказываются весьма несовершенными. Рассмотрим две задачи Л.п. — на максимум и на минимум — на упрощенных примерах. Предположим, требуется разработать план производства двух видов продукции (объем первого — x1; второго — x2) с наиболее выгодным использованием трех видов ресурсов (наилучшим в смысле максимума общей прибыли от реализации плана). Условия задачи можно записать в виде таблицы (матрицы). Исходя из норм, зафиксированных в таблице, запишем неравенства (ограничения): a11x1 + a12x2 ? bi a21x1 + a22x2 ? b2 a31x1 + a32x2 ? b3 Это означает, что общий расход каждого из трех видов ресурсов не может быть больше его наличия. Поскольку выпуск продукции не может быть отрицательным, добавим еще два ограничения: x1? 0, x2? 0. Требуется найти такие значения x1 и x2, при которых общая сумма прибыли, т.е. величина c1 x1 + c2 x2 будет наибольшей, или короче: Удобно показать условия задачи на графике (рис. Л.2). Рис. Л.2 Линейное программирование, I (штриховкой окантована область допустимых решений) Любая точка здесь, обозначаемая координатами x1 и x2, составляет вариант искомого плана. Очевидно, что, например, все точки, находящиеся в области, ограниченной осями координат и прямой AA, удовлетворяют тому условию, что не может быть израсходовано первого ресурса больше, чем его у нас имеется в наличии (в случае, если точка находится на самой прямой, ресурс используется полностью). Если то же рассуждение отнести к остальным ограничениям, то станет ясно, что всем условиям задачи удовлетворяет любая точка, находящаяся в пределах области, края которой заштрихованы, — она называется областью допустимых решений (или областью допустимых значений, допустимым множеством). Остается найти ту из них, которая даст наибольшую прибыль, т.е. максимум целевой функции. Выбрав произвольно прямую c1x1 + c2x2 = П и обозначив ее MM, находим на чертеже все точки (варианты планов), где прибыль одинакова при любом сочетании x1 и x2 (см. Линия уровня). Перемещая эту линию параллельно ее исходному положению, найдем точку, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений. (Перемещая линию уровня еще дальше, уже выходим из нее и, следовательно, нарушаем ограничения задачи). Точка M0 и будет искомым оптимальным планом. Она находится в одной из вершин многоугольника. Может быть и такой случай, когда линия уровня совпадает с одной из прямых, ограничивающих область допустимых значений, тогда оптимальным будет любой план, находящийся на соответствующем отрезке. Координаты точки M0 (т.е. оптимальный план) можно найти, решая совместно уравнения тех прямых, на пересечении которых она находится. Противоположна изложенной другая задача Л.п.: поиск минимума функции при заданных ограничениях. Такая задача возникает, например, когда требуется найти наиболее дешевую смесь некоторых продуктов, содержащих необходимые компоненты (см. Задача о диете). При этом известно содержание каждого компонента в единице исходного продукта — aij, ее себестоимость — cj ; задается потребность в искомых компонентах — bi. Эти данные можно записать в таблице (матрице), сходной с той, которая приведена выше, а затем построить уравнения как ограничений, так и целевой функции. Предыдущая задача решалась графически. Рассуждая аналогично, можно построить график (рис. Л.3), каждая точка которого — вариант искомого плана: сочетания разных количеств продуктов x1 и x2. Рис.Л.3 Линейное программирование, II Область допустимых решений здесь ничем сверху не ограничена: нужное количество заданных компонентов тем легче получить, чем больше исходных продуктов. Но требуется найти наиболее выгодное их сочетание. Пунктирные линии, как и в предыдущем примере, — линии уровня. Здесь они соединяют планы, при которых себестоимость смесей исходных продуктов одинакова. Линия, соответствующая наименьшему ее значению при заданных требованиях, — линия MM. Искомый оптимальный план — в точке M0. Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л.п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве (выпуклый многогранник). Задачи Л.п., в которых нормативы (или коэффициенты), объемы ресурсов («константы ограничений«) или коэффициенты целевой функции содержат случайные элементы, называются задачами линейного стохастического программирования; когда же одна или несколько независимых переменных могут принимать только целочисленные значения, то перед нами задача линейного целочисленного программирования. В экономике широко применяются линейно-программные методы решения задач размещения производства (см. Транспортная задача), расчета рационов для скота (см. Задача диеты), наилучшего использования материалов (см. Задача о раскрое), распределения ресурсов по работам, которые надо выполнять (см. Распределительная задача) и т.д. Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. Один из видов решения имеет особое значение для экономической интерпретации задачи Л.п. Он связан с тем, что каждой прямой задаче Л.п. соответствует другая, симметричная ей двойственная задача (подробнее см. также Двойственность в линейном программировании). Если в качестве прямой принять задачу максимизации выпуска продукции (или объема реализации, прибыли и т.д.), то двойственная задача заключается, наоборот, в нахождении таких оценок ресурсов, которые минимизируют затраты. В случае оптимального решения ее целевая функция — сумма произведений оценки (цены) vi каждого ресурса на его количество bi— то есть равна целевой функции прямой задачи. Эта цена называется объективно обусловленной, или оптимальной оценкой, или разрешающим множителем. Основополагающий принцип Л.п. состоит в том, что в оптимальном плане и при оптимальных оценках всех ресурсов затраты и результаты равны. Оценки двойственной задачи обладают замечательными свойствами: они показывают, насколько возрастет (или уменьшится) целевая функция прямой задачи при увеличении (или уменьшении) запаса соответствующего вида ресурсов на единицу. В частности, чем больше в нашем распоряжении данного ресурса по сравнению с потребностью в нем, тем ниже будет оценка, и наоборот. Не решая прямую задачу, по оценкам ресурсов, полученных в двойственной задаче, можно найти оптимальный план: в него войдут все технологические способы, которые оправдывают затраты, исчисленные в этих оценках (см. Объективно обусловленные (оптимальные) оценки). Первооткрыватель Л.п. — советский ученый, академик, лауреат Ленинской, Государственной и Нобелевской премий Л.В.Канторович. В 1939 г. он решил математически несколько задач: о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта и др., при этом разработав универсальный метод решения этих задач, а также различные алгоритмы, реализующие его. Л.В.Канторович впервые точно сформулировал такие важные и теперь широко принятые экономико-математические понятия, как оптимальность плана, оптимальное распределение ресурсов, объективно обусловленные (оптимальные) оценки, указав многочисленные области экономики, где могут быть применены экономико-математические методы принятия оптимальных решений. Позднее, в 40—50-х годах, многое сделали в этой области американские ученые — экономист Т.Купманс и математик Дж. Данциг. Последнему принадлежит термин «линейное программирование». См. также: Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткость, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна — Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача.
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика
• электросвязь, основные понятия

EN

• linear programming

линейное программирование
—
[ http://www.iks-media.ru/glossary/index.html?glossid=2400324]

линейное программирование
Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны ограничения типа или в так называемой канонической форме, к которой можно привести все три указанных случая Требуется найти неотрицательные числа xj (j = 1, 2, …, n), которые минимизируют (или максимизируют) линейную форму Неотрицательность искомых чисел записывается так: Таким образом, здесь представлена общая задача математического программирования с теми оговорками, что как ограничения, так и целевая функция — линейные, а искомые переменные — неотрицательны. Обозначения можно трактовать следующим образом: bi — количество ресурса вида i; m — количество видов этих ресурсов; aij — норма расхода ресурса вида i на единицу продукции вида j; xj — количество продукции вида j, причем таких видов — n; cj — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m1, от m1 + 1 до m2 и от m2 + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — «не больше», во втором — «столько же», в третьем — «не меньше»; Z — в случае максимизации, например, объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т.п. Добавим еще одно обозначение, оно появится несколько ниже; vi — оптимальная оценка i-го ресурса. Слово «программирование» объясняется здесь тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно в совокупности определяют программу (план) работы некоторого экономического объекта. Слово, «линейное» отражает факт линейной зависимости между переменными. При этом, как указано, задача обязательно имеет экстремальный характер, т.е. состоит в отыскании экстремума (максимума или минимума) целевой функции. Следует с самого начала предупредить: предпосылка линейности, когда в реальной экономике подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задач Л.п. оказываются весьма несовершенными. Рассмотрим две задачи Л.п. — на максимум и на минимум — на упрощенных примерах. Предположим, требуется разработать план производства двух видов продукции (объем первого — x1; второго — x2) с наиболее выгодным использованием трех видов ресурсов (наилучшим в смысле максимума общей прибыли от реализации плана). Условия задачи можно записать в виде таблицы (матрицы). Исходя из норм, зафиксированных в таблице, запишем неравенства (ограничения): a11x1 + a12x2 ? bi a21x1 + a22x2 ? b2 a31x1 + a32x2 ? b3 Это означает, что общий расход каждого из трех видов ресурсов не может быть больше его наличия. Поскольку выпуск продукции не может быть отрицательным, добавим еще два ограничения: x1? 0, x2? 0. Требуется найти такие значения x1 и x2, при которых общая сумма прибыли, т.е. величина c1 x1 + c2 x2 будет наибольшей, или короче: Удобно показать условия задачи на графике (рис. Л.2). Рис. Л.2 Линейное программирование, I (штриховкой окантована область допустимых решений) Любая точка здесь, обозначаемая координатами x1 и x2, составляет вариант искомого плана. Очевидно, что, например, все точки, находящиеся в области, ограниченной осями координат и прямой AA, удовлетворяют тому условию, что не может быть израсходовано первого ресурса больше, чем его у нас имеется в наличии (в случае, если точка находится на самой прямой, ресурс используется полностью). Если то же рассуждение отнести к остальным ограничениям, то станет ясно, что всем условиям задачи удовлетворяет любая точка, находящаяся в пределах области, края которой заштрихованы, — она называется областью допустимых решений (или областью допустимых значений, допустимым множеством). Остается найти ту из них, которая даст наибольшую прибыль, т.е. максимум целевой функции. Выбрав произвольно прямую c1x1 + c2x2 = П и обозначив ее MM, находим на чертеже все точки (варианты планов), где прибыль одинакова при любом сочетании x1 и x2 (см. Линия уровня). Перемещая эту линию параллельно ее исходному положению, найдем точку, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений. (Перемещая линию уровня еще дальше, уже выходим из нее и, следовательно, нарушаем ограничения задачи). Точка M0 и будет искомым оптимальным планом. Она находится в одной из вершин многоугольника. Может быть и такой случай, когда линия уровня совпадает с одной из прямых, ограничивающих область допустимых значений, тогда оптимальным будет любой план, находящийся на соответствующем отрезке. Координаты точки M0 (т.е. оптимальный план) можно найти, решая совместно уравнения тех прямых, на пересечении которых она находится. Противоположна изложенной другая задача Л.п.: поиск минимума функции при заданных ограничениях. Такая задача возникает, например, когда требуется найти наиболее дешевую смесь некоторых продуктов, содержащих необходимые компоненты (см. Задача о диете). При этом известно содержание каждого компонента в единице исходного продукта — aij, ее себестоимость — cj ; задается потребность в искомых компонентах — bi. Эти данные можно записать в таблице (матрице), сходной с той, которая приведена выше, а затем построить уравнения как ограничений, так и целевой функции. Предыдущая задача решалась графически. Рассуждая аналогично, можно построить график (рис. Л.3), каждая точка которого — вариант искомого плана: сочетания разных количеств продуктов x1 и x2. Рис.Л.3 Линейное программирование, II Область допустимых решений здесь ничем сверху не ограничена: нужное количество заданных компонентов тем легче получить, чем больше исходных продуктов. Но требуется найти наиболее выгодное их сочетание. Пунктирные линии, как и в предыдущем примере, — линии уровня. Здесь они соединяют планы, при которых себестоимость смесей исходных продуктов одинакова. Линия, соответствующая наименьшему ее значению при заданных требованиях, — линия MM. Искомый оптимальный план — в точке M0. Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л.п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве (выпуклый многогранник). Задачи Л.п., в которых нормативы (или коэффициенты), объемы ресурсов («константы ограничений«) или коэффициенты целевой функции содержат случайные элементы, называются задачами линейного стохастического программирования; когда же одна или несколько независимых переменных могут принимать только целочисленные значения, то перед нами задача линейного целочисленного программирования. В экономике широко применяются линейно-программные методы решения задач размещения производства (см. Транспортная задача), расчета рационов для скота (см. Задача диеты), наилучшего использования материалов (см. Задача о раскрое), распределения ресурсов по работам, которые надо выполнять (см. Распределительная задача) и т.д. Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. Один из видов решения имеет особое значение для экономической интерпретации задачи Л.п. Он связан с тем, что каждой прямой задаче Л.п. соответствует другая, симметричная ей двойственная задача (подробнее см. также Двойственность в линейном программировании). Если в качестве прямой принять задачу максимизации выпуска продукции (или объема реализации, прибыли и т.д.), то двойственная задача заключается, наоборот, в нахождении таких оценок ресурсов, которые минимизируют затраты. В случае оптимального решения ее целевая функция — сумма произведений оценки (цены) vi каждого ресурса на его количество bi— то есть равна целевой функции прямой задачи. Эта цена называется объективно обусловленной, или оптимальной оценкой, или разрешающим множителем. Основополагающий принцип Л.п. состоит в том, что в оптимальном плане и при оптимальных оценках всех ресурсов затраты и результаты равны. Оценки двойственной задачи обладают замечательными свойствами: они показывают, насколько возрастет (или уменьшится) целевая функция прямой задачи при увеличении (или уменьшении) запаса соответствующего вида ресурсов на единицу. В частности, чем больше в нашем распоряжении данного ресурса по сравнению с потребностью в нем, тем ниже будет оценка, и наоборот. Не решая прямую задачу, по оценкам ресурсов, полученных в двойственной задаче, можно найти оптимальный план: в него войдут все технологические способы, которые оправдывают затраты, исчисленные в этих оценках (см. Объективно обусловленные (оптимальные) оценки). Первооткрыватель Л.п. — советский ученый, академик, лауреат Ленинской, Государственной и Нобелевской премий Л.В.Канторович. В 1939 г. он решил математически несколько задач: о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта и др., при этом разработав универсальный метод решения этих задач, а также различные алгоритмы, реализующие его. Л.В.Канторович впервые точно сформулировал такие важные и теперь широко принятые экономико-математические понятия, как оптимальность плана, оптимальное распределение ресурсов, объективно обусловленные (оптимальные) оценки, указав многочисленные области экономики, где могут быть применены экономико-математические методы принятия оптимальных решений. Позднее, в 40—50-х годах, многое сделали в этой области американские ученые — экономист Т.Купманс и математик Дж. Данциг. Последнему принадлежит термин «линейное программирование». См. также: Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткость, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна — Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача.
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика
• электросвязь, основные понятия

EN

• linear programming

library edition - издание для библиотек

popular edition - популярное /массовое/ издание

pocket edition - карманное издание

the book has just entered the seventh edition - книга только что начала выходить седьмым изданием

improved edition of the airship - усовершенствованный вариант самолёта

her younger sister, a weaker edition of herself - её младшая сестра - ухудшенное издание её самой

the newest edition of a popular musical revue - последняя постановка популярного мюзикла

proof edition - пробный оттиск

edition in boards - набранное издание

edition in quires [in sheets] - издание в сфальцованных [несфальцованных] листах

advance(d) edition - предварительное /пробное/ издание

added edition - дополнительный тираж

the work is to be issued in an edition limited to 100 copies - работа будет выпущена тиражом всего в 100 экземпляров