Week # 09 Computer Communication & Network Powerpoint

Week # 09 Computer Communication & Network Powerpoint

Week # 09 Computer Communication & Network Powerpoint Templates ACKNOWLEDGMENTS Mostly adopted from lecture slides by Behrouz A. Forouzan. Week 9: Course Plan Data Link Layer

Types of Framing Byte count character-based framing Bit-oriented framing Random Multiple Access Control Protocols Pure ALOHA Slotted ALOHA CSMA CSMA/CD CSMA/CA Data Link Layer

The data link layer is responsible for moving frames from one hop (node) to the next Functions of the Data Link Layer (local focus) Specific things that DLL does in order to accomplish the general functions of handling errors and regulating data flow Framing: divides the stream of bits received from the network layer into manageable data units called frames Error Control: adds reliability to the physical layer by adding mechanisms to

detect and retransmit damaged, duplicate, or lost frames. Both detection and correction schemes may be used Flow Control (imposes a flow control mechanism to prevent sender from swamping or overwhelming the receiver which is normally built into the protocol Media access control determines which device has control over the link at any given time when two or more devices are connected to the same link Addressing adds a header to the frame to define the addresses of the sender and receiver of the frame Framing The data link layer needs to pack bits into frames, so that each

frame is distinguishable from another Deciding, at the receiving end, where frames start and stop and filling idle periods Types of framing byte count character-based framing bit-oriented framing Framing: Byte (length) count Header contains length of frame Problems count may become corrupted

receiver has no way to tell where next frame starts Example: Framing: character-based framing special characters (flag bytes) used with byte stuffing Two consecutive flag bytes indicate the end of one frame and the start of the next Thus, if the receiver ever loses synchronization it can just search for two flag bytes to find the end of the current frame and the start of the next frame

If FLAG byte occurs in data itself (such as in binary data: transmission of photographs or songs) Interfering problem Insert ESC byte before each FLAG data byte (byte stuffing) If ESC byte itself appears in data Insert another ESC byte before ECS byte of data Framing: character-based framing (a) A frame delimited by flag bytes

(b) Four examples of byte sequences before and after stuffing Byte stuffing and unstuffing Byte stuffing is the process of adding 1 extra byte whenever there is a flag or escape character in the text Framing: bit-oriented framing special bit sequences (flag bits) used with bit stuffing It was developed for HDLC (Highlevel Data Link Control) protocol Each frame begins and ends with a special bit pattern, 01111110

or 0x7E in hexadecimal (a flag byte) Framing: bit-oriented framing whenever the senders data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream so that the receiver does not mistake the pattern 01111110 for a flag. This process is called Bit Stuffing. This bit stuffing is analogous to byte stuffing, in which an escape byte is stuffed into the outgoing character stream before a flag byte in the data When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically de-stuffs (i.e., deletes) the 0

bit Framing: bit-oriented framing Bit stuffing (a) The original data (b) The data as they appear on the line (c) The data as they are stored in receivers memory after de-stuffing Data link layer divided into two functionality-oriented sub-layers Data link control and Medium Access Control

The Medium Access Control Sub-layer 14 Medium Access Control There are Two categories of network links Those using point-to-point connections Those using broadcast channels In any broadcast network

How to determine who gets to use the channel when there is competition for it? Broadcast channels are sometimes referred to as multi-access channels or random access channels Multiple-access problem: when a channel is shared among many nodes, the problem arises to when each node should access the channel Protocols used to determine who goes next on a multi-access channel belongs to MAC layer Distributed system is the key matter which makes this issue hard as there is no one in-charge in the system 15

MAC Protocols MAC is important in LANs, particularly critical to the performance of wireless LANs as wireless is naturally an open, shared, and broadcast medium/channel MAC allows several stations connected to the transmission medium to transmit over it and to share its capacity A MAC protocol is used to resolve potential contention and collision when using the communication medium MAC protocols define rules to force distributed nodes to access wireless medium in an orderly and efficient

manner 16 Ingredients of MAC Protocols Carrier sense (CS) Hardware capable of sensing whether transmission taking place in vicinity Acknowledgments When collision detection not possible, link-layer mechanism for identifying failed transmissions Backoff mechanism Method for estimating contention and deferring

transmissions Collision detection (CD) Hardware capable of detecting collisions Collision avoidance (CA) Protocol for avoiding collisions 17 Propagation Vs Transmission Propagation Transmission

How long it takes one bit to travel from one end of the medium to the other or time it takes the signal to travel from source to destination How long it takes to get all the bits into the medium in the first place or time it takes the sender to transmit all bits of the packet It is proportional to the length of the medium (length/speed or distance/speed)

It is ----- packet length/data rate Propagate means to move something in a medium..... Transmit means to send something....... Therefore, propagation delay is the time taken by an object to pass through a medium Whereas transmission delay is the time taken

to transfer something It depends on the distance between source and receiver and also the medium through which it is travelling It depends on the length of object which is to be transmitted and the rate at which the object is transmitted 18

Propagation Vs Transmission Packet transmission time: Example Consider a 100 Mbit/s Ethernet, and the maximum packet size of 1520 bytes Then Maximum packet transmission time 1520*8 bit / (100 000 000 bit/s) =----- ss Packet propagation time: Example Consider wireless communication with maximum distance of 100 meter between sender and receiver Then Maximum link propagation delay 100 m / (300 000 000 m/s) = ---- ss

19 Example A 1000 byte packet is sent from your home to a server. It is first sent over a 10 Mbps wireless link. Once it has been received completely, it is then sent over a 100 Mbps ISP link. The propagation delay of the wireless link is 500 nanoseconds and the propagation delay of the ISP link is 10ms. How long does it take (in milliseconds) for the packet to reach the server? 20

Taxonomy of multiple-access protocols Random multiple access protocols In random access or contention methods, No station is superior to another station and No station is assigned the control over another No station permits, or does not permit, another station to send At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send A station can transmit When it desires Provided it obeys the mechanism defined by the protocol

Such as verification of state of medium 22 Random multiple access protocols Stations transmit without any schedule Methods are called random access because transmission is random among the stations

Also called contention methods Stations have competition to access the common medium that can lead to conflicts no rules specify which station should transmit next Access collision If more than one stations try to send Frames can be either destroyed or modified 23 Random multiple access protocols

To avoid access collision or resolve when it happens, a node follows a procedure that tackles the following: When to access the medium What to do if medium busy How to determine the transmission failure or success What to do in the situation of collision

24 ALOHA Network (Areal LOcations of Hazardous Atmospheres) Norm Abramson devised a new protocol at the University of Hawaii for multiple access When should nodes send? computer network connecting the Hawaiian islands in the late 1960s with wireless links Use of very simple procedure: Multiple access All random access methods evolved from ALOHA

Principal of pure ALOHA: If you have data to send, send the data If the message collides with another transmission (no ACK received), sender waits random time before trying again (resend) 25 Frames in a pure ALOHA network: 4 stations each with 2 frames contending with one another for access to the shared channel 26

Pure ALOHA Even if one bit of a frame coexists on the channel with one bit from another frame: There is a collision Resend the frames that have been destroyed during transmission It relies on ACKs from receiver If no ACK received after a time-out period, then assumes that frame has been destroyed and resend the frame If all collided stations retransmit after time out: Frame may collide again Pure ALOHA dictates that each station waits a random amount of time (backoff time:TB) before resending its frame The randomness helps in avoiding more collisions

To prevent congestion of the channel with retransmitted frames a station must give up after a maximum number of retransmission attempts Kmax and try later 27 Procedure for pure ALOHA protocol 28 Pure ALOHA Example On a wireless ALOHA network

stations are maximum 300 Km apart Assume that signals propagate at 3 x 108 m/s Maximum propagation time= Tp = ? Backoff time = TB = ? If K = 1, 2,3 What will be the maximum propagation time and backoff time if stations are 900 Km apart 29 Slotted ALOHA Slotted ALOHA was invented to improve the efficiency of

pure ALOHA In slotted ALOHA, time is divided into slots of Tfr seconds (average transmission time for a frame) and force the station to send only at the beginning of the time slot A station must wait until the beginning of the next time slot If it misses to transmit at the start of a time slot Possibility of collision If two stations try to send at the start of the same time slot 30 Frames in a slotted ALOHA network

31 CSMA (Carrier Sense Multiple Access) CSMA protocol was developed to minimize the chances of collision, so as to improve the performance Improves ALOHA by listening for activity before we send (carrier sense) Protocols in which station listen for a carrier (such as an electrical bus, or a band of the electromagnetic spectrum) and act accordingly are called carrier sense protocols Collision chances can be reduced to great extent if a station senses the channel before trying to use it

So CSMA is based on the principal of sense before transmit If channel sensed idle, transmit entire frame If channel sensed busy, defer transmission Human analogy: dont interrupt others 32 CSMA CSMA cannot eliminate the possibility of collision completely it can only reduce the chances of collision

Collision is possible if two nodes send instantaneously (simply) BUT a collision is still possible even if they send at slightly different times it takes time for frames to propagate along the medium The propagation delay is the major concern for the chances of collision 33 CSMA Let station B senses the medium at t1 and finds it idle,

so it sends a frame At time t2 (t2> tI)station C senses the medium and finds it idle because, at this time, the first bits from station B have not reached station C So, C also sends a frame The two signals collide and both frames are destroyed CSMA Access Modes 1-persistent CSMA Non-persistent CSMA P-persistent CSMA 34

1-Persistent CSMA station that wants to transmit data, continuously senses the channel to check whether it is idle or busy If the channel is busy the station continues sensing until it becomes idle When an idle channel is detected The station immediately transmits the frame with probability 1 (so called1-persistent CSMA) It has the highest chance of collision two or more stations may find channel to be idle at the same time and transmit their frames When the collision occurs, the stations wait a random amount of time

and start all over again This mode is used in CSMA/CD 35 Drawback 1-Persistent CSMA The propagation delay time greatly affects this protocol Let us suppose, just after the station 1 begins its

transmission, station 2 also becomes ready to send its data and sense the channel If the signal of station 1 has not yet reached station 2, station 2 will sense the channel to be idle and will begin its transmission. This will result in collision Even if propagation delay time is zero, collision will still occur If two stations become ready in the middle of third stations transmission both stations will wait until the transmission of first station ends and both will begin their

transmission exactly simultaneously resulting in collision 36 Non-Persistent CSMA A station that has a frame to send senses the channel If the channel is idle, it sends immediately If the channel is busy, it waits a random amount of time, and then senses the channel again In non-persistent CSMA the station does not continuously

sense the channel for the purpose of capturing it when it detects the end of precious transmission 37 Non-Persistent CSMA Advantages of non-persistent It reduces the chances of collision because the stations wait a random amount of time It is unlikely that two or more stations will wait for same amount of time and will retransmit at the same time Disadvantages of non-persistent

It reduces the efficiency of network because the channel remains idle when there may be station with frames to send This is due to the fact that the stations wait a random amount of time after the collision 38 P-Persistent CSMA This method is used when channel has time slots such that the time slot duration is equal to or greater than the maximum propagation delay time Whenever a station becomes ready to send, it senses the channel

If channel is busy, station waits until next slot If the channel is idle, it transmits with a probability p With the probability q=1-p, the station then waits for the beginning of the next time slot If the next slot is also idle, it either transmits or wait again with probabilities p and q respectively This process is repeated till either frame has been transmitted or another station has begun transmitting In case of the transmission by another station, the station act as though a collision has occurred and it waits a random amount of time and starts again This mode is used in CSMA/CA

Advantage: it reduce collision chances and improve the efficiency of the network 39 Flow diagram for three persistence methods Behavior of three persistence methods CSMA does not specify any procedure after collision CSMA/CD enhances the algorithm to handle the collision

42 CSMA/CD (carrier sense multiple access/ collision detection) Persistent and non-persistent CSMA protocols are definitely an improvement over ALOHA because they ensure that no station begins to transmit while the channel is busy However, if two stations sense the channel to be idle and begin transmitting simultaneously, their signals will still collide. Another improvement (on top of ALOHA) is for the

stations to quickly detect the collision and abruptly stop transmitting, (rather than finishing them).This scheme saves time and bandwidth 43 CSMA/CD When a sender detects a collision, it sends a jam signal. Make sure that all nodes are aware of the collision Length of the jam signal is 32 bit times In CSMA/CD, stations abort their transmission when they detect a collision e.g., Ethernet, IEEE802.3

It is not applicable to wireless systems 44 CSMA/CD: Procedure 1. Node has a frame to transmit 2. Sense the medium I. If busy (not idle): wait until becomes free II. If idle: transmit 3. After transmission, check weather collision has occurred I. If collision has detected a) Send a jam signal b) Increment retransmission counter

