1、A Hybrid Multicast-Unicast Infrastructure for Efficient Publish-Subscribe in Enterprise Networks,Danny Bickson, Ezra N. Hoch, Nir Naaman and Yoav Tock IBM Haifa Research Lab, Israel,2,Outline,Motivation The channelization problem Our hybrid approach Experimental results Conclusions,3,Motivation: lar

2、ge scale publish subscribe application,Large number of information flows (topics) and subscribers Each flow must be delivered to a subset of interested subscribers Example: financial market data dissemination Publisher divides data feed into a large number information flows, (100K) e.g. stock symbol

3、s, futures, commodities Many stand-alone subscribers (1K) Subscribers display interest heterogeneity - are interested in different yet overlapping subsets of the topics Any single topic may be delivered to a large number of subscribers (hot / cold topics),4,Common approaches,Use unicast (point-to-po

4、int) connections Limitations: poor utilization of network resources (duplicate transmissions) Use broadcast (single multicast channel) Limitations: receivers filter unwanted content Utilize multicast to transmit data Topics are mapped into multicast groups. Each user joins the groups that cover his

5、topic-interest. Reduces receiver filtering Limitations: limited amount of multicast addresses Network element state problem Receiver resources (NICs),5,Our novel contribution,Create a hybrid approach that combines both multicast and unicast Flexible allocation of transmissions Topics with high inter

6、est enjoy efficiency of multicast Topics with low interest are transmitted in unicast Formalize as an optimization problem Propose a two step alternating method for computing the resource allocation,6,The Channelization Problem,n flows Flow rates k multicast groups m users Interest matrix W The task

7、: find mapping matrices X,Y that minimizes the communication cost The cost of transmission take into account transmission to multiple groups The cost of reception minimize excess filtering,7,The Hybrid Channelization Problem,F1,F2,Fn,F3,G1,G2,Gk,U1,U2,Um,U3,Flows,Users,Multicast Groups,F1 F2,F1 F2 F

8、8,F3 F4 F6,F1 Fn,InterestExtraction (W),F4,X flow to group map,Y user subscription map,T unicast transmission map,8,The Hybrid Channelization Problem,Modified cost function Problem objective is,Cost of multicast reception,Cost of multicast transmission,Cost of unicast reception & transmission,9,Prop

9、osed Solution,Unfortunately the hybrid problem is NP-hard We propose a two step heuristic solution First step: solve the channelization problem (multicast mapping) Second step: Choose flow-user pairs for unicast, Remove redundant assignments from multicast mapping Recalculate the cost Iterate until

10、convergence, or unicast BW limit exceeded,10,First step: channelization problem solution,We have experimented with the following algorithms K-Means (2005) performs best,11,K-Means Mapping Algorithm,Input Interest matrix, topic rate vector Basic insight Put “similar” topics in the same group “Similar

11、” topics have a similar audience - causes less filtering Take the rate into account,Iterative Clustering Algorithm (K-means) Init: Topics are assigned into a fixed number of groups Move: In each step, remove a single topic, and move it to the best group the one producing the lowest cost Cost: After

12、each epoch, compute total filtering cost Stop: cost doesnt improve | time elapsed | max # iter.,T1,T2,T3,T4,T5,T6,T7,T8,T9,T5,?,?,?,v,x,x,x,x,x,v,v,x,x,Users,Topics,x,x,v,v,v,Users Interest Vector,TopicsAudience Vector,Interest Matrix =,Rate Vector =,12,Second step: choosing user-flow pairs for unic

13、ast,Experimented with several heuristics Heavy users - all transmission to a specific heavy user is sent using unicast Lightweight flows - flows with low bandwidth are sent using unicast Greedy flows - move to unicast the flow which best minimizes the total cost Greedy users - move to unicast the us

14、er which best minimizes the total cost An additional heuristic - Greedy user-flow pairs move to unicast the user-flow pair which best minimizes the total cost - very slow, impractical run-time,13,Experimental results,Construction of user-interest matrix W Random, uniform Market distribution based on

15、 a model of NYSE stock volume IBM WebSphere cell a real system,14,Channelization algorithms,K-Means (2005) performs best Takes rate into account Gradient decent on the true cost function,15,Effect of the interest matrix on channelization performance,The interest and rate have a significant effect on

16、 channelization performance Some interests have patterns that are easy to “channelize” Interests with less entropy, more order, are easier,16,Hybrid Algorithm Heuristics,Market dist. - Greedy users Can use more unicast BW,WebSphere dist. - Greedy flows Doesnt need more than 20% unicast BW,Unicast BW

17、 limit algorithm will use optimal amount up to the limit,17,Hybrid using greedy flow unicast / multicast tradeoff,Unicast BW allocation exact amount of unicast BW used,Every interest and rate distribution has an optimal amount of unicast BW it can use The hybrid approach improves upon both unicast-o

18、nly and multicat-only,18,Conclusions,We have presented a novel hybrid approach for publish subscribe We have shown using extensive and realistic simulation results that our approach reduces consumed network and host resources K-Means (2005) performs best for channelization, from the selection of alg

19、orithms we tested Greedy hybrid heuristics performed best in our tests Relative competitiveness of the greedy-flows & greedy-users heuristics depends on the structure of the interest matrix and rate, The End ,19,Model based on statistical analysis of NYSE daily trade data 20K Topics 500 Subscribers

20、Avg. 70 flows / user Min 15 flows / user Max 115 flows / user Avg. message fan out 10.1 clients Multicast - message is transmitted once Unicast transmitter data rate is x10 of multicast !,Real Life Messaging Load Model,Backup Model,20,Messaging Load Model Based on Market Research,Financial front off

21、ice Hundreds of users, requiring stock quotes and financial information from several markets Topic space structure Within each market, symbol popularity and rate are exponentially distributed (NYSE market research) Several different markets, with Avg. popularity and size prop. 1/m (assumption). 20K

22、flows, 10 markets, 500 users User interest Each user: selects some markets, selects a percent of the symbols from each chosen market, according to the said distributions,10% of Symbols55% of trade,Backup Model,21,Mapping Algorithm,Input interest matrix, topic rate vector Basic insight Put “similar”

23、topics in the same group “Similar” topics have a similar audience A group with a homogenous audience causes less filtering Take the rate into account The cost of putting two topics in the same group The cost of adding a new topic to a group of topics,v,x,x,x,x,x,v,v,x,x,Users,Topics,x,x,v,v,v,Interest Matrix,T