Blockchain Data Encoding: How RLNC Turbocharges Web3 Networks | Optimum Tech — Transcript

Full transcript

1. 0:00Hi everyone. Uh I'm Yuriel Medart um
2. 0:03co-founder Optimum uh of Optimum and
3. 0:07also uh CEO and uh welcome back to my
4. 0:10board. I've made a little bit more space
5. 0:12than last time uh to continue talking
6. 0:14about coding. So last time uh we looked
7. 0:18at the simplest uh setting where we had
8. 0:22three numbers x1, x2, x3 and we were
9. 0:25sending them from one node to another.
10. 0:28We're trying to make up for the problems
11. 0:31that could arise from losing some of
12. 0:33these numbers. Okay. Now, this is not
13. 0:36really a network or it's just, you know,
14. 0:38it's just a single link network. It's
15. 0:40not what we would consider really to be
16. 0:42a network. So, let's look at the
17. 0:44simplest version of a network which is
18. 0:47at least having two links rather than a
19. 0:49single link. So let me look at this very
20. 0:52simple version where I have at uh a
21. 0:55transmitter here node one a relay node
22. 0:59two and a last node node three and we're
23. 1:02going to see what happens uh in this
24. 1:04system. Okay, so um we know about coding
25. 1:09now. We know that coding is about
26. 1:11generating equations
27. 1:14and we have our old friends X1, X2, X3.
28. 1:17We're trying to get them from the
29. 1:19transmitter all the way here to the
30. 1:21receiver.
31. 1:22Okay, what do we do? Well,
32. 1:26assume for the time being that I end up
33. 1:29losing one of the numbers on the first
34. 1:32link and also one of the numbers on the
35. 1:35second link. But of course, we don't
36. 1:37know which number will get lost. And as
37. 1:39an example, let's say that uh I send x1,
38. 1:43x2, x3 over to
39. 1:47node two and that the second number gets
40. 1:49lost and node two is just a dumb relay.
41. 1:53is just sending along what it received
42. 1:56and it so it sends then these three
43. 1:59numbers that it got X1, X3 because it
44. 2:02missed X2 and the sum of the X's and it
45. 2:06sends it over to the receiver and
46. 2:09another number gets lost along this two
47. 2:12to three link. Say that it's X3 that
48. 2:15gets lost. we end up here with two
49. 2:18unknowns uh two uh three unknowns x1 x2
50. 2:21and x3 but only two equations and so
51. 2:24node three is not able to uh decode.
52. 2:28Now, what we could do is have the
53. 2:30transmitter say, well, there's going to
54. 2:32be two losses total, one here, one
55. 2:36there. I should really add
56. 2:39two equations rather than a single
57. 2:41equations. We could come up with another
58. 2:42equation. Say x1 + 2x2 + 3x3. Any other,
59. 2:47you know, a lot of other equations will
60. 2:49do. And that way, this node one here
61. 2:52would have to do five transmissions.
62. 2:55they would be then four received uh
63. 2:59equations and then node two would say
64. 3:02four transmissions and they would be
65. 3:03three received equations. Okay. Uh so
66. 3:07that would cost me basically
67. 3:10five transmissions and four
68. 3:13transmissions for a total of nine
69. 3:16transmissions.
70. 3:18Now could I have better utilization? So
71. 3:22somehow end up recovering all of the
72. 3:25data without doing that many
73. 3:27transmissions. Well, I could in
74. 3:30particular
75. 3:32what I could ask the middle node to do
76. 3:35node two is to do something maybe a
77. 3:37little smarter. I could say well look
78. 3:40why don't you decode
79. 3:43from the transmitter? You have x1 you
80. 3:47have x3. You have the sum of x1 and x2
81. 3:50and x3. You could reconstruct X2 decode
82. 3:57and then by reconstructing you would now
83. 4:01have X1, X2, X3
84. 4:03and now you can decode recode
85. 4:08now
86. 4:10send and that would cost me so here I
87. 4:13would have four transmissions
88. 4:15now I would have again four
89. 4:16transmissions and I would have maybe
90. 4:19this time it was if you recall
91. 4:21U X3 that got lost. Okay. And if X3 gets
92. 4:26uh gets lost this time, I still have
93. 4:29three unknowns, three equations, I can
94. 4:32reconstruct X3 from X1, X2 and this uh
95. 4:36and the sum. Okay. So now rather than
96. 4:40having a total of um having to have um
97. 4:45five and four which remember before it
98. 4:47cost me nine units of transmission. Now
99. 4:50it's costing me just
100. 4:53eight units of transmission. Okay. So I
101. 4:56got a better efficiency in my network. I
102. 5:00didn't have to pay as much in terms of
103. 5:02transmissions and so I got a better
104. 5:04throughput by not having to do that.
105. 5:07Okay, so you would say, "All right,
106. 5:09that's not so bad. Maybe that's what I
107. 5:11should do. Ask the middle node to
108. 5:14decode." And by asking the middle node
109. 5:16to decode in order to get the three
110. 5:19numbers x1, x2, x3 from one to three,
111. 5:23the total cost of the network is eight
112. 5:26transmissions rather than nine
113. 5:27transmissions. This is basically the
114. 5:29throughput, right? throughput is you're
115. 5:31trying to send as few transmissions as
116. 5:34possible in the network in order to
117. 5:36recover the three numbers that you
118. 5:39wanted to recover.
119. 5:42The problem here is we've talked about
120. 5:46number of transmissions but what about
121. 5:48time here I have to send four numbers
122. 5:54which in terms of time is going to cost
123. 5:57me four units of time and then I send
124. 6:02have to get all four numbers.
125. 6:06Obviously, one of them uh is missing,
126. 6:09but I have to wait for four time slots.
127. 6:11Okay, so four time slots here and then
128. 6:16I'm going to have to do that again. So,
129. 6:18four time slots plus four time slots,
130. 6:21it's for a total of eight time slots.
131. 6:26So, I'm going to put squares around the
132. 6:28time. This is time. So this is number of
133. 6:32transmissions and this is total time. It
134. 6:35cost me eight transmissions and eight
135. 6:39units of time. All right. What if I do
136. 6:42something different? What if
137. 6:46I transmit and I don't decode,
138. 6:52but I simply recode. So this is what's
139. 6:55going to happen. Now what happens if the
140. 6:58middle node doesn't just do dumb
141. 7:02forwarding which needed more total
142. 7:04transmissions doesn't do decoding and
143. 7:08recoding which requires a lot of time
144. 7:11but actually does randomly network
145. 7:13coding. Let's work through this example.
146. 7:16So at time one over here up top um I'm
147. 7:21showing what I'm transmitting on the
148. 7:23link on the bottom right above this. So
149. 7:27I transmit X1
150. 7:29from one to two. Two has nothing to
151. 7:31transmit so it's blank. At time two, I
152. 7:36transmit two X2 from one to two and two
153. 7:42now has X1 to transmit.
154. 7:46At time three, I transmit X3. Now,
155. 7:49recall that in our example, two got lost
156. 7:53in going from one to two. So, it
157. 7:55actually didn't make it. And therefore
158. 7:59in the link from two to three, node two
159. 8:02only has x1 to transmit because the
160. 8:05second transmission had been lost in our
161. 8:08example.
162. 8:09Now at time four, the transmitter one
163. 8:14transmits the sum x1 x2 x3 to node two.
164. 8:19And what is the link from two to three
165. 8:24going to transmit? Well, the link from 2
166. 8:25to three at this point has two numbers.
167. 8:28It has X1 and it has X3. Maybe it goes
168. 8:30ahead and sends X1 plus 2 X3. Okay, time
169. 8:35five
170. 8:37transmitter is not going to transmit
171. 8:39anything anymore here. What are we going
172. 8:41to transmit from 2 to three? Well, let's
173. 8:45see what two has available at this
174. 8:46point. It has received X1.
175. 8:50It did not receive X2.
176. 8:52It has received x3 and it has received
177. 8:56the sum x1 + x2 plus
178. 9:02x3. Okay. So maybe what it does is it
179. 9:06goes ahead and sends another equation
180. 9:10say
181. 9:142x1
182. 9:16plus
183. 9:18x2. So it adds uh x1 here to this
184. 9:22equation. Uh plus maybe 3
185. 9:28x3. Okay. So that's the equation. And
186. 9:30what it did is it added 2x3 to this
187. 9:33equation here at the bottom. 1 x1 and it
188. 9:36got to 2x1 + 2x3 + 3x3. So now what does
189. 9:41the receiver have? Remember that a
190. 9:43receiver basically
191. 9:46um was losing the third transmission
192. 9:49from two to three. So in this case the
193. 9:52third transmission from 2 to three would
194. 9:54have been um the the first the third
195. 9:57time slot. So the third time slot was
196. 9:59this one. Okay. So not the third
197. 10:01transmission but the third time slot. So
198. 10:03the third time slot was basically x1 x
199. 10:07this multi this extra x1 got lost. So
200. 10:11now the receiver has x1 x1 + 2 x3 is
201. 10:15able to recover x3. Now it knows x1 and
202. 10:18x3 is able to recover x2 with the last
203. 10:21the last equation. So how many time
204. 10:23slots did we have? Well, we had a total
205. 10:27now of just five time slots.
206. 10:31How many transmissions did we have?
207. 10:34Well,
208. 10:35the first link did four transmissions
209. 10:39and the second link did four
210. 10:41transmissions. They overlap everywhere
211. 10:44except at the beginning and at the end
212. 10:46where at the end the first link ceases
213. 10:49to transmit and at the beginning the
214. 10:53second link doesn't start transmitting.
215. 10:54So they're basically pipeline. That's
216. 10:56what we call pipeline.
217. 10:58So what do we have? have a delay of
218. 11:02five. And how many total transmissions
219. 11:05did it cost me? Well, it actually cost
220. 11:08me just
221. 11:11four over here and four over there. So,
222. 11:15same number of transmissions as if I was
223. 11:19encoding, decoding, encoding, decoding,
224. 11:23but massively, massively lower number of
225. 11:27time slots. So this is why doing
226. 11:32recoding
227. 11:34at the intermediate node
228. 11:37gives you a actually provable optimum
229. 11:41throughut. That's to say most efficient
230. 11:43use of
231. 11:46total number of transmissions for the
232. 11:48numbers that got actually received and
233. 11:53gives you this massively lower delay
234. 11:56than doing encoding and decoding. So if
235. 11:58you want to have both throughput and low
236. 12:01delay, low latency, this is why you need
237. 12:03to use recoding.