计网第四章笔记 -- 网络层

网络层概述

• 网络系统提供的是端到端的传输服务：从发送端的主机到接收端的主机，至于送给哪一个进程是传输层的事情

• 网络层能够被分解为两个相互作用的部分：数据平面和控制平面。

  • 数据平面功能（每台路由器的功能）：决定到达路由器输入链路之一的数据报如何转发到该路由器的输出链路之一。
  • 控制平面功能（网络范围的逻辑）：控制数据报沿着从源主机到目的主机的端到端路径中路由器之间的路由方式。（路由选择算法、路由选择协议）

• 两个重要功能：转发（核心功能、用硬件实现）；路由选择（用软件实现）

网络服务模型

QoS参数

• 带宽
• 数据传输无抖动（包间隔变化很小）
• 不丢包
• 数据报的传输是有序的
• 拥塞反馈机制
• 无错误
• 实时性
• 安全性

不同网络提供的QoS是不一样的

• Internet：传输模型：尽力而为
• CBR（常数速率）：传输语音的，由于不丢包所以不会拥塞，因此不需要丢包反馈
• VBR（变化的速率）：传输视频的，有保证的带宽
• ABR（有效位率）：保证最小带宽，如果有多余带宽，可以使用多余的带宽
• UBR（未指定位率）：通信时候有可用才能用，没有可用的直接把数据报丢掉了

网络层的连接

ATM网络了解就可以了

IP是无连接的网络

虚电路网络在呼叫（call setup）的时候需要把资源都留好，通信完成之后再把资源撤销掉

虚拟电路是发送端和接受端之间的一条虚拟电路，由若干条电路构成

建立连接：半物理半逻辑的，称为虚拟链接，（虚电路网络）

中间的每个路由器都要为这个连接保存信息和资源，数据报基本不需排队

IP网络是没有这个建立过程的，这个建立链接过程是ATM、帧中机（frame relay），和X.25网络才需要的

每一个包头里面都有一个虚电路号（不包含目的地的IP地址），每过一个交换机虚电路号可能会变，虚电路上的每个交换机都会维护这个状态，新的虚电路号存在每个交换机的转发表上

一个虚拟电路包括：

• 从发送端到接收端的路径
• 虚拟电路号
• 链路上每个交换机上都要有转发表关于这个节点的入口

转发表

转发表是由路由选择处理器计算和更新的 （ 使用路由选择协议与其他网络路由器中的路由选择处理器进行交互 ），或者转发表接收来自远程 SDN 控制器的内容 。

拨号建立链路的协议是信令协议（signaling protocol）

ipv4目前没有信令协议，只在ATM和X25中有，ipv6中会涉及到这个协议

两个端交流的路径都走固定的路径进行通信

IPv4网络

没有呼叫建立的过程

传输的过程中可能会走不同的路径到达接收端

每次走的路径长度可能不一样，所以可能会出现乱序

IP网络的转发表

一个地址块走一个接口，根据目的IP地址确定

如果不在的话就直接走缺省端口

匹配是使用的是最长前缀匹配原则，简称为最长匹配原则

上面的对应的是端口号0，下面对应的是端口1

IPv4设计之初是发邮件的，对实时性要求不高

瘦内核，胖端系统，内核比较简单，对链路层要求比较简单（光纤，铜导线等等）

ATM是打电话，对于实时性要求比较高

胖内核，瘦端系统，内核复杂，对链路层要求高

路由器工作原理

路由器架构

每个端口既是输入端口也是输出端口，中间是一个交换结构

路由器的两个主要功能

• 可以运行相应的路由协议或算法，维护路由表
• 将数据报从输入链路转发到输出链路

输入端口

链路层处理的单位是帧

网络层是去中心化的交换

• 给定数据报的目的地，在转发表上寻找输出端口（转发表是存在输入端口的内存上的）
• 目标：以“line speed”完成输入端口处理 （line speed是线速度？）
• 如果数据报到达的速度比转发到交换机结构的速度快，则会把数据存在一个队列中

交换结构

分为三种类型

