В Лаборатории можно выделить три группы исследователей: 1) Полесский В. П., Рубинов А. Р., Кузнецов А. В.; 2) Лиханов Н. Б., Введенская Н. Д., Цыбаков Б. С., Михайлов В. А.; 3) Левшин И. П., Орлов И. А., а также Полякова В. Г. - исследователя, работающего самостоятельно.
Для решения актуальных проблем теории современных коммуникационных сетей группа 1 разрабатывает, в основном, методы дискретной математики, а группы 2 и 3 - вероятностные методы.
Показано, что в случае высоконадежных узлов и линий хорошие метрические свойства топологии не гарантируют ее высокую структурную надежность из-за возможности наличия большого числа 2-разрезов (двух линий, одновременный отказ которых делает сеть не связной). Найдена взаимосвязь метрических характеристик и характеристик надежности топологии. В классе 2-связных 2-лесистых графов с заданным числом вершин и ребер найден граф, имеющий максимальное число 2-разрезов - надежная 2-лесистая топология. Доказано, что в классе Z(n,m) случайный граф с минимальной для любой надежности ребра вероятностью связности существует всего лишь для трех случаев: m=n, m=n+1, m=2(n-1). (В. П. Полесский)
Разработаны и исследованы несколько новых эффективно вычислимых мер сходства последовательностей, основанных на вложении коротких последовательностей. Эти меры могут применяться для анализа генных последовательностей и белков. Часть таких мер применима также для сравнения древовидных структур и декомпозиции графов. (А. Р. Рубинов)
Продолжены работы в области теории кодирования и её приложений в системах оптической и магнитной записи. В основном, это построение и исследование итеративных систем декодирования для каналов магнитной записи ("hard disk drives") с использованием низкоплотностных кодов. Для построения низкоплотностных кодов с регулярной структурой использовались различные конструкции, описанные в литературе по комбинаторике. Получены следующие основные результаты: построен широкий класса низкоплотностных кодов из систем Штайнера и целочисленных решеток; исследованы вероятности ошибок в различных каналах магнитной записи, использующих предложенные коды и итеративный алгоритм с мягкими решениями для их декодирования. Отличительной особенностью предложенных систем является наличие двух декодеров с мягкими решениями, один из которых оперирует на решетке канала с частичным откликом, а другой осуществляет декодирование низкоплотностного кода. Обмен мягкими решениями между этими двумя декодерами ведет к рекордно низким вероятностям ошибок, а структурные свойства кода позволяют рассчитывать, что данный подход может быть реализован практически в следующем поколении "hard disk drives". По результатам работ опубликована одна статья и подана заявка на два патента США. (А. В. Кузнецов)
Для сети передачи данных произвольной конфигурации и потоками типа включен\выключен разработан подход, который для случая, если потоки не образуют взаимных петель, позволяет оценивать вероятность потерь пакетов и вероятность переполнения буфера для любого заданного узла сети. Данный результат является существенным обобщением результатов, полученных ранее для случая отдельно рассматриваемого узла связи. Полученные аналитические результаты дают возможность производить необходимые расчеты нагрузок малыми затратами вычислительных ресурсов, а также являются полезными для качественного анализа рассматриваемых систем. (Н. Б. Лиханов)
Продолжены исследования больших систем массового обслуживания. Проведено асимптотическое исследование большой открытой сети Джексона в случае постоянного времени обслуживания заявок. Задача привела к исследованию новых и нетривиальных дифференциальных уравнений в частных производных с нелокальными коэффициентами и запаздыванием. Была исследована задача о больших уклонениях задержки в системе с двумя приборами и тремя потоками - два из них - первый и второй - направлены на первый и второй сервер, соответственно, а в третьем потоке сообщение направляется туда, где задержка этого сообщения будет меньшей. Выведены формулы для вероятности большого уклонения задержки виртуального сообщения из третьего потока. (Н. Д. Введенская)
Рассмотрен множественный доступ подвижных пользователей в радиоканал общего пользования к базовой станции. Канал является дискретным по времени и имеет двоичную обратную связь типа пустое/не пустое окно ко всем пользователям, требующим доступа. Дан обзор известных алгоритмов множественного доступа для такого канала и показано, почему эти алгоритмы не годятся для внедрения. Построены два новых алгоритма, не имеющие недостатков, свойственных алгоритмам, известным ранее. Новые алгоритмы являются стабильными в отличие от алгоритма ALOHA. Пропускная способность первого из этих алгоритмов ограничена сверху величиной 0.256 пакетов на окно. Второй алгоритм - более мощный, чем первый, и он может работать в канале с захватами и множественным приемом. Он имеет пропускную способность 0.2891 пакетов/окно при тех же условиях, что и первый алгоритм. Показано, как захваты и множественный прием каналов с замираниями могут увеличить его пропускную способность до 0.6548 пакетов/окно и снизить задержку пакетов. Для двух моделей каналов с замираниями найдены средняя задержка пакетов и дисперсия. Эти модели - Рэлеевские замирания с некогерентным и когерентным приемом. Все результаты получены для случая пуассоновского входного трафика. Автором разработок в 2003 году получено 2 патента США. (Б. С. Цыбаков)
Подготовлен обзор существующих методов маршрутизации, узлов коммутации и архитектуры сетей. Исследована зависимость способа маршрутизации от категории обслуживания и параметров трафика. Предложен новый способ маршрутизации для соединений с постоянной битовой скоростью в B-ISDN сетях. (В. А. Михайлов)
Разработана методика применения информационной технологии имитационного моделирования, созданной и развиваемой в ИППИ РАН, в задачах автоматизированного прогноза качества каналов передачи информации со случайными параметрами (КССП) между подвижными морскими объектами. В методике используется системный подход при построении математических и имитационных моделей сложных физических сред, когда они служат каналом передачи информации, а также моделей отдельных компонентов и их совокупности, составляющих информационную систему. Задействуются существующие и вновь создаваемые Банки геофизических и гидрологических параметров, применяемых в моделях. В задачах прогноза эффективности составных радио- и гидроакустических КССП морской связи (берег - космос - поверхность - глубина) определяются специфические критерии качества канала, позволяющие осуществлять прогноз условий работы системы связи для оперативного планирования способов и режимов передачи информации в различных акваториях Мирового океана и различной сигнально-помеховой обстановке. Рассмотрены различные критерии оценки эффективности канала, отличающиеся степенью сложности и достоверности от простейшего, такого как отношение сигнал/шум, до наиболее информативного, такого как пропускная способность. С целью исследования физических свойств открытой в 1991 г. квазичастицы солитонного типа, названной акустоном, и так называемого 'акустонного газа', способного оказывать заметное влияние на условия подводного распространения акустических сигналов, разработана имитационная компьютерная модель генерации акустонов. Модель позволяет исследовать особенности физического механизма образования акустона при различных характеристиках подводных течений и рельефа морского дна. Разработано алгоритмическое и программное обеспечение имитационного моделирования систем гидроакустической связи с многочастотной манипуляцией информационных сигналов и шумоподобными сигналами. Разработанные алгоритмические и программные средства являются составной частью математического обеспечения программно-аппаратного комплекса, предназначенного для реализации элементов системы автоматизированного прогноза качества КССП между подвижными морскими объектами. (И. П. Левшин и И. А. Орлов)
На основе технологии автоматизированной анимации разработан прототип профессионального инструмента для создания мультфильмов. Новая система интерактивных средств создания, графического редактирования и структурного контроля ключевых кадров позволяет эффективно использовать автоматическое восполнение фильма промежуточными кадрами для повышения качества мультфильмов и значительного удешевления их производства. (В. Г. Поляков)