system and method for providing quality of service in a wide area message factory

专利摘要:
SYSTEM AND METHOD FOR PROVIDING QUALITY OF SERVICE IN A WIDE AREA MESSAGE FACTORY Techniques for transmitting data in accordance with at least one service quality requirement. A message path is calculated by specifying a sequence of intermediate computers selected from a network of interconnected intermediate computers. The message path is estimated statistically to satisfy at least one quality of service requirement. Quality of service metrics are received over the interconnected intermediary computer network. If the message path is determined not to satisfy the quality of service requirement, a new message path is calculated by specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network. The new message path is estimated statistically to satisfy at least one quality of service requirement.
公开号:BR112012012942B1
申请号:R112012012942-2
申请日:2010-10-18
公开日:2020-12-08
发明作者:Kyriakos Karenos；Fan Ye；Minkyong Kim；Hui Lei；Dimitrios Pendarakis；Hao Yang
申请人:International Business Machines Corporation；
IPC主号:

专利说明:

BACKGROUND OF THE INVENTION Field of invention
[0001] The present invention relates in general to sending messages. More specifically, the present invention relates to techniques for providing quality of service (QoS) for the transmission of messages over networks that potentially cover a large geographical area. Description of the Basics
[0002] Quality of service (QoS) is a requirement, a set of requirements, imposed on data transfer over a computer network. A network that provides quality of service is configured to cause data transfers to be carried out according to the requirement or set of requirements. The network can provide a guarantee that the quality of service requirements will be enforced. The quality of service (QoS) of the message sending substrate plays a critical role in the overall performance of the system as perceived by end users.
[0003] Publish / subscribe messages are a fundamental mechanism for interconnecting different services and systems in modern service-oriented computing architecture. In the publishing / subscription paradigm, publishers transmit messages to subscribers. Each message can be associated with a specific topic. A subscriber can subscribe to a topic in order to receive messages from publishers on that topic. An arbitrary number of subscribers can subscribe to the same topic. It is noted that publishing / subscribing is commonly abbreviated as "pub / sub". SUMMARY OF THE INVENTION
[0004] One aspect of the invention is a method for transmitting data according to at least one quality of service requirement. The method includes calculating a message path that specifies a sequence of intermediate computers selected from a network of interconnected intermediate computers. The sequence begins with an initial intermediate computer connected with a sending computer and ends with an end intermediate computer connected with a receiving computer. The message path is statistically estimated to satisfy at least one quality of service requirement. A transmission operation transmits a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path. The method additionally includes receiving quality of service metrics over the interconnected intermediary computer network. A determination operation determines whether the message path meets at least one quality of service requirement based on a quality of service metric. If the message path is determined not to satisfy at least one quality of service requirement, the calculation operation is repeated for a new message path specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network. The new message path is estimated statistically to satisfy at least one quality of service requirement.
[0005] Another aspect of the invention is an intermediate computer coupled with a network of interconnected intermediate computers to transmit data according to at least one quality of service requirement. The buffer computer includes a calculation unit configured to calculate a message path specifying a sequence of buffer computers selected from the interconnected buffer network. The sequence begins with an initial intermediate computer connected with a sending computer and ends with an end intermediate computer connected with a receiving computer. The message path is statistically estimated to satisfy at least one quality of service requirement.
[0006] The intermediate computer additionally includes a transmitting unit and a receiving unit. The transmission unit is configured to transmit a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path. The receiving unit is configured to receive quality of service metrics over the interconnected intermediary computer network. An intermediate computer determination unit is configured to determine whether the message path meets at least one quality of service requirement based on a quality of service metric. If the message path is determined not to satisfy at least one quality of service requirement, the unit of determination causes the calculation unit to calculate a new message path by specifying a new sequence of intermediate computers selected from the network. interconnected intermediate computers. The new message path is estimated statistically to satisfy at least one quality of service requirement.
[0007] Another aspect of the invention is a computer program product for transmitting data in accordance with at least one quality of service requirement. The computer program product comprises a computer-readable storage medium having computer-readable program code incorporated therewith. The computer-readable program code is configured to: calculate a message path by specifying a sequence of intermediate computers selected from a network of interconnected intermediate computers, the sequence beginning with an initial intermediate computer connected with a sending computer, the sequence ending with a final intermediate computer connected to a receiving computer, the message path being statistically estimated to satisfy at least one quality of service requirement; transmitting a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path; receive quality of service metrics on the interconnected intermediary computer network; determine whether the message path meets at least one quality of service requirement based on a quality of service metric; and if the message path is determined not to satisfy at least one quality of service requirement, run the calculation program code for a new message path specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network , the new message path being statistically estimated to satisfy at least one quality of service requirement. BRIEF DESCRIPTION OF THE DRAWINGS
[0008] The subject that is considered as the invention is particularly highlighted and distinctly claimed in the claims at the conclusion of the specification. The foregoing objectives and other objectives, functionalities, and advantages of the invention are apparent from the following detailed description taken in conjunction with the accompanying drawings in which: FIG. 1 shows an example of an environment incorporating the present invention. FIG. 2 illustrates an example of a message path. FIG. 3 demonstrates an example of a sequence of operations for transmitting data according to at least one quality of service requirement. FIG. 4 demonstrates an example of a sequence of operations to receive quality of service metrics over the interconnected intermediary computer network. FIG. 5 demonstrates an example of a sequence of operations for calculating a message path. FIG. 6 demonstrates an example of a sequence of operations for sorting a plurality of messages waiting for transmission through a common message path segment between intermediate computers. FIG. 7 illustrates an example of an intermediate computer for transmitting data according to at least one quality of service requirement. FIG. 8 illustrates a network model for an embodiment of the present invention. FIG. 9 demonstrates an example of establishing a route within the embodiment. FIG. 10 illustrates an implementation of the WMB flow in each overlay intermediary in the embodiment. FIG. 11 shows a graph of the end-to-end delay for both delivery and direct connection. DETAILED DESCRIPTION OF THE INVENTION
[0009] The present invention is described with reference to embodiments of the invention. Through the description of the invention reference is made to Figs. 1 to 11. When referring to the Figures, structures and similar elements shown through it are indicated with similar reference numerals.
[00010] Referring now to FIG. 1, an example of environment 102 incorporating the present invention is shown. It is initially noted that environment 102 is presented for purposes of illustration only, and is representative of numerous configurations in which the invention can be implemented. Thus, the present invention should not be construed as limited to the environmental configurations shown and discussed here.
[00011] Environment 102 includes nodes 104, 106, 108. A node can be any one of a wide variety of technological devices. A node can be implemented in hardware, software or a combination thereof. A node can be a computer or it can be software that runs on a computer. In any case, the computer can comprise one or more computer processors. Nodes can be heterogeneous in terms of hardware characteristics, software characteristics, or both.
[00012] A node can be, or can comprise, a sensor 104. A sensor can generate and transmit event data. A node can also be, or can comprise, an actuator 106. An actuator can receive and act on the control directives. The sensors and actuators can be distributed in the field.
[00013] A node may also be, or may comprise, a processing element 108. A processing element may incorporate processing capabilities of the back end process, such as analytical capabilities. A processing element can perform back-end processing tasks, such as event processing. A processing element can be located in a data center or a back-end office.
[00014] It is noted that while three nodes are sufficient to demonstrate the present invention, the number of nodes included in the environment is not limited to three. On the contrary, the number of nodes can be very large.
[00015] Nodes 104, 106, 108 are interconnected with each other. This interconnection allows the nodes to communicate with each other. It is emphasized that as a result, the sensors 104 and actuators 106 included in the environment are interconnected with, and can communicate with, the processing elements 108.
[00016] It is emphasized that the 102 environment can be spread over a large geographical area. Specifically, any nodes included in the environment, including any sensors 104 and actuators 106, can be distributed over a large geographic area.
[00017] The nodes included in environment 102 can constitute an event-driven system. Thus, some nodes, such as sensors 104, can generate events. Other nodes, such as processing elements 108, can respond to events.
[00018] Environment 102 additionally includes a plurality of intermediate computers 110. An intermediate computer can be a general purpose computer. Such a computer can incorporate any of a wide variety of architectures. The computer can be based on a general purpose operating system such as the IBM® z / OS® operating system, the IBM AIX® operating system, the Linux® operating system, either the UNIX® operating system or the Windows® operating system. IBM, z / OS and AIX are registered trademarks of International Business Machines Corporation, Armonk, New York, United States of America, the United States of America, other countries, or both. Linux® is the registered trademark of Linus Torvalds in the United States of America and other countries. UNIX is a registered trademark of the Open Group in the United States of America and other countries. Windows is a registered trademark of Microsoft Corporation, Redmond, Washington, United States of America, the United States of America and / or other countries. An intermediate computer can also be a special-purpose computer manufactured specifically to implement the present invention.
[00019] An intermediate computer 110 may comprise one or more computer processors. An intermediate computer can also incorporate any of a wide variety of computer program products. Intermediate computers can be heterogeneous in terms of hardware characteristics, software characteristics, or both.
[00020] The intermediate computer 110 may comprise a software application or computer program product incorporating logic that implements any or all of the operations described hereinafter as being performed by the intermediate computer. Thus, running this software application or computer program product on the intermediate computer causes the intermediate computer to act as an intermediary in accordance with the present invention.
[00021] Intermediate computers 110 are interconnected to form a network 112. Interconnected intermediary computers collectively implement a message mesh that interconnects nodes 104, 106, 108. To achieve this goal, interconnected intermediate computers transmit messages between the nodes. The message fabric can be middleware.
[00022] The message fabric provides message functionality. Messages can include any of a wide variety of techniques for exchanging information. Messages can be implemented using a wide variety of methods. Messages can be provided as a layer on a larger system that provides application level connectivity for all components within the larger system. Appropriately, messages can be a mechanism that facilitates the integration of different system components.
[00023] In one embodiment of the present invention, intermediate computers 110, nodes 104, 106, 108, or both implement the Java ™ Messaging System standard. Java is a trademark or registered trademark of Sun Microsistemas, Inc., Santa Clara, California, United States, or its subsidiaries in the United States of America and other countries. Previous system components can employ this pattern to understand the exchange of messages between them.
[00024] Intermediate computers 110 can be paired in a person-to-person network structure. In this way, intermediaries may not be assigned the roles of clients and servers.
[00025] Intermediate computers 110, and the messaging network implemented in this way, can be spread over a large geographic area. This advantageously facilitates the connection of nodes that are spread over a large geographical area.
[00026] Environment 102 can be a distributed system. In this sense, nodes 104, 106, 108, intermediate computers 110, or both can be distributed.
[00027] Each node 104, 106, 108 included in the environment can be connected with one or more intermediate computers 110. The connection between a node and an intermediate computer can be made by a connection component 114.
[00028] Each node can be directly connected with a number of intermediate computers. This is possible because a node can communicate with other nodes through an intermediate computer to which it is connected. This intermediate computer can cause the communication to be relayed to the destination node. A node may still be unaware of different intermediate computers than those to which it is directly connected.
[00029] In one embodiment of the present invention, each node is directly connected with one or fewer intermediate computers. In one embodiment of the present invention, each node is directly connected with two or less intermediate computers. In another embodiment of the present invention, each node is directly connected with three or less intermediate computers.
[00030] Environment 102 may additionally include a plurality of different message domains 116. Different message domains may be distributed in different locations. Different message domains can be associated with different organizations. Different message domains may employ different network protocols. Different nodes 104, 106, 108 can be located in different message domains. Likewise, different intermediate computers 110 can be located in different message domains. Entities within a common message domain can be considered to be local to each other.
[00031] For performance reasons, any or all of the nodes 104, 106, 108 in environment 102 can be connected with an intermediate computer 102 that is located within the same message domain 116. Thus, a message domain can comprise one or more intermediate computers and all nodes that are connected with any intermediate computer comprised by the message domain. The intermediate computers comprised by the message domain can then be responsible for the communication between nodes comprised by the message domain and nodes in other message domains.
[00032] The environment additionally includes one or more networks 118. A network can be any one of a wide variety of systems known in the art to allow two or more systems to communicate. A network can be, or can comprise, the public Internet or a subset of them. A network can also be, or can comprise, any type of public network, such as the public switched telephone network (PSTN). A network can also be, or can comprise, a virtual private network (VPN) or any type of private network. A network can be, or can comprise, a wide area network (WAN) or a local area network (LAN). Remarkably, networks can be heterogeneous, although this is not necessary.
[00033] A 118 network can employ any of a wide variety of network technologies such as ethernet, IEEE 802.11, IEEE 802.16, Bluetooth® technology, token ring, Digital Subscriber Line (DSL), cable Internet access , satellite Internet access, Integrated Services Digital Network (ISDN) and dial-up Internet access. Bluetooth is a registered trademark of Bluetooth SIG, Inc., Bellevue, Washington, United States of America. A network can include various topologies and protocols known to those skilled in the art, such as TCP / IP, UDP, and Internet Voice Protocol (VoIP). A network can comprise direct physical connections, radio waves, microwaves, or any combination thereof. In addition, a network may include various network devices known to the person skilled in the art, such as routers, switches, bridges, repeaters, etc.
[00034] Interconnected intermediate computers 110 can communicate over any or all of the networks 118. More specifically, messages transmitted by any of the intermediate computers can be transmitted by any or all of the networks. It is emphasized that a message mesh that implements the present invention can be distributed to facilitate sending messages over the previous types of networks.
[00035] Interconnected intermediate computers 110 can be connected to each other via network connections 120. Network connections can be provided through any or all networks 118. Each intermediate computer can have direct network connections to only a small number of neighboring intermediate computers. If an intermediate computer wishes to communicate with an intermediate computer to which it is not directly connected, the communication can be routed through other intermediate computers until it reaches the destination intermediate computer. It is emphasized that as a result, pair connections between each pair of intermediate computers are not necessary.
[00036] It is noted that WAN's, including the public Internet, present several challenges from a communications point of view. Generally speaking, WAN's have different patterns of dynamics and failure than LAN's, such as the network found in a data center. Specifically, since WAN's are typically spread over a large geographic area, communications over WAN's are often long-range communications. As a result, communication over WAN's is often poorly reliable (for example, prone to error). Communication over WAN's also often has high latency, or very high latency, between nodes. In addition, the public Internet and other Internet Protocol (IP) based services provide only connectivity for best efforts. Those skilled in the art will realize that the connectivity of the best efforts offers no guarantee of specific quality of service. In addition, applications typically cannot control network behavior over a WAN.
[00037] Environment 102, and communication between nodes 104, 106, 108 included therein, can facilitate any of a wide variety of applications in any of a wide variety of application domains. Applications may include, without limitation, aviation information and airspace surveillance systems, intelligent transport systems, intelligent grids for energy production and distribution, intelligent utility and electricity networks, control and command centers for smart cities, management intelligent water, and emergency response and preparedness. Applications can be mission critical in nature. Nodes can be end points of the application.
[00038] In advance of such applications, a wide variety of event data and control directives can be carried between sensors 104, actuators 106, and processing elements 108 (possibly including data centers and back-end offices) where the latter are located) through the message mesh. This can occur for any of the applications described above. However, it is contemplated that specific event data and control policies vary depending on the specific application.
[00039] In many situations, data transmitted in accordance with the present invention, such as data generated by sensors and control directives, are time sensitive, mission critical, or both. For example, sensors in a power grid can monitor the state of the grid and detect potential power failures. These sensors can generate events. An event can be an alarm that indicates a possible power failure. Unless the alarm is received promptly, it may be too late to avoid a current power outlet. Thus, the events generated by the sensors must clearly be distributed in a reliable manner, as failure to detect an alarm is clearly dangerous. It follows that this sensor data that indicates a failure event within a power grid is clearly time sensitive and mission critical.
[00040] Similarly, sensor data that indicates the location of one or more suspect aircraft is clearly time sensitive and mission critical. Switching control commands are also commonly time sensitive and mission critical. More generally, many applications known in the art require information to be distributed in a time-sensitive and highly reliable manner.
[00041] The message mesh is operable to provide a defined quality of service (QoS), and therefore predictable. In other words, the message fabric is aware of QoS. The provision of QoS may include making one or more quality of service requirements for messages and data transmitted through the message fabric. The QoS requirements that can be enforced by the message fabric include, without limitation, latency, reliability, availability and throughput. QoS requirements can be enforced on an end-to-end basis.
[00042] The present invention comprises a framework and set of mechanisms to provide this quality of service defined within the message mesh. This is achieved effectively by addressing the dynamics and heterogeneity of the underlying networks and systems on which the messaging network operates. This is additionally achieved by addressing any fault conditions that occur within networks and systems.
[00043] The provision of a defined predictable QoS can beneficially cause messages to be distributed across components and subsystems in a reliable and timely manner. This is clearly advantageous for data that is time sensitive, mission critical or both.
[00044] In addition, different messages may have different QoS requirements. Differentiated QoS requirements can be specified based on a wide variety of criteria. QoS requirements can be specified per message topic, such that all messages that belong to a specified topic share a set of QoS requirements. QoS requirements can be specified per connection session, such that all messages within a connection session share a set of QoS requirements. QoS requirements can even be specified for an individual message.
[00045] In order to transmit a message, a sending node 104, 106, 108 can initially transmit the message to an intermediate computer 110 to which the sending node is connected. This intermediate computer can then determine a routing path for the message. The routing path can comprise a sequence of intermediate computers. Adjacent intermediate computers in this sequence can be directly connected to each other. Thus, each intermediate computer, in turn, can transmit the message to the next intermediate computer in the sequence. The final intermediate computer in the sequence can then transmit the message to the receiving node. The routing path can also specify the sending node, the receiving node, or both.
[00046] The present invention includes a routing algorithm configured to establish routing paths as described above. These routing paths are subject to end-to-end QoS requirements, including any latency and availability requirements imposed in this way.
[00047] Intermediate computers 110 can monitor networks, intermediate computers, nodes 104, 106, 108, or any combination thereof. Monitoring can be carried out periodically. Monitoring can also be chronic and continuous. Such monitoring can detect that QoS requirements are violated for one or more routing paths. QoS requirements are considered to be violated when the current performance of the routing path contradicts any or all of the QoS requirements. Whenever a violation of QoS requirements is detected, the routing paths are adjusted. The adjusted routing path is intended to conform to QoS requirements. In this way, the present invention automatically manages routing paths to ensure that they conform to QoS requirements even when network conditions and system state change over time.
[00048] In one embodiment of the present invention, a message is transmitted using multipath routing. Specifically, a plurality of routing paths is determined as described above. Message replication is performed such that a duplicate copy of the message is transmitted along each of the routing paths. Thus, the message will be received as long as a case of the message reaches its destination. This can occur even if an appropriate subset of routing paths fails.
[00049] As a result, multipath routing advantageously increases the reliability of sending messages. This helps to achieve QoS requirements with respect to reliability. In addition, multipath routing increases the likelihood of meeting a QoS requirement by specifying maximum latency. This is because even if one case of the message is delayed, another case of the message may still arrive on time. However, the previous advantages are achieved in the increased cost of traffic.
[00050] It is noted that multipath routing does not inherently require message recognition and retransmission. Thus, multipath routing does not cause the latency penalty associated with this recognition and retransmission.
[00051] In one embodiment of the present invention, intermediate computers 110 can collectively implement a message mesh that provides message exchange according to the publishing / subscription paradigm. In this paradigm and realization, a publisher publishes information. The publisher can be a node 104, 106, 108 in environment 102. The information can include any type of data and can be expressed in the form of a message. Subscribers who are interested in the information subscribe to it. Subscribers can also be nodes in the environment. An arbitrary or possibly large number of subscribers can subscribe to information transmitted by a single publisher. The publisher transmits the information to an intermediate computer. The intermediate computer then dispatches the information to each of the subscribers, possibly with the assistance of other intermediate computers. It is emphasized that as a result, QoS is provided for the exchange of messages according to the publishing / subscription paradigm.
[00052] It is noted that nodes can be end points for publishers and subscribers as opposed to publishers and subscribers themselves.
[00053] As noted above, each node can be connected with a local intermediate computer. Since the publishers and subscribers are us, each publisher and each subscriber, or their end points, so they can be connected with a local intermediary computer, for example, an intermediary computer in the same message domain 116. Conversely, each intermediary computer can be attached with at least one publisher and at least one subscriber in the same message domain.
[00054] In a further embodiment of the present invention, the publishing / subscription paradigm is based on topic. Topics help publishers and subscribers understand what data is useful to the other party. A topic can be interpreted as a bookmark that is applicable to all information associated with a category identified by the topic. Appropriately, a publisher specifies a topic that describes information published in this way. A subscriber can then subscribe to this topic in order to receive this information. An arbitrary and possibly large number of subscribers can subscribe to a single topic. Differentiated QoS requirements can be specified for each message topic as described above.
[00055] Thus, for each topic, intermediate computers can establish and manage routing paths as described above in order to connect all publishers and subscribers in environment 102 who publish or subscribe to that topic. Routing paths are established subject to the application's QoS requirements and system state.
[00056] It is noted that publishing / signing message meshes are efficient in allowing large numbers of system components to communicate with each other. In addition, in publish / subscribe systems, a subscriber is not required to be aware of the publisher's identity, and vice versa. Thus, producers and consumers of information are decoupled. As a result, the scalability of the messaging system is increased. In addition, publishers and subscribers do not need to remain online at all times. Additionally, not being aware of the identity of other participants increases security and privacy. Enabling publication / subscription messages, this embodiment advantageously provides the following advantages.
[00057] Additionally, the publishing / subscription paradigm is advantageous for implementing service-oriented architectures (SOA's). Thus, this embodiment advantageously facilitates communication within SOA's.
[00058] In another embodiment of the present invention, intermediate computers collectively can implement a message mesh that provides message exchange according to a point-to-point paradigm. When exchanging point-to-point messages, a single sender sends a message to a single recipient. It is emphasized that as a result, QoS is provided for the exchange of messages according to the point-to-point paradigm. It is noted that switching messages from point to point is typically synchronous. The sender is aware of the recipient's identity, and vice versa. Both the sender and the receiver in general must be online in order to communicate. Message exchange from point to point is also known in the art as sending and receiving communication.
[00059] The message sending paradigms that can be provided by the message mesh that implements the present invention are not limited to the previous ones. Intermediate computers can collectively implement a message mesh that provides message exchange according to any of a wide variety of advanced message exchange paradigms. Additionally, the message mesh can implement multiple message exchange paradigms. For example, the same mesh of messages can provide both the exchange of messages according to the publishing / subscription paradigm and the exchange of messages according to a point-to-point paradigm.
[00060] In one embodiment of the present invention, the message mesh employs an overlap-based approach. Specifically, a set of intermediate computers are interconnected through an Application layer overlay network. QoS requirements are addressed through a set of resource scheduling and overlap routing mechanisms. The routing algorithm is an overlapping routing algorithm. The overlapping routing mechanisms can be operable to intelligently redirect messages to bypass a failed or congested network connection.
[00061] It is emphasized that a message mesh that advantageously implements the present invention is capable of managing the reliability and latency problems inherent to WAN's. Therefore, a message fabric that implements the present invention ensures that QoS requirements are satisfied even when the message fabric transmits messages over WAN's, including the public Internet. Additionally, so that a message grid to interconnect sensors 104 and actuators 106 over a large geographic area, it may be advantageous or necessary for the message grid to operate over WAN's, the public Internet, or both. Thus, the present invention advantageously allows sensors and actuators to be interconnected over a large geographical area while maintaining QoS standards.
[00062] Similarly, a message fabric implementing the present invention ensures that the QoS requirements are satisfied even when the message fabric transmits messages across heterogeneous networks.
[00063] In addition, message fabrics implementing the present invention can advantageously provide QoS even if the underlying networks employed by the message fabric fail to provide any QoS guarantees. This is possible since the present invention is capable of redirecting messages from intelligent way to bypass congested or failed network lines without requiring any intervention by the underlying networks. This can be achieved using overlap routing as described above. As the public Internet does not provide any guarantees for QoS, these properties beneficially allow the message fabrics implementing the present invention to be distributed, and to provide QoS, to the public Internet. Similarly, many VPN's known in the art do not provide QoS guarantees. These properties beneficially allow message meshes implementing the present invention to be distributed, and to provide QoS, for such VPN's.
[00064] Similarly, the present invention can advantageously provide QoS even without the control of the physical networks employed by the message mesh. Since applications typically cannot control the network behavior of a WAN, this property beneficially allows the message fabrics that implement the present invention to provide QoS over WAN's.
[00065] A message mesh implementing the present invention is beneficially scalable. Such a mesh of messages can connect large numbers of nodes, including sensors, actuators, or both, while maintaining QoS standards. This scaling capability is possible since, for the reasons noted above, each node only needs to be aware of a small number intermediate computers and each intermediate computer needs to be aware of only a small number of neighboring intermediate computers. Notably, the present invention does not require pairwise connections between each pair of entities through the system they wish to communicate with. Minimizing the number of direct connections is critical to the scalability of the system.
[00066] Turning now to FIG. 2, an example of a message path is illustrated.
[00067] The message path and the entities shown in FIG. 2 exist within an environment 102 such as the example environment shown in FIG. 1. In the environment example, a sensor 104 is configured to send event data to a processing element 108. The processing element is configured to receive and process this event data. The sensor and the processing element are knots. In addition, the sensor and the processing element are computers. The sensor is a publisher in a publish / subscribe system, and the processing element is a subscriber in the publish / subscribe system.
[00068] The sensor 104 is connected directly with the intermediate computer "A" 110a. The sensor is not connected directly to any other intermediate computer. The sensor and the intermediate computer "A" are located in the same message domain.
[00069] The processing element 108 is connected directly with the intermediate computer "C" 110c. As with the sensor, the processing element is not connected directly to any other intermediate computer. The processing element and the intermediate computer "C" are located in the same message domain. This message domain is different from the message domain including the sensor and the intermediate computer "A".
[00070] No direct connection exists between intermediate computer "A" 110a and intermediate computer "C" 110c. However, intermediate computer "A" is directly connected to intermediate computer "B" 110b. Intermediate computer "B" is directly connected to intermediate computer "C". Thus, the communication between the intermediate computer "A" and the intermediate computer "C" can be achieved by routing the communication through the intermediate computer "B".
[00071] A message path 202 is calculated to specify a route on which messages can travel through the interconnected intermediate computer network 110. The message path specifies a sequence of intermediate computers selected from the interconnected intermediate computer network. The sequence begins with an initial intermediate computer 110a connected with a sending computer 104. The initial intermediate computer and the sending computer can be included in the same message domain. The sequence ends with a final intermediate computer 110c connected with a receiving computer 108. The final intermediate computer and the receiving computer can be included in the same message domain.
[00072] In environment example 102, message path 202 specifies a sequence starting with intermediate computer "A" 110a. The next intermediate computer in the sequence is the intermediate computer "B" 110b. The sequence ends with the intermediate computer "C" 110c.
[00073] In one embodiment of the present invention, the message path is the complete routing path. The message path need not expressly specify the sending computer and the receiving computer, for example, the publisher and the subscriber. This is because the sending computer is directly connected to the initial intermediate computer and the receiving computer is directly connected to the final intermediate computer. Therefore, the message path is, in itself, sufficient to route to the sending computer and the receiving computer.
[00074] In another embodiment of the present invention, the message path is a subset of a wider routing path including elements external to the interconnected intermediary computer network. For example, a routing path can begin with the sending computer 104. The following elements in the routing path can be the intermediate computers 110 included in the message path in the specified order. The routing path can then end with the receiving computer 108.
[00075] The message path may expressly or implicitly define a sequence of message path segments 204. A message path segment begins with an intermediate computer in the sequence and ends with the subsequent intermediate computer in the sequence. Thus, message path 202 includes two message path segments. A message path segment 204ab begins with intermediate computer "A" 110a and ends with intermediate computer "B" 110b. Another message path segment 204bc begins with intermediate computer "B" 110b and ends with intermediate computer "C" 110c. Each message path segment can represent the network link 120 between the intermediate computers connected by the message path segment.
[00076] The message path can be calculated by one or more of the intermediate computers. Thus, routing decisions can be made by intermediate computers. In one embodiment of the present invention, the message path is calculated by the initial buffer computer 110a in the sequence. As noted above, this intermediate computer is directly connected to the sending computer.
[00077] Regardless, each intermediate computer 110 in the interconnected intermediate computer network can be configured to compute and install message paths as described above. As a result, each intermediate computer can calculate an appropriate message path for messages that originate from a sending computer to which the intermediate computer is connected. The intermediate computer can perform this calculation locally, for example, without having to consult any other intermediate computer. Therefore, a single point of failure in the pathmaking process is beneficially avoided.
[00078] The initial intermediate computer 110a in the message path can receive a message from sending node 104. The initial intermediate computer can direct the message to the second intermediate computer in the sequence. Each intermediate computer in the sequence, in turn, can direct the message to the next intermediate computer in the sequence. The final intermediate computer 110c can then direct the message to the receiving node. It is emphasized that the intermediate computers in the sequence are directing messages on behalf of the intermediate computers at the edges of the sequence.
[00079] Thus, in environment example 102, intermediate computer "A" 110a receives a message from sending node 104. Intermediate computer "A" directs the message to intermediate computer "B" 110b. Intermediate computer "B" directs the message to intermediate computer "C" 110c. Intermediate computer "C" directs the message to processing element 108.
[00080] Each intermediary computer 110 on the interconnected intermediary computer network can be configured to direct messages to neighboring intermediates. Appropriately, any broker who receives a message can direct the message to the next broker in the message path for the message.
[00081] Each intermediate computer 110 in the interconnected intermediate computer network can be configured to perform message mediation. Such message mediation can include format transformation. Format transformation can include translation between two different Extensible Markup Language (XML) schemes. Extensible Markup Language and XML are registered trademarks (registered in several countries) of the World Wide Web Consortium; W3C brands are registered and maintained by their host institutions MIT, ERCIM and Keio. For example, a publisher can send in an XML schema and the subscriber can expect a different XML schema.
[00082] In addition, intermediate computers can be configured to calculate 206 latency budgets. A latency budget is the amount of extra latency that can be tolerated if a QoS requirement specifying a maximum latency 208 must be satisfied. A statistical estimate 210 of the message path latency may have been calculated. In this case, the latency budget can be determined by subtracting the statistically estimated latency of the message path from the maximum latency. The latency budget can then be distributed among the message path segments.
[00083] For example, if the QoS requirements specify a maximum latency of 500 ms and the statistically estimated latency of the message path is 300 ms, the latency budget is 200 ms. This latency budget can be distributed between both 204ab, 204bc message path segments. The latency budget can be distributed according to a variety of techniques, provided that the sum of the assigned latency budget for each segment is not greater than 200 ms.
[00084] A message path segment can carry several types of traffic. Messages crossing the message path segment, message topics, or both may have different requirements for the opportunity. Appropriately, differential latency budgets can be dynamically specified for different messages or topics that divide the common message path segment. If two message paths have a common message path segment, and two messages are pending transmission through the common message path segment, the scheduling problem can be resolved by transmitting the message or the topic having the lowest latency budget first . The latency budget, therefore, may imply the priority of a message. Latency budgets thus can beneficially optimize the latency performance in each message path segment, subject to the end-to-end latency requirements of all messages or topics transmitted through the message path segment.
[00085] In one embodiment of the present invention, as described above, interconnected intermediate computers implement a publish / subscribe system. The sending computer is a publisher, or an end point of it, in the publish / subscribe system. The receiving computer is a subscriber, or an end point of it, in the publish / subscribe system.
[00086] An intermediate computer connected to a publisher is known as an intermediate computer that publishes. The intermediate computer that publishes can be located in the same message domain as the publisher.
[00087] Likewise, an intermediate computer connected with a subscriber is known as a subscription intermediate computer. The subscription intermediate computer can be located in the same message domain as the subscriber.
[00088] As described above, the publish / subscribe system can be based on topic. Each intermediate computer may be able to match publishers and subscribers on the same topic. The topic of a message can be specified as metadata associated with the message. Metadata can describe a common functionality of messages in the category identified by the topic. In one embodiment of the present invention, the topic is a column. The topic can be defined by the application that communicates through the publish / subscribe system. The topic can be any value that is mutually understood by the relevant publishers and subscribers.
[00089] Message paths calculated as described above can connect all intermediate computers that publish to a topic with all subscription intermediate computers for the same topic. For each message path, the publishing intermediate computer can be the starting intermediate computer, and the signing intermediate computer can be the final intermediate computer. The above statement can be repeated for each topic in the publish / subscribe system.
[00090] In addition, a single intermediate computer can direct messages to different topics. Latency budgets can be allocated to different topics in each message path segment in order to control local resource management. The middleman can manage the distribution of network resources among these topics based on these latency budgets.
[00091] More specifically, a variety of messages on different topics can be placed on the same request on the intermediate computer. The intermediate computer decides the order in which messages are transmitted based on the priority of the messages, which in turn depends on the topic's latency budget according to the algorithm described above.
[00092] A publisher and the subscriber who are in communication can be located in the different message domains 116. In particular, a publisher on a given topic and a subscriber for the same topic can be located on the different message domains. In this case, the message path can be calculated and used as described above.
[00093] A publisher and the subscriber who are communicating can instead be located in the same message domain 116. In particular, a publisher on a given topic and a subscriber for the same topic can be located on the same message domain. In this case, the middleman can directly direct messages between publishers and subscribers located in the same message domain.
[00094] Calculating and using the message path as described above can be omitted. Alternatively, this case can be expressed as a message path in which the sequence includes only a single intermediate computer that is connected with both the publisher and the subscriber.
[00095] A subscriber can connect with a subscription intermediate computer to request a topic. The subscription intermediate computer can analyze data located on it to determine if it already receives messages for the topic. If so, the subscription middleman can start simply by directing messages to the topic to the subscriber. If not, for example, if no node in the same message domain previously requested the topic, the subscription broker can propagate the topic requirement to other broker computers. An intermediate computer that receives the topic requirement can determine whether it is connected with a publisher for this topic. If so, the intermediate computer can store an indication that messages for this topic should be sent to the subscription intermediate computer that convey the topic requirement.
[00096] Information about requirements to subscribe to a topic last can spread through the entire network of intermediary computers. However, such propagation can be an iterative process. One iteration, two iterations, or more may be required before the topic requirement is received on any particular intermediate computer on the network. Regardless of this, an intermediate computer that publishes may eventually be aware of the identity of all subscribers to the information published by the publisher.
[00097] Turning now to FIG. 3, an example of a sequence of operations for transmitting data according to at least one quality of service requirement is demonstrated.
[00098] The sequence of operations shown in FIG. 3 transmits messages in accordance with at least one quality of service requirement. The QoS requirement or requirements can be any of a wide variety of standards that impact message transmission.
[00099] A QoS requirement may include a specification of the reliability with which messages are to be transmitted. Reliability can be specified as a maximum probability of failure to transmit a message. Thus, at least one quality of service requirement may include a maximum probability of failure to transmit the message.
[000100] A QoS requirement can also include a specification of the latency with which messages are to be transmitted. Latency can be specified as a maximum latency for transmitting a message. Thus, at least one quality of service requirement may include maximum latency for message transmission.
[000101] The sequence of operations shown in FIG. 3 can run on an intermediate computer, such as the intermediate computer shown in FIG. 7 or any of the intermediate computers shown in FIG. 1. The intermediate computer can be included in a network of interconnected intermediate computers, such as the network of intermediate computers shown in FIG. 1.
[000102] The intermediate computer that performs the sequence of operations can be connected with a sending computer. The sending computer can be a node as shown in FIG. 1. The sending computer can transmit one or more messages to the intermediate computer for retransmission to a receiving computer. The receiving computer can be a node as shown in FIG. 1. The intermediate computer can cause messages received from the sending computer to be relayed to the receiving computer. This retransmission can take place via one or more message paths as described below. The intermediate computer that performs the sequence of operations may be the initial intermediate computer in the message path or message paths, except where noted otherwise.
[000103] In one embodiment of the present invention, the sending computer is a publisher in a publish / subscribe system. The receiving computer is a subscriber to a publish / subscribe system.
[000104] The sequence of operations shown in FIG. 3 can run simultaneously on multiple intermediate computers included in the network. Each such intermediate computer can transmit a significant number of messages. It is emphasized that network congestion can occur as a result. The present invention includes techniques for handling this network congestion as described below.
[000105] In one embodiment of the present invention, messages are transmitted via a single path. This embodiment hereinafter is described as the one-way embodiment.
[000106] In another embodiment of the present invention, messages are transmitted using multipath routing as described above with respect to FIG. 1. This embodiment hereinafter is described as the multiple path realization.
[000107] It is noted that the subsequent description of the sequence of operations shown in FIG. 3 is performed for both previous embodiments, except when noted otherwise.
[000108] In calculation operation 302, a message path is calculated. The message path specifies a sequence of intermediate computers selected from the network of interconnected intermediate computers. The sequence begins with an initial intermediate computer connected to the sending computer. The sequence ends with a final intermediate computer connected to the receiving computer.
[000109] The message path can be statistically estimated to satisfy at least one quality of service requirement. In addition, if at least one quality of service requirement includes a maximum latency for message transmission, the latency of the message path is estimated statistically. The statistically estimated latency can be compared with the maximum enabled latency to ensure that the former is less than or equal to the latter.
[000110] In one embodiment of the present invention, calculation operation 302 includes the sequence of operations shown in FIG. 5 or a subset of it.
[000111] In the embodiment of a single path, the calculation operation 302 calculates a single message path as described above. The only calculated message path is statistically estimated to satisfy at least one quality of service requirement.
[000112] In the realization of multiple paths, the calculation operation 302 calculates a plurality of message paths. Each of the message paths is calculated as described above. The calculated plurality of message paths is estimated statistically to collectively satisfy at least one quality of service requirement.
[000113] The number of message paths calculated can be a parameter. This parameter can have a value of both. This parameter can also be specified by a system administrator. This parameter can also be selected to achieve a desired level of resilience. This selection can be based on estimates of the probabilities of failure of intermediate computers, network connections between intermediate computers, or both. These estimates can be based on one or more models of failure probabilities such as the failure models shown in FIG. 7. The minimum number of message paths that is sufficient to ensure that a QoS requirement specifying a maximum failure probability is satisfied can be calculated based on these estimates. The result can be used as the parameter. Thus, the number of message paths for multipath routing can be calculated based on the failure model or failure models.
[000114] The pluralities of message paths can be parallel to each other. In other words, the message paths can be configured in such a way that in the two message paths they transmit data about a common segment between two intermediate computers. For example, if the parameter for the number of message paths is equal to the number of neighboring intermediate computers to which the initial intermediate computer is connected, each message path can include a different neighboring intermediate computer. This beneficially ensures that a failure in the connection that connects the two intermediate computers does not cause multiple message paths to fail. Even if it is impossible or impracticable that all message paths are completely parallel, segments of the message paths can be parallel to each other.
[000115] Calculation operation 302 may include storing the calculated message path or plurality of message paths may be stored on a computer-readable storage medium. As a result, the message path or message paths can be retrieved in order to determine how to route messages subsequently received.
[000116] After calculation operation 302 is completed, it passes control to calculation operation 304.
[000117] In calculation operation 304, a latency budget is calculated. The calculation of the latency budget comprises subtracting a statistically estimated latency from the message path from the maximum latency. The statistically estimated latency can be the value calculated in calculation operation 302 as described above.
[000118] If the at least one quality of service requirement does not specify a maximum latency, the 304 calculation operation can be omitted.
[000119] Calculation operation 304 can perform the calculations described above for each message path calculated in calculation operation 302. Appropriately, in the realization of single path, calculation operation 304 performs the calculations described above for the only path calculated message. In the embodiment of multiple paths, calculation operation 304 performs the calculations described above for each of the calculated plurality of message paths.
[000120] After the calculation operation 304 is completed, it passes control to distribute the operation 306.
[000121] In distribution operation 306, the latency budget calculated in calculation operation 304 is distributed among the message path segments between intermediate computers specified by the message path. The 306 dispatch operation can equally divide the latency budget among the message path segments. The 306 dispatch operation can also proportionally divide the latency budget among the message path segments.
[000122] If the at least one quality of service requirement does not specify a maximum latency, the 306 distribution operation can be omitted.
[000123] Distribution operation 306 can perform the calculations described above for each message path calculated in calculation operation 302. Appropriately, in the embodiment of single path, distribution operation 306 performs the distribution described above for the only path calculated message. In the embodiment of multiple paths, the delivery operation 306 performs the distribution described above for each of the calculated plurality of message paths.
[000124] After the 306 distribution operation is completed, it passes control to the 308 distribution operation.
[000125] In the distribution operation 308, the message path calculated in the calculation operation 302 is distributed through the intermediate computers included in the message path. In one embodiment of the present invention, the current intermediate computer transmits a signaling message to any other intermediate computer included in the message path. The signaling message is a signal for each intermediate computer so a topic will be transmitted through that intermediate computer. The signaling message additionally signals that the messages received in the topic need to be directed to a specific intermediate computer. As a result of the signaling message, targeting states are configured in the targeting component of each intermediate computer included in the message path. After the 308 distribution operation is completed, it passes control to receive the 310 operation.
[000126] In receive operation 310, a message is received at the initial intermediate computer from the sending computer. After the reception operation 310 is completed, it moves from control to transmission operation 312.
[000127] In transmission operation 312, the message received in reception operation 310 is transmitted from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path.
[000128] The initial intermediate computer can invoke the transmission along the entire message path. However, the initial intermediate computer may itself be responsible for sending the message to the second intermediate computer in the sequence. As described above, each intermediate computer in the sequence, in turn, can direct the message to the next intermediate computer in the sequence. The final intermediate computer can direct the message to the receiving computer.
[000129] In one embodiment of the present invention, transmitting the message from the sending computer to the initial intermediate computer, between intermediate computers, from the final intermediate computer to the receiving computer, or any combination thereof is carried out in the layer of Application (level 7) of the Open Systems Interconnect (OSI) model. In another embodiment of the present invention, transmitting the message between the entities mentioned above is carried out at the Session layer (level 5) of the OSI model. In any case, an application, as opposed to the network layer (level 3) of the OSI model, is responsible for routing, redirecting and targeting as needed.
[000130] Transmission operation 312 can transmit the message through each message path calculated in calculation operation 302. Appropriately, in the embodiment of a single path, transmission operation 312 transmits the message according to the only path of message. In the embodiment of multiple paths, the transmission operation 312 transmits the message according to each of the calculated plurality of message paths. It is noted that in the latter case, duplicate messages can exist if the message paths are not completely parallel. In this case, intermediaries can remove duplicate messages to reduce overhead.
[000131] As noted above, network congestion can occur. In particular, a plurality of messages can be expected to be transmitted via a common message path segment between intermediate computers. In this case, the intermediate computer where the messages are waiting for transmission can perform the sequence of operations shown in FIG. 6 to determine the order in which messages are transmitted. The intermediate computer that performs the sequence of operations shown in FIG. 6 can be the intermediary computer that is executing the sequence of current operations or it can be any other intermediary included in the message path.
[000132] In the sequence of example operations shown in FIG. 3, after transmission operation 312 is complete, it passes control to receive operation 314. However, this is not inherently the case. Reception operation 310 and transmission operation 312 can be repeated for each of a plurality of messages before invoking reception operation 314. Conversely, reception operation 314 can be invoked even if reception operation 310 and operation transmission 312 were not performed in the event that no message requires transmission. Notably, the receive operation 314 can be performed at predefined time intervals, regardless of the number of messages transmitted in the transmit operation 312 since the previous iteration of the receive operation 314.
[000133] In reception operation 314, quality of service metrics over the interconnected intermediary computer network are received. The quality of service metric can include at least one resilience metric, at least one latency metric, or both.
[000134] Reception operation 314 may additionally include monitoring the interconnected intermediary computer network. To achieve this objective, the receive operation 314 can include the sequence of operations shown in FIG. 4 or a subset of it. The at least one resilience metric can be determined as described below with respect to FIG. 4.
[000135] Similarly, at least one latency metric can be determined as described below with respect to FIG. 4.
[000136] The intermediate computers included in the intermediate computer network can monitor periodically, chronically, or continuously to each other. To achieve both objectives, each intermediate computer can periodically, chronically or continuously perform the receive operation 314. This iteration of the receive operation 314 can include the execution of the sequence of operations shown in FIG. 4.
[000137] After the reception operation 314 is complete, it passes from control to determination operation 316.
[000138] In the determination operation 316, a determination is made as if the message path meets at least one quality of service requirement based on a quality of service metric received in the receive operation 314. The determination operation 316 you can also directly analyze network status measurements, such as the data described below with respect to FIG. 4.
[000139] The message path or the plurality of message paths can fail to satisfy the QoS requirement for any of a variety of reasons. For example, message path segments can develop network congestion, causing latency to increase.
[000140] In the realization of a single path, the determination operation 316 determines whether the single calculated message path satisfies at least one quality of service requirement.
[000141] In the realization of multiple paths, the determination operation 316 determines whether the calculated plurality of message paths collectively satisfies at least one quality of service requirement.
[000142] If it is determined that at least one quality of service requirement is satisfied, it passes from control to receive operation 310. Otherwise, it passes from control to calculation operation 302.
[000143] Appropriately, in the realization of a single path, if the message path is determined not to satisfy at least one quality of service requirement, the calculation operation 302 is repeated for a new message path specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network. The new message path is estimated statistically to satisfy at least one quality of service requirement.
[000144] In the realization of multiple paths, if the calculated plurality of message paths is determined not to collectively satisfy at least one quality of service requirement, the calculation operation 302 is repeated for a new plurality of message paths. Each of the new message paths specifies a new sequence of intermediate computers selected from the network of interconnected intermediate computers. The new plurality of message paths is estimated statistically to collectively satisfy at least one quality of service requirement.
[000145] If all message paths have failed, the determination operation 316 can also cause calculation operation 302 to be repeated for a new message path specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network . This can occur even if failures do not directly satisfy the QoS requirements.
[000146] A message path or a plurality of message paths can be left in place until QoS requirements are violated or until all message paths have failed.
[000147] It is noted that a change in the QoS requirements may not automatically cause the message paths to be recalculated. For example, if QoS requirements are changed to be strictly less stringent, changing QoS requirements cannot cause a message path to violate QoS requirements.
[000148] The intermediate computer can continue to proceed through the cycle shown in FIG. 3 until taken offline.
[000149] Turning now to FIG. 4, an example of a sequence of operations to receive quality of service metrics over the interconnected intermediary computer network is demonstrated.
[000150] As the term is used below, neighboring intermediate computers include those intermediate computers with a direct connection to this intermediate computer, for example, the intermediate computer that performs the sequence of operations shown in FIG. 4.
[000151] In monitoring operation 402, a state of at least one of the intermediate computers included in the interconnected intermediate computer network is monitored. The status information can be monitored for each neighboring intermediate computer.
[000152] The intermediate computer can be aware of whether each neighboring intermediate computer is up or down. This can be achieved by periodically sending ping messages to the neighboring intermediate computer. Thus, the intermediate computer can count the number of times each monitored intermediate computer was down, the duration for which each monitored intermediate computer was down, or both for the most recent measurement period.
[000153] After monitoring operation 402 is complete, it moves from control to monitoring operation 404.
[000154] In monitoring operation 404, a state of at least one message path segment between intermediate computers included in the interconnected intermediate computer network is monitored. Status information can be monitored for the message path segment between the intermediate computer and each neighboring intermediate computer. As the term is used here, a message path segment can include a network link between two intermediate computers even if the network link is not currently employed by any active message path.
[000155] The intermediate computer may be aware of whether each segment of the message path for which it is an end point is up or down. Thus, the intermediate computer can count the number of times each monitored message path segment was down, the duration for which each monitored message path segment was down, or both for the most recent measurement period.
[000156] After the monitoring operation 404 is complete, it moves from control to determination operation 406.
[000157] In determination operation 406, at least one resilience metric is determined based on the monitored state in monitoring operation 402 and monitoring operation 404.
[000158] The at least one resilience metric can include a failure probability for each intermediate computer monitored in monitoring operation 402. The at least one resilience metric can additionally include a failure probability for each monitored message path segment in 404 monitoring operation.
[000159] In one embodiment of the present invention, a moving average is taken from the resilience metric. Each new measurement can be measured along with the previous measurements. The average can be heavy. The information related to the moving average can be stored and described in any of a variety of data structures known in the art, including arrays, lists and matrices.
[000160] After the 406 determination operation is complete, it moves from control to monitoring operation 408.
[000161] In monitoring operation 408, a latency of at least one message path segment between intermediate computers included in the interconnected intermediate computer network is monitored. Latency can be measured for each neighboring intermediate computer, for example, each intermediate computer to which this intermediate computer is connected. After monitoring operation 408 is complete, it moves from control to determination operation 410.
[000162] In determination operation 410, at least one latency metric is determined based on the monitored state in monitoring operation 408. In one embodiment of the present invention, a moving average is taken from the latency metric. The moving average can be calculated as described above. The at least one latency metric can also include the average latency of messages sent on a specified topic during the most recent measurement window. After the determination operation 410 is complete, it passes control to the propagation operation 412.
[000163] It is noted that monitoring operation 402, monitoring operation 404 and determination operation 406 can be performed separately if only the resilience metric is required, for example, if the QoS requirements do not specify a maximum latency. Similarly, monitoring operation 408 and determination operation 410 can be performed separately if only the latency metric is required, for example, if the QoS requirements do not specify a minimum reliability.
[000164] In propagation operation 412, any or all of the previous data is propagated to at least one other intermediary on the network. Previous data can include at least one resilience metric, at least one latency metric, any of the raw data collected, or any combination of them.
[000165] Each intermediate computer can combine propagated data received from a plurality of other intermediate computers. As a result, every intermediary can eventually acquire data over the entire interconnected intermediary computer network. This data can include latency and probability of failure (for example, reliability) for each message path segment on the network. This data can also include the probability of failure for each intermediate computer on the network. These data can be stored in an array, a data set or any of a variety of suitable data structures known in the art.
[000166] This data can be used by any intermediate computer on the network for subsequent computation of the message path. Notably, this data can be used by an intermediate computer connected to a publisher in order to compute a message path for each intermediate computer connected with a subscriber on the same topic.
[000167] After the 412 propagation operation is complete, the sequence of operations shown in FIG. 4 is complete. If the operations shown in FIG. 4 were included in the receiving operation 314 in FIG. 3, this operation can summarize the processing. The quality of service metric received in receive operation 314 can include the resilience metric determined in determination operation 406, the latency metric determined in determination operation 410, or both.
[000168] Turning now to FIG. 5, an example of a sequence of operations for calculating a message path is demonstrated.
[000169] The sequence of operations shown in FIG. 5 can run on an intermediate computer, such as the intermediate computer shown in FIG. 7 or any of the intermediate computers shown in FIG. 1. The intermediate computer may be included in a network of interconnected intermediate computers, such as the network of intermediate computers shown in FIG. 1.
[000170] The calculation step performed in calculation operation 302 in FIG. 3 can comprise the sequence of operations shown in FIG. 5 or a subset of it.
[000171] The sequence of operations example shown in FIG. 5 assumes that the applicable QoS requirements for the message include both the reliability requirement and a latency requirement. Specifically, at least one quality of service requirement includes a maximum probability of failure to transmit the message and a maximum latency for transmission of the message. Those skilled in the art can modify the operations shown in FIG. 5 to address other sets of QoS requirements.
[000172] As described above, each intermediate computer can already have a significant amount of data on the interconnected intermediate computer network. Notably, this data can include reliability and latency data for the network. Each intermediate computer can additionally have a graphical data structure that expresses the structure of the interconnected intermediate computer network. The algorithm implemented by the sequence of operations shown in FIG. 5 can process this data set to determine the optimal message paths in the manner described below.
[000173] In the selection operation 502, a set of one or more message paths is selected such that the one or more message paths included in the set are statistically estimated to satisfy the maximum latency for the transmission of the message.
[000174] Selection operation 502 can compute the one or more message paths according to a shorter k path algorithm. The algorithm can be applied to the chart data structure and the latency data described above.
[000175] After the 502 selection operation is complete, it moves from control to the 504 estimate operation.
[000176] In estimation operation 504, a probability of failure to transmit the message from each of the message paths in the set of one or more message paths is estimated statistically.
[000177] In one embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on a combined failure probability to transmit the message by each of the intermediate computers in the message path. An intermediary computer will be unable to transmit the message if the network connection between itself and the next intermediary computer in the sequence (or the receiving computer in the case of the final intermediary) has failed. Therefore, this estimate can be calculated based on the probability of failure of the relevant network connections. The relevant network connections include the network connections between any two adjacent intermediate computers in the sequence. Relevant network connections may also include the network connection between the sending computer and the starting intermediate computer, the network connection between the final intermediate computer and the receiving computer, or both. The estimate can be additionally based on the calculated failure probability of the intermediate computers in the sequence itself.
[000178] In another embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on a correlated failure probability.
[000179] In another embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on one or more models of failure probabilities. The failure probability models can be the failure models shown in FIG. 7. It is emphasized that as a result, the computation of routing paths can consider failure models in estimating the availability of message paths.
[000180] Statistically estimating the probabilities of failure based on the failure model or failure models can be performed to ensure that at any point in time, the probability that at least one path exists between a pair of publication and subscription intermediaries exceeds one target limit. The threshold can be one minus a maximum probability of failure specified by the QoS requirements.
[000181] Additionally, any or all of the three previous embodiments can be combined. Thus, statistically estimating the probability of failure to get the message across can be based on a combination of the factors noted above.
[000182] After the 504 estimate operation is complete, it moves from control to 506 selection operation.
[000183] In selection operation 506, at least one candidate message path from the set of one or more message paths is selected such that the at least one candidate message path is statistically estimated to satisfy the maximum failure probability for convey the message. Selection operation 506 is based on the statistically estimated probability of failure to transmit the message. It is emphasized that the at least one selected candidate message path satisfies the resilience requirement while minimizing the cost, for example, in terms of the time to convey the message. After the 506 selection operation is complete, it moves from control to the 508 estimation operation.
[000184] In estimation operation 508, the expected failure probability of at least one candidate path selected in selection operation 506 is estimated statistically. If a candidate path has been selected, the estimate operation 508 can simply determine the probability of failure for the individual message path as calculated in the estimate operation 504. If two or more candidate paths were selected, the estimate operation 508 in instead you can calculate the probability of failure of candidate paths as a set. This calculation may be based in part on a probability of correlated failures between different candidate message paths.
[000185] After the estimation operation 508 is completed, the sequence of operations shown in FIG. 5 is complete. If the operations shown in FIG. 5 were included in calculation operation 302 in FIG. 3, this operation can summarize the processing. In the single path embodiment, the calculation operation 302 in FIG. 3 can select any of the candidate message paths as the only calculated message path. In the multipath embodiment, the calculation operation 302 in FIG. 3 can select any or all of the candidate message paths for inclusion in the calculated plurality of message paths.
[000186] In one embodiment of the present invention, the interconnected intermediary computer network implements a publish / subscribe system as described above. The sequence of operations shown in FIG. 5 can be repeated for each intermediate computer connected with any subscriber on a specific topic. The sequence of operations shown in FIG. 5 can also be repeated for each intermediate computer connected with any subscriber on any topic in the system. In any case, the paths to individual subscription intermediaries can be merged into a mesh structure combining common message path segments or network connections.
[000187] Turning now to FIG. 6, an example of a sequence of operations for ordering a plurality of messages awaiting transmission through a common message path segment between intermediate computers is demonstrated.
[000188] The sequence of operations shown in FIG. 6 can run on an intermediate computer, such as the intermediate computer shown in FIG. 7 or any of the intermediate computers shown in FIG. 1. The intermediate computer may be included in a network of interconnected intermediate computers, such as the network of intermediate computers shown in FIG. 1. The intermediate computer can be the same intermediate computer on which the plurality of messages are waiting for transmission.
[000189] The common message path segment may be, or may represent, a network link or any other type of coupling that connects two or more intermediate computers included in the interconnected intermediate computer network.
[000190] In the selection operation 602, a target message is selected from the plurality of messages pending transmission through the common message path segment between intermediary computers included in the interconnected intermediary computer network such that the target message has a smaller budget latency among the plurality of messages. After the 602 selection operation is complete, it moves from control to the 604 prioritization operation.
[000191] In prioritization operation 604, the target message selected in selection operation 602 is prioritized for transmission. It is emphasized that as a result, a topic with a lower latency budget is assigned a higher priority. After the 604 prioritization operation is complete, it moves from control to the 606 determination operation.
[000192] In determination operation 606, it is determined whether one or more messages are waiting for transmission through the common message path segment. The determination operation 606 does not consider any message that has already been prioritized in the prioritization operation 604 but has not yet been transmitted. If it is determined that one or more messages are waiting for transmission, it passes from control to selection operation 602. Otherwise, the sequence of operations shown in FIG. 6 is complete.
[000193] Messages can be transmitted in the order in which messages were prioritized in the 604 prioritization operation. For example, the first message prioritized in the prioritization of the 604 prioritization operation can be transmitted first. The priority can be enforced by a broadcast scheduler based on priority or based on relaxation.
[000194] Turning now to FIG. 7, an example of intermediate computer 110 for transmitting data according to at least one quality of service requirement is illustrated.
[000195] The intermediate computer 110 is coupled with a network of interconnected intermediate computers to transmit data according to at least one quality of service requirement 702. The network of interconnected intermediate computers can be as shown in FIG. 1.
[000196] The at least one quality of service requirement 702 may include a maximum probability of failure 704 to transmit the message.
[000197] The at least one quality of service requirement 702 may additionally include a maximum latency 706 for the transmission of the message.
[000198] The intermediate computer 110 comprises a calculation unit 708. The calculation unit configured to calculate a message path specifying a sequence of intermediate computers selected from the interconnected intermediate computer network. The sequence starts with an initial intermediate computer connected to a sending computer. The sequence ends with a final intermediate computer connected to a receiving computer. The message path is statistically estimated to satisfy at least one quality of service requirement 702. To perform the above, the calculation unit can be configured to perform calculation operation 302 in FIG. 3.
[000199] In the embodiment of multiple paths, the calculating unit 708 is additionally configured to calculate a plurality of message paths.
[000200] In one embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on a combined failure probability to transmit the message by each of the intermediate computers in the message path.
[000201] In one embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on a correlated failure probability.
[000202] In one embodiment of the present invention, statistically estimating the failure probability to transmit the message is based on one or more models of failure probabilities 710. The models of failure probabilities can be known simply as failure models. Failure models can express the probability of failure independent of intermediate computers, networks and network connections. Failure models can also express the probability of correlated failures.
[000203] A 710 fault model can be any one of a wide variety of model types. Models can include statistics that estimate the probability of independent failures, correlated failures, or both.
[000204] Failure models can be built according to any of a wide variety of techniques. Failure probabilities can be learned from historical measurement. For example, a specific number of subsequent measurement periods can be analyzed to determine the number of times a network connection was down, the number of times an intermediate computer was down, and the like. Failure probabilities can also be learned from external data sources and external failure models.
[000205] A failure model can be represented as a probability distribution on the intermediate computers, the message path segments, or both. In this case, the message path calculation can use the model to estimate current failure probabilities.
[000206] A failure model, for example, may be based on the frequency and magnitude of earthquakes across a geographic area, for example, in Southern California.
[000207] Additionally, any or all of the three previous embodiments can be combined. Thus, statistically estimating the probability of failure to get the message across can be based on a combination of the factors noted above.
[000208] In one embodiment of the present invention, the calculating unit 708 is further configured to select a set of one or more message paths such that the one or more message paths included in the set are statistically estimated to satisfy maximum latency 706 for the transmission of the message. The calculation unit is additionally configured to statistically estimate a probability of failure to transmit the message from each of the message paths in the set of one or more message paths. The calculation unit is additionally configured, based on the statistically estimated probability of failure to transmit the message, to select at least one candidate message path from the set of one or more message paths such that the at least one message path from candidate is estimated statistically to satisfy the maximum probability of failure 704 to transmit the message. To perform the above, the calculation unit can be configured to perform the sequence of operations shown in FIG. 5 or a subset of it.
[000209] Intermediate computer 110 additionally comprises a budget unit 712. The budget unit configured to calculate a latency budget for a message path calculated by the 708 calculation unit. The calculation of the latency budget comprises subtracting a statistically estimated latency from the path from the maximum 706 latency. The budgeting unit is additionally configured to distribute the latency budget among message path segments among intermediate computers specified by the message path. To accomplish this, the budgetary unit can be configured to perform calculation operation 304 and distribution operation 306 in FIG. 3.
[000210] The intermediate computer 110 further comprises a transmission unit 714. The transmission unit is configured to transmit a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by a message path calculated by calculation unit 708. To perform the above, the transmission unit can be configured to perform transmission operation 312 in FIG. 3.
[000211] In the embodiment of multiple paths, the transmission unit 714 is additionally configured to transmit the message according to each of the plurality of message paths calculated by the calculation unit 708.
[000212] The intermediate computer 110 additionally comprises a receiving unit 716. The receiving unit is configured to receive quality of service metrics over the interconnected intermediate computer network. To effect the above, the receiving unit can be configured to perform receiving operation 314 in FIG. 3.
[000213] Receiving unit 716 can be additionally configured to monitor the network of interconnected intermediate computers. To achieve this goal, the receiving unit can be further configured to perform the sequence of operations shown in FIG. 4 or a subset of it.
[000214] In one embodiment of the present invention, receiving the quality of service metric over the interconnected intermediate computer network includes monitoring a state of at least one of the intermediate computers included in the interconnected intermediate computer network and at least one path path segment. message between intermediary computers included in the interconnected intermediary computer network. Receiving quality of service metrics over the interconnected intermediary computer network additionally includes determining at least one resilience metric based on the monitored state. The quality of service metric includes at least one resilience metric.
[000215] In another embodiment of the present invention, receiving the quality of service metric over the interconnected intermediate computer network includes monitoring a latency of at least one message path segment between intermediate computers included in the interconnected intermediate computer network. Receiving the quality of service metric over the interconnected intermediary computer network also includes determining at least one latency metric based on the monitored state. The quality of service metric includes at least one latency metric.
[000216] Additionally, the two previous embodiments can be combined. In this case, the quality of service metric includes both at least one resilience metric and at least one latency metric.
[000217] Intermediate computer 110 further comprises a determination unit 718. The determination unit is configured to determine whether a message path calculated by calculation unit 708 satisfies at least one quality of service requirement 702 based on a metric quality of service received by the receiving unit 714. The unit of determination is further configured to make the calculation unit 708 calculate a new message path by specifying a new intermediary computer sequence selected from the interconnected intermediary computer network if the message path is determined not to satisfy at least one quality of service requirement. The new message path is estimated statistically to satisfy at least one quality of service requirement. To effect the above, the determination unit can be configured to perform determination operation 316 in FIG. 3.
[000218] In the multi-path embodiment, the determination unit 718 is further configured to determine whether the plurality of message paths calculated by the calculation unit 708 collectively meets at least one quality of service requirement 702. The determination unit is configured additionally to cause the calculation unit to calculate a new plurality of message paths if the calculated plurality of message paths is determined not to collectively satisfy at least one quality of service requirement.
[000219] The intermediate computer 110 additionally comprises a prioritization unit 720. The prioritization unit is configured to select a target message from a plurality of messages pending transmission through a common message path segment between intermediate computers included in the interconnected intermediary computer network such that the target message has a lower latency budget among the plurality of messages. The prioritization unit is additionally configured to prioritize the target message for transmission. To accomplish this, the prioritization unit can be configured to perform the sequence of operations shown in FIG. 6.
[000220] The intermediate computer 110 further comprises a configuration unit 722. The configuration unit is configured to configure the intermediate computer in which it is included. The configuration unit can be a software program or computer program product or a subset of it. The configuration unit can be configured to accept user input to allow a user or administrator to control and specify the intermediate computer's configuration, including any of the parameters and rules described below.
[000221] The configuration unit 722 can be configured to determine the other intermediate computers in the interconnected intermediate computer network to which this intermediate computer 110 is connected. Thus, the configuration unit can be configured to control the network topology as it pertains to this intermediate computer.
[000222] The topology of the network between intermediate computers, including the selection from which intermediate computers are directly connected with which other intermediate computers, can be determined according to any of a wide variety of methods and factors. Such factors may include network quality between the intermediate computers. Network quality can include physical proximity between intermediate computers. Thus, intermediate computers can be directly connected with those intermediate computers that are positioned relatively close together.
[000223] Such factors may also include security policies and administrative policies. Specifically, rules can specify minimum security requirements for intermediate computers to which this intermediate computer can be directly connected. Trust relationships between intermediate computers can be specified, with connections being created only between two intermediate computers between which such a trust exists.
[000224] The configuration unit 722 can be additionally configured to configure the parameter specifying the number of message paths for multipath routing as described above. This parameter can be received as user input.
[000225] Turning now to FIG. 8, a network model for an embodiment of the present invention is illustrated. Achievement is message-driven middleware that provides end-to-end QoS assurance in wide area publish / subscribe communication.
[000226] Embodiment is an overlay-based messaging system that can manage end-to-end QoS, in terms of latency, throughput and availability, in publish / subscribe communications based on application requirements. This is achieved through a holistic set of overlapping route and maintenance mechanisms, which actively exploit the diversity of network paths and redirect traffic through connections with good quality, for example, low latency and high availability. In order to deal with failures and network dynamics, the implementation continuously monitors the quality of the connection and adapts the routes whenever their quality deteriorates below the application requirements. The realization also leverages resource scheduling capabilities at the underlying data transport layer, and uses a new budget designation scheme to control its scheduling behavior. We have fully implemented the implementation and evaluated its performance on a real test bed. Our experimental results confirmed that the implementation can effectively provide end-to-end QoS over wide area networks despite the fact that the underlying networks provide only best-effort connectivity and are inherently dynamic.
[000227] We are witnessing major transformations for the enterprise computing landscape. One of such transformations is the increasing awareness of real world conditions and events through massive shipping, control and analytical capabilities, leading to a proliferation of cyber physical systems (CPS). Another major transformation is the interoperation and growing interconnection of business systems over a wide, widely distributed area triggered by business practices such as mergers and acquisitions, off-shoring, outsourcing, and the formation of virtual companies. The second transformation has triggered an emerging engineering discipline around the systems system (SoS). CPS and SoS introduced new non-functional requirements in message-oriented middleware (MOM). Specifically, MOM must be aware of and must satisfy the unique quality of service (QoS) needs of these new systems in order to be practically useful.
[000228] Consider physical cyber systems being developed for a wide variety of application domains ranging from the smart grid of electricity to environmental monitoring and smart transportation. Bulky event sensor data needs to be transported from sensor fields to back-end business servers for complex event processing and integration with business processes. Sensor data is generally time sensitive because the correct data that arrives too late becomes the wrong data. Therefore, sensor data must be transported in a reliable and very responsive manner. Similarly, control directives carried out in the reverse direction of traffic can trigger several mission-critical systems. Control directives may have strict requirements on distribution and security performance in order to avoid catastrophic consequences. On the other hand, the communication infrastructure for sensor data and control directives presents a number of challenges. Sensors are generally deployed in potentially hostile environments, making sensors more prone to malicious attacks and natural hazards. In addition, sensors are connected via wireless connections that are inherently weak. There can be a high degree of variability in wireless bandwidth due to mobile obstructions, RF interference, and weather. There may also be periods of intermittent disconnections. Such characteristics can be very difficult for MOM to effectively address the CPS QoS requirements.
[000229] In the realm of systems, constituent systems can be distributed over a large geographic area, for example, by a nation or even covering multiple constituents. Messages between systems generally need to travel a long communication path, incurring a much greater delay than exchanging messages from the local area. It is also more difficult for a long-range communication path to maintain high availability due to the increased number of nodes and connections on the way. Additionally, the systems are likely to be distributed and operated by separate organizations, which result in different security properties and degrees of reliability to be associated with these systems. Despite the technical challenges arising from the communication infrastructure, many SoS applications require messaging capabilities with certain guarantees in a range of QoS metrics including latency, throughput, availability and security.
[000230] The implementation is designed to combine the best of business message exchange and real-time message exchange to suit the needs of the emerging SoS and CPS paradigms. Specifically, the implementation facilitates the interconnection of different message domains across large geographic areas and heterogeneous network infrastructure, and provides compatibility and interoperability with de facto message exchange standards including both the Java ™ Message Service (JMS) standard and the Data Distribution Service for standard Real-Time Systems ™ (DDS ™). Data Distribution Service for Real-Time Systems and DDS are either registered trademarks or trademarks of Object Management Group, Inc. in the United States of America and / or other countries. An outstanding feature of the implementation is the holistic provision of predictable and reliable QoS effectively addressing network and system dynamics, heterogeneity and failure conditions. Allows the specification of required performance properties (ie, latency and throughput), availability and reliability models, and security restrictions separately for each message topic or connection session; it additionally transports messages through autonomously administered domains respecting the above requirements from end to end.
[000231] We focus on the provision of end-to-end latency QoS to materialize in the context of MoM for wide area federated domains. This is achieved through an integrated approach that combines overlap routing and message programming techniques to manage network latency and processing latency respectively. In particular, overlap routing mechanisms actively exploit diversity in network paths and redirect messages over these connections with good quality, for example, low latency and high availability. In order to deal with failures and network dynamics, the implementation continuously monitors the quality of the connection and adapts the routes whenever their quality deteriorates below the application requirements. The realization also levels the resource scheduling capabilities in the data transport layer, and employs a new budget allocation scheme to adapt to short-term network dynamics. Our experiment results demonstrate that implementation can effectively manage end-to-end latency with respect to application requirements despite the dynamics in wide area networks.
[000232] Our work targets that emerge from intelligent systems that incorporate cyber infrastructure into the physical world with massive detection, processing and control capabilities. Examples of such systems include Smart Grid for electricity distribution, smart city management and smart transport. In all of these applications, a large number of sensors and actuators are distributed in the field, and they must be interconnected with event processing and analytical capabilities on the back end. A wide variety of event data and control policies are transported by different nodes in real time. This requires a message exchange service that supports different communication paradigms, such as point to point, multicast and publish / subscribe. While the system we develop support for all these communication paradigms, we focus on the publish / subscribe aspect, since it is the fundamental mechanism for asynchronous communication in distributed systems.
[000233] We assume that sensor nodes can be grouped for many local domains, and there is an intermediate node within each domain. These intermediaries are interconnected through an overlay network and collectively provide the service of publication / subscription messages. Each endpoint node, such as a sensor, actuator or processing element, is attached with the local intermediary. There can be an arbitrary number of topics in the system, which can be defined either through administrative tools or dynamically using programming APIs. Each endpoint can publish and subscribe to one or multiple topics, while each intermediary can perform publish / subscribe correspondence, transport messages to local endpoints or neighboring intermediaries, and optionally perform message mediation (for example, format transformation). Compared to the traditional approach using a single intermediary or a grouping of intermediates, our overlap-based approach provides several architectural benefits as follows: Scalability: Each node needs to know only the local intermediary, while each intermediary only communicates with one small number of neighboring intermediaries. In this way, we can avoid keeping connections in tandem, which is prohibitively expensive as the system escalates. Federation: The system is likely to be distributed and operated jointly by multiple organizations. In such a federated scenario, it is critical that each administrative domain can independently manage access from / to its own nodes, which can be easily facilitated by local intermediaries. Heterogeneity: Sensors are inevitably heterogeneous in a large-scale system. It is difficult, if possible, for any intermediary to understand all the protocols used by different nodes. With an overlap, intermediaries can agree on a canonical protocol with each other, and use a few adapters to communicate with the local sensor nodes.
[000234] Within each local domain, the sensor and actuator nodes can be connected with the intermediary in a variety of ways, for example, wireless sensor networks. We focus on providing Quality of Service (QoS) guarantees within the network of overlapping intermediaries.
[000235] Providing predictable Quality of Service (QoS) is an essential requirement for mission-critical applications. In particular, the message exchange service must be able to ensure reliable and timely delivery of critical messages, such as an emergency alert or a real-time control command. Formally stated, our goal is to provide QoS-aware publish / subscribe service in terms of message latency and distribution rate among all corresponding pairs of publishers and subscribers. Specifically, each topic is associated with a maximum delay that your messages can tolerate, and our system seeks to maximize the rate of message distribution over time, that is, the percentage of messages that appear before their respective deadline. We consider the latency requirement by topic for ease of presentation. Our system can be easily extended to provide different QoS for individual publishers and subscribers.
[000236] Note that the end-to-end delay for a given message consists of both the processing delay at each intermediary and the communication delay between adjacent intermediaries. The former is affected by the load (that is, message arrival process) of an intermediary, while the latter is affected by the characteristics of the network connections. The broker processing delay also varies with time as each broker dispatches messages on multiple topics, and messages can arrive in bursts. Additionally, since the sensors and actuators are distributed over a large geographical area, they will inevitably operate over wide area networks, where the quality of the connection fluctuates due to the dynamic traffic load. While some applications may employ dedicated networks, in general we assume that the underlying network provides any guarantee of QoS. Such a relaxed network model allows our system to be applicable in different distribution scenarios, but it also has challenges for our project since the The message exchange service must deal with such network and system dynamics, and ensure that the end-to-end latency requirement is continuously satisfied.
[000237] Turning now to FIG. 9, an example of route establishment within the embodiment is demonstrated. It is noted that in FIG. 9, numbers indicate the sequence of an operation.
[000238] We use two basic techniques to satisfy the end-to-end latency requirement: 1) use overlapping routing to bypass a congested network link or an overloaded intermediary, 2) schedule the transmission of different messages on each intermediary accordingly with your deadlines. However, in a publish / subscribe system where each topic can have many publishers and subscribers widely distributed, there are a few non-trivial challenges. First, how to locate all publishers and subscribers to a given topic in a distributed manner, and how to establish and adapt overlapping routes between switches in response to network dynamics such as intermediates and congested or failed connections Second, how can we coordinate scheduling decisions with intermediaries along a route to achieve end-to-end latency
[000239] To address these challenges, we take an integrated QoS approach that combines overlap routing and message scheduling, which take care of two components in end-to-end delay, namely network latency and processing latency. To distribute messages, intermediaries first exchange control messages to locate other intermediaries who have subscribers for topics they publish on. Each broker also employs a monitoring agent that keeps track of its processing latency and network latency for neighboring brokers. These measurement messages are exchanged between intermediaries to find overlap routes that satisfy end delay for end requirements.
[000240] To adapt latency changes of medium or short term magnitude, we use a latency budget allocation technique that specifies the latency budget allowed on each hop, including both processing and network latencies. The intermediary schedules message transmissions such that each message is distributed to the next hop intermediary within that latency budget. When processing or network latencies increase at one intermediary, the system can reduce some budget at other intermediaries and increase the budget at this intermediary, such that the end-to-end delay is still satisfied. However, when changes in latency go beyond what can be manipulated by shifting the budget, new routing paths are computed to avoid congested calls or overloaded intermediaries.
[000241] For simplicity, we assume that the intermediate overlay topology is relatively stable. Intermediaries maintain long-term links between them. These intermediaries and bonds can fail, but in general intermediaries do not join or leave the overlap frequently. This assumption is reasonable in many application scenarios since the distribution of the intermediary only changes over very rough timescales (for example, once every few weeks). In cases where intermediaries do often come together and leave, a topology maintenance scheme is necessary to adjust the topology of the network. We leave this problem for future study.
[000242] In general, there are two approaches to routing, called link state (for example, OSPF, such as OSPF Version 2 as defined by RFC 2328) and distance vector (for example, RIP, such as RIP Version 2 as defined by RFC 2453). While each approach has its own merits, our project follows the linkage state that is most appropriate for our specific context, which we will explain later. We also employ several techniques to support QoS in distributed publish / subscribe communication.
[000243] Each end point can subscribe to any topic at any time. Such signatures are sent to the local intermediary to which this end point is attached. Each broker maintains a local subscription table to record which topics each local endpoint subscribes to. The intermediaries then propagate these topics to other intermediaries. As a result, each broker knows what topics any other broker needs; keeps such information in a remote subscription table.
[000244] When an endpoint publishes a message on a topic, say T, the message is sent to the local intermediary. This intermediary first checks the local subscription table and transmits it to all local T subscribers. It also checks the remote subscription table to find all remote intermediaries who subscribe to T, and sends the message to these intermediaries using the overlap routes. . Upon receipt of this message, these intermediaries additionally direct to their respective local subscribers. In this way, the message will eventually reach all T topic subscribers in the system.
[000245] Intermediaries periodically warn connection states, including the processing latency measured for each topic, and the network latency for each of its neighbors. Such latency measurements are propagated to all other intermediaries through a single neighboring targeting mechanism. Thus, each intermediary has a local copy of the network map, that is, the topology with latency measurements for all nodes and connections.
[000246] An intermediary also employs a monitoring agent to measure processing and network latencies. Periodically detonates neighboring intermediaries to obtain network latency. We use Exponentially Weighted Moving Averaging (EWMA) to avoid sudden spikes and drops in measurements. On the other hand, if a neighbor fails to respond to three consecutive ping messages, it is considered to have failed and the connection latency is marked as ™ (infinite). The monitoring agent also keeps track of the broker's processing latency. Both delay measurements are included in the connection status warning so that each intermediary can construct a complete network map.
[000247] In OSPF, each node, independently, runs Dijkstra's algorithm on the network map to determine the shortest path to each other node, and then populates its routing table appropriately. We do not directly apply this method to our intermediary overlay due to the need to control the latency budget for QoS. As each node on a route makes independent and possibly different decisions on how to reach the destination, end-to-end routes change frequently; no single node can control the route. This makes it very difficult to apply the budget allocation technique on a hop-by-hop basis.
[000248] Instead, we employ a new source routing scheme, where a publisher intermediary computes the routes locally for all destinations (ie, corresponding subscribers), and uses a signaling protocol to configure these routes. Specifically, the source node sends a route establishment message (RT_EST) to its next hop neighbor on a route. The RT_EST message contains the topic name and all intermediaries on the route.
[000249] Upon receipt of this message, an intermediary first checks whether it is the destination on the route. If so, it sends an acknowledgment to the node upstream from which it receives this message. Otherwise, it extracts its own next hops from the routes and directs this RT_EST message to its next hop intermediary. When a node receives an acknowledgment from its downstream broker, it inserts the <topic, next_hop> pairs into its routing table, and then recognizes it for its own upstream node. In this way, finally the source node receives recognition and the path is established, as shown in FIG. 9.
[000250] We have further improved the resilience of constructed paths by allowing applications to request the construction of multiple concurrent paths for each destination. The publisher broker first computes multiple paths, ordered by their respective delays and starting from one with the least delay. The first is chosen, so each subsequent path is compared with all the previous chosen paths to see if it is disunited for all of them. Only one that is disunited is chosen as the next path. In this way, we can find multiple ways to improve both end-to-end resilience and delay. This is similar with shortest path algorithms k.
[000251] To summarize briefly, our scheme differs from OSPF in two fundamental aspects: 1) In OSPF, each node independently decides its next hop nodes. In our scheme, the source node decides all routes. 2) In OSPF, a new link status warning can trigger an intermediate node to update its routing table, thus changing the routes from end to end. In our scheme, once the routes are established, they remain fixed until the source node shatters them. To adapt to the network dynamics, we employ a route maintenance mechanism powered by QoS.
[000252] The embodiment updates the overlap routes only when they cannot satisfy the latency requirement. This can happen when the route is interrupted by network interruption or intermediary failure, or when the quality of the route deteriorates when the intermediaries are overloaded or the network is congested. All of these cases can be easily detected by a source node, as it receives warning of connection status from all other intermediaries (assuming that the overlap is not partitioned by the failures). Specifically, when a source node receives a link state update, it checks whether the reported latency affects any of its routes. If you do this, it updates the end-to-end latency of current routes and compares it to the latency requirement. If the requirement is still satisfied, no action is taken. Otherwise, it again computes a new set of routes and establishes them using the signaling protocol as described above.
[000253] When routes need to be updated, a task similar to route establishment is performed, with the difference that routing tables are updated incrementally. In particular, the source computes the delta path between the previous and current paths and sends a route establishment message (RT_EST) that contains the list of new connections as well as the list of obsolete connections. Upon receipt, a node will perform a similar operation as stated above, that is, direct (RT_EST) to current and new nodes downstream, but just wait for responses from its new nodes downstream. As long as acknowledgments are received, the routing table is updated with the new destinations downstream and released from its new connections removed. This technique ensures that no flows are interrupted while the updated process is performed.
[000254] Message scheduling is another important QoS mechanism that we employ. It complements overlap routing through proactive management of network resources along established routes.
[000255] Although each intermediary can run a programmer to manage their local requests, this does not always lead to globally optimal results. Each of the multiple intermediaries through which a message passes through can dispatch messages independently from each other, which does not necessarily meet the required end-to-end delay. Although a centralized algorithm can collect request behavior (eg, arrival process, steady states) from all intermediaries and make decisions, such information changes quickly and is difficult to maintain.
[000256] We apply a heuristic algorithm where a latency margin, the difference between the delay requirement and the current end-to-end delay, is divided among all intermediaries. Each intermediary will have some "temporary storage" to absorb sudden increases in latency, provided that they are small enough compared to the margin.
[000257] Consider an intermediate B that is currently on the following routes for a set of topics TI, T2, ..., TI. Let Di be the end-to-end latency requirement for the Ti topic. The route to the Ti topic has Ki hops, and the latency measured at each jump is d !, where 1 <j <Ki.
[000258] Our intuition is to give higher priority to these topics where end-to-end latency is approaching the call. To do this, we calculate end-to-end latency for each topic (say Ti) as:

