用于确定多入口与多出口之间的数据传递序列的方法和装置

摘要

本发明的目的是提供一种用于确定多入口与多出口之间的数据传递序列的方法和装置。本发明提供了用于确定多入口与多出口之间的数据传递序列的方法。在此，入口和出口的数量均为N，并且将从多入口传递的数据构成一个N*N数据矩阵；其中，每一个入口的深度是M，其表明用于传递所述数据矩阵的传递周期的数量；其中，在每一个传递周期中，所述方法包括以下步骤：a.基于每一个非零元素的交叉属性和数值属性确定矩阵中的每一个非零元素的传递成本，并且确定零元素的传递成本是零；b.从已确定成本的元素当中选择具有最大成本的元素；c.不考虑所选元素的行和列，回到步骤a来重新确定矩阵中剩余元素的传递成本，直到只剩下一个要重新确定传递成本的元素为止；d.基于N个数据样本确定数据传递序列，其中每一个数据样本是从N个所选元素当中的一个获得的。

说明书

技术领域

本发明涉及在多入口与多出口之间传递交叉并行数据的技术。

背景技术

在多入口与多出口之间进行交叉并行数据传递是矩阵问题。经典的解决算法是执行行交换或列交换以使得矩阵对角元素非零。当所有对角元素都非零时，生成传递矩阵。并且，单位矩阵执行相同的流程以获得传递矩阵。但是由于有时需要许多迭代，因此计算处理较为复杂并且花费更多时间。

发明内容

本发明的目的是提供一种用于确定多入口与多出口之间的数据传递序列的方法和装置。

根据本发明的一个方面，提供一种用于确定多入口与多出口之间的数据传递序列的方法。其中，入口和出口的数量均为N，并且将从多入口传递的数据构成一个N*N数据矩阵；

其中，每一个入口的深度是M，其表明用于传递所述数据矩阵的传递周期的数量；

其中，在每一个传递周期中，所述方法包括以下步骤：

a.基于每一个非零元素的交叉属性(cross-attribute)和数值属性(value-attribute)确定矩阵中的每一个非零元素的传递成本，并且确定零元素的传递成本是零；

b.从已确定成本的元素当中选择具有最大成本的元素；

c.不考虑所选元素的行和列，回到步骤a来重新确定矩阵中剩余元素的传递成本，直到只剩下一个要重新确定传递成本的元素为止；

d.基于N个数据样本确定数据传递序列，其中每一个数据样本是从N个所选元素当中的一个获得的。

根据本发明的一个方面，提供一种用于确定多入口与多出口之间的数据传递序列的交换设备。其中，入口和出口的数量均为N，并且将从多入口传递的数据构成一个N*N数据矩阵；

其中，每一个入口的深度是M，其表明用于传递所述数据矩阵的传递周期的数量；

其中，在每一个传递周期中，所述交换设备被配置来：

a.基于每一个非零元素的交叉属性和数值属性确定矩阵中的每一个非零元素的传递成本，并且确定零元素的传递成本是零；

b.从已确定成本的元素当中选择具有最大成本的元素；

c.不考虑所选元素的行和列，回到步骤a来重新确定矩阵中剩余元素的传递成本，直到只剩下一个要重新确定传递成本的元素为止；

d.基于N个数据样本确定数据传递序列，其中每一个数据样本是从N个所选元素当中的一个获得的。

根据本发明的一个方面，提供一种计算机可读介质。所述计算机可读介质包含计算机代码，所述计算机代码由包括多个入口和多个出口的交换设备执行，其中入口和出口的数量均为N，并且将从多入口传递的数据构成一个N*N数据矩阵；

其中，每一个入口的深度是M，其表明用于传递所述数据矩阵的传递周期的数量；

其中，在每一个传递周期中，所述交换设备被配置来：

a.基于每一个非零元素的交叉属性和数值属性确定矩阵中的每一个非零元素的传递成本，并且确定零元素的传递成本是零；

b.从已确定成本的元素当中选择具有最大成本的元素；

c.不考虑所选元素的行和列，回到步骤a来重新确定矩阵中剩余元素的传递成本，直到只剩下一个要重新确定传递成本的元素为止；