• 第一种是有一个内存，直接放入内存，由内存再放入输出端口中
• 第二种是总线类型的，直接把数据放到总线上，就到输出端口了
• 第三种是交叉网络，有开关控制的，横线和竖线交叉的地方有一个bar，平时是断开的，当需要通信的时候才会接通，在图上用点表示，逻辑上相当于多总线方式，是一个并行总线结构

方式一

经内存交换，最早期的模样

• 两次访问内存（一次写：从输入端口处被复制到处理器内存中；一次读：从内存中复制到输出端口的缓存中）
• 两次使用总线
• 数据转发效率不高

最早期性能很差路由器使用这种方式

方式二

经总线交换

无需访存，直接通过总线传输数据

带宽取决于总线的带宽，总线带宽越宽，总线竞争越小

方式三

经内部互联的网络交换，为了克服单一 、 共享式总线带宽的限制

这里不过多讲解，例如多级网络，路径可以是动态的

这些技术都是在超级计算机中连接多个CPU的，往往采用的都是比较复杂的网络，性能都比较高，带宽比较宽，但是价格也比较贵

输出端口

是网络层的镜像，也有一个队列，满了仍然是会丢包的

输出端口队列

何时出现排队：

• 当通过开关到达的速度超过输出线路速度时进行缓冲；

• 输出端口缓冲区溢出导致排队(延迟)和丢失

队列长度多大比较合适？

了解一下就好了

经验法则(rule of thumb)：RTT乘以连接容量（带宽）

最近的一个推荐，如果承载了N了TCP的流，则为$\frac{RTT\times C}{\sqrt{N}}$

输入端口的行头阻塞问题

如果数据到达速度超过数据转发能力会把数据存在队列中，队列满了之后会发生丢包

当队列没有满的时候也可能会发生丢包，当多个输入端口的包都要转发到同一个输出端口的时候不能同时转发，同一时间只能有一个端口转发，另一个仍然待在队列里面，这种情况叫做行头阻塞（HOL Head-of-the-Line blocking）

标准一点的概念：队列前面排队的数据报会阻止队列中的其他人向前移动

路由器结构

包含CPU、RAM、ROM，没有硬盘，取代的是FLASH，容量也比较大

不使用硬盘是因为容易坏

网际协议：IPv4、寻址、IPv6及其他

只有边界网关才有BGP协议

路由协议

• 路径选择
• RIP（路由信息协议），OSPF（开放的最短路径优先协议），BGP（边界网关协议）

ICMP: （internet control message protocol）控制报文协议

• 错误报告
• 连通性检查

最重要的协议：IP协议

网络层在逻辑上可以分为两个子层

• 上层是路由协议和ICMP协议
• 下层是IP协议

IP数据报格式

分为两部分，头和负载

头总共有五行，每行32位，4字节，总共有20个字节长（TCP的段头也是20个字节的长度，但是字段不一样）

知道字段什么意思就行了

• 第一行
  • version：版本号，IPv4填的是4,4位长
  • 头长度：4位
  • 服务类型：8位，期望数据报接受什么级别的转发服务，普通或者vip的IP包，一直没用过，意味着所有的数据报在路由器上都是平等的，到了IPv6可能就要启用了
  • length：数据报的总长度
• 第二行，实际中很少使用
  • id：相当于包序号
  • flag是标志位，在拆分时候用的
  • 偏移量：把ip包切片用的，如果切成十个，则前九个片的flag都是1，第十个是0，表示分片的结束，设计的时候是为了考虑适应不用的链路
• 第三行
  • TTL: time to live 寿命，离开网络层的时候会填写一个值，每过一跳就会减1，到0时候路由器会扔掉他，一般都是64
  • 上层协议：区分封装的是什么内容
  • 右边16位叫做校验核，（TCP和UDP里面都有，但是没有用），每经过一个路由器都要检查一下，而且没什么用，在经过链路层发送出来的时候都已经检查过是不是有问题了，如果有问题了就会直接扔到（二楼），到这里（三楼）肯定是没问题的
• 第四行：源IP地址
• 第五行：目的IP地址

更好的方法是把目的IP地址放在上面，这样可以更早的接收到目的IP地址，用的是IP地址的网络层

数据区不仅可以封装TCP和UDP的报文，而且还可以封装ICMP的报文

IP包的分片和装配

了解一下就行了

