定义3 给定的一组用户中，每个用户都有一个由D位数字组成的全局惟一的ID，对于组群中的任何一个用户u，每个(i,j)端口，如果在邻居表中满足以下条件，则认为这些邻居表是K一致的，K>0，0≤i≤D-1，0≤j≤B-1：

　　(1)如果j=u.ID[i]，则(i,j)端口为空。

　　(2)如果j≠u.ID[i]，则(i,j)端口包含了min(K,m)(i,j)-邻居，这里m是所有从属于u的(i,j)-ID子树上所有用户的数目。

　　密钥服务器也维护了一个邻居表，该邻居表只有单独一行。该行包含了B个端口，每一个称之为(0,j)端口，j=0,1,…，B-1。ID号具有“[j]”前缀的所有用户中，密钥服务器选择K(或者当这样的用户数目少于K)个与密钥服务器具有最小往返时延的用户，作为它的(0，j)-邻居。

　　2.3 多播方案：T-Mesh

　　给定的一组用户，它们嵌入在多播树上的邻居表是建立在密钥服务器和用户之上的。不论是密钥服务器还是用户都能使用邻居表，通过多播向其他用户发送消息。多播组由单个发送方，一组接收方和需要多播的消息组成，发送方是多播源。密钥更新多播组中，密钥服务器即为发送方，在组群中的所有用户为接收方。在数据传输的多播组中，需要进行数据传输的特定用户为发送方，所有其他用户为接收方。下面用“成员”特指组群中的密钥服务器或某个用户。

　　T-Mesh多播方案适用于密钥更新和数据传输。在该多播方案中，需要进行多播的消息中含有“forward_level”域。该域对应于用户的转发层。在多播会话中，用户要收到一个多播消息的复本，所以这些用户都在一个相同的转发层上。

　　定义4 在多播会话中，发送方的转发层定义为0。如果一个用户u收到的消息中“forward_level”值为i，该用户u则被认为在i转发层上。

　　多播一个消息时，发送方首先将消息中的“forward_level”域值置为0，然后进行选路转发。当用户收到消息时，也执行该过程。每个成员根据多播消息中的“forward_level”域值核对自己的邻居表用以决定多播消息的下一跳接收者。

　　5个用户组成的密钥更新多播树的例子。多播消息的一个复本首先进入每个ID子树的level-1层，然后进入level-2层，依次类推，一个成员的ID与它的下游用户满足一个特定关系。如下所述：

　　引理1 在多播会话中，如果成员u位于转发层i，0≤i≤D。那么u的ID和它所有下游用户都具有相同的前缀u.ID[0:i-1]。即u和它的下游用户都位于ID子树的level-i层。

　　本文提出的用户ID分配方案的优化，从属于相同ID子树的所有用户在相同拓扑逻辑区域中。

　　引理2 多播会话中，假设成员u位于i转发层，0≤i≤D。那么，对于任何其他ID前缀为u.ID[0:i-1]的用户w只可能是u的下游用户。

　　引理1和引理2使得嵌入在邻居表中的多播树具有拓扑意识。即在多播会话中，仅有一个多播消息的复本进入每个拓扑逻辑区域；当forward_level=i的消息进入一个区域时(即ID子树的i层)，它仅被转发到它的子区域中(即ID子树中的(i+1)儿子层)，而不会被转发到其他区域。这样，在那些连接到较远区域，并具有较大时延的链路上，消息仅被转发一次。这有助于降低多播过程中的分布时延，也降低了链路传输的压力。

　　定理1 在多播会话中，如果组群中的每个用户都具有I一致(I-consistent)的邻居表，那么多播树中除发送方之外的每个用户都将收到多播消息的一个复本。

　　当K>1时，T-mesh同样提供故障快恢复，并能迅速适应网络的动态变化。如果某个成员探测到下一跳路径上有故障，或者通过突发丢失探测到下一跳链路上发生拥塞时，它能将消息转发给表中另外一个邻居。同时，该成员会寻找更多的邻居来代替出现故障或发生拥塞的邻居。

　　2.4 修改后的密钥树

　　密钥服务器维护着一棵密钥树。为了能够支持有效的密钥更新消息分离，本文中的密钥树不同于以往的密钥树。以前的密钥树具有固定的深度，当有新的用户加入时，树会垂直生长。经过修改后的密钥树具有固定的高度，并且当有新用户加入时，它只在纵向上生长。(本文中除非有其他的声明，后面的“密钥树”都是指修改后的密钥树)。

　　密钥树以组群密钥作为根节点。一棵密钥树含有两种节点：u节点和k节点。每个u节点为某一特定的用户，它含有该用户的用户密钥。用户只和密钥服务器共享用户密钥。k节点含有组群密钥或辅助密钥。当组群中的用户通过u节点与根节点通讯时，将会被授予包含在u节点中的用户密钥和包含在k节点中的密钥。

　　为了便于密钥更新消息分离，密钥树的结构必须与ID树相匹配，这由密钥服务器完成。密钥树上的每个u节点所具有的用户u的用户密码对应于ID树上ID号为u.ID的叶节点。

