ЛАБОРАТОРИЯ № 10

Лаборатория теории коммуникационных сетей

И.о.заведующего лабораторией – д.ф.-м.н. Рыков Владимир Васильевич

Тел.: (095) 299-50-02; E-mail: vladimir_rykov@mail.ru

 

Ведущие ученые лаборатории:

 

 

Направления исследований:

 

·        теория надежности сетей связи;

·        управляемые системы;

·        анализ структуры потоков информации в сетях связи;

·                 сети связи с множественным доступом пакетов и виртуальным соединением;

·        кодирование и обработка сигналов в системах памяти;

·        имитационные модели гидроакустических систем передачи информации;

 

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

 

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

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

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

Установлена связь между нестационарными пуассоноскими потоками (НПП) и введенными ранее распределениями с почти отсутствующей памятью (ПОП-распределениями). Такая взаимосвязь не только дает новые знания о поведении НПП, но и позволяет эффективно использовать ее при статистическом анализе таких потоков. Поскольку для потоков информации, поступающей и обрабатываемой в телекоммуникационных и компьютерных сетях, характерно наличие существенной неоднородности, полученные результаты имеют большое значение при моделировании и анализе загрузки телекоммуникационных и компьютерных сетей. Для реального статистического анализа ПОП-распределений разработаны вычислительные процедуры и компьютерные средства. Результаты докладывались на международных конференциях. (В. В. Рыков)

Исследована возможность использования алгоритмов кратчайших путей при маршрутизации в широкополосных сетях интегрального обслуживания. Исследовалась чувствительность рассматриваемых алгоритмов к изменению параметров входного трафика. Было установлено, что при некоторых топологиях сети возможны «колебания», при которых итоговая маршрутизация оказывается далеко не оптимальной. Были предложены методы устранения подобных нежелательных явлений. Исследовались также основные характеристики алгоритмов кратчайших путей: быстродействие, сложность и т.п. (В. А. Михайлов)

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

Продолжено изучение больших систем обслуживания с динамической маршрутизацией. Подготовлена к печати работа, в которой рассматривается система с большим числом выходящими время от времени из строя серверами. Показано, что если заявка случайно выбирает два сервера и направляется в наименее загруженный из них, то вероятности больших очередей на серверах убывают сверхэкспоненциально. Но при этом среднее число загруженных неработающих серверов оказывается в такой системе больше, чем в системе, где заявка выбирает сервер случайно. Рассмотрена марковская модель системы с большим числом источников, посылающих пакетированную информацию на единственный сервер с буфером большого объема. В системе используется протокол TCP. Выведены уравнения, которыми описываются распределение длин сообщений и распределение свободной части буфера. С помощью методов теории больших уклонений рассмотрена вероятность больших задержек в системе обслуживания с двумя серверами и тремя пуассоновскими потоками заявок с распределением длительностей обслуживания общего вида. Заявки из первого и второго потоков направляются на первый и второй сервер, а заявка из третьего потока направляется на сервер, наименее загруженный в момент ее появления. Приведены явные формулы для главного члена в логарифме вероятности большой задержки виртуальной заявки, помещенной в третий поток. Моделирование системы показало, что эти формулы дают и хорошее приближение для логарифма вероятности небольших задержек. (Н. Д.Введенская)

Проведено исследование присвоения пользователям радиосети связи ортогональных Уолш-кодов переменной длины. Рассмотрены также присвоения, при которых все пользователи разбиваются на несколько групп. Каждая группа может использовать ее собственные коды, которые различны для различных групп. Каждый пользователь имеет несколько присвоенных ему кодов. Определена матрица М, зависящая от числа пользователей в группе n, числа Уолш-кодов k в группе и числа Уолш-кодов L, приписанных каждому пользователю группы. Дано определение свойства присвоения, построена матрица М, которая обладает свойством присвоения. Доказано необходимое условие существования матрицы М со свойством присвоения. Даны две конструкции таких матриц. Конструкции являются оптимальными в том смысле, что они дают минимум L при заданных n и k. Найдена сложность предложенного оптимального присвоения (Б. С. Цыбаков)

