ElasticSearch三--ES-基本概念-节点集群分片副本

发表于 2021-04-23 更新于 2025-01-26 分类于 ES 阅读次数： Valine：

基本概念

分布式系统的可用性与扩展性

高可用性

服务可用性：允许有节点停止服务。
数据可用性：部分节点丢失，不会丢失数据。

可扩展性

请求量提升/数据的不断增长（将数据分布到所有节点上）

分布式特性

Elasticsearch 的分布式架构好处

存储的水平扩容
提高系统的可用性，部分节点停止服务，整个集群的服务不受影响

Elasticsearch的分布式架构

不同的集群通过不同的名字来区分，默认名字“Elasticsearch”
通过配置文件修改，或者在命令行中 -E cluster.name=xxx来设置
一个集群可以有一个或多个节点

节点

节点是一个Elasticsearch 的实例

本质上就是一个JAVA进程
一台机器上可以运行多个Elasticsearch进程，但是线上建议一个机器一个节点

每一个节点都有名字，通过配置文件配置，或者启动时 -E node.name=xxx 来设置

每个节点在启动之后会有一个UID，保存在data目录下

Master-eligible nodes 和 Master Node

每个节点启动后，默认是一个 Master eligible 节点。

可以设置 node.master:false 禁止
Master-eligible 节点可以参加选主流程，成为 master 节点

当第一个节点启动时候，它会将自己选举成为 master 节点

每个节点上都保存了集群的状态，只有 master 节点才能修改。

集群状态(Cluster State)，维护了一个集群中必要的信息
- 所有的节点信息
- 所有的索引和其相关的 Mapping 与 Settings 信息
- 分片的路由信息
任意节点都可以修改会导致数据的不一致

Data Node 和 Coordinating Node

Data Node

可以保存数据的节点，叫做Data Node。负责保存分片数据。在数据扩展上起到了至关重要的作用。

Coordinating Node

负责接受Client 的请求，将请求分发到合适的节点，最终把结果汇集到一起。
每个节点默认都起到了Coordinating Node的职责

其他的节点类型

Hot & Warm Node

不同硬件配置的Data Node ，用来实现 Hot & Warm 架构，降低集群部署的成本。

Machine Learning Node

负责跑机器学习的Job,用来做异常检测

Tribe Node

(5.3开始使用 Cross Cluster Search) Tribe Node 连接到不同的Elasticsearch 集群，并且支持将这些集群当成一个单独的集群处理

配置节点类型

生产环境建议一个节点担任一个角色

节点类型	配置参数	默认值
maste eligible	node.master	true
data	node.data	true
ingest	node.ingest	true
coordinating only	无	每个节点默认都是coordinating节点，设置其他类型全部为false
machine learning	node.ml	true(需要 enable x-pack)

分片（Primary Shard & Replica Shard）

主分片，用以解决数据水平扩展的问题。通过主分片，可以将数据分布到集群内的所有节点之上。

一个分片是一个运行的Lucene的实例
主分片数在索引创建时指定，后续不允许修改，除非Reindex

副本，用以解决数据高可用的问题。分片是主分片的拷贝

副本分片数，可以动态调整
增加副本数，还可以在一定程度上提高服务的可用性（读取的吞吐）

分片的设定

对于生产环境，需要提前做好容量规划

分片数设置过小

导致后续无法增加节点实现水平扩展
单个分片的数据量太大，导致数据重新分配耗时

分片数设置过大，7.0开始，默认分片设置为1，解决了over-sharding的问题

影响搜索结果的相关性打分，影响统计结果的准确性
单个节点上过多的分片，会导致资源浪费，同时也会影响性能

查询集群的健康状态

使用GET方法访问 _cluster/health

1	GET /_cluster/health

或者访问 http://localhost:9200/_cluster/health

Green : 集群健康
Yello : 主分片分配，副本未分配
Red : 主分片未分配

ElasticSearch三--ES-基本概念-索引文档REST API

发表于 2021-04-23 更新于 2025-01-26 分类于 ES 阅读次数： Valine：

基本概念

文档(Document)

Elasticsearch 是面向文档的，文档是所有可搜索数据的最小单位。

日志文件中的日志项。
电影的具体信息/唱片的具体信息
MP3播放器里的一首歌/一篇PDF文档中的具体内容

文档会被序列化成 JSON 格式，保存在Elasticsearch中。

JSON对象由字段组成
每个字段都有对应的字段类型（字符串/数值/布尔/日期/二进制/范围类型）

每个文档都有一个Unique ID

你可以自己指定ID
或者通过Elasticsearch自己生成

