山东大学计算机网络期末

内容仅供参考。如有错误之处，敬请指正！

计算机网络

大纲

第一章 概述
第二章 物理层
第三章 数据链路层
第四章 介质访问子层
第五章 网络层
第六章 传输层
第七章 应用层

第一章 概述

1.基本概念

计算机网络定义：

表示一组通过单一技术相互连接起来的自主计算机集合。

分布式系统：

是建立在网络上的软件系统，有高度的内聚性（数据库分布节点高度自治）和透明性（数据库分布节点对用户是透明的）。

Internet 是最著名的计算机网络，万维网是最著名的分布式系统，万维网（软件）运行于 Internet（硬件）上。internet，泛泛，指互联网络（两个或多个网络的连接）。

VPN：虚拟专用网络

一种可以将不同地点的单个网络联结成一个扩展网络的技术。

P2P与CS：

CS：由高性能计算机服务器和普通计算机客户机组成，服务器负责存储数据并处理客户请求，而客户机可远程访问服务器

P2P：对等模型（又称工作组），各台计算机具有相同功能，一台计算机可作为服务器设定共享资源供网络中其他计算机使用，又可作为工作站。没有专用的服务器或工作站。

2.网络硬件

依据传输模式划分网络：

单播(unicasting)：只有一个发送方和一个接收方的点到点传输，也叫点到点链路(point-to-potint)

广播(boradcasting)：任何一台机器发出的数据包能被其他人任何机器收到。每个数据包的地址字段指定了预期的接收方，只有预期的接收方会做出应答，其他的机器会忽略这个数据包。

两种广播网络，bus总线型；ring令牌环网络

多播/组播(mutilcasting)：将数据包发给一组机器，即所有机器的一个子集。广播可以看成是一种特殊的组播形式。

依据网络尺度划分网络：

PAN（个域网）：允许设备围绕一个人进行通信。例子，计算机通过无线网络与其外围设备链接。突出技术，蓝牙。

LAN（局域网）：一种局部地区的私有网络。分为有线和无线两种。

局域网特点：①距离短；②传输速率高；③错误率低。

无线LAN，代表技术WIFI。

有线LAN，大多使用铜线作为传输介质，也有一些使用光纤。

许多有线局域网的拓扑结构是以点到点链路为基础的，俗称以太网的 IEEE 802.3 是迄今为止最常见的一种有线局域网。

有线局域网在性能的所有方面都超过了无线局域网。

MAN（城域网）：范围覆盖一个城市。最著名的城域网例子是许多城市都有的有线电视网。

WAN（广域网）：范围很大，它跨越很大的地理区域，通常是一个国家、地区或者一个大陆。

两个不同的网络用路由器连接，两个相同的网络用交换机连接。

internet（互联网）：一组相互连接起来的网络。

Internet（因特网）：是一个特殊的互联网络。

gateway（网关）：将两个或多个网络连接起来并提供必要转换的机器，其硬件和软件方面的总称是网关。

packet switching（分组交换/包交换）：在通信过程中，通信双方以分组为单位、使用存储-转发机制实现数据交互的通信方式。

3.网络软件

协议（protocol）：是指通信双方就如何进行通信的一种约定。

层次（layer）：为降低网络设计的复杂性，绝大多数网络都组织成一个层次栈，每一层都建立在下一层的基础之上。每一层都向上一层提供特定的服务，而把如何实现这些服务的细节对上一层屏蔽。

接口（interface）：在每一对相邻层次之间。定义了下层向上层提供哪些原语操作和服务。

服务（service）：是由一组原语(primitive)正式说明，用户可以通过这些原语来访问该服务。

错误控制：从接收到的信息中发现错误。一种机制，检错编码。

流量控制：在每一层会发生的分配问题，如何保持快速发送方不会用数据把慢速接收方淹没。（解决 从接收方到发送方的反馈机制）

面向连接和无连接的服务：

面向连接：服务用户首先必须建立一个连接，然后使用连接传输数据，最后释放连接。本质上像一个管道。（电话系统）

无连接：每一个报文都携带者完整的目的地址，每个报文都由系统中的中间节点路由，并且独立于后续的报文。（邮政系统）

区别：

a．面向连接的要求建立连接，因而没有传输的数据没有必要再标明传输的目的地址；

而无连接的则对每个报文都由独立的目标地址。

b．一般来说，面向连接的可靠性较高，协议相对复杂，传输的数据按照发送顺序到达；

而无连接的可靠性较差，协议相对简单，常出现乱序，重复和丢失现象。

可靠和不可靠的服务：

可靠服务：即从来不丢失数据的一种服务。一般情况下，可靠服务都要求接收方向发送方确认收到的每个报文。

不可靠的服务：不会给发送方反馈任何确认消息，不保证数据不丢失。

可靠与不可靠服务同时存在的原因：

在给定的层次可靠通信并不总是可以使用的。为了提高可靠服务而导致的固有延迟可能是不可接受的。

面向连接的服务是可靠的吗？

面向连接的服务只是在发送发和接收方之间建立连接，它并不能保证发送的数据流能准确无误的按序到达接收方。面向连接的服务同样分为可靠的面向连接服务和不可靠的面向连接服务。其中，前者主要包括报文序列、字节流，后者如数字化语音。

服务与协议的关系：

服务（上下层之间的联系）是指某一层向它上一层提供的一组原语操作，服务定义了该层打算代表其用户执行哪些操作，但是他不涉及如何实现这些操作。

协议（对等体之间的规范）是一组规则，用来规定同一层上的对等体之间所交换的消息或者分组的格式和含义。实体利用协议来实现他们的服务定义，可以自由的改变协议而不影响它提供给上层的服务。

4.参考模型

OSI模型：实力在于模型本身

开放系统互连。七层，由低到高：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层。

如物理层实现了点到点的传输，而链路层使此传输变得可靠；网络层确定了传输路径，而传输层使此传输变得可靠。

TCP/IP模型：实力在于协议

本书使用的模型，混合模型，包括五层：物理层，数据链路层，网络层，传输层，应用层。

模型的比较：

相同点：两者都是建立在协议栈概念上的，并且协议栈中的协议彼此相互独立。同时两个模型中各个层的功能也大致相似。

不同点：OSI 模型的实力在于模型本身，TCP/IP 模型实力在于协议。

OSI 模型分为 7 层，明确区分了服务、接口和协议。这个模型是在协议之前产生的，网络层同时支持无连接和面向连接的通信，但是传输层只支持面向连接的通信。

TCP/IP 模型分为 4 层，没有明确区分服务、接口和协议。通用性差。TCP/IP 模型是先有的协议后有的模型，协议和模型切合度高。TCP/IP 模型的网络层只支持无连接的通信，但是传输层同时支持两种。

5.802和网络标准化

802协议，致力于研究局域网和城域网的物理层和MAC层中定义的服务和协议，对应OSI网络参考模型的最低两层（即物理层和数据链路层）。

第二章 物理层

1.数据通信的理论基础

概念：

数据：传输信息的实体，信息是数据的内容或解释。

信号：数据的物理量编码，数据以信号的形式传播。

信道：传送信息的线路。

比特率：数据传输速率，bps。每秒传送的二进制位数。

码元：时间轴上的一个信号编码单元。

波特率：信号传送速率。信号每秒钟变化的次数，也称调制速率。

带宽：信号或信道占据的频率范围。频率越高，传递距离越短，易损坏。

编码器：数据→适合传输的信号——便于识别、纠错

调制器：信号→适合传输的形式——按频率、幅度、相位

（理解：信息到数据，数据到信号，信号需调制成适合传输的形式）

通信的三个要素：信源、信宿和信道。

信息通过通信系统传输。信息和数据（0，1）不能直接在介质上传输（转换成物理信号）。

模拟信号和数字信号

周期信号和非周期信号

数字通信的优点：

抗噪声能力强；可控制差错，提高了传输质量；便于计算机处理；易于加密；可以传输多种，语音数据影像

传输模式：

单工、半双工、全双工

数字数据的传输方式：

基带：不调制编码后的数字脉冲信号直接传输

频带：调制成模拟信号再传输，需解调

数据同步方式：

位同步（使接收端接收的每一位信息都与发送端保持同步）、字符、帧

公式：

信道最大传输率：

尼奎斯特定理 Nyquist（信道无噪声）

单位：bps

实际信道上的三类损耗：衰减、延迟、噪声

香农定理 Shannon（信噪比是 S/N）

2.传导性传输介质（有导向的传输介质）

磁介质（高带宽、低费用、高延时）

金属导体（双绞线、同轴电缆）

光纤

无线介质

双绞线：

优缺点：成本低。密度高、节省空间。安装容易（综合布线系统）。平衡传输（高速率）。抗干扰性一般。连接距离较短