Хотя итеративные методы приема и декодирования сигналов давно привлекают внимание специалистов в области обработки сигналов, работающих в компаниях по производству жестких дисков памяти, но до последнего времени применение таких технологий было крайне ограниченным. Завершен проект, в котором проанализированы различные принципы построения итеративных каналов приема и обработки сигналов для жестких дисков памяти, а также проведено их сравнение со стандартными методами, используемыми в настоящее время в промышленности. Подробные результаты этого проекта опубликованы. В 2004 году издательство CRC Press выпустило книгу, в которой глава о применении комбинаторных конструкций для построения низкоплотностных кодов и их применении в жестких дисках памяти написана с участием А. В. Кузнецова. Получен патент США на использование таких конструкций в системах памяти и каналах связи. (А. В. Кузнецов)

Передача информации в океанической среде посредством акустических сигналов испытывает ряд трудностей и ограничений, обусловленных сложностью и многообразием физических процессов, сопровождающих распространение акустических волн в морской среде. Неоднородность структуры океана и случайный характер его параметров (температура, давление, соленость, волнение поверхности и др.) затрудняют разработку и эксплуатацию эффективных и помехоустойчивых гидроакустических систем передачи информации (ГАКПИ). Особую важность вследствие указанных причин приобретает возможность оценки пропускной способности ГАКПИ (С).

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

 

работа с научной молодежью

 

В. В. Рыков – профессор кафедры прикладной математики и компьютерного моделирования РГУ нефти и газа им. И. М. Губкина. Руководит 3 аспирантами и 3 дипломниками. В 2004 г. подготовлена 1 диссертация на соискание ученой степени кандидата физико-математических наук, издано учебное пособие для Вуза. В. А. Михайлов – доцент кафедры МФТИ, Н. Б. Лиханов также доцент кафедры МФТИ, руководит 4 аспирантами и 3 дипломниками.

 

ГРАНТЫ:

 

·        Российский фонд фундаментальных исследований (№ 02-01-00068): "Асимптотический анализ взаимодействующих многокомпонентных случайных систем". Руководитель Н. Д. Введенская.

·        Российский фонд фундаментальных исследований (№ 04-07-901156):

"Разработка методов и программных средств исследования потоков информации в телекоммуникационных сетях на основе регенеративного подхода". Участник В. В. Рыков.

·        Российский фонд фундаментальных исследований (№04-01-10549-з): "Международная конференция по математическим методам теории надежности (MMR -2004)". Участник В.В.Рыков.

 

ПУБЛИКАЦИИ в 2004 г.

 

Книги, монографии, учебники

       1.         Рыков В.В. Надежность технических систем и техногенный риск. М.: РГУ нефти и газа им. И. М. Губкина, 2004.

       2.         Vasic B., Kurtas E., Kuznetsov A. V., Milenkovic O. Structured Low-Density Parity-Check Codes. Chapter in the book Signal Processing and Coding For Recording Systems. Еds. B. Vasic, E. Kurtas. CRC Press, 2004.

 

