借曦光

计网笔记_4

Mon, 13 Dec 2021 22:26:24 +0800

第4章网络层：数据平面

4.1 导论

数据平面：

网络服务模型；

转发和路由；

路由器的组成和工作原理；

通用转发。

网络层服务：

在发送主机和接收主机之间传送段；

在发送端将段封装到数据报中；

在接收端将段上交给传输层实体；

网络层协议存在于每一个主机和路由器；

路由器检查每一个经过它的IP数据报的头部（解封装看IP选路径再封装）。

SDN根据很多因素，端口、IP、标志位匹配做流表，比传统只看IP的方式更灵活。

传统方式数据平面在路由上实现，网络中一个个路由构成控制平面，是分布式的，数据平面和控制平面在同一层实现，所以需要重构路由逻辑很困难。

现在的方式SDN 软件定义网络，逻辑集中的控制平面，先根据一些因素算出流表，再按路由表对数据做动作，所以之后再要修改逻辑，升级功能只需要修改流表就可以了，所以是可编程的集中式的。

网络服务模型service model：

对于单个数据报提供的服务：可靠传送；延迟保证，如：少于40ms的延迟；

对于数据报流的服务：保序数据报传送；保证流的最小带宽；分组之间的延迟差jitter。

IP网络对上层提供的服务：best effort尽力而为。

4.3 路由器router组成

传统路由结构（简化）：

路由：运行路由选择算法/协议（RIP, OSFP, BGP）生成路由表；

转发：从输入到输出链路交换数据报，根据路由表进行分组转发。

输入端口的功能：

分布式交换：

根据数据报头部的信息如：目标地址，在输入端口内存中的转发表中查找合适的输出端口（匹配+行动）；

基于目标的转发：仅仅依赖于IP数据报的目标IP地址（传统方法）；

通用转发：基于头部字段的任意集合进行转发。

输入端口缓存：

当交换机的输出顺序小于输入顺序时，可能需要排队，所以要缓存一部分降低排序延迟，并在一定程度上预防溢出造成的数据丢失。

Head-of-the-Line HOL blockings，排在队头的数据报组织了队列中的其他数据报向前移动。

交换结构：

通过内存交换：第一代路由器：

在传统的计算机上，在CPU直接控制下完成的交换，用软件的方式，通过memory实现，需要过两次系统总线BUS，被内存的带宽限制，而且一次只能转发一个组。

通过总线交换（不是系统总线）：第二代路由器：

数据报经过共享总线，从输入端口转发到输出端口，省去了走系统总线的过程，且只走一次共享总线，但共享总线也限制了交换速度，而且一次也只处理一个分组。

通过互联网络crossbar等交换：第三代路由器：

同时处理多个分组，克服总线带宽限制。有多种实现方式，比如榕树Banyan，纵横crossbar，等。高级设计可以将网络数据报分片为固定长度的信元，通过交换网络交换。

调度机制：

先来先服务FIFO first in first out：按照分组到来的顺序优先发送。

按优先级服务：优先发送优先级高的。

其他调度策略：weight fair queuing WFQ，加权优先级。

4.3 IP internet protocol

IP数据报格式：

第一层32 bits：

协议版本号Ver 4 bits，head 4 bits，type of service 8 bits，length数据包总长16 bits

第二层32 bits：

分片/重组使用：16 bits identifier，4 bits flags，12 bits fragment offset偏移量

第三层32 bits：

Time to live：8 bits，upper layer上一层协议将载荷交付 8 bits，Internet校验和 16 bits

第四层32 bits：

Source IP address 源IP地址

第五层32 bits：

Destination IP address 目标IP地址

------上面是固定长度的，20个字节的IP head

第六层32 bits：

Options，时戳，由路由器记录，指定所经过路由器的列表。

第七块儿：

数据。

IP数据报传输TCP段时头部有：

20 bytes of TCP，20 bytes of IP = 40 bytes + app layer overhead

IP分片和重组：Fragmentation & Reassembly

网络链路有 MTU maximum transmission unit 最大传输单元

MTU – 链路层帧所携带的最大数据长度：不同的链路类型；不同的MTU

大的IP数据报在网络上被分片fragmented，一个大IP数据报被分成若干个小的数据报，每个数据报在头上有一样的IP，按需来的offset偏移量，最后一个分片的flag标记为0，这些头部包含的信息被用于标识，排序相关分片，遇到flag为0的分片就知道数据报传完了。

重组只在最终的目标主机进行，减小路由器压力是一方面，不同分片走的不同路由是另一方面。

IP地址：32位（4字节）标识，对主机或者路由器的接口编址，标记的是点而不是机器。

AP接入点（无线局域网中）access point

IP子网subnets：

子网具备两个条件：

IP前几位是一样的（从路由上断开后，形成的孤岛式结构，路由器也有IP，也算）；

子网内部数据的分发不需要借助路由器，一跳可达，可以借助交换机。

网络主机

A类网（第1个字节网络号） 2^7-2=126 2^24-2=

B类网（第1，2个字节网络号） 2^14-2= 2^16-2=65534

C类网（第1，2，3个字节网络号）两百多万 2^8-2=254

D类网 multicast多播（组播）网

E类网预留

网络中传播信息是以一个个局域网（子网）为单位传的，按IP地址的话路由表根本没法算，代价太大，数据先发到子网，再由子网路由到目标IP。

特殊IP：

子网部分全0：本网络；

主机部分全0：本主机；

主机部分全1：广播地址，这个网络的所有主机。

127.x.x.x地址：回流地址，或测试地址，到网络层返回。

内网地址：在互联网中没有意义，只在局域网中分配，用作标识主机。

IP编址：CIDR Classless Inter Domain Routing 无类域间路由：

子网部分可以在任意位置划分，剩下为主机号。

不固定前几个字节是网络号了。

所以需要子网掩码，将作子网部分的网络号编码与1做与运算，主机部分编码与0做与运算，如此得到的结果就是子网的IP网络号，这个由两段1和0组成的编码就是子网掩码。

转发表和转发算法：

获得IP数据报的目标地址；

对于转发表中的每一个表项：如果目标IP地址和子网掩码与运算之后能得到有意义的目标地址，则按表项对应的接口转发该数据报；如果没找到，则按默认表项转发数据报（所谓默认表项就是该网络的一个出口，把数据报送出去）。

如何获得IP地址：

网络管理员手动配置；或者通过DHCP Dynamic Host Configuration Protocol动态主机分配协议从服务器自动获得一个IP地址。

DHCP：自动分配，每次重启更新，也支持使用之前用过的IP地址。

工作概况：

主机广播DHCP discover报文；

DHCP服务器用DHCP offer提供报文响应；

主机请求IP地址：发送DHCP request报文；

DHCP服务器发送地址：DHCP ack报文。

如何获得一块地址：

ICANN：internet corporation for assigned names and numbers国际机构：

分配地址；管理DNS；分配域名，解决冲突。

层次编址：

路由聚集route aggregation：子网前缀一样的那些子网，都发给同一个路由，这个路由再下一条往外发的时候，就可以把子网前缀合一块儿，即路由聚集一次，只区分子网前缀之外的部分，外面送进来的时候，只要子网前缀是这个的数据，都先发到这个路由就行。

特殊路由信息more specific routes：整体迁移。

NAT network address translation网络地址转换：

内网地址和外网地址转换，要记住源端口和源IP（内网），回来的时候可以进行分发。

NAT穿越问题：外网要跟内网通信，不知道具体目标主机地址：

方案1：静态配置NAT，内网分配固定，转发进来的对服务器特定端口连接请求；

方案2：UPnP Universal Plug and Play协议，和IGD Internet Gateway Device协议，允许NATted主机可以获知网络的公共IP地址，列举存在的端口映射，增/删端口映射；

方案3：增加中继，外网信息到中继，中继转发给目的主机。

IPv6结构：一层一样32 bits

Ver版本， priority优先级， flow label流标签。