c) Check maximum number of retransmission attempts. If yes, abort transmission d) Based on number of collisions, calculate random backoff time and wait that time e) Repeat from step 2 again II. If no collision detected, transmission is successful 4. Retransmission counters are reset and end frame transmission 45 Flow diagram for the CSMA/CD Energy level during transmission, idleness, or collision

level of energy in a channel can have three values Zero: the channel is idle Normal: The station has successfully captured the channel and is sending its frame Abnormal: there is a collision and the level of the energy is twice the normal level station that has a frame to send or is sending a frame needs to monitor the energy level to determine if the channel is idle, busy, or in collision mode 47

Collision detection: If the signal, the sender reads back, is different from the signal it is putting out, it knows that a collision is occurring In fact, a received signal must not be tiny compared to the transmitted signal In CSMA/CD : a station needs to be able to receive while transmitting to detect a collision When there is no collision, the station receives one signal: its own signal When there is a collision, the station receives two signals: its own signal and the signal transmitted by a second station To distinguish between these two cases, the received signals in these

two cases must be significantly different 48 In a wired network, the received signal has almost the same energy as the sent signal because So in a collision, the detected energy almost doubles Popular CSMA scheme and its variant CSMA/CD developed for wired networks Can not be used directly in wireless networks

49 CSMA/Collision Avoidance Timing in CSMA/CA CONTROLLED ACCESS In controlled access, the stations consult one another to find which station has the right to send. A station cannot send unless it has been authorized by other stations. Three popular controlled-access methods are Reservation, Polling and Token Passing

