A system for providing a message-based protocol for multiplexing messages sent via a stream-based connection protocol is provided. A multiplexing system provides high-level sockets of the message-based protocol that interact with low-level sockets of a stream-based connection protocol. The multiplexing system executes in a privilege mode. To send a message, an application uses a high-level socket to provide a request to send the message using the multiplexing system. The multiplexing system selects an available low-level socket from a group of sockets and sends the message via that socket. The message is sent as an atomic operation. If, during the sending of the message, the application requests to send another message, the multiplexing system selects another available low-level socket of the group and sends the other message via the selected low-level socket.