[000259] We equally divide this margin of latency from end to end among the Ki jumps on the route. So the jump latency margin for the IT topic is:

[000260] Now intermediate B can sort topics in an increasing order of their latency margin per jump. That is, the first topic has the lowest margin, so it should have the highest priority. Since relaxation-based programming is used by the broadcast request, a high priority can be enforced by assigning a small latency budget to this topic. In general, for the nth topic in the classified list, we can designate a latency budget as (where δ is a step parameter):

[000261] We need to highlight that the equal division among the intermediaries is a simpler form of budget allocation.
[000262] It allows coordinated programming behavior through intermediaries, such that messages close to their delay call receive preferential treatment. We left the differentiated division of the margin between intermediaries as future work.
[000263] Turning now to FIG. 10, an implementation of the WMB flow in each overlapping intermediate in the embodiment is illustrated.
[000264] We have implemented our system within IBM's WebSphere® Message Broker (WMB) development platform. WebSphere is a registered trademark of International Business Machines Corporation, Armonk, New York, United States of America, United States of America, other countries, or both. WMB introduces the concepts of message flows; a message flow comprised of one or more incoming connections, a message processing component and one or more outgoing connections. Inbound connections are used by local domain applications to access the realization. Our implementation significantly simplifies the process of accessing the message exchange service for local domain applications using the Java message exchange service (JMS) API. Thus, applications that already access a message exchange service through JMS can readily switch to message exchange according to the embodiment, while for legacy applications, JMS transformers can be easily embedded. Finally, incoming and outgoing connections are also established to interconnect intermediaries over the wide area network.
[000265] The implementation control mechanism lies between the incoming and outgoing connections, the manipulation of the process of routing the various messages to the appropriate outgoing connections. In this way, WMB acts as the integration agent between the delivery routing control layer and the data transport layer. Therefore, the routing control layer of the embodiment remains decoupled from any specific transport.
[000266] As discussed above, the embodiment uses the JMS API publish / subscribe messages. To facilitate message targeting, the embodiment defines a different topic namespace and naming convention to make a clear distinction between (i) topics from and intended for local domain applications and (ii) topics that come to from and intended for WAN overlay intermediaries. The embodiment will then handle the topic name transformation from the local domain to WAN overlay. More precisely, in the local domain a global topic name T is transformed to the form / src / T when directed to the embodiment and / dst / T when sent from the embodiment. In the WAN overlay, topic T will be transformed according to the destination as / destID / T. This new targeting approach significantly simplifies the routing process by directly leveling the underlying publish / subscribe infrastructure by removing the requirement for a separate targeting protocol. Additionally, it can be readily used among different publish / subscribe engines in addition to the implementation of the JMS.
[000267] The overall project is illustrated in FIG. 10 where the current WMB flow components of the embodiment are shown. Two inbound JMS components are noted, one that subscribes to local domain topic application publications (JMSInput_LAN) and one for messages that arrive from remote intermediaries (JMSInput_WAN). Message topics from the LAN are transformed via the Sensor Adapter component for internal names as designated by the embodiment. Then, these messages along with incoming wide area messages are directed to the routing component that maintains routing destinations by topic. A deduplication component removes possible duplicate messages received at the local node that can occur in the case of multipath routing. Finally, similar to incoming messages, outgoing JMS components are used to publish local domain (JMSOutput_LAN) and wide area messages (JMSOutput_WAN) according to destinations provided by the routing component of the embodiment.
[000268] Turning now to FIG. 11, a graph of the end-to-end delay for both the embodiment and the direct link is shown.
[000269] To understand the performance of our system, we use IBM Research Cloud and report some preliminary results for our system. We instantiated 20 Linux VMs to form the overlay for the realization. To reflect wide area network delays, we use AT&T measurements to define the network delay on each overlap link. Each node has its own corresponding location. The 20 nodes are distributed across the United States of America.
[000270] Like the initial experiment, we compared the end-to-end delay between two intermediate nodes when (i) they use a direct link and (ii) using the QoS routing embodiment. We set up the publisher application on the node 9 (located in LA) and the subscriber application on node 19 (in Seattle). Firstly, we measured the message distribution delay from end to end over the direct link, which has an average delay of 100 ms and a variance of 10 ms. We let the publisher send 10 messages per second and measure the end-to-end delay for multiple runs. Then we use routing provided by the implementation and repeat the same experiments. To study how the implementation behaves with different network delays on alternate paths, we vary the network latency on the alternative path from 40 ms to 140 ms in the 20 ms steps, with 10% variance. This simulates cases where alternating paths may have different and greater delays.
[000271] FIG. 11 shows the end-to-end comparison when the delay in the alternate path changes. Initially, the alternative path has less delay. Since the implementation can level paths with less delay and distribute messages earlier, the end-to-end delay is less than that of the direct link. When the delay on the alternate path increases, the delay from end to end gradually increases. When the delay in the alternate path exceeds that of the direct link, the end-to-end delay of the embodiment becomes slightly greater. And it becomes flat when the delay on the alternate path continues to increase. This is because in such cases the embodiment uses the direct link for distribution. Even without better alternative paths, the implementation achieves performance similar to that of the direct link.
[000272] We present the design and implementation of an embodiment that provides a resilient and QoS aware messaging system. The embodiment builds an overlay network at the top of the physical topology and provides a new fusion of routing, scheduling and budget allocation delay to maintain the QoS requirements of event-driven applications. The implementation allows for path adaptation and reconfigurations when as many network interruptions as excessive delays occur along a distributed path. We have fully implemented the implementation, distributed a prototype on a large-scale network and verified the feasibility and advantages of our approach.
[000273] Currently, we are looking for several improvements and extensions for the implementation. We are extending our path computing algorithms to accommodate multiple dimensions of QoS in parallel. In addition, we plan, in our future work, to support the construction of dynamic topology and adaptation as we unite and leave the overlap in order to optimize the available connectivity to improve the output of path computing and the level of resilience. Finally, we plan to integrate the mediation functionality into the implementation to allow applications to perform various types of action on messages such as transformations and filtering.
[000274] As will be appreciated by one skilled in the art, one or more aspects of the present invention can be incorporated as a computer program system, method or product. Suitably, one or more aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment that combines aspects of software and hardware that in general can all be referred to here as a "circuit," "module" or "system". In addition, one or more aspects of the present invention may take the form of a computer program product incorporated in one or more computer-readable media having computer-readable program code incorporated therein.
[000275] Any combination of one or more computer-readable media can be used. The computer-readable medium can be a computer-readable storage medium. A computer-readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared or semiconductor device, apparatus or system, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer-readable storage medium include the following: an electrical connection having one or more wires, a portable floppy disk, a hard disk, a random access memory (RAM), a memory read-only (ROM), erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a read-only portable compact disc (CD-ROM) memory, an optical storage device, a magnetic storage, or any suitable combination of the above. In the context of this document, a computer-readable storage medium can be any tangible medium that can contain or store a program for use by or in connection with a device, apparatus and instruction execution system.
[000276] A computer-readable signal medium may include a data signal propagated with computer-readable program code incorporated therein, for example, in the baseband or as part of a carrier wave. Such a propagated signal can take any of a variety of forms, including, but not limited to, electromagnetic, optical, or any suitable combination thereof. A computer-readable signal medium can be any computer-readable medium that is not a computer-readable storage medium and that can communicate, propagate, or carry a program for use by or in connection with a device, device and system instruction execution.
[000277] Program code embedded in a computer-readable medium can be transmitted using an appropriate medium, including, but not limited to, wireless, wired, fiber optic cable, RF, etc., or any suitable combination of the above.
[000278] Computer program code to perform operations for one or more aspects of the present invention can be written in any combination of one or more programming languages, including an object-oriented programming language such as Smalltalk, C ++ or the like, and conventional procedural programming languages, such as the "C" programming language or similar programming languages. Readable program code can run entirely on the user's computer, partially on the user's computer, as a remote software package, partially on the user's computer and partially on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer can be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection can be made to a computer (for example, over the Internet using an Internet Service Provider).
[000279] Aspects of the invention are described here with reference to flowchart illustrations and / or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and / or block diagrams, and combinations of blocks in the flowchart illustrations and / or block diagrams, can be implemented by the computer readable program instructions. These computer-readable program instructions can be provided for a general-purpose computer processor, special-purpose computer, or other programmable data processing device to produce a machine, such as instructions, which run through the computer's processor or other programmable data processing apparatus, create means to implement the functions / acts specified in the flowchart and / or block or blocks of the block diagram.
[000280] These computer-readable program instructions can also be stored on a computer-readable storage medium that can direct a computer, a programmable data processing device, and / or other devices to function in a particular way, such that the computer-readable storage medium having instructions stored therein comprises a manufacturing article including instructions that implement aspects of the function / act specified in the flowchart and / or block or blocks of the block diagram.
[000281] Computer readable program instructions can also be loaded onto a computer, another programmable data processing device, or another device to cause a series of operational steps to be performed on the computer, another programmable device, or another device to produce a process implemented by a computer, such that the instructions that execute on the computer, another programmable device, or another device implement the functions / acts specified in the flowchart and / or block or blocks of the block diagram.
[000282] The flowchart and block diagrams in the Figures illustrate the architecture, functionality and operation of possible implementations of systems, methods, and computer program products in accordance with various embodiments of the present invention. In this sense, each block in the flowchart or block diagrams can represent a module, segment, or portion of instructions, which comprises one or more executable instructions to implement the specified logical functions. In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession, in fact, can be executed substantially concurrently, or the blocks can sometimes be executed in reverse order, depending on the functionality involved. It will also be noted that each block in the block diagrams and / or flowchart illustration, and combinations of blocks in the block diagrams and / or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or specified acts or perform combinations of computer instructions and special purpose hardware.
[000283] The flow diagrams shown here are examples only. They can have many variations for these diagrams or the steps (or operations) described here without departing from the spirit of the invention. For example, steps can be performed in a different order, or steps can be added, deleted or modified. All of these variations are considered a part of the claimed invention. Additionally, the use of the terms one, one, etc. it does not denote a quantity limitation, but instead denotes the presence of at least one of the referenced item.
[000284] While the preferred embodiments of the invention have been described, it will be understood that those skilled in the art, both now and in the future, may take various improvements and refinements that are within the scope of the claims that follow. These claims must be interpreted to maintain the appropriate protection for the invention described first.

