Computer Networks Lecture Notes PDF

COMPUTER NETWORKS [R15A0513] LECTURE NOTES B.TECH III YEAR – II SEM (R15) (2019-20) DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING MALLA REDDY COLLEGE...

COMPUTER NETWORKS [R15A0513] LECTURE NOTES B.TECH III YEAR – II SEM (R15) (2019-20) DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY (Autonomous Institution – UGC, Govt. of India) Recognized under 2(f) and 12 (B) of UGC ACT 1956 (Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified) Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, India III Year B. Tech. CSE –II Sem L T/P/D C 4 1/- / - 3 (R15A0513) Computer Networks Objectives:  To introduce the fundamental types of computer networks.  To demonstrate the TCP/IP & OSI model merits & demerits.  To know the role of various protocols in Networking UNIT - I: Introduction: Network, Uses of Networks, Types of Networks, Reference Models: TCP/IP Model, The OSI Model, Comparison of the OSI and TCP/IP reference model. Architecture of Internet. Physical Layer: Guided transmission media, Wireless transmission media, Switching UNIT - II: Data Link Layer - Design issues, Error Detection & Correction, Elementary Data Link Layer Protocols, Sliding window protocols Multiple Access Protocols - ALOHA, CSMA,CSMA/CD, CSMA/CA, Collision free protocols, Ethernet- Physical Layer, Ethernet Mac Sub layer, Data link layer switching: Use of bridges, learning bridges, spanning tree bridges, repeaters, hubs, bridges, switches, routers and gateways. UNIT - III: Network Layer: Network Layer Design issues, store and forward packet switching connection less and connection oriented networks-routing algorithms-optimality principle, shortest path, flooding, Distance Vector Routing, Count to Infinity Problem, Link State Routing, Path Vector Routing, Hierarchical Routing; Congestion control algorithms, IP addresses, CIDR, Subnetting, SuperNetting, IPv4, Packet Fragmentation, IPv6 Protocol, Transition from IPv4 to IPv6, ARP, RARP. UNIT - IV: Transport Layer: Services provided to the upper layers elements of transport protocol addressing connection establishment, Connection release, Error Control & Flow Control, Crash Recovery. The Internet Transport Protocols: UDP, Introduction to TCP, The TCP Service Model, The TCP Segment Header, The Connection Establishment, The TCP Connection Release, The TCP Sliding Window, The TCP Congestion Control Algorithm. UNIT - V: Application Layer- Introduction, providing services, Applications layer paradigms: Client server model, HTTP, E-mail, WWW, TELNET, DNS; RSA algorithm, TEXT BOOKS: 1. Computer Networks - Andrew S Tanenbaum, 4th Edition, Pearson Education. 2. Data Communications and Networking - Behrouz A. Forouzan, Fifth Edition TMH, 2013. REFERENCES BOOKS: 1. An Engineering Approach to Computer Networks - S. Keshav, 2nd Edition, Pearson Education. 2. Understanding communications and Networks, 3rd Edition, W. A. Shay, Cengage Learning. 3. Computer Networking: A Top-Down Approach Featuring the Internet, James F. Kurose, K. W. Ross, 3rd Edition, Pearson Education. Outcomes:  Students should be understand and explore the basics of Computer Networks and Various Protocols.  Student will be in a position to understand the World Wide Web concepts.  Students will be in a position to administrate a network and flow of information further  Student can understand easily the concepts of network security, Mobile  INDEX TOPIC PAGE NO UNIT NO INTRODUCTION TO NETOWRKS 1 TYPES OF NETWORKS, 4 I INTRODUCTION TO PYSICAL LAYER 18 COMPARISON OF OSI AND TCP/IP 25 PROTOCOLS DATA LINK LAYER DESIGN ISSUES 35 II SLIDI NG WINDOW PROTOCOLS 41 MULTIPLE ACCESS PROTOCOLS 49 NETWORK LAYER DESIGN ISSUES 78 III CONNECTION LESS AND CONNECTION 80 ORIENTED PROTOCOLS 81 ROUTING PROTOCOLS,IP ADDRESS TRANSPORT LAYER SERVICES 101 IV PROVIDED THE INTERNET TRANSPORT 130 PROTOCOLS APPLICATION LAYER SERVICES 249 V APPLICATIONS LAYER PARADISMS 256  UNIT - I NETWORKS A network is a set of devices (often referred to as nodes) connected by communication links. A node can be a computer, printer, or any other device capable of sending and/or receiving data generated by other nodes on the network. “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. There is considerable confusion in the literature between a computer network and a distributed system. The key distinction is that in a distributed system, a collection of independent computers appears to its users as a single coherent system. Usually, it has a single model or paradigm that it presents to the users. Often a layer of software on top of the operating system, called middleware, is responsible for implementing this model. A well-known example of a distributed system is the World Wide Web. It runs on top of the Internet and presents a model in which everything looks like a document (Web page). USES OF COMPUTER NETWORKS 1. Business Applications  to distribute information throughout the company (resource sharing). sharing physical resources such as printers, and tape backup systems, is sharing information  client-server model. It is widely used and forms the basis of much network usage.  communication medium among employees.email (electronic mail), which employees generally use for a great deal of daily communication.  Telephone calls between employees may be carried by the computer network instead of by the phone company. This technology is called IP telephony or Voice over IP (VoIP) when Internet technology is used.  Desktop sharing lets remote workers see and interact with a graphical computer screen  doing business electronically, especially with customers and suppliers. This new model is called e-commerce (electronic commerce) and it has grown rapidly in recent years. 2 Home Applications  peer-to-peer communication  person-to-person communication  electronic commerce  entertainment.(game playing,) 3 Mobile Users  Text messaging or texting  Smart phones,  GPS (Global Positioning System)  m-commerce  NFC (Near Field Communication) 4 Social Issues With the good comes the bad, as this new-found freedom brings with it many unsolved social, political, and ethical issues. Social networks, message boards, content sharing sites, and a host of other applications allow people to share their views with like-minded individuals. As long as the subjects are restricted to technical topics or hobbies like gardening, not too many problems will arise. The trouble comes with topics that people actually care about, like politics, religion, or sex. Views that are publicly posted may be deeply offensive to some people. Worse yet, they may not be politically correct. Furthermore, opinions need not be limited to text; high-resolution color photographs and video clips are easily shared over computer networks. Some people take a live-and-let-live view, but others feel that posting certain material (e.g., verbal attacks on particular countries or religions, pornography, etc.) is simply unacceptable and that such content must be censored. Different countries have different and conflicting laws in this area. Thus, the debate rages. Computer networks make it very easy to communicate. They also make it easy for the people who run the network to snoop on the traffic. This sets up conflicts over issues such as employee rights versus employer rights. Many people read and write email at work. Many employers have claimed the right to read and possibly censor employee messages, including messages sent from a home computer outside working hours. Not all employees agree with this, especially the latter part. Another conflict is centered around government versus citizen’s rights. A new twist with mobile devices is location privacy. As part of the process of providing service to your mobile device the network operators learn where you are at different times of day. This allows them to track your movements. They may know which nightclub you frequent and which medical center you visit. Phishing ATTACK: Phishing is a type of social engineering attack often used to steal user data, including login credentials and credit card numbers. It occurs when an attacker, masquerading as a trusted entity, dupes a victim into opening an email, instant message, or text message. BOTNET ATTACK: Botnets can be used to perform distributed denial-of-service attack (DDoS attack), steal data, send spam, and allows the attacker to access the device and its connection. The effectiveness of a data communications system depends on four fundamental characteristics: delivery, accuracy, timeliness, and jitter. I. Delivery. The system must deliver data to the correct destination. Data must be received by the intended device or user and only by that device or user. 2 Accuracy. The system must deliver the data accurately. Data that have been altered in transmission and left uncorrected are unusable. 3. Timeliness. The system must deliver data in a timely manner. Data delivered late are useless. In the case of video and audio, timely delivery means delivering data as they are produced, in the same order that they are produced, and without significant delay. This kind of delivery is called real-time transmission. 4. Jitter. Jitter refers to the variation in the packet arrival time. It is the uneven delay in the delivery of audio or video packets. For example, let us assume that video packets are sent every 30 ms. If some of the packets arrive with 30-ms delay and others with 40-ms delay, an uneven quality in the video is the result. A data communications system has five components I. Message. The message is the information (data) to be communicated. Popular forms of information include text, numbers, pictures, audio, and video. 2 Sender. The sender is the device that sends the data message. It can be a computer, workstation, telephone handset, video camera, and so on. 3. Receiver. The receiver is the device that receives the message. It can be a computer, workstation, telephone handset, television, and so on. 4. Transmission medium. The transmission medium is the physical path by which a message travels from sender to receiver. Some examples of transmission media include twisted-pair wire, coaxial cable, fiber-optic cable, and radio waves. 5. Protocol. A protocol is a set of rules that govern data communications. It represents an agreement between the communicating devices. Without a protocol, two devices may be connected but not communicating, just as a person speaking French cannot be understood by a person who speaks only Japanese. Data Representation Text Numbers Images Audio Video Data Flow Communication between two devices can be simplex, half-duplex, or full-duplex as shown in Figure. Simplex In simplex mode, the communication is unidirectional, as on a one- way street. Only one of the two devices on a link can transmit; the other can only receive (Figure a). Keyboards and traditional monitors are examples of simplex devices. Half-Duplex In half-duplex mode, each station can both transmit and receive, but not at the same time. When one device is sending, the other can only receive, and vice versa (Figure b). Walkie-talkies and CB (citizens band) radios are both half- duplex systems. Full-Duplex In full-duplex, both stations can transmit and receive simultaneously (Figure c). One common example of full-duplex communication is the telephone network. When two people are communicating by a telephone line, both can talk and listen at the same time. The full-duplex mode is used when communication in both directions is required all the time. Network Criteria A network must be able to meet a certain number of criteria. The most important of these are performance, reliability, and security. Performance Performance can be measured in many ways, including transit time and response time. Transit time is the amount of time required for a message to travel from one device to another. Response time is the elapsed time between an inquiry and a response. The performance of a network depends on a number of factors, including the number of users, the type of transmission medium, the capabilities of the connected hardware, and the efficiency of the software. Performance is often evaluated by two networking metrics: throughput and delay. We often need more throughput and less delay. However, these two criteria are often contradictory. If we try to send more data to the network, we may increase throughput but we increase the delay because of traffic congestion in the network. Reliability: In addition to accuracy of delivery, network reliability is measured by the frequency of failure, the time it takes a link to recover from a failure, and the network's robustness in a catastrophe. Security: Network security issues include protecting data from unauthorized access, protecting data from damage and development, and implementing policies and procedures for recovery from breaches and data losses. Physical Structures Before discussing networks, we need to define some network attributes. Type of Connection A network is two or more devices connected through links. A link is a communications pathway that transfers data from one device to another. There are two possible types of connections: point-to-point and multipoint. Point-to-Point A point-to-point connection provides a dedicated link between two devices. The entire capacity of the link is reserved for transmission between those two devices. Most point-to-point connections use an actual length of wire or cable to connect the two ends, but other options, such as microwave or satellite links, are also possible When you change television channels by infrared remote control, you are establishing a point-to-point connection between the remote control and the television's control system. Multipoint A multipoint (also called multi-drop) connection is one in which more than two specific devices share a single link In a multipoint environment, the capacity of the channel is shared, either spatially or temporally. If several devices can use the link simultaneously, it is a spatially shared connection. If users must take turns, it is a timeshared connection. Physical Topology The term physical topology refers to the way in which a network is laid out physically. Two or more devices connect to a link; two or more links form a topology. The topology of a network is the geometric representation of the relationship of all the links and linking devices (usually called nodes) to one another. There are four basic topologies possible: mesh, star, bus, and ring MESH: A mesh topology is the one where every node is connected to every other node in the network. A mesh topology can be a full mesh topology or a partially connected mesh topology. In a full mesh topology, every computer in the network has a connection to each of the other computers in that network. The number of connections in this network can be calculated using the following formula (n is the number of computers in the network): n(n-1)/2 In a partially connected mesh topology, at least two of the computers in the network have connections to multiple other computers in that network. It is an inexpensive way to implement redundancy in a network. In the event that one of the primary computers or connections in the network fails, the rest of the network continues to operate normally. Advantages of a mesh topology  Can handle high amounts of traffic, because multiple devices can transmit data simultaneously.  A failure of one device does not cause a break in the network or transmission of data.  Adding additional devices does not disrupt data transmission between other devices. Disadvantages of a mesh topology  The cost to implement is higher than other network topologies, making it a less desirable option.  Building and maintaining the topology is difficult and time consuming.  The chance of redundant connections is high, which adds to the high costs and potential for reduced efficiency. STAR: A star network, star topology is one of the most common network setups. In this configuration, every node connects to a central network device, like a hub, switch, or computer. The central network device acts as a server and the peripheral devices act as clients. Depending on the type of network card used in each computer of the star topology, a coaxial cable or a RJ-45 network cable is used to connect computers together. Advantages of star topology  Centralized management of the network, through the use of the central computer, hub, or switch.  Easy to add another computer to the network.  If one computer on the network fails, the rest of the network continues to function normally.  The star topology is used in local-area networks (LANs), High-speed LANs often use a star topology with a central hub. Disadvantages of star topology  Can have a higher cost to implement, especially when using a switch or router as the central network device.  The central network device determines the performance and number of nodes the network can handle.  If the central computer, hub, or switch fails, the entire network goes down and all computers are disconnected from the network BUS: a line topology, a bus topology is a network setup in which each computer and network device are connected to a single cable or backbone. Advantages of bus topology  It works well when you have a small network.  It's the easiest network topology for connecting computers or peripherals in a linear fashion.  It requires less cable length than a star topology. Disadvantages of bus topology  It can be difficult to identify the problems if the whole network goes down.  It can be hard to troubleshoot individual device issues.  Bus topology is not great for large networks.  Terminators are required for both ends of the main cable.  Additional devices slow the network down.  If a main cable is damaged, the network fails or splits into two. RING: A ring topology is a network configuration in which device connections create a circular data path. In a ring network, packets of data travel from one device to the next until they reach their destination. Most ring topologies allow packets to travel only in one direction, called a unidirectional ring network. Others permit data to move in either direction, called bidirectional. The major disadvantage of a ring topology is that if any individual connection in the ring is broken, the entire network is affected. Ring topologies may be used in either local area networks (LANs) or wide area networks (WANs). Advantages of ring topology  All data flows in one direction, reducing the chance of packet collisions.  A network server is not needed to control network connectivity between each workstation.  Data can transfer between workstations at high speeds.  Additional workstations can be added without impacting performance of the network. Disadvantages of ring topology  All data being transferred over the network must pass through each workstation on the network, which can make it slower than a star topology.  The entire network will be impacted if one workstation shuts down.  The hardware needed to connect each workstation to the network is more expensive than Ethernet cards and hubs/switches. Hybrid Topology A network can be hybrid. For example, we can have a main star topology with each branch connecting several stations in a bus topology as shown in Figure Types of Network based on size The types of network are classified based upon the size, the area it covers and its physical architecture. The three primary network categories are LAN, WAN and MAN. Each network differs in their characteristics such as distance, transmission speed, cables and cost. Basic types LAN (Local Area Network) Group of interconnected computers within a small area. (room, building, campus) Two or more pc's can from a LAN to share files, folders, printers, applications and other devices. Coaxial or CAT 5 cables are normally used for connections. Due to short distances, errors and noise are minimum. Data transfer rate is 10 to 100 mbps. Example: A computer lab in a school. MAN (Metropolitan Area Network) Design to extend over a large area. Connecting number of LAN's to form larger network, so that resources can be shared. Networks can be up to 5 to 50 km. Owned by organization or individual. Data transfer rate is low compare to LAN. Example: Organization with different branches located in the city. WAN (Wide Area Network) Are country and worldwide network. Contains multiple LAN's and MAN's. Distinguished in terms of geographical range. Uses satellites and microwave relays. Data transfer rate depends upon the ISP provider and varies over the location. Best example is the internet. Other types WLAN (Wireless LAN) A LAN that uses high frequency radio waves for communication. Provides short range connectivity with high speed data transmission. PAN (Personal Area Network) Network organized by the individual user for its personal use. SAN (Storage Area Network) Connects servers to data storage devices via fiber-optic cables. E.g.: Used for daily backup of organization or a mirror copy A transmission medium can be broadly defined as anything that can carry information from a source to a destination. Classes of transmission media Guided Media: Guided media, which are those that provide a medium from one device to another, include twisted-pair cable, coaxial cable, and fiber-optic cable. Twisted-Pair Cable: A twisted pair consists of two conductors (normally copper), each with its own plastic insulation, twisted together. One of the wires is used to carry signals to the receiver, and the other is used only as a ground reference. Unshielded Versus Shielded Twisted-Pair Cable The most common twisted-pair cable used in communications is referred to as unshielded twisted-pair (UTP). STP cable has a metal foil or braided mesh covering that encases each pair of insulated conductors. Although metal casing improves the quality of cable by preventing the penetration of noise or crosstalk, it is bulkier and more expensive. The most common UTP connector is RJ45 (RJ stands for registered jack) Applications Twisted-pair cables are used in telephone lines to provide voice and data channels. Local-area networks, such as l0Base-T and l00Base-T, also use twisted-pair cables. Coaxial Cable Coaxial cable (or coax) carries signals of higher frequency ranges than those in twisted pair cable. coax has a central core conductor of solid or stranded wire (usuallycopper) enclosed in an insulating sheath, which is, in turn, encased in an outer conductor of metal foil, braid, or a combination of the two. The outer metallic wrapping serves both as a shield against noise and as the second conductor, which completes the circuit.This outer conductor is also enclosed in an insulating sheath, and the whole cable is protected by a plastic cover. The most common type of connector used today is the Bayone-Neill-Concelman (BNe), connector. Applications Coaxial cable was widely used in analog telephone networks,digital telephone networks Cable TV networks also use coaxial cables. Another common application of coaxial cable is in traditional Ethernet LANs Fiber-Optic Cable A fiber-optic cable is made of glass or plastic and transmits signals in the form of light. Light travels in a straight line as long as it is moving through a single uniform substance. If a ray of light traveling through one substance suddenly enters another substance(of a different density), the ray changes direction. Bending of light ray Optical fibers use reflection to guide light through a channel. A glass or plastic core is surrounded by a cladding of less dense glass or plastic. Propagation Modes Multimode is so named because multiple beams from a light source move through the core in different paths. How these beams move within the cable depends on the structure of the core, as shown in Figure. In multimode step-index fiber, the density of the core remains constant from the center to the edges. A beam of light moves through this constant density in a straight line until it reaches the interface of the core and the cladding. The term step index refers to the suddenness of this change, which contributes to the distortion of the signal as it passes through the fiber. A second type of fiber, called multimode graded-index fiber, decreases this distortion of the signal through the cable. The word index here refers to the index of refraction. Single-Mode: Single-mode uses step-index fiber and a highly focused source of light that limits beams to a small range of angles, all close to the horizontal. Fiber Construction The subscriber channel (SC) connector, The straight-tip (ST) connector, MT-RJ(mechanical transfer registered jack) is a connector Applications Fiber-optic cable is often found in backbone networks because its wide bandwidth is cost-effective.. Some cable TV companies use a combination of optical fiber and coaxial cable,thus creating a hybrid network. Local-area networks such as 100Base-FX network (Fast Ethernet) and 1000Base-X also use fiber-optic cable Advantages and Disadvantages of Optical Fiber Advantages Fiber-optic cable has several advantages over metallic cable (twisted pair or coaxial). 1 Higher bandwidth. 2 Less signal attenuation. Fiber-optic transmission distance is significantly greaterthan that of other guided media. A signal can run for 50 km without requiring regeneration. We need repeaters every 5 km for coaxial or twisted- pair cable. 3 Immunity to electromagnetic interference. Electromagnetic noise cannot affect fiber-optic cables. 4 Resistance to corrosive materials. Glass is more resistant to corrosive materials than copper. 5 Light weight. Fiber-optic cables are much lighter than copper cables. 6 Greater immunity to tapping. Fiber-optic cables are more immune to tapping than copper cables. Copper cables create antenna effects that can easily be tapped. Disadvantages There are some disadvantages in the use of optical fiber. 1Installation and maintenance 2 Unidirectional light propagation. Propagation of light is unidirectional. If we need bidirectional communication, two fibers are needed. 3 Cost. The cable and the interfaces are relatively more expensive than those of other guided media. If the demand for bandwidth is not high, often the use of optical fiber cannot be justified. UNGUIDED MEDIA: WIRELESS Unguided media transport electromagnetic waves without using a physical conductor. This type of communication is often referred to as wireless communication. Radio Waves Microwaves Infrared Unguided signals can travel from the source to destination in several ways: ground propagation, sky propagation, and line-of-sight propagation, as shown in Figure Radio Waves Electromagnetic waves ranging in frequencies between 3 kHz and 1 GHz are normally called radio waves. Radio waves are omni directional. When an antenna transmits radio waves, they are propagated in all directions. This means that the sending and receiving antennas do not have to be aligned. A sending antenna sends waves that can be received by any receiving antenna. The omni directional property has a disadvantage, too. The radio waves transmitted by one antenna are susceptible to interference by another antenna that may send signals using the same frequency or band. Omni directional Antenna Radio waves use omnidirectional antennas that send out signals in all directions. Based on the wavelength, strength, and the purpose of transmission, we can have several types of antennas. Figure shows an omnidirectional antenna. Applications The Omni directional characteristics of radio waves make them useful for multicasting, in which there is one sender but many receivers. AM and FM radio, television, maritime radio, cordless phones, and paging are examples of multicasting. Microwaves Electromagnetic waves having frequencies between 1 and 300 GHz are called microwaves. Microwaves are unidirectional. The sending and receiving antennas need to be aligned. The unidirectional property has an obvious advantage. A pair of antennas can be aligned without interfering with another pair of aligned antennas Unidirectional Antenna Microwaves need unidirectional antennas that send out signals in one direction. Two types of antennas are used for microwave communications: the parabolic dish and the horn Applications: Microwaves are used for unicast communication such as cellular telephones, satellite networks, and wireless LANs Infrared Infrared waves, with frequencies from 300 GHz to 400 THz (wavelengths from 1 mm to 770 nm), can be used for short-range communication. Infrared waves, having high frequencies, cannot penetrate walls. This advantageous characteristic prevents interference between one system and another; a short- range communication system in one room cannot be affected by another system in the next room. When we use our infrared remote control, we do not interfere with the use of the remote by our neighbors. Infrared signals useless for long-range communication. In addition, we cannot use infrared waves outside a building because the sun's rays contain infrared waves that can interfere with the communication. Applications: Infrared signals can be used for short-range communication in a closed area using line-of-sight propagation. Switching A network is a set of connected devices. Whenever we have multiple devices, we have the problem of how to connect them to make one-to-one communication possible. One solution is to make a point-to-point connection between each pair of devices (a mesh topology) or between a central device and every other device (a star topology). These methods, however, are impractical and wasteful when applied to very large networks. The number and length of the links require too much infrastructure to be cost-efficient, and the majority of those links would be idle most of the time. A better solution is switching. A switched network consists of a series of interlinked nodes, called switches. Switches are devices capable of creating temporary connections between two or more devices linked to the switch. In a switched network, some of these nodes are connected to the end systems (computers or telephones, for example). Others are used only for routing. Figure shows a switched network. We can then divide today's networks into three broad categories: circuit- switched networks, packet-switched networks, and message-switched. Packet- switched networks can further be divided into two subcategories-virtual-circuit networks and datagram networks as shown in Figure. CIRCUIT-SWITCHED NETWORKS A circuit-switched network consists of a set of switches connected by physical links. A connection between two stations is a dedicated path made of one or more links. However, each connection uses only one dedicated channel on each link. Each link is normally divided into n channels by using FDM or TDM. In circuit switching, the resources need to be reserved during the setup phase; the resources remain dedicated for the entire duration of data transfer until the teardown phase Three Phases The actual communication in a circuit-switched network requires three phases: connection setup, data transfer, and connection teardown. Setup Phase Before the two parties (or multiple parties in a conference call) can communicate, a dedicated circuit (combination of channels in links) needs to be established. Connection setup means creating dedicated channels between the switches. For example, in Figure, when system A needs to connect to system M, it sends a setup request that includes the address of system M, to switch I. Switch I finds a channel between itself and switch IV that can be dedicated for this purpose. Switch I then sends the request to switch IV, which finds a dedicated channel between itself and switch III. Switch III informs system M of system A's intention at this time. In the next step to making a connection, an acknowledgment from system M needs to be sent in the opposite direction to system A. Only after system A receives this acknowledgment is the connection established. Data Transfer Phase After the establishment of the dedicated circuit (channels), the two parties can transfer data. Teardown Phase When one of the parties needs to disconnect, a signal is sent to each switch to release the resources. Efficiency It can be argued that circuit-switched networks are not as efficient as the other two types of networks because resources are allocated during the entire duration of the connection. These resources are unavailable to other connections. Delay Although a circuit-switched network normally has low efficiency, the delay in this type of network is minimal. During data transfer the data are not delayed at each switch; the resources are allocated for the duration of the connection. The total delay is due to the time needed to create the connection, transfer data, and disconnect the circuit. Switching at the physical layer in the traditional telephone network uses the circuit-switching approach. DATAGRAM NETWORKS In a packet-switched network, there is no resource reservation; resources are allocated on demand. The allocation is done on a first come, first-served basis. When a switch receives a packet, no matter what is the source or destination, the packet must wait if there are other packets being processed. This lack of reservation may create delay. For example, if we do not have a reservation at a restaurant, we might have to wait. In a datagram network, each packet is treated independently of all others. Packets in this approach are referred to as datagrams. Datagram switching is normally done at the network layer. Figure shows how the datagram approach is used to deliver four packets from station A to station X. The switches in a datagram network are traditionally referred to as routers. The datagram networks are sometimes referred to as connectionless networks. The term connectionless here means that the switch (packet switch) does not keep information about the connection state. There are no setup or teardown phases. Each packet is treated the same by a switch regardless of its source or destination.  A switch in a datagram network uses a routing table that is based on the destination address. The destination address in the header of a packet in a datagram network remains the same during the entire journey of the packet. Efficiency The efficiency of a datagram network is better than that of a circuit-switched network; resources are allocated only when there are packets to be transferred. Delay There may be greater delay in a datagram network than in a virtual-circuit network. Although there are no setup and teardown phases, each packet may experience a wait at a switch before it is forwarded. In addition, since not all packets in a message necessarily travel through the same switches, the delay is not uniform for the packets of a message. Switching in the Internet is done by using the datagram approach to packet switching at the network layer. VIRTUAL-CIRCUIT NETWORKS A virtual-circuit network is a cross between a circuit-switched network and a datagram network. It has some characteristics of both. 1. As in a circuit-switched network, there are setup and teardown phases in addition to the data transfer phase. 2. Resources can be allocated during the setup phase, as in a circuit-switched network, or on demand, as in a datagram network. 3. As in a datagram network, data are packetized and each packet carries an address in the header. However, the address in the header has local jurisdiction (it defines what should be the next switch and the channel on which the packet is being carried), not end-to-end jurisdiction. 4. As in a circuit-switched network, all packets follow the same path established during the connection. 5. A virtual-circuit network is normally implemented in the data link layer, while a circuit-switched network is implemented in the physical layer and a datagram network in the network layer. Addressing In a virtual-circuit network, two types of addressing are involved: global and local (virtual-circuit identifier). Global Addressing A source or a destination needs to have a global address-an address that can be unique in the scope of the network. Virtual-Circuit Identifier The identifier that is actually used for data transfer is called the virtual-circuit identifier (VCI). A VCI, unlike a global address, is a small number that has only switch scope; it is used by a frame between two switches. When a frame arrives at a switch, it has a VCI; when it leaves, it has a different VCl. Figure shows how the VCI in a data frame changes from one switch to another. Note that a VCI does not need to be a large number since each switch can use its own unique set of VCls. Three Phases Three phases in a virtual-circuit network: setup, data transfer, and teardown. We first discuss the data transfer phase, which is more straightforward; we then talk about the setup and teardown phases. Data Transfer Phase  To transfer a frame from a source to its destination, all switches need to have a table entry for this virtual circuit. The table, in its simplest form, has four columns. We show later how the switches make their table entries, but for the moment we assume that each switch has a table with entries for all active virtual circuits. Figure shows such a switch and its corresponding table. Figure shows a frame arriving at port 1 with a VCI of 14. When the frame arrives, the switch looks in its table to find port 1 and a VCI of 14. When it is found, the switch knows to change the VCI to 22 and send out the frame from port 3. Figure shows how a frame from source A reaches destination B and how its VCI changes during the trip. Each switch changes the VCI and routes the frame. The data transfer phase is active until the source sends all its frames to the destination. The procedure at the switch is the same for each frame of a message. The process creates a virtual circuit, not a real circuit, between the source and destination. Setup Phase In the setup phase, a switch creates an entry for a virtual circuit. For example, suppose source A needs to create a virtual circuit to B. Two steps are required: the setup request and the acknowledgment. Setup Request A setup request frame is sent from the source to the destination. Figure shows the process. a. Source A sends a setup frame to switch 1. b. Switch 1 receives the setup request frame. It knows that a frame going from A to B goes out through port 3. For the moment, assume that it knows the output port. The switch creates an entry in its table for this virtual circuit, but it is only able to fill three of the four columns. The switch assigns the incoming port (1) and chooses an available incoming VCI (14) and the outgoing port (3). It does not yet know the outgoing VCI, which will be found during the acknowledgment step. The switch then forwards the frame through port 3 to switch 2. c. Switch 2 receives the setup request frame. The same events happen here as at switch 1; three columns of the table are completed: in this case, incoming port (l), incoming VCI (66), and outgoing port (2). d. Switch 3 receives the setup request frame. Again, three columns are completed: incoming port (2), incoming VCI (22), and outgoing port (3). e. Destination B receives the setup frame, and if it is ready to receive frames from A, it assigns a VCI to the incoming frames that come from A, in this case 77. This VCI lets the destination know that the frames come from A, and not other sources. Acknowledgment A special frame, called the acknowledgment frame, completes the entries in the switching tables. Figure shows the process. a. The destination sends an acknowledgment to switch 3. The acknowledgment carries the global source and destination addresses so the switch knows which entry in the table is to be completed. The frame also carries VCI 77, chosen by the destination as the incoming VCI for frames from A. Switch 3 uses this VCI to complete the outgoing VCI column for this entry. Note that 77 is the incoming VCI for destination B, but the outgoing VCI for switch 3. b. Switch 3 sends an acknowledgment to switch 2 that contains its incoming VCI in the table, chosen in the previous step. Switch 2 uses this as the outgoing VCI in the table. c. Switch 2 sends an acknowledgment to switch 1 that contains its incoming VCI in the table, chosen in the previous step. Switch 1 uses this as the outgoing VCI in the table. d. Finally switch 1 sends an acknowledgment to source A that contains its incoming VCI in the table, chosen in the previous step. e. The source uses this as the outgoing VCI for the data frames to be sent to destination B. Teardown Phase In this phase, source A, after sending all frames to B, sends a special frame called a teardown request. Destination B responds with a teardown confirmation frame. All switches delete the corresponding entry from their tables. Efficiency In virtual-circuit switching, all packets belonging to the same source and destination travel the same path; but the packets may arrive at the destination with different delays if resource allocation is on demand. Delay In a virtual-circuit network, there is a one-time delay for setup and a one-time delay for teardown. If resources are allocated during the setup phase, there is no wait time for individual packets. Figure shows the delay for a packet traveling through two switches in a virtual-circuit network Switching at the data link layer in a switched WAN is normally implemented by using virtual-circuit techniques. Comparison Diagrams from Tanenbaum Textbook OSI  OSI stands for Open Systems Interconnection  Created by International Standards Organization (ISO)  Was created as a framework and reference model to explain how different networking technologies work together and interact  It is not a standard that networking protocols must follow  Each layer has specific functions it is responsible for  All layers work together in the correct order to move data around a network  Top to bottom –All People Seem To Need Data Processing Bottom to top –Please Do Not Throw Sausage Pizza Away Physical Layer  Deals with all aspects of physically moving data from one computer to the next  Converts data from the upper layers into 1s and 0s for transmission over media  Defines how data is encoded onto the media to transmit the data  Defined on this layer: Cable standards, wireless standards, and fiber optic standards. Copper wiring, fiber optic cable, radio frequencies, anything that can be used to transmit data is defined on the Physical layer of the OSI Model  Device example: Hub  Used to transmit data Data Link Layer  Is responsible for moving frames from node to node or computer to computer  Can move frames from one adjacent computer to another, cannot move frames across routers  Encapsulation = frame  Requires MAC address or physical address  Protocols defined include Ethernet Protocol and Point-to-Point Protocol (PPP)  Device example: Switch  Two sublayers: Logical Link Control (LLC) and the Media Access Control (MAC) o Logical Link Control (LLC)  –Data Link layer addressing, flow control, address notification, error control o Media Access Control (MAC)  –Determines which computer has access to the network media at any given time  –Determines where one frame ends and the next one starts, called frame synchronization Network Layer  Responsible for moving packets (data) from one end of the network to the other, called end-to-end communications  Requires logical addresses such as IP addresses  Device example: Router  –Routing is the ability of various network devices and their related software to move data packets from source to destination Transport Layer  Takes data from higher levels of OSI Model and breaks it into segments that can be sent to lower-level layers for data transmission  Conversely, reassembles data segments into data that higher-level protocols and applications can use  Also puts segments in correct order (called sequencing ) so they can be reassembled in correct order at destination  Concerned with the reliability of the transport of sent data  May use a connection-oriented protocol such as TCP to ensure destination received segments  May use a connectionless protocol such as UDP to send segments without assurance of delivery  Uses port addressing Session Layer  Responsible for managing the dialog between networked devices  Establishes, manages, and terminates connections  Provides duplex, half-duplex, or simplex communications between devices  Provides procedures for establishing checkpoints, adjournment, termination, and restart or recovery procedures Presentation Layer  Concerned with how data is presented to the network  Handles three primary tasks: –Translation , –Compression , –Encryption Application Layer  Contains all services or protocols needed by application software or operating system to communicate on the network  Examples o –Firefox web browser uses HTTP (Hyper-Text Transport Protocol) o –E-mail program may use POP3 (Post Office Protocol version 3) to read e-mails and SMTP (Simple Mail Transport Protocol) to send e-mails The interaction between layers in the OSI model An exchange using the OSI model SUMMARY:  TCP/IP Model (Transmission Control Protocol/Internet Protocol) –A protocol suite is a large number of related protocols that work together to allow networked computers to communicate Relationship of layers and addresses in TCP/IP Application Layer  Application layer protocols define the rules when implementing specific network applications  Rely on the underlying layers to provide accurate and efficient data delivery  Typical protocols: o FTP – File Transfer Protocol  For file transfer o Telnet – Remote terminal protocol  For remote login on any other computer on the network o SMTP – Simple Mail Transfer Protocol  For mail transfer o HTTP – Hypertext Transfer Protocol  For Web browsing  Encompasses same functions as these OSI Model layers Application Presentation Session Transport Layer TCP &UDP  TCP is a connection-oriented protocol o Does not mean it has a physical connection between sender and receiver o TCP provides the function to allow a connection virtually exists – also called virtual circuit  UDP provides the functions: o Dividing a chunk of data into segments o Reassembly segments into the original chunk o Provide further the functions such as reordering and data resend  Offering a reliable byte-stream delivery service  Functions the same as the Transport layer in OSI  Synchronize source and destination computers to set up the session between the respective computers Internet Layer  The network layer, also called the internet layer, deals with packets and connects independent networks to transport the packets across network boundaries. The network layer protocols are the IP and the Internet Control Message Protocol (ICMP), which is used for error reporting. Host-to-network layer The Host-to-network layer is the lowest layer of the TCP/IP reference model. It combines the link layer and the physical layer of the ISO/OSI model. At this layer, data is transferred between adjacent network nodes in a WAN or between nodes on the same LAN. THE INTERNET The Internet has revolutionized many aspects of our daily lives. It has affected the way we do business as well as the way we spend our leisure time. Count the ways you've used the Internet recently. Perhaps you've sent electronic mail (e-mail) to a business associate, paid a utility bill, read a newspaper from a distant city, or looked up a local movie schedule-all by using the Internet. Or maybe you researched a medical topic, booked a hotel reservation, chatted with a fellow Trekkie, or comparison-shopped for a car. The Internet is a communication system that has brought a wealth of information to our fingertips and organized it for our use. A Brief History A network is a group of connected communicating devices such as computers and printers. An internet (note the lowercase letter i) is two or more networks that can communicate with each other. The most notable internet is called the Internet (uppercase letter I), a collaboration of more than hundreds of thousands of interconnected networks. Private individuals as well as various organizations such as government agencies, schools, research facilities, corporations, and libraries in more than 100 countries use the Internet. Millions of people are users. Yet this extraordinary communication system only came into being in 1969. In the mid-1960s, mainframe computers in research organizations were standalone devices. Computers from different manufacturers were unable to communicate with one another. The Advanced Research Projects Agency (ARPA) in the Department of Defense (DoD) was interested in finding a way to connect computers so that the researchers they funded could share their findings, thereby reducing costs and eliminating duplication of effort. In 1967, at an Association for Computing Machinery (ACM) meeting, ARPA presented its ideas for ARPANET, a small network of connected computers. The idea was that each host computer (not necessarily from the same manufacturer) would be attached to a specialized computer, called an inteiface message processor (IMP). The IMPs, in tum, would be connected to one another. Each IMP had to be able to communicate with other IMPs as well as with its own attached host. By 1969, ARPANET was a reality. Four nodes, at the University of California at Los Angeles (UCLA), the University of California at Santa Barbara (UCSB), Stanford Research Institute (SRI), and the University of Utah, were connected via the IMPs to form a network. Software called the Network Control Protocol (NCP) provided communication between the hosts. In 1972, Vint Cerf and Bob Kahn, both of whom were part of the core ARPANET group, collaborated on what they called the Internetting Projec1. Cerf and Kahn's landmark 1973 paper outlined the protocols to achieve end- to-end delivery of packets. This paper on Transmission Control Protocol (TCP) included concepts such as encapsulation, the datagram, and the functions of a gateway. Shortly thereafter, authorities made a decision to split TCP into two protocols: Transmission Control Protocol (TCP) and Internetworking Protocol (lP). IP would handle datagram routing while TCP would be responsible for higher-level functions such as segmentation, reassembly, and error detection. The internetworking protocol became known as TCPIIP. The Internet Today The Internet has come a long way since the 1960s. The Internet today is not a simple hierarchical structure. It is made up of many wide- and local-area networks joined by connecting devices and switching stations. It is difficult to give an accurate representation of the Internet because it is continually changing-new networks are being added, existing networks are adding addresses, and networks of defunct companies are being removed. Today most end users who want Internet connection use the services of Internet service providers (lSPs). There are international service providers, national service providers, regional service providers, and local service providers. The Internet today is run by private companies, not the government. Figure 1.13 shows a conceptual (not geographic) view of the Internet. International Internet Service Providers: At the top of the hierarchy are the international service providers that connect nations together. National Internet Service Providers: The national Internet service providers are backbone networks created and maintained by specialized companies. There are many national ISPs operating in North America; some of the most well known are SprintLink, PSINet, UUNet Technology, AGIS, and internet Mel. To provide connectivity between the end users, these backbone networks are connected by complex switching stations (normally run by a third party) called network access points (NAPs). Some national ISP networks are also connected to one another by private switching stations called peering points. These normally operate at a high data rate (up to 600 Mbps). Regional Internet Service Providers: Regional internet service providers or regional ISPs are smaller ISPs that are connected to one or more national ISPs. They are at the third level of the hierarchy with a smaller data rate. Local Internet Service Providers: Local Internet service providers provide direct service to the end users. The local ISPs can be connected to regional ISPs or directly to national ISPs. Most end users are connected to the local ISPs. Note that in this sense, a local ISP can be a company that just provides Internet services, a corporation with a network that supplies services to its own employees, or a nonprofit organization, such as a college or a university, that runs its own network. Each of these local ISPs can be connected to a regional or national service provider.  UNIT- II DATA LINK LAYER FUNCTIONS (SERVICES) 1. Providing services to the network layer: 1 Unacknowledged connectionless service. Appropriate for low error rate and real-time traffic. Ex: Ethernet 2. Acknowledged connectionless service. Useful in unreliable channels, WiFi. Ack/Timer/Resend 3. Acknowledged connection-oriented service. Guarantee frames are received exactly once and in the right order. Appropriate over long, unreliable links such as a satellite channel or a long- distance telephone circuit 2. Framing: Frames are the streams of bits received from the network layer into manageable data units. This division of stream of bits is done by Data Link Layer. 3. Physical Addressing: The Data Link layer adds a header to the frame in order to define physical address of the sender or receiver of the frame, if the frames are to be distributed to different systems on the network. 4. Flow Control: A receiving node can receive the frames at a faster rate than it can process the frame. Without flow control, the receiver's buffer can overflow, and frames can get lost. To overcome this problem, the data link layer uses the flow control to prevent the sending node on one side of the link from overwhelming the receiving node on another side of the link. This prevents traffic jam at the receiver side. 5. Error Control: Error control is achieved by adding a trailer at the end of the frame. Duplication of frames are also prevented by using this mechanism. Data Link Layers adds mechanism to prevent duplication of frames. Error detection: Errors can be introduced by signal attenuation and noise. Data Link Layer protocol provides a mechanism to detect one or more errors. This is achieved by adding error detection bits in the frame and then receiving node can perform an error check. Error correction: Error correction is similar to the Error detection, except that receiving node not only detects the errors but also determine where the errors have occurred in the frame. 6. Access Control: Protocols of this layer determine which of the devices has control over the link at any given time, when two or more devices are connected to the same link. 7. Reliable delivery: Data Link Layer provides a reliable delivery service, i.e., transmits the network layer datagram without any error. A reliable delivery service is accomplished with transmissions and acknowledgements. A data link layer mainly provides the reliable delivery  service over the links as they have higher error rates and they can be corrected locally, link at which an error occurs rather than forcing to retransmit the data. 8. Half-Duplex & Full-Duplex: In a Full-Duplex mode, both the nodes can transmit the data at the same time. In a Half-Duplex mode, only one node can transmit the data at the same time. FRAMING: To provide service to the network layer, the data link layer must use the service provided to it by the physical layer. What the physical layer does is accept a raw bit stream and attempt to deliver it to the destination. This bit stream is not guaranteed to be error free. The number of bits received may be less than, equal to, or more than the number of bits transmitted, and they may have different values. It is up to the data link layer to detect and, if necessary, correct errors. The usual approach is for the data link layer to break the bit stream up into discrete frames and compute the checksum for each frame (framing). When a frame arrives at the destination, the checksum is recomputed. If the newly computed checksum is different from the one contained in the frame, the data link layer knows that an error has occurred and takes steps to deal with it (e.g., discarding the bad frame and possibly also sending back an error report).We will look at four framing methods: 1. Character count. 2. Flag bytes with byte stuffing. 3. Starting and ending flags, with bit stuffing. 4. Physical layer coding violations. Character count method uses a field in the header to specify the number of characters in the frame. When the data link layer at the destination sees the character count, it knows how many characters follow and hence where the end of the frame is. This technique is shown in Fig. (a) For four frames of sizes 5, 5, 8, and 8 characters, respectively.  A character stream. (a) Without errors. (b) With one error The trouble with this algorithm is that the count can be garbled by a transmission error. For example, if the character count of 5 in the second frame of Fig. (b) becomes a 7, the destination will get out of synchronization and will be unable to locate the start of the next frame. Even if the checksum is incorrect so the destination knows that the frame is bad, it still has no way of telling where the next frame starts. Sending a frame back to the source asking for a retransmission does not help either, since the destination does not know how many characters to skip over to get to the start of the retransmission. For this reason, the character count method is rarely used anymore. Flag bytes with byte stuffing method gets around the problem of resynchronization after an error by having each frame start and end with special bytes. In the past, the starting and ending bytes were different, but in recent years most protocols have used the same byte, called a flag byte, as both the starting and ending delimiter, as shown in Fig. (a) as FLAG. In this way, if the receiver ever loses synchronization, it can just search for the flag byte to find the end of the current frame. Two consecutive flag bytes indicate the end of one frame and start of the next one. (a) A frame delimited by flag bytes (b) Four examples of byte sequences before and after byte stuffing It may easily happen that the flag byte's bit pattern occurs in the data. This situation will usually interfere with the framing. One way to solve this problem is to have the sender's data link layer insert a special escape byte (ESC) just before each ''accidental'' flag byte in the data. The data link layer on the receiving end removes the escape byte before the data are given to the network layer. This technique is called byte stuffing or character stuffing. Thus, a framing flag byte can be distinguished from one in the data by the absence or presence of an escape byte before it. What happens if an escape byte occurs in the middle of the data? The answer is that, it too is stuffed with an escape byte. Thus, any single escape byte is part of an escape sequence, whereas a doubled one indicates that a single escape occurred naturally in the data. Some examples are shown in Fig. (b). In all cases, the byte sequence delivered after de stuffing is exactly the same as the original byte sequence. A major disadvantage of using this framing method is that it is closely tied to the use of 8-bit characters. Not all character codes use 8-bit characters. For example UNICODE uses 16-bit characters, so a new technique had to be developed to allow arbitrary sized characters Starting and ending flags, with bit stuffing allows data frames to contain an arbitrary number of bits and allows character codes with an arbitrary number of bits per character. It works like this. Each frame begins and ends with a special bit pattern, 01111110 (in fact, a flag byte). Whenever the sender's data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream. This bit stuffing is analogous to byte stuffing, in which an escape byte is stuffed into the outgoing character stream before a flag byte in the data. When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically de- stuffs (i.e., deletes) the 0 bit. Just as byte stuffing is completely transparent to the network layer in both computers, so is bit stuffing. If the user data contain the flag pattern, 01111110, this flag is transmitted as 011111010 but stored in the receiver's memory as 01111110. Fig:Bit stuffing. (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in the receiver's memory after destuffing. With bit stuffing, the boundary between two frames can be unambiguously recognized by the flag pattern. Thus, if the receiver loses track of where it is, all it has to do is scan the input for flag sequences, since they can only occur at frame boundaries and never within the data. Physical layer coding violations method of framing is only applicable to networks in which the encoding on the physical medium contains some redundancy. For example, some LANs encode 1 bit of data by using 2 physical bits. Normally, a 1 bit is a high-low pair and a 0 bit is a low-high pair. The scheme means that every data bit has a transition in the middle, making it easy for the receiver to locate the bit boundaries. The combinations high- high and low-low are not used for data but are used for delimiting frames in some protocols. As a final note on framing, many data link protocols use combination of a character count with one of the other methods for extra safety. When a frame arrives, the count field is used to locate the end of the frame. Only if the appropriate delimiter is present at that position and the checksum is correct is the frame accepted as valid. Otherwise, the input stream is scanned for the next delimiter ELEMENTARY DATA LINK PROTOCOLS Simplest Protocol It is very simple. The sender sends a sequence of frames without even thinking about the receiver. Data are transmitted in one direction only. Both sender & receiver always ready. Processing time can be ignored. Infinite buffer space is available. And best of all, the communication channel between the data link layers never damages or loses frames. This thoroughly unrealistic protocol, which we will nickname ‘‘Utopia,’’.The utopia protocol is unrealistic because it does not handle either flow control or error correction Stop-and-wait Protocol It is still very simple. The sender sends one frame and waits for feedback from the receiver. When the ACK arrives, the sender sends the next frame It is Stop-and-Wait Protocol because the sender sends one frame, stops until it receives confirmation from the receiver (okay to go ahead), and then sends the next frame. We still have unidirectional communication for data frames, but auxiliary ACK frames (simple tokens of acknowledgment) travel from the other direction. We add flow control to our previous protocol. NOISY CHANNELS Although the Stop-and-Wait Protocol gives us an idea of how to add flow control to its predecessor, noiseless channels are nonexistent. We can ignore the error (as we sometimes do), or we need to add error control to our protocols. We discuss three protocols in this section that use error control. Sliding Window Protocols: 1 Stop-and-Wait Automatic Repeat Request 2 Go-Back-N Automatic Repeat Request 3 Selective Repeat Automatic Repeat Request 1 Stop-and-Wait Automatic Repeat Request To detect and correct corrupted frames, we need to add redundancy bits to our data frame. When the frame arrives at the receiver site, it is checked and if it is corrupted, it is silently discarded. The detection of errors in this protocol is manifested by the silence of the receiver. Lost frames are more difficult to handle than corrupted ones. In our previous protocols, there was no way to identify a frame. The received frame could be the correct one, or a duplicate, or a frame out of order. The solution is to number the frames. When the receiver receives a data frame that is out of order, this means that frames were either lost or duplicated The lost frames need to be resent in this protocol. If the receiver does not respond when there is an error, how can the sender know which frame to resend? To remedy this problem, the sender keeps a copy of the sent frame. At the same time, it starts a timer. If the timer expires and there is no ACK for the sent frame, the frame is resent, the copy is held, and the timer is restarted. Since the protocol uses the stop-and-wait mechanism, there is only one specific frame that needs an ACK Error correction in Stop-and-Wait ARQ is done by keeping a copy of the sent frame and retransmitting of the frame when the timer expires In Stop-and-Wait ARQ, we use sequence numbers to number the frames. The sequence numbers are based on modulo-2 arithmetic. In Stop-and-Wait ARQ, the acknowledgment number always announces in modulo-2 arithmetic the sequence number of the next frame expected. Bandwidth Delay Product: Assume that, in a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit takes 20 ms to make a round trip. What is the bandwidth-delay product? If the system data frames are 1000 bits in length, what is the utilization percentage of the link? The link utilization is only 1000/20,000, or 5 percent. For this reason, for a link with a high bandwidth or long delay, the use of Stop-and-Wait ARQ wastes the capacity of the link. 2. Go-Back-N Automatic Repeat Request To improve the efficiency of transmission (filling the pipe), multiple frames must be in transition while waiting for acknowledgment. In other words, we need to let more than one frame be outstanding to keep the channel busy while the sender is waiting for acknowledgment.  The first is called Go-Back-N Automatic Repeat. In this protocol we can send several frames before receiving acknowledgments; we keep a copy of these frames until the acknowledgments arrive. In the Go-Back-N Protocol, the sequence numbers are modulo 2 m, where m is the size of the sequence number field in bits. The sequence numbers range from 0 to 2 power m- 1. For example, if m is 4, the only sequence numbers are 0 through 15 inclusive. The sender window at any time divides the possible sequence numbers into four regions. The first region, from the far left to the left wall of the window, defines the sequence numbers belonging to frames that are already acknowledged. The sender does not worry about these frames and keeps no copies of them. The second region, colored in Figure (a), defines the range of sequence numbers belonging to the frames that are sent and have an unknown status. The sender needs to wait to find out if these frames have been received or were lost. We call these outstanding frames. The third range, white in the figure, defines the range of sequence numbers for frames that can be sent; however, the corresponding data packets have not yet been received from the network layer. Finally, the fourth region defines sequence numbers that cannot be used until the window slides The send window is an abstract concept defining an imaginary box of size 2m − 1 with three variables: Sf, Sn, and Ssize. The variable Sf defines the sequence number of the first (oldest) outstanding frame. The variable Sn holds the sequence number that will be assigned to the next frame to be sent. Finally, the variable Ssize defines the size of the window. Figure (b) shows how a send window can slide one or more slots to the right when an acknowledgment arrives from the other end. The acknowledgments in this protocol are cumulative, meaning that more than one frame can be acknowledged by an ACK frame. In Figure, frames 0, I, and 2 are acknowledged, so the window has slide to the right three slots. Note that the value of Sf is 3 because frame 3 is now the first outstanding frame.The send window can slide one or more slots when a valid acknowledgment arrives. Receiver window: variable Rn (receive window, next frame expected). The sequence numbers to the left of the window belong to the frames already received and acknowledged; the sequence numbers to the right of this window define the frames that cannot be received. Any received frame with a sequence number in these two regions is discarded. Only a frame with a sequence number matching the value of Rn is accepted and acknowledged. The receive window also slides, but only one slot at a time. When a correct frame is received (and a frame is received only one at a time), the window slides.( see below figure for receiving window) The receive window is an abstract concept defining an imaginary box of size 1 with one single variable Rn. The window slides when a correct frame has arrived; sliding occurs one slot at a time Fig: Receiver window (before sliding (a), After sliding (b)) Timers Although there can be a timer for each frame that is sent, in our protocol we use only one. The reason is that the timer for the first outstanding frame always expires first; we send all outstanding frames when this timer expires. Acknowledgment The receiver sends a positive acknowledgment if a frame has arrived safe and sound and in order. If a frame is damaged or is received out of order, the receiver is silent and will discard all subsequent frames until it receives the one it is expecting. The silence of the receiver causes the timer of the unacknowledged frame at the sender side to expire. This, in turn, causes the sender to go back and resend all frames, beginning with the one with the expired timer. The receiver does not have to acknowledge each frame received. It can send one cumulative acknowledgment for several frames. Resending a Frame When the timer expires, the sender resends all outstanding frames. For example, suppose the sender has already sent frame 6, but the timer for frame 3 expires. This means that frame 3 has not been acknowledged; the sender goes back and sends frames 3,4,5, and 6 again. That is why the protocol is called Go-Back-N ARQ. Below figure is an example(if ack lost) of a case where the forward channel is reliable, but the reverse is not. No data frames are lost, but some ACKs are delayed and one is lost. The example also shows how cumulative acknowledgments can help if acknowledgments are delayed or lost Below figure is an example(if frame lost) Stop-and-Wait ARQ is a special case of Go-Back-N ARQ in which the size of the send window is 1. 3 Selective Repeat Automatic Repeat Request In Go-Back-N ARQ, The receiver keeps track of only one variable, and there is no need to buffer out-of- order frames; they are simply discarded. However, this protocol is very inefficient for a noisy link. In a noisy link a frame has a higher probability of damage, which means the resending of multiple frames. This resending uses up the bandwidth and slows down the transmission. For noisy links, there is another mechanism that does not resend N frames when just one frame is damaged; only the damaged frame is resent. This mechanism is called Selective Repeat ARQ. It is more efficient for noisy links, but the processing at the receiver is more complex. Sender Window (explain go-back N sender window concept (before & after sliding.) The only difference in sender window between Go-back N and Selective Repeat is Window size) Receiver window The receiver window in Selective Repeat is totally different from the one in Go Back-N. First, the size of the receive window is the same as the size of the send window (2m-1). The Selective Repeat Protocol allows as many frames as the size of the receiver window to arrive out of order and be kept until there is a set of in- order frames to be delivered to the network layer. Because the sizes of the send window and receive window are the same, all the frames in the send frame can arrive out of order and be stored until they can be delivered. However the receiver never delivers packets out of order to the network layer. Above Figure shows the receive window. Those slots inside the window that are colored define frames that have arrived out of order and are waiting for their neighbors to arrive before delivery to the network layer. In Selective Repeat ARQ, the size of the sender and receiver window must be at most one-half of 2m Delivery of Data in Selective Repeat ARQ: Flow Diagram Differences between Go-Back N & Selective Repeat One main difference is the number of timers. Here, each frame sent or resent needs a timer, which means that the timers need to be numbered (0, 1,2, and 3). The timer for frame 0 starts at the first request, but stops when the ACK for this frame arrives. There are two conditions for the delivery of frames to the network layer: First, a set of consecutive frames must have arrived. Second, the set starts from the beginning of the window. After the first arrival, there was only one frame and it started from the beginning of the window. After the last arrival, there are three frames and the first one starts from the beginning of the window. Another important point is that a NAK is sent. The next point is about the ACKs. Notice that only two ACKs are sent here. The first one acknowledges only the first frame; the second one acknowledges three frames. In Selective Repeat, ACKs are sent when data are delivered to the network layer. If the data belonging to n frames are delivered in one shot, only one ACK is sent for all of them. Piggybacking A technique called piggybacking is used to improve the efficiency of the bidirectional protocols. When a frame is carrying data from A to B, it can also carry control information about arrived (or lost) frames from B; when a frame is carrying data from B to A, it can also carry control information about the arrived (or lost) frames from A. RANDOM ACCESS PROTOCOLS We can consider the data link layer as two sub layers. The upper sub layer is responsible for data link control, and the lower sub layer is responsible for resolving access to the shared media The upper sub layer that is responsible for flow and error control is called the logical link control (LLC) layer; the lower sub layer that is mostly responsible for multiple access resolution is called the media access control (MAC) layer. When nodes or stations are connected and use a common link, called a multipoint or broadcast link, we need a multiple-access protocol to coordinate access to the link. Taxonomy of multiple-access protocols RANDOM ACCESS In random access or contention methods, no station is superior to another station and none is assigned the control over another. Two features give this method its name. First, there is no scheduled time for a station to transmit. Transmission is random among the stations. That is why these methods are called random access. Second, no rules specify which station should send next. Stations compete with one another to access the medium. That is why these methods are also called contention methods. ALOHA 1 Pure ALOHA The original ALOHA protocol is called pure ALOHA. This is a simple, but elegant protocol. The idea is that each station sends a frame whenever it has a frame to send. However, since there is only one channel to share, there is the possibility of collision between frames from different stations. Below Figure shows an example of frame collisions in pure ALOHA.  Frames in a pure ALOHA network In pure ALOHA, the stations transmit frames whenever they have data to send.  When two or more stations transmit simultaneously, there is collision and the frames are destroyed.  In pure ALOHA, whenever any station transmits a frame, it expects the acknowledgement from the receiver.  If acknowledgement is not received within specified time, the station assumes that the frame (or acknowledgement) has been destroyed.  If the frame is destroyed because of collision the station waits for a random amount of time and sends it again. This waiting time must be random otherwise same frames will collide again and again.  Therefore pure ALOHA dictates that when time-out period passes, each station must wait for a random amount of time before resending its frame. This randomness will help avoid more collisions. Vulnerable time Let us find the length of time, the vulnerable time, in which there is a possibility of collision. We assume that the stations send fixed- length frames with each frame taking Tfr S to send. Below Figure shows the vulnerable time for station A. Station A sends a frame at time t. Now imagine station B has already sent a frame between t - Tfr and t. This leads to a collision between the frames from station A and station B. The end of B's frame collides with the beginning of A's frame. On the other hand, suppose that station C sends a frame between t and t + Tfr. Here, there is a collision between frames from station A and station C. The beginning of C's frame collides with the end of A's frame  Looking at Figure, we see that the vulnerable time, during which a collision may occur in pure ALOHA, is 2 times the frame transmission time. Pure ALOHA vulnerable time = 2 x Tfr Procedure for pure ALOHA protocol Example A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the requirement to make this frame collision-free? Solution Average frame transmission time Tfr is 200 bits/200 kbps or 1 ms. The vulnerable time is 2 x 1 ms =2 ms. This means no station should send later than 1 ms before this station starts transmission and no station should start sending during the one I-ms period that this station is sending. The throughput for pure ALOHA is S = G × e −2G. The maximum throughput Smax = 0.184 when G= (1/2). PROBLEM A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces a. 1000 frames per second b. 500 frames per second c. 250 frames per second. The frame transmission time is 200/200 kbps or 1 ms. a. If the system creates 1000 frames per second, this is 1 frame per  millisecond. The load is 1. In this case S = G× e −2 G or S = 0.135 (13.5 percent). This means that the throughput is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000 will probably survive. b. If the system creates 500 frames per second, this is (1/2) frame per millisecond. The load is (1/2). In this case S = G × e −2G or S = 0.184 (18.4 percent). This means that the throughput is 500 × 0.184 = 92 and that only 92 frames out of 500 will probably survive. Note that this is the maximum throughput case, percentage wise. c. If the system creates 250 frames per second, this is (1/4) frame per millisecond. The load is (1/4). In this case S = G × e − or S = 0.152 (15.2 2G percent). This means that the throughput is 250 × 0.152 = 38. Only 38 frames out of 250 will probably survive. 2 Slotted ALOHA Pure ALOHA has a vulnerable time of 2 x Tfr. This is so because there is no rule that defines when the station can send. A station may send soon after another station has started or soon before another station has finished. Slotted ALOHA was invented to improve the efficiency of pure ALOHA. In slotted ALOHA we divide the time into slots of Tfr s and force the station to send only at the beginning of the time slot. Figure 3 shows an example of frame collisions in slotted ALOHA FIG:3 Because a station is allowed to send only at the beginning of the synchronized time slot, if a station misses this moment, it must wait until the beginning of the next time slot. This means that the station which started at the beginning of this slot has already finished sending its frame. Of course, there is still the possibility of collision if two stations try to send at the beginning of the same time slot. However, the vulnerable time is now reduced to one-half, equal to Tfr Figure 4 shows the situation Below fig shows that the vulnerable time for slotted ALOHA is one-half that of pure ALOHA. Slotted ALOHA vulnerable time = Tfr  The throughput for slotted ALOHA is S = G × e−G. The maximum throughput Smax = 0.368 when G = 1. A slotted ALOHA network transmits 200-bit frames using a shared channel with a 200- Kbps bandwidth. Find the throughput if the system (all stations together) produces a. 1000 frames per second b. 500 frames per second c. 250 frames per second Solution This situation is similar to the previous exercise except that the network is using slotted ALOHA instead of pure ALOHA. The frame transmission time is 200/200 kbps or 1 ms. a. In this case G is 1. So S =G x e-G or S =0.368 (36.8 percent). This means that the throughput is 1000 x 0.0368 =368 frames. Only 368 out of 1000 frames will probably survive. Note that this is the maximum throughput case, percentagewise. b. Here G is 1/2 In this case S =G x e-G or S =0.303 (30.3 percent). This means that the throughput is 500 x 0.0303 =151. Only 151 frames out of 500 will probably survive. c. Now G is 1/4. In this case S =G x e-G or S =0.195 (19.5 percent). This means that the throughput is 250 x 0.195 = 49. Only 49 frames out of 250 will probably survive Comparison between Pure Aloha & Slotted Aloha Carrier Sense Multiple Access (CSMA) To minimize the chance of collision and, therefore, increase the performance, the CSMA method was developed. The chance of collision can be reduced if a station senses the medium before trying to use it. Carrier sense multiple access (CSMA) requires that each station first listen to the medium (or check the state of the medium) before sending. In other words, CSMA is based on the principle "sense before transmit" or "listen before talk." CSMA can reduce the possibility of collision, but it cannot eliminate it. The reason for this is shown in below Figure. Stations are connected to a shared channel (usually a dedicated medium). The possibility of collision still exists because of propagation delay; station may sense the medium and find it idle, only because the first bit sent by another station has not yet been received. At time tI' station B senses the medium and finds it idle, so it sends a frame. At time t2 (t2> tI)' station C senses the medium and finds it idle because, at this time, the first bits from station B have not reached station C. Station C also sends a frame. The two signals collide and both frames are destroyed.  Space/time model of the collision in CSMA Vulnerable Time The vulnerable time for CSMA is the propagation time Tp. This is the time needed for a signal to propagate from one end of the medium to the other. When a station sends a frame, and any other station tries to send a frame during this time, a collision will result. But if the first bit of the frame reaches the end of the medium, every station will already have heard the bit and will refrain from sending Vulnerable time in CSMA Persistence Methods What should a station do if the channel is busy? What should a station do if the channel is idle? Three methods have been devised to answer these questions: the 1-persistent method, the non-persistent method, and the p-persistent method 1-Persistent: In this method, after the station finds the line idle, it sends its frame immediately (with probability 1). This method has the highest chance of collision because two or more stations may find the line idle and send their frames immediately. Non-persistent: a station that has a frame to send senses the line. If the line is idle, it sends immediately. If the line is not idle, it waits a random amount of time and then senses the line again. This approach reduces the chance of collision because it is unlikely that two or more stations will wait the same amount of time and retry to send simultaneously. However, this method reduces the efficiency of the network because the medium remains idle when there may be stations with frames to send. p-Persistent: This is used if the channel has time slots with a slot duration equal to or greater than the maximum propagation time. The p-persistent approach combines the advantages of the other two strategies. It reduces the chance of collision and improves efficiency. In this method, after the station finds the line idle it follows these steps: 1. With probability p, the station sends its frame. 2. With probability q = 1 - p, the station waits for the beginning of the next time slot and checks the line again. a. If the line is idle, it goes to step 1. b. If the line is busy, it acts as though a collision has occurred and uses the backoff procedure.  a. Carrier Sense Multiple Access with Collision Detection (CSMA/CD) The CSMA method does not specify the procedure following a collision. Carrier sense multiple access with collision detection (CSMA/CD) augments the algorithm to handle the collision. In this method, a station monitors the medium after it sends a frame to see if the transmission was successful. If so, the station is finished. If, however, there is a collision, the frame is sent again. To better understand CSMA/CD, let us look at the first bits transmitted by the two stations involved in the collision. Although each station continues to send bits in the frame until it detects the collision, we show what happens as the first bits collide. In below Figure, stations A and C are involved in the collision. Collision of the first bit in CSMA/CD At time t 1, station A has executed its persistence procedure and starts sending the bits of its frame. At time t2, station C has not yet sensed the first bit sent by A. Station C executes its persistence procedure and starts sending the bits in its frame, which propagate both to the left and to the right. The collision occurs sometime after time t2.Station C detects a collision at time t3 when it receives the first bit of A's frame. Station C immediately (or after a short time, but we assume immediately) aborts transmission. Station A detects collision at time t4 when it receives the first bit of C's frame; it also immediately aborts transmission. Looking at the figure, we see that A transmits for the duration t4 - tl; C transmits for the duration t3 - t2. Minimum Frame Size For CSMAlCD to work, we need a restriction on the frame size. Before sending the last bit of the frame, the sending station must detect a collision, if any, and abort the transmission. This is so because the station, once the entire frame is sent, does not keep a copy of the frame and does not monitor the line for collision detection. Therefore, the frame transmission time Tfr must be at least two times the maximum propagation time Tp. To understand the reason, let us think about the worst-case scenario. If the two stations involved in a collision are the maximum distance apart, the signal from the first takes time Tp to reach the second, and the effect of the collision takes another time Tp to reach the first. So the requirement is that the first station must still be transmitting after 2Tp.  Collision and abortion in CSMA/CD Flow diagram for the CSMA/CD PROBLEM A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal, as we see later) is 25.6 μs, what is the minimum size of the frame? SOL The frame transmission time is T fr = 2 × Tp = 51.2 μs. This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision. The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet. DIFFERENCES BETWEEN ALOHA & CSMA/CD The first difference is the addition of the persistence process. We need to sense the channel before we start sending the frame by using one of the persistence processes The second difference is the frame transmission. In ALOHA, we first transmit the entire frame and then wait for an acknowledgment. In CSMA/CD, transmission and collision detection is a continuous process. We do not send the entire frame and then look for a collision. The station transmits and receives continuously and simultaneously  The third difference is the sending of a short jamming signal that enforces the collision in case other stations have not yet sensed the collision. Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) We need to avoid collisions on wireless networks because they cannot be detected. Carrier sense multiple access with collision avoidance (CSMAlCA) was invented for wirelesss network. Collisions are avoided through the use of CSMA/CA's three strategies: the inter frame space, the contention window, and acknowledgments, as shown in Figure Timing in CSMA/CA Inter frame Space (IFS) First, collisions are avoided by deferring transmission even if the channel is found idle. When an idle channel is found, the station does not send immediately. It waits for a period of time called the inter frame space or IFS. Even though the channel may appear idle when it is sensed, a distant station may have already started transmitting. The distant station's signal has not yet reached this station. The IFS time allows the front of the transmitted signal by the distant station to reach this station. If after the IFS time the channel is still idle, the station can send, but it still needs to wait a time equal to the contention time. The IFS variable can also be used to prioritize stations or frame types. For example, a station that is assigned shorter IFS has a higher priority. In CSMA/CA, the IFS can also be used to define the priority of a station or a frame. Contention Window The contention window is an amount of time divided into slots. A station that is ready to send chooses a random number of slots as its wait time. The number of slots in the window changes according to the binary exponential back-off strategy. This means that it is set to one slot the first time and then doubles each time the station cannot detect an idle channel after the IFS time. This is very similar to the p-persistent method except that a random outcome defines the number of slots taken by the waiting station. One interesting point about the contention window is that the station needs to sense the channel after each time slot. However, if the station finds the channel busy, it does not restart the process; it just stops the timer and restarts it when the channel is sensed as idle. This gives priority to the station with the longest waiting time.  In CSMA/CA, if the station finds the channel busy, it does not restart the timer of the contention window; it stops the timer and restarts it when the channel becomes idle. Acknowledgment With all these precautions, there still may be a collision resulting in destroyed data. In addition, the data may be corrupted during the transmission. The positive acknowledgment and the time-out timer can help guarantee that the receiver has received the frame. This is the CSMA protocol with collision avoidance.  The station ready to transmit, senses the line by using one of the persistent strategies.  As soon as it finds the line to be idle, the station waits for an IFS (Inter frame space) amount of time.  If then waits for some random time and sends the frame.  After sending the frame, it sets a timer and waits for the acknowledgement from the receiver.  If the acknowledgement is received before expiry of the timer, then the transmission is successful.  But if the transmitting station does not receive the expected acknowledgement before the timer expiry then it increments the back off  parameter, waits for the back off time and re senses the line Controlled Access Protocols In controlled access, the stations seek information from one another to find which station has the right to send. It allows only one node to send at a time, to avoid collision of messages on shared medium. The three controlled-access methods are: 1 Reservation 2 Polling 3 Token Passing Reservation  In the reservation method, a station needs to make a reservation before sending data.  The time line has two kinds of periods: 1. Reservation interval of fixed time length 2. Data transmission period of variable frames.  If there are M stations, the reservation interval is divided into M slots, and each station has one slot.  Suppose if station 1 has a frame to send, it transmits 1 bit during the slot 1. No other station is allowed to transmit during this slot.  In general, i th station may announce that it has a frame to send by inserting a 1 bit into i th slot. After all N slots have been checked, each station knows which stations wish to transmit.  The stations which have reserved their slots transfer their frames in that order.  After data transmission period, next reservation interval begins.  Since everyone agrees on who goes next, there will never be any collisions. The following figure shows a situation with five stations and a five slot reservation frame. In the first interval, only stations 1, 3, and 4 have made reservations. In the second interval, only station 1 has made a reservation.  Polling  Polling process is similar to the roll-call performed in class. Just like the teacher, a controller sends a message to each node in turn.  In this, one acts as a primary station(controller) and the others are secondary stations. All data exchanges must be made through the controller.  The message sent by the controller contains the address of the node being selected for granting access.  Although all nodes receive the message but the addressed one responds to it and sends data, if any. If there is no data, usually a “poll reject”(NAK) message is sent back.  Problems include high overhead of the polling messages and high dependence on the reliability of the controller. Token Passing  In token passing scheme, the stations are connected logically to each other in form of ring and access of stations is governed by tokens.  A token is a special bit pattern or a small message, which circulate from one station to the next in the some predefined order.  In Token ring, token is passed from one station to another adjacent station in the ring whereas incase of Token bus, each station uses the bus to send the token to the next station in some predefined order.  In both cases, token represents permission to send. If a station has a frame queued for transmission when it receives the token, it can send that frame before it passes the token to the next station. If it has no queued frame, it passes the token simply.  After sending a frame, each station must wait for all N stations (including itself) to send the token to their neighbors and the other N – 1 stations to send a frame, if they have one.  There exists problems like duplication of token or token is lost or insertion of new station, removal of a station, which need be tackled for correct and reliable operation of this scheme. Error Detection Error A condition when the receiver’s information does not matches with the sender’s information. During transmission, digital signals suffer from noise that can introduce errors in the binary bits travelling from sender to receiver. That means a 0 bit may change to 1 or a 1 bit may change to 0. Error Detecting Codes (Implemented either at Data link layer or Transport Layer of OSI Model) Whenever a message is transmitted, it may get scrambled by noise or data may get corrupted. To avoid this, we use error-detecting codes which are additional data added to a given digital message to help us detect if any error has occurred during transmission of the message. Basic approach used for error detection is the use of redundancy bits, where additional bits are added to fac