服务质量劣化点估计方法、服务质量劣化点估计设备和程序

摘要

一种QoS劣化点估计设备(S1)，包括流集合确定单元(3)、流质量信息收集单元(1)、路径信息收集单元(2)、流链路表管理单元(4)和QoS劣化点估计单元(8)。在生成将经过网络的流的QoS与所述流所经过的链路相关联的流链路表之前，流集合确定单元(3)优先选择经过约所述网络的链路总数的1/2的链路的流作为要被登记在所述流链路表中的流。流质量信息收集单元(1)收集流的QoS信息。路径信息收集单元(2)收集网络的路径信息。流链路表管理单元(4)基于QoS信息和路径信息来生成流链路表。QoS劣化点估计单元(8)基于流链路表来估计QoS劣化链路。

说明书

技术领域

本发明涉及通信网络系统，并且更具体地涉及用于估计QoS(服务质量)劣化点的QoS劣化点估计方法、QoS劣化点估计设备以及QoS劣化点估计程序。

背景技术

为了在QoS劣化时迅速指明通信网络中的QoS劣化点，在网络中布置了许多监视设备来始终监视它们的位置的QoS。当QoS劣化发生时，基于发生QoS劣化处的监视设备的位置来估计QoS劣化的区间(例如，日本专利文件特开2002-271392号公报)。该方法需要许多监视设备来准确地估计QoS劣化点，因而布置成本很高。为了解决这个问题，已经提出了这样一种方法：经由穿过网络的每个通信流的QoS信息和路由信息来估计QoS劣化点(例如，日本专利文件特开2006-238052号公报)。

将描述日本专利文件特开2006-238052号公报中所公开的QoS劣化点估计方法。首先，创建表(以下，称为流链路表(flow link table))，该表将流、流所经过的链路(有向链路)和QoS相互关联。假定流F1至F5经过包括图15中所示的路由器(或分组交换机)R1至R6的网络。在图15中示出的网络中，每个链路如图16中所示被命名。分组丢失率用来表示QoS。假定流F1至F5的分组丢失率分别是3.0％、2.5％、3.5％、1.0％和0.5％。在这种情况中，创建图17中所示的流链路表。假定每个流每秒发送100个分组，并且分组丢失率是基于每2秒丢失的分组数来计算的。图17中的比特“1”指示流所经过链路。

该QoS劣化点估计方法接下来执行非劣化链路去除处理。更具体而言，基于流质量的预定劣化阈值和非劣化阈值，所具有的质量低于劣化阈值的各个流被定义为劣化流。所具有的质量高于非劣化阈值的各个流被定义为非劣化流。其余的流被定义为中间质量流。通过从流链路表去除中间质量流的行、非劣化流的行和非劣化流所经过的链路的列可以创建缩减的流链路表。

例如，考虑分组丢失率，将劣化阈值设为2％，将非劣化阈值设为1％。在图17中所示的示例中，F1至F3是劣化流，F5是非劣化流，并且F4是中间质量流。如图18中所示，从图17所示的流链路表中删除中间质量流F4的行、非劣化流F5的行以及非劣化流F5经过的链路L30和L45的列，从而创建图19中所示缩减的流链路表。

最终，QoS劣化点估计方法基于图19中的缩减的流链路表估计QoS劣化点。例如在基于QoS劣化流的估计方法中，经过图19中的链路L10、L20、L50和L40的劣化流的数目分别是1、3、1。则最多数量的流所经过的链路L20被估计为QoS劣化点。

在最小链路计数估计方法中，考虑经过图19中的链路L10、L20、L50和L40的流的集合。获得覆盖图19中的所有流的最少数量的链路的集合作为劣化链路集合。更具体而言，在图19中示出的示例中，经过链路L10、L20、L50、L40的流的集合分别是{F1}、{F1、F2、F3}、{F2}、{F3}。流经例如包括3个链路的链路集合{L10，L50、L40}的流的并集是覆盖所有流的{F1、F2、F3}。包括两个链路的链路集合{L10，L20}或包括一个链路的链路集合{L20}也可以覆盖所有的流。在覆盖所有流的链路集合中，包括最少数量的链路的{L20}被估计为最小链路集合。

发明内容

要解决的问题

