автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математические модели процедур управления потоком высоконагруженных транспортных соединений

На правах рукописи

Кокшепёв Владимир Владимирович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОЦЕДУР УПРАВЛЕНИЯ ПОТОКОМ ВЫСОКОПАГРУЖЕННЫХ ТРАНСПОРТНЫХ СОЕДИНЕНИЙ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов н компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических паук

3 МАР 2015 005559765

Томск 2015

005559765

Работа ныполнепа в федеральном государственном автономном образовательном учреждении высшего образования «Национальный исследовательский Томский государственный университет» на кафедре прикладной информатики.

Научный руководитель: доктор технических паук, профессор

Официальные оппоненты:

Мещеряков Роман Валерьевич, доктор технических паук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники», кафедра безопасности информационных систем, заведующий кафедрой Гайдамака Юлия Васильевна, кандидат физнко-математнческнх паук, доцент, федеральное государственное автономное образовательное учреждение высшего образования «Российский университет дружбы народов», кафедра прикладной информатики и теории вероятностей, доцент

Ведущая организация: федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.Л. Трапезникова Российской академии паук

Защита состоится 0 апреля 2015 г. в 10'!п па заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. 2, ауд.

С диссертацией можно ознакомиться в Научной библиотеке и на официальном сайте федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет» www.tsu.ru.

Материалы но защите диссертации размещены на официальном сайте ТГУ: http://www.tsu.ru/content/news/announcement_of_t.he_rtissertations_in_the_tsu.php

Сущенко Сергей Петрович

102).

Автореферат разослан феврали

2015 года.

Ученый секретарь диссертационного совета доктор технических наук, профессор

—>

Скворцов Алексей Владимирович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Интернет-ресурсы, сетевые службы и приложения, занимают центральную роль в современной индустрии хранения и обработки информации. Важным показателем качества сетевого взаимодействия является пропускная способность транспортных соединений. Основным протоколом транспортного уровня является TCP. Он обслуживает 70-80% трафика сети Интернет и определяет производительность большинства сетевых приложений.

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

Для описания процессов информационного обмена в сетях передачи данных используются методы теории вероятнос ти, теории массового обслуживания и цепей Маркова. Значительный вклад в развитие науки в данной области внесли как отечественные, так и зарубежные ученые: Л.Б. Богуславский, Г.П. Башарин, К.Е. Самуилов, D.M. Вишневский, С.П. Сущенко, L. Kleinrock, С. Casetli, M. Meo, A. Wierman, T. Osogaini, Y. Olsen, J. Padhcy, V. Firoiu, D. Towsley, J. Knrose п многие другие.

Процедуры управления потоком осуществляют регулирование количества данных, передаваемых отправителем, и, как следствие, определяют скорость информационного обмена между взаимодействующими абонентами. Моделирование асинхронных процедур управления потоком обычно осуществляется цепями Маркова с непрерывным или дискретным временем (Л.Б. Богуславский, С.П. Сущенко). Однако существующие модели либо tie учитывают влияния длительности тайм-аута ожидания подтверждения, длины тракта передачи данных, а также внешней нагрузки от абонентов, соперничающих за полосу пропускания, либо предлагают лишь численное решение.

Процедуры управления перегрузкой контролируют размер окна отправителя с целью регуляции нагрузки на сеть при транспортном обмене. Данная функция необходима, так как тракт передачи может быть не способен обслужить поток данных, предложенный взаимодействующими сторонами. Отсутствие подобной регуляции приводит к эффекту сетевых коллапсов. Для моделирования алгоритмов управления перегрузкой применяется широкий спектр методов: теория восстановления и цепи Маркова, метод неподвижной точки, жидкостные модели, теория управления и другие подходы. При этом многие исследователи сходятся во мнении, что наиболее адекватным методом моделирования транспортного обмена являются цепи Маркова. Анализ показывает, что предложенные модели либо не учитывают достаточного количества функциональных возможностей процедур управления перегрузкой (.J. Pailhey, Л. Кишат, D. Towsley, V. I'eroiu, .J. (Jill, M. Mathis), то

3

есть являются недостаточно точными, либо предлагают модели источника пульсирующего трафика (J. Olsen, С. Casetti, М. Meo, N. Ewald, A. Kemp) с. использованием цепей Маркова с непрерывным временем, что не охватывает анализ высоконагруженных транспортных соединений, в ряде случаев плохо описывает дискретный характер сетевого обмена и потенциально затрудняет возможность получения дополнительных операционных характеристик, кроме среднего значения пропускной способности транспортного соединения.

Цель исследования. Целью диссертации является разработка и исследование математических моделей процесса передачи информации в транспортном соединении для оценки его средней пропускной способности с учетом особенностей стандартизованных процедур управления потоком и перегрузкой .

В рамках данной цели были сформулированы следующие задачи:

• Анализ стандартизованных алгоритмов управления потоком и перегрузкой и их моделей, выбор основных подходов и методик моделирования, выявление их особенностей и недостатков;

• Построение математических моделей асинхронных процедур управления потоком для оценки их пропускной способности;

• Построение математических моделей процедур управления перегрузкой для оценки средней пропускной способности транспортного соединения;

• Сравнение предсказаний разработанных моделей с существующими, а также с результатами натурных измерений пропускной способности TCP соединений;

• Реализация программного обеспечения, позволяющего рассчитать среднюю пропускную способност ь транспортного соединения на основе харак терист ик тракта передачи данных и протокольных параметров.

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

Научная новизна. Получены модели процедур управления потоком и перегрузкой транспортного протокола, учитывающие различные канальные характеристики и протокольные параметры, и позволяющие оцепить пропускную способность транспортного соединения:

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

в отдельных его звеньях, протокольных параметров размера окна и длительности

4

тайм-аута ожидания подтверждении для селективного н группового режимов повтора;

2. Предложена индикаторная модель транспортного обмена для селективной процедуры отказа н нагруженном тракте ие])едачи данных, отличающаяся учетом размера очереди протокольных блоков данных перед потоком исследуемого абонентского соединения, и позволяющая получить аналитические зависимости доступной доли пропускной способности тракта от уровня конкурентного трафика, измеряемого распределением длин очередей;

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

