[toc]

1.数据库

1.1 数据库概念(数据库)

数据库是长期储存在计算机内,有组织的,可共享的大量数据的集合,数据库中的数据按照一定的数据模型组织,描述和储存,具有较小的冗余度(redundancy),较高的数据独立性与易扩展性,并可以为各种用户共享

基本特点

  • 永久存储
  • 有组织
  • 可共享

1.2 数据库的存储过程(数据库)

存储过程是由过程化SQL语句书写的过程,这个过程经过编译和优化后存储在数据库服务器中,使用时只需要调用,无需编译

优点

  • 因为存储过程不需要在提出操作请求时才进行语法分析和优化,因此运行效率高,提供了在服务器快速执行SQL语句的有效途径
  • 存储过程降低了客户机与服务器之间的通信量,只有最终的处理结果才返回客户端
  • 方便实施企业规则

1.3 什么是原子操作(数据库/Java)

如果这个操作所处的层(layer)的更高层不能发现其内部实现与结构,那么该操作为原子操作

  • 原子操作可以是一个步骤,也可以是多个操作步骤,但是其顺序不可以被打乱

通俗的说,原子操作中的所有内容要么全部按顺序执行,要么不执行,不可能只执行其中一个子操作

1.4 什么叫视图?视图在数据库的第几层(数据库)

视图是从一个或者几个基本表导出的表,与基本表不同,视图是一个虚表

  • 数据库中只存放视图的定义,而不存放视图对应的数据,这些数据仍然存放在原来的基本表中
  • 一旦基本表中的数据发生变化,从视图中查询出来的数据也就随之改变了

视图在数据库中属于外模式(用户模式)

1.5 关系模式与关系(数据库)

关系模式与关系的区别

  • 关系的描述,称为关系模式
  • 关系模式是型,关系是值

可以形式化的表示为 R(U,D,DOM,F)

  • R为关系名
  • U为组成该关系的属性名集合
  • D为U中属性所来自的域
  • DOM为属性向域的映像集合
  • F为属性间数据的依赖关系集合

1.6 事务的四个性质(数据库)

事务一般指的是要做的或所做的事情,事务是应用程序中一系列严密的操作

  • 原子性 : 一个事务是一个不可分割的单位
  • 一致性 : 事务必须是数据库从一个一致性状态到另一个一致性状态
  • 隔离性 : 一个事务的执行不能被其他事务所干扰
  • 持久性 : 一个事务一单提交,其对数据库中数据的改变就是永久性的

俗称ACID
atomicity,consistency,isolation,durability

1.7 数据库的三级模式结构(数据库)

三种模式指 外模式,模式,内模式

模式(schema)

也称为逻辑模式,是数据库中全体描述的逻辑结构和特征的描述,是所有用户的公共数据视图

外模式(External schema)

也称为子模式或者用户模式,是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述

  • 是数据库用户的数据视图
  • 是与某一应用有关的数据的逻辑表示

外模式一般是模式的子集,一个数据库可以有多个外模式

内模式(Internal schema)

也称为存储模式,一个数据库只有一个内模式。是数据物理结构和存储方式的描述,是数据在数据库内部的组织方式

1.8 关系操作(数据库)

基本关系操作

基本的5种关系操作

  • 选择
  • 投影
  • 笛卡尔积

其他操作都可以用基本的操作来定义和导出

1.9 关系的完整性(数据库)

①实体完整性

如果属性A是基本关系R的主属性,则A不能取空值

②参照完整性

参照关系与外码

设F为基本关系R的一个或者一组属性,但不是关系R的码,Ks是基本关系S的主码,如果F与Ks相对应,则称F是R的外码(foreign key),并且称基本关系R为参照关系,基本关系S为被参照关系(referenced relation)或者目标关系,关系R和S不一定是不同的关系

参照完整性规则

如果属性F是基本关系R的外码,其与基本关系S的主码Ks相对应,则对于R中每个元组在F上的值必须

  • 或者取空值(F的每个属性值都为空值)
  • 或者等于S中某个元组的主码值

③用户定义的完整性

任何关系数据库系统都应该支持实体完整性和参照完整性

1.10 断言(数据库)

在SQL中可以使用数据定义语言中的CREATE ASSERTION语句,通过声明性断言(declarative assertions)来指定更具一般性的约束

