b站中科大郑铨
课本：《自顶向下计算机网络》

第一章
电路交换网络和分组交换网络

电路交换网络
电路交换不适合计算机之间的通信
- 连接建立时间长
- 计算机之间的通信有突发性，如果使用线路交换，则浪费的片较多
  - 即使这个呼叫没有数据传递，其所占据的片也不能够被别的呼叫使用
- 可靠性不高？

TDM相对于FDM的优点

频谱效率：
- 更高的频谱利用率：TDM在时间上进行复用，不需要为每个信道分配不同的频段，避免了频谱资源的浪费，提高了频谱利用效率。
设备复杂度：
- 设备简单：TDM不需要复杂的滤波器来分离不同频段的信号，只需使用时间片分配即可，因此硬件实现相对简单。
减少干扰：
- 干扰更小：TDM信号在时间上是分离的，不存在不同频段之间的相互干扰问题，而FDM中不同信道之间的频谱相邻可能会产生干扰。
动态带宽分配：
- 灵活的带宽管理：TDM可以根据需要动态调整每个用户分配的时间片，便于管理和调整带宽分配，适应不同用户的需求。
同步和定时：
- 同步性强：TDM具有严格的时间同步要求，确保各个时隙的准确性，而FDM需要对不同频段进行同步和管理，复杂度更高。

电路交换网络的优点

固定带宽和延迟：
- 固定带宽：一旦建立连接，整个通信过程中的带宽是固定的，不会受到其他用户的影响。
- 固定延迟：因为通信路径在整个通话过程中保持不变，所以延迟是固定和可预测的，适合实时通信如语音通话。
高质量的服务（QoS）：
- 确定性传输：由于有专用的通信路径，数据传输的质量和顺序有保证，丢包率低，数据传输更加可靠。
简单的通信协议：
- 协议简单：电路交换网络的协议相对简单，不需要处理复杂的分组头信息和重组数据包，适合于对协议复杂度要求低的应用。

分组交换网络

alt text

虚电路网络和数据报网络

alt text

数据报(datagram)网络

数据报(datagram) 的工作原理

在通信之前,无须建立起一个连接,有数据就传输
每一个分组都独立路由(路径不一样,可能会失序)
路由器根据分组的目标地址进行路由
虚电路(Virtual circuit)网络

总结

电路交换网络提供了固定带宽和延迟，适合高质量、实时通信。相对于FDM，TDM在频谱效率、设备复杂度、干扰管理和动态带宽分配方面具有明显优势，因而更适用于现代高效的通信系统。

住宅接入技术

住宅接入技术包括拨号调制解调器（Dial-up modem）、混合光纤同轴电缆（HFC，Hybrid Fiber-Coaxial）、数字用户线（DSL，Digital Subscriber Line）和光纤到户（FTTH，Fiber to the Home）。以下是它们的传输速率范围和是否共享的讨论：

1. 拨号调制解调器（Dial-up Modem）

传输速率范围：

上行和下行速率均为56 kbps（理论最大值）。

传输速率：

专用：每个用户有单独的连接线路，速率不会因其他用户的使用而受到影响。但实际速度通常会因电话线质量等因素降低。

2. 混合光纤同轴电缆（HFC）

传输速率范围：

下行速率：100 Mbps到1 Gbps。
上行速率：10 Mbps到100 Mbps。

传输速率：

共享：用户在同一个节点共享带宽，峰值时段（如晚上）可能因多人同时使用而导致速度下降。

3. 数字用户线（DSL）

传输速率范围：

ADSL（非对称数字用户线）：下行速率为1.5 Mbps到24 Mbps，上行速率为128 kbps到3.5 Mbps。
VDSL（超高速数字用户线）：下行速率为30 Mbps到100 Mbps，上行速率为5 Mbps到50 Mbps。

传输速率：

专用：每个用户有独立的铜线到电信局的连接，速率不受其他用户影响。但速度会随着距离电信局的增加而减低。

4. 光纤到户（FTTH）

传输速率范围：

下行速率：100 Mbps到1 Gbps，甚至更高。
上行速率：100 Mbps到1 Gbps。

传输速率：

专用：每个用户有独立的光纤连接到电信局，速率不受其他用户影响。

总结

拨号调制解调器：传输速率低且专用。
HFC：传输速率较高且共享。
DSL：传输速率中等且专用，受距离影响。
FTTH：传输速率最高且专用。

不同技术的传输速率和共享情况反映了它们适用的用户需求和网络架构特点。FTTH作为最先进的技术，提供了最优的速度和专用连接，适合对网络性能要求较高的用户。

各层运输单元及其封装关系（复用，解复用）

在网络通信的不同层次中，帧（Frame）、段（Segment）、和数据报（Datagram）是不同层次上的数据封装单位：

帧（Frame）：
- 帧是数据链路层（Data Link Layer）的封装格式。它包括数据链路层的头部和尾部，以及在两个网络设备之间传输的数据（可能是来自上层的数据）。
- 数据链路层头部通常包含目的MAC地址和源MAC地址，以及可能的错误检测和流量控制信息。
- 帧的尾部通常包含用于错误检测的信息，如循环冗余检查（CRC）。
段（Segment）：
- 段是传输层（Transport Layer）的TCP协议的数据封装单位。它包括TCP头部、TCP数据和可能的TCP尾部（包含紧急数据的指针）。
- TCP头部至少包含源端口号、目的端口号、序列号、确认号、控制位（如SYN、ACK等）、窗口大小、校验和等字段。
- 段用于在两个TCP端点之间可靠地传输数据。
数据报（Datagram）：
- 数据报是网络层（Network Layer）的IP协议的数据封装单位。它包括IP头部和IP数据（来自上层的数据）。
- IP头部包含源IP地址、目的IP地址、生存时间（TTL）、协议类型等字段。
- 数据报用于在网络中的设备之间独立地传输数据，但不保证数据的顺序或可靠性。

封装关系如下：

在发送数据时，一个应用程序首先生成数据，并将其传递给传输层（TCP或UDP）。
如果使用TCP，数据被封装在TCP段中，包括必要的TCP头部信息。
然后，TCP段被传递给网络层，IP协议将TCP段连同IP头部封装在IP数据报中。
最后，数据链路层将IP数据报封装在帧中，添加数据链路层头部和尾部，然后在物理网络上进行传输。

解封装过程则相反：帧被去除数据链路层头部和尾部，IP数据报被去除IP头部，TCP段被去除TCP头部，最终数据被传递给接收端的应用程序。这个过程涉及每一层检查其头部信息，以确保数据正确地在网络中传输和路由。

应用层

HTTP

持久与非持久HTTP

non-persistent的缺点：

each object suffers a delivery delay of two RTTs, broswer often open parallel TCP connections to fetch referenced objects
the connection is closed after the object is delivered

persistent的优点：

only one RTT for each object
multiple objects can be sent over a single connection
all objects can be sent over the same connection
the connection can be closed after all objects have been sent
DNS
a distributed database implemented in a hierarchy of DNS servers, an application-layer protocol that allows hosts to query the distributed database.

alt text

(6) Which of the following is the main function of DNS? ( C )
A. Query the computer name of a host.
B. Query the MAC address of a host.
C. Get the information between host and network through querying.
D. Assign rationally the usage of IP addresses.
DNS（域名系统）的主要功能是将域名映射到 IP 地址，从而方便人类可读的域名与网络使用的 IP 地址之间的转换。因此，正确答案是：
C. 通过查询获取主机和网络之间的信息。
此选项最能描述 DNS 在网络通信环境中的主要作用。
选项 A 不是主要功能。虽然 DNS 在某种意义上可以帮助解析主机的计算机名称，但其核心是域名到 IP 地址的映射。

SMTP和其他邮件协议

SMTP、POP3和ICMP是网络协议，它们在互联网上扮演着不同的角色：

SMTP (Simple Mail Transfer Protocol)：
- 功能：SMTP是用于发送电子邮件的主要协议。它定义了电子邮件从发送者到接收者服务器的传输方式。
- 用途：大多数电子邮件客户端使用SMTP来发送邮件。
- 工作方式：当用户通过电子邮件客户端发送邮件时，SMTP客户端会与SMTP服务器建立连接，并将邮件发送到收件人的邮件服务器。
POP3 (Post Office Protocol version 3)：
- 功能：POP3是一种用于从邮件服务器接收电子邮件的协议。
- 用途：用户使用POP3客户端从邮件服务器下载邮件到本地计算机。
- 工作方式：POP3通常用于下载存储在邮件服务器上的邮件，然后可以在没有网络连接的情况下阅读。一旦邮件被下载，它们可以从服务器上删除，尽管有些客户端允许邮件保留在服务器上。

这些协议在电子邮件通信和网络管理中发挥着关键作用，确保信息能够正确、高效地在网络中传输。

FTP

P2P

应用层Q

应用层的核心问题是什么？

满足用户需求
通讯模式，数据从A到B，谁和谁交换数据
拥有资源和索取资源的节点分别叫：客户端client和服务器server
设计应用的时候，架构:
1. C/S
2. B/S
  - C/S和B/S的区别：C/S架构需要专门的客户端软件来访问服务、适合需求高度定制化和对性能要求较高的场景、更倾向于局域网或者有限的网络环境中使用；而B/S架构通过Web浏览器作为客户端、更便于跨平台使用、简化了客户端的部署和维护、更适用于互联网或广域网环境
3. P2P
4. mixed
通信协议：怎么样传输数据。应用层有哪些协议？
- HTTP
- DNS
- SMTP
- POP3
- FTP
为什么有那么多协议？
- 为了满足不同的需求
七层模型和五层模型的区别？
- 七层模型：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层
- 五层模型：应用层、传输层、网络层、数据链路层、物理层
- 七层模型多了表示层和会话层
- 表示层在应用层之下，负责数据表示和加密等方面的处理。在这一层中，数据被转换成一种通用的格式，以便不同的应用程序之间能够进行交互。同时，表示层还负责对数据进行加密和解密，以确保数据传输的安全性。数据的表示、安全、压缩。（在五层模型里面已经合并到了应用层）信息的语法语义以及他们的关联，如加密解密、转换翻译、压缩解压。格式有，JPEG、ASCll、EBCDIC、加密格式等，如LPP（轻量级表示协议）
- 会话层位于表示层之下，负责建立和维护通信会话。会话层通过建立连接、数据传输和断开连接等过程来管理网络通信。在这一层中，数据被分成数据段或数据包进行传输，并确保数据的顺序和完整性。建立、管理、终止会话。（在五层模型里面已经合并到了应用层）不同机器上的用户之间建立及管理会话。对应主机进程，指本地主机与远程主机正在进行的会话。安全协议：SSL（安全套接字层协议）、TLS（安全传输层协议）
  传输层
  UDP
  UDP 报头

源端口(Source Port)：
目标端口(Destination Port)：
长度(Length)：整个 UDP 报文的长度(报头加上数据)
校验和(CheckSum)：可选的，如果不校验就是全零，UDP 校验包括报文、数据和 IP 的源地址、目的地址、协议值(17 表示 UDP 协议)，用来报文不被传输到错误的地址中
checksum
需要对首部、数据、加上伪首部进行计算校验和：包括 4 字节的源 IP 地址和 4 字节的目的地址，1 字节的全 0，1 字节的 17(UDP 协议号)和两字节的 UDP 长度。如果数据不为偶数个字节，要补上全 0 字节，计算后删除。
对所有 16 位的字进行求和再反码，在每次求和过程中出现的溢出要进行回卷(wrap around)
例如：