Практическая ценность. Предложенные модели позволяют проводить расчеты операционных характеристик транспортного протокола и сравнивать эффективность работы управляющих процедур в разных эксплуатационных условиях, а также дают достаточно точную оценку средней пропускной способности транспортного соединения в сравнении с натурными измерениями. Разработало программное обеспечение, позволяющее рассчитать пропускную способность TCP соединения на основе значений протокольных параметров и канальных характеристик.

Теоретическая значимость. Представленные математические модели процедур управления потоком позволяют проанализировать не только среднее значение пропускной способности транспортного соединения, но также и характер распределения значений размера окна отправителя, а следовательно, и среднеквадратичное отклонение для пропускной способности. Предложенный метод построения моделей может быть применен к изучению и других реализаций TCP, использующих потери как сигнал перегрузки. Кроме того результаты работы могут быть использованы для анализа операционных характеристик протокола SCTP.

Внедрение результатов работы. Программное обеспечение расчета пропускной способности транспортного соединение внедрено в компьютерной фирме ООО «Ф5 Нстворкс» (г. Томск) и используется в процессе тестирования сетевых программно-аппаратных комплексов BIG-IP. Методы оценки протокольных параметров управляющих

процедур внедрены в компьютерной фирме ООО «Интант» (г. Томск) и используются в процессе проектирования и расчета корпоративных мультисервисных сетей передачи данных, а также при настройках телекоммуникационного и серверного оборудования. Кроме того, материалы исследований используются в учебном процессе при чтении курса лекций «Математические модели вычислительных систем и компьютерных сетей» для магистрантов направления 02.04.02 «Фундаментальная информатика и информационные технологии» Томского государственного университета.

На защиту автором выносятся следующие положения:

1. Модели процедур управления потоком транспортного соединения в нагруженном и ненагруженном трактах, учитывающие протокольные параметры размера окна и длительности тайм-аута ожидания подтверждения, характеристики надежности и длины тракта передачи данных для селективного и группового режимов повтора;

2. Модели процедур управлении перегрузкой транспортного протокола для нмеокопа-груженных соединений, учитывающие режимы медленного старта, обхода перегрузки и быстрого восстановления, селективные и групповые подтверждения, обнаружение потерь по тайм-ауту и подтверждениям-дублям, а также алгоритм коррекции размера тайм-аута по экспоненциальной схеме Карна;

3. Программа расчета средней пропускной способности транспортного соединения под управлением процедуры TCP Reno при известном уровне потерь пакетов и круговой задержки сети передачи данных между взаимодействующими абонентами.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-технических форумах: XI Всероссийская научно-практическая конференция «Научное творчество молодежи (НТМ-2007)» (Анжеро-Судженск, 20-21 апреля 2007г.), XII Всероссийская научно-практическая конференция «Научное творчество молодежи (НТМ-2008)» (Анжеро-Судженск, 18-19 апреля 2008 г.), XV Всероссийская научно-практическая конференция «Научное творчество молодежи (НТМ-2011)» (Анжеро-Судженск, 15-10 апреля 2010 г.), XVII Всероссийская научно-практическая конференция «Научное творчество молодежи (НТМ-2013)» (Анжеро-Судженск, 25-2G апреля 2013 г.), VII Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование (ИТММ-2008)» (Анжеро-Судженск, 14-15 ноября 2008 г.), VIII Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование (ИТММ-2009)» (Анжеро-Судженск, 12-13 ноября 2009 г.), IX Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование (ИТММ-2010)» (Анжеро-Судженск, 19-20 ноября 2010 г.), X Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование» (ИТММ-2011)» (Анжеро-Судженск, 25-20 ноября 2011г.), XI Всероссийская

ü