可以定义涉及多个表的或者聚集操作的比较复杂的完整性约束
断言创建之后,任何对断言中所涉及的关系的操作都会触发关系数据库管理系统对断言的检查,任何使断言不为真值的操作都会被拒绝执行

1.11 触发器(数据库)

trigger,触发器是用户定义在关系表上的一类由事件驱动的特殊过程,一单定义,触发器就会被保存在数据库服务器中

任何用户对表的增删改操作均由服务器自动激活相应的触发器

  • 触发器类似于约束,但是比约束更加灵活,可以实施更为复杂的检查和操作

1.12 规范化(数据库)

函数依赖

设R(U)是属性集U上的关系模式,X,Y是U的子集,如果对于R(U)的任意一个可能的关系r, r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或者Y函数依赖于X,记为 X→Y

  • 设K为R<U,F>中的属性或者属性组合,如果U完全函数依赖于K,则K为R的候选码
  • 如果U部分函数依赖于K,则K为超码,候选码是最小的超码
  • 如果候选码多于一个,则选定其中一个为主码
  • 包含在任何一个候选码中的属性称为主属性
  • 如果整个属性组是码,则称其为全码

1NF

满足最低要求的叫做第一范式
最低要求:确保每个子弹不可再分

2NF

倘若R∈1NF,且每一个非主属性完全依赖于任何一个候选码,则R∈2NF

3NF

设关系模式R<U,F>∈ 1NF,若R中不存在这样的码X,属性组Y以及非主属性Z(Z不属于Y)使得X→Y,Y→Z成立,X不函数依赖于Y,则称R<U,F> ∈ 3NF

通俗的说就是不存在传递依赖

若R∈3NF,则每一个非主属性既不传递依赖于码,也不部分依赖于码

BCNF

(Boyce Codd Normal Form),

关系模式R<U,F>∈1NF,若X→Y 且 Y不属于X时X必含有码,则R<U,F>∈ BCNF

也就是说,关系模式R<U,F>中如果每一个决定因素都包含码,就证明该关系模式∈BCND

多值依赖

设R(U)是属性集U上的一个关系模式,X,Y,Z是U的子集。并且Z=U-X-Y,关系模式R(U)中多值依赖 X→→Y成立。当且仅当对R(U)的任一关系r,给定的一对(x,z)值,有一组Y的值,这组值仅仅决定于x值而与z值无关

4NF

关系模式R<U,F>∈1NF,如果对于R的每个非平凡多值依赖 X→→Y(Y不属于X),X都含有码,则称R<U,F>∈4NF
4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖

一个关于规范化的不错的文章: link

1.13 数据库中的连接运算类型(数据库)

等值链接

其从关系R与S的广义笛卡尔积中选取A,B属性值相等的那些元组

自然连接

是一种特殊的等值连接,其要求两个关系中进行比较的分量必须是同名的属性组,并且要在结果中把重复的属性列去除

1.14 数据独立性(数据库)

物理独立性

指用户的应用程序与存储在磁盘上的数据库中的数据是互相独立的

逻辑独立性

指的是用户的应用程序与数据库结构是相互独立的(数据的逻辑结构改变时,用户程序可以不变)

1.15 索引(数据库)

索引是用于提高数据库表数据访问速度的数据库对象

  • 可以避免全表扫描
  • 对于非聚集索引,有些查询可以不访问数据也

选定原则

  • 表的某个字段值的离散度越高,越适合选座索引的关键字
  • 占用存储空间少的字段更适合
  • 存储空间固定的字段适合
  • 经常在Where语句中被使用的字段
  • 更新频繁的字段不适合创建索引

2.操作系统

2.1 操作系统中的系统调用(操作系统)

资料来源
系统调用(system call),是OS与应用程序之间的接口,是用户程序取得OS服务的唯一途径

执行过程

  1. 硬件接收到中断信号,立刻保护现场,并查找中断向量表,将CPU控制权交给系统调用总入口程序
  2. 对于系统的调用总入口程序,也要保护现场,将参数保存在内核的堆栈中,然后查找系统调用表,将CPU控制权转交给对应的系统调用处理程序或者是内核函数
  3. 执行系统调用处理程序
  4. 恢复现场,返回用户程序

2.2 进程的三种状态,以及转换过程(操作系统)

三种状态分别是: 就绪状态,运行状态,阻塞状态

  1. 就绪状态:进程获得了除了CPU之外的所有必要资源,只需要获得CPU就可以执行
  2. 运行状态:进程已经获得了CPU,正在运行
  3. 阻塞状态:处于执行状态的进程由于发生某些事情而暂时无法继续执行,放弃处理处理机处于暂停状态

