A4. Надійна доставка поверх UDP

просунутийспирається на модуль 11, модуль 12

Мета

UDP нічого не обіцяє: датаграма може не дійти, дійти двічі або обігнати попередню. TCP обіцяє доставку байтів у порядку, і майже все, що він для цього робить, можна написати самому: номери, підтвердження, таймер повторної передачі, вікно. Модуль 11 розбирає ці механізми зверху, модуль 12 пояснює, чому вікно мусить обмежуватися ще й мережею, а не лише отримувачем. Тут ви реалізуєте надійну передачу файла поверх UDP і переконаєтеся, як швидко «просте» рішення ламається.

Після цієї роботи ви зможете:

• побудувати протокол із номерами пакетів і підтвердженнями, який доставляє файл без втрат, дублікатів і перестановок;
• обрати таймаут повторної передачі й пояснити, чому він має залежати від виміряного RTT і чому після кожного таймера його збільшують удвічі;
• порахувати, скільки дає stop-and-wait на каналі з RTT 40 мс, і чому ковзне вікно розв’язує цю проблему;
• розрізнити кумулятивне підтвердження й вибіркове (SACK) і сказати, що кожне з них економить;
• перевірити мережевий код на контрольованих вадах, не чекаючи, поки вони трапляться самі.

Так влаштовані QUIC, TFTP, RTP із повторами, протоколи реплікації та будь-який «власний надійний UDP» у ігровому чи IoT-коді. Після цієї роботи ви будете знати, чому в таких протоколах стільки подібного до TCP, хоч їх пишуть, щоб TCP уникнути.

Завдання

Написати на C дві програми: rudp-send і rudp-recv. Формат датаграм ви вигадуєте самі, чекер його не знає й не залежить від нього.

./rudp-recv 9000 out.bin                   # чекає на передачу і пише файл
./rudp-send input.bin 127.0.0.1 9000       # передає файл

Відправник:

• читає файл і передає його отримувачу так, щоб кожен байт дійшов на місце і рівно один раз;
• завершується з кодом 0, коли все підтверджено;
• не вважає, що отримувач уже запущений: стартує першим і повторює спроби;
• якщо протягом приблизно 20 секунд не прийшло жодного підтвердження, пише в stderr, що здається, і завершується з ненульовим кодом;
• не надсилає датаграм із даними понад 1472 байти (MTU 1500 мінус заголовки IP і UDP).

Отримувач:

• приймає передачу від першого відправника, що надіслав дані, складає файл за номерами (а не за порядком прибуття) і записує його у вказаний файл;
• ігнорує дублікати, відповідає на кожну датаграму, навіть на дублікат, бо попереднє підтвердження могло загубитися;
• після завершення передачі лишається ще на кілька секунд (не менше ніж на час, за який відправник повторить останній пакет) і відповідає на повтори, а потім завершується сам з кодом 0;
• не повинен завершуватися, не отримавши файл повністю.

Етапи роботи дають два рівні вимог:

1. Stop-and-wait. Відправник шле один пакет і чекає підтвердження; не прийшло за таймаут — надсилає ще раз.
2. Ковзне вікно. Відправник тримає в дорозі до W непідтверджених пакетів, отримувач підтверджує кумулятивно (і за бажанням вибірково), таймери окремі для кожного пакета.

Чого робити не треба. Керування перевантаженням (вікно можна вибрати сталим), шифрування, стиснення, кілька одночасних передач, IPv6.

Обмеження. C, сокети SOCK_DGRAM, poll або select для таймерів. Потоки не потрібні. Файл можна прочитати в пам’ять цілком.

Готово, коли:

• STAGE=1 ./check.sh ./rudp-send ./rudp-recv проходить усе для етапу 1;
• ./check.sh ./rudp-send ./rudp-recv проходить усе, зокрема заміри з ковзним вікном;
• у звіті є відповіді на запитання з етапів 2, 4 і 5 та виміряна швидкість передачі для вікон 1, 4, 16 і 64 на каналі з RTT 40 мс.