日本专利文件特开2006-238052号公报中所公开的QoS劣化点估计方法使用经过网络的所有流或从所有流中任意选出的流来估计QoS劣化点。当将经过网络的所有流用于QoS劣化点估计时，流链路表中行的数目(流的数目)非常大，导致耗费时间的QoS劣化点估计。将从所有流中任意选出的流用于QoS劣化点估计使得QoS劣化点估计不准确。

本发明的一个目的是缩短QoS劣化点估计所需要的时间并且提供QoS劣化点估计的准确度。

解决问题的手段

根据本发明的一种QoS劣化点估计方法，包括以下步骤：在生成将经过网络的流的QoS与所述流所经过的链路相关联的流链路表之前，优先选择经过所述网络的链路总数的约1/2的链路的流作为要被登记在流链路表中的流；基于经过网络的流的QoS和网络的路径信息来生成流链路表；以及基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计方法，包括以下步骤：在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，优先选择经过多数链路的流作为要被登记在流链路表中的流；基于经过网络的流的QoS和网络的路径信息来生成流链路表；以及基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计方法，包括以下步骤：在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，从网络上的任意两个终端之间可发送/可接收的所有流的集合中，优先选择包括经过的链路不相同的数目约为网络的链路总数的1/2的两个流的流对作为要被登记在流链路表中的流；基于经过网络的流的QoS和网络的路径信息来生成流链路表；以及基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计方法，包括以下步骤：在生成将经过网络的流的QoS与所述流所经过的链路相关联的流链路表之前，从所述网络上的任意两个终端之间可发送/可接收的所有流的集合中优先选择使得所述集合的流中的至少一个流所经过的链路的集合较大的流来作为要被登记在所述流链路表中的流；基于经过所述网络的流的QoS和网络的路径信息来生成流链路表；以及基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计设备，包括：流集合确定装置，用于在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，优先选择经过网络的链路总数的约1/2的链路的流作为要被登记在流链路表中的流；流质量信息收集装置，用于收集经过网络的流的QoS的信息；路径信息收集装置，用于收集网络的路径信息；流链路表生成装置，用于基于所收集的QoS的信息和路径信息来生成流链路表；以及估计装置，用于基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计设备，包括：流集合确定装置，用于在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，优先选择经过多数链路的流作为要被登记在流链路表中的流；流质量信息收集装置，用于收集经过网络的流的QoS的信息；路径信息收集装置，用于收集网络的路径信息；流链路表生成装置，用于基于所收集的QoS的信息和路径信息来生成流链路表；以及估计装置，用于基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计设备，包括：流集合确定装置，用于在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，从网络上的任意两个终端之间可发送/可接收的所有流的集合中，优先选择包括经过的链路不相同的数目约为网络的链路总数的1/2的两个流的流对作为要被登记在流链路表中的流；流质量信息收集装置，用于收集经过网络的流的QoS的信息；路径信息收集装置，用于收集网络的路径信息；流链路表生成装置，用于基于所收集的QoS的信息和路径信息来生成流链路表；以及估计装置，用于基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

根据本发明的一种QoS劣化点估计设备，包括：流集合确定装置，用于在生成将经过网络的流的QoS与流所经过的链路相关联的流链路表之前，从网络上的任意两个终端之间可发送/可接收的所有流的集合中优先选择使得集合的流中的至少一个流所经过的链路的集合较大的流来作为要被登记在流链路表中的流；流质量信息收集装置，用于收集经过网络的流的QoS的信息；路径信息收集装置，用于收集网络的路径信息；流链路表生成装置，用于基于所收集的QoS的信息和路径信息来生成流链路表；以及估计装置，用于基于流链路表来估计作为网络上的QoS劣化点的QoS劣化链路。

发明的效果

根据本发明，经过约网络链路总数的1/2的链路的流被优先地选为要被登记在流链路表中的流。这缩减了流链路表的行数(流的数目)。因此可以使QoS劣化点估计所需的时间比以前短。也可以最小化在流链路表上具有相同垂直比特串的链路的数目。这提高了QoS劣化点估计准确度。

根据本发明，经过多数链路的流被优先地选为要被登记在流链路表中的流。这缩减了流链路表的行数(流的数目)。因此可以使得QoS劣化点估计所需的时间比以前短。也可以最小化在流链路表上具有相同垂直比特串的链路的数目。这提高了QoS劣化点估计准确度。

