2023.11.19晚,比赛还未结束,也许是暂时还没结束,但是我已经绝望地合上电脑,走出待了四个小时的教室

我的手臂伤势恢复一直不错,我可以继续比赛,不过休息不是件坏事,我会考虑我的下一步选择
——the shy赛后采访

其实走出来的那个时候,外面的冷风倒是没那么的刺,依稀记得,那个时候我脑海里的是:

明凯你不要退役啊
——女粉丝

小时候不懂得这一切背后的意义,只是单纯觉得:“有必要吗?不就是一场比赛而已。”

shy哥你不要退役啊
——我的内心

现在我上大学了,似乎懂得了一点点这份英雄暮年的无奈,也许会有一些素不相识的小孩疑惑着:“有必要吗?不就是一场比赛而已。”

年少时射出的一颗子弹,经过多年,正中眉心

虽然很不想承认,但是这轮比赛完完全全地让宙斯登上了上路的王座,不再年轻的你看着意气风发的宙斯,会不会满眼都是18岁的自己

我想啊,初二那年如果我没有看你的比赛,这几天也不会有如此感触吧

从8强开始看的比赛,或许不能算什么真正的粉丝,毕竟自我小学开始玩LOL的时候,冠军总是被faker斩获,因此总是对所谓的比赛提不起多大兴趣,但是你真的让我对早已失去的LOL职业比赛重燃信心

同样的上单位,你让我明白了原来可以这么玩游戏,原来可以这么压制,原来可以$\cdots \:\cdots$

虽然上了高中后再也没有时间玩LOL了,但是在难得的两周一天的回家时间,在凌晨,我还是愿意打开你的直播间,看你rank,甚至是看你吃夜宵,我想那些日子我应该也挺开心吧

后来啊,你被人们说靠小虎抬进的世界赛,被人们说瑞士轮1:2闹麻了,被人们嘲笑上限冠军,被人们说打个欧美弱鸡闹麻了,被人们说抽签组闹麻了,被人们说打个BLG闹麻了,直到一步步走到首尔,走到最大的舞台$\cdots \:\cdots$

而我看到的是,早已下坡的你一次次挽狂澜于既倒,扶大厦于将倾,直到决赛之前,你的世界赛表现堪称完美,甚至是让人看到了IG.The Shy的身影,因此我更加相信,你在今年拥有一个美满的结局

The Shy向上天祈祷,回应他的只有18年的自己
——虎扑评论

这样的评论,几乎在决赛前的每一局都能出现,我也那么以为,登神的剧本描述的是你,我们万分期待着,四号种子掀翻T1的剧情再次上演

决赛时候我看BP过程的担心,还是应验了:

  • 三楼出剑魔的话宙斯会出永恩

  • 塞拉斯不ban不能拿大树

毋庸置疑faker的表现无可挑剔,也许他生来就是LOL这个故事的主角:主角在年少时拿下三连冠,后来沉寂许久,最后在自己第10年职业生涯拿下第四个冠军。一切看起来都那么完美,但是啊,我不是主角的粉丝,我好像永远被困在18年的仁川了,这次shy哥还是没能把我们带回家,也许再也没有机会了

晚上路过茶百道的时候,wjy问我:“你还想喝橙露啵啵吗?”我苦笑了一阵,一时也说不出话来。但其实啊,不管你拿不拿得到这个冠军,我都只是希望能看你多打几局比赛,这对我来说就是已经足够了

现在看来,我一个星期前梦中WBG 2 : 0 T1的梦境显得那么荒谬,但是无论无论怎么样,我全程看完今年世界赛的眼睛告诉我你发挥已经极致

下山的路太吵了,我听不见
——网友

故事的开始:

基地来了个孩子,他的锐雯在天上飞

故事的尾声:

很可惜走到决赛却输了,更可惜的是我觉得我年纪大了,如果我再年轻一点是不是可以过更精彩的人生
——the shy赛后采访

我想啊,如果身体还允许的话,能不能再让我看你一年,不奢求能走到多远了,只希望你开开心心地结束自己作为选手的生涯。你的少年时期,已经看过山上的风景,这段路,已经足够伟大

许多年前,你有一双清澈的双眼
奔跑起来,就像一道春天的闪电
——焦迈奇《你曾是少年》

我明白时光不能倒转,但是我还是很怀念我的初二,很怀念我初识你的时候,一切都能重新来过

概述

动态主机配置协议DHPC服务器可以是服务器

  1. 一个协议软件在使用前先作正确协议配置,具体配置内容取决于协议
  1. 连接到因特网的计算机协议软件需要配置的项目:

    • IP地址

    • 子网掩码

    • 默认路由器的IP地址

    • 域名服务器的IP地址

  2. DHCP可以高效地分配IP地址

    • 局域网的网络协议

    • 使用UDP来实现

DHCP报文类型

  • DHCP Discoevr:发现

  • DHCP Offer:提供

  • DHCP Request:告知决定

  • DHCP ACK:租约确认

  • DHCP NCK:租约不确认

  • DHCP Release:释放租约

  • DHCP Decline:收到ACK后,Client告诉服务器不接受

  • DHCP Inform:客户端向服务器端请求详细信息

DHCP报文结构

  1. OP:报文类型

    • 1请求,2应答
  2. HTYPE:硬件地址类型

  • 1表示10M以太网地址
  1. HLEN:以太网地址长度

    • 10M为6
  2. Hops:是否使用代理服务器进行处理

DHCP过程

  1. Client先广播Discover报文,然后Server返回一个Offer报文

  2. Client选择优先返回的Offer来优先服务

  3. Client广播Request报文,告知到底谁服务了谁,然后Server返回一个ACK报文

  4. 时间到了之后可以选择Release或者续租

A和B的信息不对称不同步

  • 局域网的地址B分配完成了而A不知道

  • 广播里面会携带分配的地址信息,告知A进行同步

发现阶段

广播携带的地址是MAC地址

响应阶段

选择阶段

所有的Server进行同步

租约确认阶段

租期续约

在租期中,DHCP Client直接向为其提供IP地址的DHCP Server发送DHCP Request消息,收到回应的DHCP ACK消息后,DHCP Client根据所提供的新的租期以及其它更新的TCP/IP参数更新自己的配置

租期释放

当DHCP Client不再需要使用分配IP地址时,就会主动向DHCP Server发送Realease报文,DHCP Server会释放被绑定的租期

  • 到时间后Server会主动询问,没有应答会自动释放

DHCP欺骗及防范

欺骗原理

非授权的DHCP服务器先应答,客户端最后获得的网络参数即是非授权的

  • 恶意服务器把自己作为默认网关

在实际应用DHCP的网络中,基本上都会采用DHCP中继,因此本网络的非授权DHCP服务器一般都会先于其余网络的授权DHCP服务器的应答

  • 网络传输有延迟

欺骗攻击

  1. 首先PC发出请求

  2. 然后将DHCP请求发送出去

  3. 伪装者收到后,DHCP伪装者给出应答

  1. DHCP Server也会给出应答,但是可能比伪装者慢

  2. 这样子A收到的就是伪装者的报文

  1. A发出去的网关就是B,所以A上网的请求就发送给B,B转发给默认网关上网,然后返回信息给B

  2. B再把返回的信息给A

  3. 很隐蔽的安全问题

  4. 除了服务器不应该启动DHCP进程

DHCP欺骗防范

在交换机上启用DHCP Snooping功能DHCP Snooping技术通过建立和维护DHCP Snooping绑定表过滤不可信任的DHCP信息:比如B的DHCP不能通过认证,交换机拒绝进行转发

  1. 在交换机的全局配置模式启用DHCP Snooping:

    switch (config) # ip dncp snooping

  2. 在交换机的全局配置模式中开启需要启用DHCP Snooping的VLAN:

    switch (config) # ip dhcp snooping vlan vlan号

  3. 在端口配置子模式中将授权DHCP服务器所连的端口设为新人端口(缺省都是非信任的端口):就是连接到DHCP Server的端口:

    switch (config-if) # ip dhcp snooping trust

会话层(Session)

如果用户想要完成一定的数据控制,就会对应在会话层完成

  • TCP控制传输

职责

  1. 基于令牌进行交互发言,通过数据同步保证数据完整性

  2. 进行数据分段、拼接、保证传输的有效

  3. 同步技术,保证故障恢复

服务

  1. 同步:

    • 全双工通信

    • 半双工通信

    • 单工通信

  2. 控制:

    • 会话连接、活动开始、数据校验

    • 令牌转换

同步点(CheckPoint)用于分割对话的各个部分

  • 同步点:发送一定数据后设置同步点

  • 次同步点:作为同步点的一个子集,进行数据校验

  • 主同步点:按照主同步点进行校验确认

  • 如果错误,恢复到上次已经同步的主同步点

对话分离(Seperation)是通信的有序启动、终止和管理,尽量保证了通话的效率和可靠性

设备

客户端-服务器模式(Client-Server):通过会话实现

表示层(Presentation)

负责以接收设备可以理解的形式表示数据

  • 传输语法协商

  • 接受语法协商

协商编码方式可以在会话层中实现

  • 解决不同的底层操作系统编码方式不同的问题,以防造成误解

主要功能

  • 数据格式化(format)

  • 数据压缩(compression)

  • 数据加密(encryption)

数据格式化

选择大家都能识别的编码形式传输,保证大家都能理解

  • 提供了不同类型的代码之间的转换

数据格式类型:

  1. 图形文件格式:

    • 图形交换格式GIF(Graphic Interchange Format)

    • 联合图像专家组JPEG(Joint Photographic Experts Group)

  2. 多媒体文件格式:

多媒体文件格式存储声音、音乐和视频

数据加密与压缩

数据加密可在信息传输过程中保护信息

应用层

OSI模型各层对应的一些协议:

  • 第六层对应了各种协议,第七层对应了应用界面

  • 第七层最接近用户,支持应用程序的通信组件

职责

  • 确定并确定预期的通信合作伙伴的可用性

  • 同步合作的应用程序

  • 同步协作的应用

  • 建立有关错误恢复程序的协议

  • 控制数据完整性

  • 通过网络应用为OSI模型的其余部分提供一个直接接口,或是通过独立应用程序提供非直接接口,如文字处理、电子表格、演示管理器、网络重定向器

超文本传输协议HTTP

HTTP是面向事务(transaction-orient)的客户服务器协议