Перед початком

• У модулі 11 прочитайте про номери послідовності, підтвердження й таймер повторної передачі, у модулі 12 про вікно й швидкість.
• Розпакуйте архів курсу: чекер лежить у labs/a4-reliable-udp/check.sh, UDP-проксі з утратами в proxy.py, поруч є Makefile.
• Знадобляться gcc і python3. Права root не потрібні. Підійде будь-який Linux, зокрема контейнер і WSL2.

Етапи

1. Формат датаграм.

   Вигадайте заголовок: тип (дані чи підтвердження), номер пакета, ознака останнього пакета. Вирішіть, скільки байтів даних в одному пакеті (не більше 1472 мінус ваш заголовок) і як отримувач дізнається довжину файла. Порожній файл теж треба передати.

2. Stop-and-wait.

   Відправник: надіслав пакет i, чекає poll із таймаутом, прийшло підтвердження i — надсилає i+1, не прийшло — повторює. Отримувач: номер очікуваного пакета, на правильний відповідає підтвердженням і дописує дані, на старий просто підтверджує ще раз.

   Запустіть на чистій мережі: STAGE=1 ./check.sh ./rudp-send ./rudp-recv. Запишіть у звіт, що станеться, якщо втрачається підтвердження, а не дані, і чому без номерів пакетів отримувач не відрізнив би нову порцію від повтору.

3. Проксі з утратами.

   Чекер ставить між вашими програмами proxy.py; його можна запустити й самому:

   python3 proxy.py 9001 9000 --loss 0.1 --dup 0.1 --reorder 0.2 --delay 10 --stats st.json &
   ./rudp-recv 9000 out.bin &
   ./rudp-send input.bin 127.0.0.1 9001      # не на 9000, а на порт проксі
   cmp input.bin out.bin

   --loss, --dup, --reorder — імовірності (від 0 до 1), --delay — затримка в один бік у мілісекундах, --blackout 0.3:1.5 — повний обрив на 1,5 с, що починається через 0,3 с після першого пакета. Фіксований --seed робить послідовність відтворюваною.

   Витримайте всі перевірки етапу 1 і подивіться, скільки вони тривають.

4. Таймаут.

   Фіксована секунда працюватиме, але повільно: одна втрата — секунда простою. Виміряйте RTT за парами «надіслав — отримав підтвердження» і виставте таймаут як згладжене значення плюс запас на розкид. Не беріть зразок від пакета, який уже повторювався: відповідь незрозуміло, на яку з копій. Після кожного спрацювання таймера збільшуйте таймаут удвічі, а після прогресу повертайте назад: так перевантажену або мертву лінію не засипають повторами.

   Запишіть у звіт, чому без цього відступання обрив зв’язку на 1,5 с викликає лавину повторів, а не просто паузу.

5. Ковзне вікно.

   Вікно з W пакетів: відправник шле нові, поки next < base + W, і пересуває base із кожним кумулятивним підтвердженням. Отримувач тепер буферизує пакети, що прийшли не по порядку, і в підтвердженні називає найменший номер, якого ще немає. Окремий таймер на кожен пакет або один на найстаріший: обирайте самі, але повторюйте лише те, що справді прострочено.

   Порахуйте заздалегідь: при RTT 40 мс і пакеті 1400 байтів stop-and-wait дає приблизно 1400 / 0,04 = 35 КБ/с, отже мегабайт передаватиметься майже 30 секунд, що сильно перевищує ліміт чекера. Вікно з 16 пакетів дасть у 16 разів більше за умови, що канал витримає. Виміряйте швидкість для W = 1, 4, 16, 64 і запишіть у звіт, де графік перестає рости і чому.