MTU（ Maximum Transmission Unit）最大传输单元，太小的时候就会把IP包进分片，到达接收端之后才会把小的片装配成大的IP包

每个分片里面的标识号是一样的，flag前面的都是1，最后面的是0，

例子：

这里每个分片都要有一个头，所以长度比未拆分的长度长

IP地址

介绍

IP：主机的三十二位标识号

IP地址不是与主机对应，是与网络接口对应的，有几个网络接口就可以有几个IP地址

路由器往往有多个接口，所以一般有多个地址

由于路由器的每个端口对应的网段（一个局域网/子网），该地址的网络部分是相同的

32位地址分为网络部分（高若干位）和主机部分（低若干位），同一网段内网络部分必须是相同的，主机部分不同，不同的网段网络部分肯定不相同

至于具体多少位取决于网络的类型

子网

这个子网是由是3个子网组成的

223.1.1.0/24 高24位是网络部分，低8位是主机部分

下面这个网络有6个网段

把路由器拿走有几个孤岛就有几个网段，只有线也算一个孤岛

Ipv4地址分为ABCD4类

分为网络部分和主机部分

这里一定要记住了，包括可表示地址范围

A类第一位固定为0，网络段有8位，一个网段逻辑上可以容纳$2^{24}-2$个主机

B类网段前面两位固定为10，网络段有16位，其余16位为主机段

C类网段前面三位固定为110，网络段有24位，其余八位为主机段

D类没有主机，以1110开头，叫做多播地址，是一对多通信，只能作为目的地址使用

这里面有相当多的地址是保留的，不分配出去使用

特殊地址

0.0.0.0不属于任何类型的地址，只能作为原地址使用，不能作为目标地址，表示本网络的本主机

net-id全为0：表示本网络的Host-id这个主机

1.1.1.1（即255.255.255.255）是一个广播地址，对所有主机广播

host-id全为1：也是一个广播地址，对这个网络内的所有主机进行广播

127.0.0.1自发自收，是一个自测试地址

更多信息

不能分配给用户的IP地址，大约有1%

A: 10.0.0.0~10.255.255.255
B: 172.16.0.0~172.31.255.255
C: 192.168.0.0~ 192.168.255.255

能够分配给主机的大约有85%

• 74%都在美国，平均一人6个
• 中国只占1%，平均26个人一个IP地址，

子网划分

国内一般不进行子网划分，划分会浪费一部分IP地址

对于一个B类主机来说，可以容纳$2^{16}-2=65534$个地址，如果要分6位的子网id，那么最后可以分配的地址是$(2^6-2)(2^{10}-2)=63364$个，浪费了大约2000个地址

子网划分的时候必须使用子网掩码

• 高若干位的网络部分不能动，把主机部分的高若干位拿出来作为子网id
• 根据要求的子网个数确定需要的位数，其中全0和全1是不能用的，比如3位只能用来标记六个子网
• 因此IP地址现在被划分为了三个部分：网络部分，子网部分，主机部分

不论是IP地址还是网络地址还是子网地址都是32位，不要和网络id和子网id搞混了，网络id和子网id就固定的几位

网络地址是网络段保持，其余位全0

子网地址是网络段和子网段保持不动，其余为0，也就是ip address & subnet mask

缺省子网地址：

• A: 255.0.0.0
• B: 255.255.0.0
• C: 255.255.255.0

例题：

一个小公司有一个C类网络，需要配置10个可用的子网，每个子网段可以容纳12台主机，最适合的子网掩码是多少？

答案：255.255.255.240

子网id段4位，可以配置14个不同的子网

主机段4位，可以配置14台不同的主机

CIDR

无类的域间路由

CIDR: Classless Inter Domain Routing

a.b.c.d/x表示高x位是网络段，是转发数据报是使用的地址

DHCP协议

DHCP:（Dynamic Host Configuration Protocol）动态主机配置协议，是应用层的协议，下层是UDP协议