同轴电缆：

细，优缺点：价格低。安装方便。抗干扰能力强。距离短。可靠性差

粗，优缺点：价格稍高。安装方便。抗干扰能力强。距离中等。可靠性好

光纤：依靠光波承载信息

优缺点：速率高，通信容量大。传输损耗小，适合长距离传输。抗干扰性能极好，保密性好。轻便

无线介质：电磁波或光波承载信息

优缺点：无需物理连接。适用于长距离或不便布线的场合。易受干扰

不同类型的信号在不同类型的信道上传输有4种组合

3.三种数字编码波形图

不归零制：连着两个0不好区分，不具备自同步机制，带宽效率低。

曼彻斯特：每个码元中间发生跳变。高到低0低到高1。

差分：码元开始处有跳变表示0，无跳变表示1。（这样的话，就可能有两种相反的结果了）是设定一个初始电平（默认为高电平）

4.PSTN电话系统

PSTN 是一种常用的旧式电话系统，提供的是一个模拟的专用通道，通道之间经由若干电环交换机连接而成，当两台主机或路由器需通过PSTN 连接时，必须在网络接入侧使用调制解调器实现信号的模数/数模转换。

电话系统的组成：本地回路、干线上的（多路复用）和交换局的（交换机、交换技术如虚电路交换和分组交换等）

非对称数字用户线（ADSL）：一种数据传输方式，上行和下行带宽不对称。采用 FDM（一种多路复用技术）把普通的电话线分成电话、上行和下行三个相对独立信道，从而避免相互之间的干扰。

三种常用的调制技术：调幅、调频、调相（分别表示是改变 A、f 和φ三个参数来区分不同信号）

多路复用技术：

使多个信号可以共享同一传输路线。（为何复用，线路成本）

分类：（1）频分复用FDM

整个传输频带被划分为若干个频率通道，每个用户占用一个频率通道。频率通道之间留有防护频带。

（2）波分复用WDM

整个波长频带被划分为若干个波长范围，每个用户占用一个波长范围来进行传输。

（3）时分复用TDM

把时间分割成小的时间片，每个时间片分为若干个通道（时隙） ，每个用户占用一个通道传输数据。

TDM的缺点：某用户无数据发送，其他用户也不能占用该通道，将会造成带宽浪费。

改进：统计时分多路复用（STDM），用户不固定占用某个通道，有空槽就将数据放入。

交换技术：

分为电路交换、分组交换。

电路交换：交换设备在通信双方找出一条实际的物理线路的过程。

特点：数据传输前需要建立一条端到端的通路。

优缺点：建立连接的时间长；一旦建立连接就独占线路，线路利用率低；无纠错机制；建立连接后，传输延迟小。

电路交换的三个阶段：⑴建立连接⑵通信⑶释放连接

分组交换：将报文划分为若干个大小相等的分组(Packet)进行存储转发。

特点：数据传输前不需要建立一条端到端的通路。有强大的纠错机制、流量控制和路由选择功能。

优点：存储量要求较小，可以用内存来缓冲分组——速度快；转发延时小——适用于交互式通信；某个分组出错仅重发该分组——效率高；各分组可通过不同路径传输，可靠性高。

第三章 数据链路层

数据链路层是基于物理层不可靠的传输向上层提供可靠的传输，它提供的是相邻两个节点之间可靠的数据传输。

1.数据链路层的设计问题

数据链路层使用物理层提供的服务在通信信道上发送和接受比特。完成一些功能：

（1）向网络层提供一个定义良好的服务接口。

（2）处理传输错误。

（3）调节数据流，保证慢速的接收方不会被快速的发送方淹没。

为实现这些目标：数据链路层从网络层获得数据包，并将之包装成包含：

帧头 + 有效载荷（存放数据包）+ 帧尾 的帧（frame）

数据链路层的工作核心就是帧的管理。

（源机器的网路层有一个实体-称为进程，它将一些比特交给数据链路层，要求传输到目标机器。数据链路层的任务就是将这些比特传输给目标机器，然后再进一步交付给网络层。）

一般情况下，提供三种服务：

（1）无确认的无连接服务。

源机器向目标机器发送独立的帧，目标机器不对这些帧进行确认。不需建立逻辑连接。适用于错误率低或者实时通信（语音传输）的情况。以太网是一个极好实例。

（2）有确认的无连接服务。

源机器向目标机器发送独立的帧，目标机器会对这些帧进行确认。不需建立逻辑连接。适用于不可靠的信道（无线系统，WiFi）。

（3）有确认的有连接服务。

源机器和目标机器在传输任何一个数据之前要建立一个连接，保证目标机器按照正确的顺序接受每一个帧。适用于长距离且不可靠的链路（卫星信道，长途电话）。

成帧：

数据链路层使用物理层提供给它的服务。数据链路层接收到的比特流不能保证没有错误。为检测错误和纠正错误，数据链路层将比特流拆分成多个离散的帧，为每个帧计算一个称为校验和的短令牌，并将该校验和放在帧中一起传输。

拆分比特流注意：（1）如何识别帧的边界（2）如果帧的数据出现与边界一样的flag，如何防止数据被识别为边界。

4种方法。

（1）字节计数法

用头部的一个字段来标识该帧中的字符数：

问题：因为一个传输错误，就会全弄混。很少被使用。

（2）字节填充的标志字节法

发送方使用标志字节（FLAG）作为开始和结束；使用转义字节（ESC）表示其后的字节为数据字节而不是标志字节或转义字节。接收方将收到的数据中的转义字节删除后再传递给网络层。

（3）比特填充的标志比特法（位填充）

使用“01111110”表示帧的开始和结束。每当发送方的数据链路层在数据中遇到连续5个1（不做处理若下一个还是1就会被识别为边界），就自动在输出的比特流中填入一个0。

（4）物理层编码违禁法

使用“不会出现在常规数据中”的冗余比特作为边界。

差错控制：引入计时器；序号（后续细讲）

流量控制：发送方发送帧的速度超过了接收方能够接收这些帧的速度，而导致丢帧。

解决方法：

基于反馈的流量控制（链路层）。

基于速率的流量控制（网络层）。

2.差错检测和纠正

传输出错的原因：一是信道的加性噪声；二是由于传输总特性（包括收、发滤波器和信道的特性）不理想引起的码间串扰。

主要的反馈重传方式：（一种差错控制方式）

–发送-等待ARQ（停—等协议）

–连续发送ARQ（滑动窗口协议）

–选择重传ARQ

奇偶校验码（通过增加冗余位使得码字中”1″的个数恒为奇数或偶数的编码方法，可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。）

循环冗余码CRC：

信息码/信息代码f(x)；生成多项式G(x)，它的最高次为r。

过程：发送方发送信息字段和校验字段

接收方接收到以后根据数据重新计算R(x)，相等则接收正确。

**计算步骤：**得到f(x)*x^r作为被除数，除数为G(x)对应的码字。模2运算得到商Q(x)，位数同信息码。余数为R(x)，位数为r。

计算原则：无进位与退位，被除数首位为1则商取1，为0则商取0。

3.基本数据链路协议

组成帧的四个字段：kind、seq、ack 和 info。
格式：

（1）一个乌托邦式的单工协议（协议 1）

不需考虑任何错误情况：数据单向传输，双方总是就绪，数据处理时间不计，缓存空间无限大，通信信道永不丢帧。

发送过程是一个无限的 while 循环，它尽可能快速地把数据放到线路上。无差错控制或者流量控制方面的限制。接受过程一直等待一个未损坏的帧到达。（发送速率和接收速率必须一样快）

（2）无错信道上的单工停-等式协议（协议 2）

单向数据传输，发送方网络层一直有无限的数据要发送， 信道不会出错，从不损坏或丢失帧，发送方需等待接收方确认帧返回后才发送下一帧。如果接收方不反馈应答信号，则发送方必须一直等待，然后就陷入等待接收方确认信息的过程中，因而传输效率低。

（3）有错信道上的单工停-等式协议（协议 3）

信道存在噪音。需要计时器与序号配合，需要超时重传机制。

4.滑动窗口协议

滑动窗口（sliding window）：为了便于理解，可以认为数据是一条传送带，而滑动窗口中的数据是当前准备处理的数据。

捎带确认（piggybacking）：暂时延缓确认以便将确认信息搭载在下一个待发数据帧上的技术。捎带确认通常与累计确认一同使用，更好的利用了信道的可用带宽。

期望确认：收到数据帧以后向发送方发送期望对方发送的下一帧的序号。

累计确认（cumulative acknowledgement）：当 n 号帧的确认到达，n-1 号帧、n-2号帧等都会自动被确认。

