IP路由表
上次有写过一篇《20张图深度详解MAC地址表、ARP表、路由表》的文章，里面有提到路由表，那么什么是IP路由、什么又是IP路由表呢？
路由：路由是网络中的基本概念，网络的基本功能就是使得处于网络中两个IP地址能够互相通信。
当路由器收到一个IP数据包时，路由器会解析出IP数据包中的目的IP地址，然后根据目的IP地址查找路由表，依据最长掩码匹配原则，找到对应的路由条目，根据路由条目中的下一跳或者出接口将报文转发出去，这就是路由。
路由表：简单点说路由表就是路由器用于指导数据包如何转发的表项，记录了去往目的IP的下一跳去哪里（如下图）。
路由表的作用类似于我们生活中的地图或者指示牌，指引我们去往一个目的地该如何走?
IP路由表包含了哪些要素
IP路由表中包含了目的网络/掩码，协议类型，优先级，开销，标志，下一跳，出接口这个七大要素。
下面我们来看下一个真实的路由表：
从这个路由器我们可以通过命令 displayiprouting-table 来查询该设备的路由表，我们可以看到这条设备一共有12条路由条目。
每个路由条目必须包括下面几个信息元素：
目的网络/掩码
目的网络/掩码：也被称为路由前缀，这是路由条目所关联的目的网络地址及网络掩码。
一条完整的路由前缀由：网络地址+前缀长度（或者网络掩码）构成，两者缺一不可，例如192.168.1.0/24与192.168.1.0/25，虽然网络地址相同，都是192.168.1.0，但是两者绝对是两条不同的路由，因为他们的前缀长度不相同。
当路由器收到一个IP数据包时，路由器会解析出IP数据包中的目的IP地址，然后根据目的IP地址查找路由表，依据最长掩码匹配原则，找到对应的路由条目。
最长掩码匹配原则匹配的就是目的网络/掩码。
比如：路由器收到一个目的IP地址为10.1.1.1的数据包，此时查找路由表，有两个路由条目，一个路由条目的A的目的网络/掩码是10.1.1.0/24，另一条路由条目B的目的网络/掩码是10.1.1.0/28，那么这个数据包匹配的是哪一个路由条目呢？
正确答案：是匹配路由条目B，因为B的掩码长。
协议类型
协议类型：指该路由条目是通过什么路由协议学些过来的。例如是直连的，或是静态的，或者是通过OSPF、IS-IS、EIGRP、BGP等动态路由学习到的。
1、直连路由：指和路由器的接口直接的地址生成的路由。
如下图中，协议类型是direct的就是直接直连地址生成的路由。
2、静态路由：静态路由是指通过静态路由协议生成的路由。
3、动态路由：动态路由协议主要有RIP、OSPF、ISIS、BGP。RIP和BGP是基于距离矢量的路由协议，OSPF和ISIS都是基于链路状态的路由协议。
优先级
路由表中去往同一目的地的路由可能通过多种路由协议生成。
举个例子：去往目的IP为192.168.2.1的通过静态路由生成了，也通过OSPF路由生成了。那么这个时候什么样的路由才会加入到路由表中呢？这个时候就和路由协议的优先级有关系了。
每种协议类型对应不同的优先级，优先级值越小则路由越优。
常用路由协议和优先级的关系表如下图。
那么当一台路由器同时从多种不同的路由协议学习到去往同一个目的地的路由时，它将优选路由协议优先级值最小的那条路由。
因此，本次例子中，正确的应该是通过OSPF学习到路由加入到路由表中（OSPF的路由优先级比静态路由优先级小）
开销
开销：路由的度量值，经常也使用metric来描述。
直连及静态路由的Cost为0。
通过动态路由协议学习到的Cost则根据实际情况而定。不同的路由协议计算Cost的方法不同。
例如上图中，R1去往PC2的路由条目通过OSPF路由协议学习到，开销为3。
标记
标志：路由标记，R表示该路由是迭代路由。D表示该路由下发到FIB（ForwardingInformationBase）表。
迭代路由：路由必须有直连的下一跳才能够指导转发，但是路由生成时下一跳可能不是直连的，因此需要计算出一个直连的下一跳和对应的出接口，这个过程就叫做路由迭代。BGP路由、静态路由和UNR路由的下一跳都有可能不是直连的，都需要进行路由迭代。
例如，BGP路由的下一跳一般是非直连的对端loopback地址，不能指导转发，需要进行迭代。即根据以BGP学习到的下一跳为目的地址在IP路由表中查找，当找到一条具有直连的下一跳、出接口信息的路由后（一般为一条IGP路由），将其下一跳、出接口信息填入这条BGP路由的IP路由表中并生成对应的FIB表项。
下一跳
下一跳：去往目标网络的下一跳IP地址。
出接口
出接口：去往目标网络从本设备的哪个接口出去。
---END---
数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。
它们是做什么用的？
想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。
特性
链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。
它们是做什么用的？
链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。
特性
堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。
堆栈可以使用数组或链表来实现。
它们是做什么用的？
现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。
堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。
另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。
特性
队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。
它们是做什么用的？
这种抽象数据类型(ADT)的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。
一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个ADT在许多图算法（Dijkstra算法、BFS、Prim算法、霍夫曼编码）中是必不可少的。它是使用堆实现的。
另一种特殊类型的队列是deque队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。
特性
Maps（dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。
哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。
最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是6，则键x的值是x%6。
理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。
它们是做什么用的？
Maps最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。
通讯录也是一张Map。每个名字都有一个分配给它的电话号码。
另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24小时=1440分钟）分配一个从0到1439的索引。哈希函数将为h(x)=x.小时*60+x.分钟。
特性
术语：
因为maps是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在O(logn)内完成；所有哈希表操作都是常量。
图是表示一对两个集合的非线性数据结构：G={V，E}，其中V是顶点（节点）的集合，而E是边（箭头）的集合。节点是由边互连的值-描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。
图有两种主要类型：有向图和无向图。在无向图中，边(x，y)在两个方向上都可用：(x，y)和(y，x)。在有向图中，边(x，y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x，y)与箭头(y，x)不同。
它们是做什么用的？
特性
图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：
一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。
根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。
它们是做什么用的？
我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。
树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。
特性
二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有n层的完整二叉树具有所有2?-1个可能的节点。
二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。
它们是做什么用的？
BT的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法(RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。
BST经常使用，因为它们可以快速搜索键属性。AVL树、红黑树、有序集和映射是使用BST实现的。
特性
BST有三种类型的DFS遍历：
所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。
AVL树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为1。AVL以其发明者的名字命名：Adelson-Velsky和Landis。
在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。
在Splay树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是O(logn)。
它们是做什么用的？
AVL似乎是数据库理论中最好的数据结构。
RBT（红黑树）用于组织可比较的数据片段，例如文本片段或数字。在Java8版本中，HashMap是使用RBT实现的。计算几何和函数式编程中的数据结构也是用RBT构建的。
在WindowsNT中（在虚拟内存、网络和文件系统代码中），Splay树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。
特性
最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]
