1. 总览

1.1 局域网（LAN）

第一个网络是LAN（Local Area Network），为了方便办公楼内共享数据和存储空间
最著名的LAN是1970年诞生的Ethernet以太网

• Ethernet

最开始是以一根以太网连接线连接各个电脑，每个电脑都能看到以太网传输的数据，但是不知道数据要发给
为了解决这个问题，Medica Access Control Address诞生了（MAC地址）
MAC地址作为数据的前缀发送到网络当

• CSMA

Carrier Sense Multiple Access载波侦听多路访问
Carrier：数据传输的载体（媒介）
Sense：侦听
意思是Multiple的计算机同时Sense Carrier
Carrier传播Data的速率叫做Bandwidth（带宽）

• CSMA的缺点

当Carrier中存在数据时，Ethernet中的计算机想要传输新的数据只能等Carrier中的数据清空，计算机虽然能检测到这种冲突，但是解决方法只用等待清空

• 解决CSMA冲突的方法

Exponential Backoff（指数避让）：当检测到冲突时，计算机等待1 + 0.random秒，如果该时间依然冲突，则等待2 x 之前的time

• Collision Domain（冲突域）

指一个Carrier以及其中的设备总称

• 交换机（Network Swich）

  • 作用

    将冲突域划分为更小的冲突域，解决一个冲突域中设备过多的情况

• 交换机列表

该列表记录了哪个MAC地址属于哪个冲突域
交换机判断计算机传输的数据属于哪个冲突域，如果是当前冲突域，只占用当前的一个冲突域，如果是另外一个冲突域，则占用两个冲突域

1.2 互联网（Internet）

• 网络的大小次序

LAN → WAN（由ISP管理） → Internet

• 数据交换的方式
  • 电路交换（Circuit Swithing）
• 使用专用通路直接连接
  • 报文交换（Message Switching）
• 在路由网络中，经过不同路由结点最终到达目的地，优势是可以由多条路
  hop count：路由跳转的次数。
  hop limit：限制路由跳转的总次数。作用是当hop count过大时，可判断路由线路出错（报文循环）
  报文交换缺点：当传输大文件时，整条线路都被占用，小文件只能等或者绕路
  • 分组交换（Packet Switching）
• 将message划分为更小的packets，每个packet的头部都有地址信息
  IP address：为使packets准确到达目的地，遵循Internet Protocol为终端划分的唯一地址

• 互联网的起源：ARPA Net

• 网络协议（Protocol）

  • IP：Internet Protocol
• 一种最低级的网络协议，存在于packets的头部，告诉packet要发送的目标地址，在packet’s head 中的目标地址遵循IP，头部中的目标地址称为metadata（元数据）
  • UDP：User Data Protocol
• 比IP高一级，标明packets要达到的目标程序。UDP也在packets的头部。
  • UDP内容
• Port Number（端口号），每个要联网的程序，都要向OS申请一个port number
  Checksum（校验和），通过发送前和接收后对数据求和，验证数据是否在传输过程中出错
  • UDP的缺陷
  • 1.没有数据修复和重发机制
    2.UDP不知道目标程序是否接收到消息
  • UDP适用情况
  • 1.当小部分数据缺失无伤大雅的情况，比如视频通话
    2.要求极低时延的情况，如FPS
  • TCP：Transmission Control Protocol
• TCP也存在于packets的head，一般与IP一同被称为TCP/IP, 和UDP一样，TCP也有端口号和校验和
  • TCP独有内容
• 1.Sequential Number：packets的序号，有了这个即使packets到达次序不同，最后也能按照原始顺序排列
  2.ACK 1：在接收方收到packets后要向发送方传递一个“确认码”，得知上一个packet到达后，发送方才发送下一个packet。如果在一定时间内未接收到确认码，packet将重发。TCP还能根据确认码的接收情况判断网络的拥塞情况，从而调整packets的发送
• DNS（Domain Name System）

域名系统，将域名对应到相应的IP address

• DNS的结构

2. 应用层

2.1 DNS

域名系统：Domain Name System

为什么要DNS？
因为“IP：Port”的组合代表的进程过多，不好记忆，使用域名来映射地址以帮助记忆