否定确认（NAK）：接收方检测到错误时发送的否定确认，实际是一个重传请求，在 NAK中指定了要重传的帧。

发送窗口（sending window）：发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小 = 上界 – 下界，大小可变；

接收窗口（receiving window）：接收方维持着的一个窗口对应于一组允许它接受的帧。接收窗口的上界表示已接收的序号最大的帧，下界表示希望接收的帧

（1） 1 位滑动窗口协议（协议 4）

（发送窗口大小=1，接收窗口大小=1）

当接收窗口大小为 1 时，可保证帧的有序接收，但效率较低。能保证无差错传输，但是基于停等方式；若双方同时开始发送，则会有一半重复帧。

（2）回退 N 协议（协议 5）

（发送窗口大小>1，接收窗口大小=1）

如果发生超时重传事件，发送方重传所有的已发送但未收到确认的帧。

对于接收方，如果中间第n号帧丢失了，接收方就会一直等待，这时再次收到后边的帧会直接丢弃，只想等着丢失的帧到来，（发送方超时会重新发送）接收方会返回一个n的确认帧，代表n以及n之前的都已经收到了，这时发送方会从 n+1 号帧开始在发送一遍后边所有的帧（很专一）。

一般使用累计确认。

（3）选择重传协议（协议 6）

（发送窗口大小>1，接收窗口大小>1）

先暂存出错帧的后继帧。

发送方按照窗口的顺序依次发送帧给接收方，而接收方检查该帧是否可以落在接收窗口内，即以前没有接收过且该序号在窗口可接收的范围内，如果可以那么不管这一帧是否为网络层所期望的下一个数据包都接收该帧并暂存于缓冲区内。

每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。

接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧【收到谁确认谁】，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层网络层，然后向前移动滑动窗口。

对数据帧逐一确认，收一个确认一个；
只重传出错帧；
接收方有缓存；

第四章 介质访问控制子层

属于数据链路层底层。

用来确定多路访问信道下一个使用者的协议属于数据链路层的一个子层，称为介质访问控制（MAC）子层。多路访问信道与LAN紧密相关。

1.静态和动态信道分配

静态：把信道容量拆开分给多个用户使用（频分多路复用）。或每个用户拥有固定的信道传送时槽（时分多路复用）。流量呈突发性，大量宝贵的频谱将被浪费。静态不适应突发性的流量。

动态信道分配的假设

2.多路访问协议

定义：控制多个用户共用一条信道的协议

ALOHA协议：

分为纯ALOHA协议和分槽ALOHA协议。

纯ALOHA：

基本思想：用户有数据要发送时，可以直接发至信道；然后监听信道看是否产生冲突，若产生冲突，则等待一段随机的时间重发;（以太网间隔，51.2μs。

很大可能帧被破坏（只要两个帧试图在相同时间占用信道，冲突就会发生。）信道利用率最高只有18.4%。

分槽ALOHA协议：

基本思想：把信道时间分成离散的时间槽，槽长为一个帧所需的发送时间。**每个站点只能在时槽开始时才允许发送。**其他过程与纯ALOHA协议相同。

本法要求用户遵守统一的时间槽边界。这将易受冲突期减小了一半。信道利用率最高为36.8%。

载波监听多路访问协议（CSMA）：

站点在为发送帧而访问传输信道之前，首先监听信道有无载波，若有载波，说明已有用户在使用信道，则不发送帧以避免冲突

分为1-坚持型、非坚持型、p-坚持型。

1-坚持型：若站点有数据发送，先监听信道；若站点发现信道空闲，则发送；若信道忙，则继续监听直至发现信道空闲，然后完成发送；若产生冲突，等待一随机时间，然后重新开始发送过程。

减少了信道空闲时间，增加了发生冲突的概率。

非坚持型：若信道忙，等待一随机时间，然后重新开始发送过程；若产生冲突，等待一随机时间，然后重新开始发送过程。

减少了冲突发生的概率。增加了信道空闲时间

p-坚持型：若站点发现信道空闲，则以概率p发送数据，以概率q =1- p 延迟至下一个时槽发送。若下一个时槽仍空闲，重复此过程，直至数据发出或时槽被其他站点所占用；若信道忙，则等待下一个时槽，重新开始发送；若产生冲突，等待一随机时间，然后重新开始发送

带冲突检测的载波监听多路访问协议CSMA/CD：

站点使用CSMA协议进行数据发送；在发送期间如果检测到冲突，立即终止发送，并发出一个瞬间干扰信号，使所有的站点都知道发生了冲突；在发出干扰信号后，等待一段随机时间，再重复上述过程。

一个站点确定发生冲突要花多少时间？最坏情况下，2倍电缆传输时间

二进制指数后退算法：

最小帧长：避免帧的第一个比特到达电缆的远端前帧已经发完，帧发送时间应该大于 2t。10Mbps LAN，最大冲突检测时间为51.2微秒，最短帧长为64字节；

MACAW：

冲突避免多路访问（MACA）：

无线的冲突避免多路访问。发送方刺激接收方输出一个短帧，以便其附近的站能检测到该次传输，从而避免在接下去进行的较大数据帧传输中也发送数据。

解决的方案就是发送方先发 RTS，之后接收方回 CTS 信号，并从这个信号中包含这次传输的持续时长信息保证让此时长内接收方附近站点主动静默，从而不会使其受到干扰。

MACAW：

无线的冲突避免多路访问。在此基础上增加了三个检验分组。ACK、DS、RRTS。

3.以太网

802.3帧格式：

前导码不被计算进帧长中。

SOF，指start of frame delimiter

4.WLAN

隐藏终端问题：由于站点距离竞争者太远，从而不能发现潜在介质竞争者的问题称为隐藏站点问题。eg，A向B发送数据的过程中，C由于收不到A的数据，也可以向B发送数据，导致B接收发生冲突。

暴露终端问题：由于非竞争者距离发送站点太近，从而导致介质非竞争者不能发送数据的问题称为暴露站点问题。eg，B向A发送数据，被C监听到，导致C不能向D发送数据。

一个点如果只听到 RTS，没有听到 CTS，说明它在发送方的发送范围内，却不在接收方的发送范围内，则它只要不干扰发送方收 CTS，即可随便发送。解决了暴露终端问题。

一个点如果只要听到 CTS 说明它就在接收方发送范围内，此时它要保持静默到持续时长，直到此次传输结束它再进行发送，否则会干扰接收方接收。解决了隐藏终端问题。

传统的CSMA协议不适合于无线局域网，需要特殊的MAC子层协议。

CSMA/CA：

带有冲突避免的 CSMA

它是 802.11 MAC 子层协议的核心协议，与之前的 MACA 相比，它引入了短确认确保每一帧的发送成功，即数据发送后站启动确认计时器，如果计时器时间到但没有收到接收方回复的收到的确认，则试图重新发送。但在 RTS 和 CTS 方面并没有考虑暴露终端问题。

二进制指数后退的 CSMA/CA P220，P234

侦听很短的一段时间后发现没有信号，则随机选择 0-15 个时间槽进行倒计时倒数，当听到有帧发送时暂停倒计时，空闲时计数，到 0 时就发送，如果发送成功则目标站会发送一个短确认，如果没收到确认，则发送方加倍自己选择的时间槽数，重新试图发送。如此反复，直到成功发送帧或达到最大重传次数。

详细：智库p25

802.11 MAC子层协议：

与以太网有很大的不同，这种本质上的差异性来自于无线通信的两大因素：无线电几乎总是半双工的，这意味着它们不能在一个频率上传输的同时侦听该频率的突发噪声；不同站的传输范围可能有所不同。

blog计算机网络整理——介质访问控制子层_衔蝉君的博客-CSDN博客

4.数据链路层交换

网桥：

是工作在数据链路层的一种网络互连设备，它在互连的LAN之间实现帧的存储和转发。

工作原理：

网桥工作在混杂（promiscuous）方式，接收所有的帧；

网桥接收到一帧后，通过查询地址/端口对应表来确定是丢弃还是转发；（散列表/哈希表）

网桥刚启动时，地址/端口对应表为空，采用洪泛（flooding）方法转发帧；

在转发过程中采用逆向学习（backward learning）算法收集MAC地址。网桥通过分析帧的源MAC地址得到MAC地址与端口的对应关系，并写入地址/端口对应表；

网桥软件对地址/端口对应表进行不断的更新，并定时检查，删除在一段时间内没有更新的地址/端口项；

帧的路由过程/具体的转发过程：

（1）目的LAN与源LAN相同，则丢弃帧；

（2）目的LAN与源LAN不同，则转发帧；

（3）目的LAN未知，则洪泛帧，并逆向学习

