Коммуникационные сети: краткое введение

Жан Вальран
Шьям Парех

Коммуникационные сети:

краткое введение

Communication Networks

A Concise Introduction

Second Edition

Jean Walrand
University of California, Berkeley

Shyam Parekh
AT&T Labs Research and University of California, Berkeley (Adjunct)

Москва, 2023

Жан Вальран
Калифорнийский университет, Беркли

Шьям Парех
AT&T Labs Research и Калифорнийский университет, Беркли, адьюнкт

Коммуникационные сети:

краткое введение

УДК   004.7
ББК   32.971.35
В15

В15   Жан Вальран, Шьям Парех
Коммуникационные сети: краткое введение / пер. с англ. К. В. Петровичевой – М.: ДМК Пресс, 2023. – 268 с.: ил.

         ISBN 978-5-97060-967-5

Эта книга посвящена основным принципам, лежащим в основе проектирования и функционирования интернета. В ней дается целостное 
описа ние этой критически важной, но сложной инфраструктуры и четко 
и ясно объясняются основные идеи, не скрываясь за несущественными 
деталями реализации. 
Издание предназначено ИТ­специалистам, студентам, преподавателям, а также может быть полезно широкому кругу читателей.

Copyright ©2018 Morgan and Claypool Publishers. All Rights Reserved Morgan and Claypool 
Publishers.

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

ISBN 978­1­62705­887­2 (англ.)         Copyright © Morgan and Claypool Publishers, 2018
ISBN 978­5­97060­967­5 (рус.)                           © Оформление, перевод на русский язык, 
 
                   издание, ДМК Пресс, 2023

Оглавление

Предисловие от издательства ...........................................................11
Отзывы ................................................................................................12
Аннотация ко второму изданию ......................................................14
Предисловие .......................................................................................15

Глава 1. Интернет ...............................................................................17

1.1. Основные операции ...................................................................................17

1.1.1. Хосты, маршрутизаторы, каналы связи ...................................................... 17
1.1.2. Коммутация пакетов .................................................................................... 18
1.1.3. Адресация ...................................................................................................... 19
1.1.4. Маршрутизация ............................................................................................ 19
1.1.5. Обнаружение ошибок ................................................................................... 21
1.1.6. Повторная передача ошибочных пакетов .................................................. 22
1.1.7. Управление перегрузками ............................................................................ 22
1.1.8. Управление потоком..................................................................................... 23

1.2. DNS, HTTP и www .......................................................................................23

1.2.1. DNS ................................................................................................................. 23
1.2.2. HTTP и www................................................................................................... 23

1.3. Краткое изложение ....................................................................................24
1.4. Задачи .........................................................................................................24
1.5. Ссылки ........................................................................................................25

Глава 2. Принципы .............................................................................26

2.1. Совместное использование .......................................................................26
2.2. Метрики ......................................................................................................27

2.2.1. Скорость канала связи .................................................................................. 28
2.2.2. Широкополосный канал и его производительность .................................. 28
2.2.3. Задержка ........................................................................................................ 29
2.2.4. Пропускная способность .............................................................................. 30
2.2.5. Джиттер ......................................................................................................... 32
2.2.6. Очередь М/М/1 .............................................................................................. 33
2.2.7. Закон Литтла .................................................................................................. 35
2.2.8. Fairness, или индексы справедливости в сети ............................................ 37

2.3. Масштабируемость ....................................................................................38

2.3.1. Адресация на основе местоположения ....................................................... 38
2.3.2. Двухуровневая маршрутизация .................................................................. 39
2.3.3. Негарантированная доставка ...................................................................... 40
2.3.4. Сквозной (end-to-end ) принцип и маршрутизаторы stateless ................. 41
2.3.5. Иерархическое именование ......................................................................... 42

2.4. Приложения и технологическая независимость .....................................42

2.4.1. Уровни модели OSI ....................................................................................... 43

2.5. Топология приложений .............................................................................44

2.5.1. Клиент/сервер ............................................................................................... 44
2.5.2. P2P ................................................................................................................. 45

 Оглавление

2.5.3. Облачные вычисления ................................................................................. 45
2.5.4. Распределение контента .............................................................................. 46
2.5.5. multicast/anycast ........................................................................................... 46
2.5.6. push/pull ........................................................................................................ 46
2.5.7. Подбор контента по местоположению ........................................................ 47

