zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Mathematical modeling in networks. Факультативный курс

Mathematical modeling in networks

Лектор: аспирант Д.А. Немировский

Goals and purposes learning of the subject

The goal of the course «Mathematical modeling in networks» is to introduce students into mathematical modeling problem giving them ideas of math tools like Probability theory and Mathematical statistics, Queue theory, Group theory, Graph theory, Game theory, Information theory, Algebra and providing concrete examples where the tool are used in modern applied mathematics. The area of application is restricted to networks: World Wide Web (PageRank), Wire Networks (TCP), Wireless Networks (CDMA, Ad hoc and MANET), and Peer-to-Peer networks (P2P data storage and P2P file sharing).

Content of the course

1. Introduction into mathematical modeling and networks.
2. World Wide Web.
2.1. Web as a graph
Ergodic structure of the Web, Bow-tie structure. Markov model of the Web, Random surfer model (Markov chains). PageRank as stationary distribution of the Markov chain.
2.2. Solution methods for solving the PageRank problem
Power iteration method and its rate of convergence (Algebra). Aggregation-disaggregation methods. Method MonteCarlo for PageRank calculation (Mathematical Statistics).
2.3. Properties and applications of PageRank.
Sensitivity and stability of PageRank. Updating PageRank. Choice of damping factor for PageRank. Personalized PageRank. Spam detection using PageRank. PageRank of evolutionary networks (Probability theory).
2.4. Quasi-stationary distributions as an alternative to PageRank (Perturbation theory).
3. Wire networks.
3.1. Introduction.
Performance of wire networks (bandwidth, throughput, rate, delay).
3.2. Protocol TCP.
Open system interconnection model OSI. Protocol TCP/IP in OSI. Versions of TCP: TCP Reno, TCP New Reno, TCP Westwood, TCP Westwood+, TCP Vegas. Round Trip Time. Modeling of Performance of TCP. Interaction of different TCP versions in a network.
4. Wireless networks.
4.1. Ad Hoc networks.
Managed and Ad Hoc regime of acting of Wi-Fi network cards.
Coverage, Connectivity and Capacity in Wireless networks (Probability theory, distributions).
Protocols for Ad hoc communication: two-hop routing protocol, epidemic routing protocol (Markov chains).
Mobile Ad hoc Networks (MANET). One-dimensional mobility models: Brownian Motion (Continuous time, Continuous state space Markov process), Random Walker (Discrete time, Finite state space Markov chain). Two-dimensional mobility models: Random Waypoint Mobility model, Random Direction Mobility model, Random Walker Mobility model. Spatial nodes distribution for mobility models. First meeting times. Message Delay.
4.2. CDMA Systems.
Energy consumptions and power allocation mechanism. Centralized and distributed power allocation mechanisms. Games theory for CDMA Systems.
4.3. Sensor networks.
Wireless Sensor Networks. Equilibrium in Wireless Sensor Networks (Game theory).
5. Peer-to-Peer networks
5.1. P2P data storage systems.
Centralized and distributed data storage approaches. Replication and Erasure code (Group theory). Documents lifetime and required redundancy (Markov chains).
5.2. P2P file sharing systems.
BitTorrent, eDonkey, Kaasa, Gnutella. Tit-for-Tat strategies (Game theory).

Математическое моделирование в сетях

(факультативный курс на английском языке)

Цель и задачи изучения дисциплины

Целью дисциплины "Математическое моделирование в сетях" является дать студентам представление о математическом аппарате, таком как теория вероятности и математическая статистика, теория массового обслуживания, теория групп, теория графов, теория игр, теория информации и высшая алгебра, в приложении к реальным задачам математического моделирования, возникающих в сетях различных видов, таких как Всемирная Путина (PageRank), проводные сети (протокол TCP), беспроводные сети (CDMA, Ad hoc и MANET), пиринговые сети (распределенные хранение и доступ к данным).

Место дисциплины в профессиональной подготовке выпускника

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

Требования к уровню освоения материала дисциплины

Содержание дисциплины