научно-практическая конференция с международным участием «Информационные технологии п математическое, моделирование. (ИТММ-2012)» (Анжеро-Судженск, 23-24 ноября 2012 г.), XII Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование (ИТММ-2013)» (Анжеро-Судженск, 2U-30 ноября 2013 г.), XIII Всероссийская научно-практическая конференция имени А.Ф. Tepnyi-oiia «Информационные технологии и математическое моделирование (ИТММ-2014)» (Анжеро-Судженск, 20-22 ноября 2014 г.), XXII Белорусская зимняя школа-семинар но теории массового обслуживания (BWWQT-2013) «Современные вероятностные методы анализа, проектирования и оптимизации информационно телекоммуникационных сетей» (Минск, 28-31 января 2013 г.), Девятая российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур» (Алтай, июнь 2012 г.), Десятая российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур» (Алтай, июнь 2014 г.), International Conference «Distributed Computer and Communication Networks (DCCN-2013)» Control, Computation, Communications (Moscow, October 2013), XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Томск, 15-17 Октября 2013 г.).

Публикации. По материалам диссертации опубликовано 2G печатных работ, в том числе 4 статьи в журналах, включенных в Перечень рецензируемых научных изданий, рекомендованных Высшей аттестационной комиссией при Министерстве, образования и науки Российской Федерации для опубликования основных результатов диссертаций (из них 2 статьи в журналах, включенных в библиографические базы Web of Science и Scopus), 22 публикации в других научных изданиях.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы и приложения, включающего документы о внедрении. Общий объем работы — 175 страниц. Список литературы включает в себя 174 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе приводится краткое описание транспортного уровня и протокола TCP как основного его представителя, его места и роли в модели OSI. Рассматриваются стандартизованные алгоритмы управления потоком и перегрузкой, такие как RFC0793, Такое, Reno и New-Reno. Дается обзор и краткий анализ существующих математических моделей алгоритмов управления потоком и перегрузкой, а также делаются выводы о па-правлениях работ.

Во второй главе предлагаются и анализируются модели процедур управления потоком высоконагруженных транспортных соединений для замкнутых трактов передачи данных и виде цепи Маркова с дискретным временем, учитывающие длину тракта (£>), размер окна передачи (го), длительность тайм-аута ожидания подтверждения (S1), режим

7

формирования подтверждений (селективный или групповой) и вероятности потери пакетов в прямом и обратном направлениях тракта (В„, П„). Здесь и далее под высоконягру-женными понимаются соединения, имеющий большой объем данных к передаче.

В параграфе 2.1 построены .модели селективной и групповой процедур для одно-звенного тракта передачи. Динамика очереди переданных, но не подтвержденных сегментов па узле-отправителе описывается цепью Маркова с дискретным временем и числом состояний равным 5. Тактом дискретизации I считается время, необходимое для передачи одного пакета. Переходные вероятности цепи Маркова для селективного и группового отказа соответственно задаются зависимостями (1), (2):

1,

По, i=l,S-2■j = г + 1

1 - По, г = 1, ш — = 1

7Гу = <

1 - Но, г = ш, в — 2; у = 0

1, г = 5 - 1 \з = 0

о, о£/1е?'юг ее;

1, ' = 0; 3 = 1

До, ¿ = 1,5 -2 -,з = г + 1

(1- Ло)(1 - вп)\ i = 1,ги -1 ;з = 1

(1- "(1 -й,,)1), 1 = 1,™ = 0

(1)

1 - К, 1. 0.

(2)

г = «1,5 - 2; з = 0 г = Я - 1; ] = 0 о^е-гю^зе.

Пропускная способность рассматриваемого одиозвенного тракта определяется как отношение среднего объема данных, передаваемых до получения квитанции, к среднему времени получения кви танции (3):

С(ш,5)

Ь и>

(3)

где Ь - размер передаваемых сегментов, I - среднее время между поступлением подтверждений, гО - среднее количество сегментов, переданных верно, между последовательным получением подтверждений. Среднее время между поступлением квитанций можно представить в виде I = . Расчет ш выполняется из соотношения (4):

ш-1 А'-1

™ = £ РНь + Т. Ыи,,

к= 1 к—и>

где 1к - среднее количество сегментов, переданных Сх« ошибок в пачке длины к, а Рд. -вероятность нахождения в к-ом состоянии цепи Маркова, что по смыслу соответствует вероятности передачи к сегментов до поступления квитанции.

Вероятности состоянии цепи Маркова находим из систем уравнений локального равновесия, записанных па основе переходных вероятностен, что позволяет получить окончательную формулу нормированной пропускной способности селективной Zc{w,S) и групповой процедуры отказа:

= (1-Л„)(1-Л„) х

/м I I II,,-Но I (1 -"^П"' ' ' (I 1' I /',,(1 !',,)!)

В параграфе 2.3 предлагается обобщение модели селективной процедуры отказа из п. 2.1 на случай тракта передачи произвольной длины I).

Соотношения между Я и I) задают 4 вида решения систем уравнений равновесия для следующих областей изменения протокольных параметров:

1. 1 < ю < 2П, тах(2П,ю + 1) < 5 < 2П + ш - 1;

2. 1 < ш < 2£>, Я > 2й + V) - 1;

3. и) > 20, и> + 1 < Я < 2П + то - 1;

4. ги > 20, 5 > 20 I и; - 1.

Для 1 < т < 2£), тах(20,и: + 1) < 5 < 2£> + т — 1 нормированная пропускная способность '(го, Я, И) принимает вид:

Л=1-Л-; Л=1-Д.. (7)

При ограничениях 1 < ю < 2Д, Я > 2С + ш — 1 нормированная пропускная способность

¿^(ы, Я, П)

выражается как:

В случае ю > 2Л, !/> + 1 < Я < 2Г) + и> — 1 нормированная пропускная способность {т, Я, П) описывается следующей формулой:

Когда же значения параметров окна находится в диапазоне ю > 2П, а тайм-аута - Я > 2Г) + ю — 1, выражение нормированной пропускной способности Я, П) при-

нимает вид:

В параграфе 2.4 предлагается обобщение модели групповой процедуры отказа из п. 2.1, на случай тракта передачи произвольной длины П.

Для длительности тайм-аута, ограниченной снизу 5 > 2О | ги — 1, и произвольной ширины окна пропускная способность с точностью до сомножителя ЛЬ (вероятность нахождения в начальном состоянии цепи Маркова) выразится зависимостью:

'' ' (I - ) /,, I /',Л(| - -1

(11)

А в случае ограничения сквозного тайм-аута сверху тах(2П,и> + 1) < 6' < 'II) + ш — 1 имеем:

¿Р О-ИОИ-РпИ'оРпК!-^)!-',.!5-:"'!- ■

В параграфах 2.2 и 2.5 проводится сравнительный анализ селективной и групповой процедур отказа для односменных и многозвенных трактов. Показано, что представленные модели одпозвенпых трактов при 5 = ш + 1 сводятся к ранее известным моделям асинхронных процедур управления передачей, не учитывающих длительность тайм-аута, а также при ш = 1 полученный результат совпадает с известными выражениями для стартстопного протокола. Также показано, что модели многозвенных трактов при П = 1 сводятся к результатам, представленным в п. 2.1. В параграфах представлен анализ пропускной способности для различных частных случаев.

В параграфе 2.6 приводятся общие выводы по второй главе. Полученные результаты позволяют качественно сравнить эффективности селектинной и групповой процедур отказа. Селективные подтверждения позволяют получить большую пропускную способность транспортного соединения, чем групповые подтверждения. Преимущество селективной процедуры тем больше, чем длиннее тракт передачи данных и чем выше уровень потерь и его каналах связи.

В третьей главе предложена индикаторная модель асинхронной процедуры управлении виртуальным соединением транспортного протокола с селективным режимом отказа в многозвенном тракте в виде двумерной цепи Маркова с дискретным временем. Кроме ранее учтенных параметров и>, Б, £), Р„ данная модель учитывает влияние конкурентного трафика от абонентов, соперничающих за полосу пропускания тракта передачи данных. Учет влияппя внешнего трафика реализуется через заданное распределение длин очередей в транзитных узлах Ьп, п = О, Дг, где N - максимально возможный размер очереди.

В параграфе 3.1 приводится модель селективной процедуры отказа в нагруженном тракте, нвлнющаися расширением модели из п. 2.3. Динамика процесса передачи информационного по тока описывае тся двумерной цепыо Маркова с дискретным временем с переходными вероятностями вида (13). В состоянии цепи Маркова (г,п) источник отправил последовательность размера (г - п) сегментов, которая в процессе переноса в одном из звеньев встретила очередь длиной п сегментов.

10

(1) 1*1,

г = 0,2О - 2; п = 0; ./ = (' + 1; т = 0;

(2) Ь0( 1 - /-;,), г = 21) - 1. - 2: п = 0; У = 1 + 1; т = 0;

(3) 6,„,

(4) Ь0Р„,

(5)

(0) ЪпР0:

(7)1,

(8)1,

(У) 1 - р„,

(10) к,

(11) к,

(12) Я,,

г = 0,5 - 2; п = 0; ,/ = г; П1 = 1, Л":

г = 2£> — 1, го — 1; п = 0; j = 2П - 1; т = 0;

г = т. XV + 2П — 2; п = 0; ./ = IV + 2П - 2 - г; т = 0:

г = ги+ 2П - 1 :.9 - 2; п = 0;

= 0; т = 0; г = 5- 1: п - (НУ; ] =0; т = 0;

г = 0,21)-2 +н; п = 1,ЛГ; 7 = г + 1; т — п;

г = 2О - 1 + 71,6" - 2; 71 = 1, ТУ; _/ = г + 1; т = п;

г = 20 - 1 + 71. ги - 1 + п; 71 = 1, ¿V; ^ = 2£> - 1; т = 0;

г = ги + п. и> + п + 2£> - 2; п = 1, ДГ; ./ = ги + тг + 2£) - 2 - г; т = 0;

(13)

i = «) + п + 2П - 1, 5 - 2; и = 1, Л'; ./ = 0; т = 0.

Нормированная пропускная способность вычисляется аналогично п. 2.1 и принимает вид (14):