权利要求:
Claims (22)
[0001]
1. Method for transmitting data according to one or more quality of service requirements for a message topic, characterized by comprising: calculating a message path by specifying a sequence of intermediate computers selected from a network of interconnected intermediate computers, a sequence of intermediary computers including intermediary publishers that publish messages with the message topic and subscription intermediaries that receive messages with the message topic, the sequence beginning with an initial intermediate computer connected to a sending computer, the sequence ending with an end intermediate computer connected with a receiving computer, the message path being statistically estimated to satisfy the one or more quality of service requirements; transmitting a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path, the message including the message topic as metadata; receive quality of service metrics on the interconnected intermediary computer network; determine whether the message path meets one or more quality of service requirements based on the quality of service metric; and if the message path is determined not to satisfy one or more quality of service requirements, repeat the calculation step for a new message path specifying a new sequence of intermediate computers selected from the interconnected intermediate computer network, the new message path being statistically estimated to satisfy the one or more quality of service requirements for the message topic.
[0002]
2. Method, according to claim 1, characterized by the fact that the one or more quality of service requirements includes a maximum probability of failure to transmit the message.
[0003]
3. Method, according to claim 2, characterized by the fact that: o one or more quality of service requirements includes maximum latency for the transmission of the message; and the calculation step comprises: selecting a set of one or more message paths such that the one or more message paths included in the set are statistically estimated to satisfy the maximum latency for the message transmission, statistically estimating a failure probability for transmit the message from each of the message paths in the set of one or more message paths, and based on the statistically estimated probability of failure to transmit the message, select one or more candidate message paths from the set of one or more message paths message such that the one or more candidate message paths are statistically estimated to satisfy the maximum probability of failure to transmit the message.
[0004]
4. Method, according to claim 3, characterized by the fact that statistically estimating the probability of failure to transmit the message is based on a combined probability of failure to transmit the message by each of the intermediate computers in the message path.
[0005]
5. Method, according to claim 3, characterized by the fact that statistically estimating the failure probability to transmit the message is based on at least one of a correlated failure probability and a failure probability model.
[0006]
6. Method, according to claim 1, characterized by the fact that the one or more quality of service requirements include maximum latency for the transmission of the message.
[0007]
Method according to claim 6, characterized in that it further comprises: calculating a latency budget, in which calculating the latency budget comprises subtracting a statistically estimated latency from the message path from the maximum latency; and spreading the latency budget across message path segments among intermediate computers specified by the message path.
[0008]
Method according to claim 7, characterized in that it further comprises: selecting a target message from a plurality of messages pending transmission through a common message path segment between intermediate computers included in the interconnected intermediate computer network such that the target message has a lower latency budget among the plurality of messages; and prioritize the target message for transmission.
[0009]
9. Method, according to claim 1, characterized by the fact that: the calculation step calculates a plurality of message paths; the transmission step transmits the message according to each of the calculated plurality of message paths; the determination step determines whether the calculated plurality of message paths collectively satisfy one or more quality of service requirements; and repeating the calculation step if the calculated plurality of message paths is determined not to collectively satisfy one or more quality of service requirements.
[0010]
10. Method, according to claim 1, characterized by the fact that: receiving quality of service metrics over the interconnected intermediate computer network includes: monitoring the status of one or more of the intermediate computers included in the interconnected intermediate computer network and one or more message path segments between intermediary computers included in the interconnected intermediary computer network, and determine one or more resilience metrics based on the monitored state; and the quality of service metric includes one or more resilience metrics.
[0011]
11. Method according to claim 1, characterized by the fact that: receiving quality of service metrics over the interconnected intermediate computer network includes: monitoring a latency of one or more message path segments between intermediate computers included in the network interconnected intermediate computers, and determine one or more latency metrics based on the monitored state; and the quality of service metric includes one or more latency metrics.
[0012]
12. Intermediate computer coupled with a network of interconnected intermediate computers to transmit data according to one or more quality of service requirements, characterized by comprising: a calculation unit configured to calculate a message path specifying a sequence of selected intermediate computers a from the interconnected intermediary computer network, the sequence of intermediary computers including intermediary publishers that publish messages with the message topic and subscription intermediaries that receive messages with the message topic, the sequence beginning with an initial intermediary computer connected with a sending computer , the sequence ending with a final intermediate computer connected with a receiving computer, the message path being statistically estimated to satisfy one or more quality of service requirements; a transmission unit configured to transmit a message from the initial intermediate computer to the receiving computer through the sequence of intermediate computers specified by the message path, the message including the message topic as metadata; a reception unit configured to receive quality of service metrics over the interconnected intermediary computer network; and a unit of determination configured to determine whether the message path meets one or more quality of service requirements based on the quality of service metric, and whether the message path is determined not to satisfy one or more quality requirements service, to make the calculation unit calculate a new message path by specifying a new sequence of intermediate computers selected from the interconnected intermediary computer network, the new message path being statistically estimated to satisfy one or more service requirements. service quality.
[0013]
13. Intermediate computer according to claim 12, characterized by the fact that the one or more quality of service requirements include a maximum probability of failure to transmit the message.
[0014]
14. Intermediate computer, according to claim 13, characterized by the fact that: the one or more quality of service requirements include maximum latency for the transmission of the message; and the calculation unit is additionally configured to: select a set of one or more message paths such that the one or more message paths included in the set are statistically estimated to satisfy the maximum latency for message transmission, statistically estimate a probability of failure to transmit the message from each of the message paths in the set of one or more message paths, and based on the statistically estimated probability of failure to transmit the message, select one or more candidate message paths from the set of one or more more message paths such that the one or more candidate message paths are statistically estimated to satisfy the maximum probability of failure to transmit the message.
[0015]
15. Intermediate computer according to claim 14, characterized by the fact that statistically estimating the failure probability to transmit the message is based on a combined failure probability to transmit the message by each of the intermediate computers in the message path.
[0016]
16. Intermediate computer, according to claim 14, characterized by the fact that statistically estimating the failure probability to transmit the message is based on at least one of a correlated failure probability and a failure probability model.
[0017]
17. Intermediate computer, according to claim 12, characterized by the fact that the one or more quality of service requirements include maximum latency for the transmission of the message.
[0018]
18. Intermediate computer, according to claim 17, characterized by the fact that it additionally comprises a budget unit configured to: calculate a latency budget, in which calculating the latency budget comprises subtracting a statistically estimated latency from the message path to from maximum latency; and spreading the latency budget across message path segments among intermediate computers specified by the message path.
[0019]
19. Intermediate computer, according to claim 18, characterized by the fact that it additionally comprises a prioritization unit configured to: select a target message from a plurality of pending transmission messages through a common message path segment between intermediate computers included in the interconnected intermediate computer network such that the target message has a lower latency budget among the plurality of messages; and prioritize the target message for transmission.
[0020]
20. Intermediate computer, according to claim 12, characterized by the fact that: the calculation unit is additionally configured to calculate a plurality of message paths; the transmission unit is further configured to transmit the message according to each of the calculated plurality of message paths; and the unit of determination is further configured to determine whether the calculated plurality of message paths collectively satisfy one or more quality of service requirements, and whether the calculated plurality of message paths is determined not to collectively satisfy one or more requirements quality of service, to make the calculation unit calculate a new plurality of message paths.
[0021]
21. Intermediate computer, according to claim 12, characterized by the fact that: receiving quality of service metrics over the interconnected intermediary computer network includes: monitoring a state of one or more of the intermediary computers included in the interconnected intermediary computer network and one or more message path segments between intermediate computers included in the interconnected intermediate computer network, and determining one or more resilience metrics based on the monitored state; and the quality of service metric includes one or more resilience metrics.
[0022]
22. Intermediate computer according to claim 12, characterized by the fact that: receiving quality of service metrics around the interconnected intermediate computer network includes: monitoring a latency of one or more message path segments between included intermediate computers on the interconnected intermediary computer network, and determine one or more latency metrics based on the monitored state; and the quality of service metric includes one or more latency metrics.

