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

简介: 【计算机网络】—— 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} 8M208 ,需要的总片数为:n=⌈ L − 20 d \frac{L-20}{d} dL20⌉ ,每片的片偏移字段取值为: 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+201i<nL(n1)di=n ,每片的MF标志位为: M F i = { 1 , 1 ≤ i < n 0 , i = n M{\rm F}_i=\left\{\begin{aligned} & 1, 1≤iMFi={11i<n0i=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

分片 数据 偏移/量 MF
1 1480 0 1
2 1480 1480/8 1
3 1480 1480*2/8 1
4 760+8 1480*3/8 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‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬

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

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

      编程相对简单,参照方法一,取得网络位的二进制,然后将子网位用数组列出来(2N长度,方法一中红色标记部分),连起来补齐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

分片 数据 偏移量 DF MF
1 1480 0 0 1
2 1480 1480/8 = 185 0 1
3 1480 1480*2/8 = 370 0 1
4 1480 1480*3/8 = 555 0 1
5 1480 1480*4/8 = 740 0 1
6 760+ 1480*5/8 = 925 0 0

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

ping命令并带有8000bytes数据

      抓包验证:

抓包验证

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

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

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

目录
相关文章
|
8天前
|
传感器 算法 安全
基于WSN网络的定向步幻影路由算法matlab仿真
该文探讨了无线传感器网络中的位置隐私保护,对比了NDRW路由与定向步幻影路由在安全时间和能耗方面的性能。在MATLAB2022a中进行测试,结果显示NDRW路由提供最长的安全时间,尤其在长距离传输时,且在近距离下能耗低于幻影路由。幻影路由虽消耗更多能量,但通过随机步创造幻影源以增强安全性。NDRW路由利用非确定性随机游走策略,避免拥堵并提高效率,而幻影路由则引入方向性控制,通过启发式算法优化路径选择。
|
1月前
|
算法 网络协议 数据建模
【计算机网络】—— IP协议及动态路由算法(下)
【计算机网络】—— IP协议及动态路由算法(下)
23 0
|
12天前
|
算法 网络架构
计算机网络: 点对点协议 PPP
计算机网络: 点对点协议 PPP
13 0
|
11天前
|
网络协议 C语言 网络架构
计算机网络——数据链路层-点对点协议(组成部分、PPP帧格式、透明传输、差错检测、工作状态)
计算机网络——数据链路层-点对点协议(组成部分、PPP帧格式、透明传输、差错检测、工作状态)
33 7
|
11天前
|
缓存
计算机网络——数据链路层-可靠传输的实现机制:选择重传协议SR(介绍、工作原理、窗口尺寸、题目练习)
计算机网络——数据链路层-可靠传输的实现机制:选择重传协议SR(介绍、工作原理、窗口尺寸、题目练习)
15 0
|
11天前
|
缓存
计算机网络——数据链路层-可靠传输的实现机制:回退N帧协议GBN(无差错情况、累积确认、有差错情况、发送窗口尺寸)
计算机网络——数据链路层-可靠传输的实现机制:回退N帧协议GBN(无差错情况、累积确认、有差错情况、发送窗口尺寸)
13 0
计算机网络——数据链路层-可靠传输的实现机制:回退N帧协议GBN(无差错情况、累积确认、有差错情况、发送窗口尺寸)
|
11天前
|
缓存 网络架构
计算机网络——数据链路层-可靠传输的实现机制:停止-等待协议SW(确认与否认、超时重传等,信道利用率及相关练习题)
计算机网络——数据链路层-可靠传输的实现机制:停止-等待协议SW(确认与否认、超时重传等,信道利用率及相关练习题)
33 0
|
11天前
|
网络协议 网络架构
计算机网络——计算机网络体系结构(4/4)-计算机网络体系结构中的专用术语(实体、协议、服务,三次握手‘三报文握手’、数据包术语)
计算机网络——计算机网络体系结构(4/4)-计算机网络体系结构中的专用术语(实体、协议、服务,三次握手‘三报文握手’、数据包术语)
10 0
|
11天前
|
网络架构
计算机网络——计算机网络体系结构(2/4)-分层的必要性(五层协议原理体系结构)
计算机网络——计算机网络体系结构(2/4)-分层的必要性(五层协议原理体系结构)
12 0
|
11天前
|
网络协议 网络架构
计算机网络——计算机网络体系结构(1/4)-常见的计算机网络体系结构(OSI体系、TCP/IP体系、原理体系五层协议)
计算机网络——计算机网络体系结构(1/4)-常见的计算机网络体系结构(OSI体系、TCP/IP体系、原理体系五层协议)
16 0

热门文章

最新文章