计算机网络

谨以此讲义送给老王，感谢他给了我大学四年中唯一的一门满分课程，希望能永远看见他开着奔驰买菜的样子

第一章 计算机网络体系结构

networks system

计算机网络概述

• 一般认为，计算机网络是一个将分散的、具有独立功能的计算机系统，通过通信设备与线路连接起来，由功能完善的软件实现资源共享和传递的系统
• 计算机网络按分布范围可分为广域网(WAN)、城域网(MAN)、局域网(LAN)和个人局域网(PAN)
• 计算机网络按拓扑结构可分为星形网络、总线形网络、环形网络、网状形网络
• 计算机网络的性能标准包括如下几种：
  1. 时延带宽积 = 传播时延 * 信道时延
  2. 吞吐量：单位时间内通过某个网络的数据量
  3. 信道效率（信道利用率）：一个发送周期的时间内，有效地发送数据所需要的时间占整个发送时间的比率
  4. 信道吞吐率 = 信道利用率 * 发送方的发送速率

计算机网络结构

• 协议：对等层通信的规则，包括语法、语义、同步。下层协议对上层来说是透明的
• 接口：相邻两层交换信息的连接点
• 服务：下层为紧邻的上层提供的功能调用
• 第n层的实体不仅要使用n-1层提供的服务，实现自身定义的功能，还要向n+1层提供本层的服务
• 分层结构的优点是：各层之间相对独立、灵活性好、易于抽象和标准化

OSI参考模型和TCP/IP模型

• OSI模型由下至上包括物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。其中会话层功能是建立、管理进程间的会话。表示层功能是数据压缩、加密和解密。这两个层存在感稀薄，所以拿出来说下
• TCP/IP模型由下而上包括：网络接口层、网际层（仅支持无连接）、传输层（支持无连接和面向连接）、应用层。其中网络接口层对应OSI的物理层和数据链路层，网际层对应网络层，传输层对应传输层，应用层对应会话层、表示层、应用层
• TCP/IP与IP模型的比较：
  相同点：都采用分层的体系结构、都是基于独立的协议栈的概念、都可以解决异构网络的互联
  不同点：1. OSI精确定义了服务、协议和接口，而TCP/IP则没有 2.OSI不偏向任何协议，通用性好，而TCP/IP只适用于TCP/IP的协议栈 3.TCP/IP考虑到了多种易购网互联问题，并将网际IP作为一个单独的重要层次，而OSI只考虑用一种标准的公用数据将不同的系统互联 4.OSI在网络层支持无连接和面向连接，在传输层仅支持面向连接，而TCP/IP在网际层仅支持无连接，在传输层支持无连接和面向连接
• OSI定义的很全面，就是实现难，所以大家都用TCP/IP

第二章 物理层

physics level

奈斯奎特定理和香农定理

• 码元传输速率表示单位时间内数字通信系统所传输的码元个数，单位是波特(Baud)
• 信息传输速率表示单位时间内数字通信系统传输的二进制码元个数，单位是b/s
• 奈斯奎特定理指出无噪声的信道中极限码元传输速率为2W Baud。其中W是信道的带宽，单位为Hz。若用V表示每个码元离散点平的数目，则极限数据率 = 2Wlog(V) 单位为b/s
  显然可通过奈斯奎特定理得到以下结论：
  1. 在任何信道中，码元传输速率有上限
  2. 信道频率越宽，就可以用更高的速率进行码元的有效传输
  3. 奈式准则给出了码元传输速率的限制，但是并没有给出信息传输速率的限制
• 香农定理给出了带宽受限且有高斯白噪声干扰的信道的极限数据传输速率，即
  极限数据传输速率 = W * log(1 + S/N) 单位为b/s，其中W为信道带宽，S为信道平均功率，N为信道内高斯噪声功率，S/N为信噪比，信噪比 = 10lg(S/N) 单位为db
  显然可通过香农定理得到以下结论：
  1. 信道带宽或信道中的信噪比越大，信息的极限传输速率就越高
  2. 对一定的传输带宽和一定的信噪比，信息传输速率的上限就确定了
  3. 只要信息的传输速率低于信道的极限传输速率，就一定能找到某种方式来实现无差错的传输
  4. 香农定理得出的为极限信息传输速率，实际信道能达到的传输速率要比他低不少

