Б1В Классификация алгоритмов маршрутизации

Протоколы маршрутизации могут быть реализованы с помощью алгоритмов маршрутизации, которые классифицируются по следующим классификационным признакам: По способу выбора наилучшего маршрута. Все алгоритмы маршрутизации делятся на 2 группы: Одношаговые алгоритмы маршрутизации. Каждый маршрутизатор при выборе маршрута определяет только одно звено этого маршрута. Ответственность только за один шаг этого маршрута. Одношаговые алгоритмы реальней на этапе инициализации. Многошаговые алгоритмы маршрутизации (алгоритм маршрутизации от источника). Весь маршрут задается в уже отправленном пакете узлом источника. Многошаговые алгоритмы считаются перспективней. По способу построения таблиц маршрутизации Алгоритмы простой маршрутизации Таблиц маршрутизации как правило нет, или таблицы являются очень примитивными (они не передают никакой маршрутной информации) Алгоритмы случайной маршрутизации – пакет посылается в случайном направлении Лавинная маршрутизация (алгоритмы заполнения) – пакеты посылаются во все выходные направления, во все порты Алгоритмы скорейшей передачи (алгоритм горячей картошки) – как только маршрутизатор поучает пакет – он старается скорее его отослать Алгоритмы кратчайшей очереди (наименьшей загрузки) – информация идет на порт, который наименее загружен Алгоритм по предыдущему опыту – таблица маршрутизации очень примитивна, есть запись, дублирующая предыдущую передачу Сегодня используют лавинные алгоритмы. Они самые быстрые по доставке информации, а так же могут информировать об экстренной информации возникающей в сети передачи данных. Алгоритмы фиксированной и статической маршрутизации Это алгоритмы, которые заносятся администратором сети, поэтому все записи являются статическими или меняется время функционирования сети. Используются для сетей с простой топологией и чаще всего применяются в теоретических приложениях. Однопутевые (одномаршрутные, безальтернативные) Многопутевые (многомаршрутные, допускающие альтернативу) Адаптивные алгоритмы, = алгоритмы динамической маршрутизации Они самые реальные и самые распространенные. Автоматическое построение таблиц маршрутизации, эти алгоритмы адаптированы к изменениям в сети. К Адаптивным алгоритмам предъявляются следующие требования: Адитивность – скорость адаптивности алгоритма к изменениям в сети. Для достижения скорости алгоритмы должны быть простыми Адаптивные алгоритмы маршрутизации должны обеспечивать если не оптимальные, то хотя бы наилучшие маршрутные решения. Сходимость алгоритма – это когда алгоритм после некоторого времени приводит к однозначному результату. По месту выбора маршрутов (маршрутного решения) По месту выбора маршрутного решения все алгоритмы маршрутизации делятся на три класса: Изолированные алгоритмы (локальные) – нет никакого обмена маршрутной информацией и каждый маршрутизатор принимает решение на основании той информации, которую он сам собрал. Централизованные – вся маршрутная информация со всех маршрутизаторов стекается в сетевой маршрутный центр – он ответственный за определение оптимальных маршрутов и сбор маршрутной информации. Возможны 2 подхода: Подход виртуального канала – маршрут определяется на основе оптимальной информации, посылаемой во все промежуточные маршрутизаторы. Недостатком является уязвимость маршрутного центра Подход формирования по таблице для каждого маршрутизатора. Распределенные – это самые распространенные алгоритмы, где все маршрутизаторы участвуют в сборе и распространении маршрутной информации и работа по выбору наилучшего маршрута распределена между всеми маршрутизаторами. По виду информации которой обмениваются маршрутизаторы Все алгоритмы делятся на 2 класса: Дистанционно-векторные алгоритмы – RIP протокол (протокол маршрутной информации). В дистанционно-векторном: каждый маршрутизатор периодически всем своим соседям передаёт вектор сообщения, где указывает адреса всех известных ему подсетей и расстояние до них, в качестве (расстояния используется промежуточные узлы). Каждый маршрутизатор периодически всем своим соседям передает вектор сообщений, где указывается адреса известных ему подсетей и расстояния до них от данного маршрутизатора. Недостатки: Плохая адаптация к отказам маршрутизаторов, интерфейсов, подсетей. Возможность возникновения маршрутных петель Данный алгоритм используется для небольших сетей (количество ХАП-ов не больше 15 единиц) Для устранения этих недостатков каждому маршруту присваивается время жизни (TTL=180 сек) за которое если информация не обновляется – то маршрут «умирает», прекращает действовать. Если маршрутизатор вышел из строя – то в качестве расстояния указывается 16, то есть ∞ Главная причина всех недостатков – это получение информации через соседних маршрутизаторов, а не напрямую (это называется отсутствием полной нужной информации). Алгоритмы состояния связи – OSPF протокол OSPF протокол – Open Shortest Path First – открытый протокол кратчайшего маршрута – в стеке протокола TCP/IP. NLSP протокол – Netware Link Services Protocol – используется для сетевых служб, указанных в различных подсетях, с целью управления – принадлежит стеку протоколов IPX/SPX. IS-IS – Intermediate System to Intermediate System – подмножество модели OSI. Каждый маршрутизатор обеспечивается необходимой и точной (достаточной) информацией для построения адекватной (точной) топологии сети. Для точного построения графа-связи сети в данной топологии вершинами выступают маршрутизаторы и подсети. Принцип действия:
Каждый маршрутизатор распространяет соседям о всех своих близких соседях: Адрес соседней подсети Тип интерфейса (М-М (маршрутизатор – марш) и М-S (марш – сеть)) Метрика интерфейса (пропускные способности каждого из путей, время задержки и метрика надежности) Соседний маршрутизатор получает информацию без коррекции, и через некоторое время все маршрутизаторы будут иметь полную информацию о всех подсетях и маршрутизаторах. Вся информация записывается в Базу Данных, после чего каждый маршрутизатор знает топологию, определяет кратчайшие маршруты для всех подсетей. Для этого используется алгоритм Дейкстра – алгоритм определения кратчайшего маршрута, где каждое звено этого маршрута записывается в таблицу маршрутизации. Вычисления происходят по всей метрике. Маршрутизатор не имеет сетевого адреса! Для проверки в каждый маршрутизатор пересылается сообщение каждые 10 сек и если ответа нет, то таблица корректируется без учета вышедшего из строя маршрутизатора (в т.ч. поэтому – адаптивный алгоритм). Топология сети в течении длительной работы сети не меняется, информационные потоки тоже не меняются после их распределения, однако реально при стабильной топологии потоки могут меняться, именно поэтому более оптимальным является адаптивный алгоритм. Cm = f (Функциональные сетевые компоненты ФСК)