DHCP 允许主机自动获取 （ 被分配 ） 一个 IP 地址 。 网络管理员能够配置 DHCP, 以使某给定主机每次与网络连接时能得到一个相同的 IP 地址 ， 或者某主机将被分配一个临时的 IP 地址 （ tempomry IP address ） , 每次与网络连接时该地址也许是不同的 。 除了主机 IP 地址分配外 ， DHCP 还允许一台主机得知其他信息 ， 例如它的子网掩码 、 它的第一跳路由器地址 （ 常称为默认网关 ） 与它的本地DNS 服务器的地址 。

工作涉及到四路广播（目的地址是全1的）：

• DHCP服务器发现（源地址为全0，本主机；目的地址为全1，广播）
  • 主机首先要广播一个DHCP discover报文，用于找DHCP服务器（如果网络比较大的话可能有多个DHCP服务器）
• DHCP服务器提供（也使用IP广播地址）
  • DHCP服务器回应一个DHCP offer报文，提供IP地址
• DHCP请求
  • 主机从接受到IP地址中选择一个并发出请求，发送DHCP request报文
• DHCP Ack
  • 被选中的DHCP服务器会发送一个DHCP ack报文，同意之后才能把IP地址分配给这个主机，同时其他的DHCP服务器把自己刚刚发出去的IP地址收会回来

一段时间不通信服务器会回收IP地址，再次通信时会重新分配

DHCP可以返回除了IP地址之外的其他东西

• 直接相连的路由器MAC地址
• DNS服务器的名称和IP地址
• 子网掩码

层次寻址

ICANN: （Internet Corporation for Assigned Names and Numbers）管理网络的公司

• 分配地址
• 管理DNS
• 分配域名，解决争端

NAT：网络地址转换

NAT: Network Address Translation，网络地址变换

多个假的IP地址映射到一个真的IP地址上面

优点：

• 内部IP地址变化不需要通知服务商
• 外部真IP地址变化对内部无影响
• 使用假IP地址不容易受到攻击
• 内部网络的设备不是明确可寻址的，安全性比较好

实现：NAT table

真假地址变换，使用端口号

需要维护一个表，叫做网络地址变换表

每一行的内容是假IP地址和端口号，真IP地址和端口号

发出去的时候把假IP地址和端口号换为真IP地址和端口号，回来时候需要再换回来，进出时候IP包的内容都发生了变换，通信效率下降

IP地址在IP包里，端口在TCP/UDP的段里面

内网可以使用的假IP端口号有16位，大约六万主机

NAT网关穿越

静态配置NAT表

只要有一个新的应用，NAT表中就新加一行，并向外广播，由NAT网络管理员进行配置

动态配置NAT表

UPnP: Universal Plug and Play，通用热插拔软件（通用即插即用）

Internet Gateway Device Protocol（IGD），工作在网络内部，有一个主机接进来后就会通知路由器添加这一条记录。同时向外广播

添加后是有寿命的，一段时间内不用就会从表中删掉，Cache的思想

ICMP协议

ICMP: Internet Control Message Protocol（控制报文协议）

作用：主机和路由器用它在网络层交流信息

• 错误报告（主要）
• 回声(echo)请求和响应（used by ping）

ICMP信息存储在IP数据报里面

ICMP由三部分构成：类型，编码，差错原因

写ping程序的时候需要建立一个额外的套口，区别于TCP，UDP套口

Ping sender: rawSocket = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);

traceroute：跟踪路由器（用ICMP报文实现）

命令：tracert + 主机名，跟踪路由器

为了判断源和目的地之间所有路由器的名字和地址 ， 源主机中的 Traceroute 向目的地主机发送一系列普通的 IP 数据报 。 这些数据报均携带了一个具有不可达 UDP 端口号的 UDP 报文段 。第一个数据报的TTL=1，第二个TTL=2，依次递推，当TTL到达0时候，路由器会返回一个ICMP报文，告诉数据被扔了，同时报文中有路由器的IP地址，所以按照收到的顺序就可以得到路径路由的信息，也可以根据到达时间计算RTT，即路径上用了多长时间

IPv6

原始动机：32位的地址空间即将要被分配完了

其他动机

• 原始的包处理起来太慢了
• IPv4的协议不支持QoS（所有人发的数据报都是平等的）

IPv6数据报格式：

• 定长40字节的header
• 不允许碎片（no fragmentation allowed）

内容：

