⬅️ Navigation  |  ← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

🔀 Tutorial 2: Multiplexing, Demultiplexing, and Socket‑Based Communication (Advanced)

Advanced university‑level treatment – COMP347 (TrustOpen University)

🎯 Learning Objectives

Upon completion of this tutorial, you should be able to:

🔍 Overview

Multiplexing and demultiplexing are the core mechanisms that allow a single host to run numerous network applications concurrently. This tutorial delves into the operating system’s internal implementation of these functions, from the protocol control block (PCB) and hash table lookups to the subtle semantics of INADDR_ANY and SO_REUSEADDR. We also explore how demultiplexing interacts with network address translation (NAT), firewalls, and modern multicore scaling techniques. By the end, you will have a deep understanding of how the transport layer dispatches packets with high efficiency and correctness.

📘 1. Kernel Demultiplexing Architecture

1.1 The Protocol Control Block (PCB)

In BSD‑derived stacks (including Linux, macOS, and FreeBSD), each transport‑layer endpoint is represented by a protocol control block (often called inpcb for IPv4). The PCB stores:

The kernel maintains separate hash tables for listening and established connections to speed up lookups. For TCP, the established table is hashed by the full 4‑tuple; the listening table is hashed by the destination port (and sometimes IP).

1.2 Demultiplexing Algorithm: Step‑by‑Step (Linux Implementation)

The Linux kernel’s tcp_v4_rcv() function performs the following steps:

  1. Validate the TCP header checksum and basic length.
  2. Look up the socket using __inet_lookup_established() – a hash table search on the full 4‑tuple. If found, deliver the segment.
  3. If not found, call __inet_lookup_listener() – search the listening sockets hashed by port. For each match, check if the socket’s bound IP is INADDR_ANY or matches the destination IP of the segment. The kernel selects the most specific match (e.g., a socket bound to the exact IP takes precedence over INADDR_ANY).
  4. If a listening socket is found, the kernel creates a new child socket (if the segment is a SYN) or delivers the segment to the listening socket’s queue (for SYN‑ACK processing).
  5. If no match, send a RST segment.

This algorithm ensures O(1) average‑time lookups, crucial for handling millions of concurrent connections.

1.3 The Socket State Machine and Demultiplexing

For TCP, the socket state influences demultiplexing. A socket in LISTEN state is never used for data delivery; it only receives SYN segments. A socket in ESTABLISHED or CLOSE_WAIT is used for data. The kernel maintains separate queues: the listen backlog for pending connections and the receive buffer for in‑order data. Demultiplexing routes segments to the appropriate queue based on the socket’s state.

📘 2. Advanced Socket Options and Their Impact

2.1 SO_REUSEADDR in Depth

The SO_REUSEADDR option allows multiple sockets to bind to the same port, but only under specific conditions:

This option is essential for servers that are restarted frequently, allowing them to rebind before the TIME_WAIT expires.

2.2 SO_REUSEPORT and Load Balancing

Introduced in Linux 3.9, SO_REUSEPORT allows multiple sockets to bind to the exact same (IP, port) tuple, including wildcard addresses. The kernel distributes incoming connections (or datagrams) among the sockets using a hash of the 4‑tuple, providing load balancing across CPU cores. This eliminates the single‑listener bottleneck and improves scalability for high‑performance servers (e.g., NGINX, HAProxy).

2.3 The IP_BIND_ADDRESS_NO_PORT Option

In Linux, this option allows an application to bind to a specific IP address without automatically reserving a port. This is useful for UDP when the application wants to later connect to a specific remote address, avoiding the need to pick a source port early.

📘 3. Demultiplexing in the Presence of NAT and Firewalls

3.1 Connection Tracking in NAT

Network Address Translation (NAT) devices maintain a connection tracking table that maps internal (private) 4‑tuples to external (public) 4‑tuples. When a packet from an internal host leaves the NAT, the source IP and port are rewritten. When a response arrives, the NAT reverses the mapping using the 4‑tuple of the response. The demultiplexing on the internal host is unaffected, but the NAT’s tracking table is essentially a demultiplexing mechanism at the router level.

