Компьютерные сети. 6-е изд.

Вопросы и задачи

1. При каких условиях служба, ориентированная на установление соединения, будет (или по крайней мере должна) доставлять пакеты не по порядку? Обоснуйте свой ответ.

2. Рассмотрим проблему проектирования, которая возникает при реализации сервиса с виртуальными каналами. Если в сети используются виртуальные каналы, то каждый пакет данных должен иметь 3-байтный заголовок, а каждый маршрутизатор должен выделить 8 байт памяти для идентификации канала. Если сеть основана на дейтаграммах, нужны 15-байтные заголовки, но не требуется место в таблице маршрутизатора. Стоимость пропускной способности составляет 1 цент за 106 байт для каждого транзитного участка. Стоимость быстродействующей памяти для маршрутизатора составляет 1 цент за 1 байт; при этом срок ее амортизации равен двум годам при 40-часовой рабочей неделе. Согласно статистике, сеанс в среднем длится 1000 с, и за это время передается 200 пакетов. В среднем пакету требуется четыре транзитных участка. Какая реализация эффективнее и насколько?

3. Докажите, что проблема счета до бесконечности на илл. 5.10 (б) будет решена, если маршрутизаторы добавят в своих векторах расстояний исходящее соединение для каждой пары «получатель — стоимость». Например, узел C на илл. 5.10 (а) не только объявит маршрут до узла A с расстоянием 2, но и сообщит, что этот путь проходит через узел B. Покажите расстояния от каждого маршрутизатора до A после каждого обмена векторами расстояний, пока все маршрутизаторы не убедятся в том, что узел A больше для них не доступен.

4. Рассмотрим сеть на илл. 5.12 (а). Используется алгоритм дистанционно-векторной маршрутизации. На маршрутизатор D только что поступили следующие пакеты состояния линий: от A: (B: 5, E: 4); от B: ( A: 4, C: 1, F: 5); от C: (B: 3, D: 4, E: 3); от E: ( A: 2, C: 2, F: 2); от F: (B: 1, D: 2, E: 3). Накладные расходы от D до C и F равны 3 и 4 соответственно. Какой будет новая таблица маршрутизатора D? Укажите используемые выходные линии и ожидаемые накладные расходы.

5. Рассмотрим сеть на илл. 5.7, не учитывая при этом указанные на линиях веса. Допустим, что в качестве алгоритма маршрутизации используется лавинная адресация. Перечислите все маршруты пакета, отправленного из A в D, если максимальное количество транзитных участков равно 3. Сколько пропускной способности затратит этот пакет в пересчете на количество транзитных участков?

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

7. Рассмотрим подсеть на илл. 5.12 (а). Используется алгоритм дистанционно-векторной маршрутизации. На маршрутизатор C только что поступили следующие векторы: от B: (5, 0, 8, 12, 6, 2); от D: (16, 12, 6, 0, 9, 10); от E: (7, 6, 3, 9, 0, 4). Накладные расходы от C до B, D и E равны 6, 3 и 5 соответственно. Какой будет новая таблица маршрутизатора C? Укажите используемые выходные линии и ожидаемые накладные расходы.

8. Объясните, в чем состоит разница между маршрутизацией, пересылкой и коммутацией.

9. На илл. 5.13 логическое ИЛИ двух наборов ACF-битов равно 111 для каждого ряда. Является ли это случайностью или же это значение одинаково во всех подсетях при любых условиях?

10. Какие размеры регионов и кластеров следует выбрать для минимизации таблиц маршрутизации при трехуровневой иерархической маршрутизации, если число маршрутизаторов равно 4800? Начните с гипотезы о том, что решение в виде k кластеров по k регионов из k маршрутизаторов близко к оптимальному. Это значит, что k примерно равно корню кубическому из 4800 (около 16). Методом проб и ошибок подберите все три параметра так, чтобы они были близки к 16.

11. В тексте было отмечено, что когда мобильный хост находится вне дома, пакеты, отправленные на адрес его домашней LAN, перехватываются внутренним агентом этой LAN. Как этот перехват осуществляет внутренний агент в IP-сети на основе локальной сети 802.3?