把取反之后的值放进 checksum 中。
在接收方中，把所有的 4 个 16 位的字(包括校验和)相加，如果没有出错的话就是全为 1，如果有一位为 0，就说明出错了

实现了差错检测，但是没有丢失检测。

rdt

在rdt（Reliable Data Transfer，可靠数据传输协议）的FSM（有限状态机）中，状态转移旁边的代码通常遵循以下格式：

[事件]/[动作]

横线上面的部分代表事件（Event）：这是触发状态转移的条件。事件可以是接收到特定类型的数据包（如ACK或数据包）、超时事件（即等待ACK的时间超过了预定的阈值）等。
横线下面的部分代表动作（Action）：一旦事件发生，就会执行的操作。动作可以包括发送数据包、发送ACK、启动或重置计时器等。

例如，在rdt3.0的发送方FSM中，一个可能的状态转移是：

1	[收到ACK]/[发送下一个数据包，启动计时器]

这意味着，当发送方收到ACK（事件）时，它将发送下一个数据包并启动计时器（动作）。

在rdt的各个版本中，这种表示方法帮助理解协议如何在不同事件发生时响应，以及它将执行哪些动作来维持数据传输的可靠性。

在计算机网络和协议设计中，”wait for call from above/bellow”通常指的是在一个分层的网络协议栈中，较低/高层等待来自上层/下层的调用或请求。这个表达通常出现在有限状态机（FSM）的描述中，特别是在描述可靠数据传输协议（如rdt）的接收方或发送方的状态时。

具体到rdt（Reliable Data Transfer）协议的上下文中，”wait for call from above”意味着：

对于发送方，这个状态表示发送方正在等待来自应用层的数据。在这个状态下，发送方不会发送任何数据包，直到它从应用层接收到数据。一旦接收到数据，发送方将进入下一个状态，比如打包数据并发送。

在rdt协议的FSM中，”wait for call from above”是一个重要的状态，因为它表明了协议在等待应用层的输入，这是开始数据传输过程的触发点。

各个版本的rdt协议的区别：

rdt1.0：假设底层信道是完全可靠的，不会出现数据包丢失、损坏或重复的情况。
rdt2.0：假设底层信道是具有比特差错信道，引入了数据包的损坏和重复，但不会丢失。通过校验和来检测数据包的损坏，并通过ACK和NAK来处理重复数据包。
rdt2.1：针对rdt2.0中ACK/NAK受损可能会导致重传的问题，rdt2.1加入了序列号机制(sequence number)，分组的号码可以让发送方知道是否需要重传以及让接收方确认这是否是一次重新传输的分组。
rdt2.2：一次使用两种确认信息ACK，NAK处理起来比较费力，因此rdt2.2中移除NAK的信息，在ACK中加入编号就可以达到确认与否认的效果。发送方必须检查接收到的ACK中的报文中被确认的分组序号。
rdt3.0：在rdt3.0中，引入了超时重传机制，以处理数据包丢失的情况。发送方在发送数据包后会启动一个计时器，如果在超时时间内没有收到ACK，发送方会重传数据包。

rdt1.0

Assumptions:
• The underlying channel is
completely reliable

alt text

rdt2.0

sending side

alt text

receiving side

alt text

rdt2.1

sender

alt text

receiver

alt text

rdt2.2

sender

alt text

receiver

alt text

rdt3.0

sender

alt text

receiver

