Computer Network Module 2

COMPUTER NETWORKS (BCSE 3306) Lecture Notes Module II Ajit K Nayak [email protected] Department of Computer Science Engineering & Application

Out Line of Module II „

Data-Link Layer „ „ „ „ „ „ „

Error detection and correction Data link control and protocols Point-to-Point access (PPP) Multiple Access Local Area Networks: Ethernet Wireless LANS Virtual Circuit Switching: Frame Relay and ATM

Text: “Data Communications and Networking” Third Edition, Behrouz A Forcuzan, Tata Mc Graw-Hill. Chapter 10 - Chapter 15 and Chapter 18 Computer Networking / Module II / AKN / 2

Lecture I • Error Detection and Correction • Types of Errors • Detection • Error Correction

• Data Link Control and Protocols • Stop and Wait ARQ • Go-Back-N ARQ • Selective Repeat ARQ • HDLC • PPP Computer Networking / Module II / AKN / 3

The Link layer

ƒ

ƒ

Datalink layer is subdivided into two sub-layers ƒ

Logical Link Control (LLC): non architecture specific, same for all LANS (IEEE)

ƒ

Media Access Control (MAC): contains a number of distinct module each carries proprietary information specific to the LAN product being used

Project 802 of IEEE sets standards to enable intercommunication between equipment from a variety of manufacturers

Computer Networking / Module II / AKN / 4

Errors in Transmission „

„

Data can be corrupted during transmission, for reliable communication, errors must be detected and corrected Two types of transmission errors „

Single bit error: only one bit of the data unit is changed

„

Burst error: two or more bits in the data unit have changed

Computer Networking / Module II / AKN / 5

Detection mechanisms „

„

To detect errors in transmission the concept of redundancy is used i.e. adding extra bits along with data and transmitted to other end. Detection Methods „

Parity Check

Cyclic Redundancy Check (CRC) „

„

Checksum

Computer Networking / Module II / AKN / 6

Parity check „ „

It can be simple or two dimensional Simple Parity Check „

„

A redundant bit called parity bit is added to every data unit so that the total no of 1s (including parity bit) in the unit becomes even or odd Performance: it can detect all single bit errors, „ also it can detect burst errors of odd size i.e. 1, 3, 5 etc. „ However it can not detect burst errors of even size, i.e. 2, 4, 6 etc „

Computer Networking / Module II / AKN / 7

Example: Simple Parity Check „

„

„

„

„

„

Suppose the sender wants to send the word ‘world’. In ASCII the five characters are coded as 1110111 1101111 1110010 1101100 1100100 The following shows the actual bits sent after adding parity bit 11101110 11011110 11100100 11011000 11001001 Now suppose the word ‘world’ is received by the receiver without being corrupted in transmission. 11101110 11011110 11100100 11011000 11001001 The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4). No errors, The data are accepted. Now suppose the word ‘world’ is corrupted during transmission as follows. 11111110 11011110 11101100 11011000 11001001 The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4). Contains error, the data are discards them, and asks for retransmission. Computer Networking / Module II / AKN / 8

Two-Dimensional Parity Check „

„ „

A block of bits is organised in a table, now parity bit is calculated for each row then parity bit of each column thus generating one more row (redundant data unit). The extra data unit is also transmitted Performance A redundancy of n bits can easily detect a burst error of n bits „ If some even number of bits of two data units gets corrupted in same position then it can not be detected Computer Networking / Module II / AKN / 9 „

Example: Two dimensional Parity Check „

„

„

„

Suppose the following block is sent: 10101001 00111001 11011101 11100111 10101010 However, it is hit by a burst noise of length 8, and some bits are corrupted. 10100011 10001001 11011101 11100111 10101010 When the receiver checks the parity bits, some of the bits do not follow the even-parity rule 10100011 10001001 11011101 11100111 10101010 and the whole block is discarded.

Computer Networking / Module II / AKN / 10

Cyclic Redundancy Check (CRC) „ „

„

It is the Most powerful method based on binary division The redundancy bits used by CRC are derived by dividing the data unit by a predetermined divisor; the remainder is the CRC

Method A string of n 0s appended to data unit, n is one less then the number of bits present in the predetermined divisor

„

Data unit appended with 0s is divided by the divisor using modulo-2 division and the remainder is collected

„

„

Remainder replaces n no of 0s appended to data unit and transmitted

At the receiving end the data along with CRC is divided by the divisor and if remainder is Zero than no error Computer Networking / Module II / AKN / 11

„

Binary Division in CRC: An Example

Sending End

Receiving End Computer Networking / Module II / AKN / 12

CRC contd. „

Modulo-2 division „ „ „

„

If left most bit of dividend is 1 then quotient will be 1 else 0 0-0 = 0, 1-1=0, 1-0=0, 0-1=1 Note: we are dealing with bit-patterens not with quantitative values

Divisor

It is calculated from an algebraic poly nomial „

„

Properties It should not be divisible by x, guarantees that all burst errors of a length equal to the degree of polynomial are detected „

It should be divisible by x+1, guarantees that all burst errors affecting an odd number of bits Computer Networking / Module II / AKN / 13 are detected „

Standard Polynomials

„

Name

Polynomial

Application

CRC-8

x8 + x2 + x + 1

ATM header

CRC-10

x10 + x9 + x5 + x4 + x 2 + 1

ATM AAL

ITU-16

x16 + x12 + x5 + 1

HDLC

ITU-32

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

LANs

An Example „

„

„

It is obvious that we cannot choose x (binary 10) or x2 + x (binary 110) as both are divisible by x. However, we can choose x + 1 (binary 11) because it is not divisible by x, but is divisible by x + 1. We can also choose x2 + 1 (binary 101) because it is divisible by x + 1 (binary division). Computer Networking / Module II / AKN / 14

Checksum „ „

A simple but effective method based on redundancy Method „

Subdivide the data unit into equal segment of n bits

These segments are added using ones complement arithmetic so that result is also n bits

„

The sum is complemented and appended at the end of original data unit as redundant bits

„

At the receiving end all the groups are added again and if the result is zero then there is no error

„

„

Performance Detects all errors involving an odd number of bits as well as most errors involving an even number of bits Computer Networking / Module II / AKN / 15

„

Example „ „ „ „ „ „ „ „ „ „

Suppose the following block of 16 bits is to be sent using a checksum of 8 bits. 10101001 00111001 The numbers are added using one’s complement 10101001 00111001 -----------Sum 11100010 , Checksum 00011101 The pattern sent is 10101001 00111001 00011101 Now suppose the receiver receives the pattern sent without any error. Receiver adds all sections using same method 10101001 00111001 00011101

Sum

11111111 , Complement 00000000 means that the pattern is OK. Computer Networking / Module II / AKN / 16

Example Now suppose there is a burst error of length 5 that affects 4 bits. 10101111 11111001 00011101 When the receiver adds the three sections, it gets 10101111 11111001 00011101 Partial Sum Carry

1 11000101 1

Sum

11000110

Complement

00111001

the pattern is corrupted. Computer Networking / Module II / AKN / 17

Error Correction „

Two ways of error correction „

Error correction by retransmission „

„

„

When an error is detected, receiver asks sender to retransmit the whole data unit This method is normally used in TCP/IP. i.e. CRC is used in Link layer and Checksum is used in Network and Transport Layer

Forward Error Correction „

„

A receiver uses an error correcting code, but it requires more number of redundant bits to know the position of error in comparison to error detection methods e.g. for a single bit error, one bit parity is sufficient to know if there is error or no error, i.e. 0 or 1 Computer Networking / Module II / AKN / 18

Forward Error correction „

Redundancy bits needed is „ „ „

„

„ „

Let number of data bits be m, and redundant bits be r Therefore total no of bits sent is m+r Then r must be able to indicate m+r+1 different states. i.e. to indicate if there is an error in one of the m+r positions and one state is needed to say that there is no error One bit can represent 2 states, then r bit can represent 2r states therefore the inequation must be satisfied 2r ≥ m+r+1 Now given the value of m, r can be calculated e.g. if m=7 then r has to be 4, i.e. 24 ≥ 7+4+1 is satisfied Computer Networking / Module II / AKN / 19

Hamming Code for Single bit error Correction „ „

Provides a practical solution to FEC Method: „

„

„

Let number of data bits (m) be 7 => number of redundant bits (r) are 4 Position of redundant bits are defined as 1st, 2nd, 4th, and 8th, i.e. 2x, x=0,1,2,…

Value of each of r bits is calculated as parity bit for one combination of data bits given as follows „ „ „ „

r1: r2: r3: r4:

