The End of TCP for AI Clusters — John Ousterhout, Stanford
AAI Engineer
Internet TechnologyComputing/Software
Transcript
00:00:00Please welcome to the stage the Professor Emeritus at Stanford University, John Oosterhout.
00:00:30Good morning, it's really great to be here to talk about the network side of AI applications
00:00:42and in particular to make the case that latency matters and it's probably going to be mattering
00:00:47more in the future.
00:00:48But I just want to say, this talk is unusual for me, I've never before given a talk where
00:00:52there are fog generators in the auditorium, it's a really San Francisco experience I guess.
00:00:59So it's well known that AI workloads depend on really great networking performance in
00:01:06order to achieve their own performance and of course that's because the workloads are
00:01:09so large that they have to be distributed across machines and then you have to communicate
00:01:13between the machines.
00:01:15But what I want to talk about today is that it seems that those workloads are changing and
00:01:19so I hope to do three things over the next 15 or 20 minutes, first to convince you that
00:01:24in fact the workloads are changing and that whereas the workloads used to be completely
00:01:28dominated by large transfers where throughput is the key metric that matters, that we're seeing
00:01:35more and more smaller transfers where the latency is crucial.
00:01:39The second thing I hope to do is to convince you that legacy protocols like TCP and RDMA are
00:01:46poorly suited to this environment.
00:01:47They weren't designed for this environment and unfortunately they suffer from very high tail latency when you
00:01:54create small messages with large ones and I'll talk a little bit about why that's the case.
00:01:59Then third, I'd like to introduce HOMA which is a new protocol we've developed at Stanford that actually was designed in a clean
00:02:05slate that's redesigned to handle data center workloads like these and in fact it does quite well on those workloads and can reduce tail latency by an order of magnitude or more.
00:02:15So let's dive in first workloads.
00:02:20Historically AI workloads have consisted of enormous transfers between machines.
00:02:26That's all that really mattered.
00:02:28Gigabytes of data for things like weight gradients and so on.
00:02:32In these workloads what you really care about is throughput.
00:02:3630 gigabits per second you can pump through the pipes.
00:02:39And these are relatively easy workloads for networks because if it takes a while to set up the connection and start the transfer it doesn't matter.
00:02:48The transfers go on for so long that all that really matters is the throughput.
00:02:53And so in these environments TCP and RDMA perform pretty well.
00:02:56By the way when I say RDMA what I really mean is rocky RDMA over converged Ethernet which is the underlying transport that's used by RDMA for most purposes today.
00:03:08So anyhow the old workloads, big transfers, throughput matters, the legacy protocols work pretty well.
00:03:16However it appears that the workloads are changing.
00:03:19They're becoming more granular with smaller chunks of computation and smaller exchanges of data.
00:03:25And this seems to be particularly true in the world of inference and also in agentic workloads.
00:03:30Not so much for training workloads are still massive transfers.
00:03:34And so what's happening is that more and more there are small message exchanges.
00:03:38Typically for things like metadata and coordination.
00:03:40Such as checking to see if a particular entry is present in a KV cache that's distributed.
00:03:45Or doing barrier synchronization at the end of periods of compute.
00:03:49And for these workloads what really matters is latency.
00:03:54That is what's the round trip time to send some small piece of data across the network.
00:03:59Do a little bit of computation and get a small result back again.
00:04:03And in fact it isn't just latency or average latency that matters.
00:04:07What really matters is tail latency.
00:04:09That is you'd like to know that if we send a whole lot of small messages all of them will complete quickly.
00:04:15So for example we typically measure things like 99th percentile latency.
00:04:20And if we have high tail latency that can limit the overall throughput of the system.
00:04:24So here's an example.
00:04:26Suppose a common thing is to take a workload and split it up across several nodes.
00:04:30Which do intensive computation and using their GPUs for some period of time.
00:04:34And then once they've all finished their computation.
00:04:37You do some small exchange between the nodes.
00:04:40To exchange data and metadata.
00:04:41And then it'll go on to the next round of computation.
00:04:45And while that exchange is happening.
00:04:47That synchronization is happening.
00:04:48The GPUs are sitting idle.
00:04:51So if even one of those exchanges takes a long time.
00:04:56It turns out the whole process stalled.
00:04:58You need all of those exchanges to complete.
00:05:01Before you can go on to the next phase of computation.
00:05:04Now if the computation phase is say five seconds.
00:05:07And it takes a few milliseconds for the exchange.
00:05:09You know not a problem.
00:05:11And that's historically what it's been.
00:05:13But now with the agentic workloads.
00:05:15Where you're trying to pump out tokens.
00:05:17Relatively rapidly at a regular rate.
00:05:20The periods of computation are getting down into sort of the millisecond time scale.
00:05:24And if it also takes milliseconds to do that synchronization.
00:05:28Then you're wasting a significant fraction of your GPU's resources.
00:05:32Waiting for the synchronization to occur.
00:05:36So I'm curious.
00:05:36I'd like to just do a quick audience poll here.
00:05:39Is there anybody here where you have reason to believe.
00:05:42That the latency of small messages.
00:05:44Is impacting the overall throughput of your applications.
00:05:47If so can you just raise your hand.
00:05:49Is there anybody out there today.
00:05:51Actually more hands than I expected.
00:05:53So quite a few people out there are raising their hands.
00:05:55I think this problem is likely to get worse.
00:05:58As the trends continue.
00:06:01So what's going on.
00:06:02Why is tail latency bad.
00:06:05Well typically the cause.
00:06:06Is congestion resulting from incast.
00:06:10So incast is when several nodes all decide simultaneously to transfer data to some destination node.
00:06:18And if they all send large messages.
00:06:20Well the links are the same everywhere in the network.
00:06:23So three nodes can transfer three times as fast as one node can possibly receive.
00:06:28And so what happens is that packets accumulate at the last hop going to that destination.
00:06:34In the top of rack switch.
00:06:36At its egress port for the destination node.
00:06:40Then if some other node decides it wants to send a short message to that same destination.
00:06:44The short message gets stuck behind the long ones in the queue there.
00:06:49And actually that causes delay.
00:06:51In the worst case.
00:06:53So many packets arrive.
00:06:54That the switch runs out of buffer space.
00:06:56And it has to drop packets.
00:06:57And then there are timeouts and retransmissions that make everything even worse.
00:07:03So somehow we need some way to reduce the congestion in those queues.
00:07:09Somehow we have to get the sending nodes to stop sending so fast.
00:07:14So the queues don't just build up without limit.
00:07:17So the way this is done historically virtually all network protocols before HOMA.
00:07:23Including TCP and RDMA.
00:07:26Congestion control is the responsibility of the sender.
00:07:29So senders somehow have to figure out that congestion is happening.
00:07:32And they have to slow down their rate of transmission.
00:07:34Now you might wonder why are senders doing it.
00:07:36Because the congestion is way over at the other end of the data center network.
00:07:40How does the sender find out?
00:07:43Well in the really old days.
00:07:45The way they would find out is the queues would overflow and packets would get dropped.
00:07:48The sender would detect the packets got lost.
00:07:50Because it wouldn't get acknowledgements back.
00:07:52And it would assume that means there's congestion.
00:07:54And then slow down its rate of transfer.
00:07:57That's really expensive.
00:07:58So today there are better techniques.
00:08:00That mostly involve the switches providing information.
00:08:04So a top of rack switch when it sees that the queue length for an egress port has reached some thresholds.
00:08:10Starting to fill.
00:08:12Long before the queue overflows.
00:08:13It starts marking all of the packets that pass through.
00:08:16With what's called early congestion notification.
00:08:18ECN marking.
00:08:20And so when those packets pass through to the receiver.
00:08:23The receiver sees the marking in the packets.
00:08:26And then when it communicates back to the sender next.
00:08:29For example to send an acknowledgement.
00:08:31Then it includes that marking that goes back to the sender.
00:08:34And now the sender sees.
00:08:35The sender realizes oh there's congestion someplace.
00:08:38I've got to slow down my rate of transmission.
00:08:41So that's the basic idea.
00:08:42Unfortunately getting this right is really hard.
00:08:45Really hard.
00:08:45It's very hard for the congestion to figure out exactly how to set its rates.
00:08:49Because it gets one bit of information.
00:08:52There's congestion someplace.
00:08:54And there are multiple senders all sending to the same destination.
00:08:57They're all trying to make adjustments simultaneously.
00:09:00How much do you cut back?
00:09:01And how do I know when I can ramp up again?
00:09:04And even worse it's really hard to do this in a way that's stable.
00:09:07Because there's control lag.
00:09:09That is it takes time before the sender finds out that there's congestion.
00:09:14And in fact using this process it typically takes several round trips for the sender to
00:09:18gradually adjust its rate to get just the right rate to match the available bandwidth.
00:09:24But by the time you do that in a network things have changed.
00:09:27New transmissions have started or old ones have finished.
00:09:30And so these systems tend to never stabilize.
00:09:33They're constantly oscillating between sending too much and sending too little.
00:09:37This problem has been around for a long time.
00:09:39It's been known in the research community for more than 20 years now.
00:09:42There have been tons of papers published on it.
00:09:45There have been some improvements made.
00:09:46That's undeniable.
00:09:47But we're still a long ways from anything that works well.
00:09:50And the problem is with the fundamental nature of doing the congestion control on the sender side.
00:09:54It just doesn't work very well.
00:09:57So you end up with a lot of queue buildup.
00:09:59And in fact you can see the only way to find out that there's congestion is if there's queues.
00:10:03And so by that point we're already experiencing delays.
00:10:07So that's a problem.
00:10:09One other problem with TCP and RDMA also is that their basic data model is a byte stream.
00:10:14Just a stream of bytes with no differentiation in it.
00:10:18So if you send a series of messages say through a TCP socket they get serialized into that stream.
00:10:25And on this slide I've you know I've shown messages appear like they have different colors in the stream.
00:10:30Well there are no colors in real life.
00:10:32TCP has no idea where the message boundaries are.
00:10:35And that also makes life hard.
00:10:37For example you don't know how much more data is coming.
00:10:40If you knew how big the message was you'd know how much more is coming.
00:10:43And you can't prioritize short messages.
00:10:45Which we'd really like to do.
00:10:47Get the short messages through faster.
00:10:49And you can end up with what's called head of line blocking.
00:10:51Where somebody sends a series of messages to the same destination.
00:10:55And they send two really large ones.
00:10:57And then a small one after that they get stuck behind them in that stream.
00:11:01And so it gets delayed.
00:11:02And again you have tail latency issues.
00:11:05So all in all TCP and RDMA are just not well suited to this environment.
00:11:11So what do we do?
00:11:13Well what I'd like to do next is tell you about a new protocol called HOMA.
00:11:16That we've developed at Stanford.
00:11:18Which was based on a completely clean slate redesign for network transport.
00:11:21If you could start from scratch.
00:11:23And rethink how you do transport for data centers.
00:11:26How would you do it?
00:11:28And it turns out in HOMA virtually every major design decision is different from TCP and RDMA.
00:11:34TCP for all the amazing things it's done is just not a good match to today's data centers.
00:11:39Nor RDMA.
00:11:41So what HOMA does particularly well is to manage a combination of large and small messages.
00:11:46And to make sure that the short messages have really low latency.
00:11:51So this started off as a PhD dissertation for one of my students, Benam Monteseri.
00:11:55And then the results were so great that I decided to make it my personal project.
00:12:00To see if we could get it out of the lab and into production.
00:12:03As you may know I'm not like most professors and I love to code.
00:12:07And so I turned this into my own programming project.
00:12:09I have created a kernel module for Linux.
00:12:12I'm currently working through the process of getting that upstreamed into the kernel.
00:12:15It's available on GitHub for download.
00:12:18So let me tell you just a little bit about how HOMA works.
00:12:21I want to mention three things.
00:12:23First, it's message based, not stream based.
00:12:27In fact, the fundamental unit at HOMA is a remote procedure call.
00:12:31Which consists of two things.
00:12:33A request message sent from a client to a server.
00:12:37And then a response message returned back from the server to the client.
00:12:42So the key thing here is that HOMA knows about message lengths.
00:12:46They're buried in the transport all the way down to the bottom.
00:12:49And this has a bunch of advantages.
00:12:51First, it allows us to predict the future.
00:12:54As soon as a receiver gets the first packet of a message, it knows exactly how much more data
00:12:59the sender wants to send.
00:13:00And that's so much more information for doing congestion control.
00:13:05Second, HOMA prioritizes shorter messages.
00:13:08It uses SRPT, shortest remaining processing time first, to try and prioritize shorter messages.
00:13:15And third, because messages are all independent, they're not serialized into a stream.
00:13:22Every message is independent.
00:13:23Shorter messages can bypass long ones.
00:13:25So they don't get queued behind long messages.
00:13:29The second thing about HOMA that's different is that it controls congestion from the receiver.
00:13:35Now, when you think about it, this makes sense.
00:13:37Because the congestion happens primarily at that last downlink to the receiver.
00:13:42And so the receiver has way more information.
00:13:44In fact, with HOMA, as soon as it gets the first packet of a message,
00:13:48it knows exactly how much more is coming.
00:13:49So it has essentially complete information about congestion.
00:13:54And it can therefore respond to congestion much more quickly and much more precisely.
00:14:00The way things work with HOMA is that when a sender has a message to send,
00:14:04it breaks it up into packets, but it only transmits the first few packets.
00:14:09Those are called unscheduled packets to the receiver.
00:14:12Packets after that are called scheduled packets.
00:14:15And they only get transmitted when the receiver asks for them.
00:14:19So the receiver will send grant packets back.
00:14:22He'll paste them out and send those back to the sender over time,
00:14:25telling the sender, "It's now time for you to send me the next chunk of data."
00:14:29And the receiver can delay those grants.
00:14:32So, for example, if the receiver has 10 messages that are incoming,
00:14:36there's no point in sending grants to all 10 of them,
00:14:38because then you'll just get congestion in the top of RAP queues.
00:14:42So it can use the grants to reduce congestion.
00:14:45And then it can also use the grants to give preference to its most favorite messages,
00:14:50which would be the shorter ones.
00:14:51So it's a way of implementing SRPT by favoring short messages.
00:14:57The third aspect of HOMA is that it takes advantage of the priority queues in modern switches.
00:15:02So modern data center switches have more than one queue at each egress port, typically eight.
00:15:08And they can be used in a priority mechanism where packets get transmitted
00:15:12preferentially from the highest priority queue.
00:15:14So I've shown only two queues on the slide here, but typically there's more than that.
00:15:19You can specify in packets, using the various fields of the packet,
00:15:22you can specify which queue it should go into.
00:15:24And so HOMA dynamically makes those choices in a way to give priority to shorter messages.
00:15:31So if we go back to the NCAST example from a few slides ago,
00:15:34all of those long messages will pile up in the lowest priority queue.
00:15:38But if there's a short message coming, it will use a higher priority queue.
00:15:41And so it will immediately bypass all of the queued packets from the longer messages
00:15:48and get through to the destination more quickly.
00:15:52So how much of a difference does this make?
00:15:54Here's a - on this slide I've got one sample benchmark that I use as part of my tuning and evaluation of HOMA.
00:16:01It consists of a workload of a bunch of machines on a network that are exchanging
00:16:05messages back and forth of different sizes, ranging from very small to very large.
00:16:10And on this graph you can see on the x-axis is the message length from about 50 bytes up to a megabyte.
00:16:16The y-axis shows you the round trip time for messages of that length.
00:16:20So this request - this uses request and response messages that are the same length.
00:16:24You can see TCP in green, HOMA in blue, and the y-axis is round trip time, so lower is better.
00:16:30And for each protocol I've got two curves.
00:16:34One curve is the p50 curve, that's the median latency for messages of this length.
00:16:40And then p99 is the 99th percentile, i.e. tail latency for messages of this length.
00:16:46So I want to point out two things.
00:16:48First, the p99 for short messages is dramatically better for HOMA.
00:16:52So with TCP it's more than a millisecond, tail latency.
00:16:55HOMA is less than 100 microseconds, about 13 times faster.
00:17:00Second, interestingly, you might think that because HOMA favors shorter messages,
00:17:06that long messages suffer and get worse performance.
00:17:09It turns out that's actually not the case.
00:17:11Even on the longest messages, HOMA is almost a factor of two better than TCP.
00:17:16I don't have time to explain that today, but it has to do with the fact that HOMA uses run to
00:17:20completion approaches, which are much more effective than the fair scheduling used by TCP.
00:17:27So just to wrap up, the role of short messages in AI appears to be increasing.
00:17:33I think it's likely that it's going to continue to increase.
00:17:37We'll see over the next year or two if that happens.
00:17:39And I just want to pose a question to you.
00:17:41You know, as you're running your applications and measuring performance and seeing what the bottlenecks are,
00:17:46ask yourself, is high latency for short messages affecting your throughput?
00:17:51If the answer is yes, then just know there is a solution available.
00:17:55If you give HOMA a try, you can probably reduce your tail latency by an order of magnitude or more.
00:18:00And by the way, HOMA is basically my life mission right now.
00:18:04I'm sort of semi-retired from Stanford.
00:18:06And the reason I did that is so I can spend 100% of my time hacking on HOMA.
00:18:10So I'd be delighted to work with you and help you if you decide you want to experiment with HOMA.
00:18:14If you need help getting started, answer questions, bug fixes, whatever,
00:18:18you know, I'd be happy to work with you to try and make you successful with it.
00:18:21So if that is interesting, feel free to contact me.
00:18:23My email is on the slide or you can Google me too and find me over the internet.
00:18:28So thanks very much for listening and hope to hear from some of you.
Community Posts
No posts yet. Be the first to write about this video!
Write about this video