　　每次密钥更新结束，由于有新的节点加入或离开，密钥服务器将改变这些节点到根节点路径上的密钥。密钥服务器使用更新后的k节点的儿子节点中的密钥来加密更新后的k节点中的密钥。这时密钥服务器需要改变所知道的密钥，密钥服务器进行4次加密；{}，{}，{}，以及{}。其中，{}表示用密钥来加密。所有的加密都被置于密钥更新消息之中。每个用户仅需要密钥更新消息中的一个很小的子集。例如， 仅需要{}。

　　本文中提出的加密方案用来识别密钥和加密过程。密钥树上密钥的ID定义为密钥树上相应节点的ID。加密的ID定义为加密密钥的ID。ID与每个加密相联系。通过该识别方案，用户能够通过检查加密的ID确定它是否需要给定的加密。

　　引理3 给定的一个加密，用户需要密钥加密当且仅当加密的ID为用户ID的前缀。

　　2.5 密钥更新消息分离

　　当密钥更新完成之后，为了将新的密钥发送给用户，较为直接的方法就是向每个用户多播所有加密，并让用户自己去提取所需要的加密。但突发的密钥更新流量可能会使具有带宽限制的链路产生拥塞，尤其在用户接入链路。接入链路的拥塞还会导致所有下游用户的数据丢失。因此，必须尽可能地降低密钥更新的带宽开销。

　　为此本文提出了密钥更新消息分离方案。在本方案中，每个成员仅当它的下游用户中至少有一个用户需要加密，才向其转发加密。为了实现这个目标，密钥服务器通过路由密钥更新消息分离为每个(0,j)主要用户对分散的消息进行组合，j=0,1,…,B-1。每个在i转发层的用户，同样通过路由为每个主要用户(s,j)对分离消息进行组合，0≤i≤D-1,s=i,i+1,…,D-1,j=1,2,…,B-1。密钥更新消息分离方案的正确性阐述如下：

　　定理2 在密钥更新传输的多播会话中，假设成员u在i转发层，0≤i≤D-1。w为u的一个(s,j)主要邻居中，如果u是密钥服务器，则s=0；如果u是用户并且j=0,1,…,B-1,则s=i,i+1,…,D-1。假设集合V包含了w以及它的所有下游用户，那么当且仅当在V中至少有一个用户e.ID是w.ID[0:s]的前缀，或者，w.ID[0:s]是e.ID的前缀，才会调用加密e。

　　推论1 在密钥更新传输的多播会话中，假设组群中所有的用户具有I一致的邻居表，针对组群中每个用户的多播方案和密钥更新消息分离方案或由密钥服务器产生的加密e，当且仅当用户u需要e或他的下游用户中至少有一个需要e，u才能收到e的一份复本。

　　2.6 讨论

　　在密钥更新消息分离方案中，用户通过检查加密的ID可以确定一个加密是否是他的下游用户所需要的。因此，对于用户来说，没有必要去维护下游用户的状态。但如果我们用现有的应用层多播方案,或者不对密钥树进行修改，那么为了实现密钥更新消息分离，每个用户都必须清楚谁是他的下游用户，哪些加密是他们需要的。

　　分离方案与现有的应用层多播方案相比，有效地降低密钥更新的带宽开销。在T-mesh中，提取结构与修改过的密钥树和ID树相匹配，所以所有的用户共享属于相同ID子树i层的共同加密，这里i为包含在加密ID中的数字。这样，当转发层的值小于或等于i时，才有一份加密的复本被转发。在下面的转发层中，如果还有用户需要，复本将再被复制。

　　3  协议描述

　　3.1 用户ID分配

　　如果用户u想加入一个组群，它首先和密钥服务器(或是单独的注册服务器)通讯，然后通过SSL这样的协议来相互识别。如果用户通过了识别并被组群接收，那么u将会收到它的用户密钥和当前的组群密钥。此后，所有在用户u和服务器之间的通讯都会用该用户密钥进行加密。用户u和组群中其他用户之间的通讯都会用组群密钥进行加密。

　　3.1.1 步骤1：收集用户资料

　　u要想知道哪些用户属于他的(i+1,j)-ID子树，j=0,1,…,B-1，较为直接的方法就是让密钥服务器提供这些信息。但这样会增加密钥服务器的带宽开销。因此，u必须通过询问其他用户来收集这些信息。
　　当i=0时，u发送一份查询，用户的记录由服务器提供给u。当i>0时，因为u已经确定了ID中的第一位数字，他知道至少有一个用户属于u的(i,0)-ID 子树和(i,B-1)-ID子树。u向这样的用户发送一份查询。查询将目标ID前缀指定为u.ID[0:i-1]。当收到该查询时，接收用户检查他的邻居表，并返回邻居中所有具有目标ID前缀的用户记录。这样，如果子树不为空，u就可以从(i+1,j)-ID子树上收集到一个或多个用户，j=0,1,…,B-1。

　　为了从(i+1,j)-ID子树上收集到更多的用户，u必须不间断的查询那些从ID子树上收集到的用户，直到他收集到了P个用户，或者是他已经查询了子树上的所有用户。在每次查询中，u将目标ID前缀指定为u.ID[0:i-1]，并增加j。本文中假设P=10。

　　3.1.2 步骤2：测量往返时延