CN105959239B - 三维光片上网络的通信方法 - Google Patents

Abstract

本发明公开了一种三维光片上网络的通信方法，主要解决现有三维光片上网络中通信链路利用率低下、单一节点阻塞影响其他节点通信、通信时延大和网络吞吐量低的问题。其技术方案是：以三维Mesh和Torus结构为例，当资源预约分组在中间节点被阻塞时，根据网络实时情况对该资源预约分组进行重传，并在进行资源预约分组重传过程中对资源预约分组重传的条件进行优化，本发明克服了三维Mesh和三维Torus结构中通信阻塞较大，单一节点的阻塞影响其他节点通信的问题，解除了三维Torus结构采用最短维序路由算法产生的死锁，在能耗增加不大的情况下提高了通信链路利用率和吞吐量，减小了延时，可用于实现光片上IP核之间的高效通信。

Description

三维光片上网络的通信方法

技术领域

本发明属于通信技术领域，特别涉及一种片上网络的通信方法，可用于实现光片上IP核之间的高效通信。

背景技术

在片上系统朝着多核化和异构化方向发展的过程中，片上网络的概念被提出来，其核心思想是将计算机网络技术融合到芯片设计中，从体系结构上来彻底改善总线结构带来的一系列问题。但随着单片集成电路上的IP核数达到众核甚至千核，集成电路尺寸进入纳米时代后，时钟频率越来越高，电互联技术的寄生电容、信号串扰等问题将变得十分显著。光互连技术由于具有高带宽，低功耗，低延时，小串扰和电磁干扰等优势，能有效地解决片上网络传统电互连技术领域的一系列瓶颈问题。因此，光互连技术已经成为片上网络倍受关注的一种技术。

随着核数进一步增多，芯片尺寸进一步缩小，在工艺尺寸缩减受限的情况下，二维片上网络在集成密度、通信带宽、可扩展性和面积开销等方面凸显瓶颈，因此三维光片上网络应运而生，通过三维光片上网络的三维立体互联通信解决上述诸多问题。

目前，在片上缺乏低成本、高效率的光缓存器件，同时光逻辑处理技术尚不成熟的条件下，传统的光电路交换由于其数据传输速度快、不需要片上光缓存、信息分组传输可靠等优点被广泛应用于光片上网络。在光电路交换中，源节点和目的节点之间的通信需要独享链路资源。其不利之处在于链路的利用率较低，随着网络负载的增加，网络阻塞会比较严重。

三维Mesh和Torus两种网络构架具有拓扑规则、结构简单、易于实现的特点，是目前三维片上网络广泛使用的架构。当光电路交换应用于三维Mesh网络架构时，建链分组在预约光路径的过程中一旦发现输出端口被占用，只能阻塞在当前节点等待端口释放。同时，由于该建链分组预约的前一段路径并未释放，使得这段资源既不能自己使用，又不能释放给其他通信节点使用。这极大的降低了链路的利用率并造成单一节点的阻塞扩散至网络其他节点。当光电路交换应用于三维Torus网络架构时，除了有以上问题外，在通信过程中还容易产生死锁，严重降低通信效率。为减轻以上问题带来的坏处，顾华玺等人在《实现光片上网络的低阻塞通信路由器及通信方法》，专利号为ZL201110330001.9的专利中，针对二维Mesh网络提出回收数据分组的通信方法：当建链分组在中间节点被阻塞时，把数据临时回收到中间节点，然后再由中间节点转发给目的节点。此方法虽然在一定程度上克服了单一节点的阻塞可能影响其他节点通信的问题，但由于片上缺乏低成本，高效率的光缓存器件，同时光逻辑处理技术尚不成熟，每回收一次数据就需要经过一次光信号转变成电信号，电信号在转换成光信号的过程，这会使得能耗非常大。如果将此方法用于三维mesh网络结构，上述问题会更加突出，且此方法不能用于Torus网络结构中解决死锁问题。

发明内容

本发明的目的是针对上述已有技术的不足，提出一种三维光片上网络的通信方法，以解除通信中的死锁，解决单一节点阻塞影响其他节点通信的问题，提高资源利用率，减小延时、提高网络吞吐量。

为实现上述目的，本发明技术方案包括如下：

(1)网络初始化

1a)参数初始化：设置阻塞确认分组的回传时间权值β，阻碍其它资源预约分组个数回传门限值N_max，以及源节点IP核收到阻塞确认分组后再次重发该资源预约分组的等待时间T_ip；