data data data data

bits bits bits bits

1, 2, 4, 8,

3, 3, 5, 9,

5, 7, 9, 11 (binary value containing 1 at 1st position) 6, 7, 10, 11 (binary value containing 1 at 2st position) 6, 7 (binary value containing 1 at 3rd position) 10, 11 (binary value containing 1 at 4th position) Computer Networking / Module II / AKN / 20

Redundancy bits calculation

Computer Networking / Module II / AKN / 21

Error detection using Hamming code

Computer Networking / Module II / AKN / 22

Burst error Correction „

„ „

„

„

Hamming code cannot correct a burst error directly. But by rearranging the sending data the code may be applied Method: Instead of sending all bits in a data unit together, we organise N units in a column and then send first unit of each unit followed by second bit of each and so on If a burst error of M bits occur (M
Data link control and Protocols „

„

Flow Control and Error control are the important responsibilities of link layer, collectively called 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 waiting for acknowledgement

Error Control „

It is based on the Automatic Repeat reQuest (ARQ), i.e. any time an error is detected, specified frames are retransmitted also called Positive Acknowledgement with Computer Retransmission(PAR) Networking / Module II / AKN / 24

Stop and Wait ARQ „

„

„

„

„

„

„

The sending device sends a frame and waits for the acknowledgement before sending another The sending device keeps a copy of the last frame transmitted until it receives an ACK Both data and ACK frames are numbered and a data frame 0 acknowledged by ACK 1 frame indicating that the receiver has received data 0 and expecting Data 1. If a receiver receives a damaged frame then it is discarded without any response to sender Sender maintains a variable ‘S’, that holds the number of recently sent frame. Receiver maintains a variable ‘R’ that holds the number of next expected frame The sender starts a timer when a fame is sent, if ACK is not received within a pre allotted time period (Time out) the same frame is retransmitted The receiver sends ACK if a correct frame is received Computer Networking / Module II / AKN / 25

Operation Normal

Lost ACK

Lost or damaged frame

Delayed ACK

Computer Networking / Module II / AKN / 26

Piggybacking „

„

„

To achieve full duplex (bi-directional transmission) we use a concept called piggybacking It is a method to combine data frame with an ACK instead of sending two separate frames, thus ACK gets a free ride on the next out going data frame. It saves bandwidth.

Characteristics of Stop & Wait „ It is simple but inefficient because a) The network will be completely idle during times that the receiver responses b) Wasting of substantial amount of BW c) Duplication due to premature retransmission or lost ACK

Round Trip Time(RTT): The time required for a frame to arrive at the receiver plus the transmission time for ACK to come back

Computer Networking / Module II / AKN / 27

Example „

„

Given Channel BW=50Kbps, RTT=500ms, 1 frame contains 1000bits, then Find channel utilization Answer (Method 1) „ „

„ „

„

„

„

At t=0 first frame transmission starts The time required to push 1000 bits to medium (1 frame) is t=1000/50,000=20ms 1st bit arrives at t=250ms (RTT/2), the last bit arrives at t=270ms Ignoring the processing time, and length of ACK, At t=520ms ACK arrives at the sender, i.e. At t=520ms the next frame transmission starts i.e. 20ms utilization time and 500ms waiting time for a total of 520 ms communication time Utilization = 4%, waiting=96% loss of BW

Answer (Method 2) „

„

The system can send 50000×.5=25,000 (BW×delay)bits during the time it takes for the data to go from the sender to the receiver and then back again. However, the system sends only 1000 bits. i.e. the link utilization is only 1000/25,000, or 4%. Computer Networking / Module II / AKN / 28

Sliding Window „

„

„

„

„

The main disadvantage of Stop and wait method is loss of bandwidth and efficiency is low To improve efficiency, multiple frames should be in transition while waiting for ACK In this method an window amount of frames can be sent without receiving ACK An imaginary window with fixed size slides over the frames at sending end. It contains the frames to be transmitted next It is implemented in two ways. 1. Go Back n ARQ 2. Selective Repeat ARQ Window size = 7 frames Direction of transmission

Sequence number 0, 1, 2, . . ., 7 then wrap around Computer Networking / Module II / AKN / 29

Go Back n ARQ „

The sender maintains three variables „ „ „ „

„

S: holds the sequence number of the recently sent frame SF: holds the sequence number of the first frame in the window SL: holds sequence number of last frame in the window The size of the window W = SL – SF + 1

The receiver maintains only one variable „

R: holds the sequence number of the next frame expected Direction of transmission

Computer Networking / Module II / AKN / 30

Go Back n ARQ

ACK 2

Normal

Lost or damaged frame Computer Networking / Module II / AKN / 31

Go Back n ARQ contd. „

A damaged or lost ACK results in two situations „

„

„

A delayed ACK results in two situations „

„

„

If next ACK arrives before the timer expires, no retransmission is required If next ACK does not arrive before timer expires then all the frames starting from last ACK received is retransmitted again, thus the name Go Back n If next ACK arrives before the timer expires, no retransmission is required If no ACK is received before timer expires then all the frames starting from last ACK is resent again and these frames are discarded at the other end if already received before

Piggybacking „

Each direction needs a window Computer Networking / Module II / AKN / 32

Go Back n ARQ: Sender Window size „

Size of Sender window < 2m „

m is the number of bits available in the header to store the

sequence number of the frames „ Let m = 2 then sequence nos are 0, 1, 2, 3 (i.e. 4 frames) „ Sender window size = 3 frames? Other wise there will be problem

Computer Networking / Module II / AKN / 33

Selective Repeat ARQ „

„

„

Go Back n method is inefficient in case of noisy links where there is higher probability of damage, as this method has to resent multiple frames making the condition more worse To avoid this we have another method called Selective repeat ARQ, which resends only the damaged/lost frame instead of all frames. Sender and Receiver windows „

Both have a window having size at most on-half of the value 2m

Computer Networking / Module II / AKN / 34

Selective Repeat ARQ, lost frame

• Draw the figures for • lost Ack • delayed ACK • Piggybacking Computer Networking / Module II / AKN / 35

Selective Repeat ARQ, sender window size

ƒ Bandwidth-Delay Product ƒ It is a measure of efficiency of an ARQ, it is a measure of no of bits that can be sent while waiting from the receiver ƒ i.e. BW (bits/sec) × round trip time (sec) = no of bits

Computer Networking / Module II / AKN / 36

Example In a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit takes 20 ms to make a round trip. What is the bandwidth-delay product? If the system data frames are 1000 bits in length, what is the utilization percentage of the link? What is the utilization percentage of the link, if the link uses Go-Back-N ARQ with a 15-frame sequence?

Solution Stop & Wait ARQ ƒ The bandwidth-delay product is 1 × 106 × 20 × 10-3 = 20,000 bits , can be sent during one RTT, But system sends only 1000 bits. i.e. link utilization is 1000/20,000 = 5%.

Go Back n ARQ ƒ The bandwidth-delay product is still 20,000. ƒ The system can send up to 15 frames or 15,000 bits during a round trip. ƒ This means the utilization is 15,000/20,000 = 75%. ƒ Of course, if there are damaged frames, the utilization percentage is much less because frames have to be resent. Computer Networking / Module II / AKN / 37

HDLC Protocol „

„

High-level Data Link Control is an actual protocol designed(by ISO in 1979) to support half-duplex and full-duplex communication over point-to-point and multipoint links Two Transfer Modes defined „ „

Normal Response Mode (NRM) Asynchronous Balance Mode (ABM)

NRM: in this unbalanced mode one station is designated as primary station and others are secondary

„

A primary station can send commands and secondary stations can only respond to the commands ¾

Uses both point-to-point and multipoint links ¾

Computer Networking / Module II / AKN / 38

HDLC Protocol contd „

Asynchronous Balance Mode (ABM): in this balanced mode each station can command and response. It uses point-to-point link

„

Frames: HDLC defines three types of frames

„

„

„

„

Information Frames (I-Frame):used to carry user data and control information relating to user data Supervisory frames (S-Frame): used only to carry control information Unnumbered Frames (U-Frames): reserved for system management or link management Computer Networking / Module II / AKN / 39

HDLC Frame Formats „ „

„

Each frame contains up to 6 fields as shown above Flag: An 8-bit sequence with a bit-pattern that identifies both beginning and end of a frame and also used for synchronization. Address: It contains the secondary station’s address i.e. a ‘to address’ if frame created by primary or contains a ‘from address’ if created by secondary. „

„

