Разработка методов и программных средств функционального моделирования протоколов межмашинной связи вычислительных сетей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Хачатрян, Геворк Жоржикович

• Хачатрян, Геворк Жоржикович
• кандидат физико-математических наук
• 1985

Оглавление диссертации кандидат физико-математических наук Хачатрян, Геворк Жоржикович

Введение

ГЛАВА I. СОСТОЯНИЕ ПРОБЛЕМЫ И ОБЗОР ЛИТЕРАТУРЫ

§ I. Вычислительные сети и их характеристики

1.1. Логическая структура вычислительной сети.

Уровни программного обеспечения. Протоколы

§ 2. Методы и средства исследования протоколов

2.1. Цель исследования

2.2. Методы формального описания и логического анализа протоколов

2.3. Оценка эффективности функционирования протоколов передачи данных

ГЛАВА 2. СТРЭДТУРНО-ПАРАМЕТРИЧЕСКАЯ ИМИТАЦИОННАЯ

МОДЕЛЬ ПРОТОКОЛОВ МЕЖМАШИННОЙ СВЯЗИ

§ I. Постановка задачи

§ 2. Концептуальная модель ПМС

2.1. Общая характеристика ПМС

2.2. Балансный класс процедур ПМС

2.3. Концептуальная схема процедур ПМС

§ 3. Математическое описание СПИ модели

3.1. Агрегативное представление системы межмашинной связи

3.2. Описание агрегативной модели

§ 4. Принципы построения программного обеспечения

СПИ модели

ГЛАВА 8. ЗЖРИДНОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА

ОУНКЦИОНИРОВАНИЯ ПМС

§ I. Постановка задачи

1.1„ Модель системы .♦

§ 2. Алгоритм вычисления пропускной способности ПМС

2.1 о Схема алгоритма

2.2., Оценка времени подтвервдения

2.3« Анализ механизма "окна"

2.4« Анализ и вычисление виртуального времени передачи кадра (насыщенный вариант трафика) 86 2.5, Вычисление статистических характеристик реального потока

§ 3. Алгоритм среднего времени передачи сообщений

З.Х. Схема алгоритма

3.2. Анализ и вычисление виртуального времени передачи кадра (ненасыщенный вариант трафика)

ГЛАВА 4, ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ И ИССЛЕДОВАНИЕ

ХАРАКТЕРИСТИК ФУНКЦИОНИРОВАНИЯ БАЛАНСНОГО

КЛАССА ПРОЦЕДУР ПМС .ИЗ

§ I. Насыщенный вариант трафика

§ 2. Ненасыщенный вариант трафика

§ 3. Оценка адекватности, эффективности моделей и точности результатов моделирования

§ 4. Выводы

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

Объем издержек, связанный с созданием и сопровождением программных средств, вызывает необходимость научного обоснования управленческих решений относительно разработок программного обеспечения. Доводы в пользу того или иного программного обеспечения оказываются более убедительными, если они подкреплены экспериментами, демонстрирующими его преимущество. Поэтому в процессе разработки технического задания на программное обеспечение в течение ряда лет используется моделирование [69], предназначенное для развития количественного подхода и повышения точности при определении требований к рабочим характеристикам программного обеспечения. При этом очень важно какие методы и средства применяются для оценки параметров системы.

Чтобы получить информацию, необходимую для определения требований к системе обработки данных (например, пропускную способность, задержку и т.п.),обычно приходится использовать функциональное (т.е. управляемое событиями) моделирование аппаратных и программных средств системы, алгоритмов управления и модель связи с внешней средой [63]. И прежде чем сделать выводы относительно свойств программных средств, следует понимать характер и "природу" задачи, которая реализуется программными средствами [ИЗ-].

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

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

В классическом подходе программное обеспечение вычислительной се:?и организуется по слоистой (многоуровневой) архитектуре [45, 96]. Разработка каждого уровня базируется на множестве процедур, определяемых протоколами [14] данного уровня. Следовательно,, программное обеспечение уровня выполняет задачи и функции, в основе которых лежат процессы определенного протокола. Отсюда становится очевидным необходимость моделирования процессов функционирования протоколов на этапе логического проектирования соответствующего программного обеспечения [19, 91].

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

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

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

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

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