根据本发明，网络上的任意两个终端之间可发送/可接收的所有流的集合中、包括经过的不相同链路的数目约为网络的链路总数的1/2的两个流的流对被优先地选为要被登记在流链路表中的流。这缩减了流链路表的行数(流的数目)。因此可以使得QoS劣化点估计所需的时间比以前短。也可以最小化在流链路表上具有相同垂直比特串的链路的数目。这提高了QoS劣化点估计准确度。

根据本发明，网络上的任意两个终端之间可发送/可接收的所有流的集合中、使得集合的流中的至少一个流所经过的链路的集合较大的流被选为要被登记在流链路表中的流。这缩减了流链路表的行数(流的数目)。因此可以使得QoS劣化点估计所需的时间比以前短。也可以最小化在流链路表上具有相同垂直比特串的链路的数目。这提高了QoS劣化点估计准确度。

在本发明中，被选作要被登记在流链路表中的流被确定为测试流。当网络上的终端被指示向网络发送测试流时，测试流经过终端。每个终端将测试流的QoS信息发送给QoS劣化点估计设备。结果，有关当前正在通信的流(包括测试流)的流链路表被创建。在本发明中，可以针对QoS劣化点估计确定被使得独立于网络用户的通信而流动的测试流的最佳集合。根据本发明，由于可以确定测试流的最佳集合，所以还可以确定用于布置终端来在网络上传递测试流的最佳方法。

附图说明

图1是示出根据本发明第一示例性实施例的网络的布置的示例的示图；

图2是示出根据本发明第一示例性实施例的QoS劣化点估计设备的内部布置的框图；

图3是示出根据本发明第一示例性实施例的QoS劣化点估计设备中的流集合确定单元的操作的流程图；

图4是示出根据本发明第一示例性实施例的完整流链路表的示例的示图；

图5是示出根据本发明第一示例性实施例的QoS劣化点估计设备中的流链路表管理单元的操作的流程图；

图6是示出根据本发明第一示例性实施例的流链路表的示例的示图；

图7是示出根据本发明第一示例性实施例的QoS劣化点估计设备中的非劣化链路去除单元的操作的流程图；

图8是示出根据本发明第一示例性实施例的缩减的流链路表的示例的示图；

图9是示出根据本发明第一示例性实施例的QoS劣化点估计设备中的QoS劣化点估计单元的操作的流程图；

图10是示出流链路表的示例以说明本发明第一示例性实施例的效果的示图；

图11是示出缩减的流链路表的示例以说明本发明第一示例性实施例的效果的示图；

图12是示出根据本发明第二示例性实施例的QoS劣化点估计设备中的流集合确定单元的操作的流程图；

图13是示出根据本发明第三示例性实施例的QoS劣化点估计设备中的流集合确定单元的操作的流程图；

图14是示出根据本发明第四示例性实施例的QoS劣化点估计设备中的流集合确定单元的操作的流程图；

图15是示出与本发明关联的网络布置的示例和经过该网络的流的示例的示图；

图16是示出图15中的网络的链路的示图；

图17是示出流链路表的示例的示图；

图18是示出从图17中的流链路表中删除中间质量流的行、非劣化流的行和非劣化流所经过的链路的列的示图；以及

图19是示出缩减的流链路表的示例的示图。

具体实施方式

【第一示例性实施例】

现在将参考附图描述本发明示例性实施例。图1是示出根据本发明第一示例性实施例的网络的布置的示例的示图。网络包括路由器(或交换机)R1至RN。用于测量质量的测试终端A1至AK和QoS劣化点估计设备S1是连接的。在该示例性实施例中，将两个路由器中相反的链路视作不同的链路，由L1至LM表示路由器R1至RN之间的通信链路。

测试终端A1至AK具有以下功能：测量QoS的功能、向QoS劣化点估计设备S1通知测量到的QoS信息的功能、生成测试流并且根据来自QoS劣化点估计设备S1的指令向网络发送该测试流的功能。

图2示出根据本发明第一示例性实施例的QoS劣化点估计设备S1的内部布置。QoS劣化点估计设备S1包括流质量信息收集单元1、路径信息收集单元2、流集合确定单元3、用作流链路表生成装置的流链路表管理单元4、流链路表存储单元5、非劣化链路去除单元6、缩减的流链路表存储单元7、QoS劣化点估计单元8和显示单元9。QoS劣化点估计设备S1从测试终端A1至AK收集每个流的QoS信息，基于从路由器R1至RN获得的路径信息估计QoS劣化点，并且将估计结果输出给显示单元9。

