第一章 计算机网络和因特网

计算机网络的两大功能

• 连通性
• 共享性

Internet具体构成

• 数以亿计的计算互连设备、通信链路、分组交换：路由器和交换机

• 主机（host）=端系统（end system）

  • 运行网络应用程序

• 通信链路(link)

  双绞线,光纤, 无线电频谱, 卫星
  传输速率 = 带宽(bandwidth)
  带宽单位为bps，bit per second每秒传输的位数，例如百兆光纤就是100M bps，实际传输使用的单位为BPS，1B=8bit，所以传输速率为100/8=12.5M BPS，就是12.5MB/s
  通信链路只有极限带宽，例如5号线极限带宽为300M，不能接千兆网卡，只能接百兆网卡
  网卡有传输的能力，传输速率取决于网卡能传输的能力，例如百兆，千兆网卡

• 分组(packet)交换：

  • 路由器（Router）和交换机（Switch）
  • 交换机：形成局域网
  • 路由器：链接互联网

协议的基本要素

• 语法：语法即是用户数据与控制信息的结构和格式
• 语义：语义即是需要发出控制信息，以及完成的动作与做出的响应
• 同步：同步可以理解为时序，即是对事件实现顺序的详细说明

网络核心

电路交换

电话交换机接通电话线的方式成为电路交换

• 每次会话预留沿其路径（线路）所需的独占资源－－电话网

• 从主机A到主机B经一个电路交换网络需要多长时间发送一个640Kb的文件?
  电路交换的频分和时分

  

  举例子：

  

• 过程

  • 建立连接
    • 会一直霸占着这条路径
  • 传输数据
  • 释放连接

• 优点

  • 传输速度快、高效
  • 实时

• 缺点

  • 资源利用率低
  • 新建连接需要占据一定的时间，甚至比通话的时间还长

多路复用

• 数据以离散的数据块通过网络来发送
  • 分片分配到会话
  • 分片没有被会话使用的情况下，分片空载(不共享)
  • 电路级性能（有保证）
  • 要求呼叫建立－－建立一个专门的端到端线路(意味着每个链路上预留一个线路)
  • 链路带宽分片

频分－frequency division

时分－time division

分组交换

每个端到端的数据流被划分成分组

• 所有分组共享网络资源

• 每个分组使用全部链路带宽

• 资源按需使用

  

报文交换

比较分组交换与电路交换：

• 分组交换允许更多的用户使用网络
• 
• 优势
  • 适合大量的突发数据传输
  • 资源共享
  • 简单，无需连接
• 缺点
  • 过渡竞争导致分组延迟与丢失
  • 需要可靠数据传输、拥塞控制协议

网络的分类

• 图中FDM频分，TDM时分
• 虚电路网络一定是面向连接的
• 数据报网络既可以提供面向连接的服务，也可以提供无连接的服务

四种时延

1.节点处理时延nodal processing delay：分析地址部分，进行差错检验等花费的时间

检查错误位
选择输出链路
高速路由器处理延迟－微秒级

2. 排队时延queueing delay：在进入路由器之后等待处理的时间

等待被发送到输出链路上的时间
取决于路由器的拥塞程度

3. 传输(发送)时延Transmission delay：从发送分组的第一个bit算起，到该分组最后一个分组被发送完毕需要的时间

R=链路带宽 (bps)
L=分组长度 (bits)
发送分组比特流的时间 = L/R

4. 传播时延Propagation delay：一个比特从链路一端传播到另一端所需要的时间

d = 物理链路的长度
s = 介质的信号传播速度 (~2x108 m/sec)
传播延迟 = d/s
注意: s和R是两个完全不同的速度参量!

总的节点延迟

• dproc = 处理时延
• dqueue = 排队时延
• dtrans = 传输时延
• dprop = 传播时延

流量强度

流量强度=分组长度L*平均分组到达率a/链路带宽R

L=分组长度 (bits)

a=平均分组到达率 average packet arrival rate

R=链路带宽 (bps)

流量强度：traffic intensity = La/R

流量强度与延迟关系

La/R ~ 0: 分组稀疏到达,无队列,平均排队延迟极小接近于0

La/R -> 1: 分组猝发到达,形成队列,队列长度迅速增加,排队延迟大幅增大

La/R > 1: 输出队列平均位到达速率超过送走这些位的极限速率，输出队列持续增长，排队延迟趋于无穷大

分组丢失

• 路由器输入链路和输出链路的缓冲区容量有限
• 当分组到达路由器输入链路发现缓冲区已满，则路由器只好丢弃分组
• 当分组在路由器内部要转发到输出链路时发现输出缓冲区队列已满，路由器只好丢弃分组
• 丢失的分组可能被前路由节点、源节点重传，或不重传
• 丢包率或分组丢失率（packet loss rate/ratio）

吞吐量

• 网络吞吐量：

  • 单位时间内整个网络传输数据的速率或分组数

• bps或data packets per second

• 吞吐量: 接收端接收到数据的比特速率 (bps )

  瞬时吞吐量: 某一瞬间的吞吐量

  平均吞吐量: 一段时间内的吞吐量均值

各层次常用协议

分层次结构

应用层

• 支持网络应用，报文传
• FTP, SMTP, STTP

传输层

• 主机进程间的数据段传送
• TCP、UDP

网络层

• 主机与主机间分组传送

• IP、路由协议

链路层

• 相邻网络节点间的数据帧传送
• PPP(Point to Point Protocol)，Ethernet

物理层

• 物理介质上的比特传送

• 对等实体:

  • 两台计算机上同一层所属的程序、进程或实体称为该层的对等程序、对等进程或对等实体

第二章 应用层

两种方式

客户机/服务器 CS

• 服务器：具有客户资源

  • 总是打开的主机
  • 具有固定的、众所周知的IP地址
  • 主机群集常被用于创建强大的虚拟服务器

• 客户机：发出请求和接受数据

  • 同服务器端通信
  • 可以间断的同服务器连接
  • 可以拥有动态IP地址
  • 客户机相互之间不直接通信

对等 P2P方式

进程通信

• 进程
  • 运行在端系统中的程序
• 同一主机上的两个进程通过内部进程通信机制进行通信
• 不同主机上的进程通过交换报文相互通信

套接字

• 又叫应用程序编程接口API

进程寻址

IP地址+端口号

web应用和HTTP

• 网页

• 由许多对象组成

• 对象就是文件，可以是HTML文件, JPEG图像, Java applet, 音频文件…

  多数网页由单个基本HTML文件和若干个所引用的对象构成

  • 每一个对象对应一个URL

使用TCP：HTTP属于应用层，使用运输层的TCP进行传输

• 1 客户初始化一个与HTTP服务器80端口的TCP连接(创建套接字)
• 2 HTTP服务器接受来自客户的TCP连接请求, 建立连接
• 3 Browser (HTTP client)和Web服务器 (HTTP server) 交换HTTP消息(应用层协议消息)包括HTTP请求和响应消息
• 4 最后结束，关闭TCP连接

HTTP是无状态协议

• HTTP服务器不维护客户先前的状态信息

非持久的HTTP连接

• 每个TCP连接上只传送一个对象，下载多个对象需要建立多个TCP连接

• HTTP/1.0使用非持久HTTP连接

• 非持久HTTP详解

  • 假设用户输入URL http://www.someSchool.edu/someDepartment/home.index 网页由1个HTML文件, 和10个jpeg图像构成
  • 解析步骤

  第一步：建立TCP连接

  • HTTP客户机初始化与服务器主机中HTTP服务器的TCP连接
  • 服务器中HTTP服务器在80端口监听TCP连接。收到请求连接，接受，建立连接，通知客户

  第二步：HTTP请求连接

  • HTTP客户发送HTTP请求消息，包含URL到TCP连接套接字，消息指出客户所需要的web对象
  • HTTP服务器接受请求消息，产生一个响应消息，包含被请求对象，并发送这个消息到自身TCP连接套接字
  • HTTP服务器结束TCP连接
  • HTTP 客户接收包含html文件的响应消息, 显示html. 解析html文件，找出10个jpeg对象
  • 对十个引用对象重复上述操作(图中是并行的，串行的话需要一个一个按顺序来)

• 在非持久HTTP连接下，上述只需4RTT

• 由于是非持续的，那么建立一次连接服务器返回消息之后就会断开连接，所以先建立TCP连接，发HTTP请求得到HTML对象，然后解析得到10个图片对象然后重新建立连接发送请求就得到对象了

• 

• 缺点：

  • 每个对象都需要2个RTT
  • OS必须为每个TCP连接分配主机资源
  • 大量客户的并发TCP连接形成服务器的严重负担

持久HTTP连接

• 一个TCP连接上可以传送多个对象，也就是说建立TCP连接之后正常状态下等整个过程结束之后再断开，保证了持续性

• HTTP/1.1默认使用持久HTTP连接

• 例题

• 

不带流水线(可以理解为串行)的持久HTTP连接

• 客户先前响应消息收到,才发出新的请求消息
• 每个引用对象经历1个RTT
• 

带流水线(可以理解为并行)的持久HTTP连接：最优解决方案

• HTTP/1.1默认使用
• 客户遇到1个引用对象就发送请求消息
• 所有引用对象只经历1个RTT
• 

例子：

响应时间模型

• 定义往返时间RTT(Round-Trip Time):
  • 响应时间:
    • 1个RTT用于建立TCP连接
    • 1个RTT用于HTTP请求/响应消息的交互
    • Html文件传输时间
  • total = 2RTT+transmit time
• 

HTTP报文格式

• 请求报文（ASCII文本：易于人读的格式）

• 响应报文

cookie：跟踪用户

cookie文件是存在用户本地的!!!

把无状态的Http协议进行状态化!!!

Cookie和隐私：

• Cookies允许网站更加了解你
• 你可以给网站提供名字和e-mail给网站
• 广告公司通过网站获得信息
• Cookies不适合游动用户

web缓存(代理服务器)

• 目标：在不访问服务器的情况下满足用户的Http请求(代表起始服务器满足HTTP请求)
• 一般有ISP(Internet服务提供商)架设

所有HTTP请求指向缓存

• 对象在缓存中：缓存器返回对象
• 否则缓存器向起始服务器发出请求，接收对象后转发给客户机
• 这么看起来缓存既可以充当服务器给用户返回对象，也可以充当客户端向起始服务器发送请求

为什么需要Web服务器？

• 减少对客户机请求的响应时间
• 减少内部网络与接入链路上的通信量
• 能从整体上大大降低因特网上的Web流量

条件get方法

确认缓存服务器中的对象是否为最新的，使用户拿到最新的数据

web缓存中的文件都有两个附加字段，last-modified最近一次修改时间和expires有效时间

先请求web缓存，如果未过期，则直接返回；如果过期了，则请求原始服务器

web缓存向原始服务器发送请求，包含last-modified，和自己的进行比对，如果相同则返回304 not modified，不附加其他数据，如果已更改，就返回已更改的对象

FTP文件传送协议

概念

主动模式

被动模式

例题

电子邮件

结构：用户代理，邮件服务器，电子邮件使用的协议

过程

用户代理(UA)：

用户和电子邮件系统的接口

用户代理向用户提供一个很友好的接口来发送和接收邮件，用户代理至少应当具有撰写、显示和邮件处理的功能

邮件服务器：

它的功能是发送和接收邮件，同时还要向发信人报告邮件传送的情况（已交付、被拒绝、丢失等）。

邮件服务器采用客户/服务器方式工作，

但它必须能够同时充当客户和服务器邮件发送协议和读取协议∶

邮件发送协议用于用户代理向邮件服务器发送邮件或在邮件服务器之间发送邮件，如SMTP;

邮件读取协议用于用户代理从邮件服务器读取邮件，如POP3

SMTP用的是“推”（Push）的通信方式，POP3用的是“拉”（Pull）的通信方式

电子邮件格式与MIME

多用途网际邮件扩充（MIME）

由于SMTP只能传送一定长度的ASCII码，

许多其他非英语国家的文字（如中文、俄文，甚至带重音符号的法文或德文）就无法传送，

且无法传送可执行文件及其他二进制对象，因此提出了用途网络邮件扩充

SMTP

• Simple Mail Transfer Protocol

• 客户使用 TCP 来可靠传输邮件消息到 服务器端口号25

• 直接传送: 发送服务器到接收服务器

• 传输的3个阶段

  • 连接建立(握手)

    发件人的邮件发送到发送方的邮件服务器的缓存中；

    SMTP客户每隔一段时间就对邮件缓存扫描一次，如果发现有邮件就建立TCP连接

  • 邮件消息的传输

    连接建立后，就可开始传送邮件。邮件的传送从 MAIL 命令开始，MAIL 命令后面有发件人的地址

  • 连接释放(结束)

    邮件发送完毕后，SMTP 客户应发送 QUIT 命令。

    SMTP 服务器返回的信息是 221（服务关闭），表示 SMTP 同意释放TCP 连接

• 命令/应答的交互

  • 命令: ASCII文本格式
  • 应答: 状态码及其短语

• 

  

• SMTP总结

  • SMTP使用持久连接
  • SMTP 要求邮件消息(header & body)必须是7-bit ASCII、

• SMTP与HTTP的比较

  • HTTP：拉协议

  • SMTP：推协议

  • HTTP: 每个对象封装在它各自的HTTP响应消息中发送

  • SMTP: 一个邮件内各个对象置于同一个邮件消息的多目部分发送

  

Mime

SMTP协议只能传送7bit的ASCII码文本数据，不能传可执行文件或者其他二进制对象

SMTP不能传送多媒体文件，以及其他非英语国家的文字

解决不能传送ASCII码数据的问题，一处多用途因特网邮件扩展MIME

MIME还可以用于面向非ASCII码的Http！！！

POP3和IMAP

POP也使用客户/服务器的工作方式，在传输层使用TCP，端口号为110。IMAP4使用143

POP有两种工作方式：

“下载并保留”和”下载并删除”

基于万维网的电子邮件

邮件消息的格式

• SMTP: 用来交换邮件消息的协议

• RFC 822: 文本邮件消息格式标准

• 信头－头部行。如：

  To:

  From:

  Subject:

  这些头部不同于SMTP命令!

  信体

  邮件消息也必须是ASCII字符

  

DNS

关于主机名和域名

概述

域名系统

• 功能

  • 主机名到IP地址的转换
  • 主机别名：一个主机可以有一个规范主机名和多个主机别名
  • 邮件服务器别名
  • 负载分配：DNS实现冗余服务器：一个IP地址集合可以对应于同一个规范主机名

• 特点：

  • 分布式数据库：一个由分层DNS服务器实现的分布式数据库
  • 应用层协议：DNS服务器实现域名转换 (域名/地址转换)

