计算机网络

一、选择题（共 30 题，每题 1 分）

1. 局域网（LAN）:概念，划分。（11 页，297 页）

Ethernet, wireless LAN 此题答案不明确

2. 域名解析服务（DNS）三层结构：根（root）DNS 服务器，顶级域（top-level domain）服务器，权威（authoritative）

DNS 服务器。DNS 记录结构。离你最近的 DNS 服务器上存放着什么？（87 页，90 页）

root name server: contacts authoritative name server if name mapping not known, gets mapping, returns mapping to local name server

顶级域 (TLD) servers: responsible for com, org, net, edu, etc, and all top-level country domains uk, fr, ca, jp.

权威Authoritative DNS servers:主机名映射为IP地址的DNS记录

本地Local Name Server: caches mapping

3. TCP 连接的建立：三次握手（three-way handshaking），SYN 和 ACK 标志位，顺序号和确认号。（169 页）

4. SMTP: 推协议（push protocol），邮件服务器间投递邮件，不使用中间邮件服务器，25 端口，只能用 7 位 ASCII

码表示。（77 页）

SMTP: sending server to receiving server, port 25, messages must be in 7-bit ASCII, SMTP server uses CRLF.CRLF to determine end of message, SMTP: push

5. TCP/IP 协议族（TCP/IP protocol suite）

application: FTP, SMTP, HTTP transport: TCP, UDP network: IP, routing protocols link: PPP, Ethernet

6. 流水线（pipelining）：允许发送方发送多个分组而无需等待确认，但必须增加序号范围且缓存分组。（146 页）

Pipelining: range of sequence numbers must be increased, buffering at sender and/or receiver

7. URL 的格式（format）：<协议>://<主机名>:<端口>/<路径> （谢希仁第五版教材 238 页）

8. C/S 结构与 P2P 结构（7 页，53 页）

Client-server architecture: server: always-on host, permanent IP address, server farms for scaling(规模化的服务器场). clients: communicate with server, may be intermittently(间歇) connected, may have dynamic IP addresses, do not communicate directly with each other(客户机相互之间不能直接通信).

Pure P2P architecture: no always-on server, arbitrary(任意的) end systems directly communicate, peers are intermittently connected and change IP addresses, example: Gnutella, Highly scalable(可扩展性高) but difficult to manage

9. 分用（demultiplexing）和复用（multiplexing）（128 页）

Demultiplexing at rcv host: delivering received segments to correct socket

Multiplexing at send host: gathering data from multiple sockets, enveloping data with header (later used for demultiplexing)

10. 后退 N 帧协议（go-back-N）：滑动窗口（sliding-window）协议。累积确认（cumulative acknowledgement）： 接收方对目前收到的最后一个正确有序的分组发出确认，丢弃所有乱序分组。如果超时，发送方将重传所有已 发送但还未被确认的分组。接收窗口大小为 1。（147 页）

11. 端口号（port number）的范围：0-65535，周知端口号（well-known port number）0-1023，登记端口号（registered

port）1024-49151，短暂端口号(ephemeral port)49152-65535。(129 页，谢希仁第五版教材 183 页)

周知端口号：是保留给诸如HTTP和FTP之类的周知应用层协议的

12. TCP 顺序号（sequence number）和确认号(acknowledge number)：顺序号是该报文段首字节的字节流编号，确 认号是期望收到的下一个报文段的顺序号。（157 页）

补：假定数据流由一个包含500 000字节的文件组成，MSS为1000字节，数据流的首字节编号0。TCP将为该数据流构建500个报文段。第一个报文段的序号被赋为0，第二个报文段的序号被赋为1000，以此类推。

从主机B到达的每个报文段中都有一个序号用于从B流向A的数据，主机A填充进报文段的确认号是主机A期望从主机B收到的下一字节的序号。

13. 发送窗口：受制于流量控制和拥塞控制，拥塞控制中的拥塞窗口（congestion window）和阈值（threshold）

（147 页，180 页，183 页）

sender limits transmission: LastByteSent-LastByteAcked < CongWin

After 3 dup ACKs: CongWin is cut in half, window then grows linearly

after timeout event: CongWin instead set to 1 MSS, window then grows exponentially(指数), to a threshold, then grows linearly(线性)

14. TCP 报文段结构，各字段的名称、作用和值。TCP 报文段首部的长度范围：20-60 字节。（157 页）

15. 拥塞控制（congestion control）：慢启动（slow start），拥塞避免（congestion avoidance），加性增乘性 减（AIMD）。（180-184 页）

additive increase: increase CongWin by 1 MSS every RTT until loss detected