文档的元数据

元数据，用于标注文档的相关信息
- _index - 文档所属的索引名
- _type - 文档所属的类型名
- _id - 文档唯一的ID
- _source - 文档的原始JSON数据
- _all - 整合所有字段内容到该字段，已被废除
- _version - 文档的版本信息
- _score - 相关性打分

索引（Index）

索引是文档的容器，是一类文档的集合。

Index 体现了逻辑空间的概念：每个索引都有自己的Mapping定义，用于定义包含的文档的字段名和字段类型
Shard 体现了物理空间的概念：索引中的数据分散在Shard上

索引的 Mapping 和 Settings

Mapping 定义文档字段的类型
Setting 定义不同的数据分布

索引的不同语意

名词：一个Elasticsearch中，有多个不同的索引。
动词：保存一个文档到Elasticsearch的过程也叫索引（indexing）
- ES中，创建一个倒排索引的过程
名词：一个B树索引，一个倒排索引

类型Type

7.0 开始每个索引只能创建一个 Type - “_doc”

REST API

Elasticsearch提供了REST API的方式进行调用，这样不管什么语言都可以通过HTTP的方式进行调用。

这些API的文档可以在Elasticsearch的文档里面找到.

可以在Kibana里面的dev tools进行REST API的测试。

ElasticSearch二--ES-Kibana安装

发表于 2021-04-01 更新于 2025-01-26 分类于 ES 阅读次数： Valine：

Kibana安装

安装

从官网（https://www.elastic.co/cn/downloads/kibana)可以进行下载安装

启动

1	/bin/kibana

启动后可以访问 localhost:5601 进行查看信息

ElasticSearch二--ES安装

发表于 2021-03-25 更新于 2025-01-26 分类于 ES 阅读次数： Valine：

ES–安装

安装

运行ElasticSearch, 需安装并配置JDK
- 设置 $JAVA_HOME
各个版本对 Java的依赖
- ElasticSearch 5 需要 Java 8 以上的版本
- ElasticSearch 从6.5开始支持 Java 11
- https://www.elastic.co/support/matrix#matrix_jvm
- 7.0开始，内置了Java环境

从官网（https://www.elastic.co/cn/downloads/elasticsearch)可以进行下载安装

目录说明

bin : 脚本文件，包括启动 ElasticSearch，安装插件。运行统计数据等。
config : 配置文件：elasticsearch.yml。集群配置文件，user,role based相关配置
JDK: Java运行环境
data: path.data 数据文件
lib : Java类库
logs: path.log 日志文件
modules: 包含所有ES模块
plugins: 包含所有已安装插件

JVM配置

修改JVM - config/jvm.options
- 7.1 下载的默认设置是1GB
配置的建议
- Xmx 和 Xms设置成一样
- Xmx 不要超过机器内存的50%
- 不要超过 30GB - https://www.elastic.co/blog/a-heap-of-trouble

启动

单节点启动

1	/bin/elasticsearch

启动后可以访问 localhost:9200 进行查看信息

多节点启动

cluster.name 指定同一个集群，node.name指定每个节点的名称，path.data指定数据存放位置

1
2
3

/bin/elasticsearch -E node.name=node1 -E cluster.name=test -E path.data=node1_data -d
/bin/elasticsearch -E node.name=node2 -E cluster.name=test -E path.data=node2_data -d
/bin/elasticsearch -E node.name=node3 -E cluster.name=test -E path.data=node3_data -d

启动完成以后可以直接访问localhost:9200/_cat/nodes查看node信息

安装插件

使用elasticsearch-plugin进行插件的安装和查看

1 2	/bin/elasticsearch-plugin list //查询已安装的插件列表 /bin/elasticsearch-plugin install analysis-icu //安装analysis-icu插件

还可以通过api进行查看已安装的插件，访问localhost:9200/_cat/plugins可以查看已安装的插件

ElasticSearch一--ES简介

发表于 2021-03-19 更新于 2025-01-26 分类于 ES 阅读次数： Valine：

ES–简介

起源

ES起源于Lucene.Lucene是基于JAVA开发的搜索引擎类库。

Lucene具有高性能，易扩展的优点。

Lucene的局限性：

只能基于JAVA开发
类库的接口学习曲线陡峭
原生并不支持水平扩展

ES的诞生

ES的创始人Shay Banon说过：Search is something that any application should have。

2004年基于Lucene开发了 Compass

2010年重写了 Compass ，取名 ElasticSearch

支持分布式，可水平扩展
降低全文检索的学习曲线，可以被任何编程语言调用