alt text
由于分组序号总是在 0 与 1 之间交替，有时 rdt3.0 也被称为比特交替协议(alternating-bit protocol）

流水线rdt

流水线 RDT
在停等协议里，对信道的使用率极低
alt text
因此我们以流水线的方式——即在确认 ACK 抵达前就开始发送新的 packet

我们需要增加序号范围，因为每个运输中的 packet 都要有一个唯一的信号

协议的发送方和接收方也要缓存多个分组。发送方最少要缓冲那些已发送但是未确认的 packet，接收方要缓冲那些已经正确接收的 packet

所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢包，也就是怎么处理重传。有两种基本方法：回退 N 步(Go-Back-N, GBN)和选择重传(Selective Repeat, SR）

GBN和SR

GBN: swndow size≥1, rwndow size=1；
SR: swndow size≥1, rwndow size≥1；
同样是用窗口长度 N 来限制未完成、未被确认的 packet 数量。
不同的是 SR 的接收方会对失序的分组(即落在窗口内的非起始 packet)进行接收并缓存。

TCP
三次握手
TCP 三次握手是建立一个 TCP 连接时，客户端和服务器总共发送 3 个报文的过程。三次握手的目的是连接服务器指定端口，建立 TCP 连接，并同步连接双方的序列号和确认号，交换 TCP 窗口大小信息。在 socket 编程中，客户端执行 connect()时，就会发起三次握手。

第一次握手：客户端发送一个 SYN 包到服务器，告诉服务器我要发送数据了。
第二次握手：服务器收到 SYN 包后，回复一个 ACK 包和一个 SYN 包，告诉客户端我准备好了，你可以发送数据了。
第三次握手：客户端收到 ACK 包和 SYN 包后，回复一个 ACK 包，告诉服务器我也准备好了，可以开始传输数据了。

这个过程可以实现可靠数据传输，避免双方选择的序列号得不到确认的情况。三次握手后，双方可以知道对方的 MSS，接收缓冲区大小，以及是否支持 SACK，窗口缩放等选项。

少一次的话无法确定客户端能收到服务器信息，也无法确认对方能同步序列号等服务器端 TCP 信息

四次挥手

TCP 四次挥手是断开一个 TCP 连接时，需要客户端和服务端总共发送 4 个包以确认连接的断开。

第一次挥手：客户端发送一个 FIN 报文到服务器，告诉服务器我已经没有数据要发送了。
第二次挥手：服务器收到 FIN 报文后，回复一个 ACK 应答报文，告诉客户端我知道你要断开连接了。
第三次挥手：服务器发送一个 FIN 报文到客户端，告诉客户端我也没有数据要发送了。
第四次挥手：客户端收到 FIN 报文后，回复一个 ACK 应答报文，告诉服务器我知道你也要断开连接了。

这个过程可以拆除两条通道和释放资源。四次挥手后，双方都会进入 TIME-WAIT 状态，等待 2 MSL（最长报文段寿命）后，才会完全关闭。

TCP段

TCP（传输控制协议）报文头部的最小尺寸是20字节，但这不包括任何选项字段。TCP头部的最小结构包括以下字段：

源端口号（16位）
目的端口号（16位）
序列号（32位）
确认号（32位）
数据偏移（4位），指示TCP报头的长度
保留（6位），未使用，必须置为0
标志位（6位），包括URG（紧急指针有效）、ACK（确认号有效）、PSH（推送功能）、RST（重置连接）、SYN（同步序列编号以发起一个连接）、FIN（结束一个连接）
窗口大小（16位）
校验和（16位）
紧急指针（16位），仅当URG标志位被设置时使用
alt text

往返时间的估计与超时

估计往返时间
alt text

超时重传

TCP 会为每个报文设置一个重传计时器，计时器的初始值为

$TimeoutInterval=EstimatedRTT+4 \cdot DevRTT$

每当超时时间发生，触发重传时，会把下次的 TimeoutInterval 设置为当前的两倍

flow control vs congestion avoidence

flow control: 根据接收方发回的包中的window字段调整发送窗口

congestion avoidence: 自动探测网络情况调整发送窗口

流量控制(Flow control)

指消除发送方使接收方缓存溢出的可能性。是一个速度匹配服务。而解决 TCP 发送方因为 IP 网络拥塞而被遏制的称为拥塞控制(Congestion Control）

在 TCP 报头中，包含一个 data sequence number(LastByteSent)，一个 acknowledgment sequence number(LastByteAcked)，还包含一个 window 字段来表示接收方的 window 的剩余大小，也就是说 TCP 接收器只会处理数据序列号等于 ACKnum + window 的数据，也不允许发送方发送序列号超过 ACKnum + window 的数据.

接收方为连接分配的接收缓存大小为recvbuffer，接收窗口rwnd的大小随着应用程序不断取走数据，IP 报文不断抵达不断变化

传输层Q

传输层的核心问题
进程间的逻辑通信，通过复用解复用等技术让数据到达对应的端口
分组交换网络
数据传输的问题
- 排队延迟&丢失
- 乱序
- 错误
- 重复
解决上述问题的技术：校验和，这是个通信和数学的学科（通信纠错），有很多具体方法
解决丢包问题的原理：超时重传
解决乱序问题的原理：序号
网络层
Default router（默认路由器）或 first-hop router（第一跳路由器）是指在一个网络中，当数据包需要发送到本地网络之外的目的地时，它首先会被发送到的路由器。这个路由器负责将数据包转发到目的地或者下一个路由器，直到数据包最终到达目的地。在大多数情况下，这个默认路由器的设置是自动配置的，例如通过DHCP协议，确保网络中的设备知道向哪个路由器发送所有外发的流量。默认路由器是实现网络互连的关键组件，它允许网络中的设备访问外部网络，如互联网。
路由算法
LS：链路状态
idea：每个节点都知道全局的拓扑结构，然后通过Dijkstra算法来计算最短路径
step：

learn about the neighbors
measuring the cost
construct the link state packet telling all it has just learned
flooding the link state packet to all other nodes
run Dijkstra’s algorithm to find the shortest path

DV：距离矢量
idea：每个节点只知道自己的邻居，然后通过Bellman-Ford算法来计算最短路径
重要公式：$D_x(y)=min_v{c(x,v)+D_v(y)}$，解释：从x到y的最短路径是从x到v的最短路径加上从v到y的最短路径

• Distributed
• each node receives some information from one or more of its
directly attached neighbors, performs a calculation, and then
distributes the results of its calculation back to its neighbors
• Iterative
• this process continues on until no more information is exchanged
between neighbors
• Asynchronous
• it does not require all of the nodes to operate in lockstep with each other.

LS和DV算法比较

消息复杂度（DV胜出）

LS：有n节点，E条链路，发送报文的复杂度是O(nE)
- Dijkstra算法
- 局部的路由信息，全局传播
DV：每个节点只需要发送给相邻节点，复杂度是O(n)
- 全局的路由信息，局部传播
  收敛速度（LS胜出）
LS:o(n^2)
- 有可能震荡
DV:
- 可能存在路由环路
- 可能会出现count-to-infinity问题
  健壮性（LS胜出）
LS:
- 节点会通告不正确的链路代价
- 每个节点只计算自己的路由表
- 错误信息影响较小，局部，路由较健壮
DV:
- DV节点可能会通告全网所有节点的不正确路径代价
  - 距离矢量
- 每一个节点的路由表可能被其他的节点使用
  - 错误可能会扩散到全网

2种路由选择算法都有优缺点，而且在互联网中都有应用。

在网络中路由

OSPF

OSPF（Open Shortest Path First）是一种链路状态（LS）路由协议，用于在 IP 网络中选择最佳路径。OSPF 使用 Dijkstra 算法来计算最短路径，通过洪泛算法来传播链路状态信息，以及通过 Hello 协议来维护邻居关系。OSPF 是一个开放的标准协议，适用于各种网络环境，包括局域网、广域网和互联网。

BGP

BGP（Border Gateway Protocol，边界网关协议）是一种距离矢量（DV）协议，用于在互联网中交换路由信息。BGP 是互联网中最常用的路由协议之一，用于在自治系统（AS）之间交换路由信息。BGP 使用路径矢量算法来选择最佳路径，通过 TCP 连接来传输路由信息，以及通过 BGP 消息来交换路由信息。BGP 是一个非常灵活和强大的协议，可以实现复杂的路由策略和路由控制。

RIP(Routing Information Protocol)

RIP（Routing Information Protocol）是一种距离矢量（DV）路由协议，用于在小型网络中选择最佳路径。RIP 使用 Bellman-Ford 算法来计算最短路径，通过 UDP 协议来传输路由信息，以及通过 RIP 消息来交换路由信息。RIP 是一个简单和易于实现的协议，适用于小型网络环境，如家庭网络、小型企业网络等。

为什么选择OSPF而不是RIP？

OSPF（Open Shortest Path First）和RIP（Routing Information Protocol）都是内部网关协议（IGP），用于在单个自治系统（AS）内进行路由。选择OSPF而不是RIP的原因包括：

链路状态与距离矢量：OSPF是一种链路状态协议，它能够更快速地响应网络变化，因为它可以立即更新所有路由器的路由表。相比之下，RIP是一种距离矢量协议，它在网络变化时可能需要更长时间来收敛。
可扩展性：OSPF能够更好地处理大型网络。RIP有15跳的最大限制，而OSPF没有这样的限制，可以支持更大规模的网络。
路由选择：OSPF支持更复杂的路由选择标准，如成本（cost），而RIP仅基于跳数来选择路由。
类型长度值（TLV）：OSPF使用TLV结构来定义各种类型的数据，这使得协议更加灵活和可扩展。
区域划分：OSPF允许网络被划分为多个区域（Areas），这有助于减少路由信息的泛洪和提高效率。
多路径路由：OSPF支持多路径路由和负载均衡，而RIP不支持。
认证和安全性：OSPF支持对路由信息进行认证，增加了网络的安全性。

尽管RIP在小型或非常简单的网络中可能足够使用，但OSPF由于其上述优点，在现代网络中更为常见，特别是在需要高性能和可扩展性的环境中。因此，OSPF是推荐用于内部AS的路由协议。

链路层和局域网

广域网的物理限制，一般使用单点连接，因此寻址和媒体访问控制功能就被弱化了。

引论和服务

术语

节点：主机、路由器、交换机
链路：相邻节点间的通信信道
- 有线链路
- 无线链路
- 局域网，共享性链路
帧：链路层的协议数据单元
链路层服务
成帧，链路接入
将数据包封装在帧中，加上帧头和帧尾
如果采用的是共享性介质，还需要信道的访问权
在帧头部使用MAC（物理）地址来表示源和目的地址
在两个相邻节点间的可靠传输
出错率低的光纤和双绞线链路，不需要可靠传输
出错率高的无线链路和卫星链路，需要可靠传输
流量控制
如果发送方发送速度过快，接收方可能来不及处理
通过接收方向发送方发送控制信息，告诉发送方可以发送的数据量
差错检测和纠正
差错由信号衰减和噪声引起
- 接收方检测出的错误，通知发送方重传或者丢弃
- 通过CRC校验和来检测差错
接收端检查和纠正bit错误，不通过重传来纠正
- 通过ARQ协议来纠正差错
  半双工和全双工
  链路层在哪里实现？
在每个主机、路由器或者交换机的端口上
网络适配器，也就是网络接口卡（network interface card, NIC）或者界面卡，俗称网卡
- 以太网卡，802.11网卡
- 以太网芯片组
- 实现链路层和相应物理层的功能
硬件软件固件的综合体

差错检测和纠正

EDC：Error Detection and Correction，差错检测和和纠正位（冗余位）
D：data bits 数据由差错检测保护，可以包含头部字段

错误检查不是100%可靠，也存在小概率的漏检
更长的EDC字段，或者更复杂，EDC和D同时出错的可能性极小，可以提高检测和纠正的准确性
奇偶校验
单比特奇偶校验
奇偶校验位：1个
加多一位校验位，使得数据与校验位拼接起来是一个偶数/奇数，这种方法有 50%的几率检测出错误。
把 d 个比特分为 i 行 j 列，通过二维校验，能对单个比特的错误进行纠错！以及对两个比特差错的任何组合进行检测

alt text
接收方检测和纠正差错的能力被称为前向纠错(Forward Error Correction, FEC)

二维奇偶校验

能检测到，不能定位错误；不能检测出对偶错误。

checksum

CRC，循环冗余校验

modulo-2 arithmetic，模2运算，实际上就是异或，相同为0，不同为1
位串的两种表示，二进制码和二进制多项式（$kn*x^n+k{n-1}x^{n-1}…x_0x^0，其中k_i =0或者1$）
生成多项式，G(x)，用于计算CRC
- 1001，$x^3+x^0$，对应的多项式为$x^3+1$
数据位后面加上r位的冗余位，使得整个数据位串能够被G(x)整除
- D左移了r位，$D*2^r$
- 我们希望下面这个式子成立：$D2^r \oplus R = nG(x)$
- 推导： $D \cdot 2^r \oplus R = n \cdot G(x) $$$$\Rightarrow D \cdot 2^r \oplus R \oplus R= n \cdot G(x)\oplus R$$$$\Rightarrow D \cdot 2^r = n \cdot G(x)\oplus R$$$$\Rightarrow R=reminder[\frac{D \cdot 2^r}{G(x)}]$
- 最后，我们将冗余位R附加到原始数据位串D的末尾，得到最终要发送的位串。
- 这样，接收端在接收到数据后，可以通过同样的生成多项式G(x)来除这个位串，如果余数为0，那么就认为数据没有错误；如果余数不为0，那么就认为数据出现了错误。
- 通俗的解释就是，5/4…1，这个5就是左移之后的D’，1就是R，由于异或中加和减其实是一样的，那么就有(5-1)/4=1整除
- 适合用硬件实现
  多点访问控制
  MAC（媒体访问控制）协议：分类

信道划分
- 信道划分成小片（时间，频率，编码）
- 分配片给每个节点使用
随机访问
- 信道不划分，允许冲突
- 冲突后恢复
依次轮流
- 节点依次轮流
- 但是有很多数据传输的节点可以获得较长的信道使用权
- 如果主节点出现问题，整个网络就会瘫痪,所以存在主节点和单点故障问题，不存在冲突问题
  信道划分
TDM（Time Division Multiplexing）：时间划分多路复用
- 时分多路复用
- 时隙分配给不同的节点
- 时隙不使用就浪费了
FDM（Frequency Division Multiplexing）：频率划分多路复用
- 频分多路复用
- 频率分配给不同的节点
- 频率不使用就浪费了
CDM（Code Division Multiplexing）：码分多路复用
- 码分多路复用
- 通过不同的码来区分不同的节点
- 码不使用就浪费了

随机访问

当节点有帧要发送的时候
- 以信道带宽的全部R bps发送
- 没有节点间的预先协调
两个或者更多节点同时传输，冲突collision
随机存取协议规定：
- 如何检测冲突
- 如何恢复冲突，例如等待随机时间后重传
随机MAC协议
- 时隙ALOHA
- ALOHA
- CSMA，CSMA/CD，CSMA/CA
  时隙ALOHA
时隙ALOHA
- 时隙划分成固定长度
- 节点只在时隙开始时发送
- 如果冲突，等待下一个时隙
- 优点：节点可以全速发送；高度分布，仅需要节点之间在时隙上的同步
- 缺点：时隙利用率低，时隙浪费（空闲的）
时隙ALOHA的效率
- 时隙利用率S：成功时隙的概率
- 如果有N个节点，每个节点有p的概率发送，有1-p的概率不发送
- 一个节点发送成功的概率是p(1-p)^(N-1)
- 有N个节点，每个节点发送成功的概率是Np(1-p)^(N-1)
- 时隙利用率S=Np(1-p)^(N-1)
- 最大时隙利用率是1/e=0.37
  ALOHA
纯ALOHA（非时隙）
- 节点在任何时候发送
- 如果冲突，等待随机时间后重传
- 优点：简单，无需在时隙上同步
- 缺点：冲突的概率增加
  - 帧在t0发送，和其他在[t0-1,t0+1]区间内发送的帧冲突
纯ALOHA的效率比时隙ALOHA低，1/2e=0.18
载波侦听多路访问(CSMA)
说话之前先听。如果其他人正在说话，等到他们说完话为止。在网络领域中，这被称为载波侦听（carrier sensing），即一个节点在传输前先听信道。如果来自另一个节点的帧正向信道上发送，节点则等侍直到检测到一小段时间没有传输，然后开始传输。

但是由于传播延迟的存在（说了话不是马上能听到），所以可能会有传输干扰和碰撞的情况发生。例如，$t_0$时刻B侦听到信道空闲，于是开始广播，而在$t_1$时刻，D也侦听到信道空闲，开始传输。
alt text

CSMA/CD

如果与他人同时开始说话，停止说话。在网络领域中，这被称为碰撞检测（collision detection），即当一个传输节点在传输时一直在侦听此信道。如果它检测到另一个节点正在传输干扰帧，它就停止传输，在重复“侦听-当空闲时传输”循环之前等待一段随机时间。

加入碰撞检测之后，在检出碰撞后停止传输。
alt text

二进制指数后退

当检测到碰撞后，肯定不能两者中止相同的时间，这样会一直碰撞下去。
用于以太网以及DOCSIS电缆网络多路访问协议中的二进制指数后退（binary exponential backoff）算法，简练地解决了这个问题。特别是，当传输一个给定帧时，在该帧经历了一连串的次碰撞后，节点随机地从（$0~2^{k-1}$）中选择一个K值。
因此，一个帧经历的碰撞越多，K选择的间隔越大。对于以太网，一个节点等待的实际时间量是一个时间间隔的整数倍，这个时间间隔是一个时钟滴答的时间，通常是微秒级别的。这样，一个节点在每次碰撞后等待的时间是指数级增长的，这样就避免了多次碰撞的情况。

在CSMA/CD中，当发生冲突时，所有检测到冲突的设备都将执行退避算法，而不仅仅是造成冲突的设备。等待随机时间后再次尝试传输，并没有特定的优先级。

CSMA/CA

避免冲突。在网络领域中，这被称为碰撞避免（collision avoidance），即在传输之前，节点发送一个小的控制帧，以便在传输之前检查信道是否空闲。如果信道空闲，节点等待一个随机时间后再次发送控制帧。如果信道仍然空闲，节点开始传输。如果信道忙，节点等待一段时间后重复这个过程。

依次轮流

轮询协议

由一个主节点轮询各个节点，通过观察信道情况，告诉它是否能传输，以及能传输的帧的最多数量。但是这带来主节点通信的时延，以及主节点失效后整个网络的失效。
例如蓝牙协议

令牌传递

一个特殊的帧，令牌，从一个节点传递到另一个节点。只有拥有令牌的节点才能传输。但是这样的话，如果令牌丢失，整个网络就会失效。

没有主节点，一个被称为令牌(token)的小的特殊帧在节点之间以固定顺序传递，当有帧发送时它持有这个节点，否则就马上传递给下一个。

如果一个节点故障可能导致整个循环的崩溃，以及如果节点忘记释放令牌，还需要进行额外的恢复步骤使循环恢复。

LANs

ARP

MAC地址和ARP协议

ipv4 32bit，ipv6 128bit
MAC地址是48bit，通常用16进制表示，前24bit是厂商ID，后24bit是序列号
Ethernet interface addresses, more commonly known as MAC (Media Access Control)

网络号在前n-1跳（也就是到达了目标ip的子网）的过程中起作用，主机号在最后一跳到主机的过程中起作用

最后一跳在网络内部，通过链路层，从路由到主机。

ARP协议（address resolution protocol，地址解析协议）：将ip地址解析为MAC地址。虽然ARP在功能上与网络层紧密相关，但它实际上工作在网络层和数据链路层之间，用于将IP地址解析为MAC地址。

网卡在链路层，只能识别MAC地址，所以需要ARP协议来解析ip地址，从而找到对应的MAC地址。在物理网络从内部来标识每一个节点，把分组封装成帧，从一个节点传输到另一个节点。

网络地址和MAC地址的映射表分离：

分离的好处
- 网卡坏咯，换了一个网卡，mac地址变了，但是ip地址不变，对于应用层来说没有感知。
- 物理网络除了ip之外还有其他的网络层协议，链路层协议为任意上层网络协议，如IPX等。
捆绑的问题
- 如果仅仅使用IP地址，不用MAC地址，那么它只支持IP协议
- 每次上电都要重新写入网卡IP地址
- 如果不使用任何地址，不用MAC，则每到来一个帧都要上传到IP层次，由他来判断是不是需要接受，干扰一次

LAN地址和ARP地址

MAC是平面的，移动了也可以标识，但是ip是层次化的，不能随便移动。

plugin play：插上网线就能用，不用配置ip地址，因为有DHCP协议，自动分配ip地址。即插即用。

Ethernet

目前最主流的LAN技术：98%的局域网使用以太网技术
廉价
最早广泛应用的LAN技术
比令牌环网和ATM LAN更简单、廉价
带宽不断提升

switches

同轴电缆

总线型线路
- 可靠性：容易破损
集线器
- 逻辑上是总线型拓扑
- 物理上是星型拓扑
- hub外的某条线路断了，hub内其他线路的还能通信
- 碰撞域：一个节点发送的帧可能会与其他节点发送的帧相撞
switch
- 效率更高
- 更加可靠
- 交换机的端口直接与主机相连，一个端口就是一个碰撞域

以太帧结构

前导码：7个字节的10101010
- 用于同步接收方和发送方的时钟速率
目的地址：6个字节
源地址：6个字节
出错率较低，不需要可靠传输

在现代以太网中，由于交换机的使用，CSMA/CD（载波侦听多路访问/冲突检测）协议的需求已经大大减少。

交换机可以在其端口之间建立专用的连接，这意味着每个端口的设备可以同时发送和接收数据，而不会发生冲突。因此，交换机环境下的以太网已经变成了全双工模式，不再需要CSMA/CD协议来处理冲突。

然而，对于旧式的共享媒体网络（如集线器环境），或者在半双工模式下工作的以太网，CSMA/CD仍然是必要的，因为在这些环境中，冲突仍然可能发生。

VLANs
虚拟局域网（VLAN）是一种在交换机上创建的逻辑网络，它允许网络管理员将一个物理网络分割成多个虚拟网络，每个虚拟网络都是一个独立的广播域。VLAN技术使得网络设备即使在物理上不在同一位置，也可以属于同一个逻辑网络。这种逻辑分割基于端口、协议或其他属性，而不是基于物理连接。VLAN的创建提供了更高的灵活性和安全性，因为它允许网络管理员根据部门、功能或项目需求来组织网络资源。

VLAN的优点：

安全性：VLAN可以将敏感数据流量与其他流量隔离开来，从而提高网络安全性。
灵活性：VLAN可以根据需要随时更改，而无需重新布线。
性能：VLAN可以减少广播流量，提高网络性能。
管理：VLAN可以简化网络管理，提高网络可管理性。
成本：VLAN可以减少网络设备的数量，从而降低网络成本。

划分广播域，增强健壮性，增强局域网安全性，灵活构建工作组

*链路虚拟化：MPLS

*数据中心网络

a day in the life of a web request

物理层

a day in the life of a web request

alt text

考试题型

选择题
填空题
判断题
简答题 20分（4×5）
综合题 30分（3×10）
考点
综合题类似于：
传输层字节流，这三个字节变成segment，后面多少个字节变成一个segment，每个segment的number，告诉你其中一个参数，让你推导出别的segment的参数
tcp的rdt必考：告诉条件，如A向B发送了几个，丢了一部分，多种情况，B的ACK怎么响应的？
tcp 拥塞控制快速重传等不同情况下会有什么表现一次只能发一个MSS 1248非线性增长每个轮次double，double，然后线性增长。
ip组网 DHCP NAT 链路层端口号这个节点的网关是夺少，MAC地址转换
ip层routing 连起来考subnets server client 发一个请求，从这个请求之后，数据包这么走，每一个节点
LS, DV，自己跑一边，路由表建立起来
arp协议不会单独考，放在网络的结构里，问某个请求之后，这个switch的switch table会怎么变化
简答题类似于：
链路层的etc：特别是crc校验、
osi的层次名字和handle的问题
packet switch和circuit switch的区别（数据包交换和电路交换）

习题

第六章链路层

R2：链路层都可靠，为什么还需要TCP？
- 每一条链路都可靠，不代表端到端就可靠
- 所以即使链路层都可靠，tcp也不是多余的
R6：CSMA/CD中，在五次碰撞之后，节点选择K=4的概率有多大？结果K=4在10Mbps的以太网上对应于多少秒的时延？
- 五次碰撞后，节点选择K的范围是$[1,2,…2^5]$，所以K=4的概率是$1/2^5=1/32$，对应于10Mbps的以太网上的时延是$4*512/10^6=204.8\mu s$
- 碰撞窗口为32，那么平均等待时间：$\frac{32}{2}512/10^6 = 16512/10^6 = 409.6\mu s$
R11 ARP查询为什么要在广播帧中发送呢？ARP响应为什么要在一个具有特定目的的MAC地址的帧中发送呢？
- ARP查询需要在广播帧中发送，因为ARP查询的目的是找到对应的MAC地址，而广播帧是唯一能够找到所有节点的帧，所以ARP查询需要在广播帧中发送
- ARP响应需要在一个具有特定目的的MAC地址的帧中发送，因为ARP响应的目的是告诉请求的节点对应的MAC地址，发送节点知道应该将响应报文发给哪个MAC地址，所以不需要广播
R12 路由器由两个ARP模块，每个都有自己的ARP.同样的MAC地址可能在两张表中都出现吗？
- 不可能，因为MAC地址是唯一的，所以不可能在两张表中都出现。
- ARP缓存是为了查询快，删除是为了适应变化
P2 举例说明二维奇偶校验能够纠正和检测单比特差错。举例说明某些双比特差错能被检测倒是不能纠正。
- 二维奇偶校验的能力比较有限，如果是单比特差错，可以检测出来也可以找到错误在哪；如果是双比特成行成列出现错误，可以检测出来但是定位不到，无法纠正；如果是对偶错误，那么就无法检测出来。
P8
- ALOHA的效率是$S=Np(1-p)^{N-1}$
- 分部求导，得出P=1/N的时候有最大时隙利用率是$1/e=0.37$
p15
- P15 考虑图6-33。现在我们用一台交换机代替子网l和子网2之间的路由器，并且将子网2和子网3之间的路由器标记为R1。
1. 考虑从主机E向主机F发送一个IP数据报。主机E将请求路由器RI帮助特发该数据报吗?为什么?在包含P数据报的以太网帧中，源和目的IP和MAC地址分别是什么?
  - 没有跨越子网，直接走交换机，不需要路由器的帮助。源IP是E的IP，源MAC是E的MAC，目的IP是F的IP，目的MAC是F的MAC。
2. 假定E希望向B发送一个IP数据报，假设E的ARP缓存中不包含B的MAC地址。E将执行ARP查询来发现B的MAC地址吗?为什么?在交付给路由器R的以太网锁(包含发向B的IP数据报)中，源和目的IP和MAC地址分别是什么?
  - 不会查询B。B和E不在同一个子网，跨越子网了，所以下一跳是路由器的出口。所以他会查询路由器的MAC地址。源IP是E的IP，源MAC是E的MAC，目的IP是B的IP，目的MAC是路由器R的MAC。
3. 假定主机A希望向主机B发送一个数据报，A的ARP缓存不包含B的MAC地址，B的ARP缓存也不包含A的MAC跑址。进一步假定交换机S1的转发表仅包含主机B和路由器R1的表项。因此，A将广播一个ARP请求报文。一旦交换机S1收到ARP请求报文将执行什么动作?路由器RI也会收到这个ARP请求报文吗?如果收到的话，R1将向子网3转发该报文吗?一旦主机B收到这个ARP请求报文，它将向主机A回发一个ARP响应报文。但是它将发送一个ARP查询报文来请求A的MAC地址吗?为什么?一旦交换机S1收到来自主机B的一个ARP响应报文，它将做什么?
  - S1会通过两个接口广播这个ARP请求报文。路由器R1也会收到这个ARP请求报文，但是它不会向子网3转发。B不会发送ARP查询报文，因为A的MAC地址可以从其广播的请求报文中得出。S1收到之后会在转发表中添加B的表项，并向A发送ARP响应报文。
p21 现在考虑习题P14中的图6-33。对主机A、两台路由器和主机F的各个接口提供MAC地址和IP地址。假定主机A向主机F发送一个数据报。当在下列场合传输该帧时，给出在封装该IP数据报的帧中的源和目的MAC地址:
(i)从A到左边的路由器:
- 源MAC: 00-00-00-00-00-00
- 目的MAC: 22-22-22-22-22-22
- 源IP: 111.111.111.001
- 目的IP: 133.333.333.003
(ii)从左边的路由器到右边的路由器:
- 源MAC: 33-33-33-33-33-33
- 目的MAC: 55-55-55-55-55
- 源IP: 111.111.111.001
- 目的IP: 133.333.333.003
(iii)从右边的路由器到F：
- 源MAC: 88-88-88-88-88-88
- 目的MAC: 99-99-99-99-99-99
- 源IP: 111.111.111.001
- 目的IP: 133.333.333.003
R16 假设支持K个VLAN组的N台交换机经过一个干线协议连接起来。连接这些交换机需要多少端口？
- 最头和最尾的两个交换机各自需要1个端口，中间的N-2个交换机各需要2个端口，一共需要$2N-2$个端口
P31 在这个习题中，你将把已经学习过的因特网协议的许多东西拼装在一起。假设你走进房间，与以太网连接，并下载一个 Web页面。从打开PC电源到得到 Web 网页，发生的所有协议步骤是什么?假设当你给PC加电时，在DNS或浏览器缓存中什么也没有。(提示:步骤包括使用以太网、DHCPARP、DNS、TCP和HTTP协议。)明确指出在这些步骤中你如何获得网关路由器的IP和MAC地址
- 首先使用 DHCP 获取 IP 地址,计算机在 DHCP 服务器创建一个发往255.255.255.255的特殊 IP 数据报，将其放入以太网帧并在以太网中广播。然后按照 DHCP 协议中的步骤，计算机可以获得具有给定租约时间的IP地址。
- 以太网中的 DHCP 服务器还提供第一跳路由器的 IP 地址列表、计算机所在子网的子网掩码以及本地 DNS 服务器的地址(如果存在)。计算机的 ARP 缓存最初为空，使用ARP协议来获取第一跳路由器和本地DNS服务器的MAC地址计算机具有网页的IP地址后，如果网页不驻留在本地Web服务器中，它将通过第一跳路由器发出HTTP请求。HTIP请求消息将被分段并封装到TCP数据报中，然后进一步封装到 IP 数据报中，最后封装到以太网帧中。计算机发送目的地为第一跳。
P28 假设一台外部路由器与交换机的端口1相连，为EE和CS的主机和路由器端接口分配ip地址。跟踪从EE主机向CS主机传送一共数据报时，网络层和链路层采取的步骤。
- EE的主机IP地址为111.111.1.x，子网掩码111.111.1/24，CS的主机IP地址为111.111.2.x，子网掩码111.111.2/24。每个IP地址与VLAN ID相关联，假设111.111.1.0和111.111.2.0分别和VLAN1和VLAN2相关联，子网111.111.1/24和111.111.2/24中的每个帧分别添加一个VLAN ID 为11、12的802.1Q标签。

第五章网络层控制平面

P7 为什么在因特网中用到了不同类型的AS间与AS内协议?
- 策略:在 AS 之间, 策略问题起主导作用。一个给定 AS 产生的流量不能穿过另一个特定的 AS，这可能非常重要。类似地，一个给定的 AS 也许想很好地控制它承载的其他 AS之间穿越的流量。我们已看到，BGP承载了路径属性，并提供路由选择信息的受控分布，以便能做出这种基于策略的路由选择决策。一个 AS 内部,一切都是在相同的管理控制名义下进行的，因此策略问题在 AS 内部选择路由中起着微不足道的作用。
- 规模:扩展一个路由选择算法及其数据结构以处理到大量网络或大量网络之间的路由选择的这种能力，是 AS 间路由选择的一个关键问题。在一个 AS 内，可扩展性不是关注的焦点。首先，如果单个 ISP变得太大时，总是能将其分成两个AS,并在这两个新的 AS 之间执行 AS 间路由选择。(前面讲过，OSPF 通过将一个 AS 分成区域而建立这样的层次结构。)
- 性能:由于 AS 间路由选择是面向策略的，因此所用路由的质量(如性能)通常是次要关心的问题(即一条更长或开销更高但能满足某些策略条件的路由也许被采用了，而更短但不满足那些条件的路由却不会被采用)。我们的确看到了在 AS 之间，甚至没有与路由相关的开销(除了 AS 跳计数外)概念。然而在一个 AS 内部，这种对策略的关心就不重要了，可以使路由选择更多地关注一条路由实现的性能级别。
R8 当一台OSPF路由器发送他的链路状态信息时，他仅向那些直接连接的邻居发送，解释理由
- OSPF是使用LS的，LS是全局的。
- 错误。使用OSPF，路由器将其链路状态信息广播到他所属的自治系统中的所有其他路由器，而不仅仅是直接连接的邻居。因为对于OSPF，每一个路由器都需要构建整个AS的完整拓扑，然后在本地运行Dijkstra算法来计算最短路径。来确定到同一AS中的所有其他节点的最低成本路径。
P3 Djisktra算法计算x到所有节点的最短路径。
- |步骤|N’|D(t),p(t)|D(u),p(u)|D(v),p(v)|D(w),p(w)|D(y),p(y)|D(z),p(z)|
  |—-|—-|—-|—-|—-|—-|—-|—-|
  |0|x|∞|∞|3,x|6,x|6,x|8,x|
  |1|xv|7,v|6,x||6,x|6,x|8,x|
  |2|xvu|7,v|||6,x|6,x|8,x|
  |3|xvuw|7,v||||6,x|8,x|
  |4|xvuwy|7,v|||||8,x|
  |5|xvuwyt||||||8,x|
  |6|xvuwytz|||||||
- x节点的汇集树sink tree是x->v->u->w->y->t->z
P5 假设每个节点初始时知道到它的每个邻居的费用，考虑距离向量算法，并显示在节点z中的距离表表项（一次次迭代）
- 类似于：
- |节点|到x的距离|到y的距离|到z的距离|
  |—-|—-|—-|—-|
  |x|1|4|7|
  |y|∞|2|∞|
  |z|2|∞|0|
- |节点|到x的距离|到y的距离|到z的距离|
  |—-|—-|—-|—-|
  |x|1|3|6|
  |y|4|2|5|
  |z|2|4|0|
P14
- 路由器3c从4c处学习到前缀x，所以是外部BGP；
- 路由器3a从3c处学习到前缀x，所以是内部BGP；
- 路由器1c从3a处学习到前缀x，所以是外部BGP；
- 路由器1d从1c处学习到前缀x，所以是内部BGP；
P15 路由器的表项如何选择接口？一旦路由器1d知道了x的情况，它将一个表项(x，1)放人其转发表中。
- a.对这个表项而言，I将等于I1还是I2?用一句话解释其原因。
- b.现在假定在AS2和AS4之间有一条物理链路，显示为图中的虚线。假定路由器1d知道经AS2以及经AS3能够访问到x。I将设置为I1还是I2?用一句话解释其原因。
- c. 现在假定有另一个AS，它称为AS5，其位于路径AS2和AS4之间(没有显示在图中)。假定路由器1d知道经AS2AS5AS4以及经AS3AS4能够访问到xI1将设置为I1还是I2?用一句话解释其原因。
- 总结路由器的表项选择接口的原则是：
  - 先看AS之间的谁经过的AS数少
  - 再看AS内部的哪一条跳数少
  - 实在都一样，随机选呗，反正不能有两个表项

第四章网络层数据平面

R11 描述在输入端口会出现分组丢失的原因。描述在输入端口如何消除分组丢失（不使用无限大缓存区）
- 如果分组到达输入端口的速率超过交换结构处理速率，则分组将需要在输入端口排队。当队列增长到溢出输入端口缓存区的时候，分组将被丢弃。
- 如果交换结构速度至少是出入线速度的n倍，那么就不会出现分组丢失。n是输入端口的数量。
R17 假定主机A向主机B发送封装在一个数据报中的TCP报文段。当主机B接收到该数据报时，主机B中的网络层怎样知道它应当将该报文段(即数据报的有效载荷)交给TCP而不是UDP或某个其他东西呢?
- 8比特的协议字段值指示了IP数据报的数据部分应交给哪个特定的运输层协议。
R30 比较ipv4和ipv6的首部字段。他们有相同的字段吗？
|IPv4|IPv6|
|—-|—-|
|版本|版本|
|服务类型|服务类型|
|数据报长度|有效载荷长度|
|协议|下一个头部|
|TTL|跳数限制|
R33 基于目的地转发和OpenFlow流表之间有什么差异？
- 基于目的地转发的转发表仅包括IP报头部字段以及对应的输出链路接口
- 而OpenFlow流表包括了更多的字段：
  1. 首部字段值集合：用于匹配；
  2. 计数器集合：当分组和流表条目匹配时进行更新；
  3. 当分组分配流表项时采取的动作集合
P14 考虑向具有700字节MTU的一条链路发送一个2400字节的数据报。假定初始数据报标有标识号422。将会生成多少个分片?在生成相关分片的数据报中各个字段的值是多少?
- 最大传输单元(MTU)为700字节，其中要包含20个字节的IP首部，能够存放680字节的数据。数据报为2400字节，除去20字节的IP首部，共有2380字节的数据。分片的个数为2380/680~4。四个分片的标识号均为422，片偏移字段分别为0、85、170、255，标志分别为1、1、1、0
  - 片偏移字段是IPv4首部中的一个字段，用于支持数据报的分片和重组。当一个数据报太大而无法通过网络中某个段（如某个具有较小最大传输单元（MTU）的链路）时，它会被分成多个较小的片段传输。每个片段都是原始数据报的一部分，并且包含相同的目的地址。
  - 片偏移字段表示该片段在原始数据报中的相对位置。它的单位是8字节（64位）块。这意味着通过将片偏移字段的值乘以8，可以确定该片段数据的起始字节在原始数据报中的位置。
  - 片偏移字段使得接收端能够正确地将接收到的片段重新组装成完整的原始数据报。每个片段的IPv4首部都会包含片偏移值，接收端根据这个值将所有片段按正确顺序组装起来。
首先，我们需要确定一个合适的子网掩码来满足条件：总共有240台主机。这些主机需要被分配到4个部门。

确定子网掩码
主机位数：因为每个部门至少需要60台主机，我们需要至少6位来表示主机部分（因为$2^6=64$，足以容纳60台主机，同时留有空间用于网络地址和广播地址）。

部门位数：我们需要为4个部门划分网络，所以我们需要2位来表示部门（因为$2^2=4$）
子网掩码：剩下的位数将用于子网掩码。由于我们需要6位给主机，2位给部门，剩下的位数（32 - 6 - 2 = 24位）给网络部分，这意味着我们使用的子网掩码是/24。但是，由于我们需要为每个部门分配一个独立的网络，我们需要更小的子网，即更多的主机位。

子网划分
由于我们需要4个部门，每个部门至少60台主机，我们可以这样划分：

子网掩码：/26（因为/26提供64个地址，足以容纳每个部门的60台主机，同时还有2个地址用于网络地址和广播地址）。
网络地址分配
使用192.168.100.0/24作为基础网络，我们可以为每个部门分配如下的/26子网：

第一个部门：192.168.100.0/26 (网络地址范围192.168.100.0 - 192.168.100.63)
第二个部门：192.168.100.64/26 (网络地址范围192.168.100.64 - 192.168.100.127)
第三个部门：192.168.100.128/26 (网络地址范围192.168.100.128 - 192.168.100.191)
第四个部门：192.168.100.192/26 (网络地址范围192.168.100.192 - 192.168.100.255)
这样，每个部门都有自己的子网，且每个子网都有足够的地址空间来容纳60台主机。
端口范围
一般用到的是1到65535，其中0一般不使用。端口号可分为3大类：
1、公认端口（Well Known Ports）：从0到1023，它们紧密绑定（binding）于一些服务。通常这些端口的通讯明确表明了某种服务的协议。例如：80端口实际上总是HTTP通讯。
2、注册端口（Registered Ports）：从1024到49151。它们松散地绑定于一些服务。也就是说有许多服务绑定于这些端口，这些端口同样用于许多其它目的。例如：许多系统处理动态端口从1024左右开始。
3、动态和/或私有端口（Dynamic and/or Private Ports）：从49152到65535。理论上，不应为服务分配这些端口。实际上，机器通常从1024起分配动态端口。但也有例外：SUN的RPC端口从32768开始。

第三章传输层
R7 假定在主机C上的一个进程有一个具有端口号6789的UDP套接字。假定主机A和主机B都用目的端口号6789向主机C发送UDP段。这两台主机的这些报文段在主机C都被描述为相同的套接字吗？如果是这样的话，主机C的进程如何知道源于不同两台主机的这个报文段？
- 被描述为相同的套接字，根据源IP地址区分。
- udp socket只和目标ip地址和目标端口号相捆绑，所以A和B发过来的都定位成相同的socket发送给同一个进程。
- 怎么回传呢？udp socket的api中的receive from中有一个参数，包括了源地址ip和端口号，所以可以根据这个参数来区分是谁发过来的，回传回去。
R9 rdt协议中为什么要引入序号？
- 序号可以用来区分到达的数据包是重传还是新数据，也可以用来判断数据包顺序是否正确
- 也可以进行排序，得知哪些是乱序的
R10 为什么rdt要引入定时器？
- 定时器用来检测数据包是否丢失，如果超时则重传
R14
- A发送给B一个大数据，B如果没有要发送的数据，就单独发送确认；如果有，就在发送的数据里捎带确认
- 在连接过程中，tcp的rwnd（接受窗口），维护一个接受的buffer，buffer的可用空间随时间变化，B通过捎带或者单独给控制信息给发送方，发送方按照这个来设置发送窗口。rwnd也会随时间动态变化
  - rwnd = 接收缓存 - 主机B中已经接收但未读取的数据量
- A向B发送一个大文件，主机A发送但未被确认的字节数不会超过receive buffer的大小，也不会超过空闲的buffer的数量（流量控制）
- A用TCP向B发送大文件，如果对于这条连接的一个报文段的序号为m，则对于后继报文段的序号必须为m+1（错误），为m+该段的字节数量。
  - 这是因为TCP是字节流协议，不是报文段协议，所以序号是按照字节来的，而不是按照报文段来的。
- TCP报文段在首部有一个rwnd字段
- 假定在一条TCP连接中最后的sampleRTT等于1秒，那么对于该连接的TimeoutInterval的当前值必定大于等于1秒？
  - 不一定，TimeoutInterval的当前值是根据sampleRTT和estimatedRTT来计算的，如果sampleRTT和estimatedRTT相差很大，那么TimeoutInterval的当前值可能会小于1秒。
  - DevRTT = (1-β) DevRTT + β |SampleRTT - EstimatedRTT|, β = 0.25
  - EstimatedRTT = (1-α) EstimatedRTT + α SampleRTT, α = 0.125
  - 超时时间间隔：TimeoutInterval = EstimatedRTT + 4 * DevRTT
- A TCP B 发送一个序号为38的4个字节的报文段，在这个相同的报文段中，确认号必定是42？
  - 取决于B是否接受到了这个报文段，如果接受到了，那么确认号是42，如果没有接受到，那么确认号是38（期待从38开始传输）。
R15 A TCP B发送两个紧挨着的TCP报文段，第一个报文段的序号为90，第二个报文段序号为110
- 第一个报文段有多少数据？
  - 20字节
- 假设第一个报文段丢失而第二个人报文段到达，B将发送确认号为多少？
  - 90，累积确认（cumu lative acknowledgment）
R18 考虑TCP的拥塞控制。当发送方定时器超时时，其ssthresh值将被设置为原来的一半？
- 错误。当发送方定时器超时时，ssthresh值将被设置为当前拥塞窗口cwnd的一半。
- ssthresh（慢启动阈值，Slow Start Threshold）是TCP（传输控制协议）拥塞控制算法中的一个关键参数。它用于控制TCP连接的拥塞窗口（cwnd）的增长行为，从而影响数据的传输速率。ssthresh的主要作用是作为慢启动（Slow Start）和拥塞避免（Congestion Avoidance）两个阶段之间的界限。
  0)F.png?raw=true>)
  - Reno算法是TCP拥塞控制算法的一种，用于调整网络中的数据传输速率以避免拥塞。它在TCP Tahoe算法的基础上进行了改进，引入了快速恢复（Fast Recovery）机制。Reno算法主要通过四个阶段来控制数据的传输：慢启动（Slow Start）、拥塞避免（Congestion Avoidance）、快速重传（Fast Retransmit）和快速恢复（Fast Recovery）。
  1. 【状态】慢启动（Slow Start）：在连接开始时，拥塞窗口（cwnd）从1个最大段大小（MSS）开始，每收到一个确认ACK，cwnd加倍。当cwnd达到慢启动阈值（ssthresh）时，进入拥塞避免阶段。
  2. 【状态】拥塞避免（Congestion Avoidance）：在此阶段，cwnd的增长方式变为线性增长，即每经过一个往返时间（RTT），cwnd增加1个MSS。这有助于避免网络拥塞。
  3. 【事件】快速重传（Fast Retransmit）：当发送方收到三个重复的确认（Duplicate ACKs）时，立即重传未被确认的最小序号的数据包，而不是等待超时发生。这意味着网络可能出现了数据包丢失。
  4. 【状态】快速恢复（Fast Recovery）：在快速重传之后，Reno算法进入快速恢复阶段。在这个阶段，ssthresh设置为当前拥塞窗口的一半，cwnd设置为ssthresh加上3个MSS（对应于收到的三个重复ACK）。对于后续收到的每个重复ACK，cwnd增加1个MSS。当收到新的确认时，cwnd设置为ssthresh的值，算法返回到拥塞避免阶段。
- Reno算法通过这些机制能够在检测到拥塞迹象时快速减少发送速率，同时在网络条件允许时逐渐增加速率，从而有效地利用网络资源并减少拥塞的可能性。
- tahoe算法收到三个冗余的ack和超时一样，cwnd变为1，ssthresh变为原来的一半
P1
- talnet使用23端口，ftp使用21端口，smtp使用25端口，http使用80端口
P3 UDP和TCP使用反码来计算它们的检验和（发送方）。假设你有下面3个8比特字节:01010011，01100110，01110100。这些8比特字节和的反码是多少?(注意到尽管UDP和TCP使用16比特的字来计算检和，但对于这个问题，你应该考虑8比特和。)写出所有工作过程。UDP为什么要用该和的反码，为什么不直接使用该和呢?使用该反码方案，接收方如何检测出差错?1比特的差错将可能检测不出来吗?2比特的差错呢?
- 01010011 + 01100110 = 10111001
- 10111001 + 01110100 = 100101101进位回滚=00101110
- 反码是11010001，即为checksum。将checksum放在UDP的checksum字段中，传输给接收方，接收方将数据报的所有16比特字节相加，包括checksum字段，如果和的反码为全1，则认为数据报没有差错。如果和的反码不是全1，则认为数据报有差错。
- UDP使用反码来计算检验和，是因为反码可以检测出1比特的差错，但是不能检测出2比特的差错。
P8 画出rdt3.0接收方的FSM
- rdt3.0引入的超时重传机制带来的问题是重复，但是重复已经在rdt2.2中解决了，所以rdt3.0接收方的FSM和rdt2.2是一样的。
P15 窗口长度设置成多少的时候，能使信道的利用率超过90%？假设分组的长度为1500字节（包括首部字段和数据）
- 信道利用率定义为发送方在发送数据和等待确认过程中有效使用信道的比例
- 传输时延：$t_{trans}=\frac{L}{R}=\frac{1500 × 8 bits/pkt}{10^9 bit/s}=12 \mu s$
- $U_{sender}=\frac{n*\frac{L}{R}}{RTT+\frac{L}{R}}=\frac{0.012n}{30.012}>0.9$
- 这个公式基本上是在计算在一次完整的发送-确认循环中，发送方有效发送数据的时间与总循环时间的比例。如果这个比例接近1（或100%），则意味着信道几乎在所有时间都被有效利用；如果这个比例较低，则意味着有很多时间信道是空闲的，或者发送方在等待确认，这降低了信道的利用率。
- $n>2250.9$,所以窗口长度设置为2251的时候，能使信道的利用率超过90%
P23 GBN和SR最大窗口和序号空间的关系
- 为了避免接收方发回给发送方的ACK全部丢失后，重发的旧包被接收方当成了新包，需要满足以下条件：
- 序号字段的比特数为n，序号空间：$2^n$,那么GBN发送窗口的最大空间为$2^{n}-1$，SR发送窗口的最大空间为$2^{n-1}$ 。这是因为SR是非累计确认，所以必须要保证窗口滑动之后，每一个序号都不会和之前的重复。但是GBN是累计确认，所以只需要保证窗口内的序号开头不重复即可。
P24 判断
- 对于SR,发送方可能会收到落在其当前窗口之外的分组的ACK？
- 对于GBN,发送方可能会收到落在其当前窗口
  - GBN和SR都有可能。旧分组的ACK滞留了。
- 当发送方和接收方窗口长度都为1的时候，比特交替协议与SR协议是等价的？
- 当发送方和接收方窗口长度都为1的时候，比特交替协议与GBN协议是等价的？
  - 都是正确的。
  - GBN: swndow size≥1, rwndow size=1；
  - SR: swndow size≥1, rwndow size≥1；
  - 比特交替协议，也就是stop-and-wait协议，如果swndow size=1, rwndow size=1；GBN 和SR都会退化成“比特交替协议”。
    第二章应用层
P10 考虑一条10米短链路，某发送方经过它能够以 150bps 速率双向传输。假定包含数据的分组是100K比特长，仅包含控制(如ACK或握手)的分组是200比特长。假定N个并行连接每个都获得1/N的链路带宽。现在考虑HTTP协议，并且假定每个下载对象是100Kb长，这些初始下载对象包含10个来自相同发送方的引用对象。在这种情况下，经非持续HTTP的并行实例的并行下载有意义吗?现在考虑持续 HTTP。你期待这比非持续的情况有很大增益吗?评价并解释你的答案。
- 1. 非持久HTTP的并行实例的并行下载。
    - 请求连接建立（200b），连接确认（200b），请求对象（200b），返回对象（100Kb）；对于十个子对象并行建立连接，但是只有1/10带宽:（200*3）+100k = 100.6Kb。
      于是$t{I}=3t_1+ t_2$，$t_1=\frac{200}{150}$,$t_2=\frac{100k}{150}$，$t{II}=3t1’+t_2’$,$t_1’=\frac{200}{15}=10t_1$,$t_2’=\frac{100k}{15}=10t_2$，$t=t{I}+t_{II}+8t_p$
- 1. 持久HTTP串行下载
    - $t=2t_1+t_1+t_2+10(t_1+t_2)+24t_p$
- 1和2 其实差不多，因为带宽太小了，怎么传其实无所谓。$t_p$是传播时间，一趟就算一个$t_p$，但是其实可以忽略不计。
P22 考虑向N个对等方分发F=15Gb的一个文件。该服务器具有$u_s=30Mbps$的上载速率，每个对等方具有$d_i=2Mbps$的下载速率和上载速率$u$。对于N=10、100和1000并且u=300kbps、700kbps 和2Mbps，对于N和u的每种组合绘制出确定最小分发时间的图表。需要分别针对客户-服务器分发和 P2P 分发两种情况制作。
- C/S
  - $D{C/S}=\max{\frac{NF}{u_s},\frac{F}{d{min}}}$
  - 随着N的增加，瓶颈从客户端转移到了服务端。
- P2P
  - $D{P2P}=\max{\frac{F}{u_s},\frac{F}{d{min}},\frac{NF}{u_s+\sum u_i}}$
  - 随着N的增加，瓶颈从客户端转移到了服务端。
P9 考虑图 2-12，其中有一个机构的网络和因特网相连(15Mbps)。假定对象的平均长度为850k比特，从这个机构网的浏览器到初始服务器的平均请求率是每秒16个请求。还假定从接入链路的因特网一侧的路由器转发一个HTTP请求开始，到接收到其响应的平均时间是3秒(参见2.2.5节)。将总的平均响应时间建模为平均接入时延(即从因特网路由器到机构路由器的时延)和平均因特网时延之和。对于平均接入时延，使用 $\Delta/(1-\Delta \beta)$，式中$\Delta$是跨越接入链路发送一个对象的平均时间，$\beta$是对象对该接入链路的平均到达率。
- a.求出总的平均响应时间。
- b.现在假定在这个机构 LAN 中安装了一个缓存器。假定命中率为0.4，求出总的响应时间。
- a. 无缓存
  - $t_{\Delta}=\frac{L}{R}=\frac{850k}{15Mbps}$
  - 流量强度$I=\frac{\beta L}{R}$,其中$\beta$是16个请求/秒，L是850k比特，R是15Mbps
  - $t{access}=\frac{1}{1-I}\cdot t{\Delta}=\frac{t{\Delta}}{1-t{\Delta}\beta}$
  - $t{total}=t{access}+t{internet}=t{access}+3$
- b. 有缓存
  - hit rate=0.4，miss rate=0.6
  - 流量强度$I’=\frac{0.6 \beta L }{R}$
  - $t{access}’=\frac{1}{1-I’}\cdot t{\Delta}$
  - $t{total}’=t{access}’+t{internet}=t{access}’+3s=3.124s$
  - $t{arange}’=0.4 \cdot t{LAN}+0.6 \cdot t_{total}’$
P23.考虑使用一种客户-服务器体系结构向N个对等方分发一个F比特的文件。假定一种某服务器能够同时向多个对等方传输的流体模型，只要组合速率不超过$u_s$，则以不同的速率向每个对等方传输。
- a. 假定 $us/N≤d{min}$。定义一个具有 $NF/u_s$分发时间的分发方案。
- b. 假定 $us/N≥d{min}$。定义一个具有 $F/d_{min}$分发时间的分发方案。
  - 参考P22。a是客户端瓶颈，b是服务端瓶颈。
- c.得出最小分发时间通常是由$max|NF/u{s}，F/d{min}|$所决定的结论。
(2) The transfer of a web document from one host to another is : ( A )
- A. loss-intolerant and time insensitive
- B. loss-tolerant and time sensitive
- C. loss-intolerant and time sensitive
- D. none of the above
- HTTP使用tcp协议，网页传输是不可容忍丢失的，但是对时间不敏感。

第一章

R9 拨号调制解调器、HFC、DSL和FTTH都用于住宅接入。对于这些技术，给出每种技术的传输速率的范围，并讨论它们的传输速率是共享的还是专用的。
R11.假定在发送主机和接收主机间只有一台分组交换机。发送主机和交换机间以及交换机和接收主机间的传输速率分别是R1和R2。假设该交换机使用存储转发分组交换方式，发送一个长度为L的分组的端到端总时延是什么?(忽略排队时延、传播时延和处理时延。)
- t= L/R1 + L/R2
R12.与分组交换网络相比，电路交换网络有哪些优点?在电路交换网络中，TDM比FDM有哪些优点?
R13.假定用户共享一条2Mbps链路。同时假定当每个用户传输时连续以1Mbps传输，但每个用户仅传输20%的时间。
- a.当使用电路交换时，能够支持多少用户?
  - 2Mbps/1Mbps=2
- b.作为该题的后继问题，假定使用分组交换。为什么如果两个或更少的用户同时传输的话，在链路前面基本上没有排队时延?为什么如果3个用户同时传输的话，将有排队时延?
  - 两个用户同时传输，链路前面没有排队时延，因为链路的传输速率是2Mbps，两个用户的传输速率是1Mbps，所以链路的传输速率大于两个用户的传输速率，不会出现排队时延。
  - 三个用户同时传输，链路前面有排队时延，因为三个用户的传输速率是3Mbps，大于链路的传输速率2Mbps，所以会出现排队时延。
- c.求出某指定用户正在传输的概率。
  - 0.2
- d.假定现在有3个用户。求出在任何给定的时间，所有3个用户在同时传输的概率。
  - $0.2^3$
R19.假定主机A要向主机B发送一个大文件。从主机A到主机B的路径上有3段链路，其速率分别为R1=500kbps,R2=2Mbps，R3=1Mbps。
- a.假定该网络中没有其他流量，该文件传送的吞吐量是多少?
  - 最小的链路速率是500kbps，所以吞吐量是500kbps
- b.假定该文件为4MB。用吞吐量除以文件长度，将该文件传输到主机B大致需要多长时间?
  - 4MB/500kbps=4×10^6×8/500×10^3=64s
  - 计算时通常认为k=1000,K=1024,B=8b
  - 机网中的K、M、G、T等表示的是1000的幂次方，而计组中的K、M、G、T等表示的是1024的幂次方。
- c.重复(a)和(b)，只是这时R2减小到100kbps。
  - 100kbps，吞吐量是100kbps，4MB/100kbps=320s
R23 网络协议栈中有几个层次？每层的任务是什么？
- 5层
  - 应用层：应用层协议，如HTTP、SMTP、FTP、DNS
  - 传输层：负责提供端到端的通信服务，管理数据包的分割、传输和重组，保证数据的完整性。
  - 网络层：负责数据包从源到目的地的传输和寻址、路由选择，包括分段和重组，确保数据包能跨越多个网络从源到达目的地。
  - 数据链路层：负责在相邻的网络设备之间建立、维护和终止链路。它提供了帧的传输，包括帧的同步、差错控制等
  - 物理层：负责传输原始比特流，通过物理媒介传输数据。加载和还原数字信号。
主机处理的是所有层次，路由器处理网络层，链路层交换机处理数据链路层。
P2 对于经过N段链路一个接一个地发送P个分组，分组长度为L，传输速率均为R，则总的端到端时延是多少？
- 一个接一个：每隔$\frac{L}{R}$发送一个分组
- $t=N \frac{L}{R}+(p-1)\frac{L}{R}$
P3 考虑一个应用程序以稳定的速率传输数据(例如，发送方每k个时间单元产生一个N比特的数据单元，其中k较小且固定)。另外，当这个应用程序启动时，它将连续运行相当长的一段时间。回答下列问题，简要论证你的回答:
- a.是分组交换网还是电路交换网更为适合这种应用?为什么?
  - 电路交换网，因为这种应用程序的数据传输速率是稳定的，电路交换网适合传输稳定速率的数据。
- b.假定使用了分组交换网，并且该网中的所有流量都来自如上所述的这种应用程序。此外，假定该应用程序数据传输速率的总和小于每条链路的各自容量。需要某种形式的拥塞控制吗?为什么?
  - 不需要拥塞控制，不会引起拥塞。
P6 区分传播时延和传输时延。考虑两台主机AB由一条速率为R bps的链路相连。相隔m米，沿着该链路的传播速率为s m/s.主机A向B发送一个长度为L比特的分组。
- a. 用m和s来表示传播时延$d_{prop}$
  - $d_{prop}=\frac{m}{s}$
- b. 用L和R来表示传输时延$d_{trans}$
  - $d_{trans}=\frac{L}{R}$
- c. 忽略处理和排队时延，求出从主机A发送分组到主机B接收到分组的总时延
  - $t=d{prop}+d{trans}$，这里的传播延迟其实是最后一个比特离开发送方到达接收方的时间
- d. 假定A在$t=0$时刻发送分组，在$t=d_{trans}$，该分组的最后一个比特在哪里？
  - 刚刚离开发送方A
- e. 假定$d{prop}$ 大于 $d{trans}$，在$t=d_{trans}$,该分组的第一个比特在哪里？
  - 在路上，A刚打完分组，但是还没到达接收方
- f. 假定$d{prop}$ 小于 $d{trans}$，在$t=d_{trans}$,该分组的第一个比特在哪里？
  - 已经到了接收方
- g. 假定$s=2.5*10^8 m/s,L=120b,R=56kbps$。求使得传输时延和传播时延相等的m的值。
  - $\frac{m}{s}=\frac{L}{R}$,m=536m
P14 【公式】考虑排队时延，令I 表示流量强度：$I=L\frac{\alpha}{R}$。假定排队时延的形式为$\frac{IL}{(1-I)R}$，其中$I<1$.
- a. 总时延（排队时延加上传输时延）
  - $t=\frac{IL}{(1-I)R}+\frac{L}{R}=\frac{1}{(1-I)}\frac{L}{R}$
- b. 以L/R为函数画出总时延图
  - $t=\frac{1}{(1-I)}\frac{L}{R}=\frac{1}{1-\frac{L\alpha}{R}}\frac{L}{R}$,当$\frac{L}{R}=\frac{1}{\alpha}$时，时延越接近无穷大
P22.考虑图1-19b。假定服务器与客户之间的每条链路的丢包概率为P，且这些链路的丢包率是独立的。一个(由服务器发送的)分组成功地被接收方收到的概率是多少?如果在从服务器到客户的路径上分组丢失了，则服务器将重传该分组。平均来说，为了使客户成功地接收该分组，服务器将要重传该分组多少次?
- 成功的概率$p_s=(1-p)^n$
- 概率论算期望
- 需要重传次数为需要传输次数-1：$N=\frac{1}{p_s}-1=\frac{1}{(1-p)^n}-1$
P25
- a. $R \cdot t_{prop}$
- b. $R \cdot t_{prop}<8×10^5$
- c. 带宽延迟积：$R \cdot t_{prop}$，物理意义是链路上最大的数据量
- d. 计算一个比特的宽度：$\frac{1}{R} \cdot s$,$s=2.5*10^8m/s=125m$
- e. 一个比特的宽度一般式：$\frac{1}{R} \cdot s$
P31
- a. $t_1=3\cdot \frac{L}{R}=4×3s=12s$
- b. $t_2= 5\cdot 3 ms+(800-1)*5ms=4.01s$
(1) The most important kinds of delay at each node along the path is nodal processing delay , queuing delay , Transmission delay__ , Propagation Delay__ .
(2) The task of the data link layer is providing data transmission services between __ ; The task of the network layer is providing data transmission services between __ ; and the task of transport layer is providing data transmission services between __.
- 在OSI模型或TCP/IP模型中，每一层都提供特定的服务，以下是填空的答案：
  - 数据链路层：提供数据传输服务在相同网络中的节点之间（或在直接相连的网络设备之间）。
  - 网络层：提供数据传输服务在不同网络中（或在源主机和目的主机之间，跨越多个可能的网络）。
  - 传输层：提供数据传输服务在端系统之间（或在发送端应用程序和接收端应用程序之间）。
    
    因此，填空应该是：
    
    The task of the data link layer is providing data transmission services between nodes on the same network; The task of the network layer is providing data transmission services between different networks; and the task of the transport layer is providing data transmission services between end systems.

综合刷题

选择题+填空

(9) What is the ICMP used for ？ ( C )
A. Error reporting B. Used by ping C. A and B D. None above.
(5) The job of delivering the data in a transport-layer segment to the correct socket is called ( A ).
A. Demultiplexing B. Multiplexing
C. TDM D. FDM
(1) It is the architecture for TCP/IP protocol stack, which one below doesn’t belong to the application layer ( B )?
A. TELNET　 B.ICMP　　C. POP　　D. SMTP

ICMP是网络层的协议，其他都是应用层的协议
将传输层段中的数据传送到正确的套接字的工作称为解复用。此过程涉及从传输层段（例如 TCP 或 UDP 数据包）中提取数据，并将其路由到与段的目标端口号匹配的主机上的适当应用程序或服务。解复用是 TCP 和 UDP 协议中传输层的一项关键功能。

alt text

Which one of the following media has characteristics as high-speed operation and immune to electromagnetic noise? ( C )
A. Coaxial cable（同轴电缆） B. Radio（无线电）
C. Fiber optic（光纤）D. Twisted pair（双绞线）

光纤传输速度快，不受电磁干扰

(1) The task of the data link layer is providing data transmission services between Adjacent nodes__;
The task of the network layer is providing data transmission services between _host_;
and the task of transport layer is providing data transmission services between _process__.

(3) Two routing protocols have been used extensively for routing within an autonomous system in the Internet: RIP protocol and OSPF_ protocol.

(5) RIP advertisements typically announce the number of hops to various destination; BGP updates, on the other hand, announce the _Path（Sequence of ASs on the routes）_to the various destinations.

(6) TCP provides a flow control（流量控制） service to its applications to eliminate the possibility of the sender overwhelming the receiver. Flow control mechanisms, such as the sliding window protocol, allow the receiver to manage the rate at which data is sent by the sender, preventing the sender from sending more data than the receiver can handle.

(7) The tool (command) that can be used to determine the number of hops to a destination and the round trip time (RTT) for each hop is traceroute (or tracert on some systems). This command uses a technique involving incrementing the Time to Live (TTL) field in IP packets and listening for ICMP Time Exceeded messages to discover the path to a destination and measure the RTT for each hop in the path.

（2）The two key functions of the network layer are:

Forwarding , routing

Routing: Determining the best path for data transmission across a network or between networks. This involves forwarding data packets from one node to the next until they reach their destination.
Logical Addressing: Assigning and managing logical addresses (such as IP addresses) to devices on the network, which enables data packets to be addressed and routed to their correct destinations.

判断题

以下是正确或错误陈述的答案：

错误：Traceroute 使用 ICMP（Internet 控制消息协议）或具有增加的 TTL（生存时间）值的 UDP 消息来确定源主机和目标主机之间的路由，而不是专门使用 ICMP。

正确：RDT（可靠数据传输）3.0 是一种停止等待协议，这意味着它会等待每个段的确认后再发送下一个段，这可能会导致性能问题。

错误：当用户请求包含文本和图像的网页时，客户端通常会发送多个请求（一个用于 HTML，其他用于每个图像的请求）并收到多个响应。

正确：对于 VoIP 等实时应用，UDP 通常比 TCP 更受欢迎，因为它提供较低的延迟，即使它不能保证交付或顺序。

正确：当窗口大小为 1 时，SR（滑动窗口）和 GBN（Go-Back-N）协议的功能相似，因为它们都是流量和错误控制机制，但方法不同。

错误：距离矢量路由算法不需要完整的网络拓扑信息。它们只需要知道到相邻路由器的成本以及这些路由器报告的距离。

错误：电子邮件客户端使用 POP3（邮局协议 3）从服务器检索电子邮件，但电子邮件通常使用 SMTP（简单邮件传输协议）传递到服务器。

错误：CSMA/CD 协议下可能会发生冲突，但该协议旨在通过让冲突设备停止传输并等待再重新传输来检测和管理冲突。

正确：TCP 段指向的套接字由封装 TCP 段的 IP 数据报中的目标端口号和 IP 地址确定。

错误：AS（自治系统）通常根据其路由策略向其邻居宣布最佳路由，而不一定是所有可能的路由。BGP（边界网关协议）用于此目的，它可以根据各种因素有选择地通告路由。

正确：(8) Both CIDR and NAT can lead to much more efficient use of the available IPv4 address space.

错误：(10) When a TCP segment arrives to a host, the socket to which the segment is directed depends on the destination port number and the destination IP address.

要用四元组表示，源IP，目的IP，源端口，目的端口

错误：HTTP, FTP and SMTP use TCP to be protocol of transport layer rather than UDP for Security. 前半句对，但是不是为了安全，而是为了可靠性。

大题

(1) Consider sending a packet from a source host to a destination host over a fixed route.Name the four factors of delay for the packet. Is the delay constant ? Why or why not? Identify which factor will most likely predominate (i.e. ,be the largest factor ) for 1M Byte Packets in a flow on the following different links.
a) 10 Mb/s LAN segment between two PCs in the same building
b) 1 Mb/s geosynchronous-orbit satellite (同步轨道卫星) link between the US and China
c) on the Internet between the US and China

