计算机网络知识点及例题总结（四）网络层

知识点部分

1.网络层服务（尽力而为服务）
网络层基本概念：从发送主机(将数据段封装在数据报中)向接收主机(向传输层交付数据段)传送数据段，每个主机和路由都运行网络协议，路由器检验所有穿越它的IP数据报的头部域(决策如何处理IP数据报)。
网络层核心功能：①转发(涉及单一路由器，将分组从路由器的输入端口转移到合适的输出端口)②路由(涉及一个网络的所有路由器，确定分组从源到目的经过的路径—路由算法详见9)。③某些网络(ATM,帧中继，MPLS等)中的功能:连接建立
网络层服务模型：①无连接服务：不事先为系列分组的传输确定传输路径，每个分组独立确定传输路径，不同分组可能传输路径不同；数据报网络。②连接服务：首先诶系列分组的传输确定从源到哦目的经过的路径即建立连接，沿该路径传输系列分组，系列分组传输路径相同，传输结束后拆除连接；虚电路网络。
网络层与传输层连接和无连接的区别：①网络层提供的服务是由网络层向传输层提供的主机到主机(端到端)的服务，传输层是传输层向应用层提供的进程向进程的服务②运输层面向连接服务是在位于网络边缘的端系统中实现的，网络层连接服务除了在端系统中实现，也在位于网络核心的路由器中实现。
网络层3个主要组件：IP协议(见3)，因特网路由选择协议(见13)，因特网控制报文协议(见8)
2.虚电路和数据报:分组交换
虚电路网络(仅在网络层提供连接的服务)
组成：①虚电路：一条从源主机到目的主机的类似于电路的路径。分组交换，每个分组的传输利用链路的全部带宽，源到目的路径经过的网络层设备共同完成虚电路功能。②VCID(虚电路标识，每个分组携带VC而不是目的主机地址)，标识沿路径每条链路的号码(同一条VC，在每段链路上的VCID通常不同)③沿路径路由器中转发表中的项。VC路径上每个路由都需要维护VC连接的状态信息。
通信过程：呼叫建立→数据传输→拆除呼叫
数据报网络(仅在网络层提供无连接的服务)
每个分组携带目的地址，路由器根据分组的目的地址转发分组(每个分组独立选路)，路由使用最长前缀匹配规则(检索转发表时，优先选择与分组目的地址匹配前缀最长的入口)与转发表中的表项进行匹配。

组成：输入端口，交换结构，输出端口，路由器选择处理器。
两者对比：
数据报网络:计算机之间的数据交换,链路类型多统一困难，智能端系统，简化网络复杂边缘
虚电路网络:电话网演化而来，实时对话，非智能系统(例电话机，传真机)，简化边缘复杂网络
3.IP协议——IP数据报

版本号：4位，IP协议的版本号(IPV4，IPV6).
首部长度：4位，IP分组首部长度；以4字节为单位,若首部长度为5则IP分组长度为4x5=20.
服务类型(区分服务)：8位，指示期望获得的服务类型.
总长度：16位，IP分组的总字节数(首部+数据)，最大IP分组总长度65535B,最小20B，可封装的最大数据:65535-20=65515B.
标识：16位，标识一个IP分组，每产生IP分组计数器加一，作为该IP分组的标识.
标志位：3位，DF=1禁止分片,DF=0允许分片,MF=1非最后一片,MF=0最后一片(未分片).
片偏移：13位，一个IP分组分片封装IP分组数据的相对偏移量，片偏移字段以8字节为单位.
生存时间(TTL)：8位，IP分组在网络中可以通过的路由数(跳步数)，路由器转发一次分组，TTL减1，若TTL=0则路由器丢弃该IP分组.
协议：8位，指示IP分组封装的是哪个协议的数据包。6为TCP, 表示封装为TCP段，17为UDP.
首部检验和：16位，实现对IP分组首部的差错检测；计算校验和时，该段全部置为0.
源IP地址，目的IP地址：各32位，分别表示发送分组的源主机/路由器(网络接口)和接收分组的目的主机/路由器(网路接口)的IP地址.
选项字段：长度可变(1-40B)，携带安全、源选路径, 时间戳和路由记录等内容(很少使用该字段)
填充：长度可变(0-3B)，补齐整个首部，复合32位对齐，即保证首部长度是4字节的倍数.
4.IP协议——IP分片
数据总长度L,链路MTU为M,若L>M则分片，记最大分片可封装的数据为d,需要的总片数为n，片偏移为F(offset).（公式如下）

