【计算机网络】—— IP协议及动态路由算法（上）

原理

1、网络层与IP协议

      网络层核心功能是转发(forwarding将分组从路由器的输入端口转移到合适的输出端口)与路由(routing确定分组从源到目的经过的路径)。

      IP数据报包含：

      版本号字段占4位；首部长度字段占4位；服务类型(TOS)字段占8位；总长度字段占16位；生存时间（TTL ）字段占8位(路由器转发一次分组，TTL减1; TTL=0，丢弃该IP分组); 协议字段占8位; 首部校验和字段占16位(对IP分组首部的差错检测)；源IP 地址、目的IP 地址字段各占32位。

      IP分片：

      网络链路存在MTU (最大传输单元)—链路层数据帧可封装数据的上限，将IP分组向较小MTU链路转发时，进行“分片” (fragmented)：1个IP分组分为多片IP分组；IP分片到达目的主机后进行“重组”(reassembled)；IP首部的相关字段用于标识分片以及确定分片的相对顺序，包括总长度、标识、标志位和片偏移。

      标志位字段占3位：

      DF (Don’t Fragment) 、MF (More Fragment)

      DF =1：禁止分片；DF =0：允许分片；MF =1：非最后一片；MF =0：最后一片。

      片偏移字段占13位：一个IP分组分片封装原IP分组数据的相对偏移量，片偏移字段以8字节为单位。

      最大分片可封装的数据为：d=⌊ M − 20 8 \frac{M-20}{8} 8M−20⌋8 ，需要的总片数为：n=⌈ L − 20 d \frac{L-20}{d} dL−20⌉ ，每片的片偏移字段取值为： F i = d 8 {\rm F}_i=\frac{d}{8} Fi=8d(i-1) ，1≤i≤n ，每片的总长度字段为： f ( x ) = { d + 20 ， 1 ≤ i < n L − ( n − 1 ) d ， i = n f(x)=\left\{\begin{aligned} & d+20， 1≤if(x)={d+20，1≤i<nL−(n−1)d，i=n ，每片的MF标志位为： M F i = { 1 ， 1 ≤ i < n 0 ， i = n M{\rm F}_i=\left\{\begin{aligned} & 1， 1≤iMFi={1，1≤i<n0，i=n

      IP编址(addressing)：

      32 比特(IPv4)编号，用以标识主机、路由器的接口。包含网络号(NetID) – 高位比特，用以标志网络，主机号(HostID) – 低位比特，用以标志主机。

      IP 子网，IP地址具有相同网络号的设备接口，不跨越路由器（第三及以上层网络设备）可以彼此物理联通的接口。其中第一个IP编号为网络号，最后一个为广播号，或者广播地址。

      Prefix和subnet mask，NetID、SubID位全取1，HostID位全取0的IP address 称为subnetmask 子网掩码，全部为1的 个数称为 prefix，前缀。

      子网地址+子网掩码→准确确定子网大小。每一个IP地址都应该详细标明子网掩码或者前缀，如10.10.10.10 255.255.255.0 或者10.10.10.10/24对于数据报网络路由器转发路由非常重要。

2、ICMP

      互联网控制报文协议 ICMP (Internet Control Message Protocol)支持主机或路由器进行差错(或异常)报告以及网络探询。网络探询报文(2组)主要含回声(Echo)请求与应答报文(Reply)与时间戳请求与应答报文。

      ICMP协议中较为常用的工具Ping和Tracer route。Ping 的原理是通过向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo Reply 回答报文，Ping根据时间和成功响应的次数估算出数据包往返时间以及丢包率；Traceroute工具用来跟踪一个分组从源点到终点的路径，有2种实现方案：基于UDP实现和基于ICMP实现。

3、DHCP

      动态主机配置协议，DHCP: Dynamic Host ConfigurationProtocol，客户端能够从配置了DHCP的服务器动态获取：IP 地址；子网掩码；默认网关地址；DNS 服务器名称与IP 地址。

      过程为：客户端0.0.0.0向255.255.255.255发送主机广播 “DHCP discover”(发现报文)；DHCP服务器利用 “DHCP offer” (提供报文) 进行响应；主机请求IP地址: “DHCP request” (请求报文)；DHCP服务器分配IP地址: “DHCP ack” (确认报文)。

4、动态路由算法

      路由算法(协议)确定去往目的网络的最佳路径，转发表(路由表)确定在本路由器如何转发分组。主要分为静态路由和动态路由。静态路由手工配置、路由更新慢、优先级高；动态路由的路由更新快、能够定期更新并及时响应链路费用或网络拓扑变化。

      动态路由算法典型的有两种：基于全局信息(所有路由器掌握完整的网络拓扑和链路费用信息)的链路状态(LS) 路由算法，基于分散信息(路由器只掌握物理相连的邻居以及链路费用，邻居间信息交换、运算是迭代过程)的距离向量(DV)路由算法。

      Dijkstra 算法可以实现链路状态(LS) 路由算法，Bellman-Ford算法可以实现距离向量(DV)路由算法。

主要内容以及使用的设备以及软件

前期准备

1、安装有Wireshark的客户端；

2、能够提供DHCP服务的服务器，或者能够开启热点的手机；

3、Packet Tracer、ENSP、GNS3、EVE-NG等网络虚拟仿真平台。

主要内容

1、ICMP协议中的工具Ping和Tracer route测试。

      Tracer route在Linux及路由器交换机等设备使用Traceroute，在Windows一般使用tracert。

      使用Traert 探测牛津大学的域名：

      验证了从源地址到目的地址的转发表，经过18跳到达，路途经过的节点查询IP所在地，即可得到路径。

      使用Ping 探测该域名，Windows系统中默认发送4个32bytes的ECHO，Linux系统默认不会自动终止，需要按ctrl+c终止。Ping不能完全确保目标主机是否可访问，有些服务器为了防止通过Ping探测到，通过防火墙设置了禁止Ping或者在内核参数中禁止Ping。

      TTL为47，47+18-1 = 64猜测服务器是Linux或者Unix类，查看Header得知其Server是Apache。

      使用Ping 和 Tracer route，以及Nslookup并不能完全保证得到确切的网站对应的IP地址(很多WEB使用反向代理、CDN、负载均衡等技术)，如上图Princedon.edu使用了Cloudflare基于反向代理的内容分发网络(CDN, Content Delivery Network)技术。

2、IP数据报格式与IP数据报分片

      IP数据报分片的计算和验证思路：应该先根据理论知识计算分片，再验证。IP分片时暂不考虑传输层分段，可以尝试用编写一个基于IP的Socket 也就是原始套接字(RAW)，发送一个至少大于14802(比如5200)bytes的包，捕捉报文验证，也可以使用ICMP 的经典应用Ping 命令，发送一个大于14802(比如5200)bytes的报文到IP地址，捕捉报文验证。

      Ping的命令为 ping [-t] [-a] [-n count] [-l length] [-f] [-i ttl] [-v tos] [-r count] [-s count] [-j computer-list] | [-k computer-list] [-w timeout] destination-list，-l可以控制发送字节大小，-n控制次数，Echo和Echo reply 不包含发送的[-l length]其他数据为8bytes。

      计算IP分片 Ceiling(5200+8/1480)=4 DF=0

      验证：开启wireshark捕捉，在cmd输入命令ping 运行

      可以看到Echo被分为了4个分片，IP数据报格式和分片如下图所示，值得注意的是第一个分片的Offset 0，最后一个分片Offset 4440，虽然最后一个分片只发送768bytes数据。

3、IP编址

      1)、子网划分

      将172.16.64.0/26划分为4个等长子网。

      示例：将172.16.16.0/20划分为相同长度8个子网

      方法一：2N=8 → N = 3 →划分后的prifix = 23

172.16.16.0 = 10101100‬ 00010000‬ 00010000‬ 00000000 SubID 为 NetID后的3位：‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

10101100‬ 00010000‬ 00010000‬ 00000000 10101100‬ 00010000‬ 00010010‬ 00000000‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

10101100‬ 00010000‬ 00010100‬ 00000000 10101100‬ 00010000‬ 00010110‬ 00000000‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

10101100‬ 00010000‬ 00011000‬ 00000000 10101100‬ 00010000‬ 00011010‬ 00000000‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

10101100‬ 00010000‬ 00011100‬ 00000000 10101100‬ 00010000‬ 00011110‬ 00000000‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

      方法二：2^N=8 → N = 3 → 划分后的prifix = 23 → 每个子网IP数：2(32-23)=2*2⁸

      网络为 172.16.16.0/23 172.16.18.0/23 172.16.20.0/23 ……… 72.16.30.0/23

      编程相对简单，参照方法一，取得网络位的二进制，然后将子网位用数组列出来(2^N长度，方法一中红色标记部分)，连起来补齐32位即可，也可转十进制：

      2)、确定网络号(子网地址)

      试确定172.115.116.117/21的子网地址。

      确定网络号(子网地址)非常重要，路由转发时根据目的IP编址的NetID检索转发表，计算方法示例如右图；编程相对简单，方法一:将IP地址与子网掩码(点分十进制)每段依次从左侧按位进行与运算；运行结果即为NetID，如图：

      方法二:①将IP地址与前缀转为32bit(32位二进制)；②依次从左侧按位进行与运算；③运行结果即为NetID，可以点分十进制输出，程序运行如下图：

      3)、路由总结

      试确定172.112.0.0/22、172.116.0.0/22、172.120.0.0/22这三个子网的路由总结。

      无类域间路由(CIDR: Classless InterDomain Routing) 消除传统的 A 类、B 类和 C 类地址界限，NetID+SubID → Network Prefix (Prefix)可以任意长度。CIDR可以提高IPv4 地址空间分配效率，提高路由效率。将多个子网聚合为一个较大的子网，称为路由总结或者路由汇总Route aggregation。

      计算过程如图所示。编程相对简单，① 将所有子网转为32bit(32位二进制)；②依次从左侧匹配位数，匹配位数量即Prefix；③匹配位即汇总网络的NetID,添加0补齐32位，即为路由汇总后的子网，可以点分十进制输出。运行结果参考下图：

      一般而言，在一个网络内的子网是不覆盖冲突的，但有时也会遇到要汇总的子网中，一个子网已经覆盖了其他子网的情况，完善一下：

代码参考(JAVA)：

//将<=255的十进制转二进制(8位输出)：
StringBuilder binary = new StringBuilder();for (int t = 0; t < 8; t++) {binary.append(ipAddDecPer>>(7 - t) & 1); }
//将Prefix(一般8-32)转为二进制
String subnetMaskBin[] = new String[32];for (int i = 0; i < 32; i++) {
if (i <prefix) { subnetMaskBin [i] = 1 + "";} else { subnetMaskBin [i] = 0 + "";}}
//二进制IP(32bit)转为点分十进制
for(int i=0;i<4;i++){ipDec+=Integer.valueOf(ipBin.substring(i*8,(i+1)*8),2).toString()+".";}

4、DHCP

      动态主机配置协议，DHCP: Dynamic Host ConfigurationProtocol，客户端能够从配置了DHCP的服务器动态获取：IP 地址；子网掩码；默认网关地址；DNS 服务器名称与IP 地址。

      遵循网络体系分层结构，DHCP可以配置在Windows，Linux，Router(路由器)，三层交换机等设备，甚至可以配置在手机，为了简单验证DHCP的过程及协议内容，我们使用手机开热点，在具备了WLAN的PC或者Notebook无线网卡捕捉报文，即可得到DHCP过程，为了保障捕捉到DHCP Discover报文，应将手机的SSID(一般是手机名字)重新设定。

      捕捉到的报文通过bootp过滤，结果如下：

      可以清晰的看到客户端和服务器的交互过程(DORA)：DHCP Discover (C68 → S67)；DHCP Offer” (S67 → C68)；DHCP Request；DHCP Ack。

      验证了：

      客户端0.0.0.0 的68端口向255.255.255.255的67端口发送了DHCP Discover报文；在一般网络故障分析排除中，有没有这个广播报文，非常重要，因为DHCP Discover并不会跨越到一个LAN之外去获得IP地址，要跨网络，必须依赖DHCP中继帮助转发DHCP Discover报文。

      DHCP Offer中一般包含：iP地址，子网掩码，网关，DNS(为域名劫持提供了巨大便利，很少有移动终端用户会去探究自己的DNS服务器是谁)，以及租约期，比如右图租约期85537S。

5、动态路由算法

      1)、距离向量(Distance Vector)路由算法

      距离向量(Distance Vector) 路由算法是一种分布式，异步迭代的算法。

      分布式(每个结点只当DV变化时才通告给邻居)，异步迭代(局部链路费用改变或邻居DV更新引发迭代)，源代码参考Bellman-Ford算法。

      距离向量(Distance Vector) 路由算法验证，构造如图所示拓扑。算法如右图所示。计算R1-R7路径，应该为R1-R2-R3-R7。

      运行编程验证结果如下：

2)、链路状态(Link-state)算法

      链路状态算法计算从一个源结点到达所有其他结点的最短路径，是一种全局迭代算法。

      全局(所有结点路由器掌握全局网络拓扑和链路费用)；迭代 (k次迭代后，得到到达k个目的结点的最短路径)，源代码参考Dijkstra算法。

      链路状态(Link-state)算法，构造如图所示拓扑，算法如右图所示。由于R1-R2-R3-R7与R1-R4-R5-R6-R7 开销和相等，所以两条链路都可。

      运行结果如下：可以看到返回了两条路径，链路状态支持负载均衡功能。

      扩展拓扑，增加一条R5-R3的链路，设置开销2，则正确路径应该是 R1- R4- R5- R3- R7。

      重新运行程序验证结果如下：

验证

1、ping和tracer route测试；

      在windows系统ping www.baidu.com，可以看出发生了四次32字节的ECHO。

Ping测试

      由ping命令中得出，到达www.baidu.com的TTL为53，则从源主机到目标主机需要的跳数为：64-53+1 = 12跳，由tracert命令进行下图验证。

tracer route测试

      查看Header得知其Server是nginx/1.8.0。

查看Header

2、IP数据报分片计算、验证

      用ping命令传输一个大小为8000bytes的数据包，下面为对分片的预测

      通过计算，8000/1480 = 5.4，由于向上取整，则其进行六个分片，前五个为1480，第六个预测为：8000-(1480+1480+1480+1480+1480)+20+8 = 628

      下图为ping命令并带有8000bytes数据：

ping命令并带有8000bytes数据

      抓包验证：

抓包验证

      可以看到，除了最后一个包为628bytes外，其余都为MTU最大值1500bytes。

      而且且标志位DF和MF都与预测相同：

【计算机网络】—— IP协议及动态路由算法（下）https://developer.aliyun.com/article/1507506?spm=a2c6h.13148508.setting.48.1b484f0eD2AqhJ