(1) nodal processing delay, queuing delay, transmission delay, Propagation delay.
It’not constant, and depends on the consgestion.
a) transmission delay
b) propagation delay
c) queuing delay

DNS相关

(2) Domain Name System (DNS) uses a distributed approach as opposed to a single server. Why? Assume a client needs to find the IP address of www.newpool.org using the DNS. And assume the client has a local DNS server, but that server does not have any addresses cached. What are the DNS servers that are queried (in order) to find the IP address?

(2) Why: A distributed hierarchy of servers gives better scalability and does not present a single point of failure.
In order: Local - Root Top level(org) Authoritative (newpool.org) DNS server

域名系统 (DNS) 使用分布式方法有几个原因：

可扩展性：分布式系统可以比单个服务器更有效地处理大量请求和大量数据。
冗余：数据的多个副本存储在不同位置，从而降低数据丢失风险并提高容错能力。
负载分配：DNS 查询的负载分散在多个服务器上，防止任何单个服务器成为瓶颈。
引用位置：本地 DNS 服务器可以缓存经常访问的数据，从而减少延迟和根服务器上的负载。
灵活性：它允许更轻松地管理和更新 DNS 记录。

当客户端需要查找 www.newpool.org 的 IP 地址并且本地 DNS 服务器没有缓存该地址时，通常会发生以下 DNS 查询序列：

