Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
Dima T
Member

Откуда:
Сообщений: 13913
Делаю прогу для копирования файла по UDP. Отправитель разбивает файл на блоки и шлет получателю.

ТЗ кратко:
Отправитель каждые 20 мс отправляет один пакет с запросом подтверждения (MSG_TYPE_DATA_ASK) и окно из N (размер окна) пакетов MSG_TYPE_DATA (в каждом очередной блок файла, если есть запрос потерянных то сначала их). Отправка может начаться раньше, если придет подтверждение последнего MSG_TYPE_DATA_ASK. В этом случае отсчет 20 мс начинается с отправки первого пакета.
Получатель сохраняет принятые блоки и следит за порядком их поступления. Если получен блок не по порядку, то пропущенные заносятся в таблицу пропущенных. При получении ранее пропущенного он убирается из таблицы.
Получатель отправляет подтверждение MSG_TYPE_COMMIT (номер последнего принятого и список пропущенных) при получении MSG_TYPE_DATA_ASK и при последнего блока (прием завершен).

Схему уже тестил, в целом она рабочая, потери происходят в основном последних блоков окна, т.е. первый пакет окна доходит практически всегда. Теряются как правило несколько последних пакетов подряд, что ожидаемо, т.к. окно пакетов прилетает на очередной шлюз, начало входит, а что не входит - рубится, т.е. хвост.

Вопрос: как управлять размером окна?

