LECTURE 1Connecting Computers with PacketSwitching1This lecture discusses different ways of interconnecting links (of the same kind) to builda simple computer network. To achieve this task, we will use a device called a switch, anddiscuss several different ways of switching to move data across a network. We focus onpacket switching, discussing its main ideas and principles.This lecture assumes that the reader is familiar with standard w ays of communicatingdigital information (bits and link-layer frames) over a single link. Most networking textscover this material in depth; we provide a short summary of the essential ideas in L0.! 1.1 InterconnectionsThe rather limited scope—in terms of physical distance, number of connected hosts, andamount of sustainable traffic—of s ing le-link network s leads us to examine ways of inter-connecting single-link communication media together to form larger networks of comput-ers. We start by discussing a fe w different interconnection techniques. The fundamentalproblem is that the most obvious w ay to build a comp uter network — by connecting eachpair o f comput ers with a dedicated link—is both prohibitively exp ensive (because of thesheer number of links required, a number that grows quadratically with the network size)and technically challenging (because signals attenuate with distance, requiring ways toregenerate information across large distances). The solution to t h ese problems is to de-velop ways to share links betwe en different communicating nodes, and to regenerate theinformation being communicated as it travels across the network.The key component us ed for such inte rconnections is a switch, which is a specializedcomputing device that receives data frames (of bits) that arrive over links, processes them,and forwards the m over one (or more) other links. Links are physically con n ected toswitches at attachment points or switch ports.1Copyright Hari Balakrishnan, 1998-2005, all rights reserved. Please do not redistribute without permis-sion.12 LECTURE 1. CONNECTING COMPUTERS WITH PACKET SWITCHINGThe fundamental functions performed by switches are to multiplex and demultiplexdata frames belonging to differe n t computer-to-computer information transfer sessions(or “conversations”), and to determine the link(s) along which to forward any given dataframe. This task is essential because a given physical link will usually be shared by severalconcurrent s essions between different computers.Over time, t wo radically different techniques have developed for doing this. The first,used by networks like the telephone networ k, is called circuit switching. The second, usedby network s like the Internet, is called packet switching. The key difference be tween thetwo is that, in circuit-switched networks, the frames do not need to carry any special in-formation that tells the switches how to forward information, while in packet -switchednetworks, the y do.The transmission of information in circuit-switched networks usually occurs in twophases: first, a setup phase in which some state is configured at each switch along a pathfrom source to destination, and second, the information transfer p h ase when the framesare actually sent. Of course, because the frames themselves contain no information aboutwhere they should go, the setup phase nee ds to instantiate the correct st ate in the switchesto enable correct forwarding.A common (but not the only) way to implement circuit switching is using time-divisionmultiplexing (TDM), also known as isochronous transmission. Here, the physical capacity ofa link connected to a switch, C (in bits/s), is conceptually broken into some number N o fvirtual “channels,” such that the ratio C/N bits/s is sufficient for each information transfersession (such as a telephone call between two parties). Call this ratio, R, t h e rate of eachindependent transfer se ssion. Now, if w e constrain each frame to be of some fixed size,s bits, then the switch can perform time multiplexing by allocating the link’s capacity intime-slots of len gth s/C u n its each, and by associating the ith time-slice to the ith trans fer(modulo N). It is easy to s ee that this approach provides each session with the required rateof R bits/s, because each session gets to send s bits over a time period of Ns/C seconds,and th e r atio of the two is equal to C/N = R bits/s.Each data frame is therefore forwarded by simply using the time slot in which it arrivesat the switch to decide which port it should be sent on. Thus, the state set up during thefirst ph ase has to associate one of these channels with the correspond ing soon-to-followdata transfer by allocating the ith time-slice to the ith transfer. The end comp uters trans-mitting data send frames only at the specific time-slots that they have been told to do soby t h e setup phase .Other ways of doing circuit switching include w avelength division m ultiplexing (WDM),frequency division multiplexing (FDM), and code division multiplexing (CDM); the latter two(as well as TDM) are used in s ome cellular wireless networks. Various networking text-books (e.g. , Tanenbaum, Peterson and Davie, etc.) describe these schemes in some det ail.Circuit switching makes sense fo r a networ k where t h e workload is relatively uniform,with all information transfers using the same capacity, and where each transfer uses a con -stant bit rate (CBR) (or near-constant bit rate). The most compelling example of such aworkload is telephony, and this is indeed how most telephone netw orks today are archi-tected. (The other reason for t h is d esign choice is historical; circuit switching was inventedlong before packet switching.)However, circuit-switching tends to waste link capacity if the workload has a variableSECTION 1.2. PACKET SWITCHING 3bit-rate, or if the frames arrive in bursts at a switch. Because a large number of computerapplications induce burst data patt erns, we should consider at othe r link sharing strategiesfor computer n etworks. It tur n s out that the once-radical packet-switching technique is ageneral way of getting better performance for such workloads, and is the fundamentalmultiplexing approach use d in most networks to day.! 1.2 Packet switchingThe best way to overcome t h e above inefficiencies is to allow for any sender to transmitdata at any time, but yet allow the link to be shared. Packet switching is a way to accom-plish this, and u ses a tantalizingly simple idea: add to