转换过程

1.PNG

2.3 分段与分页的区别(操作系统)

  • 页的大小固定且由系统确定,一个系统只能有一种大小的页面。段的长度不固定,决定于用户所编写的程序,通常由编辑程序在对源程序进行编辑的时候,根据信息的性质来划分

  • 页是信息的物理单位,分也是为了实现离散的分配方式,从而消减内存的外零头。 段是信息的逻辑单位,含有一组相对完整的信息,目的是为了能更好的满足用户的需要

  • 页的地址空间是一维的,也就是单一的线性地址空间。而段的地址空间是二维的,标识一个段地址时要同时给出段名和段内地址

  • 分页会产生内零头,但没有外零头。分段有外零头,但没有内零头

  • 分页不容易实现共享和动态链接,分段容易实现

2.4 抖动 与 工作集(操作系统)

抖动 的根本原因

同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程的正常运行基本要求。使得每个进程在运行中频繁的出现缺页。必须请求系统将缺失页面调入内存。

  • 系统中排队等待页面调入/调出的进程数目增加
  • 对磁盘的有效访问时间急剧增加,造成每个进程的大部分时间都用于页面的换进换出

最终导致 处理机的利用率急剧下降趋于0

工作集

是指在某段时间间隔△里,进程实际所要访问的页面集合

为了较少的产生缺页,应当将程序的所有工作集装入内存中。
用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似

2.5 程序局部性(操作系统)

程序局部性是指程序在运行的时候呈现出来的局部性规律

  • 空间局部性:一个存储单元被访问,则其附近的单元也可能被访问
  • 时间局部性:在一段时间间隔内程序的执行局现在某个部分,所访问的存储空间也局限在某个区域

2.6 同步与互斥(操作系统)

  • 同步表现为直接制约,比如说管道通信
  • 互斥表现为间接之约,比如多个进程同时请求打印机

2.7 线程与进程的区别(操作系统)

  • 线程是程序执行的最小单位,而进程是操作系统分配资源的最小单位
  • 一个进程由一个或多个线程构成,线程是一个进程中代码的不同执行路线
  • 进程之间相互独立,但是同一进程下的各个线程共享程序的内存空间以及一些进程级的资源
  • 线程的切换相比于进程来说要快很多

2.8 产生死锁的必要条件(操作系统)

  • 互斥条件 : 进程对所分配到的志愿进行排他性使用
  • 请求与保持条件 : 进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有
  • 不可抢占条件 : 进程已获得的资源在未使用完之前不能被抢占
  • 循环等待条件 : 在发生死锁时,必然存在一个进程-资源的循环链

2.9 操作系统的基本特性(操作系统)

  • 并发(Comcurrence)
  • 共享(Sharing)
  • 虚拟(Virtual)
  • 异步(Asynchronism)

2.10 进程调度算法

先来先服务算法

最简单,不利于短作业

1.时间片轮转法(抢占)

以一个周期性间隔产生时钟中断,中断发生后当前正在运行的进程置于就绪队列中,并给予先来先服务策略选择下一个就绪作业
因为每个进程在被抢占之前都给定一定时间,因此也称为时间片

2.最短进程优先(非抢占)

原则是下一次选择与处理时间最短的进程,利于短作业,不利于长作业

3.最短剩余时间优先(抢占)

在最短进程优先基础上加上了抢占机制,进程调度总是选择预期剩余时间更短的进程
存在抢占,有长作业进程饥饿的危险

最高响应比优先

设等待处理时间为w,s为预计的服务时间,响应比R如下计算
R=(w+s)/s

反馈法(适用于没有关于进程相对长度的情况)

使用动态优先级机制

  • 当一个进程第一次进入系统中时,被放置于一个优先级队列中
  • 当第一次被抢占后并返回就绪状态时,会被放置在下一个低优先级队列中,依次类推
  • 除了优先级在最低的队列中之外,都使用先来先服务机制

2.11 重定位

静态重定位

根据内存的具体情况将装入模块装入到内存的适当位置,会使得装入模块中的所有逻辑地址与实际装入内存后的物理地址不同

动态重定位

将地址重定位的时间推迟到程序执行时在进行,也就是说装入内存的所有地址依旧都是逻辑地址