Payload length（ttl），next header，hop limit

Source address

Destination address

Data

Internet control message protocol 网络控制报文协议 ICMP也更新了ICMPv6

IPv4到IPv6的过渡：

平滑升级：局部v6，外面是v4，接口使用双栈协议（一边v6，一边v4），升级多了局部大了之后，就是局部v4了，还是双栈协议，转个身就完事了。

4.4 通用转发和SDN

整个网络层的功能由数据层面和控制层面合作实现。

数据平面完成数据的转发。

控制平面控制数据怎么走。

传统的IP网络结构，路由实现数据层面和控制层面的功能，且控制方式是分布式的，控制逻辑固化，改变工作方式很困难。

SDN：分发流表，交给路由分发就可以了，路由也可以上报自身状态给SDN控制器，之后路由功能统一，都是分组交换机就可以了。而且不同厂商的服务器都支持SDN协议，各级都可以统一标准，创造健康生态。

OpenFlow数据平面抽象

流flow：由头部字段定义；

通用转发：简单的分组处理规则：

模式pattern：将分组头部字段和流表进行匹配；

行动action：对于匹配好的分组，可以是丢弃、转发、修改、泛洪等操作将匹配的分组发送给控制器；

优先权priority：几个模式匹配了，优先采用哪个，消除歧义；

计数器counters：bytes以及packets。

match + action统一化各种网络设备的功能，逻辑集中式，因此，路由器，防火墙，交换机，NAT都可以合到一种设备去实现这些功能。

计网笔记_5

Mon, 13 Dec 2021 22:26:57 +0800

第5章网络层：控制平面

5.1 导论

传统方式：根据路由信息怎么算路由表；

SDN方式。

5.2 路由选择算法

Link state链路状态算法 & distance vector距离矢量算法

路由协议的目标：如何在网状网中，找到一条比较好的路径，跳数尽量少，所以以子网为单位减少路由表的计算和路由转播的压力很重要。

路由route的概念：

路由route：按照某种指标（传输延迟、经过的站点数目等）找到一条从源节点到目标节点的较好路径。

因为以子网为单位传输数据，而源主机所在的子网只需要交换机就可以分发到第一个路由，最后一个子网中也只需要交换机就可以从最后一个路由到目标主机，所以在节约路由表计算的同时，还把主机到主机的数据交换简化为了寻找网络中路由到路由的最佳路径问题。

路由器-路由器之间的最优路径 = 主机对之间的最优路径

大大减少了路由计算的规模。

路由选择算法routing algorithm：网络层软件的一部分，完成路由功能。

最优化原则optimality principle：

汇集树sink tree：

此节点到所有其他节点的最优路径形成的树，由于取最优，所以只能是树；

路由选择算法就是为所有路由器找到并使用汇集树。

路由的原则：

路由选择算法的原则：

正确性correctness；简单性simplicity；健壮性/鲁棒性robustness；

稳定性stability；公平性fairness；最优性optimality。

路由算法分类：全局或局部路由信息：

全局：link state算法

所有的路由器拥有完整的拓扑和边的代价的信息；

分布式：distance vector算法

路由器只知道与它有物理连接关系的邻居路由器，和到对应邻居路由器的代价值；

迭代地与邻居交换路由信息、计算路由信息。

现在基本都是动态的。

配置LS路由选择算法的工作过程：

各点通过各种渠道获得整个网络的拓扑（上帝视角），网络中所有链路代价等信息（这部分和算法没关系，属于协议和实现）；

使用LS路由算法，计算本站点到其他站点的最优路径（汇集树），得到路由表；

按照此路由表转发分组（datagram方式）。

链路状态路由选择link state routing：

LS路由的基本工作过程：

1. 发现相邻节点，获知对方网络地址；

2. 测量到相邻节点的代价（延迟，开销）；

3. 组装一个LS分组，描述它到相邻节点的代价情况；

4. 将分组通过扩散的方法，泛洪发到所有其他路由器（得带上类似ttl的字段，或者版本号，预防在网络中产生广播风暴）；

（以上四步让每个路由器获得拓扑和边代价，上帝视角）

5. 通过Dijkstra算法找出最短路径（这才是路由算法，传统Dijkstra复杂度为n^2，较好的实现方式的话，可以降低到nlogn）：

每个节点独立算出来到其他节点（路由器=网络）的最短路径（汇集树）；

迭代算法：第K步能够知道本节点到K个其他节点的最短路径。

链路状态路由选择的工作流程：

初始化：

除源节点外，所有节点都为临时节点；

节点代价除了与源节点代价相邻的节点外，都记为无穷；

从所有临时节点中找到一个节点代价最小的临时节点，将之标记为永久节点（当前节点）W；

对此节点的所有在临时节点集合中的邻节点（V）：

如果D(V) > D(W) + C(W, V)，则重新标注此点，(D(W) + C(W, V), W)；

否则，不重新标注。

开始一个新的循环。

距离矢量路由选择distance vector rating

动态路由选择算法之一。DV和LS。

距离矢量路由选择算法的主要思想：

各路由器维护一张路由表；

各路由器与相邻路由器交换路由表；

根据获得的路由信息，更新路由表。

Distance vector中，每个节点的邻节点都告诉该节点彼此之间的代价（通过交换距离矢量），形成一张表，在网络中迭代，取得最小值，和相应的下一跳，这样获得最短路径。

距离矢量算法是一种动态规划问题（过一阵子算法笔记里会写），Bellman-Ford方程：

（这是一个分布式的迭代算法）

d_x(y) = min{c(x, v) + d_v(y)}, d_x(y)表示从x到y的最小路径代价。

特性：好消息传得快，坏消息传得慢。

好消息：链路代价变小，无需重新迭代新的最短路径，直接按原路接着传，速度变快；

坏消息：链路前面的代价变大，或者链路断掉，这样后面的节点仍然认为自己可达目标节点，向源节点申请，但是节点收到分组之后，其实还是传回那个代价增大甚至断掉的节点，就会形成环路，需要再次迭代，耗费时间。

LS和DV算法的比较：

消息复杂度：DV小，只和邻居节点交换分组消息，而LS算法中，若有n个节点E条链路，每个节点要发送nE个分组，在全网范围内泛洪，每个路由都尽量给所有路由都发一个分组；

收敛时间：LS快，复杂度为n^2，可以降到nlogn，而DV因为需要迭代计算，收敛速度很慢，而且有可能存在路由环路（坏消息传得慢），也有可能有count-to-infinity问题。

健壮性/鲁棒性：LS更好，每个节点都只计算自己的路由表，错误信息影响小；而DV中，一个节点的错误信息会被所有邻居获取利用，若路由表被其他节点使用，节点出错的影响可能会扩散到全网。

所以不能全网直接使用LS或DV，运算量太大，管理起来也很困难，需要把整个网络分成两个层面，在把网络划分为一个个小区域/自治区域之后，就只需要解决自治区域之内和自治区域之间的路由选择。分块解决，就可以满足功能和规模的需要。

5.3 自治系统内部的路由选择

自治区域内的路由选择协议：RIP、OSPF

RIP（routing information protocol）路由信息协议：

DV算法中，限制最大跳数，规定每过30s和邻居交换一次DV，通告advertisements，每个通告包括最多25个目标子网，在对方的请求下也可以发通告。

如果180s没收到通告，则认为邻居宕机或者链路断路，发送新的通告给邻居，更换路径，然后消息逐渐传遍整个网络，最大跳数为。

RIP在网络层，采用应用层的进程的方式实现，route-d(daemon)，使用传输层的UDP协议进行报文发送，周期性重复。

OSPF（Open Shortest Path First）开放式最短路径优先：

高级特性（RIP没有的）：

安全：所有OSPF报文都是经过认证的，防止恶意攻击；

允许多个代价相同的路径存在，RIP中只允许一个；

对于每一个链路，对不同的TOS有多重代价矩阵，按照不同的代价指标（如时间、延迟、跳数和拥塞程度等）分别计算最优路径；

