Задача
Для передачи пакетов в глобальной компьютерной сети используются специальные устройства - маршрутизаторы. Они подключены к нескольким линиям связи и на основе содержащихся в их памяти таблиц маршрутизации определяют, по какому из направлений передавать приходящие пакеты.
IPv4 - 4-я и первая, получившая широкое распространение, версия протокола IP (Internet Protocol).
Адреса в этой версии представляют собой 4 октета - блока по 8 бит. В человекочитаемом представлении адреса принято записывать в форме 4-х десятичных чисел от 0 до 255, разделённых точками.
Поскольку маршрутизатор имеет несколько интерфейсов (физических разъёмов, куда подключены кабели связи), в таблице маршрутизации задано соответствие каждого интерфейса той или иной сети. Сеть определяется парой из IP-адреса и битовой маски (в которой N старших бит заполнены единицами, а 32-N младших заполнены нулями). Для проверки того, можно ли маршрутизировать
пакет в какую-либо сеть, битовая маска применяется к адресу сети и адресу узла назначения из пакета с помощью побитового И. Если получившийся результат совпадает, то пакет можно отправить на соответствующий интерфейс.
Протокол управления передачей TCP (transmission control protocol) - протокол более высокого уровня по сравнению с IP, предназначенный для доставки данных в неизменном виде. Для решения этой задачи в нём применяется ряд принципов, один из которых - подтверждение
получения данных. Для подтверждения от получателя к отправителю направляется специальный пакет с признаком ACK, в котором указан диапазон полученных байтов.
При этом для исключения перегрузок сети при передаче больших объёмов данных применяются "окна" передачи. Окном называется максимальный объём данных, который может быть отправлен от отправителя получателю без подтверждения получения. По мере подтверждения получения данных окно смещается вправо и отправляются новые данные.
Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел
указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), и время передачи до следующего маршрутизатора в миллисекундах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.
Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами.
Примечание
102400 = 10240*10, значит, для передачи данных потребуется 10 итераций (сдвигов окна передачи). Каждые 10 Кбайт будут проходить следующую цепочку: отправка с первого маршрутизатора на второй - 10мс, затем со 2-го на 4-й ещё 10 мс, затем 1 мс задержки на
отправку подтверждения и сама передача подтверждения напрямую с 4-го маршрутизатора на 1-й - ещё 10 мс. Таким образом, на передачу каждых 10 Кбайт будет уходить 31 мс.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
10.0.0.0 8 2 10
20.0.0.0 8 3 10
10.0.0.0 8 5 10
1
10.0.0.0 8 4 10
1
30.0.0.0 8 4 10
1
40.0.0.0 8 1 10
1
10.0.0.0 8 4 20
40.1.1.1 1 10.1.1.1 4 102400
|
310
|