So, today we are going to be continuing our discussion of interconnection
networks, and I wanted to say a few notes about interconnection network in general.
above in connection networks or how do I put this?
interconnection networks can be very broad.
So, sometimes people talk about this as fitting together multiple computers,
things like the internet very wide scale interconnection networks.
You can also think about it connecting things together in a very small place.
For instance on a chip or on-chip networks, and things in between.
So for instance, computers where inside of one cache for instance there's some
connection, interconnection network between different processors, or
processors and memory, or IO devices processors and memory inside of one box.
Between multiple chasis, something like a super computer, or, wide
area networks. all these things probably fall under what
we're talking about here as interconnection networks.
And I wanted to bring this up because someone came during office hours this
last week and said, oh you're talking about switches.
And switches are, in my [INAUDIBLE] class, we learned about switches as this
very well defined thing. A switch is, like the ethernet switch.
You plug some cables into it, and the definition of switching that we were
using. .
Whoops, the definitions of switching that we were
using in our lectures here, were not the same as the definitions that were being
used as a sort of Ethernet switch, or Ethernet router.
And that's, that's true. So we're looking at a much broader class
of networks here than just something like Ethernet, or IP networks.
We're looking at inter, we call them interconnection networks,
because it can be ways to connect things together.
It does not have to be a specific protocol.
So, just to, to recap, switching is the manner in which you
connect different things together. Topology is the layout, or the connection
of the wires. Routing, is the algorithm used, to route
packets across or route packets or data, or if it's a circuit-switch network route
calls, across a network. And then, we're looking at flow control a
bunch today, which is how do you actually prevent data from getting lost on a
network? Just to recap, we talked about this last
time. We have a message which is made up of
some number of bytes we'll say or some number of bits [COUGH] From a
nomenclature perspective we can split this packet into a, or we send this
message, excuse me, into a packet here. And typically, you sort of have a head
and a tail with packets. And maybe there's a destination and a
length that's pretty useful in our header and there maybe even a tail bit.
Sometimes some networks actually have bits or prologs that say the packet is,
is being completed now. [COUGH] And inside of our packet.
Our packet could be made up of multiple flow control digits, or Flits.
A flow control digit is the minimal amount of data which can be flow
controlled upon, upon a particular link, or the minimum amount of data, which is
accounted for if you will. But the flit is not necessarily the
smallest amount of data here. You can actually split that up into your
flit, if you will, into multiple fits. Where the fit is a physical transfer
digit, and a good example of this is if you have a network where let's say all of
the data going across this network is always accounted for as 32 bit works.
But the links on the network are only eight bits wide.
So a good example of this is, you're trying to connect together two chips.
You only had eight wires to connect the two chips together, so you have eight
wires connecting those two chips together.
It makes really no sense to try to flow control on any basis smaller networks,
because the smallest thing you're going to try to communicate is let's say a 32
bit word. So you're going to [INAUDIBLE] flow
control only counting on the 32-bit flit. But inside of that it'll be made up of
four bytes or four pumps or four data transfers across the actual physical
wires. And that's a physical transfer digit.
[COUGH] We, we talked about this last time circuit switching, storing forward,
and cut through, or what is known as wormhole routing, or wormhole switching.
circuit switched is you physically run a wire.
Between point a and point b and you reserve that whole length the whole time
and there's typically a what's called a call set up and a call tear down phase.
Store and Foraward is that each router along the path.
We'll buffer the entire packet and wait till the end shows up before it starts to
send ahead to the next router over. So literally stores the whole packet and
forwards it. And this is actually typically sort of
our, Ethernet routers and our internet routers will typically try to do
something like store and forward. If you don't care about latency this
makes a lot of things easier because you don't have to worry about some of the
deadlock concerns that we'll see in a little bit with cut-through routing.
Cut-through routing matters if you start to worry about latency.
Cut-through routing, you're actually going to send the head on the next router
before you've received the tail of the message, or the tail of the packet.
So you can actually worm through the network.
So one packet will actually, cou-, could potentially go across multiple routers
across, the network. And one router will not have completed
the, the packet until the next one has started.
So, to draw, sort of, an example of this, we have a packet here which is, let's say
eight words long. And we have some form of architecture
where there's let's say it's a, a ring. Our, one-directional torus looks
something like this. And we're trying to send this packet.
And we inject the packet here. Each one of these are routers, so they
have some sort of switching fabric inside of it, in this case it's a two1 to one
MUX, which will take the input and the sort of flow through case.
And we inject here, and let's say this is destined for this
output link here. We're actually going to use, multiple of
these links or multiple of these routers and links at a time.
So, we start to send, say, one here is the header.
We'll start to send the header. And then the next cycle, we'll send the
next word, and this can flow over here. And one can be here, and two can be
there. The next cycle one will be in this, let's
say there's a pipeline register somewhere along the route here.
One will be here, two will there, three will be there and we're about to send
four the next cycle. One has arrived, two is there, three is
there, four is there, five is being sent. And continues going on until finally,
eight slowly moves across the network and kind of goes out.
So we call this, , cut-through or, or wormhole routing.