реши задачу: По защищенному каналу взаимодействуют...
Создано: 8 февраля 2025 г.
Создано: 8 февраля 2025 г.
реши задачу: По защищенному каналу взаимодействуют устройства А и Б.
Устройство А может выполнять следующие типы операций:
Проверка пакета перед отправкой (скорость операции -
1 Мб/с).
Отправка пакета (скорость операции -
4 Мб/с).
Проверка наличия шифрования на пакете (операция выполняется за
1 с).
Дешифровка пакета (операция выполняется со скоростью
2 Мб/с).
Проверка совпадения дешифрованного пакета с одним из последних
5 отправленных (операция является мгновенной).
Отправка устройству Б уведомления о прекращении взаимодействия (операция является мгновенной).
Приём уведомления о недоставке пакета (операция является мгновенной).
Устройство Б может выполнять следующие типы операций:
Выбор пакета из
5 последних полученных (операция является мгновенной).
Приём пакета от устройства А (операция является мгновенной).
Приём уведомления о прекращении взаимодействия от устройства А (операция является мгновенной).
Шифровка пакета (операция выполняется со скоростью
1,5 Мб/с).
Отправка пакета устройству А (операция выполняется со скоростью
4 Мб/с).
Уведомление устройства А о недоставке пакета (операция является мгновенной).
Передача пакетов может происходить одновременно в обоих направлениях. Пакет доставляется целиком по прошествии
t секунд, где
t - размер пакета (в Мб) / скорость передачи (в Мб в секунду). Для обоих устройств отправка пакета является активным процессом.
При передаче информации по защищенному каналу с устройства А на устройство Б используется алгоритм проверки безопасности подключения: после принятия каждых
5 пакетов, устройство Б берёт один из них, шифрует, затем осуществляет передачу зашифрованного пакета устройству А.
Перед отправкой каждого пакета устройство А проверяет этот пакет.
Если во время проверки некоторого пакета
X перед отправкой или отправки пакета
X устройству A приходит пакет от Б, текущий активный процесс прерывается, и устройство А начинает проверку пакета от Б. Устройство A проверяет, что пакет зашифрован и далее дешифрует пакет.
В случае, если пакет не был зашифрован или если полученный в результате дешифровки пакет не является одним из
5 последних отправленных пакетов, устройство А оповещает устройство Б о прекращении соединения и прекращает все взаимодействия с устройством Б.
Если проверка проходит успешно, А возвращается к передаче пакетов и начинает заново выполнять проверку перед отправкой пакета
X, вне зависимости от того, какая операция над пакетом
X была прервана. То есть, если для пакета не были выполнены и проверка, и отправка, устройство А считает, что ещё не взаимодействовало с этим пакетом.
Если пакет от устройства A приходит в тот момент, когда устройство Б осуществляет шифрование контрольного пакета или передачу зашифрованного пакета, оно не принимает пакет и моментально уведомляет об этом А. Уведомление о недоставке пакета устройство А получит моментально. Если пакет не доставлен, устройство A пытается отправить пакет заново: сначала проводится проверка пакета, затем отправка, до тех пор, пока пакет не будет доставлен или не будет остановлена передача.
Определите, сколько секунд заняла отправка
756 пакетов, если устройство A последовательно отправляло пакеты размером
36 и
24 Мб, а устройство Б выбирало в качестве контрольного всегда
4-й пакет.
Ниже приведён один из возможных разборов задачи «по шагам», который приводит к окончательному ответу 34910 секунд.
Обозначим:
Скорости и времена на стороне устройства A:
Скорости и времена на стороне устройства B:
Алгоритм «контрольного» пакета (со стороны B):
Поведение устройства A при получении контрольного пакета:
Поведение устройства B при получении очередного пакета в момент, когда B занят шифрованием или отправкой контрольного:
Размеры передаваемых пакетов от A к B идут «по очереди»:
Всего требуется отправить 756 пакетов от A к B.
После каждого 5‑го принятого пакета B шифрует и возвращает 4‑й из этих пяти.
Нужно вычислить общее время до полной доставки всех 756 пакетов (с учётом «контрольных» пакетов и всех описанных прерываний).
Таким образом, контрольная передача произойдёт 151 раз.
Для любого пакета размера :
Отсюда для двух размеров:
Когда B после каждых 5 доставленных пакетов шифрует 4‑й из них и отправляет обратно:
Поскольку A чередует пакеты и , то в каждой группе из 5 отправленных пакетов нумерация такая:
Но главное — 4‑й пакет в пятёрке либо (если «4» идёт на чётном номере), либо (если вдруг совпал бы номер 4‑й = нечётный).
Фактически получается, что:
Таким образом, контрольные пакеты будут чередоваться по размеру: 24 МБ, 36 МБ, 24 МБ, 36 МБ, …
Если контрольный пакет размера (тут = либо 24, либо 36):
Когда контрольный пакет прибывает на A:
Значит, для контрольного размера :
По условию, если «контролька» (от B к A) приходит ровно в тот момент, когда A проверяет очередной пакет перед отправкой (или отправляет его), то A бросает свою текущую операцию, переходит к проверке контрольного пакета, а затем начинает заново проверять (и потом отправлять) свой прерванный пакет.
Из этого вытекают дополнительные задержки, потому что A успевает «часть» проверки сделать «впустую», а потом эту часть придётся делать заново.
Ключевой сценарий, который повторяется «в каждой пятёрке»:
В итоге на каждый «контрольный» приход от B получается лишний «срыв» проверки на A.
Пусть контрольный пакет имеет размер . Тогда:
Если смотреть именно на «дополнительную» просадку по времени (по сравнению с тем, если бы контрольный пакет не пришёл), то получаем формулу:
Поскольку прерывание наступает почти всегда до конца проверки , время «прерванной проверки» оказывается примерно равным всему .
Итоговое «штрафное»
Преобразуем дроби:
Таким образом:
Подставим два возможных размера :
Это в точности согласуется с тем, что получается при детальном «пошаговом» разборе первых групп.
Если мы смотрим на последовательность пакетов A (по 5 штук), то они идут чередуясь:
И т.д. То есть по «очерёдности» группы из 5 пакетов чередуются с суммами
Однако важно, что этот «штраф» обычно падает на первый пакет следующей пятёрки. Иными словами, структура времён выглядит так (если смотреть подряд группы):
Но в итоге считать проще «по цепочке», складывая для каждой группы сумму:
где для самой 1‑й группы штрафа «сверху» нет (поскольку «предыдущей» не было).
Обозначим:
Тогда:
Группа 1 (нечётная).
Группа 2 (чётная).
Группа 3 (нечётная).
Группа 4 (чётная).
И т.д. То есть чётные группы дают «215», нечётные (кроме самой первой) дают «247», а самая первая даёт «195».
Общее количество полных групп (по 5 пакетов) – 151.
Теперь посчитаем суммарное время:
Из 76 нечётных одна – это самая первая группа (группа 1), которая даёт .
Остальные нечётных групп дают по .
Итого нечётные группы суммарно:
Все 75 чётных групп дают по каждая:
Сложим:
Это время, когда завершена передача всех 5 × 151 = 755 пакетов.
После 151‑й группы (нечётной) ещё остаётся один пакет .
В итоге на 756‑й:
(это «чистое» время 30 с плюс 35 с дополнительной задержки из‑за контрольного пакета от группы 151).
Общее время:
Полная передача всех 756 пакетов с учётом алгоритма проверки безопасного подключения занимает 34910 секунд.
Если перевести в часы, это примерно часа.