It can be on byte or multiple bytes. If the last bit of one byte is a 1 then there is no other byte. If the last bit is zero then next byte is also contains address The system that does not use primary/secondary configuration like ethernet needs two address field for Computer Networking / Module II / AKN / 40 sender and receiver respectively

HDLC Frame Formats „

„

„

Control: 1 or 2 byte segment used for flow and error control Information: contains user information or network management information. Length is fixed within each network FCS: Frame Check Sequence field contains either a 2byte or 4 byte CRC

Computer Networking / Module II / AKN / 41

HDLC I-Frame Format „

Control field „ „

„

first bit is zero for I-Frame Next thee bits called N(S) represents sequence number of data frames P/F bit used for dual purpose i.e. if value is one then it is either POLL bit or a FINAL bit. If 0 then it is unused „ „

„

„

Poll: when a frame is sent by primary to secondary Final: when frame sent from secondary to primary

Next thee bits called N(R) represents sequence number of ACK frames when piggybacked

Information field „

Contains user users data, i.e. data received from upper layer Computer Networking / Module II / AKN / 42

HDLC S-Frame Format „

„

These frames are used for ACK, flow and error control, i.e. used for ACK whenever piggybacking is inappropriate or not possible Control field „ „ „

First two bits are 10 for S-Frame Next two code bits defines 4 types of S-Frame Receive Ready (RR): value 00, it can be used in 4 different ways „

„ „ „

ACK: P/F=0, used by receiver to send an +ve ACK for a received IFrame, N(R) contains next frame expected Poll: P=1, used by primary for polling Final: F=1, used by secondary to tell that nothing t be sent +ve response to select, F=1, used by secondary, ready to receive

Computer Networking / Module II / AKN / 43

HDLC S-Frame Control field contd. „

Receive Not Ready (RNR): value 10, can be used in 3 different ways „

„ „

„

„

„ „

„

ACK, RNR: used by receiver, acknowledging receipt of all frames up to & excluding N(R), and announces busy condition, i.e. unable to receive more frames Select: P=1, used by primary to send information to secondaries -ve response to Selcet: F=1, used by secondary, unable to receive data

Reject (REJ): value 01, used by receiver to represent –ve ACK (NAK) Selective reject (SREJ): code 11, used by receiver, NAK for Selective repeat ARQ P/F bit is as discussed for I-Frames Next thee bits called N(R) represents sequence number of ACK or NAK value It has no N(S) field as it is never used for data transmission Computer Networking / Module II / AKN / 44

HDLC U-Frame „

„

Theses frames are used to exchange session management and control information It contains 5 code bits having following options Code

Command

Meaning

Response

00

001

SNRM

11

011

SNRME

Set Normal Response Mode Set Normal Response Mode (Extended)

11

100

SABM

Set Asynchronous Balance Mode, Disconnect Mode

DM

11 00

110 000

SABME UI

Set Asynchronous Balance Mode (Extended) Unnumberd Information

UI

00

110

00

010

DISC

Unnumberd Acknowledgement Disconnect, Request Disconnect

10 00 11 11 10

000 1000 001 101 001

SIM UP RSET XID

Set Initialization Mode, Request Information Mode Unnumbered poll Reset Exchange ID Frame Reject

UA RD

RIM

XID FRMR

Computer Networking / Module II / AKN / 45

Data Transparency „

„

„

„

If a data field of an HDLC frame contains a pattern that is same as flag sequence then receiver interprets it the sequence as ending flag which causes problem called lack of data transparency To ensure that the flag sequence does not appear in the any where else in the frame HDLC uses technique called Bit Stuffing According to this technique each time a sender wants to transmit a bit sequence having more than five consecutive 1s, it stuffs (inserts) one redundant 0 after the fifth 1. At the receiving end receiver deletes (unstuffs) one 0 after fifth 1 in the received bit stream. Computer Networking / Module II / AKN / 46

Point-to-Point Access: PPP „

„

„ „

It is deigned to connect home computers to the server of ISP. They are connected to the Internet either through a telephone line or cable TV connection using a modem PPP is a datalink layer protocol PPP provides following services „ „ „

It defines the data format of the frame Establishment of link and exchange of data Authentication Computer Networking / Module II / AKN / 47

Point-to-Point Access: PPP „ „ „

„

„

„ „

It employs a version of HDLC frame Flag: 011111110, identifies boundaries of a PPP frame Address: 11111111, uses broadcast address, as it is a point to point Control: 11000000, format of U-frame and shows that does not contain any sequence number, thus no flow or error control Protocol: it defines the type of data field, i.e. either user data or any other information Data: carries either user data or other information FCS: 2-byte or 4-byte CRC.

Computer Networking / Module II / AKN / 48

Point-to-Point Access: PPP „

„

„

„

Idle state: link is not being used, no active carrier, line is quit Establishing State: one of the endpoints starts communication, options are negotiated. If negotiation is successful, system goes to authentication state Authenticating State: is optional, if successful, connection goes networking state, otherwise goes to termination stage Terminating stage: closing the connection

Computer Networking / Module II / AKN / 49

PPP Stack „

„

PPP uses a stack of protocols to provide the service. Each time, a PPP packet can carry packets related to one of these protocols in its data field. The type of protocol is defined by the protocol field Link Control Protocol (LCP) „

„

It is responsible for establishing, maintaining, configuring, and terminating links Also provides negotiation mechanism to set options

Computer Networking / Module II / AKN / 50

PPP Stack „ „

Code: Type of LCP Packet ID: A value used to match request with reply. Code

„ „

Length: length of LCP Packet Information: extra information needed for LCP Packet

Packet Type

Options: There are many options that can be negotiated between two end points Options are inserted in the information field Some of the options are as follows

0116

Configure-request

0216

Configure-ack

0316

Configure-nak

0416

Configure-reject

0516

Terminate-request

0616

Terminate-ack

0716

Code-reject

Maximum receive unit

1500

0816

Protocol-reject

Authentication protocol

None

0916

Echo-request

Protocol field compression

Off

0A16

Echo-reply

0B16

Discard-request

Address and control field compression

Off

„

„ „

Option

Default

Computer Networking / Module II / AKN / 51

LCP Packet Options „

Configuration Packets: are used to negotiate options „ „ „

„

„

Link Termination Packets: are used to disconnect the link „ „

„

Configuration Request: initiating communication Configuration ACK: if options of configuration Request are accepted. Configure NAK: if configurations are revised, then sender sends a totally new configuration request Configure Reject: if some options are not recognized then these are marked with reject packet, sender send a new configure request Termination Request: either of the two parties Termination Reply: other answers

Link Monitoring and Debugging Packets „ „ „ „

Code Reject: receives a packet with unknown code Protocol Reject: receives a packet with unknown protocol Echo Request & Echo Reply: to monitor the link Discard Request: loop-back test packet, used by sender to check internal condition, request is simply discarded Computer Networking / Module II / AKN / 52

Authentication Protocol „

„

„

PPP is designed to be used over dial-up links where verification of user identity is necessary Two protocols are used for authentication(PAP & CHAP). Password Authentication Protocol(PAP) „

„

User needs to access sends an authentication identification(user name) and a password The system checks the validity of the identification and password and either accepts or denies connection

Computer Networking / Module II / AKN / 53

PAP contd. „

PAP packet is embedded in information frame of PPP „ „ „

Authentication request: request access Authentication-ACK: accept access Authentication-NAK: to deny access

Computer Networking / Module II / AKN / 54

Challenge Handshake Authentication Protocol „

Is a three way handshaking protocol that provides more security than PAP „

„

„

System sends the user a challenge packet containing a challenge value, usually a few bytes User applies a predefined function to received value and own password and produces a result. Sends the result back to system System also performs same operation with same data and compares with the received result.

Computer Networking / Module II / AKN / 55

CHAP Contd. „

4 packet types as shown

Computer Networking / Module II / AKN / 56

Network Control Protocol (NCP) „

„

„

After successful authentication connection goes to network state NCP used to encapsulate data coming from network layer to PPP frame Internetwork Protocol Control Protocol(IPCP) „

„

Before the packet can be sent one more connection at the network layer has to established The set of packets that establish and terminate a network layer connection for IP Packets is called IPCP

Computer Networking / Module II / AKN / 57

Network Control Protocol Contd. „ „ „

„

It uses 7 types of packets Configuration request packet is used to negotiate options with other party After configuration link is ready to carry IP data in the payload field of PPP, and the value of protocol field is changed to 002116 After data transmission again IPCP takes control to terminate the network connection A Complete Example Types of IPCP packets Code

IPCP Packet

01

Configure-request

02

Configure-ack

03

Configure-nak

04

Configure-reject

05

