计算机网络网络层笔记

路由算法

有连接和无连接

• Virtual circuits【虚电路】 are complete routes that are set up in advance. • Datagrams【分组交换？反正就是发送各种包】 comprise individual packets of which the route is determined on the fly: they hop from router to router

从图到树

每个节点都维护一个汇集树

算法

朴素的：最短路径-就是用图搜索开搜泛洪-向各个方向转发

复杂的:DVR 每个路由器维护一个到其他已知节点的距离，每过一段时间，路由器与周围的路由器交换距离矢量表并更新自己的

link state routing

age = 后面的ttl，seq用来标识不同的包这样

路由算法区别

最短路径和泛洪是朴素的idea，不做总结

DVR和linked state packet的区别是，路由器是否知道全局的链路状态

DVR eg: RIP->低层次网络路由
linked state packet eg : OSPF ->高层次路由；理解为国家/公司维护的路由器算力强

其他的一些关于路由的信息

层次路由：防止路由表表项过多

组播的路由

拥塞控制

两种方案：预防或者通过反馈停止

在虚电路的网络中

在分组交换的子网中

路由器丢弃策略

QoS

保障服务的质量

抖动控制

抖动：分组到达的时间的变化量

流量整形

其他的qos

综合服务 RSVP：资源预留协议

区分服务（Differentiated Services）：区分服务是一种在网络中为不同类型的流提供不同服务质量的方法。它采用了分类和标记的方式来区分流量，并在网络中的路由器上为不同类别的流量应用不同的服务策略。

确保转发：定义优先级和服务级别，然后在加权公平队列里排队

‍

MPLS

本质：instead of having standard routers provide QoS on datagram routing, let them try to establish connections(然后2.5层交换).

采用MPLS的数据包只须在OSI第二层（数据链结层）执行硬件式交换（取代第三层（网络层）软件式路由），它集成了IP选径与第二层标记交换为单一的系统，因此可以解决Internet路由的问题，使数据包传送的延迟时间减短，增加网络传输的速度，更适合多媒体讯息的传送

Internetworking

构建各种网关，连接不同类型的网络。

各层的internetwork设备：  Repeaters at the physical layer for boosting signals.  Bridges/Switches to make the interconnection at the data link layer.  Multi protocol routers for forwarding, and possibly splitting up packets ( bridges can’t do the later).  Transport gateways for coupling byte streams in different networks. 比如：把一个TCP连接和一个SNA连接“粘连”起来  Application gateways, e.g., for handling electronic mail between OSI and TCP/IP networks.

链接虚电路

链接数据报

网络层仅提供数据报服务：不可靠、无序的数据包流。

 虚电路方法 ◼ 可以提前预留缓冲区、分组顺序可以得到保证、可以使用较短的头部，… ◼ 路由器为每个打开的连接使用表空间、无法使用其它路由路径、易受沿途路由器失败的影响 ◼ 连接不可靠数据报网络的话，难以实现串联虚电路  数据报方法 ◼ 可能会拥塞、面对路由器失效有更好健壮性、需要更长的头部，… ◼ 最大优点：可以包含未使用虚电路的子网,性能提升.

【所以这大约是一些idea而不是真正的实现？？？】

隧道

基本思想：当我们假设源和目的地位于同一类型的网络上时，我们可以解决许多网络互连问题。在这种情况下，我们只需要通过中间网络对数据包进行隧道传输。

【通过隧道解决不同类型网络互联的问题】

两级路由算法

内部路由协议和外部路由协议

LAN中的互联网分组→本地多协议路由器→直接下一跳（本地主机\路由器）或是隧道下一跳→ … →目标网络→目标主机

碎片和重组

不同类型的网络允许的包大小也不一样，所以我们可能需要把包切分和重组

问题是怎么重建，因为一个包可能被碎片化若干次甚至丢失

解决方案：丢弃整个数据包。 VS重传丢失的部分。

Internet

终于看到现实生活了

internet : view it as a collection of autonomous systems connected together by a bunch of backbones

layer:

 IP ◼ Addressing ◼ Datagram format ◼ Fragmentation and packet handling  ICMP,ARP,RARP,DHCP… ◼ Error reporting ◼ Signaling  Routing: defining paths and compiling forwarding tables ◼ RIP ◼ OSPF ◼ BGP

IP协议