对单播和多播的集成支持：Multicast OSPF (MOSPF) 使用OSPF相同的拓扑数据库；

大型网络支持层次性OSPF，网络很大的话进行分层，大体分为本地和骨干backbone，链路状态通告只在区域内泛洪，限制泛洪范围和数量，区域外的话需要先到backbone，所以需要区分边界路由器和骨干路由器。

5.4 ISP之间的路由选择：BGP

自治区域之间的协议：BGP Border Gateway Protocol边界网关协议。

太多个区域之间如何管理依然是个问题。

BGP是一个“事实上的”标准，大家在长时间的摸索之后达成的一个普遍遵守的规定，最后成了BGP协议，并非某一个组织事先拟定好的。

BGP分两个部分：eBGP external-BGP和iBGP internal-BGP：

eBGP：（AS间）从相邻的ASes获得子网可达信息，通告；

iBGP：（AS内）将获得的子网可达信息传输到AS内部的所有路由器。

BGP会话：两个BGP路由器peers之间建立半永久的TCP连接，之后交换BGP报文。

5.5 SDN控制平面

SDN还是一个在进展中的技术。

网络设备通过南向接口上报状态，SDN控制器的操作系统计算流表再下发，也可以通过南向接口完成修改流表等操作，SDN控制器也可以通过南向接口对网络路由下达指令。

南向接口协议：OpenFlow

网络控制器（0S）：OpenDaylight ODL，ONOS，等。

SDN控制器还可以通过北向接口与其操作系统上的应用做交互。

北向接口目前还没有很统一的协议。

SDN面临的挑战：

强化控制平面：可信、可靠、性能可扩展性、安全的分布式系统

（对于失效的鲁棒性：利用为控制平面可靠分布式系统的强大理论；可信任、安全：从开始就进行铸造）

网络、协议满足特殊任务的需求：实时性、超高可靠性、超高安全性等；

互联网网络范围内的扩展性：不只是在一个AS的内部部署，要可以在全网部署。

Python学习笔记_0

Mon, 13 Dec 2021 22:29:19 +0800

Python学习笔记开更

教材：Python基础教程（第三版）

挪威海特兰德的原著，袁国忠老师翻译的，书的排版很好，但是翻译有些问题，有条件有能力可以买原版来看。

但是从内容来说，这本书无论是正文自身知识框架和表达方式，还是正文内容与伪代码之间的配合讲解，还是书里夹杂着的一些tips，都能让我这个半吊子C很快地理解。

平台：PyCharm

TO DO：给书里的每一节都走一遍。

Python学习笔记_1

Mon, 13 Dec 2021 22:35:22 +0800

第一章快速上手：基础知识

1.1 交互式解释器

Python与常见的C/C#/C++/Java等编程语言不同，Python是一种解释性的语言，（可以这么理解）Python代码的编译运行需要先通过解释器转换成C之类的高级语言，再转换成汇编，机器语言。

Python的交互式解释器有很多种，分别由不同的语言开发实现，如果是C语言实现的解释器，便把Python转换成C，其他同理，所以Python的编程能够更接近自然语言，省去了其他语言很多规则上的限制，Python也有种类丰富功能强大的包供开发者调用，让学习者可以更方便地学习它，但这也让Python程序的运行速度慢上了一截，所以Python主要用来开发上层应用，底层的逻辑实现还是要依靠传统的高级语言。

1.2 算法是什么

算法由对象和语句组成，主要描述了如何完成任务。

这地方显然是很笼统的介绍，在算法导论的相关笔记中有更详细的记录。

1.3 数和表达式

Python中，直接使用操作符/对整形数据进行计算，会转换成浮点数据。

操作符//则表示向下圆整，即丢掉余数，也即丢掉小数部分，只保留商：

1 // 2 = 0

10 // -3 = -4

操作符%则表示求模（取余），舍弃商：

5 % 2.4 = 0.2

操作符**表示求幂，不再需要power了XD：

(-3)**2 = 9

另外，十六进制数用0x标记，八进制数据用0o表示，二进制则是0b。

1.4 变量

变量是表示（或指向）特定值的名称，以赋值操作为例：

x = 3 表示将值3赋给了变量x，在代码接下来的内容里，x就表示值3。

和其他的语言不同，Python使用变量之前必须给它赋值，因为Python的变量没有默认值。

同时，变量名只能由数字，字母和下划线组成，且不能用数字打头。

1.5 语句

没有十分明确的定义，可以把语句理解为一系列告诉计算机如何动作的命令。

1.6 获取用户输入

举例：input()函数：

运行结果：

Tip：input()函数接收到的数据是字符类型，如果打算处理数值的话需要先通过类型转换。

1.7 函数

其实刚刚input()就是一个函数。

像之前提到的求幂运算（**）也可以通过函数pow(·····, ·)来实现。

这样的函数有很多，比如abs()函数可以用来计算绝对值，而round()函数可以把计算圆整到与结果更接近的整数（正好为5的话圆整到偶数）。

1.8 模块

也就是之前说过的包，python的扩展性基本都通过调用包来实现。

如果想要在函数中调用某个包，需要在代码中import它（跟C语言include头文件一样功能的语句），比如包含了很多数学计算函数的math包，想用现成的计算函数的话，比如将给定数据向下圆整的floor()函数，或者求开方的sqrt()函数，就需要先import math，之后才能在代码中直接使用这些函数。

1.9 保存并执行程序

在Python程序中，可以使用#对这一行的代码进行注释，从井号开始到行尾的所有内容都将被编译器忽略，编译器是看不到这一行内容的。

由于教材之前的内容都是在交互式解释器中进行的，所以有这一节，但笔记在前面已经就已经用PyCharm操作过了，所以跳过这一节。

Tip：这一节后面有一些关于使用命令行操作.py文件的内容，作为一些基础知识，对有使用Linux系统需要的人来说还是很有帮助的。

1.10 字符串

String类型的数据，前面提及input()函数的时候有谈到，即文本信息。

可以通过双引号（”...”）或者单引号（’...’）表示字符串类型的值。

如果字符串本身含有引号部分怎么办呢？

首先可以单引号和双引号换着用，实在不行可以通过反斜杠\对引号进行转义，比如\’之后，编译器就不会把这个’当成某一组单引号的一部分，而把它看成文本信息。除此之外，既然说了文本也不过是字符串类型的值，那么如果嫌弃转义操作符很麻烦，可以使用+操作符来把两个字符串拼起来。

输出：

另外，和C一样，通过\n可以对字符串进行换行操作。

而如果字符串本身包含反斜杠\，那么可以通过反斜杠转义反斜杠，要是想表示路径一样包含很多反斜杠的文本信息，可以通过原始字符串函数r来让编译器不对r后面的反斜杠起反应，比如：

输出：

要注意的是，原始字符串函数不能以反斜杠结尾，主要是防止编译器不知道字符串结没结束，真有这种使用需求的话，可以把结尾的反斜杠单独做一个字符串并进行转义。

计网笔记_6

Fri, 17 Dec 2021 18:31:39 +0800

第6章链路层和局域网LAN

6.1 引论和服务

链路层的功能基本通过网卡/网络适配器NIC (Network Interface Controller)实现。

存在一些寻址问题和网络控制问题。

链路层导论：包括优先链路、无线链路，也可以分为点对点的链路和多点链路。

主要功能：把分组封装成这个网卡所对应的帧，再通过链路传输给目标节点。

链路层服务：

成帧，链路接入：

将数据封装在帧中，加上帧头帧尾；

如果采用的是共享介质，信道接入获得信道访问权；

在帧头使用MAC media access control 即网卡物理地址来标识源和目的。

在相邻两个节点完成可靠数据传递：

在低出错率的链路上很少使用（光纤、同轴电缆等介质）；

在无线链路上经常使用（出错率高）。

流量控制：使相邻的发送和接收方的速度相匹配；

检错、纠错；