Объектом исследования в данной диссертационной работе являются протоколы межмашинной связи (IMC), предназначенные для обеспечения надежной и эффективной передачи данных между двумя удаленными ЭВМ, соединенными физическим каналом связи.

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Хачатрян, Геворк Жоржикович

§ 4. Выводы

Результаты, полученные в данной главе, позволяют сделать следующие основные выводы:

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. В рамках локального подхода предложен метод гибридного моделирования ПМС. По этому методу построены и исследованы алгоритмы вычисления характеристик функционирования ПМС. Разработан комплекс программ реализации алгоритмов гибридного моделирования.

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

Автор выражает глубокую признательность своему научному руководителю доктору физико-математических наук, профессору Евгению Александровичу Гребеникову за постоянную поддержку и внимание к работе. Автор особенно благодарен кандидату физикоматематических наук Георгию Андреевичу Волкову за полезные обсуждения и многостороннюю помощь. Пользуясь случаем, автору хотелось бы поблагодарить всех тех, с кем приходилось общаться во время выполнения работы.

Список литературы диссертационного исследования кандидат физико-математических наук Хачатрян, Геворк Жоржикович, 1985 год

1. Андрианов A.B. Аналитическая модель алгоритма управления потоком протокола Х.25. - В кн. Вычислительные сети коммутации пакетов. Рига: Зинатне, 1981, с.5-9.

2. Богуславский Л.Б. и др. Методы и модели управления потоком данных в сетях ЭВМ. Зарубежная радиоэлектроника, 1980,10, с.3-27.

3. Богуславский Л.Б. и др. Анализ сквозного управления потоком данных в сетях ЭВМ. Автоматика и вычислительная техника, 1980, В 5, с.61-69.

4. Бочман Г., Мартин Ф. Разработка связных протоколов. Проблемы МСНТИ/МЦНТИ, 1982, 2, с. 146-155.

5. Бусленко В.Н. Моделирование сложных систем. М.: Наука, 1968, - 400с.

6. Бусленко Н.П., Калашников В.В., Коваленко H.H. Лекции по теории сложных систем. М.: Советское, радио, 1973. - 440 с.

7. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ. М.: Финансы ж статистика, 1981. - 256 с.

8. Буянов О.И. Исследование процедур управления звеном передачи данных верхнего уровня. Техника средств связи. Серия ТПС, вып. 8, 1980, с.31-37.

9. Ван дер Варден Б.Л. Математическая статистика. М.: ИЛ, i960. - 434 с.

10. Волков Г.А., Хачатрян Г.Ж. Имитационная модель процедур межмашинной связи. В кн.: Математическое обеспечение и технические средства СКП ЭВМ МГУ. М.: Изд-во Моск.ун-та, 1984,с. I45-.I58.

11. Воронцов Ю.А. Оптимизация обработки смешанного трафика в узлах сети ЭВМ. М.: Изд-во ВИНИТИ, 1982. - 75 с.

12. Гильберт Н.Э. Пропускная способность канала с пакетами ошибок. В кн.: Кибернетический сборник. - М.: Мир, 1964, с.109-141.

13. Даен И.Л. Один метод автоматического конструирования протоколов. В кн.: Седьмая всесоюзная школа-семинар по вычислительным сетям. Тезисы докладов. М.: Изд-во ВИНИТИ, 1983, с.26-29.

14. Дэвис Д. и др. Вычислительные сети и сетевые протоколы.-М.: Мир, 1982, 562 с.

15. Дал У.И. Языки для моделирования систем с дискретными событиями. В кн.: Языки программирования. М.: Мир, 1972, с. 344-403.

16. Ионин Г.Л., Седол Я.Я. Статистическое моделирование систем телетрафика. М.: Радио и связь, 1982. - 184 с.

