Delay Analysis of Real-Time Data Dissemination Gidon Gershinsky, Avi Harpaz, Nir Naaman, Harel Paz, Konstantin Shagin IBM Haifa Labs © 2007 IBM Corporation IBM Labs in Haifa Motivation Performance guarantees and predictable task execution-time are becoming increasingly important Distributed real-time applications require a predictable form of communication between the different components Need to use a messaging system that delivers messages according to their timeliness requirements © 2007 IBM Corporation IBM Labs in Haifa The Messaging System Model We consider a messaging transport that provides real-time quality of service One-to-many reliable message dissemination The network transport is assumed to be unreliable The messaging transport implements a reliable dissemination protocol Sender-initiated protocol (ACK based): upon receiving a packet, a receiver sends an ACK to the sender Receiver-initiated protocol (NAK based): a receiver sends a NAK for missing packets © 2007 IBM Corporation IBM Labs in Haifa This Work We investigate messages delay: the delay between a message submission (generation) at the sender and its delivery to all receivers Provide an analytic model for congestion in data dissemination protocols A rate control mechanism limits the sender’s transmission rate Investigate transmission rate effect on message delivery latency Main aspect examined: receiver side congestion We consider the processing overhead of a discarded packet Use a simulation to study additional effects Evaluate the on-time delivery probability of a message © 2007 IBM Corporation IBM Labs in Haifa Referred Applications We investigate messages delay of 2 types of applications: Bulk-data applications- very large messages A message is converted into many packets Short-message applications- bursty nature An ON/OFF source Alternates between ON and OFF periods During ON periods packets are generated at a high rate During OFF periods no packets are generated © 2007 IBM Corporation IBM Labs in Haifa Results Computational & simulation results Processing times & network parameters are based on experiments Analysis uses expectations Simulation employs uniform distributions Time unit = the time is takes a receiver to handle a single packet The receiver rate = 1.0 packets per time unit Examine various transmission rates Low transmission rate ( 1.0): no congestion High transmission rate ( > 1.0): congestion occurs Discarding overhead is set to 0.3 time units Network loss = 0.01 © 2007 IBM Corporation IBM Labs in Haifa Computational Results: Bulk-Data # of Packet Transmissions as Function of Transmission Rate (ACK-based) 90 1 receiver 80 10 receivers 100 receivers 70 1000 receivers 60 50 40 30 20 10 3. 5 3. 3 3. 1 2. 9 2. 7 2. 5 2. 3 2. 1 1. 9 1. 7 1. 5 1. 3 1. 1 0. 9 0. 7 0. 5 0. 3 0 0. 1 number of packet transmissions 100 normalized transmission rate © 2007 IBM Corporation IBM Labs in Haifa Computational Results: Bulk-Data Delivery Time as Function of Transmission Rate (ACK-based) 3.50E+05 1 receiver 3.00E+05 100 receivers 10 receivers 1000 receivers 2.50E+05 2.00E+05 1.50E+05 1.00E+05 5.00E+04 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 0. 0. 0. 0. 1. 1. 1. 1. 1. 2. 2. 2. 2. 2. 3. 3. 3. 0.00E+00 0. delivery time (in time units) 4.00E+05 normalize d transmission rate © 2007 IBM Corporation IBM Labs in Haifa Computational Results: Bulk-Data Delivery Time as Function of Transmission Rate (ACK-based) 4.00E+05 3.50E+05 1 receiver 3.00E+05 100 receivers d elive ry tim e (in tim e u n its) 10 receivers 1000 receivers 2.50E+05 1 receiver 3.50E+05 2.00E+05 1.50E+05 1.00E+05 10 receivers 100 receivers 3.00E+05 1000 receivers 2.50E+05 2.00E+05 1.50E+05 1.00E+05 5.00E+04 5.00E+04 9 1 3 5 7 9 1 3 5 1. 2. 2. 2. 2. 2. 3. 3. 3. 5 3. 7 3 3. 5 1 3. 1. 9 2. 3 7 2. 1. 5 2. 1. 3 2. 1 1 2. 9 9 1. 1. 7 1. 7 5 1. 0. 3 1. 0. 1 1. 5 9 0. 3 7 0. 0. 5 1 3 0. 0. 1 0. normalize d transmission rate 0. 0.00E+00 0.00E+00 0. d e liv e ry tim e (in tim e u n its ) 4.00E+05 normalized transmission rate Discard overhead is ignored © 2007 IBM Corporation IBM Labs in Haifa Computational Results: Bulk-Data Delivery Time as Function of Transmission Rate (NAK-based) 9.00E+05 1 receiver 8.00E+05 10 receivers 100 receivers 7.00E+05 1000 receivers 6.00E+05 5.00E+05 4.00E+05 3.00E+05 2.00E+05 1.00E+05 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 0. 0. 0. 0. 1. 1. 1. 1. 1. 2. 2. 2. 2. 2. 3. 0.00E+00 0. delivery time (in time units) 1.00E+06 normalized transmission rate © 2007 IBM Corporation IBM Labs in Haifa Results- Short Messages Duration (time units) Message generation rate (per time unit) ON period 50 3 OFF period 250 0 © 2007 IBM Corporation IBM Labs in Haifa Simulation: ON/OFF Model Latency Measurements (10 receivers) 600 rate .5 latency (in time units) 500 400 phase 2 300 phase 1 200 100 0 1 73 145 217 289 361 433 505 577 649 721 793 865 937 1009 1081 1153 1225 1297 1369 1441 packet number © 2007 IBM Corporation IBM Labs in Haifa Simulation: ON/OFF Model Delivery by Deadline Probability (Different Receiver Sets) 1.2 1 receiver 1 10 receivers 1 receiver 100 receivers 0.6 0.4 10 receivers 100 receivers 0.2 7 9 1 3 5 7 9 1 3 1. 2. 2. 2. 2. 2. 3. 3. 1 1. 1. 9 0. 5 7 0. 1. 5 0. 3 3 0. 1. 1 0 0. probability 0.8 normalized transmission rate © 2007 IBM Corporation IBM Labs in Haifa Summary We study aspects related to real-time message dissemination Applications that generate large messages and short messages Sender-initiated and receiver-initiated protocols Congestion at the receivers The analytic model draws the dependency between transmission rate limit and the expected message latency The simulation indicates that the analysis’ simplifications have a negligible effect The analysis can be incorporated in a transmission rate control logic to attain high probability of timely delivery and support stricter real-time requirements © 2007 IBM Corporation