类似技术:

---

公开号 | 公开日 | 专利标题

---

BR112012012942B1|2020-12-08|system and method for providing quality of service in a wide area message factory

---

US10673741B2|2020-06-02|Control device discovery in networks having separate control and forwarding devices

---

CN104426766B|2019-03-15|The end-to-end network path of dynamic across multiple network layers is established

---

US9461877B1|2016-10-04|Aggregating network resource allocation information and network resource configuration information

---

Ghosh et al.2013|Scalable multi-class traffic management in data center backbone networks

---

US9705750B2|2017-07-11|Executing data stream processing applications in dynamic network environments

---

US8259620B2|2012-09-04|Self-healing communication trees

---

US20180302343A1|2018-10-18|System and method for convergence of software defined network | and network function virtualization |

---

Abts et al.2012|A Guided Tour through Data-center Networking: A good user experience depends on predictable performance within the data-center network.

---

US20140086065A1|2014-03-27|Disjoint multi-paths with service guarantee extension

---

Yang et al.2014|Traffic uncertainty models in network planning

---

US10855575B2|2020-12-01|Adaptive traffic routing in a software-defined wide area network

---

Yang et al.2009|Message-oriented middleware with QoS awareness

---

Lin et al.2016|Jointly optimized QoS-aware virtualization and routing in software defined networks