IP 协议
IP 数据报的格式分为：头 + 正文（也叫有效净荷）。头的格式为：20byte 定长部分 + 变长部分，如下（从左到右，从上到下传输）：
各个字段的意义如下：
版本：协议的版本，目前常用的是 4，也就是 IPv4
IHL：头部长度
服务类型：
（修改前）前 3 位是优先级，后 4 位表示延迟、吞吐量、可靠性、花费哪个最重要，最后 1 位置 0。然而，没人只要要怎么用。
（修改后）前 6 位表示服务类型，后 2 位表示拥塞通知信息。
总长度
标识：确定分段属于哪个数据报
DF：Don’t Fragment
MF：More Fragment 除最后一段，其他段都置 1，用于判断所有段是否都到达。
分段偏移量：该段在数据报中的位置
生存期：一开始设置为 255，每一跳减 1，避免数据包永远逗留在网络中
协议：传输层采用的协议
校验位：将其他字段按 16 位累加取补码，这样接收方将所有字段按 16 位累加的结果为 0.（每一跳都会重新计算）
源地址：后面介绍
目标地址：后面介绍
选项（不介绍）
P.S. 这里有个 Big-endian 的问题需要注意，详情去看：CSDN：大端、小端、与网络字节序和 Tcp/IP 协议

注意，主机和路由器都需要IP地址

IP地址

ABC类地址->已经不再使用

现在用的是子网掩码，一个比较好的解释是这个知乎回答，但是有一说一，怎么用呢

每个 IP 地址由高位的 可变长网络部分（前缀）^^ 和 主机部分 组成。同一网络下的主机有相同的前缀，因此一般用前缀来代表某个子网。为了表明前缀的长度，我们一般在 IP 地址后面加条 /，然后写上前缀的位数（比如上面最后一行的例子）。在路由算法中，会以十进制掩码的形式将前缀长度告知路由器，称为 子网掩码，比如：

IP地址：211.66.11.192/24
子网掩码：255.255.255.0
IP地址 && 子网掩码 = 211.66.11.0 ➡ 前缀

CIDR

基本思想：将剩余的IP地址以可变大小块的方式进行分配，而不管它们所属的类别。意味着”转发”过程变得更为复杂！

CIDR
将一个前缀分为多个子网叫 子网划分，而将多个小前缀的地址合并为一个大前缀的地址叫 路由聚合，这个大前缀有时称为超网。
在分类寻址中，网络大小只能是 A、B、C 中的其中一类，也就是前缀长度只能是 /8、/16、/24，这样会造成空间浪费。
CIDR（Classless Inter Domain Routing，无类域间路由） 的思想很简单，就是前缀可以是任意长度（当然，前缀的前几位始终和上层网络一致）。如果子网前缀分别是 /17、/18、/19 ，那么路由聚合后的超网就取其公共部分（≤16）。
路由器使用子网掩码决定分组往哪个子网转发，路由器采用 “AND” 操作（目的 IP 和子网掩码），得到目的网络地址，使用这种机制，路由器不必记录全部主机的 IP 地址，缩减了路由器的规模。
甚至，前缀允许重叠😳！举个例子，假如一个子网是 192.24.0.0，另一个平行的子网是 192.24.12.0，这时路由器会使用 最长匹配前缀，即尽量匹配最长的子网，假如一个数据包要发给 192.24.12.1，路由器在匹配到 192.24.0.0 后，发现更长的 192.24.12.0 也能匹配，就发给 192.24.12.0。显然，这种算法要求两个子网内的 IP 不能重叠。
由于 CIDR 的掩码可以是任意长度，不再局限于 /8、/16、/24，所以就需要 VLSM（Variable Length Subnet Mask，可变长子网掩码） 。CIDR 和 VLSM 是配合使用的。

【但是这些策略没有复用ip地址，谈何解决ip地址不够的问题呢？ans by AI】

当你有一个大的IP地址空间可用，例如一个类A或类B的地址范围，而你的网络规模相对较小，只需要连接少量主机，使用子网掩码划分子网可以更好地利用有限的IP地址资源，避免浪费。

举例来说，假设你拥有一个类B的IP地址范围，即从172.16.0.0到172.16.255.255，总共包含65536个IP地址。然而，你的网络只需要连接100台主机。如果你直接将所有IP地址分配给这100台主机，绝大多数IP地址将被浪费。