HTTP 1.0协议是无状态的(stateless)

  • 每一次请求都是独立的,不记录上一次登陆的信息

  • Cookie是征求同意的存储(维持登陆状态

HTTP协议本身是无连接的,虽然它使用了面向连接的TCP向上提供的服务

万维网浏览器就是一个HTTP客户,而在万维网服务器等待HTTP请求的进程称为HTTP daemon,也称为HTTPD

  • HTTP daemon收到HTTP客户的请求后,把所需的文件返回给HTTP客户

HTTP报文结构(请求报文)

HTTP报文主要由开始行、首部行和实体主体组成

  • 在请求报文中,开始行就是请求行

  • 请求报文和应答报文的应答结构都是一样的

    1. 2xx:成功

    2. 3xx:重定向

    3. 4xx:失败

    4. 5xx:服务器内部错误(不是客户端请求的错误)

方法 意义
OPTION 请求一些选项的信息
GET 请求读取由URL所标志的信息
HEAD 请求读取由URL所标志的信息的首部
POST 给服务器添加信息
PUT 在指明的URL下存储一个文档
DELETE 删除指明的URL所标志的资源
TRACE 用来进行换回测试的请求报文
CONNECT 用于代理服务器

统一资源定位符URL

URL是对可以从因特网上得到的资源的位置和访问方法的一种简洁的表示

  • URL给资源的位置提供一种抽象的识别方法,并用这种方法给资源定位

  • URL相当于一个文件名在网络范围的拓展,是与因特网相连的机器上的任何可访问对象的一个指针

URL一般由以下四个部分组成:

<协议>://<主机>:<端口>/<路径>

  • 协议:HTTPS或HTTP

  • 主机:域名的方式

  • 端口:对应进程

  • 路径:对应具体的文件

HTML

HTML文档是一种可以用任何文本编辑器创建的ASCII码文件

  • HTML用一对标签或几对标签来标识一个元素

    • 浏览器针对各种标签,根据所使用的显示器的尺寸和分辨率大小,重新排版并会付出所读取的页面

FTP和TFTP

FTP是一种可靠的、面向连接的服务,使用TCP传输文件

  1. FTP首先在客户端和服务器(端口21)之间建立控制连接

  2. 然后建立计算机之间用于传输数据的连接(端口20

TFTP是使用UDP的无连接服务

  1. 不支持交互,没有目录浏览功能

  2. 体积小,易于实施,更加方便

  3. TFTP在路由器上用于传输配置文件和Cisco IOS镜像

工作步骤

  1. 打开熟知端口21,使客户进程连接上
  • 可以修改熟知端口
  1. 等待客户进程发出连接请求

  2. 启动从属进程来处理客户进程发来的请求

    • 处理完毕就终止

    • 运行期间可能根据需要创建一些其他子进程

      • 主进程和从属进程的处理是并发
      1. 控制连接

      2. 数据连接

        • 需要建立上面两个连接才能完成传输
  3. 回到等待状态,继续接受其他客户进程发来的请求

Telnet协议

Telnet客户端软件提供了登录到运行Telnet服务器应用程序的远程Internet主机,然后从命令行执行命令的功能

  • 输入参数,达成一致,对服务器进行操作

  • 不同操作系统之间的快捷键和指令是有差异的,需要进行转换

SMTP和POP(电子邮件)

电子邮件服务器使用SMTP发送和POP接收邮件相互通信

  • 发送者先登录到服务器,通过服务器根据 SMTP 传输到对应的服务器,然后用户登录后通过 POP3 协议收邮件到本地

SMTP(Simple Mail Transfer Protocol):邮件发送、登陆发送等

POP3(Post Office Protocol version 3):邮件接收

  • 邮件到达邮件服务端,由客户端和服务端联系接收邮件

MIME和SMTP

很多文件并不是ASCII码的,需要用MIME进行转换(扩充)

  • MIME标准扩充了SMTP标准

MIME增加五个新的邮件首部

  1. MIME-version:标志MIME的版本

  2. Contenet-Description:可读字符串,说明此邮件主体是否是图像、音频或视频

  3. Content-Id:邮件的唯一标识符

  4. Content-Transfer-Encoding:在传送时邮件的主体是如何编码的

  5. Content-Type:说明邮件主体的数据类型和子类型

简单网络管理协议SNMP

SNMP可简化网络设备之间的管理信息交换

  • 网络管理系统NMS:通过下发请求对上网的所有主机关于流量等信息进行管理

  • 通过管理数据库MIB进行交流

  • 使用UDP通过广播进行实现

DNS域名系统

DNS管理域名并相应客户端将域名转换为关联IP地址的请求

域名

  • 使用.将字符串进行分割

  • 越靠后域名级别越高

  • www 对应到主机群

类别 域名 使用者
国家 .cn 中国
.us 美国
.uk 英国
通用 .com 企业和公司
.net 网络服务提供商
,org 非盈利组织
.edu 教育机构
.gov 政府
.mil 军方
.int 国际组织
基础设施领域 arpa 用于反向解析域名
Recently .aero 航空运输企业
.biz 公司和企业
.travel 旅游业
.jobs 人力资源管理者
.museum 博物馆
.info 各种资讯

顶级域名底下的域名由顶级域名进行管理

跟域名服务器存储位置,所以子服务器知道跟服务器地址就行

DNS域名解析

DNS系统以层次结构设置,该层级结构创建不同级别的DNS服务器

次级别的DNS服务器判断其自身能否将域名转换为IP地址

  • 如果不行,将请求发送到更高级别

  • 如果可以,将结果返回给服务端

沟通方式

  1. 无上下文:

    • 当浏览器打开时,将连接到默认页面,并且将页面的文件传输到客户端,处理完成后连接断开
  2. 有上下文:

    • 作为Telnet和FTP,建立与服务器的连接并保持该链接,直到执行所有处理,确定都完成后才断开连接

数据的机器级表示

信息的二进制编码

  • 自信息量:$I(x_i) = -log_2\:p(x_i)$

  • 系统的信息熵:$H(X) = E[I(X)] = -\sum_i p(x_i)log_2p(x_i)$

补码

计算机中普遍使用补码

补码无论同号还是异号都可以直接相加

  • 原码可能会出错

负数的补码等于对应的正数各位取反末位加一

浮点数二进制表示

科学计数法:$\pm S \times B^E$

  • S:尾数
  • B:基底
  • E:阶码

规格化数

S E M
  • 尾数(S)第一位总是1,不需要存于尾数字段(默认)

    • 23位原码表示24位尾数
  • 阶码(E)的真实值加偏移量后再存入阶码字段

    • 真实值 -127~128

    • 全0和全1表示特殊值

      • 规格化数的阶码范围为0000 0001(-126) ~ 1111 1110(127)

规格化表示:

  • $\pm 1.bbb…b \times 2^E$

  • $X = (-1)^S \times M \times 2^E$

规格化数的范围:(重要难耐

格式 最小整数 最大整数 最小负数 最大负数
单精度 E = 1, M=0 E = 254, M = $1 - 2^{-23}$ E = 254, M = $1-2^{-23}$ E = 1, M = 0
真值 $1.0 \times 2^{-126}$ $(2-2^{-23}) \times 2^{127})$ $-(2-2^{-23}) \times 2^{127}$ $-1.0 \times 2^{-126}$

阶码的值 尾数的值 表示
0(全0) 0 $\pm 0$
0(全0) 非0 非规格化数
1~254 任意 规格化数
255(全1) 0 $\pm \infty$
255(全1) 非0 NaN

非规格化数

用于处理规格化数中的下溢情况

$(-1)^S \times 0.bbb…b \times 2^{-126}$

自然BCD码(NBCD,8421码)(随便看看得了

用四个二进制位表示每一个十进制数字

符号:四个最高有效位

  • 正:1100
  • 负:1101

数据校验码

纠错

基本思想存储额外的信息以进行检错和校正

处理过程

  • 数据输入:使用函数f在M位数据D上生成K位校验码C

  • 数据输出:使用函数f在M位数据$D’$上生成新的K位校验码$C’’$,并与取出的K位校验码$C’$进行比较

    • 没有检测到差错:使用数据$D’$

    • 检测到差错并可以校正:校正数据$D’$来生成数据$D’’$,并用数据$D’’$

    • 检测到差错但无法纠正:报告

  • 一旦进入Memory,C和D就已经永远消失了

奇偶校验码

增加1位校验码在数据最后面来表示数据中的1的数量是奇数还是偶数

处理过程

假设数据为$D = D_M \cdots D_2 D_1$

  • 数据输入

    • 奇校验:$C = D_M \oplus \cdots D_2 \oplus D_1 \oplus 1$

    • 偶校验:$C = D_M \oplus \cdots D_2 \oplus D_1$

  • 数据输出

    • 奇校验:$C’’ = D’_M \oplus \cdots D’_2 \oplus D’_1 \oplus 1$

    • 偶校验:$C’’ = D’_M \oplus \cdots D’_2 \oplus D’_1$

  • 检错

    $S = C’’ \oplus C’$

    • S = 0:正确/数据中出错的位数为偶数

    • S = 1:数据中出错的位数为奇数

优点:代价低,只需要1位额外数据

缺点:不能发现出错位数为偶数的情形,发现错误后无法校正

海明码

将数据分成几组,对每一组都使用奇偶校验码进行检错

处理过程

将𝑀位数据分成𝐾组

  • 数据输入

    • 为数据𝐷中每组生成1位校验码,合并得到𝐾位校验码𝐶
  • 数据输出

    • 为数据𝐷′中每组生成1位校验码,合并得到新的𝐾位校验码𝐶′′
  • 检错:将校验码𝐶′′和取出的校验码 C’ 按位进行异或,生成𝐾位故障字(syndrome word)

检验码

检验码的长度为 $2^K \geq M + K + 1$,使K成立的最小值就是校验码的位数

  • 数据中有1位出现错误:M

  • 检验码中有1位出现错误:K

  • 没有出现错误:1

每一个检验位都放在二进制串中$2^n(n \in \mathbb{N})$的位置

位置 1 2 3 4 5 6 7 8 9 10 11 12
数据位 $D_1$ $D_2$ $D_3$ $D_4$ $D_5$ $D_6$ $D_7$ $D_8$
校验位 $C_1$ $C_2$ $C_3$ $C_4$
  • 检验位$C_i$负责检验二进制第 i 位为1的位置的检错

    • 比如$C_1$负责0011、0101、0111 、1001$\cdots$,也就是第3、5、7、9 $\cdots$位

    • 比如$C_2$负责0011、0110、0111、1010 $\cdots$,也就是第3、6、7、10$\cdots$位

  • 检验位$C_i$的值要根据选择的奇/偶校验来决定

    • 所有负责的位进行异或(奇检验最后还要异或1)

故障字

每种取值反映一种情形

  • 全0:没有检测到错误

  • 有且仅有1位是1:错误发生在校验码中的某一位,不需要纠正

  • 有多位为1:错误发生在数据中的某一位,将$D’$中对应数据位取反即可纠正

故障字 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
数据位 $D_1$ $D_2$ $D_3$ $D_4$ $D_5$ $D_6$ $D_7$ $D_8$
校验位 $C_1$ $C_2$ $C_3$ $C_4$

循环冗余检测

  • 模2运算:进行加法和减法都不进位

循环冗余检测CRC计算假定数据M有k个比特,CRC运算就是在数据M后面添加供差错检测用的n位冗余码,然后构成一个帧发出去,一共发送(k + n)位

n位冗余码获得方式:在M后面加上n个0,得到的(n + k)位的数初一事先商定的(n + 1)位除数P,得出商是Q而余数是R(n位),这个余数R就作为冗余码拼接在数据M后面发送出去,也就是发送(k + n)位的CRC码

  • 这种冗余码称作帧检验序列FCS(Frame Check Sequence)

循环冗余检验 的图像结果

接收端把收到的数据进行CRC检验:把收到的每一个帧除以相同的除数P(模2运算),然后检查得到的余数R

  • R = 0则判定没有差错,接收

  • R $\ne$ 0则出现差错(无法确定具体位置

整数运算

加法

溢出表示:

全加器

  • 与门延迟:1ty ,或门延迟:2ty,异或门延迟:3ty

  • 进位延迟:2ty,数据延迟:6ty

串行进位加法器

  • $S_n = 2 \times(n - 1) + 3 = 2n + 1$

    • 在等待C来的时候,已经提前把$X_i$和$Y_i$进行计算

    • n=1的时候,计算出来是3,而实际是6

      • 需要 $2 \times (n - 1) \geq 3$ 才行
    • $S_1 = 6,S_2 = 6,S_3 = 7$,$S_1$和$S_2$是同时出来的,只要C过去了就行

全先行进位加法器

超前进位:

  • 所有的 $P_i$ 和 $G_i$ 都是可以同时计算的,代价是1ty

  • 求出所有 $C_i$ 代价为2ty

    • 先计算所有的与,再计算所有的或
  • 求出所有的 $S_i$ 代价为3ty

    • 异或只需要再做一次(有一次跟上面的时间重叠了)

部分先行进位加法器

思路:采用多个CLA并将其串联,取得计算时间和硬件复杂度之间的权衡

  • 最后算出的是最前面的加法部分

  • 最左边是3 = 1 + 2

  • 然后中间两个+2:之前P和G都算好了

  • 最后一步5 = 2 + 3

    • P和G已经算好了
  • 多一个加2

减法

$X - Y = X + (-Y)$

  • Sub是控制线,1为减法,0为加法

    • Sub为1会走下面的路(取反
  • Sub另一端连接在CarryIn上面

乘法

原码一位乘法

所有数用原码表示

计算X + Y:

  1. 符号位单独计算

  2. X和Y数值位的绝对值进行计算

  • 根据Y低位决定ACC

    • 低位为1则ACC加X,然后逻辑右移

    • 低位为0则ACC不变,然后逻辑右移

  • 进行n次计算(X和Y的位数为n)

布斯乘法(补码一位乘法)

所有数用补码表示

计算 X + Y:

  1. 乘数末尾补0

这张图有问题,但是思想没问题

  • 错误点是第三次横移应该高位补1

  • 根据乘数最低两位决定ACC

    • 最低位- 倒二低位 = 1:加上X补码,然后算数右移

    • 最低位- 倒二低位 = 0:不变,然后算术右移

    • 最低位- 倒二低位 = -1:加上-X补码,然后算术右移

  • 进行n次运算(X和Y的位数为n)

除法

原码恢复余数法

  1. 所有数用原码表示

  2. 符号位单独处理

  3. 数值位采用绝对值计算

计算X / Y

计组学习笔记第三章运算方法与运算器3.6 - AcWing

  • 根据$X + [-Y]_补$来计算

    • 结果为负:上商0,加Y恢复余数,被除数和商左移一位

    • 结果为非负:上商1,被除数和商左移一位

  • 左移n次,上商n+1次(n为数值位)

    • 最后一次不用左移

原码不恢复余数法

  1. 所有数用原码表示

  2. 符号位单独处理

  3. 数值位采用绝对值计算

计算X / Y

QQ截图20211017160416.png

  • 根据$X + [-Y]_补$来计算

    • 结果为负:上商0,余数左移一位,再加Y

    • 结果为非负:上商1,余数左移一位,再减Y

  • 左移n次,上商n+1次(n为数值位)

    • 最后一次不用左移

    • 若最后一次余数为负,需要加Y得到正确的余数

补码不恢复余数法

  1. 所有数用补码表示

  2. 符号位参与运算

    • 拓展为双符号位

计算X / Y

  • 根据X和Y的符号来确定运算方式

    • 同号:$X - Y$

    • 异号:$X + Y$

  • 根据余数和除数的符号来计算

    • 同号:上商1,余数左移一位,然后再减Y

    • 异号:上商0,余数左移一位,再加Y

  • 左移n次,上商n+1次(n为数值位)

    • 第n+1次上的商恒置为1

浮点数运算与表示

加法和减法

必须保证两个操作数有相同的指数值

  • $X_E \leq Y_E$

    • $X+Y = (X_S \times B^{X_E - Y_E} + Y_S) \times B^{Y_E}$

    • $X-Y = (X_S \times B^{X_E - Y_E} - Y_S) \times B^{Y_E}$

步骤:

  1. 检查0

  2. 对齐有效值

  3. 加或减有效值

  4. 规格化结果

原码加法

如果两个操作数有相同的符号,做加法;否则,做减法

  • 做加法:直接相加

    • 如果最高位有进位,则溢出

    • 符号和被加数(被减数)相同

  • 做减法:加第二个操作数的补数

    • 如果最高位有进位,正确

      • 符号与被减数相同
    • 否则,计算它的补码

      • 符号与被减数相反

乘法

  1. 无论哪个操作数是0,乘积都为0

  2. 从阶值的和中减去一个偏移量

    • 其实是减去两个,但是最后表示出来要加一个
  3. 有效值相乘

  4. 结果规格化和舍入

    • 规格化可能导致阶值下溢

除法

  1. 如果除数是0,则报告出错

  2. 如果被除数是0,则结果是0

  3. 被除数的阶值减除数的阶值,加上偏移量

  4. 有效值相除

  5. 结果规格化和舍入处理

精度考虑

寄存器的长度几乎总是大于有效值位长与一个隐含位之和,这些附加位称为保护位

  • 保护位用0填充,用于扩充有效值的右端

舍入

  • 四舍五入:结果被舍入成最近的可表示数

    • 最后四位:如果第一位是0,直接截去

    • 最后四位:如果第一位是1,产生进位

  • 朝$\pm\infty$舍入:结果朝无穷大的方向舍入

  • 朝0舍入:结果朝0舍入

概述

组织和结构

组织:对编程人员不可见

  • 操作单元及其相互连接

  • 包括控制信号、存储技术,…

结构:对编程人员可见

  • 直接影响程序逻辑执行的属性

  • 包括指令集、表示数据类型的位数,…

计算机简史

  • 第一代:真空管

    • 出现冯诺依曼模型
  • 第二代:晶体管

  • 第三代及后续几代:集成电路

冯诺依曼模型

基本原则:计算机由运算器、存储器、控制器、输入设备、输出设备组成,指令和数据均用二进制表示

最重要的思想:存储程序

01 | 冯·诺依曼体系结构:计算机组成的金字塔-CSDN博客

  1. 主存储器:地址和存储内容

  2. 算术逻辑单元:执行信息的实际处理

  3. 程序控制单元:指挥信息的处理

  4. 输入设备:将信息送入计算机中

  5. 输出设备:将处理结果以某种形式显示在计算机外

摩尔定律

单芯片上所能包含的晶体管数量每年翻一番 (1965-1969) / 1970
年起减慢为每18个月翻一番

CPU性能

系统时钟

  • 时钟频率(时钟速度):计算机在单位时间内执行最基本操作的次数,单位Hz

  • 时钟周期(周期时间):执行每次最基本操作的时间,单位s

指令执行

处理器由时钟驱动,时钟具有固定的频率,或等价为

CPI每条计算机指令执行所需的时钟周期数

  • $CPI = \frac{\sum_{i = 1} ^{n}(CPI_i \times I_i)}{I_c},I_c = \sum_{i = 1} ^ {n} I_i$

    • $CPI_i$:指定类型i所需要的周期数

    • $I_i$:某一给定程序中所执行的i类指令的条数

执行一个给定程序的处理时间是:

  • $T = I_c \times CPI \times t$

每秒百万条指令(MIPS):

  • $MIPS = \frac{I_c}{T \times 10^6} = \frac{f}{CPI \times 10^6}$

每秒百万条浮点操作(MFLOPS):

  • $MFLOPS = \frac{N_{floating-point\:op}}{T \times 10^6}$

平均结果

  • 算术平均值:$R_A = \frac{1}{m}\sum_{i = 1}^m R_i$

  • 调和平均值:$R_H = \frac{m}{\sum_{i = 1}^m \frac{1}{R_i}}$

  • 几何平均值:$R_G = (\prod_{i = 1}^n R_i)^{\frac{1}{n}}$

性能设计基本原则

大概率事件优先原则:对于大概率事件(或最常见的事件),赋予它优先的处理权和资源使用权

  • $系统加速比 = \frac{总执行时间_{改进前}}{总执行时间_{改进后}}$

Amdahl定律

  • 加快某部件执行速度所获得的系统性能加速比,受限于该部件在系统中所占的重要性比例

  • 性能增加的递减规则:如果仅仅对计算机中的一部分做性能改进,改进越多,系统获得的效果越小

    • $系统总加速比 = \frac{总执行时间_{改进前}}{总执行时间_{改进后}} = \frac{1}{(1 - 局部占比) + \frac{局部占比}{提升的性能}}$

顶层视图

COA-2019-第二章 A Top-Level View of Computer Function and Interconnection ...

计算机工作原理(感觉不是很重要

  • 指令和数据存储在单个读写存储器中

  • 主存中的内容按位置访问,无需考虑其中包含的类型

  • CPU从一条指令到下一条指令到下一条指令以顺序方式执行

  • I/O模块与CPU、贮存交换计算机系统外部的数据

CPU频率不能无限提高随便提一嘴):

  • 理论限制:

    1. mos管开关、脉冲通过门电路需要时间

    2. 为了信号同步、每个脉冲信号需要持续一定时间

  • 制造限制:

    1. 芯片面积越来越大。导致连线延迟越来越大,需要保证信号在设计指定时钟周期内从芯片的一角到达另一角

    2. 频率越高会导致开关损耗也越高,CPU会费电和散热高

  • 解决方法

    1. 改进CPU芯片结构

主存和CPU之间传输数据的速度跟不上CPU的速度(内存墙)也是随便提一嘴

  • 采用高速缓存Cache

CPU在等待I/O设备时保持空闲还是随便提一嘴

  • 采用中断机制

层次式存储结构可以兼顾存储容量、速度和成本知道我要说什么吧

I/O设备传输速率差异大累了

  • 采用缓冲区和改进I/O操作技术

计算机部件互连复杂这个可以看看):

  • 采用总线

    • 控制线:控制数据线和地址线的访问和使用

    • 地址线:指定数据总线和地址I/O端口上的数据的来源或去向

    • 数据线:在系统模块之间传送数据

概述

传输层向它上面的应用层提供通信服务

  • 从传输层看,通信的真正端点不是主机而是主机中的进程

传输层有一个很重要的功能:复用(multiplexing)和分用(demultiplexing)

  • 复用:应用层的所有应用程序都可以通过传输层再传送到网络层

  • 分用:传输层从网络层收到发送给各应用程序的数据后,必须交付指明的各应用程序

运输层提供应用进程间的逻辑通信

  • 数据的传送好像是沿着水平方向传送的

  • 网络层为主机之间提供逻辑通信

《计算机网络》学习总结——运输层、TCP与UDP(详细理解)_为什么要提供两种tcp udp2中协议_羊and船的博客-CSDN博客

传输层会对收到的报文进行差错检测

传输层有两种不同的运输协议:

  1. 面向连接的TCP

  2. 无连接的UDP

传输层向高层用户屏蔽了下面网络核心的细节,使得应用进程看见的就是好像在两个运输层实体之间有一条端对端的逻辑通信信道

  • 传输层采用面向连接的TCP协议时,尽管下面的网络是不可靠的,但这种逻辑通信信道相当于一条全双工的可靠信道

  • 传输层采用无连接的UDP协议时,这种逻辑通信信道仍然是一条不可靠信道

传输层的两个协议

传输层有两种不同的运输协议:

  1. 面向连接的TCP(传输控制协议)

    • 传送数据前要先建立连接,数据传送结束后要释放连接

    • 不提供广播或多播服务

  2. 无连接的UDP(用户数据报协议)

    • 传送数据前不需要先建立连接,远地主机收到UDP报文后不需要确认

端口

TCP和UDP都是用端口来跟踪同时穿越网络的不同网络(即不同进程)

端口分配规范:

  1. 0-255保留给TCP和UDP公共应用程序使用

  2. 0-1023是熟知端口,有分发的规范,不应当被随便使用

应用程序 FTP TELNET SMTP DNS TFTP HTTP SNMP SNMP(trap) HTTPS
熟知端口号 21 23 25 53 69 80 161 162 443
  1. 1024-49151可以进行登记使用,避免冲突

  2. 49152-65535为短暂端口号,用于远程通信

套接字Socket

第四层进行通信的单位是进程,由IP和端口共同制定,socket是第四层的地址

  • socket表示为(IP地址,端口)

  • 每个连接都表示为($socket_{source}$,$socket_{destination}$)

  • 通信被认为是以一个socket和另一个socket之间的连接

TCP协议

TCP最主要的特点:

  1. TCP是面向连接的传输层协议

  2. 每一条TCP连接只能由两个端点(endpoint),只能是点对点

  3. TCP提供可靠交付的服务

    • 通过TCP连接传送的数据无差错、不丢失、不重复、按需到达
  4. TCP提供全双工通信

    • 两端都设有发送缓存和接收缓存
  5. 面向字节流

    • TCP把应用程序交下来的数据仅仅看成是一连串的无结构字节流

【图解】三次握手,四次挥手 —— 用心看这一篇就够了-阿里云开发者社区

TCP必须解决的问题:

  1. 可靠传输

  2. 流量控制

    • 滑动窗口

    • 拥塞避免

  3. 连接控制

    • 建立连接:三次握手

    • 断开连接:四次握手

TCP数据报

基本情况:一行4字节,固定首部长度为20字节

  1. 源端口和目的端口

    传输层和应用层的服务接口,各占2字节

    • 复用和分用功能都要通过端口实现
  2. 序号

    TCP传送的数据流中的每一个字节都编上一个编号,序号字段的值指本报文所发送的数据的第一个字节的序号,占4字节

    • 通过序号字段做可靠传输的保证,指示的是TCP传输的比特编码,而不是地址

    • 从小向大进行使用,使用到最大之后会从小再次重新开始分配

  3. 确认号

    期望收到的下一个报文段的数据的第一个字节的序号,用于确认对方的数据号,同时对上一次传输进行确认,占4字节

    • 体现出全双工通信的有点,比如上回收到的最后序号是700,那么确认号就是701
  4. 数据偏移

    指出TCP报文段的数据起始处距TCP报文段的起始处的长度,单位是32位字(即4字节)

    • 不满足的话使用填充位保证为4字节的整数倍
  5. URG

    URG = 1时,表明紧急指针字段有效,告诉系统此报文段中有紧急数据,应尽快传送

  6. ACK

    ACK = 1时确认号字段有效

  7. 推送PSH(PuSH)

    接收TCP收到PSH = 1的报文段,就尽快交付应用进程,而不再等到整个缓存都填满了再向上交付,此时将缓存所有部分都传输

  • TCP在正常情况下并不是马上传输的,而是等到缓存满了才发送
  1. 复位RST

    ReSeT = 1时表明TCP连接中出现严重差错,必须释放连接再重新建立连接

    • 如果请求方发送的请求,如果应答方不想连接则将ReSeT置为1
  2. 同步SYN

    SYN = 1时表明这是一个连接请求或连接接受报文

  3. 终止FIN

    FIN = 1表明此报文段的发送端的数据已发送完毕,并要求释放传输连接

    • 断开连接有四次握手
  4. 窗口

    用来让对方设置发送窗口的依据,表示可以进行传输的窗口大小,单位是字节,占2字节

  5. 校验和

    校验和字段检验的范围包括首部和数据这两部分,占2字节

  6. 紧急指针

    指出在本报文段中紧急数据共有几个字节,占2字节

    • 紧急数据放在本报文段数据的最前面
  7. 选项

    TCP最初只有一种选项,即最大报文段长度MSS(Maximum Segment Size)

    • MSS告诉对方缓存所能接收的报文段的数据字段的最大长度是MSS个字节
    • 数据字段要加上TCP首部才等于整个TCP报文段
  8. 填充字段

    使整个首部长度是4字节的整数倍

主机使用网段(TPDU)交换数据

  • 每个段都有首部20字节 + 0或更多数据字节
  • 段的大小必须与IP数据报匹配,并且必须满足底层的需求

  • 每个字节都有一个32位序号

    • 通讯中商定初识序号,确认到每一位

    • 面向字节:数据块大小可以不对应

    • 根据网络条件,对每一个字节进行确认

建立可靠连接(三次握手)

  1. 第一次握手

    • 客户端:执行CONNECT原语,生成 SYN = 1 和 ACK = 0 的TCP段,代表连接请求

    • 服务器:执行LISTEN和ACCEPT原语,并进行被动监视

  2. 第二次握手

    服务器检查是否存在监视端口的服务进程

    • 如果没有任何进程,则使用 RST = 1 回答一个TCP段

    • 如果存在进程,则决定拒绝或接受请求

      • 如果接受连接请求,则发送 SYN = 1 和 ACK = 1 的网段
  1. 第三次握手

    客户端发送一个 SYN = 0 和 ACK = 1 的网段确认连接

    • 三次握手是为了避免出现延时之类的情况

    • 默认三次握手就认为可靠了,之后进行数据传输

    • 有时候会选择则第三次握手的时候同时携带数据

停止等待协议

发送段后要暂时保留备份

  • 没有收到确认可以进行重传(超时重传

    • 设置一个超时计数器:如果对方的应答超过一定时间后则直接重发

    • 重新发送时间必须大于 平均传输时间 $\times$ 2

  • 收到确认就抛弃备份

每个网段和ACK必须具有ID

停止等待协议效率较低

没有收到应答或者丢失都要直接重传

收到重复的就直接丢弃并重新发送确认

  • 出现在ACK丢失的情况

连续ARQ协议(滑动窗口的思想)

多个数据同时发送(一次发送多个)

窗口大小是双方协定的

  • 通过TCP报文中的窗口字段表示

出现丢失的情况

  • 如果连续发送五个分组,而第三个分组丢失了,则要不最后三个分组都重传一遍,这叫做后退N帧

释放连接(四次握手)

释放连接前必须等待最大的网络往返时间 2MSL(保证能处理到B最后发送的报文)

  • 防止出现任何无效的连接请求段

  1. 第一次握手

    发起断开连接请求

  2. 第二次握手

    ACK = 1:允许断开,此时不再发送数据,需要完成之前未处理完成的数据的处理

  3. 第三次握手

    FIN = 1:数据处理完成,表示正式断开

  4. 第四次握手

    收到断开信息

TCP中的计时器

  1. 重传计时器:决定多长时间进行重传

  2. 坚持计时器:避免死锁

    • WIN = 0的时候修改但是无法发送过去

    • 收到WIN = 0的时候开始进行计时,到时候主动询问

  3. 保持计时器:发送数据段后刷新,如果到达一定时间则再次询问是不是还要保持连接

  4. 时间等待计时器

TCP有限状态机

  • 粗线:正常的服务器端

  • 细线:异常状态

  • 虚线:正常的客户端

UDP协议

UDP的最主要特点:

  1. 没有建立连接(避免延时)

  2. 简单:发送方、接收方无连接状态

    • 没有握手等

    • 每个UDP段都独立处理

  3. 小段标题

  4. 没有拥塞控制

UDP常见用处:

  1. 流媒体和多媒体应用

    • 速率敏感而非质量敏感
  2. RIP:定期发送路由信息

  3. DNS:避免延迟建立TCP连接(DNS需快速找到

  4. SNMP:拥塞时,SNMP必须仍然可以运行,在没有拥塞和可靠性控制机制的情况下,UDP性能优于TCP

    • 组播和多播
  5. 其他协议如TFTP、DHCP

UDP数据帧格式

UDP详解 - 知乎

  • 首部只有8字节,因此UDP报文最少是8字节

  • 校验时包括数据部分,如果出现错误直接丢弃

  • 应用层进行数据切片,决定如何进行发送,UDP直接发送,不会再自己切片

TCP和UDP的异同

不同点

  1. TCP不是直接交给上层校验,而是需要先和对方沟通,缓存满了才统一交付

  2. UDP直接转发报文,保留报文标间,IP进行划分,应用程序会发送比较何时的UDP报文大小

共同点

  1. 校验相同

NAT和PAT

NAT是再IP数据报头部将一个地址转化为另一个地址的过程

NAT用于允许私下寻址的主机访问Internet,NAT是IP地址耗尽的解决方案之一:

  1. 保留注册(合法)地址

  2. 连接到Internet时增加灵活性

NAT需要一个路由器来实现

  • NAT路由器可以双向转换

NAT(地址转换技术)详解【转载】 - 知乎

NAT的类型

  1. 静态NAT:固定的内部地址到注册地址的映射

  2. 动态NAT:映射以先到先得的方式动态进行

  3. PAT:端口地址转换用于允许许多内部用户共享一个“内部全局”地址

    • 基于socket映射而不是IP地址

    • 多个内网主机映射到一个公网地址

NAT地址类型

  1. 内部本地地址(Inside Local address):内网IP地址

  2. 内部全局地址(Inside Global address):注册IP地址,对外部展示的内部地址

  3. 外部全局地址(Outside Global address):由主机所有者分配的IP地址,通常是注册地址

内部主机发送报文给网关,网关根据NAT table进行翻译,转换成内部全局地址,然后进行转发

NAT的优缺点

  1. 优点:并非每个内部主机都需要同时进行外部访问,因此可以是用少量的全局唯一地址池来服务相对大量的私有寻址主机

  2. 缺点:映射没有从根本上解决地址短缺的问题

PAT

  • 同样的出口IP,用不同的端口号来区别

通用语法及分类

MySQL语法:

  • 可以单行或多行书写,以分号结尾

  • 可以使用空格和缩进提高可读性

  • 不区分大小写,关键字建议大写

SQL分类:

分类 全称 说明
DDL Data Definition Language 数据定义语言,用来定义数据库对象(数据库、表、字段)
DML Data Manipulation Language 数据操作语言,用来对数据库表中的数据进行增删改
DQL Data Query Language 数据查询语言,用来查询数据库中表的记录
DCL Data Control Language 数据控制语言,用来创建数据库用户,控制数据库的访问权限

PS:[…]为可选参数

DDL

数据库操作:

  1. 查询

    • 查询所有数据库:

      1
      SHOW DATABASES;
    • 查询当前数据库:

      1
      SELECT DATABASE();
  2. 创建

    1
    CREATE DATABASE [IF NOT EXISTS] 数据库名 [DEFAULT CHARSET 字符集] [COLLATE 排序规则];
  3. 删除

    1
    DROP DATABASE[IF EXISTS] 数据库名;
  4. 使用

    1
    USE 数据库名;

表操作:

  1. 查询

    • 查询当前数据库所有表:

      1
      SHOW TABLES;
    • 查询表结构:

      1
      DESC 表名;
    • 查询指定表的建表语句:

      1
      SHOW CREATE TABLE 表名;
  2. 创建

    1
    2
    3
    4
    5
    CREATE TABLE 表名(
    字段1 字段1类型 [COMMENT 字段1注释],
    ......
    字段n 字段n类型 [COMMENT 字段n注释]
    ) [COMMENT 表注释];
    • 最后一个字段后面没有逗号

    • 添加字段

  3. 修改

    • 添加字段

      1
      ALTER TABLE 表名 ADD 字段名 类型(长度) [COMMENT 注释] [约束]
    • 修改数据类型

      1
      ALTER TABLE 表名 MODIFY 字段名 新数据类型(长度);
    • 修改字段名和字段类型、

      1
      ALTER TABLE 表名 CHANEG 旧字段名 新字段名 类型(长度) [COMMENT 注释] [约束];
    • 修改表名

      1
      ALTER TABLE 表名 RENAME TO 新表名;
  4. 删除

    • 删除字段

      1
      ALTER TABLE 表名 DROP 字段名;
    • 删除表

      1
      DROP TABLE [IF EXISTS] 表名;
    • 删除指定表,并重新创建该表(清除数据

      1
      TRUNCATE TABLE 表名;

DML

  1. 添加数据

    • 给指定的字段添加数据

      1
      INSERT INTO 表名(字段名1,字段名2,...) VALUES (值1,值2,...);
    • 给全部字段添加数据

      1
      INSERT INTO 表名 VALUES (值1,值2,...);
    • 批量添加数据

      1
      2
      3
      INSERT INTO 表名(字段名1,字段名2,...) VALUES (值1,值2,...),(值1,值2,...),(值1,值2,...);

      INSERT INTO VALUES (值1,值2,...),(值1,值2,...),(值1,值2,...);

    注意

    • 插入数据时,指定的字符顺序一定与值的顺序是一一对应的
    • 字符串和日期型数据应该包含在引号中
  2. 修改数据

    1
    UPDATE 表名 SET 字段名1=1,字段名2=2,... [WHERE 条件];
    • 没有条件就会修改整张表的数据
  3. 删除数据

    1
    DELETE FROM 表名 [WHERE 条件];
    • 如果没有条件会删除整张表的数据

DQL

DQL编写顺序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SELECT 
字段列表
FROM
表名列表
WHERE
条件列表
GROUP BY
分组字段列表
HAVING
分组后条件列表
ORDER BY
排序字段列表
LIMIT
分页参数

DQL执行顺序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FROM
表名列表
WHERE
条件列表
GROUP BY
分组字段列表
HAVING
分组后条件列表
SELECT
字段列表
ORDER BY
排序字段列表
LIMIT
分页参数
  1. 基本查询

    • 查询多个字段

      1
      SELECT 字段1,字段2,字段3,... FROM 表名;
      1
      SELECT * FROM 表名;
      • * 表示查询全部字段
    • 设置别名

      1
      SELECT 字段1 [AS 别名],字段2[AS 别名],... FROM 表名;
    • 去除重复记录

      1
      SELECT DISTINCT 字段列表 FROM 表名;
  2. 条件查询

    1
    SELECT 字段列表 FROM 表名 WHERE 条件列表;
  3. 聚合函数

    定义:将一列数据作为一个整体,进行纵向计算

    • 不计算null值

      1
      SELECT 聚合函数(字段列表) FROM 表名;
常用的聚合函数 功能
max 最大值
min 最小值
sum 求和
avg 平均值
count 统计数量
  1. 分组查询

    1
    SELECT 字段列表 FROM 表名 [WHERE 条件] GROUP BY 分组字	段名 [HAVING 分组后过滤条件];
    • 不满足where条件不参与分组,且where不能对聚合函数进行判断

    • 分组后不满足having条件过滤掉

  2. 排序查询

    1
    SELECT 字段列表 FROM 表名 ORDER BY 字段1 排序方式1,字段2,排序方式2;
排序方式 功能
ASC 升序(默认)
DESC 降序
  1. 分页查询

    1
    SELECT 字段列表 FROM 表名 LIMIT 起始索引,查询记录数;

    注意

    1. 起始索引从0开始,$起始索引 = (查询页码 - 1)\times 每页记录数$

    2. 分页查询是数据库的方言,不同数据库有不同的实现,MySQL中是LIMIT

    3. 如果查询的是第一页数据,起始索引可以省略

DCL

管理用户

  1. 查询用户

    1
    2
    USE mysql;
    SELECT * FROM user;
  2. 创建用户

    1
    CREATE USER '用户名'@'主机名' IDENTIFIED BY '密码';
    • 主机名为 localhost 或 %(任意主机)
  3. 修改用户密码

    1
    ALTER USER '用户名'@'主机名' IDENTIFIED WITH mysql_native_password '新密码';
  4. 删除用户

    1
    DROP USER '用户名'@'主机名';

权限控制

  1. 查询权限

    1
    SHOW GRANTS FOR '用户名'@'主机名';
  2. 授予权限、

    1
    GRANT 权限列表 ON 数据库名.表名 TO '用户名'@'主机名';
    • 数据库名和表名可以用 * 来表示所有
  3. 撤销权限

    1
    REVOKE 权限列表 ON 数据库名.表名 FROM'用户名'@'主机名';
    • 数据库名和表名可以用 * 来表示所有
  • 多个权限之间要用逗号分隔

数据模型

MySQL数据库:

  • 关系型数据库(RDBMS):建立在关系模型基础上,由多张相互连接的二维表组成的数据库

    • 使用表存储数据,格式统一,便于维护

    • 使用SQL语言操作,标准统一,使用方便

MySQL:认识数据库_MySQL数据库的优点_About_yyyyyyy的博客-CSDN博客_mysql的优点

SQL

通用语法及分类

MySQL语法:

  • 可以单行或多行书写,以分号结尾
  • 可以使用空格和缩进提高可读性
  • 不区分大小写,关键字建议大写

SQL分类:

分类 全称 说明
DDL Data Definition Language 数据定义语言,用来定义数据库对象(数据库、表、字段)
DML Data Manipulation Language 数据操作语言,用来对数据库表中的数据进行增删改
DQL Data Query Language 数据查询语言,用来查询数据库中表的记录
DCL Data Control Language 数据控制语言,用来创建数据库用户,控制数据库的访问权限

PS:[…]为可选参数

数据类型

数字类型 大小
TINYINT 1byte
SMALLINT 2bytes
MEDIUMINT 3bytes
INT或INTEGER 4bytes
BIGINT 8bytes
FLOAT 4bytes
DOUBLE 8bytes
DECIMAL 依赖精度和标度
  • 可以在类型后面加入UNSIGNED表示无符号范围
  • 浮点数()内两个数分别表示整体长度和小数位数
字符串类型 大小 描述
CHAR 0-255bytes 定长字符串
VARCHAR 0-65535bytes 变长字符串
TINYBLOB 0-255bytes 不超过255个字符的二进制数据
TINYTEXT 0-255bytes 短文本字符串
BLOB 0-65535bytes 二进制形式的长文本数据
TEXT 0-65535bytes 长文本数据
MEDIUMBLOB 0-16777215bytes 二进制形式的中长长度文本数据
MEDIUMTEXT 0-16777215bytes 中长长度文本数据
LONGBLOG 0-4294967295bytes 二进制形式的极大文本数据
LONGTEXT 0-4294967295bytes 极大文本数据
  • CHAR和VARCHAR需要接上()表示最大长度
  • 定长的空间会全部占用,性能比VARCHAR好
日期类型 大小 范围 格式 描述
DATE 3 1000-01-01至9999-12-31 YYYY-MM-DD 日期值
TIME 3 -838:59:59至838:59:59 HH:MM:SS 时间值或持续时间
YEAR 1 1901至2155 YYYY 年份值
DATETIME 8 1000-01-01 00:00:00至9999-12-31 23:59:59 YYYY-MM-DD HH:MM:SS 混合日期和时间值
TIMESTAMP 4 1970-01-01 00:00:01至2038-01-19 03:14:07 YYYY-MM-DD HH:MM:SS 混合日期和时间值、时间戳

整理BY:Misayaas

内容来自:《线性代数讲义》

行列式

克莱姆法则简单版

若存在方程组$\begin{cases}
a_{11}x_1 + a_{12}x_2= b_1 \\
a_{21}x_1 + a_{22}x_2= b_2\\
\end{cases}$,

可令$\Delta = \begin{vmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{vmatrix}$,$\Delta_1 = \begin{vmatrix}
b_1 & a_{12} \\
b_2 & a_{22} \\
\end{vmatrix}$,

$\Delta_2 = \begin{vmatrix}
a_{11} & b_1 \\
a_{21} & b_2 \\
\end{vmatrix}$

则对该方程组有一下结论(可以递推更高阶):

  1. 若$\Delta \neq 0$,则方程组有唯一的解,$x_1 = \frac{\Delta_1}{\Delta},x_2 = \frac{\Delta_2}{\Delta}$

  2. 若$\Delta = 0$,但$\Delta_1,\Delta_2$不全为0,则方程组无解

  3. 若$\Delta = \Delta_1 = \Delta_2 =0$,则方程组有无穷多组解

方程组解的结论

  1. 齐次线性方程组必有零解,非齐次方程都是非零解

  2. 含有n个未知数的n个方程的齐次线性方程组若有非零解,则它的行列式等于0(充要条件)

行列式基本性质

  1. 某两行(列)对应成比例,则行列式的值为0

  2. 若行列式的某一行\列拆分成两行(列)元素的和,则行列式可以拆成两个行列式的和

  3. 行列式任一行\列的公因子可以提出称为该行列式的因子

  4. 两行\列元素交换后,原行列式的值差一个负号

n阶行列式的性质

  1. 行列式和它的转置行列式的值相等

  2. 两行\列元素交换后,原行列式的值差一个负号

    • 两行(列)相等的行列式的值为0
    • 行列式可以按任一行(列)展开
  3. 行列式任一行\列的公因子可以提出称为该行列式的因子

    • 用k乘以行列式的某一行(列),其结果就等于用k去乘这个行列式
  4. 将行列式 的任意一行(列)乘以k加到另一方(列)上去,行列式的值不变

  5. 行列式任一行(列)的元素与另一行(列)的代数余子式对应的乘积之和为0

反对称

一切奇数阶的反对称行列式都等于0

范德蒙德行列式

$D = \begin{vmatrix}
1 & 1 & \cdots &1\\
x_1 & x_2 & \cdots &x_n\\
x_1^2 & x_2^2 & \cdots &x_n^2\\
\vdots & \vdots & &\vdots\\
x_1^{n-1} & x_2^{n-1}& \cdots &x_n^{n-1}\\
\end{vmatrix} = \prod_{1 \leq i \leq j \leq n}(x_j - x_i)$

矩阵、向量

奇异矩阵

如果|A| $\neq$ 0,则称矩阵A是非异矩阵,如果|A| = 0,则矩阵A是奇异矩阵或退化矩阵

矩阵乘法

结合律:(AB)C = A (BC)

数乘结合律:k(AB)= (kA)B = A(kB)

分配律:A(B + C)= AB + AC

  • AO = OA = O;AE = EA = A

矩阵相乘的行列式|A$\cdot$B| = |A| $\cdot$ |B|

转置矩阵

  1. $(A^T)^T = A;|A^T| = |A|$

  2. $(A + B)^T = A^T + B^T$

  3. $(kA)^T = kA^T$

  4. $(AB)^T = B^TA^T$

分块矩阵

$A = \begin{vmatrix}
P_{11} & P_{12} \\
P_{21} & P_{22} \\
\end{vmatrix}$,则$A^T = \begin{vmatrix}
P_{11}^T & P_{21}^T \\
P_{12}^T & P_{22}^T \\
\end{vmatrix}$

初等变换和初等矩阵

初等矩阵左(右)乘一个矩阵的结果就是对这个矩阵做相应的初等行(列)变换

  • 左行右列

推论:

  1. 设A为$m \times n$矩阵,r(A) = r,则存在m阶可逆矩阵P和n阶可逆矩阵Q,使得$A = P\Lambda Q$

    • 其中$\Lambda = \begin{vmatrix}
      E_r & O \\
      O & O_{(m -r)\times (n-r)} \\
      \end{vmatrix}$

等价

等价关系具有自反性、对称性、传递性,若A和B等价,那么A可以经过有限次初等变换得到B

具有行等价关系的矩阵所对应的线性方程组有相同的解

行梯型矩阵和行简化梯形矩阵

共同点:

  1. 零行在最下面

  2. 从第一行起,每行第一个非零元素前面的零的个数逐行增加

行简化阶梯型特有:

  1. 非零行第一个非零元素为1,其所在列其他元素为0

矩阵的秩

矩阵的秩是非零子式的最高次数宋浩说的最重要

基础知识:

  1. $0 \leq r(A_{m \times n}) \leq min(m,n)$

  2. $r(A^T) = r(A)$

  3. $r(A) = n \Longleftrightarrow |A| \neq 0 \Longleftrightarrow A非异$

  4. 初等变换不改变矩阵的秩

  5. 任一满秩矩阵可以经过若干次初等行(列)变换变为单位矩阵

可逆矩阵

AB = BA = E且逆矩阵是唯一

基本性质:

  1. 若A可逆,则$A^{-1}$也可逆,且$(A^{-1})^{-1} = A$,且|$A^{-1}$| = $|A|^{-1}$

  2. 若A可逆,则kA也可逆(k$\neq$ 0),且$(kA)^{-1} = k^{-1}A^{-1}$

  3. 若A可逆,则$A^T$也可逆,且$(A^T)^{-1} = (A^{-1})^T$

  4. 若A、B为同阶可逆矩阵,则AB也可逆,且$(AB)^{-1} = B^{-1}A^{-1}$

推论:

  1. 矩阵A可逆的充要条件是:A为满秩矩阵

  2. 矩阵A可逆的充要条件是:$|A| \neq 0,且A^{-1} = \frac{1}{|A|} A^*$

伴随矩阵

基本公式是:$AA^\ast = A^\ast A = |A|E$

推论:

  1. 设A为n阶方阵($n \geq 2$),则$|A^*| = |A|^{n-1}$

  2. 设A为n阶方阵($n \geq 2$),则$(A^\ast) ^\ast= |A|^{n-2}A$

线性组合

给定n维向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_m$和同维向量 $\beta$,如果存在一组数$k_1,k_2,\cdots,k_m$,使得 $\beta = k_1\alpha_1+k_2\alpha_2+\cdots+k_m\alpha_m$,则称 $\beta$ 是向量组A的一个线性组合或称向量 $\beta$ 可由向量组A线性表示

性质:

  1. 零向量是任何向量组 $\alpha_1,\alpha_2,\cdots,\alpha_m$ 的线性组合

  2. 任何n维向量都可由 $e_1,e_2,\cdots,e_n$ 线性表示,向量组 $e_1,e_2,\cdots,e_n$ 也称为n维基本向量

等价向量组

设有两个向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_m$ 及B:$\beta_1,\beta_2,\cdots,\beta_m$,若A中的每个向量都可由向量组B线性表示,则称向量组A可由向量组B线性表示,若两个向量组A,B可以相互表示,则成这两个向量等价

线性相关和线性无关

定义:(超级无敌重要啊啊啊啊啊

  1. 给定一向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_m$,如果存在不全为零的数 $k_1,k_2,\cdots,k_m$,使得 $k_1\alpha_1+k_2\alpha_2+\cdots+k_m\alpha_m = \theta$,那么称向量组A是线性相关

  2. 如果只有当 $k_1=k_2=\cdots=k_m=0$ 时,上述等式才成立,那么就是线性无关

线性相关的充要条件是:$x_1\alpha_1+x_2\alpha_2+\cdots+x_m\alpha_m = \theta$($Ax = \theta$) 有非零解

最基本的结论:

  1. 一个向量线性相关的充要条件是: $\alpha = \theta$

  2. 一个向量线性无关的充要条件是: $\alpha \neq \theta$

  3. 包含零向量的向量组是线性相关的

  4. 如果一个向量组的部分向量组线性相关,则该向量组也线性相关

  5. 如果一个向量组线性无关,则其中任一个部分分量也线性无关

定理:

  1. 向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_m$($m \geq 2$)线性相关的充要条件是:向量组A中至少有一个向量可由其余 m-1 个向量线性表示

  2. 向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_m$($m \geq 2$)线性无关的充要条件是:其中任何一个向量都不能由其余向量线性表示

  3. 设向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_r$ 线性无关,而向量组B:$\alpha_1,\alpha_2,\cdots,\alpha_r,\beta$ 线性相关,则向量 $\beta$ 必可由向量组A线性表示,并且表达式唯一

  4. 设向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_r$ 线性无关,则向量组B:$\alpha_1,\alpha_2,\cdots,\alpha_r,\beta$ 线性无关的充分必要条件是向量 $\beta$ 不可能由向量组A线性表示

向量线性相关性与矩阵秩的关系

  1. n维列向量组A:$\alpha_1,\alpha_2,\cdots,\alpha_r$ 线性相关的充要条件是: $r(A) < r$,线性无关的充要条件是: $r(A) = r$

    • 向量个数m大于维数n,则该向量组线性相关
  2. n个n维向量线性无关的充要条件是其行列式不为0

  3. 设 $A_{m \times n}$ 的秩 $r(A) = r \leq m$ ,且 A 的某 r 列(行)组成的矩阵含有不等于零的r阶子式,则此 r 列(行)向量线性无关

极大无关组和向量组的秩

极大无关组定理推论:

  1. 设 $\alpha_{i_1},\alpha_{i_2},\cdots,\alpha_{i_r}$ 是向量组 $\alpha_1,\alpha_2,\cdots,\alpha_m$ 的一个极大无关组,则向量组 $\alpha_1,\alpha_2,\cdots,\alpha_m$ 中的任一向量可由 $\alpha_{i_1},\alpha_{i_2},\cdots,\alpha_{i_r}$ 线性唯一表示

  2. 一个向量组的各个极大无关组所含向量个数相同

  1. 向量组和它的极大无关组等价

  2. 一个向量组的各个极大无关组是等价的

  3. 两个向量组等价的充要条件是:一组的一个极大无关组与另一组的一个极大无关组等价

向量组的秩:

  1. 等价的向量组必有相同的秩

  2. 任一矩阵的秩与其行秩、列秩相等

  3. 秩的重要性质

    • $r(A + B) \leq r(A) + r(B)$

    • $r(AB) \leq min\{r(A),r(B)\}$

    • 若A,B都为n阶方阵,$r(AB) \geq r(A) + r(B) - n$

秩的不等式

  1. $0 \leq r(A) \leq min(m, n)$

  2. $r(kA) = r(A)$

  3. $r(A) = r(A^T) = r(AA^T) = r(A^TA)$

  4. 对于$n \times n$矩阵$A$,有 $r(A^n) = r(A^{n+1})$

  5. $max(r(A),r(B)) \leq r(A,B) \leq r(A) + r(B)$

  6. $r(A + B) \leq r(A, B)$

  7. $r(AB) \leq min(r(A), r(B))$

  8. $r(\left(\begin{matrix}
    A & O \\
    O & B \\
    \end{matrix}\right)) = r(A) + r(B)$

  9. $r(A) + r(B) \leq r(\left(\begin{matrix}
    A & O \\
    C & B \\
    \end{matrix}\right)) \leq r(A) + r(B) + r(C)$

  10. $r(AB) \geq r(A) + r(B) - n$

  11. 若 $AB = O$,则 $r(A) + r(B) \leq n$,其中n是A的列数

线性代数组解的结构

线性方程组的可解性

线性方程组有解的充要条件是:系数矩阵A的秩等于增广矩阵B的秩

  • $r(A) = r(B) = n$ 时,方程组有唯一解
  • $r(A) = r(B) \leq n$ 时,方程组有无穷多组解
  • $r(A) \neq r(B)$ 时,方程组无解

齐次方程组解的结构

  1. 若 $\alpha_1,\alpha_2$ 是方程组 $Ax = \theta$ 的解,则其线性组合 $k_1\alpha_1 + k_2\alpha_2$ 也是该方程组的解

  2. 设 $A \in R^ { m \times n}$,若 $r(A) = n$ 时,则 $Ax = \theta$ 只有零解;若 $r(A) < n$,则 $Ax = \theta$ 有非零解

    • 方程组 $r(A) = n$,$A \in R^ { m \times n}$ 有非零解的充要条件是:|A| = 0

    • 若 $A \in R^ { m \times n}$,且m < n,则 $Ax = \theta$ 有非零解

  3. 若齐次方程有非零解,则该方程组的基础解系并不唯一

  4. 若齐次方程组的系数矩阵A的秩为r,则其基础解系的向量个数为$n-r$

非齐次方程组解的结构

若 $A\eta = b$($b \neq \theta$),则 $Ax = b$ 的通解为 $\eta + \alpha$

  • 其中 $\alpha$ 为 $Ax = \theta$ 的解(齐次方程的解
  • 若 $Ax = \theta$ 的基础解系为 $\alpha_1,\alpha_2,\cdots,\alpha_r$,则 $A\eta = b$ 的通解为$\eta + k_1\alpha_1 + k_2\alpha_2 + \cdots + k_r\alpha_r$

矩阵的特征值线性无关和特征向量

相似矩阵

对于同阶方阵A与B,如果存在可逆矩阵P,使得 $B = P^{-1}AP$,则称A相似于B,记为 $A \sim B$,P称为A到B的相似变换矩阵

  • 相似矩阵满足等价关系三个性质

相似矩阵性质:

  1. 若 $A \sim B$,则|A| = |B|,从而A和B可逆性相同

  2. 若 $A \sim B$,且A或B可逆,则 $A^{-1} \sim B^{-1}$

  3. 若 $A \sim B$,则 $A^n \sim B^n$,$kA \sim kB$

  4. 若 $A \sim B$,则 $f(A) \sim f(B)$,其中 $f(x) = \alpha_nx^n + \alpha_{n-1}x^{n-1}+\cdots +\alpha_1x^1+\alpha_0x^0$ 为任意多项式

  5. 相似矩阵具有相同的特征多项式,从而有相同的特征值

    • 特征多项式相同的矩阵未必相似
  6. 相似矩阵具有相同的迹和行列式

特征值和特征向量

特征多项式是:$|\lambda E - A| = 0$

  1. 设方阵A有特征值 $\lambda$,$\xi_1,\xi_2$ 是属于$\lambda$ 的特征向量,则它们的任意不等于零向量的线性组合 $\eta = k_1\xi_1 + k_2\xi_2$ 仍是属于 $\lambda$ 的特征向量

    • 属于 $\lambda$ 的特征向量有无数个
  2. 若 $f(x)$ 为x的多项式,矩阵A有特征值 $\lambda$,则 $f(A)$ 有特征值 $f(\lambda)$

  3. 若n阶可逆方阵A的所有特征值为 $\lambda_1,\cdots,\lambda_n$(包含相同的特征值),则 $\lambda_i \neq 0$,且矩阵 $A^{-1}$ 的特征值为 $\lambda_1^{-1},\cdots,\lambda_n^{-1}$

  4. 若n阶矩阵A的特征值为 $\lambda_1,\cdots,\lambda_n$

    • 主对角线之和等于特征值之和:$tr(A) = \sum_{i = 1}^n \lambda_i$
    • 行列式的值等于特征值的乘积:$|A| = \prod_{i = 1}^n \lambda_i$
  5. 设A是一个块对角矩阵,$A =
    \left(
    \begin{matrix}
    A_1 & & & \\
    & A_2 & & \\
    & & \ddots&\\
    & & & A_m
    \end{matrix}
    \right)$
    则A的特征多项式是 $A_1,A_2,\cdots,A_m$ 的特征多项式的乘积,于是 $A_1,A_2,\cdots,A_m$ 的所有特征值就是A的所有特征值

  6. m阶方阵AB与n阶方阵BA具有相同的非零特征值,且 $tr(AB) = tr(BA)$

  7. 属于不同特征值的特征向量线性无关

  8. 若 $\lambda_1,\lambda_2,\cdots,\lambda_n$ 是矩阵A的不同特征值,而A的属于 $\lambda_i$ 的线性无关的特征向量为 $\alpha_{i1},\alpha_{i2},\cdots,\alpha_{is_i}$,则向量组 $\alpha_{11},\cdots,\alpha_{1s_i},\alpha_{21},\cdots,\alpha_{2s_i},\cdots,\alpha_{m1},\cdots,\alpha_{ms_m}$ 线性无关

  9. 设 $\lambda_0$ 是n阶方阵A的k重特征值,则A的属于特征值 $\lambda_0$ 的线性无关的特征向量的个数不超过k

矩阵可对角化的条件

n阶矩阵可对角化的充要条件是:有n个线性无关的特征向量,且对角矩阵的主对角线由特征值组成,相似变换矩阵由属于相应特征值的特征向量构成

  • 若n阶矩阵有n个互不相同的特征值,则矩阵可对角化

n阶方阵可对角化的充要条件是:每个 $k_i$ 重特征值 $\lambda_i$ 对应的特征矩阵 $|\lambda_iE - A|$ 的秩为 $n-k_i$

向量内积

  1. $(\alpha,\beta)=(\beta,\alpha)$
  2. $(k\alpha,\beta)=k(\alpha,\beta)$
  3. $(\alpha+\gamma,\beta)=(\alpha,\beta) + (\gamma,\beta)$
  4. $(\alpha,\alpha)\geq0;(\alpha,\alpha)=0当且仅当\alpha = \theta$

若 $(\alpha,\beta)=0$,则称 $\alpha$ 和 $\beta$ 正交或垂直

正交向量和正交矩阵

若实矩阵满足 $A^TA=E$,则称A为正交矩阵

  • 若A,B是同阶的正交矩阵,那么AB也是正交矩阵
  • E也为正交矩阵

性质:

  1. 正交向量组必线性无关

  2. 对于方阵A,下面一些条件互为等价

    • A为正交矩阵

    • $A^T=A^{-1}$

    • $AA^T=E$

    • A的列向量构成标准正交列向量组

    • A的行向量构成标准正交行向量组

  3. 设A是n阶正交矩阵,$\lambda$ 是A的特征值,$\alpha$ 为n维列向量

    • $|A|^2=1$(重要)

    • $(A\alpha)^T(\overline{A\alpha})=\alpha^T\overline{\alpha}$

    • $|\lambda|=1$(也重要)

实对称矩阵对角化

实对称矩阵一定可以对角化

性质:

  1. 实对称矩阵的特征值均是实数

  2. 实对称矩阵的属于不同特征值的特征向量相互正交

  3. 设有实n维单位列向量 $\beta$,则比能找到 n-1 个向量与 $\beta$ 一起构成由n个向量组成的标准正交向量组

  4. 若A是实对称矩阵,则存在同阶的正交矩阵P使得 $P^TAP$ 是实对角矩阵,从而实对称矩阵可以对角化

实二次型

线性变换

定义:$x = cy$(宋浩说x一定写在前面,我觉得怎么不用

线性变换系数行列式为$|P| = \begin{vmatrix}
c_{11} & c_{12} & \cdots &c_{1n}\\
x_{21} & x_{22} & \cdots &x_{2n}\\
\vdots & \vdots & &\vdots\\
x_{n1} & x_{n2}& \cdots &x_{nn}\\
\end{vmatrix}$

  • 如果$|P| \neq 0$,称为非异线性变换非退化线性变换

  • 如果$|P| = 0$,称为奇异线性变换退化线性变换

  • 如果P为正交矩阵,则称为正交变换

合同

定义:同阶方阵A、B之间存在一个可逆矩阵P,使得$B = P^TA\:P$,那么称为A合同于B

  • P称为A到B的合同变换矩阵

合同关系是一个等价关系

二次型化简

矩阵表示:$f(x_1,x_2,\cdots,x_n) = x^TA\:x$

  • A是对称矩阵

定理

  1. 存在非退化的线性变换将实二次型化为标准形,且平方项系数可以任意次序排列

  2. 存在可逆矩阵将实对称矩阵合同变换为实对角矩阵,且对角元素可以任意次序排列

化简方法

  • 正交矩阵法

    1. 求解矩阵A的特征方程$|\lambda E-A| = 0$

    2. 求出基础解系

    3. 将标准正交化的特征向量作为列构成正交矩阵$P= \left(\begin{matrix}
      p_{11} & p_{12} & p_{13}\\
      p_{21} & p_{22} & p_{23}\\
      p_{31} & p_{32}& p_{33}\\
      \end{matrix}\right)$

    4. 得到线性变换$\begin{cases}
      x_1 = p_{11}y_1 + p_{12}y_2 + p_{13}y_3\\
      x_2 = p_{21}y_1 + p_{22}y_2 + p_{23}y_3\\
      x_3 = p_{31}y_1 + p_{32}y_2 + p_{33}y_3
      \end{cases}$

  • 配方法

    1. 式中有非零平方项比如$a_{11}x_1^2$:将式中所有含$x_1$的项配成一个平方项$a_{11}(x_{11} + \frac{a_12}{a_11}x_2 + \cdots + \frac{a_{1n}}{a11}x_n)^2$,并令非退化线性变换为$\begin{cases}
      y_1 = x_1 + \frac{a_{12}}{a_{11}}x_2 + \cdots + \frac{a_{1n}}{a_{11}}x_n\\
      y_2 = x_2\\
      \cdots \cdots \\
      y_n = x_n
      \end{cases}$
      即可把原式化为不含$x_1$和$y_1$的交叉项的式子

    2. 式中无非零平方项:可以用一个线性变换配出平方项,例如$2a_{12}x_{1}x_{2}$,则作如下非退化线性变换
      $\begin{cases}
      x_1 = y_1 + y_2\\
      x_2 = y_1 - y_2\\
      x_3 = y_3 \\
      \cdots \cdots \\
      x_n = y_n
      \end{cases}$,然后再按情况一处理

  • 合同变换法

    1. 设二次型矩阵为$A = \left(\begin{matrix}
      a_{11} & a_{12} & \cdots &a_{1n}\\
      a_{12} & a_{22} & \cdots &a_{2n}\\
      \vdots & \vdots & &\vdots\\
      a_{n1} & a_{n2}& \cdots &a_{nn}\\
      \end{matrix}\right)$

    2. 对矩阵$B = \left(\begin{matrix}
      A \\
      E \\
      \end{matrix}\right)$ 做一次初等列变换后接着做一次对应的初等行变换,重复这种做法,直到得到$\left(\begin{matrix}
      \Lambda \\
      P \\
      \end{matrix}\right)$,然后P的用法参考正交矩阵法

二次型的规范形

惯性定理:存在非退化的线性变换将实二次型化为实规范形 $z_1^2 + \cdots + z_p^2 - z_{p + 1}^2 - \cdots - z_r^2$ ;存在实可逆矩阵将实对称矩阵合同变换为 $diag(E_p,-E_{r-p},O_{n-r})$,其中r是二次型矩阵的秩

推论

  1. 实二次型矩阵A的正特征值个数为正惯性指数,负特征值个数为负惯性指数,非零特征值个数为二次型的秩

正定二次型

若A为n阶是实对称矩阵,则下列条件互为等价:

  • 半正定等情况类似

    1. A为正定矩阵

    2. A的特征值为正

    3. A的正惯性指数为n

    4. A的各阶顺序主子式都为正

线性空间与线性变换

数环

属于集合 $R$ 的任意两个数的和、差、积仍属于 $R$,则称这个集合 $R$ 为数环

  • 任何数环必有0

数域

若 $K$ 是至少含有两个互异数的数环,且其中任何两个数之商仍属于 $K$ ,则称这个集合 $K$ 为数域

  • 任何数域必有0和1

线性空间

设 $V$ 是一个非空集合,$K$ 是一个属于,V满足以下两个条件:

  1. 在 $V$ 中定义一个封闭的加法运算,即当 $x,y \in V$ 时,有唯一的 $z = x + y \in V$,且满足:

    • $x + y = y + x$

    • $x + (y + z) = (x + y) + z$

    • 存在零元素 $0 \in V$,对 $V$ 中任意元素 $x$,都有 $x + 0 = x$

    • 存在负元素:对任一元素 $x \in V$,存在一个元素 $y \in V$,使得 $x + y = 0$,称 $y$ 为 $x$ 的负元素,记为 $-x$,即 $x + (-x) = 0$

  2. 在 $V$ 中定义一个封闭的数乘运算,即当 $x \in V,\lambda \in K$ 时,有唯一的 $\lambda x \in V$,且满足:

    • $(\lambda + \mu)x = \lambda x + \mu x$

    • $\lambda(x + y) = \lambda x + \lambda y$

    • $\lambda(\mu x) = (\lambda \mu)x$

    • $1\cdot x = x$

我们称 $V$ 是属于 $K$ 上的线性空间,记作 $V(K)$

性质:

  1. 线性空间的零元素是唯一的

  2. 线性空间中任一元素的负元是唯一的

  3. 设 $0,1,-1,\lambda \in K,x,-x,0 \in V$,则有:

    • $0x = 0$

    • $(-1)x = -x$

    • $\lambda 0 = 0$

    • 若 $\lambda x = 0$,则 $\lambda = 0$ 或 $x = 0$

只含一个元素的线性空间称为零空间

  • 那个元素就是零元素

基与坐标

设 $V$ 是数域 $K$ 上的线性空间,

  1. 如果在 $V$ 中可以找到任意多个线性无关的向量,则称 $V$ 是无限维线性空间

  2. 如果存在有限多个向量 $a_1, a_2, \cdots, a_n \in V$,满足:

    1. $a_1, a_2, \cdots, a_n$ 线性无关

    2. $V$ 中任一向量都可由 $a_1, a_2, \cdots, a_n$ 线性表示

      则称 $V$ 是有限维线性空间,称 $a_1, a_2, \cdots, a_n$ 是V的一组基底),$a_i$ 叫第 $i$ 个基向量,基向量的个数 $n$ 称为线性空间的维数,记为 $dim(V) = n$,并称 $V$ 是 $n$ 维线性空间

定理:

  1. 设 $a_1, a_2, \cdots, a_n$ 是 $n$ 维线性空间 $V$ 的一组基,对任意 $a \in V$,$a$ 可以唯一地由这一组基线性表出

    设 $a_1, a_2, \cdots, a_n$ 是 $n$ 维线性空间 $V$ 的一组基,对任意 $a \in V$,若有一组有序数 $x_1,x_2,\cdots,x_n$ 使得 $a$可表示为 $a = x_1a_1 + x_2a_2 + \cdots + x_na_n$,这组有序数就称为向量 $a$ 在基 $a_1, a_2, \cdots, a_n$ 下的坐标,记为 $x = (x_1,x_2,\cdots,x_n)$ 或 $x = (x_1,x_2,\cdots,x_n)^T$

基变换和坐标变换

设 $\alpha_1, \alpha_2, \cdots, \alpha_n$ 和 $\beta_1,\beta_2,\cdots,\beta_n$ 是 $n$ 维线性空间 $V$ 的两组基,并且 $(\beta_1,\beta_2,\cdots,\beta_n) = (\alpha_1, \alpha_2, \cdots, \alpha_n)P$,若 $V$ 中任意元素 $\alpha$ 在这两组基下的坐标分别是 $(x_1,x_2,\cdots,x_n)$ 和 $(y_1,y_2,\cdots,y_n)$

  • 存在 $(y_1,y_2,\cdots,y_n)^T = P^{-1}(x_1,x_2,\cdots,x_n)^T$

子空间

线性空间 $V$ 的一个非空子集 $W$ 是 $V$ 的子空间的充要条件

  1. 对任意 $\alpha , \beta \in W$,有 $\alpha +\beta \in W$,即对加法封闭

  2. 对任意 $\alpha \in W,\lambda \in K$,有 $\lambda \alpha \in W$,即对数乘封闭

线性空间 $V$ 的一个非空子集 $W$ 是 $V$ 的子空间的充要条件

  1. 对任意的 $\alpha , \beta \in W,\lambda,\mu \in K$,有 $\lambda \alpha +\mu \beta \in W$

齐次方程组的全体解向量是 $R^n$ 的一个非空子集 $W$ ,则 $W$ 是 $R^n$ 的一个子空间,该齐次方程组的任一组基础解系是 $W$ 的一组基,若这个方程组系数矩阵的秩为 $r$ ,则 $dim(W) = n -r$

  • 这个子空间称为齐次方程组的解空间

子空间的交与和

  1. 数域 $K$ 上线性空间 $V$ 的两个子空间 $W_1,W_2$的交与和仍是$V$ 的子空间

  2. 若 $W_1,W_2$ 是线性空间 $V$ 的两个有限维子空间,则 $dim(W_1) + dim(W_2) = dim(W_1 + W_2) + dim(W_1 \cap W_2 )$

子空间的直和

若 $W_1 + W_2$ 中任一向量都只能唯一地表示为子空间 $W_1$ 的一个向量与子空间 $W_2$ 的一个向量和,则称 $W_1 + W_2$ 是直和,记为 $W_1 \oplus W_2$

定理:

  1. $W_1 + W_2$ 是直和的充要条件:$W_1 \cap W_2 = \{0\}$

  2. $W_1 + W_2$ 是直和的充要条件:$dim(W_1 + W_2) = dim(W_1) + dim(W_2)$

若 $W_1,W_2,\cdots W_m$ 是线性空间 $V$ 的子空间,若

  • $W_1 + W_2 +\cdots +W_m = V$

  • $W_1 \cap W_2 = \{0\},(W_1 + W_2) \cap W_3 = \{0\}, \cdots ,(W_1 + W_2 + \cdots + W_{m-1}) \cap W_m = \{0\}$

则 $V$ 是 $W_1,W_2,\cdots W_m$ 的直和

线性变换

如果 $V_1$ 到 $V_2$ 的映射满足:$T(\lambda \alpha +\mu \beta) = \lambda T \alpha + \mu T \beta$,则称 $T$ 为 $V_1$ 到 $V_2$ 的线性映射

  • 其中 $\alpha,\beta \in V_1,\lambda \in K$

  • 在 $V_1 = V_2 = V$ 时,称这个 $T$ 为 $V$ 上的线性变换

线性映射性质

  1. $T0 = 0$

  2. 对任意的 $\alpha_1,\alpha_2,\cdots,\alpha_m \in V_1$,有 $T(K_1\alpha_1 + k_2\alpha_2 + \cdots k_m\alpha_m) = k_1T\alpha_1 + k_2T\alpha_2 + \cdots + k_mT\alpha_m$

  3. 若 $\alpha_1,\alpha_2,\cdots,\alpha_m$ 线性相关,则 $T\alpha_1,T\alpha_2,\cdots,T\alpha_m$ 也线性相关

特殊的线性变换:

  • 数乘变换:对任意 $\alpha \in V$,有 $T_k\alpha = k\alpha$

  • 恒等变换:$T\alpha = \alpha$

  • 零变换:$T\alpha = 0$

像空间和核空间

若 $V_1,V_2$ 都是数域 $K$ 上线性空间,有线性映射$T:V_1 \rightarrow V_2$

  • 像空间:$V_1$ 中所有元素的像的集合

  • 核空间:集合 $N = N(T) = \{\alpha:T\alpha = 0,\alpha \in V_1\}$,记作 $ker(T)$

定理:

  1. 线性映射的像空间和核空间是线性子空间

线性变换的矩阵表示

定义

  1. 设线性变换的矩阵为 $A$,则存在 $(T\varepsilon_1,T\varepsilon_2,\cdots,T\varepsilon_n) = (\varepsilon_1,\varepsilon_2,\cdots,\varepsilon_n)A$

    • $A$ 的第 $i$ 个列向量是 $T\varepsilon_i$ 在基 $\varepsilon_1,\varepsilon_2,\cdots,\varepsilon_n$ 下的坐标
  2. 设由基底 $\varepsilon_1,\varepsilon_2,\cdots,\varepsilon_n$ 到 $\omega_1,\omega_2,\cdots,\omega_n$ 的过度矩阵为 $P$,也就是 $(\omega_1,\omega_2,\cdots,\omega_n) = (\varepsilon_1,\varepsilon_2,\cdots,\varepsilon_n)P$,而且线性变换的矩阵分别为 $A,B$,那么有以下结论:

    • $B = P^{-1}AP$,可以看出 $P$ 必须可逆

    • $A$ 相似于 $B$

定理

  1. 对 $V$ 的两个线性变换 $T_1,T_2$,有 $T_1 \varepsilon_i = T_2\varepsilon_i$,则 $T_1 = T_2$

  2. $A \sim B$ 的充要条件它们是 $n$ 维的线性空间 $V$ 上的某个线性变换 $T$ 在不同基底下的矩阵

线性变换的特征值和特征向量

特征子空间:线性变换 $T$ 对应于特征值 $\lambda$ 的子空间 $V_{\lambda} = \{\xi \in V:T\xi = \lambda \xi\}$

  • 包括对应于 $\lambda$ 的所有特征向量和零向量

最简表示:线性变换 $T$ 在某组基上的矩阵为对角矩阵

定理:

  1. 有限维线性空间上的线性变换的特征值和特征多项式与所选基底无关

  2. 设 $\lambda_1,\lambda_2,\cdots,\lambda_s$ 是线性变换 $T$ 的 $s$ 个互异的特征值,$\xi_i$ 是属于特征值 $\lambda_i$ 的特征向量,则 $\xi_1,\xi_2,\cdots,\xi_s$ 线性无关

  3. $n$ 维线性空间上的一个线性变换 $T$ 有最简表示的充要条件: $T$ 有 $n$ 个线性无关的特征向量

    • $T$ 有 $n$ 个互异的特征值(充分条件
  4. 若 $\xi_1,\xi_2,\cdots,\xi_s$ 和 $\nu_1,\nu_1,\cdots,\nu_s$ 分别是线性变换 $T$ 不同特征值的线性无关的特征向量,则 $\xi_1,\xi_2,\cdots,\xi_s$;$\nu_1,\nu_1,\cdots,\nu_s$ 线性无关

  5. 若 $\lambda_0$ 是线性变换 $T$ 的 $s$ 重特征值,则属于 $\lambda_0$ 的特征向量中,线性无关的最大组包含的向量个数不超过 $s$

概述

  • 对于不同帧使用同一方案进行处理
  • 希望通过路由选择算法进行路径选择和转发,对第二层是透明的
  • 只能避免拥塞,不能流量控制

职责

  • 使用分层寻址方案,方便逐步细化目的地地址
  • 细分网络并控制流量
  • 减少交通堵塞,基于IP做分段和传达,用来减少拥塞
  • 与其他网络交谈
  • 对于不同的数据链路层的帧,第三层基于IP协议,来实现跨介质的逻辑理解和互通
  • 负责进行连通和传达,数据可靠性由终端设备(第四层及以上)来进行保证

    路由器

    • 互连网段或网络(分割网段)
    • 根据IP地址做出合理的决定
    • 根据路由表确定最佳路径
    • 将数据报从入站端口切换到出站端口
  1. 如果A网段的设备向路由器发送了一个B网段的广播地址,那么路由器会进行转发
  2. 如果A网段的设备发送的是本网段的广播地址,那么路由器不会进行转发(广播域划分)

IP协议

网际协议IP是TCP/IP体系中两个最主要的协议之一,配套使用的还有三个协议:

  • 地址解析协议ARP(Address Resolution Protocol)
  • 网际控制报文协议ICMP(Internet Control Message Protocol)
  • 网际组管理协议IGMP(Internet Group Management Protocol)

IP数据报格式

数据格式常以32位(4字节)为单位来描述

IP数据报格式_片偏移怎么计算_小皮子摘星星的博客-CSDN博客

  • 首部的前一部分是固定长度,共20字节
  • 首部固定部分后面是一些可选字段,长度可变

首部固定部分中的各字段:

  1. 版本:IP协议的版本,共4位,广泛使用的版本是IPv4

  2. 首部长度:首部长度的表示单位是32位字(4字节),可表示的最大十进制数值是15,共4位

    • 由于首部的固定长度是20字节,所以首部长度字段最小值为5,最大值为60字节($15 \times 4 = 60$)
    • IP分组的首部长度不是4的字节时,必须利用最后的填充字段加以填充,因此数据部分永远在4字节的整数倍开始
    • 最常用的是20字节,即首部长度为0101
  3. 区分服务:在旧标准中叫做服务类型,共8位,一般情况不使用这个字段

  4. 总长度:首部和数据部分的长度和,单位为字节,共16位

    • 数据链路层设置了最大传输单元MTU,因此数据报的总长度不能超过规定的MTU值,不然会将数据报进行分片处理
  5. 标识(identification):IP软件在存储器中维持一个计数器,每产生一个数据报计数器+1,并将此值赋给标识字段,当产生分片时就将标识字段的值复制给每一个分片,便于重装为完整的数据报,共16位

  6. 标志(flag):共3位,但只有两位有意义

    • 最低位为MF(More Fragment),MF = 1表示后面还有分片,MF = 0表示这时若干数据报片的最后一个
    • 中间一位是DF(Don’t Fragment),表示不能分片,只有DF = 0才允许分片
  7. 片偏移:指出分片在原分组的相对位置(相对于起点在何处开始),偏移单位为8字节,共13位

  8. 生存时间:数据报在网络中的寿命,防止无法交付的数据报无限制地在互联网中兜圈子,现在功能为跳数限制(至多可经过几个路由器),共8位

  9. 协议:指出数据报携带的数据是使用何种协议,共8位

  1. 首部校验和: 这个字段只检验数据报的首部,共16位

  2. 源地址:共32位

  3. 目的地址:共32位

首部可变部分:
可变部分就是一个选项字段,选项字段用来支持排错、测量以及安全等措施,内容很丰富,最后用全0的填充字段补齐成为4字节的整数倍

IP地址

IP地址就是给互联网上的每一台主机(或路由器)的每一个端口分配一个在全世界范围内唯一的32位标识符

IP地址分为若干类,但都由两个固定长度的字段组成,分别是网络号主机号
如何对IP地址进行子网划分?

  • D类地址为组播/多播(一对多)
  • 通常写法是点分十进制(每8位二进制加一个点)

A类:0 ~127
B类:128~191
C类:192~223
D类:224~239
E类:240~255

A类网络号只有7位可指派,但是一般不能指派全0和全1

  • 全0表示本网络
  • 全1用于环回测试(根本不是一个网络地址)

B类网络号只有14位可指派,但是网络地址128.0.0.0是不指派的

  • B类开始IP地址是128.0.0.1

C类网络号只有21位可指派,但是网络地址192.0.0.0是不指派的

  • C类开始IP地址是192.0.0.1

主机号一般不能取全0,也不能取全1

  • 全0用来标识网段地址
  • 全1用来表示网段的广播地址

一般不使用特殊IP地址 的图像结果

  • 用交换机或网桥连接起来的若干个局域网仍属于一个网络
  • IP地址是一种逻辑地址

划分子网和构造超网

早期IP地址的设计不够合理,主要体现在:

  • IP地址空间利用率有时很低
  • 两级IP地址不够灵活

划分子网(subnetting):在IP地址中增加一个子网号字段,也叫做子网寻址或者子网路由选择

  • 主机号借用若干位作为子网号,从而变成三级IP地址:网络号、子网号、主机号
  • 减小了广播域,提高网络利用率

子网可以借用的位数:

  • 最小位数是2:当只借用1位时就只能表示本网络和广播
  • 最大位数可以是保留至少2位主机号的任何数字
    • A类20位
    • B类14位
    • C类6位
  • 借用4位是最高效率的

32位IP地址本身以及数据报首部都没有包含任何有关子网划分的信息,因此我们可以使用子网掩码(subnet mask)来确认数据报属于哪个子网

  • 把网络号和子网号全赋1,主机号全赋0
    计算机网络子网划分相关知识点 | 张甲博客

子网掩码和IP地址逐位相与,就可以得到子网的网络地址
IP2——IP地址和子网划分学习笔记之《子网掩码详解》 - 白灰 - 博客园

  • 不管有没有划分子网,与运算后都能得出网络地址

默认子网掩码

  • A类:255.0.0.0
  • B类:255.255.0.0
  • C类:255.255.255.0

子网数 = $2 ^ n$ - 2

  • 子网号有n位
  • 除去全0和全1(实际上在CIDR协议中已经可以使用这两种情况了)

无分类编制CIDR(构建超网)
在一个划分子网的网络中可同时使用几个不同的子网掩码,使用可变子网掩码VLSM(Variable Length Subnet Mask)可进一步提高IP地址资源利用率。在VLSM的基础上又进一步研究出无分类编制路由选择CIDR(Classless Inter-Domain Routing)

  1. 网络前缀

    CIDR消除了传统的A类、B类、C类地址以及划分子网的概念,而是把互联网地址分为网络前缀和主机号

    • 使用斜计线法(CIDR记法),即在IP地址后面加上斜线“\”,然后写上网络前缀所占的位数
    • 网络前缀相同的连续IP地址组成一个“CIDR地址块”,我们只要知道CIDR地址块中任何一个地址,就可以知道起始地址和最大地址以及地址数

      为了更方便的进行路由选择,CIDR使用32位的地址掩码(address mask),也可以继续称作子网掩码

    • 网络前缀赋为1,主机号赋为0
    • 分配到地址块后仍可以划分子网,但是借用的位应当加入到网络前缀

      路由表利用CIDR地址块查找目的网络,这种地址的聚合常称为路由聚合(route aggregation),也称为构成超网

      CIDR记法有多种形式:

    • 地址块10.0.0.0/10可以简写为10/10,也就是把点分十进制中低位连续的0省略
    • 在网络前缀的后面加个*,例如00001010 00*,意思是*之前是网络前缀,*之后是主机号,可以是任意数字

      从表格可以看出,除了最后几行,CIDR地址块都包含了多个C类地址($2^n$倍),这就是构成超网一词的由来划分子网和构造超网之无分类编址 CIDR_ 融合统一通信常见问题

    • 网络前缀越短,包含的地址数越多
  2. 最长前缀匹配(最长匹配/最佳匹配)
    路由表项目和由网络前缀下一跳地址组成

    • 可能查找路由表时不止一个结果

应该在匹配结果中选择具有最长网络前缀的路由

  1. 利用二叉线索查找路由表
    先找出对应于每一个IP地址的唯一前缀
    • 唯一前缀就是在表中所有IP地址中,该前缀是唯一的

二叉线索查找路由表 的图像结果

路由器

路由器有两个功能:路径选择、分组转发
二叉线索查找路由表 的图像结果

  1. 分组转发

    • 在分类子网划分时,全0代表本机地址,全1代表广播地址
    • 做转发根据的是网段而不是具体的IP
  2. 路径选择
    路由器根据路由规范,选择他当时认为最合适的路径

    • 选择数据包到达目的地的路径中的下一跳

路由器端口:

接口是路由器连接到网络的附件,在IP路由中也可以称为端口

  • 这个IP地址往往被称作这个网络的网关
  • 每个接口必须有一个单独的唯一网络地址
    • 比如S1和S2不能相同
    • 路由器的连接的网段一定要不同·

  1. 路由器端口记录了网段的IP地址(和连接的地方是相同的)
  2. 在计算需要分配的端口总数时,注意路由器的端口也需要算上

IP地址分配:

  1. 静态地址分配(Static addressing)

    • 为每个单独的设备配置一个IP地址
    • 保证不重复
    • 需要知道规范,通过命令行进行分配
  2. 动态地址分配(Dynamic addressing)

    • 反向地址解析RARP(Reverse Address Resolution Protocol):发起请求根据IP地址信息来分配
    • BOOTStrap协议(BOOTP):用于工作栈
    • 动态主机配置协议DHCP(Dtnamic Host Configuration Protocol):IP地址和掩码处理后得到网络地址,保证每个网段中的主机的网段地址一致

地址解析协议ARP

ARP协议通过IP地址解析出MAC地址

  • 在IP层抽象的互联网上只能看到IP数据报
  • 在局域网的链路层只能看见MAC帧

ARP协议在主机ARP高速缓存中存放一个从IP地址到硬件地址的映射表,并且动态更新

  • 每台主机都设有一个ARP高速缓存(ARP cache),里面有本局域网各主机和路由的IP地址到硬件地址的映射表(已知)

主机A向本局域网上的主机B发送IP数据报过程:

  1. 先在ARP高速缓存中查看有无主机B的IP地址

    • 如果有就查出硬件地址并写入MAC帧,然后发送
    • 如果无就进行下面步骤
  2. 广播发送ARP请求分组,内容为自身IP地址、自身硬件地址、想知道IP地址为xxx的主机的硬件地址

    • 写入自身信息是便于以后主机B向主机A发送数据报
  3. IP地址一致的主机B收下ARP请求分组,并发送ARP响应分组,内容是自身IP地址、自身硬件地址

    • ARP响应分组是单播
  4. 主机A收到ARP响应分组后就写入ARP高速缓存

主机发送给另一个网络上的另一主机数据报时,应该先找到相应的路由器进行转发,这时需要把路由器的IP地址解析为硬件地址

为了使设备与另一网络上的零一设备通信,必须提供默认网关

  • 默认网关就是路由器连接到源主机所在网段的接口的IP地址

ARP四种典型情况:
网络层(七)地址解析协议ARP_数学家是我理想的博客-CSDN博客

  1. 主机$H_1$发送数据报到同一网络上的另一主机$H_2$。这时$H_1$发送ARP请求分组,找到$H_2$的硬件地址

  2. 主机$H_1$发送数据报到零一网络上的另一主机$H_3$或$H_4$,这时$H_1$发送ARP请求分组,找到路由器$R_1$的硬件地址,剩下的交给$R_1$,即下面的3和4

  3. 路由器$R_1$把数据报转发到与$R_1$相连的网2的主机$H_3$,这时$R_1$发送ARP请求分组,找到$H_3$的硬件地址

  4. $R_1$要把数据报发送到网3上的主机$H_4$,这时$R_4$发送ARP请求分组,找到$R_2$的硬件地址,剩下的交给$R_2$

网络层设备

面向连接的网络服务

在任何发送数据的行为之前,要先建立好连接,协商好参数才会开始传输,所有数据有序传输

  • 网络情况导致数据出现问题,需要接收方进行一定处理来保证数据正确
  • 传输过程要保持连接距离,只有完成传输才能断开连接
  • 传输比较可靠,代价高

无连接的网络服务

不要求发送方和及受访在发送前先建立一个连接,分别对待每一个数据包,系统不需要进行大量的数据保留,不需要很多的缓存

  • 局域网使用比较多,可靠性比较低,不处理报文丢失
  • 少量报文使用无连接可以调高效率(可靠网)

IP就是提供无连接的网络服务

电路交换(Circuit Switched)

电路交换要先建立一个虚电路关系,之后报文走对应的虚电路

  • 所有数据包依次在同一虚拟通道上传播
    • 电路利用效率低
    • 可能是分段建立,可能局部可以复用,但是整体不可以复用
  • 虚电路强于面向连接,传输更可靠,保证传输先后关系

报文交换(Packet Switched

当数据包从源传递到目标时,它们可以:

  1. 切换到其他路径(根据当前的网络情况,进行路由选择)
  2. 乱序到达

将原始数据分为很多子报文,每个子报文自己选择路径进行发送

  • 设备根据各种标准为每个数据包确定路径,某些标准可能因分组而异
  • 大部分无连接网络都是基于报文交换实现的,可以控制网络拥塞
  • 出现问题时只需要重传对应部分的报文

网络协议操作

被动路由协议用于路由器之间,保证路由器之间连通

主动路由用于做各自路由表的生成,路由器彼此交换信息

routed protocol是用来使用路由表的
routing protocol是用来生成路由表的
routing protocol决定routed protocol

  • 存在冗余,A转发给B是由当前网络状况处理
  • ABC之间都是通过帧来今进行计算的

被动可路由协议Routed protocol

路由协议或可路由协议是为网络层提供支持的协议

  • IP是网络层协议,因此它可以通过互联网进行路由(routed)

不可路由协议Non-routable protocol

不可路由协议是不支持第三层的协议,最常见的是NetBEUI

  • 直接根据目的方的地址在局域网中进行生成定位
  • 跨局域网也不支持第三层
  • NetBEUI仅限于在一个网段上运行

routing protocol是主动可路由协议也就是Dynamic routes

被动可路由协议的寻址:

将目的主机和子网掩码进行逻辑与运算得到对应的网段,然后请求路由表可以发现某个端口为目的网段,接着将报文封装转发给对应的主机

  • 路由表存储在内存中

路由协议的分类

  1. 静态路由
    网络管理员在路由器中手动输入路由信息

    • 用于隐藏部分网络,安全(不进行路由表交换)
    • 测试网络中的特定链接
    • 用于仅在到达目标网络的路径时维护路由表
  2. 动态路由
    路由器在运行过程中互相学习信息,使用路由协议更新路由信息,如RIP、IGRP、EIGRP、OSPF等,人工维护代价比较大

    • 维护路由表
    • 以路由更新的形式即使分发信息
    • 路由器可以调整以适应不停变化的网络状况
    • 打开后会启动进程,按照不同的协议和网上的不同设备学习信息,然后根据算法生成路由表

主动路由协议Routing protocol也是动态路由

  • 路由协议确定路由协议遵循的到达目的地的路径
  • 用来构建路由表
  • 公平、简单、适应变化

动态路由协议分类

  1. 内部网关协议(Interior Gateway Protocols):

    例如RIP,IGRP,EIGRP,OSPF等,可在自治系统中使用

    • 自治系统是逻辑的划分,而不是物理层次的划分
    • IGP是内部确定的管理规则

      分类:

    1. 距离矢量协议DVP(Distance-Vector Protocols)

      例如RIP、IGRP

      • 邻居的角度查看网络拓扑(不是全局)
      • 在路由器之间添加距离向量(根据跳数决定和)
      • 经常会定期更新
      • 将路由表副本传递到邻居路由器

        示例:

        • 只知道最少跳数(不知道最佳路径
        • 定时路由表会相互交换给邻居

        DVP的代表RIP(Routing Information Protocol):

        基于距离矢量的内部网关协议,唯一指标是跳数,选择走跳数最短的路径而非最快的路径,最受欢迎

        • 最大跳数是15
        • 每30秒更新一次(广播),可以修改
        • RIP v2是RIP v1的改进版本,更加常用

        IGRP(Interior Gateway Routing Protocol) 和 EIGRP(Enhanced IGRP):

        基于距离矢量的内部网关协议,指标由带宽、负载、延迟、可靠性组成,EIGRP是IGRP的高级版本,它是混合路由协议(不全根据跳数计算)

        • IGRP最大跳数为255
        • 每90秒更新一次
    2. 链路状态协议LSP(Link State Protocols)

      例如OSPF

      • 获取整个网络拓扑的通用视图(全局)
      • 计算到其他路由器的最短路径
      • 事件触发的更新
      • 将链路状态路由更新传递给其他路由器

        LSP操作过程:

      1. 相互交换彼此学到对应的Topological Database(全局)
      2. 使用SPF算法,以自己为根,通过最短路径优先算法,生成以自己为根的树
      3. 根据这一个树再生成路由表,逻辑是树的逻辑

        示例:

        • 彼此交换连接状态
        • LSP不是定时进行交换的,而是初始的时候进行交换,稳定之后根据事件触发的时候才会更新数据
          • 更新后发送给所有路由器,需要将Database发送给所有路由器
          • 根据Database更新自己的树,然后再次生成路由表
        • 从所有可达的道路上找到代价最小的路径

        LSP的代表OSPF(Open Shortest Path First)

        • 最短路径优先协议
        • 本科阶段指标只考虑带宽
  2. 外部网关协议(Exterior Gateway Protocols):例如EGP、BGP,用于自治系统之间路由数据报

    • 通过BGP,让其他自治系统了解自己的自治系统中的网段(不同系统)

因特网控制报文协议ICMP

ICMP为了提高IP数据报交付成功的机会,允许主机或路由器报告差错情况和提供有关异常情况的报告,一般路由器在丢弃报文的时候,都会返回一个ICMP差错报文

  • ICMP报文作为IP层数据报的数据,加上数据报的首部,组成IP数据报发送出去
  • ICMP只是IP层的协议

ICMP报文格式:

数据字段如下:

  1. 一般会把原始的 IP 数据报文的数据报首部 + 8 字节(数据的,可能会包含端口信息)作为 ICMP 的数据部分
  2. ICMP 的前 8 个字节的是确定的(前 4 个字节是类型,校验位,后面四个字节是确定的)
  3. 然后添加一个首部作为 IP 数据报进行发送。

两种ICMP报文:

  • 查询报文:不是很多
  • 差错报告报文:比较多

目的站不可到达

  1. 网络不可到达(net unreachable)
  2. 主机不可到达(host unreachable)
  3. 协议不可到达(protocol unreachable)
  4. 端口不可到达(port unreachable)
  5. 源路由选择不能完成(source route failed)
  6. 目的网络不可知(unknown destination network)
  7. 目的主机不可知(unknown destination host)
  8. 不可知是完全不可以解析,不可达是可以解析但是不可以到达

下面几种情况不应该发送ICMP差错报文

  1. 对ICMP差错报文不再发送
  2. 对第一个分片的数据报片的所有后续数据报片
  3. 对具有多播地址的数据报
  4. 对具有特殊地址的数据报

PING(Packet InterNet Groper)

  1. PING 用来测试两个主机之间的连通性,一般是用来检查局域网的连通性:PING 不通,不仅仅是发送不过去,有可能是应答不回来
  2. PING 使用了ICMP 回送请求与回送回答报文
  3. PING 是应用层直接使用网络层 ICMP 的例子,它没有通过运输层的 TCP 或 UDP

不同设备


0%