2.12 页面置换算法

先进先出页面淘汰算法(FIFO)

淘汰最新进入内存的页面

最近最久未使用页面淘汰算法(LRU)

总是把最长时间没有访问过的页面淘汰

最近最少用页面淘汰算法(LFU)

总是把当前使用最少的页面淘汰出去

###最优页面淘汰算法(OPT)
把以后不再使用或者最长时间内不会用到的页面淘汰出去(上帝视角)

3.数据结构

3.1 Dijkstra算法(数据结构)

资料来源:source
该算法用于寻找最短路,即最短路问题
从图中某个顶点除法到达另外一个顶点所经过边的权重和最小的一条路径称为最短路径

  • 该算法使用了广度优先搜索解决了赋权有向图或者无向图的单源最短路径问题,算法最终得到的是一个最短路径树
  • 该算法实际采用的是一种贪心策略

过程

  1. 首先声明一个数组dis来保存源点到各个顶点的最短距离,和一个保存已经找到了最短路径的顶点集合T
  2. 初始时,源点的路径权重被赋值为0(dis[begin] = 0)
  3. 对于顶点s能直接到达的边,就把对应的dis设为该边的权重,同时把其他所有的(不能直达的)顶点路径长度设为无穷,此时集合T只有源点
  4. 随后从dis数组中选择最小值,则该值就是源点待该值对应的顶点的最短路径,并把该点加入T中
  5. 重复进行如下比较:新加入的顶点是否可以到达其他顶点,并且通过该顶点到达其他点的路径长度是否比源点直接到达短。如果是就替换

3.2 排序梳理(数据结构)

①堆排序

  • 不稳定排序
  • 最坏,最好,平均时间复杂度都为O(nlogn)
  • 是选择排序的一种

基本思想

将待排序序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点,将其与莫为元素进行交换,此时末尾就为最大值,然后将剩余 n-1 个元素重新构造成一个堆,得到n个元素的次小值。如此反复执行就能得到有序序列了

  • 一般升序采用大根堆,降序采用小顶堆

②快速排序

  • 思路为 分治法
  • 最坏时间复杂度为O(n^2),仅当排序已经为基本有序状态时,但是可以避免这种状况
  • 平均时间复杂度为O(nlog2n)
  • 是一种不稳定排序
  • 其空间复杂度为O(log2n)

③归并排序

  • 最好,最坏,平均时间复杂度均为O(nlog2n)
  • 是一种稳定排序

④冒泡排序

  • 最好时间复杂度O(n)
  • 最坏和平均时间复杂度均为O(n^2)
  • 是稳定排序

⑤希尔排序

  • 平均时间复杂度为O(n^1.3)
  • 稳定排序

⑥选择排序

  • 平均,最好,最坏时间复杂度均为O(n^2)
  • 是不稳定排序

3.3 排序算法的稳定性(数据结构)

能保证排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同

如果A[i] == A[j]
排序之后,A[i]还是要在A[j]之前

一篇很好的稳定性随笔 : link

4.计算机网络

4.1 网络服务质量(QoS)包含哪些方面(计算机网络)

QoS(网络服务质量),是网络的一种安全机制,用于解决网络延迟与阻塞等问题的技术

  • 吞吐量(往上流量的度量)
  • 时延(时延=发送时延+传输时延+处理时延+排队时延)
  • 时延变化(包括抖动和漂移)
    • 抖动:高频的时延变化
    • 漂移:低频的时延变化
  • 可用性
  • 丢包

4.2 网络模型(计算机网络)

TCP/IP四层模型

  • 应用层
  • 传输层
  • 网络层
  • 网络接口层

TCP/IP五层模型

  • 应用层
  • 传输层
  • 网络层
  • 数据链路层
  • 物理层

OSI七层模型

  • 应用层
  • 表示层
  • 会话层
  • 传输层
  • 网络层
  • 数据链路层
  • 物理层

具体关系

2.jpg

4.3 iPv4与iPv6的主要区别(计算机网络)

  • iPv6的地址空间更大,其地址空间为128位,而iPv4只有32位
  • iPv4使用地址解析通讯协议(ARP),iPv6使用多点传播(Neighbor Solicitation)消息取代
  • iPv4使用地址掩码,iPv6未使用

4.4 网络协议的三个核心要素(计算机网络)

  • 语法 : 定义了数据与控制信息的格式
  • 语义 : 定义了需要发出何种控制信息,完成何种响应动作以及作出何种响应
  • 同步 : 定义了事件实现顺序的详细说明

