0:41

Okay, and it can start from a cold start, meaning that nobody has an idea about

existence of any other node other than yourself.

Now the good thing about these messages is a.

They're short. How short?

There're basically three fields here, for each message.

Node ID. Who am I?

Destination ID. Which destination are we talking about?

And cost of the mean cost path. Okay, so may be is this A, I am A, I can

get to B with five units of cost, okay that will be one message, and you send

this message to your next door neighbors, okay those that you have e- address link

pointing too, so this is only local interactions of the messages, no need for

broadcast to the rest of the world and finally at the conclusion of this protocol

each node only has a local view. Of the topology.

For example, at the conclusion of the protocol, I ask a particular node A and

1:43

say, Well, you've successfully completed this Bellman-Ford calculation.

Can you please draw me the graph now? Say, Well, nope, I does not, I do not know

the topology, the graph. I only know, if there is a packet for node

B, I will hop forward this to some of my neighbor.

And the minimum cost to get to B is this much.

That's it. I have no idea how my neighbor actually

would carry through the rest of the job. And I don't need to, that's the beauty of

this. That you can even have no one with a low

global bird's eye view of the topology and yet collectively they have accomplished

this routing. Now, compared to routing back when we were

talking about small worlds in the social network.

We want not just a polynomial of the, logrythmic of the size of the network.

An order kind of result. We want a practically very efficient

solution. But, the benefits that we can allow these

message passing, okay. Because their message passing is on these

kind of causing, cause path, it's called the distance vector.

3:00

Based intra-domain routing, routing within the same company's network.

Now, in the actual routing table that forwarding will be using, you'll of course

have your ID, the destination and the corresponding min cost path cost.

You also need another information, which is the next hop, let's say, node C.

This is one of your neighbors. You're going to have four fields in the

routing tables. Each row.

And then, when you broadcast out the message, however.

When you send the message only to your local friends however, you only need to

send the first three fields. You don't even need to tell your neighbor,

how you're going to finish the job. That's your business, it's none of their

business. They don't need to know how you do your

part of the job. They just need to know, the cost it takes

for you to get to this destination. So the message pass of three of you each

row of the routing table actually consists of four fuse.

So here's a small example. It's even smaller than before.

Four notes by five links, each link's bidirectional.

The number next to links one, one two three five are the link weights.

4:12

Please do not eyeball the answer. Please do not use a centralized

computation. Instead we'll look at a distributed way to

compute Bellman-Ford. You think probably that this is painfully

slow and kind of stupid, but just bear in mind that A, computers can do this real

fast and B in a practical situation, you cannot afford to eyeball the solution, not

even centrally compute the solution. You have to start with co-start, where

each node does not even know the existence of the other nodes.

So at time zero, at initialization, the routing table is very simple for each

node. Say for Node A,

The four fuse are, I'm node A, I can get to A, with zero cost, of course.

And the next hop is node A. And that's the only row in the routing

table for node A. Similarly, B, B zero B, is the only row in

the routing table for node B. So at the conclusion of 0th iteration the

message you send is just AA0. I may, I can get to A with zero cost and

you will tell that to your neighbors A, B and C.

Similarly B, C, D will send this similar message to their neighbors.

So now at T equals to one, the first iteration.

How can we find out the, the answers? So let's say, not just for destination A,

let's say, for node A, okay? Let's construct the routing table for node

A during the first iteration. Well, for node A to get to node A, I still

write down AA0A, that's clear. What about node destination B?

Alright. So, for A to get to B , it will be the

mean of the three neighbors . Numbers going through neighbor B and for B

to get to B going through neighbor C for B to get to C.

7:05

So this is min of three plus zero , one plus infinity, infinity because from the

message you received from node C, you see, hey.

It doesn't even know the existence of node B, so it can't get to node B.

And five plus infinity. So, again, you know three, one, five ,

these three numbers, because it have one route of communication.

And you know zero infinity, infinity because you were reading the messages from

the last round. And this is obviously three, that's the

answer. Similarly, you can look at how do I get

from A to C? And how do I get from A to D?

And you will see the answers are, respectively one and five.

7:55

So you can now summarize this as the following.

This is the routing table for node A. Okay, I am node A, I can get you a zero

cost, go to A. I am node A, I can go to B as the

destination the, the cost of min cost past three, I should hop to B.

Send the packets to next hop as node B. To get to C, go to C, the cost is one and

you can keep going down like this. Okay,

So this is for A you can write down the similar routing tables for nodes B, C and

D as well is also in the text book. Okay,

Now you can repeat this process. What about iteration two?

You want to write down the routing tables for A, B, C and D nodes.

Here is the answer for routing table for node A.

Remember, at the end of the routing round one, A is going to send the following four

messages, same message, AA0. New message AB3.

Alright. If you want to get to B, you can go

through me. And the cost is three.

If you want to go to C you can go through me, the cost is one.

You want to go through D, then you can go through me, the cost is five.

So, A will send these three couples in each message. Four messages all together

sent to all his neighbors. Which turn out to be B, C, and D.

10:00

of three plus zero, one plus what?, One plus one Y because from the last round's

message, okay, sent to me from node C, I know C can get to node B with a cost of

one. See?

And then will be five plus two. Why?

Because from the last round of message I know node D can also get to destination B

with a cost of two. So now I can update these and the answer

is the min between three, two, and seven. That is two.

Also, next hop is now C. So instead of a three and B, those are

outdated, replaced by two and C in this entry of the routing table.

So, you can work other rest two, the other two entries as well as rest of the four

three nodes or in the text book. And this is, what happens after another

round. Now, of course notice we have assumed that

there is a synchronize clock everybody at the same notion of time and rounds.

That's not the case, I think we have one more problem talking about, what happened.

Alright, so. You can write down for node A and

similarly node B, C, D routing table at the conclusion of round three.

You can keep going but you'll realize that the routing table doesn't change any more.

Now, in reality of course there are nodes come and go.

So it may change all the time. So how do you keep track of both a

synchronous behavior of the clocks and also the nodes failure.

Those are some of the questions, practically important and explored a

little bit in the homework problem. So finally.

We have concluded this long lecture. I don't know which one's longer.

This one, or lecture four but both are very long.

Because we touched upon two things here. One is the underlying design principle of

the Internet. Why it has been so successful?

One is packet switching for scalable connectivity and efficiency.

Two is layered protocol stack for efficient modularization.

Well I should I say efficient motorization, say for smart modularization

sacrificing efficiency performance for a probability and third is distribute a

hierarchy with the help of overlay network.

Okay. Packet switching, layer protocol, power

que with no relay. We then looked at routing.

The routing has many variants and many ingredients.

Okay. Addressing, routing and forwarding are the

three main ingredients. So many different variants.

We only got the time so far to talk about a specific case.

Distance vector routing with destination based and hub by hub forwarding.

So based on the Bellman-Ford Algorithm, we can execute it in centralized way or

co-start in a distributed way with the help of those message passings.