泛洪算法：对于每个发向未知目的地址的入境帧，网桥将它输出到所有的端口，但它来的那个输入端口除外。随着时间的推移，网桥将会学习到每个目标地址在哪里。一旦知道了一个目标地址，以后发给该地址的帧只被放到正确的端口，而不再被泛洪到所有端口。

后向学习法：网桥工作在混杂模式下，所以，它们可以看得到每个端口上发送的所有帧。通过检查这些帧的源地址，网桥就可获知通过哪个端口能访问到哪些机器。

动态拓扑结构变化：当打开、关闭或者移动机器和网桥时，网络的拓扑结构会发生变化。为了处理这种动态的拓扑结构，一旦构造出一个散列表项后，帧的到达时间也被记录在相应的表项中。当一帧到达时，如果它的源地址已经在表中，那么对应表项中的时间值被更新为当前时间。因此，与每个表项相关联的时间值反映了网桥最后看到该机器发出一帧的时间。在网桥中有一个进程定期扫描散列表，并将那些时间值在几分钟以前的表项都清除掉。

其他概念：

生成树网桥：通过去掉一些链路，由网桥之间的连接组成的图即被简化为一棵生成树。在这棵树上，从每个站到每个其他站恰好只有一条路径。一旦网桥同意这棵生成树，则站之间的所有转发都将沿着这棵树进行。由于从每个源到每个目标都只有唯一一条路径可走，所以不可能产生回路。

中继器：物理层，模拟设备，用于连接两根电缆段，放大信号。

集线器：物理层，有许多输入线路，它将这些输入线路连接起来，在任何一条线路上到达的帧都被发送到其他线路上。

交换机：数据链路层，多端口的网桥。根据帧的目的地址转发，常被用来连接独立计算机。

路由器：网络层。检查数据包的地址，并基于这些地址路由数据包。（当一个分组进入到一个路由器中的时候，帧头和帧尾被剥掉，位于帧的 IP 分组被传递给路由软件，路由软件利用分组的头信息来选择一条输出线路。）

网关：用于两个高层协议不同的网络互连。传输层，应用层。

第五章 网络层

数据链路层保证了数据在相邻节点的可靠传输，网络层关注的是如何将源端数据包经过网络上的节点一路送到接收方。为了实现这个目标，网络层必须知道网络拓补结构，并从中选出适当的路径。

1.网络层设计要点

（1）无连接的服务——数据报网络

每个数据包独立路由，无需提前建立任何设置。IP协议是无连接网络服务的重要范例。每个数据包携带一个目标IP地址，路由器使用该地址来单独转发每一个数据包。

（2）面向连接的服务——虚电路网络

需要首先建立一条从源路由器到目标路由器之间的路径。当建立连接时，路径就被确定下来，并保存在这些中间路由器的表中。一种面向连接的网络服务例子是多协议标签交换（MPLS）。

小节：

2.路由算法

路由算法（routing algorithm）：网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上。

最优化原则：最优路径的子路径还是最优路径。（如果路由器 J 在从路由器 I 到路由器 K 的最优路径上，那么从 J 到 K 的最优路径也必定遵循同样的路由。）

汇集树（sink tree）：作为最优化原则的一个直接结果，从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。

所有路由算法的目标是为所有路由器找到这样的汇集树，并根据汇集树来转发数据包。

最短路径路由算法：（属于静态路由算法）

每一个节点都标出了从源节点沿着已知的最佳路径到达本节点的距离。初始时，所有的路径都不知道，因此所有节点都被标记为无限远。随着算法的不断进行，陆续有一些路径被找到，于是节点的标记可能发生变化，以便反映出更好的路径。

Dijkstra算法：（单源最短路径算法）选择一个起始点，标记出它到邻居的最短距离（初始化）。选择距离起始点最小的点，用它的邻居更新最短距离。剔除掉已选择的点，在剩余点中选择距离起始点最近的点，更新距离。直到能够算出起始点到终点的最短距离。

洪泛算法：（属于静态路由算法）把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。

距离矢量路由：（属于动态路由算法）

每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的链路。这些表通过邻居之间相互交换信息而不断被更新，最终每个路由器都了解到达每个目的地的最佳链路。

得到距离表：公式：
注意式子第二项：是Z到Y的距离（前面应该更新过）与权重比较选最小。

当前点与所有邻居节点交换的路由表：看懂例子。

无穷计数问题：

“坏消息”传播得慢。“好消息”传播的快。

摘自blog

链路状态路由：每个节点都将自己的邻居信息表传给所有节点，每个节点都保存所有节点的邻居信息表，并使用 Dijkstra 计算出本节点到其他所有节点的最短路。

因为距离矢量算法每个节点只与邻居节点交换信息，在面临路由器失效时会出现无穷计数问题。链路状态算法用泛洪的方式分发链路状态包，所以每个节点都知道完整的网络加权拓补图。实际上，算法将完整的拓扑结构分发给了每一个路由器，然后每个路由器运行Dijkstra算法就可以找出从本地到每一个其他路由器的最短路径。

基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃。序号循环使用会混淆，解决办法：使用32位序号。

过程：发现邻居（在每一条点到点线路上发送hello数据包）（LAN复杂引入人造节点代替）；设置链路成本（确定延迟的方法，发送echo数据包，要求对方立即返回，测量时间/2）；构造链路状态包（内容：发送方的标识符、seq、age、邻居列表，列表包括延迟信息即距离）；分发链路状态包（泛洪法，通过序号判断新来的数据包是新的并转发还是旧的需丢弃，age每秒减一，数据包不会无限生存）；计算新路由（Dijkstra）。

距离矢量路由DV和链路状态路由LS的比较：

LS：路由信息全网发送 DV：信息只与邻居交换

LS：使用最短路径优先算法，复杂度O(n^2)；可能存在路由振荡 DV：收敛时间问题，路由循环和无限计数问题。

LS：（路由器故障）可以通告不正确的链接成本，每个节点只计算自己的表 DV：其他节点使用每个节点的表，错误通过网络传播

层次/分级路由：路由器被划分成区域，每个路由器知道如何将数据包路由到自己所在区域内的目标地址，但是对于其他区域的内部结构毫不知情。

广播路由：同时给全部目标地址发送一个数据包。

移动主机路由：为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。

3.拥塞控制

主要RED协议。完整的流量控制应该是网络层（RED 协议）和传输层（TCP 慢启动）配合的任务。

拥塞：网络上有太多的包时，性能会下降，这种情况称为拥塞

拥塞原因：多个输入对应一个输出；慢速处理器；低带宽线路

RED（随机早期检测）：

在所有缓冲空间都精疲力竭之前丢弃数据包。

为了确定何时开始丢弃数据包，路由器要维护一个运行队列长度的平均值。当某条链路上的平均队列长度超过某个阈值时，该链路就被认为即将拥塞，因此路由器随机丢弃一小部分数据包。丢失的数据包起到了传递抑制包的作用，是隐含的。

4.服务质量

资源预留协议（RSVP）：主要功能是预留资源。建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。

缓冲：当一个数据包抵达时，它通常被保留在路由器的缓冲区直到可以从选择的输出线路上发送出去。

抖动（jitter）：网络延迟的变化率。（延迟的变化（即标准方差）或者数据包到达时间的变化。）

漏桶算法：将用户发出的不平滑的数据包流转变成网络中平滑的数据包流。无论注入桶内的速率是大是小，出桶的速率总是恒定的。

令牌桶：漏桶存放令牌，每ΔT秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。发送数据时取出令牌，流量大小受限于积累的令牌数量。一般令牌桶下面会有一个漏桶用于平滑发送速率。（包传输之前必须获得一个令牌，传输之后删除该令牌。）

漏桶算法与令牌桶算法的区别：

流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。

漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。

5.网络互连

隧道技术应用场景：源主机和目标主机所在网络的类型完全相同，但它们中间却隔着一个不同类型的网络。

隧道技术：是一种通过使用互联网络的基础设施在不同网络之间传递数据的方式。

理解：ipv6，外部封装一层ipv4，即可在不同的网络环境中传输，拆掉后即可得到原来的ipv6。

6.Internet的网络层

IPv4协议：

层与层之间数据的传递：上层整段消息内容是对下一层透明的数据。

上层信息封装到下层数据。IP 协议 Internet Protocol 提供尽最大努力的数据传输，不保证可靠。

IP头格式：

IP 数据报由头和正文组成，正文是有效净荷，携带数据**；头由 20 字节定长及一个可选变长组成**，携带此数据报的解释信息。

版本：记录数据报属于什么版本，Ipv4 Ipv6

IHL：IP 头长，单位为 4 字节（32-bit），因为头部至少 20 字节定长，所以值域 5~15。

服务类型

总长度：数字报总长度，单位是 1 字节（8 bit），包括头和数据，最大长度 2^16字节

