Алгоритмы для сетевых приложений

Алгоритмы для сетевых приложений

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

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

И дальше начинается фактически неограниченный пул задач: на свете много разных архитектур буферов, у пакетов может быть много разных характеристик (размер, требуемая работа, ценность и т.п.) Основной теоретический инструмент -- конкурентный анализ: чтобы доказать верхнюю оценку A на конкурентность, нужно доказать, что наш онлайн-алгоритм работает не более чем в A раз хуже оптимального алгоритма, который знает последовательность входов заранее.

Но это ещё не всё. Есть масса других интересных задач, связанных с алгоритмами в сетях передачи данных:

  • эффективное представление сетевых классификаторов: routing-таблицы в роутерах представляют собой набор правил для классификации пакетов, которые по булевскому представлению заголовка пакета определяют, что с ним делать; как максимально сжать представление этих правил, как выразить классификатор наиболее эффективно (это особенно актуально, учитывая, что мир постепенно переходит на IPv6)?
  • эффективное представление счётчиков: когда пакеты идут через сеть, их часто нужно по дороге подсчитывать; как, заняв как можно меньше места, как можно быстрее подсчитать проходящие через сетевые элементы (то есть свитчи и роутеры) пакеты?
  • оптимизация графов сети: можно ли представить сеть, по которой движутся пакеты, в виде более простого графа с сохранением свойств, важных для маршрутизации?
  • и многие, многие другие...

 

Сотрудники кафедры: 

С.И.Николенко, А.П.Давыдов

 

Публикации сотрудников кафедры

  1. K. Kogan, S.I. Nikolenko, O. Rottenstreich, W. Culhane, P. Eugster. Exploiting Order Independence for Scalable and Expressive Packet Classification. IEEE Transactions on Networking, vol. 24, no. 2, 2016, pp. 1251–1264
  2. P. Eugster, K. Kogan, S.I. Nikolenko, A.V. Sirotkin. Heterogeneous Packet Processing in Shared Memory Buffers. Published online ahead of print, Journal of Parallel and Distributed Computing, 2016
  3. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin. Online Scheduling FIFO Policies with Admission and Push-Out. Theory of Computing Systems, vol. 58, no. 2, 2016, pp. 322-344
  4. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, G. Scalosub, M. Segal. Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors. Journal of Network and Computer Applications, vol. 74, 2016, pp. 31–43
  5. P. Chuprikov, S.I. Nikolenko, K. Kogan. On Demand Elastic Capacity Planning for Service Auto-scaling. 2016 IEEE International Conference on Computer Communications (INFOCOM 2016), 2016, pp. 1–9
  6. K. Kogan, D. Menikkumbura, G. Petri, Y. Noh, S.I. Nikolenko, P. Eugster. BASEL (Buffering Architecture SpEcification Language). 12th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2016), 2016, pp. 69–74
  7. K. Kogan, S.I. Nikolenko, P. Eugster, A. Shalimov, O. Rottenstreich. FIB Efficiency in Distributed Platforms. Accepted to 24th IEEE International Conference on Network Protocols (ICNP 2016), 2016.
  8. S.I. Nikolenko, K. Kogan, G. Retvari, E.R. Berczi-Kovacs, A. Shalimov. How to Represent IPv6 Forwarding Tables on IPv4 or MPLS Dataplanes. Proc. 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS): GI 2016: 9th IEEE Global Internet Symposium (IEEE GI 2016), 2016
  9. P. Chuprikov, S.I. Nikolenko, K. Kogan. Priority Queueing with Multiple Packet Characteristics. 2015 IEEE International Conference on Computer Communications (INFOCOM 2015), 2015, pp. 1418–1426
  10. P. Eugster, A. Kesselman, K. Kogan, S.I. Nikolenko, A.V. Sirotkin. Essential Traffic Parameters for Shared Memory Switch Performance. 22nd International Colloquium on Structural Information and Communication Complexity ( SIROCCO 2015), Lecture Notes in Computer Science, vol. 9439, Springer, 2015, pp. 61–75
  11. K. Kogan, S.I. Nikolenko, O. Rottenstreich, W. Culhane, P. Eugster. SAX-PAC (Scalable And eXpressive PAcket Classification). Proceedings of the 2014 ACM conference on SIGCOMM (SIGCOMM 2014), ACM Press, 2014, pp. 15–26
  12. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, G. Scalosub. Balancing Work and Size with Bounded Buffers. Proc. 6th International Conference on Communication Systems and Networks (COMSNETS 2014), IEEE Press, 2014, pp. 1–8
  13. S.I. Nikolenko, K. Kogan. Single and Multiple Buffer Processing. Encyclopaedia of Algorithms, Springer, 2014, pp. 1–9
  14. P. Eugster, K. Kogan, S.I. Nikolenko, A.V. Sirotkin. Shared-Memory Buffer Management for Heterogeneous Packet Processing. Proceedings of the 34th International Conference on Distributed Computing Systems (ICDCS 2014), IEEE Press, 2014, pp. 471–480
  15. K. Kogan, S.I. Nikolenko, P. Eugster, E. Ruan. Strategies for Mitigating TCAM Space Bottlenecks. 22nd IEEE Annual Symposium on High-Performance Interconnects ( HOTI 2014), IEEE, 2014, pp. 25–32
  16. K. Kogan, S.I. Nikolenko, S. Keshav, A. Lòpez-Ortiz. Efficient Demand Assignment in Multi-Connected Microgrids with a Shared Central Grid. Proc. 3rd IFIP Conference on Sustainable Internet and ICT for Sustainability 2013 (SustainIT 2013), 2013
  17. K. Kogan, S.I. Nikolenko, W. Culhane, P. Eugster, E. Ruan. Towards efficient implementation of packet classifiers in SDN/OpenFlow. Proc. 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking ( HotSDN 2013), 2013, pp. 153–154
  18. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin. Multi-Queued Network Processors for Packets with Heterogeneous Processing Requirements. Proc. 5th International Conference on Communication Systems and Networks (COMSNETS 2013), IEEE Press, 2013, pp. 1–8
  19. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin. A Taxonomy of Semi-FIFO Policies. Proc. 31st IEEE International Performance Computing and Communications Conference (IPCCC 2012), IEEE Press, 2012, pp. 295–304
  20. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin, D. Tugaryov. FIFO Queueing Policies for Packets with Heterogeneous Processing. Proc. 1st Mediterranean Conference on Algorithms (MedAlg 2012), Lecture Notes in Computer Science, vol. 7659, Springer, 2012, pp. 248–260

Квалификационные работы

  1. П. С. Чуприков. Оценки пропускной способности алгоритмов управления буфером сетевого процессора в модели с несколькими характеристиками пакетов. Магистерская диссертация, СПбАУ РАН, 2015.