3.2 Firewall Filtering and Demultiplexing

Stateful firewalls use the same 4‑tuple information to allow only responses to outbound connections. They maintain a similar state table. If a firewall receives a segment that does not match an existing connection (i.e., no 4‑tuple in its state table), it may drop the segment. This interaction with transport demultiplexing is critical for network security.

📘 4. Multicast and Broadcast Demultiplexing

UDP multicast and broadcast require special demultiplexing logic. When a multicast datagram arrives (dest IP in 224.0.0.0/4), the kernel:

This is a departure from the usual “single receiver” semantics and requires careful handling to avoid excessive copying.

📘 5. Performance Considerations and Scaling

5.1 Socket Table Scalability

With millions of concurrent connections, the established table must be efficient. Modern kernels use hashed tables with bucket sizes that grow with the number of connections. The hash function is typically based on the 4‑tuple to ensure even distribution. However, hashing collisions can degrade performance; some systems use RCU (Read‑Copy‑Update) to allow lock‑free lookups for improved scalability.

5.2 Listening Socket Performance

The listening socket uses a backlog queue (set by listen()) to hold pending connections. If the backlog is too small, SYNs may be dropped. Demultiplexing must quickly determine if the socket is listening and whether the backlog has room.

5.3 Zero‑Copy and Offloading

Modern NICs support Receive Side Scaling (RSS), which uses a hash of the 4‑tuple to direct packets to specific CPU cores, distributing the demultiplexing workload. This works in tandem with SO_REUSEPORT to achieve high throughput.

📝 Quiz