通过使用子网掩码，你可以将IP地址空间划分为多个子网，每个子网只分配所需数量的IP地址，以避免浪费。假设你将子网掩码设置为255.255.255.0，这意味着前24位用于标识网络部分，后8位用于标识主机部分。

现在，你可以将IP地址空间划分为多个子网，每个子网可以容纳256个IP地址。你可以为每个子网分配一个子网地址，例如172.16.0.0、172.16.1.0、172.16.2.0，依此类推。然后，每个子网只使用其中的一部分IP地址，例如172.16.0.1到172.16.0.100。

这样，你就可以将大的IP地址空间划分为多个子网，每个子网只使用所需数量的IP地址，避免了大量的IP地址浪费。同时，你还可以为不同的子网应用不同的网络策略和安全设置，更好地管理和组织你的网络。

NAT

为在特殊路由器（也可以充当防火墙）后面运行的本地网络应用一些地址，并仅允许传出连接

Example: When a connection is set up from address 10.0.0.1, port X, the router sends it off using source address 198.60.42.12 (its ISP-supplied address) on port Y, and registers the mapping X<-→Y. when a reply comes in for port Y, it is sent back to 10.0.0.1 on port X

NAT
如果子网内的 IP 不够咋办？一种解决方法是动态分配 IP，只分配给活跃的客户端，但如果所有客户端都活跃咋办？这就需要 NAT（Natwork Address Translation，网络地址转换）
NAT 的思想很简单，几个人共用一个 IP 就好啦～对外都是同一个 IP 地址，对内则用另一套 IP 地址来区分不同客户端，然后通过 NAT 盒来进行转换。
对内使用的 IP 地址有三种：
10.0.0.0 ~ 10.255.255.255/8
172.16.0.0 ~ 172.16.255.255/12
192.168.0.0 ~ 192.168.255.255/16
宿舍 / 家里用的 WiFi 用的就是 NAT，一般家用 WiFi 可支持的终端数比较少，所以一般用的是第三种（你可以在手机的 WiFi 设置界面中看到 192.168 开头的 ip 地址）。
那两个 IP 地址如何转换呢？这时我们就要利用上层网络 —— 传输层，传输层中用端口号来区分不同应用的传输。于是 NAT 盒就将内部 ip + 端口号映射到真实 ip + 端口号，从而实现网络地址转换。
这种映射每次都会变的，如果想要固定，必须手动设置端口映射。

ICMP

 基本思想：我们需要在什么时候通知主机和路由器出现问题，或者同样应该能够发送查询获取状态信息。将控制消息封装在正常的IP数据报。

【我并不知道这个会不会深入细节，下面是小林coding的解释】

# ICMP
ICMP 全称是 Internet Control Message Protocol，也就是互联网控制报文协议。
里面有个关键词 —— 控制，如何控制的呢？
网络包在复杂的网络传输环境里，常常会遇到各种问题。
当遇到问题的时候，总不能死个不明不白，没头没脑的作风不是计算机网络的风格。所以需要传出消息，报告遇到了什么问题，这样才可以调整传输策略，以此来控制整个局面。
ICMP 功能都有啥？
ICMP 主要的功能包括：确认 IP 包是否成功送达目标地址、报告发送过程中 IP 包被废弃的原因和改善网络设置等。
在 IP 通信中如果某个 IP 包因为某种原因未能达到目标地址，那么这个具体的原因将由 ICMP 负责通知。

如上图例子，主机 A 向主机 B 发送了数据包，由于某种原因，途中的路由器 2 未能发现主机 B 的存在，这时，路由器 2 就会向主机 A 发送一个 ICMP 目标不可达数据包，说明发往主机 B 的包未能成功。
ICMP 的这种通知消息会使用 IP 进行发送。
因此，从路由器 2 返回的 ICMP 包会按照往常的路由控制先经过路由器 1 再转发给主机 A 。收到该 ICMP 包的主机 A 则分解 ICMP 的首部和数据域以后得知具体发生问题的原因。
ICMP 类型
ICMP 大致可以分为两大类：
一类是用于诊断的查询消息，也就是「查询报文类型」
另一类是通知出错原因的错误消息，也就是「差错报文类型」

ARP

通过IP地址寻找MAC地址的方法

‍

这里说的是路由器？这部分咋越看越复杂