2.6. Резюме ........................................................................................................47
2.7. Задачи .........................................................................................................47
2.8. Ссылки ........................................................................................................51

Глава 3. Ethernet .................................................................................52

3.1. Типовая установка .....................................................................................52
3.2. История Ethernet ........................................................................................52

3.2.1. Сеть Aloha (Alohanet) .................................................................................... 53
3.2.2. Кабельная сеть Ethernet ................................................................................ 54
3.2.3. Хаб Ethernet ................................................................................................... 56
3.2.4. Коммутируемый Ethernet ............................................................................. 57

3.3. Адреса .........................................................................................................57
3.4. Кадр .............................................................................................................57
3.5. Физический уровень ..................................................................................58
3.6. Коммутируемый Ethernet ..........................................................................59

3.6.1. Пример .......................................................................................................... 59
3.6.2. Обучение (learning) ....................................................................................... 59
3.6.3. Протокол spanning tree ................................................................................. 60

3.7. Aloha ............................................................................................................62

3.7.1. Версия с тайм-слотами ................................................................................. 62

3.8. Aloha без слотов .........................................................................................63
3.9. Хаб Ethernet ................................................................................................63

3.9.1. Максимальное время обнаружения коллизии ............................................ 63

3.10. Приложение: теория вероятности ..........................................................65

3.10.1. Вероятность ................................................................................................. 65
3.10.2. Аддитивность эксклюзивных событий ..................................................... 65
3.10.3. Независимые события ................................................................................ 66
3.10.4. Слотовая Aloha ............................................................................................ 67
3.10.5. Неслотовая Aloha ........................................................................................ 67
3.10.6. Ожидание успеха ........................................................................................ 69
3.10.7. Хаб Ethernet ................................................................................................. 69

3.11. Резюме ......................................................................................................70
3.12. Задачи .......................................................................................................70
3.13. Ссылки ......................................................................................................73

Глава 4. Wi-Fi.......................................................................................74

4.1. Основные операции ...................................................................................74
4.2. Управление доступом к среде (MAC) ........................................................75

4.2.1. Протокол MAC ............................................................................................... 75
4.2.2. Усовершенствования для доступа к среде передачи .................................. 78
4.2.3. MAC-адреса ................................................................................................... 79

4.3. Физический уровень ..................................................................................80
4.4. Анализ эффективности протокола MAC ...................................................81

Оглавление  7

4.4.1. Одно устройство ........................................................................................... 81
4.4.2. Несколько устройств ..................................................................................... 82

4.5. Последние достижения ..............................................................................87

4.5.1. IEEE 802.11n – введение MIMO в Wi-Fi ........................................................ 87
4.5.2. IEEE 802.11ad – Wi-Fi в миллиметровом диапазоне .................................. 88
4.5.3. IEEE 802.11ac – введение MU-MIMO в Wi-Fi ............................................... 88
4.5.4. IEEE 802.11ah – Wi-Fi для IoT и M2M ........................................................... 89
4.5.5. Одноранговая Wi-Fi ...................................................................................... 90

4.6. Приложение: цепи Маркова ......................................................................91
4.7. Резюме.........................................................................................................94
4.8. Задачи .........................................................................................................95
4.9. Ссылки ........................................................................................................97

Глава 5. Маршрутизация ...................................................................98

5.1. Домены и двухуровневая маршрутизация ...............................................98

5.1.1. Масштабируемость ....................................................................................... 99
5.1.2. Транзит и пиринг .......................................................................................... 99

5.2. Междоменная маршрутизация ............................................................... 100

5.2.1. Алгоритм вектора пути .............................................................................. 101
5.2.2. Возможные колебания................................................................................ 102
5.2.3. Мультивыходные дискриминаторы .......................................................... 103

5.3. Внутридоменная маршрутизация по кратчайшему пути ..................... 103

5.3.1. Алгоритм Дейкстры и состояние связи ..................................................... 103
5.3.2. Алгоритм Беллмана–Форда и вектор расстояния .................................... 105

5.4. Anycast, multicast ...................................................................................... 107

5.4.1. Anycast ......................................................................................................... 108
5.4.2. Multicast ....................................................................................................... 108
5.4.3. Прямая коррекция ошибок (FEC) .............................................................. 109
5.4.4. Сетевое кодирование .................................................................................. 111

5.5. Сети ad hoc ................................................................................................ 113