Terminate-request

06

Terminate-ack

07

Code-reject

Computer Networking / Module II / AKN / 58

Lecture II • Multiple Access • Random Access • Controlled Access • Channelization

• Wired LAN: Ethernet (802.3) • Traditional Ethernet • Fast Ethernet • Gigabit Ethernet

• Wireless LAN • IEEE 802.11 • Bluetooth (802.15) Computer Networking / Module II / AKN / 59

Access Control „

„

The way to coordinate access to a link when used by more than one device The methods may be classified as follows

Computer Networking / Module II / AKN / 60

Random Access „

„

„

According to this method , each station has the right to the medium without being controlled by any other station Some procedures are defined to resolve the access conflict called collision. Multiple Access (ALOHA) „

„

Any station sends when a frame is ready Waits for an ACK, if not received in allotted time then the frame is resent Computer Networking / Module II / AKN / 61

Carrier Sense Multiple Access (CSMA) „

„

„

„

„

To minimize the chance of collision, The CSMA method is developed Each station listens before transmitting. i.e. transmission is possible only if line is idle Possibility of collision still exists because of propagation delay The garbled signal reaches at times t4 and t5 respectively Two strategies to sense a busy medium „ „

Non persistent persistent

Computer Networking / Module II / AKN / 62

CSMA, Persistence Strategies „

„

If the line is idle, station sends immediately, otherwise waits a random period of time before resending Reduces the chance of collision as it is unlikely that two stations will wait same amount of time. But decreases efficiency as waits unnecessarily random amount of time „

„

„

If the line is idle, the station sends with a probability 1-persistent: station sends frame with a probability 1 (i.e. 100%). Increases chance of collision P-persistent: station sends a frame with a probability p and refrains with a probability 1p Computer Networking / Module II / AKN / 63

CSMA/CD (Collision Detection) „

After sending the system monitors for a collision „

„

If collision detected, it informs others by sending a jam signal and waits for some time(?) before resending

To reduce the probability of collision, station waits for a little time for first time. Changes waiting time for subsequent collision

Computer Networking / Module II / AKN / 64

CSMA/CD Contd. „

Back-off methods „

„

„

„

Exponential Back-off n „ System waits between 0 – 2 ×max-propagation time „ ‘n’ is the attempted no of transmissions Random Back-off „ system waits for a random amount of time before resending. „ The random number is generated based on current value of parameter n. „ ‘n’ is initially 0 and incremented by one each time a collision occurs

When jam signal is received by others, they will discard the part of the frame received. This method is used in traditional Ethernet Computer Networking / Module II / AKN / 65

CSMA/CA (Collision Avoidance) „

„

This procedure avoids collision, uses one of the persistence strategies After it finds a line is idle „

„

„

System waits an Inter Frame Gap (IFG) amount of time then another random amount of time before sending and sets a timer If it does not receive ACK before timer expires then it increments back-off and waits this amount of time before sensing the line again.

Used in W-LANs.

Computer Networking / Module II / AKN / 66

Controlled Access „

„

A Station cannot send unless authorized by other stations Reservation Method „ „

„

A station needs to reserve before sending Time is divided into intervals, In each interval, a reservation frame precedes the data frames sent in that interval If N stations are there in the system, there are exactly N reservation mini slots. Each belonging to a station

Computer Networking / Module II / AKN / 67

Polling „ „

„ „

One device designated as primary and others are as secondary Primary has control over the link, the secondaries follows instructions Polling: Primary asks secondary if they have anything to send Select: primary needs to send to a secondary

Computer Networking / Module II / AKN / 68

Token Passing A station authorized to send data when it receives a special frame called token „ A token keeps circulating around the ring „ If a station needs to send it captures the token and sends data frames. „ Finally it releases the token when finishes. Now the token may be used by others „

Computer Networking / Module II / AKN / 69

Channelization „

„ „ „

„

In this method the available bandwidth of a link is shared in space, time, frequency or through code SDMA: space is divided FDMA: The bandwidth is divided into channels TDMA: bandwidth is one channel that is time shared CDMA: one channel carries all transmissions simultaneously with different code Computer Networking / Module II / AKN / 70

FDMA „ „ „ „

„

Separation of the whole spectrum into smaller frequency bands A channel gets a certain band of the spectrum for the whole time Advantages: no dynamic coordination k1 k2 k3 k4 k5 k6 necessary c works also for analog signals f

„ „

„ „

Disadvantages: waste of bandwidth if the traffic is distributed unevenly inflexible t guard spaces Computer Networking / Module II / AKN / 71

TDMA „

A channel gets the whole spectrum for a certain amount of time k k k 1

„

Advantages: „

„

2

3

k4

k5

k6

c

only one carrier in the medium at any time throughput high even for many users

f

t

„

Disadvantages: „

precise synchronization necessary Computer Networking / Module II / AKN / 72

FTMA „ „

„ „

Combination of both methods A channel gets a certain frequency band for a certain amount of time Example: GSM Advantages: „ „

„

„

better protection against tapping protection against frequency selective interference higher data rates compared to code multiplex

k1

k2

k3

k4

k5

k6

c f

but precise coordination required t

Computer Networking / Module II / AKN / 73

CDMA „

Each channel has a unique code k1

„

„

All channels use the same spectrum at the same time Advantages: „ „

„

„

k3

k4

k5

k6

c

bandwidth efficient no coordination and synchronization necessary good protection against interference and tapping

f

Disadvantages: „ „

„

k2

lower user data rates more complex signal regeneration

Implemented using spread spectrum technology

t

Computer Networking / Module II / AKN / 74

Access method - Mathematical Representation

Each station is assigned a code, which is a sequence of numbers called chips „ 0 represented as –1 and 1 as +1 „

Computer Networking / Module II / AKN / 75

„

Disadvantages: „

„

„

higher complexity of a receiver (receiver cannot just listen into the medium and start receiving if there is a signal) all signals should have the same strength at a receiver

Advantages: all terminals can use the same frequency, no planning needed „

huge code space (e.g. 232) compared to frequency space

„

„

interferences is not coded

forward error correction and encryption can be easily integrated

„

Computer Networking / Module II / AKN / 76

Codes in CDMA ¾

What is a good code for CDMA? ¾

¾

A code for one user should have a good autocorrelation and should be orthogonal to other codes If inner product of two vectors is zero then two vectors are said to be Orthogonal ¾

¾ ¾

¾

(2,5,0) × (0,0,17) = 0 + 0 + 0 = 0

It has a similar meaning in code space also If the inner product of a code with itself is very large and drops when shifted by one chip. It stays at that low value until the code matches itself again perfectly Example Barker code

+ - + + - + + + - - + + - + + - + + + - + - - + - - + + - + +

Original Shifted once

sop ¾Thus Barker code has a good autocorrelation and this property helps receiver to reconstruct the original data precisely

Computer Networking / Module II / AKN / 77

Sequence Generation „ „

„

Walsh table is used to generate the sequence. It is a two-dimensional having equal number of rows and columns Each row is a sequence of chips

W2=4W1, with last w1 complemented W4=4W2, with last W2 complemented

Computer Networking / Module II / AKN / 78

Properties of Orthogonal Sequences „

If –1 is multiplied with the sequence, every element is complemented „

„

Inner product of same sequence = N (N is the no of chips in the sequence) „

„

C.C = [+1, +1, -1, -1]. [+1, +1, -1, -1] = 1+1+1+1 = 4

Inner product of diff sequences = 0 „

„

C.-1 = [+1, +1, -1, -1].-1 = [-1, -1, +1, +1]

B.C = [+1, -1, +1, -1].[+1, +1, -1, -1] = 1-1-1+1=0

Inner product of a sequence with its complement = -N „

C.-C = [+1, +1, -1, -1]. [-1, -1, +1, +1]=-1-1-1-1=-4

Computer Networking / Module II / AKN / 79

Local Area Networks: Ethernet „

„

„

„ „

„

Designed for a limited geographical area such as a building or campus Most dominant technology used today for LAN is Ethernet The original ethernet was designed at Xerox’s Palo Alto Research Center (PARC) The LLC sub-layer is not used often today LANs differ in their MAC sub-layer and physical layer ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, Computer Networking / Module II / AKN / 80

Three Generations of Ethernet

Computer Networking / Module II / AKN / 81

Traditional Ethernet „ „ „

„

„

„

Designed to operate at 10Mbps Access method used is 1-persistent CSMA/CD Frame defined by 802.3, contains seven fields

