Datalink

Link layer: introduction

nodes：hosts and routers
links： communication channels that connect adjacent（相邻） nodes along the communication path
layer-2 packet: frame, encapsulates datagram

功能： data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link

datagram transferred by different link protocols over different links:

在不同链路上传输的数据报的链路层协议是不同的

each link protocol provides different services

may or may not provide rdt over link

链路层服务

framing：encapsulate datagram into frame, adding header, trailer
link access:“MAC” addresses used in frame headers to identify source, destination
reliable delivery between adjacent nodes: seldom used on low bit-error link (fiber, some twisted pair) 通常用于wireless links: high error rates
flow control: pacing between adjacent sending and receiving nodes
error detection: errors caused by signal attenuation, noise.

receiver detects presence of errors
error correction: 不仅可以检测错误，还可以检测错误出现的位置

receiver identifies and corrects bit error(s) without retransmission
half-duplex and full-duplex：with half duplex, nodes at both ends of link can transmit, but not at same time

链路层在何处实现

in each and every host, combination of hardware, software, firmware

link layer implemented in “adaptor”网络适配器 (aka network interface card NIC 网络接口卡) or on a chip芯片

attaches into host’s system buses

控制器接收frame并抽取出网络层数据报

Error detection

EDC= Error Detection and Correction bits

D = Data protected by error checking, may include header fields

通常D中不只包含数据报，同时包含链路层frame首部

Error detection not 100% reliable!

选择合适的差错检测方案使得遗漏错误概率很小miss some errors, but rarely

larger EDC field yields better detection and correction

EDC的比特越多，检测和纠错效率越好

Parity checking

single bit parity:

奇偶校验：发送方只需要包含一个附加的比特，选择它的值，使得ｄ＋１位中的１的总数总是偶数，如果总数为计数就说明至少有一个比特的错误

two-dimensional bit parity: detect and correct single bit errors

二维奇偶校验可以检测出错误，并通过行和列的索引纠正它

Internet checksum

校验和方法

detect “errors” in transmitted packet

full packet checksum guaranteed UDP/TCP only（对首部和数据字段都计算checksum）

具体方法：

treat segment contents as sequence of 16-bit integers

checksum: addition (1’s complement sum) of segment contents 求和之后的补码

sender puts checksum value into UDP checksum field

check if computed checksum equals checksum field value:

• NO - error detected

• YES - no error detected.

Cyclic Redundancy Check (CRC)

algorithm has good protection against bursts of errors.

Multiple access protocols

两种类型链路：

point-to-point (connect two computers only)

broadcast (shared wire or medium)

链路层中一个很重要的问题就是：如何协调多个发送和接收节点对一条单一共享广播信道的访问，这就是多路访问问题。为了避免冲突（collision，如果有多个节点同时传输数据帧而不受任何控制，传输的帧可能在接收方处碰撞，碰撞帧的信号纠缠在一起

“collision” – 2 or more transmissions at once

采用多路访问协议（multiple access protocol）来规范它们在共享的广播信道（“share” medium）上的传输行为

理想的多路访问协议：

给定：Rbps的广播信道

当一个节点要发送时，可以R速率发送
当M个节点要发送，每个可以以R/M的平均速率发送
fully decentralized:
Simple

三种多路访问协议类型

Partition channel 信道划分协议, random access 随机接入协议, “take turns”轮流协议

Channel partitioning MAC protocols

TDMA

time division multiple access 时分多址

时间域被分成周期循环的等长的时分复用帧（TDM帧），并进一步划分每个时间帧为 N 个时隙（slot）

access to channel in “rounds”

each station gets fixed length slot (length = packet transmission time) in each round

如果站点无帧传输，时隙空闲->浪费

6站LAN，1、3、4有数据报，时隙2、5、6空闲

大家占用相同的spectrum，但是按使用不同的时间段。比如把1秒钟（或更小的一个时间单位）分成六个相等的小时间单位，时间单位1给channel1用，时间单位2给channel 2用…以此类推。

FDMA

frequency division multiple access 频分复用

channel spectrum divided into frequency bands

each station assigned fixed frequency band

分配给站点的频段如果没有被使用，则空闲

6站LAN，1、3、4有数据报，频段2、5、 6空闲

Random access protocols