5.5.1. AODV ............................................................................................................ 113
5.5.2. OLSR ............................................................................................................. 114
5.5.3. Муравьиная маршрутизация ..................................................................... 114
5.5.4. Географическая маршрутизация ............................................................... 114
5.5.5. Маршрутизация обратного давления ....................................................... 114

5.6. Резюме ...................................................................................................... 114
5.7. Задачи ....................................................................................................... 115
5.8. Ссылки ...................................................................................................... 118

Глава 6. Работа в сети Интернет ..................................................... 119

6.1. Цель ........................................................................................................... 119
6.2. Основные компоненты: маска, шлюз, ARP ............................................ 120

6.2.1. Адреса и подсети ........................................................................................ 121
6.2.2. Шлюз ............................................................................................................ 121
6.2.3. DNS-сервер .................................................................................................. 122
6.2.4. ARP ............................................................................................................... 122
6.2.5. Конфигурация ............................................................................................. 122

6.3. Примеры ................................................................................................... 122

6.3.1. Одна и та же подсеть................................................................................... 123

 Оглавление

6.3.2. Разные подсети ........................................................................................... 123
6.3.3. Поиск IP-адресов ........................................................................................ 124
6.3.4. Фрагментация ............................................................................................. 124

6.4. DHCP ......................................................................................................... 125
6.5. NAT ............................................................................................................ 125
6.6. Резюме ...................................................................................................... 127
6.7. Задачи ....................................................................................................... 127
6.8. Ссылки ...................................................................................................... 128

Глава 7. Транспорт ............................................................................ 129

7.1. Транспортные услуги ............................................................................... 129
7.2. Транспортный заголовок ......................................................................... 130
7.3. Состояния TCP .......................................................................................... 131
7.4. Контроль ошибок ...................................................................................... 132

7.4.1. Stop-and-wait ............................................................................................... 132
7.4.2. Go Back N ...................................................................................................... 133
7.4.3. Выборочные подтверждения ..................................................................... 134
7.4.4. Таймеры ....................................................................................................... 135

7.5. Управление перегрузками ....................................................................... 135

7.5.1. AIMD ............................................................................................................. 136
7.5.2. Усовершенствования: быстрая ретрансляция и быстрое  
восстановление ........................................................................................... 137

7.5.3. Регулировка производительности ............................................................. 138
7.5.4. Размер окна TCP .......................................................................................... 139
7.5.5. Терминология .............................................................................................. 140

7.6. Управление потоком ................................................................................ 140
7.7. Альтернативные схемы управления перегрузками ............................... 141
7.8. Резюме ...................................................................................................... 142
7.9. Задачи ....................................................................................................... 143
7.10. Ссылки ..................................................................................................... 148

Глава 8. Модели ................................................................................ 149

8.1. Графы ........................................................................................................ 149

8.1.1. Max-flow, min-cut ........................................................................................ 150
8.1.2. Раскраска графа и протоколы MAC ........................................................... 151

8.2. Очереди .................................................................................................... 153

8.2.1. Очередь М/М/1 ............................................................................................ 154
8.2.2. Сети Джексона............................................................................................. 155
8.2.3. Очередь против коммуникационных сетей ............................................. 156

8.3. Роль уровней............................................................................................. 158
8.4. Управление перегрузками ....................................................................... 159

8.4.1. Справедливость против производительности .......................................... 159
8.4.2. Распределенное управление перегрузками.............................................. 162
8.4.3. И снова о TCP .............................................................................................. 165

8.5. Динамические маршрутизация и управление перегрузками .............. 167
8.6. Беспроводная связь .................................................................................. 169
8.7. Приложение: обоснование  теоремы двойственности линейного 
программирования .................................................................................. 172

Оглавление  9

8.8. Резюме ...................................................................................................... 173
8.9. Задачи ....................................................................................................... 174
8.10. Ссылки .................................................................................................... 177

Глава 9. LTE ........................................................................................ 179

9.1. Сотовая сеть .............................................................................................. 179
9.2. Технологическая эволюция ..................................................................... 182
9.3. Ключевые аспекты LTE ............................................................................ 183

9.3.1. Архитектура системы LTE .......................................................................... 185
9.3.2. Физический уровень ................................................................................... 187
9.3.3. Поддержка требований QоS ....................................................................... 190
9.3.4. Планировщик .............................................................................................. 190

9.4. LTE-Advanced ............................................................................................ 192