1b)构建网络：使用路由器构建三维光片上结构的电控制网络和光传输网络；

1c)建立坐标系：建立电控制网络和光传输网络的三维坐标系XYZ，根据该三维坐标系确定当前通信的源节点位置(x_s，y_s，z_s)和目的节点的位置(x_d，y_d，z_d)；

(2)源节点产生资源预约分组，在该分组中标记源节点(x_s，y_s，z_s)、目的节点(x_d，y_d，z_d)的位置信息及资源预约分组序号，并将携带这些信息的资源预约分组通过电控制网络向目的节点传输，并在传输的过程中预约沿途光链路资源；

(3)在电控制网络的中间节点根据路由算法计算资源预约分组的输出端口M，查询输出端口M是否被锁定：若被锁定，则查询锁定该端口的资源预约分组，将此资源预约分组阻塞其它分组的次数加1，执行步骤(4)；否则，用中间节点锁定输出端口M，并记录资源预约分组的输入输出端口信息和输出端口M的锁定时刻T_lock，转发该资源预约分组，执行步骤(5)；

(4)进行资源预约分组重传过程

4a)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的源节点位置(x_s，y_s，z_s)，计算当前节点与源节点之间的跳数H_cs；根据H_cs判断当前节点是否为源节点：若H_cs＝0，则当前 节点是源节点，执行步骤4i)；否则，执行步骤4b)；

4b)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的目的节点位置(x_d，y_d，z_d)，计算当前节点与目的点之间的跳数H_cd；根据H_cd判断下一跳是不是目的节点：若H_cd≤1，则当前节点是目的节点，执行步骤4i)；否则，执行步骤4c)；

4c)查询资源预约分组已经阻塞别的分组的个数N_b，若N_b>N_max，则执行步骤4g)；若1≤N_b≤N_max，则执行步骤4d)；若N_b＝0，则执行步骤4i)；

4d)根据当前节点和目的节点之间的跳数H_cd和输出端口M查询当前节点记录中的该端口平均锁定延时T_{new_avg}；若查询记录为空，则该端口平均锁定延T_{new_avg}＝0；计算等待该端口释放所需延时T_wait：

T_wait＝T_{new_avg}-(T_cur-T_lock)

式中，T_cur为当前时刻，T_lock为该输出端口被锁定时的时刻，T_{new_avg}表示该端口在当前节点距离目的节点H_cd跳时所需锁定的平均延时，执行步骤4e)；

4e)根据当前节点和源节点之间的跳数H_cs计算重传资源预约分组的时间代价T_price：

T_price＝T_{tear_mod}+T_ip+T_{set_mod}+H_cs×T_process

式中，T_{tear_mod}为阻塞确认分组的传输延时，T_ip为源节点收到阻塞确认分组后与重新产生资源预约分组的间隔延时，T_{set_mod}为资源预约分组的传输延时，T_process为资源预约分组经过电控制网络中每一个中间节点所需的延时，执行步骤4f)；

4f)比较步骤4d)获得的延时T_wait与步骤4e)获得的时间代价T_price：若T_wait＞T_price，则满足重传条件，执行步骤4g)，否则，执行步骤4i)；

4g)当前节点产生阻塞确认分组，该阻塞确认分组携带拆链信息、源节点和目的节点的位置信息及资源预约分组序号，通过已经预约的光链路发往源节点，该阻塞确认分组携带的拆链信息将沿路释放资源预约分组预约的资源，执行步骤4h)；

4h)源节点收到阻塞确认分组后，在之后的T_ip时刻重新产生资源预约分组，该资源预约分组携带阻塞确认分组带回的源节点、目的节点的位置信息及资源预约分组序号，通过电控制网络向目的节点传输，并在传输的过程中预约沿途路径，返回步骤3；

4i)资源预约分组在当前节点的缓存中等待输出端口M被释放；

(5)根据当前节点与目的点之间的跳数H_cd判断资源预约分组是否到达目的节点，若H_cd不为零，则资源预约分组未达到目的节点返回步骤3；否则，资源预约分组达到目的节点，执行步骤6；

(6)资源预约分组到达目的节点后，由目的节点产生响应分组，该响应分组携带该资源预约分组序号，通过已经预约的光链路发往源节点；