• 为什么不集中式DNS？

  • 单点故障
  • 巨大访问量
  • 远距离集中式数据库
  • 维护
  • 难以扩展

• DNS分类

或者这么划分

根名字服务器

• 根名字服务器负责记录顶级域名服务器的信息

顶级域名服务器

• 负责顶级域名 com, org, net, edu, etc, 和所有国家的顶级域名 uk, fr, ca, jp.

权威DNS服务器

在因特网上具有公共可访问主机（如Web服务器和邮件服务器）的每个组织机构必须提供公共可访问的DNS记录，

这些记录将这些主机的名字映射为IP地址。

组织机构的权威DNS服务器负责保存这些DNS记录。

多数大学和公司维护它们的基本权威DNS服务器

本地DNS服务器

• 严格来说不属于该服务器的层次结构

• 每个ISP（如居民区ISP、公司、大学）都有一个本地DNS也叫默认服务器

  当主机发出DNS请求时，该请求被发往本地DNS服务器。

  起着代理的作用，转发请求到层次结构中。

递归查询

迭代查询

总结

递归查询：我帮你查了，妈的；查不到我让你帮我查，查到了告诉我

迭代查询：我不知道，但是我可以让你去找别人

注意，本地域名服务器查不到直接向跟域名服务器请求，然后才是接下来的操作

本地主机中也有DNS高速缓存，当高速缓存有的时候就不需要进入本地域名服务器了

例题

DNS缓存和权威DNS记录更新

• 一旦名字服务器获得DNS映射, 它将缓存该映射到局部内存
• 服务器在一定时间后将丢弃缓存信息
• 本地DNS服务器可以缓存TLD服务器的IP地址

DNS记录

RR 格式: (name, value, type,ttl)

• Type=A（Address地址）

  • name = 主机名
    value = IP地址

• Type=CNAME（canonical别名）

  • name = 主机别名：www.ibm.com的真名为servereast.backup2.ibm.com
    value = 真实的规范主机名

• Type=NS（ name server ）

  • name = 域名（如foo.com）
    value = 该域权威名字服务器的主机名

• Type=MX（mail exchange）

  • name =邮件服务器的主机别名
    value =邮件服务器的真实规范主机名

DNS协议

• 查询报文与应答报文 , 但具有同样的报文格式

• 报文头部

  • 标识符: 16位，查询和应答报文使用相同的标识符

  • 标志:有若干个标志构成，分别标识不同的功能

    查询/应答－0/ 1

    查询希望是/非递归查询－1/0

    应答可/否获得(支持)递归查询－1/0

    应答是/否来自权威名字服务器－1/ 0

应用层协议小节

第三章 运输层

运输层通信的双方是进程到进程，而网络层是主机到主机

运输层屏蔽了下层网络核心的细节，使应用进程看起来就好像是两个运输层实体之间有一条端到端的逻辑通信通道!!!

运输层使用端口号来区分不同的应用进程！！！

概念

从通信和信息处理的角度看，传输层向它上面的应用层提供通信服务，它属于面向通信部分的最高层，同时也是用户功能中的最低层

传输层位于网络层之上，它为运行在不同主机上的进程之间提供了逻辑通信，而网络层提供主机之间的逻辑通信。

显然，即使网络层协议不可靠（网络层协议使分组丢失、混乱或重复），传输层同样能为应用程序提供可靠的服务

传输层提供应用进程之间的逻辑通信（即端到端的通信）

与网络层的区别是，网络层提供的是主机之间的逻辑通信复用和分用。

在两个不同的主机上运行的应用程序之间提供逻辑通信

• 传输层协议运行在端系统

  • 发送方: 将应用程序报文分成数据段传递给网络层

  • 接受方: 将数据段重新组装成报文传递到应用层

• 两个进程之间的逻辑通信

• 可靠, 增强的网络层服务

端口号

引入端口号的原因：不同操作系统对进程PID的表示不同，为了统一，就是用端口号来在网络中表示应用层的不同进程

多路复用和多路分解

应用层把应用层数据协议单元交给运输层，运输层判断采用udp还是tcp，分别封装为udp对应的用户数据报和tcp对应的tcp报文段，这称作复用，将对应数据交给网络层封装成IP数据报，这称作IP复用，接收方采取相反的策略即可

• 多路复用
  • 多个套接字收集数据，用首部封装数据，然后将报文段传递到网络层
• 多路分解
  • 将接收到的数据段传递到正确的套接字

• 多路分解工作过程
  • 主机收到IP数据报
    • 每个数据报有源IP地址，目的IP地址
    • 每个数据报搬运一个数据段
    • 每个数据段有源和目的端口号
    • 主机用IP地址和端口号指明数据段属于哪个合适的套接字
    • 

应用层的协议对应的运输层协议以及端口号

TCP和UDP的对比

udp无连接，tcp有连接

udp支持单播，多播和广播，而tcp只支持单播(建立连接)

udp面向应用报文，tcp面向字节流

udp仅加上一个udp数据首部；

tcp将应用层协议数据单元视作连续的字节流，以字节为基础进行发送，然后在接受方重新拼接

udp提供无连接不可靠的服务，tcp提供面向连接的可靠服务

udp和tcp的首部不同

UDP

UDP使用应用层协议提供可靠性!!!!!

概述

• 提供尽力而为的服务
• 数据报可能丢失、传递失序的报文到应用程序
• 无连接
• UDP 是面向报文的。发送方 UDP 对应用程序交下来的报文，在添加首部后就向下交付

UDP 存在原因

• 无需建立连接，减少延迟
• 简单，在发送者和接受者之间不需要连接状态
• 很小的数据段首部。首部开销小，只有 8 个字节
• 没有拥塞控制，UDP 能够用尽可能快的速度传递
• UDP 支持一对一、一对多、多对一和多对多的交互通信

首部

• UDP首部格式
• 
• 
  • 首部字段8字节，4个字段，每个字段2字节
  • 长度是首部和数据的总长度
  • 源端口： 源端口号，需要对方回信时选用，不需要时全部置0
  • 长度：UDP的数据报的长度（包括首部和数据）其最小值为8（只有首部）
  • 校验和：检测UDP数据报在传输中是否有错，有错则丢弃。该字段是可选的，当源主机不想计算校验和，则直接令该字段全为0
• 校验和的计算
  • 17是协议代号，表示UDP
  • 伪首部的作用：
    • 伪首部既不向下传送也不向上递交，而只是为了计算校验和
    • 通过伪首部的IP地址检验，UDP可以确认该数据报是不是发送给本机IP地址的
    • 通过伪首部的协议字段检验，UDP可以确认IP有没有把不应该传给UDP而应该传给别的高层的数据报传给了UDP
    • 伪首部的UDP长度=UDP数据包的UDP包长度字段值
    • 识别一个通信应用需要5个因素。”**源IP地址”、”目标IP地址”、”源端口”、”目标端口”、”协议号”**。UDP首部只包含了（源端口和目标端口），用此来校验，如果其他三项信息被破坏，极有可能导致应收包应用收不到，不应该收包的应用收到。为此，有必要在通信中，验证这5项的识别码是否正确，就引入了伪首部的概念。

校验和

伪首部(12个字节)

在计算校验和的时候，UDP数据报之前需要加上 12B 的伪首部，伪首部并不是UDP的真正首部，只是在计算校验和的时候，加在前面构成一个临时的数据报，校验和既不向下传送也不向上递交，只是为了计算校验和

• 校验和例子
  

  • 求和时产生的进位必须回卷到结果上
  • 累加和按位取反得到校验和

  

TCP

MSS

• MSS: TCP 报文段中数据字段的最大长度，而 MSS 通常根据 MTU（最大链路层帧）来设置。

熟知端口号：0-1023；可提供 2^16个 不同端口

TCP 是在不可靠的 IP 层之上实现的可靠的(rdt服务)数据传输协议，它主要解决传输的可靠、有序、无丢失和不重复问题。

特点

• 点到点：

  • 面向连接的运输层协议
  • 一个发送者，一个接收者
  • 可靠按序的字节流

• 可靠：

  • 提供可靠的交付服务
  • 传输的数据无差错，不丢失，不重复且有序

• 面向字节流：

  • 虽然应用程序和 TCP的交互是一次一个数据块（大小不等）
  • 但TCP把应用程序交下来的数据仅视为一连串的无结构的字节流

• 全双工数据：

  • 允许通信双方的应用进程在任何时候都能发送数据
  • 发送和接受双方都设有发送缓存和接收缓存，临时存放双方通信的数据
  • 同一个连接上的双向数据流
  • MSS: 最大报文段长

• 没有信息边界

  • 流水线

• TCP拥塞控制设置窗口大小

  • 收发缓冲区

• 面向连接

  • 在数据交换前握手
  • 初始化发送方和接收方数据

• 流量控制

  • 发送方不会淹没接收方

报文段结构

报文段分为首部和数据两个部分

MSS：TCP允许的最大数据段长度!!!不包含TCP首部!!!

首部(20固定长度+40扩展首部)

序号

32bit，指出本报文段数据载荷的第一个字节的序号

确认号

代表希望收到的下一个数据载荷第一个字节的序号，页是最前面所有数据的确认

在建立连接之后所有的报文段都设置ACK=1，ACK=0的数据无效

数据偏移

4bit，并且以4字节为单位，实际上指出了TCP首部的长度，实际大小取决于扩展首部

保留

占6bit，保留为今后使用，目前设置为0

窗口

指出发送本报文一方的接收窗口

校验和

计算检验和时需要加上12字节的伪首部，和udp一样

SYN同步标志位

FIN终止标志位

RST复位标志位

PSH推送标志位

URG紧急标志位

选项

填充

• 首部格式 20字节

源端口目的端口：2字节

序号Seq：4字节，TCP连接中传送的数据流中的每一个字节都编上一个序号。序号字段的值则指的是本报文段所发送的数据的第一个字节的序号

确认号：期望接收的下一个报文段的数据的第一个字节的序号；如果是N，则表示到序号 N-1 为止，所有数据都正确收到

数据偏移：4比特，以32为为单位，首指出 TCP 报文段的数据起始处距离 TCP 报文段的起始处有多远；因此当此字段的值为 15 时，达到 TCP 首部的最大长度 60B

紧急位 URG：URG=1时，表明紧急指针字段有效。它告诉系统此报文段中有紧急数据，应尽快传送（相当于高优先级的数据）

确认位 ACK：确认。只有当ACK=1时确认号字段才有效。当ACK=0时，确认号无效；TCP规定，在连接建立之后所有传送的报文段都必须把ACK置为1

推送位 PSH：接收方TCP收到PSH=1的报文段，就尽快地交付给接收应用进程，而不再等到整个缓存都填满后再向上交付

同步位 SYN：SYN=1 表示这是一个连接请求或连接接收报文

终止位 FIN：用来释放一个连接。当 FIN = 1时，表明此报文段的发送方的数据已发送完毕，并要求释放传输连接。

RST：当RST=1时表示出现严重差错，必须释放连接重新建立连接

FIN：FIN=1，表明次报文段的发送端数据已发送完毕并要求释放连接

窗口：2字节，让对方设置发送窗口的依据。单位是字节

检验和：2字节，检验首部和数据两个部分。计算检验和时，要在TCP报文段前面加上12字节的伪首部(和UDP相同)

保留字段：6位，全为0

可靠数据传输

基本概念

有线链路误码率较低，一般交给运输层来进行处理；但是无线链路易受干扰，误码率比较高，要求数据链路层必须提供可靠数据传输服务

停等协议SW

确认与否认：

发送方发送一个数据分组之后，必须停止下来等待接收方对于该分组的确认ACK，确认之后才能进行下一个分组的发送，如果发生误码，接收方通过fcs段检测到误码之后就会发送NAK，发送方就重传该分组，所以在收到确认之前，发送方不能删除该分组的缓存

超时重传：

若分组发生丢失，这种情况在数据链路层的传递不太容易发生，但是在不同网络之间，通过路由器连接形成的复杂网络系统下就是经常发生的事情，这个时候需要设置一个超市定时器，如果超时了仍然没有收到确认，那么有可能发生了丢失，立即重传

确认丢失：

确认ACK丢失了，超时进行重传，那么接收方如何判断收到的是相同的分组呢？

给发送数据的分组加上序号，在停等协议中使用01即可，一个bit位，当接收方发现两个数据相同则丢弃；

那么如果确认分组迟到了呢？第四个图

ACK0迟到了，导致超时重传DATA0，接收方收到DATA0之后将其丢弃并且发送ACK，那么这个时候发送方就受到了两个一样的确认分组了，同理带上序号，ACK0第二次收到就被丢弃；在前面收到ACK0的时候发送DATA1，接收方收到并且发送ACK1，这就和前面的不同了，所以可以接着发送下一个数据

由此可见，序号的作用是用来判断该分组和上一个分组是否相同，所以用01就可以了，一个bit位

信道利用率

信道利用率一般比较低，如果超时重传那更低了，所以产生了另外两种协议

回退N帧协议GBN

是一种连续ARQ协议

无差错情况

发送窗口和接收窗口，在回退N帧协议中，接收窗口大小固定为1，发送方看情况

假设这里用3个bit，也就是0-7；发送窗口的大小取值范围为 ，这里取5，取1就是停等协议

发送方在发送的过程中，可以连续将发送窗口内的分组发给接收方，假设正确接收，每接受一个，接收方就返回一个ACK确认分组，并且把接收窗口后移，发送方接收到确认分组之后就把发送窗口后移，并且可以将确认完的分组将缓存中删除了

注意，接受并且后移的时候分组的序号要和窗口当前的序号相匹配

累计确认

接收方可以不用一个一个发送确认，可以用累计确认，比如ACK1表示1及其以前的所有分组被正确接收，也就是0 1

这里假设发送ACK1和ACK4，ACK1丢失了，但是可以通过ACK4得知已经正确接收，所以省掉了重传的步骤

即使发生确认分组丢失，发送方也不一定就必须重传!

并且还可以减少网络资源的占用，减小接收方的开销等等

有差错情况

这里5号分组发生了误码，被接受方丢弃了，剩余的分组与接收窗口不匹配，接收方无法接受，只能将这四个分组丢弃

丢弃之后，每丢弃一个序号不匹配的分组，就发送一个已经接受的ACK，这里就是ACK4，发送方接收到这些确认分组之后，就知道发送出现了问题，根据具体实现来确定收到几个重复确认来重传，总之，要么就是不等计时器重传，要么就是等待计时器结束然后进行重传

数据链路层的ACK和运输层的ack有区别，数据链路层的ACKn标识n及其以前的数据分组被正确接收

GO-Back-N

发送窗口超过上限举例

发送窗口在这里的范围显示是：1< Wt <=7，不能取8，当取8时如下

