dream

一个菜鸟程序员的成长历程

0%

发表于 更新于 分类于 阅读次数： Valine：

数据链路层CRC(循环冗余码)差错校验码详解

CRC差错校验码是数据链路层用来进行差错校验的一个码。

CRC编码过程

假设要编码的数据D，有d个比特，发送节点要将它发送给接收节点。发送方和接收方要先协商一个r + 1比特模式，成为生成多项式。我们将其表示为G。我们将要求G的最高有效位（最左边）的比特是1。

我们要有一个数据D，比如 1001
这个数据有d个比特，也就是4个比特
需要附加 r 个比特作为校验码 R
编码过后会变成数据会变成D + R
数据有d + r个比特
使得得到的数据D+R进行模2运算恰好能被G整除

CRC差错检测过程

接收方用G去除接收到的D+R数据，如果余数为非0，则有差错，如果余数为0，则无差错

CRC计算

所有CRC计算采用模2算术来做，在加法中不进位，在减法中不借位。这意味着加法和减法是相同的，而且这两种操作等价于异或（XOR）操作。

1011 XOR 0101 = 1110

异或操作：不同的为1，相同为0。也就是0 XOR 0 = 0,1 XOR 1 = 0,0 XOR 1 = 1。

乘法和除法是相同的。

给定D 和 R, D * 2r XOR R就等于 D + R数据。

如何计算R

我们要求出R使得对于n有：
D * 2r XOR R = nG

也就是说，我们要选择 R 使得G能除 D * 2r XOR R 而没有余数。如果对上面的等式两边都 XOR R.

D * 2r = nG XOR R

根据上面的等式可以得出，如果我们用G 除 D * 2r，余数刚好是R

R = remainder (D * 2r / G)

也就是使用D * 2r去除以 G。余数就是R。

如何计算G

G 作为多项式，有两种写法，一种是x2 + x + 1的写法，一种是二进制写法 111。

我们需要用 D * 2r 除以 G 。所以我们需要求出G的二进制写法，才能做除法运算。

这个转换的方法：

  1. 首先把末尾的1看成x0，也就是x的0次幂
  2. 这样提取出x的所有幂
  3. 对应幂的位置填1，如果没有对应幂的位置则填0
转换例子1

G = x4 + x + 1

提取出来的幂分别是 4,1,0。
没有的幂是3,2。
在对应的位置填上1或0。
4 3(无) 2(无) 1 0
1 0 0 1 1
这个G的二进制就是 10011。

其实很简单，0次幂对应个位，1次幂对应十位，一直往上加就行了，有1次幂十位就是1，没有就是0.

转换例子2

G = x6 + x4 + x2 + 1

6 5(无) 4 3(无) 2 1(无) 0
1 0 1 0 1 0 1

对应的二进制就是 1010101

计算CRC编码

给定 D = 101110, G = 1001, d = 6, r = 3。计算D的CRC编码后的数据

首先求R。

用D/G可以得出结果为101011，余数为011，余数就是R。

然后把R放到D后面。

编码后就是 101110 011

发表于 更新于 分类于 阅读次数： Valine：

网络层

网络层核心功能：转发与路由

转发：将分组从路由器的输入端口转移到合适的输出端口

转发表确定在本路由器如何转发分组

路由：确定分组从源到目的经过的路径。

  • 路由算法：确定通过网络的端到端路径。

某些网络的重要功能：连接建立

数据分组传输前需要建立连接，和运输层不一样的是所有网络设备路由器都会参与建立连接。

网络层是两个主机建立连接

运输层是两个应用进程建立连接

无连接服务

  • 不事先为分组确定传输路径
  • 每个分组独立路径
  • 不同分组可能传输路径不同
  • 数据报网络

连接服务：

  • 首先为分组确定传输路径
  • 沿这个路径传输
  • 系列分组传输路径相同
  • 传输结束后拆除
  • 虚电路网络

数据报网络和虚电路网络是典型两类分组交换网络。

类似UDP和TCP。但是网络层是主机到主机.网络核心实现.

虚电路

一条从源主机到目的主机，类似于电路的路径。

  • 分组交换
  • 每个分组的传输利用链路的全部带宽
  • 源主机到目的主机的所有网络设备完成虚电路连接和功能

通信过程：

  • 呼叫建立（call setup） -》 数据传输 -》 拆除呼叫
  • 每个分组携带虚电路标识（VC ID），而不是目的主机地址
  • 虚电路经过的每个网络设备，维护每条经过他的虚电路连接状态
  • 链路，网络设备资源可以面向VC进行预分配
    • 预分配资源 = 可预期服务性能
    • 如ATM的电路仿真（CBR）

每条虚电路包括：

  • 从源主机到目的主机的一条路径
  • 虚电路号（VCID），沿路每段链路一个编号
  • 沿路每个网络层设备，利用转发表记录经过的每条虚电路

分组携带虚电路号VCID，而不是目的地址。
同一条VC,在每段链路上的VCID通常不同。

  • 路由器转发分组时依据转发表改写/替换虚电路号
虚电路信令协议

用于VC的建立，维护与拆除

  • 路径选择

应用于虚电路网络

  • 如ATM

目前的internet不采用

数据报网络

  • 无连接
  • 每个分组携带目的地址
  • 路由器根据分组的目的地址转发分组
    • 基于路由协议/算法构建转发表
    • 检索转发表
    • 每个分组独立选路
  • Internet网络是数据报网络
  • 路由算法
    • 根据地址范围进行转发
    • 最长前缀匹配优先

对比

Internet(数据报网络)

  • 计算机之间的数据交换
    • 弹性服务，没有严格要求
  • 链路类型众多
    • 特点性能各异
    • 同一服务困难

ATM(虚电路网络)

  • 电话网络演变而来
  • 核心业务是实时对话
    • 严格的时间，可靠性需求
    • 需要有保障的服务
  • 非智能端系统
    • 电话机
    • 传真机

IP协议

路由协议

  • 路径选择
  • RIP OSPF BGP