d.基于N个数据样本确定数据传递序列，其中每一个数据样本是从N个所选元素当中的一个获得的。

根据本发明的一个方面，提供一种计算机程序。所述计算机程序由包括多个入口和多个出口的交换设备执行，其中入口和出口的数量均为N，并且将从多入口传递的数据构成一个N*N数据矩阵；

其中，每一个入口的深度是M，其表明用于传递所述数据矩阵的传递周期的数量；

其中，在每一个传递周期中，所述交换设备被配置来：

a.基于每一个非零元素的交叉属性和数值属性确定矩阵中的每一个非零元素的传递成本，并且确定零元素的传递成本是零；

b.从已确定成本的元素当中选择具有最大成本的元素；

c.不考虑所选元素的行和列，回到步骤a来重新确定矩阵中剩余元素的传递成本，直到只剩下一个要重新确定传递成本的元素为止；

d.基于N个数据样本确定数据传递序列，其中每一个数据样本是从N个所选元素当中的一个获得的。

本发明允许多入口与多出口之间的高效的交叉并行数据传递。本发明确保在一个传递周期期间只能传递数据矩阵的每一行和列中的一个数据样本。

附图说明

通过参照附图阅读以下关于非限制性实施例的详细描述，本发明的其他特征、目的和优点将变得更加显而易见。

图1示出了根据本发明的基于一个传递周期中矩阵元素的传递成本确定数据传递序列的示例性流程；

图2示出了适用于本发明的RRH架构的示例性示意图；

图3a)-d)分别示出了根据本发明的一个实施例的多个数据矩阵及其相应的传递序列。

附图中的相同或类似的附图标记表明相同或相应的组件。

具体实施方式

后文中将参照附图更加详细地描述本发明。

本发明提供了针对多入口与多出口之间的交叉并行数据传递确定数据传递序列的一种解决方案。进一步地，本发明适用于任何类型的具有对称的多入口和多出口的交换设备。此外，除了交换设备之外，还可以由例如专用的确定设备之类的其他设备进行基于成本的数据传递序列的确定，尽管所述数据传递序列被使用在具有对称的多入口和多出口的交换设备中。

具体来说，对于多入口和多出口，入口和出口的数量均为N，因此将从多入口传递的数据构成一个N*N矩阵(后文中称作“数据矩阵”)。每一个入口的深度是M，并且深度意味着来自入口的数据的传递次数，直到入口为空为止。也就是说，对于一个N*N数据矩阵，其将经历M个传递周期以从多入口传递到多出口。并且数据矩阵的每一行和每一列的总的元素数值是M。

进一步地，在每一个传递周期中，基于传递成本确定数据传递序列。用于所述确定的具体步骤如下：

1)按照不同方式确定数据矩阵中的非零元素和零元素的传递成本。零元素意味着数值为零的元素，并且零元素的传递成本是零。非零元素意味着具有非零数值的元素，并且非零元素的传递成本基于其交叉属性和数值属性。

非零元素的交叉属性包括零属性和非零属性。非零元素的零属性表明该非零元素的同一行和同一列中的零的总数；并且非零元素的非零属性表明在该非零元素的同一行和/或同一列中是否存在非零元素。

2)在所有已确定成本的元素当中，从中选择具有最大成本的元素。如果有两个或更多元素具有相同的最大成本，则仅从这些元素当中选择一个元素。

3)排除所选元素的行和列，并且将数据矩阵中的剩余元素视为新的输入以在步骤a中重新确定其传递成本，直到只剩下一个元素将要重新确定其传递成本。

也就是说，在该传递周期中基于其传递成本选择了第一个元素之后，针对下一个元素的下一项选择将基于除去所选元素的行和列之外的矩阵中的剩余元素重新确定的传递成本而被确定；步骤1)-3)将被重复(N-1)次，于是在(N-1)次确定数据矩阵中的相应元素的传递成本之后选择了(N-1)个元素，并且最后只剩下一个元素，也就是在该传递周期中最后一个选择的元素。