发送方一次性发送0-7，接收方正确接收并且发送累计确认ACK7，但是确认分组丢失了，于是超时之后重传该分组，重复分组进来之后发现0和0匹配，可以接受，但是这个时候接受的是重复的分组，就出现了问题

接收方无法分辨新旧分组!!!!

总结

选择重传协议SR

选择重传的接收窗口应该大于1，接收方只能按序接受正确到达的数据分组

选择重传应采用逐一确认而不是累计确认!!!

举例：

本例中Wt==Wr==4

发送方发送0-3号分组，接收方接受的时候2号分组丢失了，接收方先接受01，发送确认分组，然后将接收窗口后移；接受3号分组，但是不能将接收窗口后移，因为接收到的是失序分组，然后返回ACK3

发送方接收到01分组确认之后就将发送窗口后移，这时候45在里面，可以发送45号数据分组；与此同时，发送方接收到了3号确认分组，将3号分组的定时器暂停避免超时重传，表示已经收到，但是这个时候不能移动发送窗口，因为发送方收到的是失序的确认分组，需要等待2号分组定时器超时，然后进行重传

超时之后重传2号分组，在这之前也许45号分组已经被正确接受，但是由于失序，不能移动接收窗口，发送方接受到确认之后，由于确认分组失序，不能移动发送窗口，并且需要暂停45计时器，现在就只剩下2号分组的重传了

2号分组被正确接收后终于有序，接受窗口后移；发送方接收到确认分组后终于有序，发送窗口后移；进而可以进行后续的传输

发送，接受窗口尺寸问题

注意这里和回退N帧区别，一个是 2^(n-1)，一个是2^n -1

如果超出界限举例

这个例子最大取4，我们取5

发送方发送0-4，接收方接受并且返回确认分组，但是0号确认丢失，发送窗口不能移动；但是接收窗口移动了，如图所示

一段时间过后重传0号分组，接收方窗口中0存在，可以接受，但是这个0并不是我们想要的0，就导致了无法区分新旧数据分组；

如果大小合适接收窗口中应该没有0，这个时候接收方知道确认分组丢失了，所以重新发送确认分组ACK0，发送方接受，正常运作

总结

Tcp可靠数据传输的实现

比较

是以上上面三种协议为基础实现的，并没有独立使用哪一种

TCP以字节为单位的滑动窗口实现可靠数据传输

补充：

利用率(重要!!!)

注意RTT是往返时延，L/R就是指的是传输速率!!!

例题：

注意这里细节：

序号500开始，再发送500，最后一个字节是999，ACK是期望收到，所以是ACK1000！！！

TCP规定只能对按序到达的最高序号进行确认，所以这个1000实际上是累计确认!!!

可靠传输协议rdt

• FSM：有限状态机
  • 来表示发送方和接收方

rdt1.0 完全可靠信道上的可靠数据传输

rdt2.0 具有bit错误的信道

• 提供了差错检测和接收方反馈(ACK,NAK)

• 

• 当没有错误时：

• 当发生错误时：

• 停-等协议

  • 发送方发送一个报文，然后等待接受方的响应

• Rdt2.0的致命缺陷

  • 如果ACK/NAK混淆了会发生什么？

    • 发送方并不知道接收方发生了什么!

      万能做法：重发

      不能正确重发: 可能重复

• 处理重复:

  发送方给每个分组加一个序号

  在 ACK/NAK 混淆时发送方重发当前分组

  接收方丢弃重复的分组（并不向上传递）

  ——停等协议数据包需要多少序号？

  • ==两个序号 (0,1) 就可以满足==

rdt2.1发送方处理•两个序号 (0,1) 就可以满足混乱的ACK/NAKs

rdt2.1接收方处理混乱的ACK/NAKs

• 

rdt2.2一个NAK不要的协议

rdt3.0 具有出错和丢失的信道

性能

• 算出来的是发送方的利用率

流水线技术 go-back-N

• 流水线: 发送方允许发送多个 “在路上的”, 还没有确认的报文

  • 序号数目的范围必须增加
  • 在发送方/接收方必须有缓冲区

• 增加了利用率

滑动窗口

• 

• 发送方:

  • 在分组头中规定一个k位的序号

  • 窗口：允许的连续未确认的报文

• 接收方：

  • ACK-only: 总是为正确接收的最高序号的分组发送ACK

  • 可能生成重复的ACKs

  • 只需要记住被期待接收的序号expectedseqnum

  • 接收到失序分组:

    丢弃(不缓冲) -> 没有接收缓冲区!

    重发最高序号分组的ACK

选择性重传 Selective Repeat, SR

• 接收方分别确认已经收到的分组

  • 必要时，缓冲报文, 最后按序提交给上层

• 发送者只重发没有收到确认的分组

  • 对每个没有确认的报文发送者都要启动一个定时器(每个未被确认的报文都有一个定时器)

• 发送窗口

  N 个连续序号
    
  **限制被发送的未确认的分组数量**
  

• 

• 

  • 接收方收到窗口第一个ACK之后，向后移动一位
    • 收到非首位的ACK，窗口不移动
  • 接收方收到窗口第一个报文之后，向后移动一位
    • 当失序接收时，窗口不移动，记下已接收的报文序号，当窗口中的序号全部接收时，整体移动

窗口大小和序号大小的关系

• 窗口≤序号空间大小的一半

• 重发场景

快速重传

• 超时触发重传存在问题:超时周期往往太长——重传丢失报文之前要等待很长时间,因此增加了网络的时延

  • 发送方可以在超时之前通过重复的ACK检测丢失报文段

  • 发送方常常一个接一个地发送很多报文段

  • 如果报文段丢失,则发送方将可能接收到很多重复的 ACKs

  • 如果发送方收到一个确认后再收到3个对同样报文段的确认，发送方应意识到不对劲——生成三个重复ACK，是因为接收方存在缺失报文段

    启动快速重传: 在定时器超时之前重发丢失的报文段

流量控制

运输层的流量控制和数据链路层的流量控制的区别是：

传输层定义端到端用户之间的流量控制，

数据链路层定义两个中间的相邻结点的流量控制。

另外，数据链路层的滑动窗口协议的窗口大小不能动态变化，传输层的则可以动态变化

• TCP连接的接收方有一个接收缓冲区

• 发送速率和接收应用程序的提取速率匹配

• 流量控制：发送方不能发送的太多太快，让接收缓冲区溢出

  • 应用程序可能从这个缓冲区读出数据很慢

• 工作机制（假设 TCP 接收方丢弃失序的报文段）

  • 流量控制使用接收窗口:接收缓冲区的剩余空间
  • 接收方在报文段中宣告接收窗口的剩余空间
  • 发送方限制没有确认的数据不超过接收窗口

举例

前面的过程不再赘述

后续打破死锁

发送窗口为0之后启动持续计时器，为什么要引入持续计时器呢？

如果等待接收方通知，如果这个报文丢失了那么两方就陷入了互相等待的死锁状态；

当持续计时器超时，那么发送零窗口探测报文，如果为0返回确认，然后再启动一个持续计时器；

值得一提的是，零窗口探测报文也是具有计时器的，当超时就重发

那么接收窗口满了还能接受报文吗？TCP规定，像零窗口探测报文，确认报文，带有紧急事务的报文是必须被接受的!!!

TCP建立连接：三次握手

第一步，设置SYN=1,给定一个初始序号seq=x，发送给Tcp服务器；

第二步，服务器收到之后发送针对TCP连接请求的确认报文，SYN=1，ACK=1，seq=y，ack=x+1；TCP服务器进入同步已接收状态，TCP客户进入连接已建立状态

TCP规定，SYN=1的请求连接的报文不能携带数据，但是需要消耗一个序号

第三步，客户端发送针对TCP服务器确认的确认，ACK=1，seq=x+1，ack=y+1，这是一个普通的报文段，如果不携带数据不消耗序号，下一个序号从x+1开始!!!这时TCP服务器才进入连接已建立阶段

为什么不用两次握手？(面试常考)

浪费资源，同时

• 用户发送TCP SYN 报文段到服务器

  • 客户机TCP向服务器的TCP发送请求连接的报文段

    这个报文段置同步位SYN为1，同时指定一个初始的序号 seq = x

    TCP规定，SYN不能携带数据，并且要消耗掉一个序号

  • 指定初始的序号

  • 没有数据

• 服务器接收SYN，回复SYN/ACK报文段

  • 如同意建立连接，则向客户机发回确认，并为该TCP连接分配缓存和变量。

    在确认报文段中，把SYN位和ACK位都置1 ， 确认号是 ack=x +1 ，

    同时也为自己选择一个初始序号 scq=y 。 注 意 ， 确认报文段不能携带数据，但也要消耗掉一个序号

  • 服务器分配缓冲区和变量

  • 指定服务器的初始序号

• 客户接收SYN/ACK，回复ACK报文段

  • 当客户机收到确认报文段后，还要向服务器给出确 认，并为该TCP连接分配缓存和变量 。

    确认报文段的ACK位置1，确认号 ack=y+1 ，序号seq=x+1。

    该报文段可以携带数据， 若不携带数据则不消耗序号

  • 可能包含数据

  

TCP释放连接：四次挥手

第一步，TCP客户端向服务器发送终止报文，FIN=1，ACK=1,seq=u,ack=v，seq和ack针对上一次发送和接受的数据进行设置

TCP规定FIN=1的终止报文段即使不携带数据也要消耗一个序号

第二步，TCP服务器向客户端发送普通确认报文，ACK=1，seq=v，ack=u+1，seq和ack由上一条得出

这样TCP客户到服务器单方向的传送就关闭了

第三步，TCP服务器还可能进行一些数据传输，最后发送终止报文，FIN=1,ACK=1，seq=w，ack=u+1,w是根据自己这边数据传输得出的，u+1是因为客户端没有发送报文了，这是对u前面的重复确认

第四步，TCP客户端发送普通的确认报文，ACK=1,seq=u+1,ack=w+1

注意一点：Tcp发送确认报文之后还要经过2MSL才会完全关闭，下面探讨为什么

如果最后一个报文段丢失了那么会导致服务器一直重发这条报文，所以需要设置一段等待时间

保活计时器

TCP服务器为了避免TCP客户端出现问题而无法及时发送报文段，设置了一个保活计时器，每收到一个报文就重置一下该计时器

如果到了规定时间还未收到数据，那么TCP服务器进程会像TCP客户进程发送探测保温段，如果发送了很多(10)个仍无响应，则关闭连接

• **客户关闭套接字: **clientSocket.close()

  Step 1: 客户发送 TCP FIN 控制报文段到服务器

  该报文段的终止位 **FIN 置 1 ， 序 号 seq=u** ，它等于**前面已传送过的数据的最后一个字节的序号加1**，
  
  FIN报文段即使**不携带数据，也消耗掉一个序号**
  

  Step 2: 服务器接收 FIN, 回复 ACK. 进入半关闭连接状态

  **确认号ack=u+1 ， 序 号 seq=w** ， 等于它**前面已传送过的数据的最后一个字节的序号加1**
  
  此时，从客户机到服务器这个方向的连接就释放了
  

  Step 3: 服务器发送FIN到客户，客户接收 FIN, 回复 ACK

  进入 “time wait”状态等待结束时释放连接资源

  Step 4: 服务器接收 ACK. 连接关闭.

  

拥塞控制

拥塞控制是指防止过多的数据注入网络，保证网络中的路由器或链路不至于过载

拥塞控制和流量控制的区别：

拥塞控制是让网络能够承受现有的网络负荷，是一个全局性的过程，涉及所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。强调全局

相反，流量控制往往是指点对点的通信量的控制，是个端到端的问题（接收端控制发送端），它所要做的是抑制发送端发送数据的速率，以便使接收端来得及接收。强调点对点

• 术语

  • MSS：最大报文段
  • rwnd：拥塞控制窗口
  • ssthresh：满开始门限

• 拥塞：

  • 从信息系角度：太多源主机发送太多的数据，速度太快以至于网络来不及处理

  • 与流量控制不同

  • 表现:

    丢失分组 (路由器的缓冲区溢出)

    长延迟 (在路由器的缓冲区排队)

控制方法

• 端到端拥塞控制
  • 没有从网络中得到明确的反馈
  • 从端系统观察到的丢失和延迟推断出拥塞
  • TCP采用的方法
• 网络辅助的拥塞控制
  • 路由器给端系统提供反馈
  • 单bit指示拥塞 (SNA, DECnet, TCP/IP ECN, ATM)
  • 指明发送者应该发送的速率

TCP拥塞控制

• 三个机制
  • 慢启动
  • AIMD
  • 对拥塞事件做出反应

归纳

只要网络没有出现拥塞，拥塞窗口就可以再大一些；只要出现拥塞，就减少一些

判断是否出现网络拥塞：没有及时收到按时到达的确认报文(发生超时重传)

发送方将拥塞窗口作为发送窗口

慢启动

提前设置一个慢开始门限值，这里是16，然后采用指数的形式上涨，每次增加一倍；初值为1

• 连接开始时，CongWin=1MSS
  • 以2的指数方式增加速率
• 

拥塞避免算法

如果慢启动加倍后超过了门限值，那么发送窗口去门限值!!!

超过慢开始门限之后每次增加一倍了，而是固定的增加1

如果过程中丢失了几个报文，导致重传计时器超时，那么判断网络很可能出现了拥塞，那么如下操作：

更新门限值为当前拥塞窗口的一半，设置拥塞窗口为1，重新开始慢启动

每经过一个往返时延 RTT 就把发送方的拥塞窗口cwnd加1，而不是加倍

使拥塞窗口cwnd按线性规律缓慢增长（即加法增大），这比慢开始算法的拥塞窗口增长速率要缓慢得多

慢开始门限ssthresh

• 防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置慢开始门限ssthresh状态变量
• 当cwnd < ssthresh时，使用慢开始算法
• 当cwnd == ssthresh时，可以使用慢开始算法，也可以使用拥塞避免算法
• 当cwnd > ssthresh时，使用拥塞避免算法
• 无论使用哪种算法，只要发送方判断网络出现拥塞，就把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半，把拥塞窗口cwnd设置为1，执行慢开始算法
• 

快速重传和快速恢复

上面的意思简单来说就是：当发送方连续收到三个重复的 ACK 报文时，直接重传对方尚未收到的报文段，而不必等待那个报文段设置的重传计时器超时

快速重传

注意细节(大题考)

确认M2的意思是：我现在确认了M2，我想要的是M3!!!

收到三个重复确认的时候就对相应的报文段立即重传，而不是等待计时器超时，超时了就可能认为网络拥塞，导致网络传输效率减慢

快恢复算法

针对只是个别报文段进行丢失的情况，在收到三个重复确认的时候启动快恢复算法而不是慢启动算法

