In the simplest terms, a switch is a mechanism that allows us tointerconnect links to form a larger network. A switch is a multi-input,multi-output device that transfers packets from an input to one or moreoutputs. Thus, a switch adds the star topology (seeFigure 56) to the set of possible networkstructures. A star topology has several attractive properties:
Even though a switch has a fixed number of inputs and outputs, whichlimits 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 usingpoint-to-point links, which typically means that we can buildnetworks of large geographic scope.
Adding a new host to the network by connecting it to a switch doesnot necessarily reduce the performance of the network for other hostsalready connected.
This last claim cannot be made for the shared-media networks discussedin the last chapter. For example, it is impossible for two hosts on thesame 10-Mbps Ethernet segment to transmit continuously at 10Mbpsbecause they share the same transmission medium. Every host on aswitched network has its own link to the switch, so it may be entirelypossible for many hosts to transmit at the full link speed (bandwidth),provided that the switch is designed with enough aggregate capacity.Providing high aggregate throughput is one of the design goals for aswitch; we return to this topic later. In general, switched networks areconsidered more scalable (i.e., more capable of growing to largenumbers of nodes) than shared-media networks because of this ability tosupport many hosts at full speed.
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 atthe other end of the link. A switch’s primary job is to receive incomingpackets on one of its links and to transmit them on some other link.This function is sometimes referred to as either switching orforwarding, and in terms of the Open Systems Interconnection (OSI)architecture, it is considered a function of the network layer. (This is acase where OSI layering isn’t a perfect reflection of the real world,as we’ll see later.)
The question, then, is how does the switch decide which output link toplace each packet on? The general answer is that it looks at the headerof the packet for an identifier that it uses to make the decision. Thedetails of how it uses this identifier vary, but there are two commonapproaches. The first is the datagram or connectionless approach.The second is the virtual circuit or connection-oriented approach. Athird approach, source routing, is less common than these other two,but it does have some useful applications.
One thing that is common to all networks is that we need to have a wayto identify the end nodes. Such identifiers are usually calledaddresses. We have already seen examples of addresses, such as the48-bit address used for Ethernet. The only requirement for Ethernetaddresses is that no two nodes on a network have the same address. Thisis accomplished by making sure that all Ethernet cards are assigned aglobally unique identifier. For the following discussion, we assumethat each host has a globally unique address. Later on, we considerother useful properties that an address might have, but globaluniqueness is adequate to get us started.
Another assumption that we need to make is that there is some way toidentify the input and output ports of each switch. There are at leasttwo sensible ways to identify ports: One is to number each port, and theother is to identify the port by the name of the node (switch or host)to which it leads. For now, we use numbering of the ports.
3.1.1 Datagrams
The idea behind datagrams is incredibly simple: You just include inevery packet enough information to enable any switch to decide how toget it to its destination. That is, every packet contains the completedestination address. Consider the example network illustrated inFigure 57, in which the hosts have addresses A,B, C, and so on. To decide how to forward a packet, a switch consultsa forwarding table (sometimes called a routing table), an exampleof which is depicted in Table 5. Thisparticular table shows the forwarding information that switch2 needsto forward datagrams in the example network. It is pretty easy tofigure out such a table when you have a complete map of a simplenetwork like that depicted here; we could imagine a network operatorconfiguring the tables statically. It is a lot harder to create theforwarding tables in large, complex networks with dynamically changingtopologies and multiple paths between destinations. That harderproblem is known as routing and is the topic of a later section. Wecan think of routing as a process that takes place in the backgroundso that, when a data packet turns up, we will have the rightinformation in the forwarding table to be able to forward, or switch,the packet.
Destination | Port |
|---|---|
A | 3 |
B | |
C | 3 |
D | 3 |
E | 2 |
F | 1 |
G | |
H |
Datagram networks have the following characteristics:
A host can send a packet anywhere at any time, since any packet thatturns up at a switch can be immediately forwarded (assuming acorrectly populated forwarding table). For this reason, datagramnetworks are often called connectionless; this contrasts with theconnection-oriented networks described below, in which someconnection state needs to be established before the first datapacket is sent.
When a host sends a packet, it has no way of knowing if the networkis capable of delivering it or if the destination host is even up andrunning.
Each packet is forwarded independently of previous packets that mighthave been sent to the same destination. Thus, two successive packetsfrom hostA to hostB may follow completely different paths (perhapsbecause of a change in the forwarding table at some switch in thenetwork).
A switch or link failure might not have any serious effect oncommunication if it is possible to find an alternate route around thefailure and to update the forwarding table accordingly.
This last fact is particularly important to the history of datagramnetworks. One of the important design goals of the Internet isrobustness to failures, and history has shown it to be quite effectiveat meeting this goal. Since datagram-based networks are the dominanttechnology discussed in this book, we postpone illustrative examplesfor the following sections, and move on to the two main alternatives.
3.1.2 Virtual Circuit Switching
A second technique for packet switching uses the concept of a virtualcircuit (VC). This approach, which is also referred to as aconnection-oriented model, requires setting up a virtual connectionfrom the source host to the destination host before any data issent. To understand how this works, consider Figure 58, where hostA again wants to send packets tohostB. We can think of this as a two-stage process. The first stageis “connection setup.” The second is data transfer. We consider eachin turn.
In the connection setup phase, it is necessary to establish a“connection state” in each of the switches between the source anddestination hosts. The connection state for a single connection consistsof an entry in a “VC table” in each switch through which the connectionpasses. One entry in the VC table on a single switch contains:
A virtual circuit identifier (VCI) that uniquely identifies theconnection at this switch and which will be carried inside the headerof the packets that belong to this connection
An incoming interface on which packets for this VC arrive at theswitch
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 onthe designated incoming interface and that packet contains thedesignated VCI value in its header, then that packet should be sent outthe specified outgoing interface with the specified outgoing VCI valuehaving been first placed in its header.
Note that the combination of the VCI of packets as they are received atthe switch and the interface on which they are received uniquelyidentifies the virtual connection. There may of course be many virtualconnections established in the switch at one time. Also, we observe thatthe incoming and outgoing VCI values are generally not the same. Thus,the VCI is not a globally significant identifier for the connection;rather, it has significance only on a given link (i.e., it haslink-local scope).
Whenever a new connection is created, we need to assign a new VCI forthat connection on each link that the connection will traverse. We alsoneed to ensure that the chosen VCI on a given link is not currently inuse on that link by some existing connection.
There are two broad approaches to establishing connection state. One isto have a network administrator configure the state, in which case thevirtual circuit is “permanent.” Of course, it can also be deleted by theadministrator, so a permanent virtual circuit (PVC) might best bethought of as a long-lived or administratively configured VC.Alternatively, a host can send messages into the network to cause thestate to be established. This is referred to as signalling, and theresulting virtual circuits are said to be switched. The salientcharacteristic of a switched virtual circuit (SVC) is that a host mayset up and delete such a VC dynamically without the involvement of anetwork administrator. Note that an SVC should more accurately be calleda signalled VC, since it is the use of signalling (not switching) thatdistinguishes an SVC from aPVC.
Let’s assume that a network administrator wants to manually create anew virtual connection from hostA to hostB. First, the administratorneeds to identify a path through the network from A to B. In theexample network of Figure 58, there is onlyone such path, but in general, this may not be the case. Theadministrator then picks a VCI value that is currently unused on eachlink for the connection. For the purposes of our example, let’ssuppose that the VCI value 5 is chosen for the link from hostA toswitch1, and that 11 is chosen for the link from switch1 toswitch2. In that case, switch1 needs to have an entry in its VCtable configured as shown in Table 6.
Incoming Interface | Incoming VCI | Outgoing Interface | Outgoing VCI |
|---|---|---|---|
2 | 5 | 1 | 11 |
Similarly, suppose that the VCI of 7 is chosen to identify thisconnection on the link from switch2 to switch3 and that a VCI of 4 ischosen for the link from switch3 to hostB. In that case, switches 2and 3 need to be configured with VC table entries as shown inTable 7 and Table 8,respectively. Note that the “outgoing” VCI value at one switch is the“incoming” VCI value at the next switch.
Incoming Interface | Incoming VCI | Outgoing Interface | Outgoing VCI |
|---|---|---|---|
3 | 11 | 2 | 7 |
Incoming Interface | Incoming VCI | Outgoing Interface | Outgoing VCI |
|---|---|---|---|
7 | 1 | 4 |
Once the VC tables have been set up, the data transfer phase canproceed, as illustrated in Figure 59. For anypacket that it wants to send to hostB, A puts the VCI value of 5 inthe header of the packet and sends it to switch1. Switch1 receivesany such packet on interface2, and it uses the combination of theinterface and the VCI in the packet header to find the appropriate VCtable entry. As shown in Table 6, the tableentry in this case tells switch1 to forward the packet out ofinterface 1 and to put the VCI value 11 in the header when the packetis sent. Thus, the packet will arrive at switch2 on interface 3bearing VCI 11. Switch2 looks up interface 3 and VCI 11 in its VCtable (as shown in Table 7) and sends thepacket on to switch 3 after updating the VCI value in the packetheader appropriately, as shown in Figure 60. This process continues until it arrives at hostB withthe VCI value of 4 in the packet. To hostB, this identifies thepacket as having come from hostA.
In real networks of reasonable size, the burden of configuring VC tablescorrectly in a large number of switches would quickly become excessiveusing the above procedures. Thus, either a network management tool orsome sort of signalling (or both) is almost always used, even whensetting up “permanent” VCs. In the case of PVCs, signalling is initiatedby the network administrator, while SVCs are usually set up usingsignalling by one of the hosts. We consider now how the same VC justdescribed could be set up by signalling from the host.
To start the signalling process, hostA sends a setup message into thenetwork—that is, to switch1. The setup message contains, among otherthings, the complete destination address of hostB. The setup messageneeds to get all the way to B to create the necessary connection statein every switch along the way. We can see that getting the setup messageto B is a lot like getting a datagram to B, in that the switches have toknow which output to send the setup message to so that it eventuallyreaches B. For now, let’s just assume that the switches know enoughabout the network topology to figure out how to do that, so that thesetup message flows on to switches 2 and 3 before finally reachinghostB.
When switch1 receives the connection request, in addition to sendingit on to switch2, it creates a new entry in its virtual circuit tablefor this new connection. This entry is exactly the same as shownpreviously in Table 6. The main difference isthat now the task of assigning an unused VCI value on the interface isperformed by the switch for that port. In this example, the switchpicks the value 5. The virtual circuit table now has the followinginformation: “When packets arrive on port2 with identifier5, sendthem out on port1.” Another issue is that, somehow, hostA will needto learn that it should put the VCI value of 5 in packets that itwants to send to B; we will see how that happens below.
When switch2 receives the setup message, it performs a similar process;in this example, it picks the value 11 as the incoming VCI value.Similarly, switch3 picks 7 as the value for its incoming VCI. Eachswitch can pick any number it likes, as long as that number is notcurrently in use for some other connection on that port of that switch.As noted above, VCIs have link-local scope; that is, they have no globalsignificance.
Finally, the setup message arrives as hostB. Assuming that B is healthyand willing to accept a connection from hostA, it too allocates anincoming VCI value, in this case 4. This VCI value can be used by B toidentify all packets coming from hostA.
Now, to complete the connection, everyone needs to be told what theirdownstream neighbor is using as the VCI for this connection. HostBsends an acknowledgment of the connection setup to switch3 and includesin that message the VCI that it chose(4). Now switch3 can complete thevirtual circuit table entry for this connection, since it knows theoutgoing value must be4. Switch3 sends the acknowledgment on toswitch2, specifying a VCI of7. Switch2 sends the message on toswitch1, specifying a VCI of11. Finally, switch1 passes theacknowledgment on to hostA, telling it to use the VCI of5 for thisconnection.
At this point, everyone knows all that is necessary to allow traffic toflow from hostA to hostB. Each switch has a complete virtual circuittable entry for the connection. Furthermore, hostA has a firmacknowledgment that everything is in place all the way to hostB. Atthis point, the connection table entries are in place in all threeswitches just as in the administratively configured example above, butthe whole process happened automatically in response to the signallingmessage sent from A. The data transfer phase can now begin and isidentical to that used in the PVC case.
When hostA no longer wants to send data to hostB, it tears down theconnection by sending a teardown message to switch1. The switch removesthe relevant entry from its table and forwards the message on to theother switches in the path, which similarly delete the appropriate tableentries. At this point, if hostA were to send a packet with a VCI of 5to switch1, it would be dropped as if the connection had never existed.
There are several things to note about virtual circuit switching:
Since hostA has to wait for the connection request to reach the farside of the network and return before it can send its first datapacket, there is at least one round-trip time (RTT) of delay beforedata is sent.
While the connection request contains the full address for hostB(which might be quite large, being a global identifier on thenetwork), each data packet contains only a small identifier, which isonly unique on one link. Thus, the per-packet overhead caused by theheader is reduced relative to the datagram model. More importantly,the lookup is fast because the virtual circuit number can be treatedas an index into a table rather than as a key that has to be lookedup.
If a switch or a link in a connection fails, the connection is brokenand a new one will need to be established. Also, the old one needs tobe torn down to free up table storage space in the switches.
The issue of how a switch decides which link to forward theconnection request on has been glossed over. In essence, this is thesame problem as building up the forwarding table for datagramforwarding, which requires some sort of routing algorithm. Routingis described in a later section, and the algorithms described thereare generally applicable to routing setup requests as well asdatagrams.
One of the nice aspects of virtual circuits is that by the time the hostgets the go-ahead to send data, it knows quite a lot about thenetwork—for example, that there really is a route to the receiver andthat the receiver is willing and able to receive data. It is alsopossible to allocate resources to the virtual circuit at the time it isestablished. For example, X.25 (an early and now largely obsoletevirtual-circuit-based networking technology) employed the followingthree-part strategy:
Buffers are allocated to each virtual circuit when the circuit isinitialized.
The sliding window protocol is run between each pair of nodes alongthe virtual circuit, and this protocol is augmented with flow controlto keep the sending node from over-running the buffers allocated atthe receiving node.
The circuit is rejected by a given node if not enough buffers areavailable at that node when the connection request message isprocessed.
In doing these three things, each node is ensured of having the buffersit needs to queue the packets that arrive on that circuit. This basicstrategy is usually called hop-by-hop flow control.
By comparison, a datagram network has no connection establishment phase,and each switch processes each packet independently, making it lessobvious how a datagram network would allocate resources in a meaningfulway. Instead, each arriving packet competes with all other packets forbuffer space. If there are no free buffers, the incoming packet must bediscarded. We observe, however, that even in a datagram-based network asource host often sends a sequence of packets to the same destinationhost. It is possible for each switch to distinguish among the set ofpackets it currently has queued, based on the source/destination pair,and thus for the switch to ensure that the packets belonging to eachsource/destination pair are receiving a fair share of the switch’sbuffers.
In the virtual circuit model, we could imagine providing each circuitwith a different quality of service (QoS). In this setting, the termquality of service is usually taken to mean that the network gives theuser some kind of performance-related guarantee, which in turn impliesthat switches set aside the resources they need to meet this guarantee.For example, the switches along a given virtual circuit might allocate apercentage of each outgoing link’s bandwidth to that circuit. As anotherexample, a sequence of switches might ensure that packets belonging to aparticular circuit not be delayed (queued) for more than a certainamount of time.
There have been a number of successful examples of virtual circuittechnologies over the years, notably X.25, Frame Relay, and AsynchronousTransfer Mode (ATM). With the success of the Internet’s connectionlessmodel, however, none of them enjoys great popularity today. One of themost common applications of virtual circuits for many years was theconstruction of virtual private networks (VPNs), a subject discussedin a later section. Even that application is now mostly supported usingInternet-based technologies today.
Asynchronous Transfer Mode (ATM)
Asynchronous Transfer Mode (ATM) is probably the most well-known virtualcircuit-based networking technology, although it is now well past itspeak in terms of deployment. ATM became an important technology in the1980s and early 1990s for a variety of reasons, not the least of whichis that it was embraced by the telephone industry, which at that pointin time was less active in computer networks (other than as a supplierof links from which other people built networks). ATM also happened tobe in the right place at the right time, as a high-speed switchingtechnology that appeared on the scene just when shared media likeEthernet and token rings were starting to look a bit too slow for manyusers of computer networks. In some ways ATM was a competing technologywith Ethernet switching, and it was seen by many as a competitor to IPas well.
The approach ATM takes has some interesting properties, which makes itworth examining a bit further. The picture of the ATM packet format—morecommonly called an ATM cell—in Figure 61 will illustratethe main points. We’ll skip the generic flow control (GFC) bits, whichnever saw much use, and start with the 24 bits that are labelled VPI(virtual path identifier—8 bits) and VCI (virtual circuit identifier—16bits). If you consider these bits together as a single 24-bit field,they correspond to the virtual circuit identifier introduced above. Thereason for breaking the field into two parts was to allow for a level ofhierarchy: All the circuits with the same VPI could, in some cases, betreated as a group (a virtual path) and could all be switched togetherlooking only at the VPI, simplifying the work of a switch that couldignore all the VCI bits and reducing the size of the VC tableconsiderably.
Skipping to the last header byte we find an 8-bit cyclic redundancycheck (CRC), known as the header error check (HEC). It uses CRC-8and provides error detection and single-bit error correction capabilityon the cell header only. Protecting the cell header is particularlyimportant because an error in the VCI will cause the cell to bemisdelivered.
Probably the most significant thing to notice about the ATM cell, andthe reason it is called a cell and not a packet, is that it comes inonly one size: 53 bytes. What was the reason for this? One big reasonwas to facilitate the implementation of hardware switches. When ATM wasbeing created in the mid- and late 1980s, 10-Mbps Ethernet was thecutting-edge technology in terms of speed. To go much faster, mostpeople thought in terms of hardware. Also, in the telephone world,people think big when they think of switches—telephone switches oftenserve tens of thousands of customers. Fixed-length packets turn out tobe a very helpful thing if you want to build fast, highly scalableswitches. There are two main reasons for this:
It is easier to build hardware to do simple jobs, and the job ofprocessing packets is simpler when you already know how long each onewill be.
If all packets are the same length, then you can have lots ofswitching elements all doing much the same thing in parallel, each ofthem taking the same time to do its job.
This second reason, the enabling of parallelism, greatly improves thescalability of switch designs. It would be overstating the case to saythat fast parallel hardware switches can only be built usingfixed-length cells. However, it is certainly true that cells ease thetask of building such hardware and that there was a lot of knowledgeavailable about how to build cell switches in hardware at the time theATM standards were being defined. As it turns out, this same principleis still applied in many switches and routers today, even if they dealin variable length packets—they cut those packets into some sort of cellin order to forward them from input port to output port, but this is allinternal to the switch.
There is another good argument in favor of small ATM cells, having to dowith end-to-end latency. ATM was designed to carry both voice phonecalls (the dominant use case at the time) and data. Because voice islow-bandwidth but has strict delay requirements, the last thing you wantis for a small voice packet queued behind a large data packet at aswitch. If you force all packets to be small (i.e., cell-sized), thenlarge data packets can still be supported by reassembling a set of cellsinto a packet, and you get the benefit of being able to interleave theforwarding of voice cells and data cells at every switch along the pathfrom source to destination. This idea of using small cells to improveend-to-end latency is alive and well today in cellular access networks.
Having decided to use small, fixed-length packets, the next question waswhat is the right length to fix them at? If you make them too short,then the amount of header information that needs to be carried aroundrelative to the amount of data that fits in one cell gets larger, so thepercentage of link bandwidth that is actually used to carry data goesdown. Even more seriously, if you build a device that processes cells atsome maximum number of cells per second, then as cells get shorter thetotal data rate drops in direct proportion to cell size. An example ofsuch a device might be a network adaptor that reassembles cells intolarger units before handing them up to the host. The performance of sucha device depends directly on cell size. On the other hand, if you makethe cells too big, then there is a problem of wasted bandwidth caused bythe need to pad transmitted data to fill a complete cell. If the cellpayload size is 48bytes and you want to send 1byte, you’ll need tosend 47bytes of padding. If this happens a lot, then the utilization ofthe link will be very low. The combination of relatively highheader-to-payload ratio plus the frequency of sending partially filledcells did actually lead to some noticeable inefficiency in ATM networksthat some detractors called the cell tax.
As it turns out, 48 bytes was picked for the ATM cell payload as acompromise. There were good arguments for both larger and smaller cells,and 48 made almost no one happy—a power of two would certainly have beenbetter for computers to process.
3.1.3 Source Routing
A third approach to switching that uses neither virtual circuits norconventional datagrams is known as source routing. The name derivesfrom the fact that all the information about network topology that isrequired to switch a packet across the network is provided by the sourcehost.
There are various ways to implement source routing. One would be toassign a number to each output of each switch and to place that numberin the header of the packet. The switching function is then verysimple: For each packet that arrives on an input, the switch wouldread the port number in the header and transmit the packet on thatoutput. However, since there will in general be more than one switchin the path between the sending and the receiving host, the header forthe packet needs to contain enough information to allow every switchin the path to determine which output the packet needs to be placedon. One way to do this would be to put an ordered list of switch portsin the header and to rotate the list so that the next switch in thepath is always at the front of the list. Figure 62 illustrates this idea.
In this example, the packet needs to traverse three switches to get fromhost A to host B. At switch 1, it needs to exit on port 1, at the nextswitch it needs to exit at port 0, and at the third switch it needs toexit at port 3. Thus, the original header when the packet leaves host Acontains the list of ports (3, 0, 1), where we assume that each switchreads the rightmost element of the list. To make sure that the nextswitch gets the appropriate information, each switch rotates the listafter it has read its own entry. Thus, the packet header as it leavesswitch 1 en route to switch 2 is now (1, 3, 0); switch 2 performs anotherrotation and sends out a packet with (0, 1, 3) in the header. Althoughnot shown, switch 3 performs yet another rotation, restoring the headerto what it was when host A sent it.
There are several things to note about this approach. First, it assumesthat host A knows enough about the topology of the network to form aheader that has all the right directions in it for every switch in thepath. This is somewhat analogous to the problem of building theforwarding tables in a datagram network or figuring out where to send asetup packet in a virtual circuit network. In practice, however, it isthe first switch at the ingress to the network (as opposed to the endhost connected to that switch) that appends the source route.
Second, observe that we cannot predict how big the header needs to be,since it must be able to hold one word of information for every switchon the path. This implies that headers are probably of variable lengthwith no upper bound, unless we can predict with absolute certainty themaximum number of switches through which a packet will ever need topass.
Third, there are some variations on this approach. For example, ratherthan rotate the header, each switch could just strip the first elementas it uses it. Rotation has an advantage over stripping, however: Host Bgets a copy of the complete header, which may help it figure out how toget back to host A. Yet another alternative is to have the header carrya pointer to the current “next port” entry, so that each switch justupdates the pointer rather than rotating the header; this may be moreefficient to implement. We show these three approaches inFigure 63. In each case, the entry thatthis switch needs to read is A, and the entry that the next switchneeds to read is B.
Source routing can be used in both datagram networks and virtual circuitnetworks. For example, the Internet Protocol, which is a datagramprotocol, includes a source route option that allows selected packets tobe source routed, while the majority are switched as conventionaldatagrams. Source routing is also used in some virtual circuit networksas the means to get the initial setup request along the path from sourceto destination.
Source routes are sometimes categorized as strict or loose. In astrict source route, every node along the path must be specified,whereas a loose source route only specifies a set of nodes to betraversed, without saying exactly how to get from one node to the next.A loose source route can be thought of as a set of waypoints rather thana completely specified route. The loose option can be helpful to limitthe amount of information that a source must obtain to create a sourceroute. In any reasonably large network, it is likely to be hard for ahost to get the complete path information it needs to construct correctlya strict source route to any destination. But both types of sourceroutes do find application in certain scenarios, as we will see in laterchapters.
