Transcript ppt
PATH DIVERSITY WITH FORWARD ERROR CORRECTION SYSTEM FOR PACKET SWITCHED NETWORKS Thinh Nguyen and Avideh Zakhor IEEE INFOCOM 2003 AGENDA Motivation System Description Redundant Path Selection Simulation Results Conclusion MOTIVATION (1) (2) (3) Packet loss and end-to-end delay Solutions – Layered, error-resilient video codecs Retransmission Use of edge architectures Assume single fixed path between sender and receiver. PERFORMANCE OF FEC Depends heavily on the correlation of packet loss between multiple paths. So the question is – Are there sufficient disjoint paths between a pair of senders and receivers??? MOTIVATION Theoretical Results – RS(30,23), packet size-500 bytes, sending rate-800 kbps Optimal rate partition using two paths. MOTIVATION Ratio of irrecoverable loss probabilities of the uni-path scheme to multi-path scheme. SYSTEM ARCHITECTURE SYSTEM ARCHITECTURE Contd. Sender first executes traceroute from itself to all the participating nodes and receiver. It also sends setup packet to all participating nodes instructing them to execute traceroute. Sender Computes optimal redundant path After redundant path is choosen, sender sends the setup packet to the selected relay node instructing it to forward packets to the receiver. SYSTEM ARCHITECTURE Contd. Setup Packet = flow ID + IP Address + Port Number Use UDP to send all the packets between nodes. REDUNDANT PATH SELECTION To measure latency, bandwidth and packet loss – (1) Use of Probing tools – inc complexity (2) Passive Probing Assumption made in this system – Two paths with absolute lowest loss rates is not needed. REDUNDANT PATH SELECTION - - Sender runs this algorithm. Get information using traceroute tool. Input is names of the routers and roundtrip delays. Network Topology – G(V,E) . Weights denote the latencies b/w participating nodes. REDUNDANT PATH SELECTION Relay node is computed as(1) Compute a set of nodes that result in minimum number of joint links between the default Internet path and all redundant paths. (2) Choose k’ that results in minimum weight associated with the corresponding redundant path. SIMULATION RESULTS Simulation Topologies Used Brite s/w to generate Alber-Barabasi topologies. Flat Topology Two level Hierarchial Topology SIMULATION RESULTS To estimate average latency, hop counts and degree of disjointness – (1) Choose a set of participating nodes randomly. (2) Choose a pair of sender and receiver. (3) Use the redundant path selection algorithm proposed to find redundant and default paths for the given configuration. Default path – low latency. SIMULATION RESULTS (1) Percentage of shared links between redundant and default paths SIMULATION RESULTS (2) Latency of redundant path over the latency of default path SIMULATION RESULTS (3) Number of hops of the redundant path over the number hops of the default path SIMULATION RESULTS (4) Cumulative distribution of shared links for various network topologies SIMULATION RESULTS NS SIMULATIONS: Link capacity – 2 Mbs Packet Loss Rate is considered in 3 scenarios – (1) Sender streams the video to the receiver at 800kbps on the default path. (2) Sender streams the video to the receiver on both paths at 400kbps each. (3) Same as (2) with a shared link between both paths. SIMULATION RESULTS Sending Packets using traditional default path SIMULATION RESULTS Both redundant and default path without shared link SIMULATION RESULTS Both redundant and default path with one shared link SIMULATION RESULTS Avg. loss rate of using one path over both with various number of shared links between them. CONCLUSION - Simulations show that only 10% of participating nodes are required for the proposed path redundant selection scheme to effectively find a redundant path. - DRAWBACKS OF THE PROPOSED SYSTEMPerformance depends on the information given by traceroute. Some ASes do not report information about their networks. (1) (2) REFERENCES Path Diversity for Enhanced Media Streaming. John G. Apostolopoulos and Mitchell D Trott, Streaming Media Systems Group. Thank You