when node has packet to send transmit at full channel data rate R.

two or more transmitting nodes ➜ “collision”

在随机访问协议中，一个传输节点总是以信道的全部速率（即 R bps）进行发送。由于信道不划分，所以可能出现而且允许冲突，而冲突意味着数据传输失败，因此随机访问协议需要定义：

1）如何检测冲突；

2）如何从冲突中恢复

examples of random access MAC protocols:

• slotted ALOHA (不是首字母缩写，你好)

• ALOHA

• CSMA, CSMA/CD, CSMA/CA

但是当一个节点检测到碰撞时，不会立即重发，而是会等待一个随机的时延，碰撞的每个节点随机选择时延的过程是独立的，所以有可能重发时可以避免碰撞

Slotted ALOHA

在对时隙 ALOHA 的描述中，我们做下列假设：

① 所有数据帧大小相同，假定所有帧由 L 比特组成；

② 时间被划分成等长的时隙，每个时隙长度为 L / R 秒；

③节点只能在时隙开始时刻发送数据帧（实际上是节点上的网络适配器，或称为网卡，来发送数据帧）。nodes start to transmit only slot beginning

④ 节点间时钟同步步，每个节点都知道时隙何时开始。nodes are synchronized

⑤ 如果在一个时隙中有多个节点发送数据帧，则节点在该时隙结束之前检测到该冲突事件。

if 2 or more nodes transmit in slot, all nodes detect collision

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 until success

如果有冲突，该节点在时隙结束之前检测到这次冲突，并在下一个时隙以随机概率 p 重传该帧，直至成功。

node 1,2,3在slot1 collision,然后2在slot4发送成功，1在slot8 发送成功，3在slot10成功

优点

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 总会产生空时隙

nodes may be able to detect collision in less than time to transmit packet

节点检测冲突的时间<帧传输的时间，必须等时钟到来才能重传

clock synchronization

Pure (unslotted) ALOHA

第一个 ALOHA 协议实际上是一个非时隙、完全分散的协议，也称为纯ALOHA 协议

unslotted Aloha: simpler, no synchronization

• transmit immediately 不必等时钟，立刻重传

当有新的数据帧生成时，节点立刻将该帧完整地传输进广播信道，因此冲突的可能性增大。如果一个传输的帧与其他传输发生冲突，这个节点立即以概率 p重传该帧；否则，该节点等待一个帧传输时间后，再以概率 p重传该帧，重复以上过程直至成功

collision probability increases:

• frame sent at t0 collides with other frames sent in [$t_0$-1,$t_0$+1]：在[$t_0$-1,$t_0$]中发出的帧后半部分一定会与i 帧冲突，而i帧后半部分又会与[$t_0$,$t_0$+1]发出的帧冲突

half as efficient as slotted: 效率是slotted ALOHA的一半

CSMA (carrier sense multiple access)

ALOHA中节点在开始传输前，并不关心是否会发生冲突（不关心现在channel中是否有帧）

载波侦听多路访问采用碰撞检测：如果和另一个帧同时发出，则停止发送，作废

CSMA: listen before transmit 载波侦听

if channel sensed idle: transmit entire frame

if channel sensed busy, defer transmission

在发送数据帧之前，先监听信道，如果信道空闲，则发送完整帧；如果信道忙，则推迟发送：节点则等待直到监听到一小段时间空闲，然后开始传输。

发生collision的情况：

因为有propagation delay 所以 two nodes may not hear each other’ s transmission

只要发生collision，整个packet的transmission time wasted

传播时延越大载波节点不能侦听到另一节点开始传播的可能就越大

下图显示了连接到一个线状广播总线的 4 个节点 (A,B,C,D) 的时空图，横轴表示

每个节点在空间中的位置，纵轴表示时间。在时刻$t_0$，节点 B 监听到信道是空闲的，

因此节点 B 开始传输，沿着广播链路在两个方向上传播它的比特，B 的比特沿着广

播链路传播延迟不是零（虽然以接近光速传播）。尽管节点 B 在$t_1$时刻正在传输，但 B 传输的比特信号还没有到达节点 D，因此 D 在$t_1 $监听到信道空闲根据CSMA 协议，D 也开始传输它的数据帧。一个短暂的时间后，B 的传输开始在 D 干扰 D 的传输，也就是发生了冲突。