DNS结构是怎样的？

从上到下为顶级域，二级域，三级域（fudan牌面）

2.2 DNS服务器工作步骤

1. 先查找浏览器缓存，有则返回
2. 浏览器缓存没有则查询DSN解析器缓存，有则返回
3. DNS解析器没有则查询本地DNS服务器
4. 有则返回
5.6. 没有则依次通过根DNS服务器查到到哪个顶级DNS服务器去查找下一级
7. 通过顶级DNS服务器查到去哪个二级DNS服务器去查找下一级
8. 二级DNS服务器返回相对应的IP地址

2.3 DHCP

动态主机设置协议：Dynamic Host Configuration Protocol

作用：在局域网中应用UDP来集中管理IP地址，使局域网中的主机动态地获得IP地址，网关地址，DNS服务器地址等信息

DHCP工作流程
2.1 DHCP Client发现阶段
DHCP客户机寻找DHCP服务器的阶段。DHCP客户机以广播方式（因为DHCP服务器的IP地址对于客户机来说是未知的）发送 DHCP discover发现信息来寻找DHCP服务器，源地址为0.0.0.0目的地址为255.255.255.255。网络上每一台安装了TCP/IP协议的主机 都会接收到这种广播信息，但只有DHCP服务器才会做出响应。

2.2 DHCP Server提供阶段
DHCP服务器提供IP地址的阶段。在网络中接收到DHCP discover发现信息的DHCP服务器都会做出响应，它从尚未出租的IP地址中挑选一个分配给DHCP客户机，向DHCP客户机发送一个包含出租的 IP地址和其他设置的DHCP offer信息。

2.3 DHCP Client选择阶段
DHCP客户机选择某台DHCP服务器提供的IP地址的阶段。如果有多台DHCP服务器向DHCP客户机发来的DHCP offer提供信息，则DHCP客户机只接受第一个收到的DHCP offer提供信息，然后它就以广播方式回答一个DHCP request请求信息，该信息中包含向它所选定的DHCP服务器请求IP地址的内容。之所以要以广播方式回答，是为了通知所有的DHCP服务器，他将选择某台DHCP服务器所提供的IP地址。

2.4 DHCP Server确认阶段
DHCP服务器确认所提供的IP地址的阶段。当DHCP服务器收到DHCP客户机回答的DHCP request请求信息之后，它便向DHCP客户机发送一个包含它所提供的IP地址和其他设置的DHCP ack确认信息，告诉DHCP客户机可以使用它所提供的IP地址。然后DHCP客户机便将其TCP/IP协议与网卡绑定。
另外，除DHCP客户机选中的服务器外，其他的DHCP服务器都将收回之前为其提供的IP地址。

2.5 DHCP Client重新登录
以后DHCP客户机每次重新登录网络时，就不需要再发送DHCP discover发现信息了，而是直接发送包含前一次所分配的IP地址的DHCP request请求信息。当DHCP服务器收到这一信息后，它会尝试让DHCP客户机继续使用原来的IP地址，并回答一个DHCP ack确认信息。如果此IP地址已无法再分配给原来的DHCP客户机使用时（比如此IP地址已分配给其它DHCP客户机使用），则DHCP服务器给 DHCP客户机回答一个DHCP nack否认信息。当原来的DHCP客户机收到此DHCP nack否认信息后，它就必须重新发送DHCP discover发现信息来请求新的IP地址。

2.6 DHCP Client更新租约
DHCP服务器向DHCP客户机出租的IP地址一般都有一个租借期限，期满后DHCP服务器便会收回出租的IP地址。如果DHCP客户 机要延长其IP租约，则必须更新其IP租约。DHCP客户机启动时和IP租约期限过一半时，DHCP客户机都会自动向DHCP服务器发送更新其IP租约的信息。

2.4 HTTP

什么是HTTP？
超文本传输协议：HyperText Transfer Protocol
超文本可理解为“带超链接的文本”，HTTP是基于TCP的可靠传输协议，架构为CS模式。

HTTP格式？
http://:/<路径> ?参数

HTTP工作位置？
web浏览器与web服务器之间

web服务器工作步骤是怎样的？