---

WO2019068247A1|2019-04-11|Modeling access networks as trees in software-defined network controllers

---

Gomes et al.2016|Bandwidth-aware allocation of resilient virtual software defined networks

---

Li et al.2019|BOND: Flexible failure recovery in software defined networks

---

US10511524B2|2019-12-17|Controller communications in access networks

---

US20200336379A1|2020-10-22|Topology-aware controller associations in software-defined networks

---

Johnston et al.2011|Motivation, design, deployment and evolution of a guaranteed bandwidth network service

---

Chen et al.2012|Comet: Decentralized complex event detection in mobile delay tolerant networks

---

Subedi et al.2018|SDN‐based fault‐tolerant on‐demand and in‐advance bandwidth reservation in data center interconnects

---

Ghosh et al.2021|A centralized hybrid routing model for multicontroller SD‐WANs

---

Wang2015|Management of Temporally and Spatially Correlated Failures in Federated Message Oriented Middleware for Resilient and QoS-Aware Messaging Services.

---

Babarczi2017|CA15127 RECODIS

同族专利:

---

公开号 | 公开日

---

US20110125921A1|2011-05-26|

---

GB201210971D0|2012-08-01|

---

US8489722B2|2013-07-16|

---

GB2489140B|2016-01-27|

---

KR20120123262A|2012-11-08|