17. Кожикашзили В.А., Вишневский В.М., Талалай А.И. Метод анализа сетей связи ЭВМ с межконцевым механизмом управления потоком. В кн.: Вычислительные сети коммутации пакетов. Рига: Зинатне, 1981, с.112-116.

18. Злотников Ю.С. и др. Вероятностно-временные характеристики алгоритма квитирования сообщений на межузловых участках сети передачи данных с коммутацией пакетов. Техника средства связи. Серия ТПС, вып.6, 1978, с.66-72.

19. Зелкович Р., Шоу А., Геннон Дж. Принципы разработки программного обеспечения. М.: Мир, 1982. - 368 с.

20. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. - 600 с.

21. Клейнрок Л. Принципы и уроки пакетной связи. ТИИЭР, 1978, т.66, II, с.30-42.

22. Клейнрок JI. Теория массового обслуживания. М.: Машиностроение, 1979. - 435 с.

23. Крамер Г. Математические методы статистики. М.: Мир, 1975, - 647 с.

24. Лифшиц А.Л., Мальцев Э.А. Статистическое моделирование систем массового обслуживания. М.: Советское радио, 1978. -248 с.

25. Мартин Дж. Системный анализ передачи данных. Т.1,2. М.: Мир, 1975.

26. Петренко А.Ф. О моделировании сетевых протоколов. В кн.: Вычислительные сети коммутации пакетов. Рига: Зинатне, 1979, с.83-89.

27. Пранявичюс Г.И. Модели и методы исследования вычислительных систем. Вильнюс: Мокслас, 1982. - 228 с.

28. Пранявичюс Г.И., Применение управляющих последовательностей для: формализованного описания систем при построении имитационных моделей. Программирование, 1979, .£ 6, с. 6974.

29. Пранявичюс Г.И., Листопадкис Н.Ю. Агрегативный метод формального описания и моделирования протоколов (на примере протокола 3.25/3). М.: Изд-во ВИНИТИ, 1983. - 62 с.

30. Пранявичюс Г.И., Хмеляускас A.B. Агрегативный подход и метод управляющих последовательностей как средство исследования корректности и эффективности протоколов. М.: Изд-во ВИНИТИ, 1983. - 29 с.

31. Связной контроллер, реализующий протокол Х.25. Электроника, 1981, т.54, J^ 20, c.II2-II3.

32. Сети ЭВМ. М.: Связь, 1977. - 325 с.

33. Сипсер Р. Архитектура связи в распределенных системах. Т.1.-М.: Мир, 1981. 435с.

34. Талалай А.И. Эвристический алгоритм оптимизации параметров межконцевого механизма управления потоками в сети связи ЭВМ. В кн.: Седьмая всесоюзная школа-семинар по вычислительным сетям. Тезисы докладов. - М.: Изд-во ВИНИТИ, 1983, с. 114-120.

35. Тобаги Ф.А. и др. Методы моделирования и измерений в сетях коммутацией пакетов. ТИИЭР, 1978, т.66, 22, с.156-186.

36. Транспортный протокол ШЛА. Электроника, 1982, $ 15, с. 70-71.

37. Феррари Д. Оценка производительности вычислительных систем.-ГЛ.: Мир, 1981, 576с.

38. Хачатрян Г.Ж. Исследование протоколов передачи данных в вычислительных сетях. В кн.: Различные аспекты системного программирования. М.: Изд-во Моск. ун-та, 1981, с.55-72.

39. Хачатрян Г.Ж. Процедуры управления каналом передачи данных в балансном режиме. В кн.: Программные и технически средства СКД ЭВМ МГУ. М.: Изд-во Моск.ун-та, 1981, с.23-35.

40. Хачатрян Г.Ж. Алгоритмы вычисления вероятностно-временных характеристик линейного протокола. В кн.: Различные аспекты системного программирования. М.: Изд-во Моск. ун-та,1983, с. 16-42.

41. Хачатрян Г.Ж. Характеристики функционирования процедур межмашинной связи (анализ результатов моделирования). В кн.: Математическое обеспечение и технические средства СКП ЭВМ МГУ. М.: Изд-во Моск.ун-та, 1984, с.165-181.