Test your deep understanding of demultiplexing internals. There are 25 questions covering all aspects. Answers are hidden below.

  1. What is the primary purpose of the protocol control block (PCB) in the kernel?
    AnswerThe PCB stores the 4‑tuple, socket state, and protocol‑specific data for each transport endpoint, enabling the kernel to route incoming segments to the correct socket.
  2. Which hash table is searched first when a TCP segment arrives?
    AnswerThe established table, which is hashed by the full 4‑tuple, is searched first to deliver data to an existing connection.
  3. How does the kernel handle a SYN segment when no established connection matches, but a listening socket exists?
    AnswerIt performs the three‑way handshake and creates a new child socket associated with the 4‑tuple of the incoming connection.
  4. What is the difference between SO_REUSEADDR and SO_REUSEPORT?
    Answer>SO_REUSEADDR allows multiple sockets to bind to the same port under certain conditions (e.g., TIME_WAIT, different IPs). SO_REUSEPORT allows multiple sockets to bind to the exact same (IP, port) and distributes incoming connections among them for load balancing.
  5. Why is UDP demultiplexing considered “simpler” than TCP demultiplexing?
    Answer>UDP is connectionless; the kernel only needs to match the destination port (and IP) to find a socket, without maintaining per‑connection state tables.
  6. What happens if a UDP datagram arrives with a destination port that has no bound socket?
    Answer>The kernel discards the datagram and typically sends an ICMP “Port Unreachable” message back to the sender.
  7. How does a connected UDP socket change demultiplexing?
    Answer>The socket becomes associated with a specific remote 4‑tuple; the kernel will only deliver datagrams from that remote address and port to the socket.
  8. What is the wildcard address INADDR_ANY and how does it affect demultiplexing?
    Answer>It matches any local IP address. A socket bound to INADDR_ANY will receive traffic destined to any of the host’s IP addresses, as long as the port matches.
  9. Describe the role of the listening socket’s backlog queue.
    Answer>It holds pending connection requests (SYNs) that have been partially completed but not yet accepted by the application. If the queue is full, new SYNs may be dropped.
  10. Why does the kernel use a hash table for the established connection table instead of a linear search?
    Answer>To achieve O(1) average‑time lookups, which is critical for handling millions of concurrent connections with low latency.
  11. What is the effect of SO_REUSEADDR on a socket in TIME_WAIT state?
    Answer>It allows a new socket to bind to the same 4‑tuple before the TIME_WAIT period expires, enabling rapid server restart.
  12. How does SO_REUSEPORT help with multicore scaling?
    Answer>It allows multiple sockets to bind to the same port, and the kernel distributes incoming connections across them using a hash of the 4‑tuple, spreading the load across CPU cores.
  13. What is the typical lookup order for a TCP segment in the Linux kernel?
    Answer>First, search the established table using the full 4‑tuple. If not found, search the listening table using the destination port and IP (with wildcard matching).
  14. How does a NAT device use the 4‑tuple to map responses to internal hosts?
    Answer>It maintains a connection tracking table that maps internal (srcIP, srcPort) to external (publicIP, publicPort). When a response arrives, it looks up the external tuple and translates it back to the internal tuple.
  15. What is the purpose of the IP_BIND_ADDRESS_NO_PORT option?
    Answer>It allows a UDP socket to bind to a specific IP address without automatically allocating a port, so that a port can be chosen later (e.g., when connecting).
  16. How does multicast demultiplexing differ from unicast demultiplexing?
    Answer>For multicast, the kernel delivers a copy of the datagram to every socket that has joined the multicast group and is bound to the destination port, rather than to a single socket.
  17. What is the significance of the IP_ADD_MEMBERSHIP socket option?
    Answer>It allows a socket to join a multicast group, which then enables it to receive multicast datagrams sent to that group address.
  18. Why might a server using SO_REUSEADDR still experience port conflicts?
    Answer>If two sockets both bind to INADDR_ANY and the same port, the kernel will only deliver to the first socket; the second may not receive any traffic. Also, the option does not override all restrictions (e.g., two sockets bound to the same exact 4‑tuple may not work unless SO_REUSEPORT is used).
  19. How does Receive Side Scaling (RSS) improve demultiplexing performance?
    Answer>RSS uses a hash of the 4‑tuple to direct packets to specific CPU cores, distributing the processing load and reducing contention on kernel data structures.
  20. What is the role of the skb (socket buffer) structure in demultiplexing?
    Answer>The skb holds the network packet data; during demultiplexing, the kernel parses the headers, extracts the 4‑tuple, and then delivers the skb to the appropriate socket’s receive queue.
  21. Describe the difference between a “listening” socket and an “established” socket in TCP.
    Answer>A listening socket is used to accept new connections; it does not carry data. An established socket is a fully open connection that can exchange data with a remote endpoint.
  22. How does the kernel handle a TCP segment that does not match any listening socket and has no established socket?
    Answer>It sends a RST (reset) segment to the sender to indicate that the port is unreachable.
  23. What is the purpose of the SO_REUSEADDR option in the context of multicast?
    Answer>It allows multiple sockets to bind to the same multicast group and port, enabling multiple applications to receive the same multicast stream.
  24. Why do firewalls maintain a state table similar to the kernel’s established connection table?
    Answer>To filter packets based on whether they belong to an established connection, preventing unsolicited inbound traffic.
  25. What is the impact of a large listening backlog on demultiplexing?
    Answer>It allows more pending connections to be queued, reducing the chance of SYN drops during high connection rates, but consumes more memory.

🛠️ Exercises