Preamble: 7bytes of alternating 0s and 1s that alert the receiving system to the coming frame and enable it to synchronize Start Frame Delimiter: 1 byte (10101011) signals beginning of frame. Last chance for synchronization. Destination and Source address: 6 bytes, contains the physical address of source and destinations Computer Networking / Module II / AKN / 82

Traditional Ethernet „

„

„ „

Length/Type: if val ≤ 1518 then it represents length of data if val ≥ 1536 -> type of PDU that is encapsulated Data: carries data encapsulated from the upper layer protocols. Min of 46 bytes and a max of 1500 bytes CRC: it uses CRC –32 for error detection Frame length „

„

„

„ „

is restricted to 64 bytes min, 1518 bytes max for correct operation of CSMA/CD A collision must be heard before the total frame is sent otherwise MAC will discard the frame and start sending the next frame Standard defines the smallest length for 10 Mbps Ethernet as 512 bits or 64 bytes without preamble and SFD These 64 bytes contains 18 bits of header and 46 bytes of data. Max frame length is 1518, thus data can be upto 1518-18=1500 bytes Computer Networking / Module II / AKN / 83

Physical Address „ „

„

The 6-byte (48-bit) physical address is embedded into NIC. The address is normally represented in two-digit hexadecimal notation They are written hyphenated by octets „

„

e.g. 12:34:56:78:9A:BC

This gives a theoretical 281,474,976,710,656 addresses. „ „

„

This is more than 56,000 MAC addresses for each person on the planet! In practice, the address assignment policy will inevitably lead to some wastage - but even so, there are likely to be enough addresses for ever. computer, and a large number of household/office devices (heating systems, ovens, washing machines, fridges, dispensers, security alarms, video recorders, ...) which could in the future be internet enabled!!!

Computer Networking / Module II / AKN / 84

Physical layer • PLS Encodes using Manchester scheme • For a datarate of 10 Mbps, a BW of 20 Mbaud is needed? • AUI defines the interface between PLS and MAU • MAU is medium dependent, It creates appropriate signal for a particular medium • It transmits, receives and detects collision Computer Networking / Module II / AKN / 85

Categories of traditional Ethernet

Computer Networking / Module II / AKN / 86

10Base5

• called Thicknet, One segment < = 500 mts and uses RG 8 cable • Access method is CSMA/CD • AUI is 15 wire cable and DB-15 connector • AUI length < 50 mts • Uses BUS topology

10Base2

• Called Thinnet, uses CSMA/CD • RG-58 cable, span length <= 185 mts • Bus topology LAN, uses BNCT connectors Computer Networking / Module II / AKN / 87

10Base-T, Twisted Pair Ethernet 10Base-FL (Fiber Link)

• Uses star topology LAN, with a hub to connect multiple devices • max length 100 mts • UTP cable and RJ-45 connectors

• Star topology LAN with a hub • Uses two pairs of fiber optic cables Computer Networking / Module II / AKN / 88

Sharing bandwidth, Changes in standard • If more than one station starts sending then the capacity is shared

• If two stations have a lot of frames to send via a 10Mbps link, they alternate the usage of link • On average, each station sends 5Mbps, i.e. the capacity for each station is BW/n Computer Networking / Module II / AKN / 89

Bridged Ethernet • A bridge divides a LAN into two or more segments • Now the full capacity may be used independently by each segment, i.e. theoretically the capacity of each segment is 10/6 Mbps instead of 10/12Mbps • Thus Bridged LAN raises the bandwidth of a LAN

Computer Networking / Module II / AKN / 90

Collision domains • Another advantage of using a bridge is the separation of collision domain, but broadcast domain remains the same • smaller collision domains results in better performance of the LAN

Computer Networking / Module II / AKN / 91

Switched Ethernet • Like a bridge, Switch divides the LAN into N number of segments where each segment contains only one station. i.e. equivalent to a bridged LAN with one computer per segment • i.e. Collision domain is divided into N domains. Communication among any two station will not disturb others • The bandwidth is shared by the node and switch

Port 3 Port 1 Port 2

SWITCH

Computer Networking / Module II / AKN / 92

Full-duplex switched Ethernet • In full-duplex switched Ethernet, each station is connected to the switch via two separate channels •The full duplex mode increases the capacity of each domain • No need for CSMA/CD as each link is a point to point dedicated path between switch and node • Traditional Ethernet was designed as a connection less protocol without flow and error control • A new sub-layer is added called MAC control between LLC and MAC for full-duplex switched Ethernet to provide flow and error control Computer Networking / Module II / AKN / 93

Fast Ethernet (100 Mbps) „ „

IEEE 802.3u Access method, frame format, min and max frame length and addressing are same as Traditional Ethernet (10 Mbps) „

„

There is no need for CSMA/CD, but it is there to be compatible with traditional Ethernet

Auto negotiation: A new feature added to Fast Ethernet that allows a station or a hub to „

„ „

Allow incompatible devices to connect one another. i.e. back word compatible with traditional Ethernet to work in 10Mbps Allow one device to have multiple capabilities. Allow a station to check hub’s capabilities Computer Networking / Module II / AKN / 94

Fast Ethernet physical layer Four sub-layers: 1. Reconciliation(RS) ƒ

It replaces the PLS sub-layer in 10Mbps Ethernet

ƒ

It is specifically used to pass data in a 4bit format (nibble)

2. Medium Independent Interface (MII)

ƒ

AUI is replaced with MII

ƒ

This is improved to be used with both 10 and 100 Mbps data rate i.e. backward compatible Computer Networking / Module II / AKN / 95

Fast Ethernet Contd. ƒ

It provides a parallel data path (nibble) between the PHY and RS

ƒ

Management functions are added

3. Physical layer entity(PHY) ƒ ƒ ƒ ƒ

This is the transceiver in fast Ethernet It is responsible for encoding and decoding The transceiver can be external or internal An external transceiver is installed close to medium and is connected via an MII cable

4. Medium dependent interface (MDI) ƒ ƒ

Used to connect the transceiver to the medium and is implementation specific Is a hardware and implementation specific Computer Networking / Module II / AKN / 96

Fast Ethernet Implementations

Computer Networking / Module II / AKN / 97

100Base-TX implementation

• Uses 2 pairs of cat5/STP twisted pair with Star topology • Transceiver is responsible for transmitting, receiving, detecting collisions, and encoding and decoding of data

Encoding and decoding •To maintain synchronization, the encoder first performs block encoding. • The 4 parallel bits received from NIC are encoded into 5 serial bits using 4B/5B (requires a bw of 125MHz i.e 125Mbps) • The data is then encoded in to MLT-3 Computer Networking / Module II / AKN / 98

100Base-FX Implementation

• uses two pairs of fiberoptic cables in a physical star topology • The transceiver is responsible for transmitting, sending, detecting the collision, and encoding/decoding.

Encoding and Decoding •To maintain synchronization, the encoder performs block encoding • The four parallel bits received from NIC is encoded into 5 serial bits using 4B/5B • Then the data is encoded using NRZ-I Computer Networking / Module II / AKN / 99

100Base-T4 Implementation

ƒ Uses Cat-3, 4-pair UTP ƒ uses 8B/6T for encoding and decoding, which reduces the bW from 100 to 75Mbaud. ƒ 100Base-T4 is designed to operate on 25-Mbaud BW ƒ Two pairs are designed for unidirectional transmission, other two for bi-directional transmission. Unidirectional pairs are kept free to Computer Networking / Module II / AKN / 100 carry collision signals.

Gigabit Ethernet „ „ „

„

„

IEEE 802.3z Uses full-duplex mode without CSMA/CD Lack of collision implies that the max length of the cable is determined by the signal attenuation in the cable, not by the collision detection process GMII specifies a parallel data path (8 bits at a time) between RS sub-and transceiver Implementation „

„

Gigabit Ethernet can be categorized as either a two wire or a four wire implementation. The two wire implementations use either fiber-optic cable (1000Base-SX, shortwave or 1000Base-LX, long wave) or STP (1000Base-CX) Computer Networking / Module II / AKN / 101

Gigabit Ethernet The four wire version uses category-5 twisted pair cable (1000Base-T) Two wire implementations use NRZ encoding after 8B/10B block encoding One wire is used for sending another for receiving (fiber or STP) The four wire implementation uses 4DPAM5 to reduce the bandwidth All four wires used for input and output and carries 250Mbps each „

„

„

„

„

Computer Networking / Module II / AKN / 102

Wireless LANS ƒ Defined by IEEE 802.11 & Bluetooth ƒ The standard 802.11 defines two kinds of services ƒ

Basic Service Set(BSS): the basic building block of WLan

ƒ

