Computer Networks Notes (CS19541) PDF

CS19541 COMPUTER NETWORKS UNIT-I FUNDAMENTALS AND DATA LINK LAYER Building a network – Requirements – Layering and protocols – Internet Architecture – Network software – Application Programming Interface (sockets) - Performance – Link layer Services - Framing – Error Detection and Correction - Rel...

CS19541 COMPUTER NETWORKS UNIT-I FUNDAMENTALS AND DATA LINK LAYER Building a network – Requirements – Layering and protocols – Internet Architecture – Network software – Application Programming Interface (sockets) - Performance – Link layer Services - Framing – Error Detection and Correction - Reliable transmission UNIT-II MEDIA ACCESS AND INTERNETWORKING Media Access Protocols – ALOHA - CSMA/CA/CD –Ethernet – Wireless LANs - 802.11- Bluetooth - Switching and Forwarding - Bridges and LAN Switches – Basic Internetworking- IP Service Model – IP fragmentation - Global Addresses – ARP - DHCP – ICMP- Virtual Networks and Tunnels. UNIT-III ROUTING Routing – Network as Graph - Distance Vector – Link State – Global Internet – Subnetting - Classless Routing (CIDR) - BGP- IPv6 – Multicast routing - DVMRP- PIM. UNIT-IV TRANSPORT LAYER Overview of Transport layer – UDP – TCP - Segment Format – Connection Management – Adaptive Retransmission - TCP Congestion control - Congestion avoidance (DECbit, RED) – QoS – Application requirements. UNIT-V APPLICATION LAYER E-Mail (SMTP, MIME, POP3, IMAP), HTTP – DNS - FTP - Telnet – web services - SNMP – MIB – RMON. Text Books 1. Larry L. Peterson, Bruce S. Davie, “Computer Networks: A Systems Approach”, Fifth Edition, Morgan Kaufmann Publishers Inc., 2011. 2. Behrouz A. Forouzan, “Data Communications and Networking”, Fifth Edition, McGrawHill, 2017 Reference Books 1. William Stallings, “SNMP, SNMPv2, SNMPv3 and RMON 1 and 2”, Third Edition, Pearson Edition, 2009. 2. James F. Kurose, Keith W. Ross,” Computer Networking - A Top-Down Approach Featuring the Internet”, Seventh Edition, Pearson Education, 2017. 3. Andrew S. Tanenbaum, David J. Wetherall, “Computer Networks”, 5th Edition, Prentice Hall publisher, 2010. 4. William Stallings, “Data and Computer Communications”, Eighth Edition, Pearson Education, 2011. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 1 CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 2  CS19541 - COMPUTER NETWORKS UNIT-I FUNDAMENTALS AND DATA LINK LAYER Building a network – Requirements – Layering and protocols – Internet Architecture – Network software –Application Programming Interface (sockets) - Performance – Link layer Services - Framing– Error Detection and Correction - Reliable transmission Computer network Computer network is defined as the interconnection of nodes (computers and other devices) connected by a communication channel (wired or wireless) that facilitates communication among users and allows them to share resources (Information, hardware and software resources.) INTRODUCTION Data Communications is the transfer of data or information between a sender and a receiver. The sender transmits the data and the receiver receives it. The effectiveness of a data communication depends on three characteristics, Delivery : The system must deliver data to correct destination. Accuracy : The system must deliver data accurately. Timeliness : The system must deliver data in a timely manner. Components of data communication  Sender: It is the transmitter of data. Some examples are Terminal, Computer, and Mainframe.  Medium: The communication stream through which the data is being transmitted. Some examples are: Cabling, Microwave, Fiber optics, Radio Frequencies (RF), Infrared Wireless  Receiver: The receiver of the data transmitted. Some examples are Printer, Terminal, Mainframe, and Computer.  Message: It is the data that is being transmitted from the Source/Sender to the Destination/Receiver. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 3  Protocol: It is the set of rules and regulations (resides in the form of software and hardware) that are to be followed for communication. If protocol is not present it implies the nodes are connected but they can’t communicate.  DCE: The interface between the Sender and the Medium, and the Medium & the Receiver is called the DCE (Data Communication Equipment) and is a physical piece of equipment.  DTE: Data Terminal Equipment is the Telecommunication name given to the Source and Receiver's equipment. Direction of Data Flow It defines how the data flows between two end points. Based on the direction and time of flow there are three kinds of data flow, 1. Simplex 2. Half-Duplex 3. Full-duplex. Simplex: In this type of data communication, the data flows in only one direction on the data communication line (medium). Examples are Keyboard, Monitor, Radio and Television broadcasts Half-Duplex: In this type of data communication, the data flows in both directions but at a time in only one direction on the data communication line. Example Conversation on walkie-talkies is a half-duplex data flow. Time t1 Time t2 Figure: Half-Duplex Data Flow CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 4 Full-Duplex: In this type of data communication, the data flows in both directions simultaneously. Example Telephones and Modems Figure: Full-Duplex Data Flow Types of Connections / Line configuration / Direct links There are two types of line configuration, they are 1. point to po4int 2. multipoint Point to Point  It provides a dedicated link between two devices.  The entire capacity (bandwidth) of the link is reserved for transmission between these two devices. The two devices are connected by means of a pair of wires or using a microwave or satellite link.  Eg : Computers connected by telephone line PPP connection between remote and TV Figure: Point-to-point link Multipoint (Multiple Access)  It is a connection in which more than two devices share a single link.  In this environment a single channel is shared, either spatially or temporally.  If several devices can use the link at the same time it said to be spatially shared.  If the devices take turn to use the link then it is referred to as timesharing. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 5 Different Communication Modes 1) Unicast - one to one Unicast packets are sent from host to host. The communication is from a single host to another single host. 2) Broadcast – one to all Broadcast is when a single device is transmitting a packet to all other devices in a given address range. 3) Multicast – one to many Multicast enables a single device to communicate with a specific set of hosts. Categories of networks The three primary categories of network are Local Area Network (LAN), Metropolitan Area Network (MAN), and Wide Area Network (WAN). The category into which a network fall is determined by its size, ownership, the distance it covers and its physical architecture. LAN  A LAN is usually privately owned and links the devices in a single office, building or campus.  A LAN can be as simple as two PCs or it can extend throughout a company. LAN size is limited to a few kilometers.  The most widely used LAN technology is the Ethernet technology developed by the Xerox Corporation. MAN  A MAN is designed to extend over an entire city.  It could be a single network such as cable TV network or connect a number of LANs into a larger network.  A MAN can be owned by a private company or it may be a service provided by a public company, such as local telephone company.  Telephone companies provide a popular MAN service called (SMDS) Switched Multi-megabit Data Services. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 6   Figure: Metropolitan Area Network WAN  A WAN provides long distance transmission of data, voice, image and video information over large geographic areas.  Transmission rates are typically 2 Mbps, 34 Mbps, 45 Mbps, 155 Mbps and 625 Mbps. WAN utilize public, leased, or private communication equipment usually in combinations and therefore span an unlimited number of miles.  A WAN that is wholly owned and used by a single company is referred to as an Enterprise Network. PAN  A Personal Area Network (PAN) is the interconnection of devices within the range of an individual person, typically within a range of 10 meters.  For example, a person traveling with a laptop, a personal digital assistant (PDA), and a portable printer could interconnect them without having to plug anything in, using some form of wireless technology.  Typically, this kind of personal area network could also be interconnected without wires to the Internet or other networks. Figure: Personal Area Network CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 7  Topology Physical Topology refers to the fashion in which nodes in the network is laid out physically. The topology of a network is the geometric representation of the relationship of all the links and the linking devices tone another. It defines the physical layout of the network. The basic topologies are:  Mesh  Star  Bus  Ring  Hybrid (combination of other types) Mesh  In a mesh topology each device has a dedicated point to point link to every other device.  The term dedicated means that the link carries traffic only between the two devices it connects.  A fully connected mesh network therefore has n (n-1)/2 physical channels to link n devices. To accommodate that many links every device on the network should have (n-1) I/O ports. Merits  Eliminates the traffic problems that occur when the links are shared by multiple devices.  If one link becomes unusable, it does not incapacitate the entire system.  Since every message travels along a dedicated line only the intended recipient will receive the message and hence the data is secure. Demerits  The amount of cabling and the I/O ports required increases with the number of devices connected in the network  Installation and reconnection are difficult  The sheer bulk of the wire accommodates more space than available.  The hardware required to connect each link can be prohibitively expensive. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 8  Star  Each device has a dedicated point to point link only to a central controller usually called a hub.  If one device has to send data to another it sends the data to the controller, which then relays the data to the other connected device. Merits  Less expensive than a mesh topology. Each device needs only one link and I/O port.  Installation and reconfigure is easy.  Robustness. If one link fails only that link is affected.  Requires less cable than a mesh. Demerits  Require more cable compared to bus and ring topologies.  Failure of the central controller incapacitates the entire network. Bus  One long cable acts as a backbone to link all the devices in a network.  Nodes are connected to the bus cable by drop lines and taps.  A drop line is a connection running between the device and the main cable.  A tap is a connector that either splices into the main cable to create a contact with a metallic core.  As the signal travels farther and farther, it becomes weaker. So there is limitation in the number of taps a bus can support and on the distance between those taps. Merits  Ease of installation.  Bus uses less cabling than mesh or star topologies. Demerits  Difficult reconnection and isolation.  Signal reflection at the taps can cause degradation in quality.  A fault or break in the bus cable stops all transmission.  It also reflects signals back in the direction of origin creating noise in both directions. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 9  Ring  Each device has a dedicated point to point connection only with the two devices on either side of it.  A signal is passed along the ring in one direction from device to device until it reaches the destination.  Each device in the ring incorporates a repeater Merits:  Easy to install and reconfigure.  To add or delete a device requires changing only two connections. Demerits  A break in the ring disables the entire network. It can be solved by using a dual ring or a switch capable of closing off the break. Hybrid Topology  A hybrid topology is a type of network topology that uses two or more other network topologies, including bus topology, mesh topology, ring topology, star topology, and tree topology. Requirements The following are the requirements to be followed to build any network,  Identification of constraints and requirements  Connectivity need to be decided  Cost-effective resource sharing  Support for common services CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 10 Identification of constraints and requirements of a network Three groups of people might list their requirements for a network, 1. Application Programmer – List the services that his application needs: delay bounded delivery of data 2. Network Designer – Designs a cost-effective network with sharable resources 3. Network Provider – List the characteristics of a system that is easy to manage Connectivity in a network: Links, Nodes, and Clouds Network connectivity occurs at many different levels. At the lowest level, a network can consist of two or more computers directly connected by some physical medium, such as a coaxial cable or an optical fiber. We call such a physical medium a link, and we often refer to the computers it connects as nodes. A set of computers can be indirectly connected. A set of independent networks (clouds) are interconnected to form an internetwork. A node that is connected to two or more networks is commonly called a router or gateway. A router/gateway forwards messages from one network to another. Switched Network Those nodes that are attached to at least two links run software that forwards data received on one link out on another. If organized in a systematic way, these forwarding nodes form a switched network. There are numerous types of switched networks, of which the two most common are circuit switched and packet switched. Types of switched networks 1. Circuit Switched First establishes a dedicated circuit across a sequence of links and then allows the source node to send a stream of bits across this circuit to a destination node. 2. Packet Switched networks It uses a strategy called store-and-forward. Each node in a store-and-forward network first receives a complete packet over some link, stores the packet in its internal memory, and then forwards the complete packet to the next node. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 11 Cost-Effective Resource Sharing  Resource: links and nodes  How to share a link? o Multiplexing Analogy to a timesharing computer system. o De-multiplexing Multiplexing multiple logical flows over a single physical link Synchronous Time-division Multiplexing (STDM)  Equal-sized quanta  Round-robin fashion  Time slots/data transmitted in predetermined slots Frequency Division Multiplexing(FDM) Eg:Diff. TV stations with diff. frequencies.  Both STDM and FDM waste resources and hard to accommodate changes (fixed time slots and frequencies) Statistical Multiplexing Like STDM: sharing over time but data is transmitted based on demand rather than during a predetermined time slot. A switch multiplexing packets from multiple sources onto one shared link CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 12 Support for Common Services Logical Channels – Application-to-Application communication path or a pipe Client/Server Two types of communication channel – Request/Reply Channels – Message Stream Channels NETWORK ARCHITECTURES Network designers have developed general blueprints—usually called network architectures—that guide the design and implementation of networks. 1. Layering & protocols 2. OSI layers 3. Internet Architecture Layering and Protocols Layering provides two nice features.  It decomposes the problem of building a network into more manageable components.  It provides a more modular design. First, it decomposes the problem of building a network into more manageable components. Rather than implementing a monolithic piece of software that does everything you will ever want, you can implement several layers, each of which solves one part of the problem. Second, it provides a more modular design. If you decide that you want to add some new service, you may only need to modify the functionality at one layer, reusing the functions provided at all the other layers. Fig: Example of a layered network system CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 13  ISO - OSI reference Model  The International Standards Organization (ISO) - Open Systems Interconnect (OSI) is a standard which defines a set of rules to govern the data communication between two devices without worrying about the underlying architecture of the devices. It describes the functionalities for transfer of data between each layer. Each layer has a specific function.  ISO is the organization; OSI is the model.  There are 7 Layers in the OSI model 1. Physical Layer 2. Datalink Layer 3. Network Layer 4. Transport Layer 5. Session Layer 6. Presentation Layer 7. Application Layer Two interfaces  Service interface  Peer interface Service interface- defines the operations that local objects can perform on the protocol. Peer interface- defines the form and meaning of messages exchanged between protocol peers to implement the communication service. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 14 Fig : Service and Peer Interfaces A Data exchange using the OSI model 1. PHYSICAL LAYER (bit level transmission) The physical layer coordinates the functions required to transmit a bit stream over a physical medium. It is responsible for moving bits from one node to the next. The physical layer is concerned with the following:  Physical characteristics of interfaces and media - The physical layer defines the characteristics of the interface between the devices and the transmission medium.  Representation of bits - To transmit the stream of bits, it must be encoded to signals. The physical layer defines the type of encoding.  Data Rate or Transmission rate - The number of bits sent each second – is also defined by the physical layer. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 15   Synchronization of bits - The sender and receiver must be synchronized at the bit level. Their clocks must be synchronized.  Line Configuration - In a point-to-point configuration, two devices are connected together through a dedicated link. In a multipoint configuration, a link is shared between several devices.  Physical Topology - The physical topology defines how devices are connected to make a network. Devices can be connected using a mesh, bus, star or ring topology.  Transmission Mode - The physical layer also defines the direction of transmission between two devices: simplex, half-duplex or full-duplex. 2. DATA LINK LAYER (Node to node delivery or hop to hop delivery of frames) It is responsible for transmitting frames from one node to next node. The other responsibilities of this layer are  Framing - Divides the stream of bits received into data units called frames.  Physical addressing – If frames are to be distributed to different systems on the n/w, data link layer adds a header to the frame to define the sender and receiver.  Flow control- If the rate at which the data are absorbed by the receiver is less than the rate produced in the sender, the Data link layer imposes a flow control mechanism.  Error control- Used for detecting and retransmitting damaged or lost frames and to prevent duplication of frames. This is achieved through a trailer added at the end of the frame.  Access control -Used to determine which device has control over the link at any given time. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 16 3. NETWORK LAYER (Source to destination delivery of individual packets) This layer is responsible for the delivery of packets from source to destination. It is mainly required, when it is necessary to send information from one network to another. It ensures that each packet gets from its point of origin to its final destination. The other responsibilities of this layer are  Logical addressing - If a packet passes the n/w boundary, we need another addressing system for source and destination called logical address.  Routing – The devices which connects various networks called routers are responsible for delivering packets to final destination. 4. TRANSPORT LAYER (Source to destination delivery of entire message)  It is responsible for Process to Process delivery of entire message.  It also ensures whether the message arrives in order or not. The other responsibilities of this layer are  Port addressing - The header in this must therefore include a address called port address. This layer gets the entire message to the correct process on that computer.  Segmentation and reassembly - The message is divided into segments and each segment is assigned a sequence number. These numbers are arranged correctly on the arrival side by this layer. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 17   Connection control - This can either be connectionless or connection- oriented. The connectionless treats each segment as a individual packet and delivers to the destination. The connection-oriented makes connection on the destination side before the delivery. After the delivery the termination will be terminated. Flow and error control - Similar to data link layer, but process to process take place. ie end to end error & flow control 5. SESSION LAYER (Responsible for dialog control and synchronization) This layer establishes, manages and terminates connections between applications. The other responsibilities of this layer are  Dialog control - This session allows two systems to enter into a dialog either in half duplex or full duplex.  Synchronization-This allows to add checkpoints into a stream of data. Example: If a system is sending a file of 2000 pages, check points may be inserted after every 100 pages to ensure that each 100 page unit is advised and acknowledged independently. So if a crash happens during the transmission of page 523, retransmission begins at page 501, pages 1 to 500 need not be retransmitted. 6. PRESENTATION LAYER Presentation Layer is concerned with the syntax and semantics of the information exchanged between two systems. The presentation layer is responsible for translation, compression, and encryption. It is concerned with the syntax and semantics of information exchanged between two systems. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 18 The other responsibilities of this layer are  Translation – Different computers use different encoding system, this layer is responsible for interoperability between these different encoding methods. It will change the message into some common format.  Encryption and decryption-It means that sender transforms the original information to another form and sends the resulting message over the network and vice versa.  Compression and expansion-Compression reduces the number of bits contained in the information particularly in text, audio and video. 7. APPLICATION LAYER This layer enables the user to access the network resources. This allows the user to log on to remote user. The other responsibilities of this layer are  FTAM(file transfer,access,mgmt) - Allows user to access files in a remote host.  Network Virtual terminal: A network virtual terminal is a software version of a physical terminal and allows a user to log on to a remote host.  Mail services - Provides email forwarding and storage.  Directory services - Provides database sources to access information about various sources and objects. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 19  Internet(TCP/IP) Architecture The Internet architecture, which is sometimes called the TCP/IP architecture after its two main protocols. The Internet architecture evolved out of experiences with an earlier packet-switched network called the ARPANET. Both the Internet and the ARPANET were funded by the Advanced Research Projects Agency (ARPA), one of the research and development funding agencies of the U.S. Department of Defense. The Internet and ARPANET were around before the OSI model, and the experience gained from building them was a major influence on the OSI reference model. Layers of TCP / IP model Application layer Transport layer Internet layer Network interface layer Fig: Alternative view of the Internet architecture. The “Network Interface” layer shown here is sometimes referred to as the “sub-network” or “link” layer. While the 7-layer OSI model can, with some imagination, be applied to the Internet, a 4-layer model is often used instead. The TCP/IP protocol suite was developed prior to the OSI model. Therefore, the layers in the TCP/IP protocol suite do not exactly match those in the OSI model. Comparison of OSI and TCP / IP layers CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 20 fig: Internet Protocol Graph At the lowest level is a wide variety of network protocols, denoted NET1, NET2, and so on. In practice, these protocols are implemented by a combination of hardware (e.g., a network adaptor) and software (e.g., a network device driver). For example, you might find Ethernet or wireless protocols (such as the 802.11 Wi-Fi standards) at this layer. (These protocols in turn may actually involve several sublayers, but the Internet architecture does not presume anything about them.) The second layer consists of a single protocol—the Internet Protocol (IP). This is the protocol that supports the interconnection of multiple networking technologies into a single, logical internetwork. The third layer contains two main protocols—the Transmission Control Protocol (TCP) and the User Datagram Protocol (UDP).TCP and UDP provide alternative logical channels to application programs: TCP provides a reliable byte-stream channel, and UDP provides an unreliable datagram delivery channel (datagram may be thought of as a synonym for message). In the language of the Internet, TCP and UDP are sometimes called end-to-end protocols, although it is equally correct to refer to them as transport protocols. Running above the transport layer is a range of application protocols, such as HTTP, FTP, Telnet (remote login), and the Simple Mail Transfer Protocol (SMTP), that enable the interoperation of popular applications. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 21  Framing-Datalink Layer Data link layer divides the stream of bits received from the upper layer (network layer) into manageable data units called frames. It adds a header to the frame to define the physical address (source address & destination address).  Blocks of data (called frames at this level) are exchanged between nodes.  It is the network adaptor that enables the nodes to exchange frames.  When node A wishes to transmit a frame to node B, it tells its adaptor to transmit a frame from the node's memory.  This results in a sequence of bits being sent over the link.  The adaptor on node B then collects together the sequence of bits arriving on the link and deposits the corresponding frame in B's memory.  Recognizing exactly what set of bits constitutes a frame—that is, determining where the frame begins and ends—is the central challenge faced by the adaptor. Fixed-Size Framing: Frames can be of fixed or variable size. In fixed-size framing, there is no need for defining the boundaries of the frames; the size itself can be used as a delimiter. An example of this type of framing is the ATM wide-area network, which uses frames of fixed size called cells. Variable-Size Framing: In variable-size framing, we need a way to define the end of the frame and the beginning of the next. Three approaches were used for this purpose: Framing Protocols: (i) Byte-oriented protocols (ii) Bit-oriented protocols (iii) Clock-based protocols Byte-oriented protocols:  sentinel approach 1. BISYNC – Binary Synchronous Communication 2. PPP – Point-to-point Protocol  Byte-counting approach 3. DDCMP- Digital Data Communication Message Protocol CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 22 Bit-oriented protocols: (i) HDLC – High Level Data Link Control Clock-based protocols: (i) SONET - Synchronous Optical Network Byte oriented Protocols Sentinel Approach  It uses special characters known as sentinel characters to indicate where the frame starts and ends. Binary Synchronous Communication (BISYNC)  The beginning of a frame is denoted by sending a special SYN (synchronization) character.  The data portion of the frame is then contained between special sentinel characters: STX (start of text) and ETX (end of text).  The SOH (start of header) field serves much the same purpose as the STX field.  The problem with the sentinel approach, of course, is that the ETX character might appear in the data portion of the frame.  BISYNC overcomes this problem by "escaping" the ETX character by preceding it with a DLE (data-link-escape) character whenever it appears in the body of a frame; the DLE character is also escaped (by preceding it with an extra DLE) in the frame body. This approach is often called byte stuffing or character stuffing because extra characters are inserted in the data portion of the frame. Example CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 23  PPP - Point-to-Point Protocol (PPP):  It is similar to BISYNC in that it uses character stuffing. The format for a PPP frame is given below.  The special start-of-text character, denoted as the Flag field is 01111110, which is byte stuffed if it occurs within the payload field.  The Address and Control fields usually contain default values.  The Address field which is always set to the binary value 11111111, indicates that all stations are to accept the frame. This value avoids the issue of using data link addresses.  The default value of the Control field is 00000011. This value indicates an unnumbered frame. In other words, PPP does not provide reliable transmission using sequence numbers and acknowledgements.  The Protocol field is used for demultiplexing. It identifies the high-level protocol such as IP or IPX (an IP-like protocol developed by Novell).  The frame payload size can be negotiated, but it is 1500 bytes by default.  The Checksum field is either 2 (by default) or 4 bytes long.  The PPP frame format is unusual in that several of the field sizes are negotiated rather than fixed.  This negotiation is conducted by a protocol called LCP (Link Control Protocol). PPP and LCP work in tandem: LCP is also involved in establishing a link between two peers when both sides detect the carrier signal. Byte-counting approach DDCMP protocol – Digital Data Communication Message Protocol:  The COUNT field specifies how many bytes are contained in the frame's body.  One danger with this approach is that a transmission error could corrupt the COUNT field, in which case the end of the frame would not be correctly detected.This is sometimes called a framing error.  The receiver will then wait until it sees the next SYN character to start collecting the bytes that make up the next frame. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 24 Bit-Oriented Protocols (HDLC)  A bit oriented protocol is not concerned with byte boundaries—it simply views the frame as a collection of bits.  The Synchronous Data Link Control (SDLC) protocol developed by IBM is an example of a bit-oriented protocol; SDLC was later standardized by the ISO as the High-Level Data Link Control (HDLC) protocol.  HDLC denotes both the beginning and the end of a frame with the distinguished bit sequence 01111110.  This sequence is also transmitted during any times that the link is idle so that the sender and receiver can keep their clocks synchronized.  Because this sequence might appear anywhere in the body of the frame—in fact, the bits 01111110 might cross byte boundaries—bit-oriented protocols use a technique known as bit stuffing. Bit stuffing in the HDLC protocol works as follows.  On the sending side, whenever 0 followed by five consecutive 1’s has been seen in the body of the message the sender inserts a 0.  On the receiving side, when 0 followed by five consecutive l’s arrive, the receiver makes its decision based on the next bit it sees (i.e., the bit following the five 1’ s).  If the next bit is 0, it must have been stuffed, and so the receiver removes it.  If the next bit is a 1, then one of two things is true: Either this is the end-of frame marker or an error has been introduced into the bit stream. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 25 Clock based Protocols Clock-Based Framing (SONET):  A third approach to framing is exemplified by the Synchronous Optical Network (SONET) standard.  SONET addresses both the framing problem and the encoding problem.  It also addresses a problem that is very important for phone companies—the multiplexing of several low-speed links onto one high-speed link.  No bit stuffing is used, so that a frame’s length does not depend on the data being sent.  A STS-1 (lowest-speed SONET link runs at 51.84 Mbps.) frame is shown in Figure 2.13.  It is arranged as nine rows of 90 bytes each.  The first 3 bytes of each row are overhead, with the rest being available for data that is being transmitted over the link.  The first 2 bytes of the frame contain a special bit pattern, and it is these bytes that enable the receiver to the receiver looks for the special bit pattern consistently, hoping to see it appearing once every 810 bytes, since each frame is 9 × 90 = 810 bytes long.  When the special pattern turns up in the right place enough times, the receiver concludes that it is in sync and can then interpret the frame correctly. Fig : A SONET STS-1 Frame For example, 64 Kbps of a SONET link’s capacity is set aside for a voice channel that is used for maintenance. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 26 The overhead bytes of a SONET frame are encoded using Non Return to Zero (NRZ), the simple encoding described in the previous section where 1s are high and 0s are low. However, to ensure that there are plenty of transitions to allow the receiver to recover the sender’s clock, the payload bytes are scrambled. This is done by calculating the exclusive-OR (XOR) of the data to be transmitted and by the use of a well-known bit pattern. The bit pattern, which is 127 bits long, has plenty of transitions from 1 to 0, so that XORing it with the transmitted data is likely to yield a signal with enough transitions to enable clock recovery. Fig : Three STS-1 Frames multiplexed onto one STS-3c frame. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 27  ERROR DETECTION AND CORRECTION ERROR Data can be corrupted during transmission. Signals flows from one point to another. They are subjected to unpredictable interferences from heat, magnetism and other forms of electricity. For reliable communication, errors must be detected and corrected. TYPES OF ERRORS  Single bit Error: The term single bit error means that only one bit of a given data unit is changed from 1 to 0 or 0 to 1. 010101 is changed to 110101 here only one bit is changed by single bit error.  Burst Error: A burst error means that 2 or more bits in the data unit have changed. Example: Here two bits are corrupted. Errors can happen in the following ways,  The bits in the frame can be inverted, anywhere within the frame including the data bits or the frame's control bits.  Additional bits can be inserted into the frame, before the frame or after the frame and  Bits can be deleted from the frame. ERROR DETECTION Redundancy Error detection use the concept of redundancy, which means adding extra bits for detecting errors.i.e., instead of repeating the entire data stream, a shorter group of bits may be appended to the end of each unit. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 28 Error Detection methods 1. Parity check o Simple parity check ( Vertical Redundancy Check) o Two dimensional Parity Check (Longitudinal Redundancy Check) 2. Cyclic redundancy check 3. Checksum Parity check A redundant bit called parity bit, is added to every data unit so that the total number of 1’s in the unit becomes even (or odd). Simple parity check ( Vertical Redundancy Check) Sender Side: In a simple parity check a redundant bit is added to a stream of data so that total number of 1’s in the data become even or odd. Receiver Side: The total data bit+ Redundant bit is then passed through parity checking function. For even parity, it checks for even number of 1’s and for odd parity it checks even number of 1’s. If the check fails, it implies error is detected the data is rejected otherwise accepted. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 29 Note :  Simple parity check can detect all single-bit errors. It can detect burst errors only if the total number of bits changed in each data unit is odd. Two dimensional Parity Check (Longitudinal Redundancy Check) In two-dimensional parity check, a block of bits is divided into rows to form a 2-dimensional array; add single parity check bits to each row and each column; transmit row-by-row. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 30  Example 2 CYCLIC REDUNDANCY CHECK (CRC) CRC is based on binary division. In CRC, a sequence of redundant bits, called the CRC or the CRC remainder is generated by performing binary division (using a predetermined divisor) and it is appended to the end of the data unit at the sender side. At the receiver side, if the resulting unit (data + CRC) becomes exactly divisible by the same predetermined binary number (divisor) , the data is accepted. If a remainder results it indicates that the data unit has been damaged in transit and therefore must be rejected. STEP BY STEP PROCEDURE  First a starting of n 0’s is appended to the data unit. The number n is one less than the number of bits in the predetermined divisor, which is n+ 1 bit.  The newly elongated data unit is divided by the divisor, using a process called binary division. The remainder resulting from this division is the CRC.  The CRC of n bits derived in step 2 replaces the appended 0s at the end of the data unit and the data is transmitted.(Note: CRC can also be all 0’s)  The data unit arrives at the receiver data first, followed by the CRC. The receiver treats the whole stream as unit and divides it by the same divisor that was used to find the CRC remainder.  If the string arrives without error, the CRC checker yields a remainder of zero and the data unit passes. If the stream has been changed in transit, the division yields a non zero remainder and the data does not pass. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 31  Figure : CRC generator and checker CRC GENERATOR AND CHECKER Example: Data is 100100 and Divisor is 1101 CRC GENERATOR It uses modulo-2 division. The following figure shows this process. CRC CHECKER  A CRC checker function is exactly as the generator does. After receiving the data appended with the CRC, it does the same modulo-2 division.  If the remainder is all 0s, the CRC is dropped and the data are accepted; otherwise, the received stream of bits is discarded and data are resent.  The following figure shows the process of division in the receiver. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 32 POLYNOMIALS The divisor in the CRC most often represented not as a string of 1s and 0s, but as an algebraic polynomial. The polynomial format is useful to solve the concept mathematically. 7 5 2 x +x +x +x+1 A polynomial x7+x5+x2+x+1 101 0 01 1 1 1010 0 1 1 1 The polynomial generator should have following properties: 1. It should have at least two terms. 2. The coefficient of the term x0 should be 1. 3. It should not be divisible by x. 4. It should be divisible by x+ 1. There are several different standard polynomials used by popular protocols for CRC generation. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 33 CRC Performance  All burst errors with length less than or equal to the degree of the polynomial (r)  CRC can detect all burst errors that affect an odd number of bits  CRC can detect all burst errors of length equal to the degree of the polynomial+1 (r+1) with probability 1 – (1/2)r–1.  CRC can detect burst errors of length greater than the degree of the polynomial+1 (r+1) with probability 1 – (1/2)r (where r is the degree of the CRC polynomial) CHECKSUM The checksum is based on the redundancy. CHECKSUM GENERATOR (sender side) 1. The message is divided into 16-bit words. 2. The value of the checksum word is set to 0. 3. All words including the checksum are added using one’s complement addition. 4. The sum is complemented and becomes the checksum (redundancy bits). 5. The checksum is sent with the data across the network CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 34 CHECKSUM CHECKER (receiver side) 1. The message (including checksum) is divided into 16-bit words. 2. All words are added using one’s complement addition. 3. The sum is complemented and becomes the new checksum. 4. If the value of checksum is 0, the message is accepted; otherwise, it is rejected. EXAMPLE Suppose the block of 16 bits is to be sent using a checksum of 8 bits. 10101001 00111001 the numbers are added using one’s complement arithmetic 10101001 block 1 00111001 block 2 11100010 00000000 initial checksum _ 11100010 sum 00011101 Checksum ( 1’s complement value of sum ) The data sent it is 10101001 00111001 00011101 Now the receiver receives the pattern with no error 10101001 00111001 00011101 the receiver adds these three sections, it will get all ones, which, after complementing, is all 0s and shows that there is no error. 10101001 00111001 00011101 11111111 sum 00000000 complement (DATA is correct ) suppose there is a burst error of length 5 that affects four bits. 10101111 11111001 00011101 when the receiver adds these sections, it gets 10101111 11111001 (1)1 0 1 0 1 0 0 0 1 (carry 1) 1010100 1 00011101 1 1 0 0 0 1 1 1 (carry 1) CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 35  1 1 0 0 0 1 0 1 sum 0 0 1 1 1 0 0 0 complement As the complement is non zero we assume that (the data is errored) Example 2: PERFORMANCE  It detects all errors involving an odd number of bits as well as most errors involving an even number of bits.  If one or more bits of a segment are damaged and the corresponding bit or bits of opposite value in the second segment are also damaged, the sum of those columns will not change and the receiver will not detect the problem. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 36  Error correction Two methods 1. Retransmission after detecting error -retransmit the data if error is detected 2. Forward error correction (FEC) -hamming code is used to correct the error HAMMING CODE  A minimum number of redundancy bits needed to correct any single bit error in the data  A minimum of 4 redundancy bits is needed if the number of data bits is 4.  Redundancy bits in the Hamming code are placed in the codeword bit positions that are a power of 2  Each redundancy bit is the parity bit for a different combination of data bits  Each data bit may be included in more than one parity check.  But the r bits are also transmitted along with data; hence  Number of Redundant Bits Number of Number of Total redundancy data bits bits bits k k+r r 1 2 3 2 3 5 3 3 6 4 3 7 5 4 9 6 4 10 7 4 11 CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 37  Redundant Bit Calculation For r1, The bits considered are -1,3,5,7,9,11(to decide on these bits, follow this trick, since r1 bit, start from 1st bit, take one and leave one and so on) For r2, The bits considered are -2,3,6,7,10,11(to decide on these bits, follow this trick, since r2 bit, start from 2nd bit, take two and leave two and so on) For r4, The bits considered are -4,5,6,7(to decide on these bits, follow this trick, since r4 bit, start from 4th bit, take four and leave four and so on) For r8, The bits considered are -8,9,10,11(to decide on these bits, follow this trick, since r8 bit, start from 8th bit, take eight and leave eight and so on) CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 38  Example: Hamming Code Example: Correcting Error Receiver receives 10010100101 CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 39  FLOW CONTROL (RELIABLE TRANSMISSION) Flow control is a technique used for the following reasons, ◦ If sender sends frames faster than recipient processes, then buffer overflow occurs at the receiver side. ◦ Receiver needs some time to process incoming frames. Flow control coordinates the amount of data that can be sent before receiving acknowledgement from the receiver. It is one of the most important duties of the data link layer. Flow control Refers to a set of procedures used to restrict the amount of data that the sender can send before waiting for acknowledgment from the receiver. ACK  An acknowledgement (ACK for short) is a small control frame that a protocol sends back to its peer saying that it has received the earlier frame. ◦ A control frame is a frame with header only (no data). ◦ The receipt of an acknowledgement indicates to the sender of the original frame that its frame was successfully delivered. MECHANISMS 1. Stop and Wait Protocol  Idea of stop-and-wait protocol is straightforward.  After transmitting one frame, the sender waits for an acknowledgement before transmitting the next frame.  If the acknowledgement does not arrive after a certain period of time, the sender times out and retransmits the original frame. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 40 Timeline showing 4 different scenarios for the stop-and-wait algorithm a) The ACK is received before the timer expires; b) the original frame is lost; c) the ACK is lost; d) the timeout fires too soon Fig: illustrates four different scenarios that result from the basic algorithm. The sending side is represented on the left, the receiving side is depicted on the right, and time flows from top to bottom. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 41  In Fig (a) ACK is received before the timer expires, (b) and (c) show the situation in which the original frame and the ACK, respectively, are lost, and (d) shows the situation in which the timeout fires too soon..  Suppose the sender sends a frame and the receiver acknowledges it, but the acknowledgment is either lost or delayed in arriving. This situation is in (c) and (d). In both cases, the sender times out and retransmit the original frame, but the receiver will think that it is the next frame, since it correctly received and acknowledged the first frame.  This makes the receiver to receive the duplicate copies. To avoid this two sequence numbers (0 and 1) must be used alternatively. The main drawback of the stop-and-wait algorithm is that it allows the sender have only one outstanding frame on the link at a time. 2. Sliding Window  The sender can transmit several frames before needing an acknowledgement.  Frames can be sent one right after another meaning that the link can carry several frames at once and it s capacity can be used efficiently.  The receiver acknowledges only some of the frames, using a single ACK to confirm the receipt of multiple data frames  Sliding Window refers to imaginary boxes at both the sender and the receiver.  Window can hold frames at either end and provides the upper limit on the number of frames that can be transmitted before requiring an acknowledgement.  Frames are numbered modulo-n which means they are numbered from 0 to n-1  For eg. If n=8 the frames are numbered 0,1,2,3,4,5,6,7. i.e the size of the window is n -1.  When the receiver sends ACK it includes the number of the next frame it expects to receive.  When the sender sees an ACK with the number 5, it knows that all frames up CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 42  through number 4 have been received. Sliding Window Sender Sliding Window Receiver Sliding Window CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 43 CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 44  UNIT-II MEDIA ACCESS AND INTERNETWORKING Media Access Protocols – ALOHA - CSMA/CA/CD –Ethernet – Wireless LANs - 802.11- Bluetooth - Switching and Forwarding - Bridges and LAN Switches – Basic Internetworking- IP Service Model – IP fragmentation - Global Addresses – ARP - DHCP – ICMP- Virtual Networks and Tunnels. Media access control The data link layer is divided into two sub layers, 1. Logical link Control Layer 2. Medium Access Control Layer Logical Link Control Layer: The LCL layer is concerned with managing traffic (flow and error control) over the physical medium and may also assign sequence numbers to frames and track acknowledgements. Medium Access Control Layer: Media Access Control layer is one of two sublayers of the Data Link Control layer and is concerned with sharing the physical connection to the network among several computers. Medium Access Control:  Problem: When two or more nodes transmit at the same time, their frames will collide and the link bandwidth is wasted during collision How to coordinate the access of multiple sending/receiving nodes to the shared link???  Solution: We need a protocol to coordinate the transmission of the active nodes CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 45   These protocols are called Medium or Multiple Access Control (MAC) Protocols belong to a sublayer of the data link layer called MAC (Medium Access Control)  What is expected from Medium Access Control Protocols: 1. Main task is to minimize collisions in order to utilize the bandwidth by: 2. Determining when a station can use the link (medium) 3. what a station should do when the link is busy 4. what the station should do when it is involved in collision 5. To avoid the multiple access problem is used in which the station is forced to sense the medium before transmitting. This is called as Carrier Sense Multiple Access (CSMA). The two commonly used medium access protocols are 1. ALOHA 2. CSMA 3. CSMA/Collision Detection (CSMA/CD) 4. CSMA/Collision Avoidance(CSMA/CA) ALOHA PURE ALOHA  Each source (transmitter) in a network sends data whenever there is a frame to send.  If the frame successfully reaches the destination (receiver), the next frame is sent.  When two or more stations transmit simultaneously, there is collision and the frames are destroyed.  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. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 46 SLOTTED ALOHA The time of the shared channel is divided into discrete intervals called slots The stations can send a frame only at the beginning of the slot and only one frame is sent in each slot. In slotted ALOHA, if any station is not able to place the frame onto the channel at the beginning of the slot i.e. it misses the time slot then the station has to wait until the beginning of the next time slot. In slotted ALOHA, there is still a possibility of collision if two stations try to send at the beginning of the same time slot CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 47  CSMA (Carrier Sense Multiple Access) CSMA is based on the principle “Sense Before Transmit or Listen Before Talk. Each station must listen before transmitting.  If a frame was sent by a station, All stations knows immediately so they can wait before start sending  A station with frames to be sent, should sense the medium for the presence of another transmission (carrier) before it starts its own transmission CSMA can reduce the possibility of collision but it cannot eliminate it. Collision can only happen when more than one station begin transmitting within a short time (the propagation time period) The possibility of collision still exists because of propagation delay; when a station sends a frame, it still takes time (although very short) for the first bit to reach every station and for every station to sense it. In other words, a station may sense the medium and find it idle, only because the first bit sent by another station has not yet been received. Vulnerable time Vulnerable time for CSMA is the maximum propagation time  The longer the propagation delay, the worse the performance of the protocol because of the above case. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 48   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. Figure shows the worst case. The vulnerable time for CSMA is the propagation time tp.  The leftmost station A sends a frame at time t1 which reaches the rightmost station D at time t1+ tp. The gray area shows the vulnerable area in time and space. Types of CSMA Protocols Different CSMA protocols that determine:  What a station should do when the medium is idle?  What a station should do when the medium is busy? The channel can access the medium using any of three persistence methods, 1. Non-Persistent CSMA 2. 1-Persistent CSMA 3. p-Persistent CSMA No persistent CSMA  A station with frames to be sent, should sense the medium 1. If medium is idle, transmit; otherwise, go to 2 2. If medium is busy, (backoff) wait a random amount of time and repeat 1  Non-persistent Stations are deferential (respect others)  Performance: 1. Random delays reduces probability of collisions because two stations with data to be transmitted will wait for different amount of times. 2. Bandwidth is wasted if waiting time (backoff) is large because medium will remain idle following end of transmission even if one or more stations have frames to send CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 49 1-persistent CSMA To avoid idle channel time, 1-persistent protocol used Station wishing to transmit listens to the medium: 1. If medium idle, transmit immediately; 2. If medium busy, continuously listen until medium becomes idle; then transmit immediately with probability 1  Performance  1-persistent stations are selfish  If two or more stations becomes ready at the same time, collision guaranteed P-persistent CSMA Time is divided to slots where each Time unit (slot) typically equals maximum propagation delay Station wishing to transmit listens to the medium: 1. If medium idle,  transmit with probability (p), OR  wait one time unit (slot) with probability (q= 1 – p), then repeat 1. 2. If medium busy, continuously listen until idle and repeat step 1 3. Performance  Reduces the possibility of collisions like nonpersistent  Reduces channel idle time like 1-persistent CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 50 Flow diagram for three persistence methods CSMA/CD (CSMA - Collision Detection)  CSMA (all previous methods) has an inefficiency:  If a collision has occurred, the channel is unstable until colliding packets have been fully transmitted  CSMA/CD (Carrier Sense Multiple Access with Collision Detection) overcomes this as follows:  While transmitting, the sender is listening to medium for collisions.  Sender stops transmission if collision has occurred reducing channel wastage. CSMA/CD is Widely used for bus topology LANs (IEEE 802.3, Ethernet). CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 51  Collision of the first bit in CSMA/CD 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 Figure , stations A and C are involved in the collision. 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 ofA'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 ofC'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' Later we show that, for the protocol to work, the length of any frame divided by the bit rate in this protocol must be more than either of these durations. At time t4, the transmission ofA:s frame, though incomplete, is aborted; at time t 3 , the transmission ofB's frame, though incomplete, is aborted. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 52  CSMA/CA (CSMA – Collision Avoidance) Carrier Sense Multiple Access with Collision Avoidance Used in a network where collision cannot be detected E.g., wireless LAN Collisions are avoided in CSMA / CD using three strategies, 1. Inter Frame Space [IFS] 2. Contention window 3. Acknowledgements CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 53 Inter Frame Sequence [IFS] Collisions are avoided by transmitting if a channel is found idle If the channel is found idle, the station does not send immediately It waits for a period of time called interframe space (IFS) Contention window contention window is an amount of time divided into slots. The 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 binary exponential back off ie) it is set to one slot the first time and then doubles each time the station cannot detect an idle channel. 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 Acknowledgements Collisions can be avoided by setting positive acknowledgements to assure that the receiver has received the frame or not. Flow Diagram for CSMA / CA: CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 54  Ethernet (802.3) Wired LAN Most successful local area networking technology of last 20 years. Ethernet is a multiple access network with a set of nodes that send and receive frames over a shared link. Uses CSMA/CD technology – Carrier Sense Multiple Access with Collision Detection. – A set of nodes send and receive frames over a shared link. – Carrier sense means that all nodes can distinguish between an idle and a busy link. – Collision detection means that a node listens as it transmits and can therefore detect when a frame it is transmitting has collided with a frame transmitted by another node. Ethernet can operate at A SPEED - 100 Mbps (Fast Ethernet) - 1000 Mbps (Gigabit Ethernet) Ethernet also used in full duplex, point-to-point configuration Physical Properties An Ethernet segment is implemented on a coaxial cable of up to 500 m. Hosts connect to an Ethernet segment by tapping into it. A transceiver (a small device directly attached to the tap) detects when the line is idle and drives signal when the host is transmitting. The transceiver also receives incoming signal. The transceiver is connected to an Ethernet adaptor which is plugged into the host. The protocol is implemented on the adaptor. Multiple Ethernet segments Can be joined together by repeaters. A repeater is a device that strengthens and forwards weakened digital signals. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 55. Any signal placed on the Ethernet by a host is broadcast over the entire network – Signal is propagated in both directions. – Repeaters forward the signal on all outgoing segments. – Terminators attached to the end of each segment absorb the signal. 10Base5 cable. 10Base5 cable or "Thick Ethernet" or Thicknet is the cable which is the oldest in the category. it is called as thicknet because of the use of thick coaxial cable. The cable is marked after each 2.5 meters. 10Base2 Cable. 10Base2 cable also called "Thin Ethernet" or Thinnet or cheapnet or cheapernet, was designed after the thick Ethernet cable. This type of cable is usually thin, flexible and bends easily. It also make use of bus topology. It is also a coaxial cable that is having a smaller diameter than the 10Base5 cable. 10BaseT Cable. l0BaseT cable or "Twisted Pair" Cable is cheapest and easiest to maintain. This type of cabling is most popular among local area networks. It make use of unshielded twisted pair and provides maximum segment length of 100 m. It make use of start topology. In this type of network, every station is having a wired link to a central device, called "Hub". l0BaseF Cable. 10BaseF cable or "Fiber Optics Cable" is the most efficient and fastest cable in the category of cables for 802 LANs. The fiber optic cable is very expensive as compared to above discussed cables but it offers a very high data transmission speed and noise immunity. This type of cabling is preferred for running networks between buildings or widely separated hubs. It has the highest length per cable segment i.e. 2000 meters and it can support 1024 nodes per cable segment. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 56 Ethernet Frame Format Preamble (64bit): - allows the receiver to synchronize with the signal. (sequence of alternating 0s and 1s). Host and Destination Address physical addresses of the nodes(48bit each). Packet type (16bit): - acts as demux key to identify the higher level protocol Data (up to 1500 bytes) - Minimally a frame must contain at least 46 bytes of data. Frame must be long enough to detect collision. CRC (32bit) - error detection Ethernet Addresses Each host on an Ethernet (in fact, every Ethernet host in the world) has a unique Ethernet Address. The address belongs to the adaptor, not the host. – It is usually burnt into ROM. Ethernet addresses are typically printed in a human readable format – As a sequence of six numbers separated by colons. – Each number corresponds to 1 byte of the 6 byte address and is given by a pair of hexadecimal digits, one for each of the 4-bit nibbles in the byte – For example, 8:0:2b:e4:b1:2 is 00001000 00000000 00101011 11100100 10110001 00000010 To summarize, an Ethernet adaptor receives all frames and accepts – Frames addressed to its own address – Frames addressed to the broadcast address – Frames addressed to a multicast addressed if it has been instructed Ethernet Transmitter Algorithm Algorithm is defined as follows,“When the adaptor has a frame to send and theline is idle, it transmits the frame immediately” When the adaptor has a frame to send and the line is busy, it waits for the line to go idle and then transmits immediately. The Ethernet is said to be 1-persistent protocol because an adaptor with a frame to send transmits with probability 1 whenever a busy line goes idle.When this happens, the two (or more) frames are said to be collide on the network. Since Ethernet supports collision detection, each sender is able to determine that a collision is in progress. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 57  At the moment an adaptor detects that its frame is colliding with another, it first makes sure to transmit a 32-bit jamming sequence and then stops transmission. Thus, a transmitter will minimally send 96 bits in the case of collision 64-bit preamble + 32-bit jamming sequence One way that an adaptor will send only 96 bit (called a runt frame) is if the two hosts are close to each other. Had they been farther apart,They would have had to transmit longer, and thus send more bits, before detecting the collision. The worst case scenario happens when the two hosts are at opposite ends of the Ethernet. To know for sure that the frame its just sent did not collide with another frame, the transmitter may need to send as many as 512 bits. Every Ethernet frame must be at least 512 bits (64 bytes) long. 14 bytes of header + 46 bytes of data + 4 bytes of CRC Ethernet Transmitter Algorithm A begins transmitting a frame at time t d denotes the one link latency The first bit of A’s frame arrives at B at time t + d Suppose an instant before host A’s frame arrives, host B begins to transmit its own frame B’s frame will immediately collide with A’s frame and this collision will be detected by host B Host B will send the 32-bit jamming sequence Host A will not know that the collision occurred until B’s frame reaches it, which will happen at t + 2 * d Host A must continue to transmit until this time in order to detect the collision Host A must transmit for 2 * d to be sure that it detects all possible collisions Worst-case scenario: (a) A sends a frame at time t; (b) A’s frame arrives at B at time t + d; (c) B begins transmitting at time t + d and collides with A’s frame; (d) B’s runt (32-bit) frame arrives at A at time t + 2d. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 58  Once an adaptor has detected a collision, and stopped its transmission, it waits a certain amount of time and tries again. Each time the adaptor tries to transmit but fails, it doubles the amount of time it waits before trying again. This strategy of doubling the delay interval between each retransmission attempt is known as Exponential Backoff. Wireless LAN (IEEE 802.11) / Wi-Fi 1. Wireless networking that is Standard IEEE 802.11 is a rapidly evolving technology for connecting computers. It is also known as Wi-Fi. 2. Like Ethernet and token ring siblings, 802.11 is designed for use in a limited geographical area (homes, office buildings, campuses) Protocol Architecture Physical Layer Properties: 802.11 runs over six different physical layer protocols (so far). Five are based on spread spectrum radio, and one on diffused infrared. The fastest runs at a maximum of 54 Mbps. Original 802.11 standard defined two radio-based physical layer standard – One using the frequency hopping Over 79 1-MHz-wide frequency bandwidths – Second using direct sequence Using 11-bit chipping sequence – Both standards run in the 2.4-GHz and provide up to 2 Mbps CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 59  Then physical layer standard 802.11b was added – Using a variant of direct sequence 802.11b provides up to 11 Mbps – Uses license-exempt 2.4-GHz band Then came 802.11a which delivers up to 54 Mbps using OFDM – 802.11a runs on license-exempt 5-GHz band Most recent standard is 802.11g which is backward compatible with 802.11b – Uses 2.4 GHz band, OFDM and delivers up to 54 Mbps Example of a wireless network: IEEE 802.11 Multiple Access Collision Avoidance (MACA) Multiple Access with Collision Avoidance (MACA) is a protocol for slotted media access control used in wireless LAN data transmission. MACA is used to avoid data collisions caused by hidden station problems as well as simplifying known station problems. Hidden nodes problem Suppose both A and C want to communicate with B and so they each send it a frame. – A and C are unaware of each other since their signals do not carry that far – These two frames collide with each other at B But unlike an Ethernet, neither A nor C is aware of this collision – A and C are said to hidden nodes with respect to each other CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 60  Key Idea-Solution – Sender and receiver exchange control frames with each other before the sender actually transmits any data. – This exchange informs all nearby nodes that a transmission is about to begin – Sender transmits a Request to Send (RTS) frame to the receiver. The RTS frame includes a field that indicates how long the sender wants to hold the medium -Length of the data frame to be transmitted – Receiver replies with a Clear to Send (CTS) frame This frame echoes this length field back to the sender – Any node that sees the CTS frame knows that – it is close to the receiver, therefore – cannot transmit for the period of time it takes to send a frame of the specified length – Any node that sees the RTS frame but not the CTS frame – is not close enough to the receiver to interfere with it, and – so is free to transmit Exposed node problem Another problem called exposed node problem occurs – Suppose B is sending to A. Node C is aware of this communication because it hears B’s transmission. – It would be a mistake for C to conclude that it cannot transmit to anyone just because it can hear B’s transmission. – Suppose C wants to transmit to node D. – This is not a problem since C’s transmission to D will not interfere with A’s ability to receive from B. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 61 Solution for exposed node problem: MACA: Medium Access Collision Avoidance: MACA is for Wireless LANs – Receiver sends an ACK to the sender after successfully receiving a frame – All nodes must wait for this ACK before trying to transmit – If two or more nodes detect an idle link and try to transmit an RTS frame at the same time – Their RTS frame will collide with each other – 802.11 does not support collision detection – So the senders realize the collision has happened when they do not receive the CTS frame after a period of time – In this case, they each wait a random amount of time before trying again. – The amount of time a given node delays is defined by the same exponential backoff algorithm used on the Ethernet. – 802.11 is suitable for an ad-hoc configuration of nodes that may or may not be able to communicate with all other nodes. – Nodes are free to move around CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 62  – The set of directly reachable nodes may change over time – To deal with this mobility and partial connectivity, – 802.11 defines additional structures on a set of nodes – Instead of all nodes being created equal, some nodes are allowed to roam some are connected to a wired network infrastructure - they are called Access Points (AP) and they are connected to each other by a so- called distribution system IEEE 802.11 – Distribution System Following figure illustrates a distribution system that connects three access points, each of which services the nodes in the same region Each of these regions is analogous to a cell in a cellular phone system with the APIs playing the same role as a base station The distribution network runs at layer 2 of the ISO architecture Although two nodes can communicate directly with each other if they are within reach of each other, the idea behind this configuration is – Each nodes associates itself with one access point – For node A to communicate with node E, A first sends a frame to its AP-1 which forwards the frame across the distribution system to AP-3, which finally transmits the frame to E The technique for selecting an AP is called scanning – The node sends a Probe frame – All APs within reach reply with a Probe Response frame – The node selects one of the access points and sends that AP an Association Request frame – The AP replies with an Association Response frame A node engages this protocol whenever – it joins the network, as well as – when it becomes unhappy with its current AP This might happen, for example, because the signal from its current AP has weakened due to the node moving away from it Whenever a node acquires a new AP, the new AP notifies the old AP of the change via the distribution system CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 63 Node Mobility Consider the situation shown in the following figure when node C moves from the cell serviced by AP-1 to the cell serviced by AP-2. As it moves, it sends Probe frames, which eventually result in Probe Responses from AP-2. At some point, C prefers AP-2 over AP-1 , and so it associates itself with that access point. – This is called active scanning since the node is actively searching for an access point APs also periodically send a Beacon frame that advertises the capabilities of the access point; these include the transmission rate supported by the AP – This is called passive scanning – A node can change to this AP based on the Beacon frame simply by sending it an Association Request frame back to the access point. IEEE 802.11 – Frame Format Source and Destinations addresses: each 48 bits Data: up to 2312 bytes CRC: 32 bit Control field: 16 bits – Contains three subfields (of interest) 6 bit Type field: indicates whether the frame is an RTS or CTS frame or being used by the scanning algorithm A pair of 1 bit fields : called ToDS and FromDS Addr1 – target node Addr2 – immediate sender Addr3 – intermediate destination node Addr4 – original source CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 64  Bluetooth (802.15.1) Bluetooth is a wireless LAN technology designed to connect devices of different functions such as telephones, notebooks, computers, cameras, printers, coffee makers, and so on. A Bluetooth LAN is an ad hoc network, which means that the network is formed spontaneously. Used for very short range communication between mobile phones, PDAs, notebook computers and other personal or peripheral devices. Bluetooth is an adhoc network which means the network is formed spontaneously ie the devices find each other and make a network called piconet. Has a range of only 10 m Communication devices typically belong to one individual or group – Sometimes categorized as Personal Area Network (PAN) Version 2.0 provides speeds up to 2.1 Mbps Power consumption is low Bluetooth is specified by an industry consortium called the Bluetooth Special Interest Group It specifies an entire suite of protocols, going beyond the link layer to define application protocols, which it calls profiles, for a range of applications – There is a profile for synchronizing a PDA with personal computer – Another profile gives a mobile computer access to a wired LAN The basic Bluetooth network configuration is called a piconet – Consists of a master device and up to seven slave devices – Any communication is between the master and a slave – The slaves do not communicate directly with each other – A slave can be parked: set to an inactive, low-power state CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 65 Scatternet A scatternet is a number of interconnected piconets that supports communication between more than 8 devices. Scatternets can be formed when a member of one piconet (either the master or one of the slaves) elects to participate as a slave in a second, separate piconet. The device participating in both piconets can relay data between members of both ad hoc networks. Bluetooth layers CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 66 L2CAP Layer - Logical Link Control and Adaptation Layer - Used for data exchange, It can do multiplexing Baseband Layers - Equivalent to MAC sublayer in LAN - The primary and secondary stations communicate with each other using time slots (TDMA-Time Division Multiple Access) Radio layer - Equivalent to physical layer of the internet model. Bluetooth devices are low-power and have a range of 10 m Switch 1. A mechanism that allows us to interconnect links(LANs) to form a large network is called switching. 2. Switches are devices capable of creating temporary connections between two or more devices linked to the switch. 3. A switch’s primary job is to receive incoming packets on one of its links and to transmit them on some other link. This function is referred as switching and forwarding. 4. A multi-input, multi-output device which transfers packets from an input to one or more outputs. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 67  EXAMPLE: Advantages of switches: 1. Large networks can be built by interconnecting a number of switches. 2. We can connect switches to each other and to hosts using point-to-point links, which typically means that we can build networks of large geographic scope. 3. Adding a new host to the network by connecting it to a switch does not necessarily mean that the hosts already connected will get worse performance from the network. 4. A switch is connected to a set of links and for each of these links, runs the appropriate data link protocol to communicate with each node attached on link. Switched networks (switching) Circuit switched networks packet switched networks (Circuit switching) (Packet switching) Datagram networks virtual-circuit network (Datagram approach) (Virtual circuit approach) Circuit switched networks In circuit switched network, it consists of set of switches connected by physical links. A connection between two stations is a dedicated path made of one or more links. Physical layer is responsible for circuit switching. The communication in circuit-switched network has three phases, 1) Connection setup 2) Data transfer 3) Teardown (connection termination) In these types of networks, data are not packetized and there is a continuous flow by the source station to destination station. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 68 Packet switched networks If the message is passing through a packet switched network, it needs to be divided into packets of fixed or variable size. This type of switching is done by network layer. The two approaches commonly used are, Datagram or Connectionless approach Virtual circuit or Connection-oriented approach Datagram approach Every packet contains enough information i.e. destination address that enable any switch to decide where the packet has to go. Consider An example network with many hosts for datagram forwarding, To decide how to forward a packet, a switch consults a forwarding table (sometimes called a routing table) Fig : Datagram forwarding : an example network Characteristics of Connectionless (Datagram) Network A host can send a packet anywhere at any time. When a host sends a packet, it has no way of knowing if the network is capable of delivering it or if the destination host is even up and running. Each packet is forwarded independently of previous packets that might have been sent to the same destination. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 69  Thus two successive packets from host A to host B may follow completely different paths A switch or link failure might not have any serious effect on communication if it is possible to find an alternate route around the failure and update the forwarding table accordingly. Virtual Circuit Switching Widely used technique for packet switching Uses the concept of virtual circuit (VC) Also called a connection-oriented model First set up a virtual connection from the source host to the destination host and then send the data Host A wants to send packets to host B Fig : An example of a virtual circuit network Two-stage process Connection setup Data Transfer Connection setup Establish “connection state” in each of the switches between the source and destination hosts The connection state for a single connection consists of an entry in the “VC table” in each switch through which the connection passes One entry in the VC table on a single switch contains A virtual circuit identifier (VCI) that uniquely identifies the connection at this switch and that will be carried inside the header of the packets that belong to this connection An incoming interface on which packets for this VC arrive at the switch An outgoing interface in which packets for this VC leave the switch A potentially different VCI that will be used for outgoing packets. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 70 Two broad classes of approach to establishing connection state Network Administrator will configure the state The virtual circuit is permanent (PVC) The network administrator can delete this Can be thought of as a long-lived or administratively configured VC A host can send messages into the network to cause the state to be established This is referred as signalling and the resulting virtual circuit is said to be switched (SVC) A host may set up and delete such a VC dynamically without the involvement of a network administrator Let’s assume that a network administrator wants to manually create a new virtual connection from host A to host B First the administrator identifies a path through the network from A to B The administrator then picks a VCI value that is currently unused on each link for the connection For our example, Suppose the VCI value 5 is chosen for the link from host A to switch 1 11 is chosen for the link from switch 1 to switch 2 So the switch 1 will have an entry in the VC table For switch 1 Incoming Interface Incoming VC Outgoing Interface Outgoing VC 2 5 1 11 Similarly, suppose VCI of 7 is chosen to identify this connection on the link from switch 2 to switch 3 VCI of 4 is chosen for the link from switch 3 to host B Switches 2 and 3 are configured with the following VC table CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 71 Switch 2 Incoming Interface Incoming VC Outgoing Interface Outgoing VC 3 11 2 7 Switch 3 Incoming Interface Incoming VC Outgoing Interface Outgoing VC 0 7 1 4 For any packet that A wants to send to B, A puts the VCI value 5 in the header of the packet and sends it to switch 1 Switch 1 receives any such packet on interface 2, and it uses the combination of the interface and the VCI in the packet header to find the appropriate VC table entry. The table entry on switch 1 tells the switch to forward the packet out of interface 1 and to put the VCI value 11 in the header Packet will arrive at switch 2 on interface 3 bearing VCI 11 Switch 2 looks up interface 3 and VCI 11 in its VC table and sends the packet on to switch 3 after updating the VCI value appropriately This process continues until it arrives at host B with the VCI value of 4 in the packet To host B, this identifies the packet as having come from host A CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 72 Data transfer The data transfer phase is active until the source sends all its frame to destination when the connection state is established. Teardown In this phase, source A, after sending all frames to B, sends a special frame called teardown request. Destination B responds with a teardown confirmation frame and all switches delete the corresponding entry from their tables. Source Routing Its a type if less commonly used approach in packet switching All the information about network topology that is required to switch a packet across the network is provided by the source host Circuit switching Packet switching The connection between two station is a Virtual connection is established between dedicated path using physical links two station Physical layer is responsible Network layer is responsible Messages are not packetized and there is Messages are divided into packets of a continuous flow of messages fixed or variable size Used in telephone companies Used in switched WANs such as frame relay and ATM networks - Types are  Datagram approach  Virtual circuit approach  Source routing CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 73  Bridges  Bridge is a connecting device that is used to connect two or more LANs. It operates in both the physical and the data link layer.  As a physical layer device, it regenerates the signal it receives.  As a data link layer device, the bridge can check the physical (MAC) addresses (source and destination) contained in the frame.  Switch that is used to forward packets between shared-media LANs such as Ethernets.  It is also called as LAN switches. Transparent bridges It is a bridge in which the stations are completely unaware of bridge’s existence. If a bridge is added or deleted from the system, reconfiguration is not needed. According to the IEEE 802.1 d specification, a system equipped with transparent bridges must meet three criteria, as follows Functions of bridges (three criteria) 1. Frame filtering or forwarding 2. Learning 3. Avoidance of loops in system Frame filtering or forwarding Bridges has a table which is used for filtering or forwarding decisions. It can check the destination address of frame and decide if the frame has to be forwarded or dropped. If the frame is to be forwarded, the decision must specify the port. CS19541 – CN Units 1 & 2 RAJALAKSHMI ENGINEERING COLLEGE PAGE 74 Let us give an example. In Figure two LANs are connected by a bridge. If a frame destined for station 712B13456142 arrives at port 1, the bridge consults its table to find the departing port. According to its table, frames for 7l2B 13456142 leave through port 1; therefore, there is no need for forwarding, and the frame is dropped. On the other hand, if a frame for 712B13456141 arrives at port 2, the departing port is port 1 and the frame is forwarded. Learning The earliest bridges had forwarding tables that were static. The systems administrator would manually enter each table entry during bridge setup. Although the process was simple, it was not practical. If a station was added or deleted, the table had to be modified manually. The same was true if a station's MAC address changed, which is not a rare event. A better solution to the static table is a dynamic table that maps addresses to ports automatically. To make a table dynamic, we need a bridge that gradually learns from the frame movements. To do this, the bridge inspects both the destination and the source addresses. The destination address is used for the forwarding decision (table lookup); the source address is used for adding entries to the table and for updating purposes. 1. When station A sends a frame to station D, the bridge does not have an entry for either D or A. The frame goes out from all three ports; the frame f