12. Сколько широковещательных пакетов формируется маршрутизатором B на илл. 5.6 с помощью:

а) пересылки в обратном направлении;

б) входного дерева?

13. Рассмотрим сеть на рис 5.15 (а). Предположим, что добавляется новая линия между F и G, но входное дерево на илл. 5.15 (б) не меняется. Какие изменения нужно внести в илл. 5.15 (в)?

14. Два хоста соединены друг с другом через маршрутизатор. Объясните, как может возникнуть перегрузка, даже если оба хоста и маршрутизатор используют управление потоком (но не контроль перегрузок). Также объясните, каким образом может быть перегружен получатель при контроле перегрузок, но без управления потоком.

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

16. Дейтаграммная сеть позволяет маршрутизаторам при необходимости удалять пакеты. Вероятность того, что маршрутизатор отвергнет пакет, равна p. Представим путь, проходящий от хоста к хосту через два маршрутизатора. Если один из маршрутизаторов отвергнет пакет, у хоста-источника рано или поздно истечет интервал ожидания, и он попытается повторить передачу. Если обе линии (хост — маршрутизатор и маршрутизатор — маршрутизатор) считать за транзитные участки, чему равно среднее число:

а) транзитных участков, преодолеваемых пакетом за одну передачу;

б) передач для одного пакета;

в) транзитных участков, необходимых для получения пакета?

17. В чем состоит основная разница между двумя методами предотвращения перегрузки: ECN и RED?

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

19. Одно из возможных решений предыдущей проблемы сводится к тому, чтобы формировать трафик передачи файлов таким образом, чтобы он никогда не превышал определенную скорость. Вы решили формировать трафик так, чтобы его скорость никогда не превышала 20 Мбит/с. Какой алгоритм для этого подойдет — маркерного ведра, дырявого ведра или ни один из них? Какой должна быть скорость протекания ведра?

20. Отправитель передает данные со скоростью 100 Мбит/с. Вы решили автоматически отбрасывать идущий от него трафик через 1 с. Каким должен быть размер ведра в байтах?

21. Компьютер использует маркерное ведро емкостью 500 Мбайт и скоростью 5 Мбайт/с. После того как в ведро поступает 300 Мбайт, скорость возрастает до 15 Мбайт/с. Сколько потребуется времени, чтобы передать 1000 Мбайт?

22. Рассмотрим очереди пакетов на илл. 5.29. Назовите время завершения и порядок отправки пакетов, если вес 2 будет иметь не нижняя, а средняя очередь? Пакеты с одинаковым временем завершения отправки следует расположить в алфавитном порядке.

23. Имеется следующая спецификация потока: максимальный размер пакета — 1000 байт, скорость маркерного ведра — 10 Мбайт/с, его размер — 1 Мбайт, максимальная скорость передачи — 50 Мбайт/с. Сколько может длиться передача непрерывной последовательности данных на максимальной скорости?

24. Сеть на илл. 5.32 использует RSVP в деревьях групповой рассылки для хостов 1 и 2. Допустим, хост 3 запрашивает канал с пропускной способностью 2 Мбайт/с для потока от хоста 1 и еще один канал с пропускной способностью 1 Мбайт/с для потока от хоста 2. Одновременно хост 4 запрашивает канал с пропускной способностью 2 Мбайт/с для потока от хоста 1, а хост 5 запрашивает канал с пропускной способностью 1 Мбайт/с для потока от хоста 2. Какую суммарную пропускную способность необходимо зарезервировать для удовлетворения перечисленных запросов на маршрутизаторах A, B, C, E, H, J, K и L?

25. Маршрутизатор может обрабатывать 2 млн пакетов в секунду. Нагрузка составляет в среднем 1,5 млн пакетов в секунду. Сколько времени уйдет на формирование очередей и обслуживание пакетов процессорами, если на пути от источника до получателя имеется 10 маршрутизаторов?

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

