CS601 Short Notes (Handouts) for Final - PDF

CS601 Short Notes(Handouts) Composed By Amir These notes will cover all Final term topics.Including all concepts of PPT slides For short lecture search on Youtube: "CS601 short lecture by Amir" Topi...

CS601 Short Notes(Handouts) Composed By Amir These notes will cover all Final term topics.Including all concepts of PPT slides For short lecture search on Youtube: "CS601 short lecture by Amir" Topics 124-127 Data link Layer , Nodes and Links The Internet is a combination of networks glued together by connecting devices (routers or switches) If a packet is to travel from a host to another host, it needs to pass throughthese networks Data Link layer controls node-to-node communication Data link layer: The data link layer is the second layer of the seven-layer OSI model.This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer provides the functional and procedural means to transfer data between network entities and might provide the means to detect and possibly correct errors that may occur in the physical layer. Data link layer control Node-to-Node communication. Nodes and Links: Communication in data link layer is node to node. We also know about data unit from one point to another point in Internet needs to pass through many networks to reach another point. We refer to the two endpoints that are called hosts and the router as notes and the networks in between as links. Services provided by Data link Layer Data link layer provides the following services: 1. framing 2. flow control 3. error control 4. congestion control Framing: First and foremost function of data link layer is framing. Date link layer divides data packets into small frames. Framing is a primary service of data link layer. In case of framing we gone talk about two processes encapsulation and de capsulation, both combined are call framing. We know that data travel in the form of packets. Data link layer encapsulate this Packets into multiple frames. Encapsulation means breakdown of a packet into multiple frames which is stream of bit for transmission. Data Link Layer is also add its own header to each off frame.When data receive data link layer de-capsulate these frames. It Takes multiple frames and combined it in form of packet. Example of Encapsulation & De Capsulation: Suppose you have to travel from one city to another, the first thing you will do is you will take taxi for railway station and get off here for the train, and get on the train and go to another city. After landing in another city, you will take the taxi again and reach your destination. Flow Control: In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver. It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node. Flow control is important because it is possible for a sending computer to transmit information at a faster rate than the destination computer can receive and process it. This can happen if the receiving computers have a heavy traffic load in comparison to the sending computer, or if the receiving computer has less processing power than the sending computer. Error Control: Data link layer is the layer where deploy some sort of error correction first of all detection and then error correction as well. Congestion control: Congestion control is a method used for monitoring the process of regulating the total amount of data entering the network so as to keep traffic levels at an acceptable value. This is done in order to avoid the telecommunication network reaching. Topic 128 Types of data link layer(DLL) There are two types of DLL: Point-to-point link Broadcast link Point -to-point link: A point-to-point link refers to a communications connection between two communication endpoints or nodes. An example is a telephone call, in which one telephone is connected with one other, and what is said by one caller can only be heard by the other. The term is also used in computer networking and computer architecture to refer to a wire or other connection that links only two computers or circuits, as opposed to other network topologies such as buses or crossbar switches which can connect many communications devices. Point-to-point is sometimes abbreviated as P2P. Broadcast link: Broadcast links connect two or more nodes and support broadcast transmission, where one node can transmit so that all other nodes can receive the same transmission. Ethernet is an example of broadcast. Sub layers of DLL: There are two sub layers of Data link layer: Data link control (DLC): it deals with point-to-point link as well as broadcast link. Media Access Control (MAC): it deals with only broadcast link. For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 129 to 134 Link Adressing Link layer addresses 1. IP addresses: 2. Link layer addresses / physical addresses / MAC addresses: IP Addresses: IP addresses are the identifiers at the network layer in Internet we cannot send a packet to its destination using only IP addresses. Link Layer Addresses: Source and destination IP addresses Define Two ends but cannot Define which links the packet and path will take. Encapsulation and de capsulation processes are involved In these link layer addresses. In process of encapsulation also involve header. This header contains the link layer addresses of the source and destination. Three types of address a. Unicast b. Multicast c. Broadcast Unicast: unicast is one to one communication. Unicast is the term used to describe communication where a piece of information is sent from one point to another point. In this case there is just one sender, and one receiver. Unicast transmission, in which a packet is sent from a single source to a specified destination, is still the predominant form of transmission on LANs and within the Internet. All LANs and IP networks support the unicast transfer mode, and most users are familiar with the standard unicast applications (e.g. http, smtp, ftp and telnet) which employ the TCP transport protocol. Multicast: Multicast is the term used to describe communication where a piece of information is sent from one or more points to a set of other points. In this case there is may be one or more senders, and the information is distributed to a set of receivers. Multicasting is the networking technique of delivering the same packet simultaneously to a group of clients. IP multicast provides dynamic many-to-many connectivity between a set of senders and a group of receivers. Broadcast:  Broadcast is the term used to describe communication where a piece of information is sent from one point to all other points. In this case there is just one sender, but the information is sent to all connected receivers. Address Resolution Protocol (ARP) In networking if a host send data to another host then it must have IP address. This process is done by using DNS. DNS finding IP address of the destination. IP address is good, but it is not enough to find out the destination nodes. In this case IP address is not helpful for moving the frame through different nodes and links that make up the rote from the source to the destination. Here we need address resolution protocol. Address Resolution Protocol (ARP) Operation ARP Operation: ARP broadcast request package to all the machines on LAN and ask if any of the machine know they are using particular IP address. when a Machinery can recognize the IP address as it's own it sends a reply. So to ARP can update the cash for future reference and proceed with communication. ARP request is always broadcast. ARP reply is always Unicast Caching: In caching system A the link layer address of system B once it received. If once store address in cash then all the Future transactions from system A to system B are normally unit cost. For short lecture search on Youtube: "CS601 short lecture by Amir"  Chapter 10 Types of Error Topic 135 – 140 Data transmission suffers unpredictable change because of interference. This interference can change the shape of signal. There are two types of errors: Single bit error Burst error Single bit Error: means that only one bit of given data unit is changed from 1 to 0 or 0to 1. Example: 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 Burst Error: means that two or more bits in data unit have change from 1 to 0 or from 0 to 1. 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 Length of burst error is 8 bits. Number of impacted bits actually depends on two things: Data rate Duration of rate Note: higher data rate cause of more bits impacted. And more duration of noise is source of higher number of bits going to be impacted. Because of these two things burst error is common then single bit error. Redundancy Central concept of detecting or correcting error is redundancy to be able to detect or correct error we send some extra bits with our data. The presence of these redundant bits allowed the receiver to detect or correct corrupted bits. Error detection VS Error correction Error detection is simple while error correction is complex. In error detection we are only looking to see if error has occurred (yes or no). We are not interested in the number of corrupted bits. In error detection single bit error is same as burst errors. Error Correction: In error correction we need to know: The exact numbers of corrupted bits, and The location of corrupted bits. Coding schemes can be derived into two broad categories: Block coding Convolution coding Block coding: In block coding we divide our message into blocks, each of them has ‘k’ bits, called as data word. Here “k” means a certain number of bits. Then we add ‘r’ redundant bits to each block to make the length n = k + r. The resulting ‘n’ bit blocks are called code word. Note: sender sends code words to receiver and receiver checks code words. Block coding in error detecting: If the following two conditions are met, the receiver can detect a change in the original code words: The receiver has a list of valid code words The original code word has changed to an invalid one. Block Coding Let us assume that k = 2 and n = 3, table below shows that list of code word and data word. Letter we will see how to derive a code from a data word. Data word Code word Data word Code word 00 000 10 101 01 011 11 110 Look at 2nd code word that is ‘011’: Let suppose: If receiver get ‘011’ and this is valid code word, then ‘01’ is extracted and it is passed to receiver. If we send ‘011’ and received as ‘000’ this is invalid code word. It is corrupted code word. This will not be processed by the receiver, and this will be discarded. If code word is corrupted during transmission and we receive the corruption of two bits. We receive ‘011’ instead of ‘000’. In this case this matches with a valid code word in given data. For short lecture search on Youtube: "CS601 short lecture by Amir"  topic 141 to 145 Hamming Distance Hamming distance is a metric for comparing two binary data strings. While comparing two binary strings of equal length, Hamming distance is the number of bit positions in which the two bits are different. The Hamming distance between two strings, x and y is denoted as d(x,y). Hamming Distance between receiver code word and sent code word is actually number of bits that are corrupted. Example: 1. d (000, 011) ; 000 is x and 011 is y. d (000, 011); 0 0 0 , 0 1 1 Here hamming distance is 2 because two bits are different: 2. d ( 10101, 11110) => ‘10101’ is x and ‘11110’ is y d(10101, 11110) => 1 0 1 0 1 , 1 1 1 1 0 Here hamming distance is 3 because 3 bits are corrupted: In simple words hamming distance tells us how many bits are corrupted.If d (x,y) ≠ 0 → that means there is an error in our data. Minimum Hamming Distance Minimum Hamming distance is a smallest hamming distance between all possible pair of code words. dmin = s + 1 Where s → no of detected error dmin → minimum hamming distance: Example: A code scheme has a hemming distance dmin=4. This code guarantees the detection. Up how to many errors. dmin = 4 dmin = s + 1 s = dmin - 1 S=4–1 S=3 If you got a block code which has got a minimum hamming distance 4, it means that this block code guarantees error detection up to three bears in the cold word. Linear block code: Is all subsets of block code in which the exclusive OR of two valid code words creates another world code. Data word Code word Data word Code word 00 000 10 101 01 011 11 110 If we do exclusive OR ⊕ between two code words:001 ⊕10 =110 → linear block code. Parity check code Parity check is a simple way to add redundancy bits to the packets such that the total number of 1's is even or odd. Most common error detecting code. Linear block code (n = k + 1). The extra parity bits is selected to make total number of 1s coed word even. Example: C (5, 4) => k= 4, n=5 Data word (k) Code word (n) Data word (k) Code word (n) 0000 00000 1000 10001 0001 00011 1001 10010 0010 00101 1010 10100 0011 00110 1011 10111 0100 01001 1100 11000 1010 10100 1101 11011 0110 01100 1110 11101 0111 01111 1111 11110 n > k → no of code word > no of data word If total number of 1s is odd then our extra parity bit is 1 to make our total number of 1 is even. If the total number of 1s is already even then extract parity bit that we are adding to our code word is 0. CYCLIC CODES: In coding Theory a cyclic code is a block code where the circular shift of each codeword gives another word that belongs to the code. They are error correcting codes that have algebraic properties that are convenient for efficient error detection and correction. Example: CRC  CRC is an error detection technique to detect change to Raw data and is used widely in today's computer networks CRC codes are also known as polynomial codes since it is possible to view thebit string to be sent as a polynomial. Advantages of Cyclic Codes Good performance in detection: Single-bit errors Double errors Odd number of errors Burst errors Easy Implementation Fast Implementation Topic 146 CHECKSUM: A checksum is a small-sized block of data derived from another block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. Error-detection technique that can be applied to a message of any length. Checksum mostly used at the network and transport layer rather than the data-link layer Concept behind Checksum The idea of the traditional checksum is simple. We show this using a simple example: Suppose the message is a list of five 4-bit numbers that we want to send to a destination. In addition to sending these numbers, we send the sum of the numbers. Set of numbers is (7, 11, 12, 0, 6) Example: 7 + 11 + 12 + 0 + 6 = 36 We should to send as follow (7, 11, 12, 0, 6, 36) but here five 4–bit word that are (7, 11, 12, 0, 6) and 36 is not 4 bit number. So for sending 36 with our data we shout convert it 4 bit number first as following method: In the previous example, the decimal number 36 in binary is (100100)2. To change it into a 4-bit number we add the extra leftmost bit to the right four bits as shown below (10)2 + (0100) 2 = (0110) 2 (6) 10 So instead of sending (7, 11, 12, 0, 6, 36) we will send (7, 11, 12, 0, 6, 6) now checksum is in 4 bit form. Now receiver again add these numbers and if the result is 6 then it will accepted otherwise rejected. For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 147-148 Forward Error Correction (FEC)  Retransmission of corrupted and lost packets is not useful for real-time multimedia transmission We need to correct the error or reproduce the packet immediately Several techniques developed and are commonly called Forward Error Correction techniques Using Hamming Distance For error detection, we definitely need more distance It can be shown that to correct ‘t’ errors, we need to have:dmin = 2t + 1 If we want to correct 10 bits in a packet, we need to make the minimum hamming distance 21 bits A lot of redundant bits need to be sent with the data Example: If we want to correct 10 bits in a packet, we need to make the minimum hamming distance 21 bits dmin = 2t + 1 dmin = 2(10) + 1 dmin = 21 this is amount of redundant bits that you send with your data word. Using XOR Another recommendation is to use the property of the exclusive OR operation asshown below. R = P1 + P2 +…+ Pi + … + PN This means: Pi = P1 + P2 +…+ R +...+ PN Chunk Interleaving Another way to achieve FEC in multimedia is to allow some small chunks tobe missing at the receiver We cannot afford to let all the chunks belonging to the same packet bemissing; however, we can afford to let one chunk be missing in each packet. Combining Hamming Distance & Interleaving Hamming distance and interleaving can be combined We can first create n-bit packets that can correct t-bit errors Then we interleave m rows and send the bits column by column Possible to correct burst errors up to m × t bits of errors Compounding High & Low Resolution Packets Creation of a duplicate of each packet with a low-resolution redundancy and combine the redundant version with the next packet. For example, we can create four low-resolution packets out of five high-resolution packets and send them. Topic 149 – 151 Chapter…#11 The data link control (DLC) deals with procedures for communication between two adjacent nodes no matter whether the link is dedicated or broadcast. Data link control functions include framing, flow control and error control. Framing Data-Link layer needs to pack bits into frames. So that each frame is distinguishable from another. Our postal system practices a type of framing. Framing separates a message by adding a sender address and a destination address. The destination address defines where the packet is to go; the sender address helps the recipient acknowledge the receipt. Frame Size Why not one BIG Frame? If we make one big size frame it creates a problem. In case of error if we have one big frame our whole data will be lost. That is why we make number of small frames instead of one big frame. Frames can be of: Fixed Size Size acts as a boundary/delimiter In fix size every frame have same size The problem with fixed size framing is that, error detection, error correction, flow control and all these kind of functions become very difficult. Variable Size How to define Beginning and End of a Frame? In variable-size framing, we need a way to define the end of the frame and the beginning of the next. Historically, two approaches were used for this purpose: a character-oriented approach and a bit-oriented approach. Character-Oriented Protocols: Bit-Oriented Protocols: Topic 151 – 153 Character (Byte) Oriented Protocols : In a character-oriented protocol, data to be carried are 8-bit characters from a coding system such as ASCII. The header, which normally carries the source and destination addresses and other control information. The trailer, which carries error detection or error correction redundant bits, are also multiples of 8 bits.  To separate one frame from the next, an 8-bit (1-byte) flag is added at the beginning and the end of a frame. The flag, composed of protocol-dependent special characters, signals the start or end of a frame. Figure shows the format of a frame in a character-oriented protocol. Character-oriented framing was popular when only text was exchanged by the data link layers. The flag could be selected to be any character not used for text communication. Now, however, we send other types of information such as graphs, audio, and video. Any pattern used for the flag could also be part of the information. If this happens, the receiver, when it encounters this pattern in the middle of the data, thinks it has reached the end of the frame. To fix this problem, a byte stuffing strategy was added to character-oriented framing. Byte stuffing (or character stuffing): In this 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. Of course, the next question is: 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. Major disadvantage of Character-oriented protocols is it use 8-bits characters. The universal coding systems in use today, such as Unicode, have 16-bits and 32- bits characters that conflict with 8-bits characters. Bit-Oriented Protocols: In this data frames contains an arbitrary number of bits and allowscharacter 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 inthe 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 isstuffed into the outgoing character stream before a flag byte in the data. When the receiver sees five consecutive incoming 1 bits, followed by a 0bit, it automatically un 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.  Topic 154 FLOW Control: Balance between production and consumption rates If frames are produced faster than they are consumed at the receiving data link layer, the frames will be discarded Use of buffers; one at sending end and other at receiving end In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver. It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node. Flow control should be distinguished from congestion control, which is used for controlling the flow of data when congestion has actually occurred. Flow control is important because it is possible for a sending computer to transmit information at a faster rate than the destination computer can receive and process it. This can happen if the receiving computers have a heavy traffic load in comparison to the sending computer, or if the receiving computer has less processing power than the sending computer. Example Consumers need to communicate with the producers on two occasions: When the buffer is full; & When there are vacancies If the two parties use a buffer with only one slot, the communication can be easier  Topic 155 Error Control Error Control at Data Link layer uses CRC in one of the two ways: If a frame is corrupted, it is silently discarded and if it is good, it is delivered to network layer. If frame is corrupted, it is silently discarded and if it is good, an acknowledgement is sent to sender that the frame is received safely. Connectionless and Connection-Oriented A DLC protocol can be either connectionless or connection-oriented Connectionless: No relationship between the frames. Connection-Oriented: Frames are numbered and sent in order. Connectionless: All frames are independent. Connectionless doesn't mean that no physical connection between frames, but it means that you don't have any relationship between frames that you are sending so you have one frame for one message and other frame for another message. Connection-Oriented: In this particular case as we discussed in data link layer connection oriented protocol as those that actually establish a connection first, then they do the setup, then they do the data transmission and then they have to do connection dare down. In this particular case the frames are sent in particular order. They have got a transmission with another when a frame is successfully received. Receiver sends acknowledgement back to the sender to tell the sender that this Frame is received successfully and error free now send the Next one.  For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 156 DATA-LINK LAYER PROTOCOLS: Traditionally four protocols have been dsefined for the data-link layer to deal with flow and error control: Simple Protocol Stop-and-Wait Protocol Go-Back-N Protocol Selective-Repeat Protocol Last two protocols have almost disappeared completely Note: Before we have to discussion Data link layer protocol we have to discuss Finite State Machine (FSM). Finite State Machine (FSM) A machine with a finite number of states Machines stays in one of the states until an event occurs Each event is associated with 2 reactions: List of actions to be performed Determining the next state Definition: A state-of-the-art machine is a model of counting based on a fictitious machine consisting of one or more states. Only one mode of this machine can be activated at a time. This means that the machine has to be moved from one state to another to perform various functions. Explanation: Let's supposed the State is standing that is your starting stat you stay at your standing State until a force applied to you. Same concept of FSM it starts from a particular Stat and stay in this stat until a specific event happens. When event is occurred there are two things your FSM does. List of actions to be performed Determining the next state Topic 157 Simple Protocol Simple protocol has neither flow nor error control. Assumption: The receiver can immediately handle any frame it receives. The receiver can never be overwhelmed with incoming frames. FSM for Simple Protocol: Example Here is an example of communication using this protocol. It is very simple. The sender sends frames one after another without even thinking about the receiver. Topic 158 Stop-and-Wait Protocol Stop-and-Wait protocol uses both flow and error control. The sender sends one frame at a time and waits for an acknowledgment before sending the next one.  To detect corrupted frames, we add a CRC code. Acknowledgement caring with two messages: I have received the previous frame please send next one. The frame that we have sent previously he has been received error free. Topic 159 Example:  Topic 160 Piggybacking Both Simple and Stop-and-wait protocols are designed for unidirectional communication Data flows in one direction and ACK travels in the other To make the system efficient, the data in one direction is piggybacked with the acknowledgment in the other direction High-level Data Link Control (HDLC) Bit -oriented protocol for communication over point-to-point and multipoint links It implements Stop-and-Wait protocol Most of the concepts defined in this protocol is the basis for other protocols such as PPP, Ethernet, or wireless LANs Configurations & Transfer Modes in HDLC HDLC provides two common transfer modes that can be used in different configurations: Normal Response Mode (NRM) Asynchronous Balanced Mode (ABM) Normal Response Mode (NRM) Asynchronous Balanced Mode (ABM) Topic 161 HDLC Framing HDLC defines three types of frames: information frames (I-frames) Information frames, or I-frames, transport user data from the network layer. Theycan also include flow and error control information piggybacked on data. Supervisory frames (S-frames) Supervisory frames, or S-frames, are used for flow and error control whenever piggybacking is impossible or inappropriate, such as when a station does not have data to send. S-frames do not have information fields.  Unnumbered frames (U-frames) Unnumbered frames, or U-frames, are used for various miscellaneous purposes, including link management. Some U-frames contain an information field, depending on the type. Topic 162 Point-to-Point Protocol (PPP) Most common protocol for point-to-point access Millions of Internet users who need to connect their home computers to theserver of an Internet service provider use PPP To control and manage the transfer of data, there is a need for a PPP at thedata-link layer For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 163 Services provided by PPP The designers of PPP have included several services to make it suitable for a point-to-point protocol, but have ignored some traditional services to make it simple Link Establishment and Error Correction (PPP hasCRC DataExchange Authentication No Sequence Numbering Multilink PPP Absence of Address sophisticated configuration Addressing Mechanism Network Address configuration PPP Frame Format PPP uses a character-oriented (or byte-oriented) frame T o p i c  1 6 4 Multiplexing in PPP Although PPP is a link-layer protocol, it uses another set of protocols to establish thelink, authenticate and carry the network-layer data Three sets of protocols are: Link Control Protocol (LCP): This is responsible for establishing, maintaining,configuring and terminating our PPP links. Two Authentication Protocols (APs): AP has two types: PAP stands forPassword Authentication Protocol. CHAP stands for Challenge handshake Authentication protocol. Several Network Control Protocols (NCPs): It has OSI, CP and IPCP.s LCP Packet encapsulated in a Frame LCP Packets Topic 165 Authentication Protocols in PPP PAP Packets encapsulated in a PPP frame CHAP Packets encapsulated in a PPP frame Internet Protocol Control Protocol (IPCP) Code values for IPCP Packets  IP datagram encapsulated in a PPP frame For short lecture search on Youtube: "CS601 short lecture by Amir" Chap _12 Topic-166 Media Access Control (MAC) Sub-Layer When nodes use a multipoint or broadcast link, we need a multiple-accessprotocol to coordinate access to the link Many protocols have been devised to handle access to a shared link All of these protocols belong to Media Access Control (MAC) sub-layer Taxonomy of Multiple-Access Protocols  Topic 167 Random Access Protocol In random-access or contention no station is superior to the other and none isassigned control over the other. Station that has data to send uses a procedure defined by the protocol tomake a decision on whether or not to send. This decision depends on the state of the medium (idle or busy). It has three types: Aloha CSMA/CD CSMS/CA Topic 168 ALOHA ALOHA, the earliest random access method, was developed in early 1970s. Designed for a radio (wireless) LAN, but it can be used on any shared medium. Potential collisions in this arrangement as the medium is shared between the stations. When a station sends data, another station may attempt to do so at the same time. The data from the two stations collide and become garbled and we will lose that data. ALOHA is a multiple access protocol for transmission of data via a shared network channel. It operates in the medium access control sub-layer (MAC sub-layer) of the open systems interconnection (OSI) model. Using this protocol, several data streams  originating from multiple nodes are transferred through a multi-point transmission channel. In ALOHA, each node or station transmits a frame without trying to detect whether the transmission channel is idle or busy. If the channel is idle, then the frames will be successfully transmitted. If two frames attempt to occupy the channel simultaneously, collision of frames will occur and the frames will be discarded. These stations may choose to retransmit the corrupted frames repeatedly until successful transmission occurs. Frames in a pure ALOHA Network: In pure ALOHA, the time of transmission is continuous. Whenever a station hasn’t available frame, it sends the frame. If there is collision and the frame is destroyed, the sender waits for a random amount of time before retransmitting it. Topic 169 Procedure for pure ALOHA protocol:  Vulnerable Time for pure ALOHA protocol: Topic 170 Slotted ALOHA: We divide time into slots of Tfr sec and force the station to send only at the beginning of the slot Invented to improve the efficiency of pure ALOHA If a station misses the time slot, it must wait until beginning of next time slotreducing vulnerable time to Tfr (vs. 2 x Tfr for pure ALOHA) The communicating stations agree upon the slot boundaries. Any station can send only one frame at each slot. Also, the stations cannot transmit at any time whenever a frame is available. They should wait for the beginning of the next slot. However, there still can be collisions. If more than one frame transmits at the beginning of a slot, collisions occur. The collision duration is 1 slot. The situation is depicted in the following diagram. Frames in a Slotted ALOHA Network: Vulnerable Time for Slotted ALOHA: Topic 171 Carrier Sense Multiple Access (CSMA):  To minimize the chance of collision and, therefore, increase the performance,CSMA was developed The chance of collision is reduced as the station is required to sense/listen tothe medium before sending data ‘sense before transmit’ or ‘listen before talk’. CSMA / CD (Career Sense Multiplus / Collision Detection) is a way to control media access that was widely used in early Ethernet technology / LAN, when shared bus topology And each node (computer) was connected by coaxial cables. Now a days Ethernet is full duplex and CSMA / CD is not used because the topology is either star or point to point but still They are supported. Consider a scenario where there are "n" stations on a link and everyone is waiting for data to be transmitted through this channel. In this case, all N stations will want to access their link / channel to transfer their data. The problem arises when more than one station transmits data at a time. In this case, the data from different stations will clash. CSMA / CD is one such technique where the various stations following this protocol agree on certain conditions and collision detection measures for effective transmission. This protocol decides which station to move when the data reaches its destination without any corruption. But even this technique doesn’t completely eliminate collisions because propagation delay. When a station sends a frame in CSMA/CD it still takes some time before this frame gets to all the other stations that are sharing the medium. The time that takes first bit of a frame that sent on medium to reach all the other stations is called propagation delay. Space/Time Model of a Collision in CSMA: Vulnerable Time in CSMA: Behavior of Three Persistence Methods: persistence: This is a simplest method. In this method after the station find link ideal it sends immediately without waiting. This method has got highest chance of collision. Non-persistence: In this method the channel has time slots. A station that has frame to send, it sense the link. If the link is Idle it send frame immediately. If links are not idle, it waits for a random amount of time and the sense that link again. So Collision rate in this case goes down as compared to I-persistence but the efficiency goes also down. P-persistence: In this case we have got a slot duration which is equal to or greater than the maximum propagation time. This approach combined the advantages of both I-persistence and Non-persistence. Topic 172 CSMA method does not specify the procedure following a collision. CSMA/CD arguments the algorithm to handle the collision. The station monitors the medium after it sends a frame to see if thetransmission was successful. If there is a collision, the frame is sent again. Collision of the First Bits in CSMA/CD: Collision and Abortion in CSMA/CD: Flow Diagram for the CSMA/CD: Energy Level During Transmission, Idleness and Collision: For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 173 CSMA/CA CSMA/CA was invented for Wireless Networks Collisions are avoided through the use of three strategies: The Inter frame Space The Contention Window Acknowledgements Carrier-sense multiple access with collision avoidance (CSMA/CA) in computer networking, is a network multiple access method in which carrier sensing is used, but nodes attempt to avoid collisions by beginning transmission only after the channel is sensed to be "idle". The algorithm of CSMA/CA is:  When a frame is ready, the transmitting station checks whether the channel is idle or busy. If the channel is busy, the station waits until the channel becomes idle. If the channel is idle, the station waits for an Inter-frame gap (IFG) amount of time and then sends the frame. After sending the frame, it sets a timer. The station then waits for acknowledgement from the receiver. If it receives the acknowledgement before expiry of timer, it marks a successful transmission. Otherwise, it waits for a back-off time period and restarts the algorithm. Flow Diagram for CSMA/CA:  Topic 174 CSMA/CA Inter frame Space (IFS): Collisions are avoided by deferring transmission even if the channel is idle Contention Window: Amount of time divided into slots. Station chooses a random number of slots as its wait time (one slot first time and double each time system cannot detect an idle channel) Carrier-sense multiple access with collision avoidance (CSMA/CA) in computer networking, is a network multiple access method in which carrier sensing is used, but nodes attempt to avoid collisions by beginning transmission only after the channel is sensed to be "idle". Contention Window CSMA/CA Acknowledgement: Positive acknowledgement and time-out timer can help guarantee that the receiver has received the frame. CSMA/CA and Network Allocation Vector (NAV)  Topic 175 CONTROLLED ACCESS The stations consult one another to find which station has the right to send A station cannot send unless authorized by other stations We discuss three controlled-access methods: Reservation Polling Token Passing In the reservation method, a station needs to make a reservation before sendingdata. Time is divided into intervals. In each interval, a reservation frame precedes the data frames sent in thatinterval. Reservation Access Method Polling Polling works with topologies in which one device is designated as aprimary station and the other devices are secondary stations. All data exchanges must be made through primary device even whenthe ultimate destination is a secondary device. The primary device controls the link; the secondary devices follow its instructions. Polling is the process where the computer or controlling device waits for an external device to check for its state. Select Poll Token Passing In the token-passing method, the stations in a network are organized in a logicalring For each station, there is a predecessor and a successor The predecessor is the station which is logically before the station in the ring; the successor is the station which is after the station in the ring Special packet called TOKEN circulates through the ring Possession of TOKEN gives the station the right to send the data TOKEN Management is required to manage possession time, token monitoring, priority assignment etc. For short lecture search on Youtube: "CS601 short lecture by Amir" Topic 177 CHANNELIZATION (Channel Partition)  The available bandwidth of a link is shared in time, frequency, or through code, among different stations We discuss three protocols: Frequency Division Multiple Access (FDMA) Time Division multiple Access (TDMA) Code Division Multiple Access (CDMA) Frequency-Division Multiple Access (FDMA) In FDMA, the available bandwidth is divided into frequency bands. Each station is allocated a band to send its data i.e. each band is reserved fora specific station, and it belongs to the station all the time. Each station also uses a band pass filter to confine the transmitterfrequencies. Frequency-division multiple access (FDMA) is a channel access method used in some multiple-access protocols. FDMA allows multiple users to send data through a single communication channel, such as a coaxial cable or microwave beam, by dividing the bandwidth of the channel into separate non-overlapping frequency sub-channels and allocating each sub-channel to a separate user. Users can send data through a sub- channel by modulating it on a carrier wave at the sub-channel's frequency. It is used in satellite communication systems and telephone trunk lines. Frequency-Division Multiple Access (FDMA)  Topic 178 TDMA Stations share the bandwidth of the channel in time Each station is allocated a time slot during which it can send data Each station transmits its data in its assigned time slot  Topic 179 Code Division Multiple Access (CDMA) CDMA differs from FDMA in that only one channel occupies the entire bandwidth of the link. CDMA differs from TDMA in that all stations can send data simultaneously; there is no timesharing. TOPIC 180 Chap..#..13 If two computers send data at the same time, a collision will occur. When this happens, the data sent is not usable. In general, both computers will stop sending, and wait a random amount of time, before they try again. A special protocol was developed to deal with such problems. It is called CSMA/CD. Ethernet Protocol Data-link layer and the physical layer are the territory of the local and wide area networks. We can have wired or wireless networks. Ethernet is a family of wired computer networking technologies commonly used in local area networks (LAN), metropolitan area networks (MAN) and wide area networks (WAN). It was commercially introduced in 1980 and first standardized in 1983 as IEEE Ethernet has since been refined to support higher bit rates, a greater number of nodes, and longer link distances, but retains much backward compatibility. Over time, Ethernet has largely replaced competing wired LAN technologies such as Token Ring, FDDI and ARCNET. It is a way of connecting computers together in a LAN. It has been the most widely used method of linking computers together in LANs since the 1990. The basic idea of its design is thatmultiple computers have access to it and can send data at any time. IEEE Project 802 In 1985, the Computer Society of the IEEE started a project, called Project 802, to set standards to enable inter-communication among equipment from a variety of manufacturers Project 802 did not seek to replace any part of the OSI model or TCP/IP protocol suite A way of specifying functions of the physical layer and the data-link layer of major LAN protocols IEEE 802 is a family of Institute of Electrical and Electronics Engineers (IEEE) standards for LAN, PAN, and MAN. The IEEE 802 LAN/MAN Standards Committee (LMSC) maintains these standards. The IEEE 802 family of standards has twelve members, numbered 802.1 through 802.12, with a focus group of the LMSC devoted to each. IEEE Standard for LANs For short lecture search on Youtube: "CS601 short lecture by Amir" TOPIC 181 Ethernet Evolution The Ethernet LAN was developed in the 1970s Since then, it has gone through four generations: Standard Ethernet (10 Mbps) Fast Ethernet (100 Mbps) Gigabit Ethernet (1 Gbps) 10 Gigabit Ethernet (10 Gbps) Standard Ethernet The original Ethernet technology with the data rate of 10 Mbps is called Standard Ethernet. Most implementations have moved to later evolutions. Still some features of the Standard Ethernet that has not changed during the evolution. A standard Ethernet network can transmit data at a rate up to 10 Mbps per second. Other LAN types include Token Ring, Fast Ethernet, Gigabit Ethernet, 10 Gigabit Ethernet, Fiber Distributed Data Interface (FDDI), Asynchronous Transfer Mode (ATM) and Local Talk. Connectionless & Unreliable Service Each frame is independent of other. No connection establishment or tear down process. The sender may overwhelm receiver with frames and frames are dropped. If frame drops, sender will not know about it unless we are using TCP (Transport). Ethernet is unreliable like IP and UDP. If a frame is corrupted, receiver silently drops it. Left to high level protocols to find out about it. TOPIC 183 Addressing in Standard Ethernet Each station on Ethernet has its own network interface card (NIC). Every NIC has got a unique link-layer address. The NIC fits inside the station and provides the station with a link- layer/physical address.  The Ethernet address is 6 bytes (48 bits), normally written in hexadecimal notation, with a colon between the bytes. For example, the following shows an Ethernet MAC address:4A:30:10:21:10:1A. Transmission of Address Bits How the address 47:20:1B:2E:08: EE is sent out online. The address is sent left to right, byte by byte; for each byte, it is sent right to left,bit by bit, as shown below: Unicast and Multicast Addresses Example 13.2 Define the type of the following destination addresses: a. 4A:30:10:21:10:1A b. 47:20:1B:2E:08:EE c. FF:FF:FF:FF:FF:FF To find the type of the address, we need to look at the second hexadecimal digit from the left. If it is even, the address is unicast. If it is odd, the address is multicast. If alldigits are Fs, the address is broadcast. Therefore, we have the following: This is a unicast address because A in binary is 1010 (even). This is a multicast address because 7 in binary is 0111 (odd). This is a broadcast address because all digits are Fs in hexadecimal. Implementation of Standard Ethernet As we know all the frames in Ethernet by nature is broadcast. If the all frame are broadcast then how we know which of the unicast or multicast. The answer is we know that by specifying the way these frame are actually treated when they reach at destination. Example:  TOPIC 184 Access Method in Standard Ethernet Since the network that uses the standard Ethernet protocol is a broadcast network, we need to use an access method to control access to the sharing medium The standard Ethernet chose CSMA/CD with 1-Persistent Method.  TOPIC 185 Efficiency of Standard Ethernet The ratio of the time used by a station to send data to the time the medium is occupied by this station The practical efficiency of standard Ethernet has been measured to be: Efficiency = 1/(1+ 6.4 x a) where a = number of frames that can fit on a medium TOPIC 186 Implementation of Standard Ethernet  The Standard Ethernet defined several implementations, but only four of them became popular during the 1980s Summary of Standard Ethernet implementations Encoding in Standard Ethernet 10Base5 Implementation 10Base2 Implementation 10Base-T Implementation 10Base-F Implementation For short lecture search on Youtube: "CS601 short lecture by Amir" TOPIC 187 Changes in the Standard The changes that occurred to the 10-Mbps Standard Ethernet opened the road to the evolution of the Ethernet to become compatible with other high-data-rate LANs Bridged Ethernet Switched Ethernet Full-Duplex Ethernet Bridged Ethernet An Ethernet network bridge is a device which connects two different local area networks together. Both networks must connect using the same Ethernet protocol. Bridges can also be used to add remote computers to a LAN. Many bridges can connect multiple computers or other compatible devices with or without wires. ANetwork with and without Bridging: Advantages: The basic advantage of bridging is that we can now divide 10Mbps capacity. We also separate the collision domains as well. TOPIC 188 Switched Ethernet: A network switch (also called switching hub, bridging hub, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device. Full – Duplex Switched Ethernet (FDSE) The Ethernet switch or Ethernet FDSE (Full Duplex Switched Ethernet), was born in the early 1990s before the advent of switched Ethernet, shared Ethernet networks were cut into shared subnets autonomous, interconnected by bridges. Therefore, the traffic was multiplied by the number of subnets. Advantages of FDSE This increases the direct capacity from 10MBS to 20MBS. Instead of using one link between stations, we use two links. CSMA / CD is not required. For short lecture search on Youtube: "CS601 short lecture by Amir" TOPIC 189 Fast Ethernet In the 1990s, Ethernet made a big jump by increasing the transmission rate to 100 Mbps, and the new generation was called the Fast Ethernet. To make it compatible with the Standard Ethernet, the MAC sub-layer was left unchanged. But the features of the Standard Ethernet that depend on the transmission rate, had to be changed. To be able to handle a 100 Mbps data rate, several changes need to be madeat the physical layer. In computer networking, Fast Ethernet physical layers carry traffic at the nominal rate of 100 Mbs. The prior Ethernet speed was 10 Mbs. Of the Fast Ethernet physical layers, 100BASE-TX is by far the most common. Goals of Fast Ethernet: Upgrade data rate to 100Mbps Make it compatible with Standard Ethernet Keep same 48-bit address Keep same frame format 100BASE - TX The 100BASE-TX is a prominent form of Fast Ethernet, and connects more than two wires within a category of 5 or higher cable. Each network segment can have a maximum cabling distance of 100 meters (328 feet). One pair is used for each direction, providing full duplex operation with 100 Mbps in each direction. 100BASE - FX 100BASE-FX is a version of Fast Ethernet over optical fiber. The 100BASE-FX Physical Medium Dependent (PMD) sublayer is defined by FDDI's PMD, so 100BASE- FX is not compatible with 10BASE-FL, the 10 Mbits version over optical fiber. 100BASE-FX is still used for existing installation of multimode fiber where more speed is not required, like industrial automation plants. 100BASE - T4 100BASE-T4 was an early implementation of Fast Ethernet. It requires four twisted copper pairs of voice grade twisted pair, a lower performing cable compared to category 5 cable used by 100BASE-TX. Maximum distance is limited to 100 meters. One pair is reserved for transmit, one for receive, and the remaining two switch direction. The fact that 3 pairs are used to transmit in each direction makes 100BASE- T4 inherently half- duplex. Gigabit Ethernet TOPIC 190 For short lecture search on Youtube: "CS601 short lecture by Amir" Need for an even higher data rate resulted in the design of IEEE Standard 802.3z Gigabit Ethernet Protocol (1000 Mbps). Gigabit Ethernet (GbE or 1 GigE) is a term used in computer networking to transmit Ethernet frames at gigabits per second (1 billion bits per second). The most popular variety 1000BASE-T is defined by the IEEE 802.3ab standard. It came into use in 1999, and due to its significant improvement over Fast Ethernet, as well as the use of cables and equipment, Fast Ethernet was converted to wired local networks. Which are more widely available than previous standards, economical and soon. The goals of the Gigabit Ethernet were: Upgrade the data rate to 1 Gbps Make it compatible with standard or Fast Ethernet Use same 48 bit address Use the same frame format Keep same minimum and maximum frame lengths The physical layer in Gigabit Ethernet is more complicated than that inStandard or Fast Ethernet. MAC Sub-layer A main consideration in the evolution of Ethernet was to keep the MAC sub-layer untouched To achieve a data rate of 1 Gbps, this was no longer possible Gigabit Ethernet has two distinctive approaches for medium access: Half-duplex Full-duplex Encoding in Gigabit Ethernet: Giga bit Ethernet is either a 2 wire or 4 wire Implementation. In case of 2 wire implementation it uses the fiber optic cable for 1000 Mbps or 1 gigabit. 1000 base SX is use for short waves and 1000 base XL for long waves. prepare chap-14 from ppts thanks