编码与调制

• 非归零码简称NRZ。非归零反向编码简称NRZI，用两个周期间的跳变表示0
• 曼彻斯特编码和差分曼彻斯特编码都自带时钟。曼彻斯特编码的前半个周期代表真值，差分曼彻斯特编码用两个周期间的电平跳变表示0
• 以太网使用曼彻斯特编码
• 要将模拟信号转化为数字信号，设原始信号最大频率为f，那么采样频率必须大于等于2f才能保证完全保留原始模拟信号的信息

电路交换、报文交换和分组交换

• 电路交换：在通信指前两个节点之间要建立一条专用的物理通信路径，该路径由通信双方的交换设备和链路逐段连接而成
• 报文交换：以报文为数据交换的单位，在交换节点采用存储转发的传输方式
• 分组交换：将一个大的数据报分为若干小数据块，加上一些必要的控制信息构成分组，然后采用存储转发的方式传输
• 一般各种延时的计算用画图可解

数据报与虚电路

• 分组交换根据其通信子网向端点系统提供的服务还可分为面向连接的虚电路方式和无连接的数据报方式
• 数据报就是各个分组会通过不同的路由到达目的地，不同的分组会走不同的路径，到达的顺序也不确定
• 虚电路就是通信双方建立一条逻辑通路，所有分组在这条通路上有序传输。逻辑通路不是专用的，和电路交换并不一样

物理层接口和物理层设备

• 双绞线的绞合是为了减少对相邻导线的电磁干扰
• 光纤是通过光的全反射实现的，详见人教版物理选修3-4
• 物理层的接口特性包括以下几个：
  1. 机械特性：主要定义物理连接的边界点，即接插装置，如物理连接采用的规格、引线的数目、引脚数目和排列情况等
  2. 电气特性：线路上信号的高压低压、阻抗匹配、传输速率和距离限制等
  3. 功能特性：指明某条线路上出现的某一电平的电压有何种意义
  4. 过程特性：指明对于不同功能的各种可能事件的出现顺序
• 中继器是物理层设备，他的作用是将信号整形并放大再转发出去，来扩大网络的传输速率。中继器不分割子网
• 集线器是一个多端口中继器，把从一个端口接到的信号向其他所有端口转发出去。显然，集线器不分割冲突域，也不分割广播域

第三章 数据链路层

data link level

零比特填充法

• 透明传输指不管所传输据是什么样的比特组合，都应该能在链路上传输
• HDLC的标志字段F为01111110，通信过程中检测到F代表帧的开始，在检测到代表帧的结束
• HDLC采用零比特比特填充法使一帧中除了F之外不会出现6个连续的1，再发送端检测到比特流中有5个连续的1后，立即插入一个0；在接收端检测到有5个连续的1后将后一个0删除。

流量控制、可靠传输与滑动窗口机制

• 流量控制指接收方对发送方发送数据的限制
• 可靠传输通常使用确认和超时重传两种机制完成。当确认信息捎带在一个回复帧中时，称为稍待确认。
• 自动重传请求(ARQ)指通过接收方请求发送方重传出错的数据帧来恢复出错的帧。传统自动重传请求分为：停止等待、后退N帧、选择重传
• 在停止等待协议中，发送方发送单个帧后必须等待接收方确认后才能发送下一帧。在停止等待协议中，可能发生的差错有：数据帧丢失、数据帧损坏被接受方简单丢弃、确认帧被破坏。停止等待协议的发送窗口=接收窗口=1。
• 后退N帧(GBN)帧工作原理：发送方连续发送帧，当发送方发现某一帧超时后仍未收到确认嘻嘻，则认为该帧出错或被丢失，应重发该帧之后的所有帧。接收方只按照顺序接受帧，当接收方检测到失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后所有未被确认的帧。后退N帧协议若采用n比特对帧编号，则接收窗口=1，1<=发送窗口<=2^n - 1
• 选择重传(SR)只重传出现差错的数据帧或超时的数据帧，这要求接收方有相当容量的缓冲区，用于暂存未按顺序正确收到的帧。此外，选择重传协议提供了更有效的差错处理策略：一旦接收方怀疑帧出错，就会发一个否定帧NAK给发送方，要求发送方对NAK中指定的帧进行重传。在选择重传中若采用n比特对帧编号，则发送窗口<=接收窗口<=2^(n-1)
• 显然，停止等待和GBN接收帧是有序的，而SR接收帧是不确定的