本地 DNS 服务器（递归服务器）：客户端首先查询其配置的本地 DNS 服务器。由于没有缓存，本地服务器将充当递归解析器的角色。
根 DNS 服务器：然后本地 DNS 服务器查询其中一个根 DNS 服务器。全球共有 13 个根服务器集群，本地服务器通常会根据其配置或最近的地理位置选择一个。
顶级域 (TLD) DNS 服务器：根服务器将响应指向负责 .org 域的顶级域 (TLD) DNS 服务器的引荐。
权威 DNS 服务器：收到引荐后，本地 DNS 服务器查询 TLD DNS 服务器，后者又将本地服务器引荐到 newpool.org 的权威 DNS 服务器。
最终 DNS 解析：本地 DNS 服务器查询 newpool.org 的权威 DNS 服务器，后者最终提供 www.newpool.org 的 IP 地址。

找到 IP 地址后，本地 DNS 服务器会缓存此信息以供将来的请求使用，从而减少再次执行完整解析过程的需要。此缓存机制是 DNS 效率的一个关键方面。

tcp滑动窗口flow control、GBN、SR相关

(3)Try to describe the main principles of reliable data transfer for GBN

i. “window” of up to N, consecutive unack’ed pkts allowed.
ii. ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
a) may receive duplicate ACKs (see receiver)
b) Only a single timer for the oldest transmitted but not yet acknowleged.
timeout(n): retransmit pkt n and all higher seq # pkts in window