IP协议

  • 寻址规约
  • 数据报格式
  • 分组处理规约

ICMP协议

  • 差错报告
  • 路由器“信令”

IP数据报

  • 首部
    • 版本号 4比特 ipv4就是4
    • 首部长度 4比特 首部的长度，以4字节为单位 默认是5 表示20字节
    • 服务类型 8比特 期望获得哪种类型的服务 只有在网络提供区分服务时使用 通常是0
    • 总长度 16比特 IP数据报的长度（首部 + 数据），以字节为单位， 最大IP分组总长度 65535B 最小分组首部 20B IP分组数据最大可以是 65515B
    • 标识 16比特 ID，计数器+1
    • 标志位 3比特 保留1比特 DF = 1禁止分片 0 允许分片 MF = 1非最后一片 0 最后一片或未分片
    • 片偏移 13比特 IP分组分片封装原IP分组数据的相对偏移量 以8字节为单位
    • 生存时间 8比特 IP分组在网络中可以通过的路由器数（跳步数）
    • 协议 8比特 指示IP分组封装的是哪个协议的数据包 6是TCP或者17是UDP
    • 首部校验和 16比特 IP分组首部的差错检测 逐步计算
    • 源IP地址 32比特
    • 目的IP地址 32比特
    • 选项字段 变长 范围 1 - 40B 携带安全，源选路径，时间戳和路由记录等内容 实际很少被使用
    • 填充字段 变长 范围 0 - 3B 补齐整个首部，保证32位对齐
  • 数据

IP分片

链路最大数据单元MTU。如果现在的IP分组大于下个链路的MTU就可以进行分片。

  • 如果进行分片就分片，然后重组
  • 如果不可以分片则丢弃分组

分片过程：
假设IP分组长L，带转发MTU为M
若L > M且DF = 0,则可以分片
分片时每个分片的标识复制原IP分组的标识
通常分片时，除最后一个分片，都为MTU允许的最大分片
一个最大分片可封装的应该是 8 的倍数。
d = M - 20 / 8 * 8
n = L - 20 / d
分片偏移量
Fi = d / 8 * (i - 1)
每片总长度
d + 20
最后一个
L - （n - 1）d

IP编址

32比特（IPv4） 11011111 00000001 00000001 00000001 = 233.1.1.1
IP地址与每个接口关联

  • 网络号：高位比特
  • 主机号：低位比特

IP子网

IP子网：

  • IP地址具有相同的网络号
  • 不跨越路由器可以彼此物理联通
  • 233.1.1.0/24

有类编址
A类地址：

  • 网络号 8比特 主机号 24比特 50% 0.0.0.0 - 127.255.255.255
    B类地址：
  • 网络号 16比特 主机号 16比特 25% 128.0.0.0 - 191.255.255.255
    C类地址：
  • 网络号 24比特 主机号 8比特 12.5% 192。0.0.0 - 223.255.255.255
    D类地址：
  • 6.25% 224.0.0.0 - 239.255.255.255
    E类地址：
  • 6.25% 240.0.0.0 - 255.255.255.255

私有IP地址：

  • A类：网络号10开头的 10...*
  • B类：172.16 - 172.31 16个
  • C类：192.168.0 - 192.168.255

IP地址：

  • 网络号：高位比特
  • 子网号：原主机号的部分
  • 主机号：地位比特

子网掩码：网络号和子网号取255，主机号取0

  • A类网络子网掩码 255.255.255.0

子网地址 + 子网掩码 = 准确确定子网大小

例子：

子网 201.2.3.0 子网掩码 255.255.255.0，划分为4个等长的子网。

  • 201.2.3.0 = 201.2.3.00000000 255.255.255.11000000 = 255.255.255.192
  • 201.2.3.64 = 201.2.3.01000000 255.255.255.11000000 = 255.255.255.192
  • 201.2.3.128 = 201.2.3.10000000 255.255.255.11000000 = 255.255.255.192
  • 201.2.3.192 = 201.2.3.11000000 255.255.255.11000000 = 255.255.255.192

将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址。
目的IP:172.32.1.112 = 10101100.00100000.00000001.01110000
子网掩码：255.255.254.0 = 11111111.11111111.11111110.00000000
子网地址：10101100.00100000.00000000.00000000 = 172.32.0.0
地址范围：172.32.0.0 - 172.32.1.255
可分配地址范围：172.32.0.1 - 172.32.1.254
广播地址：172.32.1.255

CIDR与路由聚合

无类域间路由CIDR

  • 消除传统的A类，B类，C类地址划分
  • 网络号 + 子网号 = 网络前缀 可以任意长度
  • 融合子网地址和子网掩码，方便子网划分
    • 无类地址格式：a.b.c.d/x 其中x为网络前缀长度
  • 提高IPv4地址空间分配效率
  • 提高路由效率
    • 将多个子网构成一个大的子网
    • 构造超网
    • 路由聚合

例如：
前23位是网络前缀，后9位是主机号
11001000 00010111 00010000 00000000
200.23.16.0/23

11001000.00010111.00010010.00000000
200.23.18.0/23

11001000.00010111.00010100.00000000
200.23.20.0/23
聚合成超网：
11001000 00010111 00010000 00000000
200.23.16.0/20

如果有一个子网不在也没事，路由记录两条信息。根据最长前缀匹配优先。不会出错。

DHCP

动态分配路由协议：
客户：DHCP discover

  • src:0.0.0.0:68
  • dest:255.255.255.255:67 广播
  • yiaddr:0.0.0.0
  • transactionID:654

DHCP服务器：DHCP offer

  • src:223.1.2.5:67 DHCP服务器的IP
  • dest:255.255.255.255:68 广播
  • yiaddr:223.1.2.4 分配的IP
  • transactionID:654
  • lifetime:3600 secs

客户：DHCP req

  • src:0.0.0.0:68
  • dest:255.255.255.255:67 广播
  • yiaddr:223.1.2.4 分配的IP
  • transactionID:655
  • lifetime:3600 secs

