Задача
В реальных компьютерных сетях также используется понятие максимальной единицы передачи (MTU, maximum transmission unit) - размер блока данных, который может быть передан на отрезке сети между двумя устройствами. Этот размер зависит от ограничений используемой технологии
передачи данных на нижнем уровне.
В данной задаче требуется составить оптимальный план передачи пакетов с учётом MTU между разными маршрутизаторами и вычислить минимальное время передачи на его основе.
Нужно иметь в виду, что окно передачи работает по "скользящему" принципу, то есть после получения подтверждения доставки первых байтов окна оно сдвигается вправо на размер доставленной информации.
Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), время передачи до следующего маршрутизатора в миллисекундах и MTU в байтах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.
Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
Примечание 2: считать, если объём данных, который требуется отправить с одного маршрутизатора на другой, превышает MTU, то данные делятся на пакеты, равные максимальной единице передачи или меньше, и отправляются с задержкой в 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами и размером пакета ACK (считать, что он меньше любого MTU).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
3
10.0.0.0 8 2 10 100
20.0.0.0 8 3 10 100
10.0.0.0 8 5 10 10240
1
10.0.0.0 8 4 10 100
1
30.0.0.0 8 4 10 100
1
40.0.0.0 8 1 10 100
1
10.0.0.0 8 4 20 10240
40.1.1.1 1 10.1.1.1 4 102400 |
410 |
Примечание
Если отправлять пакеты с 1-го маршрутизатора на 5-й, то время передачи каждых 10240 байт с учётом подтверждения займёт 41 мс. Если же отправлять с 1-го через 2-й, то 10240 байт окна передачи будут делиться на 103 блока и суммарное время доставки для первого окна
увеличится до 133 мс, а для всего объёма данных - более 1000 мс.