Telecommunication Protocols Laboratory Course
Lecture 5
Last time
• We studied the network layer
o Routing algorithms
o Network layer protocols
• Main problem: how to get through the network, from source to destination
Today
• One layer up we concentrate on end-to-end pairs and how to get reliably from source to destination, independently of the underlying network
• More precisely: TRANSPORT LAYER
• Not just another layer
• The heart of the whole protocol hierarchy
• Task Æ
to provide reliable, cost-effective data transport from source machine to destination machine, independently of the physical network(s) currently in use
Services Provided to the Upper
Layers
Transport service
• Uses NL services
• Transport entity (TE)
o Hardware/software within TL that does the work
o Can be located in – OS kernel
– Separate user process
– Library package bound into network applications – Network interface card
• NL and TL
o Both have connection-oriented and connectionless services
o Connections have 3 phases in either layer
o Addressing and flow control are similar
NL vs TL
• Difference:
o TL code runs entirely on the users machines
o NL code is usually on the routers, operated by the carrier
• Importance
o Users have no real control over network
o TL is on the top of NL and improves quality of service
• Examples
o Connections
o Lost packets, mangled data
o TL service primitives Æ calls to library procedures
o Application programmers can code based on a standard set of
primitives and have programs running in a wide variety of networks
Network overview
• Transport service provider Æ bottom 4 layers
• Transport service user Æ layers above layer 4
=> TL in a key position, as major boundary between user and provider of the reliable data transmission service
Transport service primitives
• Transport service (TS) interface Æ operations provided to application programs by TL
• Each TS Æ its own interface
• Reaquirements Æ convenient and easy-to-use
• TS similar to NS
o Connection-oriented and connectionless services
• TS different from NS
o NS models the service offered by real networks
o TS intended to provide reliable service over an unreliable network
The nesting of TPDUs, packets, and frames
TPDU (transport protocol data unit) Æ messages sent between TEs
Transport service primitives 2
The primitives for a simple transport service.
Example
Æ Server and some remote clients
1. Server executes LISTEN (e.g. by calling a library procedure, that makes a system call to block server until a client turns up)
2. Client wants to talk to server: it then executes CONNECT (blocks the client and sends TPDU - with CONN_REQ - to server)
3. When TPDU arrives to server, TE checks if it is blocked on a
LISTEN => interested in handling requests; if so it unblocks it and sends TPDU - with CONN_ACC – back to client
4. When this TPDU arrives at client, it is unblocked and connection established
5. Client and server now exchange data using SEND and RECEIVE 6. When connection no longer needed, it must be released by freeing
up table space within the TEs, with DISCONNECT
Connection states
A state diagram for a simple connection management scheme. Packet arrivals.
Berkeley sockets
• Socket primitives used in Berkeley UNIX for TCP and widely for Internet programming
• TPDUs not discussed now
Berkeley Sockets
The socket primitives for TCP.
Server side
• First four executed in order
• SOCKET
o Creates a new endpoint, allocates table space in TE
o Parameters specify addressing format, type of service, protocol
o When successful, returns an ordinary file descriptor
o No network address specified
• BIND Æ assigns addresses
• LISTEN Æ allocates queue space; not blocking
• ACCEPT
o Blocks server, to wait for incoming connection
o When TPDU asking for connection comes:
– TE creates new socket with same properties as original one, returns file descriptor for it
– Server forks off a process/thread to handle connection on new socket AND go back
Client side
• Socket created with SOCKET, BIND not needed
• CONNECT blocks caller, actively starts connection process
• When connection process completed (appropriate TPDU comes from server): client unblocked, connection established
• Both sides can now use SEND/RECEIVE over the full duplex connection
• CLOSE Æ symmetric release of the connection with sockets
Elements of Transport Protocols
• Transport service (TS) is implemented by a transport protocol (TP) used between two TEs
• TL protocols resemble DLL protocols
o Error control
o Sequencing
o Flow control
• Differences
o Due to major environment dissimilarities in which the two operate
Transport Protocol
(a) Environment of the data link layer.
(b) Environment of the transport layer.
Differences between TL and DLL
• Explicit addressing needed in TL
o In DLL each outgoing line uniquely specifies a particular router
• Establishing connections
o In DLL, over wire => simple
• Potential existence of storage capacity in subnet
• Amount-related difference
Elements of Transport Protocols
• Addressing
• Connection Establishment
• Connection Release
• Flow Control and Buffering
• Multiplexing
• Crash Recovery
Addressing
• Needed both for connection-oriented and for connectionless services
• Method Æ define transport addresses to which processes can listen for connection requests
• Transport addresses
o In Internet: ports
o In ATM networks: AAL-SAPs
o Generically: TSAP (TS access point)
• Network addresses: NSAP
o IP is an example of NSAP
• An application process (client or server) attaches to a TSAP to establish connection to a remote TSAP
Addressing 2
TSAPs, NSAPs and transport connections.
Why not only NSAPs?
• A connection goes through NSAPs on each host
• Some hosts have only one NSAP
⇒We need to distinguish between connections
⇒We need to distinguish between multiple endpoints sharing the same NSAP
⇒We need TSAPs
Addressing problem
• How do user processes know that some needed server (services) is (are) attached to TSAP x ?
1. Stable TSAP addresses, listed in well-known places 2. Initial connection protocol
o Special process server (PS), acting as a proxy for less heavily used servers
o It listens to a set of TSAPs at the same time, waits for connection requests
o Users begin with CONNECT request, for a TSAP x; if no server waiting, they get a connection to PS
o PS searches for x and lets it inherit its existing connection with user
o New server does the work, PS goes back to listening for new requests
3. Name server Æ like a phone book
o Listens to a well-known TSAP
o Every server registers with the name server
Time-of-day server
How a user process in host 1 establishes a connection with a time-
Connection Establishment
• Tricky, as network can lose/store/duplicate packets
• How to attack duplicate packets
o Use throw-away TSAPs
o Connection IDs: sequential nr, incremented for each established connection; chosen by initiating party, put in every TPDU
– When connection released: each TE updates table with obsolete connections (peer-TE, connection ID)
– When connection request arrives, checked against table
– FLAW: each TE maintains certain amount of information indefinitely – FLAW: when a crash occurs, machine loses memory, table lost
New target
• Kill off aged packest (instead of letting packets living forever in network)
• Method: restricted packet lifetime, by:
o Restricted subnet design
o Hop counter in each packet
o Time-stamping packets (requires routers clocks synchronized)
• We need to ensure
o A packet is dead
o All acknowledgements about it are also dead
• T Æ period needed for a packet to disappear from network
Tomlinson method
• Hosts equiped with time-of-day clock, need not synchronization
• Clock Æ binary counter incrementing itself at uniform intervals
• Nr bits counter ≥ nr bits seq nr
• Clock assumed to continue working even if host crashes
• Goal: ensure 2 identically numbered TPDUs are never outstanding at the same time
• Connection establishment: low-order k bits of counter used as seq nr (also k bits)
• Sequence space should be large
• When both TEs agree on initial seq nr, any sliding window protocol can be used for flow control
Tomlinson method Æ host crashes
• Solution 1
o TEs idle for period T after recovery, to let all old TPDUs die off
o In large networks, we have large T => not good
• Solution 2
o Prevent seq nr from being used (assigned to new TPDUs) for period T
o Forbidden region (FR) Æ illegal combinations of time and seq nr
o Before sending any TPDUs TE must read clock and check it’s not in FR
o Protocol can get into trouble in 2 ways – It sends too much data, too fast
– It sends too slowly
Connection Establishment 2
(a) Too many TPDUs.
Connection establishment 3
• 3-way handshake (Tomlinson)
o Connection Request (seq=x): A Æ B
o Acknowledgement (seq=y, ack=x): B Æ A
o Data (seq=x, ack=y): A Æ B
• Solves the problem of getting sides to agree on initial seq nr
• Does not require sides to begin sending with same seq nr
• Delayed CR duplicate does no damage
• Delayed CR duplicate and delayed ack still cause no damage
Connection Establishment 4
Three protocol scenarios for establishing a connection using a three-way handshake. CR denotes
CONNECTION REQUEST.
(a) Normal operation,
(b) Old CR appearing out of nowhere.
Asymmetric Connection Release
Symmetric conection release
• Treats connection as two separate unidirectional connections, each has to be released separately
• A host can continue to receive data even after it has sent a disconnect-TPDU
• Works well when processes have fixed amount of data to send and know clearly when they sent it
• There are situations when determining that all work is done and connection should close is not obvious
The two-army problem
Connection Release with timers
6-14, a, b
Protocol scenarios for releasing a connection. (a) Normal case of a
Connection Release with timers 2
6-14, c,d
Connection release with timers 3
• Another situation
o All N retransmissions of A are lost
o A times out and releases connection (for A, situation identical to d) on previous page)
o B fully active, having no idea something happened
• Yet another situation (to avoid the above)
o A not allowed to give up after N retries: A goes on forever until a response comes
o Now, if AÆB (DR) OK, but BÆA (DR) lost - situation d) on
previous page- then B times out and disconnects while A runs forever
• The last situation (to avoid the above)
o B not allowed to time out
d) situation on previous page: B hangs on forever
Connection release with more timers
• Intended to kill half-opened connections
• Rule: if no TPDUs received for a period P, then connection automatically disconnected
⇒ If one side disconnects, the other will eventually too
• Timer needed by every TE:
o stopped when TPDU sent, then restarted
o If timer expires, dummy TPDU sent, to keep other side from disconnecting
o If too many dummy TPDUs are lost on an otherwise idle connection => hosts will eventually disconnect
• Conclusion Æ there is no perfect solution
Flow control and buffering
• Sliding window or other schemes needed for flow control
• Impractical to adopt the DLL buffering schemes
o In DLL a router has a few out-lines
o In TL a host may have numerous connections
• Optimal trade-off between source buffering vs destination buffering
o Low-bandwidth bursty traffic (interactive terminal): buffer at sender
o High-bandwidth traffic (file transfer): buffer at receiver, to ensure max data flow
Buffer sizes
(a) Chained fixed-size buffers. (b) Chained variable-sized buffers.
(c) One large circular buffer per connection.
Dynamic buffering
• Connections open and close, traffic patterns change =>
sender and receiver need to dynamically adjust their buffer allocation
• TP should allow a sending host to request buffer space at the other end
• Receiver knowing its current status may reply with as many buffers it can
• Buffers can be allocated per connection or colectively for all connections between 2 hosts
Dynamic buffering 2
• A reasonable general way to manage dynamic buffer allocation: decouple buffering from acknowledgements
• Dynamic buffer management = variable-sized window
• To avoid deadlocks Æ each host should periodically send control TPDUs giving ACKs and buffer status on each connection
• When memory is plentiful: worry about network capacity
Flow Control and Buffering (2)
Dynamic buffer allocation. The arrows show the direction of
Multiplexing
• Appears at many layers
• In TL:
o When only one network address is available on a host, all transport connections have to use it: when TPDU comes in, some way is needed to tell to which process to give it to: upward multiplexing
o When more bandwidth is needed than NL can provide, opening multiple connections and distributing traffic evenly on them is a solution: downward multiplexing
Multiplexing 2
(a) Upward multiplexing. (b) Downward multiplexing.
Crash recovery
• If TE entirely on hosts, recovery from routers and network crashes is manageable
• Recovery from host crashes
o Requirement: clients able to work when servers crash and then reboot
o Issue 1: sending ACKs and writing data to upper layers cannot be simultaneous events
o Issue 2: at crash time, client may be in state S1 (one TPDU outstanding) or in state S0 (no TPDU outstanding)
o Issue 3: crash can occur before ACK and Write, between ACK and Write, or after ACK and Write
Crash recovery 2
• Sad result:
o No matter if ACK is first or Write is first, no universal solution exist to problem when does the client retransmit?
o I.e.: there are always situations in which the protocol may fail to recover properly
• Making protocol more elaborate does not help
• Hence, recovery from a layer N crash can be resolved only in layer N+1, if layer N+1 retains enough status
information
• True end2end ACK is probably impossible to obtain
Crash Recovery 3
Different combinations of client and server strategy.
UDP
• Connectionless TP in Internet Protocol suite
• With it, applications can send encapsulated IP datagrams, w/o establishing connections
• UDP transmits segments: 8-byte header + payload
• No flow control, no error control, no retransmissions upon receipt of bad frame
• Provides an interface to IP protocol with the added feature of demultiplexing multiple processes using ports
• Useful in client-server (C-S) situations (DNS uses this)
o C sends short request to S, expects short reply back
o If either lost, C times out and retries
The UDP header
• Source port and end port identify the endpoints on the respective machines Æ main value of having UDP over just raw IP
• Length: header + data
• Checksum optional: 00…0 if not computed; a true computed 0 stored as 11…1
Remote procedure call
• Procedures and function calls are ubiquitous
• Sending msg to remote host and getting reply back
o Similar to having procedures
o Parameters sent, result expected
• People tried to arrange request-reply interactions on networks to be cast as procedure calls => applications more easier to program, more familiar
• Birrell and Nelson (‘84): key work in this area Æ RPC
o No msg passing visible to programmer
o Basis of networking applications; conceptual elegance
Remote procedure call 2
Steps in making a remote procedure call. The stubs are
RPC – other issues
• Some problems
o Pointers as parameters
o Weakly typed languages
o Types of parameters not obvious to deduce
o Global variables
• Fits nicely with UDP, can be also used with TCP, especially if
o Parameters/results are too large for a UDP packet
o Operation requested non-idempotent
Real-Time Transport Protocol
• Real-time multimedia applications: Internet radio, Internet telephony, music-on-demand, video-on-demand, video- conferencing
• Basic function: multiplex several real-time data strams onto a single stream of UDP packets
o Sent to a single or to multiple destinations
• No flow control, no error control, no acknowledgements, no retransmission mechanisms
• It has seq nr, for destination to determine if packets are missing; if so, best action is to approximate missing value by interpolation
• Multiple encoding formats of payload allowed
TCP (transmission control protocol)
• For most Internet applications: reliable, sequenced delivery is needed
• Main workhorse in Internet
• TSAP=port; well-known ports have nr < 1024
• Maximum segment size: 64 KB (65536 bits, 8192 bytes)
o Often 1460 bytes to fit Ethernet frame payload when IP and TCP headers are on
• Connections
o Identified by (socket1, socket2)
o Full duplex, point-to-point
o Byte stream
Some assigned ports
Port Protocol Use
21 FTP File transfer
23 Telnet Remote login
25 SMTP E-mail
69 TFTP Trivial File Transfer Protocol 79 Finger Lookup info about a user
80 HTTP World Wide Web
110 POP-3 Remote e-mail access
119 NNTP USENET news
TCP connection is byte stream
(a) Four 512-byte segments sent as separate IP datagrams.
(b) The 2048 bytes of data delivered to the application in a single READ CALL.
The TCP Segment Header
The pseudo-header needed in the
TCP checksum
TCP Connection Establishment
6-31
(a) TCP connection establishment in the normal case.
(b) Call collision.
TCP Congestion Control
(a) A fast network feeding a low capacity receiver.
TCP Congestion Control 2
TCP Timers Management
• Multiple timers are used
o Retransmission timer
o Persistence timer
o Keepalive timer
Wireless TCP
• When a timer goes off, TCP slows down and sends less vigorously
o Reduce network load, i.e., alleviate congestion
o This works fine for wired networks
• In wireless networks
o The sender should try harder when packets are lost in these networks
Transitional TCP
Assignment 4
• Choose a protocol from UDP, RPC, RTP, TCP and simulate it. Emphasize in the simulation
o Addressing scheme
o Connection establishment
o Connection release
o Flow control and buffering
o Multiplexing (if appropriate)
o Crash recovery
Important update
• Number of assignments: from the 5 possible assignments you need to choose only 3 and simulate them by May 6