DHCP服务器：DHCP ACK

  • src:223.1.2.5:67 DHCP服务器的IP
  • dest:255.255.255.255:68 广播
  • yiaddr:223.1.2.4 分配的IP
  • transactionID:655
  • lifetime:3600 secs

网络地址转换NAT

子网使用一个公共IP。发送网络数据的时候路由器替换源IP地址。

动机：

  • 只需从ISP申请一个IP地址
    • IPv4地址耗尽
  • 本地网络地址是私有的，局部的，IP地址变更根外界没有影响
  • 变更ISP时候，无需修改内部网络IP
  • 内部网络设备对外界网络不可见，更加安全

实现：

  • 替换
    • 利用（NAT IP地址，新端口号）替换每一个外出IP数据报的（源IP地址，源端口号）
  • 记录
    • 将每对（NAT IP地址，新端口号）和（源IP地址，源端口号）记录在NAT转换表中
  • 替换
    • 根据NAT转换表，利用（源IP地址，源端口号）替换（NAT IP地址，新端口号）

发表于 更新于 分类于 阅读次数： Valine：

数据链路层

负责通过一条链路从一个节点向另一个物理链路直接相连的相邻节点传送数据报

组帧

  • 封装数据报，加首部和尾部
  • 帧同步

链路接入

  • 如果是共享介质，需要解决信道接入
  • 帧首部的MAC地址，用于标识帧的源和目的，不同于IP地址

相邻节点间可靠交付

  • 在低误码率的有线链路上很少采用（如光纤，某些双绞线）
  • 无线链路：误码率高，需要可靠交付

流量控制

  • 协调相邻的发送和接受

差错检测

  • 信号衰减和噪声会引起差错
  • 接收端检测到差错
    • 通知发送端重传或丢弃

差错纠正

  • 接收端直接纠正比特差错

全双工和半双工通信控制

  • 全双工:链路两端节点同时双向传输数据
  • 半双工：链路两端节点交替双向传输数据

差错检测：差错编码

差错编码基本原理：
D -> DR ，其中R为差错检测与纠正比特

差错编码分为检错码和纠错码
对于检错码：如果编码集的汉明距离ds = r + 1，则可以检测r位的错误
对于纠错码：ds = 2r + 1则可以检测r位的错误

MAC协议

两类链路

点对点链路

  • 拨号接入的PPP
  • 以太网交换机与主机间的点对点链路

广播链路（共享介质）

  • 早期的总线以太网
  • HFC的上行链路
  • 802.11 无线网

单一共享广播信道

  • 两个或者两个以上节点同时传输：干扰
  • 冲突：节点同时接收到两个或者多个信号 =》 接收失败

多路访问控制协议MAC解决这些问题：

  • 采用分布式算法决定节点如何共享信道，及决策节点何时可以传输数据
  • 必须基于信道本身，通信信道共享协调信息
    • 无带外信道协调

理想MAC协议

给定：速率为R bps的广播信道
期望：

  1. 当只有一个节点希望传输数据时，他可以以速率R发送
  2. 当有M个节点发送，每个节点R/M速率
  3. 完全分散控制
    • 无需特定节点协调
    • 无需时钟、时隙同步
  4. 简单

MAC协议分类

三大类：

  • 信道划分MAC协议
    • 多路复用
    • TDMA,FDMA,CDMA,WDMA等
  • 随机访问MAC协议
    • 信道不划分，允许冲突
    • 采用冲突恢复机制
  • 轮转MAC协议
    • 节点轮流使用信道
随机访问MAC协议

发送时候使用信道全部速率

需要定义：

  • 如果检测冲突
  • 如何从冲突恢复（通过延迟重传）

典型的协议

  • 时隙 ALOHA
  • ALOHA
  • CSMA CSMA/CD CSMA/CA
时隙 ALOHA

假定：

  • 所有帧大小相同
  • 时间被划分为等长的时隙
  • 节点只能在时隙开始时刻发送数据
  • 节点间时钟同步
  • 如果2个或2个以上节点在同一时隙发送帧，节点就检测到冲突

运行：

  • 当节点有新的帧时，在下一个时隙发送
    • 无冲突：发送成功
    • 冲突：节点在下一个时隙以概率P重传该帧，直至成功

优点：

  • 单个节点活动时，可以连续以信道全部速率发送
  • 高度分散化：只需同步时隙
  • 简单

缺点：

  • 冲突，浪费时隙
  • 空闲时隙
  • 节点也许能以远小于分组传输时间检测到冲突

最大效率0.37

ALOHA

非时隙，更简单，无需同步
当有新的帧，立即发送
冲突可能增大

最大效率0.18

CSMA

载波监听多路访问协议

  • 发送帧之前，监听信道（载波）
    • 信道空闲：发送完整帧
    • 信道忙：推迟发送
      • 1-坚持CSMA 一直监听信道
      • 非坚持CSMA 随机等待一段时间再监听信道
      • P-坚持CSMA 以概率P监听信道，概率1-P不监听信道

冲突仍可能发生：

  • 信号传播延迟

继续发送冲突帧：浪费信道资源

CSMA/CD

带有冲突检测的载波监听多路访问协议

  • 短时间内可以检测到冲突
  • 冲突后传输中止，减少信道浪费

运行：

  1. 适配器从网络获取一条数据报，准备链路层帧，并放入帧适配器缓存中。
  2. 如果适配器侦听到信道空闲（即无信号能量从信道进入适配器），他开始传输帧。另一方面，如果适配器侦听到信道正在忙，他将等待，直到侦听到没有信号能量时才开始传输帧。
  3. 在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。
  4. 如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成了该帧。另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，他中指传输（即他停止了传输帧）
  5. 中止传输后，适配器等待一个随机时间量，然后返回步骤2.
    • 等待一个随机（而不是固定）的时间量的需求是明确的–如果两个结点同时传输帧，然后这两个结点等待相同固定的时间量，他们将持续碰撞下去。但选择随机回退时间的时间间隔多大为好呢？如果时间间隔大而碰撞结点数量小，在重复“侦听-当空闲时传输”的步骤前。