Опубликованные статьи

       1.         Ефросинин Д.В. Управляемые системы массового обслуживания с неоднородными приборами. Диссертация на соискание ученой степени к.ф.-м.н. РУДН, 2004.

       2.         Левшин И.П. Параллельный алгоритм решения системы дифференциальных уравнений 2-го порядка в задачах определения траекторий лучей при подводном распространении звука. Труды II Международной конференции Параллельные вычисления и задачи управления. М: ИПУ РАН, PACO’2004, 4-6 октября 2004 г., стр. 101-109.

       3.         Левшин И.П. Пропускная способность гидроакустического канала передачи информации. Труды VII Международной конференции Прикладные технологии гидроакустики и гидрофизики. C-Петербург: Морфизприбор, 8-10 июня 2004 г., стр. 337-341.

       4.         Петрунин В.И., Полесский В.П. 2-связанный 2 лесистый граф с заданным числом вершин и ребер с минимальным числом остовов. Информационные процессы, 2004, том 4, № 4, стр. 275-283.

       5.         Петрунин В.И., Полесский В.П. 2-связанный 2-лесистый граф с заданным числом вершин и ребер с максимальным числом 2-разрезов. Информационные процессы, 2004, том 4, № 4, стр. 261-268.

       6.         Рубинов А.Р. Методы прогноза пассажиропотоков. Железнодорожный транспорт, 2004, № 1, стр. 50-56.

       7.         Dimitrov B., Green D., Rykov V., Stanchev P. Reliability Model for Biological Objects. Longevity, Aging and Degradation Models. Transactions of the First Russian-French Conference LAD-2004. Saint Petersburg , June 7-9, 2004, Ed. V. Antonov, C. Huber, M. Nikulin, V. Polischook, Saint Petersburg State Politechnical University, SPB, 2004, vol. 2, pp. 230-240.

       8.         Dimitrov B., Krougly Z., Rykov V. Periodic Poisson Processes and Almost-luck of memory Diostrivbutions. Autom. And Remote Control, 2004, vol. 65, no. 10, pp. 1597-1610.

       9.         Lynch R., Kurtas E.M., Kuznetsov A.V., Yeo E., Nikolić B. The Search for a Practical Iterative Detector for Magnetic Recording. IEEE Trans. on Magnetics, 2004, vol. 40, No. 1.

    10.       Ozturk O., Mazumdar R., Likhanov N. Many sources asymptotics for networks with small buffers. Queueing Systems, 2004, 46, pp. 129-147.

    11.       Rykov V., Buldaeva E. On reliability control of fault tolerance units: regenerative approach. Transactions of XXIV International Siminar on Stability Problems for Stochastic Modes, September 10-17, 2004, Jurmala, Latvia. Transport and Telecommunication Institute, Riga, Latvia, 2004.

    12.       Rykov V., Efrosinin D. Optimal Control of Queueing Systems with Heterogeneous Servers. Queueing Systems: Theory and Applications, 2004, vol. 46, pp. 389-407.

    13.       Rykov V., Efrosinin D. Reliability Control of Biological Systems with failures. Longevity, Aging and Degradation Models. Transactions of the First Russian-French Conference LAD-2004. Saint Petersburg, June 7-9, 2004, Ed. V. Antonov, C. Huber, M. Nikulin, V. Polischook, Saint Petersburg State Politechnical University, SPB, 2004. vol. 2, pp. 241-255.

    14.       Tsybakov B. On Walsh code assignment. IEEE Transactions on Information Theory, 2004, vol. 50, no. 6, pp.1073-1078.

    15.       Vvedenskay N.D., Duffy K., Malone D., Pechersky E.A., Syhov Y.M. Large deviation provide good approximation to queueing system with dynamic routing. Preprint. Dublin Institute for Advanced Studies, 2004, DIAS-STP-04-15.

    16.       Vvedenskaya N.D., Pechersky E.A., Syhov Y.M. Large deviation in two-server system with dynamic routing. Preprint. Network Institute for Math. Sci., Cambridge, UK, 2004, no. I 03075-IGS.

 

Статьи, принятые к публикации

       1.         Rubinov A.R. Diversity of synthetically accessible compounds. Journal of Computer-Aided Molecular Design.

 

Тезисы докладов

       1.         Vvedenskaya N.D., Pechersky E.A., Syhov Y.M. Large devilation in two- server system with dynamic routing. IEEE International Symposium on Information Theory. Proceedings, 2004, p. 114.

       2.         Dimitrov B., Green D., Rykov V., Stanchev P. Reliability of complex hierarchical fault tolerance systems. Thesis of the International Conference MMR-2004. Santa Fe (U.S.A.), June 21-25, 2004. Published on CD.

       3.         Петрунин В.И. Эвристика выбора минимальных путей и минимальных разрезов для оценок двухполосной надежности. Тезисы докладов V Международного семинара "Информационные сети, системы и технологии". Москва, 26-27 октября 2004 г., с.174-178.

       4.         Rykov V., Efrosinin D. Reliability control of fault tolerance units. Thesis of the International Conference MMR-2004. Santa Fe (U.S.A.), June 21-25, 2004. Published on CD.

       5.         Rykov V.V., Stepanov D.V., Lepikhin A.N., Minenko R.A. Decision Support System for Reliability Analysis. Accepted by International Conference on Stochastic Models in Reliability, Safety, Security and Logistics (SMRSSL’05). 16-18 February 2005, Beer Sheva, Israel.

 

Патенты

       1.         Kuznetsov A. V., Kurtas E. M. A method and Decoding Apparatus using Linear Code with Parity Check Matrices Composed from Circulants. United States Patent 6757122, Jan. 29, 2004.