---

TW201145040A|2011-12-16|

---

WO2011066043A1|2011-06-03|

---

BR112012012942A2|2020-06-23|

---

GB2489140A|2012-09-19|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

---

US5995503A|1996-06-12|1999-11-30|Bay Networks, Inc.|Method and apparatus for providing quality of service routing in a network|

---

WO1998058501A1|1997-06-16|1998-12-23|Telefonaktiebolaget Lm Ericsson|A telecommunications performance management system|

---

US6813272B1|1999-06-23|2004-11-02|Korea Telecommunication Authority|QoS-based routing method|

---

US7260635B2|2000-03-21|2007-08-21|Centrisoft Corporation|Software, systems and methods for managing a distributed network|

---

US20020087699A1|2000-07-31|2002-07-04|Telefonaktiebolaget Lm Ericsson |Dynamic QoS management in differentiated services using bandwidth brokers, RSVP aggregation and load control protocols|

---

US7257120B2|2000-11-17|2007-08-14|Altera Corporation|Quality of service based supervisory network for optical transport systems|

---

EP1248431B1|2001-03-27|2007-10-31|Sony Deutschland GmbH|Method for achieving end-to-end quality of service negotiation for distributed multimedia applications|

---

US7068667B2|2001-04-27|2006-06-27|The Boeing Company|Method and system for path building in a communications network|