Яс(ш.Л'.П)=Я-„Р0 Е ТГГГ £ (¡-2П+2-т.)Г(Ь0+«' £ Р(Л

\« = 2/>-1 + п ( — к> { 2/)—14 п

(14)

где Р(1,п) - вероятности состоянии цепи Маркова.

В параграфах 3.2 и 3.3 приводятся аналитические решения для нормированной пропускной способности в ряде частным случаев, а также проводится их анализ. При Ь(1 = 1 модель сводится к результатам, представленным в главе 2.

Индекс быстродействия виртуального соединения при р0 = 1 для однозвенного тракта (/} = 1) при ю > 2 составит1:

1)

Ьп

(15)

N

где N = пЬп-

п=1

Для случая, когда поток исследуемого однозвенного виртуального соединения всегда встречает очередь ненулевой длины (Ъц = 0), его быстродействие определится выражением:

Zc■(w, 5,1) = Р„ х (

- (1 - Я,)«'-») + £ ^ [1 - (1 - К)'" - - Я0)5-"-1] ^

1 + Р„(1 + I (1 - Р,,)'""1 - (1 - - £ Ья(1 -

(10)

/

В случае многозвенного тракта передачи данных (£> > 1) при 6о = 0, 5 = и> + 1 и иг > 2О + N получаем:

гс{и,, ю + 1,о) = р, я

-2П-Щ2

Т1=1

(1 - У<„(ш - 2Г> - га-I-2))] ^

(17)

1 + Я„(1 + ЛГ) + (2ЛЯ - 1) ¿>„(1 - я;

<и-2Г>-71+1

-1

В параграфе 3.4 приводятся общие выводы по третьей главе. Численные исследования показывают, что доступная виртуальному соединению полоса пропускания для И) > 2/7 и прочих равных условиях практически инвариантна к длипе тракта передачи данных, ощутимо снижаясь от области насыщения лишь при и> = 2П и < 1. Также можно отметить, что индекс пропускной способности моно тонно растет с увеличением размера окна и выходит в режим насыщения уже при и> превышающем удвоенную длину тракта и размер очереди на З-С в зависимости от достоверности передачи в обратном канале. С ростом конкуренции между абонентами за полосу пропускания тракта передачи данных размер очереди увеличивается, и скорость информационного переноса быстро надает.

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

В параграфе 4.1 представлена математическая модель процедуры управления перегрузкой, учитывающая режимы медленного старта и обхода перегрузки. Для описания изменения основных протокольных параметров применяется двумерная цепь Маркова с дискретным временем. Первое измерение описывает изменения значения текущего окна передачи па стороне отправителя (С71ГЛШ). Второе измерение описывает изменения значения порога переключении от режима медленного старта к обходу перегрузки (56ТЯДВ5Й). Тактом дискретизации является время круговой задержки между взаимодействующими абонентами. Переходные вероятности цени Маркова пЦ" принимают вид:

(1)

(2) F',

(3) Fw,

(4) 1 " F\

(5) 1 -

i = 2\ к = 0, [log2 n\ - 1; n = 2, \}V/2\; j = mm(2i,n); m = n;

г = n.W — 1; n = 2, [IV/2J; j = i + 1; m = n;

г = IF; n = 2, \\V/2\\ j -= W; m — n\

i = 2l,fc = 0, ройг"!-!; n = 2, [1T/2J;

j = 1; m = max(2, |>/2|):

г = п, И7; п = 2, |И72]; з = 1; т = шах(2,\г/2\). Используя численные методы, находим вероятности состояний цени Маркова Р{п. Средней размер окна передачи отправителя (СИ'ЛГ£)„,„,) вычисляется по формуле:

1Г \\V/2\

CWNDaVf, J2 Y, iP"

(18)

где 1Г - максимально возможный размер окна отправителя (т.е. CW'ND = 1 ,\V).

Среднее значение пропускной способности В транспортного соединения принимает вид:

В = F

, CWNDlwn MSS RTT

(19)

где F - вероятность потери пакета в прямом направлении передачи.

В параграфе 4.2 предложено расширение модели, описанной в п. 4.1, учетом обнаружения потерь по тайм-ауту и подтверждениям-дублям, что соответствует технической спецификации процедуры TCP Такое. Переходные вероятности цепи Маркова не приводятся ввиду их громоздкости.

Длительность тайм-аута ожидании подтверждения S выражена в количестве тактов дискретизации. S вычисляется как от ношение размера тайм-аута (НТО), выраженного

в секундах, к длительности круговой задержки (RTT), выраженной также в секундах:

НТО

S-- ^ . (20)

Средний размер окна передачи отправителя C\VNnavg вычисляется по формуле:

W \W/2\+S

C\VNDnv!! = Yl Е ip™- (21)

¡=1 11=2

Отправка данных осущест вляется только в тех состояниях цепи Маркова, которые соответствуют режимам медленного старта и обхода перегрузки. В состояниях, соответствующих ожиданию истечения тайм-аута повторной передачи, отправки сегментов не происходит. Поэтому для оценки средней пропускной способности предложено использовать не средней размер окна отправителя, а среднее количество сегментов, отправляемых за такт (SNDnvg):

\v [W/2\

SNDav,, Y, Z ipm- (22)

i=l Tí—2

Кроме того предложенная модель позволяет оценить среднюю долю времени, проводимую протоколом в режиме ожидания истечения тайм-аута повторной передачи TOnvg. Значение TOaV!l задает среднюю долю тактов, в которых управляющая процедура ничего не передавала и просто ожидала наступления тайм-аута:

IV \W/2\+S

ТОт„ ]Г Р,п. (23)

¿=1 n=\\V/2\+l

Выражение средней пропускной способности В транспортного соединения принимает вид:

В = F SNDMSS лш

RTT '

В параграфе 4.3 предложена модель процедуры TCP Reno, основанная на модели из п. 4.2, и дополнительно учит ывающая фазу быстрого восстановления, метод быстрой повторной передачи, алгоритм Карна корректировки длительности тайм-аута, а также селективные подтверждения.

Алгоритм Карна предполагает экспоненциальное увеличение размера тайм-аута ожидания подтверждения после каждого его истечения:

ЯТОк <- 2кНТО0, к = 0, МК,

где к - количество последовательных наступлений тайм-аута без положительных подтверждений между ними, НТО^ - величина тайм-аута ожидания подтверждения, соответствующая к последовательным наступлениям тайм-аута, МК - параметр, ограничивающий экспоненциальный рост сверху (обычно равен 5 или б).

14

Вводится дополнительный параметр МЬ, обозначающий количество потерь, которые способна обнаружить процедура управления передачей, находясь в режиме медленного старта пли обхода перегрузки, и восстановить в режиме быстрого восстановления. При это для групповой схемы подтверждений МЬ — 1, а для селективных подтверждении МЬ = 4.

Переходные вероятности цепи Маркова не приводятся ввиду их громоздкости. Используя численные методы, находятся вероятности состояний цепи Маркова

Средней размер окна передачи отправителя С\УNОа1,а вычисляется но формуле:

\Г I 2МКН \Vt2MK \}У/2\ I 2Л,КА'

СУУМП^^^ Е ?Р»'+ Е Е ЪАтоЛ^- П'-1,2) + 1), (25)

¿=1 п=1 г=»'+1 "=1

где тос1(х, у) - это остаток от деления х на у.

Для оценки средней пропускной способности также используется не средний размер окна отправителя, а оценка среднего количества сегментов, отправляемых за такт:

U-+2MA- LnV2j i _ j 1}

SNDavq = Е Е ipi" + Е -■———- -

t = i 11=2 i=4 /

L"72J IV ML гкЫ-к:П р^к

- Е ^-Е^ЕО/ ( }

71=2

U. fei ^CYF'-^l-F)»

С1)едняя доля времени, проводимого протоколом в режиме ожидания истечения тайм-аута повторной передачи, вычисляется по формуле:

W+2MK L»72J+2"K.V

TOavg= Е Е р™- (2?)

¡-1 п— L1I'/2J -н 1

Средняя пропускная способность транспортного соединения принимает вид:

B=SND^MSS (28)

В параграфе 4.4 приводятся результаты натурных измерений пропускной способности транспортного соединения иод управлением процедуры TCI' Reno для разных значений времени круговой задержки и вероятности потери пакетов.

В параграфе 4.5 приводится сравнительный анализ моделей, представленных в п. 4.1, 4.2 и 4.3, а также показано сравнение численных результатов моделирования с PFTK-формулой и с результатами натурных измерений пропускной способности транспортного соединения (см. рис. 1, где Ml, М2. МЗ соответствуют моделям, предложенным в и. 4.1, 4.2, 4.3, a TCPR соответствует результатам натурных измерений).

0,0001

O.OOÍ

0,01

а

од

Рис. 1: Сравнение численных результатов представленных моделей с натурными измерениями и PFTK-формулоЛ.

В параграфе 4.6 приводятся общие выводы по четвертой главе. Проведенный анализ показывает, что модель МЗ наиболее точно предсказывает поведение процедуры управления перегрузкой TCP Reno для групповых подтверждений. Также можно сделать вывод о том, что модель Ml и PFTK показывают наименьшую точность; при этом Ml нельзя использовать как оценку сверху, так как сначала ее надо расширить режимом быстрого восстановления, a PFTK можно использовать как консервативную оценку снизу. Также можно сделать вывод о положительном влиянии селективных подтверждений не только на пропускную способность, но и на время простоя управляющей процедуры.

В заключении диссертации представлены основные результаты работы, изложенные в пунктах научной новизны, теоретической значимости и практической ценности.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в журналах, включенных в Перечень рецензируемых научных изданий, рекомендованных Высшей аттестационной комиссией при Министерстве образования и науки Российской Федерации для опубликования основных научных результатов диссертаций, и в журналах, включенных в международную базу научного цитирования Scopus;

1. Кокшенёв, В.В. Ai 1ализ быстродействия асинхронной процедуры управления звеном передачи данных / В.В. Кокшенёв, С.П. Сущепко // Вычислительные технологии. - 2008. - Т. 13, спец. вып. 5. - C.G1-G5. - 0,5 / 0,25 п.л.

2. Кокшенёв, В.В. Анализ селективного режима отказа транспортного протокола в нагруженном тракте передаче данных / В.В. Кокшенёв, СЛ. Сущенко, П.А. Михеев // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2013. - №3(24). - С. 78-94. - 0,9 / 0.3 п.л.

10