5.IP协议——IP地址计算
IP地址：

IP子网：具有相同网络号的设备接口，不跨越路由器。

IP地址分类：A类IP地址：网络号8位(1-127)，主机号24位；默认子网掩码：255.0.0.0
B类IP地址：网络号16位(128-191)，主机号16位；255.255.0.0
C类IP地址：网络号24位(192-223)，主机号8位；255.255.255.0
子网掩码(网络掩码，地址掩码)：标识网络ID部分(连续1)，主机ID部分(连续0)，对于C类IP来说，它的子网掩码就是255.255.255.0，前3个字节为网络位，最后一个字节为主机位。
网络地址：将IP地址和子网掩码进行与运算(即将主机号位全部置为0)；
广播地址：将IP地址中主机号全部置为1；
地址范围：网络地址至广播地址；
可分配地址范围：网络地址+1至广播地址-1；若网络地址为192.168.100.0，广播地址为192.168.100.255,则地址范围为192.168.100.1-192.168.100.254；
主机数：主机号有6位，那么该网络段中，最多有2^6-2=62台主机。
网关：网关实质上是一个网络通向其他网络的IP地址。默认网关的意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机使用的网关，一般指的是默认网关。
192.168.0.1/24是什么意思? “/24”表示的就是网络号的位数，也就是告诉我们了子网掩码是多少，连续24个1，剩下位为0，即255.255.255.0。
例

例题部分：

6.IP子网划分
206.110.4.0/18被划分成16个子网，每个子网能容纳的主机数？
答：根据206.110.4.0/18,我们就能得出子网掩码为255.255.252.0，网络位有18位，主机位也就有14位，因为要在该网络下划分子网，并且子网个数为16，也就是2^{4，所以，要在主机位借出4位，用来划分子网，所以主机位也就变成了10位，所以最大能够容纳2}10-2=1022台主机。
7.CIDR与路由聚合
CIDR(无类域间路由)：消除了传统的A类，B类和C类地址界限，直接在IP地址后面加上NetID和SubID的长度和Prefix，得到无类地址格式：a.b.c.d/x，x是前缀长度。

这种方式特点：
①提高了IPv4地址空间分配效率
②提高路由效率
③将多个子网聚合为一个较大的子网(将相同的公共前缀提出来，并修改Prefix)，这个称为路由聚合。
路由聚合本质上是一种层级编址，通过层级编址实现了IP地址的按区域段进行分发，它们有同意的前缀，且分布在同一个子网区域。但是在互联网中相同前缀的IP可能没有分布在同一个IP子网中，那么就采用最长前缀匹配，提高分配的效率。图示路由聚合过程：

8.DHCP协议(动态主机配置协议，即插即用协议)
主机获得IP地址除了可以通过静态配置，还可以通过动态主机配置协议DHCP。DHCP从服务器动态获取IP地址，子网掩码，默认网关地址和DNS服务器名称与IP地址。DHCP协议允许地址重用，支持在用地址续租，支持移动用户加入网络。
DHCP协议在应用层实现，请求报文封装在UDP数据报中，IP广播，链路层广播，每个子网具有一台DHCP服务器(内建于路由器中)，如果某子网中没有服务器，则需要一个DHCP中继代理(通常是一台路由器)，这个代理知道用于该网络的DHCP服务器的地址。
DHCP构造ACK报文(包括分配给客户的IP地址，子网掩码，默认网关，DNS服务器地址)主要实现过程如下(报文内容需要掌握)：
①主机广播“DHCP discover”发现报文；(客户端向服务器发送)
客户端在UDP分组中向端口67发送该发现报文；DHCP客户将该IP数据报传递给数据链路层，链路层将该帧广播到所有与该子网连接的子网。