冲突检测

  • 有线局域网易于实现：测量信号强度，比较发射信号与接收信号
  • 无线信号很难实现：接收信号强度淹没在本地发射信号强度下

边发送边监听，不发送就不监听

网络带宽：R bps
数据帧最小长度：Lmin(bits)
信号传播速度：V(m/s)
信道长度：Dmax

满足：
L /R >= 2 Dmax / V
Lmin / R = 2 Dmax / V
Lmin / R = RTT max

远优于ALOAH，并且简单，分散。

轮转MAC

轮询：

  • 主节点轮流“邀请”从属节点发送数据
  • 典型应用：
    • “哑”从属设备

优点：

  • 不会冲突
  • 使用全部带宽

问题：

  • 轮询开销
  • 等待延迟
  • 单点故障
令牌传递

控制令牌依次从一个节点传递到下一个节点
令牌：特殊帧
获取令牌才可以发送数据

优点：

  • 不会冲突
  • 使用全部带宽

缺点：

  • 令牌开销
  • 等待延迟
  • 单点故障
MAC协议总结

信道划分协议：
优点：网络负载高，利用率高，性能高
缺点：网络负载低，利用率低，性能低

随机访问MAC协议：
优点：网络负载低，利用率高，性能高
缺点：网络负载高，会冲突

轮转MAC:
主节点轮询：令牌传递
结合两者优点，不是最好也不是最坏

发表于 更新于 分类于 阅读次数： Valine：

网络原理自顶向下三可靠数据传输原理实现GBN滑动窗口协议

在GBN中，允许发送方发送多个分组而不需等待确认，但它也受限于在流水线中未确认的分组数不能超过某个最大允许数N。

我们需要

  • base 基序号 最早未确认分组的序号
  • nextSeqNum下一个序号 最小的未使用序号

则可以将序号范围分割成四段

  • 0 至 base - 1 已经发送并被确认的分组
  • base 至 nextSeqNum - 1 已经发送没有被确认的分组
  • nextSeqNum 至 base + N - 1 可以被发送的分组序号
  • base + N 至 无穷大 不能使用的序号

已经被发送的可以但未被确认的可以看成是一个在序号范围内长度为N的窗口。随着协议允许，窗口往前滑动。因此N常被成为窗口长度，GBN协议也被称为滑动窗口协议

发送端

GBN的发送方必须响应三种类型的事件

  • 上层的调用。检测有没有可以使用的序号，如果有就发送。
  • 收到ACK。GBN使用累计确认。即收到的N之前的全部确认。
  • 超时事件。如果出现超时，就重传所有已发送未确认的分组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//序号
$base = 1;
$nextSeqNum = 1;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet[$nextSeqNum] = make_pkt($data, $checkSum, $nextSeqNum);
    //调用网络层传输 
    udt_send($packet[$nextSeqNum]);
    //只启动一个定时器
    if ($base == $nextSeqNum) {
        start_timer();
    }
    //如果超时
    if (timeout()) {
        //重传所有已发送的分组
        for ($i = $base; $i <= $nextSeqNum - 1; $i++) {
            udt_send($packet[$i]);
        }
    } else if ($isAck = rdt_rev() && check($isAck)) {
        //等待接收方回传ack 并且没有出现错误
        //获取确认的序号
        $ackNum = getAckNum($isAck);
        //确认这个序号之前所有的分组
        $base = $ackNum;
        //如果确认了最新的分组，那么停止定时器
        if ($base == $nextSeqNum) {
            stop_timer();
        } else {
            start_timer();
        }
    }
}

接收端

GBN的接收端较为简单，因为接收端只需要按序号交付数据就可以了。如果数据没有按序到达接收端，接收端只需要直接丢弃，因为发送端会重传所有分组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//期望的序号
$expackNum = 1;
function rdt_rev($packet) {
    //差错检测通过了并且报文序号正确
    if (check($packet) && $packet['num'] == $expackNum) {
        //解析报文
        $data = extract($packet);
        //序号对的
        //没有错，把数据交付给应用层并回传ack
        //把数据给应用层
        deliver_data($data);
        //回传ACK
        $ack = make_pkt(1, $expackNum);
        $expackNum++;
        udt_send($ack);
    } else {
        //没通过差错检测或者序号错误，我们回传一个上一个ack，告诉发送端上一个分组我们收到了，当前分组没收到。
        //回传ACK
        $ack = make_pkt(1, $expackNum);
        udt_send($ack);
    }
}

SR

在SR中，和GBN不同，SR是给每一个分组设置定时器，发送端只确认重传当前分组，而不是所有分组。接收端在接收到乱序的分组的时候会进行缓存，当前面的分组到达以后一起提交给应用层。

发送端

  • 等待上层调用。这里和GBN一样
  • 超时。超时哪个重传哪个
  • 收到ACK。如果收到的是最小序号的ACK，那么base可以往前移动，也就是窗口滑动。如果收到其他序号的ACK。那么把这些ACK缓存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//序号
$base = 1;
$nextSeqNum = 1;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet[$nextSeqNum] = make_pkt($data, $checkSum, $nextSeqNum);
    //调用网络层传输 
    udt_send($packet[$nextSeqNum]);
    //每个启动一个定时器
    start_timer($nextSeqNum);    
    //如果超时
    if ($timeNum = timeout()) {
        //重传超时的分组
        udt_send($packet[$timeNum]);
    } else if ($isAck = rdt_rev() && check($isAck)) {
        //等待接收方回传ack 并且没有出现错误
        //获取确认的序号
        $ackNum = getAckNum($isAck);
        stop_timer($ackNum);
        //判断这个ACK是不是base
        if ($ackNum == $base) {
            ++$base;
            //判断缓存有没有
            while(array_key_exists(++$ackNum, $cache)) {
                //如果下一个ack已经收到了，那么就把base接着往前移动
                ++$base;
            }
        } else {
            //缓存起来
            $cache[$ackNum] = $ackNum;
        }
    }
}