将慢开始门限和拥塞窗口都调为当前窗口的一半，开始拥塞避免算法；也有的把拥塞窗口调整为新的门限加3

做题时记得加上3!!!

注意(快速恢复阶段受到重复的ACK)

(在三个重复ACK之后)这个时候调成发送窗口为门限值大小!!!!!

总结

• 当 CongWin 低于阀值, 发送方处于慢启动阶段, 窗口指数增长.
• 当 CongWin 高于阀值, 发送方处于拥塞避免阶段, 窗口线性增长.
• 当三个重复的ACK 出现时,阀值置为CongWin/2 并且CongWin 置为阀值加上3个MSS并进入快速恢复阶段，此时每收到一个重复的ACK拥塞窗口增加1MSS，如果收到新的ACK则拥塞窗口置成阀值）.
• 当超时发生时 ，阀值置为CongWin/2 并且CongWin 置为1 MSS.

第四章 网络层

协议总览

可靠传输，面向连接(虚电路)；不可靠传输，无连接(数据报网络)

通过TCP/IP协议栈的网际层来学习网络层的理论知识和技术

概念

• 从发送方主机传输报文段到接收方主机
• 发送方主机封装报文段(segments)为数据报(datagrams)
• 接收方主机递交报文段给传输层
• 在每个主机、路由器上都需要运行网络层协议
• 路由器会检查通过它的所有IP数据报头部字段，然后根据目的的IP地址对数据报进行转发

两个主要的网络层功能

转发**(forwarding)** (数据平面)(硬件实现)

• 将分组从路由器的输入端口转移到正确的路由器输出端口

路由(routing)(控制平面)(软件实现)

• 确定分组从发送方传输到接收方(目的主机)所经过的路径(或路由)
  • 路由算法
  • 
• 路由是端到端的路线。整体路线
• 转发是局部具体怎么走
• 两者的相互作用
• 你要先路由确定路径我才能根据路径进行转发
  • 
  • 路由算法确定通过网络的端到端路径
  • 转发表确定本路由器上的本地转发

数据平面和控制平面

• 数据平面

  • 本地的，每个路由器自身的功能

  • 决定抵达路由器输入端口的数据包如何转发到输出端口，进行路由器内部的数据报文从输入端口到输出端口的转发

• 控制平面

  • 整个网络范围
  • 决定数据报在端到端路径上的路由器之间如何路由
  • 两种控制平面的实现方式
    • 传统的路由算法
    • 软件定义网络 SDN

虚电路和数据报网络

虚电路

这个虚电路的建立是逻辑上的连接，和电路交换物理上的连接是不同的!!!

数据报网络

采用这种设计，把可靠数据传输的实现交给了上层的运输层来实现，而网络层是负责存储转发数据报就ok了

网络的造价大大降低，运行方式灵活，能够适应多种应用

比较

• 数据报网络提供网络层的无连接服务

• 虚电路网络提供网络层的连接服务

• 任何网络中的网络层只提供两种服务之一，不会同时提供

• 传输层：面向连接服务在网络边缘的端系统中实现

• 网络层：面向连接服务在端系统及网络核心的路由器中实现

• 数据报网络特点

数据报转发表

• 采用地址范围建立表项
• 对于给定的目的地址，使用最长地址前缀匹配来完成输出端口的查找
  • 
  • 路由器转发表只维持转发状态信息
  • 转发表由选路算法修改；虚电路网络转发表随虚电路的建立和拆除更新
  • 一个端系统发送给另一个端系统的一批分组可能在网络中选择不同的路径，到达的顺序可能不一致
• 数据报网络的特点
  • 网络层服务模型简单
  • 端系统功能复杂。高层实现许多功能，如按序传送、可靠数据传输、拥塞控制和DNS名字解析等
  • 带来的结果
    • 因特网服务模型提供的服务保证最少（可能没有！），对网络层的需求最小，使得互连使用各种不同链路层技术的网络变得更加容易
    • 许多应用都是在位于网络边缘的主机(服务器)上实现

路由器的工作原理

结构及功能

• 两个核心功能
  • 运行路由算法/协议(OSPF,RIP,BGP)
  • 将分组从路由器的输入端传送到正确的输出链路
• 路由器的体系结构
  • 

输入端功能

• 线路端接模块
  • 将一条物理链路端接到路由器的物理层
• 数据链路处理模块
  • 实现路由器的数据链路层功能
• 查找与转发模块
  • 实现查找与转发功能，以便分组通过路由器交换结构转发到适当的输出端口
  • 确定将一个到达的分组通过交换结构转发给哪个输出端口。通过查找转发表实现，这里的转发表是存储在输入端口的内存中
  • 分布式交换
    • 选路处理器计算转发表，给每个输入端口存放一份转发表拷贝
    • 在每个输入端口本地作出交换决策，无需激活中央选路处理器
    • 可避免在路由器中某个单点产生转发处理瓶颈
    • 目的：以线速完成输入端口的处理
    • 排队：如果数据报到达输入端口的速度快于输入端口将数据报转发到交换结构的速度，就会发生排队
• 

三种交换结构

• 经内存的交换结构

  • 输入端口与输出端口之间的交换由CPU(选路处理器)控制完成

  • 输入端口与输出端口类似I/O设备：

    • 当分组到达输入端口时，通过中断向选路处理器发出信号，将分组拷贝到处理器内存中；

    • 选路处理器根据分组中的目的地址查表找出适当的输出端口，将该分组拷贝到输出端口的缓存中

  • 交换速度受总线带宽的速度限制(每个分组穿过两次总线)

    • 若总线带宽为每秒写入或读出B个分组，则总的转发吞吐量 (分组从输入端口被传送到输出端口的总速率)小于B/2
    • 

• 经总线的交换结构

  • 输入端口通过一条共享总线将分组直接传送到输出端口，不需要CPU选路处理器的干预
    • 每次只能有一个分组通过总线传送
    • 分组到达一个输入端口时，若总线正忙，会被暂时阻塞，在输入端口排队
    • 路由器交换带宽受总线速率控制

• 经交换矩阵的交换结构

  • 纵横式交换机：由2n条总线组成，n 个输入端口与n 个输出端口连接

  • 到达输入端口的分组沿水平总线穿行，直至与所希望的输出端口的垂直总线交叉点

    • 若该条垂直总线空闲，则分组被传送到输出端口
    • 否则，该到达的分组被阻塞，必须在输入端口排队

  • 输出端口：

    • 取出存放在输出端口内存中的分组，并将其传输到输出链路上
    • 当交换结构将分组交付给输出端口的速率超过输出链路速率，就需要排队与缓存管理功能。当输出端口的缓冲区溢出时，就会出现延时和丢包

    

  • 输入端口排队

网络层转发分组的流程

相邻直接传，否则查表传，特定>到达>默认，否则出错

1、从数据报的首部提取目的主机的IP地址D，得出目的网络地址N

2、若网络N与此路由器直接相连，则把数据报直接交付给目的主机 D，这称为路由器的直接交付；否则是间接交付，执行步骤 3

3、若路由表中有目的地址为D的特定主机路由（对特定的目的主机指明一个特定的路由，通常是为了控制或测试网络，或出于安全考虑才采用的），

则把数据报传送给路由表中所指明的下一跳路由器；否则，执行步骤 4。

4、若路由表中有到达网络N的路由，则把数据报传送给路由表指明的下一跳路由器∶ 否则，执行步骤 5

5、路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器;否则， 执行步骤6

6、报告转发分组出错

IP数据报

发送过程

IP数据报发送可以直接发到本网络，也可以通过路由器转发到其他网络，如果发到本网络称作直接交付，发到其他网络称作间接交付；

IP数据报中包含源IP地址和目的IP地址，IP数据报到达路由器的位置，先检查首部看是否出错，如果出错发送ICMP差错报告报文，路由器查路由表，把目的地址和子网掩码相与，如果得到的目的网络不匹配，则查下一项；查到匹配的则根据吓一跳进行转发，如果查不到则丢弃并且给发送方返回信息

注意发送过程中源IP和目的IP地址是不变的，修改的是源MAC地址和目的MAC地址!!!

例题

中继器和集线器工作在物理层，既不隔离冲突域也不隔离广播域

网桥和交换机(多端口网桥)工作在数据链路层，可以隔离冲突域，不能隔离广播域

路由器工作在网络层，既隔离冲突域，也隔离广播域

例题

注意要配置好默认网关

首部

版本

首部长度

区分服务

只有使用区分服务该字段才有作用，一般情况不使用

总长度

表示总长度(首部+数据载荷)

IP数据报是16位，理论上的最大长度是2的16次方-1，65535

首部长度以四字节为单位，总长度以字节为单位!!!

标识，标志，片偏移(用于IP数据报分片)

标识：标识各个分片数据报同一个数据报分片下来的

标志：DF 1表示不允许分片，0表示允许

      **MF 1表示后面还有分片 0表示最后一个分片**

     **保留位 必须置0**

片偏移：指出分片数据包的数据载荷部分在原来的数据报上偏移了多少的位置，以8字节为单位(写的时候注意要除以8)，并且片偏移量必须为整数!!!

IP分片举例

生存时间TTL(与路由环路相关)

举例：防止路由环路

协议(熟悉)

首部检验和(如何计算)

IP只计算首部，tcp,udp需要包含首部和数据

IP地址

例题

注意：

1.首部+数据载荷 对应MTU，记得要加上首部!!!也就是数据链路层的数据部分最大值!!!

2.片偏移量是以8字节为单位，并且一定是整数，所以数据载荷部分记得取8的整数倍数!!!

学校PPT所讲

• 各功能
  • 版本号：4位。表示该IP数据报使用的IP协议版本。目前Internet中使用的主要是TCP/IP协议族中版本号为4的IP协议
  • 首部长度：4位。此域指出整个报头的长度（包括选项）
    • 该长度是以32位二进制数为一个计数单位的
    • 接收端通过此域可以计算出报头在何处结束及从何处开始读数据
    • 普通IP数据报（没有任何选项）该字段的值是5（即20个字节的长度）
  • 服务类型（TOS、type of service）：8位。服务类型字段的8位分成了5个子域
  • 长度：16位。总长度字段是指整个IP数据报的长度（报头区+数据区），以字节位单位
    • 利用头部长度字段和总长度字段就可以计算出IP数据报中数据内容的起始位置和长度
  • 生存时间(寿命 TTL，time to live)：占用8位二进制位
    • 指定了数据报可以在网络中传输的最长时间
    • TTL的初始值由源主机设置（通常为32、64、128或256），一旦经过一个处理它的路由器，它的值就减1。当该字段为0时，数据报就丢弃，并发送ICMP报文通知源主机，因此可以防止进入一个循环回路时，数据报无休止地传输下去
  • 高层：占用8位二进制位
    • IP协议可以承载各种上层协议，目标端根据协议标识就可以把收到的IP数据报送到TCP或UDP等处理此报文的上层协议了
  • 首部检查和
    • 占用16位二进制数
      • 用于协议头数据有效性的校验
      • 保证IP报头区在传输时的正确性和完整性。头部检验和字段是根据IP协议头计算出的检验和，它不对头部后面的数据进行计算
      • 原理：发送端首先将检验和字段置0，然后对头部中每16位二进制数进行反码求和的运算，并将结果存在校验和字段中。 由于接收方在计算过程中包含了发送方放在头部的校验和，因此，如果头部在传输过程中没有发生任何差错，那么接收方计算的结果应该是全1。
  • 源IP地址：占用32位二进制数，表示发送端IP地址
  • 目的地址：占用32位二进制数，表述目的端IP地址

分片和重组

• 分片：
  • 把一个数据报为了适合网络传输而分成多个数据报的过程称为分片，被分片后的各个IP数据报可能经过不同的路径到达目标主机
  • 一个IP数据报在传输过程中可能被分片，也可能不被分片。如果被分片，分片后的IP数据报和原来没有分片的IP数据报结构是相同的，即也是由IP头部和IP数据区两个部分组成
  • 分片后的IP数据报，数据区是原IP数据报数据区的一个连续部分，头部是原IP数据报头部的复制，但与原来未分片的IP数据报头部有两点主要不同：**标志和片偏移 **
    • 标志：在IP数据报头部有一个叫标志的字段，用3位二进制数表示
  • —片偏移：IP数据报被分片后，各片数据区在原来IP数据区中的位置用13位片偏移来表示。上图中分片1的偏移为0；分片2的偏移为600；分片3的偏移为1200实际在IP地址中,由于偏移是以8个字节为单位进行计算的,因而在IP数据报中分片1的偏移是0；分片2的偏移是75；分片3的偏移是150
• 重组
  • 当分了片的IP数据报到达最终目标主机时，目标主机对各分片进行组装，恢复成源主机发送时的IP数据报，这个过程叫做IP数据报的重组。
  • IP数据报头部中，标识用16位二进制数表示，它唯一地标识主机发送的每一份数据报
    • 在一个数据报被分片时，每个分片仅把数据报“标识”字段的值原样复制一份，所以一个数据报的所有分片具有相同的标识
  • 目标端主机重组数据报的原理:
    • 根据“标识”字段可以确定收到的分片属于原来哪个IP数据报
    • 根据“标志”字段的“片未完MF”子字段可以确定分片是不是最后一个分片
    • 根据“偏移量”字段可以确定分片在原数据报中的位置

ip地址

概述

IPV4地址就是给因特网上的每一台主机或者路由器的每一个接口分配一个全世界范围内唯一的32位bit的标识符

分类编制的IPV4

D类多播地址

A类

B类

C类

特殊IP地址

• IPV4编址

  • 

  • 

    • 分为主机号和网络号

  • 传统的IP地址分类

    • A类地址：第一个字节作为网络地址，最高位为0，其余的三个字节作为主机地址。

    • B类地址：l两个字节作为网络地址，最高位为10，其余的两个字节作为主机地址

    • C类地址：利用IP地址的前三个字节作为网络地址，最高位为110，最后一个字节作为主机地址

    • 特殊IP地址段

      

    • 同一局域网上的主机或路由器的IP地址中的网络号必须相同

    • 交换机互连的网络仍然是一个局域网，只能有一个网络号

    • 路由器总是具有两个或两个以上IP地址

    • 当两个路由器直接相连时，在连线两端的接口处，可以指明IP地址也可以不指明IP地址

划分子网的IPV4

为什么要划分子网呢？

如果不划分子网，那么对于新的主机网络，就需要构建新的网络，申请新的网络号，如下弊端：

用子网掩码可以表示借用了多少位主机号来充当子网号

例题

子网号能否为全0或者全1

在 ABC类 划分子网时，子网号不能为全0或全1
在 CIDR 划分子网时，子网号可以为全0或全1

默认子网掩码