(7)源节点在接收到响应分组后，检查响应分组携带的序号，并根据此序号提取本地数据分组队列中的相应数据分组，通过已经预约的光链路向目的节点传输该数据分组；

(8)传输数据分组，数据分组的尾部携带着拆链信息，在沿着预约的路径经过中间节点时，该拆链信息将通知光路由器释放被预约的资源，在解锁输出端口M时更新该端口平均锁定延时T_{new_avg}；数据分组沿着预约好的光链路传输至目的节点；

(9)目的节点接收数据分组后，将其传送至本地IP核中处理，完成整个通信过程。

本发明与现行技术相比具有以下优点：

1.本发明根据网络实时环境对资源预约分组进行动态重传，克服了传统三维光片上系统中阻塞较大、单一节点的阻塞可能影响其他节点通信的问题，解决了一些三维网络通信中的死锁问题，在能耗增加不大的情况下减小延时、提高吞吐量。

2.本发明结合资源预约分组所需等待时间、与目的节点的距离以及资源预约分组阻塞其他资源预约分组的个数等因素，在进行资源预约分组重传过程中对资源预约分组重传的条件进行了优化，克服了现有通信方法忽略通信的实际情况、不具有灵活性的问题。

附图说明

图1是本发明的实现流程图。

具体实施方式

下面结合附图对本发明的实施方式做进一步详细描述。

本发明以三维Mesh和三维Torus结构为例，解决三维Mesh和三维Torus结构采用光电路交换时链路利用率较低，单一节点阻塞影响其他节点通信的问题，并解决三维Torus结构中采用光电路交换的死锁问题，有效提高网络资源的利用率，从而减小通信延时，提高网络吞吐量。

参照图1，本发明的实现步骤如下：

步骤1：网络初始化。

网络的初始化包括参数初始化，构建网络和建立坐标系三个步骤：

1a)参数初始化：资源预约分组为数据分组的传输预约光链路资源，当资源预约分组在电控制网络中发生阻塞时，希望通过及时释放该资源预约分组预约的前一段链路，以便其他数据分组可以利用，降低网络阻塞。因此需要选择资源预约分组重传的规则并设定参数对被阻塞资源预约分组是否执行重传进行判定，具体参数包括阻塞确认分组回传时间权值β，阻碍其它资源预约分组个数门限值N_max以及源节点IP核收到阻塞确认分组后再次重发该资源预约分组所需等待时间T_ip；

β满足条件为0≤β≤1，该回传时间权值与等待端口释放的延时T_wait相关，N_max根据网络平均跳数确定其具体数值，T_ip根据当前网路流量大小确定其具体数值；

1b)构建网络：使用路由器构建三维Mesh结构、三维Torus结构的电控制网络和光传输网络，该路由器有7对输入输出端口，其中本地输入输出端口通过网络接口与IP核相连，向东、向西、向北、向南、向上和向下的输入输出端口分别与相邻的路由器相连；

1c)建立坐标系：在电控制网络中，以左下角为原点，根据右手螺旋法则建立三维坐标系XYZ，节点坐标值为(x，y，z)；根据该三维坐标系确定当前通信的源节点位置(x_s，y_s，z_s)和目的节点的位置(x_d，y_d，z_d)；光传输网络的坐标系和电控制网络重合。

步骤2：产生资源预约分组。

源节点产生资源预约分组，在该分组中标记源节点(x_s，y_s，z_s)、目的节点(x_d，y_d，z_d)的位置信息及资源预约分组序号；

将携带位置信息及资源预约分组序号通过电控制网络向目的节点传输，并在传输的过程中预约沿途光链路资源。

步骤3：传输资源预约分组。

传输资源预约分组包括计算输出端口M和查询输出端口M是否被锁定两个步骤：

3a)计算输出端口M：

在不同的结构中，资源预约分组传输到中间节点时，根据不同的结构采用不同的路由算法计算其所需输出端口，即：

在三维Mesh结构中计算输出端口M，是由电控制网络的中间节点采用XYZ维序路由算法计算资源预约分组的输出端口M；

在三维Torus结构中，电控制网络的中间节点采用维序最短路由算法计算资源预约分组的输出端口M；