4.5 TCP与IP的区别

TCP

传输控制协议,是一种面向连接的,端对端,可靠的基于IP的传输层协议,主要特点是3次握手建立连接,4次挥手断开连接

IP

因特网协议,IP协议位于网络层,IP协议规定了数据传输时的基本单元和格式,IP协议还定义了数据包的递交办法和路由选择

IP层接收由更底层发来的数据包,并把该数据包发送到更高层(TCP层),相反,IP层把从TCP接收来的数据包传送到更底层

4.5 数据交换方式

电路交换

  • 步骤:建立连接,传输连接,拆除连接
  • 特征为:独占信道资源
  • 实时性好,信道利用率低

分组交换

  • 化整为零,存储转发
  • 信道利用率高,有利于差错控制,安全
  • 传输延迟较大,实时性差

4.6 差错控制

传输中的差错都是由噪声引起的

  • 全局性:随机热噪声,信道固有,持续存在
    • 解决方法:提高信噪比来减少避免干扰
  • 局部性:外界特定的短暂原因造成的冲击噪声,是产生差错的主要原因
    • 可用编码技术来解决

4.6.1.1 自动重传请求(ARQ)

接收端检测出差错时,就设法通知发送端重发,直到接收到正确的码字

4.6.1.2 前向纠错(FEC)

接收端不但能发现差错,而且能确定二进制数码的错误位置

4.6.2 检错编码

  • 奇偶校验码:只能检查出奇数个byte错误
  • 循环冗余码

4.6.3 纠错编码

  • 海明码:发现双byte错误,纠正单byte错误

4.7 OSI七层各层具体作用

参考:https://www.sohu.com/a/359929827_120300832

物理层

  • 参考模型的最底层,该层是网络通信的数据传输介质
  • 由连接不同节点的电缆与设备共同构成
  • 主要功能:利用传输介质为数据链路层提供物理连接,负责处理数据传输并且监控数据出错率,以便数据流的透明传输

数据链路层

主要功能:在物理层提供的服务基础上,在通信的实体之间建立数据链路连接,传输以“帧”为单位的数据报,并采取差错控制和流量控制的方法,使得物理线路由有差错变为无差错

网络层

主要功能:为数据在节点之间传输创建逻辑链路,通过路由选择算法为分组通过通信子网选择最适当的路径,实现拥塞控制等功能

传输层

主要功能:向用户提供可靠的端到端服务,处理数据包错误,数据包次序等关键传输问题

会话层

主要功能:负责维护两个结点之间的传输连接,确保点到点传输不中断,管理数据交换等

表示层

用于处理在两个通信系统中交换信息的表示方式

应用层

为应用软件提供服务

4.8 虚电路和数据报

虚电路

  • 虚电路在通信前发送方和接收方之间必须建立连接
  • 虚电路是面向连接的网络服务
  • 虚电路不是真正的物理电路,而是一种逻辑电路
  • 一条链路上可以有多条虚电路
  • 一旦虚电路建立完毕,本地通信的所有分组必须经过该虚电路进行,因此,虚电路可以保证分组的顺序接收
  • 仅当建立虚电路时需要源/目的节点地址

数据报

  • 无需提前建立连接
  • 每个报文分组携带完整的源/目地址,独立选择路径,通过不同的路径到达目的主机
  • 子网无需保存状态信息

4.9 数字信号的编码

非归零编码

用高电平表示0,低电平表示1,或者反之

  • 编码/译码简单
  • 内部不含时钟信号,收发端同步困难

曼彻斯特编码

每一位中间有一次跳变,又表示数据,又作为同步信号,从高电平跳变到低电平表示0,从低电平跳变到高电平表示1,反之亦然

  • 抗干扰能力强

差分曼彻斯特编码

每一位中间也有一次跳变,但是跳变仅作为同步信号,不表示数据,数据值通过每位开始时有无跳变来表示有跳变表示0,无跳变表示1,反之亦然

  • 比曼彻斯特的抗干扰能力更强

4.10 多路复用技术

频分多路复用(FDM)

将一条物理线路的总带宽分割为若干个较小带宽的子信道,每个子信道传输一路信号

时分多路复用(TDM)

将一条高速物理线路的传输时间划分为若干相等的时间片,轮流的为多路信号使用

统计时分多路复用(TDM)

