Accelerating stream processing by dynamic network aware topology re-optimization

Patent metadata

Field	Value
Publication number	US-2016269247-A1
Application number	US-201615069621-A
Country	US
Kind code	A1
Filing date	Mar 14, 2016
Priority date	Mar 13, 2015
Publication date	Sep 15, 2016
Grant date	—

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.

First claim

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:

minimize




w
cu

*

max
n





S


(
n
)



/



C


(
n
)


CU

+

w
nu

*

max

u
,
n





F


(

u
,
v

)



/



R


(

u
,
v

)


NU





subject



to




x

b
,
n

∈

{

0
,
1

}



∀
b

,

n
;

Σ
n





x

b
,
n

=

1


∀
b

(
1
)

wherein N denotes a set of nodes in the network, n is an individual node in the set N, C(n) denotes the computing c

Assignees

• Nec Lab America Inc

Inventors

• Chakradhar Srimat
• Rapolu Naresh

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L67/12

  specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L43/0894

  Packet rate · CPC title