Надо придумать какую-то функцию или алгоритм, который в момент получения очередного подтверждения (MSG_TYPE_COMMIT) рассчитает на сколько увеличить/уменьшить текущее значение N.
При расчете можно использовать:
  • Текущее значение размера окна (N).
  • Сколько пакетов доставлено на текущий момент.
  • Количество потерянных пакетов в подтверждении.
  • Количество потерянных пакетов всего.
  • Возможно еще какая-то статистика накопленная отправителем в процессе отправки.

    Пока придумал просто уменьшать размер окна на кол-во потерянных пакетов. В случае если потерь нет - увеличивать на 10%.
    На коротких расстояниях (< 2 мс) оно нормально должно заработать. Подтверждение доставки предыдущего окна будет приниматься сразу после отправки текущего окна.

    Самая большая проблема с большими расстояниями (> 20 мс). Там поправочные изменения будут приходить раз в 20 мс, интервал отправки окон, т.е. корректировка N будет происходить в десятки раз реже, чем на коротких.

    Понимаю что надо как-то учесть время, но тут есть проблемы точных замеров из-за дискретности штатных часов 1-10 мс, а так же из-за вытесняющей многозадачности ОС, т.е. измеряющий поток может банально ожидать получения своего кванта процессорного времени.
    Поэтому при измерении времени вводим погрешность 10 мс (или +/- 5 мс)
  • 11 янв 19, 14:13    [21782837]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    В гитхабе есть?
    11 янв 19, 14:22    [21782845]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    mayton
    В гитхабе есть?

    Пока нет, не доделал еще. Закончу - выложу. Будет с акторами :)
    11 янв 19, 14:28    [21782859]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Я заранее скажу в чём мой интерес. Мне интересно посмотреть на протокол DNS (как подмножество UDP).
    Я хотел приспособить локальный DNS сервер для раздачи каких-то своих сведений не имеющих отношения
    к почте и доменам. А ... ну вобщем какие-то свои сведенья.

    Твою разработку я поддерживаю на уровне энтузиазма, но не очень понимаю что получится
    в конце. Будет ли это твой транспортный протокол поверх протокола коротких сообщений? Или что-то другое?
    11 янв 19, 14:37    [21782876]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dimitry Sibiryakov
    Member

    Откуда:
    Сообщений: 48130
    mayton
    Я хотел приспособить локальный DNS сервер для раздачи каких-то своих сведений не имеющих отношения к почте и доменам.

    Не имеющие отношения к доменам это вряд ли: у него на входе имя хоста/домена. А так https://ru.wikipedia.org/wiki/Типы_ресурсных_записей_DNS и раздавай ТХТ записи сколько пожелаешь.
    11 янв 19, 15:01    [21782912]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    mayton
    Твою разработку я поддерживаю на уровне энтузиазма, но не очень понимаю что получится
    в конце. Будет ли это твой транспортный протокол поверх протокола коротких сообщений? Или что-то другое?

    Я решил есть слона по частям :)

    Конкретно это - создание транспортного протокола передачи сообщений поверх UDP. Плюс побаловаться с акторами. Заодно еще раз попытаться выжать гигабит в локалке.

    На одном конце запускаем ожидание приема на заданном порту и сохранение принятого в заданную папку
    udp_copy -listen_port 1234 -store_folder c:\download
    


    На другом отправляем
    udp_copy c:\backup\*.* 12.34.56.78:1234
    

    Потом запущу прием дома на cubie и буду слать туда бэкапы. Почти продакшн :)
    11 янв 19, 15:02    [21782914]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Dima T
    На одном конце запускаем ожидание приема на заданном порту и сохранение принятого в заданную папку
    udp_copy -listen_port 1234 -store_folder c:\download
    


    На другом отправляем
    udp_copy c:\backup\*.* 12.34.56.78:1234
    

    Потом запущу прием дома на cubie и буду слать туда бэкапы. Почти продакшн :)

    Ну это круть.

    Но я-бы посоветовал считать MD5 в конце и проверять. Так. Навсякий. Вдруг битик потеряешь в пути.
    11 янв 19, 15:28    [21782950]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Basil A. Sidorov
    Member

    Откуда:
    Сообщений: 9288
    Я бы сказал, что "всё украдено до нас", но "прям щас" не могу найти RFC-шки, где расписано управление потоком, быстрое восстановление при потерях и т.п.
    Общий смысл примерно такой: стартуем с оценки RTT в одну секунду и адаптируемся к фактическим задержкам в канале.

    P.S.
    Не исключено, что можно, не изобретая велосипед, просто адаптировать для своих нужд TFTP (с учётом уже сделанных расширений).
    Даже если "не подойдёт" - можно почерпнуть немало полезного.
    11 янв 19, 15:38    [21782966]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Basil A. Sidorov
    Member

    Откуда:
    Сообщений: 9288
    Рекомендую сделать поиск в RFC Index по слову "Congestion" и посмотреть, например, RFC3649 и RFC3124.

    P.S.
    Очень полезно знать о Path MTU Discovery, чтобы не гадать про оптимальный размер блока.
    UDP-Lite, опять-таки. Хотя это если уж совсем упороться по оптимизации ...
    11 янв 19, 15:57    [21782986]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Вот какая-то сравнительная статья есть. Может пригодится.

    https://www.bizety.com/2016/02/03/open-source-udp-file-transfer-tool-comparison/
    11 янв 19, 16:03    [21782996]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Basil A. Sidorov
    Member

    Откуда:
    Сообщений: 9288
    NETIO – Network Benchmark
    11 янв 19, 16:21    [21783017]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    Basil A. Sidorov, спасибо за ссылки. Натолкнул на мысль.

    Мысль такая: я хочу слать максимально быстро, но с минимальным количеством потерь по дороге, т.к. это лишние перезапросы, подготовка к отправке и т.д. и т.п. С другой стороны отсутствие потерь говорит о том что скорость скорее всего можно повысить.
    В итоге напрашивается решение что я должен управлять потерями, т.е. держать скорость такой, чтобы потери были, но в рамках допустимого.

    Думаю надо отталкиваться от доли потерь, но не с начала отправки (например гигабайт отправляется и в конце резко потери возросли), а за последние 1-2 секунды, может даже меньше. Т.е. вычисляем долю потерь, если она ниже нормы - увеличиваем окно, выше - уменьшаем.
    Тут встает вопрос подбора нормы потерь, думаю можно будет подобрать методом научного тыка. Буду думать в этом направлении.

    PS MTU учел, есть проверка хэша всего файла и каждого пакета в отдельности, есть шифрование, есть рандомная составляющая для разнообразия шифрованных пакетов с одинаковым содержимым. Т.к. это за рамками вопроса топика, поэтому не стал усложнять ненужными подробностями.
    11 янв 19, 17:27    [21783115]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    mayton
    В гитхабе есть?

    Сделал папку, пока там только описаловка основных моментов.
    11 янв 19, 18:38    [21783201]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Dima T
    mayton
    В гитхабе есть?

    Сделал папку, пока там только описаловка основных моментов.

    Хм... не знаю. У меня LibreOffice и он открывает этот документ как минимум странно.
    Ты мог-бы его .. экспортировать в что-то очень простое.
    11 янв 19, 22:36    [21783350]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    mayton
    Dima T
    пропущено...

    Сделал папку, пока там только описаловка основных моментов.

    Хм... не знаю. У меня LibreOffice и он открывает этот документ как минимум странно.
    Ты мог-бы его .. экспортировать в что-то очень простое.

    Перепробовал все варианты. Не заточен гитхаб на форматированный текст, только их самодельное форматирование. В PDF`е показывает.
    12 янв 19, 10:27    [21783495]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Dima T
    mayton
    пропущено...

    Хм... не знаю. У меня LibreOffice и он открывает этот документ как минимум странно.
    Ты мог-бы его .. экспортировать в что-то очень простое.

    Перепробовал все варианты. Не заточен гитхаб на форматированный текст, только их самодельное форматирование. В PDF`е показывает.

    Для ведения документиции онлайн мы обычно используем Atlassian Confluence.
    12 янв 19, 11:29    [21783516]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Можешь эскпортнуть в PDF ?
    12 янв 19, 16:44    [21783649]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Я кстати придумал подход при котором тебе вообще никакое окно не нужно.
    12 янв 19, 16:46    [21783651]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Anatoly Moskovsky
    Member

    Откуда: Odessa
    Сообщений: 6376
    Dima T,

    См. алгоритм BBR https://queue.acm.org/detail.cfm?id=3022184
    12 янв 19, 19:31    [21783717]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    kealon(Ruslan)
    Member

    Откуда: Нижневартовск
    Сообщений: 5107
    Dima T
    PS MTU учел, есть проверка хэша всего файла и каждого пакета в отдельности, есть шифрование, есть рандомная составляющая для разнообразия шифрованных пакетов с одинаковым содержимым. Т.к. это за рамками вопроса топика, поэтому не стал усложнять ненужными подробностями.
    MTU это делитель твоего блока UDP, чтобы его избежать тебе придётся либо "сырые сокеты" использовать, т.е. самому генерить блок либо увеличивать его в настройках системы

    вся оптимизация у тебя будет лишь в уменьшении переотправки потерявшихся блоков
    12 янв 19, 21:51    [21783816]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Да. Дима выложил PDF. Спасибо.
    13 янв 19, 14:43    [21784016]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    mayton
    Я кстати придумал подход при котором тебе вообще никакое окно не нужно.

    Делись. Только учти с таймерами все плохо, погрешность 10 мс. Т.е. я могу быстро послать окно пакетов и долгая пауза. Я выбрал 20 мс, т.к. это будет относительно стабильная частота срабатывания.
    Моя мысль в том чтобы нащупать максимальный размер окна, который можно за раз отправить и придерживаться его.
    13 янв 19, 18:14    [21784103]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    Dima T
    Member

    Откуда:
    Сообщений: 13913
    kealon(Ruslan)
    Dima T
    PS MTU учел, есть проверка хэша всего файла и каждого пакета в отдельности, есть шифрование, есть рандомная составляющая для разнообразия шифрованных пакетов с одинаковым содержимым. Т.к. это за рамками вопроса топика, поэтому не стал усложнять ненужными подробностями.
    MTU это делитель твоего блока UDP, чтобы его избежать тебе придётся либо "сырые сокеты" использовать, т.е. самому генерить блок либо увеличивать его в настройках системы

    вся оптимизация у тебя будет лишь в уменьшении переотправки потерявшихся блоков

    Для учета MTU я просто ограничиваю размер UDP пакета. Никакими raw-сокетами MTU ты не увеличишь, это жестко зашитое ограничение. В случае превышения происходит фрагментация или пакет теряется.
    Все сетевое оборудование оперирует пакетами в единицу времени, поэтому пакет надо максимально наполнить чтобы получить максимальную скорость передачи.
    13 янв 19, 18:23    [21784110]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    Dima T
    mayton
    Я кстати придумал подход при котором тебе вообще никакое окно не нужно.

    Делись. Только учти с таймерами все плохо, погрешность 10 мс. Т.е. я могу быстро послать окно пакетов и долгая пауза. Я выбрал 20 мс, т.к. это будет относительно стабильная частота срабатывания.
    Моя мысль в том чтобы нащупать максимальный размер окна, который можно за раз отправить и придерживаться его.

    Да к чорту окна и таймеры. У тебя - задача другая. Тебе вообще не нужен поточный протокол.

    Стоит задача засинхронизировать два файла. Это можно делать так-же как делают p2p клиенты.
    Заполнять их (чанки) в том порядке в каком прилетают пакеты.

    По сути у тебя должно быть две роли. Sender, Receiver. Они должны протокольно сообщить о намерениях.
    Они должны контролировать heartbeat. Тоесть раз в несколько секунд слать ping-pong.
    Если долго нет хертбита то сеанс завершается.

    Они должны отвечать статистикой. Тоесть - принято 20 пакетов за единицу времени.
    Sender должен принимать решение о скорости. Receiver должет запрашивать те chunks
    которые пустые или с битыми CRC32 суммами.

    Sender по завершении сеанса должен сказать что дескыть я всё отправил. И нет-ли еще каких-то потерянных пакетов.

    Чанк может быть равным размеру UDP_DATA а может быть и нет.
    13 янв 19, 18:36    [21784118]     Ответить | Цитировать Сообщить модератору
     Re: Пятничная передача файла по UDP. Алгоритм управления размером окна  [new]
    mayton
    Member

    Откуда: loopback
    Сообщений: 41805
    UP. Дима привет. Вот случайно нашел ссылку. Может будет полезно.

    14 май 19, 09:42    [21884067]     Ответить | Цитировать Сообщить модератору
    Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
    Все форумы / Программирование Ответить