---

US7587517B2|2002-07-08|2009-09-08|Precache Inc.|Packet routing via payload inspection for quality of service management|

---

US7200144B2|2001-10-18|2007-04-03|Qlogic, Corp.|Router and methods using network addresses for virtualization|

---

US7406537B2|2002-11-26|2008-07-29|Progress Software Corporation|Dynamic subscription and message routing on a topic between publishing nodes and subscribing nodes|

---

US20030135556A1|2001-12-14|2003-07-17|International Business Machines Corporation|Selection of communication strategies for message brokers or publish/subscribe communications|

---

US8122118B2|2001-12-14|2012-02-21|International Business Machines Corporation|Selection of communication protocol for message transfer based on quality of service requirements|

---

US7113796B2|2002-01-18|2006-09-26|Microsoft Corporation|Framework and method for QoS-aware resource discovery in mobile ad hoc networks|

---

US7529263B1|2002-01-19|2009-05-05|Ucentric Systems, Inc.|Local area-networked system having intelligent traffic control and efficient bandwidth management|

---

US7725590B2|2002-04-19|2010-05-25|Computer Associates Think, Inc.|Web services broker|

---

US7764617B2|2002-04-29|2010-07-27|Harris Corporation|Mobile ad-hoc network and methods for performing functions therein based upon weighted quality of service metrics|