采用动态分配实践策略,也就是有数据要传输的线路才分配时间片

4.11 流量控制

停等协议

过程

  • 发送方发送一帧之后等待对方的应答
  • 接收端收到一帧之后检查校验位串,如果出错,就返回否认,否则返回确认
  • 发送端收到确认后,立即发送下一帧,收到否认重发该帧
  • 发送端发送一帧后会启动超时计时器,如果超时,则重发该帧
  • 接收端保存最近收到的帧序号

优点

简单

缺点

信道利用率低

滑动窗口协议

允许发送方连续发送若干帧后等待对方应答

  • 窗口:可容纳数据帧的缓冲区
  • 发送窗口:发送方用来保存已发送但是尚未经确认的数据帧
  • 接收窗口:接收方用于保存已经正确接收但是尚未提交给主机的数据帧

顺序接收管道协议(回退n)

接收窗口尺寸为1的滑动窗口协议,或者称为回退n协议

  • 发送方可以连续发送n帧而无需对方应答,但是需要将已发出但是尚未收到确认的帧保存在发送窗口中,以备由于出错或者丢失而重发
  • 接收方将正确的帧序号落入当前接收窗口的帧存入接收窗口,同时按顺序将接收窗口的帧交给主机,出错或者帧序号未落入当前窗口的帧全部予以丢弃
  • 当某个帧出错或者丢失,其后到达的帧都丢弃,并且返回否认信息,请求对方从出错帧开始重发

选择重传协议

如果某一帧出错,后面正确到达的帧虽然不能立即送达网络层,但是接收方可以将其保存在接收窗口,仅要求发送方重传发错帧

比较

停等协议是发送窗口为1,接收窗口为1的滑动窗口协议
回退n是发送窗口大于1,接收窗口为1的滑动窗口协议
选择重传协议是发送窗口大于1,接收窗口大于1的协议

4.12 路由选择策略

扩散法(静态策略)

  • 当结点收到一个分组之后,将该分组向除了进来的链路之外的所有其他链路进行转发,结果至少有一个分组以最快的速度到达目的节点
  • 会产生大量重复分组(解决方法:每个分组设置一个下跳字段,每经过一个节点下跳数-1.当下跳数为0时,丢弃该分组)

固定式路由选择(静态策略)

  • 每个节点保存一张固定的路由表,当某一分组到达时,根据分组的目的节点
  • 一般由网管中心根据最佳路由算法为每个路由产生固定路由表并发给该节点,固定路由表一旦生成就不再改变
  • 无法适应网络流量和拓扑结构的变化

热土豆/孤立路由算法(动态策略)

  • 当一个结点收到一个分组后,选择一条输出队列最短的链路尽快转发出去(不管目的节点位于何方)
  • 提高链路的利用率,但是具有很大盲目性
  • 与固定路由算法混合使用

逆向自学习算法(动态策略)

  • 每个分组中包含结点计数器,每经过一个节点,计数器加一
  • 当一个结点R从链路L收到一个来自源节点S的分组时,如果结点计数器为n,就知道距离不会超过n
  • 经过一段时间的自学习,节点R会找到它到其他节点的最短路径以及最小距离值
  • 对好消息反应灵敏,对坏消息无法了解到

距离向量路由选择D-V算法(动态策略)

每个节点都保存一张路由表,路由表包括三个主要字段,也就是目的地址,最短距离,最佳输出链路。
相邻结点之间定期交换路由信息,并根据最新路由信息刷新路由表

无穷计数问题的解决

规定足够大的数作为无穷大

链路状态路由选择L-S算法

每个节点定期广播路由信息,并根据最新路由刷新路由表

  • 对网络反应迅速,但是广播LS分组占用信道容量大

DV算法和LS算法比较

  • DV定期交换路由信息,LS只有等网络拓扑结构发生改变时交换路由信息
  • DV交换范围是相邻的节点,而LS是全网
  • DV适用于小规模,变化缓慢的网络,而LS适用于大规模,变化比较激烈的网络

4.13 RIF,OSPF与BGP等协议

RIP协议

采用DV算法,用于小规模网络,选择16作为无穷

开放最短路由优先协议(OSPF)

采用LS算法,是目前Internet的主要内部网关协议

  • 支持区域概念,支持认证服务

BGP边界网关协议

采用改进型的DV算法,作为Internet外部网关协议

IP,ICMP,RARP等协议

