1 00:00:02,940 --> 00:00:08,936 So, today we are going to be continuing our discussion of interconnection 2 00:00:08,936 --> 00:00:15,643 networks, and I wanted to say a few notes about interconnection network in general. 3 00:00:15,643 --> 00:00:21,266 above in connection networks or how do I put this? 4 00:00:21,266 --> 00:00:23,896 interconnection networks can be very broad. 5 00:00:23,896 --> 00:00:28,278 So, sometimes people talk about this as fitting together multiple computers, 6 00:00:28,278 --> 00:00:32,134 things like the internet very wide scale interconnection networks. 7 00:00:32,134 --> 00:00:36,983 You can also think about it connecting things together in a very small place. 8 00:00:36,983 --> 00:00:40,781 For instance on a chip or on-chip networks, and things in between. 9 00:00:40,781 --> 00:00:45,455 So for instance, computers where inside of one cache for instance there's some 10 00:00:45,455 --> 00:00:49,369 connection, interconnection network between different processors, or 11 00:00:49,369 --> 00:00:53,810 processors and memory, or IO devices processors and memory inside of one box. 12 00:00:53,810 --> 00:00:57,084 Between multiple chasis, something like a super computer, or, wide 13 00:00:57,084 --> 00:01:00,524 area networks. all these things probably fall under what 14 00:01:00,524 --> 00:01:03,466 we're talking about here as interconnection networks. 15 00:01:03,466 --> 00:01:07,850 And I wanted to bring this up because someone came during office hours this 16 00:01:07,850 --> 00:01:10,736 last week and said, oh you're talking about switches. 17 00:01:10,736 --> 00:01:14,898 And switches are, in my [INAUDIBLE] class, we learned about switches as this 18 00:01:14,898 --> 00:01:18,450 very well defined thing. A switch is, like the ethernet switch. 19 00:01:18,450 --> 00:01:22,940 You plug some cables into it, and the definition of switching that we were 20 00:01:22,940 --> 00:01:23,790 using. . 21 00:01:23,790 --> 00:01:27,640 Whoops, the definitions of switching that we were 22 00:01:27,640 --> 00:01:32,023 using in our lectures here, were not the same as the definitions that were being 23 00:01:32,023 --> 00:01:34,926 used as a sort of Ethernet switch, or Ethernet router. 24 00:01:34,926 --> 00:01:38,432 And that's, that's true. So we're looking at a much broader class 25 00:01:38,432 --> 00:01:42,048 of networks here than just something like Ethernet, or IP networks. 26 00:01:42,048 --> 00:01:45,389 We're looking at inter, we call them interconnection networks, 27 00:01:45,389 --> 00:01:48,128 because it can be ways to connect things together. 28 00:01:48,128 --> 00:01:50,484 It does not have to be a specific protocol. 29 00:01:50,484 --> 00:01:56,651 So, just to, to recap, switching is the manner in which you 30 00:01:56,651 --> 00:02:04,092 connect different things together. Topology is the layout, or the connection 31 00:02:04,092 --> 00:02:08,140 of the wires. Routing, is the algorithm used, to route 32 00:02:08,140 --> 00:02:14,758 packets across or route packets or data, or if it's a circuit-switch network route 33 00:02:14,758 --> 00:02:19,741 calls, across a network. And then, we're looking at flow control a 34 00:02:19,741 --> 00:02:25,737 bunch today, which is how do you actually prevent data from getting lost on a 35 00:02:25,737 --> 00:02:31,626 network? Just to recap, we talked about this last 36 00:02:31,626 --> 00:02:35,063 time. We have a message which is made up of 37 00:02:35,063 --> 00:02:40,109 some number of bytes we'll say or some number of bits [COUGH] From a 38 00:02:40,109 --> 00:02:44,695 nomenclature perspective we can split this packet into a, or we send this 39 00:02:44,695 --> 00:02:49,406 message, excuse me, into a packet here. And typically, you sort of have a head 40 00:02:49,406 --> 00:02:53,300 and a tail with packets. And maybe there's a destination and a 41 00:02:53,300 --> 00:02:57,948 length that's pretty useful in our header and there maybe even a tail bit. 42 00:02:57,948 --> 00:03:02,785 Sometimes some networks actually have bits or prologs that say the packet is, 43 00:03:02,785 --> 00:03:06,615 is being completed now. [COUGH] And inside of our packet. 44 00:03:06,615 --> 00:03:11,602 Our packet could be made up of multiple flow control digits, or Flits. 45 00:03:11,602 --> 00:03:16,588 A flow control digit is the minimal amount of data which can be flow 46 00:03:16,588 --> 00:03:22,660 controlled upon, upon a particular link, or the minimum amount of data, which is 47 00:03:22,660 --> 00:03:28,406 accounted for if you will. But the flit is not necessarily the 48 00:03:28,406 --> 00:03:33,007 smallest amount of data here. You can actually split that up into your 49 00:03:33,007 --> 00:03:37,805 flit, if you will, into multiple fits. Where the fit is a physical transfer 50 00:03:37,805 --> 00:03:43,130 digit, and a good example of this is if you have a network where let's say all of 51 00:03:43,130 --> 00:03:48,460 the data going across this network is always accounted for as 32 bit works. 52 00:03:48,460 --> 00:03:51,473 But the links on the network are only eight bits wide. 53 00:03:51,473 --> 00:03:55,548 So a good example of this is, you're trying to connect together two chips. 54 00:03:55,548 --> 00:03:59,845 You only had eight wires to connect the two chips together, so you have eight 55 00:03:59,845 --> 00:04:02,190 wires connecting those two chips together. 56 00:04:02,190 --> 00:04:06,943 It makes really no sense to try to flow control on any basis smaller networks, 57 00:04:06,943 --> 00:04:11,391 because the smallest thing you're going to try to communicate is let's say a 32 58 00:04:11,391 --> 00:04:13,951 bit word. So you're going to [INAUDIBLE] flow 59 00:04:13,951 --> 00:04:18,826 control only counting on the 32-bit flit. But inside of that it'll be made up of 60 00:04:18,826 --> 00:04:23,396 four bytes or four pumps or four data transfers across the actual physical 61 00:04:23,396 --> 00:04:26,900 wires. And that's a physical transfer digit. 62 00:04:26,900 --> 00:04:33,064 [COUGH] We, we talked about this last time circuit switching, storing forward, 63 00:04:33,064 --> 00:04:39,306 and cut through, or what is known as wormhole routing, or wormhole switching. 64 00:04:39,306 --> 00:04:43,130 circuit switched is you physically run a wire. 65 00:04:43,130 --> 00:04:47,488 Between point a and point b and you reserve that whole length the whole time 66 00:04:47,488 --> 00:04:51,960 and there's typically a what's called a call set up and a call tear down phase. 67 00:04:51,960 --> 00:04:56,320 Store and Foraward is that each router along the path. 68 00:04:56,320 --> 00:05:00,989 We'll buffer the entire packet and wait till the end shows up before it starts to 69 00:05:00,989 --> 00:05:05,716 send ahead to the next router over. So literally stores the whole packet and 70 00:05:05,716 --> 00:05:08,656 forwards it. And this is actually typically sort of 71 00:05:08,656 --> 00:05:12,749 our, Ethernet routers and our internet routers will typically try to do 72 00:05:12,749 --> 00:05:16,957 something like store and forward. If you don't care about latency this 73 00:05:16,957 --> 00:05:21,684 makes a lot of things easier because you don't have to worry about some of the 74 00:05:21,684 --> 00:05:25,950 deadlock concerns that we'll see in a little bit with cut-through routing. 75 00:05:25,950 --> 00:05:29,980 Cut-through routing matters if you start to worry about latency. 76 00:05:29,980 --> 00:05:35,486 Cut-through routing, you're actually going to send the head on the next router 77 00:05:35,486 --> 00:05:40,640 before you've received the tail of the message, or the tail of the packet. 78 00:05:40,640 --> 00:05:44,962 So you can actually worm through the network. 79 00:05:44,962 --> 00:05:52,741 So one packet will actually, cou-, could potentially go across multiple routers 80 00:05:52,741 --> 00:05:58,600 across, the network. And one router will not have completed 81 00:05:58,600 --> 00:06:03,018 the, the packet until the next one has started. 82 00:06:03,018 --> 00:06:12,527 So, to draw, sort of, an example of this, we have a packet here which is, let's say 83 00:06:12,527 --> 00:06:17,382 eight words long. And we have some form of architecture 84 00:06:17,382 --> 00:06:24,222 where there's let's say it's a, a ring. Our, one-directional torus looks 85 00:06:24,222 --> 00:06:29,079 something like this. And we're trying to send this packet. 86 00:06:29,079 --> 00:06:34,873 And we inject the packet here. Each one of these are routers, so they 87 00:06:34,873 --> 00:06:41,008 have some sort of switching fabric inside of it, in this case it's a two1 to one 88 00:06:41,008 --> 00:06:46,717 MUX, which will take the input and the sort of flow through case. 89 00:06:46,717 --> 00:06:52,511 And we inject here, and let's say this is destined for this 90 00:06:52,511 --> 00:06:57,357 output link here. We're actually going to use, multiple of 91 00:06:57,357 --> 00:07:02,538 these links or multiple of these routers and links at a time. 92 00:07:02,538 --> 00:07:06,530 So, we start to send, say, one here is the header. 93 00:07:06,530 --> 00:07:12,382 We'll start to send the header. And then the next cycle, we'll send the 94 00:07:12,382 --> 00:07:16,131 next word, and this can flow over here. And one can be here, and two can be 95 00:07:16,131 --> 00:07:20,971 there. The next cycle one will be in this, let's 96 00:07:20,971 --> 00:07:25,713 say there's a pipeline register somewhere along the route here. 97 00:07:25,713 --> 00:07:31,434 One will be here, two will there, three will be there and we're about to send 98 00:07:31,434 --> 00:07:37,565 four the next cycle. One has arrived, two is there, three is 99 00:07:37,565 --> 00:07:42,737 there, four is there, five is being sent. And continues going on until finally, 100 00:07:42,737 --> 00:07:46,956 eight slowly moves across the network and kind of goes out. 101 00:07:46,956 --> 00:07:51,040 So we call this, , cut-through or, or wormhole routing.