介质访问控制

• 介质访问控制所要完成的主要任务是为使用介质的每个结点隔离来自信道上其他结点所传送的信号。常见的介质访问控制方法有：信道划分介质访问控制、随机访问介质访问控制和轮询访问介质访问控制，其中前者是静态划分信道的方法，后两者是动态划分信道的方法
• 信道划分介质访问控制分为以下几种：频分多路复用(FDM)、时分多路复用(TDM)、波分多路复用(WDM)、码分多路复用(CDM)，显然这些都不会发生碰撞
• 码分多址(CDMA)是码分复用的一种。具体思想是：假设A发给C的向量是S，B发给C的向量是T，那么计算S与S+T的内积，将其除以向量的维数，若为1则代表A发送的是1，为-1在代表A发送的是0；同理，将T与S+T进行上述操作可得到B发送的内容。需要注意的是，S与T须是正交的
• 常用的随机访问介质访问控制分为如下几种：ALOHA、CSMA、CSMA/CD、CSMA/CA。其中CSMA又可细分为1-坚持CSMA、非坚持CSMA、p坚持CSMA
• CSMA/CD工作流程可简单概括为：先听后发，边听边发。冲突停发，随机重发
  1. 载波监听：发送前先侦听，如果空闲则发送，不空闲则继续侦听，等待空闲
  2. 碰撞检测：适配器边发送数据边检测冲突，检测到冲突时停止传送帧，取而代之传送一个拥塞信号，采用截断二进制指数退避算法等待一段随机时间后重新侦听。显然CSMA/CD无法进行全双工通信
  3. 争用期：也称碰撞窗口，设单程传播时延为τ，则争用期为2τ
  4. 最小帧长 = 总线传播时延 * 数据传输速率 * 2，这是显然的
  5. 二进制指数退避算法：太长了，不赘述
• CSMA/CA对CSMA/CD进行了修改，把碰撞检测改为碰撞避免，广泛用于无线局域网。它仍采用二进制指数退避算法。值得注意的是，尽管叫“碰撞避免”，实际上还是会有碰撞，只是减少了碰撞的概率罢了。实现碰撞避免的机制包括：
  1. 预约信道：发送方再发送数据的同时通知其他站点自己传输数据需要的时间长度
  2. ACK帧：只有当发送方受到返回的ACK帧后才确认数据已经正确到达目的地
  3. RTS/CTS帧：可选的碰撞避免机制，主要解决无线网中的“隐蔽站”问题

局域网

• 以太网的所有计算机共享一条主线，以广播方式发送信息，使用CSMA/CD进行访问控制，并采用无连接、不对数据帧编号，不要接收方发送确认，采用不可靠的工作方式简化通信流程
• MAC帧头部长14B，尾部长4B，数据长46~1500B，也就是说MAC帧最少为64B
• MAC帧头部包括目的地址、源地址、类型，其中地址长6B，用12个16进制数表示
• 前导码用于接收端和发送端时钟同步，长8B，在帧的头部插入

广域网

• PPP协议时使用串行线路通信的面向字节的协议，在SLIP基础上发展而来，用于建立点对点连接发送数据
• HDLC协议时ISO制定的面向比特的协议，可实现透明传输

数据链路层设备

• 网桥可将两个以太网连接起来变成一个更大的以太网。他可以分割碰撞域。网桥转发帧时，先暂存在缓存中，若未出错再发，出错则丢弃。
• 以太网交换机本质是一个多端口网桥，能提供更高的带宽。如对于普通的10Mb/s的共享式以太网，若有N个用户，则分到的平均带宽为10M/N，但使用以太网交换机之后，每个用户的带宽都为10M，交换机的总容量为N*10M
• 以太网的转发表依据的是源MAC地址。某个MAC地址A从S端口进来，那么下次目的地址为A的话转发就转发到S端口去