IP协议

IP协议是Internet体系结构的核心协议,是连接异构网络的工业标准

  • 提供无连接的数据报服务,不能保证分组可靠,按需到达

ICMP网际控制报文协议

是为了提高IP数据报交付成功的机会
ICMP是IP层的协议

ICMP的目的是希望对IP包无法传输时提供报告,这些差错报告帮助发送方了解网络中发生的问题

ARP地址解析协议

地址解释协议(Address Resolution Protocol)是IP协议最重要的配套协议之一,其目的就是将IP地址转化MAC地址

标准ARP

ARP请求报文的各相关地址项,源IP和源MAC发出ARP请求的主机的IP地址和MAC地址,目标IP为希望获得其MAC地址的主机的IP地址,目标MAC位全“0”

无偿ARP

也称为免费ARP,是一种特殊的ARP请求报文

  • 源IP地址和目标IP地址都是发出这个ARP报文的主机的IP地址
  • 源MAC地址是发出这个ARP的MAC地址
  • 目的MAC地址是广播地址

RARP协议

直到MAC地址,不知道IP地址,通过该协议广播询问分组获取IP地址

4.14 IP地址与MAC地址的区别

  • IP地址是指Internet协议使用的地址,MAC地址是Ethernet协议使用的地址
  • IP地址的分配基于网络拓扑,MAC地址的分配基于制造商
  • IP地址为32位,MAC地址为48位

4.15 套接字

套接字是为了使应用程序能够方便的使用协议栈软件进行通信的一种方法

套接字上联应用进程,下联网络协议栈,是应用程序通过网络协议栈进行通信的接口

4.16 为何TCP连接要经过2MSL后才真正释放

MSL是任何报文在网络上存在的最长时间,超过这个时间的报文将会被丢弃

  • 第一,保证客户端发送的最后一个ACK报文段能够到达服务器,防止已经失效的连接请求报文段出现在本连接中

4.17 可靠传输

可靠传输就是无差错传输,所有发送的数据都能被无差错接受

无差错接受指的是只接收没有传输错误的数据,丢弃或更正所有在传输过程中发生错误的数据

在不可靠的信道上实现可靠运输的条件

  • 各数据位无差错
  • 无数据丢失
  • 无数据重复
  • 数据顺序与发送端保持一致

4.18 什么是Karn算法

当重传发生时,RTO已经采用了指数退避,下一次的传输将按照这个已经增大的RTO计时,不应该将其纳入到RTT的统计样本中

指数避退

在TCP中当超时而发生连续多次重传时,两次重传之间超时阈值的设置遵循“指数避退原则”

超时第一次重传后,第二次重传等待时间是第一次的2倍,第三次重传等待时间是第二次的2倍,2位退避因子,直到收到重传数据包的应答

4.19 拥塞控制

1. 慢开始和拥塞避免

发送方维持一个叫做拥塞窗口cwnd的状态变量,拥塞窗口的大小取决于网络的拥塞程度

  • 原则 : 只要网络没有出现拥塞,拥塞窗口就大一些,以便把更多的分组发送出去,但网络出现拥塞后,拥塞窗口就小一些

2. 快重传和快恢复

4.20 DNS协议使用UDP还是TCP

DNS既可以使用UDP也可以使用TCP
大部分情况下使用UDP
但是当遇到,DNS响应报文过长

4.last 零散概念

  • 网络带宽 : 特定一段时间内网络所能传送的byte数,单位一般为bps
  • 网络延迟 : 一般与光速有关
  • 网络吞吐量 : 网络的可用带宽,也就是应用感受到的有效带宽
  • 路由选择(Routing) : 将来自一个网络的数据向另一个网络转发,路由器为不同计算机网络提供数据转发功能
  • 单播地址(Unicast Address) : 唯一地址标识网络中单一的目标节点
  • 多播/组播地址(Broadcast Address) : 标识网络中特定的一组节点
  • 服务 : 服务定义了某层向上一层提供的操作,服务由层与层之间的接口定义,低层是服务的提供者,而上层是服务的用户
  • 协议 : 协议定义了实现某层服务而需要在不同节点的相同层之间交换的数据的格式,含义以及流程
  • 信号带宽 : 信号能量所集中的频率范围(频谱)
  • 信道 : 传输信号的一条通路
  • 误码率 :数字信号byte在传输过程中出错的概率

5.离散数学

5.1

5.

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议