主机号不管划不划分，讲子网号和主机号全取0

无分类编制的IPV4(CIDR)

表示方法

举例

聚合C类网的数量是指这个地址块相当于多少个C类网络的数量

C类网络主机号8位，因此12-8，留出4位当子网号，就是2的4次方

路由聚合(构造超网)

减少路由表的占用，对R1的5条路由信息合成一条！

寻找共同的前缀，作为新的IP地址的网络前缀，然后主机号取0就得到了这个目的网络号

值得主要注意的是，如果出现了多个匹配项，选择网络前缀最长的那个，称为最长前缀匹配。这样的路由更加具体

例题

IP地址的应用规划

定长的子网掩码

注意看题目给出的是主机还是总的IP地址需求个数，记得根据情况是否加上网络地址，广播地址和路由器接口地址!!!!

注意，这些合计的IP地址数都是主机号决定的，而对于分类编址的IPV4的子网号不能取同0和同1，这个和这些没关系

注意，分类编址子网号不能全0和全1，CIDR是可以全0和全1的

变长的子网掩码(CIDR重点)

注意分配原则：每个子块的起点位置不能随意选取，只能选取块大小整数倍的地址作为起点，建议从大的子块开始分配!!!

注意这里的子网所需地址数量普通情况下是大于主机数量+网络地址+广播地址+路由器接口地址，但是我们划分子网主机号位数得出的子网地址数是2的n次方倍，这样虽然划分的子网中有地址浪费，但是大大减小了；并且也能选取块大小整数倍的地址为起点

子网划分老师所讲

划分子网

• 划分子网的方法是从主机号借用若干个比特作为子网号，剩下的主机位为主机号
• 子网特点：
  • 设备接口的IP地址具有同样的网络部分
  • 没有路由器的介入，物理上能够相互到达
• 子网掩码
  • l子网号字段长度是可变的，因此，为了确定子网地址，IP协议提供了子网掩码的概念 。
  • l子网掩码用来确定网络地址（包括网络号和子网号）和主机地址的长度。子网掩码长为32位比特，其中的1对应于IP地址中的网络号和子网号，而子网掩码中的0对应于主机号。

子网划分技术

• 主机号全0的地址不能用，它被用做表示该子网的子网号；主机号全1的也不能用，它用于本子网的广播。因此每个子网所能容纳的主机数是2^N-2，N是主机号位数

无分类域间路由CIDR

• Classless Inter-Domain Routing，CIDR

• lCIDR消除了传统的A类、B类和C类地址的概念。

• 使用斜线记法，又称为CIDR记法来区分网络前缀和主机号，即在IP地址后面加上一个斜线“/”，斜线后面用一个数字指定网络前缀的长度。

• 构造超网

• 

• 层次寻址，路由聚合

• 练习：

  （1）

  以最多台数的部门（60台）为准，需要的最接近数为2^6=64，故要从最后个字节借8-6=2位，

  子网分别为 202.1.1.0, 202.1.1.64, 202.1.1.128, 202.1.1.192，在这4个其中任选3个即可。掩码均为255.255.255.192。

  （2）

  若以最多台数的部门（120台）为准，仅能分两个子网，无法满足。故应采用CIDR法：

  首先以最小需求台数部门为准（60台），此时主机号位数需要6位（因为60=<2^6-2），则子网号位数为8-6=2位，然后将子网划分出来。此时和（1）一样；

  接下来，部门2、3可以直接在4个子网中任选两个，部门1选剩下2个以满足120台的要求（但这两个子网要连续，以便用CIDR法合并之，做超网）。比如202.1.1.128、202.1.1.192分别给部门2、3，部门1用202.1.1.0、202.1.1.64。

  （3）最后将各部门IP段用CIDR超网形式描述，以便对外发布：

  部门1：202.1.1.0/25; (注意含义：表示前25位是网络号，且最后一个字节最高位为0，后面7位是主机号)

  部门2：202.1.1.128/26; (最后一个字节最高两位为10，后面6位是主机号)

  部门3：202.1.1.192/26; (最后一个字节最高两位为11，后面6位是主机号)

  说明：将202.1.1.128、202.1.1.192给部门1，202.1.1.0、202.1.1.64分别给部门2、3亦可。此时答案为：

  部门1：202.1.1.0/26;

  部门2：202.1.1.64/26;

  部门3：202.1.1.128/25

静态路由配置

静态路由是指网络管理员使用命令给路由器配置路由表

简单，开销小，但是不能适应网络拓扑的变化，一般只在小规模网络中使用

静态路由配置：人为配置好

默认路由：0.0.0.0(或者0.0.0.0/0)，在其他的路由查不到的时候，就是默认走这里；网络前缀最短，路由最模糊

特定主机路由：给网络中的某个主机特定配置的一个路由，网络前缀最长，路由最具体

当有多个路由可选的时候，找最长前缀匹配的!!!

路由环路

静态路由配置错误导致路由环路

配置错误后，R2吓一跳给R3，R3查表又给R2，死循环

IP首部设有生存时间TTL的字段，进入路由器后-1，若不为0则转发，否则丢弃，这样就很好的缓解了路由环路问题

聚合路由中有不存在的网络导致路由环路

为了节省空间，R2的路由表将R1 0和2 接口连接的网络聚合成了一个聚合路由存在了R2的路由表中，R2发出目的网络地址192.168.2.0/24，查R2的路由表发现192.168.0.0/22前缀匹配，则转发到R1，R1则正确接受并且转发给目的网络；

好，但是实际上24位的网络前缀在22位的基础上可以衍生出4个网络，其中两个网络是图中的网络拓扑没有的，所以就容易出现下列问题

发送192.168.3.0/24，按照前缀匹配会发给R1，然后R1找不到，就会找默认路由，然后又回到R2了,形成环路

解决方法：针对这两个不存在的路由存储黑洞路由，下一跳设置为NULL

网络故障导致路由环路

最开始正常，然后出故障，R2不知道，仍发送到R1，然后这个时候出故障之后从路由表中删除这个信息，然后就找到了默认路由，导致环路

解决：在消除之后设置黑洞路由，网络恢复之后将路由表恢复或者禁用黑洞路由

动态主机配置协议DHCP(应用层协议)

DHCP发现(客户发)

源IP：0.0.0.0，目的：255.255.255.255，因为不知道服务器地址所以广播

帧当中带有事务ID和客户的MAC地址

DHCP提供(服务器发)

服务器收到后发送DHCP提供报文，源IP：自己服务器IP，目的IP：广播

帧当中带有事务ID，用来标识这个是刚才客户发送的DHCP报文的回复

还带有IP的配置信息，包括IP地址，子网源码，地址租期，默认网关，DNS服务器等等

注意使用该IP的时候需要用ARP协议保证该IP地址未被其他主机使用

DHCP请求(客户发)

客户收到DHCP提供报文后，选择一个服务器的报文，想用它为自己提供的IP，发送DHCP请求报文，目的地址仍为0.0.0.0，因为还未正式使用这个IP地址，目的地址为广播，这样就不用单独给每一个DHCP服务器发送我是否同意用你的IP地址了

帧当中包含事务ID，DHCP客户的MAC，DHCP给分配的IP地址和DHCP服务器的IP地址

DHCP确认(服务器发)

这时候服务器1收到请求，如果同意则返回确认报文

注意客户收到后，IP地址仍需要用ARP协议检测是否被占用，如果在这个过程中有人捷足先登占用了，那么发送DHCP取消报文取消租约，并重新来过

关于租用期和补充

关于DHCP中继代理

我们不愿意给每个网络都设置一个DHCP服务器，这样会导致DHCP服务器太多了

所以例如DHCP的发现报文，由于目的地址为全1，为广播地址，这样的地址一般情况下是不会被路由器转发的，但是就是要通过路由器转发才能被DHCP服务器接受

那么只需要在路由器中配置DHCP服务器的IP地址就好了，这个路由器也就成为了DHCP中继代理

这个时候广播到达路由器的DHCP发现报文就会被路由器存储并且单播转发给DHCP服务器了

老师PPT所讲

用于给主机动态的分配IP地址，它提供了即插即用的联网机制，这种机制允许一台计算机加入新的网络和获取IP 地址，而不用手工参与

DHCP是应用层协议，是基于UDP的

• DHCP: Dynamic Host Configuration Protocol

  • 自动从一个DHCP服务器得到IP地址

• 工作过程

  • 1：DHCP 服务器被动打开 UDP 端口 67，等待客户端发来的报文

  • 2：DHCP 客户从 UDP 端口 68发送 DHCP 发现报文，以便从DHCP服务器获得一个IP地址

  • 3：凡收到 DHCP 发现报文的 DHCP 服务器

    **都发出 DHCP 提供报文**，因此 DHCP 客户
        
    可能**收到多个 DHCP 提供报文**。
    

  • 4：DHCP 客户从几个 DHCP 服务器中选择

    **其中的一个，并向所选择的 DHCP 服务**
        
    **器发送 DHCP 请求报文**。
    

  • 5：被选择的 DHCP 服务器发送确认报文

    DHCPACK，客户进入已绑定状态，并可
          
    开始使用得到的**临时 IP 地址**了。
    

  DHCP 客户现在要根据服务器提供的租用期 T 设置两个计时器 T1 和 T2，它们的超时时间分别是 0.5T 和 0.875T。当超时时间到就要请求更新租用期。

  • 6：租用期过了一半（T1 时间到），DHCP客户 发送

    **请求报文 DHCPREQUEST** 要求**更新租用期**。
    

  • 7： DHCP 服务器若不同意，则发回否认报文DHCPNACK。这时 DHCP 客户必须立即停止使用原来的 IP 地址，而必须重新申请 IP 地址（回到步骤2）

  • 8： DHCP 服务器若同意，则发回确认报文DHCPACK。DHCP 客户得到了新的租用期，重新设置计时器。

  • 若DHCP服务器不响应步骤6的请求报文DHCPREQUEST，则在租用期过了 87.5% 时，DHCP 客户必须重新发送请求报文 DHCPREQUEST（重复步骤6），然后又继续后面的步骤。

• 服务场景

• DHCP分配的不仅仅是IP地址，还可以分配

  • 客户的第一跳路由器的地址(网关)
  • DNS服务器的IP地址或域名
  • 子网掩码

• DHCP是应用层协议，基于UDP

NAT网络地址转换

私有IP地址

本地网络只能用于局域网内部通信而不能被路由器进行转发，进入到公网当中

NAT过程

存在的问题：一个内网地址对应一个路由器上接口的外网地址，那么如果外网地址的数量不够的话会出问题

NAPT

把多个公网IP的问题用运输层的端口号来解决了，公网IP地址是相同的，但是端口号不同，所代表的进程服务就不同

补充

使用NAT不能让外网主机优先向内网主机发送请求，因为这会导致在NAT表里面找不到记录而失败

NAT对外网屏蔽了内网的IP地址

• 使本地网络分组离开时具有同样的IP地址

