# McElieceTalk

Published on February 5, 2008

Author: Paola

Source: authorstream.com

Routing in Error-Correcting Networks:  Routing in Error-Correcting Networks Edwin Soedarmadji May 10, 2006 California Institute of Technology Department of Electrical Engineering Pasadena, CA 91125, USA Introduction:  Introduction Start from an unrelated network problem Route planning under fuel capacity and refueling constraints Especially relevant Increasing energy cost Vehicles with alternative fuel Vehicles exploring remote areas The Gas Station Problem:  The Gas Station Problem Shortest Path Problem in Vehicle has limited a fuel capacity Refueling nodes in the network Edge weights expressed in fuel units Vehicle starts at with fuel units  The Gas Station Problem:  The Gas Station Problem Feasible paths are paths where the vehicle always carries a non-negative amount of fuel on the path nodes Is {all feasible paths} an empty set ? If not, what is the path that minimizes the travel distance?  Theorem:  Theorem Example:  Example Remove infeasible edges in E and vertices in V Compute all-pairs shortest path between nodes in V’ Remove infeasible edges in E’ and vertices in V’ Calculate the shortest path from s to t Solution produced in Error-Correcting Network:  Error-Correcting Network Possible Generalization to Communication Networks The Gas-Station algorithm works for transportation networks Is it applicable to communication networks? There are many similarities Vehicle  information packet Gas tank capacity  error budget Gas station  error correction node Gas consumption  packet error Error Budget:  Error Budget  M U R F L E S M A R B L E S Suppose each packet contains seven symbols, and the error-correction scheme employed in the network can correct up to (but not more than) three errors. Then the error budget is three units for a given alphabet size.   Edge model: Symmetric Channel:  Edge model: Symmetric Channel The Cascaded SC:  The Cascaded SC The ary Erasure Channel:  The ary Erasure Channel Generalized Dijkstra Algorithm:  Generalized Dijkstra Algorithm x + min( y , z ) = min ( x + y , x + z ) The Error Distribution:  The Error Distribution Edge Weight: Worst-Case Error:  Edge Weight: Worst-Case Error p = 0.10 p = 0.25 p = 0.98 p = 0.50 Routing in Error-Correcting Networks:  Routing in Error-Correcting Networks WCE x is a non-decreasing function of p The algorithm used in the Gas Station Problem can be used to find the feasible path with minimum WCE from s to t. Questions? 

24. 04. 2008
0 views

22. 01. 2008
0 views

21. 02. 2008
0 views

09. 01. 2008
0 views

11. 01. 2008
0 views

11. 01. 2008
0 views

12. 01. 2008
0 views

12. 01. 2008
0 views

14. 01. 2008
0 views

20. 01. 2008
0 views

21. 01. 2008
0 views

22. 01. 2008
0 views

22. 01. 2008
0 views

17. 01. 2008
0 views

22. 01. 2008
0 views

23. 01. 2008
0 views

04. 02. 2008
0 views

04. 02. 2008
0 views

25. 01. 2008
0 views

25. 01. 2008
0 views

28. 01. 2008
0 views

06. 02. 2008
0 views

07. 02. 2008
0 views

07. 02. 2008
0 views

14. 02. 2008
0 views

18. 02. 2008
0 views

31. 01. 2008
0 views

20. 02. 2008
0 views

22. 02. 2008
0 views

15. 01. 2008
0 views

28. 02. 2008
0 views

15. 01. 2008
0 views

29. 02. 2008
0 views

14. 01. 2008
0 views

08. 03. 2008
0 views

16. 03. 2008
0 views

21. 03. 2008
0 views

17. 01. 2008
0 views

16. 04. 2008
0 views

16. 04. 2008
0 views

17. 04. 2008
0 views

17. 01. 2008
0 views

18. 01. 2008
0 views

06. 02. 2008
0 views

15. 02. 2008
0 views

24. 03. 2008
0 views

21. 04. 2008
0 views

13. 02. 2008
0 views

07. 05. 2008
0 views

08. 05. 2008
0 views

30. 04. 2008
0 views

02. 05. 2008
0 views

07. 02. 2008
0 views

21. 01. 2008
0 views

09. 01. 2008
0 views

13. 01. 2008
0 views

11. 02. 2008
0 views

03. 03. 2008
0 views

05. 02. 2008
0 views

28. 01. 2008
0 views

08. 01. 2008
0 views

30. 01. 2008
0 views

15. 03. 2008
0 views

15. 01. 2008
0 views

09. 01. 2008
0 views

22. 01. 2008
0 views