北京交通大学《通信网理论基础》课程，讲解排队论、路由、网络设计的基本原理和算法，一路下来，带大家在动手中，走上网络建模、性能分析、优化设计的职业道路。详细课程信息请访问：https://yishuai.github.io/net
视频合集：B站链接
课本：Dimitri P. Bertsekas and Robert G. Gallager, Data Networks (2nd Edition), Prentice Hall, 1992， 全书下载网站，排队论部分PDF
本节介绍中国骨干网的基本情况，包括传输网和业务网。你会发现自己每天都在用的网络，原来是这样构造的。
互联网发展如此迅猛，彻底改变了人类的生活方式。它的成功，很大程度上来自它基于“自治域”的管理模式。本节介绍这种模式。相信它会给你带来启发。
全世界的自治域连接在一起，形成了互联网。两个自治域互连时，可以是平等的，也可以是“客户-服务商”的关系。本节介绍这些概念，然后介绍最新的测量感知全球自治域关系的算法。
Flash crowd 是直播业务中经常出现的一种用户到达模式，给网络系统带来很大的挑战。本节介绍该模型及其性能分析。
本节介绍负指数分布，特别是它与长尾分布的区别。
负指数分布最神奇的是它的无记忆性。本节告诉你买二手手机的时候，为什么要选择寿命符合负指数分布的手机。
如何模型用户随机到达公园门口的过程？泊松过程。本节介绍泊松过程的定义，很有意思。
泊松过程还可以通过两个连续到达用户的到达时间间隔、极短时间内用户到达概率来描述。这些描述对我们建立排队模型非常有用。
马尔科夫链让我们能很方便地建立起离散状态随机过程的数学模型，特别厉害，
马尔科夫链的平稳状态，让我们可以评估随机过程的稳态概率分布，感知其工作状态，具有很强的实际意义，
基于平衡方程，我们可以快速计算出马尔科夫模型的稳态概率。有两种平衡方程：全局平衡方程和局部平衡方程。本节介绍这些方程。
排队买票如何模型？本节讨论这个问题。
大家争抢着打电话，如何模型？本节讨论这个问题。
缓存越大越好？缓存设计应考虑哪些因素？如何构建缓存性能模型？本节讨论这些问题。
电话网如何模型？性能如何分析？排队论研究的是何种随机过程？本节讨论这些问题。
排队买饭如何模型？这取决于食堂的管理策略。本节讨论这一问题。
本节介绍各种排队模型，讨论不同场合，比如售票大厅、银行，适用的不同的模型。
基于排队模型，我们会发现一个神奇的现象：随着系统负荷的增长，用户平均时延会迅速增长。本节介绍这一现象，并基于一个有趣的仿真工具，形象地说明这是为什么。
本节利用马尔科夫链，建立一个服务员的缓存排队模型，由此获得系统中存在人数的概率分布、用户到达时的等待概率、和平均队长。
利用Kendall表示法，能够方便地描述各种各样的排队模型。本节我们来看看它。
本节利用我们前面学习的马尔科夫排队模型，来解决实际问题，包括：1）分组链路传输的排队模型；2）传真服务排队模型。
我们前面学习的马尔科夫排队模型，可以得到系统中的平均人数。Little定理，能够基于这个平均人数，算出用户在系统中平均呆的时间。这个时间，才是我们排队的时候最关心的，对吧？
基于Little定理，我们现在来分析M/M/1排队模型的平均用户等待时间和停留时间。它们是我们排队的时候最关心的
Little定理有着非常广泛的应用。要发挥它的威力，灵活使用是关键。本节我们介绍它的各种应用，并练习习题
本节介绍多服务器、无限缓存时的排队系统，建立其马尔科夫链模型。基于该模型，我们可以得到一个重要的系统性能指标：用户等待概率。这是我们的好朋友爱尔兰同学在一百年前的研究成果，厉害吧？因此，计算它的公式被命名为爱尔兰C公式。
本节介绍多服务器、无缓存时的排队系统，建立其马尔科夫链模型。这就是通信工程中关于电话网性能的最重要模型：呼叫损失模型。基于该模型，我们可以得到一个重要的系统性能指标：用户阻塞概率。这也是我们的好朋友爱尔兰同学在一百年前的研究成果，因此，计算它的公式被命名为爱尔兰B公式。
本节利用 M/M/m/m 排队模型的分析结果，特别是关于用户阻塞概率的爱尔兰B公式，进行电话网中最重要的中继线数目设计。作为专业人士，我们要熟悉掌握基于表格的系统性能分析和设计方法。
本节分析一种实际中不会出现，但有理论价值的排队系统：系统中的服务器数目无限。用马尔科夫链对其进行分析后，你将发现它与泊松分布隐秘的联系。这个结果实在是太有意思了。
本节我们介绍法国著名的IMT大学的排队论课程配套的Python仿真实验。通过编程的方法把学习的理论进行实验，看到它的真实结果，无疑是令人激动的。课程链接：https://www.edx.org/course/queuing-theory-from-markov-chains-to-multi-server-systems-2
本节我们学习路由的基本概念，比如：我打开手机上的地图软件，搜索回家的路，这就是一个路由问题哦。在我们身边的各种各样的网络中，都存在路由问题。我们将讨论它们的特点。
讨论路由的算法，需要了解一些基本的图论的概念，这样，我们讨论起来就会非常方便。本节介绍图的以下基本概念：路径、环、树
生成树是能够生成网络的一棵树。最小重量生成树，是边权和最小的生成树。它们在网络的设计和通信中很有价值。本节介绍它们的基本概念和获得它的一个基本算法：Prim-Dijkstra 算法
在大数据时代，一个图的节点数可能是海量的，比如：几十亿个。此时，Prim-Dijkstra 算法就会很慢。这时候，我们就可以采用分布式方法。本节介绍最小重量生成树的 Kruskal 算法及其分布式实现，十分适合大数据的场景。
网络中一个节点和其它所有节点的最短路径关系，可描述为一个最短路径生成树。本节介绍这一基本概念。注意它和最小重量生成树的区别哦。
Bellman-Ford 最短路径算法通过不断迭代，可以得到网络中一个节点的最短路径生成树。本节我们介绍它的基本思想、算法描述、收敛条件和计算复杂度。
距离矢量路由算法，是一种基于 Bellman-Ford 的分布式路由算法，在网络中有广泛的应用。本节我们就学习它。
Dijkstra 算法能够让网络中的一个节点找到它的最短路径生成树。基于 Dijkstra 的分布式路由算法，被称为链路状态路由算法。本节我们学习它们。
基于 Dijkstra 的链路状态路由算法，因为需要在网络中广播链路状态信息，所以在网络不稳定时，会出现问题，导致网络故障。本节我们就来看看这些问题，并设计解决方案。
故障发生时，距离矢量路由算法可能会发生计数到无穷问题，导致网络故障。本节我们用两个例子，说明这一问题，然后介绍各种解决办法，如：水平分割，反向毒化
计数到无穷，是路由环路问题中的一种。要更好地解决路由环路问题，我们有”路径矢量“方法。该方法要求节点向邻居发送路由信息的时候，要清楚地告知该路由的完整路径。这样其它节点就可以检查自己是不是在这条路径上，因此避免路由环路的问题。本节首先通过示例说明水平分割、反向毒化等常规方法，不能完全解决路由环路问题，然后介绍路径矢量方法的基本思想及其在BGP中的应用。
自适应路由是根据当前网络状态（如流量），自适应调整路由，以获得最佳网络性能的路由方法。可是，因为根据网络状态调整的路由，反过来又会导致网络状态变化，所以，如果处理不好，很容易出现路由震荡的问题。本节我们先介绍自适应路由的基本概念，然后用示例说明其导致的路由震荡问题，最后介绍现有的解决方法。
互联网由很多自治域（AS）组成，结构非常灵活。其中，AS之间有两种典型的商业关系：对等、用户-提供商。数据包在这些AS之间传递，需要域间路由。本节介绍这些基本概念。
边界网关协议负责AS之间的路由更新。本节介绍BGP的基本设计，并用示例说明其发送路径矢量的过程。
本节首先介绍具体的三种AS之间的商业关系：用户-提供商、对等、兄弟，然后用示例说明其中的道理，以及如何通过配置BGP路由实现它。
VALLEY-FREE方法，可以直观地判断一条AS路径是否合法；而 GAO-REXFORD 准则告诉我们应该如何配置，以确保获得合法AS路径。本节介绍它们。
在实践中，多个AS可能因为竞争的关系，进行 BGP 操纵，以提高自己的收益。本节介绍前缀劫持、AS路径预先计划、网络前缀拆分、AS路径毒化等方法。这些技巧在实际中非常重要。快来看看吧。
本节介绍线性规划，它是我们将要学习的网络设计问题的主要工具。
本节介绍我们将要设计的网络：传送网，包括它的模块化单位、需求矩阵、路径、链路的基本概念。
本节首先介绍网络设计问题的基本概念，然后介绍一种简单、直观的网络设计模型记法。这种记法能直观反映链路-路径经过的节点，因此很容易理解。
本节介绍另一种网络设计模型记法：节点-链路模型。这种记法有固定数目的变量下标，用简单的数据结构就可以实现它。
本节介绍一种更常用的网络设计模型记法：链路-需求-路径标识模型。这种记法非常灵活，功能强大，是我们后面建模使用的记法。请一定掌握。
本节介绍如何建立网络模型，获得最优的网络链路容量。该问题是各种网络优化设计问题的基础，请一定要掌握它。
本节介绍各种网络优化问题：单路径约束；模块化链路容量；给定链路容量，分配网络流量。
本节介绍一个新的问题：如何设置最短路径路由的链路权重，实现我们的流量分配方案。这在实际中有各种挑战，因此，我们又设计了ECMP协议来帮助实施。
本节介绍网络资源分配中的各种公平：绝对公平、最大最小公平、比例公平。非常有意思。
本节介绍如何设计网络拓扑，即：要不要在两个节点间敷设一条链路。
本节介绍如何在网络链路容量的设计中，留出足够的余量，在某一链路发生故障的情况下，继续为用户服务。请注意，在这种情况下，我们的成本会大大增加。
本节介绍多径传输的好处：可以节省故障恢复需要付出的成本。
本节介绍多层网络的联合设计。我们要建立多层网络的联合优化模型，然后讨论它的最优解。
本节介绍如何配置路由协议所依据的链路权重，降低链路利用率，改善用户质量。本节我们将学到一个建立优化模型的特别方法：通过引入一个变量，将非线性的优化方程，变为线性优化方程，以便我们更容易求解。
本节首先介绍 MPLS 网络的原理，解释它的基本约束是标签数目的约束，然后给出其优化模型，其中包括：路径最小负载约束、路径使用指示变量、链路标签数均匀。
本节首先介绍电话交换网，包括汇接局和端局，然后利用爱尔兰公式，给出一定呼损率的条件下，话务量和所需中继线数目的关系，由此建立链路容量和网络流量（即话务量）的关系，获得电话交换网的优化模型。我们并讨论了时变用户需求下的模型设计。
本节首先介绍 SDH 光传输网络的拓扑、速率等级、复用，然后介绍其设计模型，特别是其模块化的传输单元。最后介绍其保护设计，包括分流、备用路径容量设计。
本节介绍 SDH 光传输网的重要设计特性：环。首先介绍其工作原理，特别是自愈特性。然后建立其容量设计模型。
本节介绍 WDM 波分复用网络的基本原理，建立其链路容量设计模型。
本节介绍IP over SDH 的两层网络设计模型。