生存期 TTL：计数单位为跳数，每经过一跳减一，递减到 0 的时候数据包被丢弃并由路由器给源地址发送一个报警包。

协议：记录 IP 分组携带数据的协议类型，即传输层协议的编号，如 TCP、UDP 等

头校验和：对 IP 头信息进行校验，检测数据包穿过网络时是否发生错误。但是由于只校验了头，所以 IP 数据报整体依旧不可靠

源地址和目的地址：源地址可以用于丢包时给源地址发消息；目的地址用于寻找路径时查路由表

选项：可给出对寻址过程中要求必须经过的路由器

DF：Don’t Fragment；MF：More Fragments

分段处理：不同网络的最大帧长的要求可能不同，从而大数据进入小网络需要对大的数据进行分段。DF 表示是否允许分段，DF=1 表示该数据报不允许分段，到达需要分段的地方就丢包返回消息；MF 表示所属于的数据报是否还有更多的段。MF=0 表示当前分段是该数据报的最后一段；分段偏移量表示该分段在整个数据包中的位置，以 8 字节为单位。

头后面加上数据，是更高层协议封装起来的内容。

IP地址：

地址组成：网络号 + 主机号

全0：表示本网络或本主机；全1：表示广播地址；路由器默认广播消息通过。

IP 地址被分为五类。（65536=2^16）

A类：0开头，有2^7个网络。前八位是网络地址。后24为host。

B类：10开头，有2^14个网络。前十六位是网络地址。后16为host，即65536个。

C类：110开头，21+8

D类：1110开头，E类

现使用无类别IP地址+子网掩码（用于区分网络或主机）

子网：分而治之：为了便于管理和使用，可以将网络分成若干供内部使用的部分，称为子网。对外界，该网络还是一个单独的网络。

不论划出几位，都要写八位。

子网（第二章）：分隔一个大型网络得到的一系列结果网络，比如以太网

子网划分 subnetting：在内部将一个网络块分成几个部分供多个内部网络使用，但对外部世界仍然像是单个网络一样。

子网掩码：因为前缀长度仅从 IP 地址无法推断出来，路由协议必须把前缀携带给路由器。前缀长度相当于网络部分中 1 的二进制掩码，它可以与一个 IP 地址进行 AND 操作，以便提取出该 IP 地址的网络部分。

无类域间路由：CIDR

在变长子网掩码的基础上提出的一种消除 ABCDE 类网络划分。为解决 IP 路由表爆炸、IP 地址耗尽。

地址分配的原则是：一个网路只能有一个网络号，进行 IP 地址分配时尽可能连续分配。以牛津大学为例，尽管前面余下 2 10 个空白，但是依旧选择向后

路由/地址聚合：

为了减小路由表长度，将多个小前缀地址块合并为一个大前缀地址块，如上面的三个地址就可以聚合成一个地址，方法是将三者网络号最大公共部分聚合为新网络号

最长匹配原则：在没有聚合时，查路由只需要找到匹配的一项就可以跳到下一跳，但是有聚合以后，需要寻找路由表项中的最长匹配。

路由器的转发过程完善如下：当新的消息进入路由器时，首先进入等待队列，通过一定的调度策略进行调度。调度到这个消息时，获取其目的地址，将目的地址分别与路由表中的每一项网络号的子网掩码进行比对，选取最长匹配的网络表项进行转发。当然，没有查询到匹配的时候，转发到缺省表项，也就是给上一层路由，继续寻找。

NAT：网络地址转换

思想：设定两套 IP 地址,内网相对于外网来说共用一个 public 地址，而在内网中，每台机器对应一个 private 地址。内网之间的通信使用 private 地址，当想要向外网发送消息时，只需将源地址替换为内网共用的 public 地址。当外网向内网发送消息时，因无法区分内网的主机，所以引入了 port。将私有 IP与端口号影射成新的 port，当与这个端口号交互时，根据影射算法可以知道私有 IP。

IP 地址短缺问题解决策略：

①动态分配 IP ②迁移到 IPv6 ③多台共用一个 IP

7.Internet控制协议

ICMP：控制消息协议

为了提高 IP 数据报交付成功的机会，在网络层使用了网络控制报文协议来允许主机或者路由器来报告差错和异常情况。当路由器在处理一个数据包的过程中发生了意外，可通过该协议向数据包的源端报告有关事件。ICMP 是通过向数据包的源地址报告有关事件使网络运行正常。

ARP：地址解析协议

网络层负责寻找路径，而真正实现消息传递的是链路层，所以要实现两层地址之间的映射。（IP地址——以太网地址MAC）

解决统一局域网上的主机路由器的IP地址和硬件地址的映射问题。

已知源 IP、源 MAC 和目的 IP 的情况下怎样获取目的 MAC：

本网（1）首先，每个主机都会在自己的 ARP 缓冲区中建立一个 ARP 列表，以表示 IP 地址和 MAC 地址之间的对应关系。

（2）当源主机要发送数据时，首先检查 ARP 列表中是否有对应 IP 地址的目的主机的 MAC 地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送 ARP 数据包，该数据包包括的内容有：源主机的 IP 地址、源主机 MAC 地址、目的主机 IP 地址。

（3）当本网络的所有主机收到该 ARP 数据包时，首先检查数据包中的 IP 地址是否是自己的 IP 地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的 IP 和 MAC 地址写入到 ARP 列表中，如果已经存在，则覆盖，然后将自己的 MAC 地址写入 ARP 响应包中，告诉源主机自己是它想要找的 MAC 地址。

（4）源主机收到 ARP 响应包后，将目的主机的 IP 和 MAC 地址写入 ARP 列表，并利用此信息发送数据。如果源主机一直没有收到 ARP 响应数据包，表示 ARP 查询失败。

不在本网，则发给默认网关。若目的主机在同一子网内，用目的IP地址在ARP表中查找，否则用缺省网关的IP地址在ARP表中查找。若未找到，则发送广播包，目的主机收到后给出应答，ARP表增加一项

动态主机配置协议（DHCP）：每个网络必须有一个 DHCP 服务器负责地址配置。当计算机启动时，它有一个嵌入在 NIC 中的内置以太网地址或其他链路层地址，但没有 IP 地址。像 ARP 一样，该计算机在自己的网络上广播一个报文，请求 IP 地址。当 DHCP 服务器收到请求，它就为该主机分配一个空闲的 IP 地址并为它指定一段固定的时间。在时间到达前，主机必须请求 DHCP 续订，如果没有提出续订请求或请求被拒绝，主机或许不能使用以前分配给它的 IP 地址。

最短路径开放优先（OSPF）：一种内部网关路由协议，用一个图来表示实际的网络，然后每个路由器使用链路状态方法计算从自身出发到所有其他节点的最短路径。有可能协议会发现多个同样短的路径，在这种情况下，OSPF 记住最短路径集合，并在报文转发期间把流量分摊到这些路径上。

外部网关路由协议（BGP）：是一个在自治系统网络中两个邻近的网关主机间交换路由信息的协议。（考虑政治等因素）

IPv4与IPv6比较，，通讯：

双协议栈（边界路由器进行转化，但会丢失一部分v6信息，有损）、隧道技术。

第六章 传输层

这一层实现的是端到端的可靠的传输，是基于不可靠的网络层之上的。

1.传输协议的要素

寻址：方法：定义传输服务访问点TSAP（Transport Service Access Point），将应用进程与这些TSAP相连。在Internet中，TSAP为（IP address, local port）。

其他人如何知道你的端口号：有一些常见的端口地址；从名字服务器/目录服务器获得TSAP。

建立连接：

三次握手：

（1）A 发出序号为X的CR TPDU；

（2）B 发出序号为Y的CR TPDU并确认A的序号为X的CR TPDU；

（3）A 发出序号为X+1的第一个数据TPDU，并确认B的序号为Y的CR TPDU。

三次握手方案解决了由于网络层会丢失、存储和重复包带来的问题。

释放连接：

对称式和非对称式。

非对称式：一方释放连接，整个连接断开，存在丢失数据的危险

对称式：由于两军问题的存在，可以证明不存在安全的通过N次握手实现对称式连接释放的方法

但是在实际的通信过程中，使用三次握手 + 定时器的方法释放连接在绝大多数情况下是成功的。

a，正常的三次握手释放

b，最后主机 1 发出的 ack 丢失的情况，这时候，当主机 2 的计时器超时后，主机 2 就会释放连接。

c，主机 2 给主机 1 的 DR的应答丢失了，这种情况下，当主机 1 的计时器超时后，主机 1 会重新发送 DR。

d，是主机 2 给主机 1 的 DR的应答和主机 1后续的 DR 都丢失了，这种情况下，主机 1 经过 N 次重传之后，就会放弃，并且释放连接；而主机 2 在计时器超时之后也会释放连接。