HTTP有哪几种请求方法？
其实就是增删改查

HTTP的特点是什么？

1. 协议简单，所以通信速度快；
2. HTTP是无连接的协议，意思是每次连接只处理一个请求，服务器在处理完用户的一个请求并且受到用户应答后即断开连接，所以HTTP的总传输时间少；

3. 无状态的连接，意思是HTTP对事务没有记忆能力，当当前的事务需要处理前面的消息时，需要将前面的消息重传，所以在不需要前面消息的场景下很快，经常需要前置消息的情况很慢（HTTP1.1后支持保持连接状态）；

   2.4.1 HTTP请求

   HTTP请求的内容是什么？
   HHTP请求由三部分组成：

4. 请求行：HTTP协议中的第一行

   1. 请求方式：GET、POST等
   2. 请求路径
   3. 请求协议版本
5. 请求头：HTTP协议中的kv对
6. 请求正文：传递的数据

注意：get没有请求正文，因为get直接将请求的数据写在了地址栏（地址栏?后面跟的就是get的请求正文）

2.4.2 HTTP响应

HTTP响应的内容是什么？

1. 响应行（状态头）
   1. 协议版本
   2. 状态码：404（找不到），500（服务器异常），200（正常），3.7（重定向）等
   3. 状态码说明符
2. 响应头：一些kv对
3. 响应体：服务器返回的数据（浏览器所看到的内容）

   2.4.3 HTTP消息头

• 请求头

Referer：指明该请求的从哪而来
例如A页面跳转到B页面时，B中的Refere就是A页面的URL

• 响应头

Location：重定向域名
将客户端请求访问的域名重定向到一个新的域名，常用于网页域名更新时

Refresh：自动跳转（秒为单位）
隔几秒刷新页面或者隔几秒跳转到另外的页面

什么是web缓存？
工作原理： Web缓存就在服务器-客户端之间搞监控，监控请求，并且把请求输出的内容（例如html页面、 图片和文件）（统称为副本）另存一份；然后，如果下一个请求是相同的URL，则直接请求保存的副本，而不是再次麻烦源服务器。

什么是proxyServer（代理服务器）？
作用：

1. 防火墙：隐藏自身IP以免被攻击
2. proxy缓存：通常代理服务器都具有缓冲的功能，有很大的存储空间，网络出现拥挤或故障时，可通过代理服务器访问目的网站，节约带宽、显著提高访问速度和效率
3. 突破自身IP访问限制，访问一些自己网络无法打开的网站等

特点： 两次连接（browser与proxy之间，proxy与web server之间）

2.5 CDN

内容分发网络：Content Delivery Network
传统的浏览器访问服务器过程：

使用CDN之后：

CDN步骤：
1. 用户在浏览器中输入域名
2. 浏览器向DNS服务器请求对域名的解析，由于CDN对域名解析进行了调整，DNS会将域名解析权交给CDN专用的DNS服务器
3. CND专用DNS服务器向用户返回CDN负载均衡设备的IP给用户
4. 用户向CND负载均衡设备发送URL访问请求
5. CDN负载均衡设备为用户选择一台合适的CDN缓存服务器
6. 用户向缓存服务器发送请求
7. 缓存服务器响应用户请求，若这台缓存上没有用户想要的内容，这台缓存服务器将向上一级缓存服务器请求内容，知道追溯到网站的源服务器内容。

2.6 HTTPS（security）

由于HTTP是明文传输的，容易出现安全问题

HTTPS结构：https://:/<路径>
与HTTP的区别在于HTTPS的port为443

数字证书是什么？
可信任组织颁发给特定对象的认证（参考身份证）
（数字证书内容）

什么是SSL？
安全套接层：Secure Sockets Layer
位置：SSL是位于应用层和传输层之间的子层

作用：保证数据安全以及数据完整，对传输层数据进行加密后再进行传输

HTTPS工作流程
（E和D指的是加密和解密）

SSL安全参数握手过程是怎么样的？