3. Kokshenev, V.V. Analytical Model of the TCP Reno Congestion Control Procedure through a Discrete-Time Markov Chain / V.V. Kokshenev, S.P. Suschenko // Communications in Computer and Information Science. Vol. 279: Distributed Computer and Communication Networks. 17th International Conference, DCCN 2013, Moscow, Russia, October 7-10, 2013. Revised Selected Papers Vishnevsky, V.; Kozyrev, D.; Larionov, A. (Eds.). - 2014. - pp. 124-135. - 0,04 / 0.32 п.л.

4. Kokshenev, V.V. TCP Reno Congestion Window Size Distribution Analysis / V.V. Kokshenev, S.P. Suschenko // Communications in Computer and Information Science. Vol. 487: Information Technologies and Mathematical Modelling: proceedings of 13th International Scientific Conference, ITMM 2014 named after A.F. Terpugov. - 2014. -pp. 205-213. - 0,48 / 0,24 п.л.

Публикации в других иау^тых изданиях:

5. Кокшенёв, В.В. Сравнительный анализ пропускной способности селективной и групповой процедур отказа транспортного протокола в однозвепном тракте передачи / В.В. Кокшенёв, С.П. Сущенко // Вестник Томского Государственного университета. Управлении, Вычислительная техника и информатика. - 2008. - №2(3). - С. 42-50. - 0,54 / 0,27 п.л.

0. Кокшенёв, В.В. Оптимизация параметров транспортного протокола / В.В. Кокшенёв, С.П. Сущенко // Обозрение прикладной и промышленной математики. - Москва: Редакция журнала «ОПиПМ», 2007. - Т. 15, Выпуск 1 (20.9 - 7.10 2007). - С. 143-144. - 0,11 / 0,055 п.л.

7. Кокшенёв, В.В. Анализ пропускной способности протокола транспортного уровня / В.В. Кокшенёв, С.П. Сущенко // Обозрение прикладной и промышленной математики. - 2008. - Т. 15, вып. 5 (1-8/5/2008). - С. 887-889. - 0,15 / 0,075.

8. Кокшенёв, В.В. О пропускной способности транспортного соединения / В.В. Кокшенёв, C.II. Сущенко // Обозрение прикладной и промышленной математики. -Москва: Редакция журнала «ОПиПМ», 2012. - Т. 19, Выпуск 4. - С. 570-572. - 0,12 / 0,00 п.л.

9. Kokshenev, V.V. TCP Reno Modeling through a Discrete-Time Markov Chain / V.V. Kokshenev, S.P. Suschenko // Distributed Computer and Communication Networks: Control, Computation, Communications. Proceedings, Moscow, Russia, October 7-10, 2013. - Moscow: Teclmosphera, 2013. - P. 74-80. - 0,04 / 0,32 п.л.

10. Kokshenev, V.V. Transport Connection Performance in Loaded Transmission Data

Path / V.V. Kokshenev, S.P. Suschenko, P.A. Mikheev // Distributed Computer

and Communication Networks: Control, Computation, Communications. Proceedings,

17

Moscow, Russia, Oclobcr 7-10, 2013. - Moscow: Teclmospliera, 2013. - P. 81-88. - (),GG / 0,22 п.л.

11. Кокшенёв, В.В. О доступной полосе пропускания виртуального соединения с селективным режимом отказа в нагруженном тракте передачи данных / В.В. Кокшенёв, С.П. Сущенко, П.А. Михеев // Материалы международной научной конференции «Современные вероятностные методы анализа, проектирования н оптимизации информационно телекоммуникационных сетей», Минск, 28-31 января 2013 г. - Минск: Издат. Центр БГУ, 2013. - Выпуск 22. - С. 77-84. - 0,42 / 0,14 п.л.

12. Кокшенёв, В.В. Анализ влияния параметра максимальной коррекции тайм-аута ожидания подтверждения алгоритмом Карна на пропускную способность TCP Reno в условиях постоянной круговой задержки / В.В. Кокшенёв, С.П. Сущенко // XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям: Тезисы докладов, 15-17 октября 2013 г. Томск. -Томск, 2013. - С. 30. - 0,07 / 0,035 п.л.

13. Кокшенёв, В.В. Анализ времени простоя управляющей процедуры протокола транспортного уровня при селективном режиме отказа в многозвенном тракте /'/ Научное творчество молодежи (НТМ-2011): Материалы XIV Всероссийской научно-практической конференции 15-1G апреля 2010 г. в г. Анжеро-Судженске: в 2 ч. -Томск: Издательство Томского университета, 2011. - Ч. 1. - С. 49-50. - 0,1 п.л.

14. Кокшенёв, В.В. Анализ времени простоя управляющих процедур протокола транспортного уровня // Информационные технологии н математическое моделирование (ИТММ-2009), Материалы VIII Всероссийской научно-практической конференции с международным участием 12-13 ноября 2009 г. в г. Анжеро-Судженске: в 2 ч. -Томск: Издат 'сльство Томского университ ета, 2009. — т I 1, — С. 151 — 154. — 0,15 п л

