UNIT-II
Peer-to-Peer Protocols
Peer-to-Peer Protocols and Service Models Flow Control ARQ Protocols Data Link Control
Peer-to-Peer protocols: many protocols involve the interaction between two peers
Service Models Detailed discussion of ARQ provides example of development of peer-to-peer protocols Data Link Control Framing PPP HDLC
Peer-to-Peer Protocols
n + 1 peer process
n + 1 peer process
SDU
n peer process
SDU PDU
n peer process
Peer-to-Peer processes execute layer-n protocol to provide service to layer-(n+1) Layer-(n+1) peer calls layer-n and passes Service Data Units (SDUs) for transfer Layer-n peers exchange Protocol Data Units (PDUs) to effect transfer Layer-n delivers SDUs to destination layer-(n+1) peer
n 1 peer process
n 1 peer process
Service Models
The service model specifies the information transfer service layer-n provides to layer-(n+1) The most important distinction is whether the service is:
Connection-oriented Connectionless
Service model possible features:
Arbitrary message size or structure Sequencing and Reliability Timing and Flow control Multiplexing Privacy, integrity, and authentication
Message Size and Structure What message size and structure will a service model accept?
Different services impose restrictions on size & structure of data it will transfer Single bit? Block of bytes? Byte stream? Ex: Transfer of voice mail = 1 long message Ex: Transfer of voice call = byte stream
1 voice mail= 1 message = entire sequence of speech samples (a) 1 call = sequence of 1-byte messages (b)
Segmentation & Blocking
To accommodate arbitrary message size, a layer may have to deal with messages that are too long or too short for its protocol Segmentation & Reassembly: a layer breaks long messages into smaller blocks and reassembles these at the destination Blocking & Unblocking: a layer combines small messages into bigger blocks prior to transfer
1 long message 2 or more short messages
2 or more blocks
1 block
Reliability & Sequencing
Reliability: Are messages or information stream delivered error-free and without loss or duplication? Sequencing: Are messages or information stream delivered in order? ARQ protocols combine error detection, retransmission, and sequence numbering to provide reliability & sequencing Examples: TCP and HDLC
Flow Control
Messages can be lost if receiving system does not have sufficient buffering to store arriving messages If destination layer-(n+1) does not retrieve its information fast enough, destination layer-n buffers may overflow Flow Control provide backpressure mechanisms that control transfer according to availability of buffers at the destination Examples: TCP and HDLC
Timing
Applications involving voice and video generate units of information that are related temporally Destination application must reconstruct temporal relation in voice/video units Network transfer introduces delay & jitter Timing Recovery protocols use timestamps & sequence numbering to control the delay & jitter in delivered information Examples: RTP & associated protocols in Voice over IP
Multiplexing Multiplexing enables multiple layer-(n+1) users to share a layer-n service A multiplexing tag is required to identify specific users at the destination Examples: UDP, IP
Privacy, Integrity & Authentication
Privacy: ensuring that information transferred cannot be read by others Integrity: ensuring that information is not altered during transfer Authentication: verifying that sender and/or receiver are who they claim to be Security protocols provide these services Examples: IPSec, SSL
End-to-End vs. Hop-by-Hop
A service feature can be provided by implementing a protocol end-to-end across the network across every hop in the network Example: Perform error control at every hop in the network or only between the source and destination? Perform flow control between every hop in the network or only between source & destination?
We next consider the tradeoffs between the two approaches
End-to-End Approach Preferred
Hop-by-hop
Hop-by-hop cannot ensure E2E correctness
Data 1 ACK/ NAK 2 ACK/ NAK Data 3 ACK/ NAK Data 4 ACK/ NAK Data 5
Faster recovery Simple inside the network More scalable if complexity at the edge
End-to-end
ACK/NAK
1 Data
2 Data
3 Data
4 Data
Flow Control: Initial Assumptions
Simplex Channel Infinite buffer capacity with the receiver Error free transmission Network layer at the senders end is always ready with data
10/06/11
Computer Networks and Protocols
14
10/06/11
Computer Networks and Protocols
15
Stop and Wait
10/06/11
Computer Networks and Protocols
16
Sliding Window
Sliding Window Protocols are a feature of packet-based data transmission protocols. They are used where reliable in-order delivery of packets is required, such as in the data link layer (OSI model) as well as in TCP (transport layer of the OSI model). Conceptually, each portion of the transmission (packets in most data link layers, but bytes in TCP) is assigned a unique consecutive sequence number, and the receiver uses the numbers to place received packets in the correct order, discarding duplicate packets and identifying missing ones. The problem with this is that there is no limit of the size of the sequence numbers that can be required.
10/06/11
Computer Networks and Protocols
17
Sender Sliding Window
10/06/11
Computer Networks and Protocols
18
Receiver Sliding Window
10/06/11
Computer Networks and Protocols
19
Sliding Window Example
10/06/11
Computer Networks and Protocols
20
Sender
Receiver
10/06/11
Computer Networks and Protocols
22
Automatic Repeat Request (ARQ)
Purpose: to ensure a sequence of information packets is delivered in order and without errors or duplications despite transmission errors & losses We will look at:
Stop-and-Wait ARQ Go-Back N ARQ Selective Repeat ARQ
Basic elements of ARQ:
10/06/11
Error-detecting code with high error coverage ACKs (positive acknowledgments) NAKs (negative acknowlegments) Timeout mechanism
Computer Networks and Protocols 23
ERROR CONTROL
10/06/11
Computer Networks and Protocols
24
Stop-and-Wait ARQ
Transmitter Ready state
Await request from higher layer for packet transfer When request arrives, transmit frame with updated S and CRC Go to Wait State Wait for ACK or timer to expire; block requests from higher layer If timeout expires
retransmit frame and reset timer
Receiver Always in Ready State
Wait for arrival of new frame When frame arrives, check for errors If no errors detected and sequence number is correct (S=R), then
accept frame, update Rnext, send ACK frame with Rnext, deliver packet to higher layer
Wait state
If no errors detected and wrong sequence number
discard frame send ACK frame with Rnext
If ACK received:
If sequence number is incorrect or if errors detected: ignore ACK If sequence number is EQUAL accept frame, go to Ready state
If errors detected
discard frame
10/06/11
Computer Networks and Protocols
25
Applications of Stop-and-Wait ARQ
IBM Binary Synchronous Communications protocol (Bisync): character-oriented data link control Xmodem: modem file transfer protocol Trivial File Transfer Protocol (RFC 1350): simple protocol for file transfer over UDP
10/06/11
Computer Networks and Protocols
26
Stop-and-Wait ARQ
Transmit a frame, wait for ACK
Packet
Information frame
Error-free packet Transmitter (Process A) Receiver (Process B)
Control frame
Timer set after each frame transmission
Header Information packet
10/06/11
CRC Header
Computer Networks and Protocols
CRC
27
Information frame
Control frame: ACKs
Damaged Frame
10/06/11
Computer Networks and Protocols
28
Stop-and-Wait ARQ, lost frame
10/06/11
Computer Networks and Protocols
29
Stop-and-Wait ARQ, lost ACK frame
10/06/11
Computer Networks and Protocols
30
Go-Back-N
Improve Stop-and-Wait by not waiting! Keep channel busy by continuing to send frames Allow a window of up to Ws outstanding frames Use m-bit sequence numbering If ACK for oldest frame arrives before window is exhausted, we can continue transmitting If window is exhausted, pull back and retransmit all outstanding frames Alternative: Use timeout
10/06/11 Computer Networks and Protocols 31
Go-Back-N ARQ
Go-Back-4: A
fr 0 fr 1 fr 2 fr 3 fr 4 fr 5
4 frames are outstanding; so go back 4
fr 6 fr 3 fr 4 fr 5 fr 6 fr 7 fr 8 fr 9
Time
B
A C K 1 A C K 2 A C K 3 out of sequence frames A C K 4 A C K 5 A C K 6 A C K 7 A C K 8 A C K 9
Rnext 0
Frame transmission are pipelined to keep the channel busy Frame with errors and subsequent out-of-sequence frames are ignored Transmitter is forced to go back when window of 4 is exhausted
Computer Networks and Protocols 32
10/06/11
Damaged Frame
10/06/11
Computer Networks and Protocols
33
Lost Frame
10/06/11
Computer Networks and Protocols
34
Lost ACK
10/06/11
Computer Networks and Protocols
35
Applications of Go-Back-N ARQ
HDLC (High-Level Data Link Control): bitoriented data link control V.42 modem: error control over telephone modem links
10/06/11
Computer Networks and Protocols
36
Selective Repeat ARQ
Go-Back-N ARQ inefficient because multiple frames are resent when errors or losses occur Selective Repeat retransmits only an individual frame
Timeout causes individual corresponding frame to be resent NAK causes retransmission of oldest un-acked frame
Receiver maintains a receive window of sequence numbers that can be accepted
Error-free, but out-of-sequence frames with sequence numbers within the receive window are buffered Arrival of frame with R causes window to slide forward by 1 or more
10/06/11 Computer Networks and Protocols 37
Selective Reject
10/06/11
Computer Networks and Protocols
38
Applications of Selective Repeat ARQ
TCP (Transmission Control Protocol): transport layer protocol uses variation of selective repeat to provide reliable stream service Service Specific Connection Oriented Protocol: error control for signaling messages in ATM networks
10/06/11
Computer Networks and Protocols
39
Data Link Control
10/06/11
Computer Networks and Protocols
40
Point-to-Point Protocol PPP
10/06/11
Computer Networks and Protocols
41
PPP provides router-to-router and host-tonetwork connections over synchronous and asynchronous circuits, which can be either dialup or leased lines. PPP is the protocol of choice when configuring serial links in a multivendor environment.
10/06/11
Computer Networks and Protocols
42
PPP actually uses HDLC as a basis for encapsulating datagrams. PPP's frame format is based on the HDLC frame format. PPP defines the Link Control Protocol (LCP). The job of LCP is to establish, configure, and test the data-link connection.
10/06/11
Computer Networks and Protocols
43
Point-to-Point Link
10/06/11
Computer Networks and Protocols
44
Transition States
10/06/11
Computer Networks and Protocols
45
PPP Layers
10/06/11
Computer Networks and Protocols
46
PPP Frames
10/06/11
Computer Networks and Protocols
47
LCP Packet Encapsulated in a Frame
10/06/11
Computer Networks and Protocols
48
PAP
Password Authentication Protocolprovides a simple method for the peer to establish its identity using a 2-way handshake. This is done only upon initial link establishment. After the Link Establishment phase is complete, an Id/Password pair is repeatedly sent by the peer to the authenticator until authentication is acknowledged or the connection is terminated
10/06/11 Computer Networks and Protocols 49
PAP Packets
10/06/11
Computer Networks and Protocols
50
IPCP Packet Encapsulated in PPP Frame
Internet Protocol Control Protocol
- Is responsible for configuring, enabling, and disabling the IP protocol modules on both ends of the point-to-point link.
10/06/11 Computer Networks and Protocols 51
HDLC High Level Data Link Control
Early Link Layer Protocol. Used in many LAN and WAN Protocols. Support Broad range of Application.
10/06/11
Computer Networks and Protocols
52
HDLC Basis
Why do we use it ?
Framing Frame Protection Error Recovery
Three types of Stations
Primary Station. Secondary Station. Combined Station.
Three Modes
Normal Response Mode[NRM] Asynchronous Response Mode[ARM] Asynchronous Balance Mode[ABM]
10/06/11 Computer Networks and Protocols 53
HDLC Configuration
10/06/11
Computer Networks and Protocols
54
HDLC Configuration
10/06/11
Computer Networks and Protocols
55
HDLC Configuration
10/06/11
Computer Networks and Protocols
56
HDLC Modes
10/06/11
Computer Networks and Protocols
57
HDLC Frame Types
10/06/11
Computer Networks and Protocols
58
HDLC Frame Types
10/06/11
Computer Networks and Protocols
59
HDLC Frame Types
10/06/11
Computer Networks and Protocols
60
HDLC Flag Field
10/06/11
Computer Networks and Protocols
61
Bit Stuffing
10/06/11
Computer Networks and Protocols
62
HDLC Address Field
10/06/11
Computer Networks and Protocols
63
HDLC Control Field
10/06/11
Computer Networks and Protocols
64
Poll/Final
10/06/11
Computer Networks and Protocols
65
HDLC Information Field
10/06/11
Computer Networks and Protocols
66
HDLC FCS Field
10/06/11
Computer Networks and Protocols
67
Peer-to-Peer Example
10/06/11
Computer Networks and Protocols
68
Peer-to-Peer Example
10/06/11
Computer Networks and Protocols
69