②DHCP服务器利用“DHCP offer”提供报文进行响应；(服务器向客户端发送)

③主机利用“DHCP request”请求报文请求IP地址(客户端向服务器发送)

④DHCP服务器利用“DHCP ack”确认报文分配IP地址(服务器向客户端发送)

9.NAT协议
NAT(网络地址转换协议)：本地网络内通信的IP数据报的源于目的IP地址均在子网10.0.0/24内；所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NAT IP地址以及不同的端口号(16bit端口号可以支持六万多个并行连接)。
使用NAT的原因：①IPv4地址耗尽，只能从ISP申请一个IP地址②本地网络设备IP地址变更，无需通告外界网络③变更ISP时，无需修改内部网络设备IP地址④内部网络设备对外界网络不可见，即不可直接寻址（安全）。
NAT实现：①替换，利用(NAT IP地址,新端口号)替换每个外出IP数据报的(源IP地址,源端口号)②记录，将每队(NAT IP地址,新端口号)与(源IP地址,源端口号)的替换信息存储到NAT转换表中③替换，根据NAT转换表，利用(源IP地址,源端口号)一环每个进入内网的IP数据报的(目的IP地址,目的端口号)即(NAT IP地址,新端口号)。

NAT主要争议：
①路由器只处理第3层功能
②违背端到端通信原则
③地址短缺问题赢由IPv6解决。

NAT穿透问题：客户期望连接内网地址为10.0.0.1的服务器，却不能直接利用该地址直接访问服务器；对外唯一可见的地址是NAT地址138.76.29.7。
解决方案①静态配置NAT，将特定端口的连接请求转发给服务器②利用即插即用UPnP互联网网管设备协议自动配置：学习到NAT公共IP地址，在NAT转换表中增删端口映射③中继，NAT内部与中继服务器进行连接，外部客户也与中继服务器进行连接，中继服务器桥接连个连接的分组。

10.ICMP协议
ICMP(互联网控制报文协议)协议：被主机和路由器用来彼此沟通网络层的信息。ICMP报文是承载在IP分组中的，即lCMP报文是作为IP有效载荷承载的；当一台主机收到一个指明上层协议为ICMP的IP数据报时，它分解出该数据报的内容给ICMP。
两类ICMP报文：差错报告报文(5种)&网络探询报文(2组)
ICMP报文格式：ICMP报文封装到IP数据报中传输(右图为差错报告报文数据封装)

如图，ICMP报文有一个4bit类型字段、一个4bit编码字段、一个8bit检验和字段，并且包含引起该ICMP报文首次生成的IP数据报的首部+前8字节内容（以便发送方能确定引发该差错的数据报）。
差错报告报文：
①目的不可达(类型3)；
②源抑制：这种报文在实践中很少使用，其最初目的是执行网络层拥塞控制。路由器发现缓存已满，到达的分组被丢弃，路由器向源主机发送源一个ICMP源抑制报文，以强制该主机减小其发送速率。实际未采用该拥塞控制方式。TCP有自已在传输层操作的拥塞控制机制，不需要利用网络层中的反馈信息 ；
③超时/超期：超过IP数据报生存周期，或者分段的IP数据报没有在规定时间内重组；
④参数问题；
⑤重定向：告诉发送主机，到达目的IPv4地址有更好的路由。
网络探询报文：
①回声(Echo)请求与应答报文(Reply)：ping程序发送一个类型8编码0的回显（echo）请求到指定主机，目的主机发回一个类型0编码0的ICMP回显回答。大多数TCP/IP实现直接在操作系统中支持ping服务器，即该ping服务器不是一个进程。
②时间戳请求与应答报文
几种不发送ICMP差错报告报文的特殊情况：
（1）对ICMP差错报告报文不再发送ICMP差错报告报文
（2）除第1个IP数据报分片外，对所有后续分片均不发送ICMP差错报告报文
（3）对所有多播IP数据报均不发送ICMP差错报告报文
（3）对具有特殊地址（如127.0.0.0 或 0.0.0.0）的IP数据报不发送ICMP 差错报告报文
几种ICMP报文已不再使用：
①信息请求与应答报文
②子网掩码请求和应答报文
③路由器询问和通告报文
ICMP应用举例：Traceroute
Trareroute程序允许我们跟踪从一台主机到世界上任意一台其他主机之间的路由，是用ICMP报文来实现的：
（1）源主机向目的主机发送一系列UDP数据报，目的端口号为不可能使用的端口号
第1组IP数据报TTL=1，第2组IP数据报TTL=2……
（2）当第n组数据报(TTL=n)到达第n个路由器时，路由器丢弃数据报，向源主机发送TTL过期ICMP报文（type=11，code=0），ICMP报文携带路由器名称和IP地址信息
（3）当ICMP报文返回到源主机时，记录RTT
（4）UDP数据报最终到达目的主机，目的主机返回目的端口不可达ICMP报文（type=3，code=3）
（5）源主机停止发送UDP数据报