1. 客户端生成随机数1，向服务器发送随机数1、协议版本和加密算法
2. 服务器生成随机数2，向客户端发送随机数2、数字证书（包含自身公钥）和加密算法ACK
3. 客户端确定证书是否有效，若有效，生成随机数3，用公钥加密传递给服务器，服务器通过私钥解密（非对称加密）获得随机数3
4. 双方通过随机数1、2、3以及加密算法生成对称秘钥开启对称加密通信并且秘钥外界无法获得

3. 传输层

• 传输层概览

网络编程面向的接口即为传输层
网络层之间的通行可以看做是进程之间的通信

• 端口（Port）：每个端口对应一个进程
  • 大小：16bit（0-65535）
    一些常用端口号：
    
• Socket：可理解为TCP/IP协议的API
  • UDP：User Datagram Protocol
• UDP位置
  • 
• UDP首部
  • 
• UDP特点
  • 1. UDP为无连接协议：通信时无需首先建立连接
       2. 由于无连接，所以不能保证可靠传输
       3. 面向报文传输：面对应用层传输的数据，不做处理，直接合成UDP报文
       4. 无拥塞控制
       5. 首部开销小（对比TCP）
  • TCP：Transmission Control Protocol
• TCP的位置
  • 与UDP类似

• TCP结构（首部）

• 序号

范围:0~2^32 -1
含义：每个数据报的第一个字节的序号

• 确认号

期望收到的下一个数据报序号
举例：确认号为N，则N-1的数据报的数据都已收到

• 数据偏移

大小：4bits，范围0~15，每个bit表示32位（4字节）的偏移量
含义：数据偏离首部的距离
由于TCP选项的大小不同，所以偏移不同
最大偏移：15x4 = 60，所以TCP首部大小范围为20-60

• 保留字段
• TCP标记
  • 大小：6bits
    
• 窗口

大小：16bits
作用：允许对方发送的数据量
举例：确认号为501，窗口大小为1000，则可接受501~1500的数据

• 紧急指针

当URG=1时启用，指定紧急数据在报文中的数据

• TCP选项

主要为了TCP协议的拓展

• 可靠传输的基本原理
  • 停止等待协议

没有收到消息或者确认消息之前，双方都会停止发送确认消息或下一条消息
例外情况：消息超时，重传（每发送一条消息，都需设置一个定时器）