4)根据前面的步骤1)-3)，基于N个所选元素确定数据传递序列。由于在一个传递周期中只能从每一个所选的元素传递一个数据样本，因此所确定的数据传递序列也构成一个N*N传递矩阵(后文中称作“传递矩阵”)，其中具有分别对应于N个所选元素当中的每一个的N个“1”元素以及填充传递矩阵的剩余部分的“0”元素。因此，在每一个N*N传递矩阵中，每一行和列中的数据样本不超过一个，因此在一个传递周期中最多传递N个数据样本。

以4*4多链路(multi-links)为例，将从多入口传递的数据也构成一个4*4数据矩阵，并且每一个入口的深度是64。因此，存在64个传递周期，并且每一个周期具有一个传递序列。如下示例性地示出将要传递的数据矩阵：

在一个传递周期中，N个所选元素是数据矩阵中的用行-列表明的元素，比如1-1、2-2、3-3和4-4。并且在每一个所选元素中只能传递一个数据样本。因此，该传递周期中的数据传递序列是：

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

5)在每一个传递周期之后更新数据矩阵，其中N个所选元素当中的每一个的数值减小1。随后把更新后的数据矩阵应用于传递序列的下一个周期。这一更新将经历(M-1)次，或者直到数据矩阵中的所有元素都是零为止。

参照图1，其中示出了基于一个传递周期中矩阵元素的传递成本确定数据传递序列的示例性流程。对于本发明的示例性说明，数据传递序列的确定被描述成由一交换设备实施。

在步骤101中，交换设备可以确定数据矩阵中的每一个零元素和非零元素的传递成本。零元素的传递成本是零。基于每一个非零元素的交叉属性和数值属性确定每一个非零元素的传递成本。

对于非零元素，其交叉属性包括其零属性以及其非零属性。非零元素的零属性表明该非零元素的同一行和同一列中的零的总数；并且非零元素的非零属性表明在该非零元素的同一行和/或同一列中是否存在非零元素。

下面的表1示出了将从多入口传递到多出口的数据矩阵。入口和出口的数量均为4。

出口1出口2出口3出口4入口100101入口2002—B02入口313—A014入口4010101430

表1

表1还表明多入口与多出口之间的对应关系。举例来说，元素A处于行入口3和列出口2，这意味着元素A将从入口3被传递到出口2。

以元素A为例来计算其传递成本。

①元素A的零属性

在同一行中有1个零并且在同一列中有2个零，因此零的总数是3个，于是元素A的零属性是3。

每次在基于最大成本选择了一个元素之后更新零属性，因此该元素的行和列被排除。

②元素A的非零属性

在同一行中有2个非零，这使得非零属性的数值为1，并且在同一列中有1个非零，这使得非零属性的数值为1，因此元素A的非零属性最终为2。也就是说，一个元素的非零属性可以是0、1或2。

在确定一个数据传递序列之后更新非零属性。

③元素A的数值属性

元素A的数值是3，因此元素A的数值属性是3。

④元素A的传递成本

传递成本是一个元素的交叉属性和数值属性的加权和。具体来说，包括在交叉属性中的零属性和非零属性可以被设定不同的权重。

举例来说，传递成本＝1*零属性+0.1*非零属性+0.001*数值属性。

因此，元素A的传递成本＝1*3+0.1*2+0.001*3＝3.203。

此外，对于元素B，其零属性是5(3+2)，其非零属性是1(0+1)，并且其数值属性是2。因此，元素B的传递成本＝1*5+0.1*1+0.001*2＝5.102。

在步骤102中，交换设备可以从已确定成本的元素当中选择具有最大成本的元素。假设元素B的传递成本是表1中的所有元素当中的最大成本，于是选择元素B。

当有多于一个元素具有最大成本时，交换设备可以随机选择一个，或者选择第一个元素。可以根据具体应用来设定选择规则。

在步骤103中，交换设备可以排除所选元素的行和列，并且返回步骤101来重新确定数据矩阵中的剩余元素的传递成本，直到只余一个元素来重新确定传递成本。