半双工、全双工通信。

适配器通信：

发送方：在帧中封装数据报；加上差错控制编码，实现RDT和流量控制功能等。

接收方：检错，执行RDT和流量控制功能等；解封装数据报，将之交给上层。

RDT: Reliable Data Transfer 可靠数据传输协议。

网卡NIC是半自治的，实现了链路层和部分物理层功能

6.2 差错检测和纠错

EDC：差错检测和纠正位

D：数据由差错检测保护，可以包含头部字段。

差错检测不是100%可靠，协议会漏检，EDC和D也会出错，但是比较少。越长的EDC检错效果会越好。

奇偶校验：

单bit奇偶校验：检测单个bit级错误；

双bit奇偶校验：可以检错也可以纠错，如果是对偶错误，则检测不出来。

CRC：Cyclic Redundancy Check 循环冗余校验：

模2运算：加不进位，减不借位，等价于异或运算（按位，不同为1，相同为0）；

位（比特）串的两种表示：比如：1011 或1*x^3+0*x^2+1*x^1+1*x^0=x^3+x+1；

生成多项式，r次方的比特序列：如G=x^3+1，r次方多项式共r+1位，表示1001；

约定：D | EDC：D位后附上r位冗余位，使数据可以被生成多项式整除，若接收方不能被生成多项式整除，则说明传输过程出错。

R的计算方法：D | R 可以被生成多项式整除：

D * 2^r ⊕ R = n * G （⊕表示模2运算）

等价于：D * 2^r ⊕ R ⊕ R = n * G ⊕ R

等价于：D * 2^r = n * G ⊕ R

两边同除生成多项式G：

R = remainder[D * 2^r / G] （remainder[ ]：表示取余数）

CRC性能：

能检测所有1bit和2bits的错误；

能检查所有长度=r或者<r的错误；

出现长度为r+1的突发错误，检查不出的概率使1/2^(r-1)；

出现长度大于r+1的突发错误，检查不出的概率是1/2^r。

6.3 多点访问协议

多点网络：传统以太网同轴电缆，无线局域网，等。

多点同时发送报文会冲突，比如电磁波信号会相互干扰。

多路访问协议：MAC multiple access control protocol

理想的多路访问协议：

在速率为Rbps的广播信道中，当一个节点要发送时，可以R速率发送，但当有M个节点需要发送时，我们希望每个节点都可以R/M的速率发送，即公平性。而且对于一个理想的协议，它应该不需要特殊节点来辅助协调发送，也不需要时钟和时隙来做同步，当然作为一个好协议最重要的一点，是要尽量简单。

MAC multiple access control 媒体访问控制协议，分类：（三大类）

信道划分：把信道划分成小片（时间、频率、编码等）；

随机访问：信道不划分，允许传输时发生冲突，冲突发生后恢复；

依次轮流：节点依次轮流，但是数据较多的节点可以获得较多的信道使用权。

1. 信道划分：TDMA分时、FDMA分频、CDMA分码，编码方式不一样来划分

2. 随机访问：允许冲突，问题是如何检测冲突，冲突后如何恢复

常见协议：时隙ALOHA、ALOHA、CSMA、CSMA/CD、CSMA/CA

时隙ALOHA：

检测冲突：根据频率和幅度判断冲突的发生；

恢复发送：以时钟同步，都以概率p发送，完全分布，时间越长，冲突概率越小。

效率efficient：最好的频率37%

ALOHA：

不按时隙的时隙ALOHA，按帧时传，帧时小于数据传输时间，效果更差，p=17.5%

CSMA Carrier Sense Multiple Access：载波侦听多路访问：

发之前先听一下信道有没有人在发，有人在发就不发了，在ALOHA基础上减少冲突的可能性，冲突仍然可能发生：听的时候一方已经发了但是因为传播延迟没检测到（局部探知全局），信道延时越大，节点之间距离越远，发生冲突的概率就越大。

CSMA/CD： Carrier Sense Multiple Access with Collision Detection（冲突检测）

侦听到冲突之后发出表示冲突的信号，足够长足够大，让其他节点都知道此时信道冲突。冲突记次数，连续冲突K次之后，节点在长度为2^K的空间中选一个位时传输数据，这就是二进制指数退避，这样连续冲突次数越多，发生冲突的概率就越小，但是导致平均等待时间增加。

比ALOHA更好，简单，廉价，分布式。

CSMA/CA Carrier Sense Multiple Access with Collision Avoid（冲突避免）

无线局域网中，电磁波传输，无法检测冲突，自己的发送信号比接收别人的发送信号强多了，所以不能用CD，而且无线网络中冲突不一定意味着传输失败（覆盖范围大了，能量和频率问题），没冲突也不意味着成功（可能检测不到冲突，冲突信号被挡住了），只能期望CA。

CA的实现：先听信道，信道忙的时候就直接在时序空间里随机选时间，每过一周期-1，为0的时候直接发送，因为CD不了。但是仍然有冲突可能，完全避免冲突，可以先发送预约报文，很小占用信道资源少，冲突了也没事，预约保温发送出去之后可以被信道上的所有节点听到，之后预约过的节点全速发送，其他节点一直发送。

线缆接入网络：

下行：端上只有一个用户CMTS，单向传输，节点上每个节点都检测报文，比较地址，是自己的就拿走，不是自己的就放掉。

上行：所有节点向CMTS预约，预约之后CMTS将预约结果下发给所有节点，然后按预约结果使用信道，如果预约报文本身冲突预约失败，则二进制指数退避。

3. 依次轮流协议taking turns

信道划分MAC在高负载的时候有效且公平，低负载时效率低下，只能用1/N信道。

随机访问MAC低负载时效率高，冲突概率低，单个传输用全部信道，高负载时冲突开销大，二进制指数退避增加平均等待时间。

依次轮流协议taking turns有有两者的优点：

有两种：轮询、令牌token传递

轮询：主节点要求其他所有节点依次轮流，问题是万一主节点挂了，系统就不工作了，存在单点故障问题single point of failure (SPOF)，可靠性较差。

令牌token传递：令牌在节点中轮转（有专门的令牌总线），令牌是特殊帧，有数据需要传输时，拿下令牌放到自己数据帧里（令牌在前数据在后），开始传输，接收端接收到之后，把令牌拿下来再丢到网络中去轮转，有令牌的才能发，没令牌不准发。

Token方法高低负载利用率都很高，但都高不过前面两种“极端情况”信道划分和随机访问。此外，这种也存在风险，token可能会丢，但有办法弥补。

6.4 LANs

MAC地址由IEEE分发，固定不变。

IP地址和MAC地址分开，正常情况下对应不变，换IP网卡不用动，换网卡IP也不用动。

以太网：目前最主流的LAN技术

传统以太网使用的是通过同轴电缆连接的总线型网络。

但是同轴电缆过长的话，一旦电缆有一处受损，整个网络都会瘫痪。

HUB集线器：物理上好像是星形网络，其实逻辑上还是总线型，HUB上的所有设备处在同一个碰撞域内，但是高负载情况下，由于其使用的时CSMA/CD的方式，导致信道利用率很低，所以需要升级。（HUB中每条线路都要匹配，带宽要一致）

SWITCH交换机：HUB的升级版，相当于暂时缓存一个节点发出的数据，再将其发给目标节点，所以可以看作是点对点的连接，是一种点点共享的星型网络，效率提高很多。交换机即插即用，自学习性，无需配置，自动学哪些MAC地址可以通过哪些端口到达，主机无需关心交换机的存在（透明）。

以太帧结构：发送方适配器在以太网帧中封装IP数据报，或其他网络层协议的数据单元。

Preamble + 目的地址 + 源地址 + type + 数据data (payload) + CRC

Preamble前导码：7B 10101010 + 1B 10101011，用来同步接收方和发送方的时钟速率，类似节拍，全1的时候也收。

（CRC在最后，一边发数据一边生成，提高效率）

以太网提供的是无连接、不可靠的服务：

