With the demise of ATM, many technologists believe that circuit switching is dead and packet switching has won. Yet the current Internet multicast architecture is essentially circuit switching in disguise, since every router along the path of a multicast session has to maintain explicit connection state. Which leads me to wonder… can packet switching support multicast, or is circuit switching required?
Let me suggest first that the essential difference between packet switching and circuit switching is that a packet switched network maintains no per-connection state on switching nodes (routers), which a circuit switched network does. The only state maintained by the switching nodes in a packet switched network is common to all connections. Although state (routing tables) may change on the switching nodes in response to network load or link failures, connections can be opened or closed without any changes to the switching nodes’s stored state.
Now, this implies that each packet in a packet switched network must contain all per-connection information required to deliver it. In particular, it must contain enough information to select the path it will take through the network.
For a unicast packet, if the packet will not change as it moves through the network, and there is a unique path to each unique destination, then the packet must contain enough information to specify its destination. This means, on average, log2(n) bits, where n is the number of possible destinations. So, a unicast packet capable of addressing each human being currently alive, roughly 6 billion people, requires, on average, at least log2(6*10^9) ~ 32.48 header bits, coincidently the size of an IP address. I emphasize on average. A source routed address like I described in NAT and the Failure of Source Routing would require 64 bits. A network where some destinations were directly addressed (using 32 bits) and some require a NAT source route (using 64 bits) would average out to more than 32 addressing bits per header. Source routing thus appears to be something like a Huffman code, where less frequent destinations are addressed using more bits.
Now consider a multicast packet. Again, if the packet will not change as it moves through the network, and there is a unique path to each unique destination, and if we require our multicast packet to be able to address any subset of the possible network destinations, then the header would seem to require, on average, one bit for each possible destination, or 2^n bits, where n is, again, the number of possible destinations. For a network of 6 billion destinations, this adds up to 2^(6*10^9) bits. Clearly, this is totally impractical.
Considering this analysis, perhaps it is not surprising that the current Internet multicast scheme is essentially a circuit switching network grafted on top of the Internet’s original packet switched design. Internet multicast uses class D addresses. Normally, a single class D address is used for each multicast distribution group; however, a block of class D addresses (232/8 in IPv4, FF3x::/96 in IPv6) has been assigned for Single Source Multicast (SSM), where the destination and source addresses are paired together to form the multicast group. In either case, the class D addresses carry no information about where in the network the subscribers are located. This information has to be built and maintained by the routers in the form of routing table entries for each class D address (in the case of SSM, for each destination/source address pair). In theory, a single class D address could be used for more than one connection using UDP ports numbers, but in practice this is almost never done since two connections on the same class D address would have to share the same set of destinations. Clearly, this meets my basic definition of circuit switching – explicit per-connection state maintained on routers.
Consider, on the other hand, the design of ATM or MPLS. Each packet is labeled with an identifier (a VPI/VCI pair) that is link local and interpreted on a hop-by-hop basis by the receiving router, which looks up the identifier in a table and, based on this, decides how to forward the packet, often by changing the identifier to a different value and sending it out a given interface. MPLS (in my opinion) improves this basic scheme by allowing the identifiers to be pushed on a stack (and by removing a lot of cruft). Yet the basic principle of both ATM and MPLS remains that of circuit switching – each router has to maintain a table of identifiers, and the identifiers are established on a per-session basis.
Due to the addressing considerations discussed above, it’s hard to see how a purely packet switched network can ever fully support a general multicast service. The best we can hope for is a hybrid packet/circuit switched network with packet switching used for unicast packets and circuit switching used for some (or all) multicast packets. Why that would in any way be preferable to a purely circuit switched network remains an open question.
One Reply to “Will Multicast kill Packet Switching?”
an interesting observation of a strangely now-obvious fact. Today’s internet is a virtual circuit switched network. Should we call Wikipedia?