第四章 网络层

network system

IPv4

• IP数据报首部包括如下字段：版本、首部长度、总长度、标识、标志、片偏移、首部检验和、生存时间(TTL)、协议、源地址、目的地址。值得注意的地方如下：
  1. 首部长度单位是4B，总长度单位是1B，片偏移长度是8B
  2. 标识代表该分片属于哪个分组，标志则有三位：最低为MF=1代表后面还有分片，MF=0代表这是最后一个分片；中间为DF=0时才允许分片
  3. 片偏移指该分片相对于原分组的相对位置
• IP地址值得注意的地方如下：
  1. 主机号全0表示网络本省
  2. 主机号全1表示本网络的广播地址，可当作直接广播地址
  3. 127.0.0.0为环路自检地址
  4. 32位全1表示整个TCP/IP网络的广播地址，又称受限广播地址。可当作本地广播地址
• 网络地址转换(NAT)是将私有地址转换为共用地址，从而对外部隐藏了内部管理的IP地址。你看我们学校各种192.xx.xx.xx就使用了NAT
• 地址解析协议(ARP)将IP地址转为物理地址，用于解决同一个局域网上的主机或路由器的IP地址和硬件地址的映射问题。申请是广播，回答是单播
• 动态主机配置协议(DHLC)常用于给IP分配地址。他是应用层协议，基于UDP，采用客户/服务器方式
• 网络层使用网际控制报文协议(ICMP)来允许主机或路由器报告差错和异常情况。ICMP作为IP层数据报的数据部分，加上数据报的首部，组成IP数据报发送出去。ICMP报文的数据报有两种：差错报告报文和询问报文。差错报告报文包括以下五种类型：终点不可达、原点抑制、时间超过、参数问题、改变路由（重定向）。其中原点抑制代表路由器或主机由于拥塞而丢弃数据报。ICMP的询问报文有四种类型：会送请求和回答报文、时间戳请求和回答报文、掩码地址请求和回答报文、路由器询问和通告报文

IPv6

• 地址由24个16进制数组成，常将一个域中连续的0缩写为一个0。当有相继的0值域时，可使用::进一步缩写，但这种缩写只能出现一次

路由协议

• 因特网有两大类路由选择协议：内部网关协议(IGP)和外部网关协议(EGP)
• 路由信息协议(RIP)是IGP中最先得到应用的，它的主要思想是：
  1. 每一个路由器维护他自己到其他每一个网络的距离记录
  2. 直接相连的网络跳数为1，每经过一个路由器距离加1
  3. RIP认为好的路由就是跳数最少的路由，故优先选择跳数少的路由
  4. 每条路径最多有15个路由器，距离等于16时即代表不可达
  5. 每三十秒，相邻两个路由器就会把自身所有信息交换一次，以此更新路由信息。显然，当有两个相邻路由器能达到同一目的网络时，本地路由器会选择跳数较小的那一个。这也就导致了RIP中网络故障消息传得慢（快消息传得慢）。
  6. RIP是应用层协议，基于UDP
• 开放最短路径优先协议(OSPF)也是IGP的一种，它的思想是：
  1. OSPF向本系统中所有路由器发送信息，这里使用洪范法。
  2. 发送的信息就是本路由器相邻的所有路由器的链路状态，但这只是路由器知道的部分信息。“链路状态”是指本路由器都和哪些路由器相邻，以及该链路的代价
  3. 现在每个路由器都知道了其他路由器的相邻路由器，建图
  4. 跑Dijkstra就知道了到其他所有路由器的最短路
  5. 只有链路状态发生变化时，路由器才使用洪范法向所有路由器发送信息，因此不会出现坏消息传得慢的问题。而在RIP中，不管网络拓扑是否变化，路由器之间都会定期交换信息
  6. OSPF是网络层协议，直接使用IP数据报传送