---

US6968374B2|2002-07-03|2005-11-22|Telefonaktiebolaget Lm Ericsson |Quality of service mechanism in an internet protocol network|

---

US7499404B2|2002-08-30|2009-03-03|Nortel Networks Limited|Distributed quality of service routing|

---

US6937591B2|2003-02-27|2005-08-30|Microsoft Corporation|Quality of service differentiation in wireless networks|

---

GB0305066D0|2003-03-06|2003-04-09|Ibm|System and method for publish/subscribe messaging|

---

JP2008527848A|2005-01-06|2008-07-24|テーベラ・インコーポレーテッド|Hardware-based messaging appliance|

---

US20060224668A1|2005-03-10|2006-10-05|International Business Machines Corporation|Methods and apparatus for efficiently placing stream transforms among broker machines comprising an overlay network in a publish-subscribe messaging system|

---

US7463637B2|2005-04-14|2008-12-09|Alcatel Lucent|Public and private network service management systems and methods|

---

US8683078B2|2006-03-07|2014-03-25|Samsung Electronics Co., Ltd.|Method and system for quality of service control for remote access to universal plug and play|

---

US8442030B2|2007-03-01|2013-05-14|Extreme Networks, Inc.|Software control plane for switches and routers|

---

EP2238804A4|2007-07-13|2012-05-02|Nortel Networks Ltd|Quality of service control in multiple hop wireless communication environments|

---

CN101355492B|2007-07-27|2011-04-13|华为技术有限公司|Routing method and system for access protocol of simple objects as well as relevant equipment|

---

EP2179549B1|2007-08-09|2012-03-21|Markport Limited|Network resource management|

---

JP2009055327A|2007-08-27|2009-03-12|Hitachi Ltd|Network system|

---

US20090154397A1|2007-12-17|2009-06-18|Nortel Networks Limited|System and method for providing quality of service enablers for third party applications|WO2009151863A2|2008-06-10|2009-12-17|Myers Wolin, Llc|A network gateway for time-critical and mission-critical networks|

---

US8397138B2|2009-12-08|2013-03-12|At & T Intellectual Property I, Lp|Method and system for network latency virtualization in a cloud transport environment|

---

US8661080B2|2010-07-15|2014-02-25|International Business Machines Corporation|Propagating changes in topic subscription status of processes in an overlay network|

---

US8589536B2|2010-08-02|2013-11-19|International Business Machines Corporation|Network monitoring system|

---

US8738704B2|2010-09-07|2014-05-27|Xerox Corporation|Publish/subscribe broker messaging system and method|

---

WO2012055111A1|2010-10-29|2012-05-03|Nokia Corporation|Method and apparatus for distributing published messages|

---

US8843580B2|2011-02-20|2014-09-23|International Business Machines Corporation|Criteria-based message publication control and feedback in a publish/subscribe messaging environment|

---

US8793322B2|2011-02-20|2014-07-29|International Business Machines Corporation|Failure-controlled message publication and feedback in a publish/subscribe messaging environment|

---

US9021131B2|2011-03-24|2015-04-28|Red Hat, Inc.|Identifying linked message brokers in a dynamic routing network|

---

US9313159B2|2011-03-24|2016-04-12|Red Hat, Inc.|Routing messages exclusively to eligible consumers in a dynamic routing network|

---

US9137189B2|2011-03-24|2015-09-15|Red Hat, Inc.|Providing distributed dynamic routing using a logical broker|

---

US9225637B2|2011-04-15|2015-12-29|Architecture Technology, Inc.|Border gateway broker, network and method|

---

US9444887B2|2011-05-26|2016-09-13|Qualcomm Incorporated|Multipath overlay network and its multipath management protocol|

---

US8995338B2|2011-05-26|2015-03-31|Qualcomm Incorporated|Multipath overlay network and its multipath management protocol|

---

US9124482B2|2011-07-19|2015-09-01|Cisco Technology, Inc.|Delay budget based forwarding in communication networks|

---

US9432218B2|2011-07-28|2016-08-30|Red Hat, Inc.|Secure message delivery to a transient recipient in a routed network|

---

US8885502B2|2011-09-09|2014-11-11|Qualcomm Incorporated|Feedback protocol for end-to-end multiple path network systems|

---

WO2013059683A1|2011-10-19|2013-04-25|The Regents Of The University Of California|Comprehensive multipath routing for congestion and quality-of-service in communication networks|

---

US9256714B2|2011-11-09|2016-02-09|International Business Machines Corporation|Preserving integrity of messages in a messaging oriented middleware system|

---

US8813205B2|2012-02-06|2014-08-19|International Business Machines Corporation|Consolidating disparate cloud service data and behavior based on trust relationships between cloud services|

---

US20140012929A1|2012-06-15|2014-01-09|Life of Two|Delivering messages over multiple communication paths|

---

US9451393B1|2012-07-23|2016-09-20|Amazon Technologies, Inc.|Automated multi-party cloud connectivity provisioning|

---

US9252915B1|2012-08-15|2016-02-02|Washington State University|Systematic adaptation of data delivery|

---

US8990301B2|2012-08-22|2015-03-24|International Business Machines Corporation|Broker designation and selection in a publish-subscription environment|

---

CN105009475B|2012-12-13|2019-01-18|华为技术有限公司|In view of the ambulant method and system predicted for admission control and Resource Availability of user equipment |

---

US9455919B2|2012-12-14|2016-09-27|Huawei Technologies Co., Ltd.|Service provisioning using abstracted network resource requirements|

---

US9426075B2|2013-03-12|2016-08-23|Huawei Technologies Co., Ltd.|Method and system to represent the impact of load variation on service outage over multiple links|

---

US9584387B1|2013-03-15|2017-02-28|Google Inc.|Systems and methods of sending a packet in a packet-switched network through a pre-determined path to monitor network health|

---

KR20140137573A|2013-05-23|2014-12-03|한국전자통신연구원|Memory management apparatus and method for thread of data distribution service middleware|

---

CN103534988B|2013-06-03|2017-04-12|华为技术有限公司|Publish and subscribe messaging method and apparatus|

---

CN105379317B|2013-06-14|2019-05-28|微软技术许可有限责任公司|Method and system based on neighbouring social activity interaction|

---

US20150032495A1|2013-07-25|2015-01-29|Futurewei Technologies, Inc.|System and Method for User Controlled Cost Based Network and Path Selection across Multiple Networks|

---

US10257287B2|2013-08-28|2019-04-09|Physio-Control, Inc.|Real-time data distribution system for patient monitoring devices, cardiac defibrillators and associated information delivery systems|

---

US10587509B2|2014-02-04|2020-03-10|Architecture Technology Corporation|Low-overhead routing|

---

US20150257081A1|2014-02-04|2015-09-10|Architecture Technology, Inc.|Hybrid autonomous network and router for communication between heterogeneous subnets|

---

US9369360B1|2014-05-12|2016-06-14|Google Inc.|Systems and methods for fault detection in large scale networks|

---

US9680919B2|2014-08-13|2017-06-13|Software Ag Usa, Inc.|Intelligent messaging grid for big data ingestion and/or associated methods|

---

US10075365B2|2014-08-27|2018-09-11|Raytheon Company|Network path selection in policy-based networks using routing engine|

---

US9774654B2|2015-02-02|2017-09-26|Linkedin Corporation|Service call graphs for website performance|

---

US9544403B2|2015-02-02|2017-01-10|Linkedin Corporation|Estimating latency of an application|

---

EP3082315B1|2015-04-18|2017-02-15|Urban Software Institute GmbH|Computer system and method for message routing|

---

US10165095B2|2015-06-22|2018-12-25|Rockwell Automation Technologies, Inc.|Active report of event and data|

---

US10225219B2|2016-02-22|2019-03-05|International Business Machines Corporation|Message delivery in a message system|

---

US10326617B2|2016-04-15|2019-06-18|Architecture Technology, Inc.|Wearable intelligent communication hub|

---

US10833881B1|2017-11-06|2020-11-10|Amazon Technologies, Inc.|Distributing publication messages to devices|

---

US11025745B2|2018-06-28|2021-06-01|Intel Corporation|Technologies for end-to-end quality of service deadline-aware I/O scheduling|

---

US11184266B1|2020-05-14|2021-11-23|PubNub, Inc.|Method and system for detecting latency in a wide area network|

法律状态:
2020-06-30| B11A| Dismissal acc. art.33 of ipl - examination not requested within 36 months of filing|

---

2020-07-07| B04C| Request for examination: application reinstated [chapter 4.3 patent gazette]|

---

2020-07-14| B06F| Objections, documents and/or translations needed after an examination request according [chapter 6.6 patent gazette]|

---

2020-07-21| B06U| Preliminary requirement: requests with searches performed by other patent offices: procedure suspended [chapter 6.21 patent gazette]|

---

2020-11-10| B09A| Decision: intention to grant [chapter 9.1 patent gazette]|

---

2020-12-08| B16A| Patent or certificate of addition of invention granted|Free format text: PRAZO DE VALIDADE: 10 (DEZ) ANOS CONTADOS A PARTIR DE 08/12/2020, OBSERVADAS AS CONDICOES LEGAIS. |

优先权:

---

申请号 | 申请日 | 专利标题

---

US12/625,437|2009-11-24|

---

US12/625,437|US8489722B2|2009-11-24|2009-11-24|System and method for providing quality of service in wide area messaging fabric|

---

PCT/US2010/053032|WO2011066043A1|2009-11-24|2010-10-18|System and method for providing quality of service in wide-area messaging fabric|

---