流控：

传输层利用可变滑动窗口协议来实现流控。可变滑动窗口协议，是指发送方的发送窗口大小是由接收方根据自己的实际缓存情况给出的。

缓存：

由于网络层服务是不可靠的，传输层实体必须缓存所有连接发出的TPDU，而且为每个连接单独做缓存，以便用于错误情况下的重传。

2.UDP

UDP（User Datagram Protocol），用户数据报协议。

特点：（1）UDP 是无连接的，不可靠的；（2）分组头部开销小。TCP 有 20 字节的头部开销，UDP 只有 8 字节。
布局：

（3）UDP 尤其适用的一个领域是在客户-服务器的情形下。

（4）UDP 的一个应用是 DNS<程序与 DNS 服务器之间>。

（5）UDP 不考虑流控制、错误控制，在收到一个坏的数据段之后它也不重传。所有这些工作都留给用户进程。

3.TCP

TCP服务模型：

TCP服务由发送端和接收端创建一种称为套接字的端点获得。（套接字：IP地址+端口）

一个TCP连接就是一个字节流，而不是消息流。

TCP协议：

头部：

TCP连接建立：

通常在第三次发送消息的时候，TCP 数据段里已经携带了数据，故将 SYN 位置为了 0。

若两个主机同时试图建立彼此间的连接，则只能建立一条连接。

TCP连接断开：

单向连接的释放：释放连接时，发出FIN位置1的TCP段并启动定时器，在收到确认后关闭连接。若无确认并且超时，也关闭连接。

三次握手释放：

TCP滑动窗口协议：

延迟确认：将确认和窗口更新延迟50毫秒，希望能够获得一些数据免费大在过去。

Nagle算法：当数据每次以很少量方式进入发送端时，发送端只是发送第一次到达的数据字节，然后将其余后面到达的字节缓冲起来，直到发送出去的那个数据包被确认。然后将所有缓冲字节放在一个TCP段中发送出去，并继续缓冲字节，直到下一个段被确认。（任何时候只有第一个发送的数据包是小数据包）

低能/愚笨窗口综合症：Clark。另一个降低TCP性能的问题。

Clark的解决方案，禁止接收端发送只有1个字节的窗口更新段。

TCP拥塞控制：

拥塞控制的本质是降低发送方的发送速率。拥塞控制实际上是由网络层（RED）和传输层（TCP 慢启动）共同完成的。

丢弃数据包是判断发生拥塞的重要依据。

拥塞窗口CW：描述网络的传输能力

流量控制窗口FW：描述对方的接收能力

慢启动

一开始通过成倍增加（指数级）拥塞窗口的大小不断试探网络连接情况，当到达阈值的时候，开始线性地增长拥塞窗口的大小。当一次超时发生的时候，将阈值设置成为当前拥塞窗口的一半，而拥塞窗口被重置为初始的值。

网络层和传输层是如何合作完成拥塞控制：

当网络中路由器的被使用缓冲区的大小到达路由器的阈值的时候，路由器开始执行 RED协议，随意丢弃某些分组，被丢弃的分组的发送方因此会超时，这时通过 TCP 慢启动会降低发送方速率。

第七章 应用层

域名系统(Domain Name System)：一种层次的，基于域的将主机名(域名)映射成 IP的命名方案。

顶级域名主要包括通用的(edu,gov,com)和国家或地区的(cn,uk)。

HTTP：应用层常见协议。超文本传输协议（Hyper Text Transfer Protocol，HTTP）是一个简单的请求-响应协议，它通常运行在TCP之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。

习题

计算机网络各层网络设备（中继器、集线器、网桥、交换机、路由器、网关）总结

CSMA/CA 协议 ( 载波监听多点接入 / 碰撞避免 协议 | CSMA/CA 协议工作原理 | CSMA/CD 协议 与 CSMA/CA 协议对比 )

14-15

概念性（非名词解释）：

1.NAT：

网络地址转换协议。在网络内部使用私有地址（private），在网络外部使用公用地址。使用源端口号+私有IP地址映射为新的源端口号，私有IP转换为公用IP。解决IP地址短缺问题的手段。

2.ADSL：

非对称用户数字线路。将线路带宽划分为多个信道，其中一大部分用于下行数据，一小部分用于上行数据，保留单独的语音信道，并使用几个信道隔离数据信道和语音信道。

3.隧道技术：

当两端网络属于同一种网络时，中间网络采用的一种封装技术。在中间网络使用新的协议头驱动，在两端网络使用原有协议头驱动。

4.带宽：

单位时间可以传递的数据位数；或对介质而言没有明显衰减的一段频率范围。

5.协议：

通信双方为了正常通信所进行的一组规则或约定的集合。

选择填空知识点：

1.计算机网络的目的是实现资源共享。

2.传递分组时，每一个中间路由器都会完整地接收、保存，等到线路空闲时再转发出去的技术称为存储-转发。

3.TCP连接是面向字节流的。

4.以太网卡（MAC）地址的长度是48位。

5.属于第三层（网络层）的网络设备是路由器。

物理层：中继器、集线器

数据链路层：网桥、交换机（定义，数据链路层，多端口的网桥。根据帧的目的地址转发，常被用来连接独立计算机。）

网络层：路由器（定义，检查数据包的地址，并基于这些地址路由数据包。）

应用层（七层模型的最后一层）：网关

6.将一个分组发给所有机器的操作模式称为广播。

7.电子邮件常用到的协议：SMTP、POP。

8.IP提供的服务是尽最大努力传递。（IP在网络层，不保证可靠）

9.网络中，用于报告错误和测试的协议为ICMP。（控制消息协议）

10.网络按照覆盖范围，分为局域网、城域网、广域网。

11.服务质量用来描述网络能够提供的服务能力或网络应用的要求，网络中经常使用的服务质量参数有带宽、延迟、延迟抖动、丢失率。

12.无线局域网对应的IEEE标准为IEEE802.11，宽带无线网络对应的IEEE标准为IEEE802.16。

13.网络中常见的调制方式调频、调幅、调相。

14.TCP协议中校验和校验的范围包括TCP头、数据、伪TCP头。

15.在以太网中发生冲突后，经常采用二进制指数后退算法来解决冲突。

16.IP协议中有一个TTL字段，用于限制分组在网络上的存活时间，避免分组无休止的在网络上循环。

计算简答：

1.CRC校验

生成式是除数。发送数据是要增加位数的。校验和即最后的余数。

2.漏桶和令牌桶的工作原理：

漏桶：需发送的数据放到一个称为漏桶的缓冲区，以给定速率往外发送。溢出时丢失数据。

令牌桶：保存的是发送数据的权利，可以支持高速传输。发送时消耗令牌，溢出时丢失令牌。

3.介质访问控制：

（1）什么是介质访问控制问题

介质访问控制简称MAC。 是解决共用信道的使用产生竞争时，如何分配信道的使用权问题。

（2）以太网中采用的介质访问控制协议

CSMA/CD。

工作原理：概括为1先听后说，边听边说；2一旦冲突，立即停说；3等待时机，然后再说。

在发送数据前，先监听信道是否空闲，若信道忙，则等待；若信道空闲，则把准备好的数据发送到信道上。在发送数据的过程中，工作站边发送边监听信道，看是否自己发送的数据有冲突。若无冲突，则继续发送直到全部数据传完为止；若有冲突，则立即停止发送数据，但是要发送一个加强冲突信号，以便使网络上所有工作站都知道网上发生了冲突，然后，等待一个预定的随机时间，且在信道为空闲时，再重新发送未发完的数据。

（可能是特点：满足最小帧长 冲突时使用二进制指数后退算法）

（3）无线局域网中采用的介质访问控制协议

CSMA/CA。

工作原理：

① 检测信道 : 发送数据前 , 检测信道是否空闲 ;

② 信道空闲 : 发出 RTS ( Request To Send ) , RTS 包括发射端地址 , 接收端地址 , 发送持续时间等信息 ;

③ 信道忙 : 等待 ;

④ 接收端收到 RTS : 发送 CTS ( Clear To Send ) 响应 ;

⑤ 发送端收到 CTS : 同时执行以下两个操作 ;
发送数据 : 开始发送数据帧 ;
预约信道 : 告知其它站点 , 自己要传输数据 , 并给出传输时间 ;

⑥ 接收方接收到数据后 , 使用 CRC 循环冗余校验码校验数据是否正确 , 如果数据正确 , 返回 ACK 确认帧 ;

⑦ 发送方接收到 ACK 确认帧 后 , 才进行下一帧的发送 , 如果没有收到 , 则一直重传 , 直到16次失败为止 ; ( 二进制指数退避算法 )