• 边界网关协议(BGP)是不同自治系统之间交换路由信息的协议，属于外部网关协议。他的主要思想是：
  1. 每一个自治系统的管理员都要选择至少一个路由器作为该自治系统的BGP发言人
  2. 两个BGP发言人之间要交换路由信息就要建立TCP连接，在此基础上建立BGP会话
  3. 所有BGP发言人都互相交换网络可达性的信息后，各BGP发言人就找到到达各个自治系统较好的路由
• 三种路由协议的比较：

IP组播

• 组播仅应用于UDP，因为TCP是两个端之间建立连接
• 主机组播时只发送一份数据，只有数据在传送路径出现分岔时才将分组复制并继续转发
• 对组播数据报不产生ICMP差错报文
• 组播使用D类地址(224.0.0.0~239.255.255.255)，但并非所有D类地址都能用于组播
• 为了使路由器知道组播成员的信息，需使用IGMP协议

移动IP

• 简单叙述一下：比如你家在地址A，然后你去地址B旅游，你怕出去玩的时候有人找你，就在A处找了个人，让他作为本地代理。当你到达B处后，再找一个人，称为外部代理，你将外部代理的信息跟本地代理报告。这样有信息发送到A时，就由本地代理接受，本地代理发给B处的外部代理，外部代理再转给你就可以了。这样，你的IP地址永远都不用换，因为你如果再去别的地方，只要再跟A处的本地代理报告一下，更新外部代理的信息就好了

网络层设备

• 路由器主要完成两个功能：一是分组转发，二是路由计算。在同一个网络中传递数据不用路由器，但跨网通信必须使用路由器进行转发
• 如果源主机和目的主机在同一个网络中，直接交付，无需经过路由器。如果源主机和目的主机不在同一个网络中，需经过路由器转发给下一路由器，称为间接交付
• 路由器既分割冲突域，还分割广播域
• 路由表项一般包括如下字段：目的网络地址、子网掩码、下一跳IP地址、端口

第五章 传输层

transition level

传输层提供的服务

• 传输层提供进程之间的逻辑通信（即端到端），主要提供两种不同的传输协议：UDP与TCP
• 端口号中0~1023称为熟知端口号，1024~49151称为登记端口号，49152~65535称为临时端口，通信结束后，这些端口号就不复存在
• 常用的端口号包括：

• 套接字=（主机IP地址，端口号），用于表示和区分一台主机中的不同应用进程

UDP

• UDP只在IP的数据报服务上增加两个最基本的服务：服用和分用以及差错检测。UDP没有拥塞控制，UDP是面向报文的
• UDP首部只有8个字节，包括四个字段：源端口、目的端口、长度、校验和。源端口用于对方回复用，不需要时可以为0。当源主机不需要计算校验和时，令校验和字段为0。
• 接收方UDP发现收到的目的端口号不正确时，丢弃该报文并由ICMP发送“端口不可达”差错报文给发送方
• UDP校验时要在数据报之前加上12B的伪首部，这个伪首部不向下传送也不向上提交，仅用于计算校验和。UDP校验时把首部和数据部分一起校验

TCP

• TCP是面向字节流的，尽管TCP的交互是一次一个的数据块，但TCP将其仅仅看作一连串无结构的字节流
• TCP报文段首部由20B的固定长度，包括如下字段：源端口号和目的端口号、序号字段、确认号字段、数据偏移、保留字段、确认位ACK、同步位SYN、终止位FIN、窗口字段、校验和。其他还有一些选项、填充字段（目的是使长度为4B的整数倍）。值得注意的地方如下：
  1. 序号字段表示本报文段发送的数据的第一个字节的序号
  2. 确认号代表希望下次收到的报文段数据的第一个字节的序号
  3. 数据偏移指TCP报文段的数据起始处距离TCP报文段的起始处有多远（就是头部的长度）
• TCP连接包括三次握手，建立连接时不携带数据，但会消耗序号。注意第三次握手时已经不需要SYN=1
• TCP的释放包括四次握手，其中当某一方释放链接后，他就不能发送数据了，当时还可以接收数据。这里有两个值得注意的点：
  1. 第二次握手之后可以立即执行第三次握手
  2. 第三次握手之后再经过两个MSL（最长报文段寿命），客户端才完全关闭