• ver：版本号，4bits
• priority：优先级，号大的优先转发（支持QoS）8bits
• 流标签：20bits，一个用户发的所有包都有一个相同的游标号
• 负载长度：数据报的字节数，16bits
• 下一个头：表示数据域中封装的什么数据（TCP，UDP，ICMP），表示数据域中有没有扩展的头信息（扩展的头信息放在数据域里面）
• hop limit: TTL，过一条跳1，到0就扔
• 源地址：16个字节
• 目标地址：16个字节

没有了checkSum，确实没有用，只要接收端收到了肯定没有差错，如果有差错肯定收不到，中间就扔了

没有了IPv4中的包切片，如果帧太小了放不小就会扔了，然后返回一个ICMP的报文，通知发送端把包弄小一点重新发送，因为包切片会导致速度变慢

ICMPv6

一个新的ICMP版本

• 额外的信息类型：Packet Too Big
• 多播通信的组的管理功能(multicast group management functions)

Ipv4到IPv6之间的过渡

原因：不是所有的路由器可以被同时更新

• 隧道技术(Tunneling)
• 双栈技术(Dual-stack)，或者双协议栈技术

双栈技术(Dual-stack)

千万别写成双堆栈技术

边缘路由器：IPv4和Ipv6交接的路由器，需要能够识别两个协议，需要将两种协议的包进行转换

需要把IPv4的包转换为IPv6的包，或者把IPv6的包转换为IPv4的包，头中的对应的地方进行转换

IP地址怎么转换？16字节到8字节

答：放到数据域的最前面，重新给他一个IP地址

Tunneling

到达边缘路由器的时候把整个IPv6的包放在IPv4的数据域中，反过来也是一样的

把报文整个放到另一种格式的数据域中都叫做隧道技术

路由和转发之间的相互作用

用目的IP地址的网络部分查路由表，然后判断是从那个接口离开该路由器，不太适合实时通信

路由表是由路由算法维护的，是动态更新的

路由算法

目的：从发送方到接收方的过程中确定一条通过路由器网络的好的路径

用图来形式化描述路由选择：节点表示路由器，边表示物理链路，边上的值表示开销，用c(x,y)表示x到y的开销，若x与y之间没有链路，则置$c(x,y)=\infty$

实践中每个边的代价值通常是路由器管理员给出的

若在图中的所有边具有相同的开销 ， 则最低开销路径也就是最短路径

路由算法：找到花费最小的路径，即最小跳数

路由算法分类

全局还是局部

• 全局路由算法
  • 要求每一个路由器维护一个全局的拓扑图
  • 链路状态算法（Link State, LS）
  • 集中式算法具有关于连通性和链路开销方面的完整信息
• 分散路由算法
  • 路由器以迭代 、 分布式的方式计算出最低开销路径 。
  • 每个路由器需要记录自己和谁相连，把自己到每个点的最优路径发给邻居，邻居也把最优路径信息发给自己
  • 距离矢量算法（Distance-Vector，DV）

静态或者动态

• 静态路由算法
• 动态路由算法
  • 当前使用的多半都是动态路由算法

链路状态算法

全局路由算法，要求全局每个路由器都要维护一个全局的拓扑图

通过让每个节点向网络中所有其他节点广播链路状态分组来完成的 ， 其中每个链路状态分组包含它所连接的链路的标识和开销 。由链路状态广播算法来完成

也叫做Dijkstra算法

• 全局拓扑图：所有节点的链路成本已知，通过“链路状态广播”完成，所有节点有相同的信息
• 计算从一个节点(“源”)到所有其他节点的最小开销路径，得到该节点的转发表
• 迭代：经过k次迭代，知道到达k dest’s的最小代价路径
• 最差情况下复杂性为 $O(n^2)$

符号说明：

• C(x, y)：表示两点之间的代价，x,y是邻居
• D(V)：到算法的本次迭代，从源节点（每个路由器以自己为源节点）到目的节点v的最低开销路径的开销
• p(V)：从源节点到v节点的前继节点
• N’：节点子集；如果从源到v的最低开销路径已确知，则v在N’中

伪代码描述

求u到其他所有节点的最优路径的算法

Initialization: 
  N' = {u}        
  for all nodes v 
    if v adjacent to u //v和u是邻居
        then D(v) = c(u,v) 
    else D(v) = ∞ 
 
