技术领域technical field
本发明涉及网络领域，具体涉及一种基于内容覆盖和反馈机制的用户个性化优先级路由方法。The invention relates to the network field, in particular to a user personalized priority routing method based on content coverage and feedback mechanism.
背景技术Background technique
目前，在采集信息量巨大的网络系统中，如“上海轨道交通电力安全监控系统”中，采用基于现有的基于内容Pub/Sub系统架构，监控站点订阅的信息都将在事件发布后进入网络，进而传递到相应的订阅者。但是在信息量过大或者网络不稳定的时候，消息分发是很容易发生拥塞的，这时候所有堵塞消息将在中间节点上排队，以先来后到的顺序试图发往下一跳，然后该消息又可能在下一跳继续堵塞，更坏的情况可能拥塞过于严重直接造成事件丢失或拒传，这样的情况发生在用户特别敏感在意的消息上是难以容忍的。如，按照用户A意愿，一旦出现“电压>380伏”的事件，那么要第一时间通知他，否则可能会造成生命财产损失。按照上述传统基于内容Pub/Sub系统的拥塞情况，一旦有此类事件产生并且网络又发生堵塞，那么造成的不及时信息分发，不仅会直接降低系统的用户满意度，还有可能造成无法容忍或无法挽回的结果。因此，此类问题急需解决。At present, in the network system that collects a huge amount of information, such as the "Shanghai Rail Transit Power Safety Monitoring System", the existing content-based Pub/Sub system architecture is adopted, and the information subscribed by the monitoring site will enter the network after the event is released. , which in turn is delivered to the corresponding subscribers. However, when the amount of information is too large or the network is unstable, message distribution is prone to congestion. At this time, all blocked messages will be queued on the intermediate node, trying to be sent to the next hop in the order of first come, first come, and then the message may Congestion continues at the next hop. In a worse case, the congestion may be too severe and directly cause event loss or rejection. Such a situation is unacceptable for messages that are particularly sensitive to users. For example, according to user A's wishes, once an event of "voltage > 380 volts" occurs, he must be notified immediately, otherwise it may cause loss of life and property. According to the above-mentioned traditional content-based Pub/Sub system congestion, once such an event occurs and the network is congested again, the resulting untimely information distribution will not only directly reduce the user satisfaction of the system, but may also cause intolerable or irreversible results. Therefore, such problems urgently need to be solved.
内容覆盖路由算法是在过滤器的基础上针对订阅而提出的，它将解析路由消息得到的订阅条件与路由表中已存在的项进行内容匹配，若订阅条件覆盖路由表中项，则以之更新路由表，再予以转发；若订阅条件被路由表中项覆盖，则丢弃该消息，不再转发。该算法可以减小每个节点上的路由表大小，并相应减少每条消息在每个节点的处理时间。而且利用订阅中过滤条件之间的覆盖关系，在网络中传播的路由消息数量也会减少，从而节省网络带宽。著名的Siena、Rebeca、JEDI和Hermes等都采用了支持覆盖关系的路由。因而，可以利用内容覆盖路由算法提高如上述“上海轨道交通电力安全监控系统”等消息分发量巨大的系统的性能。The content coverage routing algorithm is proposed for subscription on the basis of filters. It will match the subscription conditions obtained by parsing the routing message with the existing items in the routing table. If the subscription conditions cover the items in the routing table, then use the Update the routing table, and then forward it; if the subscription condition is covered by the item in the routing table, discard the message and no longer forward it. This algorithm can reduce the routing table size on each node and correspondingly reduce the processing time of each message at each node. Moreover, by using the coverage relationship between the filter conditions in the subscription, the number of routing messages propagated in the network will also be reduced, thereby saving network bandwidth. The well-known Siena, Rebeca, JEDI, and Hermes all use routing that supports overlay relationships. Therefore, the content coverage routing algorithm can be used to improve the performance of a system with a huge amount of message distribution, such as the above-mentioned "Shanghai Rail Transit Power Safety Monitoring System".
优先级路由算法在因特网中早已有所应用，其目的主要是提供服务区分功能，也即在带宽等物理资源受限时使得高优先级消息能够更快地到达目的地。但传统网络中，优先级路由的实现基本是根据协议或端口号来对不同的应用程序消息进行区分；或者如JMS机制中，用户在边界节点进行标志，然后在中间网络进行简单传输，且不再涉及优先级调节之类的方法。然而，这些传统方法并不支持用户对消息优先级的个性化定制，在有限带宽等物理条件限制下，一旦发生网络拥塞，系统性能将受到明显影响，会降低用户满意度。因此，提出用户个性化路由算法是满足用户个性化需求和有限物理资源下的必然选择。The priority routing algorithm has been used in the Internet for a long time, and its main purpose is to provide service differentiation, that is, to enable high-priority messages to reach the destination faster when physical resources such as bandwidth are limited. But in the traditional network, the implementation of priority routing is basically to distinguish different application messages according to the protocol or port number; Then involves methods such as priority adjustment. However, these traditional methods do not support user customization of message priority. Under physical constraints such as limited bandwidth, once network congestion occurs, system performance will be significantly affected and user satisfaction will be reduced. Therefore, proposing a user-specific routing algorithm is an inevitable choice to meet the user's individual needs and limited physical resources.
发明内容Contents of the invention
本发明的目的在于提供一种基于内容覆盖和反馈机制的用户个性化优先级路由方法，以解决现有内容覆盖路由算法和优先级路由算法存在不支持用户对消息优先级进行个性化定制，消息传输受带宽限制大、容易发生网络拥塞等问题造成用户满意度低的技术问题。The purpose of the present invention is to provide a user personalized priority routing method based on content coverage and feedback mechanism, so as to solve the problem that the existing content coverage routing algorithm and priority routing algorithm do not support the user to personalize the message priority, and the message Transmission is subject to large bandwidth restrictions, prone to network congestion and other technical problems resulting in low user satisfaction.
为达到上述目的，本发明的目的在于提供一种基于内容覆盖和反馈机制的用户个性化优先级路由方法，包括以下步骤：In order to achieve the above object, the object of the present invention is to provide a user personalized priority routing method based on content coverage and feedback mechanism, comprising the following steps:
步骤一：根据最小生成树算法将网络拓扑生成无环结构；Step 1: Generate the network topology into an acyclic structure according to the minimum spanning tree algorithm;
步骤二：根据网络中节点数目，以节点出入度和树的深度为评判依据，采用选举算法选出若干个调整节点，各自负责网络中的部分订阅者；Step 2: According to the number of nodes in the network, based on the node in-out degree and the depth of the tree, several adjustment nodes are selected by the election algorithm, and each is responsible for some subscribers in the network;
步骤三：订阅者订阅消息，并对其设定个性化的优先级，具体分为高优先级、普通优先级和低优先级；Step 3: The subscriber subscribes to the message and sets a personalized priority for it, specifically divided into high priority, normal priority and low priority;
步骤四：订阅消息在中间代理网络中传输，每个代理节点存储一个订阅路由表，路由表每项都基于订阅者得出的优先级进行排序，接收到订阅消息后，根据路由表进行匹配，并通过合并覆盖路由算法决定订阅消息是否更新到路由表或进行舍弃处理；Step 4: The subscription message is transmitted in the intermediate proxy network. Each proxy node stores a subscription routing table. Each item in the routing table is sorted based on the priority obtained by the subscriber. After receiving the subscription message, it matches according to the routing table. And determine whether the subscription message is updated to the routing table or discarded by merging and covering the routing algorithm;
步骤五：发布者发布事件，事件到达每个代理节点，与其中的订阅路由表进行匹配，若匹配成功，从反向路径路由到感兴趣的订阅者。Step 5: The publisher publishes the event, and the event reaches each proxy node, and matches with the subscription routing table in it. If the match is successful, it is routed to interested subscribers from the reverse path.
步骤六：各个边界代理分别记录一段预设周期内其连接的订阅者接收到的消息信息；Step 6: Each border agent separately records the message information received by its connected subscribers within a preset period;
步骤七：当达到预设周期时间间隔，各个边界代理统计各订阅者的消息信息平均值，并将信息平均值发送到其所属的调整节点；Step 7: When the preset cycle time interval is reached, each border agent counts the average value of the message information of each subscriber, and sends the average value of the information to the adjustment node to which it belongs;
步骤八：各调整节点接收到所有其负责的订阅者消息后，依据各平均值、流量和各订阅者权重进行调整，调整每个订阅者所对应的高范围优先级、普通范围优先级的调整值，并将不为0的调整值返回给各订阅者所属边界代理；Step 8: After each adjustment node receives all the subscriber messages it is responsible for, it adjusts according to the average value, traffic and the weight of each subscriber, and adjusts the adjustment of the high-range priority and normal-range priority corresponding to each subscriber value, and return the adjustment value that is not 0 to the boundary agent to which each subscriber belongs;
步骤九：各边界代理收到步骤八发送的消息后，根据不同等级优先级调节本地路由表相应订阅的优先级，并将经过调整的订阅重新洪泛到网络中。Step 9: After receiving the message sent in step 8, each border agent adjusts the priority of the corresponding subscription in the local routing table according to the priority of different levels, and re-floods the adjusted subscription to the network.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤三中的订阅发送过程采用洪泛算法完成。According to the user personalized priority routing method based on the content coverage and feedback mechanism described in the preferred embodiment of the present invention, the subscription sending process in step 3 is completed using a flooding algorithm.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤二还包括：根据网络大小情况，对调整节点进行分级设置，具体为：设置一级调整节点和二级调整节点，其中，一级调整节点收集一块区域内各订阅者发送的反馈消息，二级调整节点收集一级调整节点发送的反馈消息进行全局公平性调整。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, step 2 further includes: according to the size of the network, setting adjustment nodes hierarchically, specifically: setting a first-level adjustment node and second-level adjustment nodes, wherein the first-level adjustment node collects the feedback messages sent by subscribers in an area, and the second-level adjustment node collects the feedback messages sent by the first-level adjustment nodes for global fairness adjustment.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤二和步骤三之间还包括：指定不同订阅者的优先级权重，根据权重决定一个节点订阅的不同优先级的消息在网络中的传输质量；According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, between step 2 and step 3 also includes: specifying the priority weights of different subscribers, and deciding a node to subscribe to according to the weight The transmission quality of messages with different priorities in the network;
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤四中，满足不同订阅者的有着合并覆盖关系的订阅在共同路径搭载共同路由。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, in step 4, the subscriptions that satisfy different subscribers and have a combined coverage relationship are equipped with a common route on a common path.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤七至步骤九为周期性过程，步骤七中各个边界代理在每次统计信息平均值并发送信息平均值给调整节点后自动清零。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, steps 7 to 9 are periodic processes, and in step 7, each border agent averages the statistical information and sends The average value of information is automatically cleared to the adjustment node.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤五中发布者发布的事件是没有优先级的，当其到达边界代理后，得到初始优先级，且优先级在每一中间节点上根据订阅路由表中下一跳的订阅优先级进行更新。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, the event published by the publisher in step 5 has no priority, and when it reaches the border agent, the initial priority is obtained , and the priority is updated on each intermediate node according to the subscription priority of the next hop in the subscription routing table.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤六中的消息信息具体包括：总优先级、总队列等待时间、总延迟、总流量和消息数目。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, the message information in step 6 specifically includes: total priority, total queue waiting time, total delay, total traffic and message number.
依照本发明较佳实施例所述的基于内容覆盖和反馈机制的用户个性化优先级路由方法，步骤8中对每个订阅者的优先级范围进行调整遵循以下原则：各优先级订阅不可以降级或越级到其他优先级范围。According to the user personalized priority routing method based on content coverage and feedback mechanism described in the preferred embodiment of the present invention, the adjustment of the priority range of each subscriber in step 8 follows the following principle: each priority subscription cannot be downgraded Or leapfrog to other priority ranges.
综合以上，可以看出，本发明的基于内容覆盖和反馈机制的用户个性化优先级路由方法，在发布订阅系统中首次引入了个性化优先级路由，并且可以对用户设置不同权重进行服务区分，大大增加了发布订阅系统的功能性和灵活性，可以以有限的资源更好地满足不同的用户需求。另外，本发明是构建在生成树算法生成的无环网络拓扑上的，还结合了基于内容覆盖的路由算法，因此有效地减少了消息在系统中冗余发送的情况。而且，为了避免用户在个性化订阅过程中过于“贪婪”地设置高优先级订阅，本发明还提供了一系列的公平性保证措施，确保个性化优先级订阅和公平性并存。具体地，可以根据网络规模和信息量大小，选择不同的调整节点数目、层级反馈结构或者分布式通信。因此，与现有技术相比，本发明首次提出了个性化优先级订阅，改进了系统功能，并且允许用户和订阅进行优先级双区分，具有高效地传送关键信息，大大减少了冗余消息发送量，且兼顾公平性的优点。Based on the above, it can be seen that the user personalized priority routing method based on content coverage and feedback mechanism of the present invention introduces personalized priority routing in the publish and subscribe system for the first time, and can set different weights for users to differentiate services. It greatly increases the functionality and flexibility of the publish-subscribe system, and can better meet different user needs with limited resources. In addition, the present invention is built on the acyclic network topology generated by the spanning tree algorithm, and also combines the routing algorithm based on content coverage, thus effectively reducing the redundant sending of messages in the system. Moreover, in order to prevent users from setting high-priority subscription too "greedily" during the personalized subscription process, the present invention also provides a series of fairness guarantee measures to ensure the coexistence of personalized priority subscription and fairness. Specifically, different numbers of adjustment nodes, hierarchical feedback structures, or distributed communications can be selected according to the network scale and the amount of information. Therefore, compared with the prior art, the present invention proposes personalized priority subscription for the first time, improves system functions, and allows users and subscriptions to be differentiated by priority, has the ability to efficiently transmit key information, and greatly reduces redundant message sending quantity, while taking into account the advantages of fairness.
附图说明Description of drawings
图1为本发明基于内容覆盖和反馈机制的用户订阅双区分的个性化优先级路由算法流程原理图；Fig. 1 is the schematic flow diagram of the personalized priority routing algorithm based on the content coverage and feedback mechanism of the present invention for user subscription dual distinction;
图2为应用本发明基于内容覆盖和反馈机制的用户订阅双区分的个性化优先级路由算法的网络系统结构图。Fig. 2 is a network system structure diagram applying the personalized priority routing algorithm based on the content coverage and feedback mechanism of the present invention for user subscription dual differentiation.
具体实施方式Detailed ways
以下结合附图，具体说明本发明。The present invention will be described in detail below in conjunction with the accompanying drawings.
本发明方法实现了在传统发布订阅系统中加入个性化订阅优先级区分、用户权重(权重和优先级是同等概念)区分、基于反馈机制的公平性保证等功能。发布订阅系统中有三个角色：订阅者、发布者和中间代理。其中订阅者发布订阅、发布者发布事件、中间代理进行匹配转发；另外值得注意的是，在公平性保证机制中，中间代理中的特殊角色有边界节点、一级调整节点和二级调整节点(看网络大小，网络过小则一级调整节点即可，就不需二级调整节点了；若网络很大，那么有可能需要一级、二级、三级调整节点，总之这是一个层级的局部全局共同调节的反馈机制。可能没有二级调整节点或者有三级调整节点)。在本发明方法中，连接有订阅者的边界节点将承担起监控订阅者行为的责任，主要周期性地记录订阅者接收到的事件的各种属性，然后进行层层反馈、全网调节。The method of the invention realizes functions such as adding individualized subscription priority distinction, user weight (weight and priority are equivalent concepts) distinction, fairness guarantee based on feedback mechanism, and the like to the traditional publish and subscribe system. There are three roles in a publish-subscribe system: subscriber, publisher, and intermediate broker. Among them, the subscriber publishes and subscribes, the publisher publishes events, and the intermediate agent performs matching and forwarding; it is also worth noting that in the fairness guarantee mechanism, the special roles of the intermediate agent include boundary nodes, first-level adjustment nodes and second-level adjustment nodes ( Look at the size of the network. If the network is too small, you can adjust the nodes at the first level, and you don’t need the second-level adjustment nodes; if the network is large, you may need to adjust the nodes at the first, second, and third levels. In short, this is a level Feedback mechanism for local-global co-regulation. There may be no second-level adjustment nodes or there may be third-level adjustment nodes). In the method of the present invention, the border nodes connected to the subscribers will assume the responsibility of monitoring the behavior of the subscribers, mainly periodically recording various attributes of the events received by the subscribers, and then perform layer-by-layer feedback and network-wide adjustments.
请参阅图1，一种基于内容覆盖和反馈机制的用户个性化优先级路由方法，包括以下步骤：Please refer to Figure 1, a user personalized priority routing method based on content coverage and feedback mechanism, including the following steps:
S11：根据最小生成树算法将网络拓扑生成无环结构。S11: Generate the network topology into an acyclic structure according to the minimum spanning tree algorithm.
S12：根据网络中节点数目，以节点出入度和树的深度为评判依据，采用选举算法选出若干个调整节点，各自负责网络中的部分订阅者。S12: According to the number of nodes in the network, based on the node in-out degree and the depth of the tree, several adjustment nodes are selected by the election algorithm, and each is responsible for some subscribers in the network.
根据网络大小，调整节点可以有一个，也可以有多个。在网络大小适中情况下，可设置一级调整节点和二级调整节点，其中一级调整节点收集一块区域内各订阅者发送的反馈消息，二级调整节点则收集一级调整节点发送的反馈消息进行全局公平性调整。一级调整节点可以先将得到的反馈信息平均值发给二级调整节点，然后开始本地区域化的计算比较，两个过程同时进行可节省一部分时间。然后二级调整节点会将全局的调整信息再返回给一级调整节点，在一级调整节点区域化调整幅度上进行调整，最后再将需要调整的节点信息(主要是对高、中优先级进行调整)反馈给各边界代理。同理，若是在网络节点巨大的情况下，可以以此类推设置三级调整节点等。不过若周期间隔不是非常长，不推荐层数过多，否则会延迟边界代理得到反馈的时间。According to the size of the network, there can be one or more adjustment nodes. When the network size is moderate, you can set up a first-level adjustment node and a second-level adjustment node. The first-level adjustment node collects the feedback messages sent by each subscriber in an area, and the second-level adjustment node collects the feedback messages sent by the first-level adjustment nodes. Make global fairness adjustments. The first-level adjustment node can first send the average value of the feedback information obtained to the second-level adjustment node, and then start the calculation and comparison of the local area. The two processes can save part of the time. Then the second-level adjustment node will return the global adjustment information to the first-level adjustment node, adjust the regional adjustment range of the first-level adjustment node, and finally send the node information that needs to be adjusted (mainly for high and medium priority) Adjustment) is fed back to each boundary agent. In the same way, if the network nodes are huge, you can set up three-level adjustment nodes by analogy. However, if the cycle interval is not very long, it is not recommended to have too many layers, otherwise it will delay the time for the border agent to get feedback.
S13：订阅者订阅消息，并对其设定个性化的优先级，具体分为高优先级、普通优先级和低优先级。S13: The subscriber subscribes to the message and sets a personalized priority for it, specifically divided into high priority, normal priority and low priority.
由于系统采用无环拓扑结构，该步骤的订阅发送过程利用洪泛算法完成，不会造成消息重复转发而占用不必要系统资源的情况。同时因为系统采用的是基于内容覆盖的路由算法，已经订阅过和被覆盖的消息就可以不用重新转发，进一步节省了带宽等系统资源。另外，系统中所提高优先级、普通优先级和低优先级指的是三个范围。Since the system adopts a ring-free topology, the subscription and sending process of this step is completed using the flooding algorithm, which will not cause unnecessary system resources to be occupied by repeated message forwarding. At the same time, because the system uses a routing algorithm based on content coverage, subscribed and covered messages do not need to be re-forwarded, which further saves system resources such as bandwidth. In addition, the elevated priority, normal priority and low priority in the system refer to three ranges.
通过该步骤的优先级划分，订阅者就可以将自身可支配的网络资源优先提供给设定的高优先级消息使用，从而可以更快的传送和接收关键信息。然而，由于个性化的订阅优先级设置可能会存在不公平的问题——比如某些用户可能贪婪地将自己所有的订阅都设置为高优先级，从而在中间代理节点系统抢占资源。因此，针对系统的公平性，除了防止低优先级消息“饿死”的机制外，系统还会对每个用户所有订阅的优先级进行审查。为了个性化和公平性保证，上述的步骤二和步骤三之间还包括以下操作：Through the prioritization in this step, the subscriber can give priority to the set high-priority messages with the network resources at its disposal, so that the key information can be transmitted and received faster. However, due to the personalized subscription priority setting, there may be unfair problems—for example, some users may greedily set all their subscriptions to high priority, thereby preempting resources in the intermediate proxy node system. Therefore, for the fairness of the system, in addition to the mechanism to prevent "starvation" of low-priority messages, the system will also review the priority of all subscriptions of each user. In order to guarantee personalization and fairness, the following operations are also included between the above steps 2 and 3:
指定不同指订阅者的优先级权重，根据权重决定一个节点订阅的不同优先级的消息在网络中的传输质量。Specifying different refers to the priority weight of the subscriber, and according to the weight, the transmission quality of messages of different priorities subscribed by a node in the network is determined.
具体地说，就是对任何一条订阅，其优先级都是由其在用户本身所有订阅中的重要程度和用户本身在系统中权重所决定的。在某些系统中，用户权重可进行商业收费，以达到服务质量区分。因而本系统可以指定不同用户(包括发布者和订阅者)的权重，从而根据权重决定一个节点订阅的不同优先级的消息在网络中的传输质量。Specifically, for any subscription, its priority is determined by its importance in all subscriptions of the user itself and the weight of the user itself in the system. In some systems, user weights can be charged commercially for quality of service differentiation. Therefore, the system can specify the weights of different users (including publishers and subscribers), so as to determine the transmission quality of messages of different priorities subscribed by a node in the network according to the weights.
例如，倘若一个用户贪婪地将其所有或大部分订阅都设置为高优先级(前提是订阅数超过5条，并且总的订阅范围超过一定比值，或者后期流量超过一定数目时)，那么系统可以启动两种策略：一是将其订阅按比例降低，使得其中高优先级消息数量不致于过多。二是从商业角度考虑，对可收费系统，可以针对用户订阅的高优先级消息进行收费，从控制成本角度，用户自然会科学地制定订阅优先级；对非可收费系统，也可分配给全部用户一个最大高优先级预算，一旦达到预算，就不能再继续订阅高优先级消息，用户就会针对自身需求按重要性对消息优先级进行调节。For example, if a user greedily sets all or most of his subscriptions to high priority (provided that the number of subscriptions exceeds 5, and the total subscription range exceeds a certain ratio, or the subsequent traffic exceeds a certain number), then the system can Start two strategies: one is to reduce its subscriptions proportionally so that the number of high-priority messages will not be too large. Second, from a commercial point of view, for chargeable systems, users can charge for high-priority messages subscribed by users. From the perspective of cost control, users will naturally formulate subscription priorities scientifically; for non-chargeable systems, they can also be allocated to all Users have a maximum high-priority budget. Once the budget is reached, they can no longer subscribe to high-priority messages, and users will adjust the priority of messages according to their own needs.
S14：订阅消息在中间代理网络中传输，每个代理节点存储一个订阅路由表，路由表每项都基于订阅者得出的优先级进行排序，接收到订阅消息后，根据路由表进行匹配，并通过合并覆盖路由算法决定订阅消息是否更新到路由表或进行舍弃处理。S14: The subscription message is transmitted in the intermediate proxy network. Each proxy node stores a subscription routing table. Each item in the routing table is sorted based on the priority obtained by the subscriber. After receiving the subscription message, it matches according to the routing table, and By merging and overriding the routing algorithm, it is decided whether the subscription message is updated to the routing table or discarded.
同样基于内容覆盖的路由算法，满足不同订阅者的有着合并覆盖关系的订阅在共同路径搭载共同路由，因此也进一步节省了系统资源。The same routing algorithm based on content coverage satisfies the need for subscriptions of different subscribers with a combined coverage relationship to be equipped with a common route on a common path, thus further saving system resources.
S15：发布者发布事件，事件到达每个代理节点，与其中的订阅路由表进行匹配，若匹配成功，从反向路径路由到感兴趣的订阅者。S15: The publisher publishes an event, and the event arrives at each proxy node, and is matched with the subscription routing table therein, and if the match is successful, it is routed to interested subscribers from the reverse path.
发布者发布的事件是没有优先级的，当其到达边界代理后，得到初始优先级，且优先级在每一中间节点上根据订阅路由表中下一跳的订阅优先级进行更新。The event published by the publisher has no priority. When it reaches the border agent, it gets the initial priority, and the priority is updated on each intermediate node according to the subscription priority of the next hop in the subscription routing table.
S16：各个边界代理分别记录一段预设周期内其连接的订阅者接收到的消息信息。S16: Each border agent respectively records message information received by its connected subscribers within a preset period.
该消息信息具体包括：总优先级、总队列等待时间、总延迟、总流量和消息数目。The message information specifically includes: total priority, total queue waiting time, total delay, total flow and number of messages.
S17：当达到预设周期时间间隔，各个边界代理统计各订阅者的消息信息平均值，并将信息平均值发送到其所属的调整节点。S17: When the preset periodic time interval is reached, each border agent counts the average value of the message information of each subscriber, and sends the average value of information to the adjustment node to which it belongs.
S18：各调整节点接收到所有其负责的订阅者消息后，依据各平均值、流量和各订阅者权重进行调整，调整每个订阅者所对应的高范围优先级、普通范围优先级的调整值，并将不为0的调整值返回给各订阅者所属边界代理。S18: After each adjustment node receives all the subscriber messages it is responsible for, it adjusts according to the average value, traffic and weight of each subscriber, and adjusts the adjustment value of the high-range priority and normal-range priority corresponding to each subscriber , and return the adjustment value that is not 0 to the boundary agent to which each subscriber belongs.
具体的，对每个订阅者的优先级范围进行调整遵循以下原则：各优先级订阅不可以降级或越级到其他优先级范围。Specifically, the following principle is followed for adjusting the priority range of each subscriber: each priority subscription cannot be downgraded or surpassed to other priority ranges.
S19：各边界代理收到步骤八发送的消息后，根据不同等级优先级调节本地路由表相应订阅的优先级，并将经过调整的订阅重新洪泛到网络中。S19: After receiving the message sent in step 8, each border agent adjusts the priority of the corresponding subscription in the local routing table according to different levels of priority, and re-floods the adjusted subscription to the network.
上述的步骤七至步骤九为周期性过程，步骤七中计数器在每次统计信息平均值并发送信息平均值给调整节点后自动清零。The above-mentioned steps 7 to 9 are periodic processes. In step 7, the counter is automatically cleared after each time the average value of the information is calculated and the average value of the information is sent to the adjustment node.
以下结合图2，对本发明的基于内容覆盖和反馈机制的用户订阅双区分的个性化优先级路由算法的应用过程进行具体说明。The following describes in detail the application process of the personalized priority routing algorithm based on content coverage and feedback mechanism based on user subscription double distinction in the present invention with reference to FIG. 2 .
如图2所示，其为本发明实施例的一个相对简单的网络拓扑图。应用本发明方法的网络结构由订阅者(Subscriber，黄色节点)、发布者(Publisher，绿色节点)和代理节点(Broker，粉色节点)、组成。其中订阅者有不同权重，且可给自己的订阅赋不同优先级值；从功能性角度，代理节点可细分为边界代理节点和(一级、二级等)调整节点，它们同时都有普通代理节点的匹配转发等功能。As shown in FIG. 2 , it is a relatively simple network topology diagram of the embodiment of the present invention. The network structure applying the method of the present invention is composed of a subscriber (Subscriber, yellow node), a publisher (Publisher, green node) and a proxy node (Broker, pink node). Among them, subscribers have different weights, and can assign different priority values to their own subscriptions; from a functional point of view, proxy nodes can be subdivided into border proxy nodes and (level 1, level 2, etc.) Functions such as matching and forwarding of proxy nodes.
首先，生成树算法生成一个无环的网络拓扑图。图2展示的是无环拓扑。在这个拓扑中，broker1、broker2、broker7、broker9和broker10是订阅者的边界代理，且根据距离、节点深度等因素，经选举算法可选举broker3、broker8为一级调整节点，前者负责broker1、broker2、broker7的汇总调节，后者则负责broker9、broker10的汇总调节。进一步，为了说明本发明设计，指定broker4为二级调整节点。First, the spanning tree algorithm generates an acyclic network topology graph. Figure 2 shows the acyclic topology. In this topology, broker1, broker2, broker7, broker9, and broker10 are the border agents of subscribers, and according to factors such as distance and node depth, broker3 and broker8 can be elected as first-level adjustment nodes through the election algorithm, and the former is responsible for broker1, broker2, The aggregate adjustment of broker7, and the latter is responsible for the aggregate adjustment of broker9 and broker10. Further, in order to illustrate the design of the present invention, broker4 is designated as the secondary adjustment node.
其次，订阅者发布订阅，利用洪泛算法在整个系统中传播，最终也会到达每个事件者所属边界代理节点，这个过程会在每个broker的路由表上留下事件反向路径路由回订阅者的记录。因为系统采用的是无环结构，所以消息不会在系统中重复转发占用不必要的系统资源，同时因为系统采用的是基于内容覆盖的路由算法，已经订阅过和被覆盖的消息就可以不用重新转发，相比传统发布订阅系统，本发明方法可以有效地利用宝贵的宽带和节点存储资源。Secondly, the subscriber publishes and subscribes, uses the flooding algorithm to spread throughout the system, and eventually reaches the border proxy node to which each event owner belongs. This process will leave an event reverse path on the routing table of each broker to route back to the subscription record. Because the system adopts an acyclic structure, messages will not be forwarded repeatedly in the system and occupy unnecessary system resources. At the same time, because the system uses a routing algorithm based on content coverage, messages that have been subscribed and overwritten do not need to be retransmitted. For forwarding, compared with the traditional publish-subscribe system, the method of the present invention can effectively utilize precious broadband and node storage resources.
然后，发布者发布事件。事件会在每个代理节点与路由表匹配，找到下一个感兴趣者，最终到达订阅者，这就是事件的反向路由路由。这个过程中，边界代理节点、broker2、broker7、broker9和broker10会分别负责记录subscriber1、subscriber2、subscriber3、subscriber4和subscriber5收到的事件的总优先级、总队列等待时间、总延迟、总流量和消息数目。Then, the publisher publishes the event. The event will match the routing table at each proxy node, find the next interested person, and finally reach the subscriber. This is the reverse routing of the event. In this process, the border proxy node, broker2, broker7, broker9 and broker10 will be responsible for recording the total priority, total queue waiting time, total delay, total traffic and number of messages of the events received by subscriber1, subscriber2, subscriber3, subscriber4 and subscriber5 respectively .
接着，周期性反馈机制实现。当预定时间达到时，每个边界代理会把订阅者的统计信息平均值(除以消息数目，除了总流量之外)发送到其所属的调整节点，分别是broker3和broker8。一级调整节点在收齐其负责的订阅者信息后，继续取平均值发送到二级调整节点broker4；然后，在本地同时进行区域化的两两比较等操作，决定每个订阅者的高优先级和普通优先级订阅分别应该调整多少。Broker4在收齐其负责的一级调整节点的反馈信息后开始在本地进行全局的比较调整操作——这是为了防止区域性的不公平现象(区域全部偏高或偏低)。值得注意的是，上述这些过程在时间上很可能是重叠进行的(更大范围地说，发布订阅、发布事件、反馈调节都可能同时在进行)。当broker4计算完毕时，它会返回调节信息(区域优先级分高、普通一起调低或调高)给一级调整节点。Broker3和broker4接收到全局调整信息后，会将它们与区域的调整信息合并，然后再返还给边界代理节点。紧接着，边界代理节点根据反馈更新路由表，针对改动的路由进行订阅重新发布，此过程类似于订阅发送过程。为了用户体验平稳，建议每次微调，多次周期性调整过后，系统必然慢慢趋于公平。Then, a periodic feedback mechanism is implemented. When the predetermined time is reached, each border broker will send the average value of the subscriber's statistical information (divided by the number of messages, except the total traffic) to its own adjustment nodes, which are broker3 and broker8 respectively. After the first-level adjustment node collects the information of the subscribers it is responsible for, it continues to take the average value and send it to the second-level adjustment node broker4; then, it performs regionalized pairwise comparisons and other operations locally to determine the high priority of each subscriber. How much should be adjusted for premium and normal priority subscriptions. Broker4 starts to perform a global comparison and adjustment operation locally after collecting the feedback information from the first-level adjustment nodes it is responsible for—this is to prevent regional unfairness (all regions are higher or lower). It is worth noting that the above-mentioned processes are likely to be overlapped in time (to a larger extent, publish and subscribe, publish events, and feedback adjustment may all be carried out at the same time). When broker4 completes the calculation, it will return the adjustment information (higher regional priority, lower or higher common) to the first-level adjustment node. After receiving the global adjustment information, Broker3 and Broker4 will merge them with the adjustment information of the area, and then return it to the border proxy node. Immediately afterwards, the border proxy node updates the routing table according to the feedback, and subscribes and republishes the changed route. This process is similar to the subscription sending process. For a stable user experience, it is recommended to fine-tune each time. After multiple periodic adjustments, the system will inevitably gradually become fair.
本发明的基于内容覆盖和反馈机制的用户订阅双区分的个性化优先级路由算法，在发布订阅系统中首次引入了个性化优先级路由，并且可以对用户设置不同权重进行服务区分，大大增加了发布订阅系统的功能性和灵活性，可以以有限的资源更好地满足不同的用户需求。另外，本发明是构建在生成树算法生成的无环网络拓扑上的，还结合了基于内容覆盖的路由算法，因此有效地减少了消息在系统中冗余发送的情况。而且，为了避免用户在个性化订阅过程中过于“贪婪”地设置高优先级订阅，本发明还提供了一系列的公平性保证措施，确保个性化优先级订阅和公平性并存。具体地，可以根据网络规模和信息量大小，选择不同的调整节点数目、层级反馈结构或者分布式通信。因此，与现有技术相比，本发明首次提出了个性化优先级订阅，改进了系统功能，并且允许用户和订阅进行优先级(权重和优先级是同等概念)双区分，具有高效地传送关键信息，大大减少了冗余消息发送量，同时兼顾公平性的优点。The personalized priority routing algorithm based on the content coverage and feedback mechanism of the present invention introduces personalized priority routing for the first time in the publish and subscribe system, and can set different weights for users to differentiate services, which greatly increases The functionality and flexibility of the publish-subscribe system can better meet different user needs with limited resources. In addition, the present invention is built on the acyclic network topology generated by the spanning tree algorithm, and also combines the routing algorithm based on content coverage, thus effectively reducing the redundant sending of messages in the system. Moreover, in order to prevent users from setting high-priority subscription too "greedily" during the personalized subscription process, the present invention also provides a series of fairness guarantee measures to ensure the coexistence of personalized priority subscription and fairness. Specifically, different numbers of adjustment nodes, hierarchical feedback structures, or distributed communications can be selected according to the network scale and the amount of information. Therefore, compared with the prior art, the present invention proposes personalized priority subscription for the first time, improves the system function, and allows users and subscriptions to carry out priority (weight and priority are the same concept) double distinction, and has the key to efficiently transmit Information, greatly reducing the amount of redundant message transmission, while taking into account the advantages of fairness.
以上所述，仅是本发明的较佳实施实例而已，并非对本发明做任何形式上的限制，任何未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施实例所作的任何简单修改、等同变化与修饰，均属于本发明技术方案的范围。The above is only a preferred implementation example of the present invention, and is not intended to limit the present invention in any form, any content that does not deviate from the technical solution of the present invention, any simple modification made to the above implementation examples according to the technical essence of the present invention , equivalent changes and modifications all belong to the scope of the technical solution of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210226518.8ACN102833151B (en) | 2012-07-02 | 2012-07-02 | User individuation priority routing algorithm based on content coverage and feedback mechanism |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210226518.8ACN102833151B (en) | 2012-07-02 | 2012-07-02 | User individuation priority routing algorithm based on content coverage and feedback mechanism |
| Publication Number | Publication Date |
|---|---|
| CN102833151A CN102833151A (en) | 2012-12-19 |
| CN102833151Btrue CN102833151B (en) | 2015-07-08 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210226518.8AActiveCN102833151B (en) | 2012-07-02 | 2012-07-02 | User individuation priority routing algorithm based on content coverage and feedback mechanism |
| Country | Link |
|---|---|
| CN (1) | CN102833151B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12034570B2 (en) | 2022-03-14 | 2024-07-09 | T-Mobile Usa, Inc. | Multi-element routing system for mobile communications |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103281242B (en)* | 2013-06-19 | 2016-04-13 | 迈普通信技术股份有限公司 | protocol stack routing table maintenance method and device |
| CN103685013B (en)* | 2013-11-29 | 2017-02-08 | 中国科学院计算技术研究所 | Mixed routing method and device based on contents |
| US9424083B2 (en)* | 2014-03-14 | 2016-08-23 | Google Inc. | Managing metadata for a distributed processing system with manager agents and worker agents |
| CN105991463B (en)* | 2015-02-13 | 2020-12-25 | 创新先进技术有限公司 | Method, message main node, token server and system for realizing flow control |
| WO2017214813A1 (en)* | 2016-06-13 | 2017-12-21 | 深圳天珑无线科技有限公司 | Distributed network message returning method, node and system |
| CN107370678B (en)* | 2017-06-19 | 2020-04-14 | 深圳市盛路物联通讯技术有限公司 | A routing and forwarding table update method and system applied to the Internet of Things |
| CN108156086B (en)* | 2017-12-19 | 2022-04-22 | 北京奇艺世纪科技有限公司 | Policy rule issuing method and device |
| CN111698024B (en)* | 2020-06-22 | 2022-05-06 | 泰州市柯普尼通讯设备有限公司 | Ship satellite vsat video bandwidth allocation information transmission system and method |
| CN114124704B (en)* | 2021-11-19 | 2024-01-23 | 北京天融信网络安全技术有限公司 | Route optimization method, device, electronic equipment and storage medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0731583A1 (en)* | 1995-03-08 | 1996-09-11 | International Business Machines Corporation | Method and system for routing messages in a multi-node data communication network |
| CN1625119A (en)* | 2004-12-09 | 2005-06-08 | 中国科学院软件研究所 | Routing method of pub/sub system built on structured P2P network |
| CN1815989A (en)* | 2004-10-26 | 2006-08-09 | 国际商业机器公司 | Method for efficiently constructing network overlays through interconnection topology embedding |
| CN101635895A (en)* | 2009-07-31 | 2010-01-27 | 青岛海信移动通信技术股份有限公司 | Website content subscribing system, website content subscribing method, mobile communication terminal and server |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0731583A1 (en)* | 1995-03-08 | 1996-09-11 | International Business Machines Corporation | Method and system for routing messages in a multi-node data communication network |
| CN1815989A (en)* | 2004-10-26 | 2006-08-09 | 国际商业机器公司 | Method for efficiently constructing network overlays through interconnection topology embedding |
| CN1625119A (en)* | 2004-12-09 | 2005-06-08 | 中国科学院软件研究所 | Routing method of pub/sub system built on structured P2P network |
| CN101635895A (en)* | 2009-07-31 | 2010-01-27 | 青岛海信移动通信技术股份有限公司 | Website content subscribing system, website content subscribing method, mobile communication terminal and server |
| Title |
|---|
| 内容发布订阅服务网络中的路由策略;金源等;《计算机工程与应用》;20061230(第12期);第171-174页* |
| 基于DDS的发布/订阅中间件设计;曹万华等;《计算机工程》;20070930;第33卷(第18期);第78-80页* |
| 基于内容的发布何阅模型中高效的匹配算法;张彩云;《河北师范大学学报》;20090730;第33卷(第4期);第452-第455页* |
| 应用P2P网络实现基于内容的发布订阅系统;薛涛等;《微电子学与计算机》;20071230;第24卷(第9期);第89-第91页* |
| 薛涛.移动自组网中基于内容的发布/订阅路由协议.《计算机工程》.2009,第35卷(第6期),第130-第144页.* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12034570B2 (en) | 2022-03-14 | 2024-07-09 | T-Mobile Usa, Inc. | Multi-element routing system for mobile communications |
| Publication number | Publication date |
|---|---|
| CN102833151A (en) | 2012-12-19 |
| Publication | Publication Date | Title |
|---|---|---|
| CN102833151B (en) | User individuation priority routing algorithm based on content coverage and feedback mechanism | |
| Bedewy et al. | The age of information in multihop networks | |
| US6678248B1 (en) | Policy based quality of service | |
| US6859438B2 (en) | Policy based quality of service | |
| CN100426733C (en) | System for realizing resource distribution in network communication and its method | |
| CN109714275B (en) | SDN controller for access service transmission and control method thereof | |
| CN110493145A (en) | A kind of caching method and device | |
| CN101707788B (en) | Differential pricing strategy based dynamic programming method of multilayer network services | |
| JP2009525641A (en) | High reliability event broadcaster with multiplexing and bandwidth control functions | |
| CN106533939B (en) | A kind of software-defined optical access aggregation network bandwidth dynamic adjustment method and device | |
| JP2002543669A (en) | Route setting device | |
| CN113726656B (en) | Method and device for forwarding delay sensitive flow | |
| CN113747597B (en) | Network data packet scheduling method and system based on mobile 5G network | |
| CN102904837A (en) | A Method of Distinguishing Service Survivability Based on Virtual Service Plane | |
| CN112615798B (en) | A bandwidth allocation method and device based on elephant flow reservation | |
| CN110557333A (en) | method and system for controlling and guaranteeing quality of service of software defined network | |
| CN100466593C (en) | A Realization Method of Integrated Queue Scheduling Supporting Multiple Services | |
| CN105721316B (en) | A kind of method and device issuing flow table | |
| Le et al. | A joint relay selection and buffer management scheme for delivery rate optimization in dtns | |
| Abbasloo et al. | Hyline: a simple and practical flow scheduling for commodity datacenters | |
| CN101179487B (en) | Computer network data packet forwarding queue management method | |
| Chen et al. | Packet scheduling algorithm based on priority adjustment in wireless sensor networks | |
| CN101902405A (en) | Emergency service-oriented temporary bandwidth allocation method and system thereof | |
| CN1622524A (en) | Mitigation and adjustment method of mobile IP burst traffic | |
| CN108347378A (en) | A kind of control dedicated network and dynamic routing method for bulk power grid |
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| TR01 | Transfer of patent right | Effective date of registration:20200116 Address after:Room 1709, Building No. 8, Binjiang West Road, Jiangyin City, Wuxi City, Jiangsu Province Patentee after:Jiangyin Daily Information Technology Co., Ltd. Address before:200240 Dongchuan Road, Shanghai, No. 800, No. Patentee before:Shanghai Jiaotong University | |
| TR01 | Transfer of patent right |