42. Шагин Г.А. Сети и системы с коммутацией пакетов. Зарубежная радиоэлектроника, 1981, Ш 3,4,5.

43. Шварц М„ Сети ЭВМ анализ и проектирование. - М.: Радио и связь, 1981. - 336 с.

44. Шеннон Р. Имитационное моделирование систем: искусство и наука. -- М.: Мир, 1978. 418 с.

45. Якубайтис Э.А. Архитектура вычислительных сетей. М.: Статистика, 1980. - 280 с.

46. Andre P. et al. A critical study of different flow control methods in computer networks. Сотр. Commun. Rev., 1979» v.9, К 3, p. 23-32.

47. Bennett C.J., Hinchey A. Measurements of the transmission control protocol. Computer Кetworks, 1978, v.2,H 2, p. 391-408.

48. Bochmann G.V., Chung R.A formalized specification of HDLC class of procedures. In : Proc. Nat. Telecommun. Conf., Los-Angeles, 1977, p. 03A ; 2.1-2.11.

49. Bochmann G.V., Gecsei J. A unified model for the specification and verification of protocols. In : Proc. IFIP Congress, Toronto, 1977, p. 229-234.

50. Bochmann G.V*, Vogt TU Message link protocol-funfctional specification. Comp. Commun. Rev., 1979» v. 9, N 4, p.7-39.

51. Brand D., Joyner G. Verification of protocols using symbolic exucution, In: Proc. Comput. Network Protocols Symp., Liege, 1978, p. P2.1-P2.7.

52. Bux W., Truong H. A queueing model for HDLC controlled data links. - In s Proc. Int. Symp. Plow Control in Comput. Networks, Versailles, Prance, 1979, p. 289-306.

53. Bux ¥/., Kummerle K., Truong H.L. Results on the perfoiraance of balanced HDLC procedures. In ï Proc. Network Telecommun. Conf., Birmingham, USA, 1978, p. 28.3.1-28.3.7.

54. Bux W., Kummerle K., Truong H.L. Balanced HDLC procedures: A performance analijsis. IEEE Trans. Commun, 1980, v.28, N 11, p. 1889-1898.

55. Consolidation of HDLC elements of procedures. ISO/TC 97/SC 16, 1980„ N 2100, p. 1-57.

56. Curtis B„ Measutement and experimentation in software enginee ring. Proc. of the IEEE, 1980, v.68, N 9, p. 1144-1157.

57. Danthine A. Modelling and verification of end-to-end protocols. In: Proc, Nat« Telecommun. Conf., Los.-Angeles, 1977, v.1, p. 0/Aî 3.1-3.7.

58. Danthine A# Petri nets for protocol modelling and verification. In: Proc. Computer Networks and Teleprocessing Symp., Budapest, 1977, v,2, p. 663-685»

59. Danthine A., Bremer S» An axiomatic description of the transport protocol of Cyclades. In: Proc, Conf. Computer Networks and Teleprocessing, Aachen, 1976, p. 259-273»

60. Danthine A«, Eschenauer E. Influence on packet node behaviour of the intemode protocol» IEEE Trans. Commun., 1976, v.24, M 6, p. 606-614.

61. Didic M., Wolfinger B. Simulation of a local computer network architecture applying a unified modelling systems, -Computer networks, 1982, I 6, p, 75-91.

62. Prank H», Chou V/» Routing in computer networks, Networks, 1971, v,1, N 22, p. 99-112.

63. Gelenbe E», Labetoulle J., Pujolle G. Performance evaluation of the protocol HDLC. In: Proc. Computer Network Protocols Symp,, Liege, 1978, p. G 3.1-G 3.S.

64. Gerla M», Kleinrock L. Flow control: A comparative survey,

65. EE Trans. Commun., 1980, v» 28, N 4, p.553-574. 75« Gieasier A. et al Free buffer allocation An investigation by simulation, - Computer Networks, 1978, v,2, N 2, p.191-208.