以下将说明QoS劣化点估计设备S1的各个构成元件的操作。当测试终端A1至AK开始通信时，流质量信息收集单元1接收来自它们的通信开始通知。在通信开始后，流质量信息收集单元1周期地从测试终端A1至AK接收当前QoS信息(例如，用作流发送源的发送终端的地址，用作流目的地的接收终端的地址、流质量信息和流速率)。流质量信息是诸如分组丢失率、延迟和延迟抖动之类的有关QoS的信息。流速率是在用于通信的流中每秒的分组数的信息。当测试终端A1至AK结束通信时，流质量信息收集单元1接收来自它们的通信结束通知。

路径信息收集单元2从路由器(交换机)R1至RN收集有关路由的路径信息。可以使用SMTP(简单网络管理协议)等来完成该信息收集。路径信息使得能够基于发送和接收终端的地址信息来确定用于它们之间的通信的路径。从路由器收集的路径信息更具体地包括路由表和ARP(地址解析协议)表的配置信息。从交换机收集的路径信息更具体地包括转发数据表和生成树的配置系信息。注意，网络管理员可以给出路径信息来替代从路由器(交换机)R1至RN收集路径信息。

流集合确定单元3从测试终端A1至AK获得表示连接到它们的路由器的信息。基于该信息和由路径信息收集单元2收集的路径信息，流集合确定单元3确定要以以下所述的方式传送测试流的终端并且指示测试终端A1至AK通过所判定的终端传送测试流。图3是示出流集合确定单元3的操作的流程图。

首先，流集合确定单元3通过将流、流所经过的链路、用作流发送源的发送终端的地址和用作流目的地的接收终端的地址相互关联来输出有关K个测试终端A1至AK中任意两个间的所有流的流链路表(图3中的步骤S100)。该流链路表将被称为完整流链路表X。区分了流发送方向和流接收方向，在K个测试终端A1至AK中任意两个间可以存在K×(K-1)个流。因此，完整流链路表X是针对K×(K-1)个流生成的。

图4示出完整流链路表X的示例。图4中的F1表示流。在图4中示出的示例中，所有的单元格都是空白的。在实际的完整流链路表X中，在流的行和流所经过的链路的列的交叉处的单元格中设置比特“1”。可以使用从测试终端A1至AK获得并且表示它们的连接目的地的路由器的信息和由路径信息收集单元2收集的路径信息来生成完整流链路表X。流集合确定单元3以以下方式从完整流链路表X中的K×(K-1)个流确定要被提供用于QoS测量的测试流的集合。

在该示例性实施例中，第一流集合确定方法被用作该流集合确定方法。使用第一流集合确定方法，流集合确定单元3首先计算链路总数M的1/2的值H(步骤S101)。如果链路总数M实际上不能被2整除，则通过向上取整或者去掉M/2的小数点以下的分数部分来将M/2舍入为整数值H。

接着，流集合确定单元3从完整流链路表X获得每个流所经过的链路数(步骤S102)。通过对完整流链路表X的每个行中的比特“1”进行计数获得要经过的链路数。流集合确定单元3通过以H与要经过的链路数之间的差的绝对值的升序排列流来对完整流链路表X的流进行排序(步骤S103)。如果多个流所经过相同数目的链路，即，如果对于多个流，H与要经过的链路数之间的差的绝对值相同，则这些流可以以任何顺序排序。

流集合确定单元3以优先顺序的降序排列，即，以H与经过的链路数之间的差的绝对值的升序来确定完整流链路表X中预定数目J个流作为测试流的集合(步骤S104)。可替换地，流集合确定单元3将排序后的完整流链路表X中、H与要经过的链路数之间的差的绝对值等于或小于的预定阈值的流确定为测试流的集合(步骤S104)。

最后，流集合确定单元3指示测试终端A1至AK中、所确定的测试流的发送和接收终端来发送测试流(步骤S105)。

基于由流质量信息收集单元1收集的QoS信息和由路径信息收集单元2收集的路径信息，流链路表管理单元4通过将发送终端地址、接收终端地址、要经过的链路、流质量(例如，分组丢失率)和流速率进行关联来生成有关当前正在通信的流的流链路表。流链路表存储单元5存储流链路表。该流链路表将被称为流链路表Y。图5是示出流链路表管理单元4的操作的流程图。