These exercises involve analysis, design, and troubleshooting of demultiplexing scenarios. There are 15 exercises with detailed solutions.

  1. Exercise 1: Wildcard Binding Priority
    Host has two UDP sockets: Socket A bound to 192.168.1.10:8080, Socket B bound to 0.0.0.0:8080. A datagram arrives destined for 192.168.1.10:8080. Which socket receives it? Explain.
    SolutionSocket A receives it because the kernel prefers the most specific binding (exact IP) over a wildcard when both match the destination port.
  2. Exercise 2: TCP Demultiplexing with Multiple Clients
    A server listens on port 443 with IP 203.0.113.5. Two clients connect: Client1 (10.0.0.1:52000) and Client2 (10.0.0.1:52001) — same source IP, different source ports. How does the server distinguish the two connections?
    SolutionThe connections are distinguished by their full 4‑tuples: (10.0.0.1, 52000, 203.0.113.5, 443) and (10.0.0.1, 52001, 203.0.113.5, 443). The source port differs, creating unique tuples.
  3. Exercise 3: Connected UDP Filtering
    A UDP socket on host 192.168.1.5:9999 is connected to (10.0.0.2, 53). A datagram arrives from (10.0.0.3, 53) destined to 192.168.1.5:9999. Will it be delivered? Why?
    SolutionNo. The connected socket filters datagrams based on the remote address it was connected to. Since the source IP does not match, the kernel will not deliver it to that socket.
  4. Exercise 4: Listening Socket Demultiplexing
    A server has a listening socket on 0.0.0.0:80 and another on 192.168.1.10:80. A SYN segment arrives destined for 192.168.1.10:80. Which listening socket gets the connection? Why?
    SolutionThe socket bound to 192.168.1.10:80 gets it, because it is a more specific match than the wildcard socket. The kernel selects the most specific listening socket.
  5. Exercise 5: Port Conflict with SO_REUSEADDR
    Two processes attempt to bind to 0.0.0.0:8080 with SO_REUSEADDR set. The first succeeds. What happens to the second bind? Will the second socket receive any traffic?
    SolutionThe second bind will succeed because SO_REUSEADDR allows multiple wildcard binds to the same port. However, the kernel will deliver incoming traffic only to the first socket; the second will not receive any data because the first wildcard socket matches all traffic.
  6. Exercise 6: NAT and Demultiplexing
    A NAT router has an internal host 192.168.1.100 sending a TCP SYN to 8.8.8.8:80 with source port 12345. The NAT assigns external port 55000. Describe the mapping and how the NAT handles the returning SYN‑ACK.
    SolutionThe NAT creates a mapping: (192.168.1.100, 12345) ↔ (publicIP, 55000). When the SYN‑ACK arrives destined to publicIP:55000, the NAT looks up the mapping, changes the destination to 192.168.1.100:12345, and forwards the packet.
  7. Exercise 7: Hash Table Collision Impact
    Explain how a high rate of connections with similar 4‑tuples (e.g., same source IP but varying ports) could affect hash table performance and how the kernel mitigates this.
    SolutionIf the hash function produces collisions for many tuples, lookup time increases. Kernels use robust hash functions (e.g., Jenkins) and resize the table dynamically. Also, RCU can reduce lock contention.
  8. Exercise 8: SO_REUSEPORT Load Balancing
    A server uses SO_REUSEPORT with 4 sockets bound to the same port. Incoming connections are hashed by the 4‑tuple. Why does this provide load balancing? What happens if one socket is slow?
    SolutionThe hash distributes connections evenly across sockets. If one socket is slow, its queue may fill, but the kernel still sends new connections to it based on the hash, potentially causing imbalance. Some implementations use a consistent‑hash or accept a reject mechanism.
  9. Exercise 9: Broadcast Demultiplexing
    A host has two UDP sockets bound to port 7777. One is bound to 0.0.0.0:7777, the other to 192.168.1.10:7777. A broadcast packet (dest 255.255.255.255:7777) arrives. Which sockets receive it?
    SolutionBoth sockets receive the broadcast packet, because broadcast is delivered to all sockets bound to that port, regardless of IP binding (including wildcard).
  10. Exercise 10: TIME_WAIT and Port Reuse
    A server closes a connection and enters TIME_WAIT. Can a new connection with the same 4‑tuple be established immediately? What role does SO_REUSEADDR play?
    SolutionWithout SO_REUSEADDR, the new connection will fail because the 4‑tuple is still in use. With SO_REUSEADDR on the new socket, it can bind to the same tuple before TIME_WAIT expires, but the kernel may still protect against old segments.
  11. Exercise 11: Firewall State Table vs. Kernel Demux
    How does a stateful firewall’s connection table differ from the kernel’s established socket table? What are the security implications?
    SolutionThe firewall table tracks all connections passing through, regardless of whether they terminate at the firewall itself. It may have stricter timeout policies. Security: it allows only responses to outbound connections, blocking unsolicited inbound traffic.
  12. Exercise 12: Listening Backlog Overflow
    A server sets a backlog of 5 and receives 10 SYN requests simultaneously. How many connections will be fully established? What happens to the excess?
    SolutionOnly 5 connections will be queued (backlog). The kernel may keep the SYN‑ACK state for the others, but if the queue is full, it may drop the SYN or send a RST. The actual behaviour depends on the OS.
  13. Exercise 13: UDP Demultiplexing with Multiple Interfaces
    A host has two IP addresses: 10.0.0.1 and 192.168.1.1. A UDP socket is bound to 10.0.0.1:1234. A datagram arrives destined to 192.168.1.1:1234. Will it be delivered?
    SolutionNo, because the socket is bound to a specific IP (10.0.0.1) and the destination IP does not match. The datagram will be discarded or sent to another socket if one is bound to that IP/port.
  14. Exercise 14: Analyze netstat Output
    Given the following netstat output:
    tcp 0 0 0.0.0.0:3306 0.0.0.0:* LISTEN
    tcp 0 0 192.168.1.10:3306 10.0.0.5:54321 ESTABLISHED
    Explain why the listening socket shows 0.0.0.0:3306 and how a new connection from 10.0.0.6 will be handled.
    SolutionThe listening socket is bound to all interfaces (wildcard). When a new SYN from 10.0.0.6 arrives, the kernel will create a new child socket with that client's 4‑tuple, leaving the listening socket unaffected for future connections.
  15. Exercise 15: Multicast Group Membership
    Two applications on the same host join the same multicast group (224.0.0.1:5000) using different sockets. A multicast datagram is sent to that group. How is it demultiplexed?
    SolutionThe kernel delivers a copy of the datagram to each socket that has joined the multicast group and is bound to port 5000. Both applications receive the same data.