multiplicative decrease: cut CongWin in half after loss

Slow Start: When connection begins, CongWin = 1 MSS, available bandwidth may be >> MSS/RTT, When connection begins, increase rate exponentially fast until first loss event

congestion avoidance: After 3 dup ACKs: CongWin is cut in half, window then grows linearly. after timeout event: CongWin instead set to 1 MSS, window then grows exponentially(指数), to a threshold, then grows linearly(线性)

在收到3个冗余的ACK后取消慢启动阶段的行为称为快速恢复(fast recovery)

16. 路由表的查询：最长前缀匹配。（207 页）

Longest prefix matching(例题见207页)

17. 网络流量（network traffic）和吞吐量（throughput）。（28 页，174 页，184 页）

Bottleneck link.

Average throughout: 0.75 W/RTT

18. RIP 协议：基于距离向量（DV）算法，以跳数（hop）作为代价度量（metrics）。（242 页，251 页）

Routing Information Protocol: distance vector algorithm, distance metric: # of hops (max = 15 hops)

RIP/UDP/IP

19. OSPF 协议：基于链路状态（LS）算法。（239 页，253 页）

Open Shortest Path First: uses Link State algorithm and Dijkstra’s algorithm, multiple same-cost paths allowed (only one path in RIP)

OSPF/IP

20. BGP 协议：自治系统（AS）间的选路。（255 页）

Border Gateway Protocol

BGP/TCP/IP

21. 差错控制方法（error detection method）：奇偶校验（parity check），校验和（checksum），循环冗余校验

（CRC），各自的特点和计算方法。（284 页）

Parity check: 偶校验：d个数据比特加1个比特中1的总数为偶数，奇校验：奇数个1。

在二维奇偶校验中可以检测到出现了单个比特差错的事实，而且可以利用列和行的小标来纠正。通常用于如音频CD这样的音频存储和回放设备。

Checksum：互联网检验和就是基于这种方法。所有的k比特进行求和，求和时有溢出就要被回卷，之后进行反码运算，得到检验和，在接收方将所有的k比特与检验和进行相加，如果无错就应该是全1。

CRC (polynomial code 多项式编码）：计算机网络中广泛的应用。

22. 循环冗余校验的计算。（287 页）

23. 随机接入（random access）协议：时隙 ALOHA，ALOHA，CSMA，各自的特点。（292 页）

Slotted ALOHA: when node obtains fresh frame, transmits in next slot, if no collision(碰撞): node can send new frame in next slot. if collision: node retransmits frame in each subsequent slot with prob. p(概率p) until success. 好：single active node can continuously transmit at full rate of channel, highly decentralized: only slots in nodes need to be in sync, simple. 不好：collisions, wasting slots, idle slots

At best: channel used for useful transmissions 37% of time

Pure (unslotted) ALOHA: simpler, no synchronization, transmit immediately, collision probability increases

even worse than slotted Aloha

CSMA (Carrier Sense Multiple Access): listen before transmit, If channel sensed idle: transmit entire frame, human analogy: don’t interrupt others.

CSMA/CD (Collision Detection): easy in wired LANs, difficult in wireless LANs, human analogy: the polite conversationalist.

24. ARP 的过程：广播（broadcast）发送 ARP 分组，单播（unicast）发送响应。（301 页）

A wants to send datagram to B, and B’s MAC address not in A’s ARP table, A broadcasts ARP query packet, containing B's IP address, dest MAC address = FF-FF-FF-FF-FF-FF, all machines on LAN receive ARP query, B receives ARP packet, replies to A with its (B's) MAC address, frame sent to A’s MAC address (unicast), A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out), ARP is “plug-and-play”

25. IP 地址与 MAC 地址的映射（mapping）：NAT，ARP，如何获得下一跳的地址？（228 页，300 页）

26. MAC 地址的格式，二进制到十六进制的转换。

MAC地址的长度为48位（6个字节），16进制表示，如08:00:20:0A:8C:6D(书上的表示法为08-00-20-0A-8C-6D)。其前6位08:00:20代表网络硬件制造商的编号，而后6位代表制造商所制造的某个网络产品（网卡）的系列号。

此题考的是计算，应该是二进制到十六进制的转换。

27. 特殊的 IP 地址：

全网网络地址 0.0.0.0 广播地址 255.255.255.255

本机回送（loopback）地址 127.0.0.1

组播地址 224.0.0.1

私网地址 10.0.0.0---10.255.255.255 172.16.0.0---172.31.255.255 192.168.0.0---192.168.255.255

28. IP 数据报格式，各字段的名称、作用和值。哪些字段会随着数据报的转发而改变？（216 页）