Loop 
  find w not in N' such that D(w) is a minimum 
  add w to N' 
  update D(v) for all v adjacent to w and not in N' : 
     D(v) = min( D(v), D(w) + c(w,v) ) 
  /* new cost to v is either old cost to v or known 
   shortest path cost to w plus cost from w to v */ 
until all nodes in N' 

求出最短路径的同时可以记录最短路径

震荡问题：

在该例中，节点 z 产生发往 w 的一个单元的流量，节点 x 也产生发往 w 的一个单元的流量，并且节点 y 也产生发往 w 的一个数量为 e 的流量 。

解决方法：

①强制链路开销不依赖于所承载的流量 ， 但那是一种不可接受的解决方案 ， 因为路由选择的目标之一就是要避
开高度拥塞 （ 如高时延 ） 的链路 。

②确保并非所有的路由器都同时运行 LS 算法 。更合理

距离矢量算法

使用的比链路状态早，而且比较简单，不用维护全局的拓扑图，路由器只和邻居打交道

定义$d_x(y)$为从x到y的最低开销路径的开销

该最低开销与**贝尔曼福特方程（Bellman-Ford example，也叫BF方程）**有关：
d x ( y ) = min ⁡ v { c ( x , v ) + d v ( y ) } d_x(y)=\min_v \{c(x,v)+d_v(y)\} dx​(y)=vmin​{c(x,v)+dv​(y)}
例子

定义$D_x(y)$ ：对在 N 中的所有节点 y, 估计从x到 y的最低开销路径的开销 。

使用 DV 算法，每个节点x维护下列路由选择信息 ：

• 对于每个邻居v，从x到直接相连邻居v的开销为 c(x,v)
• 节点x的距离向量 ， 即$D_x=[D_x(y):y\in N]$包含了x到 N 中所有目的地 y 的开销估计值
• 它的每个邻居的距离向量 ， 即对x的每个邻居v，有$D_v=[D_v(y):y\in N]$

贝尔曼算法的四个特性

• 异步的：每个节点不是同时在做计算
• 分布的：每个节点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居
• 迭代的：此过程一直要持续到邻居之间无更多信息要交换为止
• 自终止的

每个节点的状态图：

算法代码描述：

如果收到其他节点的广播计算完自己的路径后最短距离值没有发生变化就不用广播了

// for each node X
Initialization: 
for all destination nodes y, 
    if y is a neighbor: 
    	Dx(y) = c(x,y) 
    else Dx(y) = infinity
for each neighbor w 
    Send distance vector Dx= [Dx(y): y in Neighbor] to w   

loop 
    wait (until I see a link cost change to neighbor w or until I receive update from neighbor w)
    // 当节点x发现它的直接相连的链路开销变化 或 从某个邻居接收到一个距离向量的更新
    for each destinations y:  //节点检测到从它自己到邻居的链路开销发生变化
		Dx(y) =min v {c(x,v) + Dv(y)}  

    if Dx(y) changed for any destination y //如果最低开销路径的开销发生了变化,向邻居通知其新的距离向量
        send new value of min Dx(y) to all neighbors 
forever 

例子：

只有一行的最小值发生变化之后才会广播给邻居，否则都不广播给邻居

题目：请用类java语言描述该算法

现实之中链路代价一般都是变大了，比如电缆断了

变小是因为换路由器了

稳定后链路发生变化的情况

cost变小

需要把变化广播给邻居，然后邻居更新自己的值，经过一步修改之后由于最小值没有发生改变，所以经过一步之后算法就休眠了

只需要两步的交互就收敛了，文献称为good news travels fast

在此只关注y与z到目的地x的距离表中的有关表项：

• 在 t0 时刻，y检测到链路开销变化（开销从4变为1)，更新其距离向量，并通知其邻居这个变化，因为最低开销路径的开销已改变。
• 在 t1 时刻，z收到来自y的更新报文并更新了其距离表。它计算出到x的新最低开销（从开销5减为开销2)，它向其邻居发送了它的新距离向量。
• 在 t2 时刻，y收到来自z的更新并更新其距离表。y的最低开销未变，因此y不发送任何报文给z。该算法进入静止状态。

