- •2. Протокол. Примеры.
- •3. Конечные системы, архитектура клиент-сервер, сервисы с установление и без установления соединения.
- •4. Коммутация каналов, коммутация пакетов, коммутация сообщений, маршрутизация.
- •5. Сети доступа и среды передачи данных.
- •6. Причины задержек и потерь в сетях с коммутацией пакетов.
- •7. Уровни протоколов, стек протоколов Internet. Иерархия isp.
- •8. Требования приложений. Сервисы, предоставляемые tcp и udp.
- •9. Протокол http
- •10. Аутентификация в http, cookies, условный get в http.
- •11. Протокол ftp.
- •12. Протокол smtp.
- •13. Служба имен доменов (dns).
- •14. Распределение нагрузки (cdn, основные варианты организации). Web-proxy, принцип действия. P2p-сети (основные варианты организации).
- •15. Сервисы, предоставляемые протоколами транспортного уровня.
- •16. Мультиплексирование и демультиплексирование, порты, сокеты.
- •17. Протокол udp.
- •18. Принципы надежной передачи данных.
- •19. Протокол tcp.
- •20. Установление и разрыв соединения, состояния tcp.
- •21. Максимальное время ожидания подтверждения в tcp (timeout)
- •22. Управление потоком в tcp.
- •23. Время выполнения запроса в статическом окне.
- •24. Сервисы, предоставляемые функциями сетевого уровня.
- •25. Маршрутизация, термины, алгоритм Дейкстры (ls).
- •26. Маршрутизация, алгоритм Беллмана-Форда (dv).
- •27. Автономные системы. Иерархическая маршрутизация.
- •28. Протокол ip. Адресация и маршрутизация в ip.
- •29. Основные варианты архитектуры маршрутизатора (коммутатора).
- •30. Сервисы, предоставляемые функциями канального уровня.
- •31. Методы обнаружения и коррекции ошибок.
- •32.Способы разделения среды передачи (tdm, fdm, cdma). Основные способы организации доступа к общей среде передачи.
- •33. Адрес в локальной сети и arp
- •34. Ethernet.
- •35. Хабы и коммутаторы.
- •36. Протокол ppp.
26. Маршрутизация, алгоритм Беллмана-Форда (dv).
Для того чтобы переместить пакеты от хоста-отпарвителя к хосту-получателя, сетевой уровень должен определить путь или маршрут следования пакетов. Этим занимается протокол маршрутизации сетевого уровня. Хост напрямую подключен к одному из маршрутихзаторов - маршрутизатор по умолчанию (первого ретрансляционного участка). Задача выбора пути от источника к приемнику сводится к выбору пути пакета от маршрутизатора-источника к маршрутизатору-приемнику - алгоритм маршрутизации. Алгоритм находит «оптимальный» путь (с минимальной стоимостью).Рассмотрим граф: узлы - маршрутизаторы, дуги - линии связи. Каждой линии связи соответствует некоторое значение, представляющее «стоимость» пересылке пакета по этой линии.
Протоколы: общедоступные: RIP, BGP, OSPF; частный: EIGRP.
Глобальный алгоритм маршрутизации находит путь с наименьшей стоимостью от отправителя до получателя с помощью инф о сети. Особенность: обладает полной инф о топологии сети и стоимости линий.
Децентрализованный алгоритм вычисление пути выполняется итерационным распределенным образом. Ни 1 узел не обладает полной инф о стоимости всех линий связи. Изначальна каждому узлу известна стоимость напрямую присоединенных к нему линий, затем, путем итерационных вычислений и обмена инф с соседними узлами, узел постепенно определяет путь с наименьшей стоимостью до получателя или до группы получателей.
Алгоритмы: статические и динамические
В статическом маршруты изменяются со временем очень медленно, чаще всего вручную.
Динамический запускается либо периодически, либо в ответ на изменение топологии или стоимости линий (по протоколу).
Может быть смесь.
Чувствительность протокола маршрутизации: чувствительные реагируют на загруженность линии связи (стоимость линии возросла, а с ней и загруженность) Так не делается, не устойчиво.
В И используются: алгоритм, основанный на состояниях линий и алгоритм дистанционно-векторной маршрутизации.
Децентрализованный алгоритм (Беллмана-форда, дистанционно векторной маршрутизации): основан на рассылке сообщений (при изменении стоимости пути (событие: пришло сообщение от кого-то или изменение стоимости известной линии связи)), асинхронный (управляется событиями), нет явного критерия остановки (после какой-то итерации строка не изменится, новое сообщение посылаться не будет), не требует знания всей конструкции сети.
Алгоритм: y - 2 - x - 1 - z - 7 - y
1. Инициализация: в таблице бесконечности дл диагональных (.) известные длины пути DX(*, V) = INF, DX(V, V) = C(X, V). Для всех адресатов minWD(Y, W).
2. Ожидание события: (пока не придет сообщение, изменение стоимости линии связи)
а. Если изменилась стоимость С(X, V) на d => меняется стоимость в таблице. Для всех адресатов y DX(Y, V) +=d таблица обновляется. Если появился новый min => рассылка всем соседям
б. Если обновление - новое значение от соседа w адресат y. Обновление DX(Y, V) = C(X, V) + newval. Если получается новое min значение, то рассылка всем соседям.
3. Снова ждет пока что-нибудь не случится.
DX |
Y |
Z |
|
DX |
Y |
Z |
Y |
2 |
INF |
Y |
2 |
8 |
|
Z |
INF |
7 |
Z |
3 |
7 |
|
|
|
|||||
DY |
X |
Z |
DY |
X |
Z |
|
X |
2 |
INF |
X |
2 |
8 |
|
Z |
INF |
1 |
Z |
9 |
1 |
|
|
|
|||||
DZ |
X |
Y |
DZ |
X |
Y |
|
X |
7 |
INF |
X |
7 |
3 |
|
Y |
INF |
1 |
Y |
9 |
1 |
На 3 шаге обновлений нет
На практике строится таблица маршрутизации, по которой передаются дейтаграммы, позволяет реагировать на обрывы канала.
Сравнение: 1) скорость схождения: Д: не > N БФ = INF; 2) живучесть (устойчивость к ошибкам) БФ ниже чем у Д; 3) сложность сообщений.
Другие алгоритмы: Алгоритм горячей картофелины (получив сразу выкидывает сообщение в 1 свободный канал, позволяет избежать очередей, может применяться в сетях АТМ) Телефонные алгоритмы коммутированных каналов: канал на кратчайшем, если занят - найти в обход.