4.链路状态路由协议

（1）工作原理：

每台路由器周期或触发地将自己的邻接信息发送给网络上所有其他路由器。每台路由器根据来自所有节点的邻接信息形成一张完整的网络拓扑图，求取自己到所有结点的最短路径，完成自己的路由表。

（2）采用了什么方法来提供较少代价、可靠的信息扩散

接受方发送反馈信息来确保可靠；引入计时器防止丢失某一帧导致发送方持续等待；通过序号保证每一帧顺序和防止重复接收。

论述题：

1.滑动窗口协议是数据链路层的一个重要协议，提供在一条不可靠的线路上可靠的数据递交。

（1）发送窗口和接收窗口的含义

发送窗口：已经发送，没有收到确认的帧的集合

接收窗口：可以接受的帧的集合

（2）滑动窗口如何提供流量控制

发送方可以一直发送直到发送缓冲区满，此时发送方必须停止发送，只有发送缓冲区的一部分为空时才能继续发送。而缓冲区的清空依赖于接收方发回的确认。接收方可以通过控制发送确认的速率来实际控制发送方的发送速率，从而避免被过快的发送方淹没达到流量控制的目的。

（3）滑动窗口如何实现差错控制

接受方发送反馈信息来确保可靠；引入计时器防止丢失某一帧导致发送方持续等待；通过序号保证每一帧顺序和防止重复接收。

（4）一种滑动窗口协议的工作过程

发送窗口大小为1，接收窗口大小也为1。两个数据链路层一个先开始，发送第一帧。当这一帧到达时，接收方的数据链路层检查该帧，看它是否为重复帧。如果它正是所期望的那一帧，就将它传递给网络层。然后接收窗口向前滑动，并发送一个确认帧， 确认域包含了最后收到的无错误的帧序列号，如果该序列号和正在发送的帧序列号一致， 则发送方知道存储在buffer中的帧已经处理完毕。于是它从网络层获取下一帧。无论什么时候，只要发出一帧就要返回一帧。

2.拥塞控制

（1）RED协议的工作原理

当某条链路上的平均队列长度超过某个阈值时，该链路就被认为即将拥塞，因此路由器随机丢弃一小部分数据包。

（2）TCP慢启动协议的工作原理

首先发送一个分组，确认及时回来则加倍发送数据，一直重复直到确认不能按时回来。取一半作为阈值，从一个分组开始，在达到阈值之前，按照指数增加；达到阈值，按照线性增加。

（3）为什么两者的配合能够在一定程度上解决拥塞

当网络中路由器的被使用缓冲区的大小到达路由器的阈值的时候，路由器开始执行RED协议，随意丢弃某些分组，被丢弃的分组的发送方因此会超时，这时通过 TCP 慢启动会降低发送方速率。

3.路由/地址聚合技术（无类域间路由）

（1）CIDR 地址块中的地址数一定是 2 的整数次幂

（2）路由器的转发过程完善如下：当新的消息进入路由器时，首先进入等待队列，通过一定的调度策略进行调度。调度到这个消息时，获取其目的地址，将目的地址分别与路由表中的每一项网络号的子网掩码进行比对，选取最长匹配的网络表项进行转发。当然，没有查询到匹配的时候，转发到缺省表项，也就是给上一层路由，继续寻找。

4.ARP协议

（1）目的：地址转换协议，完成从IP地址到MAC地址的转换。

（2）ARP协议的工作内容

发送方发送一个ARP广播帧，传递到网络上所有节点，询问IP地址对应的MAC地址。

如果接收方在同一个网络内，则接收方回一个ARP应答帧；

如果网络连接的路由器端口通过发送方和接收方的IP地址判断接收方不在同一个网络，则使用自己的MAC地址应答，作为接收方的代理。

（3）工作内容详细描述

··主机A广播，该广播包携带B的IP地址，一旦B发现自己的IP地址与其一致，它就会用自己的MAC地址作为应答，使A得到自己的MAC地址。

··主机A广播，但是发现目的IP地址和自己不在一个子网。于是它转而请求路由器的MAC地址，把数据传送过去，再由路由器与子网外的主机进行交互。在路由表找到对方所属的子网后，在该子网内广播找到B的MAC地址。

隐藏站点和暴露站点问题。由于每个设备的信号不能保证 覆盖所有网络节点。

综合题：

1.IP包TCP包

首先明确，结构：数据帧 { IP头 { TCP/UDP头 { Data } } }

IP头和TCP头均为20字节

包中内容十六进制，对应的源IP地址是第四个四字节，目标IP是第五个四字节

将十六进制的8个数字/字母转换为二进制，一个数字对应4位，从而对应到十进制表示的IP

总长度在

题目中给出包结构，可以看bit

IP包头的长度：

计算时，5*4=20字节

TCP包头的长度：

判断那个分组TCP段携带了数据：

根据IP包头可以计算出总长度，减去IP包头和TCP包头的长度，若有剩余，则携带了数据。

判断IP分组在以太网传输过程中哪些需要填充：

以太网帧的数据部分长度范围为46~1500字节，总长度小于46字节的IP分组在二层封装时需要填充。计算IP头中的总长度判断是否小于46即可。

判断哪个分组完成了主机和服务器的TCP建立过程：

根据TCP报头中的SYN位和ACK位是否置1可以判断TCP连接的建立过程。建立过程即三次握手。需要主机发出的SYN（位置为1）（Seq为A的序列号x），服务器响应SYN+ACK（SYN位置为1，ACK位置为1）（Seq为B的序列号y，ack值为x+1），主机响应的ACK（SYN置为0，ACK位置为1）（Seq为x+1，ack值为y+1）。

（SYN置为1，就表示这是一个连接请求和连接接收报文）

（FIN=1时，表明此报文段的发送方的数据已发送完毕）

判断发送的数据的编号范围：

即找到开始发送数据的包（三次握手后），此时的Seq为编号开头，截至是下一个确认包ack值减一。ack为期望对方下一个发送的序列号。

主机H发送给服务器S的数据都被接收了吗：

都接收了，因为确认值（ack）为。。。，为接到的最后数据编号加1。

主机H和服务器S为本次TCP连接预留的资源各是多少

题目说明了，就是window size，在TCP包头中。表示格式为：0X4380

TTL：

不严谨。

转为十进制，相减得到跳数。

18-19

概念性：

1.汇集树：

sink tree，所有节点到某个给定节点的最短路径的并称为此节点的汇集树。

2.DNS：

一种分布式存储和访问的域名系统。支持将域名映射为相应IP地址的系统。

3.TTL：

规定一个分组在网络上的生存时间，避免分组在网络上无休止的循环。

选择填空知识点：

最大传输速率

回退N如何重传

一些协议里面选某个层的协议（RIP，PPP，…）

RIP：路由信息协议，网络层。

PPP：点对点协议，数据链路层。

SLIP：串行线路网际协议，网络层

简答题：

1.路由转发问题

使用子网掩码与分组携带的目标地址“按位与”，若与掩码相匹配，且子网掩码位数最长，则使用该表项的下一跳转发。

（根据路由表中掩码，如22，即前22位均为1。写出二进制表示，将目标地址写成二进制表示，两者按位相与。若运算后，化成十进制，与路由表项某一个相同，则使用改表项的下一跳。若有多个相同，选择子网掩码位数大的。即最长前缀优先匹配。）

2.电路交换和分组交换

（虚）电路交换：首先建立一个连接（一条虚电路），在所建立的连接上传递数据，数据传输完毕后拆除连接。是一种面向连接的技术。

（包）分组交换：每个分组携带完整的目的地址，独自选择路径。

比较：电路交换收费按分钟计，分组交换按包计；电路交换需要建立连接，分组交换不需要建立连接。

3.1位滑动窗口的过程（有图）

时刻a，初始化，发送方准备发送第0帧，接收方准备接收第0帧；

时刻b，发送方发送第0帧并等待其确认，接收方准备接收第0帧；

时刻c，发送方等待第0帧的确认，接收方正确接收第0帧，发回第0帧的确认，准备接收第1帧；

时刻d，发送方收到第0帧的确认，准备发送第1帧，接收方准备接收第1帧。

4.网桥的工作过程，如何建立MAC表（ARP）

（交换机，数据链路层，多端口的网桥。）

网桥工作在数据链路层，将多个LAN连接起来，通过检查数据链路层地址转发帧。

网桥内部配备着一个大的表，这个表列出了所有的可能目的地址和它隶属的输出端口。当一帧到达时，网桥对目的地址进行查询，如果目的地址端口和源端口相同，则丢弃该帧；如果不同，就转发该帧到目的端口；如果目的端口未知，则使用洪泛算法将帧发送到所有的端口，除了它入境的那个。