CHANNELIZATION Channelization is a multiple-access method in which the available bandwidth of a link is shared in time, frequency, or through code, between different stations. channelization protocols are FrequencyDivision Multiple Access (FDMA), Time-Division Multiple Access (TDMA) and Code-Division Multiple Access (CDMA)

Recently Viewed Presentations

  • Juan Ponce de Leon - Coolidge Elementary School

    Juan Ponce de Leon - Coolidge Elementary School

    Juan Ponce de Leon was a famous soldier and he sailed with Cristofer Columbus. ... His sponsor country was Spain and his sponsor people was King Ferdinand and Queen Isabella. Ponce de leon's exploration date was from 1506-1521. (I couldn't...
  • eliscuola.files.wordpress.com


    C'è persino un flebile ma suggestivo filo che lega il cardinale di Cusa alla scoperta dell'America: Cristoforo Colombo, infatti, copiò di suo pugno una lettera, fornita di calcoli e mappe, scritta ai reali di Spagna dal grande cartografo Paolo Dal...
  • The Discontented Fish - Loudoun County Public Schools

    The Discontented Fish - Loudoun County Public Schools

    The Discontented Fish. An African Tale. Once upon a time there was a colony of little fishes who lived together in their own small pool, isolated from the rest of the fish in the river. Most of these fish were...
  • Standard vs General - Maths Class

    Standard vs General - Maths Class

    Mathematics Standard vs Mathematics General. STANDARD. PRELIMINARY. HSC (Gen 2) Focus Studies. STANDARD 1. HSC (Gen 1) NEW. Key. Based on Mathematics Standard Stage Syllabus, NESA, 2017. This is not an authorised NESA document. It was developed for the purposes...
  • OSBM Overview

    OSBM Overview

    FY 2011-13 Presentation of Governor Perdue's Recommended Budget Prepared by: The Office of State Budget and Management February 17, 2011 * * * * * * * * * * Summary: Governor's Budget Priorities Fiscal Responsibility and Sustainability FY 2011-12...
  • Department of Health and Human Services Division of

    Department of Health and Human Services Division of

    Mosquito traps and species typing throughout NV. Most of . Aedes. species are in the north. A. aegypti. and . A. albopictus. do not currently live in NV . ZIKV shows a propensity for these two species. ... PowerPoint Presentation...
  • Transforming Patient Care Paramount Issues and Opportunities in

    Transforming Patient Care Paramount Issues and Opportunities in

    a) Strong and cohesive national coalitions of pharmacy associations, patient and consumer groups, and other healthcare organizations. b) Grassroots efforts from individual pharmacy practitioners and affiliated societies. c) Both. d) None of the above
  • George Mason School of Law Contracts I T.

    George Mason School of Law Contracts I T.

    Union strategies * * Union strategies Marriage amongst princely families Victoria and Albert, 1840 * * Union strategies: Families Doug Allen and Dean Lueck, The Nature of the Farm (MIT Press, 2003) * * Union strategies: Vertical Integration Armen Alchian...