Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    reliable data transfer

    Uploaded by

    salpurenk5064

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    reliable data transfer

    Uploaded by

    salpurenk5064
    3 views8 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    3 views8 pages

    reliable data transfer

    Uploaded by

    salpurenk5064

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 8

    Reliable Transmission

    ! The packet-based version of the same problem


    u How do we reliably send a message when packets (not just
    bits) can be lost/corrupted in the network?

    ! Two options
    u Detect a loss/corruption and retransmit

    u Send data redundantly to tolerate loss/corruption

    CSE 123 – Lecture 5: Reliable Transmission 4


    Simple Idea: ARQ
    Sender Receiver
    Sender Receiver
    Data
    Data

    Timeout
    Timeout
    Time

    AC K

    Data

    Timeout
    AC K

    ! Receiver sends acknowledgments (ACKs)


    ! Sender assumes transmission didn’t make when
    doesn’t receive an ACK after some time (timeout)
    ! Basic approach is generically referred to as Automatic
    Repeat Request (ARQ)
    CSE 123 – Lecture 5: Reliable Transmission 5
    Not So Fast…
    Sender Receiver Sender Receiver

    Data Data

    Timeout
    Timeout

    AC K AC K
    Data

    Timeout
    Data
    Timeout

    Duplicate!
    AC K
    AC K

    ! Loss can occur on ACK channel as well


    u Sender cannot distinguish data loss from ACK loss
    u Sender will retransmit the data frame
    ! ACK loss—or early timeout—results in duplication
    u The receiver thinks the retransmission is new data

    CSE 123 – Lecture 5: Reliable Transmission 6


    Sequence Numbers
    Sender Receiver Sender Receiver

    Data Data
    0
    Timeout
    0

    Timeout
    0
    AC K AC K
    0

    Data
    Data 0

    Timeout
    1 Data
    Timeout

    1
    0 Ignored!
    CK 1 AC K
    A 1
    AC K

    ! Sequence numbers solve this problem


    u Receiver can simply ignore duplicate data
    u But must still send an ACK! (Why?)
    ! Simplest ARQ also solves this problem: Stop-and-wait
    u Only one outstanding frame at a time

    CSE 123 – Lecture 5: Reliable Transmission 7


    Stop-and-Wait Performance

    ! Lousy performance if time to xmit 1 pkt << prop. delay


    u How bad?

    ! Want to utilize all available bandwidth


    u Need to keep more data “in flight”
    u How much? Called the bandwidth-delay product

    ! Also limited by accuracy of timeout:


    period of time when sender is confident it is lost.
    u More on picking timeouts at the end of the lecture
    CSE 123 – Lecture 5: Reliable Transmission 8
    Pipelined Transmission
    Sender Receiver Sender Receiver
    Data Data
    0 0
    Data Data
    1 1
    Data 0 Data 0
    2 AC K 2 AC K
    Data 1 Data 1
    3 AC K 3 AC K
    2
    AC K
    AC K
    3
    AC K
    1 Ignored!

    ! Keep multiple packets “in flight”


    u Allows sender to make efficient use of the link
    u Sequence numbers ensure receiver can distinguish frames
    ! Sender buffers outstanding un-acked packets
    u Receiver ACKs the highest consecutive frame received
    » ACKs are cumulative (covers current frame and all previous)

    CSE 123 – Lecture 5: Reliable Transmission 9


    Go-Back-N
    Sender Receiver Sender Receiver
    Data Data
    0 0
    Data Data
    1 1
    Data 0 Data 0
    2 AC K 2 AC K
    Data 1 Data 1
    3 AC K 3 AC K
    2
    AC K
    timeout

    1 3
    AC K AC K

    Data Data
    2 4

    ! Retransmit all packets from point of loss


    u Packets sent after lost packet (or ACK) are ignored
    (i.e., sent again)
    ! Simple to implement
    (receiver only has to track one packet at a time)
    ! Sender controls how much data is “in flight”
    CSE 123 – Lecture 5: Flow Control 10
    Send Window (sender buffer)
    Sender Receiver
    Data
    0
    ! Bound on number of
    Data
    Data
    1
    0
    outstanding packets
    2 AC K
    AC K
    1 u Window “opens” upon
    Data
    Data
    3 receipt of new ACK
    4
    Timeout

    AC K
    1 u Window resets entirely
    AC K
    1
    upon a timeout
    ! Limits amount of waste
    Data
    2
    Data
    3
    u Don’t need to remember all
    Data
    4 packets ever sent
    u Go-Back-N might still lead
    to sending lots of duplicates
    Go-Back-N Example
    » We can do better with
    with window size 3
    selective retransmission:
    only retransmit missed
    CSE 123 – Lecture 5: Flow Control packets 11

    You might also like