流链路表管理单元4从流质量信息收集单元1接收QoS信息(图5中的步骤S200)并且从路径信息收集单元2接收路径信息(步骤S201)。然后，流链路表管理单元4从QoS信息获得发送终端地址、接收终端地址、流质量和流速率(步骤S202)。每个流将经过的链路是基于路径信息和发送终端地址信息来确定的(步骤S203)。因此，流链路表管理单元4生成流链路表Y(步骤S204)并且将其登记在流链路表存储单元5中(步骤S205)。

图6示出流链路表Y的示例。像完整流链路表X一样，在流的行与流所经过的链路的列之间的交叉处的单元格中设置“1”。利用流集合确定单元3的上述操作，测试流所经过测试终端A1至AK。测试终端A1至AK将测试流的QoS信息发送给QoS劣化点估计设备S1。因此，流链路表Y是关于当前正在通信的流(包括测试流)而创建的。

非劣化链路去除单元6针对流链路表Y周期地执行非劣化链路去除处理，从而生成缩减的流链路表Z。缩减的流链路表存储单元7存储缩减的流链路表Z。图7是示出非劣化链路去除单元6的操作的流程图。

非劣化链路去除单元6周期地从流链路表存储单元5读出流链路表Y并且核查是否存在具有的质量低于预定劣化阈值的劣化流(图7中的步骤S300)。如果存在劣化流，则非劣化链路去除单元6从流链路表Y删除非劣化流的行(除了劣化流和非劣化流所经过的链路的列以外)以及发送终端地址、接收终端地址、流质量和流速率。因此，非劣化链路去除单元6生成缩减的流链路表Z(步骤S301)并且将其登记在缩减的流链路表存储单元7中(步骤S302)。图8示出缩减的流链路表Z的示例。

图9是示出QoS劣化点估计单元8的操作的流程图。QoS劣化点估计单元8从缩减的流链路表存储单元7中读出缩减的流链路表Z(步骤S400)，使用QoS劣化流计数估计方法或最小链路计数估计方法来估计QoS劣化点(步骤S401)，并且在显示单元9上显示估计出的QoS劣化点(步骤S402)。

如参考图19所述，QoS劣化流计数估计方法估计缩减的流链路表Z中所登记的链路中、最大数目的劣化流所经过的链路作为QoS劣化点。另一方面，最小链路计数估计方法估计缩减的流链路表Z中所登记的并且覆盖所有劣化流的链路集合(链路的组合)中、包括最少数量的链路的最小链路集合作为QoS劣化点。

因此，QoS劣化点估计设备S1使得显示单元9显示被估计作为QoS劣化点的链路。

接下来将说明本示例性实施例的效果。在日本专利文件特开2006-238052号公报中所公开的QoS劣化点估计方法中，如果流链路表Y中链路的列中所设置的垂直比特串包括具有相同比特串的一个或多个链路，则所有这些链路都被视为QoS劣化点的候选，而不论哪个链路具有实际的QoS劣化。假定图10中示出的流链路表Y。在流链路表Y中，链路L2和L4具有相同的比特串。因此，即使它们中只有一个有QoS劣化，也生成图11中示出的缩减的流链路表Z。在这种情况中，QoS劣化点估计单元8使用基于QoS劣化流的数目的估计方法或最小链路计数估计方法来将链路L2和L4两者都确定为QoS劣化点。结果，链路中没有QoS劣化的一个链路被错误地确定为QoS劣化点，造成较低的估计准确度。

然而，本示例性实施例的流集合确定单元3选择测试流的集合，以将具有相同比特串的链路的数目最小化为最小数目的流。在本示例性实施例的第一流集合确定方法中，在完整流链路表X的相应行中设置的比特数(要经过的链路数)约为链路总数的1/2的流被优先地确定为测试流。

为什么使用第一流集合确定方法的理由如下。将注意力集中到完整流链路表X的两行(流)上。如果每行任意地包括比特“1”，则包括1/2的比特“1”的行的数目可以被最大化。此外，感兴趣的这两行的比特位于不同位置的概率的平均值被最大化。从以下可见该现象发生。设P为完整流链路表X的每列具有比特“1”的概率。当两行包括相等数目的比特“1”时，比特不同的概率是p×(p-1)。当p＝1/2时，该概率被最大化。