📚 Homework

These advanced homework problems require research, synthesis, and deeper analysis. There are 15 problems with sample answers provided.

  1. Problem 1: Kernel Data Structures
    Research the struct inet_sock and struct tcp_sock in the Linux kernel. How does the kernel map a 4‑tuple to a socket efficiently? Describe the fields used for demultiplexing.
  2. Problem 2: Demultiplexing with IPv6
    How does demultiplexing differ for IPv6? Discuss the use of flow labels and how they might affect the lookup process.
  3. Problem 3: Connection Table Scalability
    Derive the time complexity of a hash table lookup with chaining. What is the worst‑case complexity? How do modern kernels avoid worst‑case scenarios?
  4. Problem 4: SO_REUSEADDR and Security
    Explain how SO_REUSEADDR could be exploited by a malicious process to intercept traffic. What measures does the kernel take to prevent this?
  5. Problem 5: High‑Performance Server Design
    Design a TCP server that can handle 1 million concurrent connections. Discuss the use of SO_REUSEPORT, RSS, memory management, and the demultiplexing strategy.
  6. Problem 6: NAT and ALG (Application Level Gateway)
    For protocols like FTP that use multiple ports, how does a NAT with an ALG handle demultiplexing? Describe the challenges.
  7. Problem 7: Demultiplexing with SCTP
    SCTP uses multi‑homing and multiple streams. How does its demultiplexing differ from TCP? Research the SCTP association identifier.
  8. Problem 8: Firewall Connection Tracking Timeouts
    Discuss the trade‑offs of different timeout values for connection tracking in firewalls. How does this affect demultiplexing of long‑lived connections?
  9. Problem 9: Zero‑Copy Demultiplexing
    Explain how zero‑copy receive operations can improve demultiplexing performance. What kernel mechanisms are involved?
  10. Problem 10: Demultiplexing in Virtualized Environments
    In a virtual machine with multiple virtual NICs, how does the hypervisor assist demultiplexing? Discuss the use of SR‑IOV and VirtIO.
  11. Problem 11: Port Exhaustion Mitigation
    Propose strategies to mitigate ephemeral port exhaustion on a busy client machine. Consider IP aliasing, multiple sockets, and application‑level connection pooling.
  12. Problem 12: Demultiplexing with IP Fragmentation
    How does IP fragmentation affect transport layer demultiplexing? When is the 4‑tuple available? Discuss the reassembly process.
  13. Problem 13: Analyzing a Packet Dump
    Given a tcpdump of a TCP connection, identify the 4‑tuple for each segment and explain how the kernel uses it for demultiplexing. Provide a step‑by‑step walkthrough.
  14. Problem 14: Non‑standard Demultiplexing in Middleboxes
    Some middleboxes (e.g., load balancers) use a different demultiplexing key (e.g., HTTP host header). How does this differ from transport layer demultiplexing? Discuss the implications.
  15. Problem 15: Future Trends in Demultiplexing
    With the rise of QUIC and HTTP/3, how does demultiplexing change? QUIC runs over UDP and uses connection IDs. Compare this to TCP's 4‑tuple demultiplexing.
