Allen Lee@Collections

第五章

路由选择算法

a_net_abstract_model
a_net_abstract_model

**路由选择算法(routing algorithm)**的目的是确定网络中一个源到目的地之间的最低开销路径

通常划分为

  • 集中式(centralized)路由选择算法，需要提前确定所有路径上的开销，典型的如链路状态(Link State, LS)算法
  • 分散式(decentralized)路由选择算法，每个路由器通过迭代、分布式的计算出所需路径，典型的如距离向量(Distance-Vector, DV)算法

另外还可以分为**静态(static)和动态(dynamic)**路由选择算法、**负载明感(load-sensitive)和负载迟钝(load-insensitive)**算法

AS

**自治系统(Autonomous System, AS)**由一组在相同管理控制下的路由器组成，目的是为了减少路由选择算法的规模，每个 AS 由全局唯一的 AS 号标识，其由 ICANN 区域注册机构分配

在同一个 AS 中运行的路由选择算法叫做自治系统内部路由选择协议(intra-autonomous system routing protocol)

**开放最短路优先(OSPF)**是一种 AS 内部的 LS 算法，使用洪泛链路状态信息和 Dijkstra 算法，其中的开销由管理员配置。其通告包含在 OSPF 报文中，由 IP 承载，上层协议值为 89

RIP 协议(Routing Information Protocol, 路由信息协议)，基于距离向量算法，适用于小型同类网络。其通过广播 UDP 报文(520)来交换路由信息，每 30 秒发送一次路由信息更新。使用跳跃计数(hop count)(一个包到达目标所必须经过的路由器的数目)作为尺度来衡量路由距离。只要跳跃计数相同，RIP 则认为两个路由是等距离的。RIP 最多支持的跳数为 15，16 为不可达

IS-IS(Intermediate System-to-Intermediate System，中间系统到中间系统)协议，使用最短路径优先算法，其定义较为复杂，具体参考：详细笔记 1/详细笔记 2

用于在 AS 间的路径选择协议，称为自治系统间路由协议(inter-autonomous system routing protocol)。全球 AS 通用的协议是边际网关协议(Broder Geteway Protocol, BGP)

BGP 采用距离向量算法

BGP 有两个作用

  1. 通告某个 IP 地址的存在。BGP 使用 179 端口的半永久 tcp 连接交换路由信息。每条直接连接及其发送的 BGP 报文称为BGP 连接。跨越 AS 的 BGP 连接(外部 BGP 连接, eBGP)的两个路由器称为网关路由器(geteway router)，其他的称为**内部路由器(internal router)**其连接叫内部 BGP 连接(iBGP)
  2. 路由选择。在通告时，BGP 将报告BGP 属性，其中重要内容有：AS-PATH(已经通过的 AS 列表)和 NEXT-HOP(AS-PATH 的起始路由器接口地址)。BGP 的路由选择算法基于热土豆路由选择(hot potato routing)

BGP 还用于实现IP 任播(anycast)服务。该服务通常处于 DNS 中，用于 ① 替换不同服务器上的相同内容 ② 让用户从最近的服务器访问内容

SDN 软件定义网络

sdn
sdn

通用转发表，通过匹配+动作的范式，对协议栈多个首部内容进行匹配，从而做到转发、负载均衡、防火墙等动作，是一般化的“分组交换机”

通用转发表经典标准为 OpenFlow，其表称为流表(flow table)

SDN 采用可编程的网络，使得可以通过 SDN 控制器的 API 来定义和控制网络设备

ICMP

**因特网控制报文协议(ICMP)**用于端系统和路由器之间沟通网络层的信息，典型用途是差错报告

ICMP 是作为 IP 载荷所承载，但其位于网络层

icmp_messages_type
icmp_messages_type

在 ICMPv6 中，添加了 IPv6 所需的类型和编码，如“分组太大”等

网络管理和 SNMP

network_managed
network_managed

被管设备(managed device)中的每个被管对象(managed object, 如网卡/协议内容等)通过网络管理代理(network management agent)与管理服务器通信，之后被存储在**管理信息库(Management Information Base, MIB)**中

MIB 对象由数据描述语言 SMI(Structure of Management Information)所定义，收集在 MIB 模块中

代理和服务器之间使用网络管理协议(network management protocol)通信，典型的如简单网络管理协议(Simple Network Management Protocol, SNMP)

SNMP 是应用层协议其报文通常称为协议数据单元(PDU)，基于 UDP，通常有两种模式：① 请求响应，服务器请求，代理响应；② 异常陷阱，代理指示异常

pdu_of_snmp
pdu_of_snmp