根据由流集合确定单元3这样确定的测试流集合，可以缩减流链路表Y的行数(流的数目)。因此，与日本专利文件特开2006-238052号公报中所公开的QoS劣化点估计方法相比，可以缩短QoS劣化点估计所需的时间。还可以最小化在流链路表Y上具有相同垂直比特串的链路的数目。这提高了QoS劣化点估计准确度。

【第二示例性实施例】

接下来将描述本发明第二示例性实施例。根据该示例性实施例的网络和QoS劣化点估计设备S1的布置和第一示例性实施例中相同，并且将使用图1和图2中的标号进行说明。与第一示例性实施例不同的是，流集合确定单元3使用第二流集合确定方法作为流集合确定方法。以下，将描述第二流集合确定方法。

图12是示出根据该示例性实施例的流集合确定单元3的操作的流程图。首先，该示例性实施例的流集合确定单元3如步骤S100中生成完整流链路表X(步骤S500)，如步骤S101中计算链路总数M的1/2的值H(步骤S501)，并且如步骤S102中从完整流链路表X获得每个流所经过的链路数(步骤S502)。

然后，流集合确定单元3通过以经过的链路数的降序排列流来对完整流链路表X的行进行排序(步骤S503)。如果多个流所经过相同数目的链路，则这些流可以以任何顺序排序。

流集合确定单元3以优先顺序的降序，即要经过的链路数的升序确定完整流链路表X中预定数目J个流作为测试流的集合(步骤S504)。可替换地，流集合确定单元3确定完整流链路表X中经过的链路数等于或大于预定阈值的流作为测试流的集合(步骤S504)。

最后，流集合确定单元3指示测试终端A1至AK中所确定的测试流的发送和接收终端来发送测试流(步骤S505)。从而，流集合确定单元3的处理结束。

QoS劣化点估计设备S1的其余构成元件的操作与第一示例性实施例中一样。

根据该示例性实施例的流集合确定单元3的第二流集合确定方法基于与第一流集合确定方法相同的概念。考虑一般的网络拓扑，流只经过远少于网络链路总数M的1/2的链路的概率可以很高。经过约链路总数M的1/2与经过尽可能多的链路实际上同义。因此，该示例性实施例使得能够获得与第一流集合确定方法相同的效果。

【第三示例性实施例】

接下来将描述本发明第三示例性实施例。根据该示例性实施例的网络和QoS劣化点估计设备S1的布置与第一示例性实施例中相同，并且将使用图1和图2中的标号进行说明。

与第一示例性实施例不同的是，流集合确定单元3使用第三流集合确定方法作为流集合确定方法。以下将描述第三流集合确定方法。

图13是根据该示例性实施例的流集合确定单元3的操作的流程图。首先，该示例性实施例的流集合确定单元3如步骤S100中生成完整流链路表X(步骤S600)并且如步骤S101中计算链路总数M的1/2的值H(步骤S601)。然后，流集合确定单元3定义完整流链路表X的所有行(流)的集合U并且在假定元素的所有可能的组合的情况下，计算集合U的两个元素之间的距离(步骤S602)。

使用在表示所经过的链路的比特串之间的汉明(Hamming)距离，即在两个元素之间的经过的链路不同的数目来所谓集合U中两个元素之间的距离。假定：在完整流链路表X中，流F1经过链路L1和L3，并且流F2经过链路L1。在流F1和F2(即，集合U的两个元素)之间，经过的链路具有一比特不同。因此，流F1与F2之间的距离为1。注意：集合U的两个元素的组合存在总共K×(K-1)×{K×(K-1)-1}种可能。以下，在步骤S602中获得元素间距离的一组元素将被称为元素对。

接着，流集合确定单元3针对在步骤S602中获得元素间距离的所有元素对计算H与元素间距离之间的差的绝对值。然后，流集合确定单元3通过以H与元素间距离之间的差的绝对值的升序排列这些元素对来对完整流链路表X的行进行排序(步骤S603)。

流集合确定单元3以优先顺序的降序，即H与元素间距离之间的差的绝对值的升序从排序后的完整流链路表X的开始选择预定数目P个元素对(步骤S604)。可替换地，流集合确定单元3从排序后的完整流链路表X中选出H与元素间距离之间的差的绝对值等于或小于预定阈值的元素对(步骤S604)。