27. Допустим, хост А соединен с маршрутизатором R1. Тот, в свою очередь, соединен с маршрутизатором R2, а R2 — с хостом B. Сообщение TCP, содержащее 900 байт данных и 20 байт TCP-заголовка, передается IP-программе, установленной на хосте А, для доставки его хосту В. Каковы значения полей Total length, Identification, DF, MF и Fragment offset IP-заголовка каждого пакета, передающегося по трем линиям? Предполагается, что на линии А–R1 максимальный размер фрейма равен 1024 байтам, включая 14-байтный заголовок фрейма, на линии R1–R2 он составляет 512 байт, включая 8-байтный заголовок, и на линии R2–B — 512 байт, включая 12-байтный заголовок.

28. Маршрутизатор обрабатывает IP-пакеты, общая длина которых (включая данные и заголовок) равна 1024 байта. Предполагая, что пакеты существуют в течение 10 с, вычислите максимальную скорость передачи данных, с которой может работать маршрутизатор без риска зацикливания в пространстве идентификационных номеров IP-дейтаграммы.

29. IP-дейтаграмма, использующая опцию Strict source routing, должна быть фрагментирована. Копируется ли эта опция в каждый фрагмент или достаточно поместить ее в первый фрагмент? Обоснуйте свой ответ.

30. Представьте, что вместо 16 бит в адресе класса B для обозначения номера сети отводилось бы 20 бит. Сколько было бы тогда сетей класса B?

31. Преобразуйте IP-адрес, шестнадцатеричное представление которого равно C22F1582, в десятичный формат, разделенный точками.

32. Двум устройствам с поддержкой IPv6 необходимо связаться друг с другом в интернете. К сожалению, путь между ними проходит через сеть, в которой еще не была внедрена поддержка протокола IPv6. Каким образом могут связаться эти два устройства?

33. Маска подсети сети интернета равна 255.255.240.0. Чему равно максимальное число хостов в ней?

34. IP-адреса подходят для обозначения сетей, а Ethernet-адреса — нет. Как вы думаете, почему?

35. Существует множество адресов, начинающихся с IP-адреса 198.16.0.0. Допустим, организации A, B, C и D запрашивают 4000, 2000, 4000 и 8000 адресов соответственно. Для каждой из них укажите первый и последний выданные адреса, а также маску вида w.x.y.z/s.

36. Маршрутизатор только что получил информацию о следующих IP-адресах: 57.6.96.0/21, 57.6.104.0/21, 57.6.112.0/21 и 57.6.120.0/21. Если для них используется одна и та же исходящая линия, можно ли их агрегировать? Если да, то во что? Если нет, то почему?

37. Набор IP-адресов с 29.18.0.0 по 29.18.127.255 агрегирован в 29.18.0.0/17. При этом, однако, остался пробел из 1024 свободных адресов с 29.18.60.0 по 29.18.63.255, которые впоследствии были присвоены хосту, использующему другую исходящую линию. Нужно ли теперь разделить агрегированный адрес на составляющие, добавить в таблицу новый блок, а потом посмотреть, возможна ли новая агрегация? Если нет, тогда что можно сделать?

38. Имеются три маршрутизатора: A, B и C. Маршрутизатор A объявляет маршруты для диапазонов адресов 37.62.5.0/24, 37.62.2.0/23 и 37.62.128.0/17. Маршрутизатор B объявляет маршруты для диапазонов адресов 37.61.63.0/24 и 37.62.64.0/18. Затем они агрегируют свои диапазоны и объявляют полученный результат маршрутизатору C. К каким ошибкам в маршрутизации это приведет, если таблица маршрутизатора C будет содержать только эти два агрегированных диапазона адресов? Что могут сделать маршрутизаторы, чтобы не допустить этого?

39. Многие компании устанавливают два и более маршрутизатора для соединения с провайдером, что гарантирует некоторый запас прочности на случай, если один из маршрутизаторов выйдет из строя. Применима ли такая политика при использовании NAT? Обоснуйте свой ответ.

40. Вы собрались поиграть со своим другом по интернету. Он запустил игровой сервер и сообщил вам номер прослушиваемого сервером порта. Допустим, что и ваша сеть, и сеть вашего друга отделены от интернета NAT-блоком. Что при этом делает NAT с входящими пакетами, которые вы отправляете? Как можно избавиться от этой проблемы, не убирая NAT?

