"Fat State" vs "Lean State" Packet Switching

The principal difference between connectionless and virtual circuit-based network technologies is in the amount of information necessary for forwarding datagrams to their destinations. That information is often referred to as the "state" of switches.

A backbone gateway in a connectionless packet routing network (such as native IP network) keeps the table with one entry for every reachable sub-network. The directions to those networks can be computed by checking that destination addresses fall into ranges of addresses assigned to those networks. It is easy to see that in an ideal network that does not experience any failures or topological changes, the routing table does not need to be changed. Every change in topology of a lean state network causes a wave of routing updates changing the routing tables in all routers within the visibility scope of that change.

A technique called aggregation is often used to reduce the sizes of routing tables; aggregation lumps several networks together when the ranges of their addresses can be combined arithmetically and when the packets to them should be routed in the same direction. There is a tradeoff between the size of a routing table and the efficiency of packet routing; often, the table can be further compressed at the price of selection of suboptimal paths to some destinations. An empirical rule regarding nearly optimal routing is that the high efficiency of routing can be achieved while maintaining the table size roughly proportional to the logarithm of the size of the network. Therefore, the gateways in packet routing networks are said to have a lean state. For simplicity, we will call lean state gateways "routers".

In a virtual circuit-based network, intermediate gateways must keep tables with one entry per every virtual connection passing through the gateway, in addition to the information similar to the routing table in the packet routers (that information is necessary to make decisions regarding routing virtual circuits). The connection tables are not static in an ideal network, they must change every time a customer wants to start or cease interaction with another customer. The evolution of the routing tables of such gateways is essentially equivalent to that of routers; so the amount of information needed for forwarding datagrams in gateways of VC-oriented networks is always greater than that of topologically identical connectionless networks. Consequently, gateways in VC-oriented networks are said to have a fat state; and hereafter, we will call fat state gateways "switches".

The obvious advantage of fat state gateways is the simplicity of the forwarding process, allowing the achievement of higher speeds of single data path gateways. Other advantages include the ability to reserve bandwidth on per-connection basis, and thus guarantee some quality of service; the ability to generate information needed for end-to-end usage metering and accounting; and the ability to route virtual circuits around heavily loaded lines. We will discuss those advantages later.

The most fundamental disadvantage of fat state gateways is the necessity of making changes in connection tables for every new connection. The computational overhead for establishing connections is relatively high, particularly because in case of resource reservation the switch must look ahead to find out which paths will lead to links that have adequate resources available. The computing power of the switch's control unit is likely to be the major factor in the real-world performance. Unfortunately (or maybe particularly because of what was said above), the switch vendors seem to forget publishing the sustainable connection churn rates, preferring instead to publish dazzling numbers of bits per second.

For short connections (less than about 30-100 packets) the computations needed to route those packets independently require fewer resources than computations required for establishing and tearing down the virtual connection. The per-connection computations require general purpose data processors because their complexity makes hardware implementation infeasible. Given that an average length of TCP connections observed in the modern Internet is about 12 packets, the pure VC-based networking is simply impossible in the global Internet because control units of switches would have to perform amounts of computations in excess of what hardware fast packet forwarding engines of modern routers do.

There are several proposed technologies, such as Ipsilon's IP switching and Cisco's tag switching (when used over VC-based fabric), trying to combine the performance benefits of fat state switching for longer data connections and lean state routing for short-living connections. The fundamental problem with those approaches is that to be of any benefit they have to produce connections for a relatively large fraction of connection, at least 10% or so. This makes the scaling characteristics of those approaches equivalent to scaling characteristics of pure VC-based networking; i.e. if a pure VC-based network breaks down from overloading the switches' control units, the hybrid network will break down with traffic about 10 times higher. (Actually, the number will be much less than that, because non-trivial computational resources have to be spent on monitoring connectionless traffic to locate and VC-ize intensive "flows"). Given the growth rates of the modern Internet it only buys 1-2 years before the break-down, which is certainly not enough to pay for introduction of the complicated new technology.

The only realistic way to use switching in the Internet backbones, therefore, is to avoid using switched virtual circuits altogether by using switching backbone connecting native IP routers at its edges with a mesh of permanent virtual circuits (the so-called "flattened" backbone). Obviously, this approach is workable for routing within backbones, and is often used (usually with Frame Relay) to build private networks.

Since flattened networks do not have the advantage of pure switched virtual-circuit networks as explicit support for resource reservation, the only benefit of such technology as compared with a native IP network running over synchronously multiplexed medium (such as SONET) is the ability to map several private networks over statistically multiplexed channels (which makes it attractive for building private networks) and the availability of the increased capacity of switches as opposed to routers.

The perceived unsuitability of native IP routing to be used in synchronously multiplexed VPNs is usually attributed to security concerns and the lack of guaranteed quality of service. However, experience shows that the security of circuit-switched networks is as easily compromised as the security of packet routing networks; the perception of safety is false. The only really secure solution is end-to-end encryption, which is readily available for native IP networks, in both software and hardware.

A lack of QoS support and guaranteed bandwidth is also not an inherent feature of IP, but rather a missing feature of many existing routers. We will discuss that and other aspects of resource reservation later.

When Cisco tag switching is used in a downstream tag allocation scheme the characteristics of the network become similar to that of the pure packet-routing network -- as long as no stream demultiplexing is required. However, to contain the growth of routing tables, backbone ISPs have to aggregate routing information they announce to other service providers at exchange points. That means that tag switching is only useful to deliver data to a boundary between service providers, and that the routers at exchange points have to perform native IP routing to split aggregated streams into smaller internal streams. Given the nature of bottlenecks at the exchange points in the Internet (as discussed in a subsequent chapter), tag switching does not give any significant advantage over native IP routing.

Providing that there are no service features available with flattened networks that couldn't be produced with native IP networks, the only real advantage is higher performance of ATM switches over native-IP routers. However, this advantage comes at the price of increased complexity of dual technology (and thus lower reliability), and the additional encapsulation overhead reducing the user payload bandwidth. In other words, if a native IP router could reach a performance level comparable to or exceeding that of ATM switches, native IP networks will be superior to flattened networks in both performance and reliability.