CS162 Lecture 24: Networking and TCP/IP (Con't), RPC, Distributed File Systems

Well, welcome everybody uh to CS 162. We're getting down to the very end here. Um and uh there's no class on Wednesday and just so you all know. Um I would uh like to pick up where we left off and we were uh talking about a number of things in uh extending operating systems out to the uh network as a whole. And so we talked about the distributed consensus making idea. And um that that was basically a situation which you have several different nodes spread throughout the network. They all propose a value. Some nodes might crash or stop responding, but eventually all the nodes decide on the same value uh from some set of proposed values. So that's the general consensus problem. There's a simpler version which is distributed decision-making and that's where uh you choose between true and false or commit and abort or uh one of two options and essentially the job of all the nodes that are participating in some protocol here for con- consensus um are basically collaborating and eventually coming up to exactly the same decision. Um equally important to the initial process of making consensus is making sure that that's recorded for posterity and so that's basically um you know, how do you make the deci- sure the decisions can't be forgotten. So the simplest thing of course is recording on discs. But in a global scale system, you could start talking about replicating much more widely um somewhat like a blockchain application. So the particular uh type of uh distributed decision-making that we spent a little time on to talking last time was two-phase commit. And basically the key behind two-phase commit is there's a stable log on every participant uh to keep uh track of whether a commit is going to happen or not. And uh if machines crash in the middle of the protocol and they wake up uh they can look at the log to see what they've committed to in the past. The two phases of course are the prepare phase is the first one um where the a global coordinator requests that all participants make a decision to either commit uh or not. And um so basically you ask each participant what they want to do. They either say commit or abort. And they make sure to record their decision in the log as we mentioned so that if they crash in the middle, they can come up and they will never come up with a different decision than the one that they've committed to, so to speak. Um and then during the commit phase, if everybody has said commit, uh then the coordinator will tell everybody to go ahead and do the actual commit, at which point uh they all record that the final decision was commit and they go forward. And of course, if any one participant decides to abort, then they all abort. And the crucial idea here is either it's atomic atomic decision-making. Either everybody decides to commit or everybody decides to abort. And uh there's no mixing of the two, okay? And so that was kind of uh the simplest example of this. And we talked about some of the downsides of two-phase commit, among other things being that a crashed machine can prevent everybody from moving forward. And so then we started talking about alternatives after that. Okay. Um Let's see here. So the log is basically a crucial part of that. So if you go back and look at um several of the slides that I had walking through the protocol, you can see how the log make sure that we always have that atomicity property of everybody decides to do commit or everybody decides to do abort. The uh second topic that we just started with uh toward the the end of the lecture was we were talking about network protocols and we mentioned that there are many layers in the network protocols. There's the physical level which is the ones and zeros. Um could be optical uh phases, could be any number of things. We talked about the link level which is packets being sent down a single link um with their formats and error control for instance. We talked about network level communication where you put a bunch of links together for a path. We talked about transport level. We just started about that which is for reliable message trans- um message delivery and we're going to spend a lot uh a good chunk of today figuring that out as well. And so this is a rough diagram uh to keep in your mind here. The physical and link layers down at the lower level can be any number of technologies like Ethernet or Wi-Fi or LTE or 5G or whatever you like. Um and those get you one hop in the network. IP typically gets you more hops, okay? So once you got the IP protocol, then you could route from here to Beijing for instance, as long as you knew the right IP address, uh things would be forwarded hop by hop through the network. Above that level is the transport layer where we actually start doing better than just talking about machine-to-machine communication. We can actually start talking about process-to-process communication. And then of course, you build applications on top. Okay. RPC stands for remote procedure call. We'll show you that a little bit later in the lecture. Okay. So um and a lot of things are built on top of remote procedure calls. So we'll talk more about that. So this layering uh is building complex services from simpler ones and each layer provides services needed by higher layers uh that utilize those services. So this is uh something that you've known for all the time you've been in computer science at Berkeley. Layering can be a good thing. Uh the physical link layer is typically very limited. So it's one hop and not only is it one hop, but it's it's uh unreliable typically. There's a maximum transfer unit. So somewhere between 200 and 1,500 bytes are very common. Um it's only uh high performance networks inside of cloud uh processing that might have what are called um larger packets that might be 9,000 uh bytes or so, but typical 1,500 is the max you see. Um routing is limited uh with a physical link uh pa- possibly through a switch. Okay? Um what we're going to try to figure out now in the next uh bit of the lecture is if we have these limited messages that are of limited size, how do we basically build something we can use? So the physical reality is packets. The abstraction is one of messages so we can build our decision-making algorithm. So we can build distributed storage which we will hopefully get to by the end of the lecture today. Um the physical reality is that packets not only are they limited in size, but they're unordered. Um so sometimes the packets might arrive in a different order than you sent them. Uh the typical abstraction is that um random ordering is not good for us. We'd like things to be ordered. Um physical reality is that packets are unreliable. Remember when we talked about the end-to-end uh philosophy, we said um gee, the network ought to not do things that the end points still have to do anyway. And so uh datagram networks where the packets are not guaranteed to make it to the destination are the typical thing in the middle because at the end points, we have to have some reliability protocols. We'll talk a little bit about that today. Um physical reality is that packets go from one machine to another which is only sometimes useful. It's much more useful to be process-to-process. Um the reality is that uh packets only go on one link over the local network. We'd like to route them anywhere. Uh the reality is that packets are asynchronous. They kind of go when they can. We'd like them to be more synchronous so that we know when something is completed. Um and then of course, packets are insecure and we'd like them to be secure. So the reality of the physical pieces on the left are ones that we would like to be able to basically uh hide under a virtual communication abstraction giving us a much cleaner messaging abstraction. Okay? Now just to uh I I showed you this last time, but I just want to pop this up really quickly. Um IP V4 for instance, basically has a header that's wrapped around data. So you put this on the front of it and this 20 bytes have a bunch of fields including the source and destination address. So where am I going? Where am I coming from? And then a protocol which I have highlighted in red here is typically what type of IP packet is this and we'll show you a couple of those. Now um my process-to-process, the question is do I mean on different machines? I certainly mean process-to-process on different machines is something we would like to achieve. Um sometimes you use the IP protocol abstraction and go to from process-to-process on the same machine. Um and uh but by the you know, the thing that's much more interesting here for this discussion is going from one machine to another. Okay? And from one process on one machine to another process on another machine. So now, doesn't the protocol field violate abstraction somehow? Um you might think of it that way, but it turns out it's gives you enough information that when an IP packet comes in, you can put it and demultiplex it to the right protocol uh handlers. And so that's kind of a minimal um call it an abstraction violation if you like, but it's kind of a minimal uh requirement there in order to very rapidly process incoming IP packets. Now protocol can be TCP, it could be UDP, it could be ICMP, could be any number of things. So today we're going to um talk about UDP and TCP, yes. Um in particular, how do we build process-to-process communication from machine-to-machine? So looking back at this header again, notice that it's 32-bit source address and destination address. So, the source is where I'm going. Let's say that's in Beijing somewhere. The destination is where I am. That's my local machine. These are two machines. They don't say anything about which processes on those machines, like a web browser for instance or a web server. Doesn't say anything about who would like to communicate, okay? And so the simplest thing we can do is called UDP, which is a type of process-to-process communication we get by taking this IP header. This is the one I showed you earlier, 20 bytes, and adding a UDP header, which basically has a source and destination ports. These are 16-bit numbers, a length for the data, and a checksum. But, these two ports, the source and destination ports, are part of that five-tuple. If you remember when I said you create a socket from machine to machine, remember it was source address destination address, source port, destination port, and protocol. So, all five of these things that you see here together work, okay, to give you a unique connection between two processes. UDP is very simple, okay? It's another type of datagram, but one that basically goes from process to process. And so, if you see here, this is IP protocol 17, which was we put a 17 in that header. It's a datagram, so it's fully unreliable as we use it. It goes from source to destination, and it's really low overhead. And it's really low overhead cuz we just put a few extra bytes, eight bytes, on top of the IP header to get the um the UDP header, okay? And it's often used for high-bandwidth video streams and so on. And it's a a very good way to sometimes overuse network bandwidth if you're not careful because there are no restrictions on how many packets you can try to force into the network. And so a number of uses of UDP can be considered antisocial almost if you use them incorrectly. All right? And we'll we'll see how TCP is is different than that. So, all right. Now, here's this layering that we just talked about. See in the gray at the bottom here is the physical, you know, ones and zeros. And the data link layer above is that link-to-link. And so, basically going one hop goes over the the data link physical combination here to go from say a host to a router to a destination host. But, that's not going to get us very far without being able to route. So, this actual hop, the data link physical gets us from host A to to the router or from the router to host B. It's this network layer on top that's doing IP, for instance, that decides how to go hop to hop to hop using routing tables to get you from your source to your destination. Above that is going to be the transport layer, which is going to be, for instance, UDP or TCP. And then applications on top of that. And of course, applications are the ones that open the sockets. So, the reason I've got these arrows the way I do here is you think when you're writing your application that it's communicating directly with an application at the destination. In reality, what's going on is your application sends something through a socket, and it really goes through the different layers in host A. It goes across the physical and data link layers to the router, which goes up to the network layer. The router makes a decision of what next hop to go, and so on. And eventually, you get to the destination host, and then it comes on up through the application through the various layers in the operating system at the host side, and eventually into the sockets and the application. So, um these these arrows represent communication, but at an abstract level, it's only the very lowest ones that represent direct connections. Okay? And so the way we can look at, uh for instance, this communication is we can think, well, we've got an application with some data. What happens is it goes through a transport layer where we wrap a transport header around it. So, that's like the UDP ports, for instance. And then we wrap a network header on it, which adds the IP address and so on. And then we put a frame header, which is the the MAC addresses for, let's say, Ethernet, like I said. And then that goes down the physical layer. There's some bits that are transmitted the other side, and then things are unwrapped. So, this is like adding an envelope that then you put it inside another envelope inside another envelope. It gets transmitted, and then you pull it out of the envelopes and eventually get back to the other application. Okay. Um So, this wrapping is something that is basically this layering that we're using for abstraction. It can get expensive, and sometimes really high-performance routers are going to completely violate all of these layers, and they'll squash everything out and process everything at once in parallel in an FPGA or whatever. But, it's important to try to understand the process as the way I've given it to you here you here where it's putting a series of envelopes together, and then taking the series of envelopes apart. And the other thing I wanted to point out here is this from the network layer to the network layer. This is machine to machine. It's really this transport layer that hands off to the right process. Okay? So, that's where we demultiplex based on port, and then eventually the right application gets it because we've demultiplexed it at the transport layer once we've gotten through the network layer. Questions? Now let's look at these transport protocols a little bit. So, transport protocols are things that we put on top of IP. We gave you UDP earlier. That's protocol 17. That really means that you put a 17 in that red field I showed you earlier. This is a no-frills extension of best-effort IP to be process-to-process rather than just machine-to-machine like IP is. TCP, which is something which we'll talk in more detail about in the next number of slides, is more reliable, okay? It's so it's got connection setup and teardown. You discuss you discard corrupted packets. You retransmit lost packets. You make sure there's flow control so you never overflow anybody's buffers. There's congestion control so that if too many people are trying to use a link in the middle, everybody fairly backs off. And so on. And so, that's going to be a slightly different animal than UDP's. And furthermore, TCP is a stream, which I'll show you in a moment. There's a lot of examples. Obviously, there's eight bits there in that protocol field. So, there's many different things other than UDP and TCP. There's, for instance, DCCP, which is another datagram protocol. There's RDP for the reliable data protocol. There's SCTP, which is a pretty cool multi-stream version of TCP that isn't used all that much. But, so there's many different things you can put in that TC in that protocol field. So just a flashback to, I don't know, a month and a half ago, we were talking about this client-server example for a web server. And if you remember, we talked through the various setups and and so on where server gets a listen port, the client connects, and then there's a socket that's set up, and so on. And ultimately, once everything's set up, we somehow are able to write and read through the socket, and everything just works reliably as a stream. And so, we're going to talk about how that works. Now, the question here that's in the chat is sort of how many non-TCP and UDP protocols are actually used. You know, they um they're used for a lot of things that you might not normally encounter. Like, for instance, if you're um if you have a an encrypted VPN from point A to point B, some of the one of those protocols is used basically for um for the encrypted packets. And there's other versions, port 500, that's actually a UDP. So, that's not that's a UDP packet, but that's used to set things up, and then it's in the encrypted the encrypted IP after you're done. There's a number of other protocols there that are actually used in ways that help manage. So, they're on the outside of the typical connections that you run into. But, obviously, TCP and UDP are extremely common. But, once you get into another thing, I guess another good example would be when you get into some of the streaming multimedia then when you get into streaming multimedia connections, those are also other protocols. So, data link is talking about the the part of the protocol that gets you one hop. That's part of the networking protocol. Datagram is just a packet that gets tossed through the network, and that might or might not make it all the way. So, those are different things. Data link is the layer in the networking layer. Datagram is the thing that we're sending. It's a packet. So, back to our sockets here. Let's take a look at kind of what is involved in this middle part here in actually communicating. And then we'll talk about setup and teardown. So, the problem of getting reliable delivery is that all physical networks garble or drop packets. We said that already. So, the physical media has lots of problems. Like, the packets might not be transmitted or received. It might be that multiple people try to talk at once, in which case there's an exponential backoff that has to happen. If the if If transmit close to the maximum rate, you might get more throughput, but you might start losing packets, okay? And so there's sometimes there's this trade-off between throughput and and absolute reliability. There's also if you're in a very low uh power scenario, you might transmit at extremely low voltage right on the edge of a bunch of errors occurring, but you put a heavy forward error correction code on it to make up for that. And so there's there's a lot of playing with the fact that these packets are unreliable. Okay? And if you remember from the end-to-end principle again, if we put reliability by retransmitting on the endpoints, it means that things don't have to be perfect in the middle and in fact we may not want them to be perfect. We just want them to be good enough that we can retransmit and get the data through eventually. Um the other thing that's going to be a big deal is congestion. So if too many people try to go through too small of a pipe in the middle of the network, then they're going to have to stop dropping start dropping because the routers will have more input than they can for their outputs and so they're going to have to drop packets. That's kind of the IP idea. Okay. So um and there's many options I kind of give here uh insufficient queue space, a broadcast link with hosts going at the same time, um buffer space at the destination, rate mismatches, you're sending it too fast and so on can cause congestion. Uh and then the way we So we want to start with that. We have to start with that. We want to make reliable message delivery on top of that. So what are we going to do? So we're going to need to have some way to make sure the packets actually make it uh so that every packet's received at least once and every packet's received at most once. Um and that because uh if we get duplication that we're not aware of or we get dropping that we're not aware of, then all of our applications that are relying on that are going to start having problems, okay? Or they're going to have to do the all the work on their own. And uh this is a level of uh this reliability is common enough need that we're going to want to make sure that we can do that in a common facility like TCP rather than having everybody roll their own. Okay. And we're going to show how dealing with misordering in the network and dealing with dropped packets and dealing with duplication are all actually handled by similar mechanism. So that'll be nice. So TCP is really a stream, okay? So the idea is you this is the alphabet, right? A B C D. So you stream the alphabet in you know, or your bytes in on one side, they show up on the other side. Uh every byte that goes in comes out uh the other side and it you know, we don't see duplication. And the other thing about it being a stream is there's really no um we're not packetizing it. It's just you send bytes in and bytes come out. And if you care about packets, it's going to be up to you to to make a packet protocol where you say, well, every message in my connection is going to start with a length and then the data's going to be after that. And now I've got a packet. Okay, but that's that's up to you you the user to packetize on your own. Um now of course underneath the covers is all the IP packets, but this trans the TCP view is really that bytes go in and bytes come out. Okay? And there may be many routers in the middle and it just works, okay? Now this is a protocol six in that little red IP protocol point that I showed you earlier. Uh it's a reliable byte stream between two processes on different machines over the internet. Okay? And we get read, write, flush, etc. And you know, that's exactly with our web server web client example that we gave you with sockets, the sockets are going to be the things that connect on either end of the TCP and um this is basically we're going to talk about what's inside uh inside that process. So some details which we're going to go into in a bit, but um since the underlying system is uh got a you know, a limited packet size and so on, it's going to be up to TCP to take your large streams worth of data and fragment it into lots of little pieces. Sometimes in the middle of the network IP will fragment into further pieces. And so we're going to need to make sure that after we've fragmented it, we can reassemble it at the other side and we can reassemble it in order. Um it's going to use a window based uh acknowledgement protocol and I'm going to show you a lot more about that in a second to minimize the state at the sender and receiver and make sure that um the sender never sends more data than the receiver has space for and the sender never sends things so quickly that it clogs up the routers and prevents other people from using this, okay? And so this windowing is going to be important uh for both reliability and for being a good citizen in the network. And obviously automatically retransmitting lost packets. Okay? And being a good citizen. So without further ado, so one of the problems is dropped packets. How do we deal with that? And again, we've said multiple times that we uh all physical net networks can garble or drop packets. And so IP can garble or drop packets as well. And uh so that means we got to build reliable message on top of that. And so the question is how are we going to do that? Well, the obvious thing to do or or maybe not so obvious, what the thing that we do is typically use something called acknowledgements. Okay? And so the idea here is you've got A communicating with B and so A sends a packet to B and then B sends an acknowledgement back. Okay? And what is the acknowledgement good for? Well, it says first of all, B got it. It says, hi I'm B and I got this packet. Okay? And assuming that we put a checksum on the packet, then B can also detect garbled packets and just throw them out. And um in those instances, you could imagine B sending back a NACK or a negative acknowledgement. In fact, what happens is B just treats a garbled packet as one that just never arrived. And uh so that's going to cause the other mechanism to come into play. So if A sends a packet to B which gets lost along the way or garbled, eventually there'll be a timeout at A and then A will send the packet again and eventually we get an ACK. Okay? So um some questions about this. If the sender doesn't get an ACK, does that mean the receiver didn't get the original message? What do you think? So just because A doesn't get an ACK back, okay? Right. So I see no, I see I know, I say who knows. Good, this is very philosophical tonight. So just because you don't get an ACK doesn't mean that A uh didn't successful successfully transmit something to B. Like for instance, the ACK could have gotten lost on the way back. So what that means is once we do a timeout and retransmission, suddenly we've got duplication as an issue. Okay? So um what if the ACK gets dropped or the message gets delayed? Same idea. So now all of a sudden we've got issues here. Now I see somebody asking about Byzantine uh so um we're going to assume here in the moment that the network is trying to do its best to act in uh the way it's supposed to. Um so we're not going to worry about malicious components in the middle or B being malicious. So let's just look at the underlying message transmission um and then the way we we get Byzantine agreement on top of that is we uh build something on top of unreliable messages. But let's at least see whether we can um get our messages to make it from A to B. All right? So um what we've just talked about here is what I would call stop and wait. So we send, we wait for an ACK, repeat. Okay? This is like, you know, put it into the washer, turn it on, wash, repeat over and over again, right? So uh we call the round trip time is the time from the sender to get to the receiver and the ACK to get back. The round trip time uh represents basically twice of the transit time, of course. And um the receiver, we can talk about a one-way path, which is the time from when the sender sent it to when the receiver got it. And so two times D is going to be our round trip time. Okay. Um and uh we keep doing that. And as you can imagine, the problem with this is there's a lot of lost opportunities here because we have one packet kind of going at a time. Okay? And how fast can we send data? Well, we can actually use Little's Law of all things. If we've got a um B uh bandwidth and a times a round trip time kind of tells us something about the number of packets that are uh on the wire or waiting in the queue. But in fact, uh we've set this up so that we only have one going at it once. And so um the bandwidth is basically one packet per round trip time. And this depends only on latency, not on the network capacity. So it doesn't matter. You could you could basically have uh strings and two cans on it on either side here for all it matters because, you know, we're not sending very fast. This doesn't have to be a gigabit link. Okay? In fact, you could do this computation pretty simply. Like suppose the round trip time is 100 milliseconds, uh the packet's 1,500 bytes, you come up with about 120 kilobits per second, which is pretty slow. Okay? So this is clearly this stop and wait is clearly not what we want to do. We got to get some more packets going. Okay? So if you have a 100 megabits per second link, you're wasting a lot of it, you know, almost almost 1,000 times. So um and the other thing is how do we know when to timeout and and uh retransmit, right? So, here's a case where the sender sent something, the act didn't make it or it got lost somewhere along the way. Clearly, the timeout needs to be at least as long as the round trip time before we start re-sending uh because otherwise, you know, we'll re-send before getting the act back. So, that's not so good. So, we're going to need to be estimating this timeout somehow with knowledge of the round trip time. And um you know, if the round if the timeout is too short, you get a huge amount of duplication. It's too long, then the packet loss really becomes disruptive even if you just happen to lose one packet, you wait a huge amount of time to keep going, um you're going to really suffer for your communication. Okay? So, and then how to deal with duplication? I mean, here's a situation maybe where the act just got delayed and we went and re-transmitted but then the act comes in and we get another act and now we got two copies at the receiver. Okay. So, how do we deal with message duplication? Well, we put a sequence number in, okay? And this is a very simple bit bit sequence number where uh the sequence number is either a zero or a one and the idea is um the sender is going to keep a copy of the data in its local buffer until it sees an act for that uh sequence number. Okay? And then furthermore, the receiver is going to track uh packets and by having exactly two options, a zero or a one, then the receiver can figure out if the um if there's a re-transmission cuz it'll see two packet zeros in a row and it can know to throw one out because it's a duplicate. Okay? So, that when we start putting some numbering acknowledgement numbering or sequence numbering onto the packets, we can start getting rid of duplication at the receiver and figuring out how long the sender needs to hold on to things to re-transmit. Okay? We're going to call this the alternating bit protocol. Um so, the pros of this of course is it's very simple, it's one bit. The con is really uh if if the network can delay things arbitrarily, then you and you had a packet zero that might got might have gotten stuck in some router in the middle and then got transmitted later, you might not be able to disambiguate uh the um duplication with only one bit. So, clearly that's a problem and furthermore, we're still doing one packet at a time in the network. So, this this doesn't look great. So, what should we do here? To uh up our bandwidth and deal with uh more uh unexpected delays in the network. Okay, don't wait and send more packets. All right, I'll buy that. But, that would seem to make the problem of disambiguating uh duplicates at the receiver worse. So, what else do we have to do? Okay, yep, we're going to sort packets later. So, what do we need in order sequence numbers? Yeah, so we're going to need more than a bit, right? Cuz one bit, you know, distinguishing between packet zero and packet one and then repeating with packet zero, that's clearly not enough, okay? So, we need a bigger space. Larger space of acknowledgements. Okay, so that seems simple, right? It's sequence numbers. Um and now we've got pipelining possibilities cuz we don't have to wait for each act before we send more. Okay, so here's here's what we had before, you know, sender sends, receiver receives, but now we have the potential to have many outstanding packets uh and many received packets in a way that basically allows us to fill up the network. Okay, so if you look during this round trip time, what you see is during that round trip time, we have many packets that are on their way to the receiver and many acts that are on their way back and as a result, we can actually fill up the network pipe and uh start getting our actual network bandwidth back rather than something that depends on the round trip time. Okay? So, the acts also are going to serve a dual purpose here. So, one, if assuming that every one of these uh outgoing packets has a unique sequence number on it, then um clearly, we can confirm that a particular packet got back here because we see its sequence number and we can do deal with ordering. So, if we have packet zero, one, two, three, four, five, six, seven, whatever and they arrive out of order, we can reorder them at the receiver side back into sequence number order and deal with misordering, okay? And so, the acts uh in addition to this reliability aspect also help us with ordering. Okay, so this seems like we're going into a good possibility here. Now, how much data is in flight? Well, if you take round trip time times whatever your actual bandwidth is, okay, that's going to give you uh the window, the sending window that basically makes sure that you um you have a lot of data out in the network and um basically lets you fill up the pipe uh both in the forward and reverse direction. Okay? And so, B in this case is bytes per second. Remember, this is the something uh we learned in chemistry in uh high school. Basically, you got to match up your your um units. So, round trip time is in seconds, B is in bytes per second, the total here is in bytes. So, in this case, W send is how many bytes do I want to have in the network uh at once in order to make sure that um nobody is waiting for packets. Okay? And so, this W send is like the sender's window size. Um and packets in flight, if we wanted to count packets instead, we could take this sending size divided by the packet size and that tells you how many packets we need to have outstanding to fill everything up. Okay? So, how long does the sender have to keep packets around? So, that's an interesting question, right? Um Ah, so uh let's uh so, the question is how long do we need to hold on to this? And the answer is, well, until we know that a particular packet has been acknowledged, right? And so, certainly, we need to have enough buffer space in the sender to have at least uh a round trip time, probably a little bit more in order to allow us to lose some packets and cause some re-transmission. Okay? Now, the other question is would a timeout result in starting over from the beginning? Um Well, what do you think? Do we need to re-send every packet if uh we lose just one? So, good. So, it seems on the face of it that we'd want to only send the ones that haven't been act. And because we have labeled every packet with a sequence number, then in principle, we can figure out which ones haven't been received and which ones need to be acknowledged again, okay? And so, that's certainly uh plausible for us. Um now, it depends on your protocol whether you always uh have the ability to individually transmit packets or not um or whether you have to go back and do a certain range of them or whatever, but at least in principle, we have enough information to uh re-send only the things that were lost. Okay? Now, how long does the receiver have to keep the packets data? So, the data at the receiver side certainly has to be there long enough to do reordering. So, if we get a bunch of the later packets, we need to make sure we have enough space to absorb the early ones so that we can wait, absorb the early ones and then send them in order to the actual application at the receiving side. So, we need to have enough space for that. Um and also, we're going to need to store data until the application's ready. So, perhaps it has it's you know, it's busy doing something else and it hasn't executed a read against the socket yet. So, we need to hold on to data at the receiver as well. Um and then of course, you have to worry about the following. What if the sender is blasting packets at the receiver and the receiver just is too slow and as a result, a bunch of the data that was sent actually made it to the receiver only to be thrown out at the receiver. So, that seems like a probably a bad idea, right? So, here's a bunch of interesting questions. Okay, so let me talk a little administrivia here. Just remember um got a midterm not this Thursday cuz uh folks are going to be hopefully over-indulging in food on Thursday, um but next uh week from Thursday is going to be uh midterm three. Okay? And uh camera zoom screen sharing just like in midterm two, we'll mail out all your links. There's going to be a review session link that'll come out in the next day or so. Um and everything up to lecture 25. So, it's this lecture and the um next Monday's lecture and uh we have no lecture on Wednesday this week, okay? And lecture 26 will be a fun lecture. So, if there's any topics in particular you want to uh cover, let me know. And I don't think I have too much more to say on this. Um I have um a so, a question about uh is this closer to a final or closer like midterm two? Uh as I think I've said before is every midterm is in principle cumulative uh in the sense that you need to not have forgotten everything that you learned, but we will certainly focus on material uh in the last third of the class. But, um we certainly will potentially ask you questions that would require you to have not forgotten everything uh from earlier parts in the term. Now, um I'm not going to go in this in great detail, but please be careful with collaborations. I realize we're getting on to the end of the term, but remember that explaining things to something at a high someone at a high level and discussing things at a high level, but not sitting down line by line going through everything. Um, you know, if there's a lot of individual syntax transfer on homeworks and in between project groups, it's probably too much sharing, okay? And so just be careful. All right, and don't get don't get friends into trouble by asking them for their code over and over again cuz you'll put them in a bad position as well of having violated our policy. So try not to do that. Okay, I've talked about this last couple of lectures, so I don't want to go into it in greater detail. So, let's keep going on this a little bit. So, I think the idea of having a big acknowledgement space or big sequence number space and sending a bunch of messages into the network to get pipelining sounds like a good idea, but if you remember here when we set up um, queues or pipes between processes on a local machine, we had a queue in the middle and we had blocking cuz the queue had fixed capacity. So if you wrote and the queue was full, the writer would actually get put to sleep or if you went to read and there was nothing in the queue, the reader would get put to sleep. And so we would we would like to have something similar to what we had with pipes, but across the network. And using TCP, the question is how do we go about that? Okay, so buffering in a TCP connection, we have process A and process B. There's a send queue on A's side and a receive queue for that particular stream. And then there's also one going the other direction. So typically, if you remember sockets are bidirectional and when we set them up, we have queues on both sides and we want to make sure there's proper blocking, so no data gets overwritten or otherwise lost. Okay? And so single TCP connection needs four in memory queues as we just said here. And the host's window size for a connection is sort of how much remaining space it has in the receive queue. So for instance, in this case, if this receive queue has 100 bytes left in it, the host is really only allowed to send another 100 bytes until things start becoming acknowledged because we never want the host to basically overwrite the receive queue. And furthermore, just acknowledging that they've been received is not enough because the receive queue could still be full because host B hasn't pulled things out. So we really need to say is we need some way to for the receive queue on either side to tell the sender how much space it's actually got left in its queue and make sure that the sender never sends more than that. And that'll prevent us from overriding at the destination. Okay? And so host advertise its window size at the receive queue and every packet going the other direction. It's keep saying, well, here's how much I have in my queue now. Here's how much I have in my queue now. And as a result, we can do this uh, buffer management so that we never overflow a host or lose data. Okay. So the idea is we're going to build a sliding window protocol, so the TCP sender knows the receiver's window size, tries never to exceed it. Packets that it previously sent may arrive filling the window up, but we want to make sure there's never more in transit than there is buffer size at the destination. And you're allowed to keep sending data as long as there uh, there's enough space guaranteed at the destination. Okay, and I'm going to show you how that works in a second here. So the idea here is I'm not I'm going to talk about packets of space at the receiver even though normally it's bytes. And so the window size to fill is you know, we have a let's say we have a bandwidth of packets per second times the round trip time is going to tell us how much we want to have in flight at once. And this is a form of little law is again little's law again to figure out sort of how much we can go with. But for instance, here's a case where we have an act packet which we're going to call packet one that got sent. Um, another uh, packet. So now the send window is got it says it one and two are outstanding. Here it says one, two, and three are outstanding and we're going to assume that we're not allowed more than three packets at the destination. Eventually, what happens is because one came in in order, we've received it and we potentially sent it up to the application. At that point, the receiver will say, well, I actually now have space in my destination for another one. Okay, at which point we'll send another one and so on. Okay? And so this explicit tracking of and here the receive queue is basically never holding on to anything. It's sending it up. So each one of these acts is basically saying, well, I still have three available. I still have three available. I still have three available. But you can imagine if the receiver was basically um, holding on to it, but the application the receiver wasn't absorbing it, then this queue would start filling up. Now, what if you never get an act from the receiver? So what happens in that case is that if we go back to this point, um, this sender will stop sending because it only knows that it's got three packets worth of space and it'll stop. And if there are no acts that comes back, then at that point I'll resend I'll start resending from the earliest one that's missing. So I'll start resending one and then two and three over and over again waiting to finally get an act back. And once I got an act, then I can go forward. So the the short answer to what happens if you never get an act is you you go up to the point at which the receiver has enough buffer space and then stop. Um, timeout doesn't necessarily it it might reset a little except for the fact that if I timeout at this point, I'm going to keep resending stuff that's in my send buffer and when it gets to the receiver, the receiver knows it there is space for it cuz it's the first slot in the receiver's buffer queue. So I'm never going to get past sending packets one, two, or three until I get one of them actually act and then I can send packet four. So it isn't a full reset on timeout. It really is a oh, some of the stuff that I thought that you thought you sent must not have gotten there cuz I got a timeout. I'm going to resend things. Okay, so the difference between timeout and acknowledgement is timeout is a resend. Acknowledgement is move forward. And notice how this window here is advancing. So once I've got this first act, now I've got two, three, and four here are in my sending sliding window and at the receiving side, potentially I've got these guys have came come in here, but I'm forwarding things up as quickly as I can and so we're never building up any buffer space at the destination. I'm going to show you in a moment what happens if you do build up at the destination. Now, here we go. So TCP windows in bytes, not packets. Okay, so if you look um, we can think of the space of sequence numbers now in TCP is not a packet count, it's a byte count. So what you can imagine, remember TCP is a stream, so there's a continuous stream going in. We have an arbitrary sequence number that we start at and then we can look at this space of sequence numbers where each sequence number represents another byte in the stream. Okay? And so we have the set of sequence numbers representing bytes that have been sent and already acknowledged. We have the set of bytes that have been sent but not acknowledged and the set bytes that haven't been sent yet. But this is a continuous stream from the initial sequence number incrementing by one each time. And then at the receiver, we have the same set of sequence numbers. Okay? And so we have this side are parts of the sequence numbers that have been received and potentially given to the act to the application. Here we have ones that have been received and are being buffered and these are ones that have not yet been received yet. So this buffer here in the middle is the thing that we want to make sure we never overflow. Okay? And I'm going to show you how that works in a moment. Okay? All right. Questions? So we're not acting on packets, we're acting on bytes. And that means we can act a whole group of bytes at once by giving the sequence number of the end of the bytes. Let me show you and this is this is where packets come back into play. But here's an example of the receiver's um, receive queue. This is an acknowledgement that came back from the receiver to the sender. Okay, and what it's saying here is we're on sequence number 100 is the next sequence number that I'm expecting and there's 300 bytes worth of space in my queue. Okay, and so now we're going to send a packet in TCP that says here's sequence number 100. It's got 40 bytes in it. So that means that after this packet's received, what I acknowledge is I'm going to acknowledge 140 is my sequence number because I've received 40 new bytes from what I had before and furthermore, notice that what I'm saying here is that the the buffer now only has 260 bytes free, no longer 300. And as I go again, you'll notice that the number of bytes free keeps going down. So, what that tells the sender is that the buffer on the receiver side is filling up and it's never going to send out more into the network than it knows is available. So, at this point at 210, it knows that um sequence number 190, it can do another 210 bytes above 190 and be okay. Okay? Now, here's an example where something happened to a packet in here, the one that was sending between sequence number 190 and 230, and it's got lost somehow. But, we sent another one which was sequence number 230 with size 30 and we got back an acknowledgement which might not be what you expected. If you look here, what you see is the acknowledgement says, "Well, the the latest most sequential thing I've received is at sequence number 190." Okay? And there's 210 after that that's available. So, this particular base TCP protocol acknowledges the sequence number that represents a solid set of bytes up to that point and ignores holes and other things that might have been received beyond it. Okay? Now, um this is useful if you can imagine because what it really says is it's yes, it's uh it's got back a you know, it got back some data and received some data, but it doesn't make sense necessarily to acknowledge this fully yet because uh it's not useful to anybody in the streaming protocol. Now, let's look a little further. You can see that this continues for a while and we haven't changed anything about our acknowledgements. And the reason for that is we were missing bytes between 190 and 230. And eventually there'll be a timeout. We're going to retransmit the missing data. And if you notice what happened there, we fully filled in the hole because the buffer at the receiver is doing the right thing. And the acknowledgement that comes back now is, "Oh, I've received everything up to sequence number 340 and by the way, I only have 60 left." And so then we can finish this up, etc. And at some point when we start feeding these up to the application because say it did a read of 40 or 30 or whatever it is, then these acknowledgements will start coming back and saying, "Oh, here there's more space in my buffer." So, if you ever wondered why when you set up a TCP channel and you start sending data and the other side freezes and doesn't the other application isn't absorbing the data, then the TCP channel will literally shut down because it knows that there's no buffer space at the receiver. All right. So, um All right. And at that point basically we've shut down because we've filled up all the buffer space and the application at the receiver side isn't absorbing any and so the sender is is stopping at that point. And the way this worked out for us is all of the information we need is in this queue size at a given sequence number and so that'll allow us to put in as many bytes into the network as we want in a way that won't violate this notion that all the bytes in flight would fit in buffer space at the receiver. So, we have enough information to never violate that. The only other thing now is to only send enough data out into the network to try to meet that round trip time times bandwidth requirement. It's actually the bandwidth of the slowest link in the middle. Uh and no more because otherwise we'll start causing congestion. Okay? So, here's a question. So, during the time when the 190 packet's missing, let's just go back here. What if the sender sends too many packets and causes the receiver buffer to be full since So, the thing here is it's not going to send uh too much It's not going to send 210 bytes past the one it's sent. It's sending 210 up to 210 bytes past the 190. So, it knows that this is the space that's free and it's that means it knows that past 340 it doesn't have more than 60 here available. So, it's not going to send anything past what would fit in this. And it's up to the receiver to reorder based on sequence numbers to put things back in the buffer. Okay? Now, what if you already go beyond 400 before retransmit? Again, that's not going to happen because we are never going to get the go-ahead to transmit beyond 400 until the the buffer space opens up here. Because when we get to this point, um we will never have sent beyond 400 because we will know that that would bring us down to past zero and so it'll never happen. And it's only when this opens up again after these have been absorbed by the client that we can start sending again. Good. So, congestion's an issue. So, congestion is because we have too much data flowing through the network. Okay? And if you look, all of this different data is all using shared links. And so IP's solution here is to drop packets. And the question might be what happens to a TCP connection? Well, you end up with lots of retransmissions. So, if you drop lots of packets, what you saw there is you end up with lots of retransmissions. By the way, I should say back here on this particular example, I want you to notice that the sender knows where the data was missing because it knows that it was at sequence number 190. And the moment it sends that missing data, notice that the acknowledgement went way all the way up to where it's still missing. And so, at that point the sender is not going to retransmit the remaining stuff. It's going to pick up where it left off. And so, we don't get duplication there. Okay? And there are protocols that let you know more about more holes than one at a time, but now we won't go into that now. So, with congestion, we need to limit congestion. Okay? And so, why do we get congestion? Well, there's shared links in the middle and there's too much data going into the shared link. And so, whatever router is at one of these shared points starts dropping packets. And so, what we really want to do is we want to back off so that we don't um send too much data. And so, we want to back off so that everybody that's sending together the rate uh doesn't exceed the rate of the router and outgoing links. Okay? And so, that's a congestion avoidance property. And so, we can really figure this out like how long should a timeout be for resending messages? Um so, clearly if it's too long, we waste time if the message is lost. If it's too short, we retransmit even though an ack will arrive shortly. So, we need to be tracking the round trip time clearly. But, there's a bit of a stability problem here. So, if there's more congestion, then acks are delayed and you start getting timeouts which send more traffic which cause even more congestion and you start um getting this positive feedback loop that causes everything to break down. Okay? And so, you got to be very careful to choose the sender's window size, not the receiver, but the sender, how much data it's going to allow to be outstanding so as to avoid congestion. To avoid this positive feedback loop. And obviously the amount of data the sender can have outstanding has got to be less than what's at the receiver so we don't overflood it, but it's probably going to be less because we're going to be trying to match the amount of data we have in the network with the round trip time and the bandwidth of the slowest link in the middle. So, we're going to try to match the rate of sending packets with the rate of the slowest link. Um there's an adaptive algorithm which is going to adjust the sender's window size. And there's a lot of interesting things a lot of interesting algorithms that have been developed over the years to deal with that. I have one up on the reading for for tonight. The Van Jacobson paper starts talking about this a little bit if you're interested. Um but the basic technique is going to be I'm going to start small and I'm going to slowly increase the window uh until I start getting acknowledgements missing. So, once I've got that to be too big, I know that I'm sending too fast and I'm going to back off. And that's the basic way that these adaptive algorithms try to get enough data in the network to make maximal use of that slowest link, but without causing congestion. Okay? This is called slow start which is you start sending slowly. And typically what happens is when you start receiving um uh when you start receiving acks being lost, then you cut in half and you work your way up. And so, typically there's a sawtooth uh behavior as it's trying to adapt and figure out what the right amount of data to be in the network. Um the cool thing about these kind of adaptive algorithms is that if a new person comes along all of a sudden, the ack the acks will be lost, you'll start losing packets. Both will back off until they hit a situation where they're both equally sharing the link in the middle. And that's kind of the way these congestion avoidance algorithms work. Um and so you can take a look if you actually measure what TCP does, you get this uh typical sawtooth behavior around uh around the right bandwidth for that middle link. So, um the question here is aren't acks more more likely to be timed out with smaller windows? I'm not sure I fully understand there. The acks are coming back in the other direction. Um and the acks uh are basically reflective. What's happening is when you see that the same ack comes back over and over again, you know that the data you sent out got lost. And so, that's that's the notification that the forward packets have been lost. And that's the point at which you make some decision to back off the amount of data you have in the network. Okay? Now, um so if you recall the setup, remember this where you request a connection, the server socket's got to is listening, um it it takes the connection, it constructs a new five-tuple style uh of connection between two sockets, and then it lets you go. And so um remember the five-tuple is a source IP address, destination IP address, source port, uh destination port, and protocol like TCP. Um and that setup is really setting up a TCP channel. Okay? And so what does that mean? So to establish, we have to open a connection, that's a three-way handshake. Then we do what we've just been talking about, which is transmitting data back and forth, and then we tear everything down when we're done. Okay? And so here we're back to this client server, but now let's look at uh this part, which is the setup. Okay? And it's really a three-way handshake. So the client uh so the server is causing a calling listen over here. The client calls connect, which sends a uh a request over, all right? And it looks like this. It's a SYN, synchronous uh bit is set in the header. It it proposes a sequence number for communication from client to server. The server uh accepts the connection, it sends back um an acknowledgement on that forward SYN and a new SYN for the other direction. Okay? With its proposed sequence number. All right? And then finally there's an ACK coming back. So this last ACK is ACK'ing the server's uh connection um from server to client. So it's three uh three messages. And when you're done, you've both agreed on a sequence number in the forward direction, a starting sequence number in the reverse direction, and you've both agreed that this is a connection that's going forward. Okay? Great. Um the other thing is just to show you the shutdown. So shutdown's actually a a four uh hop thing here. So when host one is done, it sends a FIN bit in the header. The host ACKs the FIN bit, but it also reacts the FIN bit, and it sends its own FIN bit. Um So this is a FIN ACK, excuse me. Um and the remaining data uh and then eventually it closes things down with a FIN and you get a FIN ACK on the other direction. So there's actually four uh control messages to shut down. Okay? And then eventually after a timeout, everything's deallocated. So. All right. And I'm not going to um not going to go any further on this, but just like regular files, if you have multiple file descriptors open on a socket, then the socket's only really shut down when all of them close. Okay. So how do we actually program a distributed application? So we need to synchronize multiple threads on different machines. Um so if you remember this is from last time I was talking about messages. And so now we've got this idea of how to build a reliable stream in both directions. Um and so the question is now, what next? Well, suppose we want to build an application on top of this. Well, one of the things that comes up is what's the data representation? So an object in memory on one side has a very machine-specific binary representation that may mean nothing at the other side. So if you're trying to send data from host A to host B, and you want it to be understood on host B, what are you going to do? Well, you're going to have to agree on some standardized way of communicating with each other. Okay? And so the absence of shared memory, um externalizing an object require us requires us to basically take an object, which think of a linked list for a minute, right? It's a bunch of uh objects that are all linked together with addresses and all that sort of stuff, and we need to serialize that into bytes so that it can be sent over the uh over the link. Okay? And the serializing into bytes and then marshalling it together into an object uh the object together into a message and then sending it off uh is what you do at the sender side. On the other side, you unmarshal, so you take it apart, and you deserialize it back into a local representation on the other side. And it's possible that the two communications are um or excuse me, the two hosts have different representations. Like one might be big endian and the other small endian. I'll remind you what that is for a moment. So this serializing and marshalling process has to be done in a way that allows the two hosts to communicate no matter what their representation for various things are. Okay? So simple data type, let me just show you this for instance. Suppose you got a 32-bit integer, and I want to write it to a file. So let's back off from sockets for a second. Um you open the file, okay, that's all fine and dandy. And then you have a couple of choices. One, you could actually print it out as an integer in ASCII text. The other is you could write it as a binary in with four bytes. Okay? And um those two things look very different in the file, and the person the person the the application that reads it back in uh needs to know which it is, otherwise it's not going to be able to interpret them. Okay? So neither of these two things are wrong, but the receiver needs to be consistent. Okay? And this gets even more tricky when you're going across the network, because uh if I'm trying to send uh you know, a four-byte number, 32 bits, across the network, uh how do we know that uh the recipient has X in the same way? Okay? Like for instance, if you remember uh from 61C, they talked about endianness. Like uh several of these different types of machines uh are big endian, a number are little endian. Um and the question is sort of how do we match those up if we're trying to communicate. Okay? Here's a good example of a of a little endian machine where we take a an integer uh 0x12345678, and then we uh we scan through the uh actually the uh the least significant byte of the integer is actually in the first byte in memory. So this is clearly a little endian machine. Okay? And you can write this endianness uh uh routine on your own and try running it. Okay? And see what you get. So what endianness is the internet? Well, the internet has chosen big endian as the standardized network byte order. And so typically what happens is when you're sending something across the internet, you actually put network byte order uh you put things in network byte order, and then the other side unpacks them from network byte order into its local host order. So um so you have to decide on wire endianness. We just decided for instance, if we're talking across the network, it's typically big endian. And then we convert from the uh native endianness to the on-wire format that's in the source side of the communication, and then we unpack it on the other side from the on-wire endianness to the local format. Um now, a downside of this perhaps is the fact that if you take two little endian machines, and they communicate over the network, they're both going to uh convert and uh convert to and from big endian to make that communication happen. So the question is what's the uh is there a rationale for big endian versus little endian on the web, or do you mean in different processors? Uh you know, the web if you're asking why why it was big endian network byte order, um I think the good thing about big endian is you can look at uh numbers in if you were to take a hex dump of some memory, and you look at a big endian number, you can just read it directly out. So big endian kind of has that nice property that it's uh it requires a little bit less brain gymnastics to read through a memory dump. Um that would be my uh my only uh explanation of why that was preferred. I don't know. Um I guess at this point, it's all about standards, and so I I could just say, well, it is what it is, and we got to stick with it. But um I think probably people like big endian cuz you can read it directly out. Now, I grew up with little endian processor assembly language design when I was young er, and so um I'm not as thrown for a loop when I see little endian numbers, cuz I rescrabble them in my brain, and it mostly works okay. But anyway, I think that's the reason people like the big endian, cuz you don't have to rescrabble. What about richer objects like lists and whatever? What do you do? Well, if you want to transfer a linked list of structures from point A to point B, you got to come up with some standards for serializing that so that they can be packed and unpacked. And there's lots of serialization formats. There's JSON and XML, you name them. In fact, if you were to Google data serialization, you'd find a whole bunch of different types of serialization. So there are many languages, there are many serialization formats. Um so of course this is a new issue with standardization. You have to make sure that when you're using a serialization mechanism from point A to point B, you actually do the right thing to uh to do that serialization. Okay? Now, um so raw messaging, where you just send a message from one side to another and then you build something out of it is pretty low-level for programming. You have to do a whole bunch of stuff on your own and you also have to deal with machine representation by hand and calling the things we said back there. The alternative is a remote procedure call idea which you call a procedure on a remote machine and the idea is to make communication look like an ordinary function call. And you're going to automate all the complexity of translating between representations. Okay, and so uh for instance, the client might call uh remote file system read rutabaga and at the uh remote side, the thing reads the file rutabaga and sends the results back and as far as the client and even the server is concerned, they're just um executing a function call and getting a return. Okay, so that's called a remote procedure call. And the concept here is pretty simple. So here's the client. Um it wants to execute this function of two arguments which turns out it's going to be on a remote machine. What's going to happen is to call, it's going to go through what's called a stub which is going to marshal all of these arguments V1 and V2 and put it into a standardized serialization format of some sort, send it to the receiver. The receiver stub is going to unpack it, call the the function on the server side. Server is going to give a return value. We're going to go back the other direction. Okay, and then return at the client. If you notice um really these stubs are things that are just linked into the client and the server like regular uh library function calls and they have this nice property that when you link function F with this stub, what really happens is when you call F, it ends up sending and receiving messages, okay? And the server when it links with the server stub is really going to end up uh giving its functions to be called by remote clients and um however when you write the code inside the server, you're going to just be writing normal functions. Okay, and so this is um this is basically the uh this is basically the idea of remote procedure call. So as far as the client's concerned, they're making a procedure call but it's happening remotely. Okay, and so really um we can talk about the client stub interacting with handlers that send messages across a network um on multiple machines and that this is really a machine machine boundary. Okay. And really there's also a um application application boundary. So we're going to wrap some ports in here on as well. Now, can you use RPC for interprocess communication on the same machine? Absolutely. Okay, and what's kind of cool about this, that's a good question, is really that uh you could start out with this server on the same machine and then if the machine got overloaded, you could migrate the server to another machine and as long as you clean up the packet handling stuff so that the packets are now directed at that remote machine instead of the local one, you don't even have to change the code. All you see is a change in performance. Okay. Now, um so the way that this implementation works in general is request response mess message passing under the covers. The stubs on both sides are providing glue on the client and server side to glue functions into the network. So the client stub is marshalling the arguments and unmarshalling the return values. Uh where marshalling is putting into a packet, taking out of the packet. They're also responsible for um doing the data representation serialization we talked about. The server stub stub does the the opposite. Okay, so marshalling involves converting values to canonical form, serializing the objects, copying them to uh be passed by reference, etc. Um and so some details here. Um there's an equivalence uh really between, you know, the parameters of the function call uh go into a request message. The result is a reply message. The name of the procedure is typically passed in the request message um and is used to decide in the receiver stub which function gets called. Um there mailboxes on either side, so you need to know both the IP address and the port on each side in order to do this connection. The interesting part about this is there's a stub generator which is really a compiler that generates stubs. So what you typically do is you define your RPC with a um interface definition language or IDL which contains among other things the types of arguments, the return values, etc. The output is going to be stubs in the appropriate source language um and and when you you design your interface by writing in the IDL and then when you produce that of the compiler, you now have code that you can link in at both the client and the server side and now you're able to do RPC. Okay. Um so the way we deal with class cross-platform issues is exactly what we just talked about. We're going to convert everything to and from a canonical form and this is where your particular type of RPC, so there are many types of RPC out there, will define as part of it what is the canonical form or what is the way that things are serialized. Okay, so that's a part of the RPC package. So how does the client know what they're connecting to? Um typically you translate just like with regular DNS and IP, you're translating the name of the remote service into a network endpoint, remote machine, port, maybe some other information. And the process of binding is the process of converting basically a user visible name for that service like a file server or something else into a network endpoint like an IP address and port and then um connecting it all up and so then once you do that, now the client can just be doing procedure calls and they're going to the remote machine. Okay, this is another word for naming and you could either compile in the destination machine or you could um have a dynamic check at runtime. Now the question is when are the stubs initialized? So the stubs get linked into the program and they get initialized at the um kind of before you actually start executing code that has the RPC in it. So there is this initialization process which you would call into the RPC library to do the initialization stuff and once it's now connected, then you can make your calls. So um this dynamic binding uh is good because most RPCs use dynamic binding via some name service just like uh if you were interested in, you know, www.berkeley.edu, you go to a dynamic DNS service to find the current IP address. Um there's uh most RPC systems have a dynamic binding service where you say what service you're interested in, certain file service of a certain name and it will figure that out for you through a binding process and decide what the actual IP address is and so on, what the port is. Why do we do this? One, we can do access control um to basically not even give back the names of machines if people are don't have access. The other uh is failover. So if the server fails, we can um basically failover to another one just by changing the binding. Um if there's multiple servers, you can have flexibility of binding time. So I mentioned uh last time or the time before that Google does this a lot. When you go and do a Google search and you do it from uh Northern California versus um I don't know, Boston, you're going to get different places for Google. Um in fact, you're even going to get different times of the day. You might get different service server names or the same server name, different IP addresses from the Google resolution and what they're doing is they're balancing load that way. And so that's why a dynamic RPC service is good that way as well. Okay. I think that's all I wanted to say there. So what are some problems with this idea? So this seems really cool. Um different failure modes in a distributed system than on a single machine. So, you know, think about the number of different failures. If you're um maybe a user level bug causes an address space to crash at the other side or a machine failure, kernel bug causes all processors on the same machine to fail or some machine is compromised by a malicious party. So in the old before RPC, what you would end up with is um a crash is a crash is a crash. Pretty much everything fails. After RPC, you're now reaching out to different services on the network and it could be that you get partial failures because only some of them are working. Okay, now the question here, does RPC usually run over TCP? Uh it it's uh either runs over TCP or if it runs over um UDP which it can occasionally, um it's got to have its own reliability protocol underneath to make sure things work. So um it often uh running over TCP is certainly the simplest thing for it to do. So before RPC, the whole system would crash and die. After you got partial failures, okay? And so you end up with an inconsistent view of the world and um you're not sure if your cache data got written back or not. You're not sure if your server did what you want. And so the handling of failure gets much more complicated in an RPC world but you gain the ability to have uh your services handled from many places. Okay, so the problem that RPC is a solution to, again, is that RPC basically gives you a nice clean uh way of looking at remote communication just as a file as a system call. Excuse me, strike that. It basically lets you look at uh remote communication as a procedure call and that procedure call uh you don't have to worry about marshalling the arguments. You don't have to to about serializing. You get the return value back into your code, is nice and clean. It looks like a bunch of uh function calls. Okay? The downside is you need to make sure that you uh are able to track failure modes carefully. And I will point out, by the way, that there are a lot of services that use RPC precisely because of the cleanliness of its interface and because it's very easy, as I said, to migrate where the services are from the local machine to remote machines without changing any of the programming. It's just that there are potentially more complicated failure modes that you have to be careful about. And you can do all sorts of interesting things with distributed transactions and Byzantine commit and stuff we've already talked about to make your RPC uh much more uh much less failure prone. So, RPC is not performance transparent, right? So, the cost of a procedure call is very much less than the cost of same machine RPC, which is very much less than network RPC. So, there's overheads of marshalling and stubs and kernel crossings and communication that come into play. So, there is a cost to RPC, but the transparency of location is a pretty powerful benefit. Um and so, while programmers need to be aware that RPC is not free, it still is used in a large number of circumstances. Um and for one thing that I will point out here is um now we have a new way for uh communication between domains. Um we talked about shared memory with semaphores and monitors. We talked about file systems. We talked about pipes. And now remote procedure calls can be a way to even do local communication. Um and so, uh you can use this communicate between things on the local machine or remote machines. And just to give you a few, there's many RPC systems. Um there's CORBA, the common uh object request broker. There's uh DCOM, which is distributed com. You'll see that in Windows machines a lot. There's RMI, which is Java's remote method invocation. There's a lot of different ones out there. Um and one thing I will point out is uh in the early 80s, I would say, there was this notion of microkernels, which we haven't talked a lot about in this cur uh this term yet, but um basically this monolithic kernel that we've been talking about pretty much puts all the protected code into uh the kernel address space. And applications run on top of that and they make system calls into the kernel. The microkernel is a little different. The only thing that's in the kernel itself is uh thread uh multiplexing, address space control, and an RPC service. And so, in addition to regular applications, all of these things that we used to think belonged inside the kernel, we now put as processes running on top of the microkernel and using RPC to communicate with one another. And so, if the application goes to read a file, what happens is it doesn't open by doing an RPC into the microkernel, which then um talks with the file system. That file system does the open, sends back a handle to the application, etc. And so, the application is reading and writing from the file system, but doing so uh basically through an RPC mechanism to other user level uh processes. Okay? And why do this? Well, um fault isolation. So, if there's a bug in the file system, it won't crash the whole the whole um microkernel, right? It's only going to crash part of what's going on. Or if there's a bug in the windowing system. Okay? Or other parts of the kernel, we basically have isolated the ability of faults to propagate because we we isolate them in their own user level address space and we use RPC back and forth. Okay? And it enforces a level of modularity as well. Okay? So, this is a good example of using RPC on local machine to uh to help with the overall structure in the kernel. Okay? All right. Now, if you'll bear with me for just uh one or two more slides, I want to set the stage for what we'll talk about on Monday. Um once we've got a good messaging service and a good way to do uh you know uh serialization and deserialization across the network, we can now start talking about how to build distributed storage. And the basic distributed storage problem is the following. We have a network with a lot of storage in it, so you guys can start thinking about all the cloud storage that you have out there. And we have a series of clients that are all using that storage. And the we can start asking some interesting questions about this. So, first of all, why bother with this? Well, this is the ultimate sharing scenario because these clients can be using that data that's in the middle of the network, no matter where they are. So, they could be in the the West Coast here using some data and then they get an airplane and uh hopefully are careful with their social distancing and their masks and they get on the East Coast and now they can read their same data or they can can be traveling and their data can be read and written while it's going. And so, this idea of network attached storage is a very powerful one. Okay? But it's a little different than the type type of file systems that we've talked to in this term about in this term so far. So, among other things, there's a what's colloquially called the CAP theorem. Okay, this was from Eric Brewer in the early 2000s. And the idea is that there can only be three There are three ideas, okay? Consistency, availability, and partition tolerance. And you can only have two of them at a time in any real system. So, what consistency means is that changes to a file or a data uh base or whatever appear to the same uh to everybody in the same serial order. That's consistency. Availability says you can get a result at any time. And partition tolerance says that the system will keep working even when the network gets split in half. Okay? And the problem that you encounter when you have a distributed system like uh distributed network storage is you start worrying about partition tolerance. Uh you know, what happens if the network is split? And you know, if you are going to be able to keep going while the network is split, then you're going to lose one of consistency or availability. Okay? So, you can't have all three at the same time. This is also otherwise known as Brewer's theorem. Um so, you can think pretty easily think about this for a moment. So, suppose that I want to um always have availability, so I can always use my file system, and I want to be able to deal with partitions when the network is split. You can see why consistency might not work, right? Cuz if I split the network in half and these clients over here are busy writing data and these clients over here are busy writing data, then I'm not really getting consistency because the file system's not consistent. It's got two different views of it on different coasts. Okay? So, that's one example of being able to only have two things. Um if I want to have consistency and partition tolerance, for instance, I want to be able to make sure I always see a consistent view, but I can deal with partitions in the middle. Can anybody explain to me why I lose out on availability when I do that? Why would I lose out on availability? Yep. The reason I lose out on availability is because to be consistent and deal with splits in the network, then I can't write anymore and so, it's no longer available to write because I can't allow there to be an inconsistent view. Very good. All right. So, we're going to pursue this next Monday on our last official class. We're going to talk a lot about distributed storage solutions like the NSF and NFS and AFS. We'll talk about key-value stores and and probably in the final lecture on Wednesday of a week next week, um which won't be responsible for on the exam, but we'll talk about uh things like Chord and CAN and um some of the other um distributed storage systems out there. All right. So, in conclusion, we talked a lot about TCP, which is a reliable byte stream between two processes on different machines over the internet. So, you get basically a stream and it doesn't matter whether it's local or remote, you get the same uh view of it. And we talked about how to use acknowledgements with window space acknowledgement protocol and congestion avoidance to make sure that um this works well and represents good citizenship. We talked about remote procedure calls, which is how to call a procedure on a remote machine or in a remote domain and uh give us the same interface as procedures, but uh remote. Okay? Um we started talking about the distributed file system and the CAP theorem. Okay? And next time we're going to talk about uh virtual file system layer and cache consistency and how we can basically build a file system into the network. Um All right. I'm going to end there. I hope everybody has a great Thanksgiving. Uh we will see you a week from today back on Monday. And uh hope everybody gets a little bit of a break and enjoys themselves.