RESILIENT Priority-Based Data Transmission Using NETWORK CODING

Please download to get full document.

View again

of 66
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Others

Published:

Views: 2 | Pages: 66

Extension: PDF | Download: 0

Share
Related documents
Description
RESILIENT Priority-Based Data Transmission Using NETWORK CODING Jie Wu Computer and Information Sciences Temple University Center for Networked Computing 2 Center for Networked
Transcript
RESILIENT Priority-Based Data Transmission Using NETWORK CODING Jie Wu Computer and Information Sciences Temple University Center for Networked Computing 2 Center for Networked Computing Dr. Jie Wu Computer and Information Sciences, Temple University Wireless and mobile networks Mesh networks (CRI and GENI grants) Sensor networks (NeTS and TF grants) Content sharing networks (NeTS medium grant) Network coding (CCSS grant) Vehicle networks Network security and privacy Wireless networks (ARO and CCSS grants) Cloud comp. (Microsoft and Amazon grants) Social networks Medical applications (Tobacco fund) Online social networks Mobile Infostation High performance computing NSF GPU/CPU supercomputer (MRI gr Economic development Urban Maps & Apps Studio (EDA gran Opportunistic High-Speed Link (MB/s) Roadway Sensors Center for Networked Computing Agenda 3 Network Coding Background Priority-Based Network Coding Symbol-level transmission Layered video streaming Conclusions Other Recent Works 4 Network Coding Background Network Coding in Wired Networks 5 Single multicast session Bottleneck problem (Ahlswede 00) No coding Coding 6 Network Coding in Wireless Networks No coding 4 transmissions delivery rate = COPE (coding, Katty 06) 3 transmissions (broadcast channel) delivery rate = COPE-dup (double transmission by relay, Rayanchu 08) 4 transmissions delivery rate = Scheme =0 =0.1 =0.3 =0.5 =0.7 No coding COPE COPE-dup Network Coding Classification 7 Local Hop-by-hop decoding XOR operation Decoding Decoding Global Decoding at the destination Linear network coding (on a finite field) Recoding Network Coding Classification 8 Intra-flow Within a flow Robustness enhancement Inter-flow Between different flows Throughput/capacity enhancement Joint inter- and intra-flow Within flow and between flows Network Coding in Wireless Networks 9 Intra-flow coding Inter-flow coding Reliability=2/3 3 transmissions Reliable links 2 transmissions by the relay Network Coding in Wireless Networks 10 Reliability from r to and is 2/3 Other links are reliable Intra- flow coding Joint inter- and intra-flow coding 6 transmissions by the relay 3 transmissions by the relay Opportunistic Routing (OP) 11 OP: no fixed path Relays jointly having all packets Coordination needed among relays Which packets should be sent? (coupon collection problem) OP with network coding Linear coded transmissions at relays No coordination needed among relays Network Coding Applications 12 Robustness Enhancement Error correcting code Physical layer: improving error performance on wireless link using intra-packet coding Erasure correction Spatial redundancy: handle lost packets on the end-toend connection level using inter-packet coding Joint error and erasure correction Robust linear network coding for link failures (Koetter and Medard 2003) Network Coding Applications 13 Throughput/Capacity Enhancement Overlay networks Distributed storage systems Content distribution Layered multicast Wireless networks Throughput enhancement Broadcast storm problem Network Tomography: infer network characteristics Link loss rate inference Topology inference Priority-Based Approaches 14 New twist on the classic unequal error protection Symbol-Level NC Video Streaming NC 15 Priority-Based Network Coding Symbol-Level Transmission Priority-Based Transmission 16 Numeric data Sensed data by sensors Different priorities (utility values) for symbols MSB Binary coded decimal LSB Approaches Reliable transmissions Maximizing the expected utility with a given number of transmissions Motivation 17 : utility : loss rate : weight of : number of transmissions of 2 transmissions 3 transmissions Setting and Objective 18 One-hop wireless (WiFi) network One source with multiple destinations Lossy links (randomness in wireless),,, Transmission window size X slots for a packet Objective: maximizing the total expected utility of the received symbols Single Packet (Homogenous Destinations) 19 The case of a packet with 2 symbols Saturati on point Single Packet (Homogeneous Destinations) 20 m symbols Assign the transmissions to while Then, distribute the transmissions between while Assign round-robin pattern among and and Start increasing while Single Packet (Heterogeneous Destinations) 21 The round-robin pattern does not exist Iterative algorithm : utility changes for increasing to At each iteration, assign the current transmission to the symbol with the maximum Single Packet (Heterogeneous Destinations) 22 Iteration =140 =14 = Binary coded decimal Iteration =40 =14 = =0.2 =0.4 Iteration =12.8 =14 = Multiple Packets (No Coding) 23 Our model The size of the packets is equal Each packet has the same weight k independent packets with no coding Multiple Packets (with Network Coding) 24 Heuristic First find the optimal Code all of the k packets together Send coded symbols Multiple Packets (with Network Coding) 25 Network coding may or may not improve the utility Since partial decoding is not possible Compute utility of coding/non-coding Decision for coding/non-coding at each symbol 10 packets Error rate: packets Error rate: 0.5 Simulations Setting 26 MATLAB environment 1,000 rounds Different error rates for links Weight of : Comparing with simple retransmission method Distribute transmissions equally to the different Simulations (Homogenous Destinations) 27 Single packet: 10 symbols SR: simple retransmission WSR: weighted symbol retransmission Simulations (Heterogeneous Destinations) 28 Single packet- 10 symbols 10 transmissions Variable destinations and error rates Simulations (Homogenous Destinations) 29 Packet size: 5 symbols WMP: weighted multiple packets WMP-NC: weighted multiple packets with network coding 10 transmissions 50 packets Simulations (Heterogeneous Destinations) 30 Packet size: 5 symbols 5 destinations CDF of WMP-NC s utility divided by WMP s utility Number of packets=50 Simulations Summary 31 WMP increases utility up to 22% compared to SR Utility of WMP-NC is up to 45% more than SR In 50% of the cases the utility of WMP-NC is 10-20% more than WMP As error rate increases, the performance of WMP-NC over the other methods increases Current and Future Work 32 Current Work Optimal solution for network coding with multiple packets Multiple-hop network extensions with weighted destinations (based on the number of leaf nodes) Future Work Extensions to DAG Real implementation 33 Priority-Based Network Coding Layered Video Streaming Video Streaming 34 Delivering video stream using different resolutions to satisfy different client needs/constraints Multi-Layer Coding (Multi-resolution) Base layer Enhancement layers Multiple Description Coding (MDC) Multiple independent video substreams Receiving more substreams increases the video quality Substream_1 Resolution_1 Substream_2 Resolution _2 Substream_N Resolution _N Setting and Objective 35 One-hop WiFi networks Video stream: sequence of packets Packet deadline: X transmissions Layered streams : L layers Objective: maximizing throughput in terms of the total number of received layers by the users Intra-layer coding: linear coding Inter-layer coding: triangular coding Lossy Bernoulli channel Inter-Layer Coding Strategies 36 Random linear network coding (RLNC) Triangular coding Prefix coding α + 1L1 + β1l2 γ 1L3 2L1 + β2l2 γ 2L3 3L1 + β3l2 γ 3L3 α + α + α 1 L 1 α L + β 2 1 2L2 3L1 + β3l2 γ 3L3 α + Packets in lower layers are more important Included in more coded packets More chance to be decoded Advantage of Triangular Coding 37 Coefficients are not shown for simplicity 6 transmissions in round-robin pattern Blue cells are received No coding L1 L2 L3 L1 L2 L3 Unable to decode Triangula r coding L1 L1 + L2 L1 + L2+ L3 L1 L1 + L2 L1 + L2+ L3 Decodes 2 layers Random linear coding L1 + L2+ L3 L1 + L2+ L3 L1 + L2+ L3 L1 + L2+ L3 L1 + L2+ L3 L1 + L2+ L3 Unable to decode Multi-Layer Video Streaming with Helpers 38 Links Cost: direct download from the server Reliable links Link capacity High capacity links: server to helpers Low capacity links: helpers to users Use of helpers System scalability for more users Helpers: limited capacity and bandwidth Resource Management 39 Optimal resource management Questions: Content placement: Which packets of each video should a helper node store? Bandwidth allocation: Which packets, and to which users, should each helper serve? NP-complete 40 Resource Management (Network Coding) Network coding changes the problem to a linear programming Movie m Coded Movie m Storing x percent of each segment No longer NP-complete Flow-based model using network coding Multi-Layer Video 41 Benefits of multi-layer Provides smooth playback for the users Reduces the load on the server with a fixed number of users More layers increases system scalability Motivation 42 Single video with 4 packets No-layer approach (Hao et al. 2011) 4 packets in the same layer Load on the server: 4 Motivation 43 Single video with 4 packets Intra-layer approach (Ostovari, Khreishah, and Wu 2013) 2 packets per layer Load on the server: 2 Motivation 44 Single video with 4 packets Inter- and intra-layer coding (Ostovari, Khreishah, and Wu 2013) Prefix coding 2 packets per layer Load on the server: 0 Triangular coding VoD with Inter- and Intra-Layer NC 45 Objective function (maximize upload rate from helpers to users) The upload rate of a cache cannot exceed the rate of the stored videos : Upload rate from helper to user over layer of video : Fraction of the layer of video that is stored on helper : Rate of video : Number of layers of a video : Adjacent helpers to user s request: (, ) = (quality level, video) VoD with Inter- and Intra-Layer NC 46 Bandwidth constraints Storage constraints : The bandwidth limit of helper Limits the total download of a user to the rate of the video : The capacity limit of helper VoD with Intra-Layer NC 47 The difference is in the last constraint U: the set of users Limits the total download of a user to the rate of the video The objective function and other constraints are the same Live Streaming (TV) 48 Videos are broadcast to the users Synchronous playback Helpers do not need to allocate separate bandwidths to adjacent users that watch the same video Total bandwidth: Total bandwidth: Distributed Algorithm 49 Dual optimization Solving Lagrangian dual using gradient method Helper Start from empty storage and dynamically adjust the amount of stored videos Update and transmit Lagrange variables to adjacent users User Update and transmit Lagrange variables to adjacent helpers Step control Slope of changes: fast convergence vs. oscillation Simulations Setting 50 MATLAB environment 100 random topologies Random connections of helpers and users Helpers: random bandwidth and capacity limit Users: random requests Comparing with optimal non-layer approach Measuring Load on the server Convergence to optimal solution in dynamic environments Simulation Results (Load) 51 VoD Number of videos: 5 Number of layers: 5 DIST: a non-layer approach with intra-layer coding ( Hao et al. 2011) Simulation Results (Load) 52 VoD Number of users: 50 Number of helpers: 20 Simulation Results (Load) 53 VoD Number of layers: 4 Single video Simulation Results (Convergence) 54 VoD Layers: 4 Videos: 5 Users: 50 Helpers: 20 Convergence to the optimal solution (LP) The fraction of each video on helper h5 Simulation Results (Dynamic Users) 55 VoD Layers: 4 Videos: 5 Adding 5 users Initial Users: 10 Helpers: 10 Adding 5 users Adding 5 users Adding 5 users Removing 5 users Removing 5 users Convergence to the optimal solution (LP) The fraction of each video on helper h8 Simulation Results (Dynamic Helpers) 56 VoD Layers: 4 Videos: 5 Adding 3 helpers Adding 3 helpers Users: 20 Initial helpers: 6 Adding 3 helpers Adding 3 helpers Removing 3 helpers Removing 3 helpers Convergence to the optimal solution (LP) The fraction of each video on helper h3 Future Work and Challenges 57 Other objectives Fairness, layers with different weights, Extension of layered VoD with unreliable links Using symbol-level transmission work in layered VoD Cost-efficient helper provisioning Based on user demands and resource availability Real implementation 58 Conclusions Conclusions 59 Priority-Based Network Coding Data transmission Transmitting the more important data with more redundancy Triangular coding in multi-layer video streaming Increasing the number of received layers VoD and live streaming using helper nodes in multilayer video streaming Minimizing the load on the server References 60 P. Ostovari, J. Wu, and A. Khreishah, Efficient Symbol-Level Transmission in Error-Prone Wireless Networks With Network Coding, Proc. of IEEE WoWMoM, P. Ostovari, A. Khreishah, and J. Wu, Multi-Layer Video Streaming with Helper Nodes using Network Coding, Proc. of IEEE MASS, H. Hao, M. Chen, A. Parekh, and K. Ramchandran, A Distributed Multichannel Demand-Adaptive P2P VoD System with Optimized Caching and Neighbor-Selection, Proc. of SPIE, 2011. 61 Other Recent Works Other Works 62 S. Yang, J. Wu, and M. Cardei, Efficient Broadcast in MANETs Using Network Coding and Directional Antennas, Proc. of IEEE INFOCOM, Network coding in multiple broadcast in a wireless network. Using dominating set as relays and for inter-session coding. (combine routing and coding) Using both dominating set and directional antennas to reduce contention. Other Works 63 P. Ostovari, A. Khreishah, J.Wu, and W. S. Yang, Trade-off between Redundancy and Feedbacks in Wireless Network Communication, accepted to appear in Ad-Hoc & Sensor Wireless Networks, One-hop broadcasting using XOR coding Minimum-cost reliable broadcast considering the cost of feedback messages Multiple retransmissions before receiving feedback How many retransmissions are required? Other Works 64 A. Khreishah, I. M. Khalil, and J. Wu, Universal Opportunistic Routing Scheme using Network Coding, Proc. of IEEE SECON, Distributed opportunistic routing algorithm The correlation of the links through network tomography Coded feedback (for source to determine the type of link failure) Unicast (and multicast in ACM MobiHoc 2012) Independent Correlated Negatively correlated Other Works 65 P. Ostovari, J. Wu, and A. Khreishah, Network Coding Techniques for Wireless and Sensor Networks, accepted to appear in The Art of Wireless Sensor Networks, H. M. Ammari (ed), Springer. Unicast Multicast Broadcast Acknowledgment 66 Shuhui Yang Purdue University Calumet Abdallah Khreishah New Jersey Institute of Technology Pouya Ostovari Temple University CCSS: An Architecture for Joint Integration of Inter and Intrasession Network Coding in Lossy Multihop Wireless Networks
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x