接收端

  • 序号在rcv_base 至 rcv_base + N - 1内的分组被正确接受。如果该分组不是期望的分组，那么缓存，如果是，那么给应用层并且看缓存里面有没有后续，有就直接一起给应用层
  • 序号在rcv_base - N 至 rcv_base - 1内的分组被正确接受。返回一个确认ACK。表示我已经收到了。
  • 其他情况。忽略分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//期望的序号
$expackNum = 1;
function rdt_rev($packet) {
    //差错检测通过了并且报文序号正确
    if (check($packet)) {
        if ($packet['num'] > $expackNum && $packet['num'] < $expackNum + N - 1) {
            if ($packet['num'] == $expackNum) {
                //是我们期望的，直接给应用层
                //解析报文
                $data = extract($packet);
                //序号对的
                //没有错，把数据交付给应用层并回传ack
                //把数据给应用层
                deliver_data($data);
                //回传ACK
                $ack = make_pkt(1, $expackNum);
                $expackNum++;
                udt_send($ack);
                //查询缓存里面有没有
                $key = $expackNum + 1;
                while(array_key_exists($key, $cache)) {
                    //如果下一个分组已经收到了，那么给应用层，并且滑动窗口
                    deliver_data($cache[$expackNum]);
                    ++$expackNum;
                    $key++;
                }   
            } else {
                //缓存分组
                $cache[$packet['num']] = $packet;
                //回传ACK
                $ack = make_pkt(1, $packet['num']);
                udt_send($ack);
            }
        }
    } else {
        //没通过差错检测或者序号错误，我们回传一个上一个ack，告诉发送端上一个分组我们收到了，当前分组没收到。
        //回传ACK
        $ack = make_pkt(1, $expackNum);
        udt_send($ack);
    }
}

发表于 更新于 分类于 阅读次数： Valine：

网络原理自顶向下三可靠数据传输原理实现SR选择重传协议

SR

在SR中，和GBN不同，SR是给每一个分组设置定时器，发送端只确认重传当前分组，而不是所有分组。接收端在接收到乱序的分组的时候会进行缓存，当前面的分组到达以后一起提交给应用层。

发送端

  • 等待上层调用。这里和GBN一样
  • 超时。超时哪个重传哪个
  • 收到ACK。如果收到的是最小序号的ACK，那么base可以往前移动，也就是窗口滑动。如果收到其他序号的ACK。那么把这些ACK缓存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//序号
$base = 1;
$nextSeqNum = 1;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet[$nextSeqNum] = make_pkt($data, $checkSum, $nextSeqNum);
    //调用网络层传输 
    udt_send($packet[$nextSeqNum]);
    //每个启动一个定时器
    start_timer($nextSeqNum);    
    //如果超时
    if ($timeNum = timeout()) {
        //重传超时的分组
        udt_send($packet[$timeNum]);
    } else if ($isAck = rdt_rev() && check($isAck)) {
        //等待接收方回传ack 并且没有出现错误
        //获取确认的序号
        $ackNum = getAckNum($isAck);
        stop_timer($ackNum);
        //判断这个ACK是不是base
        if ($ackNum == $base) {
            ++$base;
            //判断缓存有没有
            while(array_key_exists(++$ackNum, $cache)) {
                //如果下一个ack已经收到了，那么就把base接着往前移动
                ++$base;
            }
        } else {
            //缓存起来
            $cache[$ackNum] = $ackNum;
        }
    }
}

接收端

  • 序号在rcv_base 至 rcv_base + N - 1内的分组被正确接受。如果该分组不是期望的分组，那么缓存，如果是，那么给应用层并且看缓存里面有没有后续，有就直接一起给应用层
  • 序号在rcv_base - N 至 rcv_base - 1内的分组被正确接受。返回一个确认ACK。表示我已经收到了。
  • 其他情况。忽略分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//期望的序号
$expackNum = 1;
function rdt_rev($packet) {
    //差错检测通过了并且报文序号正确
    if (check($packet)) {
        if ($packet['num'] > $expackNum && $packet['num'] < $expackNum + N - 1) {
            if ($packet['num'] == $expackNum) {
                //是我们期望的，直接给应用层
                //解析报文
                $data = extract($packet);
                //序号对的
                //没有错，把数据交付给应用层并回传ack
                //把数据给应用层
                deliver_data($data);
                //回传ACK
                $ack = make_pkt(1, $expackNum);
                $expackNum++;
                udt_send($ack);
                //查询缓存里面有没有
                $key = $expackNum + 1;
                while(array_key_exists($key, $cache)) {
                    //如果下一个分组已经收到了，那么给应用层，并且滑动窗口
                    deliver_data($cache[$expackNum]);
                    ++$expackNum;
                    $key++;
                }   
            } else {
                //缓存分组
                $cache[$packet['num']] = $packet;
                //回传ACK
                $ack = make_pkt(1, $packet['num']);
                udt_send($ack);
            }
        }
    } else {
        //没通过差错检测或者序号错误，我们回传一个上一个ack，告诉发送端上一个分组我们收到了，当前分组没收到。
        //回传ACK
        $ack = make_pkt(1, $expackNum);
        udt_send($ack);
    }
}

发表于 更新于 分类于 阅读次数： Valine：

网络原理自顶向下三可靠数据传输原理实现停等协议

这里仅考虑单向可靠数据传输。而不是双向可靠数据传输。

构造可靠数据传输协议

经完全可靠信道的可靠数据传输 rdt1.0版本

首先考虑最简单的版本，底层信道完全可靠。

发送端

发送端应用层只需要调用rdt_send函数。网络层提供了一个函数udt_send来给运输层调用。现在假设udt_send是可靠的。

1
2
3
4
5
6
function rdt_send($data) {
    //组装报文
    $packet = make_pkt($data);
    //调用网络层传输
    udt_send($packet);
}

接收端

接收端网络层只需要调用rdt_rev函数。应用层提供了一个deliver_data函数来接受运输层的数据。