15. Кокшенёв, В.В. Анализ группового режима отказа транспортного протокола в нагруженном тракте передачи данных /' В.В. Кокшенёв, С.П. Сущенко // Информационные технологии и математическое; моделирование (ИТММ-2013): Материалы XII Всероссийской научно-практической конференции с международным участием 29-30 ноября 2013 г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2013. - С. 33-38. - 0,25 / 0,125 п.л.

1G. Кокшенёв, В.В. Анализ пропускной способности транспортного протокола в нагруженном тракте передачи данных / В.В. Кокшенёв, С.П. Сущенко // Труды международной конференции "Современные проблемы математики, информатики н биоинформатики посвященной 100-лстню со дня рождения члена-корреспондента АН СССР Алексея Андреевича Ляпунова. - 2011. - С. 49. - 0,25 / 0,125 п.л.

17. Кокшенёв, В.В. Выбор размера окна передачи и тайм-аута ожидания подтверждения управляющий процедуры протокола транспортного уроиня при селективном режиме отказа в многозвенном тракте / В.В. Кокшенёв, С.II. Сущенко // Информационные технолог ии и математическое .моделирование (ИТММ-2010): Материалы IX Всероссийской научно-практической конференции с международным участием 19-20 ноября 2010 г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2010. - Ч. 1. - С. 17-19. - 0,15 / 0,075 п.л.

18. Кокшенёв, В.В. Выбор тайм-аута ожидания подтверждения управляющей процедуры протокола транспортного уровня в однозвенном детерминированном тракте с очередями // Информационные технологии и математическое моделирование (ИТММ-2011): Материалы X Всероссийской научно-практической конференции с международным участием 25-2Ü ноября 2011г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2011. - Ч. 1. - С. 138-143. - 0,25 п.л.

19. Кокшенёв, В.В. Моделирование транспортного протокола с селективным режимом повтора в нагруженном тракте передачи данных / В.В. Кокшенёв, С.II. Сущенко, В.А. Белинский // Информационные технологии и математическое моделирование (ИТММ-2012): Материалы XI Всероссийской научно-практической конференции с международным участием 23-24 ноября 2012 г. в г. Анжеро-Судженске: в 2 ч. - Кемерово: Практика, 2012. - Ч. 2. - С. 75-79. - 0,33 / 0,11.

20. Кокшенёв, В.В. Моделирования TCI' Heno цепью Маркова с дискретным временем // Информационные технологии и математическое моделирование (ИТММ-2013): Материалы XII Всероссийской научно-практической конференции с международным участием 29-30 ноября 2013 г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2013. - Ч. 2. - С. 28-33. - 0,24 п.л.

21. Кокшепсв, В.В. Анализ распределения размера окна отправителя для протокола TCP Reno / B.I!. Кокшенёв, С.II. Сущенко // Информационные технологии и математическое моделирование (IITMM-2014): Материалы XIII Всероссийской научно-практической конференции имени А.Ф. Терпугова, 20-22 ноября 2014 г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2014. - Ч. 2. - С. 1GG-1G7. - 0,11 п.л.

22. Кокшенёв, В.В. Моделирование TCP Tahoe цепью Маркова с дискретным временем /'/ Научное творчество молодежи, Материалы XVII Всероссийской научно-практической конференции 25-26 апреля 2013 г. в г. Анжеро-Судженске: в 2 ч. -Томск: Издательство Томского университета, 2013. - Ч. 1. - С. 20-31. - 0,37 п.л.

23. Кокшенёв, В.В. О быстродействии селективного режима протокола транспортного уровня // Научное творчество молодежи, Материалы XII Всероссийской научно-

19

практической конференции 18-19 апреля 2008 г. в г. Анжеро-Судженске: в 2 ч. -Томск: Издательство Томского университета, 2008. - Ч. 1. - С.18-20. - 0,2 п.л.

24. Кокшенёв, В.В. О потенциальном быстродействии транспортного протокола / В.В. Кокшонёв, С.П. Сущенко //' Материалы девятой российской конференции с международным участием «Новые Информационные технологии в исследовании сложных структур». - Томск: Издательство НТЛ, 2012. - С. 37. - 0,1 / 0,05 п.л.

25. Кокшенёв, В.В. Оптимизация операционных характеристик протокола транспортного уровня при селективной процедуре отказа // Научное творчество молодежи: Материалы XI Всероссийской научно-практической конференции 20-21 апреля 2007г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2007. - 4.1. - С. 89-92. -0,175 п.л.

20. Кокшенёв, В.В. Пропускная способность селективного режима отказа протокола транспортного уровня в многозвенном тракте /'/ Информационные технологии и математическое моделирование (ИТММ-2008), Материалы VII Всероссийской научно-практической конференции с международным участием 14-15 ноября 2008 г. в г. Анжеро-Судженске: в 2 ч. - Томск: Издательство Томского университета, 2008. - Ч. 2. - С. 15-20. - 0,24 п.л.

Подписано к печати 28.01.2015 г. Формат С0х84!д6. Печать рнзографическая. Бумага офсетная №1. Тираж 100 экз. Заказ № 1550 Тираж отпечатан в типографии «Иван Фёдоров» 634026 г. Томск, ул. Розы Люксембург, 115/1