ACCELERATING STREAM PROCESSING BY DYNAMIC NETWORK AWARE TOPOLOGY RE-OPTIMIZATION

• US 20160269247A1
• Filed: 03/14/2016
• Published: 09/15/2016
• Est. Priority Date: 03/13/2015
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Rapolu, Naresh, Chakradhar, Srimat
• Application Number:
  US15/069,621
• Publication Number:
  US 20160269247A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

Aspects of the present disclosure are directed to techniques that improve performance of streaming systems. Accordingly we disclose efficient techniques for dynamic topology re-optimization, through the use of a feedback-driven control loop that substantially solve a number of these performance-impacting problems affecting such streaming systems. More particularly, we disclose a novel technique for network-aware tuple routing using consistent hashing that improves stream flow throughput in the presence of large, run-time overhead. We also disclose methods for dynamic optimization of overlay topologies for group communication operations. To enable fast topology re-optimization with least system disruption, we present a lightweight, fault-tolerant protocol. All of the disclosed techniques were implemented in a real system and comprehensively validated on three real applications. We have demonstrated significant improvement in performance (20% to 200%), while overcoming various compute and network bottlenecks. We have shown that our performance improvements are robust to dynamic changes, as well as complex congestion patterns. Given the importance of stream processing systems and the ubiquity of dynamic network state in cloud environments, our results represent a significant and practical solution to these problems and deficiencies.

Claims

1. A stream processing acceleration method employing network-aware routing, said method comprising the computer implemented steps of:

representing topology link structures using route-maps wherein said route-maps include tuple-routing information and topology structure encoded therein;

applying, on-the-fly, the route maps into multiple operators using a topology route-map update method.

2. A method for accelerating stream processing in a network system through the effect of dynamic network-aware topology re-optimization, the method comprising the computer implemented steps of:

choosing, for every operator, a destination operator for outgoing tuples based on route maps wherein said route maps include information on the type and proportion of traffic for each destination operator;

collecting, by a per-topology controller, a number of metrics pertaining to the network system;

determining any bottlenecks in the network system;

based on the determined bottlenecks, generating—

by the controller—

new route maps that minimize the maximum network and CPU utilization;

installing the new route maps in a consistent manner on a running cluster in the network system using a light-weight atomic route-update protocol.

3. The method according to claim 2 wherein the new route maps that minimize the maximum network and CPU utilization are generated according to the following relationship:

4. The method according to claim 3 further comprising the step of modelling traffic as data is received by fine-grained key-space buckets instead of coarse-grained operators such that fine-grained mapping of buckets to nodes is effected.

5. The method according to claim 4 further comprising the step of balancing utilization of all network links.

6. The method according to claim 5 further comprising the step of determining bandwidth estimates from a rate of tuple-acks emitted by different nodes in the network.

7. The method according to claim 6 wherein said bandwidth estimate determination is invoked only when hysteresis-applied system throughput rate in a recent time window drops by a threshold percentage as compared to a long term average wherein the system throughput rate is the rate of tuple-ingestion by a spout and the threshold percentage is 10%.

8. A method for accelerating stream processing in a network system through the effect of an atomic method for modifying topology route maps wherein each topology includes a controller and a spout, each having corresponding kafka queues which form their message sources, the method comprising the computer implemented steps of:

storing, by the controller, new route-maps in its local state and then sending a new route map message, tagged by a version-id, to the spout by placing it in the spout'"'"'s kafka queue;

reading by the spout, the new route-maps message from its kafka queue, and then appending an install-routes command to the message and sending that appended message to all involved operators by piggybacking on a next start-batch tuple;

receiving, by the spout, acknowledgements from all involved operators and in response sending a routes-installed confirmation message to the controller by placing it in the controller'"'"'s kafka queue;

storing, by the controller upon receipt of the routes-installed message, the new topology route maps in its local state and then sending an activate new routes message to the spout by placing it in the spout'"'"'s kafka queue;

upon receiving the activate new routes message, appending, by the spout, the received message onto a next start batch tuple;

sending, by the controller, the piggybacked start-batch tuple after waiting for a successful commit of all currently executing batches;

upon receiving all acknowledgements for the start batch tuple containing activate new routes message, sending by the spout an activated new routes message to the controller by placing it in the controller'"'"'s kafka queue; and

marking, by the controller, a successful completion.