1
2
3
4
5
6
function rdt_rev($packet) {
    //解析报文
    $data = extract($packet);
    //把数据给应用层
    deliver_data($data);
}

有限状态机

再来画一下对应的有限状态机（FSM）.

发送端只有一个状态，等待调用。

接收端也只有一个状态，等待调用。

经比特差错信道的可靠数据传输rdt2.0

现在底层信道有可能造成比特的错误。

回想一下打电话的时候，如果我们说的话对方没听清，会怎么样。会再说一遍也就是重传。

那么什么情况下会重传。当接收方说我没听清的时候。

所以在rdt2.0里面我们让接收方接受完信息后回传一个标志，告诉我们正确还是错误。

如果正确，那么我们继续等待调用。

如果错误，那么我们重传。

基于这样重传机制的可靠数据传输协议称为自动重传请求协议（Automatic Repeat reQuest）ARQ,需要下面三个功能

  • 差错检测
  • 接收方回传ack或者nak
  • 重传

发送端

看一下发送端的简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet = make_pkt($data, $checkSum);
    //调用网络层传输 
    udt_send($packet);
    //等待接收方回传ack或者nak
    $isAck = rdt_rev();
    //判断ack
    if ($isAck == 1) {
        //收到了Ack分组，可以结束了
        return true;
    } else if ($isAck == 0) {
        //收到了Nak分组，需要重传
        return rdt_send($data);
    }
}

接收端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function rdt_rev($packet) {
    //差错检测
    if (check($packet)) {
        //解析报文
        $data = extract($packet);
        //没有错，把数据交付给应用层并回传ack
        //把数据给应用层
        deliver_data($data);
        //回传ACK
        $ack = make_pkt(1);
        udt_send($ack);
    } else {
        //有错，回传一个nak，不交付数据
        $nak = make_pkt(0);
        udt_send($nak);
    }
}

状态机

现在发送端有两个状态

  • 等待调用
  • 等待返回ack或nak

接收端还是一个状态

  • 等待调用

rdt2.0也被称为停等协议。因为发送端处于等待ack状态是不能被上层调用的。

ack受损rdt2.1

从上面的代码可以看出来，接收端发送ack使用的是udt_send函数，这个函数是不可靠的。那么如果我们的ack或者nak损坏了怎么办。

这时候可以像处理损坏分组一样。我们校验ack是否受损，如果受损，那么我们重传分组。

可是重传分组就会造成接收方不知道这个分组我有没有收到过。所以我们需要增加分组序号。

对于停等协议来说，0和1就够用了。因为停等协议只有两个状态，发完会等待ack。

发送端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//序号
$num = 0;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    
    //组装报文
    $packet = make_pkt($data, $checkSum, $num);
    //调用网络层传输 
    udt_send($packet);
    //等待接收方回传ack或者nak
    $isAck = rdt_rev();
    //差错检测
    if (check($isAck)) {
        //没出问题，那么把改变序号
        $num = !$num;
        //判断ack
        if ($isAck == 1) {
            //收到了Ack分组，可以结束了
            return true;
        } else if ($isAck == 0) {
            //收到了Nak分组，需要重传
            return rdt_send($data);
        }
    } else {
        //ack出问题了，那么这个时候重传
        return rdt_send($data);
    }
}

接收端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//序号
$num = 0;
function rdt_rev($packet) {
    //差错检测
    if (check($packet)) {
        //判断报文序号
        if ($packet['num'] == $num) {
            //解析报文
            $data = extract($packet);
            //序号对的
            //没有错，把数据交付给应用层并回传ack
            //把数据给应用层
            deliver_data($data);
            //回传ACK
            $ack = make_pkt(1, $num);
            udt_send($ack);
        } else {
            //序号错了，说明这不是我们要的，我们回传一个ack，告诉发送端这个分组我们收到了。
            //回传ACK
            $ack = make_pkt(1, $num);
            udt_send($ack);
        }
    } else {
        //有错，回传一个nak，不交付数据
        $nak = make_pkt(0, $num);
        udt_send($nak);
    }
}

状态机

发送端有4个状态

  • 等待调用0
  • 等待ack0或者nak0
  • 等待调用1
  • 等待ack1或者nak1

接收端有2个状态

  • 等待调用0
  • 等待调用1

去掉nak分组的rdt2.2

从上面的代码可以看出来，发送端在接收到nak的时候和丢失ack或者nak的时候都是重传。
所以我们只需要判断ack就可以了。那么同样接收方只需要回传ack就可以了。
这样一来，代码更见简单了。

发送端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//序号
$num = 0;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet = make_pkt($data, $checkSum, $num);
    //调用网络层传输 
    udt_send($packet);
    //等待接收方回传ack
    $isAck = rdt_rev();
    //差错检测
    if (check($isAck) && $isAck['num'] == $num) {
        //没出问题，那么把改变序号
        $num = !$num;
        //收到了Ack分组，可以结束了
        return true;
    } else {
        //ack出问题了，那么这个时候重传
        return rdt_send($data);
    }
}

接收端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//序号
$num = 0;
function rdt_rev($packet) {
    //差错检测通过了并且报文序号正确
    if (check($packet) && $packet['num'] == $num) {
        //解析报文
        $data = extract($packet);
        //序号对的
        //没有错，把数据交付给应用层并回传ack
        //把数据给应用层
        deliver_data($data);
        //回传ACK
        $ack = make_pkt(1, $num);
        udt_send($ack);
    } else {
        //没通过差错检测或者序号错误，我们回传一个上一个ack，告诉发送端上一个分组我们收到了，当前分组没收到。
        //回传ACK
        $ack = make_pkt(1, !$num);
        udt_send($ack);
    }
}

状态机

发送端有4个状态

  • 等待调用0
  • 等待ack0或者nak0
  • 等待调用1
  • 等待ack1或者nak1

接收端有2个状态

  • 等待调用0
  • 等待调用1

经具有比特差错的丢包信道的可靠数据传输rdt3.0

现在底层信道除了会出错，还会丢包了。

如果遇到丢包怎么办呢，也就是接收方接收不到数据了。这个时候也就回传不了ack。