举例来说，对于该传递周期中的下一次传递成本确定，移除元素B的行和列。应当提到的是，所述移除动作仅仅是被用来帮助计算剩余元素的传递成本的“不考虑”的一个实例，因此并不意味着实际删除所选元素的同一行和同一列中的所有元素。仍然参照表1，元素B的交叉关联(cross-connection)被示出为下面的(1)。

随后剩余的数据矩阵(2)作为输入来重新确定每一个元素的传递成本。在矩阵(2)中，元素“3”是元素A。元素A的零属性变为1，并且其非零属性仍然是2。因此，元素A的传递成本＝1*1+0.1*2+0.001*3＝1.203。假设元素A的传递成本是矩阵(2)中的所有9个元素当中的最大成本，则选择元素A。

在下一次成本确定中将选择另一个元素。随后将只剩下一个元素。因此，该传递周期中的所有4个元素都被确定。

此外，当剩余元素全是零时，可以提前终止成本确定流程。但是，直到对于所有传递周期均确定了全部传递序列，传递序列的确定才将终止。这使得传递周期的数目与其他数据分组的数目一致。

在步骤104中，交换设备可以基于4个所选元素得到一个4*4传递矩阵的数据传递序列。具体来说，传递矩阵的每一行和每一列每次只能传递一个数据样本，于是在一个传递周期中可以传递不同行和列中的4个数据样本。

举例来说，在步骤101-103中选择了元素1-1、2-3、3-2和4-4，于是将移除这四个元素当中的每一个元素的一个数据样本，因此该传递周期中的数据传递序列是：

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

在步骤105中，交换设备可以更新该数据矩阵。在该传递周期中选择的N个元素当中的每一个的数值减小1，直到数值变为0为止。随后把更新后的数据矩阵应用于下一个传递周期以用于成本计算和传递序列确定。

根据本发明的一个实施例，RRH设备是适用的。参照图2，其中示出了RRH架构。RRH设备包括充当分组交换机的交叉(crossbar)模块。如图2中所示，所述交叉模块位于CPRI接口与天线处理链(后文中简称作天线-x/x)之间。

LTE-BBU把X*Y*Z个数据样本打包成一个分组。X是天线的数目，Y是每个天线载波的数目，并且K是每载波数据样本的数目。

举例来说，出于示例性的说明，LTE-BBU在本说明书中把8*4*8个数据样本打包成一个分组。数据样本的总数是256个。

分组通过CPRI巷道(lane)从LTE-BBU传递到RRH。

一个CPRI巷道仅提供64数据样本能力，因此存在4个CPRI巷道。

LTE-BBU根据用户配置对64个数据样本进行打包。在下面的表2中示出了“分组格式”的一个示例性实例，其中LTE-BBU基于相同的载波对数据样本进行打包。分组格式对于RRH是随机的。

CPRI巷道1CPRI巷道2CPRI巷道3CPRI巷道4天线1-载波1天线1-载波2天线1-载波3天线1-载波4天线2-载波1天线2-载波2天线2-载波3天线2-载波4天线3-载波1天线3-载波2天线3-载波3天线3-载波4天线4-载波1天线4-载波2天线4-载波3天线4-载波4天线5-载波1天线5-载波2天线5-载波3天线5-载波4天线6-载波1天线6-载波2天线6-载波3天线6-载波4天线7-载波1天线7-载波2天线7-载波3天线7-载波4天线8-载波1天线8-载波2天线8-载波3天线8-载波4

表2

如图2中所示，所述交叉模块提供交换功能以把来自CPRI的数据样本指派到对应的天线处理链中。分组格式信息已经通过其他信道被传递到RRH。

任意CPRI容器可以被路由到任意天线容器：

i.CPRI-X连续地传递分组。处于相同分组的数据样本组合到一个容器中。

ii.把一个分组从CPRI-X传递到天线-x/x侧仅花费64个周期。

iii.CPRI-X在一个周期仅弹射出一个数据样本。4个数据样本必须同步传递。

iv.天线-x/x在一个周期仅接受一个数据样本。

CPRI-X是入口的一个示例性实例，天线是出口的一个示例性实例，因此从CPRI传递到天线的数据样本构成一种多入口多出口情形。