无连接：传输前不握手。

不可靠：接收方适配器不返回ACK或NAK之类的报文。

以太网的MAC协议采用二进制退避的CSMA/CD介质访问控制形式。

低负载时因为CSMA/CD的特性，效率很高，高负载时因为引入了交换机switch，效率也很高。

以太网的标准：标准不一样，帧结构一样但物理层介质不一样。

交换机和路由器对比：

都是存储转发设备，但层次不同：

交换机：链路层设备，检查链路层头部；

路由器：网络层设备，检查网络层头部。

都有转发表：

交换机：维护交换表，按照MAC地址转发（执行过滤、自学习和生成树算法；即插即用，二层设备，速率高；执行生成树算法，限制广播帧的转发）

路由器：维护路由表，执行路由算法（路由算法能避免环路，无需再生成树也可以限制广播分组，还可以按各种拓扑构建网络；不能即插即用，需要先配置子网前缀；三层设备，效率低）

6.5 链路虚拟化MPLS

路由设备太多，会导致数据在链路中传输时需要检索的路由很多，必然带来延迟，所以在原有的分组前再加上一个特有的标签进行传输，除了最后一个路由是弹出pop标签之外，每一个路由都给到来的分组加上一个新的标签，只是其实路由是在分组前面加标签，中间的路由则是交换标签swap，即用一个新的标签替换此前旧的标签。

随着设备发展的进步，检索路由已经不再是一种困难，所以MPLS在传统链路中用得就比较少了，目前MPLS主要是用在VPN相关技术中。

计算机网络 - 总结

Fri, 17 Dec 2021 18:38:10 +0800

到这儿基本郑老师课上的内容就都结束了，后面一些网络安全技术的延申个人觉得对计算机网络而言不甚重要，所以没有学习笔记，另外第八版中有关MPLS、wireless网络的一些内容，比如VPN、CSMA/CA等技术和协议，虽然对本科生不作要求，但是研究生是需要学习的，但像CSMA/CA协议，郑老师在前面的内容中已经讲过，还有数据中心、QoS等等，都在之前的课程中有所涉及，可见郑老师课堂内容之丰富，所以虽然第八版单独成章，所以没有专门写笔记，时间确实来不太及，这第六章的内容，还是考完试回来补的XD。

这学期的计网考试，从客观的角度上来说确实不是很难，没有考察超过PPT和平时讲座的任何内容，基本每一题都有些印象，但是做选择题还是有一些题目不太确定，想要去翻找相关的知识点，却又难以精准定位，浪费了很多时间（我还把老师总计超过一千张的PPT浓缩到了300+，都来不及找，浓缩的过程中甚至浓缩掉了一个考点，数公里到数十公里覆盖范围的网络，应该是MAN，我有印象但是在记不清楚，选的WAN，WAN的范围是几百到几千公里，悲）。

翻资料耗时太多，导致最后有一道简答题写得很简答，题目要求总结一下RDT并讲一下用途，我只来得及简单地说了一下RDT期望保障可靠性，发端请求和收端返回ACK的过程，画了张C/S的草图想节省时间，也只来得及标注了收端返回n+1作期望代替NCK的做法，用途只来得及写了两种pipeline的形式，GBN和SR，没足够时间做出补充，看上去实在太过简略。就作答情况而言，老师如果高抬贵手，应该是可以过的，能过就好了，复习、课设还有实验室忙得头掉，只能说我也是尽力而为best-effort了。

整理了缩写和全称的表格，其中有一条复制的PPT上的，没细看，PPT上是错的，复制了也是错的，考的时候有所怀疑，但是依然坚定了整理的知识点，结果发现当时的自己是对的，是整理的知识点错了，悲^2。错的是CDN，应该是Content Delivery Network，当时资料上是Content Provider Network，就离谱。

刚考完计网又要复习算法了，但是就这一门了吧，还有算法的课设，前一届集体摆烂大家都没做，最后不了了之，今年有几个人带头一卷，大家一块儿难受，害。

缩写-全称表格如下，为考场快速查找，按A-Z的顺序排序，现在应该没什么错的了，属实难顶。

AF - assured forwarding

AIMD - Additive Increase Multiplicative Decrease

AON - Active Optical Network

AP - access point

API - Application Programming Interface

ARIS - Aggregate Route-Based IP Switching

ARP - Address Resolution Protocol

ARPANET - Advanced Research Projects Agency Network

ARQ - Automatic Repeat-reQuest

AS - Autonomous System

ASN - Autonomous System Number

ATM - Asynchronous Transfer Mode异步传输模式

AToM - Any Transport over MPLS

BDR - Backup Designated Router

BE - best-effort

BER - bit error rates

BF - Bellman-Ford equation

BGP - Border Gateway Protocol

BSS - Basic Service Set

C - Customer devices

CA - Control Agency

CC - Coaxial cable

CDMA - Code Division Multiple Access

CDN - Content Delivery Network

CE - Customer Edge devices

CI - congestion indication

CIDR - Classless InterDomain Routing

CLI - Command Line Interface

CLNP - ConnectionLess Network Protocol

CoS - Class of Service

CRC - Cyclic redundancy checks

CR-LDP - Constraint-based Routing LDP

CSMA - carrier sense multiple access

CSMA/CA - Carrier Sense Multiple Access with Collision Avoid

CSMA/CD - CSMA with collision detection

CSR - Cell Switching Router

CTS - Clear To Send

DASH - Dynamic, Adaptive Streaming over HTTP

DBD - Database Description

DCQCN - Congestion Point Notification Point Reaction Point

DCTCP - Data Center TCP

DHCP - Dynamic Host Configuration Protocol

DNM - Domain Name Management

DNS - Domain Name Server

DoS - Denial of service

DR - Default Routes

DR - Designated Router

DSCP - Differentiated Service Code Point

DSL - digital subscriber line

DSLAM - DSL Access Multiplexer

DSP - Digital Signal Processing

DV - Distance vector algorithm

eBGP - external BGP

ECN - Electronic Communication Network

ECN - Explicit Congestion Notification

EDC - Error Detection And Correction

EF - expedited forwarding

EGP - exterior gateway protocol

EIGRP - Enhanced Interior Gateway Routing Protocol

FCFS - FIRST COME FIRST SERVICE

FDM - Frequency Division Multiplexing

FEC - Forward Equivalence Class

FIFO - first in first out

FIN - FINAL

FLSM - Fixed length subnet mask subnetting

FOC - Fiber optic cable

FSM - finite state machines

FTP - File Transfer Protocol

FTTH - Fiber To The Home

GBN - Go-Back-N

GPRS - General packet radio service

GRE - Generic Routing Encapsulation

GTP - GPRS Tunneling Protocol

HFC - hybrid fiber coax

HOL - Head-of-the-Line

HQoS - Hierarchical Quality of Service

HTML - HyperText Markup Language

HTTP - Hyper Text Transfer Protocol

H-VPLS - Hierarchical VPLS

IAB - Internet Architecture Board

IAM - Internet Architectural Management

IANA - The Internet Assigned Numbers Authority

iBGP - internal BGP

ICANN - The Internet Corporation for Assigned Names and Numbers

ICMP - Internet Control Message Protocol

ID - Internet Draft

IDC - Information Distribution Company

IDP - Internet Datagram Protocol

IESG - Internet Engineering Steering Group

IETF - Internet Engineering Task Force

IGD - Internet Gateway Device

IGMP - Internet Group Management Protocol

IGP - interior gateway protocol

IMSI - International Mobile Subscriber Identity

IP - Internet Protocol

Ipsec - IP security

IRSG - Internet Research Steering Group

IRTF - Internet Research Task Force

ISP - Internet Service Provider

IXP - Internet Exchange Point

L2F - The Layer Two Forwarding (Protocol)

L2TPv3 - Layer Two Tunneling Protocol version 3

LAN - local area network

LDP - Label Distribution Protocol

LER - Label Edge Router