只问网桥/交换机的工作过程：

交换机内存储着节点MAC地址与端口的映射关系。当一个帧到来时，查找相应的端口转发。映射表通过自学习建立，通过不断刷新维护。

5.NAT工作过程

（网络地址转换协议）

当一个节点需要向外网发送数据时，将内网的私有IP地址转换为公有IP地址，并将私有IP地址、传输层端口号映射为新的传输层端口号。当接收一个数据时，通过映射关系查找对应的私有IP地址及传输层端口号，重新封装传递。

论述题：

1.距离矢量路由和无穷计算

距离矢量路由：每台路由器周期性的将自己的距离矢量发送给所有邻居。每台路由器根据邻居的距离矢量计算出自己新的路由表。

无穷计算：好消息传播得快，坏消息传播得慢。

。。

2.TCP

（1）TCP建立连接的机制，说明这种机制如何避免重复连接

TCP使用三步握手协议建立连接：连接请求方选择一个合法的序列号，连接应答方选择一个合法的序列号并确认连接请求方得序列号，连接请求方确认应答方的序列号。根据序列号、确认号等判断重复分组。

（2）TCP流量如何控制，从网络状态和接受者缓存两个角度（就是拥塞窗口和流量窗口两个角度）

流量控制包括两个窗口：反映接收方接受能力的window size，以及反映网络传输能力的拥塞窗口，依据慢启动等方法赋值。最终发送的最大速率取两个窗口值得最小值。

15-16

概念性：

1.广播：

任何一台机器发出的数据包能被其他人任何机器收到。每个数据包的地址字段指定了预期的接收方，只有预期的接收方会做出应答，其他的机器会忽略这个数据包。

2.组播：

将数据包发给一组机器，即所有机器的一个子集。

3.多路复用：

使多个信号可以共享同一传输路线，分为频分复用、波分复用、时分复用。

计算题：

1.子网掩码、主机范围

IP地址=网络号+主机号，子网掩码标识了哪几位为网络号。前几位为1，则网络号为几位。将题给IP地址与子网掩码按位相与，得到的就是这个IP地址的网络号。主机范围：该网络号+1~主机号全置为1-1（排除‘主机号’全0全1的）

2.信道数据传输速率

eg，采样率为2400/s，如果采用16种相位、8种振幅、8种频率的信号调制技术，计算在这个信道的假定一个信道的数据传输速率。

首先，使用奈奎斯特定理（无噪声）最大速率=2Blog2V，香农定理（有噪声）最大速率=Blog2（1+S/N）。

B表示带宽。速率单位bps。

V一般指离散级数，即可识别的信号个数，几种码元。题中相位、振幅等相乘，为V。

采样率与带宽的关系：

带宽，信号的最高频率与最低频率的差值。

采样率，采样频率必须大于被采样信号带宽的两倍，

所以本题，最大带宽1200。

简答题：

1.滑动窗口协议

分为一位滑动窗口协议、回退N协议（GBN）、选择重传协议。

GBN：发生了超时现象，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数为4。

需要重传最后一个确认的帧以后的所有帧。尽管没有1号帧的确认，但3号收到了就说明1号收到了，只是确认包丢失了。

2.DNS工作原理

应用程序调用名为解析器的库程序，将名字作为参数传递给此程序。解析器向本地DNS服务器发送一个包含该名字的请求报文；本地DNS服务器查询该名字，并且返回一个包含该名字对应IP地址的响应报文给解析器。查询报文和响应报文都作为UDP数据包发送。

3.路由协议

（1）说明一个IP分组到达一台路由器后，其主要的转发过程

当新的消息进入路由器时，首先进入等待队列，通过一定的调度策略进行调度。调度到这个消息时，获取其目的地址，将目的地址分别与路由表中的每一项网络号的子网掩码进行比对，选取最长匹配的网络表项进行转发。当然，没有查询到匹配的时候，转发到缺省表项，也就是上一层路由，继续寻找。

（2）分布于路由器的路由表中可能存在环路，IP协议是如何应对这一问题的？

设置一个最大跳数，使得跳数减为0时，数据包丢弃，防止陷入环路。

4.TCP协议实现端到端的可靠的数据传输，其数据发送速率取决于两个方面:网络传输能力,通信双方的处理和缓存能力。这两种能力分别使用拥塞窗口、流量控制窗口来描述。

（1）流量控制窗口大小的取值是如何实现的?

接收端可以缓冲的字节数

（2）拥塞窗口大小的取值是如何实现的

发送端可以往网络发送的字节数

（3）如何使用这两个窗口的取值来确定当前数据的发送速率的

取两者之间的最小值然后除连接往返时间

13-14

概念性

1.P2P:

对等通信，指两个主机在通信时并不区分哪–个是服务请求方还是服务提供方，只有两个主机都运行了对等链接连接，他们就可以进行平等的对等连接通信。

计算题

1.曼彻斯特编码等

简答题

1.发生冲突后，二进制指数后退算法

2.TCP

（1）建立连接

TCP使用三步握手协议建立连接：连接请求方选择一个合法的序列号，连接应答方选择一个合法的序列号并确认连接请求方得序列号，连接请求方确认应答方的序列号。

（2）释放连接

单向连接的释放：释放连接时，发出FIN位置1的TCP段并启动定时器，在收到确认后关闭连接。若无确认并且超时，也关闭连接。

四次挥手释放：首先主动释放的一方发送连接释放请求；然后被动释放的一方收到主动释放发送的请求后，发送确认报文；接着被动释放方再次发送连接释放请求报文；最后主动释放方收到被动释放方的释放请求后发送确认报文即可。

3.回退 N协议和选择性重发协议在两个窗口上有何异同

回退：发送窗口大小>1，接收窗口大小=1

选择性重发：发送窗口大小>1，接收窗口大小>1

4.电话系统

1)本地回路使用到的主要技术是什么?有哪些实现方式?

2)主干线使用到的主要技术是什么?有哪些实现方式?

3)交换局使用到的主要技术是什么?有哪些实现方式?

4)电话系统为什么不使用平面系统，而是使用分层系统?

1)数字信号:不归零、不归零逆转、曼彻斯特编码、差分曼彻斯特编码。模拟信号:幅移键控、频移键控、相移键控、相对调相。

2)多路复用:时分复用、频分复用、波分复用。

3)交换局:电路交换、包交换。

4)因为将每台电话和其他所有电话都连接起来的模式是不现实的，使用平面系统，电话难以管理，浪费人力物力。

综合题

在山大校园网输入xxx来访问剑桥大学计算机系的网站。

（1）指出通信过程中各个层次使用到的几个重要的地址，以及这些地址之间的转换

（2）根据网络参考模型，描述数据在各个层次的封装过程

（3）指出通信过程中各个层次使用到的主要网络协议，解释这些协议在通信中完成的功能

应用层：HTTP:WWW访问协议，DNS:域名解析服务
传输层：TCP:HTTP提供可靠的数据传输，UDP：DNS使用UDP传输
网络层：IP:IP包传输和路由选择，ICMP：提供网络传输中的差错检测，ARP：将本机的默认网关IP地址映射城物理MAC地址

在浏览器输入xxx，DNS获取iP地址，在应用层将要发送的数据内容形成了应用层的报文data,发送到传输层。

传输层，，，然后待发送的数据段发送到网络层。

网络层开始负责将这样的数据包在网络上传输，如何穿过路由器，最终到达目的地址。在这里，根据目的ip地址，就需要查找下一跳路由的地址。首先在本机，要查找本机的路由表。如果是在局域网中,每台电脑都有自己的私网IP,在对外传输的时候,会经过NAT转换,改成路由器的公网IP。

数据链路层，MAC寻址。

断开连接。

15-16

简答题

1.数据链路层协议实现相邻节点之间可靠的数据传输。根据所学任何一种数据链路层协议， 简述实现可靠传输的过程。

滑动窗口协议。

过程见上。

2.CAMA/CD

（1）CSMA工作原理

当有一个站想发送数据时，先侦听信道上是否有其他站正在传递数据，如果没有，它就发送数据，如果有，就等到信道变成空闲，然后发送一帧，如果发生冲突，就随机等待一段时间再重复上述过程。

（2）CD协议

不仅在发送前侦听信道，在发送过程中也侦听信道，一旦检测到冲突就立即停止传输信息，等待一段时间再发送。

（3）CSMA/CD 协议可以直接应用到无线局域网吗?为什么?

不能。无线通信系统通常不能检测出正在发生的冲突。无线电传输范围有限，无线局域网中的站无法给其他所有站发送帧，也无法接收到来自所有站的帧。

综合题

（3）外部网关路由协议（BGP），它的报文被封装到TCP协议段中进行运输。