• 为了实现可靠传输，TCP实现了如下机制：序号、确认、重传。其中导致重传的事件包括超时和冗余ACK

TCP拥塞控制

• 慢开始算法：初始拥塞窗口(cwad)=1，每次收到一个新的报文段确认后，将cwad加1。注意每次收到一个确认后，cwad只会增加1，但是宏观来说，经过一个RTT后，cwad就会变为2倍
• 拥塞避免算法：当cwnd达到慢开始门限ssthresh后就开始使用拥塞避免算法。此时每经过一个RTT就让cwad加1。注意当cwad * 2>ssthresh时，下一个cwad应等于ssthresh
• 网络拥塞处理：每出现一次超时，就让ssthresh等于当前的cwad的一半，然后把cwad置为1，然后执行慢开始算法
• 快重传：发送发连续收到三个重复的冗余ACK报文时，直接重传对方未收到的报文，不必等到计时器超时
• 快恢复：发送发连续收到三个重复的冗余ACK报文时，就让ssthresh等于当前的cwad的一半，然后把cwad设置为ssthresh改变后的数值，然后执行拥塞避免算法
• 发送发窗口实际大小=min{接收窗口(rwad)，拥塞窗口(cwad)}

应用层

application level

域名系统(DNS)

• DNS系统用于将域名转换为IP地址或把IP地址转换为域名，采用客户/服务器模型，运行于UDP之上，使用53号端口
• 域名服务器包括根域名服务器、顶级域名服务器、授权域名服务器和本地域名服务器
• 域名解析过程包括递归式和非递归式。但不管怎么样，查询顺序总是：本地域名服务器->根域名服务器->顶级域名服务器->权限域名服务器，且总由本地域名服务器将结果返还给主机
• DNS查询的最多次数=域名去掉”www”之后的段数 + 1（比如www.abc.xyz.com去掉www后有三段，最多就查询四次）

文件传输协议(FTP)

• FTP用于文件传送，采用客户/服务器模型，通过两个并行的TCP连接
• 控制连接：端口21，用于传送FTP控制命令，如连接请求、传送请求、终止请求。他在整个会话期间保持打开状态，在传输文件时也可以使用控制连接。FTP的控制信息也可以称是“带外传送”
• 数据连接：端口20，用于数据传输

电子邮件(E-mail)

• SMTP采用C/S模型，建立在TCP连接上，负责把邮件从用户代理推到服务器，或把邮件从一个服务器推到另一个服务器
• POP3采用C/S模型，建立在TCP连接上，，负责把邮件从邮件服务器拉到用户代理
• 由于SMTP只能传送一定长度的ASCII码，故需要使用MIME将非ASCII码和ASCII码之间进行翻译

万维网(WWW)

• WWW是一个资料空间，在这个空间中所有资源都通过唯一的“统一资源定位符(URL)”进行标识
• 超文本传输协议(HTTP)定义了浏览器怎样向万维网请求万维网文档，以及服务器怎样把文档传送给浏览器。
• HTTP是无状态的，同一个客户第二次访问同一个服务器上的页面时，服务器并不会记得这个客户。因此可以使用Cookie加数据库的方式来跟踪用户活动
• HTTP本身是无连接的，虽然他使用TCP连接保证可靠性，但通信双方在交换HTTP报文之前不用建立HTTP连接
• HTTP可使用非持久连接和持久连接。使用非持久连接时，每个网页元素的传输都要单独建立一个TCP连接。使用持久连接时，万维网服务器在发送响应后仍然保持这条连接，使同一个客户和服务器可以继续在这条连接上传送后续的HTTP请求和响应报文
• 持久连接又分为非流水线和流水线两种方式。对于非流水线，客户在收到前一个响应后才能发出下一个请求。而在流水线方式下，客户每遇到一个对象引用就立即发出一个请求，那么假如请求和相应都是连续发出的，那么所有引用到的对象共计1个RTT延时
• HTTP报文是面向文本的，分为请求报文和响应报文

• Previous
  PAT考后总结
• Next
  计算机组成复习