LS - link state algorithm

LSA - Link State Advertisements

LSAck - Link Status Acknowledgement

LSP - Label Switched path

LSR - Label Switch Router

LSR - Link Status Request

LSU - Link Status Update

LTE - Long-Term Evolution

MAC - Media Access Control

MIB - Management Information Base

MISO - Multiple-input and single-output

MPLS - Multiprotocol label switching

MSS - Maximum Segment Size

MSTP - Multi- Service Transport Platform

MTU - Maximum Transmission Unit

NAS - Network Access Servers

NAT - Network Address Translation

NCP - Network Control Protocol

NFV - network functions virtualization

NHLFE - Next Hop Label Forwarding Entry

NHLFT - Next Hop Label Forwarding Table

NI - no increase in rate

NIC - Network Interface Card

NSAP - network service access point

ODL - OpenDaylight

OFDMA - Orthogonal Frequency Division Multiple Access

OLT - Optical Line Terminator

ONT - Optical Network Terminator

OSPF - Open Shortest Path First

OTT - over the top

P - Service Provider devices

PDCP - Packet Data Convergence Protocol

PE - Service Provider Edge devices

PE-r - Provider Edge routers

PE-rs - Provider Edge devices that are capable of both routing and switching

PE-s - Provider Edge switches

PHB - Per-Hop Behavior (PHB)

PON - Passive Optical network

PoP - Points of Presence

ppm - pkts per min

PPP - Point to Point Protocol

PPTP - The Point-to-Point Tunneling Protocol

Q-in-Q - IEEE 802.1Q tunneling

QoS - Quality of Service

QUIC - Quick UDP Internet Connection

RARP - Reverse Address Resolution Protocol

RDMA - remote Division Multiple Access

RDT - Reliable data transfer protocol

RED - Random Early Detection

RFC - Request for Comments

RIP - routing information protocol

RLC - Radio Link Control

ROM - Read-Only Memory

RPC - Remote Procedure Call

RR - Round Robin

RST - RESET

RSVP - Resource Reservation Protocol

RSVP-TE - Resource ReSerVation Protocol-Traffic Engineering

RTP - Real-time Transport Protocol

RTS - Request To Send

RTS - revised technical specification

RTT - Round-Trip Time

SDH - Synchronous Digital Hierarchy

SDN - software-defined networking

SGMP - Simple Gateway Monitoring Protocol

SIM - Subscriber Identity Module

SIMO - Single-input and multiple-output

SLA - Service Level Agreement

SLAs - Service Level Agreements

SMI - Structure ofManagement Information

SMTP - Simple Mail Transfer Protocol

SNMP - Simple Network Management Protocol

SNR - signal-to-noise ratio

SONET - Synchronous Optical Network

SPF - Shortest Path First

SPOF - single point of failure

SR - Selective repeat

SSL - Secure Sockets Layer

SYN - Synchronize Sequence Numbers

TCAMs - ternary content addressable memories

TCP - Transmission Control Protocol

TDM - Time Division Multiplexing

TOR - Top of Rack

ToS - Terms of Service

TOS - Type of Service

TP - Twisted pair

TTL - Time To Live

UDP - User Datagram Protocol

UPnP - Universal Plug and Play

VLAN - Virtual Local Area Network

VLSM - Variable Length Subnet Mask

VoIP - Voice over Internet Protocol

VPLS - Virtual Private LAN Service

VPN - Virtual Private Networks

WAN - Wide Area Network

WDM - Wave Division Multiplexing

WFQ - weight fair queuing

WLAN - Wireless local area network

WRED - Weighted Random Early Detection

算法笔记

Thu, 23 Dec 2021 21:04:14 +0800

虽然对算法课程而言，老师用的教材是算法导论，就是Introduction to Algorithms，但是授课过程中更多依赖的是PPT，已经在老师的主页上获取了本学期的所有PPT了，尝试写了笔记，但是很多都是在重复PPT的内容，所以最后还是决定复习算法的时候就不写笔记了，在PPT上做好相关标注就足够了，而且每种算法都详细写一遍思路和原理的话比较耗费时间，等之后细读Introduction to Algorithms再做吧，可能会更有体系一些。

D2DL笔记_4

Sun, 27 Mar 2022 22:24:50 +0800

梯度：

在标量导数的基础上，将导数拓展到向量层面，称为梯度（gradient），梯度就是函数的这一点在梯度的方向上变化率最大，变化最快，所以机器学习/深度学习中，经常需要求梯度来优化模型。

（理解一下就好，不常用到）y是x的函数：

对于y对x向量的偏导而言，

求导就是为了得到指向y变化到最大值的方向。最后的结果形式与相反（转置），若是列向量，那么结果就是行向量。

而若是向量形式的，那么结果的形式与的形式相同，不用转置。

在机器学习/深度学习领域，一般是自动求导的，不需要人工计算。

计算图：类似链式法则，每一步取子式建立操作子，生成有向无环图。

自动梯度的实现（当然可以调现成的包）

计算y关于x的梯度：

首先需要一个地方存储梯度：

两种方法是等价的。

计算y：

这儿有一个grad_fn，gradient function表示这是一个y关于x的梯度值，因为pytorch是隐式构造的计算图。

通过调用反向传播函数backward()可以自动计算y关于x每个分量的梯度，因为反向传播其实是传统链式法则数学解法的逆，而x.grad中按照链式法则存储了每一个操作子的结果：

可以看到结果和4 * x（y关于x的导数）是一致的：

试一下对向量的sum求梯度，当然，向量求和的梯度都是1，因为向量求和相当于xE，y = xE中，y对x求导的结果就是E，但是操作之前需要用.grad.zero_()来对.grad内的数据清零（其实是写进0）：

在深度学习中，我们常常不去计算矩阵的导数，很少对向量的函数求导，而是要求对每个样本单独计算的导数之和（对标量求导），因为最终要求的都是loss，如果loss是一个向量，求一次梯度就变成一个二维矩阵，再延申一层就变成四维的，如果神经网络的层数很深，那最后就会变成一个很大的张量，自然会很麻烦，所以对于向量，一般一开始就先求一个sum，让向量变成一个标量，再进行求导：

可以通过把某一个函数detach掉，使它变成一个常量，就可以将它移动到记录的计算图之外，在训练模型中需要固定某个值的时候很管用：

显而易见，y是一个关于x的函数，而u只是一个值等于x * x的常量，所以在z对x求导的时候，只剩下了u。

那再对y求一次导看看：

意料之中的结果。

即使构建函数的计算图需要通过python控制流（条件、循环或任意函数调用），我们仍然可以计算得到变量的梯度：

线性回归的实现：

（需要安装d2l包：pip install d2l）

先做好把数据传到matplotlib的准备：

随机生成一个数据集，X从0到1取随机值，y在线性回归的基础上在加上一个从0到1之间取随机值的随机噪声，将X和y都以列向量的形式return，样本值w取[2, -3.4]，偏差b取4.2，最后把X和y分别赋值给特征features和标签labels：

可以看一下特征和标签里的第0个值：

既然用了matplotlib，也可以画一下图像：

其中，必须先detach才可以送到numpy。

然后定义一个data_iter函数（迭代器），该函数接受批量大小、特征矩阵和标签向量作输入，生成大小为batch的小批量。首先取特征矩阵的长度（特征的个数），再通过range生成一个随机标号的list，叫indices，之后对每一个i求一个batch_size（=10）：

数据集定义完了，接下来定义模型。

定义模型首先需要初始化参数，其中w是一个向量，b是一个标量，两个变量都需要做优化求导，所以都需要requires_grad=True：

定义模型：

定义损失函数（均方误差，y_hat是预测值，对应模型的输出，y是真实值，对应labels。但这里不完整，没求和）：

定义优化算法（小批量随机梯度下降，lr是learning rate学习率）：

在梯度下降最后需要把param.grad置零，保证每次下降互相独立。

定义训练函数：

