Exploring Network Topologies: RLNC — Transcript

Full transcript

1. 0:06All right. So in red we have
2. 0:09pointto-point TCP IP. In green we have
3. 0:14classical multiccast without coding.
4. 0:18What does coding give us? I'm going to
5. 0:19use black sort of echoing what we've
6. 0:22done before with coding
7. 0:24to see what we can do in black. What we
8. 0:27have is actually
9. 0:31Not just
10. 0:34the tree, but we can even have the
11. 0:37receivers help each other out. Uh we can
12. 0:41have a receiver here from different
13. 0:47nodes. Whereas in a classical tree,
14. 0:50every node only has one incident what we
15. 0:54call edge. Right? Like in a tree, you
16. 0:56would have branches, but you don't have
17. 0:58branches that merge. And a leaf doesn't
18. 1:00come out of two branches or three
19. 1:02branches like it would here. It would
20. 1:03only come out of one. But in general,
21. 1:05what we can do with random network
22. 1:08coding is just have everybody who can
23. 1:11talk to each other talk to each other.
24. 1:13And the number of packets and what
25. 1:16transmissions happen where is
26. 1:19automatically taken care of by the
27. 1:22underlying algorithm.
28. 1:25So what we're doing for instance in M
29. 1:28P2P is actually something like this
30. 1:31where we're taking a mesh such as it is
31. 1:34provided to us where the nodes are
32. 1:36talking to whoever they're talking to.
33. 1:38It's already been set up by other
34. 1:41determinations in the system and then
35. 1:44we're just automatically and optimally
36. 1:47making use of all of the available
37. 1:49resources. There's actually a really
38. 1:51funny little thing that comes here. Why
39. 1:54did I spend some time talking about the
40. 1:57complexity of the Steiner tree? The
41. 2:00Steiner tree is suboptimal not only
42. 2:02because it doesn't use all of the
43. 2:04resources. It has this constraint that
44. 2:07you can only listen as a node to a
45. 2:11single node upstream. You might talk to
46. 2:13several nodes downstream, but you only
47. 2:15have one incoming node.
48. 2:19Um so it's suboptimal because it doesn't
49. 2:21use all the resources. Uh it's also very
50. 2:24difficult to manage particularly uh not
51. 2:26only if you set it up once beautifully
52. 2:28and you just bite the bullet and take
53. 2:31the complexity cost as soon as a node
54. 2:34moves you know comps online leaves
55. 2:37everything gets messed up. um instead
56. 2:41when you use RLNC the complexity
57. 2:44actually turns out to be what we call
58. 2:47polomial time and polomial time means
59. 2:50that it's actually easy you can write a
60. 2:52program you know how fast it's going to
61. 2:54go that's the first thing the second
62. 2:56thing is that beyond being polomial time
63. 3:00it can also be solved in an entirely
64. 3:03decentralized way what does an entirely
65. 3:06decentralized way mean it means that the
66. 3:09different nodes nodes can determine how
67. 3:11many equations they should send to one
68. 3:14another without needing to know the
69. 3:18global topology. That's to say that this
70. 3:22node only needs to talk to its
71. 3:24neighbors, without actually knowing
72. 3:26everything that's going on in this
73. 3:28network. And [snorts] by talking only to
74. 3:31its neighbors, it does as well as if it
75. 3:36actually had global vision. given to
76. 3:39that node for free by magic global
77. 3:42vision of everything going on. So this
78. 3:44is why we are truly decentralized. We're
79. 3:48decentralized not just for philosophical
80. 3:50reasons. We're decentralized because we
81. 3:53don't need that extra information. If
82. 3:56you code correctly, if you do the math
83. 3:58correctly, you actually don't need to
84. 4:01have centralized knowledge. And that's
85. 4:04the magic uh of Ireland C. So what we've
86. 4:07seen here is send her to each receiver,
87. 4:10send her to multiple receivers without
88. 4:13coding and then in the end what we have
89. 4:16is the grand vision and that is the
90. 4:19optimum use of all of the resources in
91. 4:21the network decentralized optimally
92. 4:25efficient.