版本号 四位（ipv4） 首部长度 4位（最大值60字节）区分服务 8位 总长度16位（首部+data之和的长度）

标识 16位(计数器，产生数据报标识) 标志（最低位MF=1表明后面有分片；中位DF=0允许分片

TTL 8位（可能通过路由器数量的最大值） 上层协议 8位（数据在上层使用什么协议6=TCP;17=UDP）

协议中值为6表明数据部分要交给TCP,值为17表示数据要交给UDP。

在每台路由器上都必须重新计算检验和并存放在原处，因为TTL字段及选项字段可能会改变。

29. TCP 平均吞吐量=0.75*W/RTT。（184 页）

30. 二进制指数退避算法（binary exponential backoff algorithm）（308 页）k={0,1,…，2^m -1}m=min(n,10)等待K*512比特时间(1bit=0.1us)

此题请看书。

二、填空题（共 10 题，每题 1 分）

31. 协议的定义：protocols define format, order of massages sent and received among network entities,

and actions taken on massage transmission, receipt.定义了在2个或多个通信实体之间交换的报文格式和次序，以及在报文传输接收或其他事件方面采取的动作。

32. 流量强度（traffic intensity）= La/R R=链路带宽 L=分组大小 a=平均分组到达速率（25 页）

La/R ~ 0: average queueing delay small

La/R -> 1: delays become large

La/R > 1: more “work” arriving than can be serviced, average delay infinite

packet arriving to full queue dropped (aka lost又称为丢包)

L/R到达一个分组，则每个分组将到达一个空队列，因此不会有排队时延

33. FTP：控制连接 21 端口，数据连接 20 端口，控制信息带外（out of band）传送，保留用户状态（state）信息，每个数据连接只能传送一个文件（非持久 non-persistent 连接）。

34. POP3 的过程和工作模式：下载并删除（IMAP 下载并保留），USER PASS LIST RETR DELE QUIT。（82 页）

1. c: dele 1 C: retr 2 S: blah blah …… S: …..blah S: . C: dele 2 C: quit

2. c: retr 2 S: blah blah…… s: ……blah s: . c:quit

35. TCP 流量控制公式：LastByteRcvd – LastByteRead ≤ RcvBuffer

RcvWindow= RcvBuffer-[LastByteRcvd - LastByteRead] LastByteSent – LastByteAcked ≤ RcvWindow （167-168 页）

36. 对于 SR 协议而言，窗口长度必须小于等于序号空间大小的一半。The window size must be <= half the size of the sequence number space for SR protocols.（152 页）

37. 路由器的输入端口：数据链路处理（协议，拆封），查找、转发、排队。虽然转发表是由选路处理器计算的， 但通常一份转发表的影子拷贝会被存放在每个输入端口，而且会被更新。（210 页）

三种交换结构：Switching Via Memory， Switching Via a Bus， Switching Via An Interconnection Network

输出端口：queueing (delay) and loss due to output port buffer overflow

38. 因特网的路由方式。

RIP, OSPF, BGP

39. 链路类型。

point-to-point(ppp hdlc), broadcast (shared wire or medium) 以太网无线lan都是广播。

40. MAC 地址。

MAC (or LAN or physical or Ethernet) address：get frame from one interface to another physically-connected interface (same network)广播地址FF-FF-FF-FF-FF-FF

三、计算题（共 2 题，共 15 分）

41. 1）传输延时（transmission delay）与传播延时（propagation delay）：传输延时指分组从设备发送到链路

上所经历的时间，等于分组大小/网络带宽（L/R）。传播延时等于分组从物理链路一端发送到另一端所经历的 时间，等于链路长度/传播速度（d/s）。（23 页）

2）分组交换（packet switch）：存储转发（store and forward）是指在交换机能够开始向输出链路传输该分 组的第一个比特之前，必须接收到整个分组。（18 页）

3）时分多路复用（TDM）与频分多路复用（FDM）。（17 页）

传速=比速/时隙 大小/传速=时间

一条电路的传输速率等于一个时隙中的比特数乘以该帧的速率，例如，如果链路每秒传输8000个帧，每个帧由8个比特组成，则一条电路的传输速率是64kbps。

How long does it take to send a file of 640,000 bits from host A to host B over a circuit-switched network?

All links are 1.536 Mbps， Each link uses TDM with 24 slots/sec，500 msec to establish end-to-end circuit

Ans: 1.536mbps/24 = 64kbps, 640kb/64kbps = 10s, 10s + 0.5s = 10.5s