ES的分布式架构

集群规模可以从单个扩展至数百个节点

高可用 & 水平扩展
- 服务和数据两个维度

支持不同的节点类型
- 支持 Hot & Warm架构

主要功能

海量数据的分布式存储以及集群管理
- 服务与数据的高可用，水平扩展
近实时搜索，性能卓越
- 结构化/全文/地理位置/自动完成
海量数据的近实时分析
- 聚合功能

新特性5.x

Lucene 6.x ，性能提升，默认打分机制从TF-IDF改为BM25
支持Ingest节点/ Painless Scripting / Completion suggested 支持/ 原生的JAVA REST客户端
Type 标记成 deprecated ，支持了keyword类型
性能优化
- 内部引擎移除了避免同一文档并发更新的竞争锁，带来15 - 20%的性能提升
- Instant aggregation，支持分片上聚合的缓存
- 新增了Profile API

新特性6.x

Lucene 7.x
新功能
- 跨集群复制（CCR）
- 索引生命周期管理
- SQL的支持
更友好的升级及数据迁移
- 在主要版本之间的迁移更为简化，体验升级
- 全新的基于操作的数据复制框架，可加快回复数据。
性能优化
- 有效存储稀疏字段的新方法，降低了存储成本
- 在索引时进行排序，可加快排序的查询性能

新特性7.x

Lucene 8.x
重大改进 - 正式废除单个索引下多Type的支持
7.1开始，Security功能免费使用
ECK - ElasticSearch Operator on Kubernetes
新功能
- New Cluster coordination
- Feature-Complete High Level Rest Client
- Script Score Query
性能优化
- 默认的Primary Shard 数从5变为1，避免Over Sharding
- 性能优化，更快的Top K

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

发表于 2020-12-26 更新于 2025-01-26 分类于计算机网络阅读次数： 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 * 2^r XOR R就等于 D + R数据。

如何计算R

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

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

D * 2^r = nG XOR R

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

R = remainder (D * 2^r / G)

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

如何计算G

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

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

这个转换的方法：

首先把末尾的1看成x⁰，也就是x的0次幂
这样提取出x的所有幂
对应幂的位置填1，如果没有对应幂的位置则填0

转换例子1

G = x⁴ + 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 = x⁶ + x⁴ + x² + 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

网络原理自顶向下四网络层

发表于 2020-12-26 更新于 2025-01-26 分类于计算机网络阅读次数： 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地址，新端口号）

网络原理自顶向下四网络层

发表于 2020-12-26 更新于 2025-01-26 分类于计算机网络阅读次数： Valine：

数据链路层

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

组帧

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

链路接入

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

相邻节点间可靠交付

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

流量控制

协调相邻的发送和接受

差错检测

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

差错纠正

接收端直接纠正比特差错

全双工和半双工通信控制

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

差错检测：差错编码

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

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

MAC协议

两类链路

点对点链路

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

广播链路（共享介质）

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

单一共享广播信道

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

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

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

理想MAC协议

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

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

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

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

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

运行：

适配器从网络获取一条数据报，准备链路层帧，并放入帧适配器缓存中。
如果适配器侦听到信道空闲（即无信号能量从信道进入适配器），他开始传输帧。另一方面，如果适配器侦听到信道正在忙，他将等待，直到侦听到没有信号能量时才开始传输帧。
在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。
如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成了该帧。另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，他中指传输（即他停止了传输帧）
中止传输后，适配器等待一个随机时间量，然后返回步骤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:
主节点轮询：令牌传递
结合两者优点，不是最好也不是最坏

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

发表于 2020-12-12 更新于 2025-01-26 分类于计算机网络阅读次数： 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之前的全部确认。
超时事件。如果出现超时，就重传所有已发送未确认的分组。

//序号
$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的接收端较为简单，因为接收端只需要按序号交付数据就可以了。如果数据没有按序到达接收端，接收端只需要直接丢弃，因为发送端会重传所有分组。

//期望的序号
$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缓存。

//序号
$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。表示我已经收到了。
其他情况。忽略分组

//期望的序号
$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);
    }
}

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

发表于 2020-12-12 更新于 2025-01-26 分类于计算机网络阅读次数： Valine：

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

SR

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

发送端

等待上层调用。这里和GBN一样
超时。超时哪个重传哪个
收到ACK。如果收到的是最小序号的ACK，那么base可以往前移动，也就是窗口滑动。如果收到其他序号的ACK。那么把这些ACK缓存。

//序号
$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。表示我已经收到了。
其他情况。忽略分组

//期望的序号
$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);
    }
}