计算机网络——第五章:网络层(控制平面)

参考书目《计算机网络:自顶向下方法(第七版)》

路由选择算法

路由选择算法的目的是从发送方到接收方的过程确定一条好的路由路径。通常,一条好的路由路径指具有最低开销的路径
如下为计算机网络经典图模型
路由选择算法的一种分类方式是根据集中还是分散来划分:

  • 集中式路由选择算法:用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径。具有全局状态信息的算法被称作链路状态算法(Link State, LS)
  • 分散式路由选择算法:路由器以迭代、分布式的方式计算出最低开销路径。这种分散式路由选择算法称为距离向量算法DV(Distance Vector, DV)

LS路由选择算法

在LS中,网络拓扑和所有的链路开销都是已知的,实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的,其中每个链路状态分组包含它所连接的链路的标识和开销
节点广播的结果是所有节点都具有该网络的统一、完整的视图,于是每个节点都能够像其他节点一样,运行LS算法并计算出相同的最低开销路径集合
书上介绍了Dijkstra最短路径算法,此处不再赘述
LS算法存在的潜在问题————振荡。这是由于消息传播的时延导致的,它不仅存在于LS算法中,也存在于任何使用拥塞或基于时延的链路测度的算法

DV路由选择算法

距离向量算法是一种迭代的异步的分布式的算法

  • 分布式的:因为每个节点都要从一个或多个直接相连的邻居接收某些信息,执行计算,然后将其结算结果分发给邻居
  • 迭代的:因为此过程一直要持续到邻居之间无更多信息交互为止(有趣的是,此算法是自我终止的)
  • 异步的:因为它不要求所有节点相互之间步伐一致地操作

DV算法的核心思想基于贝尔曼-弗洛伊德方程 \[d_x(y) = min_v{c(x, v) + d_v(y)}\] 其中\(d_x(y)\)表示从节点x到节点y的最低开销路径的开销,\(c(x, v)\)表示从节点x到节点v的开销,该算法思想一句话总结就是:从x到y的距离能否通过途径v节点而变小
DV算法存在的问题:路由选择环路,导致关于链路开销增加的坏消息传播的很慢

LS与DV的比较

  1. 报文复杂性
    LS要求每个节点都知道网络中每条链路的开销,这就需要发送 O(|N||E|) 个报文,且任何一条链路的开销改变都需要在全网广播
    DV要求在每次迭代时,在两个直接相连节点间交换报文。当链路开销改变时,DV仅当新的链路开销导致与该链路相连节点的最低开销路径发生改变时,才传播已改变的链路开销
  2. 收敛速度
    LS是一个O(|N|^2)算法
    DV算法收敛较慢,且会遇到路由选择环路和无穷计数问题
  3. 健壮性
    在LS算法下,路由计算在某种程度上是分离的,这提供了一定程度的健壮性
    DV算法中一个不正确的节点计算值会扩散到整个网络

总之,两个算法没有一个是明显的赢家,它们的确都在因特网中得到了应用


自治系统内部的路由选择:OSPF

为什么要划分自治系统(Autonomous Systerm, AS)?

  • 规模。必须采取一些措施以减少像因特网这种大型网络中的路由计算的复杂度
  • 管理自治。ISP通常希望按自己的意愿运行路由器,如在自己的网络中运行它所选的路由选择算法,或对外部隐藏其网络的内部组织面貌

每个AS通常由一组处在相同管理控制下的路由器组成,ISP可在其整个网络使用一个AS或将其拆分为多个AS
每个AS有一个唯一的AS号(ASN),AS号由ICANN组织分配

开放最短路优先OSPF(Open Shortest Path First)

OSPF是一种链路状态协议,它使用洪泛链路状态信息和Dijkstra算法。
OSPF的优点:

  • 安全
    能够鉴别OSPF路由器之间的交换,仅有受信任的路由器能参与AS内的OSPF协议,因此可防止恶意入侵者将不正确的信息注入路由表内
  • 多条相同开销的路径 当到达某目的地的多条路径具有相同的开销时,OSPF允许使用多条路径(无须仅选择单一的路径来承载所有的流量)
  • 对单播与多播路由选择的综合支持 多播OSPF(MOSPF)[RFC 1584]提供对OSPF的简单拓展,以便提供多播路由选择
  • 支持在单个AS中的层次结构
    一个OSPF自治系统能够层次化地配置多个区域,在每个区域一台或多台区域边界路由器负责为流向该区域以外的分组提供路由选择。最后,在AS内只有一个OSPF区域配置为主干区域,其作用是为该AS中的其他区域之间的流量提供路由选择。
    整个过程为分组先到区域边界路由器,经过主干区域到达目的区域的边界路由器,最后到达目的地

ISP之间的路由选择:BGP

在因特网中,所有的AS运行相同的AS间路由选择协议,称为边界网关协议(Border Gateway Protocol, BGP)
在BGP中,分组并不是路由到一个特定的目的地址,相反是路由到CIDR化的前缀,其中每个前缀表示一个子网或子网的集合(如138.16.68/22)
在BGP中,每对路由器通过使用179端口的半永久TCP连接交换路由选择信息
每条直接连接以及所有通过该链接发送的BGP报文称为BGP连接。此外,跨越两个AS的BGP连接称为外部BGP(eBGP)连接,在相同AS中的两台路由器之间的BGP会话称为内部BGP(iBGP)连接

在BGP前缀中的BGP属性中,AS-PATHNEXT-HOP属性比较重要

  • AS-PATH属性包含了通告已经通过的AS的列表(使用ASN标识,如AS1 AS2 ...),BGP还使用该属性来检测和防止通告环路(若路由器在路径列表看到自己的AS,它将拒绝该通告)
  • NEXT-HOP是AS-PATH起始的路由器接口的IP地址(即该路径的源的IP地址)

BGP还常被用于实现IP任播(anycast)服务,该服务被DNS系统广泛用于将DNS请求指向最近的根DNS服务器


SDN:软件定义网络(Software-Defined Networking)

SDN体系结构的4个关键特征:

  • 基于流的转发
    SDN控制的交换机的分组转发工作,能够基于运输层、网络层或链路层首部中任意数量的首部字段值进行(传统方法中的IP数据报的转发仅依据数据报的目的IP地址进行)
  • 数据平面与控制平面分离
    数据平面由网络交换机组成;控制平面由服务器以及决定和管理交换机流表的软件组成
  • 网路控制功能:位于数据平面交换机外部
    控制平面自身由两个组件组成:SDN控制器(或网络操作系统)以及若干网络控制应用程序
  • 可编程的网络
    通过运行在控制平面中的网络控制应用程序,该网络是可编程的