• 执行NAT时路由器要求：

  • 外出的分组: 替换每个外出的分组的 (源IP 地址, 端口号) 为 (NAT IP 地址, 新端口号)
  • 远程客户/服务器用**(NAT IP地址, 新端口号)**作为目的地来响应。
  • (在NAT转换表中)记录每个(源IP 地址, 端口号)到 (NAT IP地址, 新端口号) 转换配对
  • 进来的分组: 对每个进来的分组，用保存在NAT表中的对应的(源IP 地址, 端口号) 替换分组中的目的域 (NAT IP 地址, 新端口号）

• 地址转换过程

因特网控制报文协议ICMP

分为两种：ICMP差错报文和ICMP询问报文

ICMP差错报文

分为五种

终点不可达

源点抑制

因为拥塞而丢弃

时间超过

当在规定时间内无法收取全部的数据报的时候也会发送ICMP差错报文(时间超过)来提醒发送方重发剩余的分片

参数问题

检测到误码

改变路由(重定向)

H1默认网关是R1，但是H1发送给N2的报文最佳路径是经过R4，R1收到这个报文后发现不是最佳路径，于是发送ICMP差错报告(改变路由)，H1添加路由项，发送报文给N2不经过默认网关R1而是R4

不应发送差错报文的情况

ICMP询问报文

回送请求和回答

时间戳请求和回答

应用

分组网间探测PING

跟踪路由

学校PPT所讲

ICMP 差错报告报文：向源主机报告差错：包括终点不可达、拥塞丢弃、时间超过

用于目标主机或到目标主机路径上的路由器向源主机报告差错和异常情况

• 终点不可达。当路由器或主机不能交付数据报时，就向源点发送终点不可达报文
• 源点抑制。当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文
• 时间超过。当路由器收到生存时间为零的数据报时，除丢弃该数据报外还要向源点发送时间超过报文

不应发送 ICMP差错报告报文的几种情况如下

• 对ICMP差错报告报文不再发送 ICMP 差错报告报文
• 第一个分片的数据报片的所有后续数据报片都不发送ICMP 差错报告报文
• 对具有组播地址的数据报都不发送 ICMP 差错报告报文

• Internet Control Message Protocol
• 用于主机路由器之间彼此交流网络层信息
  • 差错报告: 不可到达的主机, 网络,端口,协议
  • 请求/应答
• 位于IP之上
  • 因为ICMP消息是装载在IP分组里的

IPV6

更大的IP地址空间，从32位升到了128位

支持即插即用(自动配置IP地址)

IPv6 首部长度必须是 8B的整数倍，而IPv4 首部是 4B 的整数倍，tcp首部也是4B的整数倍!!!

从根本上解决了IP 地址的耗尽问题

• IPv6 数据报格式
  • 固定长度的 40 字节首部
  • 不允许分片：IPv6 只有在包的源结点才能分片，是端到端的，传输路径中的路由器不能分片

IPV6地址表示

• 冒号十六进制表示法
  • 

==选路算法==

• 路由算法确定了通过网络的端到端路径

• 转发表确定了在路由器上的本地转发

• 默认路由器：

  • 与主机直接相连的路由器，又叫第一跳路由器
  • 每当主机发送一个分组时，都先传送给它的默认路由器
    • 源路由器：源主机的默认路由器
    • 目的路由器：目的主机的默认路由器
    • 从源主机到目的主机的选路归结为从源路由器到目的路由器的选路
  • 路由算法：是确定一个分组从源路由器到目的路由器所经路径的算法
  • 

网络的抽象图模型：费用(cost)

路由算法分类：

全局路由算法

• 所有路由器拥有完整的网络拓扑信息和链路费用信息。

  链路状态路由算法LS：必须知道网络中每条链路的费用

分布式路由算法

• 以迭代的、分布式的方式计算最低费用路径
  • 节点只有与其直接相连链路的费用信息：不需拥有所有网络链路费用的完整信息
  • 通过迭代计算，并与相邻节点(邻居节点)交换信息
  • 逐步计算出到达某目的节点或一组目的节点的最低费用路径
• 距离向量路由算法DV：每个节点维护到网络中所有其他节点的费用（距离）的估计向量

静态路由算法

• 路由确定后基本不再变化。只有人工干预调整时，可能有一些变化

动态路由算法

• 网络的流量负载或拓扑发生变化时，路径可能发生改变
• 可以周期性地或直接地响应拓扑或链路费用的变化
• 易受选路循环、路由振荡之类问题的影响

链路状态路由算法LS

Dijkstra最低费用路径算法

所有节点都知道网络拓扑，以及每条线路的信息

• 通过链路状态广播来实现

• 所有节点拥有相同的信息

• 计算任意一个节点（源节点）到所有其他节点的最低费用路径

• 给出该节点的转发表

• 迭代：通过k次迭代后可以知道到达k个目的节点的最低费用路径

• 基本思想：

  • 以源节点为起点，每次找出一个到源节点的费用最低的节点，直到把所有的目的节点都找到为止

• 算法描述：

  • 1、初始化
  • 2、找出一个到源节点的费用最低的节点w，并以此更新其它点D(v) 值
  • 3、重复步骤2
    • 直到所有的网络结点都在N’中为止

例题

eg：

• 计算从u到所有可能目的节点的最低费用路径。

• 计算过程如表，表中的每一行表示一次迭代结束时的算法变量值。

• ==构建从源节点到所有目的节点的路径==

  • 对于每个节点，都得到从源节点沿着它的最低费用路径的前驱节点
  • 每个前驱节点，又可得到它的前驱节点；以此继续，可以得到到所有目的节点的完整路径

• ==构建最低费用路径树==

  • 根据目的节点找出顺序和其费用以及前驱节点，可以画出源节点u到所有目的节点的最低费用路径树
  • 根据得到的所有目的节点的完整路径，或最低费用路径树，可以生成源节点的转发表
  • 转发表
    • 存放从源节点到每个目的节点的最低费用路径上的下一跳节点
    • 即指出对于发往某个目的节点的分组，从该节点发出后的下一个节点

转发表

• 构建转发表

dijkstra复杂度

距离向量路由算法DV

• 距离向量路由算法是一种迭代的、异步的和分布式的算法
  • 分布式：每个节点都从其直接相连邻居接收信息，进行计算，再将计算结果分发给邻居
  • 迭代：计算过程一直持续到邻居之间无更多信息交换为止
  • 异步：不要求所有节点相互之间步伐一致地操作
  • 自我终结：算法能自行停止

最低费用表示

• dx(y)：节点x到节点y的最低费用路径的费用

• v: 节点x的邻居节点

• c(x,v)+ dv(y)：x与某个邻居v之间的直接链路费用c(x,v)加上邻居v到y的最小费用。即x经v到节点y的最小的路径费用

• minv ：从所有经直接相连邻居节点到节点y的费用中选取的最小路径费用

• B-F方程举例

• 对每个结点x

  • 初始化
  • 更新自己的距离向量
  • 重复执行（2），直到没有更新的距离向量发出
  • 

距离向量表

• 行：该节点的距离向量Dx和其邻居的距离向量Dv

• 列：所有目的节点

• 节点x的距离向量Dx ，即节点x到每个目的节点y的估计费用； Dx = [Dx(y)：y在N中]

• 节点x每个邻居的距离向量Dv ，即x的邻居v到每个目的节点y的估计费用，Dv = [Dv(y)：y在N中]

• 

• 更新其距离向量

  • 

    

链路费用改变与链路故障

• 当一个节点检测到从它到邻居的链路费用发生变化时，就更新其距离向量，如果最低费用路径的费用发生变化，通知其邻居

• 某链路费用减少时情况

  • 
  • 
  • 好消息在链路中能迅速传播

• 某链路费用增加时情况

  • 

  • 

  • 

  • 链路费用增加的“坏消息”传播很慢

  • 

  • 不知道坏消息已经影响他了，局部形成环路

LS算法与DV算法的比较

• LS算法：

  • 知道网络每条链路的费用，需发送O(nE)个报文；当一条链路的费用变化时，必须通知所有节点
  • 需要O(nE)个报文和O(n2)的搜寻，可能会振荡

• DV算法：

  • 迭代时，仅在两个直接相连邻居之间交换报文
  • 当链路费用改变时，只有该链路相连的节点的最低费用路径发生改变时，才传播已改变的链路费用
  • 收敛较慢。可能会遇到选路回环，或计数到无穷的问题。

• 健壮性

  • LS：
    • 路由器向其连接的一条链路广播不正确费用，路由计算基本独立（仅计算自己的转发表），有一定健壮性
  • DV：
    • 个节点可向任意或所有目的节点发布其不正确的最低费用路径，一个节点的计算值会传递给它的邻居，并间接地传递给邻居的邻居。一个不正确的计算值会扩散到整个网络
    • 无健壮性

分层次的路由选择协议

域内路由协议IGP

• 域（自治系统）内路由选择
• 内部网关协议 IGP ：AS(自治系统)内使用的
  • RIP，OSPF
• 外部网关协议EGP：AS之间使用的
  • BGP

路由信息协议RIP(自治系统内部)

• 基于距离向量的路由选择协议

• 距离：定义为路径中经过的路由器个数

  • 通常为跳数，即从源端口到目的端口所经过的路由器个数，经过一个路由器跳数+1
  • 特别的，从一路由器到直接的网络距离为1

• RIP允许路由最多包含15个路由器

  • 距离16表示不可达，而且就是用16来表示距离不可达到!!!!
  • RIP适用于小的互联网

  等价负载平衡

  

三个要点

• 和谁交换信息 和相邻的路由器
• 交换什么信息 自己的路由表
• 何时交换 周期性的交换

交换信息(路由表更新问题)

注意这里有的资料认为距离相等但是下一跳不相等的时候不进行路由表更新，也就是图中的 N8 4 C 没有，这个看情况来定

• 仅和相邻的路由器交换信息
• 路由器交换的信息是自己的路由表
• 
• eg
  • 修改发来的路由更新信息，距离+1，下一跳路由器改为发送来的路由器
  • 更新距离
• eg2：

RIP存在“坏消息传的慢”的问题

假如某一时刻R1收到N1故障，将自己的路由表修改为 N1 16 直连，然后到达周期时刻准备发给R2，然后R2这时候不知道，也发送给R1，但是R2的消息先到了，这个时候R1的消息尚未发出，收到R2的更新报文之后修改自己的路由表然后发出，这时候变为了 N1 3 R2，传过去R2变成了 N1 4 R1，以此类推，知道都更新为16的时候才知道不可到达，那么这个中间的过程就浪费了很长的时间，长达数分钟，形成了路由环路

这些措施并不能彻底解决这个问题，根本上是距离向量算法决定的

开放最短路径优先OSPF(自治系统内部)

OSPF 信息直接通过 IP 传输 （不是 TCP 或 UDP），因此必须自己实现可靠报文传输、链路状态广播等功能。

为了克服RIP协议的缺点开发出来的，开放表示不是受某一家厂商控制而是公开发表的

OSPF基于链路状态，RIP基于距离向量

• 使用了dijkstra最短路径算法
• 

交换信息

OSPF相邻路由器之间通过Hello分组来建立和维护邻居关系

每个路由器都有链路状态公告LSA

每个路由器都有一个链路状态数据库LSDB，用来存储每个数据库的LSA

工作过程

五种分组类型

工作过程

建立关系(指定路由器)

由于当链路状态更新的时候路由器需要通过广播的形式向系统中其他的路由器发送链路状态请求分组，所以在网络中就会存在大量的广播分组的传递，为了减少这个问题，引入了指定路由器DR和备用指定路由器BDR，规定其他的路由器只能和他们交换信息，减少了路由器之间相连的个数，但是增加了这两个路由器的负担

关于区域

将自治系统AS划分为若干个区域，为了减少区域内部的通信量，使得能用于大规模的网络系统

• 通过洪泛法(广播)向自制系统内所有的路由器发送信息
  • 广播
• 交换本路由器相邻的所有路由器的链路状态
• 当链路状态发生变化时交换信息

边界网关协议BGP(自治系统之间)

不同的自治系统之间所使用的代价度量可能不相同，这使得在自治系统之间没有一个相对统一的标准

自治系统之间的路由选择必须考虑相关的策略，例如：政治，经济，安全等等(比如有的自治系统不让我们的TCP报文通过)

BGP协议为了找到一条尽可能快的路径(避免兜圈圈)，而不是找到最佳路径

工作原理

BGP发言人之间通信需要建立TCP连接，端口号为179

• 从相邻AS获取子网可达信息
• 向该AS内部的所有路由器传播这些可达性信息
• 域间寻路任务：
• 基于距离矢量算法

三个封装关系

第五章 链路层

关于可靠数据传输

地位

链路加上通信协议就称为数据链路

三个重要问题(点对点传输)

封装成帧；差错检测；可靠传输

封装成帧

应用层封装好应用层协议数据单元，然后交付给运输层添加运输层协议首部，然后交给网络层添加网络层协议首部，然后交给数据链路层添加帧头帧尾，最后交给物理层把这一段帧视作比特流进行传输，到达接收方后进行一层一层的解包得到数据

差错检测

需要有一定的措施来判断传输过程的数据是否发生错误

可靠传输

尽管可能发生差错，但发送方发送什么，接收方都能相应的接受到什么，这个就叫做可靠传输

其他的

概述

• 主要术语

  • 链路层的节点包括了主机和路由器；

  • 我们将沿通信路径，将相邻节点连接起来的通信信道称为链路，这里的链路可以将主机与路由器，或者路由器与路由器连接起来。

  • 为了将一个数据报从源主机传输到目的主机，数据报必须通过沿端到端路径上的各段链路传输。

  • 链路主要包括：有线链路和无线链路。在实际链路上传输时，传输节点需要将数据报封装成数据帧进行传输。

  • 数据链路层的职责是将数据报从一个节点传送到与该节点直接有物理链路相连的另一个节点。

• 类比

• 链路层提供的服务

  • 封装成帧，链路接入
    • 封装数据报为数据帧，增加头部尾部信息
    • 若是共享链路，接入链路
    • 在数据帧头部中，用MAC地址来表示源目的MAC地址
      • 不同于IP地址
  • 在相邻节点之间可靠传输数据帧
  • 流量控制**(flow control):**
    • 用于控制发送节点向直接相连的接收节点发送数据帧的频率
  • 差错检测**(error detection):**
    • 差错可能由信号衰减、噪声引入
    • 接收方检测是否出现错误
      • 通知发送方重传或丢弃数据帧
  • 错误纠正**(error correction):**
    • 接收方标识和纠正比特错误，而不需要请求重传
  • 半双工和全双工(half-duplex and full-duplex):
    • •在半双工模式，链路的两个节点都可以发送数据，但是不能同时发送

• 链路层实现的位置

  • 在主机和网络设备(路由器)上实现
  • 在主机上，链路层的主体部分是在网络适配器上实现的(称为网卡)

封装成帧

添加帧头和帧尾使之成为帧；包含重要的控制信息；帧头帧尾重要的作用之一就是帧定界

透明传输

透明传输是指数据链路层对上层交付的数据没有任何限制，就好像数据链路层不存在一样

理解下来就是说：我的帧头帧尾里面的定界符是一串01，在数据当中很可能也存在一样的01，那么不加处理的话就会导致接收方把数据里面的01认为是定界符而导致数据出错。怎么解决呢？

面向字节的物理链路，可以在数据当中的flag前面加上一个转义字符，表示这是数据不是定界符，接受方接收到之后把转义字符剔除就好了

如果数据中也包含转义字符形式的数据那么在前面也加上转义字符，接收方接受并且剔除就好了

那么面向比特的物理链路呢？

帧定界码：01111110

在数据当中的没五个连续的1后面加一个0，接收方接受识别并剔除就好了

补充

帧数据部分尽可能大，提高利用率

最大传送单元MTU

差错检测和纠错

• 发送节点

• 接收节点

• 差错检测和纠正技术不能保证接收方检测到所有的比特差错，即可能出现未检测到的比特差错，而接收方并未发现

  • 选择一个合适的差错检测方案使未检测到的情况发生的概率很小即可。

    差错检测和纠错技术越好，越复杂，开销更大

奇偶校验

奇校验添加1保证1个数为奇数，如果1数量变为偶数就发生差错，但是如果1的奇性不变那么就无法检测出来，例如发生两位的误码

• 

• 二维奇偶校验

  

  第一行有3个1，因此第一行的校验位为1，

  第二行有4个1，因此第二行的校验位为0，

  第三行有3个1，因此第三行的校验位为1，

  最终得到得到左边这个图。

  假设在传输过程中，有一个比特错误，例如第二行第二列的1发生了翻转，变为了0，

  在接收方进行检验时，会发现第二行的校验位不对，以及第二列的校验位不对，这样一交叉就会发现，第二行第二列的比特发生错误。

  因此二维奇偶校验可以检测并纠正单个比特差错；能够检测分组中任意两个比特的差错。

Internet校验和

在发送方：

首先，将数据的每两个字节当作一个16位的整数，可分成若干整数；

其次，将所有16 位的整数求和；

最后，对得到的和逐位取反，作为检查和，放在报文段首部，一起发送。

在接收方：对接收到的信息 (包括检查和项)按与发送方相同的方法求和。

如果结果为全“1”：则收到的数据无差错；

如果结果中有“0”：则收到的数据出现差错。

• 特点：
  • 分组开销小，检查和位数比较少
  • 差错检测能力弱
  • 适用于运输层
  • 链路层的差错检测由适配器中专用的硬件实现，采用更强的CRC方法

循环冗余(CRC)检测

算法要求多项式必须包含最低此项!!!

• 即多项式编码，把要发送的比特串看作为系数是0或1的一个多项式，对比特串的操作看作为多项式运算

• 基本思想

  • 设发送节点要把数据D（d 比特）发送给接收节点
  • 发送方和接收方先共同选定一个生成多项式G（r+1比特），最高有效位 (最左边)是1。

把要发送的比特串看作为系数是0或1的一个多项式，对比特串的操作看作为多项式运算。

这里我们来看这样一个例子，10111这个比特序列，如果用多项式表示，每个比特作为多项式的系数，因此10111等价于x的4次方+x的2次方+x的1次方+1

• 基本思想

  • 模2运算

    • 加法不进位，减法不借位

    • 乘以2r，即比特模式左移r 个位置。

      *D*×2*r* XOR *R* = *D* 00…00 XOR *R*
        
                   = *DR* (*d+r* 比特)·
      

  • 如何计算CRC码。

    首先将数据D称为2的r次方，这里r表示CRC编码的位数，

    然后将其除以给定的生成多项式G，

    所得的余数为CRC编码

• 

  我们通过一个具体的例子来说明，CRC编码的计算过程。

  假设数据D为101110，生成多项式G为1001，CRC编码为3比特，是生成多项式的位数减1.

  这里用模2运输，计算CRC编码。

  首先将D乘以2的3次方，即可得101110000；

  然后将101110000除以生成多项式1001，最后可得余数为0011，因为CRC编码只取3比特，因此为011。

  因此发送方最终发送的数据为101110011。

• 例题

• CRC特点

  • 生成多项式G的选择：常见的有8、12、16和32 比特生成多项式G
  • 能检测小于 r+1 位的突发差错、任何奇数个差错。

补充

注意：CRC具有纠错能力，但是数据链路层一般只用他的检错能力，关于纠错看第四条

三种方法的比较

多路访问链路和协议

两种网络链路

• 点对点链路
  • 链路两端各一个节点。一个发送和一个接收
  • 如点对点协议ppp
• 广播链路
  • 多个节点连接到一个共享的广播信道
  • 广播：
    • 任何一个节点传输一帧时，信号在信道上广播，其他节点都可以收到一个拷贝

PPP(point to point protocol)协议（了解)

