The most basic, or one of the more basic routing algorithms that we're going to be

looking at here we're going to call dimension ordered routing.

[COUGH] And it's called dimension ordered routing because there's actually two

dimensions here. We'll label this as let's say X

increasing, we'll label this as Y increasing.

And, [COUGH] and dimension order routing says that we order the dimensions in

which we route. So, we always route it in one of the

dimensions before we go to route in the other dimension.

So, if we want to get from here to here, and let's say we have X then Y is our

routing, we're going to route this way, from A to

B first. So, now we've matched our X location to where B is, and then we're

going to route down. So, this is X and Y.

This is oblivious. It doesn't matter about the traffic.

And it has some bad problems that show up if you do this.

[COUGH] If we have let's say C and D, and it's trying to route from C to D,

it needs to share this link with traffic going from A to B.

And it can't route around it. It can't like, I don't use those links or

something else. It's just not allowed in our oblivious

routing algorithm, and definitely not allowed in our

dimension ordered. Now, dimension ordered,

there's networks that are, let's say, X and then Y and you can also have, let's

say, Y and then X. You can, this also generalizes to three

dimensional n-dimensional sort of spaces. You do, let's say X, then Y, then Z.

Or W, then X, then Y and then Z or something like that in a four dimensional

cube. [COUGH] But one of the good properties of

dimension order routing is it's not going to deadlock.

And we'll talk about that in a few slides.

But the network itself is never going to deadlock.

That doesn't mean you can't get message dependent deadlock.

But if you wormhole through the network here, you can actually come up with a

proof that shows that [COUGH] you will not ever deadlock this network.

And the, the rough sketch of the proof look goes like this.

[COUGH] By only using X links first and then using Y links,

[COUGH] you only ever acquire an X link, and then acquire a Y link,

and then release an X link, and then release a Y link.

So, you'll never actually grab a resource that you have needed, you have needed

before. And everyone else is doing that same

algorithm so they will never try to grab a resource in order that is, is, is

faulty also. So, if we go back to our sort of dining

philosophers problem here, you're guaranteed that you're going to acquire

resource one and then acquire resource two.

And everyone's doing that same algorithm so they will always acquire resource one

or block, waiting to acquire resource one and then you acquire resource two.

But you'll never see a cycle. So, because of that, you'll next acquire

X, and then Y, and then X in this dimension order of routing.

So, you'll never get a cycle in your dependency graph.

That's the rough sketch. And the, the, the full sketch is a little

more complicated. Usually, you have these two dimensional

mesh networks without end around, or without a taurus.

You have to sort of prove it in this direction and in that direction.

And then, sort of it, decomposes into sort of X from west to east, and X from

east to west, and vice versa. But, that's the rough sketch of the

proof. But, I just want to get across that.

It's a basic routing algorithm, but there's lots of other choices here.

as I sort of said there was this non-deterministic one, there's adaptive

routing algorithms. So, a good adaptive one, sometimes called

hot potato routing, is that if you, you don't have any buffering in the network,

so you can't buffer along the way. If you get to a node which has a link which is

congested, you just choose randomly some other direction, and you route that

direction. [COUGH] And the, the thinking here is

that some point you will actually be able to choose again and route towards the

right direction and slowly you'll move your, your traffic or your packet will

move to the end point. But, it allows you to sort of go around

traffic congestion points. But, I don't want to go into too much

detail on this because this is a whole lecture in itself.

Okay. So, let's talk about flow control.

This is a aspect of networking that I really enjoy, actually.