cost变大

bad news travels slow

到了 t1 时刻 ， 我们遇到路由选择环路 , 即为到达x , y 通过 z 路由 ， z 又通过 y 路由 。 路由选择环路就像一个黑洞 ， 即目的地为x的分组在 t1 时刻到达 y 或 Z 后 ， 将在这两个节点之间不停地 （ 或直到转发表发生改变为止 ） 来回反复

解决办法：引入有毒的逆向路径（adding poisoned reverse）

Z告诉Y说自己到X的路径是无穷大，所以Y不会再经过Z到X

经过三次通信之后就收敛了，比前面没有采用的该方法的时候快很多

两种算法的比较

• 消息复杂性

  • LS：总共有n个节点，E个边，总共有$O(nE)$个信息被发送
  • DV：只在邻居之间交换信息
    • 收敛时间不同

• 收敛的速度

  • LS：$O(n^2)$算法，总共需要$O(nE)$的消息交换
    • 可能会震荡
  • DV：收敛较慢 ， 且在收敛时会遇到路由选择环路 , DV 算法还会遭遇无穷计数的问题

• 健壮性（Robustness）

  • LS：可能会传递不正确的链路代价，每个节点只计算自己的table，路由计算在某种程度上是分离的 ， 提供了一定程度的健壮性
  • DV：可能会传递不正确的链路代价，每个节点的表都会广播给别人

• 链路状态算法是全局的，动态的

• 距离矢量算法是一个分散的，动态的算法

• 贝尔曼方程： D x ( y ) = min ⁡ v { c ( x , y ) + D v ( y ) } D_x(y)=\min_v\{c(x,y)+D_v(y)\} Dx​(y)=minv​{c(x,y)+Dv​(y)}表示从x到y的距离等于从当前节点到邻居节点的代价加上邻居v到目标节点y的距离

• DV算法的邻居有什么互动

  • 接受来自邻居的距离矢量或者是当自己的状态发生了变化之后发送给邻居

• 二者相比，DV算法更简单，这两个算法不兼容

层次路由

• 由于全世界的路由器太多了，所以一个路由器存储所有节点的信息是不现实的
• 哪怕可以存储这些信息，在运行算法时候也会耗费很多时间
• 链路状态发生变化后，节点更新太慢了

解决方法：AS（automomous system，自治系统）

​ 其中每个 AS 由一组通常处在相同管理控制下的路由器组成，通常在一个 ISP 中的路由器以及互联它们的链路构成一个 AS

​ 一个自治系统由其全局唯一的 AS 号（ASN）所标识。就像 IP地址那样，AS 号由 ICANN 区域注册机构所分配

​ 在相同 AS 中的路由器都运行相同的路由选择算法并且有彼此的信息

​ 不同AS通信的边界路由器叫做边界网关（Gateway router），起类似隧道的作用

边界网关中运行两种算法

• Intra-AS 路由算法
• Inter-AS 路由算法

这两个算法维护的表是不同的表，图中为Forwarding tables

AS间任务

问题：假如AS1中路由器接受到的目的地不在AS1中的数据报时，应该选择哪一个边界网关？

AS1必须

• 知道目的地是需要经过AS2还是AS3
• 当边界网关收到一条路径信息的时候需要在AS中进行广播

例子：

算法：热土豆算法(Hot potato routing)

AS中是最短的，出去了就不一定了

发给距离自己最近的边界网关

• 如果到一个目的地可以经过多个边界网关的话

• 找到AS中距离最近的边界网关

• 选择代价最小的边界网关

  

  

AS内协议

也被称为 Interior Gateway Protocols(IGP)

最常见的Intra-AS算法

• RIP: Routing Information Protocol
  • 核心算法是DV算法
  • 这个协议是开放的
  • 下层是UDP
• OSPF: Open shortest Path First
  • 核心算法是LS算法
  • 这个协议是开放的
  • 用的最多的
• EIGPR: Enhanced Interior Gateway Routing(Cisco Proprietary，思科公司的)
  • 这个协议是不开放的
• IS-IS: Intermediate System-to-Intermediate System
  • 核心算法是LS算法
  • 比OSPF算法新一点

RIP算法