Extended Service Set(ESS): communicating among BSSs

ƒ Basic Service Set ƒ

Is made of stationary or mobile wireless stations and an optional central base station known as Access Point (AP)

Computer Networking / Module II / AKN / 103

Service Sets ƒ

The BSS without AP is a stand alone network and can’t send data to other BSSs

ƒ

It is called an Ad hoc Network or Infrastructure Less Network

ƒ

An BSS with an AP is called Infrastructure based network

ƒ Extended Service Sets ƒ Is made up of two or more BSSs with Aps ƒ Communication between two stations in two different BSSs usually occurs via two Aps ƒ APs are connected via distribution System

Computer Networking / Module II / AKN / 104

Station types „

Three types of stations are defined based on their mobility „

No-transition „

„

BSS-transition „

„

is either stationary or moving only inside a BSS can move from one BSS to another, but the movement is confined to one ESS

ESS-transition „

can move from one ESS to another. But standard does not guarantee the continuity in communication Computer Networking / Module II / AKN / 105

Protocol Architecture „ „

„

„

It covers MAC and physical layer The basic tasks of MAC is medium access, fragmentation, and encryption. The MAC management supports the association and reassociation of a station to an access point and roaming between APs, it also controls authentication mechanisms, synchronization with AP etc. Physical layer provides carrier sense signal, modulation encoding/decoding of signals

Computer Networking / Module II / AKN / 106

Physical Layer • 802.11 supports three different physical layers • one layer based on infra-red and two layers based on radio transmission (in ISM band at 2.4 GHz) • FHSS: Frequency hopping spread Figure from chap 6, 4ed spectrum for signal generation in a 2.4 GHz ISM band in 79 sub-bands, each with a BW of 1MHz • A pseudorandom number generator selects the hopping sequence and the sender and receiver agree on the sequence of the allocated bands. • The amount of time spent at each sub-band is called dwell time(400ms) • Modulation is either a 2-level GFSK at 1Mbaud/s or 4-level GFSK at 2bit/baud resulting in the data rate of 1Networking or 2 Mbps Computer / Module II / AKN / 107

Direct Sequenced Spread Spectrum(DSSS) • Each bit sent by the sender is replaced by a sequence of bits called a chip code (CDMA). It uses 11 bit Barker sequence(10110111000). Uses entire band of 2.4 GHz • The data rate for sending chip codes is 11 times the data rate of the original bit stream • Modulation is Differential Binary PSK at 1Mbaud/s or DQPSK for 2Mbps

Infrared • uses Infrared light in the range of 850 to 950 nm • max range is 10m if no sunlight or heat sources interfere. • Today no products are available that offer this type of communication Computer Networking / Module II / AKN / 108

IEEE 802.11a OFDM „ „ „ „

Orthogonal frequency division multiplexing in 5GHz ISM band 52 sub-bands, 48 used for data and 4 for control information Uses PSK and QAM Datarate is 18Mbps, and 54Mbps

IEEE 802.11b HR-DSSS „ „

„ „ „

High-rate DSSS in 5GHz ISM band Uses Complementary Code Keying, which encodes 4 or 8 bits into one CCK symbol Uses 2.4 MHz ISM band Defines 1, 2, 5.5 and 11 Mbps IEEE 802.11g uses OFDM with 2.4 GHz ISM band and achieves 54Mbps data rate Computer Networking / Module II / AKN / 109

MAC sub-layers in IEEE 802.11 ƒ Defines two MACs and is called as Distributed Foundation Wireless Medium Access Control (DFWMAC)

ƒ Distributed coordination function(DCF) ƒ The CSMA/CD access method of ethernet fails in wireless medium ƒ so it uses the basic method CSMA/CA and an optional method avoiding hidden terminal problem

ƒ Point coordination function (PCF) ƒ uses contention free polling method by AP for time bounded service Computer Networking / Module II / AKN / 110

Motivation for CSMA/CA „

WLANs cannot implement CSMA/CD because „

„

„

„

It requires that the station must be able to send data and receive collision at the same time. (i.e. two paths and increased BW!) Collision may not be detected due to hidden terminal problem Signal fading could prevent a station at one end from hearing a collision from other end called near/far terminal problem Thus DCF implements CSMA/CA Computer Networking / Module II / AKN / 111

Hidden and Exposed terminals „

Hidden terminals „ „ „ „

„

A sends to B, C cannot receive A C wants to send to B, C senses a “free” medium (CS fails) collision at B, A cannot receive the collision (CD fails) A is “hidden” for C

Exposed terminals

A

B

C

B sends to A, C wants to send to another terminal (not A or B) „ C has to wait, CS signals a medium in use „ but A is outside the radio range of C, therefore waiting is not necessary Computer Networking / Module II / AKN / 112 „ C is “exposed” to B „

Near and Far terminals „

Terminals A and B send, C receives „

„ „

signal strength decreases proportional to the square of the distance the signal of terminal B therefore drowns out A’s signal C cannot receive A

A

B

C

Also severe problem for CDMA networks as all signals arrive with more or less same strength - precise power control needed! ¾

Computer Networking / Module II / AKN / 113

Inter-frame spacing times „

802.11 MAC uses three different parameters for waiting time that define the priorities of medium access „

„

„

„

Short inter-frame spacing(SIFS): shortest waiting time and hence highest priority is defined for control messages like ACK or polling responses, for DSSS SIFS is 10µs and for FHSS it is 28µs PCF inter-frame spacing(PIFS): A medium priority waiting time used for a time-bounded service like AP polling. Defined as SIFS plus one slot time DCF inter-frame spacing(DIFS): longest waiting time and has the lowest priority for medium access. Used for data service within a contention period Defined as SIFS plus two slot times Slot time is 50µs for FHSS and 20µs for DSSS Computer Networking / Module II / AKN / 114

Basic DFWMAC-DCF without RTS/CTS „

„

„

5 stations competes for sending at arrow marks At first sta3 accesses the medium at t1 Sta1, sta2, sta5 waits till the carrier is free (t2)then waits for DIFS then start there back-off timer within the contention window

t0

t1

t2

t3

t4

t5

t6 t 7

t8

t9 t 10

sta1 sta21 sta3 sta4 sta5

Sta2 gets access as it has smallest back-off time at t4 „ sta1, sta5 stops their back-off timer and stores their residual back-off time „ sta4 wants to send between t4 and t5, all three starts their timer at t6. Accidentally timers of sta4 and sta5 finishes same time(t7). Thus there is a collision and sta5 stops its timer. „ finally sta5 gets the medium at t10 „

Computer Networking / Module II / AKN / 115

Basic DFWMAC-DCF Unicasting „

station has to wait for DIFS before sending data contention

receivers acknowledge at once (after waiting for SIFS) if the packet was received correctly (CRC) „ no other station can transmit because DIFS is greater than SIFS, hence no chance of collision „ If no ACK is received sender automatically retransmits the frame „ but the sender has to wait again and compete for the access right to retransmit „

Computer Networking / Module II / AKN / 116

Process CSMA with CTS and RTS

„

Before sending a frame source senses the medium

Channel uses a persistent strategy with back-off until the channel is idle „ Station now waits for a period of time called the Distributed Inter-Frame Space; then sends a control frame called RTS (request to send) „

After receiving the RTS and waiting a short period of time called short interframe space, the destination station sends a control frame called CTS(clear to Send) „ Source sends data after waiting an amount of time equal to SIFS Computer sending Networking / ACK Module II / AKN / 117 „ Destination waits for SIFS before

„

CSMA/CA flowchart

Computer Networking / Module II / AKN / 118

Process Collision Avoidance When station sends RTS frame, it includes the duration of the time that it needs to occupy the channel „ The stations that are affected by this transmission create a timer called NAV. „ Each other station first checks NAV before sensing the channel „ If two or more stations try to send RTS at the same time and there is a collision, then sender tries again if it does not receive CTS „

As the wireless medium is noisy, It is more efficient to replace a large frame with some smaller frames. Computer Networking / Module II / AKN / 119 „

Hidden node provision for contention free access „

„

„

„

„ „ „

Sender issues a RTS after DIFS (if medium was not busy) RTS contains duration of transmission, every node listening to it sets NAV Receiver answers with CTS which includes another duration and all listening nodes readjust their NAV This method reserves the medium for one sender thus called a virtual reservation scheme Sender sends data and receives ACK after SIFS each. When NAV expires the standard cycle starts again Using RTS/CTS is an overhead. Usually it is essential for large frames and not needed in caseComputer of shortNetworking frames / Module II / AKN / 120

Fragmentation, DFWMAC-DCF „

„