那么可以在发送端加上超时机制。如果长时间没收到ack。那么就重传分组。

发送端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//序号
$num = 0;
function rdt_send($data) {
    //生成校验和
    $checkSum = generateCheckSum($data);
    //组装报文
    $packet = make_pkt($data, $checkSum, $num);
    //调用网络层传输 
    udt_send($packet);
    //启动一个定时器
    start_timer();
    //等待接收方回传ack 并且没有超时
    if ($isAck = rdt_rev() && !timeout()) {
        //差错检测
        if (check($isAck) && $isAck['num'] == $num) {
            //没出问题，那么把改变序号
            $num = !$num;
            //收到了Ack分组，可以结束了
            return true;
        } else {
            //ack出问题了，那么这个时候重传
            return rdt_send($data);
        }
    } else {
        //没接收到ack或者超时 重发
        return rdt_send($data);
    }
}

接收端

无变化

状态机

发送端

流水线可靠数据传输协议

停等协议的缺点是性能受限。因为每次要等待上一个ack回来才能发送下一个报文。

而采用流水线就是不等待ack直接发送下一个报文。

这样会有下面的影响

  • 必须增加序号范围，因为每个分组必须有序号
  • 协议的发送方和接收方两端也许不得不缓存多个分组。
  • 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失，损坏及时延大的分组。解决流水线的差错恢复有两种基本方法：
    • 回退N步（Go Back N）GBN
    • 选择重传（Selective Repeat）SR

GBN

滑动窗口协议

SR

选择重传协议

发表于 更新于 分类于 阅读次数： Valine：

运输层

运输层和网络层的关系

网络层是主机到主机，端到端的逻辑传输。

运输层是应用到应用，端口到端口的逻辑传输。

先由网络层送到主机，再通过运输层送到对应的端口程序中。

运输层将应用层报文封装成报文段交给网络层

将主机间交付扩展到进程间交付被称为运输层的多路复用和多路分解

UDP提供不可靠服务

  • 差错检测
  • 数据交付

TCP提供可靠服务

  • 流量控制
  • 序号
  • 确认
  • 定时器
  • 拥塞控制

多路复用和多路分解

源主机使用多路复用把多个套接字进程的报文发送给目的主机

目的主机使用多路分解把报文发送给多个套接字进程

运输层需要再首部信息加入

  • 源端口号
  • 目的端口号

通过端口号来区分进程

UDP套接字通过二元组来标识

  • 目的端口号
  • 目的ip
    只要你的目的ip和端口号相同就算你的源ip和端口不一样，也会分解到同一个套接字

TCP通过四元组来标识

  • 源ip
  • 源端口
  • 目的Ip
  • 目的端口

这是因为TCP会创建链接，一个TCP进程有一个“欢迎套接字”，用来等待程序过来，然后创建一个新的套接字来进行通信。

如果四元组一致会分解到一个套接字，不一致，会分解到另外的套接字。

web服务器和TCP

现在的计算机有线程的概念，所以TCP链接一般也不会创建多个进程来服务不同的客户端，而是创建多个线程套接字，通过分解到不同的线程套接字来服务多个客户端。

无连接运输：UDP

UDP只提供了运输层最低限度的东西。

  • 差错检测
  • 复用分解

DNS是使用UDP的一个应用层协议.

UDP存在的意义及优势：

  • 关于发送什么数据以及何时发送的应用层控制更为精细。
    采用UDP时，只要应用将数据给UDP,UDP就会直接传递给IP网络层。TCP有拥塞控制和重发机制，但是这样会需要更长的时间。因为实时应用通常要求最小的发送速率，不希望过分的延迟报文段的传送，且能容忍一部分数据丢失，TCP服务模型并不是特别适合这些应用的需要。这些应用使用UDP，并可以再应用层实现所需的，超出UDP的额外功能。
  • 无需链接建立
    TCP需要三次握手建立链接，UDP不需要。因此没有建立链接的时延。
  • 无连接状态
    TCP需要再端系统中维护链接状态。此链接状态包括接受和发送缓存，拥塞控制参数以及序号与确认号的参数。UDP一般能支持更多的活跃用户。
  • 分组首部开销小
    每个TCP报文段首部有20字节，UDP只有8字节

UDP也可以通过应用层实现可靠性传输。比如chrome的QUIC协议。

UDP报文段结构

  • 首部字段 8字节
    • 源端口号 2字节
    • 目的端口号 2字节
    • 长度 2字节 数据长度
    • 校验和 2字节 差错检测
  • 数据

UDP校验和

发送方的UDP对报文段中的所有16比特字的和进行反码运算，求和时候遇到的任何溢出都被回卷。得到的结果被放在UDP报文段中的校验和字段。

例子

如果有三个16比特的字：

0110011001100000
0101010101010101
1000111100001100

计算他们的和

0110011001100000
+0101010101010101
=1011101110110101
+1000111100001100
=0100101011000001

这个时候溢出了，把溢出的1加到后面
=0100101011000010

进行反码运输，把1变0，0变1
=1011010100111101

这就变成了校验和。

接收方将三个16比特和校验和加在一起，如果全是1，那么就没问题。如果有0，那么就有差错。

把上面的和加上校验和算一下
0100101011000010
+1011010100111101
=1111111111111111

UDP虽然实现了差错检测，但是没有差错恢复。他只是丢弃受损的报文段。其他实现是将受损的报文段交给应用程序并给出警告。

TCP

TCP提供全双工服务。双方都可以发送数据。

TCP首先建立连接。然后把数据引导到发送缓存中。从发送缓存中取出数据进行发送。取出的数量受限于最大报文段长度MSS。MSS一般根据最大链路层帧长度MTU。以太网和PPP链路层都具有1500MTU。所以MSS的典型值在1460 + 40字节的TCP/IP首部长度。

