next up previous contents
Next: Virtual circuit packet switching Up: Introduction Previous: Introduction   Contents

Subsections


Switching technology

In the next three subsections, we present the three switching techniques used in networks: circuit switching, datagram packet switching and virtual circuit packet switching.


Circuit switching

Figure 1.1: Circuit switching. The two different bitstreams flow on two separate circuits.
\includegraphics[width=\textwidth]{figures/circuit_switching}

Circuit switching is the transmission technology that has been used since the first communication networks in the nineteenth century. In circuit switching, a caller must first establish a connection to a callee before any communication is possible. During the connection establishment, resources are allocated between the caller and the callee. Generally, resources are frequency intervals in a Frequency Division Multiplexing (FDM) scheme or more recently time slots in a Time Division Multiplexing (TDM) scheme. The set of resources allocated for a connection is called a circuit, as depicted in Figure 1.1. A path is a sequence of links located between nodes called switches. The path taken by data between its source and destination is determined by the circuit on which it is flowing, and does not change during the lifetime of the connection. The circuit is terminated when the connection is closed.

In circuit switching, resources remain allocated during the full length of a communication, after a circuit is established and until the circuit is terminated and the allocated resources are freed. Resources remain allocated even if no data is flowing on a circuit, hereby wasting link capacity when a circuit does not carry as much traffic as the allocation permits. This is a major issue since frequencies (in FDM) or time slots (in TDM) are available in finite quantity on each link, and establishing a circuit consumes one of these frequencies or slots on each link of the circuit. As a result, establishing circuits for communications that carry less traffic than allocation permits can lead to resource exhaustion and network saturation, preventing further connections from being established. If no circuit can be established between a sender and a receiver because of a lack of resources, the connection is blocked.

A second characteristic of circuit switching is the time cost involved when establishing a connection. In a communication network, circuit-switched or not, nodes need to lookup in a forwarding table to determine on which link to send incoming data, and to actually send data from the input link to the output link. Performing a lookup in a forwarding table and sending the data on an incoming link is called forwarding. Building the forwarding tables is called routing. In circuit switching, routing must be performed for each communication, at circuit establishment time. During circuit establishment, the set of switches and links on the path between the sender and the receiver is determined and messages are exchanged on all the links between the two end hosts of the communication in order to make the resource allocation and build the routing tables. In circuit switching, forwarding tables are hardwired or implemented using fast hardware, making data forwarding at each switch almost instantaneous. Therefore, circuit switching is well suited for long-lasting connections where the initial circuit establishment time cost is balanced by the low forwarding time cost.

The circuit identifier (a range of frequencies in FDM or a time slot position in a TDM frame) is changed by each switch at forwarding time so that switches do not need to have a complete knowledge of all circuits established in the network but rather only local knowledge of available identifiers at a link. Using local identifiers instead of global identifiers for circuits also enables networks to handle a larger number of circuits.

Traffic engineering (TE) consists in optimizing resource utilization in a network by choosing appropriate paths followed by flows of data, according to static or dynamic constraints [39]. A main goal of traffic engineering is to balance the load in the network, i.e., to avoid congestion on links on a network while other links are under-utilized. To achieve such goals, traffic engineering methods can vary from offline capacity planning algorithms to automatic, dynamic changes. Since circuit switching allocates a fixed path for each flow, circuits can be established according to traffic engineering algorithms.

On the other hand, circuit switching networks are not reactive when a network topology change occurs. For instance, on a link failure, all circuits on a failed link are cut and communication is interrupted. Special mechanisms that handle such topological changes have been be devised. Traffic engineering can alleviate the consequences of a link failure by pre-planning failure recovery. A backup circuit can be established at the same time or after the primary circuit used for a communication is set up, and traffic can be rerouted from the failed circuit to the backup circuit if a link of the primary circuit fails. Circuit switching networks are intrinsically sensitive to link failures and rerouting must be performed by additional traffic engineering mechanisms.


Datagram packet switching