„ „

„

Wireless LAN have much more bit error rate than any other guided media. Wireless LAN have much more bit error rate than any other guided medium for same frame length. Standard specifies a fragmentation mode to reduce bit error rate Here frag1 also contains a duration which is used to set NAV in case of mobile nodes or for a different set of nodes, this mechanism further reduces the collision. If frag2 is not the last frame then it should contain another duration. It is not required for last fragment. Computer Networking / Module II / AKN / 121

DFWMAC – PCF with polling „

„

„

„ „

„

„

„

DCF could not cant guarantee a maximum access delay or minimum transmission BW To provide a time bound service, the standard specifies a point coordination function (PCF) on top of standard DCF mechanisms Using PCF requires a access point that controls medium access and polls one node at a time. Ad-hoc networks cant use this function The point coordinator in access point splits the access time into super frame periods. A super frame comprises a contention-free period and a contention period. It is because due to the priority of PCF over DCF, stations that only use DCF may not gain access to the medium. To prevent this the super frame other wise called as repetition interval has been designed to cover both traffic Computer Networking / Module II / AKN / 122

Contention free access using Polling Theoretical contention period starts at t0, but as another station still transmitting thus start of super frame postponed till t1 „ The point coordinator starts polling sta1 by sending D1 after PIFS and it responds with U1 after another SIFS „ If stai has nothing to send then it will not respond so that after another PIFS the coordinator polls next stai+1 „ Finally, the coordinator issues an end marker called CFend so that the contention period starts. After which the cycle starts again with next super frame „

„

Using PCF automatically sets NAV

Computer Networking / Module II / AKN / 123

MAC sub-layer Frame format

Field

Frame Control sub-fields Explanation

Version

The current version is 0.

Type

Type of information: management (00), control (01), or data (10).

Subtype

Defines the subtype of each type

To DS

Defined later.

From DS

Defined later.

More flag

When set to 1, means more fragments.

Retry

When set to 1, means retransmitted frame.

Pwr mgt

When set to 1, means station is in power management mode.

More data

When set to 1, means station has more data to send.

WEP

Wired equivalent privacy. When set to 1, means encryption implemented.

Rsvd

Reserved.

Computer Networking / Module II / AKN / 124

Other fields

„

D: This field defines the duration of the transmission used to set NAV Addresses: Four address fields, each 6byte long Sequence Control: Defines the sequence# of the frame used for flow control Frame body: Contains information based on the type and subtype field in FC FCS: 4byte CRC-32 error detection sequence

„

Frame types: standard defines three types of frames

„

„ „

„

„

„

„

Management frames: Are used for the initial communication between station and access points Control frames: Used for accessing the channel and ACK frames Data frames: used for carrying data and control information Computer Networking / Module II / AKN / 125

Control Frame format ƒ For control frame type field is 01

Addressing Mechanism (FC) To From DS DS

Address 1

Address 2

Address 3

Address 4

Subtype

Meaning

1011

Request to send (RTS)

1100

Clear to send (CTS)

1101

Acknowledgment (ACK)

Add 1: address of next device Add 2 : the address of previous device

0

0

Destination Source station station

BSS ID

N/A

0

1

Destination Sending station AP

Source station

N/A

1

0

Receiving AP

Source station

Destination N/A station

1

1

Receiving AP

Sending AP

Destination Source station station Computer Networking / Module II / AKN / 126

Add 3 : the address of Final destination if not defined by Add 1 Add 4 : the address of original source if not same as Add 2.

Addressing mechanism: case 1

Case 2

To DS=0, from DS=0 • the frame is not going and is not coming from a distribution system.

To DS=0, from DS=1

• i.e the frame is going from one station in a BSS to another system without passing through distribution system

• i.e the frame is coming from an AP and going to a station

• the frame is coming from a distribution system.

• The ACK is sent to the AP

Computer Networking / Module II / AKN / 127

Addressing mechanism: case 3

case 4

To DS=1, from DS=0

To DS=1, from DS=1

• the frame is going from a station to an AP

• The frame is going from one AP to another AP via wireless medium

• The ACK is sent to the original station • Address 3 contains the final destination in another BSS

• As in wire medium ethernet frame has to be used Computer Networking / Module II / AKN / 128

Bluetooth „

„

„ „

„

„

Is a wireless LAN technology designed to connect devices of different functions such as telephones, notebooks, computers, cameras, printers, coffee makers, and so on A Bluetooth LAN can be connected to Internet if one of the gadgets has this capability It can not be large This technology can be used to connect peripheral devices to computer, monitoring devices can be connected to sensors etc. Originally developed by Ericsson and named after Harald Blaatand (king of Denmark, 940-981). Later in 1998 five companies (Ericsson, Intel, IBM, Nokia, Toshiba) founded Bluetooth consortium to develop a low cost, single chip, radio based wireless network Today the Bluetooth technology is the implementation of a protocol defined by 802.15 and is called WPAN that is operable in a small area with small number of devices Computer Networking / Module II / AKN / 129

Bluetooth „

A Bluetooth network is called a piconet and needs no infrastructure, this type of WPANS may be used in various scenarios „ Connection of peripheral devices to a desktop „ Support of ad-hoc networking „

„

Bridging of networks „

„

e.g. teacher distributing data to students PDAs inside the class Using piconets, a mobile phone can be connected to a PDA or laptop. The mobile phone can now act as a bridge between local piconet and GSM

Bluetooth is designed to provide local wireless access at very low cost with a limited BW and without any extra infrastructure Computer Networking / Module II / AKN / 130

Bluetooth Architecture „

„

„

Operates on 79 channels in 2.4GHz band with 1MHz carrier spacing Each device performs frequency hopping with 1600 hops/sec in a pseudo random fashion A piconet is a collection of Bluetooth devices which are synchronized to the same hopping sequence with following properties

ƒ Can have up-to eight stations, one of which is called the Master, rest are slaves ƒ Master determines hopping pattern ƒ Communication may be on-to-one, or oneto-many ƒ An additional eighth slave may be in parked state, i.e. cant participate actively in piconet ƒ The limit is eight because the address field contains 3 bits and any parked device can be active if one of the seven slaves goes to parked state

Computer Networking / Module II / AKN / 131

Bluetooth Architecture A group of piconets is combined to form a scatternet and can accommodate more devices. „ Different piconets in a scatternet use different hopping sequences „ One device may participate in more than one piconet one at a time ƒ A master of one piconet can act as a slave in other piconet but one cant be master in two piconets „

ƒ communication between different piconets takes place by devices jumping back and forth between these nets ƒ however scatternets are not yet supported by all devices Computer Networking / Module II / AKN / 132

Bluetooth layers (Protocol Stack) „

Radio Layer „

„

„ „

Specifications of air interface and equivalent to physical layer of internet model Band: 2.4GHz ISM band divided into 79 channels of 1MHz each FHSS: 1600 hops/sec, i.e. one frequency is used for 625 µs Modulation: uses Gaussian FSK and are available in three classes „

„

„

Power class 1: max power of 100mW and min power of 1mW, 100m range without obstacles Power class 2: max power of 2.5mW and min power of 0.25mW, 10m range without obstacles Power class 3: max power of Computer 1mW Networking / Module II / AKN / 133

Base Band Layer „ „

„

„

Uses Time Division Duplex-TDMA If the piconet has only one slave, then the master uses even numbered slots and slave uses odd numbered slots TDD-TDMA allows the communication in half-duplex mode. i.e. in slot 0 master sends and slave receives and in slot 1 slave sends master receives If it has more slaves then master uses even numbered slots where as odd numbered slots are used by slaves. if master sends to slave 1 at slot 0 then slave 1 answers at slot 1 then master sends to slave 2 in slot 2 slave 2 answers at slot 3, and the cycle continues Computer Networking / Module II / AKN / 134 „

Base Band Layer Frame format „

A frame can be of three types „

„ „

„

„

One slot frame: 259µs is used for hopping and control mechanism thus the frame can last upto 366µs or of 366 bits Three slot frame: length of frame = 3*625-259=1616 bits Five slot frame: length of frame = 2866 bits

Access code: contains synchronization bits and the identifier of master Header: is a repeated 18 bit pattern, each pattern contains „

Address: represents active slave address. can define seven secondaries, 0 is used for broadcasting from master to slaves Computer Networking / Module II / AKN / 135

Base Band Layer Frame format contd. „ „ „ „ „ „

„ „

