Chapter Three - Data Link Layer new.pptx PDF

Chapter Three: The Data Link Layer Introduction  the data link layer is responsible for carrying a packet from one hop (computer or router) to the next hop; i.e., it has local responsibility unlike the network layer  position of the data link layer...

Chapter Three: The Data Link Layer Introduction  the data link layer is responsible for carrying a packet from one hop (computer or router) to the next hop; i.e., it has local responsibility unlike the network layer  position of the data link layer 2 3.1 Error Detection and Correction  mainly a data link layer function  networks must be able to transfer data from one device to another with complete accuracy - our wish  data can be corrupted during transmission - many factors exist - like transmission impairments  hence, reliable systems must have a mechanism for detecting and correcting errors  two types of errors: single-bit and burst  single-bit error: only one bit in a data unit (byte, character, packet,...) has changed; less likely to occur in serial transmission (since noise normally lasts longer than the transmission time of 1 bit, e.g. 1 microsecond if speed is 1 Mbps), but most likely to occur in parallel transmission 3   burst error: 2 or more bits in the data unit have changed; most likely to occur in serial transmissions  error detection and correction: include redundant error- detection (and correction) codes with the data  two possibilities  include enough redundant information (called error- correcting codes) to enable the receiver to deduce what the transmitted data must have been; this method is often referred to as forward error correction; applicable on unreliable channels such as wireless links  include only enough redundant information (called error- detecting codes) to allow the receiver to deduce that an error occurred, but not which error, and have it request retransmission; applicable on reliable channels such as fiber 4  error-detecting codes: two types: parity check and cyclic redundancy check (a third one, called checksum, also exists)  parity check: most common and simple; two varieties  simple parity check: a redundant bit, called a parity bit, is added to every data unit so that the total number of 1s in the unit (including the parity bit) becomes even (or odd for odd-parity)  this method can detect all single-bit errors; it can detect burst errors only if the total number of errors in each data unit is odd  two-dimensional parity check: a block of bits is organized in a table (rows and columns) 5  original data 1100111 1011101 0111001 0101001 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 row parities 0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 column parities more overhead data and parity bits 11001111 10111011 01110010 01010011 01010101  can detect most errors  if 2 bits in one data unit are damaged and two bits in exactly the same positions in another data unit are also damaged, the checker will not detect an error 6   cyclic redundancy check (CRC): is based on binary division  the CRC is appended to the end of a data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number  read about the method of generating the CRC  error correction: two methods  error correction by retransmission: when an error is detected, the receiver will tell the sender to retransmit the entire data unit; see next: Data Link Control  forward error correction: the receiver can use an error- correcting code to correct certain errors; the hamming code is used to detect and correct errors;  7 3.2 Data Link Control and Protocols  for reliable data delivery across the link, the data link layer has two most important responsibilities: flow control and error control, collectively known as data link control  Flow Control  refers to a set of procedures used to restrict the amount of data that the sender can send before receiving an acknowledgement  it is an end-to-end mechanism for regulating traffic between source and destination  congestion control: a mechanism used by the network to limit congestion  flow control and congestion control are not really separable, and we will refer to both as flow control 8  limiting factors: speed of the receiver (to process incoming data), amount of memory (buffer) to store the incoming data before processed, and network capacity  rate of processing is normally slower than rate of transmission the receiver must be able to inform the sender to temporarily halt transmission until it is ready to receive more  if no flow control  when overload occurs  queues build up  packets are discarded  sources retransmit messages  congestion increases  instability  flow control prevents network instability by keeping packets waiting outside the network rather than in queues inside the network  avoids wasting network resources 9  Error Control  refers to both error detection and error correction  in the data link layer, error control refers primarily to methods of error detection and retransmission  anytime an error is detected, specified frames are retransmitted; this process is called automatic repeat request (ARQ)  Flow and Error Control Mechanisms (three methods) 1. An Unrestricted Simplex Protocol  simplex transmission: from sender to receiver  processing time ignored; the receiver is assumed to process the received data infinitely quickly  infinite buffer space assumed to be available  communication channel assumed to be free of error 10 2. Stop-And-Wait ARQ  protocols in which the sender sends one frame and then waits for an acknowledgement before proceeding are called stop-and-wait  data traffic is simplex, but frames travel in both directions; hence a half-duplex physical channel suffices  this protocol fails if ack frames by the receiver do not arrive or are late; the sender may time-out and send a frame again creating duplicate frames; the solution is to give sequence numbers to data frames and acks  there are four situations: normal operation, the frame is lost, the ack is lost, the ack is delayed 11 Normal operation 12 Lost frame 13 Lost ack 14 Delayed ack 15 3. Sliding Window Protocols  Stop-and-wait ARQ is not efficient; there is only one frame that is sent  can we transmit multiple frames while waiting for an ack?  use full-duplex transmission  two protocols: Go-Back-N ARQ and Selective Repeat ARQ  both methods require frames to be numbered  sequence numbers  frames from a sending station are numbered sequentially from 0 to 2m-1, where m is the number of bits of the sequence number in the frame header  e.g., let m = 3, then frames can be numbered as 0, 1, 2, 3 ,4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, … 16 a. Go-Back-N-ARQ  the sender and receiver have sliding windows  the sender’s window is of fixed size and is at most 2m-1; but other protocols such as TCP allow variable size windows (see later in the transport layer); it holds frames sent but not acknowledged  the receiver’s window is of size 1  the sender sets a timer for each frame sent; the receiver has no timer  the receiver sends positive acknowledgements if a frame has arrived safe and in order  if a frame is damaged or out of order, the receiver discards it and keeps silent and discards all subsequent frames; this causes the timer of the sender to expire and goes back and resends all frames, beginning from the one with the expired timer  the receiver does not need to acknowledge frames individually 17 Sender sliding window 18 waiting for frame 0 Receiver sliding window 19  Why is the sender’s window < 2m?  To detect repeated frames  Let m = 2 a. If the size of the window is 3 (2m-1) and all the 3 acks are lost, the timer for frame 0 expires and all frames are resent; the window of the receiver is expecting frame 3 not frame 0; so it will discard the duplicated frame b. If the size of the window is 4 (2m) and all the 4 acks are lost, the sender will send the duplicate of frame 0; since the window of the receiver is expecting frame 0, it accepts it not as a duplicate but as the first frame in the next cycle 20 21 b. Selective Repeat ARQ  in GO-Back-N ARQ, the task of the receiver is simplified; no need to buffer out-of-order frames; they are simply discarded  this protocol is inefficient for a noisy link that has a high probability of damage resulting in the resending of multiple frames  for a noisy link, use Selective Repeat ARQ that requires resending only the damaged frame  Selective Repeat ARQ defines a negative ack (NAK) that reports the sequence number of a damaged frame before the timer expires  the sender and receiver windows are both at most half of 2m  the receiver's window defines the range of acceptable sequence numbers, i.e., frames may arrive out of order 22  Let m = 2; window sizes = 2 23  Why are the sender and receiver windows at most half of 2m?  To detect repeated frames  Let m = 2 a. If the size of the window is 2 and both acks are lost, the timer for frame 0 expires and frame 0 is sent; the window of the receiver is expecting frame 2 not frame 0; so it will discard the duplicated frame b. If the size of the window is 3 and all the 3 acks are lost, the sender sends a duplicate of frame 0; since the window of the receiver is expecting frame 0 (frame 0 is part of the window), it accepts it not as a duplicate but as the first frame in the next cycle 24 25  examples of data link protocols  HDLC - High-level Data Link Control  an ISO standard  an actual protocol designed to support both half-duplex and full-duplex communication over point-to-point and multipoint links that implements the ARQ mechanisms  PPP - Point-to-Point Protocol  used in the Internet for router-to-router and home user-to- ISP traffic 26  Discussion Points What is the main responsibilities of a data link layer and services given? Why error occur during transmission and how it will be managed in DLL(Data Link Layer)? Write the ways by which Flow control and Error Control is conducted in DLL? Compare and contrast the various flow and Error Control mechanisims. 27 3.3 Medium Access Control  The MAC Sublayer: in a network, two devices can be connected by a dedicated link (like a reserved highway, may be on certain occasions!) or a shared link (like a public highway)  point-to-point access: when two devices are connected by a dedicated link and this link can be used by them at any time; PPP is used  multiple access: when two devices are connected by a shared link; when two devices in a multiple access situation get access to the link or a channel in the link, they may need to use a point-to-point access protocol to exchange data  Multiple Access Protocols  the problem of controlling the access to the medium is similar to the rules of speaking in an assembly (the right to speak is upheld; two people do not speak at the same time; do not interrupt each other; do not monopolize the discussion;...) 28  three categories of multiple access protocols 1. Random Access Protocols - try your best like taxis do i. MA - Multiple Access ii. CSMA - Carrier Sense MA iii. CSMA/CD - CSMA with Collision Detection iv. CSMA/CA - CSMA with Collision Avoidance 2. Controlled-Access Protocols - get permission i. Reservation ii. Polling iii. Token Passing 3. Channelization Protocols - simultaneous use i. FDMA - Frequency-Division MA ii. TDMA - Time-Division MA iii. CDMA - Code-Division MA 29 1. Random Access Protocols  each station has the right to use the medium without being controlled by any other station  collision may occur if more than one station tries to send  we need a procedure to answer the following questions  when can a station access the medium?  what can the station do if the medium is busy?  how can the station determine the success or failure of the transmission?  what can the station do if there is an access conflict? i. MA - Multiple Access  ALOHA is the earliest RA method developed at the University of Hawaii in the early 1970s  originally designed to be used on a radio LAN with a data rate of 9600 bps  can also be used in satellite and wireless transmissions Aloha (in Hawaiian language) means hello and goodbye 30  a base station serves as a central controller; each station sends a frame to the base station with an uploading frequency of 407 MHz (the solid line in the figure); the base station sends it to the receiver using a downloading frequency of 413 MHz (the dashed line in the figure); 31  potential collisions exist (on the upload link); so wait for acknowledgement; if none arrives wait a period of time (2 times the maximum propagation delay), send again if back off limit did not reach; the time it waits increases from one trial to the next 32  versions  pure ALOHA  slotted ALOHA  time is divided into discrete intervals of one packet duration  transmitting a frame is allowed only at the beginning of a slot  still collision is possible; collided packet are retransmitted after a random delay 33 ii. CSMA - Carrier Sense MA - polite version of ALOHA  to minimize the chance of collision, each station first listens to the medium before sending; “listen before talk”  if the channel is busy, it waits until it is idle  otherwise it transmits; if a collision occurs, it waits a random amount of time and starts listening again  the chance of collision is minimized  but may still occur because of the propagation delay (a station doesn’t know if another one has just started transmitting) or  if two or more stations start transmitting at the same time 34 t1 < t 2 < t 3 < t 4 < t 5 35  persistence strategies: two substrategies have been defined  nonpersistent: sense a line and send if it is idle; otherwise wait a random amount of time before listening (hence less greedy than continuously listening); reduces the chance of collision, but also reduces the efficiency of the network and has longer delays 36  persistent: sense a line and “send” if it is idle; otherwise listen; two variations of sending  1-persistent: if the line is idle, send immediately (with probability 1)  p-persistent: if the line is idle, send with probability p and refrain from sending with probability 1-p; if p = 0.2, then a station sends 20% of the time that a line is idle, and refrains from sending 80% of the time  implementation: the station generates a random number between 1 and 100; if it is < 20, then it sends, otherwise it refrains  it reduces the chance of collision and improves efficiency; depends on the value of p (see next figure) 37 computed throughput versus offered traffic for the protocols discussed so far 38 iii. CSMA/CD - CSMA with Collision Detection  adds a procedure to handle a collision  if a collision is detected and to reduce the probability of collision the second time, the sender waits; it has to back off  it waits a little the first time, more if a collision occurs again, much more if it happens a third time, and so on; finally gives up  in the exponential backoff method, it waits an amount of time between 0 and 2N x maximum_propagation_time, where N is the number of attempted transmissions  line sensing is done using one of the persistent strategies 39  sending a jam alerts the other stations and also to discard the part of the frame received  used in traditional Ethernet; CSMA was never implemented 40 iv. CSMA/CA - CSMA with Collision Avoidance  avoids collision  uses one of the persistence strategies; after it finds the line idle, it waits an IFG (interframe gap) amount of time; it then waits another random amount of time; after that it sends the frame and sets a timer;  if it receives an ack before the timer expires, the transmission is successful; otherwise something is wrong (the frame or the ack is lost); waits for a backoff amount of time and re-senses the line  used in wireless LANs 41  the frame or the ack is lost 42 2. Controlled-Access Protocols  the stations consult one another to find which station has the right to send; a station can not send unless it has been authorized by other stations i. Reservation  a station needs to make a reservation before sending data  time is divided into intervals; in each interval, a reservation frame precedes the data frames sent in that interval; if there are N stations in the system, there are exactly N reservation minislots in the reservation frame 43 ii. Polling  for topologies in which one device is designated as a primary station and the other stations are secondary stations  the primary asks the secondaries if they have data to send (polling); when it has data to be sent, the primary tells the secondary to get ready to receive (selecting) a. poll b. select 44 iii.Token Passing  a station is authorized to send data when it receives a special frame called a token  the stations are arranged around a ring (each station has a predecessor and a successor)  a token circulates around the ring when no data is transmitted  token: a bit sequence  free token: 01111110  busy token: 01111111  when a node wants to transmit  wait for a free token  remove token from ring (replace with busy token)  transmit message  when done transmitting, replace free token on ring 45  token failures: tokens can be created or destroyed by noise  distributed solution  nodes are allowed to recognize the loss of a token and create a new token  collision occurs when two or more nodes create a new token at the same time  need collision resolution algorithms  node failures: since each node must relay all incoming data, the failure of a single node will disrupt the operation of the ring 46  example  FDDI - Fiber Distributed Data Interface - is a 100 Mbps fiber optic token ring LAN standard - see later in LANs  it is also used for MANs 3. Channelization Protocols  the available bandwidth of a link is shared in time, frequency, or through code, between different stations i. FDMA - Frequency-Division MA  the available bandwidth is divided into channels; each station uses its allocated band to send its data; each band is reserved for a specific station (it belongs to it all the time)  FDMA is a data link layer protocol that uses FDM at the physical layer  used in cellular telephone and satellite networks 47 iii. TDMA- Time-Division MA  the entire bandwidth is just one channel; the stations share the capacity of the channel in time; each station is allocated a time slot during which it can send data;  TDMA is a data link layer protocol that uses TDM at the physical layer  also used in cellular telephone iv. CDMA- Code-Division MA  differs from FDMA because only one channel occupies the entire bandwidth of the link; differs from TDMA because all stations can send data simultaneously (no time sharing)  based on coding theory; proposed several decades ago, but implemented recently due to advances in technology 48  Examples of Data Link Layer Protocols There are various data link protocols that are required for Wide Area Network (WAN) and modem connections. Logical Link Control (LLC) is a data link protocol of Local Area Network (LAN). Some of data link protocols are given below 49  1. Synchronous Data Link Protocol (SDLC) SDLC is basically a communication protocol of computer. It usually supports multipoint links even error recovery or error correction also. It is usually used to carry SNA (Systems Network Architecture) traffic and is present precursor to HDLC. It is also designed and developed by IBM in 1975. It is also used to connect all of the remote devices to mainframe computers at central locations may be in point-to-point (one-to- one) or point-to-multipoint (one-to-many) connections. It is also used to make sure that the data units should arrive correctly and with right flow from one network point to next network point. 50  2. High-Level Data Link Protocol (HDLC) HDLC is basically a protocol that is now assumed to be an umbrella under which many Wide Area protocols sit. It is also adopted as a part of X.25 network. It was originally created and developed by ISO in 1979. This protocol is generally based on SDLC. It also provides best-effort unreliable service and also reliable service. HDLC is a bit-oriented protocol that is applicable for point-to-point and multipoint communications both. 51  3. Serial Line Interface Protocol (SLIP) – SLIP is generally an older protocol that is just used to add a framing byte at end of IP packet. It is basically a data link control facility that is required for transferring IP packets usually among Internet Service Providers (ISP) and a home user over a dial- up link. It is an encapsulation of the TCP/IP especially designed to work with over serial ports and several router connections simply for communication. It is some limitations like it does not provide mechanisms such as error correction or error detection. 52  4. Point to Point Protocol (PPP) PPP is a protocol that is basically used to provide same functionality as SLIP. It is most robust protocol that is used to transport other types of packets also along with IP Packets. It can also be required for dial-up and leased router-router lines. It basically provides framing method to describe frames. It is a character-oriented protocol that is also used for error detection. It is also used to provides two protocols i.e. NCP and LCP. LCP is used for bringing lines up, negotiation of options, bringing them down whereas NCP is used for negotiating network-layer protocols. It is required for same serial interfaces like that of HDLC. 53  5. Link Control Protocol (LCP) – It was originally developed and created by IEEE 802.2. It is also used to provide HDLC style services on LAN (Local Area Network). LCP is basically a PPP protocol that is used for establishing, configuring, testing, maintenance, and ending or terminating links for transmission of data frames. 54  6. Link Access Procedure (LAP) LAP protocols are basically a data link layer protocols that are required for framing and transferring data across point-to-point links. It also includes some reliability service features. There are basically three types of LAP i.e. LAPB (Link Access Procedure Balanced), LAPD (Link Access Procedure D-Channel), and LAPF (Link Access Procedure Frame-Mode Bearer Services). It is actually originated from IBM SDLC, which is being submitted by IBM to the ISP simply for standardization. 55  7. Network Control Protocol (NCP) NCP was also an older protocol that was implemented by ARPANET. It basically allows users to have access to use computers and some of the devices at remote locations and also to transfer files among two or more computers. It is generally a set of protocols that is forming a part of PPP. NCP is always available for each and every higher-layer protocol that is supported by PPP. NCP was replaced by TCP/IP in the 1980s. 56