CSMA/CD (collision detection)

前面的CSMA没有加入碰撞检测机制：一旦检测到碰撞，B和D都立刻停止传输（上图还在继续传输）

具有collision的CSMD

• collisions detected within short time

• colliding transmissions aborted, reducing channel wastage

一但检测到collision，立刻结束传输

B 和 D 节点在发送数据的同时能检测冲突，一旦检测到冲突将立即停止传输，这样就能够减少信道资源的浪费

Ethernet CSMA/CD algorithm

Network Interface Card (NIC)从网络层收到 datagram, creates frame
If NIC senses channel idle, 开始传输帧. If NIC senses channel busy, 等待直到信道idle, then transmits.
If NIC 传输 entire 帧的过程中没有检测到其他帧在传输, NIC is done with frame
If NIC detects another transmission while transmitting, aborts and sends jam signal传输中止
After aborting, NIC enters 2进制指数后退算法 binary (exponential) backoff: after m th collision, NIC chooses K at random from${0,1,2, … , 2^m-1}$ NIC waits K·512 bit times, returns to Step 2

在该帧经历了一连串的 m 次 (m < 10) 碰撞后，节点随机地从${0,1,2, … , 2^m-1}$中选择一个 K 值，等待的时间量为 K ⋅ 512 比特的传输延迟（发送512比特时间的k倍）；在 10 次或更多次碰撞之后，从 {0,1,2,3,…,1023}中随机选择 K

CSMA/CD: Frame size

▪ Collision Window 碰撞窗口

Related to end-to-end propagation delay 以太网端到端的往返时延只有经过碰撞窗口这段时间还没检测到冲突，发送方才能肯定这次发送不会发生冲突。

Minimum packet size must be greater than collision window

RTT = 2x5000m/2x10^8 m/s = 0.00005s

min frame size = 0.00005s x 10,000,000 bits/sec = (500 bits) ~64B(最小帧是RTT时间里发送的帧的长度)

可以想象发送方发送一个持续时间小于RTT的帧，过了T（RTT一半）时间后在接收方发生碰撞，然而该碰撞有需要T时间传回来，此时该帧早已发完，不知道产生了碰撞。

two frames are transmitted within certain time, collisions will occur. Both senders need to detect collision. The senders only detect collision during transmission. If transmission is too short, the senders cannot detect collision. If the transmission is long enough, the senders can detect collision.

如果某主机发送一个帧的64字节仍无冲突，以后就不会再发生冲突了，称此主机捕获了信道。

所以最小帧为64B，如果小于这个数，可能无法检测到冲突

The transmitting station is still transmitting long enough for a corrupted signal to be detected

CSMA/CA（collision avoid）

无线局域网中传输

802.11: 没有冲突检测

一旦发出就一定发完整个帧

由于自身信号强度远远大于其他信号：其他信号衰减weak received signals (fading)

目标: avoid collisions: CSMA/C(ollision)A(voidance)

• 为了避免无CD带来的信道利用率低的问题，事前进行冲突避免

无法感受到所有的冲突：存在隐藏站点问题

Hidden and Exposed Station

圈代表信号覆盖范围：有可能发生冲突的区域

(a) The hidden station problem. A and C are hidden from each other

隐藏终端问题可以简单定义为：节点之间（A与C）无法互相监听对方。但当其不可以同时传输时（如果A向B发送会进入C的范围造成冲突），其同时传输，从而导致冲突发生。隐藏终端在单个AP（或者单个Receiver）时就有可能发生。

(b) The exposed station problem. B is exposed to transmission from A

暴露终端问题可以简单定义为：节点之间能够互相监听对方。但其可以同时传输时，其不传输（A在向范围内的节点传输，此时B明明可以向不在A范围内的传输，但是由于侦听到了A的信号，放弃了对C的传播），从而造成浪费。

所以802.11中不冲突检测，检测了也没用

如何解决：事前侦听

1 如果感受到channel idle for DIFS（ Short InterFrame Space） then transmit entire frame (no CD)

2 if 感受channel很忙，然后设置一个随机的backoff计时器，在信道空缺时候倒计时。当计数值减为 0，该站点发送整个数据帧并等待确认