TCP报文段结构：

  • 源端口号 16比特
  • 目的端口号 16比特
  • 序号 32比特
  • 确认号 32比特
  • 接收窗口 16比特 用于流量控制
  • 首部长度 4比特
  • 选项字段 可选变长
  • 标志字段 6比特
    • ACK用于确认
    • RST, SYN, FIN用于连接建立和删除
    • 拥塞通告中使用 CWR和ECE字段
    • PSH置位标识接收方应立即将数据交给上层
    • URG用来指示紧急数据
  • 紧急数据指针字段 16比特
  • 校验和 16比特

往返时间的估计与超时

估计往返时间

估计一个SampleRTT作为样本，根据SampleRTT取平均值，也就是EstimatedRTT。

EstimatedRTT = (1 - a) * EstimatedRTT + a * SmapleRTT

a的推荐值是0.125。

RTT的偏差用DevRTT表示

DevRTT = (1 - b) * DevRTT + b * |SampleRTT - EstimatedRTT|

b的推荐值是0.25

设置和管理重传超时间隔

超时间隔应该 >= EstimatedRTT。但是也不能大太多

TimeoutInterval = EstimatedRTT + 4 * DevRTT

TCP设置单一的定时器，每当超时一次超时时间会加倍，以免造成网络拥塞。

TCP收到同一个ACK三次，会进行快速重传而不等待定时器超时。

TCP采用的是GBN和SR的混合体。

流量控制

TCP有发送缓存和接收缓存。接收方把数据放入接收缓存，然后读取到应用层。

当发送数据太多，为防止接收缓存装不下，需要控制发送端发送数量。

接收窗口字段就是这个作用，用来控制接收方还有多少空间。发送方就可以根据这个调整发送数量。

如果接收缓存已经满了。那么发送方依旧会发送1比特的数据。这样才能知道接收方变化后的接收缓存大小。

建立连接

  • 第一步：发送一个SYN = 1 Seq = 随机序号
  • 第二步：返回一个SYN = 1 Seq = 随机序号 Ack = Seq + 1
  • 第三步：SYN = 0 Seq = Ack Ack = Seq + 1 可以携带数据

关闭连接

  • 第一步：发送一个FIN = 1
  • 第二步：接收一个ACK
  • 第三步：接收一个FIN = 1
  • 第四步：发送一个ACK

拥塞控制

  • 端到端的拥塞控制。网络层不提供支持，端系统观察网络层得到结果。

  • 网络辅助的拥塞控制。

  • 丢失的报文段表示拥塞，降低发送速率。

  • 确认报文段表示顺利，提高发送速率

  • 带宽检测，逐步提高发送速率，如果丢失超时就降低然后接着提高。

慢启动

开始速率较小。大概MSS/RTT.
每当收到一个确认，就增加一个MSS。也就是指数级增长，不断翻倍。
何时结束？

  • 遇到丢包超时
  • 达到一个阈值

结束慢启动进入拥塞避免模式

拥塞避免模式

不再郑家指数级，而是一个一个增长。线性增长

发表于 更新于 分类于 阅读次数： Valine：

supervisor

supervisor是一个守护进程软件。

安装

ubuntu安装很简单。直接apt

1
sudo apt-get install supervisor

配置

修改配置项，加入我们的命令

1
sudo vim /etc/supervisor/conf.d/test.conf

复制下面的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[program:命令名称]
;目录
;directory=/test 这里我注释掉了，如果你加上以后报错可以注释掉试试
;执行的命令如果没有配置环境变量或者软连接请使用全路径
command=php /test/think queue:listen --queue im
process_name=%(program_name)s_%(process_num)02d;
numprocs = 3
autostart = true
startsecs = 5
autorestart = true
startretries = 3
;执行的linux用户
user=root
redirect_stderr = true
stdout_logfile_maxbytes = 50MB
stdout_logfile_backups = 20
;日志位置
stdout_logfile = /var/log/supervisor/queue_worker.log
loglevel=info

然后启动supervisor，因为是apt安装的，所以很好启动

1
sudo service supervisor start

查看启动了没有，有两种方法，一种status命令，还有一种查看linux进程

1
sudo service supervisor status

查看进程

1
ps -aux |grep super

再查看我们的命令挂起来没有。我们执行的php命令所以直接查看php

1
ps -aux|grep php

如果看见刚刚的命令就成功了。

发表于 更新于 分类于 阅读次数： Valine：

php-simplexml解析一个或多个结构的坑

php解析xml还是挺方便的，不管是正常的xml，还是加了一个命名空间或者前缀的xml。都可以通过simplexml_load_string函数来解析成数组或者对象。

simplexml_load_string

来看一下使用方法。

1
2
3
$xml = "<reports><report><id>1</id><name>张三</name></report></reports>"

$arr = (array)simplexml_load_string($xml);

是不是很简单，如果你的带啦前缀或者命名空间也可以使用。下面带了s前缀

1
2
3
$xml = "<s:reports><s:report><s:id>1</id><s:name>张三</name></report></reports>"

$arr = (array)simplexml_load_string($xml,'SimpleXMLElement',0,'s',true);

但是如果带了多个前缀，这个函数就无能为力了，可以使用别的方法解析。

bug

不过这个函数解析一个和多个结果是不一样的，这里解析出来一定要做判断！！！

下面有两个report，解析出的结果是一个数组。

1
2
3
$xml = "<reports><report><id>1</id><name>张三</name></report><report><id>1</id><name>张三</name></report></reports>"

$arr = (array)simplexml_load_string($xml);

而上面只有一个report的时候，解析出来就是一个对象！！！

发表于 更新于 分类于 阅读次数： Valine：

php-thinkphp-报错Creating default object from empty value

报错第一步，打印，打印日志，在你用到对象的地方，把对象都打印出来看看，你以为他是个对象，但他。。。不一定是个对象！！！

如果你确定你从数据库查询出来的没有错，是个对象，那么。。请看一下你别的对象是不是一个对象！！！

要相信报错，一定是对象错了，但你不确定，所以，请打印日志，如果你这里没问题，别人那里有问题，那么可能是参数的问题。打印日志在别人那就能看到你想的对象可能在他那里不是一个对象！！！