Conceived in the 1960's, packet switching is a more recent technology than circuit switching which addresses a disadvantage of circuit switching: the need to allocate resources for a circuit, thus incurring link capacity wastes when no data flows on a circuit. Packet switching introduces the idea of cutting data on a flow into packets which are transmitted over a network without any resource being allocated. If no data is available at the sender at some point during a communication, then no packet is transmitted over the network and no resources are wasted. Packet switching is the generic name for a set of two different techniques: datagram packet switching and virtual circuit packet switching. Here, we give an overview of datagram packet switching.
Figure 1.2: Datagram Packet Switching. Packets from a given flow are independent and a router can forward two packets from the same flow on two different links.
\includegraphics[width=\textwidth]{figures/packet_switching}
Different from circuit switching, datagram packet switching does not require to establish circuits prior to transmission of data and terminate circuits after the transmission of data. The switches, called routers, have to make a lookup in the forwarding table, called routing table, for each incoming packet. A routing table contains a mapping between the possible final destinations of packets and the outgoing link on their path to the destination. Routing tables can be very large because they are indexed by possible destinations, making lookups and routing decisions computationally expensive, and the full forwarding process relatively slow compared to circuit switching. In datagram packet switching networks, each packet must carry the address of the destination host and use the destination address to make a forwarding decision. Consequently, routers do not need to modify the destination addresses of packets when forwarding packets.

Since each packet is processed individually by a router, all packets sent by a host to another host are not guaranteed to use the same physical links. If the routing algorithm decides to change the routing tables of the network between the instants two packets are sent, then these packets will take different paths and can even arrive out of order. In Figure 1.2 for instance, packets use two different paths to go from User 1 to User 5. Second, on a network topology change such as a link failure, the routing protocol will automatically recompute routing tables so as to take the new topology into account and avoid the failed link. As opposed to circuit switching, no additional traffic engineering algorithm is required to reroute traffic.

Since routers make routing decisions locally for each packet, independently of the flow to which a packet belongs. Therefore, traffic engineering techniques, which heavily rely on controlling the route of traffic, are more difficult to implement with datagram packet switching than with circuit switching.


Virtual circuit packet switching

Figure 1.3: Virtual circuit packet switching. All packets from the same flow use the same virtual circuit.
\includegraphics[width=\textwidth]{figures/vc_switching}

Virtual circuit packet switching (VC-switching) is a packet switching technique which merges datagram packet switching and circuit switching to extract both of their advantages. VC-switching is a variation of datagram packet switching where packets flow on so-called logical circuits for which no physical resources like frequencies or time slots are allocated (see Figure 1.3). Each packet carries a circuit identifier which is local to a link and updated by each switch on the path of the packet from its source to its destination. A virtual circuit is defined by the sequence of the mappings between a link taken by packets and the circuit identifier packets carry on this link. This sequence is set up at connection establishment time and identifiers are reclaimed during the circuit termination.

We have seen the trade-off between connection establishment and forwarding time costs that exists in circuit switching and datagram packet switching. In VC-switching, routing is performed at circuit establishment time to keep packet forwarding fast. Other advantages of VC-switching include the traffic engineering capability of circuit switching, and the resources usage efficiency of datagram packet switching. Nevertheless, a main issue of VC-Switched networks is the behavior on a topology change. As opposed to Datagram Packet Switched networks which automatically recompute routing tables on a topology change like a link failure, in VC-switching all virtual circuits that pass through a failed link are interrupted. Hence, rerouting in VC-switching relies on traffic engineering techniques.

In practice, major implementations of VC-switching are X.25 [70], Asynchronous Transfer Mode (ATM [6]) and Multiprotocol Label Switching (MPLS [50]). The Internet, today's most used computer network, is entirely built around the Internet Protocol (IP), which is responsible for routing packets from one host to another. Because of the central role of IP in the Internet, we now discuss how ATM and MPLS interact with IP.


next up previous contents
Next: Virtual circuit packet switching Up: Introduction Previous: Introduction   Contents
Yvan Pointurier 2002-08-11