• 连续ARQ协议
  • ARQ:Automatic Repeat request(自动重传请求）
    接收方不必对每个消息进行确认，而是在收到几个分组后，对序号最大的一个分组发送确认，如果发送方接受到这个确认则表示这个分组前的所有分组都已得到确认
    举例：
    当收到确认消息5时，则滑动窗口滑到6开始下一组的发送
    优势：大大减小确认报文的数量
  • TCP协议的可靠传输

注意TCP中滑动窗口基于的单位是byte

• 选择重传

  选择重传的序号存储在TCP选项中，根据前面的计算，TCP选项最多40个字节，一个序号32bits，4byte，所以一个TCP选项最多存储10个序号
  注意：选择重传的序号指的是序号的范围，不是具体的序号数

• TCP协议的流量控制

流量控制为TCP协议独有的
流量控制：接收方可能希望发送方将数据发送的速率有一个上限（可能接受不赢）
原理：对TCP的窗口进行控制
举例：

特殊情况：rwnd在传输过程中丢失了
解决方法：坚持定时器
发送发在当接收到窗口为0的消息时，坚持计时器启动，发送方的坚持计时器每隔一段时间向接收方发送窗口探测报文，检测窗口是否依然为0

• TCP协议的拥塞控制
  • 拥塞产生的原因：一条数据链路会经过多种不同的设备，各个传输中介都可能成为木桶的短板
  • 与流量控制的区别： 流量控制侧重的是基于接收方的接收能力，控制点到点的通信量大小；拥塞控制是注重于整个网络的考虑
  • 如何判断拥塞：报文超时（排除了网络故障的因素）
  • 拥塞控制算法

cwnd：拥塞窗口
1.慢启动算法：从1开始指数式增长cwnd（每收到一个报文确认，cwnd + 1），当达到慢启动阈值（ssthresh）时停止增长
2.拥塞避免算法：当达到慢启动阈值时启动该算法。cwnd每次增大1。
当发生拥塞时，ssthresh = cwnd/2，cwnd = 1，此时又开始慢启动算法

• TCP的三次握手
  • 关注TCP标记6个比特位中的2个
• ACK：确认标记
  SYN：同步位，等于1表示连接请求
  ack不是ACK，ack表示期望下次收到的seq（序列号）
  举例：
  
  ACK=1表示接收方向的seq已经得到确认，ack表示期望发送方下次发送的seq
  • 为什么发送方要发送第三个确认报文？
• 原因：为了避免超时消息建立重复连接
  
  如果已经进行第三次握手，返回的超时消息将不会进行第三次握手，因为接受方无法判断是否超时，发送方必收到第二次握手，但是第三次握手可以避免！
• TCP的四次挥手
  • 关注TCP标记中的另一个比特位
• FIN：终止位，等于1表示释放连接

第二次挥手是因为发送方发送终止请求说明发送方要发的东西已经发完了，但是接收方感受到通知，需要把终止前要发送（回应）的消息发完，再进行第三次挥手。第三次挥手连续不断的发送FIN，直到收到发送方的ACK，发送方收到一个FIN则TIME-WAIT刷新一次时间。

• 等待计时器
  • 作用： 如果在该时间内再次收到FIN，那么Client会重发ACK并再次等待2MSL。所谓的2MSL是两倍的MSL(Maximum Segment Lifetime)。MSL指一个片段在网络中最大的存活时间，2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL，Client都没有再次收到FIN，那么Client推断ACK已经被成功接收，则结束TCP连接。
  • Socket（套接字）：IP与Port的结合，表示TCP连接的一端

（一个TCP连接的Socket表示）·

• Socket编程

Socket编程一般将通信方式看做是CS模式
（服务端）（客户端）

4. 网络层

网络层目标：决定数据在网络中的传输路径

本章概览

• 虚拟互联网络

忽略底层的真实物理网络，将端到端的连接看作是一个虚拟的网络

• IP协议
  • IP地址与MAC地址
• IP地址：长度32位，一般使用点分十进制表示。
  MAC地址固定不变且唯一，IP地址是网络层划分的地址，终端位于不同的网络下，IP地址会发生变化。
• IP数据报

IP数据报位置

IP数据报内容

• 4位版本：Ipv4/Ipv6, 不同的版本不能互相通信
• 
  
• 4位首部长度：表示IP首部的长度，最大为15，单位32bits（4byte），所以首部长度最大60byte
• 
  
• 总长度：占16位，最大数值为 65535，表示的是IP数据报总长 度（IP首部+IP数据）
• 值得注意的是该总长度最大大于MTU，当IP unit长度大于MTU时，数据链路层将对IP unit进行分片

• 16位标识（Identification）：如果数据链路层进行分片，每个分片的标识都是一样的

• 3位标志（Flag）：标志分片信息， 目前只有2位有意义；最低位为MF，MF=1代表后面还有分片的数据报，MF=0代表当前数据报已是最后的数据报。次低位为DF，DF=1代表不能分片，DF=0代表可以分片

• 
  

• 13位片偏移：当IP unit被分片时，片偏移记录该数据帧属于哪个片

• 8位TTL：标志IP数据报可经过的最大路由器数量，经过一个路由TTL - 1，当TTL = 0，丢弃该报文

• 8位协议：表明IP数据属于哪种协议（ICMP、TCP、UDP等）

• 首部校验和：校验首部数据

• 路由表

• 计算机和路由器都有路由表
  路由表形式：
  
• IP协议的转发流程

发送方A，接收方C

• 单层抽象过程

1.查询A的路由表，下一跳为E
2.E查询E的路由表，下一跳为F
3.F查询路由表发现C与F直连，转发数据

• 实际过程

1.A查询路由表，下一跳为E
2.A将IP数据报交给数据链路层打包，告知数据链路层下一跳MAC地址是E（通过查询ARP缓存表）
3.A将源MAC地址A和目的MAC地址E封装至数据帧
4.通过物理层将数据从A到E

• ARP（Address Resolution Protocol）地址解析协议

作用：将32位IP地址映射为48位MAC地址

• ARP缓存表

当缓存表没有对应IP地址的映射关系时，采用广播的方式获取映射关系
由于IP地址随时可能变化，ARP缓存表的记录不是永久有效的

• ARP处于的位置

不同类型数据帧的组成方式

ARP类型数据帧的内容

虽然ARP封装在数据链路层的数据帧内，但由于含有IP地址，所以属于网络层内容

• RARP（Reverse ARP）

通过MAC地址获取IP地址

• IP地址的子网划分
  • 分类的IP地址

• 网络号 + 主机号
  
  D、E类为特殊用途

• 特殊网络号

回环地址：不属于任何一类网络号，代表设备的本地虚拟接口，一般用来判断本机的网络协议是否存在问题

• 特殊主机号

• 统计

• 划分子网

网络号 + 主机号 → 网络号 + 子网号 + 主机号

子网掩码：与IP地址&得出子网号
网络号、子网号全为1，主机号全为0（抹掉主机号，网络号+子网号就出来了）

• CIDR（无分类编址）

网络前缀 + 主机号，在后面添加一个/n，表示网络前缀占n位
子网和超网：

先使用/24的超网掩码获得超网网络号，再使用/25的子网掩码获得子网网络号

• NAT（网络地址转换）
  • 内网地址与外网地址
• 内网地址：统一网关下的内部IP地址，可与其他统一网关下的内网IP重复，解决了IP地址不够用的情况
  
  外网地址：全球唯一
  • NAT：Network Address Translation
• 内网IP发送数据通过统一网关时，IP地址自动转换为外网IP
  • 静态NAT/动态NAT
• 静态NAT：一个外部地址对应唯一的一个内部地址，其隐藏IP等的特殊作用，不能扩充IP的数量
  动态NAT：使用多个外网地址对应多个内网地址，当内网需要进行外网访问时，随机NAT映射为一个外网地址，外网合法IP地址可略少于内网地址
  • NAPT

• NAP（Pot）T：使用内网地址 + 端口号 → 外网地址 + 转换唯一端口号来实现一个外网IP对应多个内网IP的作用

• ICMP：Internet Control Message Protocol（网络控制报文协议）

作用：报告IP传输中的错误和异常

位置：

协议号：1（写在IP报文的首部中的‘8位协议’）

• 两类ICMP内容：（首部 + 数据）

  • 差错报告报文
  • 询问报告报文

• ICMP的应用

  • Ping（询问报文中的Echo）
• 一般步骤：
  1.Ping回环地址：测试本地计算机的协议栈是否出现问题
  2.Ping网关：测试计算机到网关的通路是否通畅
  3.Ping远端地址：测试到ISP的通路是否顺畅
  • Traceroute应用（dos命令：tracert）
• 作用：测试IP数据报在网络中的路径
  原理：
  TTL：当TTL减为0时，数据报停止传送，并向源终端传送该TTL为0的点的IP地址
  步骤：
  1.先传送TTL为1的数据报，得到第一个hop的IP地址
  2.传送TTL为2的数据报。。。
  3.从而得到整个路径
• 路由概述
  • 将网络抽象为图
• 
  • 路由算法要求：
• 1. 路由算法比图算法复杂，因为路由的环境是不断变换的
     2. 算法需要足够简单稳定，以适应巨大的规模和变化的环境
     • AS：Atonomous System（自制系统）
• 每个ISP或者内部网可看做一个AS
  1. AS内部的网络自行管理
  2. AS外部的设备提供统一的出口
  AS内部协议：RIP、OSPF（内部网关协议）
  AS外部协议：BGP（外部网关协议）
  

• RIP：Routing Information Protocol（内部网关协议之一）

• DV 算法：Distance-Vector

数据结构：
每个节点使用两个向量
Di：dij表示当前记录的i到j的最短距离
Sj：sij表示当前记录的到达节点j的下一跳节点

算法步骤：
1. 节点i根据相邻节点x的Dx计算新的dij，New_dij = dix + dxj
2. 更新Di，dij = min（dji，New_dij）

• RIP过程

RIP将一个hop作为一个单位距离，上限为15

对于相邻路由X传来的路由信息：
1. 将本地路由没有的目的信息加上，将X有而本地路由没有的信息下一跳设置为X，距离为Dxj + 1
2. 将下一跳为X的路由信息更新（因为本地路由下一跳为X的信息是根据X而来的，所以X代表最新动态）
3. 根据X更新剩余信息
4. 相邻路由3分钟内无响应，将距离设置为16

• RIP的不足
  • 1.“坏消息传递慢”
    2. 限制了网络规模（15hops）
  • Dijkstra Algorithm

解决问题：单源路径最小问题

数据结构：

1. 邻接矩阵存储各顶点间边的权值（如果顶点过多则使用list）
2. 一个优先队列存储相邻边
3. 一个Boolean数组存储已确定最短路径的顶点

思想：贪心算法

思路：

1. 起始点A标记为已确定，并将A直连的点push进优先队列
2. 依据A到相邻点的距离更新邻接矩阵
3. pop优先队列得到点B，标为已确定（反证法可知），将与B相邻且不在队列中的点入队
4. 依据B到相邻点的距离更新邻接矩阵
5. 重复3,4直到所有点标记为已确定

• OSPF：Open Shortest Path First
  • LS协议：Link State Protocol，注意与RIP区别
• 特点：
  1.路由器间消息的传送为链路状态：距离、带宽、时延等（RIP只有hop）
  2.只有链路状态发生变化时，才发送更新消息（RIP每隔30s更新一次）
  3.每隔路由器向所有路由器发送消息，一传十、十传百，不会出现RIP中死循环的情况
  • OSPF特点
• OSPF是依据LS协议的具体实现
  1. OSPF的每个路由器都和其他所有路由器共享消息，每个路由器都有网络拓扑（Dijkstra前提）
  2. OSPF传递的消息为LS，比单纯的hop更加全面
  3. 只有LS变化时才传递消息，减少了消息的传递次数
  • OSPF5类消息

• 1. 问候消息：用于维护、确认相邻路由器的可达性
     2. LS数据库描述消息：向相邻路由器传递LS消息
     3. LS请求消息：向相邻路由器请求LS消息
     4. LS更新消息：将Route更新消息广播（OSPF中最常见的消息）
     5. LS确认消息

     • OSPF过程
• 1. 路由器接入网络
     2. 向邻居发送问候消息
     3. 与邻居交换LS数据
     4. 广播和更新未知路由
• BGP：Border Gateway Protocol（边际网关协议）

通过BGP Speaker（发言人）来进行AS之间的通信

• 为什么要使用BGP

1. 因为互联网规模太大，路由器存储有限，Dijkstra速度随顶点增加减慢
   2. 因为政治、法律因素，不能选择最优路线

• BGP特点

1. BGP不关心网络内部的拓扑
   2. BGP Speaker可认为设置路由规则
   3. BGP只能找到一条相对较好的路线

   5. 网络接口层

• 概览

网络层次

各层的作用

终端间的抽象

网络性能指标
带宽：bps: bit/s
时延：发送时延、传播时延、排队时延、处理时延
RTT: Rout-Trip Time,往返时间，使用ping命令查看

• 物理层

基本单位是bit

• 传输中介：双绞线、光纤、无线
• 信道复用：频分、码分、时分、波分

• 数据链路层

基本单位：帧

• 封装成帧：将网络层的一段数据前后添加特定标记

帧首尾标记：

• 透明传输：为了解决IP数据报中出现SOH、EOT的情况

解决方法：\SOH
\出现在真的SOH、EPT中的解决方法：\SOH

• 差错检测
  • 奇偶校验码
  • 循环冗余校验码CRC
• MTU

Max Transmission Unit
Unit过大和过小都会影响传输效率，过大→发送、处理时延过久，过小→数据帧Unit过多

• 路径MTU
  • 一条路径中的MTU由这条路径中最小的MTU所决定（木桶效应）
  • MAC地址：唯一物理地址，48位16进制

• Ethernet以太网

运用于数据链路层的协议，可完成相邻设备中的Unit传输

• 以太网协议数据格式

单位为Byte，CRC为校验码

• MAC地址表

计算机和路由器都有MAC地址表，相邻的设备通过广播的方式获取MAC地址，更新MAC地址表，每个MAC地址对应相应的硬件接口