When a TCP connection is established, the value of Rev Window in the segment header is set by the receiver

子网划分

(4) Consider a subnet with prefix 222.201.130.64/26. Give an example of one IP address(of form xxx.xxx.xxx.xxx) that can be assigned to an interface in this network. Suppose an ISP owns the block of addresses of the form 222.201.130.64/26. And suppose it wants to create four subnets from this block, with each block having the same number of IP addresses. What are the prefixes(of form a.b.c.d/x) for the four subnets?

222.201.130. 64~ 222.201.130.127
Four subnets: 222.201.130.64/28
222.201.130.80/28
222.201.130.96/28
222.201.130.112/28

alt text

TCP拥塞控制

(2) alt text
a) Identify the intervals of time when TCP slow start is operating.

b) Identify the intervals of time when TCP congestion avoidance is operating.

c)After 14th transmission round,is segment loss detected by a triple duplicate ACK or by a timeout? And which version of TCP protocol(Reno or Tahoe) is used base on this information?

d) During what transmission round is the 50th segment sent?

e) Assuming a packet loss is detected after the 23rd round by the receipt of a triple duplicate ACKs, what will be the values of the congestion window size and Threshold?

a)[1,6],[20,23]
b) [6,14],[15,19]
c)A triple duplicate Ack; Reno
d) 6
e) 4, 4（crwd不加3，则快速重传后，cnwd和sstread相等了）