66. Lam S., Reizer M. Congestion control of stor-and-forward network by input buffer limit an analysis. - IEEE Trans. Commun., 1979, v.27, N 1, p. 127-134.

67. Le Lanne G#, Le Goff H. Verification and evaluation of communication protocols. Computer Networks, 1978,v.2, N2, p. 5069.

68. Lehman M.M. Programms, life cycles, and laws of software evaluation. Proc of the IEEE, 1980, v.68, N9, p.1060-1076.

69. Masunaga Y. A probabilistic automation model of the NRM HDX HDLC procedures. Computer Networks, 1978, v.2, p.442-453.

70. Merlin P., Farber D. Recoverability of communication protocols. IEEE Trans. Commun., 1976, v.24, N9, p.1036-1043.

71. Peters J. Math and simulation tools for testing HDLC protocol options. Data Communication, 1981, N4, p.111-113, 118-126.- 148

72. Price 'ÏÏ. Simulation studies of :an isaritmically controlled stor-and-forward data communication network. Ins Proc IFIP Congress, Lublyana, 1974, p. 151-154»

73. Reference model of open systems interconnection. ISO/TC 97/SC16, 1979, N 227, p.1-180.

74. Reed M.A„, Smetanka T.D. Implication of a selective acknow-legbment scheme on satellite performance. IBM J.Res.Devel., 1979, v. 23, N 2, p. 189-196.

75. Schneider G. VANS-A resource sharing computer networks design tools. In: Computer Network and Simulation. Ed.S.Scho-maker. 1978, p. 227-248.

76. Shoch J., Hupp J. Measured performance of ETHERNET local network. XEROX PARC, 1980, N 2, p. 22.

77. Schultz G.D» et al. Exacutable description and validation of SNA. IEEE Trans. Commun., 1980, v. 28, N 4, p.661-677.103» Schwartz M., Stern T. Routing techniques used in computer communication networks. IEEE Trans. Commun., 1980, v.28, N4, p. 539-552.

78. Schuetman H.D. Hibrid simulation models of computer systems.v- Commun, ACM, 1978, v.21, N 9, p. 718-723.

79. Sunshine C., Dalai Y. Connection management in transfer protocols. Computer Networks, 1978, v.2, N 6, p.454-473.

80. Towsley D., Wolf J.K. On the statistical analysis of queue and waiting times for statistical multiplexes with ARQ retransmission schemes. IEEE Trans. Commun., 1979* v. 27, N4, p. 693-702.

81. Traynham K.C., Steen R.F. SDLC and BSC on satellite links:

82. A performance comparision. Comput. Commun. Rev., 1977, v.7, N 10, p.3-14.108. ïi/ang J. Delay and throughput analysis for computer communicavtion with balanced HDLC procedures,» IEEE Trans. Computer, 1982, v.31, N 8, p.739-746.

83. Wecker S„ DNA:The Digital Network Architecture. IEEE Trans. Commun., 1980, v. 28, N 4, p. 510-526.

84. West C.H,>, Zafiropulo P. Automated validation of a communication protocol. The CCITT X.21 recommendations. IBM J.Res. Develop., 1978, v. 22, N 1, p. 60-71.

85. Uolffinger B. Models for computer aided simulation of communication flows in computer networks. - Preprint N 3086, Univ. Karlsruhe, 1980, p. 1-73.

86. Wood D. Measurement of user traffic characteristics on ARPANET. In: Proc. 4-th Data Commun. Symp., Quebec, Canada, 1975, p. 92-98.

87. Yeh R.T., Zave P. Specifing software requirements* Pros of the IEEE, 1980, v. 68, N 9, p. 1077-1085.

88. Yu L»7/., Majithia J.C. An analysis of aon direction of window mechanism. IEEE Trans. Commun, 1979, v.27, N 5, p.778-788.

89. Zafiropulo P. et al. Towards analizing and Binthesizing protocols. IEEE Trans. Commun., 1980, v.28, N 4, p.651-661.