（每一次epoch都对所有的数据做一遍计算，每一次计算中，l都是长为批量大小的向量）

可以看出每一次迭代，最后的损失都会越来越小，将真实参数与模型预测的参数做比较来评估训练的成功程度：

整个过程中，lr和num_epochs就是所谓的超参数，需要人工指定，可以尝试一下不同的学习率和epoch次数对最后的loss都有什么影响（每次重新跑之前都需要重新初始化w和b）。

线性回归的简洁实现（使用现成的模块）：

调用框架现有API来读取数据：

使用框架定义好的层（nn是神经网络neural network的缩写，nn中有大量定义好的层，可以直接使用，nn.Linear(*, *)需要指定输入和输出的维度，然后把它放到一个叫Sequential的容器当中，相当于list of layers）：

初始化模型参数（0读取到Linear，weight读取到w，data读取真实值，normal_用正态分布替换真实值）：

均方误差：

实例化SGD（Stochastic Gradient Descent：随机梯度下降）实例：

训练结果：

用牛顿法（求二阶导）可以比随机梯度下降的梯度下降更快，但是很多时候梯度下降快并不一定是个好事，就像学习率，而且算二阶导很贵，所以一般用跟学习率相配合的SGD。

D2DL笔记_5

Sun, 27 Mar 2022 22:37:54 +0800

数据集的使用

图像分类数据集：MNIST

但是过于简单，教材使用了类似但更复杂一些的Fashion-MNIST数据集

首先加载一些包：

（%matplotlib inline是在jupyter画图用的，如果不是jupyter如pycharm的话，是不需要这一行的）

先把transforms转成张量形式，否则所有数据返回的是PIL图片，再调用Fashion-MNIST数据集，分别看一下train和test的数据量（会有下载过程，很快，数据集就两百多兆的样子，root=”./data”的意思是在该python文件的上一级目录中新建一个data文件夹）：

训练集和测试集大小：

调用第一个图看看，[0][0]第一个0表示训练集中的第0个图，第二个0表示这张图的张量信息，是一个三维张量，分别表示图的RGB信息，而1的话就是图的标号（label）：

将数据集可视化：

Next取第一个批量的18个数据进行可视化：

读取一小批数据，大小为batch_size，用4个进程读取，查看消耗的时间：

一般在训练模型之前需要测试一下设备读取数据的速度，读取的速度至少要和训练的速度差不多，最好是读取速度比训练速度快很多，避免出现来不及读取的情况。

最后把之前搞的一些零零碎碎的小函数整合一下，此外还添加了一个resize功能，因为Fashion-MNIST数据集都是28 x 28大小的图片，而别的数据集则有各种尺寸的图像，为了提高函数的泛用性，最好可以resize，直接对transforms做resize就可以了：

Softmax回归的实现（虽然softmax叫回归，但实际上更像一个分类器，因为它是多输入多输出的，而回归问题通常只有一个输出）

由于Fashion-MNIST数据集的图像的形式都是三维的张量，而softmax的输入要求是向量，所以我们需要把图像拉长，长度为28 x 28 = 784，又因为数据集的图像有10个类别，所以网络的输出维度设为10（其实拉伸向量会使它损失掉很多空间信息，后面相似的问题会在卷积神经网络中进行处理），接着初始化权重w和偏移b，并做好计算梯度的准备，初始化的时候需要注意权重w的形状：

实现softmax：

由于X是矩阵，所以对每一行做Softmax，也就是对每一行求和，同时注意保持维度不变，这样就可以利用广播机制，对X_exp中的每一行除以对应的partition（借由广播机制，可以省去循环的设计）：

测试一下softmax函数：

可见softmax因为keepdim而没有改变X的形状（均值为0，方差为1），仍然是二行五列，而且每个元素都变成了正值且每一行的和为1（在行上做的softmax，每一项都是一个概率，所有项的和自然为100%，也就是1。机器学习/深度学习就是一直求各种概率的过程）。

定义一下softmax回归模型：

Reshape-1的意思是让torch自己确认需要多少行，然后取权重相同的列，做矩阵乘法，最后加上偏移b送到softmax里面：

接下来计算交叉熵损失：

首先需要解决的问题是，如何从预测值里面把和真实值y对应的y_hat拿出来：

通过假设简化问题，假设我们有两个真实数据，总共有三个不同的类别（0，1，2），y很当然得由两个真实值组成一个长为2的向量（第一个是第0类，第二个是第2类），而y_hat就会是一个两行三列的矩阵，两行表示对两个真实值的预测，三列分别存储该个体属于0 or 1 or 2类的概率。y_hat[[0, 1], y]的意思是，根据标号0去y里面把第0个样本的真实种类（第0类）在y_hat中对应的概率（0.1）拿出来，对标号1同理：

（其实也就是y_hat[[0, 1], [0, 2]]，取y_hat中第0行第0列和第1行第2列的数据）

实现交叉熵损失：

将预测值和真实值作比较：

首先要确认y_hat中有多类的概率预测，然后把其中每一行概率最大的下标（也就是种类）传给y_hat，最后将y_hat与y比较，判断类型是否相同，将true or false传给cmp形成一个布尔类型的变量，再将其转为float类型：

可以算一下准确率：

结果是0.5，因为这之前的预测是随机的。

可以用一样的方法算任意模型预测的准确率：

Accumulator()是一个累加器，在n个变量上累加：

可以看一下evaluate的结果：

因为总共分了十个类，而预测是随机的，所以准确率应该在10%（0.10）左右。

Softmax训练（这里直接贴教材上的代码，有注释）：

训练数据可视化（画图函数）：

以下是训练模型：

学习率设置为0.1，最后使用随机梯度下降：

训练10个epoch（还没有完全收敛）：

对图像分类进行预测：

其中交叉熵和softmax模型的实现可以直接调用nn.CrossEntropyLoss()实现，简洁不是一点半点。

感知机

感知机其实是人工智能领域最早的模型。

原始的感知机其实是一个二分类问题，一般是分成正类和负类两种。又因为在二维层面上，感知机只能生成线性分割面，所以它处理不了XOR（异或）问题，比如一个平面坐标系表示的样本空间被四个象限所划分，两个类四个样本分别分布在每个象限中，一三象限的样本实际上是一类，二四象限的样本实际上是一类，这种情况下，是无法直接通过一个线性分割面（也就是感知机）去划分的。

对于XOR问题，可以通过升维的方式升到高维的特征空间，再通过超平面去划分，到实际操作上来说就是经过多次二分类分割再做异或来综合的方式解决（多层感知机MLP）。

训练感知机（伪代码）：

initialize w = 0 and b = 0

repeat

if y_i * [<w, x_i> + b] <= 0 then

w <- w + y_i * x_i and b <- b + y_i

end if

until all classified correctly

等价于使用批量大小为1的梯度下降（因为感知机会一直repeat到所有样本都分类正确，不是随机的，所以不等价于随机梯度下降）

多层感知机

结构图：

输入肯定是训练数据集规定好的，输出也是根据实际需要规定好的，都是固定的，多层感知机可以做调整的就是隐藏层的层数和每个隐藏层的大小，这些是超参数，理论上讲需要手动调整。

多层感知机的实现：

批量大小设置成256，和前面一样。

变量初始化：

输入是28 x 28 = 784，输出是10，这两个值是固定的，一个有数据集输入的规模决定，一个由输出的实际需求决定。

隐藏层的大小是超参数，手动设置为256。

这里是只有一层隐藏层的情况。

W1的行是输入大小，列是隐藏层数，随机取是为了让模型能够学得动，如果置0的话，w1会不能更新，一直是0，因为是随机取值，所以*0.01稳住方差。

ReLU函数，也就是max(0, x)，一种很简单的激活函数，计算简洁，和sigmoid、tanh相比的话，不需要进行指数运算，节约运算开销，而且可以避免梯度爆炸或者梯度消失，此外其实对模型精度的提高的帮助并不太大，只是因为简单好用，所以挺多人用ReLU做激活函数：