CRC(Cyclic Redundancy Check)计算题

B站链接：[CRC校验]手算与直观演示

(3) A bit stream l01101001 is transmitted using the standard CRC method. The generator polynomial is $x^3 + x^2 + 1$.
- (a) Show the actual bit string transmitted, and the calculating process is required.
  - 101101001010
- (b) Suppose the fifth bit from the left is inverted during transmission. Show that this error is detected at the receiver end.
  - If the fifth bit from the left of the CRC code is inverted, then the code is 101111001010. When it is divided by 1101, the remainder is not zero, so the transmission error can be detected by the receiver.
(4) Please describe the goal and algorithm process of exponential backoff in the Ethernet CSMA/CD.
- goal：adapt retransmission attempts to estimated current load，for heavy load: random wait will be longer
- 算法：当传输一个已经经历了 $n$ 次碰撞的帧时，节点从 ${0,1,2,…2^n-1}$ 中随机选择 $K$ 的值。因此，一个帧经历的碰撞越多，选择 $K$ 的间隔就越大。对于以太网，节点等待的实际时间是 $K \cdot 512$ bits 倍(即，将512位发送到以太网所需的时间的K倍)，$n$ 可以取的最大值为10。当16次碰撞后，放弃传输。

传输层

alt text
because the offset is in units of 8 bytes