核心算法是DV算法

• 距离指标：# of hops（max = 15 hops），表示AS中最远的两跳（直径）不超过15跳
• 每30秒种要通过响应报文把自己的距离矢量表广播给邻居
• 每次广播时候最多不超过25个子网，可以理解为AS的周长不能超过25跳

链路错误和恢复

• 每180s收不到来自邻居的距离矢量信息就认为和邻居之间的链路断掉了，也可能邻居死掉了
• 然后会广播(advertisement)给其他邻居
• 邻居收到信息会更新自己的距离矢量表
• 所以很快就会广播到整个网络中（AS网络）

RIP表处理

• DV维护的表是在网络层
• 软件（名称叫做route-d(daemon) 后台程序）是实现在应用层的
• 所有的路由程序都是后台程序
• 要通过UDP套口传输，每30秒传一次，目的端口号是520

OSPF

Open Shortest Path First 开放最短路径优先

• 也是周期性的广播一些信息，广播自己和谁相连，距离多少，周期约为30min
• 广播的时候是分发到整个AS网
• OSPF的报文直接封装在IP的包中，没用用到TCP或UDP
• 说明OSPF是工作在网络层的上部，和ICMP在一起的

优点

• 安全性：相较于RIP提高了很多，所有OSPF消息需要先进行认证
• 允许多条最短代价一样的路径，通信的时候都是可以走的
• 同一条链路执行不同的任务时候可以被认配置为不同的代价
• 对单播与多播路由选择的综合支持
• 在比较大的domain中使用分层OSPF

层次OSPF

两级分层结构，在各自的区域独自运行OSPF协议

• backbone区域
• Area区域

AS间路由协议：BGP

了解一下就可以了

世界上所有的边界网关都使用的是BGP协议

BGP(Border Gateway Protocol)

BGP给每个AS提供了完成以下任务的方法：

• BGP的网关可以得到到某一个点的路径信息
• 对每个AS传播可以到达的信息
• 基于一定的策略决定到AS的最优路径

采用半永久连接(semi-permanent)的TCP进行通信，可以通过会话来进行关闭的

工作在应用层的，与实际物理链路没有关系

1c是网关路由器，1a1b1d是内部路由器

BGP协议要求缺省情况下需要把所有的路径信息告诉邻居AS，但是也可以配置不告诉某个邻居

边界网关维护的叫路径表，内部一般才叫做路由表

广播的前缀包含BGP的属性，前缀加属性=路径

两个重要的属性

• AS路径：包含AS通过前缀
• 下一跳信息：

当边界网关接受到了路径广播，可以使用一定的策略来决定是接受还是拒绝（accept/decline）

BGP路径选择

路由器通常知道不止一条路由到某些AS（前缀），所以必须选择路径，一般有以下几种策略

• 本地自定义的策略
• 最短的AS_PATH（一般都是这种）
• 到最近的NEXT-HOP
• 其他指标

BGP报文

使用TCP通信，端口号179

• open：建立一个TCP链接，互相进行认证
• UPDATE：告诉对方自己的路径更新（最核心的报文类型）
• KEEPALIVE：在没有更新报文的时候，保持TCP连接的开启；当接受到OPEN报文时候也会返回这个
• NOTIFICATION：当接受到的报文无法识别或者有差错的时候会使用这种，也可以使用这个报文来关闭连接

BGP路由策略

ABC是网路服务提供商

X，Y，W是用户

X是双穴（dual-homed）：连接了两个网络，X不会告诉B自己连接了C，也不会告诉C自己连接了B

AS之间的策略要高于算法

• Policy

  • Inter-AS：管理可以控制向谁发数据报，可以控制谁可以向自己发数据报
  • Intra-AS：内部都是同一个服务商的，所以一般走的都是最优路径，无需考虑策略

• Scale

  目前IPv4是基于AS的路由

  • 是一个分层的路由，广播的业务量比较小

• Performance

  • Inter-AS：策略高于性能
  • Intra-AS：比较关注性能

练习

1. AC
2. C
3. D（其中octets表示字节的意思）
4. BCE
5. C（127开头是自测地址）
6. D
7. E（求子网地址按位与就行）
8. D
9. BF
10. F
11. C