参照图2，每一个CPRI-X和天线-x/x仅负荷64个数据样本。在此，为了CPRI巷道与天线处理链之间的均等，两个天线被组合到一组中。因此，CPRI巷道的数量为4，天线组的数量也是4。

256个数据样本被输入到4个CPRI中，并且每一个CPRI具有随机安排的64个数据样本，正如表2中所表明的那样。在下面的表3中示例性地示出了数据样本的安排。

天线-1/2天线-3/4天线-5/6天线-7/8CPRI-16416161616CPRI-26416161616CPRI-36416161616CPRI-46416161616总数64646464

表3

根据表3，将要传递的数据矩阵被确定为：

每一个CPRI-X的深度＝256/4＝64，于是需要在64个周期中传递数据矩阵。在每一个周期中，只能移除来自不同CPRI-X的4个数据样本并且确定一个传递序列。因此，对于一个传递分组生成64个传递序列，并且每一个传递序列形成一个传递矩阵。

举例来说，对于第一个传递周期，当采用向下计数时，其为第64周期。并且在该第64周期中，根据传递成本选择元素1-1、2-3、3-2和4-4，并且将要被传递的4个数据样本形成相应的传递序列为：

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

随后在第二个传递周期(也就是第63周期)中，将要传递的数据矩阵减小为：

图3示出了前8个数据矩阵及其对应的传递序列以及最后8个数据矩阵及其对应的传递序列。在此，图3a)示出了前4个数据矩阵及其对应的传递序列；图3b)示出了接下来的4个数据矩阵及其对应的传递序列；图3c)-3d)示出了最后8个数据矩阵及其对应的传递序列。

虽然图3仅仅示出了传递分组的数据矩阵及其对应的传递序列的一部分，但是本领域技术人员还应当认识到，基于在本发明中描述的传递成本的计算，可以很容易地确定该传递分组的剩余部分的数据矩阵及其对应的传递序列。

根据传递序列，每一个CPRI-X知道将要传递哪一个数据样本，交叉模块知道将把所接收到的数据样本传递到何处，并且每一个天线-x/x知道将被所接收到的数据样本存储到何处。

应当提到的是，本发明可以通过软件或者软件与硬件的组合来实施；举例来说，本发明可以通过ASIC(专用集成电路)、通用计算机或者任何其他类似的硬件设备来实施。

本发明的软件程序可以由处理器执行来实施前面的步骤或功能。同样地，本发明的软件程序(包括相关的数据结构)可以被存储在计算机可读记录介质中，例如RAM存储器、磁性或光学驱动器或者软盘和其他类似的设备。此外，本发明的一些步骤或功能可以通过硬件来实施，例如与处理器协作来执行各种功能或步骤的电路。

此外，本发明的一部分可以作为计算机程序产品被应用，例如计算机程序指令，其在由计算机执行时可以通过计算机的操作调用或提供根据本发明的方法和/或技术解决方案。此外，调用本发明的方法的程序指令可以被存储在固定或移动记录介质中，以及/或者通过其他信号承载介质中的广播或数据流来传送，以及/或者被存储在基于程序指令操作的计算机设备的工作存储器中。在这里，根据本发明的一个实施例包括一种装置，其包括用于存储计算机程序指令的存储器以及用于执行程序指令的处理器，其中当计算机程序指令由计算机执行时，所述装置被触发运行根据本发明的多个实施例的方法和/或技术解决方案。

本领域技术人员将认识到，本发明不限于前面的示例性实施例的细节，并且在不背离本发明的精神或基本特征的情况下，可以通过其他实施例来实施本发明。因此，所述实施例在任何方面都应当被认为是示例性而非限制性的；本发明的范围由所附权利要求书而不是前面的描述限制，并且意图落到权利要求书的等效元素的含义和范围内的所有变型都应当被涵盖在本发明内。权利要求中的附图标记不应当被认为是限制所涉及的权利要求。此外还应当认识到，术语“包括”不排除其他单元或步骤，并且单数不排除复数。在系统权利要求中陈述的多个单元或模块也可以由单个单元或模块通过软件或硬件实施。例如“第一”和“第二”之类的术语被用来表明名称，而不表明任何特定顺序。