1. Введение в математическое моделирование и сети.
2. Всемирная паутина Web
2.1. Web в виде графа.
Эргодическая структура Web. Представление Web в виде "Bow-tie structure". Модель цепи Маркова для Web, модель случайного пользователя Web (цепи Маркова). PageRank как стационарное распределение цепи Маркова.
2.2. Методы нахождения PageRank.
Метод простых итераций и его скорость сходимости (Высшая алгебра). Методы агрегации-дисагрегации нахождения PageRank. Метод Монте-Карло нахождения PageRank (Математическая статистика).
2.3. Свойства и приложения PageRank.
Чувствительность и стабильность PageRank. Обновление PageRank. Проблема выбора фактора затухания для PageRank. Персонализированный PageRank. Выявление спама с помощью PageRank. PageRank эволюционирующей сети (Теория вероятности).
2.4. Квази-стационарные распределения как альтернатива PageRank (Теория возмущений).
3. Проводные сети.
3.1. Введение
Производительность в проводных сетях (ширина канала, скорость передачи дынных, задержки в передачи данных).
3.2. Протокол TCP.
Модель сетевого взаимодействия OSI. Протокол TCP/IP и его место в модели OSI. Версии протокола TCP: TCP Reno, TCP New Reno, TCP Westwood, TCP Westwood+, TCP Vegas. Время возврата пакета. Теория контроля переполнения буферов (Теория массового обслуживания). Модели производительности протокола TCP. Взаимодействие различных версий протокола TCP в одной сети.
4. Беспроводные сети.
4.1. Ad hoc сети.
Managed and Ad Hoc режимы работы сетевой карты Wi-Fi. Покрытие, связанность и емкость в беспроводных сетях (Теория вероятности). Протоколы ad hoc взаимодействия: two-hop протокол, эпидемический протокол (цепи Маркова).
Мобильные сети ad hoc (MANET). Модели движения узлов в одномерном пространстве: Броуновское движение (Марковский процесс), случайные передвижения (цепи Маркова). Модели движения узлов в двумерном пространстве: выбор случайной точки, выбор случайного направления, случайное движение в клеточной структуре. Распределение узлов в пространстве при различных моделях движения. Среднее время первой встречи узлов. Средняя задержка в передачи сообщений.
4.2. Системы CDMA.
Управление потреблением энергии и силой сигнала. Централизированный и распределенный механизмы управления силой сигнала. Теория игр для распределенного механизма управления силой сигнала.
4.3. Сенсорные сети.
Беспроводные сенсорные сети. Равновесие в беспроводных сенсорных сетях.
5. Одноранговые сети.
5.1. Одноранговые системы хранения данных.
Централизированные и распределенные системы хранения данных. Репликации и безошибочный код для хранения данных (теория групп). Среднее время жизни документов и требуемый уровень избыточности (цепи Маркова).
5.2. Одноранговые системы обмена файлами.
BitTorrent, eDonkey, Kaasa, Gnutella. Стратегия зуб-за-зуб (теория игр).

ВОПРОСЫ К ДИФФЕРЕНЦИРОВЫННОМУ ЗАЧЕТУ

  1. Понятие математическое моделирование. Понятие сети.
  2. Всемирная паутина Web. Web в виде графа. Эргодическая структура Web. Представление Web в виде "Bow-tie structure".
  3. Модель цепи Маркова для Web, модель случайного пользователя Web (цепи Маркова). PageRank как стационарное распределение цепи Маркова.
  4. Метод простых итераций и его скорость сходимости (Высшая алгебра).
  5. Методы агрегации-дисагрегации нахождения PageRank.
  6. Метод Монте-Карло нахождения PageRank (Математическая статистика).
  7. Чувствительность и стабильность PageRank. Обновление PageRank.
  8. Проблема выбора фактора затухания для PageRank.
  9. Персонализированный PageRank. Выявление спама с помощью PageRank.
  10. PageRank эволюционирующей сети (Теория вероятности).
  11. Квази-стационарные распределения как альтернатива PageRank (Теория возмущений).
  12. Проводные сети. Производительность в проводных сетях (ширина канала, скорость передачи дынных, задержки в передачи данных).
  13. Модель сетевого взаимодействия OSI. Протокол TCP/IP и его место в модели OSI. Версии протокола TCP: TCP Reno, TCP New Reno, TCP Westwood, TCP Westwood+, TCP Vegas. Время возврата пакета.
  14. Теория контроля переполнения буферов (Теория массового обслуживания). Модели производительности протокола TCP.
  15. Взаимодействие различных версий протокола TCP в одной сети.
  16. Ad hoc сети. Managed and Ad Hoc режимы работы сетевой карты Wi-Fi. Покрытие, связанность и емкость в беспроводных сетях (Теория вероятности).
  17. Протоколы ad hoc взаимодействия: two-hop протокол, эпидемический протокол (цепи Маркова).
  18. Мобильные сети ad hoc (MANET). Модели движения узлов в одномерном пространстве: Броуновское движение (Марковский процесс), случайные передвижения (цепи Маркова).
  19. Модели движения узлов в двумерном пространстве: выбор случайной точки, выбор случайного направления, случайное движение в клеточной структуре. Распределение узлов в пространстве при различных моделях движения.
  20. Среднее время первой встречи узлов. Средняя задержка в передачи сообщений.
  21. Системы CDMA. Управление потреблением энергии и силой сигнала. Централизированный и распределенный механизмы управления силой сигнала. Теория игр для распределенного механизма управления силой сигнала.
  22. Сенсорные сети. Беспроводные сенсорные сети. Равновесие в беспроводных сенсорных сетях.
  23. Одноранговые системы хранения данных. Централизированные и распределенные системы хранения данных. Репликации и безошибочный код для хранения данных (теория групп).
  24. Среднее время жизни документов и требуемый уровень избыточности (цепи Маркова).
  25. Одноранговые системы обмена файлами. BitTorrent, eDonkey, Kaasa, Gnutella. Стратегия зуб-за-зуб (теория игр).