链路层

(14) Which of following states about Switch of data link layer is error? ( C )
A. Plug-and-play and self-learning
B. Buffer frame and selectively forward frame to one-or-more outgoing links when flame is to be forwarded
C・ All nodes connected to Switch can collide with one another
D. Uses CSMA/CD to access segment

todo

rtt（round trip time）：往返时间，即发送数据包到接收到对应的ACK的时间
总结各个协议的层次

简答题

List 5 kind of OSPF messages (packets), and explain when use these messages (packets).
- Solution：
  Hello： ①启动时 ②周期性发送keep-alive消息时。
  DD（数据库描述）：链路状态数据库的摘要，用于两个OSPF路由器处于交换状态。
  LSR（链路状态请求）：当一个OSPF路由器知道另一个路由器有关于链路的完整记录时发送。
  LSU（链路状态更新）： ①作为LSR的回答 ②当OSPF路由器发现其链路已更改时发送。
  LSA（链路状态确认）：当OSPF路由器收到LSU时，它必须发回LSA。
Try to explain the work principle of switch(交换机).
- Principle:
  - Flooding
  - Filtering
  - Forwarding
  - Learning
（猜测）TCP/IP？
不同网络实现信息传输的协议簇

2024考后回忆

ipv6没复习到
出了好几个路由表
NAT？？

第一章

电路交换网络和分组交换网络

电路交换网络

TDM相对于FDM的优点

电路交换网络的优点

分组交换网络

虚电路网络和数据报网络

数据报(datagram)网络

虚电路(Virtual circuit)网络

总结

住宅接入技术

1. 拨号调制解调器（Dial-up Modem）

2. 混合光纤同轴电缆（HFC）

3. 数字用户线（DSL）

4. 光纤到户（FTTH）

总结

各层运输单元及其封装关系（复用，解复用）

应用层

HTTP

持久与非持久HTTP

DNS

SMTP和其他邮件协议

FTP

P2P

应用层Q

传输层

UDP

UDP 报头

checksum

rdt

rdt1.0

rdt2.0

sending side

receiving side

rdt2.1

sender

receiver

rdt2.2

sender

receiver

rdt3.0

sender

receiver

流水线rdt

GBN和SR

TCP

三次握手

四次挥手

TCP段

往返时间的估计与超时

超时重传

flow control vs congestion avoidence

流量控制(Flow control)

传输层Q

网络层

路由算法

LS：链路状态

DV：距离矢量

LS和DV算法比较

消息复杂度（DV胜出）

收敛速度（LS胜出）

健壮性（LS胜出）

在网络中路由

OSPF

BGP

RIP(Routing Information Protocol)

为什么选择OSPF而不是RIP？

链路层和局域网

引论和服务

术语

链路层服务

成帧，链路接入

在两个相邻节点间的可靠传输

流量控制

差错检测和纠正

半双工和全双工

链路层在哪里实现？

差错检测和纠正

奇偶校验

单比特奇偶校验