# 网络层协议-控制平面
# 路由选择算法
目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径(等价于路由)
集中式路由选择算法
用完整的、全局性的网络知识计算岀从源到目的地之间的最低开销路径。也就是说，该算法以所有节点之间的连通性及所有链路的开销为输入。这就要求该算法在真正开始计算以前，要以某种方式获得这些信息。计算本身可在某个场点进行，或在每台路由器的路由选择组件中重复进行。然而，这里的主要区别在于，集中式算法具有关于连通性和链路开销方面的 完整信息。具有全局状态信息的算法常被称作链路状态(Link State, LS) 算法,因为该算法必须知道网络中每条链路的开销。
分散式路由选择算法
路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。 相反，每个节点仅有与其直接相连链路的开销知识即可开始工作。然后，通过迭 代计算过程以及与相邻节点的信息交换，一个节点逐渐计算出到达某目的节点或 一组目的节点的最低开销路径。我们将在后面的5.2.2节学习一个称为距离向量(Distance-Vector, DV)算法的分散式路由选择算法。之所以叫作DV算法，是因为每个节点维护到网络中所有其他节点的开销(距离)估计的向量。这种分散式 算法，通过相邻路由器之间的交互式报文交换，也许更为天然地适合那些路由器直接交互的控制平面
路由选择算法的第二种广义分类方式是根据算法是静态的还是动态的进行分类。在静态路由选择算法(static routing algorithm)中，路由随时间的变化非常缓慢，通常是人丁-进 行调整(如人为手工编辑一条链路开销)。动态路由选择算法(dynamic routing algorithm) 随着网络流量负载或拓扑发生变化而改变路由选择路径。一个动态算法可周期性地运行或 直接响应拓扑或链路开销的变化而运行。虽然动态算法易于对网络的变化做岀反应，但也更容易受诸如路由选择循环、路由振荡之类问题的影响。
# 链路状态路由选择算法
链路状态算法中，网络拓扑和所有的链路开销都是已知的，也就是说可 用作LS算法的输入。
实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的，其中每个链路状态分组包含它所连接的链路的标识和开销，节点广播的结果是所有节点都具有该网络的统一、完整的视图。于是每个节点都能够像其他节点一样，运行LS算法并计算出相同的最 低开销路径集合。
Dijkstra算法或Prim算法
# 距离向量路由选择算法
距离向量(Distance-Vector, DV)算法是一种迭代的、异步的和分布式的算法，而LS 算法是一种使用全局信息的算法。说它是分布式的，是因为每个节点都要从一个或多个直 接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。说它是迭代的，是因为此过程一直要持续到邻居之间无更多信息要交换为止。
LS算法是一种全局算法，在于它要求每个节点在运行Dijkstra算法之前，首 先获得该网络的完整信息。DV算法是分布式的，它不使用这样的全局信息。实际上，节点具有的唯一信息是它到直接相连邻居的链路开销和它从这些邻居接收到的信息。每个节点等待来自任何邻居的更新(第10〜11行)，当接收到一个更新时计算它的新距离向量 (第14行)并向它的邻居分布其新距离向量(第16-17行)
# 因特网中自治系统内部的路由选择:OSPF
管理自治-因特网是ISP的网络，其中每个ISP都有它自己的路由器网络。ISP通常希望按自己的意愿运行路由器(如在自己的网络中运行 它所选择的某种路由选择算法)，或对外部隐藏其网络的内部组织面貌。在理想情况下，一个组织应当能够按自己的愿望运行和管理其网络，还要能将其网络与其他外部网络连接起来。
AS自治系统：路由器组织进自治系统(Autonomous System, AS) 来解决，其中每个AS由一组通常处在相同管理控制下的路由器组成
OSPF;开放最短路径优先协议
OSPF路由选择及其关系密切的协议IS-IS都被广泛用于因特网的AS内部路由选择。
OSPF是一种链路状态协议，它使用洪泛链路状态信息和Dijkstra最低开销路径算法。 使用OSPF, —台路由器构建了一幅关于整个自治系统的完整拓扑图(即一幅图)。于是, 每台路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根节点到所有子网的最短路径树。各条链路开销是由网络管理员配置的(参见“实践原则:设置OSPF链路 权值”)。管理员也许会选择将所有链路开销设为1,因而实现了最少跳数路由选择，或者可能会选择将链路权值按与链路容量成反比来设置，从而不鼓励流量使用低带宽链路。OSPF不强制使用设置链路权值的策略(那是网络管理员的任务)，而是提供了一种机制 (协议)，为给定链路权值集合确定最低开销路径的路由选择。
使用OSPF时，路由器向自治系统内所有其他路由器广播路由选择信息，而不仅仅是 向其相邻路由器广播。每当一条链路的状态发生变化时(如开销的变化或连接/中断状态 的变化)，路由器就会广播链路状态信息。即使链路状态未发生变化，它也要周期性地 (至少每隔30 min - 次)广播链路状态。
# ISP之间的路由选择:BGP
OSPF是一个AS内部路由选择协议。当在相同AS内的源和目的地之 间进行分组选路时，分组遵循的路径完全由AS内路由选择协议所决定。然而，当分组跨 越多个AS进行路由时，比如说从位于马里廷巴克图的智能手机到位于美国硅谷数据中心的一台服务器，我们需要一个自治系统间路由选择协议(inter-autonomous system routing protocol)o因为AS间路由选择协议涉及多个AS之间的协调，所以AS通信必须运行相同的AS间路由选择协议。在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议(Broder Gateway Protocol, BGP)
在BGP中，分组并不是路由到一个特定的目的地址，相反是路由到CIDR化的前缀, 其中每个前缀表示一个子网或一个子网的集合。在 BGP的世界中，一个目的地可以采用 13& 16. 68/22的形式，对于这个例子来说包括1024个IP地址。因此，一台路由器的转发表将具有形式为 仏，7)的表项，其中兀是一个前缀(例如13& 16. 68/22), /是该路由 器的接口之一的接口号。
通告BGP路由信息
对于每个AS,每台路由器要么是一台网关路由器(gateway router), 要么是一台内部路由器(internal router) 。网关路由器是一台位于AS边缘的路由器，它直接连接到在其他AS中的一台或多台路由器。内部路由器仅连接在它自己AS中的主机和路由器。
在 BGP中，每对路由器通过使用179端口的半永久 TCP连接交换路由选择信息。每条直接连接以及所有通过该连接发送的BGP报文，称为BGP连接(BGP cormection)。此外，跨越两个AS的BGP连接称为外部BGP ( eBGP)连 接，而在相同AS中的两台路由器之间的BGP会话称为内部BGP (iBGP)连接。