Switching and Forwarding

nA network switch (sometimes known as a switching hub) is a computer networking device that is used to logically connect devices together on a computer network, by using a form of packet switching to forward data to the destination device.

A network switch is a multi-port network bridge that processes and forwards frames at the data link layer (layer 2) of the OSI model. Switches can be designed to route packets in addition to performing packet switching; these switches are commonly known as layer-3 or multilayer switches.

A switch adds the star topology to the point-to-point link,bus (Ethernet), and ring (802.5 and FDDI) topologies.

• Even though a switch has a fixed number of inputs and outputs, which limits the number of hosts that can be connected to a single switch, large networks can be built by interconnecting a number of switches.
• We can connect switches to each other and to hosts using point-to-point links, which typically means that we can build networks of large geographic scope.
• Adding a new host to the network by connecting it to a switch does not necessarily mean that the hosts already connected will get worse performance from the network.

A switch is connected to a set of links and, for each of these links, runs the appropriate data link protocol to communicate with the node at the other end of the link. A switch’s primary job is to receive incoming packets on one of its links and to transmit them on some other link. This function is sometimes referred to as either switching or forwarding.

How does the switch decide which output port to place each packet on? The general answer is that it looks at the header of the packet for an identifier that it uses to make the decision.

There are two common approaches

• datagram or connectionless approach
• virtual circuit or connection-oriented approach

A third approach, source routing, is less common than these other two, but it is simple to explain and does have some useful applications. 

Datagrams

The idea behind datagrams is incredibly simple: every packet contains enough information to enable any switch to decide how to get it to its destination. To decide how to forward a packet, a switch consults a forwarding table (sometimes called a routing table)

                                        Datagram forwarding: an example network

Connectionless (datagram) networks have the following characteristics:

• A host can send a packet anywhere at any time, since any packet that turns up at a switch can be immediately forwarded.This contrasts with most connection-oriented networks, in which some “connection state” needs to be established before the first data packet is sent.

• When a host sends a packet, it has no way of knowing if the network is capable of delivering it or if the destination host is even up and running.

• Each packet is forwarded independently of previous packets that might have been sent to the same destination. Thus, two successive packets from host A to host B may follow completely different paths (perhaps because of a change in the forwarding table at some switch in the network).

• A switch or link failure might not have any serious effect on communication if it is possible to find an alternate route around the failure and to update the forwarding table accordingly.

Virtual Circuit Switching

• nWidely used technique for packet switching
• nUses the concept of virtual circuit (VC)
• nAlso called a connection-oriented model
• nFirst set up a virtual connection from the source host to the destination host and then send the data

Where host A again wants to send packets to host B.We can think of this as a two-stage process. The first stage is “connection setup.” The second is data transfer.

In the connection setup phase, it is necessary to establish “connection state” in each of the switches between the source and destination hosts. The connection state for a single connection consists of an entry in a “VC table” in each switch through which the connection passes. One entry in the VC table on a single switch contains

• a virtual circuit identifier (VCI) that uniquely identifies the connection at this switch and that will be carried inside the header of the packets that belong to this connection.
• an incoming interface on which packets for this VC arrive at the switch.
• an outgoing interface in which packets for this VC leave the switch.
• a potentially different VCI that will be used for outgoing packets.

The semantics of one such entry is as follows: If a packet arrives on the designated incoming interface and that packet contains the designated VCI value in its header, then that packet should be sent out the specified outgoing interface with the specified outgoing VCI value first having been placed in its header.

The combination of the VCI of packets as they are received at the switch and the interface on which they are received uniquely identifies the virtual connection. There may of be many virtual connections established in the switch at one time. 

The incoming and outgoing VCI values are generally not the same. The VCI is not a globally significant identifier for the connection; rather, it has significance only on a given link—that is, it has link local scope.
 

Whenever a new connection is created, we need to assign a new VCI for that connection on each link that the connection will traverse. We also need to ensure that the chosen VCI on a given link is not currently in use on that link by some existing connection.

There are two broad classes of approach to establishing connection state. One is to have a network administrator configure the state, in which case the virtual circuit is “permanent.” Of course, it can also be deleted by the administrator, so a permanent virtual circuit (PVC) might best be thought of as a long-lived or administratively configured VC. The next a host can send messages into the network to cause the state to be established. This is called as signalling, and the resulting virtual circuits are said to be switched. The salient characteristic of a switched virtual circuit (SVC) is that a host may set up and delete such a VC dynamically without the involvement of a network administrator. 

Note that an SVC should more accurately be called a “signalled” VC, since it is the use of signalling (not switching) that distinguishes an SVC from a PVC.

There are several things to note about virtual circuit switching:

• Since host A has to wait for the connection request to reach the far side of the network and return before it can send its first data packet, there is at least one RTT of delay before data is sent.
• While the connection request contains the full address for host B (which might be quite large, being a global identifier on the network), each data packet contains only a small identifier, which is only unique on one link. Thus, the per-packet overhead caused by the header is reduced relative to the datagram model.
• If a switch or a link in a connection fails, the connection is broken and a new one will need to be established. Also, the old one needs to be torn down to free up table storage space in the switches.
• The issue of how a switch decides which link to forward the connection request on has been similarities with the function of a routing algorithm.

For example, an X.25 network—a packet-switched network that uses the connection-oriented model—employs the following three-part strategy:

1. Buffers are allocated to each virtual circuit when the circuit is initialized.
2. The sliding window protocol is run between each pair of nodes along the virtual circuit, and this protocol is augmented with flow control to keep the sending node from overrunning the buffers allocated at the receiving node.
3. The circuit is rejected by a given node if not enough buffers are available at that node when the connection request message is processed.

Source Routing

A third approach to switching that uses neither virtual circuits nor conventional datagrams is known as source routing. The name derives from the fact that all the information about network topology that is required to switch a packet across the network is provided by the source host.

There are various ways to implement source routing. One would be to assign a number to each output of each switch and to place that number in the header of the packet. The switching function is then very simple: For each packet that arrives on an input, the switch would read the port number in the header and transmit the packet on that output. However, since there will in general be more than one switch in the path between the sending and the receiving host, the header for the packet needs to contain enough information to allow every switch in the path to determine which output the packet needs to be placed on.

Three ways to handle headers for source routing: (a) rotation; (b) stripping; (c) pointer. The labels are read right to left.