封装成帧，链路控制协议LCP，网络控制协议NCPs

帧格式

关于封装帧的透明传输

面对字节：

三种数据，定界符7E，转义字符7D和ASCII码控制符的处理

面对比特：

差错检测

计算范围如下，计算完之后填入FCS

广播信道

• 存在问题

多路访问协议

• 目的：

  • 避免多个节点同时使用信道，发生冲突，产生互相干扰

• 冲突（collide）：

  • 两个以上的节点同时传输帧，使接收方收不到正确的帧(所有冲突的帧都受损失)
    • 造成广播信道时间的浪费
    • 多路访问协议可用于许多不同的网络环境，如有线和无线局域网、卫星网等

• 理想的多地址访问协议

信道划分(静态划分信道)协议

• 把信道划分为小片(时隙)
• 给节点分配专用的小片
• 主要有TDMA、FDMA、CDMA三种

TDMA时分复用

• 设信道支持 N 个节点，传输速率是 R b/s

  • 时分多路访问TDMA (time division multiple access)

    • 将时间划分为时间帧，每个时间帧再划分为N个时隙（长度保证发送一个分组），分别分配给N个节点。每个节点只在固定分配的时隙中传输。

      例：6个站点的LAN, 时隙1、3、4 有分组, 时隙2、5、6 空闲
      

    

• 频率相同，每个用户占用不同时隙

• TDMA特点：

  • 避免冲突、公平
    • 每个节点专用速率R/N b/s
  • 节点速率有限：R/N b/s
  • 效率不高：节点必须等待它的传输时隙

FDMA频分复用

不同用户的数据使用不用的频率段

• 频分多路访问FDMA (frequency division multiple access)
• 
• 每个用户占一个频段

CDMA码分复用

与前面两个不同，码分复用允许用户在同样的时间使用同样的频带进行通信

由于各用户使用经过特殊挑选的不同码型，各用户之间不会造成干扰

每一个用户有标识性的唯一的编码，可以用这个编码对自己的数据进行编码然后进行发送

• 码分多路访问CDMA (code division multiple access)

• 

随机访问协议

• 基本思想
  • 发送节点以信道全部速率（R b/s）发送
  • 发生冲突时，冲突的每个节点分别等待一个随机时间，再重发，直到帧(分组)发送成功
  • 节点间没有协调者
• 典型随机访问协议：
  • ALOHA协议(纯ALOHA，时隙ALOHA)
  • 载波监听多路访问CSMA协议
  • 带冲突检测的载波监听多路访问CSMA/CD
  • 带冲突避免的载波监听多路访问CSMA/CA

ALOHA

• 

首先介绍ALOHA协议。

ALOHA是夏威夷大学研制的一个无线电广播通信网，采用星型拓扑结构，使地理上分散的用户通过无线电来使用中心主机。

中心主机通过下行信道向二级主机广播分组；

二级主机通过上行信道向中心主机发送分组（可能会冲突，无线电信道是一个公用信道）。如图所示。

ALOHA有两种形式：时隙ALOHA和纯ALOHA。我们将分别进行介绍。

纯ALOHA

• 非时隙ALOHA：简单，不需同步
• 帧一到达，立即传输
• 如果与其他帧产生冲突，在该冲突帧传完之后：
  • 以概率p立即重传该帧
  • 或等待一个帧的传输时间，再以概率p传输该帧，或者以概率1-p 等待另一个帧的时间
• 纯ALOHA效率
• 

时隙ALOHA

• 

• 控制发送的时间

• 比纯ALOHA效率更高

• 效率

  • 当有很多节点，每个节点有很多帧要发送时，成功时隙所占的百分比
  • 

CSMA（载波侦听多路访问）

动态接入控制

协调总线上各个主机的工作，尽量避免产生碰撞，是我们要研究的问题

• 载波侦听

  • 某个节点在发送之前，先监听信道
  • 信道忙：有其他节点正往信道发送帧，该节点随机等待（回退）一段时间，然后再侦听信道
  • 信道空：该节点开始传输整个数据帧

• CSMA特点：

  • 发前监听，可减少冲突
  • 由于传播时延的存在，仍有可能出现冲突，并造成信道浪费

• CSMA发送冲突的例子

  • 
  • 

  在时间t0：节点B侦听到信道空，开始传输帧，沿着媒体传播比特。

  在时间t1：节点D有帧要发送。B的传输信号未到达D，因此D检测到信道空，开始传输数据帧。很快，B的传输开始在D节点干扰D的传输（冲突）

  我们可以看到传播时延越长，节点不能侦听到另一个节点已经开始传输的可能性越大。

• 带来的问题：信道浪费

  • 节点没有进行冲突检测，既使发生了冲突，节点仍继续传输它们的帧。但该帧已经被破坏、是无用的帧，信道传输时间被浪费

总线局域网协议 CSMA/CD

多址接入MA：多个主机连在一条总线上，竞争使用总线

载波监听CS：发送前检测是否有其他站点正在发送，有则等待(96比特时间)

碰撞检测CD：发送的过程中检测是否出现碰撞，有则停止发送，退避一段时间再次发送（这个和发送完帧的传播不一样！发送完很有可能帧仍在传播)

载波监听多址接入/碰撞检测

CS:载波侦听/监听，每一个站在发送数据之前以及发送数据时都要检查总线上是否有其他计算机在发送数据

MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上

CD：碰撞检测(冲突检测)，边发送边监听，判断自己在发送数据时其他站是否也在发送数据

• 基本原理：传送前侦听

  • 信道忙：延迟传送
  • 信道闲：传送整个帧

• 发送同时进行冲突检测：一旦检测到冲突就立即停止传输， 尽快重发

• 目的：缩短无效传送时间，提高信道的利用率

• CSMA/CD举例

  可以看到CSMA/CD中虽然也会发生碰撞，但是两个节点B、D在检测到冲突之后很短的时间内都放弃传输。

  （备注）

  黄色表示B节点的传播物理范围，红色表示D节点的物理传播范围

  怎么看时空图，横轴表示四个节点在空间中的位置，纵轴表示时间

  在时刻t0，节点B侦听到信道是空闲的，因为当前没有其他节点在传输，于是节点B开始传输

  在t1时刻，由于B节点的电磁波还没有传播到D能检测的范围，因此D节点发现信道空闲，开始传输，这个时候就会产生相互干扰

  D节点检测到干扰后，会立即放弃传输，B节点也会放弃

• 以太网CSMA/CD的运行机制

  我们说以太网也是采用CSMA/CD机制来访问共享信道。

  其基本思想如下：

  首先，适配器从网络层获得一个数据报，封装成帧，准备发送；

  第二，如果适配器侦听到信道空闲，开始传输帧；如果检测到信道繁忙，将等待一段时间，直到侦听到信道空闲，开始传输帧；

  第三，在传输过程中，适配器会同时监听是否有其他适配器的信号能量；

  如果适配器在整个帧的传输过程中，没有监听到其他信号，则完成该帧的传输；如果监听到来自其他适配器的信号，则中止传输帧；

  中止传输后，适配器会等待一个随机时间，重新执行步骤2

  • 

关于碰撞

以太网CSMA/CD的运行机制讨论

• 拥塞信号

  • 48比特，确保所有传送者知道冲突发生

• 比特时间

  • •对于10 Mbps Ethernet 为0.1微秒，
    当K=1023，等待时间大约50毫秒

• 二进制指数回退算法

  • •目标：适配器依据当前负载情况重传，重负载时等待时间变长

    •第一次冲突： 在{0,1}中选k值；延迟Kx512比特时间传送

    •第二次冲突：在{0,1,2,3}中选k值…

    •10次以后，在 {0,1,2,3,4,…,1023}中选k值。

    •K是等概率选择

争用期

• 最迟要多久才能检测到碰撞？

引入争用期的概念

我们需要尽量做到的就是在数据发送完成之前，就是最后一个比特发送出去之前，我们的第一个比特已经到达目的主机了，如果帧太短没到达的话，这段信号就没有人监听了，意思是发生了碰撞也没人管

最小帧长

如果发送的帧太短，那么发送帧的时间就很短，完了之后可能帧还没传到地方，这个时候并没有进行碰撞检测，所以这个时候发生碰撞就没有办法处理了

如果接收方接收到的帧长度小于64字节，那么一定是发生了碰撞，这个数据为垃圾数据，应该直接丢弃

最小帧长 = 争用期 * 数据传输速率

这个是在传播时延和发送时延相同的极限情况下得出的，也就是第一个bit刚好传到然后最后一个bit刚好发送完的极限情况，保证了刚好在发送过程中能一直监听是否发生碰撞，免得发送完毕之后第一个字节还在传播就可能碰撞

最大帧长

截断二进制指数规避算法

用来计算发生碰撞之后的与下一次重传的退避(间隔时间)

信道利用率

提高利用率：以太网端到端的距离受到限制，以太网帧的长度应该尽可能长一些

接受方的流程

需要通过三个检查：最短帧长；地址正确；CRC检测出现误码

无线局域网协议 CSMA/CA

CA：避免碰撞

在无线局域网当中不能使用碰撞检测CD，应该使用碰撞避免CA！！！

原因：

• 可以适用于无线局域网

  • 这是CSMA/CD无法实现的

• 工作原理

  • 预约信道
  • ACK帧
  • RTS/CTS帧

• 两者区别

介质访问控制协议

• MAC协议：
• 

轮询协议

• 轮询开销
• 等待延迟
• 单点故障

令牌传递协议

• 令牌：
  • 一个特殊格式的MAC控制帧，不含任何信息
  • 确保同一时刻只有一个节点独占信道
• 

MAC地址，IP地址和ARP协议

Mac地址介绍

Mac地址又称为物理地址，用来全球性唯一标识网络接口，属于数据链路层，不属于物理层

单播，广播，多播MAC地址举例

多播和广播的区别：多播是一对多，不一定是全部；而广播就是一对全部

判断是否为多播地址，多播地址的第一个字节的第一个bit是1，也就是图中的第二个数字是奇数，这里就是7

给主机配置多播组列表进行私有应用时，不得使用公有的标准多播地址

IP地址

数据的封装过程

我看不懂也不需要看懂，加上首部(尾部)交给下一层

在网络层首部中应该封装有源IP地址和目的IP地址；链路层首部中应该封装有源MAC地址和目的MAC地址

数据包转发过程中的IP和MAC

在数据包的转发过程中，源IP地址和目的IP地址始终保持不变，而源MAC地址和目的MAC地址逐段链路(或逐个网络)改变！！

ARP协议

通过IP地址找到其对应的MAC地址

发送广播帧，目的MAC地址是全1(FF-FF-FF-FF-FF-FF)

对应的主机收到并且将发送方的IP和MAC存到自己的ARP缓存表中记录

返回的帧源IP和MAC是自己的，目的是发送方的；发送方收到返回帧之后解析，得到MAC地址并且存到ARP缓存表中

注意：ARP协议只能用于一个链路或者网络当中；跨网路需要逐个网络使用

交换局域网

概述

• 局域网：Local Area Network ( LAN )

• 多址访问协议广泛应用于局域网

• 基于随机访问的CSMA/CD广泛应用于局域网

• 局域网按拓扑结构进行分类：

  • 星形网、环形网、总线网、树形网和网状网

• 计算机与局域网通过网络接口板进行连接

  • 网络接口板又称通信适配器（Adapter）或网络接口卡NIC（Network Interface Card），通常我们称为“网卡”

链路层寻址和ARP

• 每个节点有网络层地址和链路层地址
  • 网络层地址
    • 节点在网络中分配的一个唯一地址（IP地址）。用于把分组送到目的IP网络。长度为32比特（IPv4）
  • 链路层地址
    • 又叫做MAC地址或物理地址、局域网地址
• MAC地址
  • LAN地址、物理地址
  • 节点“网卡”本身所带的地址（唯一）
  • MAC地址长度通常为6字节(48比特)，共248个
  • 6字节地址用16进制表示，每个字节表示为一对16进制数
    • 1A-2F-BB-76-09-AD
  • 网卡的MAC地址是永久的（生产时固化在其ROM里）

MAC地址分配

• 
• MAC 地址是平面结构
  • 带有同一网卡的节点，在任何网络中都有同样的MAC地址

AMC地址识别

• 广播信道的局域网中，一个节点发送的帧，在信道上广播传输，其他节点都可能收到该帧
• 大多数情况，一个节点只向某个特定的节点发送
• 由“网卡”负责MAC地址的封装和识别
• 发送适配器：
  • 将目的MAC地址封装到帧中，并发送。所有其他适配器都会收到这个帧。
• 接收适配器：
  • 检查帧的目的MAC地址是否与自己MAC地址相匹配：
  • 匹配：接收该帧，取出数据报，并传递给上层。不匹配：丢弃该帧
• 广播帧：发送给所有节点的帧 全1地址：FF-FF-FF-FF-FF-FF

回顾：节点的三种不同地址

刚刚我们讲到在单条链路上，数据帧的接收是根据目的MAC地址。

这里我们简单回顾下，一个节点的三种不同的地址表示。

第一种表示是：应用层的主机名，例如域名；

第二种表示是：网络层的IP地址，用于在网络层寻址，即路由器根据目的IP地址来进行转发；主机也根据目的IP地址是否是本机地址来判断是否接收。

第三章表示是：链路层的MAC地址，用于在链路层寻址，即实际链路传输时，每个主机网卡根据目的MAC地址是否是本机的MAC地址来判断是否接收。

