摘 要：本文简要分析了两种链路层重传机制——PCI-E的ACK/NAK重传协议与HIPPI协议的工作原理，并通过对同一种错误的不同响应来分析两者的异同，最后，通过计算，对包级重传以及微包级重传进行了比较，分析了两者的优缺点。
关键词：PCI-E HIPPI 链路层 重传 包级 微包级
1．引 言
差错控制是数据链路层的重要作用之一。发送方将数据包发送往接收方，接收方收到数据包后，通过错误检测机制检测是否有错，若有错，则通知接收方进行重传，直到数据包能够被正确接收。在这个过程中，采用不同的重传机制，有可能对数据的传输效率、链路的利用率等造成很大的影响。本文通过比较PCI-E的ACK/NAK链路传输协议、HIPPI协议的异同，找出影响重传性能的因素，以便今后更好地设计链路层重传协议。
2．ACK/NAK链路传输协议
2.1概述
PCI-E中，链路层的包有两种类型：链路层事务包（Link Layer TLP(Transaction Layer Packet)，LLTP，以下简称TLP）和数据链路层包（Data Link Layer Packet，DLLP）。LLTP即为上层的TLP通过添加序列号，CRC等位而生成。DLLP则是用来进行链路层管理，以及对TLP的应答等。TLP包的最大长度为4096+28=4124B，DLLP长度为8B。
概括地说，数据链路层的发送一边主要负责通过物理层向链路上发送TLP，接收一边主要负责通过物理层从链路上接收TLP。实际上，对于发送TLP的设备来说，其链路层的接收一边还负责接收从链路对边的TLP接收设备发送回来的对TLP的应答DLLP；相应地，对于接收TLP的设备来说，它的数据链路层的发送一边还负责向链路对边的TLP发送设备发送对TLP的应答DLLP。
2.2 发送方ACK/NAK协议
1、 发送方对Ack DLLP的响应
发送方收到一个Ack DLLP，则表示它之前发送的TLP已经成功到达接收方。为减少传送Ack DLLP所占用的链路带宽，不必对每一个发送的TLP，都生成一个Ack DLLP，接收方可以在连续收到多个好的TLP之后，发送最后一个TLP的Ack DLLP来对前面发送的所有TLP进行应答，这称为Ack合并。
图1 发送方ACK/NAK协议相关
如图1所示，当发送方接收到一个Ack DLLP时，有如下响应。
1) 将该Ack DLLP中所含有的应答序列号值加载到ACK_SEQ（AS）寄存器。
2) 将重传缓冲器中所有的、序列号等于或早于该Ack DLLP所含序列号的TLP清除掉。
3) 复位重传计数器REPLAY_TIME和REPLAY_NUM。
2、 发送方对Nak DLLP的响应
ACK/NAK协议约定，如果发送方收到一个Nak DLLP，则表示它以前发送的一个TLP已被接收方收到，但有错误。该Nak DLLP所含应答序列号比NEXT_RCV_SEQ少1，也就是最后一个好TLP的序列号。
当接收到一个Nak DLLP时，有如下响应。
1) 发送方清除重传缓冲器中序列号等于或早于该Nak DLLP所含序列号的TLP。
2) 然后从这个“坏”TLP开始，重传缓冲器中剩余TLP，直到最新的TLP。
3) 将该DLLP中的应答序列号加载到ACK_SEQ寄存器。
2.3 接收方ACK/NAK协议
1、 对接收TLP进行LCRC检查
接收方从链路接收TLP，然后对TLP进行LCRC检查。如果有错，则安排一个Nak DLLP返回给发送方。
图2 接收方ACK/NAK协议相关
2、 下一接收TLP的序列号
接收方设有一个12位的NEXT_RCV_SEQ（NRS）计数器，用于指示下一个需要接收TLP的序列号。如图2。
每当接收到一个好的TLP（无CRC错）时，将其序列号与NRS进行对比，若相等，则将之前推至事务层，计数器加1，并安排一个Ack DLLP返回发送方，其应答序列号为刚刚接收到的TLP的序列号。否则，若NRS较大，则说明发生了重传，接收方废弃此TLP,计数器值不变，并安排一个应答序列号等于NEXT_RCV_SEQ-1的Ack DLLP返回发送方；若NRS较小，则说明有TLP丢失了。
3、 接收方安排一个Ack DLLP
每当接收方接收到一个有效的TLP，就将NRS值加1，将TLP前推至事务层，并安排一个Ack DLLP，或者是ACK合并。
4、 接收方安排一个Nak DLLP
当接收方检测到TLP LCRC错或者其他错时，需要安排一个Nak DLLP返回发送方。当接收方已安排了Nak DLLP时，接收方仍在接收TLP，在重传TLP到达接收方之前，会收到一些TLP的序列号值大于NEXT_RCV_SEQ，从道理上讲，已经安排了Nak DLLP，就不用再为这些TLP再次安排Nak DLLP。所以，接收方设置了NAK_SCHEDULED标志，当安排了Nak DLLP时，此位置位，此后就不再安排Nak DLLP，当接收方接收到重传的、有效的TLP时，清除该标志。
3.HIPPI协议
3.1 概述
BLUEGENE/L采用了HIPPI协议的重传机制。与ACK/NAK协议不同的是，HIPPI协议的应答采用了携带的机制，由反向链路上的微包将应答序列号携带回去，这就可以达到节省链路带宽的目的。HIPPI协议省去了NAK，而采用两次肯定的应答来表示否定的应答。另外，HIPPI协议采用了微包级重传，而ACK/NAK协议采用的是包级重传。
3.2 发送方协议
1、 发送方序列号
8位序列号取值可以从0~255，进重传缓冲的包分配的序号从0~254，约定255 为无需应答的特殊含义包的发送序号，应答序号值为255 含义相当于没有捎带应答，即无效应答。
2、 发送方对应答的响应
假设当前发方重传窗口的头指针对应序号为h，则：
如果发送方收到的应答序列号是255，则不通知LLP。
如收到的应答序号i 大于h 且落在重传窗口头尾指针之间（包括尾指针），说明收方已收到h~i-1 的包且期望序号为i 的微包，这样从h 到i-1 的空间都是可以释放的，这样的应答号表示肯定应答。此时，需要将该释放的重传缓冲释放掉，并且将重传次数计数器和重传定时器置为0。需要注意的是这里的应答号是指收方期望收到的下一个序号，而PCI-E的应答号是指收方正确收到的最后一个序号。
如果到的应答序号还等于h，由于当前头指针是h ，则隐含意思为前一次应答号一定为h 且h 之前的包已收到，这第二次应答号h 表示h 仍未收到，需要重传，所以连续两次相等的应答号实际就表示否定应答。此时，需要重传重传缓冲中所有有效数据。重传指针由h逐拍加一直至尾指针。重传完毕后，重传指针重回h。在这里，应答不分种类，两个连续同样的应答号表示否定应答，而PCI-E是区分ACK和NAK的。
3.3 接收方协议
1、 信息捎带机制
在本协议中，双方需要交互的应答号等信息都是由反向流量即反向数据包进行捎带的，也就是说，不用像PCI-E那样需要使用额外的DLLP包进行传输。每个消息会被
分为若干个微包。每一个微包为10Bytes，其中有2Bytes为控制信息，控制信息中的VCR指明需要更新信用的虚通道，而CR指明更新的信用量。
2、 空包发送机制
为了保持发送方与接收方的持续信息交互，当某一方在持续一定时间没有返回流量时，LLP层会生成一个称为空包的包返回对方，用于带回应答序列号。此空包的发送序列号固定为255，在发送时不进重传缓冲，无需重传，无需返回应答，有了错误直接丢弃。
3、 接收方返回应答序列号
如果接收方收到一个序列号为255的包，则不返回应答序列号。
接收方LLP的接收窗口为i时，如果收到一个序列号为i且无CRC错的包时，将包送往上层，且窗口值加1，指示下一个需要接收包的序列号，同时，将这个值通过捎带返回发送方，表示i之前的包已经成功接收。
如果接收方收到的包不是期望序列号或者CRC校验错，则接收窗口i保持不变，并尽快捎带应答序列号i返回发送方告知发送方其期望序列号为i的包。也就是说，如果有反向流量，则立即将接收窗口值捎带回去，如果没有反向流量则立刻安排不携带数据的包将接收窗口值捎带回去。
但是，对于错误包，也并非简单返回未作改变的应答窗口号，有的情况需要捎带无效序列号：
* 没有收到需要返回应答的包，且没有有效序列号需要返回时，提供给发送LLP捎带的是无效序列号255；
* 如果初次收到错误包后连续收到错误包，且当前接收窗口已被捎带了两次，则保持返回无效序列号255，直至下次收到序列号为接收窗口期望的序列号的包为止。
4.两种协议的比较
本节给出三个例子，来看两种协议分别是如何保证可靠传输的。
4.1 发送数据包丢失
图3 ACK/NAK协议对丢失TLP的处理
如图3所示，为PCI-E的ACK/NAK协议对丢失TLP的处理。过程如下：
1、 发送设备发送TLP0。
2、 接收设备收到TLP0，返回ACK0，作为应答，接收序列号寄存器NEXT_RCV_SEQ值变为1，即下一TLP应为TLP1。接收设备又接收到TLP1，但是没有返回ACK1（ACK合并）， NEXT_RCV_SEQ值变为2。
3、 发送设备见到ACK0后，消除重传缓冲器中的TLP0及其以前的TLP。
4、 TLP2在中途丢失。
5、 接收设备收到TLP3，而其接收序列号寄存器NEXT_RCV_SEQ值为2，则丢弃TLP3，并安排应答序列号为NEXT_RCV_SEQ-1=1的NAK返回发送方。
6、 发送设备收到NAK1，消除重传缓冲中的TLP1，并重传TLP2及其以后的TLP。
图4为HIPPI协议对丢失数据包的处理。过程如下：
1、 发送设备发送Packet0。
2、 接收设备收到Packet0，接收序列号寄存器值变为1，即下一Packet应为Packet1，并捎带返回应答序列号1。接收设备又接收到Packet1，但是没有返回应答序列号2（暂无反向流量）， 接收序列号寄存器值变为2。
图4 HIPPI协议对丢失packet的处理
3、 发送设备见到ACK1后，消除重传缓冲器中的Packet0及其以前的Packet。
4、 Packet2在中途丢失。
5、 接收设备收到Packet 3，而其接收序列号寄存器值为2，则丢弃Packet 3，并安排两次应答序列号2返回发送方。
6、 发送设备收到ACK2，消除重传缓冲中的Packet1。发送设备再次接收到ACK2，发现Packet2没有被正确接收，则安排重传Packet2及其后面在接收窗口内的所有Packet。
可以看出，若丢失的消息包后再无消息包发送，则两种协议都会超时重传。若丢失消息包后还有消息包，则接收方会返回NAK通知发方重传，在ACK协议中，NAK同时应答了需要重传的消息包以前的包；在HIPPI协议中，是以两次对同一消息包的应答来表示否定应答，可能会使重传推迟发生，但同时也更加可靠的保证了重传是从错误包开始的。
4.2 ACK丢失
图5 ACK/NAK协议对丢失ACK的处理
图5为ACK/NAK协议处理ACK丢失过程。
1、 发送设备发送TLP0，接收设备收到后返回ACK0，发送设备接收到ACK0，清除重传缓冲中的TLP0。
2、 发送设备发送TLP1、2，接收设备收到后返回ACK2，但是在途中丢失，或者到达发送设备后经检测有CRC错（发送设备丢弃此DLLP）。
3、 发送设备发送TLP3、4，接收设备收到后返回ACK4。
4、 发送设备接收ACK4，清除重传缓冲中的TLP1、2、3、4。
在HIPPI协议中，丢失ACK有两种情况：一种是携带ACK的空包丢失，处理过程与上述过程类似；另一种是携带ACK的数据包丢失，如下图所示。
图6 HIPPI协议对丢失ACK的处理
接收方携带应答序列号ACK3的数据包丢失，而后续携带应答序列号的数据包由于序列号不对而不被发送方接收。所以，Packet1因得不到应答而引起超时重传。接收方，因发送方连续返回的对ACK1的应答而重传携带ACK3的数据包。
相比较而言ACK/NAK协议的实现方式更为简单，而且引起超时的可能性更小。
4.3 NAK丢失
图7中，TLP0、1正确到达接收方，TLP2到达接收方后出错，接收方返回的NAK1在途中丢失。由于已经发送过NAK，所以对于后续到达接收方的TLP，接收方不再返回ACK或者NAK。所以发送方的TLP1及以后的TLP，因得不到应答而超时重传。虽然TLP1被接收方正确接收，也有可能被重传，也就是说，重传有可能不是从错误包开始的
图7 ACK/NAK协议对丢失NAK的处理
而在HIPPI协议中，接收方是以重复的对同一序列号的应答来表示NAK，如图8所示，发送方最多两次收到接收方返回的同一应答序列号，全部丢失的概率比较小，因而HIPPI的重传一般都是从错误包开始的，基本不会重传正确的包。
5.包级重传与微包级重传的比较
PCI-E使用的是包级重传，而HIPPI使用的是微包级重传，微包级重传的好处是当一个微包出错后，不用重传整个消息，而是重传错误微包及其以后的微包，使得重传的内容减少，但是，它在每个微包内增加了控制信息，使得传送一个消息的额外开销增大。下面对包级重传与微包级重传进行一个系统的比较。假设链路的误码率为10-15，网络负载率为100%。
为了进行比较，我们以有效数据传输率（Efficient Transmitting Ratio，ETR）来进行对比，有效数据传输率定义为：
ETR=Payload/Flow
Payload为有效数据载荷。单位Byte。
Flow为在传递有效数据的过程中，链路上数据的总流量。单位Byte。
在包级重传协议中，假设在链路上传送的包长为最大包长，则Payload=4096。
在理想情况I下，链路误码率为0，则此时，FlowP0=4096+28=4124。28为附加的控制信息等所占的Byte数。此时
ETRP0=Payload/FlowP0=4096/4124=99.32%
在重传一次成功的情况E1下，因为从消息发送方发送一个包到接收到这个包的应答，发送方已经发送出去两到三个包（在未超时的情况下），所以FlowP1=4124+4124*3=16496。此时，
ETRP1=Payload/FlowP1=4096/16496=24.8%
同理，在重传两次成功的情况下：
ETRP2=Payload/FlowP2=4096/16496/2=12.4%
三次：
ETRP3=Payload/FlowP3=4096/16496/3=8.2%
……
在微包级重传协议中，4096bytes的包被分为128个微包，每个微包附加8bytes的控制信息。
在理想情况I下，FlowM0=4096+1024=5120。此时
ETRM0=Payload/FlowM0=4096/5120=80%
在出错的情况E下，因为HIPPI使用多次重复的应答表示重传，假设发送方都是接到重复ACK以后开始重传的，则从发送方发送微包到接收到该微包的重复应答，发送方已经发送的微包个数约为几十个，其个数因内部延迟，链路延迟等的不同而有差异，在本例中，假设为50个，由于每个微包40bytes，则经过N次重传
FlowMN=5120+40*50*N
此时，
ETRMN=Payload/FlowMN
ETRM1=57.5%，ETRM2=44.9%，……
可见，使用微包级重传协议时，链路上出现错误时与没有错误时，其有效数据传输率相比较包级重传很接近；而在使用包级重传协议时，若链路上发生错误，其有效数据传输率会大幅下降。
在链路的误码率为10-15的情况下，一个4096bytes的包出错的概率为：
P=1-（1-10-15）4096*8=3.3*10-11
在此情况下，
ETRP=ETRP0*（1-P）+ETRP1*P（1-P）+ ETRP2*P2（1-P）+……≈99.32%
ETRM=ETRM0*（1-P）+ETRM1*P（1-P）+ETRM2*P2（1-P）+……≈80%
如若考虑应答包的额外开销，则PCI-E的应答包是单独的8bytes的DLLP包，而HIPPI是基于携带的应答。假设每接收一个TLP都要返回一个DLLP，则
ETRP= ETRP*5120/(8+5120) ≈99.12%
综合以上情况来看，在链路的误码率为10-15的正常情况下，单从有效数据传输率方面出发，由于微包级重传附加了1/4的额外开销，采用包级重传要比微包级重传效果好。
现在假设误码率未知，则在ETRP= ETRM的情况下，可得包错误的概率P≈40%，即可算出误码率为1.56*10-5。也就是说当误码率为1.56*10-5时，包级重传与微包级重传性能相当，而误码率继续增大时，微包级重传的性能则要超过包级重传的性能。
6.结 束 语
本文简要分析了两种重传机制的优缺点，通过对比，可以看出，HIPPI协议采用了应答携带机制，省去了标示ACK/NAK的标志位，相比较而言较为复杂，但是在某些情况下，其效率也更高。ACK/NAK协议较为简单，实现起来比较容易。另外，微包级重传与包级重传相比，微包级重传更适用于误码率较高的链路，而在误码率较低的链路上，包级重传具有较好的性能。
参考文献：
N.R.Adiga et al.Blue Gene/L torus interconnection network. IBM J. Res.& Dev. 49, No. 2/3, 265–276
