E> THE TAMIL NADU : Dr. AMBEDKAR LAW UNIVERSITY (State University Established by Act No. 43 of 1997) SCHOOL OF EXCELLENCE IN LAW ‘Perungudi Campus’, M.G.R. Salai, Perungudi, Chennai - 600 113. COMPUTER NETWORKS AND NETWORK SECURITY COURSE MATERIAL FOR BCA.LL.B (For the candidates admitted from academic year 2015 - 2016 onwards) By K. SHANTHI Guest Faculty, Department of Inter-Disciplinary School of Excellence in Law The Tamil Nadu Dr. Ambedkar Law University, ChennaiPREFACE The merging of computers and communications has had a profound influence on the ‘way computer systems are organized. The old model of a single computer serving all of the organization’s computational needs has been replaced by one in which a large number of separate but interconnected computers do the job. These systems are called computer networks. Throughout the book we will use the term “computer network” to mean a collection of autonomous computers interconnected by a single technology. Two computers are said to be interconnected if they are able to exchange information. The connection need not be via a copper wire; fiber optics, microwaves, infrared, and communication satellites can also be used. Networks come in many sizes, shapes and forms, as we will see later. They are usually connected together to make larger networks, with the Internet being the most well-known example of a network of networks. The course material for the subject “Computer Networks and Network Security” isa simple version of the various topics contained in the syllabus. It deals with the fundamental concepts of computer network. This text is intended for a first course in databases at the undergraduate level. This material describes the concepts as intuitive descriptions, many of which are based on our running example of a university. Important theoretical results are covered, but formal proofs are omitted. In place of proofs, figures and examples are used to suggest why a result is true. This material is an extract of sufficient information’s collected from various texts on computer networks. This material will be a supportive one along with textbooks and other references. K.SHANTHI Guest Faculty, Department of Inter-Disciplinary School of Excellence in Law The Tamil Nadu Dr. Ambedkar Law University, ChennaiCOMPUTER NETWORKS AND NETWORK SECURITY SUBJECT CODE: HDSB/CHD5B CONTENTS S.No. Contents UNIT-I INTRODUCTION Overview of Computer Networks —Applications—Line Configuration ~Topology — Transmission Modes ~ Categories of Network: LAN,MAN, WAN —Reference Models — OSI and TCP/IP Models ~Physical Layer ~ Theoretical Basis for Data Communication —Guided Transmission Media. 2 UNIT-II DATALINK LAYER Data Link Layer: Error Detection Error Correction ~Elementary Data Link Protocols —Sliding Window Protocols ~Data Link Layer in the Intemet Medium Access Layer Channel Allocation Problem, Multiple Access Protocols. ‘Network Layer — Design Issues —Routing Algorithms Congestion Control Algorithms,UNIT- III NETWORK LAYER Network Layer: IP Protocol —IPAddress = Internet Control Protocol. ‘Transport Layer — Design Issues —Connection Management —Addressing —Establishing and releasing Connection —Simple Transport Protocol — Internet Transport Protocol (TCP). 88 - 108 UNIT—IV NETWORK SECURITY — Network Security Overview ‘Symmetric Ciphers: Classical Eneryption Techniques, Symmetric Ciphers: Block and the Data Eneryption Standards, —Public key Encryption and Hash Functions: —Public Key Cryptography and RSA. 109 - 138 UNIT—V SECURITY PRACTICES — Network Security Practices : — Authentication Applications ~ Electronic Mail Security : IP Security —Web Security — Firewall. 139-174 MODEL QUESTION PAPER and ANSWER HINTS 175UNIT-I INTRODUCTION 1.1 Overview of Computer Networks 1.1.1 Introduction of Computer Networks Today the world scenario is changing. Data Communication and network have changed the way business and other daily affair works. Now, they rely on computer networks and internetwork. A set of devices often mentioned as nodes connected by media link is called a Network. A node can be a device which is capable of sending or receiving data generated by other nodes on the network like a computer, printer etc. These links connecting the devices are called Communication channels. Computer network is a telecommunication channel through which we can share our data. It is also called data network. The best example of computer network is Internet. Computer network does not mean a system with control unit and other systems as its slave. It is called a distributed system A network must be able to meet certain criteria, these are mentioned below: 1. Performance 2. Reliability 3. Scalability Performance It can be measured in following ways : + Transit time : It is the time taken to travel a message from one device to another. + Response time : It is defined as the time elapsed between enquiry.and response. Other ways to measure performance are : 1, Efficiency of software 2, Number of users 3. Capability of connected hardware Reliability It decides the frequency at which network failure take place. More the failures are, less is the network's reliability.Security It refers to the protection of data from the unauthorised user or access. While travelling through network, data passes many layers of network, and data can be traced if attempted. Hence security is also a very important characteristic for Networks. 1.1.2 Properties of Good Network 1. Interpersonal Communication : We can communicate with each other efficiently and easily example emails, chat rooms, video conferencing etc. 2. Resources can be shared : We can use the resources provided by network such as printers etc. 3. Sharing files, data : Authorised users are allowed to share the files on the network. 1.1.3 Basic Communication Model Communication model is used to exchange data between two parties. For example communication between a computer, server and telephone (through modem). (source }= cPU eee 1.5.2 HALF DUPLEX Mode In half duplex system we can send data in both directions but it is done one at a time that is when the sender is sending the data then at that time we can’t send the sender our message. The data is sent in one direction. Example of half duplex is a walkie- talkie in which message is sent one at a time and messages are sent in both the directions 16Direction of data 1 —> +— Direction of data 2 1.5.3 FULL DUPLEX Mode In full duplex system we can send data in both directions as it is bidirectional. Data can be sent in both directions simultaneously. We can send as well as we receive the data. Example of Full Duplex is a Telephone Network in which there is communication between two persons by a telephone line, through which both can talk and listen at the same time. Direction of Data +> In full duplex system there can be two lines one for sending the data and the other for receiving data, Direction of Data ¢— Direction of Data. —> 1.6 Categories of Network: LAN, MAN, WAN 71.6.1 Local Area Network (LAN) It is also called LAN and designed for small physical areas such as an office, group of buildings or a factory. LANs are used widely as it is easy to design and to troubleshoot. Personal computers and workstations are connected to each other through LANs. We can use different types of topologies through LAN, these are Star, Ring, Bus, Tree etc. LAN can be a simple network like connecting two computers, to share files and network among each other while it can also be as complex as interconnecting an entire building. LAN networks are also widely used to share resources like printers, shared hard-drive ete. LC) Bus Network ( Ditteret Topoigies interconnected ina Local Area Network) 1.6.1.1 Applications of LAN + One of the computer in a network can become a server serving all the remaining computers called clients. Software can be stored on the server and it can be used by the remaining clients. + Connecting Locally all the workstations in a building to let them communicate with each other locally without any internet access. + Sharing common resources like printers etc are some common applications of LAN.1.6.2 Metropolitan Area Network (MAN It is basically a bigger version of LAN. It is also called MAN and uses the similar technology as LAN. It is designed to extend over the entire city. It can be means to connecting a number of LANs into a larger network or it can be a single cable. It is mainly hold and operated by single private company or a public company. Ring Network Bus Network 1.6.3 Wide Area Network (WAN It is also called WAN. WAN can be private or it can be public leased network. It is used for the network that covers large distance such as cover states of a country. It is not easy to design and maintain. Communication medium used by WAN are PSTN or Satellite links. WAN operates on low data rates. 1.6.4 ‘eless Network It is the fastest growing segment of computer. They are becoming very important in our daily life because wind connections are not possible in cars or aeroplane. We can access Internet at any place avoiding wire related troubles.. These can be used also whenthe telephone systems gets destroyed due to some calamity/disaster. WANs are really important now-a-days. Iof iy ‘Transmiting Connection Signals 1.6.5 Inter Network When we connect two or more networks then they are called internetwork or internet. We can join two or more individual networks to form an internetwork through devices like routers gateways or bridges. “Fa Ca neRNeTWoRK. 1.7 Reference Models — OSI and TCP/IP Models The most important reference models are : 1. OSI reference model 2. TCPAP reference model.1.7.1 ISO-OSI Model: There are numbers of users who use computer network and are located over the world, So to ensure, national and worldwide data communication, systems must be developed which are compatible to communicate with each other. ISO has developed this, ISO stands for International organization of Standardization. This is called a model for Open System Interconnection (OSI) and is commonly known as OSI model. The ISO-OSI model is a seven layer architecture. It defines seven layers or levels in a complete communication system. 17 Feature of OSI Model : 1. Big picture of communication over network is understandable through this OSI model. . We see how hardware and software work together. . We can understand new technologies as they are developed. |. Troubleshooting is easier by separate networks. . Can be used to compare basic functional relationships on different networks. won 21.7.2 Functions of Different Layers : L721 Layer 1: The Physical Layer : 1. It is the lowest layer of the OSI Model. 2. It activates, maintains and deactivates the physical connection. 3. It is responsible for transmission and reception of the unstructured raw data over network. 4. Voltages and data rates needed for transmission is defined in the physical layer. . It converts the digital/analog bits into electrical signal or optical signals. 6. Data encoding is also done in this layer. w 1.7.2.2 Layer 2: Data Link Layer : . Data link layer synchronizes the information which is to be transmitted over the physical layer. 2. The main function of this layer is to make sure data transfer is ervor free from one node to another, over the physical layer. 3. Transmitting and receiving data frames sequentially is managed by this layer. 4. This layer sends and expects acknowledgements for frames received and sent respectively. Resending of non-acknowledgement received frames is also handled by this layer. 5. This layer establishes a logical layer between two nodes and also manages the Frame traffic control over the network. It signals the transmitting node to stop, when the frame buffers are full. 1.7.2.3 Layer 3: The Network Layer : 1, It routes the signal through different channels from one node to other. 2. Tt acts as a network controller. It manages the Subnet traffic. 3. It decides by which route data should take. 4. It divides the outgoing messages into packets and assembles the incoming packets into messages for higher levels. 1.7.2.4 Layer 4: Transport Layer : 1. It decides if data transmission should be on parallel path or single path, 2. Functions such as Multiplexing, Segmenting or Splitting on the data are done by this layer 223. It receives messages from the Session layer above it, convert the message into smaller units and passes it on to the Network layer. 4, Transport layer can be very complex, depending upon the network requirements. Transport layer breaks the message (data) into small units so that they are handled more efficiently by the network layer. 17.25 Layer 5: The Session Layer : . Session layer manages and synchronize the conversation between two different applications. 2. Transfer of data from source to destination session layer streams of data are marked and are resynchronized properly, so that the ends of the messages are not cut prematurely and data loss is avoided. 1.7.2.6 Layer 6: The Presentation Layer : 1. Presentation layer takes care that the data is sent in such a way that the receiver will understand the information (data) and will be able to use the data. 2. While receiving the data, presentation layer transforms the data to be ready for the application layer. 3. Languages(syntax) can be different of the two communicating systems. Under this condition presentation layer plays a role of translator. 4. It performs Data compression, Data encryption, Data conversion etc. 1.7.2.7 Layer 7: Application Layer : 1. It is the topmost layer. 2. Transferring of files disturbing the results to the user is also done in this layer. Mail services, directory services, network resource ete are services provided by application layer. 3. This layer mainly holds application programs to act upon the received and to be sent data. 1.7.2.8 Merits of OSI reference model: 1. OSI model distinguishes well between the services, interfaces and protocols. 2. Protocols of OSI model are very well hidden 3. Protocols can be replaced by new protocols as technology changes. 4, Supports connection oriented services as well as connectionless service. 231.7.2.9 Demerits of OSI reference model: 1. Model was devised before the invention of protocols. 2. Fitting of protocols is tedious task. 3. It is just used as a reference model. 1.7.3 TCP/IP REFERENCE Model TCP/IP means Transmission Control Protocol and Internet Protocol. It is the network model used in the current Internet architecture as well. Protocols are set of rules which govern every possible communication over a network. These protocols describe the movement of data between the source and destination or the internet. These protocols offer simple naming and addressing schemes. TCP/IP that is Transmission Control Protocol and Internet Protocol was developed by Department of Defence's Project Research Agency (ARPA, later DARPA) as a part of a research project of network interconnection to connect remote machines. The features that stood out during the research, which led to making the TCP/IP reference model were: + Support for a flexible architecture. Adding more machines to a network was easy. + The network was robust, and connections remained intact untill the source and destination machines were functioning. The overall idea was to allow one application on one computer to talk to(send data packets) another application running on different computer. RRICATON NER = Ton TONETWORE werworn access ven) 24Description of different TCP/IP protocols 1.7.3.1 Layer 1: Host-to-network Layer 1. Lowest layer of the all. 2. Protocol is used to connect to the host, so that the packets can be sent over it. 3. Varies from host to host and network to network. 1.7.3.2 Layer 2: Internet layer 1, Selection of a packet switching network which is’ based on a connectionless internetwork layer is called a internet layer. . It is the layer which holds the whole architecture together. . It helps the packet to travel independently to the destination. |. Order in which packets are received is different from the way they are sent. . IP (Internet Protocol) is used in this layer. waRwWN 1.7.3.3 Layer 3: Transport Layer . It decides if data transmission should be on parallel path or single path. 2. Functions such as multiplexing, segmenting or splitting on the data is done by transport layer. . The applications can read and write to the transport layer. 4, Transport layer adds header information to the data. 5, Transport layer breaks the message (data) into small units so that they are handled more efficiently by the network layer. 6. Transport layer also arrange the packets to be sent, in sequence. wo 1.73.4 Layer 4: Application Layer The TCP/IP specifications described a lot of applications that were at the top of the protocol stack. Some of them were TELNET, FTP, SMTP, DNS etc. 1. TELNET is a two-way communication protocol which allows connecting to a remote machine and run applications on it. 2. FTP(File Transfer Protocol) is a protocol, that allows File transfer amongst computer users connected over a network. It is reliable, simple and efficient. 3. SMTP(Simple Mail Transport Protocol) is a protocol, which is used to transport electronic mail between a source and destination, directed via a route. 254, DNS(Domain Name Server) resolves an IP address into a textual address for Hosts connected over a network. 1.7.3.5 Merits of TCP/IP model . It operated independently. . It is scalable. . Client/server architecture. . Supports a number of routing protocols. . Can be used to establish a connection between two computers. wWRYNS 1.7.3.6 | Demerits of TCP/IP 1. In this, the transport layer does not guarantee delivery of packets. 2. The model cannot be used in any other application. 3. Replacing protocol is not easy. 4. It has not clearly separated its services, interfaces and protocols. Comparison of OSI Reference Model and TC! Reference Model Following are some major differences between OSI Reference Model and TCP/IP Reference Model OSI(Open System Interconnection) |] TCP/IP(Transmission Control Protocol / Internet Protocol) 1. OSI is a generic, protocol 1. TCP/IP model is based on standard protocols independent standard, acting as a around which the Internet has developed. It is a communication gateway between the |] communication protocol, which allows network and end user. connection of hosts over a network. 2. In OSI model the transport layer |} 2. In TCP/IP model the transport layer does not guarantees the delivery of packets. _ |} guarantees delivery of packets. Still the TCP/IP 26model is more reliable. 3. Follows vertical approach. 3. Follows horizontal approach. 4, OSI model has a separate Presentation layer and Session layer. 4. TCP/IP does not have a separate Presentation layer or Session layer. 5. OSI is a reference model around which the networks are built. Generally it is used as a guidance tool. 5. TCP/IP model is, in a way implementation of the OSI model. 6. Network layer of OSI model provides both connection oriented and connectionless service. 6. The Network layer in TCP/IP model provides connectionless service. 7. OSI model has a problem of fitting the protocols into the model. 7. TCP/IP model does not fit any protocol 8, Protocols are hidden in OSI model and are easily replaced as the technology changes. 8, In TCP/IP replacing protocol is not easy. 9. OSI model defines services, interfaces and protocols very clearly and makes clear distinction between them. It is protocol independent. 9. In TCP/IP, services, interfaces and protocols are not clearly separated. It is also protocol dependent. 10. It has 7 layers 10. Ithas 4 layers ra 71.8 Physical Layer Physical layer in the OSI model plays the role of interacting with actual hardware and signaling mechanism. Physical layer is the only layer of OSI network model which actually deals with the physical connectivity of two different stations. This layer defines the hardware equipment, cabling, wiring, frequencies, pulses used to represent binary signals etc. Physical layer provides its services to Data-link layer. Data-link layer hands over frames to physical layer. Physical layer converts them to electrical pulses, which represent binary data. The binary data is then sent over the wired or wireless media. 1.8.1 Functions of Physical Layer 1, Representation of Bits: Data in this layer consists of stream of bits. The bits must be encoded into signals for transmission. It defines the type of encoding i.e. how 0’s and 1's are changed to signal. 2. Data Rate: This layer defines the rate of transmission which is the number of bits per second. 3. Synchronization: It deals with the synchronization of the transmitter and receiver. The sender and receiver are synchronized at bit level. 4. Interface: The physical layer defines the transmission interface between devices and transmission medium. 5, Line Configuration: This layer connects devices with the medium: Point to Point configuration and Multipoint configuration. 6. Topologies: Devices must be connected using the following topologies: Mesh, Star, Ring and Bus. 7. Transmission Modes: Physical Layer defines the direction of transmission between two devices: Simplex, Half Duplex, Full Duplex. 8. Deals with baseband and broadband transmission. 28signals When data is sent over physical medium, it needs to be first converted into electromagnetic signals. Data itself can be analog such as human voice, or digital such as file on the disk. Both analog and digital data can be represented in digital or analog signals. Digital Signals Digital signals are discrete in nature and represent sequence of voltage pulses. Digital signals are used within the circuitry of a computer system. Analog Signals Analog signals are in continuous wave form in nature and represented by continuous electromagnetic waves. 1.8.3 Transmission Impairment When signals travel through the medium, they tend to deteriorate. This may have many reasons as given: Attenuation For the receiver to interpret the data accurately, the signal must be sufficiently strong. When the signal passes through the medium, it tends to get weaker. As it covers distance, it loses strength. 29Dispersion As signal travels through the media, it tends to spread and overlaps, The amount of dispersion depends upon the frequency used. Delay distortion Signals are sent over media with pre-defined speed and frequency. If the signal speed and frequency do not match, there are possibilities that signal reaches destination inarbitrary fashion. In digital media, this is very critical that some bits reach earlier than the previously sent ones. Noise Random disturbance or fluctuation in analog or digital signal is said to be Noise in signal, which may distort the actual information being carried. Noise can be characterized in one of the following class: Thermal Noise Heat agitates the electronic conductors of a medium which may introduce noise in the media. Up to a certain level, thermal noise is unavoidable. Intermodulation When multiple frequencies share a medium, their interference can cause noise in the medium. Intermodulation noise occurs if two different frequencies are sharing a medium and one of them has excessive strength or the component itself is not functioning properly, then the resultant frequency may not be delivered as expected. Crosstalk This sort of noise happens when a foreign signal enters into the media. This is because signal in one medium affects the signal of second medium. Impulse This noise is introduced because of irregular disturbances such as lightening, electricity, short-circuit, or faulty components. Digital data is mostly affected by this sort of noise. 1.8.4 Channel Capacity The speed of transmission of information is said to be the channel capacity. We count it as data rate in digital world, It depends on numerous factors such as: 30* Bandwidth: The physical limitation of underlying media. © Error-rate: Incorrect reception of information because of noise. « Encoding: The number of levels used for signaling. Multiplexing Multiplexing is a technique to mix and send multiple data streams over a single medium. This technique requires system hardware called multiplexer (MUX) for multiplexing the streams and sending them on a medium, and de-multiplexer (DMUX) which takes information from the medium and distributes to different destinations. 1.8.6 Switching Switching is a mechanism by which data/information sent from source towards destination which are not directly connected. Networks have interconnecting devices, which receives data from directly connected sources, stores data, analyze it and then forwards to the next interconnecting device closest to the destination. Switching can be categorized as: 1.9 Theoretical Basis for Data Communication 1 Fourier Analysis Fourier showed that a periodic function g(t) can be represented mathematically as an in nite series of sines and cosines: 1 1 I c g(t)=2+ “ay sin(2 nf t)+ *b,cos(2 nft) n=1 nl a11. fis the function's fundamental frequency 2. T= is the function's period 3. ay and by are the amplitudes of the nth harmonics The series representation of g(t) is called its Fourier series expansion. In communications, we can always represent a data signal using a Fourier series by imagining that the signal repeats the same pattern forever. Moreover, we can compute the coefficients a, and Dy : 22 7 o()sin(2 nf a, = t)dt To 27 7 g(t)cos(2_ nf b, = thdt TO 2 c= 77 gitydt TO For instance, suppose we use voltages (on/o ) to represent \1"s and \0"s, and we transmit the bit string \011000010'. The signal would look as follows: Recall (from calculus): 1. the derivative of sin(x) = cos(x)dx 2, the derivative of cos(x) = -sin(x)dx 2 a, = ” * g(t)sin(2 nf t)dt To 32z 2\ sin(2 nf at +” = 3.4 sin(2 nf t)dt] T1 6 21 = cos(2 nf tis" T2 of 1 [eos(2 nf3) cos(2 nf) +cos(2 nf7) cos(2 nf = 6)] nfT f=158 = *JTeos( n=4)) cos(3 n=4)+cos(6 n=4) cos(7 n=4)] Similarly, by =n [sin(3 n=4)) sin( n=4) + sin(7 n=4) sin(6 n=4)] And Points to note about the Fourier expansion 1. The more terms in the expansion, the more exact our representation becomes. ora 2. The expression a’, + b?, represents the amplitude or energy of the signal (e.g., the harmonics contribution to the wave). In our example, the amplitude consists of a, and continually gets smaller. (The b, term is always zero.) Here, as in most cases, the rst harmonics are the most important ones. 33The following facts are important: 1. Signals attenuate (strength of signal falls 0 with distance) during transmission. How much attenuation occurs? The exact amount is dependent on physical properties of the medium. N . Distortion results because attenuation is non-uniform across the frequency spectrum; some frequencies distort more than others. That is, the signal doesn't distort uniformly. If every component decreased by the same amount, the signal would be weaker, but not distorted, and amplifying the signal would restore it. Because the received signal is distorted, however, ampli cation simply magni es the distortion and probably won't help. ba A transmission medium carries signals lying within in a spectrum or range of frequencies; the absolute width of the spectrum is called the bandwidth of the channel. In other words, most channels completely attenuate (e.g. chop o ) frequencies beyond some threshold value. 1.9.2 Factors deter ig the rate of data transmission 1. The baud rate (also known as the modulation rate) refers to the maximum rate at which the signal changes value (e.g., switches voltages). For example, if \0"s and \1"s were represented as +5V, -5V, respectively, the baud rate would refer to the number of times per second the signal switches as its transmitting a string of alternating 0's and I's. Note that we can potentially achieve a higher data rate by switching the voltage faster. R . The encoding method determines the amount of information carried in one baud. In our example we encoded only one bit of information (0 or 1). How can we encode 2 bits worth of information in one baud? Use 4 di erent voltage levels. For example, 0, 1, 2, 3 could be represented as -10, -5, +5 and +10 volts respectively. Note: baud rate is not the same thing as the data rate, For a given baud rate, we can increase the data rate by changing the encoding method (subject to Nyquist and Shannon limits, of course.) 1.9.3 Voice Grade Lines What kind of data rate can we achieve using voice-grade phone lines? 34The phone system is designed to carry human voices (not data!), and its bandwidth line is limited to about 3 kHz. Suppose that we have a bit rate of b bits/sec (assume only encode one bit of data per baud). 1. For 8 bits of data, the fundamental frequency F would be b=8 Hz. 2. Because the phone line attenuates frequencies above 3 kHz, the number of the highest harmonic passed through is 3000=F = 3000=(b=8) = 24000=b. 3. At 1200 baud, the fundamental frequency is 1200=8 = 150Hz, and the highest numbered harmonic passed is 24000=1200 = 20. That is, only the rst 20 terms of the Fourier series are relevant; the phone line will chop o all higher numbered terms. The following table gives more values Baud Fundamental _ [Number of Rate [Harmonic (Hz) |Harmonics sent 1200 | __150 20 2400 300 10 4800 600. = 9600 1200 [| 2.5 19200 [2400 1.25 38400 | 4800 025 Will we be able to send data at 38,400 baud? No! It should be clear that sending data at 38400 baud over a voice grade line simply won't work, Even at 9600 baud only the rst and second harmonic are transmitted, and the signal will be severely distorted. It is unlikely that the receiver will be able to recognize the signal as intended. Must use better encoding schemes for higher data rates. Maximum Data Rate of a Channel Nyquist (1924) studied the problem of data transmission for a ne bandwidth noiseless channel. Nyquist states: 1. If a signal has been run through a low-pass Iter of bandwidth H, the Itered signal 35can be completely reconstructed by making 2H samples. The important corollary to Nyquist's rule is that sampling more often is pointless because the higher frequencies have been Itered out. 2. If the encoding signal method consists of V states: maximum data rate = 2H log V bps What's the maximum data rate over phone lines? Going back to our telephone example, Nyquist's theorem tells us that a one-bit signal encoding can produce no better than: 2° 3000 log: 2 = 6000bps. But there is a catch. In practice, we don't come close to approaching this limit, because Nyquist's rule applies only to noiseless channels. Noise on a Channel In practice, every channel has background noise. Specifically: 1. Thermal noise results from thermal agitation of electrons in a conductor. It cannot be eliminated, and depends on the temperature, bandwidth, and Boltzman's constant K. Is uniformly distributed across the frequency spectrum and thus called white noise. N Inter modulation noise results when di erent frequencies share the same transmission medium; unwanted signals often appear at frequencies that are the sum or differences of the two frequencies. wo Crosstalk noise results from unwanted coupling between signal paths. Hearing another conversation (faintly) on a telephone connection is an example of crosstalk. S Impulse noise consists of sharp, short-lived disturbances, from such sources such as lightning. How do we measure (or quantify the amount of) background noise? The signal-to-noise ratio is a measure of the unwanted noise present on a line. It is expressed in decibels (db) and given by: signal power $-Neqpy “101 (db) ~'°!°10 noise power 361.9.4 Shannon's Theorem Shannon's theorem gives the maximum data rate for channels having noise (e.g., all real channels). Shannon's theorem states that the maximum data rate of a noisy channel of bandwidth H , signal-to-noise ratio of S=N is given by: max data rate = H log, (1 + S=N ) Note: the signal to noise ratio S=N used in Shannon's theorem refers to the ratio of signal power to noise power, not the ratio expressed in dbs (decibels). Unlike Nyquist's limit, Shannon's limit is valid regardless of the encoding method. Let's consider a phone line again. A typical value for the S=N ratio for phone lines is 30db. db) = 10 = S=N = 10** 1000. Thus, the maximum data rate = 3000 log,(1 + 1000) 30; 000 bps. But wait | don't modems deliver data at 38.4 and 56 kbps? Many modem companies advertise that their modem deliver higher data rates, are they lying? Not necessarily. Read the ne print. Most likely, the modem uses data compression, and the high data rate is achieved only with text data Let's summarize what Nyquist and Shannon say: © Nyquist: sampling a received signal more frequently than 2H (where H is the bandwidth of the channel) is pointless. © Nyquist: maximum data rate = 2Hlog:V bps, where H is the bandwidth of the channel, and V is the number of distinct encodings for each baud. This result is a theoretical upper bound on the data rate in the absence of noise. Shannon: maximum data rate = Hlog,(1 + S=N ), where S/N is the ratio of signal power to noise power. Note that Shannon's result is independent of the number of distinct signal encodings. Nyquist’s theorem implies that we can alway increase the data rate by increasing the number of distinct encodings; Shannon's limit says that is not so for a channel with noise 1.10 Guided Trans ion Media It is the transmission media in which signals are confined to a specific path using wire or cable, The types of Bounded/ Guided are discussed below. 371.10.1 Twisted Pair Cable This cable is the most commonly used and is cheaper than others. It is lightweight, cheap, can be installed easily, and they support many different types of network. Some important points : + Its frequency range is 0 to 3.5 kHz. + Typical attenuation is 0.2 dB/Km @ 1kHz. + Typical delay is 50 ps/km. + Repeater spacing is 2km. Twisted Pair is of two types : + Unshielded Twisted Pair (UTP) + Shielded Twisted Pair (STP) 1.10.2 Unshielded Twisted Pair Cable It is the most common type of telecommunication when compared with Shielded Twisted Pair Cable which consists of two conductors usually copper, each with its own colour plastic insulator. Identification is the reason behind coloured plastic insulation. UTP cables consist of 2 or 4 pairs of twisted cable. Cable with 2 pair use RJ- 11 connector and 4 pair cable use RJ-45 connector. Unsheded Twisted Pa Cable 1.10.21 Advantages : + Installation is easy + Flexible + Cheap 38+ Ithas high speed capacity, + 100 meter limit + Higher grades of UTP are used in LAN technologies like Ethernet. It consists of two insulating copper wires (1mm thick). The wires are twisted together in a helical form to reduce electrical interference from similar pair. 1.10.2.2 Disadvantages : + Bandwidth is low when compared with Coaxial Cable + Provides less protection from interference. 1,10.3Shielded Twisted Pair Cable This cable has a metal foil or braided-mesh covering which encases each pair of insulated conductors. Electromagnetic noise penetration is prevented by metal casing. Shielding also eliminates crosstalk (explained in KEY TERMS Chapter). It has same attenuation as unshielded twisted pair. It is faster the unshielded and coaxial cable. It is more expensive than coaxial and unshielded twisted pair. —_ 1.10.31 Advantages : + Easy to install + Performance is adequate + Can be used for Analog or Digital transmission + Increases the signalling rate + Higher capacity than unshielded twisted pair + Eliminates crosstalk 1.10.3.2 Disadvantages : + Difficult to manufacture + Heavy 391.10.4Coaxial Cable Coaxial is called by this name because it contains two conductors that are parallel to each other. Copper is used in this as centre conductor which can be a solid wire or a standard one. It is surrounded by PVC installation, a sheath which is encased in an outer conductor of metal foil, barid or both. Outer metallic wrapping is used as a-shield against noise and as the second conductor which completes the circuit. The outer conductor is also encased in an insulating sheath. The outermost part is the plastic cover which protects the whole cable. Here the most common coaxial standards. + 50-Ohm RG-7 or RG-11 : used with thick Ethernet. + 50-Ohm RG-58 : used with thin‘Ethernet + 75-Ohm RG-59 : used with cable television + 93-Ohm RG-62 : used with ARCNET. | a E Jacket Outer Insulator Inner Plastic Conductor Conductor Cover (shield) There are two types of Coaxial cables : 1.10.4.1 BaseBand This is a 50 ohm (Q) coaxial cable which is used for digital transmission. It is mostly used for LAN’s. Baseband transmits a single signal at a time with very high speed. The major drawback is that it needs amplification after every 1000 feet. 1.10.4.2 BroadBand This uses analog transmission on standard cable television cabling. It transmits several simultaneous signal using different frequencies. It covers large area when compared with Baseband Coaxial Cable. 401.10.43 Advantages : + Bandwidth is high + Used in long distance telephone lines. + Transmits digital signals at a very high rate of 10Mbps. + Much higher noise immunity + Data transmission without distortion. + The can span to longer distance at higher speeds as they have better shielding when compared to twisted pair cable 1.10.4.4 Disadvantages : * Single cable failure can fail the entire network. + Difficult to install and expensive when compared with twisted pair. + Ifthe shield is imperfect, it can lead to grounded loop. 1.10.5Fiber Optic Cable These are’similar to coaxial cable. It uses electric signals to transmit data. At the centre is the glass core through which light propagates. In multimode fibres, the core is SOmicrons, and In single mode fibres, the thickness is 8 to 10 microns. The core in fiber optic cable is surrounded by glass cladding with lower index of refraction as compared to core to keep all the light in core. This is covered with a thin plastic jacket to protect the cladding. The fibers are grouped together in bundles protected by an outer shield. Fiber optic cable has bandwidth more than 2 gbps (Gigabytes per Second) atGlass cladding Glass Core Jacket 1,10.5.1 Advantages : + Provides high quality transmission of signals at very high speed. + These are not affected by electromagnetic interference, so noise and distortion is very less. + Used for both analog and digital signals. 1.10.5.2 Disadvantages : + It is expensive + Difficult to install. + Maintenance is expensive and difficult. + Do not allow complete routing of light signals. Revi juestions 1, Draw the ISO-OSI reference model and explain the functionalities of each layer in detail. 2. Compare the OSI reference model with TCP reference model. Explain how the layers can be grouped. 3. What is the difference between half-duplex and full-duplex transmission modes? 4. Name the four basic network topologies, and cite an advantage of each type. 5. For n devices in a network, what is the number of cable links required for a mesh, ring, bus, and star topology? 6. What are some of the factors that determine whether a communication system is a LAN or WAN? . Discuss the various transmission media in detail. . Explain the application areas of computer networks . Examine Shannon’s Theorem 0. Describe the functions of the physical layer in detail. span 42UNIT -IT DATA LINK LAYER 2.1 Data Link Layer Data Link Layer is second layer of OSI Layered Model. This layer is one of the most complicated layers and has complex functionalities and liabilities. Data link layer hides the details of underlying hardware and represents itself to upper layer as the medium to communicate. Data link layer works between two hosts which are directly connected in some sense. This direct connection could be point to point or broadcast, Systems on broadcast network are said to be on same link. The work of data link layer tends to get more complex when it is dealing with multiple hosts on single collision domain. Data link layer is responsible for converting data stream to signals bit by bit and to send that over the underlying hardware. At the receiving end, Data link layer picks up data from hardware which are in the form of electrical signals, assembles them in a recognizable frame format, and hands over to upper layer. Data link layer has two sub-layers: = Logical Link Control: It deals with protocols, flow-control, and error control. = Media Access Control: It deals with actual control of media. 2.1.1 Functionality of Data-link Layer Data link layer does many tasks on behalf of upper layer. These are: = Framing - Data-link layer takes packets from Network Layer and encapsulates them into Frames. Then, it sends each frame bit-by-bit on the hardware. At receiver end, data link layer picks up signals from hardware and assembles them into frames. = Addressing - Data-link layer provides layer-2 hardware addressing mechanism. Hardware address is assumed to be unique on the link. It is encoded into hardware at the time of manufacturing. = Synchronization - When data frames are sent on the link, both machines must be synchronized in order to transfer to take place. 432.2 Error Control - Sometimes signals may have encountered problem in transition and the bits are flipped. These errors are detected and attempted to recover actual data bits, It also provides error reporting mechanism to the sender. Flow Control - Stations on same link may have different speed or capacity. Data-link layer ensures flow control that enables both machine to exchange data on same speed. Multi-Access - When host on the shared link tries to transfer the data, it has a high probability of collision. Data-link layer provides mechanism such as CSMA/CD to equip capability of accessing a shared media among multiple Systems. Error Detection and Error Correction There are many reasons such as noise, cross-talk etc., which may help data to get corrupted during transmission. The upper layers work on some generalized view of network architecture and are not aware of actual hardware data processing. Hence, the upper layers expect error-free transmission between the systems. Most of the applications would not function expectedly if they receive erroneous data. Applications such as voice and video may not be that affected and with some errors they may still function well. Data-link layer uses some error control mechanism to ensure that frames (data bit streams) are transmitted with certain level of accuracy. But to understand how errors is controlled, it is essential to know what types of errors may occur. Types of Errors There may be three types of errors: Single bit error Sent => Received BOBBOORE 1[o[1]2 [0 BH 22) Ina frame, there is only one bit, anywhere though, which is corrupt. Multiple bits error Sent > Received BOBBOOERE 101 Ryo BR 2[2)Frame is received with more than one bits in corrupted state. Burst error Sent = Received 1Jo[2[2[ofo]3] 1 [o[2[1]2] Frame contains more than consecutive bits corrupted. Error control mechanism may involve two possible ways: o Error detection o Error correction 2.2.1 Error Detection Errors in the received frames are detected by means of Parity Check and Cyclic Redundancy Check (CRC). In both cases, few extra bits are sent along with actual data to confirm that bits received at other end are same as they were sent. If the counter- check at receiver end fails, the bits are considered corrupted. Parity Check One extra bit is sent along with the original bits to make number of Is either even in case of even parity, or odd in case of odd parity. The sender while creating a frame counts the number of Is in it. For example, if even parity is used and number of Is is even then one bit with value 0 is added. This way number of Is remains even. If the number of 1s is odd, to make it even a bit with value | is added. Data Bits = Even Pari [ofoj1]ofoj1] FICOFIOIIEN The receiver simply counts the number of Is in a frame. If the count of 1s is even and even parity is used, the frame is considered to be not-corrupted and is accepted. If the count of Is is odd and odd parity is used, the frame is still not corrupted. Ifa single bit flips in transit, the receiver can detect it by counting the number of Is. But when more than one bits are erroneous, then it is very hard for the receiver to detect the error. Cyclic Redundancy Check (CRC) CRC is a different approach to detect if the received frame contains valid data. This technique involves binary division of the data bits being sent. The divisor is generated using polynomials. The sender performs a division operation on the bits being sent and calculates the remainder. Before 45sending the actual bits, the sender adds the remainder at the end of the actual bits. Actual data bits plus the remainder is called a codeword. The sender transmits data bits as codewords. Sender Receiver a [ows - ii S ill 101} 11002. 101] 1100110_ 20a} tL ae Data Bits 110) 101 111 At the other end, the receiver performs division operation on codewords using the same CRC divisor. If the remainder contains all zeros the data bits are accepted, otherwise it is considered as there is some data corruption occurred in transit. 2.2.2 Error Correction In the digital world, error correction can be done in two ways: Backward Error Correction When the receiver detects an error in the data received, it requests back the sender to retransmit the data unit. Forward Error Correction When the receiver detects some error in the data received, it executes error- correcting code, which helps it to auto-recover and to correct some kinds of errors. The first one, Backward Error Correction, is simple and can only be efficiently used where retransmitting is not expensive. For example, fiber optics. But in case of 46wireless transmission retransmitting may cost too much. In the latter case, Forward Error Correction is used. To correct the error in data frame, the receiver must know exactly which bit in the frame is corrupted. To locate the bit in error, redundant bits are used as parity bits for error detection. For example, we take ASCII words (7 bits data), then there could be 8 kind of information we need: first seven bits to tell us which bit is in error and one more bit to tell that there is no error. For m data bits, r redundant bits are used. r bits can provide 2r combinations of information. In m+r bit codeword, there is possibility that the r bits themselves may get corrupted. So the number of r bits used must inform about m+r bit locations plus no- error information, ie. m+r+1. Elementary Data Link Protocols Data-link layer is responsible for implementation of point-to-point flow and error control mechanism, Flow Control When a data frame (Layer-2 data) is sent from one host to another over a single medium, it is required that the sender and receiver should work at the same speed. That is, sender sends at a speed on which the receiver can process and accept the data. What if the speed (hardware/software) of the sender or receiver differs? If sender is sending too fast the receiver may be overloaded, (swamped) and data may be lost. Two types of mechanisms can be deployed to control the flow: Stop and Wait This flow control mechanism forces the sender after transmitting a data frame to stop and wait until the acknowledgement of the data-frame sent is received. 47Sender Receiver SI ig Window In this flow control mechanism, both sender and receiver agree on the number of data-frames after which the acknowledgement should be sent. As we learnt, stop and wait flow control mechanism wastes resources, this protocol tries to make use of underlying resources as much as possible. Error Control When data-frame is transmitted, there is a probability that data-frame may be lost in the transit or it is received corrupted. In both cases, the receiver does not receive the correct data-frame and sender does not know anything about any loss. In such case, both sender and receiver are equipped with some protocols which helps them to detect transit errors such as loss of data-frame. Hence, either the sender retransmits the data-frame or the receiver may request to resend the previous data-frame. Requirements for error control mechanism: « Error detection: The sender and receiver, either both or any, must ascertain that there is some error in the transit. = Positive ACK: When the receiver receives a correct frame, it should acknowledge it. = Negative ACK: When the receiver receives a damaged frame or a duplicate frame, it sends a NACK back to the sender and the sender must retransmit the correct frame. 48= Retransmission: The sender maintains a clock and sets a timeout period. If an acknowledgement of a data-frame previously transmitted does not arrive before the timeout, the sender retransmits the frame, thinking that the frame or its acknowledgement is lost in transit. There are three types of techniques available which Data-link layer may deploy to control the errors by Automatic Repeat Requests (ARQ): Sender Receiver Time-Out Time-Out Time-Out The following transition may occur in Stop-and-Wait ARQ: The sender maintains a timeout counter. When a frame is sent, the sender starts the timeout counter. If acknowledgement of frame comes in time, the sender transmits the next frame in queue. + If acknowledgement does not come in time, the sender assumes that either the frame or its acknowledgement is lost in transit. Sender retransmits the frame and starts the timeout counter. 4 Ifa negative acknowledgement is received, the sender retransmits the frame. oe * 49Go-Back-N ARQ. Stop and wait ARQ mechanism does not utilize the resources at their best. When the acknowledgement is received, the sender sits idle and does nothing. In Go-Back-N ARQ method, both sender and receiver maintain a window. The sending-window size enables the sender to send multiple frames without receiving the acknowledgement of the previous ones. The receiving-window enables the receiver to receive multiple frames and acknowledge them. The receiver keeps track of incoming frame’s sequence number. When the sender sends all the frames in window, it checks up to what sequence number it has received positive acknowledgement. If all frames are positively acknowledged, the sender sends next set of frames. If sender finds that it has received NACK or has not receive any ACK for a particular frame, it retransmits all the frames after which it does not receive any positive ACK. Selective Repeat ARO Sender Receiver Set Timer for 0 Set Timer for 1 {/ a Set Timer for 2 Close Timer for 0 Send 3| Close Timer for 1 Send 4} pee Time-outfor2 > sendtrame 2 | [£806 gs ean ‘ s y In Go-back-N ARQ, it is assumed that the receiver does not have any buffer space for its window size and has to process each frame as it comes. This enforces the sender to retransmit all the frames which are not acknowledged. 50In Selective-Repeat ARQ, the receiver while keeping track of sequence numbers, buffers the frames in memory and sends NACK for only frame which is missing or damaged. The sender in this case, sends only packet for which NACK is received. 2.4 Medium Access Layer The medium access control or media access control (MAC) layer is the lower sublayer of the data link layer (layer 2) of the seven-layer OSI model. The MAC sublayer provides addressing and channel access control mechanisms that make it possible for several terminals or network nodes to communicate within a multiple access network that incorporates a shared medium, e.g. an Ethernet network. The hardware that implements the MAC is referred to as a media access controller. The MAC sublayer acts as an interface between the logical link control (LLC) sublayer and the network's physical layer. The MAC layer emulates a full-duplex logical communication channel in a multi-point network. This channel may provide unicast, multicast or broadcast communication service. A MAC layer is not required in full-duplex point-to-point communication, but address fields are included in some point-to-point protocols for compatibility reasons. The LLC layer is standardized by the IEEE as the 802.2 since the beginning 1980 Its purpose is to allow level 3 network protocols (for eg IP) to be based on a single layer (the LLC layer) regardless underlying protocol used, including WiFi, Ethernet or Token Ring, for example, All WiFi data packets so carry a pack LLC, which contains itself packets from the upper network layers. The header of a packet LLC indicates the type of layer 3 protocol in it: most of the time, it is IP protocol, but it could be another protocol, such as IPX (Internet Packet Exchange) for example. Thanks to the LLC layer, it is possible to have at the same time, on the same network, multiple Layer 3 protocols. In LAN nodes uses the same communication channel for transmission. The MAC sub-layer has two primary responsibilities: Data encapsulation, including frame assembly before transmission, and frame parsing/error detection during and after reception. Media access control, including initiation of frame transmission and recovery from transmission failure. st2.4.1 Functions performed in the MAC sublayer According to IEEE Std 802-2001 section 6.2.3 "MAC sublayer", the primary functions performed by the MAC layer are:!") + Frame delimiting and recognition + Addressing of destination stations (both as individual stations and as groups of stations) + Conveyance of source-station addressing information + Transparent data transfer of LLC PDUs, or of equivalent information in the Ethernet sublayer + Protection against errors, generally by means of generating and checking frame check sequences + Control of access to the physical transmission medium In the case of Ethernet, according to 802.3-2002 section 4.1.4, the functions required of a MAC are:"! + receive/transmit normal frames + half-duplex retransmission and backoff functions + append/check FCS (frame check sequence) + interframe gap enforcement + discard malformed frames + prepend(tx)/remove(rx) preamble, SFD (start frame delimiter), and padding + half-duplex compatibility: append(tx)/remove(rx) MAC address 2.4.2 Addressing mechanism. The local network addresses used in IEEE 802 networks and FDDI networks are called media access control addresses; they are based on the addressing scheme that was used in early Ethernet implementations. A MAC address is intended as a unique serial number. MAC addresses are typically assigned to network interface hardware at the time of manufacture. The most significant part of the address identifies the manufacturer, who assigns the remainder of the address, thus provide a potentially unique address. This makes it possible for frames to be delivered on a network link that interconnects hosts by some combination of repeaters, hubs, bridges and switches, but not by network layer routers. Thus, for example, when an IP packet reaches its destination (sub)network, the destination IP address (a layer 3 or network layer concept) is resolved with the Address Resolution Protocolfor IPv4, or by Neighbor Discovery Protocol (IPV6) into the MAC address (a layer 2 concept) of the destination host. 52Examples of physical networks are Ethemet networks and Wi-Fi networks, both of which are IEEE 802 networks and use IEEE 802 48-bit MAC addresses. 2.5 Channel Allocation Problem Channel allocation deals with the allocation of channels to cells in a cellular network. Once the channels are allocated, cells may then allow users within the cell to communicate via the available channels. Channels in a wireless communication system typically consist of timeslots, frequency bands and/or CDMA pseudo noise sequences, but in an abstract sense, they can represent any generic transmission resource. There are three major categories for assigning these channels to cells (or base-stations). They are + Fixed Channel Allocation, + Dynamic Channel Allocation and « Hybrid Channel Allocation which is a combination of the first two methods. 2.5.1 Fixed Channel Allocation Fixed Channel Allocation (FCA) systems allocate specific channels to specific cells. This allocation is static and can not be changed. For efficient operation, FCA systems typically vetaneeillocate channels in a manner that maximizes frequency jeuse Distance. Thus, in a FCA system, the distance between cells using the same channel is the minimum reuse distance for that system. The problem with FCA systems is quite simple and occurs whenever the offered traffic to a network of base stations is not uniform. Consider a case in which two adjacent cells are allocated NV channels each. There clearly can be situations in which one cell has a need for N+kchannels while the adjacent cell only requires N-mchannels (for positive integers k and m). In such a case, k users in the first cell would be blocked from making 53calls while m channels in the second cell would go unused. Clearly in this situation of non-uniform spatial offered traffic, the available channels are not being used efficiently. FCA has been implemented on a widespread level to date. 2.5.2 Dynamic Channel Allocation Dynamic Channel Allocation (DCA) attempts to alleviate the problem mentioned for FCA systems when offered traffic is non-uniform. In DCA systems, no set relationship exists between channels and cells. Instead, channels are part of a pool of resources. Whenever a channel is needed by a cell, the channel is allocated under the constraint that frequency reuse requirements cannot be violated. There are two problems that typically occur with DCA based systems. + First, DCA methods typically have a degree of randomness associated with them and this leads to the fact that frequency reuse is often not maximized unlike the case for FCA systems in which cells using the same channel are separated by the minimum reuse distance. + Secondly, DCA methods often involve complex algorithms for deciding which available channel is most efficient. These algorithms can be very computationally intensive and may require large computing resources in order to be real-time. 2.5.3 Hybrid Channel Allocation Schemes The third category of channel allocation methods includes all systems that are hybrids of fixed and dynamic channel allocation systems. Several methods have been presented that fall within this category and in addition, a great deal of comparison has been made with corresponding simulations and analyses. The developed hybrid methods are, Channel Borrowing is one of the most straightforward hybrid allocation schemes. Here, channels are assigned to cells just as in fixed allocation schemes. If a cell needs a channel in excess of the channels previously assigned to it, that cell may borrow a channel from one of its neighbouring cells given that a channel is available and use of this channel won't violate frequency reuse requirements. Note that since every channel has a predetermined relationship with a specific cell, channel borrowing (without the extensions mentioned below) is often categorized as a subclass of fixed allocation schemes. The major problem with channel borrowing is that when a cell borrows a channel from a neighboring cell, other nearby cells are prohibited from using the borrowed channel because of co-channel interference. This can lead to increased call blocking over time. To reduce this call blocking penalty, algorithms are necessary to ensure that the channels are borrowed from the most available neighboring cells; i.e., the neighboring cells with the most unassigned channels. 54Two extensions of the channel borrowing approach are Borrowing with Channel Ordering (BCO) and Borrowing with Directional Channel Locking (BDCL). + Borrowing with Channel Locking was designed as an improvement over the simpler Channel Borrowing approach as described above [Elnoubi]. BCO systems have two distinctive characteristics [Elnoubi]: 1. The ratio of fixed to dynamic channels varies with traffic load. 2. Nominal channels are ordered such that the first nominal channel of a cell has the highest priority of being applied to a call within the cell. The last nominal channel is most likely to be borrowed by neighboring channels. Once a channel is borrowed, that channel is locked in the co-channel cells within the reuse distance of the cell in question. To be "locked" means that a channel can not be used or borrowed. Zhang and Yum [Zhang] presented the BDCL scheme as an improvement over the BCO method. From a frequency reuse standpoint, in a BCO system, a channel may be borrowed only if it is free in the neighboring cochannel cells. This criteria is often too strict. In Borrowing with Directional Channel Locking, borrowed channels are only locked in nearby cells that are affected by the borrowing. This differs from the BCO scheme in which a borrowed channel is locked in every cell within the reuse distance. The benefit of BDCL is that more channels are available in the presence of borrowing and subsequent call blocking is reduced. A disadvantage of BDCL is that the statement "borrowed channels are only locked in nearby cells that are affected by the borrowing” requires a clear understanding of the term “affected.” This may require microscopic analysis of the area in which the cellular system will be located. Ideally, a system can be general enough that detailed analysis of specific propagation measurements is not necessary for implementation. 2.6Multiple Access Protocols. Protocols are used by Medium Access Layer: 2.6.1 ALOHA ALOHA is a system for coordinating and arbitrating access toa shared communication channel. It was developed in the 1970s at the University of Hawaii. The original system used terrestrial radio broadcasting, but the system has been implemented in satellite communication systems. A shared communication system like ALOHA requires a method of handling collisions that occur when two or more systems attempt to transmit on the channel at the same time. 55.In the ALOHA system, a node transmits whenever data is available to send. If another node transmits at the same time, a collision occurs, and the frames that were transmitted are lost. However, a node can listen to broadcasts on the medium, even its own, and determine whether the frames were transmitted. 2.6.2. Carrier Sensed Multiple Access (CSMA) CSMA is a network access method used on shared network topologies such as Ethernet to control access to the network. Devices attached to the network cable listen (carrier sense) before transmitting. If the channel is in use, devices wait before transmitting. MA (Multiple Access) indicates that many devices can connect to and share the same network. All devices have equal access to use the network when it is clear. Even though devices attempt to sense whether the network is in use, there is a good chance that two stations will attempt to access it at the same time. On large networks, the transmission time between one end of the cable and another is enough that one station may access the cable even though another has already just accessed it. There are two methods for avoiding these so-called collisions, listed here : 2.6.3 CSMA/CD (Carrier Sense Multiple Access/Collision Detection) CD (collision detection) defines what happenswhen two devices sense a clear channel, then attempt totransmit at the same time. A collision occurs, and bothdevices stop transmission, wait for a random amount oftime, and then retransmit. This is the technique used to access the 802.3 Ethernet network channel. This method handles collisions as they occur, but if the bus is constantly busy, collisions can occur so often that performance drops drastically. It is- estimated that network traffic must be less than 40 percent of the bus capacity for the network to operate efficiently. If distances are long, time lags occur that may result in inappropriate carrier sensing, and hence collisions. CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) : In CA collision avoidance), collisions are avoided because each node signals its intent to transmit before actually doing so. This method is not popular because it requires excessive overhead that reduces performance. Ethernet : IEEE 802.3 Local Area Network (LAN) Protocols : Ethemet protocols refer to the family of local-area network (LAN)covered by the IEEE 802.3. In the Ethernet standard, there are twomodes of operation: half-duplex and full-duplex modes. In the halfduplex mode, data are transmitted using the popular Carrier- SenseMultiple Access/Collision Detection (CSMA/CD) protocol on a shared medium. 56The main disadvantages of the half-duplex are the efficiency and distance limitation, in which the link distance is limited by the minimum MAC frame size. This restriction reduces the efficiency drastically for high-rate transmission. Therefore, the carrier extension technique is used to ensure the minimum frame size of 512 bytes in Gigabit Ethernet to achieve a reasonable link distance. Four data rates are currently defined for operation over optical fiber and twisted-pair cables : 10 Mbps - 10Base-T Ethernet (IEEE 802.3) 100 Mbps - Fast Ethernet (IEEE 802.3u) 1000 Mbps - Gigabit Ethemet (IEEE 802.32) 10-Gigabit - 10 Gbps Ethernet (IEEE 802.3ae). The Ethernet System consists of three basic elements : (1) The physical medium used to carry Ethernet signals between computers, (2) a set of medium access control rules embedded in each Ethernet interface that allow multiple computers to fairly arbitrate access to the shared Ethernet channel, and (3) an Ethernet frame that consists of a standardized set of bits used to carry data over the system. As with all IEEE 802 protocols, the ISO data link layer is divided into two IEEE 802 sub-layers, the Media Access Control (MAC) sub-layer and the MAC-client sub-layer. The IEEE 802.3 physical layer corresponds to the ISO physical layer. Each Ethernet-equipped computer operates independently of all other stations on the network: there is no central controller. All stations attached to an Ethernet are connected to a shared signaling system, also called the medium. To send data a station first listens to the channel, and when the channel is idle the station transmits its data in the form of an Ethernet frame, or packet. After each frame transmission, all stations on the network must contend equally for the next frame transmission opportunity. Access to the shared channel is determined by the medium access control (MAC) mechanism embedded in the Ethernet interface located in each station. The medium access control mechanism is based on a system called Carrier Sense Multiple Access with Collision Detection (CSMA/CD). As each Ethernet frame is sent onto the shared signal channel, all Ethernet interfaces look at the destination address. If the destination address of the frame matches with the interface address, the frame will be read entirely and be delivered to the networking software running on that computer. All other network interfaces will stop reading the frame when they discover that the destination address does not match their own address. 572.6.4 IEEE 802.4 Token Bus In token bus network station must have possession of a token before it can transmit on the network. The IEEE 802.4 Committee has defined token bus standards as broadband networks, as opposed to Ethernet's baseband transmission technique. The topology of the network can include groups of workstations connected by long trunk cables. These workstations branch from hubs in a star configuration, so the network has both a bus and star topology. Token bus topology is well suited to groups of users that are separated by some distance. IEEE 802.4 token bus networks are constructed with 75-ohm coaxial cable using a bus topology. The broadband characteristics of the 802.4 standard support transmission over several different channels simultaneously. The token and frames of data are passed from one station to another following the numeric sequence of the station addresses. Thus, the token follows a logical ring rather than a physical ring. The last station in numeric order passes the token back to the first station. The token does not follow the physical ordering of workstation attachment to the cable. Station 1 might be at one end of the cable and station 2 might be at the other, with station 3 in the middle. While token bus is-used in some manufacturing environments, Ethernet and token ring standards have become more prominent in the office environment. 2.6.5 IEEE 802.5 Token Ring Token ring is the IEEE 802.5 standard for a token-passing ring network with a star-configured physical topology. Internally, signals travel around the network from one station to the next in a ring. Physically, each station connects to a central hub called a MAU (multistation access unit). The MAU contains a "collapsed ring," but the physical configuration is a star topology. When a station is attached, the ring is extended out to the station and then back to the MAU . If a station goes offline, the ring is reestablished with a bypass at the station connector. Token ring was popular for an extended period in the late 1980s and 1990s, especially in IBM legacy system environments. IBM developed the technology and provided extensive support for connections to SNA systems. More recently, Ethernet, Fast Ethernet, and Gigabit Ethernet technologies have pushed token ring and other LAN technologies to the sidelines. 2.7 Network Layer Layer-3 in the OSI model is called Network layer. Network layer manages options pertaining to host and network addressing, managing sub-networks, and internetworking. 58Network layer takes the responsibility for routing packets from source to destination within or outside a subnet. Two different subnet may have different addressing schemes or non-compatible addressing types. Same with protocols, two different subnet may be operating on different protocols which are not compatible with each other. Network layer has the responsibility to route the packets from source to destination, mapping different addressing schemes and protocols. Layer-3 Functionalities Devices which work on Network Layer mainly focus on routing. Routing may include various tasks aimed to achieve a single goal. These can be: = Addressing devices and networks. * Populating routing tables or static routes. "= Queuing incoming and outgoing data and then forwarding them according to quality of service constraints set for those packets. = Internetworking between two different subnets. = Delivering packets to destination with best efforts. = Provides connection oriented and connection less mechanism. Network Layer Features With its standard functionalities, Layer 3 can provide various features as: © Quality of service management o Load balancing and link management © Security o Interrelation of different protocols and subnets with different schema. o Different logical network design over the physical network design. © L3 VPN and tunnels can be used to provide end to end dedicated connectivity. Internet protocol is widely respected and deployed Network Layer protocol which helps to communicate end to end devices over the internet. It comes in two flavors. IPv4 which has ruled the world for decades but now is running out 59of address space. IPV6 is created to replace IPv4 and hopefully mitigates limitations of IPv4 too. 2.8 Design Issues The network layer has been designed with the following goals: 1. The services provided should be independent of the underlying technology. Users of the service need not be aware of the physical implementation of the network - for all they know, they're messages could be transported via carrier pigeon! This design goal has great importance when we consider the great variety of networks in operation. In the area of Public networks, networks in underdeveloped countries are nowhere near the technological prowess of those in the countries like the US or Ireland. The design of the layer must not disable us from connecting to networks of different technologies. . The transport layer (that is the host computer) should be shielded from the number, type and different topologies of the subnets he uses. That is, all the transport layer want is a communication link, it need not know how that link is made. Finally, there is a need for some uniform addressing scheme for network addresses. v oe With these goals in mind, two different types of service emerged: Connection oriented and connectionless. A connection-oriented service is one in which the user is given a "reliable" end to end connection. To communicate, the user requests a connection, then uses the connection to his hearts content, and then closes the connection. A telephone call is the classic example of a connection oriented service. In a connection-less service, the user simply bundles his information together, puts an address on it, and then sends it off, in the hope that it will reach its destination. There is no guarantee that the bundle will arrive. So - a connection less service is one reminiscent of the postal system. A letter is sent, that is, put in the post box. It is then in the "postal network" where it gets bounced around and hopefully will leave the network in the correct place, that is, in the addressee's letter box. With a connection oriented service, the user must pay for the length (ie the duration) of his connection. Usually this will involve a fixed start up fee. Now, if the user intends to send a constant stream of data down the line, this is great - he is given a reliable service for as long as he wants. However, say the user wished to send only a packet or two of data - now the cost of setting up the connection greatly overpowers the cost of sending that one packet. Consider also the case where the user wishes to send a packet 60once every 3 minutes. In a connection-oriented service, the line will thus be idle for the majority of the time, thus wasting bandwidth. So, connection-oriented services seem to be useful only when the user wishes to send a constant stream of data. One would therefore think that the reliable nature of the connection oriented service would prompt people to choose it over the connectionless service - this is in fact not the case. One can never ensure that the network is 100% reliable, in fact for many applications we must assume that the network is not reliable at all. With this in mind, many applications perform their own error detection, flow and congestion control at a higher level in the protocol stack, that is, on their own machine, in the transport layer. The network layer should provide a raw means of sending packets from a to b, and that is all. Proponents of this argument are quick to point out that the standard of our networks has increased greatly in the past years, that packets of information rarely ever do get lost, so much of the correction facilities in the network layer are redundant and serve only to complicate the layer and slow down transfer. Its interesting to note here that it is easy to provide a connection oriented service over an inherently connectionless service, so in fact defining the service of the network layer as connectionless is the general solution. However, at the time of defining the network layer, the controversy between the two camps was (and still is) unresolved, and so instead of deciding on one service, the ISO allowed both. Circuit Switching: A dedicated path between the source node and the destination node is set up for the duration of communication session to transfer data. That path is a connected sequence of links between network nodes. On each physical link, a logical channel is dedicated to the connection. Communication via circuit switching involves three phases, 1, Circuit Establishment: Before any signals can be transmitted, an end-to-end (station-to-station) circuit must be established . 2. Data Transfer: The data may be analog or digital, depending on the nature of the network 3. Circuit Disconnect:After some period of data transfer, the connection is terminated, usually by the action of one of the two stations 61Acknowledgement signal Examples: PSTN, PBX etc. circuit switching telecommunication networks was originally designed to handle voice traffic, and the majority of the traffic on these networks continues to be voice. A key characteristics of the circuit switching is that resources within the network are dedicated to a particular call. For voice communication the resulting circuit will enjoy the high percentage of utilization because most of the time one party or the other is talking. However, as the circuit-switching network began to be used increasingly for data connections, two shortcomings became apparent: 1. Ina typical userlhost data connection (e.g., personal computer user logged on to a database server), much of the time the line is idle. Thus, with data connections, a circuit-switching approach is inefficient. 2. In a circuit-switching network, the connection provides for transmission at constant data rate. Thus, each of the two devices that are connected must transmit and receive at the same data rate as the other; this limits the utility of the network in interconnecting a variety of host computers and terminals. Packet Switching: Messages are divided into subsets of equal length called packets. In packet switching approach, data are transmitted in short packets (few Kbytes). A long message is broken up into a series of packets as shown in Fig Every packet contains some control information in its header, which is required for routing and other purposes. 62‘ *s, . 1H | Packet 1] [H] Packet 2] «++ [H] Packet Nj A message is divided into a number of equal length short packets Main difference between Packet switching and Circuit Switching is that the communication lines are not dedicated to passing messages from the source to the destination. In Packet Switching, different messages (and even different packets) can pass through different routes, and when there is a "dead time" in the communication between the source and the destination, the lines can be used by other sources. There are two basic approaches commonly used to packet Switching: virtual circuit packet switching and datagram packet switching. In virtual-circuit packet switching a virtual circuit is made before actual data is transmitted, but it is different from circuit switching in a sense that in circuit switching the call accept signal comes only from the final destination to the source while in case of virtual-packet switching this call accept signal is transmitted between each adjacent intermediate node as shown in Fig. Other features of virtual circuit packet switching are discussed in the following subsection. Virtual Circuit: An initial setup phase is used to set up a route between the intermediate nodes for all the packets passed during the session between the two end nodes. In each intermediate node, an entry is registered in a table to indicate the route for the connection that has been set up. Thus, packets passed through this route, can have short headers, containing only a virtual circuit identifier (VCI), and not their destination. Each intermediate node passes the packets according to the information that was stored in it, in the setup phase. In this way, packets arrive at the destination in the correct sequence, and it is guaranteed that essentially there will not be errors. This approach is slower than Circuit Switching, since different virtual circuits may compete over the same resources, and an initial setup phase is needed to initiate the circuit. As in Circuit Switching, if an intermediate node fails, all virtual circuits that pass through it are lost. The most common forms of Virtual Circuit networks are X.25 and Frame Relay, which are commonly used for public data networks (PDN). 63Node 2 Node 3 Node 4 fees] 5, Data flow begins Krall connected itiate call Virtual Circuit Datagram: This approach uses a different, more dynamic scheme, to determine the route through the network links. Each packet is treated as an independent entity, and its header contains full information about the destination of the packet. The intermediate nodes examine the header of the packet, and decide to which node to send the packet so that it will reach its destination. 64in this method, the packets don't follow a pre-established route, and the intermediate nodes (the routers) don't have pre-defined knowledge of the routes that the packets should be passed through. Packets can follow different routes to the destination, and delivery is not guaranteed . Due to the nature of this method, the packets can reach the destination in a different order than they were sent, thus they must be sorted at the destination to form the original message. This approach is time consuming since every router has to decide where to send each packet. The main implementation of Datagram Switching network is the Internet, which uses the IP network protocol. Packets Node 1 Node 2 Node 3 Node 4 Datagram Packet Switching Datagram Packet Si g Vs Virtual-circuit Packet Switching: sno |Datagram Packet Switching Virtual-circuit Packet Switching Two packets of the same user pair can|All packets of the same virtual circui 1 |travel along different routes travel along the same path. ‘The packets can arrive out od 2 |sequence. ‘Packet sequencing is guaranteed. 3 |Packets contain full Src, Dst addresses /Packets contain short VC Id. (VC). Each host occupies routine tableEach VC occupies routing table 4 entries. entries. Requires VC setup. First packet has 5 [Requires no connection setup. large delay 6 _|Also called Connection less ‘Also called connection oriented. Eg. Internet which uses IP Network| 7 |Examples: X.25 and Frame Relay protocol 652.9 Routing Algorithms 2.9.1 Router A Router is a computer, just like any other computer including a PC. Routers have many of the same hardware and software components that are found in other computers including: + CPU + RAM + ROM * Operating System 1041 Intagrted Services Router der Router is the basic backbone for the Internet. The main function of the router is to connect two or more than two network and forwards the packet from one network to another. A router connects multiple networks. This means that it has multiple interfaces that each belong to a different IP network. When a router receives an IP packet on one interface, it determines which interface to use to forward the packet onto its destination. The interface that the router uses to forward the packet may be the network of the final destination of the packet (the network with the destination IP address of this packet), or it may be a network connected to another router that is used to reach the destination network. Network 1 Router 1 Network 2 a) oe) 2 Router connects two networkInternet Architecture A router uses IP to forward packets from the source network to the destination network. The packets must include an identifier for both the source and destination networks. A router uses the IP address of the destination network to deliver a packet to the correct network. When the packet arrives at a router connected to the destination network, the router uses the IP address to locate the specific computer on the network. 2.9.2 Routing and Routing Protocols: The primary responsibility of a router is to direct packets destined for local and remote networks by: + Determining the best path to send packets + Forwarding packets toward their destination The router uses its routing table to determine the best path to forward the packet. When the router receives a packet, it examines its destination IP address and searches for the best match with a network address in the router's routing table. The routing table also includes the interface to be used to forward the packet. Once a match is found, the router encapsulates the IP packet into the data link frame of the outgoing or exit interface, and the packet is then forwarded toward its destination. 672.9.2 Static Routes: Static routes are configured manually, network administrators must add and delete static routes to reflect any network topology changes. In a large network, the manual maintenance of routing tables could require a lot of administrative time. On small networks with few possible changes, static routes require very little maintenance. Static routing is not as scalable as dynamic routing because of the extra administrative requirements. Even in large networks, static routes that are intended to accomplish a specific purpose are often configured in conjunction with a dynamic routing protocol. When to use static Routing: © A network consists of only a few routers. Using a dynamic routing protocol in such a case does not present any substantial benefit. On the contrary, dynamic routing may add more administrative overhead. A network is connected to the Internet only through a single ISP. There is no need to use a dynamic routing protocol across this link because the ISP represents the only exit point to the Internet. «A large network is configured in a hub-and-spoke topology. A hub-and-s topology consists of a central location (the hub) and multiple branch locations (spokes), with each spoke having only one connection to the hub. Using dynamic routing would be unnecessary because each branch has only one path to a given destination-through the central location. 2.9.3 Connected Routes: Those network that are directly connected to the Router are called connected routes and are not needed to configure on the router for routing. They are automatically routed by the Router. 2.9.4 Dynamic Routes: Dynamic routing protocol uses a route that a routing protocol adjusts automatically for topology or traffic changes. 68Imagine maintaining static routing configurations for THIS network! 2.9.5 Routing Protocol: A routing protocol is the communication used between routers. A routing protocol allows routers to share information about networks and their proximity to each other. Routers use this information to build and maintain routing tables. Autonomous System: An AS is a collection of networks under a common administration that share a common routing strategy. To the outside world, an AS is viewed as a single entity. The ‘AS may be run by one or more operators while it presents a consistent view of routing to the external world. ‘The American Registry of Internet Numbers (ARIN), a service provider, or an administrator assigns a 16-bit identification number to each AS. Dynamic Routing Protocol: 1, Interior Gateway protocol (IGP) 1). Distance Vector Protocol II). Link'State Protocol 2. Exterior Gateway Protocol (EGP) 69Interior gateway protocol (IGP): Within one Autonomous System. Exterior Routing Protocol(EGP):Between the Autonomous System. Example BGP (Boarder gateway protocol) Metric: There are cases when a routing protocol learns of more than one route to the same destination. To select the best path, the routing protocol must be able to evaluate and differentiate between the available paths. For this purpose a metric is used. A metric is a value used by routing protocols to assign costs to reach remote networks. The metric is used to determine which path is most preferable when there are multiple paths to the same remote network. Each routing protocol uses its own metric. For example, RIP uses hop count, EIGRP uses a combination of bandwidth and delay, and Cisco's implementation of OSPF uses bandwidth. 2.9.6 Distance Vector Routing Algorithm: As the name implies, distance vector means that routes are advertised as vectors of distance and direction. Distance is defined in terms of a metric such as hop count and direction is simply the next-hop router or exit interface. A router using a distance vector routing protocol does not have the knowledge of the entire path to a destination network. Instead the router knows only: The direction or interface in which packets should be forwarded and The distance or how far it is to the destination network. To show you more exactly what a distance vector protocol does, Figure shows a view of what a router learns with a distance vector routing protocol. The figure shows an internetwork in which R1 learns about three routes to reach subnet X: © The four-hop route through R2 © The three-hop route through RS The two-hop route through R7 70= Routing Update RI learns about the subnet, and a metric associated with that subnet, and nothing more. R1 must then pick the best route to reach subnet X. In this case, it picks the two-hop route through R7, because that route has the lowest metric. Distance vector protocols typically use the Bellman-Ford algorithm for the best path route determination. + @= B= @- ‘-_S-e—e Pass periodic copies of a routing table to neighbor routers and accumulate distance vectors. 10100 10209 10300 10400 1Initial Update: RI + Sends an update about network 10.1.0.0 out the Serial0/0/0 interface * Sends an update about network 10.2.0.0 out the FastEthernet0/0 interface + Receives update from R2 about network 10.3.0.0 with a metric of 1 * Stores network 10,3.0.0 in the routing table with a metric of 1 Sends an update about network 10.3.0.0 out the Serial 0/0/0 interface + Sends an update about network 10.2.0.0 out the Serial 0/0/1 interface + Receives an update from R1 about network 10.1.0.0 with a metric of 1 * Stores network 10.1.0.0 in the routing table with a metric of 1 * Receives an update from R3 about network 10.4.0.0 with a metric of 1 * Stores network 10.4.0.0 in the routing table with a metric of 1 Sends an update about network 10.4.0.0 out the Serial 0/0/0 interface Sends an update about network 10.3.0.0 out the FastEthernet0/0 Receives an update from R2 about network 10.2.0.0 with a metric of 1 Stores network 10.2.0.0 in the routing table with a metric of 1 After this first round of update exchanges, each router knows about the connected networks of their directly connected neighbors. However, did you notice that R1 does not yet know about 10.4.0.0 and that R3 does not yet know about 10.1.0.0? Full nknowledge and a converged network will not take place until there is another exchange of routing information. Next Update: RI ¢ Sends an update about network 10.1.0.0 out the Serial 0/0/0 interface. © Sends an update about networks 10.2.0.0 and 10.3.0.0 out the FastEthernet0/0 interface. ¢ Receives an update from R2 about network 10.4.0.0 with a metric of 2. © Stores network 10.4.0.0 in the routing table with a metric of 2. Same update from R2 contains information about network 10.3.0.0 with a metric of 1. There is no change: therefore, the routing information remains the same. R2 © Sends an update about networks 10.3.0.0 and 10.4.0.0 out of Serial 0/0/0 interface. * Sends an update about networks 10.1.0.0 and 10.2.0.0 out of Serial 0/0/1 interface. * Receives an update from RI about network 10.1.0.0. There is no change; therefore, the routing information remains the same. © Receives an update from R3 about network 10.4.0.0. There is no change; therefore, the routing information remains the same. + Sends an update about network 10.4.0.0 out the Serial 0/0/0 interface. * Sends an update about networks 10.2.0.0 and 10.3.0.0 out the FastEthernet0/0 interface. + Receives an update from R2 about network 10.1.0.0 with a metric of 2. B* Stores network 10.1.0.0 in the routing table with a metric of 2. + Same update from R2 contains information about network 10.2.0.0 with a metric of I. There is no change; therefore, the routing information remains the same. Note: Distance vector routing protocols typically implement a technique known as split horizon. Split horizon prevents information from being sent out the same interface from which it was received. For example, R2 would not send an update out Serial 0/0/0 containing the network 10.1.0.0 because R2 learned about that network through Serial 0/0/0. 2.9.7 Link State Routing Algorithm: Also known as Shortest path Routing algorithm. Link states: Information about the state of (Router interfaces) links is known as link-states. As you can see in the figure, this information includes: * The interface's IP address and subnet mask. * The type of network, such as Ethernet (broadcast) or Serial point-to-point link. + The cost of that link. + Any neighbor routers on that link. ‘Shortest Path for host on R2 LAN to reach host on R3 LAN: R2 to RI (20) + Rt to RS (6) + RS toLAN (2) = 27 Dijkstra's Shortest Path first algorithm 74Alll routers will complete the following generic link-state routing process to reach a state of convergence: iL. Each router learns about its own links, its own directly connected networks. This is done by detecting that an interface is in the up state. . Each router is responsible for meeting its neighbors on directly connected networks. link state routers do this by exchanging Hello packets with other link- state routers on directly connected networks. . Each router builds a Link-State Packet (LSP) containing the state of each directly connected link. This is done by recording all the pertinent information about each neighbor, including neighbor ID, link type, and bandwidth. . Each router floods the LSP to all neighbors, who then store all LSPs received in a database. Neighbors then flood the LSPs to their neighbors until all routers in the area have received the LSPs. Each router stores a copy of each LSP received from its neighbors in a local database. . Each router uses the database to construct a complete map of the topology and computes the best path to each destination network. Like having a road map, the router now has a complete map of all destinations in the topology and the routes to reach them. The SPF algorithm is used to construct the map of the topology and to determine the best path to each network. Advantages of Link state Routing protocol: Build the topological map: Link-state routing protocols create a topological map, or SPF tree of the network topology. Distance vector routing protocols do not have a topological map of the network. Faster Convergence: When receiving a Link- state Packet (LSP), link-state routing protocols immediately flood the LSP out all interfaces except for the interface from which the LSP was received. This way, it achieve the faster convergence. With distance vector routing algorithm, router needs to process each routing update and update its routing table before flooding them out other interfaces. 75Event Driven Updates: ‘After the initial flooding of LSPs, link-state routing protocols only send out an LSP when there is a change in the topology. The LSP contains only the information regarding the affected link. Unlike some distance vector routing protocols, link-state routing protocols do not send periodic updates. 2.9.8 Flow based routing: A flooding algorithm is an algorithm for distributing material to every part of a connected network. The name derives from the concept of inundation by a flood. Its implemented by the ospf: Advantages of Flooding The main advantage of flooding the increased reliability provided by this routing method. Since the message will be sent at least once to every host it is almost guaranteed to reach its destination, In addition, the message will reach the host through the shortest possible path. Disadvantages of Flooding There are several disadvantages with this approach to routing. It is very wasteful in terms of the networks total bandwidth. While a message may only have one destination it has to be sent to every host. This increases the maximum load placed upon the network. Messages can also become duplicated in the network further increasing the load on the networks bandwidth as well as requiring an inerease in processing complexity to disregard duplicate messages. A variant of flooding called selective flooding partially addresses these issues by only sending packets to routers in the same ditection. 2.9.9 Spanning Tree Protocol(STP) Need for Redundant Topology: The goal of redundant topologies is to eliminate network outages caused by a single point of failure. All networks need redundancy for enhanced reliability. 76A network of roads is a global example of a redundant topology. If one road is closed for repair, there is likely an alternate route to the destination. Consider a community separated by a river from the town center. If there is only one bridge across the river, there is only one way into town. The topology has no redundancy. If the bridge is flooded or damaged by an accident, travel to the town center across the bridge is impossible. A second bridge across the river creates a redundant topology. The suburb is not cut off from the town center if one bridge is impassable. 7Issues with Redundancy: 172.17.10.27 172.17.10.21 172.17.40.22 472.17.10.23 Layer 2 loops Ethernet frames do not have a time to live (TTL) like IP packets traversing routers. As a result, if they are not terminated properly on a switched network, they continue to bounce from switch to switch endlessly or until a link is disrupted and breaks the loop. Broadcast stroms A broadcast storm occurs when there are so many broadcast frames caught in a Layer 2 loop that all available bandwidth is consumed. Consequently, no bandwidth is available bandwidth for legitimate traffic, and the network becomes unavailable for data communication. Duplicate unicast frame: Broadcast frames are not the only type of frames that are affected by loops. Unicast frames sent onto a looped network can result in duplicate frames arriving at the destination device. Spanning Tree Protocol(STP) Redundancy increases the availability of the network topology by protecting the network from a single point of failure, such as a failed network cable or switch. When 78redundancy is introduced into a Layer 2 design, loops and duplicate frames can occur Loops and duplicate frames can have severe consequences on a network. The Spanning Tree Protocol (STP) was developed to address these issues. STP ensures that there is only one logical path between all destinations on the network by intentionally blocking redundant paths that could cause a loop. A port is considered blocked when network traffic is prevented from entering or leaving that port. This does not include bridge protocol data unit (BPDU) frames that are used by STP to prevent loops. Blocking the redundant paths is critical to preventing loops on the network. The physical paths still exist to provide redundancy, but these paths are disabled to prevent the loops from occurring. If the path is ever needed to compensate for a network cable or switch failure, STP recalculates the paths and unblocks the necessary ports to allow the redundant path to become active. 2.10 Congestion Control Algorithms. Congestion is an important issue that can arise in packet switched network. Congestion is a situation in Communication Networks in which too many packets are present in a part of the subnet, performance degrades. Congestion in a network may occur when the load on the network (i.e. the number of packets sent to the network) is greater than the capacity of the network (i.e. the number of packets a network can handle.) Concept of Congestion 2.10.1 Causing of Congestion: The various causes of congestion in a subnet are: = The input traffic rate exceeds the capacity of the output lines. If suddenly, a stream of packet start arriving on three or four input lines and all need the same 79