在本页的例子中，标出了每个主机的IP地址和每个网卡的MAC地址。

回顾：地址之间的转换

那么，我们说实际的数据帧发送，需要目的主机的IP地址和MAC地址，这就需要提供地址之间的转化服务。

例如已知主机名，怎么查找该主机名对应的IP地址呢？这就需要用到DNS域名解析服务；

那么如果已知目的主机的IP地址，怎么查找它在同一个局域网中的MAC地址呢？这就需要用到ARP协议。ip->MAC

我们说ARP协议的主要作用是将IP地址解析为其对应的MAC地址。

需要说明的是ARP协议只为在同一个局域网内部的节点进行IP地址解析。

ARP地址地址解析协议

• ARP*表:* 局域网上的每个节点(主机、路由器)都有这个表

  •为某些局域网节点进行IP/MAC地址映射：

  < IP address; MAC address; TTL>

  •TTL (存活时间): 地址映射将被删除的时间（通常为20分钟）

两个主机位于同一个LAN

• 1.主机A希望发送数据报给主机B
  • B的MAC地址不在A的ARP映射表中
• 2.主机A 广播 ARP查询分组, 其中包含B的IP地址
  • 目的MAC地址 = FF-FF-FF-FF-FF-FF
  • 局域网中所有节点收到ARP查询分组
• 3.主机B收到ARP查询分组，返回B的MAC地址给主机A
  • 包含有B的MAC地址的帧发送给主机A(单播)
• 4.主机A在它的ARP表中缓存 IP-to-MAC 地址对，直到信息
  • 软状态：信息超时会被删除，除非有新的更新消息
  • ARP是即插即用的：
    • 节点创建ARP表不需要网络管理员的干预

发送数据报到子网以外

• 主机A构建IP数据报，源地址是A的IP地址，目的地址是B的IP地址

• 主机A构建链路层数据帧，目的MAC地址是路由器左边端口的MAC地址

• 1.

  首先主机A构建IP数据报，数据报的源IP地址是自己的111.111.111.111，目的IP地址是主机B的IP地址222.222.222.222。

  那么该数据报封装成数据帧的源MAC地址是自己的MAC地址，74-29-9C-E8-FF-55，目的MAC地址是谁的呢？是B主机的MAC地址，还是路由器左边端口的MAC地址呢？

  我们首先分析这个数据帧的发送路径。我们说当主机A判断该数据报的接收主机与自己不在同一个局域网时，它会首先将数据报发送到自己的第一跳路由器，即这里的路由器R，

  因此该数据帧的目的MAC地址应该是R的左边端口的MAC地址，E6-E9-00-17-BB-4B。

• 2.

  该数据帧到达路由器R后，路由器R接收数据帧，然后抽取出数据报递交给网络层，网络层根据目的IP地址，判断该数据报要往右边的端口转发，且接收主机B与自己右边端口属于同一个局域网。

• 3.

  因此向右边端口输出数据帧时，数据帧的源MAC地址是路由器右边端口的MAC地址1A-23-F9-CD-06-9B，

  数据帧的目的MAC地址是主机B的MAC地址49-BD-D2-C7-56-2A。

• 这里需要强调的是，在整个传输过程中，数据报的源IP地址和目的IP地址是不会发生改变的，改变的只是数据帧的源和目的MAC地址。

以太网

以太网的帧结构

• 发送方：
  • 发送适配器将IP数据报封装成以太网帧，并传递到物理层
• 接收方：
  • 接收适配器从物理层收到该帧，取出IP数据报，并传递给网络层
• 

接着，我们再介绍以太网的帧结构，如图所示，包括了前同步码、目的MAC地址、源MAC地址、类型、数据和CRC校验码。

注意这里CRC检验的数据只包含目的MAC地址、源MAC地址、类型、数据四部分。

首先发送方的发送适配器将IP数据报封装成以太网帧，并传递到物理层。

接收方的接收适配器从物理层收到该数据帧，抽取出IP数据报，并传递给网络层。

Ref : https://blog.csdn.net/eliot_shao/article/details/123473548

• 前同步码(8 字节)

  • 前同步码有8个字节，其中前7字节是“10101010”，最后一个字节是“10101011”。

    前同步码的作用是使接收方和发送方的时钟同步，接收方一旦收到连续的8字节前同步码，可确定有帧传过来。

    注意：前同步码是“无效信号”，接收方收到后删除，不向上层传。CRC的校验范围不包括前同步码。

• 源、目的MAC地址(各6字节)

  然后是各6个字节的源、目的MAC地址。

  如果主机A向主机B发送一个IP数据报，主机B只接收目的MAC地址与自己MAC地址匹配的数据帧或广播地址的数据帧，并将数据字段的内容传递给网络层。否则，丢弃该帧。

• 类型字段(2 字节)

  • 

  • 帧结构中类型字段主要是支持以太网中的多种网络层协议的复用的，绝大多数这里的类型是指IP协议。

• 数据字段(46-1500字节)

  • 然后是数据字段，以太网的最大传输单元MTU是1500字节，最小长度是46字节。

• 循环冗余检测CRC(4字节)

  帧结构的尾部是CRC循环冗余校验码。它主要是用于帮助接收主机检测数据帧中是否出现比特差错。

不可靠的无连接服务

• 以太网向网络层提供的服务：
  • 无连接服务：
    • 通信时，发送方适配器不需要先和接收方适配器”握手”
  • 不可靠服务：
    • 接收到的帧可能含有比特差错
      • 收到正确帧，不发确认帧
      • 收到出错帧，丢弃该帧，不发否定帧
      • 发送适配器不会重发出错帧
      • 丢弃数据的恢复是通过终端传输层的可靠数据传输机制来实现的

交换机SWITCH

集线器HUB

集线器连接下的网络虽然物理上看起来不是总线型的，但是逻辑上仍然是总线型的

使用CSMA/CD协议

集线器只工作在物理层，他的每个接口只是简单的转发比特流，碰撞检测的事情交给各站的网卡进行检测

使用集线器HUB在物理层扩展以太网

使用集线器连接的以太网就相当于是把总线型的给画的好看了点，其实没什么区别，用的还是CSMA/CD协议调节各个主机使用总线，还要进行碰撞检测，只能工作在半双工模式，收发帧不能同时进行

交换机与集线器的对比

比较

某站的信号经过集线器会转发给广播域中的所有其他主机，但是经过交换机之后，由于内部的设置会只转发给目的主机

以太网交换机有多个接口，一般工作在全双工模式，不用考虑碰撞检测(不适用CSMA/CD协议)，能同时连通多个接口!

关于碰撞的问题，集线器收到帧之后就会直接向其他所有主机进行传递，这里必然就会涉及到碰撞的问题

而交换机，当交换机收到多个帧的时候，为了避免碰撞会将这些帧进行缓存，之后再进行逐一转发，避免了碰撞的问题

交换机和集线器扩展以太网

单播帧

广播帧

可能发生碰撞的时候

因此，集线器扩大了广播域，也扩大了碰撞域；而交换机扩大了广播域，但是隔离了碰撞域!!!

• 链路层设备
  • 存储转发数据帧
  • 检查到达的数据帧的MAC地址，有选择的转发数据帧到一个或多个输出链路，当数据帧被转发到一个共享网段时，使用CSMA/CD来访问共享链路
• 透明
  • 主机不关心是否存在交换机
• 即插即用和自学习
  • 交换机不需要手工配置
• 

本次课将详细讲解链路层交换机的工作原理。

首先交换机是属于链路层的设备，其主要作用是存储转发数据帧。

对于到达交换机的数据帧，交换机首先检查其目的MAC地址，然后根据MAC地址，有选择的将数据帧转发到一个或多个输出链路；

如果输出链路是一个共享网段，将使用CSMA/CD来访问共享链路。我们这里给出了一幅图来帮助大家理解后面这句话。

在这幅图中A、B、C主机和交换机的端口1由集线器设备互连，因此这里，A、B、C主机和交换机的端口1构成了一个共享网段，在共享链路发送数据帧，需要用到我们前面学习到的以太网链路访问协议CSMA/CD。

链路层交换机的第二个特点是透明，这里的透明是指的当一个主机向另一个主机发送数据帧时，它并不会知道某个交换机会收到这个数据帧，并将其转发到另一个节点。

交换机的第三个特点是即插即用和自学习，也就是说交换机是不需要手工配置的，插上就可以用。

支持多节点同时传输

在组网时加入交换机后，可以支持多个节点同时传输数据帧。

可以看上边这幅图，每个主机由单独的链路与交换机端口相连，因此交换机每个端口对应的链路和主机是一个独立的碰撞域。

又因为交换机对于收到的数据帧可进行缓存，因此在上边这幅图中，A主机和B主机同时发送数据帧，将不会发生冲突。

因此交换机具有较高的转发率。

以太网自学习和转发帧的过程(自学习算法)

考虑以下过程

A给B发送帧，进入交换机1中，先进行登记，记录A的MAC地址和接口1，然后找B的MAC地址，找不到，进行广播，接口3的B收到发现正确，接受；C则丢弃；到4号接口转发到交换机2中，帧进入交换机2中先进行登记，登记A的MAC地址和接口2，然后进行广播，都不匹配，则都丢弃，这就是一个完整的过程

后面还有两个过程

丢弃帧的例子

G发送帧到A，这个帧在分岔口两边传播，给A并接受，到交换机的时候先进行登记，然后查找，发现A 1，意思是从哪里来回哪里去，这显然是没必要转发的，于是丢弃

每条记录的持续时间不是永久的，会定期删除!!!

转发表

在右边这幅图中，我们有这样一个疑问：交换机是怎么知道A’可通过端口4达到， B’ 可通过端口5到达呢？

这是因为每个交换机都有一个转发表，其中的条目如下：(主机的MAC地址，到达主机的端口，时戳)；

因此当数据帧的目的MAC地址为A’主机时，我们通过查找相应的转发表项，就可获知该主机对应的端口。

那么转发表中的条目是怎么建立的呢？我们说是通过自学习机制。

• 自学习

下面我们就来介绍交换机的自学习机制。非常简单。

每当交换机收到一个数据帧时，交换机会学习发送主机的位置：及进入的局域网段和到达端口，并在转发表中进行记录。

如这里的例子所示，主机A发送数据帧给主机A’，数据帧到达交换机时，交换机会在转发表中记录这样一个表项：

A主机的MAC地址和可达端口号1，生存时间60秒，这就表示通过端口1可达到A主机。

数据帧的过滤/转发

• 

下面我们来学习交换机收到数据帧后，是如何进行查表转发的。我们说根据如下规则：

首先，记录到达链路和发送主机的MAC地址；

第二步，使用数据帧的目的MAC地址，在转发表中进行检索：

如果在转发表条目中找到对应的MAC地址，则执行：

如果目的MAC地址对应的端口与数据帧的到达端口相同，说明接收主机属于同一个共享网段，则直接将该数据帧丢弃。因为接收主机也会收到该数据帧；

否则，转发端口与达到端口不一致，则将该数据帧转发到指定端口

如果数据帧的目的MAC地址在转发表中没有找到，则交换机将该数据帧向除到达端口之外的所有端口转发，也就是泛洪。

自学习/转发例子

我们来看一下自学习和转发的例子。

这里初始时转发表是空的，当主机A发送数据帧给主机A’时，该数据帧到达交换机，

交换机首先根据收到数据帧的端口和该数据帧的源MAC地址，建立表项1，说明通过端口1可达到主机A，这就是自学习。

然后交换机根据数据帧的目的MAC地址（A’）在转发表中查找，由于没有找到A’的MAC地址，则交换机将该数据帧向除1端口之外的所有端口转发，

只有A’主机会发现数据帧的目的MAC地址与自己的MAC地址一致，接收该数据帧。

注意，这里主机A’发往主机A的数据帧，在到达交换机后，由于转发表中已经有目的MAC地址对应的表项，因此交换机将只向1端口转发数据帧。

交换机互连

• 

交换机也可以进行互连，以组成更大的局域网。如本页的图所示。

那么请大家思考，这样一个问题，如果主机A发送数据帧给主机G,那么交换机S1是怎么知道需要先把数据转发到S4和S3的？

我们说仍然是通过自学习。当数据帧到达S1时，可能S1的转发表中没有G主机的MAC地址的表项，于是S1将该数据帧泛洪，那么S4的端口也会收到这个泛洪的数据帧，

如果S4的转发表也没有G主机的MAC地址对应的表项，则S4会继续泛洪，于是S3也会收到数据帧，如果S3的转发表仍然没有G主机的MAC地址，则S3会继续向它的端口泛洪，直到数据帧到达G主机。

• 多个交换机自学习的例子

交换机交换特点和方式

• 特点

  • 识别目的MAC地址，根据交换表进行端口选择
  • 识别源MAC地址更新交换表

• 在识别目的MAC地址和源MAC地址的过程中是否需要接收并缓存完整的帧呢？

  • 在识别目的MAC地址和源MAC地址的过程中，需要接收并缓存完整的帧。这是因为MAC地址是位于数据链路层的帧的头部中，用于标识帧的源和目的设备。

    当一个设备接收到一个帧时，它需要读取帧头部中的目的MAC地址和源MAC地址字段来确定该帧是否是针对自己的，或者是从哪个设备发送过来的。因此，设备需要接收并缓存完整的帧，以便能够从帧头部提取MAC地址信息进行判断和处理

• 交换方式

  • 存储转发(缓存整个帧后再转发)
  • 快速分组(直通交换)
    • 识别出目的地址直接转发

存储转发交换方式

快速分组交换方式

存储转发：具有差错检测功能，转发时延较大，适用于出错率高的链路。

快速分组又称直通交换：不具有差错检测功能，转发时延较小，适用于时延要求高，出错率低的链路。

路由器和交换机的区别

最后我们将交换机和路由器进行简单的对比。

首先，路由器和交换机都是存储转发设备（中转设备），其中路由器是网络层设备，交换机是链路层设备。

第二，路由器和交换机都需要维护转发表，其中路由器使用路由算法来计算转发表，基于IP地址转发；而交换机是通过泛洪和自学习来建立转发表，基于MAC地址进行数据帧转发。

虚拟局域网VLAN

以太网的规模变大之后，随之而来的就是广播域不断增大，广播会导致很大的弊端!!!

如何缓解这个问题呢？

可以使用路由器，路由器默认情况下不对广播数据包进行转发，所以可以隔绝广播域

但是路由器成本太高了，在局域网内部尽量少的使用路由器，所以这个时候可以用虚拟局域网VLAN技术

同一个VLAN内部可以广播通信，不同的不可以广播通信；VLAN的划分与物理位置无关，只与人为的设置相关!!!

第六章 网络编程

考试只会考写步骤，代码在实验里就写过了

步骤