其中所述XYZ维序路由算法是三维Mesh结构常用的路由算法，该路由算法具有易实现、简单、无活锁和无死锁的优点。在该路由算法中，分组首先沿电控制网络X维进行路由，直到到达与目的节点X坐标相同节点位置(x_d，y_s，z_s)，然后该分组沿电控制网络Y维路由，直到到达与目的节点Y坐标相同的节点位置(x_d，y_d，z_s)，最后该分组沿电控制网络Z维路由到目的节点；

其中所述维序最短路由是Torus网络中常用的路由算法。在该路由算法中，分组首先沿电控制网络X维中离目的节点所在Y维的跳数最少方向进行路由，直到到达与目的节点的Y坐标相同的节点位置(xd，ys，zs)，然后该分组沿电控制网络Y维中离到目的节点所在Z维跳数最少的方向进行路由，直到到达与目的节点的Z坐标相同的节点位置(x_d，y_d，z_s)，最后该分组沿电控制网络Z维中离到目的节点跳数最少的方向进行路由，直至目的节点；

3b)查询输出端口M是否被锁定：若被锁定，则查询锁定该端口的资源预约分组，将此资源预约分组阻塞其它分组的次数加1，执行步骤(4)；否则，用中间节点锁定输出端口M，并记录资源预约分组的输入输出端口信息和输出端口M的锁定时刻T_lock，转发该资源预约分组，执行步骤(5)。

步骤4：进行资源预约分组重传过程。

4a)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的源节点位置(x_s，y_s，z_s)，计算当前节点与源节点之间的跳数H_cs：H_cs＝|x_c-x_s|+|y_c-y_s|+|z_c-z_s|；根据H_cs判断当前节点是否为源节点：若H_cs＝0，则当前节点是源节点，执行步骤4i)；否则，执行步骤4b)；

4b)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的目的节点位置(x_d，y_d，z_d)，计算当前节点与目的节点之间的跳数H_cd：H_cd＝|x_c-x_d|+|y_c-y_d|+|z_c-z_d|；根据H_cd判断下一跳是不是目的节点：若H_cd≤1，则当前节点是目的节点，执行步骤4i)；否则，执行步骤4c)；

4c)查询资源预约分组阻塞别的分组的个数N_b，若N_b>Nmax，则执行步骤4g)；若1≤N_b≤N_max，则执行步骤4d)；若N_b＝0，则执行步骤4i)；

4d)根据当前节点和目的节点之间的跳数H_cd和输出端口M查询当前节点记录中的该端口平均锁定延时T_{new_avg}；若查询记录为空，则该端口平均锁定延时T_{new_avg}＝0；计算等待该端口释放所需延时T_wait：T_wait＝T_{new_avg}-(T_cur-T_lock)，

式中，T_cur为当前时刻，T_lock为该输出端口被锁定时的时刻，T_{new_avg}表示该端口在当前节点距离目的节点H_cd跳时所需锁定的平均延时，T_wait值大于等于零，若计算得T_wait小于零，则取T_wait＝0；

4e)根据当前节点和源节点之间的跳数H_cs计算重传资源预约分组的时间代价T_price：

T_price＝T_{tear_mod}+T_ip+T_{set_mod}+H_cs×T_process

式中，T_{tear_mod}为阻塞确认分组的传输延时，T_ip为源节点收到阻塞确认分组后与重新产生资源预约分组的间隔延时，T_{set_mod}为资源预约分组的传输延时，T_process为资源预约分组经过电控制网络中每一个中间节点所需的延时

4f)比较步骤4d)获得的延时T_wait与步骤4e)获得的时间代价T_price：若T_wait＞T_price，则满足重传条件，执行步骤4g)，否则，执行步骤4i)；

4g)当前节点产生阻塞确认分组，并通过已经预约的光链路将该阻塞确认分组发往源节点，该阻塞确认分组携带拆链信息、源节点的位置信息、目的节点的位置信息以及资源预约分组序号，该阻塞确认分组携带的拆链信息将沿路释放资源预约分组预约的资源，执行步骤4h)；

4h)源节点收到阻塞确认分组后，在之后的T_ip时刻重新产生资源预约分组，该资源预约分组携带阻塞确认分组带回的源节点位置信息、目的节点位置信息以及资源预约分组序号，通过电控制网络向目的节点传输，并在传输的过程中预约沿途路径，返回步骤3；

4i)资源预约分组在当前节点的缓存中等待端口M被释放。

步骤5：判断资源预约分组是否到达目的节点。