3.如果收到确认，发送站点知道它的帧已被目的站正确接收了，如果未收到确认，发送站点将重新进入回退阶段，并从一个更大的范围内选取随机值

DCF = Distributed Coordination Function 分布式协调功能

DIFS = DCF InterFrame Space分布式帧间间隔

SIFS = Short InterFrame Space 短帧间间隔

此外还可以进行预约信道：allow sender to “reserve” channel rather than random

access of data frames: avoid collisions of long data frames为了避免长帧的冲突

使用CSMA向BS（base station）发送一个小的RTS（request-to-send） packets

如果发送碰撞，就backoff重发

预约成功后，BS broadcasts clear-to-send CTS in response to RTS

目的是告诉发送方可以开始发了，告诉其他节点停止发送

avoid data frame collisions completely using small reservation packets!

LANs

MAC（LAN or Physical or Ethernat）地址是48 bit MAC address (for most LANs) burned in NIC ROM只有NIC有关, also sometimes software settable

e.g.: 1A-2F-BB-76-09-AD 十六进制表示每个小隔断里有８比特（48ｂｉｔ）

function: used “locally” to get frame from one interface to another physically-connected interface (same network, in IP addressing sense)

each adapter on LAN has unique LAN address每个适配器具有一个MAC address

IP地址是分层的，MAC地址平面化的

FF-FF-FF-FF-FF-FF MAC广播地址

对于某些具有多个网卡的端设备，具有多个LAN地址

世界上的每一个网卡MAC地址都不同：MAC address allocation administered by IEEE

网卡制造商需要购买MAC address space

MAC flat address ➜ portability mac address具有扁平结果，这决定了其网卡可以在不同设备中移植，而地址不会变

• can move LAN card from one LAN to another

值得注意的是，交换机没有MAC地址！

ARP: address resolution protocol

地址解析协议：Address Resolution Protocol, ARP is used to find the destination MAC address when only the destination IP address is known（已知IP地址查找MAC地址）

each IP node (host, router) on LAN has ARP table

< IP address; MAC address; TTL>格式

TTL (Time To Live)：time after which address mapping will be forgotten

存储MAC－IP pair直到 information that times out

从表中删除每个映射的时间

子网中寻址

具体流程：

A wants to send datagram to B：B’s MAC address not in A’ s ARP table.（先查表，如果表里有对应IP的MAC直接用，如果没有开始广播）
A broadcasts ARP query packet, containing B’s IP address （destination MAC address = FF-FF-FF-FF-FF-FF）此时所有节点都收到了这个查询
B receives ARP packet, replies to A with its (B’s) MAC address

把自己的MAC发送给A的MAC地址，而不是广播

routing to another LAN

send datagram from A to B via R

A creates link-layer frame with R’s MAC address as destination address, frame contains A-to-B IP datagram 以R的MAC地址作为目的地，并把A到B的数据报封装进去

frame received at R, datagram removed, passed up to IP

R creates link-layer frame with B’s MAC address as destination address, frame contains A-to-B IP datagram

传到R后将IP数据报提取出来然后封装成以B MAC地址为目的地的帧继续发（如果不知道地址，ARP查询）

全程源IP目标IP不变，但是源MAC和目标MAC始终在变

Ethernet

有线网络中最常使用的LAN技术（与802.3几乎一致），无线网络中最常用802.11

physical topology

bus: all nodes in same collision domain（都在一个碰撞域中）同一个碰撞域中使用CSMA/CD同一时间只有一个在传

两个端口同时发出一个帧在总线中，就会发生碰撞

star:

• active switch in center

• each line runs a (separate) Ethernet protocol (nodes do not collide with each other)交换机内分端口发送不会产生碰撞（Ａ－＞Ｂ不影响Ｃ－＞Ｄ）

Ethernet frame structure

sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame

preamble（前同步码）:

7 bytes with pattern 10101010 followed by one byte with pattern 10101011前7比特都是10101010，最后一个是10101011

used to synchronize receiver, sender clock rates

addresses: 6 byte source, destination MAC addresses

if adapter receives frame with matching destination address, or with broadcast address (e.g. ARP packet), it passes data in frame to network layer protocol