模型的实现：

其中，@符号表示矩阵乘法，之前有用过mm函数，用@的话表达式会更简洁。

损失函数跟之前一样，使用CrossEntropy：

训练模型：

由于多层感知机其实也可以看作是一种多分类问题，softmax也可以看作多分类问题，所以在训练的时候，他俩的操作是一样的，可以直接调用d2l中之前对softmax训练的train_ch3函数来训练，这也是目前MLP的使用范围比SVM更广的一个原因，因为MLP可以很简单地把网络换成CNN、RNN、transformer等而不需要重新调太多参，此外，SVM学不了很大的数据，而且可以调节的超参数不多，所以深度学习里面涉及很少，这是主要原因。

这里跑10个epoch，learning rate选0.1：

可以看到多层感知机想比之前softmax的训练结果来说，损失loss虽然下降了，但是精度却没有明显的提升，这是因为多层感知机的模型比softmax的来说更大了，所以模型在拟合数据上的损失变小了，但是由于回归策略是一样的，所以精度上都差不多。所以无论是尝试增大批量大小还是减小学习率，只能将损失再次降低，却不会提高精度。

多层感知机也可以调用现成的API来实现，但是也就是精简了ReLU函数和模型部分的一些代码。

D2DL笔记_6

Sun, 27 Mar 2022 22:47:49 +0800

模型选择、过拟合和欠拟合

模型选择：训练集、验证集

用训练集训练模型得到相关权重参数，可以用验证集初步验证参数后再进行训练调整，但是测试集只有最后才能用来输出模型的结果，过程中不允许测试集数据加入训练。

这样主要是为了得到真实结果，评估模型的泛化性能，即模型不能只在训练集上有很好的结果，它要在拿出去应用的时候都能有好的表现。

拿一个预测猫狗的例子来解释过拟合与欠拟合：

过拟合：将训练集中的一些噪声或非必要信息学习成模型的特征，比如我只需要模型能够分辨是不是狗，由于数据集中只有哈士奇和阿拉斯加，导致模型认为只有黑白毛色的大型犬才是狗，这就是拟合“过了”。

欠拟合：同理，也就是训练集数据太少或是训练模型过于简单，导致模型没学到猫和狗的足够的特征，也就是没拟合到位，把猫认为是狗。

一般来说，数据集过小或模型过简单，会造成欠拟合，对不大的数据集使用很深的模型（或者跑很多个epoch）就会造成过拟合。

所以，首先就是要求模型要足够大足够深，然后争取使用更大的训练集，想比欠拟合而言，在此基础上的一定程度的过拟合是可以接受的。

这就涉及到模型的复杂度和数据的复杂度问题，后面会说如何控制模型的复杂度（实际上就是调参，调整超参数，完全看手感）。

这一节就不加代码实现内容了，解释起来就是上面那些东西。

权重衰退

权重衰退是最常见也是最传统的处理过拟合的方法。

解决过拟合一般来说有两个方向的思路，一个是降低模型的体量，或者说容量，常见方法是减少模型的层数，训练的epoch数，或者减少参数。

另一种方向就是缩小权重的取值范围，把权重能够拟合的数值限制在一个较小的范围内，从而在一定程度上防止模型拟合一些比较夸张的噪声，这种方法就是权重衰退。

权重衰退的方法：

使用均方范数作为硬性限制：直接使用均方范数限制权重w的取值范围

使用均方范数作为硬性限制：在原来损失函数的基础上加上一个均方误差形式的罚项（penalty），通过罚项（因为是均方范数形式，也叫正则项）的系数来控制惩罚力度的大小，这也是常说的正则化，可以让模型拟合的曲线更平滑。

这样的话，在求梯度的时候，权重w就会减去一个学习率和罚项系数的乘积，每一次梯度更新的时候，权重相比没有罚项的时候会少更新一点，就是所谓的权重衰退。

权重衰退的实现：

人工生成一个数据集，数据如下：

首先调用包，只取20个训练数据，因为训练数据越小，模型越复杂的情况下，就会更容易过拟合（跟测试集大小没关系，测试集只是期末考试而已，不参加模型的训练）。

初始化模型参数：

定义L2范数罚项，为了方便后面对超参数（罚项系数）进行修改，所以没有把系数加进来：

训练函数：

试验一下不同的lambda（罚项系数）有什么不同的效果：

λ = 0：

可以看到过拟合很严重，模型在训练的时候疯狂拟合，损失也一直有下降，但是测试的时候损失基本不动，说明模型后面拟合到的那些特征对测试集来说没有任何帮助。

λ = 3：

可以看到train和test之间的差距还是蛮大的，说明过拟合还是存在，但是此时训练损失在下降（学到了更多的特征）的时候，测试集的损失也是有下降的，说明新拟合到的特征在测试集中也具备，也就提高了模型的泛化性能。而进一步学到了50个epoch左右，训练的损失已经不再降低了，说明这个时候的罚项已经使得权重w的取值范围接近了0，此时模型没有剩余的空间去拟合了，过拟合也就被控制住了（但因为数据集小而无法避免），如果再训练更多的epoch的话（或者更大的λ，但并不是越大越好），训练的效果还能更好。

基本在λ = 15的时候，过拟合方面的表现达到最佳，再提高λ，不会再显著增强模型的性能。

丢弃法（Dropout）

在训练数据中加入随机噪音进行扰动再来训练，从而强化训练过程使模型对测试中的扰动鲁棒，相当于在训练中加入一种正则，因为同是限制权重范围避免过拟合的方法，所以在推理预测的过程中，是不加入dropout的。

此外，在加入噪音后，要保持数据的期望与原始数据相同。通常将dropout作用在隐藏全连接层的输出上。

丢弃法对每个元素进行如下扰动：

这就意味这采取一定的概率p来将某些元素置0，做到所谓的“丢弃”，从而控制模型的复杂度，所以，其中丢弃的概率p是一个超参数。

数值稳定性

梯度爆炸、梯度消失：

梯度爆炸的问题：

1.值超出值域，即浮点数的范围；2.对学习率敏感，学习率大了，就意味着更大的参数，更大的梯度，梯度就会爆炸，学习率太小，训练速度就会很慢。

梯度消失的问题：

根据一些激活函数，比如sigmoid函数，函数输入过大或过小时，梯度就会变得很小，n个层累乘时值就会趋近于0，此时无论如何修改学习率，训练都没有结果，学不到特征且训练速度慢，梯度消失也会限制神经网络的深度。

解决办法：

限制梯度值在一定合理的范围内；

将乘法变为加法，消除累乘带来的数值过大或过小，如ResNet和LSTM；

归一化，梯度归一化，梯度裁剪，将很小的梯度值扩大，将很大的梯度值缩小；

合理的初始权重和激活函数的选用。

让每层输出的方差都是同一个常数：

对每一层的多个输出，都保持均值为零，方差为同一特定常数，这样无论网络多深，都可以使结果在一个比较合理的范围内。

权重初始化：

在合理值区间里随机初始参数，因为训练刚开始的时候权重特别容易不稳定，变化过大意味着过大的梯度，可能导致权重变大，给后续学习增加难度，所以先给一个权重取值的范围，初始化一下，但是也不能在接近最优解的区间内初始化，因为最优解附近比较平滑，梯度很小，容易梯度消失。

要每一层的结果均值都为零，方差都为同一常数，需要满足一定的条件（需要概率论推导）。基于这一点选择激活函数，通过tanh或者ReLU，抑或是调整之后的sigmoid，即4×sigmoid-2（泰勒展开后可以明显看出调整后的激活函数经过原点且在邻域内近似y=x），也满足条件，可以使用。

TIPS：D2DL的第一部分到这里基本就结束了，基础理论和一般的传统方法主要就是之前笔记中的这些，其他内容如有遇到就在第二部分再做补充记录，下一部分主要就是pyTorch的应用内容，涉及到python和pyTorch各种模块的使用。