Type: type of data coming from upper layer F: used for flow control A: used for ACK, uses stop and wait ARQ without retransmission S: sequence number of frame HEC: header error correction uses checksum The header has three identical 18-bit sections. Receiver compares these three sections bit by bit. If all three corresponding bits are same than the bit is accepted otherwise majority is taken. This is a form of Forward error correction Payload: it contains the data or control information from upper layers. Computer Networking / Module II / AKN / 136

L2CAP data packet format „

„ „ „

The logical link control and adaptation protocol is used for data exchange on an asynchronous connection link

Length defines the size of the data, in bytes CID defines a unique identifier for the virtual channel created L2CAP duties „ Multiplexing: supports many application layer protocols „ Segmentation and reassembly: divides large packets of upper layer (65535) to smaller size „ QoS: uses best effort service „ Group management: allows devices to create logical addressing among themselves to form a multicast group

Computer Networking / Module II / AKN / 137

Lecture III • Wide Area Networks • Virtual Circuit • Frame Relay • ATM

Computer Networking / Module II / AKN / 138

Wide Area Networks „

„

„

„

„

WANs provide long distance transmission over large geographical areas It utilizes public, leased or private communication equipments to span over countries or continents It uses one of the packet switching methods called virtual circuit switching. Frame relay is a link layer protocol used in WAN technology, which provides relatively high speed transmission ATM (Asynchronous Transfer Mode) is another protocol for WAN technology that works as a super highway of communication. Computer Networking / Module II / AKN / 139

Virtual circuit switching in WAN „

Global Addressing „

„

A source or destination need to have a global address, which should be unique in the scope of WAN

Virtual Circuit Identifier „

„

„

Is a small number that only has switch scope and is actually used for data transfer i.e it is used by a frame between two switch When a frame arrives a switch, it has one VCI; when it leaves, it has another Computer Networking / Module II / AKN / 140

VCI Phases „

„

To communicate, the source and destination need to go through three phases. i.e. setup, data transfer, & tear down Data Transfer phase „

„

All switches have table called a switching table with at least 4 columns When a frame arrives it checks its VCI and incoming port no.

Computer Networking / Module II / AKN / 141

Data transfer Phase „

„

It finds corresponding out going port and changes the VCI as in the table before sending out The data transfer phase is active until the source sends all its frames

Computer Networking / Module II / AKN / 142

Setup Phase „

Setup phase „

„

„

Source and destination use their global addresses to help switches make table entries for connection Two approaches: PVC, SVC

Permanent Virtual Circuit „

„

„

„

For each destination one circuit is dedicated (always present) whether in use or not The corresponding table entry is recorded for all switches by the administrator An out going VCI is given to the source, and an incoming VCI is given to the destination If there is a need for duplex communication then two virtual circuits are established Computer Networking / Module II / AKN / 143

Switched Virtual Circuit „

„

SVC creates a temporary connection, that exists only when data are transmitted between source and destination Setup request „

„

Source sends the set up frame to the switch, switch finds out going port from its routing table and creates entry in the switching table for the incoming virtual circuit

Acknowledgement „

The last field of switching table entry is made from ACK

setup

ACK

Computer Networking / Module II / AKN / 144

Frame Relay „

„

„ „ „ „

„

Is a virtual circuit switching WAN used between 1980 – 1990 It operates at a higher speed (1.544Mbps, now 44.376Mbps) Operates in physical and datalink layer Allows bursty data with a frame size of 9000 bytes It is less expensive than other traditional WANs It has error detection mechanism at datalink layer. No flow or error control schemes available. It is so designed to provide fast transmission capability for more reliable media and for those protocols that have flow and error control at the higher layers

Computer Networking / Module II / AKN / 145

Frame Relay Architecture „ „

„

Frame relay network can be a part of Internet Frame relay uses both PVC and SVC. The virtual circuit is identified by a number called Data Link Control Identifier(DLCI is same as VCI)

Frame Format

Computer Networking / Module II / AKN / 146

Frame format contd. „ „

„

DLCI: total 10 bit used as connection identifier Command/response (C/R): used by upper layers to identify the frame as either a command or response Extended Address(EA): if 0 then another address byte to follow; if 1 then current byte is the final byte

Computer Networking / Module II / AKN / 147

Frame format contd. „

„

„

FECN: can be set by any switch to indicate that the traffic is congested in the direction of flow BECN: is set to indicate a congestion in the opposite direction Discard eligibility(DE): this bit indicates the priority level of the frame according to which the frame may be discarded in case of congestion Frame Relay Assembler/Dissembler (FRAD) „

This device is used to to handle frames coming from other protocols

Computer Networking / Module II / AKN / 148

Other features Voice Over Frame Relay (VOFR) Used to send voice by digitizing the voice using PCM and then sent in data frames

Local Management Information (LMI) Is a protocol added to frame relay to provide more management features, It provides A keep alive mechanism to check if data are flowing A multicast mechanism to allow a local end system to send frames to more than one remote end system A mechanism to allow an end system to check the status of a switch (if switch is congested)

Congestion Control and Quality of Services are also provided by frame relay Computer Networking / Module II / AKN / 149

ATM Networks Is a cell relay protocol designed by ATM forum and adopted by ITU-T A cell is a basic unit of data exchange. It is a small, fixed sized block of information Frames of different sizes and formats reach the cell network, these frames are split into some cells of fixed length Now cells are multiplexed with other cells and routed

frame of line 1 and lne 2 are splited into 3 cells each then interleaved so that none suffers long delay suitable for voice or real-time transmissions Computer Networking / Module II / AKN / 150

ATM Networks Architecture ATM uses asynchronous time division multiplexing

The user access devices, called the end points are connected to the switches through a user-to-network Interface(UNI) Switches are connected with each other through Network to Network Interface (NNI) Computer Networking / Module II / AKN / 151

ATM Architecture, Virtual Connection Connection between two end points are accomplished through transmission paths (TPs). i.e. TPs are physical connection between endpoints via a set of switches and links A TP is divided into several Virtual Paths (VPs). A VP provides a connection or set of connections between two switches All VP contains more than one Virtual circuits (VCs)

Computer Networking / Module II / AKN / 152

Virtual Connection A virtual connections are identified by a pair of parameters called The Virtual path identifier (VPI) and virtual circuit identifier (VCI) VPI defines the VP and VCI defines a particular VC inside VP

In a UNI, the VPI is represented using 8bits and in NNI it represented using 12 bits. VCI is represented using 16 bits in Computer Networking / Module II / AKN / 153 both cases

Miscellaneous Cell structure A cell is of 53 bytes with 5 byte header and 48 byte payload

Switching Uses both PVC and SVC A switch routes the cell using both VPIs and VCIs

Computer Networking / Module II / AKN / 154

ATM Layers Physical layer Original design was based on SONET as the physical layer carrier But it also can use other carriers

ATM Layer Provides routing, traffic management, switching, and multiplexing services It accepts 48 byte segments from AAL and adds 5byte header to form a cell of 53 bytes Computer Networking / Module II / AKN / 155

ATM Layer It uses two different header formats for UNI and NNI

GFC: 4bit field provides flow control at UNI level VPI: virtual path identifier (8bit for UNI, 12 bit for NNI VCI: 16 bit for both UNI and NNI PT: 3 bit field defines user data or management info CLP: 1 bit field for congestion control HEC: 8 bit CRC for header part only Computer Networking / Module II / AKN / 156

Application Adaptation Layer It is designed to accept any type of payload like internet data or multimedia load AAL defines a sub-layer called Segementation and reassembly sub-layer to segment incoming data in to 48byte segments and at the destination these segments are reassembled The converge sub-layer is defined to provide integrity of data ATM defines 4 versions of AAL: AAL1, AAL2, AAL3/4, AAL5 AAL1 is used for streaming audio and video communication and AAL5 for data communication Computer Networking / Module II / AKN / 157

AAL1 Supports applications that transfer information at constant bit rates like video or voice CS sub-layer divides bit stream into 47 byte segments and passes them to SAR sub-layer SAR adds 1 byte header to each segment. The header contains Sequence number(SN): out of 4 bits, 3bits are used to define sequence no to order the bits Sequence number protection(SNP): second 4 bit protects the first field. First 3 bit protects sequence # and last bit is for parity for all 7 bits

Computer Networking / Module II / AKN / 158

AAL5 It assumes that all cells belonging to a message travel sequentially CS sub-layer adds a trailer with following fields User-to-user(UU): used by end users Common part identifier (CPI): defines how the the subsequent fields are to be interpreted Length(L): 2-byte L field indicates the length of original data CRC: The last 4 bytes is for error control in the entire data unit Computer Networking / Module II / AKN / 159

END of Module II

Computer Networking / Module II / AKN / 160