6. Вибіркові підтвердження (за бажанням).

   Поле з бітовою маскою тих пакетів, що вже прийшли після пропуску, дозволяє відправнику не повторювати їх. Порівняйте число надісланих датаграм із SACK і без на втратах 10%; proxy.py --stats рахує їх.

Проксі замість tc netem

Для експериментів на реальному інтерфейсі є tc qdisc ... netem (затримка, втрати, перестановка на рівні ядра), і в ВМ вам він знадобиться в B6. Проте модуль sch_netem є не в кожному ядрі, а в частині контейнерів його не завантажити. Тому чекер використовує власний проксі: він працює скрізь, де є python3, і з фіксованим зерном дає відтворюваний результат. Якщо tc netem у вас працює, спробуйте ту саму передачу напряму, наприклад sudo tc qdisc add dev lo root netem loss 10% delay 20ms, і порівняйте з проксі.

Перевірка

cd labs/a4-reliable-udp
make
STAGE=1 ./check.sh ./rudp-send ./rudp-recv    # етап 1
./check.sh ./rudp-send ./rudp-recv            # повна перевірка

Повний прогін триває близько хвилини, у тому числі 20 секунд займає перевірка, що відправник без отримувача здається. Чекер по черзі запускає проксі, отримувача й відправника з різними вадами мережі, порівнює файли за sha256 і друкує час кожної передачі. Перевіряються:

• порожній файл, файл з одного байта, 1 МБ і 7 байтів на чистій мережі, розмір датаграм, самостійне завершення отримувача;
• втрати 10% в обидва боки; 25% дублікатів і 25% перестановок; суміш втрат, дублікатів, перестановок і затримки; зникнення зв’язку на 1,5 с; відправник, що стартував раніше за отримувача;
• етап 2: 1 МБ за 15 секунд при RTT 40 мс і 1% втрат, далі те саме з 3% втрат, перестановкою й дублікатами за 25 секунд, а також перевірка, що повторних датаграм не більше ніж утричі від мінімуму;
• відсутній отримувач.

Чекер не знає вашого формату датаграм, розміру пакета, розміру вікна, способу вимірювати RTT, SACK чи кумулятивне підтвердження: єдиний критерій — файл на виході й час.

Часті помилки

Таймер рахується від першої відправки. Після повторної передачі нова копія має власний момент відправки. Інакше відправник повторюватиме пакет на кожній ітерації циклу.

Отримувач не відповідає на дублікат. Якщо загубився ACK, відправник повторив пакет, а отримувач промовчав, тому що вже його бачив, то відправник повторюватиме до здачі.

Номер пакета порівнюється без урахування переповнення. Файл на гігабайти з 32-бітним номером не зіпсує нічого, але 16-бітний вичерпається на 90 МБ. Подумайте, який розмір поля вам потрібен.

Вікно ніколи не зсувається. base змінюється лише при кумулятивному ACK; якщо ACK на перший пакет загублений, а на решту ні, пересуває base вибіркове підтвердження або наступний кумулятивний.

Прострочені пакети не повторюються, поки йде потік ACK. Таймери треба перевіряти щоразу після poll, а не лише тоді, коли той нічого не повернув.

Отримувач виходить зразу після останнього пакета. Якщо останній ACK загубився, відправник не дізнається, що все дійшло, і не зможе завершитись із кодом 0. Отримувач мусить ще трохи пожити.

Датаграма завелика. Розмір даних 4000 байтів на loopback пройде, а в справжній мережі її буде фрагментовано, а втрата будь-якого фрагмента викине всю датаграму. Чекер відкидає все, що більше за 1472 байти.

Далі, якщо цікаво

Додати керування перевантаженням: вікно, що росте, поки немає втрат, і зменшується вдвічі при втраті, за образом TCP (модуль 12). Виміряти, яку частку пропускної здатності отримає ваш протокол поруч із TCP-потоком на тому самому каналі. Замінити poll на epoll і передавати кілька файлів одночасно. Порівняти з тим, як це зроблено в QUIC, який теж будується на UDP.