根据当前节点与目的点之间的跳数H_cd判断资源预约分组是否到达目的节点，若H_cd不为零，则资源预约分组未达到目的节点返回步骤3；否则，资源预约分组达到目的节点，执行步骤6。

步骤6：产生响应分组。

资源预约分组到达目的节点后，由目的节点产生响应分组，该响应分组携带该资源预约分组序号，通过已经预约的光链路发往源节点。

步骤7：发送数据分组。

源节点在接收到响应分组后，检查响应分组携带的序号，并根据此序号提取本地数据分组队列中的相应数据分组，向已经预约的光链路发送该数据分组。

步骤8：传输数据分组。

数据分组的尾部携带着拆链信息，在沿着预约的路径经过中间节点时，该拆链信息将通知光路由器释放被预约的资源，在解锁输出端口M时更新该端口平均锁定延时T_{new_avg}

T_{new_avg}＝(1-β)(T_unlock-T_lock)+βT_{old_avg}

其中，T_unlock表示解锁输出端口M的时刻，T_lock为输出端口M被锁定的时刻，(T_unlock-T_lock)表示本次已预约H_cd跳的资源预约分组从请求该路由器的此端口到释放端口的延时，T_{old_avg}表示输出端口M之前被已预约H_cd跳的资源预约分组锁定的平均延时，它的初始值为0，β表示T_{old_avg}与(T_unlock-T_lock)的权重，取值为0到1之间；数据分组沿着预约好的光链路传输至目的节点。

步骤9：接收数据分组

目的节点接收数据分组后，将其传送至本地IP核中处理，完成整个通信过程。

以上描述仅是本发明的一个具体实例，不构成对本发明的任何限制。显然对于本领域的专业人员来说，在了解了本发明内容和原理后，都可能在不背离本发明原理、结构的情况下，进行形式和细节上的各种修改和改变，例如本发明可以用于除三维Mesh和Tours以外的网络，但是这些基于本发明思想的修改和改变仍在本发明的权利要求保护范围之内。

Claims (4)

1.三维光片上网络的通信方法，包括：

(1)网络初始化

1a)参数初始化：设置阻塞确认分组的回传时间权值β，阻碍其它资源预约分组个数回传门限值N_max，以及源节点IP核收到阻塞确认分组后再次重发该资源预约分组的等待时间T_ip；

1b)构建网络：使用路由器构建三维光片上结构的电控制网络和光传输网络；

1c)建立坐标系：建立电控制网络和光传输网络的三维坐标系XYZ，根据该三维坐标系确定当前通信的源节点位置(x_s，y_s，z_s)和目的节点的位置(x_d，y_d，z_d)；

(2)源节点产生资源预约分组，在该分组中标记源节点(x_s，y_s，z_s)、目的节点(x_d，y_d，z_d)的位置信息及资源预约分组序号，并将携带这些信息的资源预约分组通过电控制网络向目的节点传输，并在传输的过程中预约沿途光链路资源；

(3)在电控制网络的中间节点根据路由算法计算资源预约分组的输出端口M，查询输出端口M是否被锁定：若被锁定，则查询锁定该端口的资源预约分组，将此资源预约分组阻塞其它分组的次数加1，执行步骤(4)；否则，用中间节点锁定输出端口M，并记录资源预约分组的输入输出端口信息和输出端口M的锁定时刻T_lock，转发该资源预约分组，执行步骤(5)；

(4)进行资源预约分组重传过程

4a)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的源节点位置(x_s，y_s，z_s)，计算当前节点与源节点之间的跳数H_cs；根据H_cs判断当前节点是否为源节点：若H_cs＝0，则当前节点是源节点，执行步骤4i)；否则，执行步骤4b)；

4b)根据当前节点位置(x_c，y_c，z_c)和资源预约分组携带的目的节点位置(x_d，y_d，z_d)，计算当前节点与目的节点之间的跳数H_cd；根据H_cd判断下一跳是不是目的节点：若H_cd≤1，则当前节点是目的节点，执行步骤4i)；否则，执行步骤4c)；

4c)查询资源预约分组已经阻塞别的分组的个数N_b，若N_b>N_max，则执行步骤4g)；若1≤N_b≤N_max，则执行步骤4d)；若N_b＝0，则执行步骤4i)；

4d)根据当前节点和目的节点之间的跳数H_cd和输出端口M查询当前节点记录中的该端口平均锁定延时T_{new_avg}；若查询记录为空，则该端口平均锁定延时T_{new_avg}＝0；计算等待该端口释放所需延时T_wait：