9.4.1. Агрегация несущих ..................................................................................... 193
9.4.2. Поддержка расширенного MIMO ............................................................... 193
9.4.3. Узлы ретрансляции (RN)............................................................................. 193
9.4.4. Координированная многоточечная работа (CoMP) .................................. 194

9.5. 5G ............................................................................................................... 195
9.6. Резюме ...................................................................................................... 196
9.7. Задачи ....................................................................................................... 196
9.8. Ссылки ...................................................................................................... 198

Глава 10. QOS ..................................................................................... 199

10.1. Обзор ....................................................................................................... 199
10.2. Формирование трафика ......................................................................... 200

10.2.1. Механизм leaky bucket .............................................................................. 200
10.2.2. Границы задержки .................................................................................... 201

10.3. Планирование ........................................................................................ 202

10.3.1. GPS ............................................................................................................. 202
10.3.2. WFQ ............................................................................................................ 204

10.4. Регулируемые потоки и WFQ ................................................................ 205
10.5. Сквозное QOS ......................................................................................... 206
10.6. Управление сквозным пропусканием .................................................. 207
10.7. Сетевой нейтралитет .............................................................................. 207
10.8. Резюме .................................................................................................... 208
10.9. Задачи ..................................................................................................... 208
10.10. Ссылки .................................................................................................. 210

Глава 11. Физический уровень сети ................................................ 211

11.1. Как передавать биты? ............................................................................ 211
11.2. Характеристики каналов связи ............................................................. 212
11.3. Проводные и беспроводные каналы связи .......................................... 213

11.3.1. Схемы модуляции: BPSK, QPSK, QAM ...................................................... 213
11.3.2. Межсотовые помехи и OFDM ................................................................... 216

11.4. Оптические линии связи ....................................................................... 218

11.4.1. Работа оптоволокна .................................................................................. 218
11.4.2. Модуляция ООК ........................................................................................ 219
11.4.3. Мультиплексирование с разделением по длине волны ......................... 220

 Оглавление

11.4.4. Оптическая коммутация .......................................................................... 220
11.4.5. Пассивная оптическая сеть ...................................................................... 221

11.5. Резюме .................................................................................................... 222
11.6. Ссылки .................................................................................................... 223

Глава 12. Дополнительные темы .................................................... 224

12.1. Коммутаторы .......................................................................................... 224

12.1.1. Модульные коммутаторы ......................................................................... 224
12.1.2. Матричные коммутаторы каналов .......................................................... 227

12.2. Оверлейные сети .................................................................................... 229

12.2.1. Примеры сетей: CDN и P2P ...................................................................... 231
12.2.2. Маршрутизация в оверлейных сетях ....................................................... 232

12.3. Как работают популярные протоколы P2P ........................................... 232

12.3.1. Первое поколение: на базе сервер/клиент .............................................. 232
12.3.2. Второе поколение: централизованный каталог ..................................... 233
12.3.3. Третье поколение: полностью распределенный протокол .................... 233
12.3.4. Появление иерархического оверлея – суперузлов ................................. 233
12.3.5. Продвинутый распределенный совместный доступ  
к файлам: BitTorrent .................................................................................... 234

12.4. Сенсорные сети ...................................................................................... 235

12.4.1. Вопросы проектирования ........................................................................ 235

12.5. Распределенные приложения ............................................................... 238

12.5.1. Алгоритм маршрутизации Беллмана–Форда ......................................... 238
12.5.2. Регулировка мощности ............................................................................. 239

12.6. Византийское соглашение ..................................................................... 241

12.6.1. Соглашение при ненадежном канале связи ........................................... 241
12.6.2. Консенсус в присутствии противников ................................................... 242

12.7. Сжатие источника .................................................................................. 244
12.8. SDN и NFV ............................................................................................... 244

12.8.1. Архитектура SDN ...................................................................................... 245
12.8.2. Новые услуги, предоставляемые SDN...................................................... 246
12.8.4. Фреймворк управления для NFV ............................................................. 250

12.9. Интернет вещей (IoT) ............................................................................ 252

12.9.1. Парадигмы удаленных вычислений и хранения данных ...................... 252

12.10. Резюме .................................................................................................. 253
12.11. Задачи ................................................................................................... 254
12.12. Ссылки .................................................................................................. 256

Об авторах ......................................................................................... 258

Библиография................................................................................... 259

Предметный указатель .................................................................... 266