type: indicates higher layer protocol (mostly IP but others possible）高层协议

CRC: cyclic redundancy check at receiver

发现错误就丢弃该frame

connectionless: no handshaking between sending and receiving NICs

不握手，直接发

unreliable: receiving NIC doesn’t send ACK or NACK to sending NIC

和UDP、IP一样，出错不归链路层管，从TCP再次生成分组重新封装成帧重发（或者应用层重发）

只有使用上层的TCP，丢弃的帧才会重传

使用的MAC协议是unslotted CSMA/CD with binary backoff

Ethernet switch

store, forward Ethernet frames

examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment

transparent：交换机对于子网中所有主机和路由器都是透明的

主机并不知道有交换机存在（网络层面认为子网内一跳可达，链路层可能经过很多交换机）

plug-and-play, self-learning：不要configured，自学习得到交换表

multiple simultaneous transmissions：多重同步传输，同时有很多节点并发的发送，每个主机有dedicate，direct connection to switch，switch可以buffer frame，并且no collision （each link is its own collision domain）

A-to-A’ and B-to-B’ can transmit simultaneously （MAC协议在其中弱化了，因为几乎不存在碰撞）

如何获取具有MAC－IP pair 的switch table? switch具有self-learning

Switch: self-learning

switch learns which hosts can be reached through which interfaces

when frame received, switch “learns” location of sender: incoming LAN segment

初始时，switch table为空，当有主机经过交换机发送时，记录其端口以及MAC地址，并设置一个TTL（Time to Live），超过这个时间自动删除。

帧发送到交换机，把A地址和1 接口存入交换表

frame filtering/forwarding过滤转发

过滤 (filtering) 是决定某个帧应该转发到某个接口还是应当将其丢弃的交换机功能

转发 (forwarding）是决定某个帧应该被导向哪个接口，并把该帧移动到那些接口

如果没有匹配的表项，直接广播，有匹配的但是和发送时使用的端口一样，无需再发回去，直接丢弃（过滤）

在上个例子基础上，A的帧到达switch后A’的location unknown: flood

然后A’向A发送frame时，A已经在表中，所以可以直接从１输出

去的时候flood，回来时候走一条确定的路线

Switches vs. routers

both are store-and-forward:

routers: network-layer devices (examine network—layer headers)

switches: link-layer devices (examine link-layer headers)both have forwarding tables:

routers: compute tables using routing algorithms, IP addresses，需要配置不是即插即用

switches: learn forwarding table using flooding, learning, MAC addresses，可以即插即用

WLANS

wireless local area network

wireless host：may be stationary (non-mobile) or mobile

base station（AP） : connected to wired network

sending packets between wired network and wireless host(s)

wireless link: connect

mobile(s) to base station

ad hoc mode:自组织网络（不需要接入点(Access Point)） no base stations，route among themselves

在Ad hoc网络中，结点具有转发能力，结点间的通信可能要经过多个中间结点的转发（多跳），这是Ad hoc网络与其他移动网络的最根本区别。

nodes can only transmit to other nodes within link coverage

不需要AP

802.11 WLAN

无线主机与基站通信base station = access point (AP)

Basic Service Set 基本服务集 (BSS) contains:

• wireless hosts

• access point (AP): base station（家用路由器）是链路层设备

• ad hoc mode: hosts only 如果是自组织网络只有主机

802.11 frame

Address1：要接收该帧的AP或主机的ＭＡＣ

Address2: 发送该帧的站点的MAC地址

Address３：与AP直接相连的路由器的MAC地址

Address4：如果不用：00-00-00-00-00-00

addressing

AP是链路层设备，它与IP地址无关，所以从路由器角度来看，它认为它与子网中一台主机H1直接相连：

H1生成一个802.11帧用AP的MAC地址和H1的MAC地址作为地址1和地址2，R1的MAC作为地址3，当AP接收到该帧，将其转换为以太网帧：源地址为H1 MAC目标地址为R1的MAC地址发往路由器（看起来好像是低一层的packet在这里deliver）

802.11帧：

上面是以byte为单位，下面是bit

VLAN

虚拟局域网：

带有VLAN功能的交换机（们）可以被配置成：一个物理LAN基础设施，虚拟成多个虚拟的LANs

在一个VLAN内主机可以彼此通信，仿佛与交换机直接相连。

流量隔离: 从/到1-8端口的流量只会涉及到1-8

动态成员: 成员可以在VLANs之间动态分配

在VLANs间转发:通过路由器进行转发 (就像他们通过各自的交换机相联一样)

Multiprotocol label switching (MPLS)

纯IP网络是按照IP地址对分组进行转发的

前缀匹配，转发的方法固定

无法控制IP分组的路径，无法支持流连工程

也无法对一个IP分组流进行资源分配，性能无法保证

MPLS网络按照标签label进行分组的转发

有基于标签的转发表

▪ initial goal: high-speed IP forwarding using fixed length label (instead of IP address)

•使用固定长度标识符(而不是最长前缀匹配)快速查找

•借鉴虚拟电路(VC)方法但IP数据报仍然保留IP地址!

MPLS capable routers

标签交换路由器

只根据标签值将报文转发到出接口(不检查IP地址)

MPLS forwarding table distinct from IP forwarding tables

flexibility: MPLS forwarding decisions can differ from those of IP

采用源地址和目标地址来路由到达同一个目标的流，不同路径（支持流量工程）

如果链路失效，能够快速重新路由: 预先计算好的备份链路 (对于VoIP有效)

▪ IP routing: path to destination determined by destination address alone

▪ MPLS routing: path to destination can be based on source and destination address

R4到A有两种路径

A day in the life

我们假定 Bob启动他的便携机，然后将其用一根以太网电缆连接到学校的以太网交换

机，交换机又与学校的路由器相连，如图6-32所示。学校的这台路由器与一个ISP连接，

本例中 ISP为comcast. net。在本例中，comcast.net 为学校提供了DNS 服务;所以，DNS

服务器驻留在 Comcast 网络中而不是学校网络中。我们将假设 DHCP服务器运行在路由器

中，就像常见情况那样。当 Bob 首先将其便携机与网络连接时，没有IP 地址他就不能做任何事情（例如下载一个Web 网页）。所以，Bob 的便携机所采取的一个网络相关的动作是运行 DHCP 协议，以从本地 DHCP服务器获得一个IP 地址以及其他信息。

1）Bob便携机上的操作系统生成一个DHCP请求报文（4.3.3节），并将这个报文放入具有目的端口67（DHCP服务器）和源端口68（DHCP客户）的UDP报文段（3.3节）链路层和局域网 327该UDP报文段则被放置在一个具有广播 IP目的地址（255.255.255.255）和源 IP地址0.0.0.0的IP数据报中（4.3.1节），因为 Bob的便携机还没有一个IP地址。

2）包含 DHCP请求报文的IP数据报则被放置在以太网帧中。该以太网帧具有目的 MAC地址 FF∶FF∶FF∶FF∶FF∶FF，使该帧将广播到与交换机连接的所有设备（如果顺利的话也包括 DHCP 服务器）;该帧的源 MAC 地址是 Bob便携机的 MAC 地址00:16: D3:23:68:8A。

3）包含 DHCP请求的广播以太网帧是第一个由 Bob便携机发送到以太网交换机的帧。该交换机在所有的出端口广播入帧，包括连接到路由器的端口。

4）路由器在它的具有 MAC地址 00∶22∶6B∶45∶IF的接口接收到该广播以太网帧。该帧中包含 DHCP请求，并且从该以太网帧中抽取出 IP数据报。该数据报的广播IP 目的地址指示了这个IP 数据报应当由在该节点的高层协议处理，因此该数据报的载荷（一个UDP报文段）被分解（3.2节）向上到达 UDP，DHCP请求报文从此 UDP报文段中抽取出来。此时 DHCP服务器有了DHCP请求报文。

5）我们假设运行在路由器中的 DHCP服务器能够以CIDR（4.3.3节）块68.85.2.0/24分配IP地址。所以本例中，在学校内使用的所有IP 地址都在 Comcast 的地址块中。我们假设 DHCP服务器分配地址 68.85.2.101 给 Bob 的便携机。DHCP服务器生成包含这个IP地址以及 DNS 服务器的 IP 地址（68.87.71.226）、默认网关路由器的 IP 地址（68.85.2.1）和子网块（68.85.2.0/24）（（等价为”网络掩码”）的一个DHCP ACK报文。该DHCP报文被放入一个UDP报文段中，UDP报文段被放入一个IP数据报中，IP 数据报再被放入一个以太网帧中。这个以太网帧的源 MAC地址是路由器连到归属网络时接口的 MAC地址（00∶22∶6B∶45∶1F∶1B）、目的 MAC地址是 Bob便携机的 MAC地址（00∶16∶ D3∶23∶68∶8A）。

6）包含 DHCP ACK 的以太网帧由路由器发送给交换机。因为交换机是自学习的，并且先前从 Bob便携机收到（包含 DHCP请求的）以太网帧，所以该交换机知道寻址到00∶16∶D3∶23∶68∶8A的帧仅从通向 Bob便携机的输出端口转发。

7）Bob便携机接收到包含 DHCP ACK 的以太网帧，从该以太网帧中抽取IP 数据报，从IP数据报中抽取 UDP报文段，从 UDP报文段抽取 DHCP ACK报文。Bob 的 DHCP客户则记录下它的IP 地址和它的 DNS 服务器的 IP地址。它还在其IP转发表中安装默认网关的地址。Bob便携机将向该默认网关发送目的地址为其子网68.85.2.0/24 以外的所有数据报。此时，Bob 便携机已经初始化好它的网络组件、并准备开始处理 Web 网页获取。（注意到在第 4 章给出的四个步骤中仅有最后两个 DHCP步骤是实际必要的。）

当Bob 将 www.google.com 的 URL 键入其Web浏览器时，他开启了一长串事件，这将导致谷歌主页最终显示在其Web 浏览器上。Bob的 Web浏览器通过生成一个TCP套接字开始了该过程，套接字用于向www.google.com发送HTTP请求。为了生成该套接字，Bob 便携机将需要知道 www.google.com 的IP地址。我们在2.4节中学过，使用 DNS协议提供这种名字到 IP地址的转换服务。

8）Bob便携机上的操作系统因此生成一个 DNS查询报文（2.4.3节），将字符串www.google.com放入DNS报文的问题段中。该DNS报文则放置在一个具有53号（DNS 服务器）目的端口的 UDP报文段中。该UDP报文段则被放入具有IP目的地址68.87.71.226和源IP 地址 68.85.2.101的IP数据报中。

9）Bob便携机则将包含 DNS请求报文的数据报放入一个以太网帧中。该帧将发送（在链路层寻址）到 Bob学校网络中的网关路由器。然而、即使 Bob 便携机经过上述第5步中的 DHCP ACK报文知道了学校网关路由器的IP 地址（68.85.2.1），但仍不知道该网关路由器的 MAC地址。为了获得该网关路由器的 MAC 地址，Bob 便携机将需要使用 ARP协议（6.4.1节）。

10）Bob便携机生成一个具有目的IP地址68.85.2.1（默认网关）的ARP查询报文，将该ARP报文放置在一个具有广播目的地址（FF∶FF∶FF∶FF∶FF∶FF）的以太网帧中，并向交换机发送该以太网帧，交换机将该帧交付给所有连接的设备，包括网关路由器。

11）网关路由器在通往学校网络的接口上接收到包含该 ARP查询报文的帧，发现在ARP报文中目标IP地址68.85.2.1匹配其接口的IP地址。网关路由器因此准备一个 ARP回答，指示它的 MAC地址00∶22∶∶6B∶45∶1F∶1B对应IP地址 68.85.2.1。它将ARP回答放在一个以太网帧中，其目的地址为00∶ 16∶D3∶23∶68∶8A（Bob 便携机），并向交换机发送该帧，再由交换机将帧交付给 Bob便携机。

12）Bob便携机接收包含 ARP回答报文的帧，并从 ARP回答报文中抽取网关路由器的 MAC地址（00∶22∶6B∶45∶1F∶1B）。

13）Bob便携机现在（最终!）能够使包含 DNS查询的以太网帧寻址到网关路由器的MAC地址。注意到在该帧中的IP数据报具有IP 目的地址 68.87.71.226（DNS服务器），而该帧具有目的地址00∶22∶6B∶45∶1F∶1B（网关路由器）。Bob 便携机向交换机发送该帧，交换机将该帧交付给网关路由器。

14）网关路由器接收该帧并抽取包含 DNS 查询的IP数据报。路由器查找该数据报的目的地址（68.87.71.226），并根据其转发表决定该数据报应当发送到图6-32的 Comcast网络中最左边的路由器。IP数据报放置在链路层帧中，该链路适合将学校路由器连接到最左边 Comcast 路由器，并且该帧经这条链路发送。

15）在 Comcast 网络中最左边的路由器接收到该帧，抽取IP数据报，检查该数据报的目的地址（68.87.71.226），并根据其转发表确定出接口，经过该接口朝着 DNS服务器转发数据报，而转发表已根据Comcast 的域内协议（如 RIP、OSPF 或IS-IS，5.3节）以及因特网的域间协议 BGP（5.4 节）所填写。

16）最终包含 DNS查询的 IP 数据报到达了 DNS服务器。DNS服务器抽取出 DNS查询报文，在它的 DNS数据库中查找名字 www.google.com（2.4 节），找到包含对应www.google. com 的IP地址（64.233.169.105）的 DNS源记录。（假设它当前缓存在 DNS服务器中。）前面讲过这种缓存数据源于 google.com的权威 DNS 服务器（2.4.2节）。该DNS服务器形成了一个包含这种主机名到IP地址映射的 DNS 回答报文，将该DNS回答报文放入 UDP报文段中，该报文段放入寻址到 Bob便携机（68.85.2.101）的IP数据报中。该数据报将通过Comcast 网络反向转发到学校的路由器，并从这里经过以太网交换机到Bob 便携机。

17）Bob便携机从 DNS报文抽取出服务器 www.google.com 的IP地址。最终，在大量工作后，Bob 便携机此时准备接触 www.google.com 服务器!链路层和局城网 329

18）既然 Bob便携机有了 www.google.com 的IP地址，它能够生成 TCP套接字，该套接字将用于向 www.google.com 发送HTTP GET报文。当 Bob生成TCP套接字时，在 Bob便携机中的TCP 必须首先与www.google.com 中的 TCP 执行三次握手（3.5.6节）。Bob便携机因此首先生成一个具有目的端口 80（针对 HTTP的）的 TCP SYN报文段，将该TCP报文段放置在具有目的IP地址64.233.169.105（www.google.com）的IP数据报中，将该数据报放置在 MAC 地址为00∶22∶6B∶45∶1F∶1B（网关路由器）的帧中，并向交换机发送该帧。

19）在学校网络、Comcast 网络和谷歌网络中的路由器朝着 www.google. com转发包含TCP SYN的数据报，使用每台路由器中的转发表，如前面步骤 14~16那样。前面讲过支配分组经 Comcast 和谷歌网络之间域间链路转发的路由器转发表项，是由 BGP 协议决定的（第5章）。

20）最终，包含TCP SYN的数据报到达 www.googole. com。从数据报抽取出 TCP SYN报文并分解到与端口 80相联系的欢迎套接字。对于谷歌 HTTP 服务器和 Bob便携机之间的TCP连接生成一个连接套接字（2.7节）。产生一个TCP SYNACK（3.5.6节）报文段，将其放入向 Bob 便携机寻址的一个数据报中，最后放入链路层帧中，该链路适合将www. google. com 连接到其第一跳路由器。

21）包含TCP SYNACK 报文段的数据报通过谷歌、Comcast 和学校网络，最终到达Bob便携机的以太网卡。数据报在操作系统中分解到步骤18生成的TCP 套接字，从而进入连接状态。

22）借助于Bob便携机上的套接字，现在（终于!）准备向 www.google.com发送字节了，Bob的浏览器生成包含要获取的URL的 HTTP GET报文（2.2.3节）。HTTPGET报文则写入套接字，其中GET报文成为一个TCP报文段的载荷。该TCP报文段放置进一个数据报中，并交付到 www. google.com，如前面步骤18~20所述。

23）在 www.google.com的 HTTP服务器从 TCP套接字读取 HTTP GET报文，生成一个HTTP响应报文（2.2节），将请求的Web 页内容放入 HTTP响应体中，并将报文发送进TCP套接字中。

24）包含 HTTP回答报文的数据报通过谷歌、Comcast 和学校网络转发，到达 Bob便携机。Bob 的 Web 浏览器程序从套接字读取 HTTP响应，从 HTTP响应体中抽取Web 网页的html，并最终（终于!）显示了Web网页。