法律状态公告日
法律状态信息
法律状态
2019-04-05
授权
授权
2017-04-19
实质审查的生效 IPC(主分类):H04L12/911 申请日:20161202
实质审查的生效
2017-03-22
公开
公开
技术领域
本发明涉及网络资源配置领域,特别是涉及一种基于时间段预约带宽资源的路径分配方法及装置。
背景技术
互联网Internet自60年代出现以来获得了蓬勃发展,伴随着多媒体技术的飞速发展,Internet上多媒体应用层出不穷,多媒体信息的数量与日俱增。已逐步由单一的数据传送网向数据、语音、图像等多媒体信息的综合传输网演化。但传统的TCP(Transmission Control Protocol,传输控制协议)/IP(Internet Protocol,互联网协议)体系中的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务,无法满足多媒体应用和各种用户对网络传输质量的不同要求。导致用户服务质量不高,网络资源配置不够合理。
发明内容
本发明实施例的目的在于提供一种基于时间段预约带宽资源的路径分配方法及装置,以实现提高用户服务质量,合理配置网络资源的目的。具体技术方案如下:
本发明实施例提供了一种基于时间段预约带宽资源的路径分配方法,包括:
获取用户的第一预约路径请求,所述第一预约路径请求至少携带有:所述第一预约路径请求的预约时间段、所述第一预约路径请求的预约时间段内的带宽需求量、源节点及目的节点,所述第一预约路径请求的预约时间段至少包括:预约开始时间及预约结束时间;
在所述第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息;
根据所述每条路径的带宽信息,确定所述第一预约路径请求的可用路径;
根据所述可用路径,确定与所述第一预约路径请求对应的匹配路径,并分配所述匹配路径给所述用户,以使所述用户在所述第一预约路径请求的预约时间段内使用所述匹配路径的带宽资源。
较佳的,所述确定每条路径的带宽信息,包括:
确定每条路径的所述带宽信息中包含的带宽需求量最大值;
相应的,所述根据所述每条路径的带宽信息,确定所述第一预约路径请求的可用路径,包括:
确定满足所述带宽需求量最大值小于或等于,路径能够提供最大带宽资源量的带宽容量的路径为所述第一预约路径请求的可用路径。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量;
相应的,所述确定每条路径的所述带宽信息中包含的带宽需求量最大值,包括:
在所述路径含有所述第二预约路径请求,且所述第二预约路径请求的预约时间段与所述第一预约路径请求的预约时间段至少部分时间段相同时,确定所述第二预约路径请求的带宽需求量与所述第一预约路径请求的带宽需求量之和;
确定所述和,作为所述带宽需求量最大值。
较佳的,所述确定每条路径的所述带宽信息中包含的带宽需求量最大值之后,所述路径分配方法还包括:
记录所述第一预约路径请求中,与所述第二预约路径请求除所述相同时间段以外的剩余时间段内的带宽需求量为第一预约路径请求的未处理部分。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量;
相应的,所述确定每条路径的所述带宽信息中包含的带宽需求量最大值,包括:
在所述路径含有所述第二预约路径请求,且所述第二预约路径请求的预约时间段与所述第一预约路径请求的预约时间段无相同时间段时,确定所述第二预约路径请求的带宽需求量与所述第一预约路径请求的带宽需求量的最大值;
确定所述最大值作为所述带宽需求量最大值。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量及每条路径能够提供最大带宽资源量的带宽容量;
相应的,所述确定每条路径的所述带宽信息中包含的带宽需求量最大值,包括:
在所述路径不含有所述第二预约路径请求时,确定所述第一预约路径请求的带宽需求量作为所述带宽需求量最大值。
较佳的,所述根据所述可用路径,确定与所述第一预约路径请求对应的匹配路径,包括:
步骤A,根据所述可用路径,获得所有节点与所述第一预约路径请求的源节点的第一距离,确定所述第一距离中的最小距离对应的节点;
步骤B,将所述第一距离中的最小距离对应的节点,归入最小距离节点的节点集中,并将所述第一距离中的最小距离对应的节点,作为归入后的节点;
步骤C,根据所述可用路径及所述归入后的节点,确定所有节点中所述归入后的节点以外剩余节点,与所述第一预约路径请求的源节点的第二距离,确定所述第二距离中的最小距离对应的节点;
步骤D,将所述第二距离中的最小距离对应的节点,归入所述节点集中,并将所述第二距离中的最小距离对应的节点,作为归入后的节点;
重复执行所述步骤C、所述步骤D,直至将剩余节点中的所述目的节点,归入所述节点集中,按照归入所述节点集中的节点归入的顺序,根据所有归入后的节点,形成一与所述第一预约路径请求对应的匹配路径。
较佳的,所述根据所述可用路径,获得所有节点与所述第一预约路径请求的源节点的第一距离,包括:
根据所述可用路径及每个路径的预设时延值,获得所有节点中每个节点分别与所述第一预约路径请求的源节点的时延值,作为所有节点中每个节点分别与所述第一预约路径请求的源节点的第一距离;
相应的,所述根据所述可用路径及所述归入后的节点,确定所有节点中所述归入后的节点以外剩余节点,与所述第一预约路径请求的源节点的第二距离,包括:
根据所述可用路径、所述归入后的节点所在的路径及所述每个路径的预设时延值,获得所有节点中所述归入后的节点以外剩余节点分别与所述第一预约路径请求的源节点的时延值为,所有节点中所述归入后的节点以外剩余节点,分别与所述第一预约路径请求的源节点的第二距离。
较佳的,所述确定与所述第一预约路径请求对应的匹配路径之后,所述路径分配方法还包括:
删除网络中除所述匹配路径以外的其余路径中,暂存的所述第一预约路径请求。
本发明实施例还提供了一种基于时间段预约带宽资源的路径分配装置,包括:
请求获取模块,用于获取用户的第一预约路径请求,所述第一预约路径请求至少携带有:所述第一预约路径请求的预约时间段、所述第一预约路径请求的预约时间段内的带宽需求量、源节点及目的节点,所述第一预约路径请求的预约时间段至少包括:预约开始时间及预约结束时间;
带宽信息确定模块,用于在所述第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息;
可用路径确定模块,用于根据所述每条路径的带宽信息,确定所述第一预约路径请求的可用路径;
匹配路径分配模块,用于根据所述可用路径,确定与所述第一预约路径请求对应的匹配路径,并分配所述匹配路径给所述用户,以使所述用户在所述第一预约路径请求的预约时间段内使用所述匹配路径的带宽资源。
较佳的,所述带宽信息确定模块,包括:
带宽需求量最大值确定子模块,用于确定每条路径的所述带宽信息中包含的带宽需求量最大值;
相应的,所述可用路径确定模块,具体用于:
确定满足所述带宽需求量最大值小于或等于,路径能够提供最大带宽资源量的带宽容量的路径为所述第一预约路径请求的可用路径。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量;
相应的,所述带宽需求量最大值确定子模块,具体用于:
在所述路径含有所述第二预约路径请求,且所述第二预约路径请求的预约时间段与所述第一预约路径请求的预约时间段至少部分时间段相同时,确定所述第二预约路径请求的带宽需求量与所述第一预约路径请求的带宽需求量之和;
确定所述和,作为所述带宽需求量最大值。
较佳的,所述装置还包括:
记录模块,用于记录所述第一预约路径请求中,与所述第二预约路径请求除所述相同时间段以外的剩余时间段内的带宽需求量为第一预约路径请求的未处理部分。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量;
相应的,所述带宽需求量最大值确定子模块,具体用于:
在所述路径含有所述第二预约路径请求,且所述第二预约路径请求的预约时间段与所述第一预约路径请求的预约时间段无相同时间段时,确定所述第二预约路径请求的带宽需求量与所述第一预约路径请求的带宽需求量的最大值;
确定所述最大值作为所述带宽需求量最大值。
较佳的,所述带宽信息中还包含:所述第一预约路径请求的预约时间段内的带宽需求量及每条路径能够提供最大带宽资源量的带宽容量;
相应的,所述带宽需求量最大值确定子模块,具体用于:
在所述路径不含有所述第二预约路径请求时,确定所述第一预约路径请求的带宽需求量作为所述带宽需求量最大值。
较佳的,所述匹配路径分配模块,包括:
第一最小距离确定子模块,用于根据所述可用路径,获得所有节点与所述第一预约路径请求的源节点的第一距离,确定所述第一距离中的最小距离对应的节点;
第一归入后节点确定子模块,用于将所述第一距离中的最小距离对应的节点,归入最小距离节点的节点集中,并将所述第一距离中的最小距离对应的节点,作为归入后的节点;
第二最小距离确定子模块,用于根据所述可用路径及所述归入后的节点,确定所有节点中所述归入后的节点以外剩余节点,与所述第一预约路径请求的源节点的第二距离,确定所述第二距离中的最小距离对应的节点;
第二归入后节点确定子模块,用于将所述第二距离中的最小距离对应的节点,归入所述节点集中,并将所述第二距离中的最小距离对应的节点,作为归入后的节点;
匹配路径确定子模块,用于重复执行所述第二最小距离确定子模块、所述第二归入后节点确定子模块,直至将剩余节点中的所述目的节点,归入所述节点集中,按照归入所述节点集中的节点归入的顺序,根据所有归入后的节点,形成一与所述第一预约路径请求对应的匹配路径。
较佳的,所述第一最小距离确定子模块,具体用于:
根据所述可用路径及每个路径的预设时延值,获得所有节点中每个节点分别与所述第一预约路径请求的源节点的时延值,作为所有节点中每个节点分别与所述第一预约路径请求的源节点的第一距离;
相应的,所述第二最小距离确定子模块,具体用于:
根据所述可用路径、所述归入后的节点所在的路径及所述每个路径的预设时延值,获得所有节点中所述归入后的节点以外剩余节点分别与所述第一预约路径请求的源节点的时延值为,所有节点中所述归入后的节点以外剩余节点,分别与所述第一预约路径请求的源节点的第二距离。
较佳的,所述装置还包括:
删除模块,用于删除网络中除所述匹配路径以外的其余路径中,暂存的所述第一预约路径请求。
由上述的技术方案可见,本发明实施例提供的一种基于时间段预约带宽资源的路径分配方法及装置,通过将获取的用户的有预约时间段内带宽需求的第一预约路径请求,暂存至网络中的多个路径之后,确定每条路径的带宽信息。并根据每条路径的带宽信息,确定第一预约路径请求的可用路径,进而确定与第一预约路径请求对应的匹配路径,并分配给用户,以使用户在预约时间段内使用匹配路径的带宽资源。本发明实施例通过对网络中多个路径进行判断,获得预约路径请求对应的多个可用路径,并在多个可用路径中确定一个匹配路径给用户,以满足用户在预约时间段内使用带宽资源的路径要求。应用本发明实施例能够合理分配网络资源,提高用户服务质量。当然,实施本发明的任一产品或方法必不一定需要同时达到以上所述的所有优点。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
图1为本发明实施例的基于时间段预约带宽资源的路径分配方法的一种流程图;
图2为本发明实施例的基于时间段预约带宽资源的路径分配方法的另一种流程图;
图3为本发明实施例的网络路径示意图;
图4为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况一的第一预约路径请求在先的示意图;
图5为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况一的第二预约路径请求在先的示意图;
图6为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况二的示意图;
图7为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况三的示意图;
图8为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况四的示意图;
图9为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况五的示意图;
图10为本发明实施例的确定可用路径的流程图;
图11为本发明实施例的基于时间段预约带宽资源的路径分配装置的结构示意图。
具体实施方式
下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例,都属于本发明保护的范围。
本发明实施例公开了一种基于时间段预约带宽资源的路径分配方法及装置,应用于SDN(Software Defined Networking,软件定义网络)中。
针对传统的TCP/IP体系无法满足多媒体应用和各种用户对网络传输质量的不同要求。导致用户服务质量不高,网络资源配置不够合理的问题,SDN技术应运而生并得到了迅速发展。本发明是基于SDN统一控制的思想,在SDN控制器中进行设计实现的方法。本发明对用户基于时间段预约带宽资源的预约路径请求,在网络中多个路径中寻求一匹配路径分配给用户,以使用户在预约的时间段内使用该匹配路径的带宽资源。本发明可广泛应用于有时间计划性的专用网尤其是军事网。能够满足用户预约时间段内使用带宽资源的需求,并且将时延最小的路径作为匹配路径分配给用户,能够合理配置网络资源、提高用户服务质量、提高网络资源的利用率。
参见图1,图1为本发明实施例的基于时间段预约带宽资源的路径分配方法的一种流程图,包括如下步骤:
步骤101,获取用户的第一预约路径请求,第一预约路径请求至少携带有:第一预约路径请求的预约时间段、第一预约路径请求的预约时间段内的带宽需求量、源节点及目的节点,第一预约路径请求的预约时间段至少包括:预约开始时间及预约结束时间。
第一预约路径请求为:SDN网络中用户发送的预约路径的请求。可以有多个用户发送第一预约路径请求,一个用户也可以发送多个第一预约路径请求,这都是合理的。
需要说明的是,若获取到多个第一预约路径请求,本发明根据第一预约路径请求的发送时间的先后顺序,依次处理多个第一预约路径请求。
第一预约路径请求的预约时间段为:第一预约路径请求中用户需要使用带宽资源的时间段,该时间段是用户发送第一预约路径请求的时间之后的一个时间段。该时间段可以以小时或者天为单位计。预约时间段至少包括预约开始时间及预约结束时间。
第一预约路径请求的预约时间段内的带宽需求量为:第一预约路径请求中用户在预约时间段内需要使用的带宽资源的带宽值。
源节点为第一预约路径请求中用户预约的路径起始地址。
目的节点为第一预约路径请求中用户预约的路径目的地址。
需要说明的是,用户所在的SDN网络中存在多个节点,由多个节点构成多个路径。节点为多种网络设备,包括计算机、交换机。由源节点至目的节点之间存在多条路径,本方案是在多条路径中,确定并分配一条满足用户的第一预约路径请求的匹配路径。
步骤102,在第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息。
将第一预约路径请求暂存至网络中的多个路径之后,暂存有第一预约路径请求的路径中除了有暂存的第一预约路径请求之外,还可能含有之前已预约成功的路径请求,本发明根据路径中的所有预约路径请求获得路径的带宽信息。
带宽信息为路径中的带宽占用情况、带宽需求情况及路径的属性信息。
步骤103,根据每条路径的带宽信息,确定第一预约路径请求的可用路径。
根据每条路径的带宽信息,确定带宽信息满足预设条件的路径为可用路径。其中,可用路径的路径起始地址是源节点,路径目的地址是目的节点。
其中,预设条件可以根据网络情况及人工需求设定,如:判断路径是否处于正常工作状态、判断路径中的预约路径请求的数量是否超过预设值及判断路径的带宽需求的最大值是否超过路径能够提供最大带宽资源量的带宽容量。
通过确定可用路径,能够排除多个不满足预设条件的非可用路径,避免出现将第一预约路径请求分配给非可用路径产生的无法传输现象或路径拥塞现象。
步骤104,根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在第一预约路径请求的预约时间段内使用匹配路径的带宽资源。
在多个可用路径中,确定一与第一预约路径请求对应的匹配路径,能够合理分配网络资源,将匹配路径分配给路径分配请求对应的用户,使用户在预约时间段内使用带宽资源的要求得以满足,能够提高用户服务质量。
可见,本发明实施例提供的方法,通过将获取的用户的有预约时间段内带宽需求的第一预约路径请求,暂存至网络中的多个路径之后,确定每条路径的带宽信息。并根据每条路径的带宽信息,确定第一预约路径请求的可用路径,进而确定与第一预约路径请求对应的匹配路径,并分配给用户,以使用户在预约时间段内使用匹配路径的带宽资源。本发明实施例通过对网络中多个路径进行判断,获得预约路径请求对应的多个可用路径,并在多个可用路径中确定一个匹配路径给用户,以满足用户在预约时间段内使用带宽资源的路径要求。应用本发明实施例能够合理分配网络资源,提高用户服务质量。
在图1的基础上,作为一种优选的实施例,参见图2,图2为本发明实施例的基于时间段预约带宽资源的路径分配方法的另一种流程图。包括如下步骤:
步骤211,获取用户的第一预约路径请求,第一预约路径请求至少携带有:第一预约路径请求的预约时间段、第一预约路径请求的预约时间段内的带宽需求量、源节点及目的节点,第一预约路径请求的预约时间段至少包括:预约开始时间及预约结束时间。
第一预约路径请求、第一预约路径请求的预约时间段、第一预约路径请求的预约时间段内的带宽需求量、源节点、及目的节点不再赘述。
本发明方案中将网络抽象为有权无向图,参见图3,图3为本发明实施例的网络路径示意图。圆点为节点,圆点旁边的字母为节点名称,节点之间的连线为路径。参见图3,a为节点0,b为节点1,c为节点2,d为节点3。由节点0、节点1、节点2及节点3构成多条路径。每条路径有预设带宽容量及预设时延值。用户的第一预约路径请求抽象为P(源节点,目的节点,预约时间段内的带宽需求R),表示用户要求分配一条从源节点至目的节点,并满足预约时间段内的带宽需求R的路径。其中R=(预约开始时间,预约结束时间,预约时间段内的带宽需求量),表示用户在预约开始时间至预约结束时间这一时间段内的带宽需求量。如R=(1,2,3)表示用户在预约开始时间1至预约结束时间2这一时间段内的带宽需求量为3。
步骤212,在第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息中包含的带宽需求量最大值。
根据路径中是否含有其他已预约成功的第二预约路径请求及第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的关系,确定每条路径的带宽信息中包含的带宽需求量最大值,具体包括:
第一种情况:带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量。
相应的,在路径含有第二预约路径请求,且第二预约路径请求的预约时间段与第一预约路径请求的预约时间段至少部分时间段相同时,确定第二预约路径请求的带宽需求量与第一预约路径请求的带宽需求量之和。
确定和,作为带宽需求量最大值。
确定每条路径的带宽信息中包含的带宽需求量最大值之后,本发明方法还包括:记录第一预约路径请求中,与第二预约路径请求除相同时间段以外的剩余时间段内的带宽需求量为第一预约路径请求的未处理部分。
第二种情况:带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量。
相应的,在路径含有第二预约路径请求,且第二预约路径请求的预约时间段与第一预约路径请求的预约时间段无相同时间段时,确定第二预约路径请求的带宽需求量与第一预约路径请求的带宽需求量的最大值。
确定最大值作为带宽需求量最大值。
第三种情况:带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量及每条路径能够提供最大带宽资源量的带宽容量。
相应的,在路径不含有第二预约路径请求时,确定第一预约路径请求的带宽需求量作为带宽需求量最大值。
根据以上所述,对确定每条路径的带宽信息进行详细介绍。针对第三种情况,路径的带宽信息中的带宽占用情况、带宽需求量最大值为第一预约路径请求的预约时间段内的带宽需求量。针对第一种情况和第二种情况,本发明实施例提供了第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的五种比较情况,通过五种比较情况能够确定出第一种情况和第二种情况下的路径的带宽信息中的带宽占用情况及带宽需求量最大值。比较情况一至比较情况五的示意图分别参见图4至图9。在图4至图9中,原请求为第二预约路径请求,原请求表示为R0(t3,t4,w2),新请求为第一预约路径请求,新请求表示为R1(t1,t2,w1)。w1为新请求的带宽需求量,w2为原请求的带宽需求量。t1为新请求的预约开始时间,t2为新请求的预约结束时间,t3为原请求的预约开始时间,t4为原请求的预约结束时间,t为第一预约路径请求的预约时间段与第二预约路径请求的预约时间段的相同时间段。以下详细说明第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的五种比较情况:
比较情况一,第二预约路径请求的预约时间段与第一预约路径请求的预约时间段无相同时间段的情况。参见图4,图4为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况一的第一预约路径请求在先的示意图。具体表示为:t2≤t3。
参见图5,图5为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况一的第二预约路径请求在先的示意图。具体表示为:t4≤t1。
在图4或者图5的比较情况一下,路径的带宽信息包括:
带宽占用情况为R0(t3,t4,w2)及R1(t1,t2,w1)。
带宽需求量最大值为w1和w2中的最大值。
比较情况二,第二预约路径请求的预约时间段与第一预约路径请求的预约时间段部分时间段相同,第一预约路径请求的预约开始时间先于第二预约路径请求的预约开始时间,第二预约路径请求的预约时间段与第一预约路径请求的预约时间段无相互包含的情况。参见图6,图6为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况二的示意图。具体表示为:t1<t3且t3<t2<t4。
在比较情况二下,路径的带宽信息包括:
带宽占用情况为:R1(t3,t2,w1+w2),R0(t2,t4,w2),记录第一预约路径请求的未处理部分为R1(t1,t3,w1)。
带宽需求量最大值为w1+w2。
比较情况三,第二预约路径请求的预约时间段与第一预约路径请求的预约时间段部分时间段相同,第二预约路径请求的预约开始时间先于第一预约路径请求的预约开始时间,第二预约路径请求的预约时间段与第一预约路径请求的预约时间段无相互包含的情况。参见图7,图7为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况三的示意图。具体表示为:t4<t2且t3<t1<t4。
在比较情况三下,路径的带宽信息包括:
带宽占用情况为:R0(t3,t1,w2),R1(t1,t4,w1+w2),记录第一预约路径请求的未处理部分为R1(t4,t2,w1)。
带宽需求量最大值为w1+w2。
比较情况四,第二预约路径请求的预约时间段包含第一预约路径请求的预约时间段的情况。参见图8,图8为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况四的示意图。具体表示为:t3≤t1<t4且t3<t2≤t4。
在比较情况四下,路径的带宽信息包括:
带宽占用情况为:R0(t3,t1,w2),R1(t1,t2,w1+w2),R0(t2,t4,w2)。
带宽需求量最大值为w1+w2。
比较情况五,第一预约路径请求的预约时间段包含第二预约路径请求的预约时间段的情况。参见图9,图9为本发明实施例的第二预约路径请求的预约时间段与第一预约路径请求的预约时间段的比较情况五的示意图。具体表示为:t1≤t3<t2且t1<t4<t2或者t1<t3<t2且t1<t4≤t2。
在比较情况五下,路径的带宽信息包括:
带宽占用情况为:R1(t3,t4,w1+w2),记录第一预约路径请求的未处理部分为R1(t1,t3,w1)、R1(t4,t2,w1)。
带宽需求量最大值为w1+w2。
步骤213,确定满足带宽需求量最大值小于或等于,路径能够提供最大带宽资源量的带宽容量的路径为第一预约路径请求的可用路径。
通过步骤211至步骤213,可以确定第一预约路径请求的可用路径。确定一路径是否为可用路径的详细的流程图参见图9,图9为本发明实施例的确定可用路径的流程图。以下对确定可用路径的流程图的步骤进行详细说明:
步骤211,获取用户的第一预约路径请求。
同图2所示的步骤211,不再赘述。
步骤2111,将第一预约路径请求暂存至网络中的多个路径。
步骤2112,判断暂存之前路径是否为空。
该步骤是判断暂存有第一预约路径请求的路径在暂存第一预约路径请求之前是否为空路径。空路径为不含有预约路径请求的路径。
步骤2113,当暂存有第一预约路径请求的路径在暂存第一预约路径请求之前为空路径时,确定该路径的带宽需求量最大值为第一预约路径请求的带宽需求量。然后执行步骤2122。
步骤2114,当暂存有第一预约路径请求的路径在暂存第一预约路径请求之前不为空路径时,将该路径中的预约路径请求按预约开始时间升序排序。
当暂存有第一预约路径请求的路径在暂存第一预约路径请求之前不为空路径时,表示该路径含有其他已预约成功的第二预约路径请求。将该路径中的所有预约路径请求按照预约开始时间从先至后进行升序排序,以进行步骤2115的各预约路径请求的预约时间段的比较。
步骤2115,参考五种比较情况,比较第二预约路径请求与第一预约路径请求的预约时间段。
参考图4至图9所示的五种比较情况,对该路径中的第二预约路径请求与第一预约路径请求的预约时间段进行比较。
步骤2116,判断是否遍历所有第二预约路径请求,如果否则继续执行步骤2115,如果是则执行步骤212。
步骤212,确定路径的带宽需求量最大值。
将该路径中的所有预约路径请求全部比较完毕后,可以获得该路径的带宽信息,带宽信息包括带宽占用情况、带宽需求量最大值。该步骤同图2所示的步骤212。
步骤2121,记录第一预约路径请求的未处理部分。
针对比较情况二、比较情况三及比较情况五需要记录第一预约路径请求的未处理部分。其余情况则不存在第一预约路径请求的未处理部分。
步骤2122,判断带宽需求量是否大于带宽容量。
步骤2131,当该路径的带宽需求量小于或等于带宽容量,该路径为可用路径。
步骤2132,当该路径的带宽需求量大于带宽容量,该路径为非可用路径。
步骤2131及步骤2132同图2所示的步骤213,为步骤213判断可用路径的两种不同情况。
在步骤213确定可用路径之后,本发明实施例的匹配路径确定及分配步骤如图2的步骤214所示:
步骤214,根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在第一预约路径请求的预约时间段内使用匹配路径的带宽资源。
其中,根据可用路径,确定与第一预约路径请求对应的匹配路径具体包括以下步骤:
步骤A,根据所述可用路径及每个路径的预设时延值,获得所有节点中每个节点分别与所述第一预约路径请求的源节点的时延值,作为所有节点中每个节点分别与所述第一预约路径请求的源节点的第一距离。
该步骤是在所有节点中查找与源节点距离最近的节点。节点与源节点的距离是以路径的时延值体现的。
步骤B,将第一距离中的最小距离对应的节点,归入最小距离节点的节点集中,并将第一距离中的最小距离对应的节点,作为归入后的节点。
该步骤是将步骤A查找到的与源节点距离最近的节点归入节点集。
步骤C,根据可用路径、归入后的节点所在的路径及每个路径的预设时延值,获得所有节点中归入后的节点以外剩余节点分别与第一预约路径请求的源节点的时延值为,所有节点中归入后的节点以外剩余节点,分别与第一预约路径请求的源节点的第二距离,确定第二距离中的最小距离对应的节点。
该步骤是更新其余节点与源节点的距离,并再次查找其余节点与源节点距离最近的节点。
步骤D,将第二距离中的最小距离对应的节点,归入节点集中,并将第二距离中的最小距离对应的节点,作为归入后的节点。
该步骤是将步骤C查找到的与源节点距离最近的节点归入节点集。
重复执行步骤C、步骤D,直至将剩余节点中的目的节点,归入节点集中,按照归入节点集中的节点归入的顺序,根据所有归入后的节点,形成一与第一预约路径请求对应的匹配路径。
确定与第一预约路径请求对应的匹配路径之后,更新匹配路径的带宽占用情况。并删除网络中除匹配路径以外的其余路径中暂存的第一预约路径请求。
需要说明的是,重复执行步骤C、步骤D,直至没有新的节点能够作为归入后的节点归入节点集,还未将目的节点归入节点集,则该网络不能满足用户的第一预约路径请求,拒绝该第一预约路径请求。
通过步骤211至步骤214,本发明获取用户的预约路径请求,确定多个可用路径,在多个可用路径中,确定一个时延值最小的路径为匹配路径,并将匹配路径分配给用户。实现了用户预约服务的功能,一旦用户预约服务成功,本发明方案可保证在预约时间段内用户可占有相应的带宽资源。能够合理分配网络资源,提高用户服务质量。
传统方案中不同虚拟网络的资源利用率是不同的,导致部分虚拟网络带宽资源不足,部分虚拟网络有处于空闲状态,网络整体的利用率低。本发明采用集中控制思想,控制器可掌控全局的资源分配情况,当时延值最小的路径不能满足用户需求时,控制器会选取次优路径,也就是时延值次小的路径分配给用户。这样尽力避免了时延值小的路径上产生拥塞,而其他时延值较大的路径出现空闲的情况,使得整个网络的利用率提高。
以下举例说明本发明实施例的基于时间段预约带宽资源的路径分配方法。如图3所示,图3为本发明实施例的网络路径示意图。网络中有4个节点,序号分别为0、1、2、3,参见表1,表1为路径的预设带宽容量及预设时延值,表1如下:
表1
以下以顺序获得的多个第一预约路径请求为例,说明本发明实施例的基于时间段预约带宽资源的路径分配方法。
获取到第一个第一预约路径请求为P=(0,1,R1),其中R1=(1,2,2)。也就是用户要求分配一条从节点0到节点1并满足预约时间段内的带宽需求R1的路径。其中R1=(1,2,2),表示用户的预约开始时间为1,预约结束时间为2,这段时间内的带宽需求为2。以下分两步对本发明实施例的基于时间段预约带宽资源的路径分配方法进行说明:
第一步,确定第一预约路径请求P的可用路径。
将预约时间段内的带宽需求R1暂存入网络中的路径[0,1]、路径[0,2]、路径[2,3]、路径[1,3],因为初始状态下所有路径为空,确定每个路径的带宽需求最大值为第一预约路径请求的带宽需求2。将带宽需求最大值2与各路径的带宽容量比较,比较结果见表2,表2为第一个第一预约路径请求的各路径带宽需求值与带宽容量的比较结果。表2如下:
表2
由表2的比较结果确定除路径[1,3]外其余路径均为可用路径。
第二步,确定第一预约路径请求P的匹配路径。
首先,查找所有节点中与源节点距离最小的节点,由于源节点是节点0,先将节点0归入节点集。节点0作为归入后的节点。
其次,更新节点0以外的剩余节点与源节点的距离。将节点之间的距离用di,j表示,其中i,j为节点序号,i,j∈(0,1,2,3)。节点之间的距离以节点之间构成的路径的时延值体现。由表1可知,节点1与源节点0的距离d1,0=2、节点2与源节点0的距离d2,0=3、节点3与源节点0的距离d3,0=∞(由于节点3和节点0为非相邻节点,且中间无转发节点,节点3与节点0的时延值为∞)。
再次,查找节点0以外的剩余节点与源节点的距离最小的节点,根据上面的判断,d1,0最小,将节点1归入节点集,节点1作为归入后的节点。因为节点1为目的节点,确定匹配路径为由节点集中的节点0、节点1依次构成的路径[0,1]。
确定匹配路径之后,更新匹配路径[0,1]的带宽占用情况为(1,2,2)。如表3所示。表3为第一个第一预约路径请求的匹配路径带宽占用情况表。表3中第一行为路径名,第二行为匹配路径的带宽占用情况,(1,2,2)表示在路径[0,1]上,从1到2这段时间内占用的带宽值为2。同时删除路径[0,1]以外的其余路径暂存的预约时间段内的带宽需求R1。表3如下:
表3
之后获取到第二个第一预约路径请求为P=(1,2,R2),其中R2=(1,4,3)。也就是用户要求分配一条从节点1到节点2并满足预约时间段内的带宽需求R2的路径。其中R2=(1,4,3),表示用户的预约开始时间为1,预约结束时间为4,这段时间内的带宽需求为3。以下分两步对本发明实施例的基于时间段预约带宽资源的路径分配方法进行说明:
第一步,确定第一预约路径请求P的可用路径。
首先将预约时间段内的带宽需求R2暂存入网络中的路径[0,1]、路径[0,2]、路径[2,3]、路径[1,3]。路径[0,1]存在已预约的带宽需求(1,2,2),其余路径均为空路径。对路径[0,1],参考图9的比较情况五,确定路径[0,1]的带宽需求最大值为2+3=5,其余路径的带宽需求最大值为第一预约路径请求的带宽需求3。将各路径的带宽需求最大值与各路径的带宽容量比较,比较结果见表4,表4为第二个第一预约路径请求的各路径带宽需求值与带宽容量的比较结果。表4如下:
表4
由表4的比较结果确定除路径[1,3]外其余路径均为可用路径。
第二步,确定第一预约路径请求P的匹配路径。
首先,查找所有节点中与源节点距离最小的节点。由于源节点是节点1,先将节点1归入节点集。节点1作为归入后的节点。
其次,更新节点1以外的剩余节点与源节点的距离。根据各路径的预设时延值可知:d0,1=2、d2,1=∞(节点2与节点1不相邻且作为中间节点的节点0还未作为转发节点,节点2与节点1的时延为∞)、d3,1=∞(节点3与节点1之间的路径[1,3]不可用,路径时延值为∞),d0,1最小,所以将节点0归入节点集。节点0作为归入后的节点。
再次,更新节点1、节点0以外的剩余节点与源节点的距离,通过节点0的转发,节点2到节点1的时延缩短为2+3=5,所以d2,1=5,因为d3,1=∞,d2,1最小,将节点2归入节点集,节点2作为归入后的节点。因为节点2为目的节点,确定匹配路径为由节点集中的节点1、节点0、节点2依次构成的路径[1,0]、[0,2]。
确定匹配路径之后,更新匹配路径[1,0]、[0,2]的带宽占用情况,见表5,表5为第二个第一预约路径请求的匹配路径带宽占用情况表。路径[1,0]中的(1,2,5)为更新的带宽占用情况,(2,4,3)为记录的第一预约路径请求的未处理部分。路径[0,2]中的(1,4,3)为路径[0,2]存储的第一预约路径请求的预约时间段内的带宽需求R2。同时删除路径[1,0]、[0,2]以外的其余路径暂存的预约时间段内的带宽需求R2。表5如下:
表5
之后获取到第三个第一预约路径请求为P=(1,2,R3),其中R2=(2,3,6)。也就是用户要求分配一条从节点1到节点2并满足预约时间段内的带宽需求R3的路径。其中R3=(2,3,6),表示用户的预约开始时间为2,预约结束时间为3,这段时间内的带宽需求为6。以下分两步对本发明实施例的基于时间段预约带宽资源的路径分配方法进行说明:
第一步,确定第一预约路径请求P的可用路径。
首先将预约时间段内的带宽需求R2暂存入网络中的路径[0,1]、路径[0,2]、路径[2,3]、路径[1,3]。
路径[1,0]存在已预约的带宽需求(1,2,5)及(2,4,3),参考比较情况一及比较情况四,确定路径[1,0]的带宽需求最大值为6+3=9。
路径[0,2]存在已预约的带宽需求(1,4,3),参考比较情况四,确定路径[0,2]的带宽需求最大值为6+3=9。
路径[2,3]为空路径,带宽需求最大值为第一预约路径请求的带宽需求6。
路径[1,3]为空路径,带宽需求最大值为第一预约路径请求的带宽需求6。
将各路径带宽需求最大值与各路径的带宽容量比较,比较结果见表6,表6为例3的各路径带宽需求值与带宽容量的比较结果。表6如下:
表6
由表6的比较结果确定无可用路径。
第二步,确定第一预约路径请求P的匹配路径。
将源节点1归入节点集,因为所有路径均不可用,所有节点与源节点的距离均为∞,没有最小距离的节点能够归入节点集,路径分配失败,拒绝用户的第一预约路径请求,不对路径的带宽占用情况进行更新。
可见,本发明实施例提供的方法,通过获取用户的有预约时间段内带宽需求的第一预约路径请求。在将第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息中包含的带宽需求量最大值。确定满足带宽需求量最大值小于或等于路径能够提供最大带宽资源量的带宽容量的路径为第一预约路径请求的可用路径。并根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在预约时间段内使用匹配路径的带宽资源。本发明实施例通过对网络中多个路径进行判断,获得预约路径请求对应的多个可用路径,并在多个可用路径中确定一个时延最小的匹配路径给用户,以满足用户在预约时间段内使用带宽资源的路径要求。应用本发明实施例能够合理分配网络资源,提高用户服务质量并提高网络资源利用率。
参见图11,本发明实施例的基于时间段预约带宽资源的路径分配装置的结构示意图。包括:
请求获取模块301,用于获取用户的第一预约路径请求,第一预约路径请求至少携带有:第一预约路径请求的预约时间段、第一预约路径请求的预约时间段内的带宽需求量、源节点及目的节点,第一预约路径请求的预约时间段至少包括:预约开始时间及预约结束时间。
带宽信息确定模块302,用于在第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息。
可用路径确定模块303,用于根据每条路径的带宽信息,确定第一预约路径请求的可用路径。
匹配路径分配模块304,用于根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在第一预约路径请求的预约时间段内使用匹配路径的带宽资源。
需要说明的是,本发明实施例的装置是应用上述基于时间段预约带宽资源的路径分配方法的装置,则上述应用基于时间段预约带宽资源的路径分配方法的所有实施例均适用于该装置,且均能达到相同或相似的有益效果。
可见,本发明实施例提供的装置,通过获取用户的有预约时间段内带宽需求的第一预约路径请求。在将第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息。并根据每条路径的带宽信息,确定第一预约路径请求的可用路径。并根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在预约时间段内使用匹配路径的带宽资源。本发明实施例通过对网络中多个路径进行判断,获得预约路径请求对应的多个可用路径,并在多个可用路径中确定一个匹配路径给用户,以满足用户在预约时间段内使用带宽资源的路径要求。应用本发明实施例能够合理分配网络资源,提高用户服务质量。
在图11的基础上,作为一种优选的实施例,带宽信息确定模块302,包括:
带宽需求量最大值确定子模块,用于确定每条路径的带宽信息中包含的带宽需求量最大值。
相应的,可用路径确定模块303,具体用于:
确定满足带宽需求量最大值小于或等于,路径能够提供最大带宽资源量的带宽容量的路径为第一预约路径请求的可用路径。
在图11的基础上,作为一种优选的实施例,带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量。
相应的,带宽需求量最大值确定子模块,具体用于:
在路径含有第二预约路径请求,且第二预约路径请求的预约时间段与第一预约路径请求的预约时间段至少部分时间段相同时,确定第二预约路径请求的带宽需求量与第一预约路径请求的带宽需求量之和。
确定和,作为带宽需求量最大值。
在图11的基础上,作为一种优选的实施例,本发明实施例的基于时间段预约带宽资源的路径分配装置还包括:
记录模块,用于记录第一预约路径请求中,与第二预约路径请求除相同时间段以外的剩余时间段内的带宽需求量为第一预约路径请求的未处理部分。
在图11的基础上,作为一种优选的实施例,带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量、每条路径能够提供最大带宽资源量的带宽容量,其他已预约成功的第二预约路径请求的预约时间段内的带宽需求量。
相应的,带宽需求量最大值确定子模块,具体用于:
在路径含有第二预约路径请求,且第二预约路径请求的预约时间段与第一预约路径请求的预约时间段无相同时间段时,确定第二预约路径请求的带宽需求量与第一预约路径请求的带宽需求量的最大值。
确定最大值作为带宽需求量最大值。
在图11的基础上,作为一种优选的实施例,带宽信息中还包含:第一预约路径请求的预约时间段内的带宽需求量及每条路径能够提供最大带宽资源量的带宽容量。
相应的,带宽需求量最大值确定子模块,具体用于:
在路径不含有第二预约路径请求时,确定第一预约路径请求的带宽需求量作为带宽需求量最大值。
在图11的基础上,作为一种优选的实施例,匹配路径分配模块304,包括:
第一最小距离确定子模块,用于根据可用路径,获得所有节点与第一预约路径请求的源节点的第一距离,确定第一距离中的最小距离对应的节点。
第一归入后节点确定子模块,用于将第一距离中的最小距离对应的节点,归入最小距离节点的节点集中,并将第一距离中的最小距离对应的节点,作为归入后的节点。
第二最小距离确定子模块,用于根据可用路径及归入后的节点,确定所有节点中归入后的节点以外剩余节点,与第一预约路径请求的源节点的第二距离,确定第二距离中的最小距离对应的节点;
第二归入后节点确定子模块,用于将第二距离中的最小距离对应的节点,归入节点集中,并将第二距离中的最小距离对应的节点,作为归入后的节点。
匹配路径确定子模块,用于重复执行第二最小距离确定子模块、第二归入后节点确定子模块,直至将剩余节点中的目的节点,归入节点集中,按照归入节点集中的节点归入的顺序,根据所有归入后的节点,形成一与第一预约路径请求对应的匹配路径。
在图11的基础上,作为一种优选的实施例,第一最小距离确定子模块,具体用于:
根据可用路径及每个路径的预设时延值,获得所有节点中每个节点分别与第一预约路径请求的源节点的时延值,作为所有节点中每个节点分别与第一预约路径请求的源节点的第一距离。
相应的,第二最小距离确定子模块,具体用于:
根据可用路径、归入后的节点所在的路径及每个路径的预设时延值,获得所有节点中归入后的节点以外剩余节点分别与第一预约路径请求的源节点的时延值为,所有节点中归入后的节点以外剩余节点,分别与第一预约路径请求的源节点的第二距离。
在图11的基础上,作为一种优选的实施例,本发明实施例的基于时间段预约带宽资源的路径分配装置还包括:
删除模块,用于删除网络中除匹配路径以外的其余路径中,暂存的第一预约路径请求。
可见,本发明实施例提供的装置,通过获取用户的有预约时间段内带宽需求的第一预约路径请求。在将第一预约路径请求暂存至网络中的多个路径之后,确定每条路径的带宽信息中包含的带宽需求量最大值。确定满足带宽需求量最大值小于或等于路径能够提供最大带宽资源量的带宽容量的路径为第一预约路径请求的可用路径。并根据可用路径,确定与第一预约路径请求对应的匹配路径,并分配匹配路径给用户,以使用户在预约时间段内使用匹配路径的带宽资源。本发明实施例通过对网络中多个路径进行判断,获得预约路径请求对应的多个可用路径,并在多个可用路径中确定一个时延最小的匹配路径给用户,以满足用户在预约时间段内使用带宽资源的路径要求。应用本发明实施例能够合理分配网络资源,提高用户服务质量并提高网络资源利用率。
需要说明的是,在本文中,诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来,而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且,术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含,从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素,而且还包括没有明确列出的其他要素,或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下,由语句“包括一个……”限定的要素,并不排除在包括要素的过程、方法、物品或者设备中还存在另外的相同要素。
本说明书中的各个实施例均采用相关的方式描述,各个实施例之间相同相似的部分互相参见即可,每个实施例重点说明的都是与其他实施例的不同之处。尤其,对于系统实施例而言,由于其基本相似于方法实施例,所以描述的比较简单,相关之处参见方法实施例的部分说明即可。
以上仅为本发明的较佳实施例而已,并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等,均包含在本发明的保护范围内。
机译: 一种基于路径质量和连接优先级的QoS优先级的DNS响应重分配方法
机译: 一种基于路径质量和连接优先级的QoS优先级的DNS响应重分配方法
机译: 一种用于制造在车辆中使用的牵引电池的压力装置,其具有可移动的压力模具,该压力模具将电池堆施加在两堆电池单元上,并且控制装置基于检测单元的信号来调节模具的行进路径。