The effectiveness of forward error correction in transport protocol at the intrasegment level.pdf Наиболее значимым показателем качества взаимодействия приложений компьютерных сетей является пропускная способность транспортных соединений. Этот операционный параметр в значительной мере определяется транспортным протоколом и параметрами тракта передачи данных [1]. Исследованию вероятностно-временных характеристик транспортных соединений посвящен широкий спектр работ [2-20]. Моделирование транспортного протокола с решающей обратной связью выполнено в [2-8], имитационное исследование его быстродействия проведено в [9-10]. Однако моделирование выполнено при существенных ограничениях на протокольные параметры и факторы, определяющие быстродействие транспортного соединения. Модель состязания конкурирующих абонентов за полосу пропускания транспортного соединения предложена в [11], но только для случая операционного режима селективного повтора. Современные транспортные протоколы для снижения доли повторных передач применяют методы прямой коррекции ошибок [12-20]. Примером такого технологического решения является протокол QUIC кампании Google [12]. В [13-14] выполнено имитационное исследование набора процедурных сценариев транспортного протокола с простейшими методами коррекции ошибок для различных сред передачи данных. Ряд натурных экспериментов на широком спектре сетевого оборудования, проведенных в [15-18], иллюстрирует целесообразность применения механизмов прямой коррекции ошибок для сетевых сервисов реального времени, а также в мультимедийных приложениях. В данных работах выполнена оценка трудоемкости коррекции частично искаженных данных, накладных расходов и ожидаемых технологических ограничений в различных средах передачи данных. Анализ технологии прямой коррекции ошибок в межсегментном пространстве транспортного протокола, проведенный в [19], позволил найти области предпочтительного применения технологии для редуцированного признакового пространства протокольных параметров и характеристик коммуникационной среды. Эффективность применения различных методов прямой коррекции ошибок (поразрядное сложение по модулю 2 с помощью операции XOR, коды Рида-Соломона, сверточные коды) в рамках протокола QUIC исследуется авторами [20]. По результатам стендовых экспериментов отмечается увеличение производительности протокола QUIC с применением технологии прямой коррекции ошибок для маршрутов с большой круговой задержкой и значительным уровнем потерь. Кроме того, авторы делают вывод о целесообразности применения методов прямой коррекции ошибок на канальном и транспортном уровнях. Следует отметить, что исследование эффективности использования методов прямой коррекции ошибок на различных уровнях сетевой архитектуры [12-20] проводилось преимущественно на качественном уровне, численно и в стендовых экспериментах при значительных ограничениях на харак-84 Эффективность прямой коррекции ошибок в транспортном протоколе на внутрисегментном уровне теристики каналов связи, параметры протоколов обмена и коррекции ошибок. В данной работе рассмотрена математическая модель транспортного соединения в фазе информационного переноса с механизмом прямой коррекции ошибок в виде цепи Маркова с дискретным временем. На основе модели предложен анализ условий, обеспечивающих преимущество в быстродействии транспортного протокола с технологией прямой коррекции ошибок в пространстве каждого сегмента перед классическим транспортным протоколом. 1. Модель транспортного соединения Рассмотрим процесс переноса данных между абонентами транспортного протокола, основанного на алгоритме с решающей обратной связью [1] и функционирующего в режиме селективного или группового отказа. Примером семейства таких надежных протоколов является доминирующий в современных компьютерных сетях протокол ТСР [Ibid.]. В режиме селективного отказа повторной передаче от источника подлежат только непринятые получателем протокольные блоки данных (сегменты), а в режиме группового отказа - все, начиная с первого непринятого [Ibid.]. Полагаем, что взаимодействующие абоненты имеют неограниченный поток данных для передачи, а обмен выполняется протокольными блоками данных транспортного протокола (сегментами) одинаковой длины. Подтверждения получателя о корректности приема данных переносятся в сегментах встречного потока. Считаем, что управляющий транспортный протокол имеет дополнительную логику внутрисегментной прямой коррекции ошибок. При этом источник перед отправкой каждого сегмента делит его на A >1 фрагментов равного размера, к ним добавляет B-A, B > A, избыточных фрагментов той же длины и передает в транспортное соединение расширенный сегмент, состоящий из В фрагментов. Каждый фрагмент снабжается служебной информацией, позволяющей обнаружить в нем возможные ошибки и восстановить из В фрагментов исходный сегмент в точке приема. Искажение до B - A произвольных фрагментов расширенного сегмента позволяет на стороне получателя восстановить исходный сегмент и не инициировать повторные передачи. Пусть ff и f - достоверность передачи фрагмента вдоль транспортного соединения от источника до адресата и обратно соответственно. Тогда вероятность доставки исходного сегмента адресату с учетом возможности его восстановления получателем B с помощью механизма прямой коррекции ошибок задается соотношением = Е CBf 0 - ff Г' , а i=A достоверность получения отправителем подтверждения о корректности доставки составит B ^ =^ Cff* (1 - f )B-i . Данные параметрические зависимости от А и В определяют математическую i=A модель различных методов прямой коррекции ошибок. Считаем, что участки переприема вдоль тракта передачи данных имеют одинаковое быстродействие в обоих направлениях, а длительность цикла передачи расширенного сегмента в отдельном звене составляет t. В общем случае длина пути от источника до адресата, переносящего информационный поток, и длина обратного пути, по которому передаются подтверждения на принятые сегменты, могут быть различными. Полагаем, что длина тракта передачи данных, выраженная в количестве участков переприема, в прямом направлении равна D > 1. Обратный тракт, по которому доставляются подтверждения отправителю о корректности приема последовательности сегментов, имеет длину Dr > 1. Считаем, что потерь сегментов из-за блокировок буферной памяти в узлах тракта не происходит. Управление потоком данных реализуется механизмом скользящего окна [Ibid.] размера W > 1. Процесс информационного переноса расширенных сегментов в транспортном соединении может быть описан Марковским процессом с дискретным временем, кратным длительности такта t, в силу того что время между получениями подтверждений имеет геометрическое распределение с параметром [2]. Цепь Маркова задает активность отправителя и изменение размера очереди расширенных сегментов в источнике, ожидающих подтверждения. Область возможных состояний 85 П.В. Приступа, П.А. Михеев, В.В. Поддубный, С.П. Сущенко цепи Маркова определяется длительностью тайм-аута ожидания подтверждения S, выраженной в количестве циклов продолжительности t. Размер тайм-аута связан с длиной тракта и шириной окна неравенствами S > W, S > Df + Dr. Сумма длин прямого и обратного трактов может быть интерпретирована как круговая задержка D = Df + Dr, выраженная в длительностях t (без учета потерь протокольных блоков при передаче вдоль тракта). Состояниям цепи Маркова i = 0, W соответствует размер очереди переданных, но не подтвержденных сегментов в источнике потока, а состояниям i = W +1, S -1 - время, в течение которого отправитель неактивен и ожидает получение подтверждения о корректности приема переданной последовательности из W сегментов. Из нулевого состояния в (D - 1)-е источник продвигается с каждым тактом t с вероятностью детерминированного события. В состояниях i > D-1 после истечения очередного дискретного цикла t к отправителю начинают прибывать подтверждения, и в зависимости от результатов доставки отправитель передает новые сегменты (при положительном подтверждении) либо повторно - искаженные. Завершение цикла пребывания в состоянии D - 1 соответствует времени доведения первого сегмента до адресата и получения на него подтверждения. Дальнейший рост номера состояния происходит с вероятностью искажения подтверждения 1 - Жг в обратном тракте. В состояниях i >D-1 в режиме селективного отказа получение подтверждения порождает переход в (D - 1)-е состояние при W > D или в состояние D + W- 2 -i при Ж D - 1 возврат в состояния D-1 (при W > D) или D + W-2-i (при W < D) происходит при получении подтверждения только в случае успешной доставки адресату дошедших к данному моменту до получателя i - D +1 расширенных сегментов, в противном случае следует возврат в нулевое состояние, поскольку очередь переданных, но не подтвержденных сегментов в этот момент обнуляется. В силу того, что в состояниях i > W источник приостанавливает отправку сегментов, получение подтверждений в состояниях i = W ,D + W - 3 приводит к переходу в состояния D + W-2-i, а из состояний i = D + W - 2,S - 2 - в нулевое. Это справедливо для селективного отказа, а в режиме группового отказа указанные изменения состояний реализуются при поступлении положительных подтверждений. В состоянии S - 1 истекает тайм-аут ожидания подтверждения от получателя о корректности принятых сегментов и происходит безусловный переход в нулевое состояние во всех режимах отказа. Для цепи Маркова с данной структурой переходных вероятностей распределение вероятностей состояний P., i = 0, S - 1, определяется соотношениями между протокольными параметрами W, S и длительностью круговой задержки D и с точностью до параметров Жf и Жг имеет функциональный вид, полученный в [2]. Основной операционной характеристикой транспортного протокола является его пропускная способность, определяемая параметрами тракта передачи данных, накладными расходами и особенностями протокольных процедур управления передачей [Ibid.]. Нормированное быстродействие транспортного соединения определяется средним числом доставленных получателю неискаженных сегментов (с учетом режима отказа [1]) за среднее время между двумя последовательными поступлениями подтверждений [2]. Поскольку время между приходами подтверждений распределено по геометрическому закону с параметром Ж, то среднее время между приходами подтверждений в длительностях цикла t составит T = 1/Жr Тогда для селективной процедуры отказа пропускная способность определится следующей зависимостью [Ibid.]: Пропускная способность транспортного соединения для режима группового отказа с учетом повторной передачи всех сегментов, начиная с первого не принятого [2], задается соотношением 86 Эффективность прямой коррекции ошибок в транспортном протоколе на внутрисегментном уровне 2. Анализ условий предпочтения прямой коррекции ошибок Транспортный протокол с прямой коррекцией ошибок в пространстве каждого сегмента предполагает разбиение на стороне отправителя информационного сегмента на А фрагментов одинаковой длины и снабжение их B-A > 0, B > A, избыточными фрагментами того же размера. Наличие в последовательности информационных фрагментов дополнительных фрагментов с поддержкой исправления ошибок (например, кодами четности, кодами Рида-Соломона и др.) позволяет восстановить сегмент на стороне получателя при искажении до В - А любых фрагментов расширенного сегмента. Получатель при приеме расширенного сегмента с искаженными фрагментами пытается восстановить его и по результатам восстановления высылает отправителю подтверждение, упакованное в аналогичный информационный расширенный сегмент встречного потока. Эффективная реализация технологии прямой коррекции ошибок предполагает поиск параметров А и В, обеспечивающих максимальное быстродействие транспортного соединения с заданными параметрами транспортного протокола, известной круговой задержкой и измеренным в результате мониторинга уровнем ошибок. Наличие избыточных фрагментов в передаваемой последовательности увеличивает вероятность доставки получателю сегмента, однако достигается это за счет роста накладных расходов в виде времени переноса избыточных данных. Отсюда возникает задача поиска в многомерном признаковом пространстве области значений характеристик транспортного соединения (D, ¥r, ¥/), параметров транспортного протокола (W, S) и механизма прямой коррекции ошибок (A, B), обеспечивающей превосходство транспортного протокола с технологией прямой коррекцией ошибок перед классической протокольной процедурой с решающей обратной связью, не применяющей исправление ошибок. Сравнительный анализ протокольных процедур проведем при равных интенсивностях потоков абонентских данных, предлагаемых к передаче. Зададим относительный выигрыш в быстродействии от применения технологии коррекции ошибок по сравнению с классической протокольной процедурой в виде разности пропускных способностей: A(A, B) = Z(W, S, D, A, B) - Z(W, S, D,1,1) . Начнем анализ значений выигрыша без учета накладных расходов, связанных с необходимостью введения дополнительных заголовков и концевиков в каждый фрагмент исходного сегмента для диагностики в них ошибок и корректной сборки сегмента из набора фрагментов. В общем случае сравнительный анализ в режимах селективного и группового повтора удается провести только численно. Однако за счет редуцирования размерности признакового пространства область мажорантных положительных значений выигрыша удается получить в аналитическом виде. В режиме селективного отказа при абсолютно надежном обратном соединительном пути / = 1) либо в случае W выигрыш упрощается до соотношения A (А, S) = К А*¥ B - ff (1) инвариантного к ширине окна (К = 1) для нагруженного транспортного соединения (W > D) и зависящего от размера окна (К = 1/[ D - W +1]) - для недогруженного (W < D). Для технологических параметров прямой коррекции ошибок, удовлетворяющих условию B = A + 1, A >1, нетрудно видеть, существует при . ' A2 f ' A +1 что область положительных значений выигрыша A (A, A +1) = Kff A - 1 - - A > 2 в интервале ff e ( a - 1) A+1 . Максимум выигрыша As (A, A +1) = К -- достигается при значении достоверности ff = 1--. С ростом параметра А положение максимума выигрыша дрейфуf А ет вправо по координате f (рис. 1). Максимально достижимый уровень выигрыша от достоверности доставки фрагментов данных, огибающий доминирующие кривые при различных А, имеет вид, представленный на рис. 2. При этом максимальный выигрыш с ростом А увеличивается вдоль кривой 87 П.В. Приступа, П.А. Михеев, В.В. Поддубный, С.П. Сущенко с насыщением от значения А^(2,3) = К/12 до As(да,да) = K/e (рис. 3). Из вида зависимостей, представленных на рис. 1, нетрудно видеть, что оптимальные значения целочисленного параметра прямой коррекции ошибок А определяются достоверностью доставки получателю фрагментов данных ff. Значения ff, разделяющие оптимальные значения коэффициента разбиения сегмента на фрагменты, равные A и A + 1, определяет условие As (A, A +1) = А (A +1, A + 2), A > 2. Отсюда находим точки разделения областей оптимальности: A( A + 2)(2 A +1) - л/A4 +12 A3 + 32 A2 + 28 A + 8 f = 2( A +1)3 . A=2 - • - A=3---A=4 .........A=5 0,3 ff Рис. 1. Зависимость выигрыша в селективном режиме повтора от достоверности доставки фрагментов данных при W > D, f = 1, B = A +1 для различных значений коэффициента фрагментации Fig. 1. Dependence of the gain in the selective retry mode on the reliability of delivery of data fragments at W > D, f = 1, B = A + 1 for different values of the fragmentation coefficient 0,45 0,4 0,35 0,3 _ 0,25 CO < 0,2 CO < 0,15 0,1 0,05 0 ff -0,05 0 0,2 0,4 0,6 0,8 1 Рис. 2. Зависимость максимально достижимого выигрыша в селективном режиме повтора от достоверности доставки фрагментов данных при W > D, f = 1, B = A +1 Fig. 2. Dependence of the maximum achievable gain in the selective repeat mode on the reliability of delivery of data fragments for W > D, f = 1, B = A +1 88 Эффективность прямой коррекции ошибок в транспортном протоколе на внутрисегментном уровне B=A+1 - • B=A+2 A Рис. 3. Зависимость максимальных значений выигрыша в селективном режиме повтора от коэффициента разбиения сегментов на фрагменты при f = 1 и различных значениях числа избыточных фрагментов Fig. 3. Dependence of the maximum values of the gain in the selective repeat mode on the coefficient of dividing the segments into fragments for f = 1 and different values of the number of redundant fragments На рис. 4 показаны области оптимальных значений коэффициента разбиения сегмента на фрагменты А. Таким образом, для нахождения оптимального значения А достаточно определить, в какую область попадает измеренное в результате мониторинга потерь в транспортном соединении значение f . Для параметров прямой коррекции ошибок B = A + 2, B = A > 1, положительный выигрыш достигается на области значений f е 0. (A -1)(A + 2) A( A +1) , A > 2, а максимум выигрыша - при f = 1 - 2 A( A +1) Максимальные значения выигрыша Ая (A, A + 2) = 11 -« с увеличеa A - 2 + A2 2/A(A +1) А я (A, A + 2) = (1 - V 2/ A( A +1)) - ^1 A + 2 нием А растут от 0,103 до 0,587 (см. рис. 3). Численные исследования выигрыша для произвольных значений параметров многомерного признакового пространства показывают, что As (A,B) имеет унимодальный характер зависимости от достоверности доставки фрагментов данных в области ff е (0,1) и вид кривой с насыщением от коэффициента разбиения сегмента на фрагменты A. Рис. 4. Области оптимальности коэффициента разбиения сегментов на фрагменты Aopt для селективного режима повтора при B = A +1, f = 1 Fig. 4. Optimality regions of the partitioning coefficient of segments into fragments Aopt for the selective repetition mode at B = A +1, f = 1 В режиме группового повтора для абсолютно надежного обратного тракта передачи данных (fr = 1) выигрыш принимает вид: Ag (A, B) A У /_ft b [d-(j-i)Tf ] d-(j-1)/;, (2) 89 П.В. Приступа, П.А. Михеев, В.В. Поддубный, С.П. Сущенко где J = W при W < D и J = D при W > D . Положительные значения выигрыша при A = 1, B = 2 достигаются для достоверности передачи фрагмента в прямом тракте транспортного соединения на ин тервалах ff el 0 D - 2 ' D -1 W > D, D > 3 и ff el 0,2 - D W -1 1 + D < W < D, D > 5 . Для нагруженно го (W > D) и недогруженного (W < D) транспортного соединения с ростом длительности круговой задержки D область положительных значений выигрыша расширяется, максимум растет по кривой с насыщением, и его положение сдвигается в область большей достоверности доставки фрагментов f (рис. 5). Зависимость выигрыша от параметра А при B = A +1, A >1, так же как и в случае селективного повтора, имеет вид кривой с насыщением. Для недогруженного транспортного соединения (1 + D < w < D) с расширением окна от значения W = 1 + D до W = D - 1 область положительных значений выигрыша по координате f расширяется, а максимум выигрыша растет и дрейфует вправо (рис. 6). Такой же эффект имеет место с увеличением параметра прямой коррекции ошибок A для B = A +1. При выполнении условия W = D - 1 рост длительности круговой задержки D приводит к сдвигу вправо по координате ff области положительных значений выигрыша и увеличению преимуществ технологии прямой коррекции ошибок (см. рис. 5, б). - D=5 - • - D=10 ---D=20.........D=40 0,4 ff а - D=5 - • - D=10 ---D=20.........D=40 0,1 0 CO < -0,1 < -0,2 -0,3 ff b Рис. 5. Зависимость выигрыша в групповом режиме повтора от достоверности доставки фрагментов данных при B = A +1 , f = 1 для различных значений D при W > D (а) и W = D -1 (b) Fig. 5. Dependence of the gain in the group repetition mode on the reliability of delivery of data fragments for B = A +1 , f = 1 for different values of D for W > D (а) and W = D -1 (b) Рис. 6. Зависимость выигрыша в групповом режиме повтора от достоверности доставки фрагментов данных для различных размеров ширины окна W при B = A +1, D = 16, f = 1 (а) и для различных длительностей круговой задержки D при B = A +1, W = 10, fr = 1 (b) Fig. 6. Dependence of the gain in the group repetition mode on the reliability of delivery of data fragments for different sizes of the window width W at B = A +1, D = 16, f = 1 (а) and for different round-trip delay times D at B = A +1, W = 10, f = 1 (b) 90 Эффективность прямой коррекции ошибок в транспортном протоколе на внутрисегментном уровне 3. Учет накладных расходов реализации Следует отметить, что при прочих равных условиях с увеличением коэффициента разбиения сегмента на фрагменты (параметра А) размер фрагментов снижается и, как следствие, растет достоверность его доставки получателю f . Кроме того, реализация получателем технологической процедуры восстановления сегмента из полученных фрагментов требует снабжения каждого фрагмента дополнительным служебным заголовком размера H, содержащим контрольную сумму для обнаружения ошибок, данные о взаимном размещении фрагментов в сегменте (смещение от начала сегмента) и, возможно, другую информацию (как это реализовано в IP-протоколе при фрагментации пакетов). Дополнение каждого фрагмента служебной информацией приводит к увеличению времени передачи сегмента в каждом звене транспортного соединения. В связи с этим для корректного сравнительного анализа выигрыша при различных значениях параметра А необходимо перейти к показателю достоверности доставки получателю отдельного бита и уточнению определения длительности такта t. Тогда длительность цикла передачи сегмента в отдельном звене t, выраженная через размер сегмента L, (L - H )/ A + H составит t = Б C , где C - физическая скорость передачи данных в звене. Достоверности доставки отдельного фрагмента получателю и приема подтверждения при Марковской модели ошибок примут вид: ff = (1 - rf )(L-H'))А+Н и fr = (1 - rr ){L-H"),А+H . Здесь rf и rr - битовый уровень ошибок в прямом и обратном тракте передачи данных соответственно. Тогда, например, мажорантные соотношения (1) и (2) перепишутся следующим образом: ЛД A, A) = KCj Л s (А, Б) = C L А¥ f Б (1 + (А -1) H/L ) А - ff Б(1 + (А -1)H/L)[D - (J - 1)Тf ] D - (J - 1)ffA Нетрудно видеть, что дополнение каждого фрагмента служебной информацией приводит к унимодальной зависимости выигрыша от параметра А (в отличие от зависимости в виде кривой с насыщением, полученной в предыдущем разделе без учета накладных расходов реализации; см. рис. 3). С одной стороны, коэффициент разбиения сегмента А следует увеличивать, чтобы повысить вероятность доставки сегментов получателю (за счет комбинаторного характера зависимости от А) и снизить количество повторных передач. С другой стороны, увеличение параметра А приводит к росту длительности такта t и снижению эффективного быстродействия. Численные исследования подтверждают унимодальную зависимость выигрыша от коэффициента А (рис. 7). Отметим также, что при прочих равных условиях с ростом накладных расходов Н область положительных значений выигрыша сужается по координате 1 - г, а максимальное значение выигрыша снижается. Рис. 7. Зависимость максимального уровня выигрыша от количества фрагментов в сегменте с учетом накладных расходов при L = 1 000 байт, H = 20, 40, 60, 80 байт, Гг = 0 для B = A + 1 (а) и B = A + 2 (b) Fig. 7. Dependence of the maximum gain level on the number of fragments in a segment, taking into account overhead costs for L = 1 000 bytes, H = 20, 40, 60, 80 bytes, Гг = 0 for B = A + 1 (а) and B = A + 2 (b) 91 П.В. Приступа, П.А. Михеев, В.В. Поддубный, С.П. Сущенко Заключение В работе предложена модель процесса переноса сегментов данных в транспортном соединении, управляемом надежным транспортным протоколом с технологией прямой коррекции ошибок, реализованной в пространстве каждого сегмента, и подтверждением данных, принятых получателем после процедуры прямой коррекции. Показано, что для всех режимов повтора применение технологии прямой коррекции ошибок выгодно на загруженных транспортных соединениях (W > D) со значительной круговой задержкой (D). Преимущество прямой коррекции ошибок при любом режиме отказа в значительной мере определяется уровнем ошибок в транспортном соединении (rf , гг), коэффициентом фрагментации исходного сегмента (А), числом избыточных фрагментов данных (B - A), соотношением между размером окна (W) и временем круговой задержки (D), а также уровнем накладных расходов реализации технологии. Направлением дальнейших исследований следует выделить задачу обобщения полученных в данной работе результатов на случай соперничества информационных потоков различных абонентских соединений за полосу пропускания маршрута с разделяемыми звеньями тракта передачи данных.

Скачать электронную версию публикации