wiki百科上的细节。但是这个协议和router到底有啥关系

在以太网中，IP数据包又是被封装在以太网帧中，经过物理层(也就是网卡)发送到网络上，以太网帧又是根据MAC地址来寻址到目的机器的网卡的(局域网中的所有机器的网卡都会接收到这个帧，而只有该帧头部中的目的MAC地址与自己网卡的MAC地址匹配时，才会向网络协议栈交付该帧中的数据包，否则网卡就会丢弃该帧)。因此，同一局域网中的一台主机要和另一台主机或者交换机，路由器等进行网络通信时，必须要知道与本机用网线连接上的，目标设备那边的那个网络接口的MAC地址(也就是网卡的地址)。这就导致在以太网中使用IP协议向下传递IP包时，IP包被包含在以太网帧中，以太网帧是有自己的格式的，在帧头部就需要填充目的机器MAC地址，而此时从ARP表里面没有查询到目的ip地址对应的MAC地址，因此主机会暂存这个ip数据包，由于主机刚连接到这个局域网时或者重启之后，是不知道目的方的MAC地址的，如果要向目的机器发送一个ip包，就需要先知道目的机器的MAC地址，于是需要一种方法，根据目的主机的IP地址，获得其MAC地址，这个方法就是通过发送一个叫做arp请求的数据包(arp数据包也是被包含在以太网帧中的，发送时，帧头部中的目的mac地址填写为0xffffffff，表示在本地局域网上广播，这样属于该局域网的所有机器接收到一个广播帧的时候都会向协议栈递交这个帧中的数据包，这里是arp数据包)广播到该局域网中，而仅当某台机器的IP地址与该arp请求中的要询问的ip地址相同时，那台机器就才会向发送方返回一个arp回应数据包，这个回应包中就包含了先前要询问的机器的IP地址 + MAC地址，本地主机接收到这个回应的arp数据包后，会提取ip地址和mac地址，记录到一个叫做arp的表的表项中，这样就把目的主机的ip地址和mac地址对应关系记录下来了，随即找到先前由于缺少目的mac地址而暂存的数据包，并用以太网帧封装它，用该arp表项中的mac地址来填充帧头部中的MAC地址域，当这个帧被发送到局域网中之后，目标机器网卡接收到这个帧之后，判断该MAC地址和自己的MAC地址相同，就会向上层协议栈递交这个帧中的数据包，从而数据得以交付，而其他主机检测到MAC地址与本机不同，会把这个帧丢弃。这就是ARP协议要做的事情。

另外，当发送主机和目的主机不在同一个局域网中时，即便知道对方的MAC地址，两者也不能直接通信，必须经过路由器进行ip层的转发才可以，因为路由器把这个局域网进行了链路层上的隔离(除非进行网络层次的显示转发，否则路由器不会把一个局域网中的以太网帧自动的转发到另一个局域网或者外网中去，如果可以自动转发，可以想象有多可怕，无效的广播帧可能像洪水一样淹没整个网络，使得网络瘫痪，这也就是路由器的基本功能之一，隔离网络)，所以此时，发送主机会把一个网关ip地址作为目的ip地址(这个是ip层决定的)，那么通过ARP协议获得的将不是目的主机的真实MAC地址，而是一台可以通往局域网外的路由器的MAC地址。于是此后发送主机发往目的主机的所有帧，都将发往该路由器，通过它向外发送。这种情况称为委托ARP或ARP代理（ARP Proxy） 。

RARP

解决主机如何知道自己的地址的问题：它广播自己的 MAC 地址，并请求知道自己的 IP 地址

现实生活的网络和层次路由

现实生活的网络极度复杂，所以我们需要层次路由！

 今天的互联网是按 AS 组织的 ◼ 独立的管理域 ◼ 网关路由器将一个AS 与其他AS 连接起来。

 基本思想：区分路由中的路由自治系统，以及自治系统之间： ◼ AS 内路由涉及从以下位置获取数据包源头到目的地。它应该尽可能地做到这一点（最佳路由）-> 内部网关路由。 • 例如，RIP（距离矢量）主要用于低层IPS 和小型企业; OSPF（链路状态）由一级 ISP 使用。 ◼ AS 间路由必须处理很多政治问题。例如，某些 AS 根本不应该被遍历，而有些不接受“外国”数据包。外部的网关路由。 • BGP 是互联网标准。