流集合确定单元3将步骤S604中所选择的元素对集合中每个元素对的至少一个元素中所包括的所有流确定为测试流(步骤S605)。最后，流集合确定单元3指示测试终端A1至AK中所确定的测试流的发送和接收终端来发送测试流(步骤S606)。从而，流集合确定单元3的处理结束。

QoS劣化点估计设备S1的其余构成元素的操作与第一示例性实施例中一样。

根据该示例性实施例的流集合确定单元3的第三流集合确定方法提供以下效果。

将注意力集中到完整流链路表X中的任意两行，经过的链路的比特不同的数目对应于汉明距离。在任意两个流之间，链路只有4种比特组合(0，0)、(0，1)、(1，0)和(1，1)。通过两个流的质量出现的方式的组合将所有链路排序成4种类型。

当任意两个流包括具有比特组合(0，0)、(0，1)、(1，0)和(1，1)的4个链路时，有关这4个链路的汉明距离为2。这扩展到所有链路。当汉明距离是链路总数的1/2时，所有的链路被极为一致地识别为这4种类型。如果流的数目是k，则当所有的流一致地识别这4种类型时，可由这k个流识别的链路数被最大化(即，具有相同垂直比特串的链路数可以被最小化)。这样的流集合使得能够使用最小数目的流来最大化QoS劣化点估计准确度。

如上所述，在该示例性实施例中，使得流之间的汉明距离更接近链路总数的1/2的流被选出。因此，可以预期QoS劣化点估计准确度被使用最小数量的流最大化。

【第四示例性实施例】

接下来将描述本发明第四示例性实施例。根据该示例性实施例的网络和QoS劣化点估计设备S1的布置与第一示例性实施例中相同，并且将使用图1和图2中的标号来进行说明。

与第一示例性实施例不同的是，流集合确定单元3使用第四流集合确定方法作为流集合确定方法。以下，将描述第四流集合确定方法。

图14是示出根据该示例性实施例的流集合确定单元3的操作的流程图。首先，该示例性实施例的流集合确定单元3如步骤S100中生成完整流链路表X(步骤S700)。然后，流集合确定单元3定义完整流链路表X的所有流(行)的集合U、作为空集的流集合S，以及T＝0(步骤S701)。

接着，流集合确定单元3检查：T是等于或大于预定值J还是U是空集(步骤S702)。如果任一个条件满足，则图14中的处理结束。否则，处理进行到下一步骤(步骤S703)。使用完整流链路表X，流集合确定单元3获得作为S的元素的这些流中的至少一个流所经过的链路总数P(步骤S703)。流集合确定单元3通过针对作为U的元素的流r中的每一个流将r加到S来获得流集合S∩{r}，并且获得作为S∩{r}的元素的这些流中的至少一个流所经过的链路总数P′(r)(步骤S704)。

流集合确定单元3针对步骤S704中获得的每个流r和步骤S703中所获得P来计算差P′(r)-P，优先地以差的降序选择流，并且将它们加到S(步骤S705)。流集合确定单元3从U排除在步骤S705中被添加到S的流，将所添加的流的数目加到T，并且返回步骤S702(步骤S706)。每次步骤S705中的处理被执行，T单调递增，并且元素数单调递减。有时一定要满足步骤S702中的两个条件中的至少一个，并且流集合确定单元3停止其操作。

QoS劣化点估计设备S1的其余构成元件的操作与第一示例性实施例中相同。

根据该示例性实施例的流集合确定单元3的第四流集合确定方法提供以下效果。

将注意力集中到完整流链路表X的各列。如果在没有流所经过的链路中发生劣化，则没有流被劣化。由于QoS劣化的发生本身被遗漏了，所以QoS劣化点估计准确度降低。在该示例性实施例中，当确定流集合时，流被选择并且被添加以最小化没有流所经过的链路数。因此，可以预期最小化QoS劣化的发生被遗漏的可能性并且使用最小数目的流来最大化QoS劣化点估计准确度。

根据第一至第四示例性实施例中任一实施例的QoS劣化点估计设备S1例如可以通过包括CPU、存储装置和用于控制这些硬件资源的程序的计算机来实现。用于操作计算机的QoS劣化点估计程序被提供作为记录在诸如软盘、CD-ROM、DVD-ROM或存储卡之类的记录介质上的程序。CPU将读出的程序写入存储装置中并且根据所述程序执行第一至第四示例性实施例中所描述的处理。

产业应用

本发明适用于在通信网络系统中估计QoS劣化点的技术。