sending a 30-Mbit MP3 file from a source host to a destination host. A transmission rate of 10 Mbps. the propagation speed is 2*10^8 meters/sec and the distance between source and destination is 10000 km. Initially suppose there is only one link between the source and the destination. Also suppose that the entire MP3 file is sent as one packet.

The transmission delay is:
Correct: 3 seconds

the end-to-end delay (transmission delay plus propagation delay) is
Correct: 3.05 seconds

how many bits will the source have transmitted when the first bit arrives at the destination.
Correct: 500,000 bits

Now suppose there are two links between source and destination, with one router connecting the two links. Each link is 5,000 km long. Again suppose the MP3 file is sent as one packet. Suppose there is no congestion, so that the packet is transmitted onto the second link as soon as the router receives the entire packet.

The end-to-end delay is
Correct: 6.05 seconds

Now suppose that the MP3 file is broken into 3 packets, each of 10 Mbits. Ignore headers that may be added to these packets. Also ignore router processing delays. Assuming store and forward packet switching at the router,

the total delay is
Correct: 4.05 seconds

Now suppose there is only one link between source and destination, and there are 10 TDM channels in the link. The MP3 file is sent over one of the channels. The end-to-end delay is
Correct: 30.05 seconds

Now suppose there is only one link between source and destination, and there are 10 FDM channels in the link. The MP3 file is sent over one of the channels. The end-to-end delay is
Correct: 30.05 seconds

四、简答题（共 45 分）

44. 一个体系结构（one architecture）：分层体系结构

两个参考模型（two reference model）：ISO/OSI 参考模型，TCP/IP 参考模型（32 页） 三个地址（three address）：URL，IP 地址，MAC 地址

四种控制（four control）：差错控制（error control），流量控制（flow control），拥塞控制（congestion control），介质访问控制（medium access control）

45. 自治系统（AS）间的路由：外部 BGP 会话（eBGP session）和内部 BGP 会话（iBGP session）。（256 页）

46. 拥塞控制（congestion control）的有限状态自动机（FSM）。

47. When you enter an URL in your browser and press ENTER, what happens? Hints: DHCP, UDP, IP, Ethernet, DNS, ARP, routing, TCP, HTTP

摘要：本题要求描述在浏览器地址栏中输入一个 URL 并按回车后将要发生的事情。大致过程包括：

1. 发送 DHCP request 消息：封装到 UDP 数据报和 IP 数据报，源 IP 0.0.0.0，目的 IP 255.255.255.255。

2. IP 数据报封装为以太网帧，源 MAC 地址 00:16:D3:23:68:8A，目的 MAC 地址 FF:FF:FF:FF:FF:FF。

3. 交换机收到广播消息并向所有端口转发。

4. 作为 DHCP 服务器的路由器收到这一消息，解封装并交付上层。

5. 分配 IP 地址，将 IP 地址、DNS 地址和网关地址放入 DHCP ACK 消息，封装并发送。

6. 交换机经过自学习，直接发送到目的地址。

7. 客户机收到分配的 IP 地址，可以上网。

8. 请求 google 的 IP 地址，封装 DNS query 消息。

9. 想要发送 DNS query，发现不知道网关的 MAC 地址。

10. 广播发送 ARP query，根据网关的 IP 请求网关的 MAC 地址。

11. 网关发送 ARP reply，告知自己的 MAC 地址。

12. 客户机收到 ARP reply。

13. 客户机将 DNS query 发送到网关。

14. 网关根据 DNS query 报文中携带的 DNS 服务器地址转发 DNS query 报文。

15. 中间路由器的转发。

16. 本地 DNS 服务器收到 query，查询到已被缓存的 google 的 IP 地址，经查询权威 DNS 知道 IP 没有改动，发送 reply。

17. 客户机收到 DNS reply，获得了 google 的 IP 地址。

18. 客户机开启 socket，发送 TCP SYN 的握手消息以建立 TCP 连接。

19. 数据报经过复用，选路，转发，分用，到达服务器。

20. 服务器开启 socket，发送 TCP SYNACK 的握手消息以建立 TCP 连接。

21. 服务器返回消息。

22. 连接建立，发送 HTTP GET 请求消息。

23. 服务器收到请求消息，将所请求的内容放入 response 消息中返回。

24. 客户端收到响应消息，解封装后在浏览器中显示。

原文中省略了一些步骤。包括 DHCP discover 和 DHCP offer 报文，以及第三次握手的消息等等。请参见原文给出的 章节编号自行查看。

下列各图说明了前文描述的过程

本文来源：https://www.2haoxitong.net/k/doc/453f9a76852458fb760b5626.html