Homework Sample Answers
  1. Sample Answer: The inet_sock contains the local and remote addresses and ports; tcp_sock extends it with TCP state. The kernel uses a hash table keyed by the 4‑tuple; lookup is O(1) on average.
  2. Sample Answer: IPv6 uses a larger address space. Flow labels can be used to identify flows, potentially simplifying demultiplexing. The lookup still uses the 4‑tuple (now with 128‑bit addresses).
  3. Sample Answer: Average O(1), worst‑case O(n) if all keys hash to the same bucket. Kernels use good hash functions and dynamic resizing to avoid worst‑case.
  4. Sample Answer: A malicious process could bind to a port in TIME_WAIT and receive old segments. The kernel mitigates this by verifying sequence numbers and using a timestamp option.
  5. Sample Answer: Use SO_REUSEPORT to bind multiple sockets, each tied to a CPU core. Enable RSS to direct packets to the correct core. Use non‑blocking I/O and event multiplexing. Manage memory with jumbo frames and large buffers.
  6. Sample Answer: FTP uses separate control and data ports. A NAT with ALG inspects the control channel to dynamically open ports for data, translating addresses accordingly.
  7. Sample Answer: SCTP uses an association identifier that is independent of the IP/port tuple, allowing multi‑homing. Demultiplexing uses the verification tag and association ID.
  8. Sample Answer: Short timeouts free resources quickly but may drop long idle connections. Long timeouts improve user experience but consume memory. Adjust based on application.
  9. Sample Answer: Zero‑copy receive uses DMA to place packet data directly into application memory, avoiding copies. The kernel must still parse headers to demultiplex.
  10. Sample Answer: SR‑IOV allows VMs to directly access NIC hardware, bypassing the hypervisor for demultiplexing, reducing latency. VirtIO uses shared memory between guest and host.
  11. Sample Answer: Use multiple IP addresses (aliases) to increase the available ephemeral port range. Implement connection pooling to reuse connections. Use longer timeouts to reduce churn.
  12. Sample Answer: For UDP, the 4‑tuple is available in the first fragment; subsequent fragments lack port info. The kernel reassembles before demultiplexing. For TCP, fragmentation is less common due to MSS.
  13. Sample Answer: In a tcpdump, each packet shows source/dest IP and ports. The kernel uses the 4‑tuple to locate the socket in the established table. Provide a sequence.
  14. Sample Answer: Load balancers may use application‑layer info (e.g., host header) to decide which server to forward to, which is a higher‑level demultiplexing.
  15. Sample Answer: QUIC uses connection IDs that survive IP/port changes, enabling connection migration. Demultiplexing is based on the connection ID, not the 4‑tuple, which is a fundamental shift.

📌 Summary

In the next tutorial, we will examine the User Datagram Protocol (UDP) in exhaustive detail, including its header, checksum calculation, and real‑world applications.

⬅️ Navigation  |  ← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

COMP347 – Computer Networks (Rev. 10) · TrustOpen University · Based on Kurose & Ross, Computer Networking: A Top‑Down Approach, 9th ed. (2025).