例题部分

11.路由基本原理与算法
路由算法（协议）确定去往目的网络的最佳路径，转发表确定在本路由器如何转发分组。
路由算法：寻找最小费用路径的算法。
路由算法分类：
静态路由：手工配置、路由更新慢、优先级高
动态路由：路由更新快（定期更新、及时响应链路费用或网络拓扑变化）
全局式路由选择算法：所有路由器掌握完整的网络拓扑和链路费用信息。例如链路状态算法。
分散式路由选择算法：路由器值掌握物理相连的邻居以及链路费用，邻居间信息交换、运算的迭代过程。例如距离向量算法。
12.链路状态算法
核心算法：Dijkstra算法：所有结点(路由器)掌握网络拓扑和链路费用，通过链路状态广播，所有结点拥有相同的信息，计算从一个结点到达所有其他结点的最短路径，即获得该结点的转发表。
这是一种全局式的路由选择算法，也就是说，一个路由器知道到其他路由器的所有链路的状态信息（例如某条链路上堵不堵），并且假设这种信息是被量化好了的（以拥堵情况为例，越拥堵该值越大），在这样的情况下，链路状态算法就是要让路由器在这些链路中选择一条最好的从源到目的主机的路径。什么是最好？当然是路径上所有链路的状态加起来最好（拥堵度最小）。假设下图中的数字代表拥堵状态（值越大，越拥堵）。
c(x,y) 结点x到y的链路费用，不直接相连为记为无穷大；D(v) 从源到目的v的当前路径费用值；p(v) 沿从源到v的当前路径，v的前序结点；N’ 已经找到最小费用路径的结点集合

算法复杂性：n个结点，每次迭代需要检测所有不在集合N’中的结点w：O(n^2)；更高效的实现：O(nlogn).
存在问题：震荡，随着TTL减少最终会丢包，可能引起随机延时。

13.距离向量算法
Bellman-Ford方程：
（动态规划）

结点获得最短路径的下一跳，该信息用于转发表中！

Dx(y)=从结点x到结点y的最小费用估计
x维护距离向量（DV）：Dx=[Dx(y): y∈N]
结点x：
已知到达每个邻居的费用：c(x,v)
维护其所有邻居的距离向量：Dv=[Dv(y): y∈N]
核心思想：
每个结点不定时地将其自身的DV估计发送给其邻居。
当x接收到邻居的新的DV估计时，即一句B-F更新其自身的距离向量估计
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y∊N
Dx(y)最终会收敛于实际的最小费用dx(y)
特点：①异步迭代：引发每次局部迭代的因素有局部链路费用的改变和来自邻居的DV变化。②分布式：每个节点只有当DV变化时才通告给邻居，邻居在必要时(其DV更新后发生变化)再通告它们的邻居。
每个结点状态：等待(本地局部链路费用变化或收到邻居DV更新)→重新计算DV估计→如果DV中到达任一目的距离发生改变，通告所有邻居。
存在问题：无穷计数(坏消息传播的慢，当网络存在环路时，可能会出现无穷计数问题)
解决方法：①毒性逆转：如果一个结点Z到达某目的X的最短路径是经过某个邻居Y，则通告给该邻居结点到达该目的的距离为无穷大。
②定义最大度量：定义一个最大的有效费用值，如15跳步，16跳步代表无穷大。