41. Два компьютера, расположенные в одной сети, пытаются использовать один и тот же номер порта для связи с сервером в другой сети. Возможно ли это? Объясните свой ответ. Что изменится, если эти компьютеры будут отделены от других сетей NAT-блоком?

42. Вы рассказали другу про протокол ARP. Когда вы закончили объяснения, он сказал: «Ясно. ARP предоставляет услуги сетевому уровню, а значит, является частью канального». Что вы ему ответите?

43. Вы подключаете телефон к беспроводной сети у себя дома. Эта сеть создана модемом, предоставленным вашим провайдером. Используя протокол DHCP, ваш телефон получает IP-адрес 192.168.0.103. Каким, скорее всего, будет IP-адрес отправителя в сообщении DHCP OFFER?

44. Опишите способ сборки пакета из фрагментов на стороне получателя.

45. В большинстве алгоритмов сборки IP-дейтаграмм из фрагментов используется таймер, чтобы из-за потерянного фрагмента буфер, где производится повторная сборка, не оказался занят остальными фрагментами. Предположим, дейтаграмма делится на четыре фрагмента. Первые три прибывают к получателю, а четвертый задерживается. У получателя истекает период ожидания, и три фрагмента удаляются из его памяти. Позже приходит последний фрагмент. Как следует с ним поступить?

46. В IP контрольная сумма покрывает только заголовок, но не данные. Почему, как вы полагаете, была выбрана подобная схема?

47. Жительница Бостона едет в Миннеаполис, захватив с собой ноутбук. К ее удивлению, в Миннеаполисе LAN является беспроводной локальной IP-сетью, поэтому ей не нужно подключать свой ноутбук. Нужно ли, тем не менее, проходить процедуру с внутренним и внешним агентом, чтобы электронная почта и другой трафик приходили корректно?

48. Протокол IPv6 использует 16-байтные адреса. На какое время их хватит, если каждую пикосекунду назначать блок в 1 млн адресов?

49. Чтобы решить проблему нехватки адресов IPv4, интернет-провайдеры могут динамически выделять их своим клиентам. После полного развертывания IPv6 адресное пространство станет достаточным для предоставления уникального адреса каждому устройству. При этом для упрощения системы можно было бы выделять каждому устройству постоянный адрес IPv6. Объясните, почему не стоит этого делать?

50. Поле Protocol, используемое в заголовке IPv4, отсутствует в фиксированном заголовке IPv6. Почему?

51. Должен ли протокол ARP быть изменен при переходе на IPv6? Если да, то какими должны быть эти изменения — концептуальными или техническими?

52. Напишите программу, моделирующую маршрутизацию методом лавинной адресации. Все пакеты должны содержать счетчик, уменьшающийся на каждом маршрутизаторе. Когда счетчик доходит до нуля, пакет удаляется. Время дискретно, и каждая линия обрабатывает за временной интервал один пакет. Создайте три версии этой программы: с лавинной адресацией по всем линиям; по всем линиям, кроме входной; только по k лучшим линиям (выбираемым статически). Сравните лавину с детерминированной маршрутизацией (k = 1) с точки зрения задержки и использования пропускной способности.

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

54. Напишите функцию, осуществляющую пересылку в IP-маршрутизаторе. У процедуры должен быть один параметр — IP-адрес. Также у нее есть доступ к глобальной таблице, представляющей собой массив из троек значений. Каждая тройка содержит следующие целочисленные значения: IP-адрес, маску подсети и исходящую линию. Функция ищет IP-адрес в таблице, используя CIDR, и возвращает номер исходящей линии.

55. Используя программы traceroute (UNIX) или tracert (Windows), исследуйте маршрут от вашего компьютера до различных университетов мира. Составьте список трансокеанских линий. Вот некоторые адреса:

www.berkeley.edu (Калифорния)

www.mit.edu (Массачусетс)

www.vu.nl (Амстердам)

www.ucl.ac.uk (Лондон)

www.usyd.edu.au (Сидней)

www.u-tokyo.ac.jp (Токио)

www.uct.ac.za (Кейптаун)