T_wait＝T_{new_avg}-(T_cur-T_lock)

式中，T_cur为当前时刻，T_lock为该输出端口被锁定时的时刻，T_{new_avg}表示该端口在当前节点距离目的节点H_cd跳时所需锁定的平均延时，执行步骤4e)；

4e)根据当前节点和源节点之间的跳数H_cs计算重传资源预约分组的时间代价T_price：

T_price＝T_{tear_mod}+T_ip+T_{set_mod}+H_cs×T_process

式中，T_{tear_mod}为阻塞确认分组的传输延时，T_ip为源节点收到阻塞确认分组后与重新产生资源预约分组的间隔延时，T_{set_mod}为资源预约分组的传输延时，T_process为资源预约分组经过电控制网络中每一个中间节点所需的延时，执行步骤4f)；

4f)比较步骤4d)获得的延时T_wait与步骤4e)获得的时间代价T_price：若T_wait＞T_price，则满足重传条件，执行步骤4g)，否则，执行步骤4i)；

4g)当前节点产生阻塞确认分组，该阻塞确认分组携带拆链信息、源节点和目的节点的位置信息及资源预约分组序号，通过已经预约的光链路发往源节点，该阻塞确认分组携带的拆链信息将沿路释放资源预约分组预约的资源，执行步骤4h)；

4h)源节点收到阻塞确认分组后，在之后的T_ip时刻重新产生资源预约分组，该资源预约分组携带阻塞确认分组带回的源节点、目的节点的位置信息及资源预约分组序号，通过电控制网络向目的节点传输，并在传输的过程中预约沿途路径，返回步骤(3)；

4i)资源预约分组在当前节点的缓存中等待输出端口M被释放；

(5)根据当前节点与目的点之间的跳数H_cd判断资源预约分组是否到达目的节点，若H_cd不为零，则资源预约分组未达到目的节点返回步骤3；否则，资源预约分组达到目的节点，执行步骤(6)；

(6)资源预约分组到达目的节点后，由目的节点产生响应分组，该响应分组携带该资源预约分组序号，通过已经预约的光链路发往源节点；

(7)源节点在接收到响应分组后，检查响应分组携带的序号，并根据此序号提取本地数据分组队列中的相应数据分组，通过已经预约的光链路向目的节点传输该数据分组；

(8)传输数据分组，数据分组的尾部携带着拆链信息，在沿着预约的路径经过中间节点时，该拆链信息将通知光路由器释放被预约的资源，在解锁输出端口M时更新该端口平均锁定延时T_{new_avg}；数据分组沿着预约好的光链路传输至目的节点；

(9)目的节点接收数据分组后，将其传送至本地IP核中处理，完成整个通信过程。

2.根据权利要求书1所述的方法，其中步骤4a)中计算当前节点与源节点之间的跳数H_cs，公式如下：

H_cs＝|x_c-x_s|+|y_c-y_s|+|z_c-z_s|

其中x_c、y_c、z_c分别为预约资源分组当前所在节点的X维坐标、Y维坐标、Z维坐标，x_s、y_s、z_s分别为源节点的X维坐标、Y维坐标、Z维坐标。

3.根据权利要求书1所述的方法，其中步骤4b)中计算当前节点与目的节点之间的跳数H_cd，公式如下：

H_cd＝|x_c-x_d|+|y_c-y_d|+|z_c-z_d|

其中x_c、y_c、z_c分别为预约资源分组当前所在节点的X维坐标、Y维坐标、Z维坐标，x_d、y_d、z_d分别为目的节点的X维坐标、Y维坐标、Z维坐标。

4.根据权利要求书1所述的方法，步骤(8)中更新端口M的平均锁定延时T_{new_avg}，计算公式如下：

T_{new_avg}＝(1-β)(T_unlock-T_lock)+βT_{old_avg}

其中，T_unlock表示解锁输出端口M的时刻，T_lock为输出端口M被锁定的时刻，(T_unlock-T_lock)表示本次已预约H_cd跳的资源预约分组从请求该路由器的此端口到释放端口的延时，T_{old_avg}表示输出端口M之前被已预约H_cd跳的资源预约分组锁定的平均延时，β表示T_{old_avg}与(T_unlock-T_lock)的权重，取值为0到1之间。