14Б2В Многоочередная дисциплина обслуживания процессов с различными приоритетами в ОС

На дисциплину формирования очередей влияют следующие факторы: Информация о классах и приоритетах заданий и шагов заданий. Информация о необходимости обращения к тем или иным устройствам, массивам данных (зафиксированных в операторах языка управления заданиями). Соглашение о приоритете уровней запросов прерывания и прерывающих программ. Соглашения в ВУ. Используемые дисциплины обслуживания очередей. Дисциплины формирования очередей разделяются на два класса: статический (приоритеты назначаются до выполнения задания) и динамический (приоритеты определяются в процессе выполнения пакета). Многоочередная дисциплина обслуживания. Здесь организуется N очередей. Все новые запросы поступают в конец первой очереди. Первый запрос из очереди i поступает на обслуживание лишь тогда, когда все очереди от 1 до (i-1) пустые. На обслуживание выделяется квант времени tk. Если за это время обслуживание запроса завершается полностью, то он покидает систему. В противном случае недообслуженный запрос поступает в конец очереди (i+1)

После обслуживания из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Таким запросом может быть следующий запрос из очереди i или из очереди i+1 (при условии, что после обслуживания запроса из очереди i последняя оказалась пустой). Новый запрос поступает в первую очередь (i=1). В такой ситуации после окончания времени tk, выделенного для обслуживания запроса из очереди i, будет начато обслуживание запроса первой очереди. Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO (каждая заявка обслуживается до конца), либо по циклическому алгоритму. Данная система наиболее быстро обслуживает все короткие по времени обслуживания запросы. Недостаток системы заключается в затратах времени на перемещение запросов из одной очереди в другую.

14Б3В Устройства кодирования и декодирования цифровой информации, примеры практической реализации схем и их функционирование

Кодирование информации – это процесс формирования определенного представления информации. Информация совершает переход от исходной формы представления информации в форму, удобную для хранения, передачи или обработки. Декодирование - когда информация совершает обратный переход к исходному представлению информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. Компьютер может обрабатывать только информацию, представленную в числовой форме. Вся другая информация (звуки, изображения, показания приборов и т. д.) для обработки на компьютере должна быть преобразована в числовую форму. Как правило, вся информация в компьютере представляются с помощью нулей и единиц. Иными словами, компьютеры обычно работают в двоичной системе счисления, поскольку при этом устройства для их обработки получаются значительно более простыми. С помощью двух цифр 0 и 1 можно закодировать любое сообщение. Инженеров такой способ кодирования привлек простотой технической реализации – есть сигнал или нет сигнала. Эти состояния легко различать. Недостаток двоичного кодирования – длинные коды. Но в технике легче иметь дело с большим числом однотипных элементов, чем с небольшим числом сложных. Устройства, обеспечивающие кодирование и декодирование, будем называть соответственно кодировщиком и декодировщиком. На рис. 1 приведена схема, иллюстрирующая процесс передачи сообщения в случае перекодировки, а также воздействия помех.

Рис. 1. Процесс передачи сообщения от источника к приемнику В настоящее время существуют разные способы кодирования и декодирования информации в компьютере. Выбор способа зависит от вида информации, которую необходимо кодировать: текст, число, графическое изображение или звук. Для чисел, кроме того, важную роль играет то, как будет использоваться число: в тексте или в вычислениях, или в процессе ввода-вывода. Рассмотрим основные принципы кодирования информации в компьютере. 5. Кодирование текстовой информации Начиная с 60-х годов, компьютеры все больше стали использовать для обработки текстовой информации и в настоящее время большая часть ПК в мире занято обработкой именно текстовой информации. Для кодирования одного символа требуется один байт информации. Учитывая, что каждый бит принимает значение 1 или 0, получаем, что с помощью 1 байта можно закодировать 256 различных символов. (28=256) Кодирование заключается в том, что каждому символу ставиться в соответствие уникальный двоичный код от 00000000 до 11111111 (или десятичный код от 0 до 255). Важно, что присвоение символу конкретного кода – это вопрос соглашения, которое фиксируется кодовой таблицей. Например, вы нажимаете на компьютере латинскую букву S. В этом случае в память компьютера записывается код 01010011. Для вывода буквы S на экран в компьютере происходит декодирование – по этому двоичному коду строится его изображение.