14.层次路由
将任意规模网络抽象为一个图计算路由—过于理想化，网络规模大(考虑6亿目的结点网络)，这种情况下路由表几乎无法储存；管理自治：每个网络的管理可能都期望自主控制其网内的路由。
层次路由：聚合路由器为一个区域：自治系统AS。同一AS内的路由器运行相同的路由协议，不同AS中的路由器可运行不同的AS内部协议；网关路由器位于AS边缘，通过链路连接其他AS的网关网络。
互连的AS：
自治系统间(Inter-AS)路由任务：假设AS1内某路由器收到一个目的地址在AS1之外的数据报: 路由器应该将该数据报转发给哪个网关路由器呢？
AS1必须（自治系统间路由任务！）:
学习到哪些目的网络可以通过AS2到达，哪些可以通过AS3到达，将这些网络可达性信息传播给AS1内部路由器。
热土豆路由：将分组发送给最近的网关路由器。
Internet采用层次路由。

15.最常见的AS内部路由协议：RIP/OSPF
AS内部路由协议也称为内部网络协议IGP。
（1）路由信息协议RIP：RIP协议是一种采用距离向量算法的路由协议。
到目的网络的距离以跳为单位，最大距离为15，距离16表示无穷大，即目的网络不可达。（这一规定限制了RIP协议只能适用于中小网络，网络规模太大的话路由信息就无法到达远端路由器了）
初始时每个RIP路由器只有到直连网的路由，距离为1；每30秒RIP路由器把它的整个路由表发给邻居（具体实现时每个邻居会错开发送，30秒的时间也会随机变化一点），成为通告(每次通告最多25个目的子网)。
简述RIP协议的工作原理：路由器每30秒把自己的路由表发给邻居。路由器用邻居发来的路由表根据距离向量算法修改自己的路由表。初始时每个路由器只有到直连网距离为1的路由。
RIP链路失效、恢复：180秒没有收到通告则邻居链路失效，经过该邻居的路由不可用(重新计算路由)，向邻居发送新的通告，邻居再次向外发送通告。毒性逆转技术用于预防乒乓环路。
RIP路由表的处理：利用一个称作route-d的应用层进程进行管理(应用进程实现)；通告报文周期性地通过UDP数据报发送。
（2）开放最短路径优先OSPF协议：公众可用。采用链路状态路由算法，OSPF通告中每个入口对应一个邻居。在这个AS范围泛洪(OSPF数据报直接封装到IP数据报中)，与其极其相似的一个路由协议：IS-IS路由协议。
优点：①安全：所有报文可以被认证②允许使用多条相同费用的路径(RIP智能选一条)③对于每条链路，可以针对不同的TOS设置多个不同的费用度量④集成单播路由与多播路由⑤OSPF支持对大规模AS分层。
两级分层：局部区(Area)，主干区(Backbone).

16.BGP协议——Internet AS间路由协议
边界网关协议BGP：事实上的标准域间路由协议，容许子网向Internet其余部分通告它的存在。eBGP：从邻居AS获取子网可达性信息；iBGP：向所有AS内部路由传播子网可达性信息。
BGP会话：两个BGP路由器交换BGP报文；BGP报文：OPEN与peer建立TCP连接并认证对方、UPDATE通告新路径(或撤销原路径)、KEEPALIVE再无UPDATE时保持连接，也用于对OPEN请求的确认、NOTIFICATION报告先前报文的差错，也用于关闭连接。
为什么采用不同的AS内与AS间路由协议？

例题部分：