Networking►Stanford CS144

TransportLayer

TCP & UDP

TCP(Transmission Control Protocol)

TCP connection is bidirection, that is to say (A —> B && B —> A == A <—> )B

handshake

1
2
3
A------------Synchronize(A want to connect B)------------->B
A<--Syn(B want to connect A),Ack(B accept A's connection)--B
A------------Acknowledgement(A accept B's connection)----->B

tcp segment

  • TCP provide Application layer a *reliable bidirection byte stream abstraction*
  • TCP use IP to send/recevie segments underlying.

tcp teardown connection

1
2
3
4
5
6
7
8
A------------Finish(A has no more data to send to B)------>B
A<---Ack(B know A and close the connection A2B)+Data-------B
A<-------Data(If B still have data to send)----------------B
A<-------Data(B can keep sending data to A)----------------B
A<-------Data(Since connection B2A is still alive)---------B
....
A<----------Finish(B has no more data to send to A)--------B
A---Ack(A know B has no more data, close Connection B2A)-->B

Both side can do clean up job like release the State Machine

TCP Service Model

How can TCP guarantee the correctness ?

  • Each package will has a confirm package to indicate its successful arrival
  • Checksum detect corrupted data
  • Sequence number detect missing data
  • Flow-control prevents overrunning receiver by telling the sender how much available space left.

TCP header

TCP header

  • Source port indicate which port the package is sent from, the receiver need to use this as destination port in response package.

    Each time a new connection is to be established, the OS will asign a unqiue port number to for it.

1
2
3
4
5
6
7
8
9
# Machine B
$ nc -vl 8899
Listening on [0.0.0.0] (family 0, port 8899)
Connection from localhost 50272 received!
# Here 50272 is the source port

# Machine A
$ nc -v localhost 8899
Connection to localhost 8899 port [tcp/*] succeeded!

  • Sequence indicate the position of this package in the byte sequence

    For example

    1
    2
    3
    4
    5
    6
    7
    8
    Byte array [1000];
    Socket.send(array);
    |||
    |||
    Package(seq_num = 0 , dataptr=array , len = 50);
    Package(seq_num = 50 , dataptr = array + 50 , len = 50);
    Package(seq_num = 100 , dataptr = array + 100 , len =400);
    ....

    In fact, in order to reduce the collision possibility of each connection, the initial sequence number is a random number

    1
    2
    3
    4
    5
    init = rand();
    Package(seq_num = init , ptr=array , len = 50);
    Package(seq_num = init+50 , ptr = array + 50 , len = 50);
    Package(seq_num = init+100,ptr = array + 100 , len =400);
    ....

  • Acknowledgment Sequence indicate the next desired sequence number, that is to say, all data before this number is successfully received.

UDP(User Datagram Protocol)

UPD is much much simpler than TCP

udp header

  • The only valuable information is port number(So it is also called “User Demulitplexing Protocol”)
  • Checksum is optional
  • No connection is established

Applicaiton of UDP

  • let people build their own protocol at application layer
  • For the purpose of “Request-Answer” service, for example DNS

Transport layer protocol in network gaming

Depends on if you’re talking about peer-to-peer, client/server with the users running the server, or client/server with a data center running the server. Only in the latter-most case is the internet really fast and reliable. Your users’ computers are not guaranteed to be fast, and certainly won’t be reliable.

UDP allows you greater control over the sort of TCP-like implementation you’re making. It gives you greater flexibility to execute packets out of order, discard packets that you consider unnecessary while retrying packets you consider important, that sort of thing. But this should only be done if needed and if you have the necessary expertise.

If you can do without that flexibility, TCP works well enough and saves you a whole lot of time. Even professional studios (like one I worked at) use TCP if they don’t absolutely need UDP, and they have people dedicated to network programming.

ICMP(Internet Control Message Protocol)

providing error message or diagnose message of Network layer

ICMP above network layer

Destination Unreachable

(If the router does not know how to forward the package)

  • Used by tools like ping, traceroute,…
  • ICMP package is usually generated by routers
  • The IP header of the original package which leads to the error will be included in the ICMP body.

End-to-end Principle

Network can do more jobs to help, but it can only help, not ensure. The responsibility lies on endpoints since only the endpoints have enough information to ensure the job.

Always remember that the network is unreliable !!! It might be correct, might !

Strong End-to-end Principle

The network’s job is to transmit datagrams as efficiently and flexibly as possible. Everything else should be done at the fringes

  • Don’t make any assumption
  • Lots of people do not follow the principle when they are designing networks, so it might has good performance, but hard to change.

Error Detection

error detection

Some of the scheme only append the value after data

1
2
ED = f(data)
send(ED + data)

Checksum

  • Fast, cheap to implement
  • Weak guarantee, if 2 bits error at the same time, the error will be canceled
  • Used by IP , TCP

CRC(Cyclic Redundancy Code)

  • Compute the reminder of a polynomial
  • Easy to implement in hardware
  • strong guarantee, detect lots of errors
  • Used by ethernet and link layer
1
2
3
4
5
6
def polynomial_mod(a,b):
    pass
Generator = 0b1011 # given by the algorithm
Data = message + polynomial_mod(message , Generator)
def validate(Data, Generator):
    return polynomial_mod(Data, Generator) == 0

MAC(Message Authenticate Code)

  • For cryptographical purpose
  • More security then error detection
  • Used by TLS

Finite State Machines

  • Composed by a finite set of state
  • Each state is a configuration of the system
  • A event can cause the system to transform from one state into another and the system will perform the action at the same time

finite state machine

HTTP example

Each rectangle is a state, The graph describe almost all possible situation

Flow Control

The sender can send faster then the receiver can receive

  • Don’t send more package then the receiver can process
  • Receiver gives sender feed back
  • Two basic approaches
    • Stop and Wait
    • Sliding window

Stop and Wait

  • At any moment, there will be only one package in the network
  • After sending the package the sender will start waiting
  • If the receiver doesn’t response with an acknowledgment in timeout limit, the sender will assume the the package is lost and resend it.

FSM of SW

  • Since there will always one package in the flight, the algorithm is inefficient, the pipe is heavily wasted

Sliding Window

  • Allow N packages in the network at the same time, when N=1, it is stop and wait.
  • Can keep the pipe full
  • sender and receiver can have different window size

Sender

  • Every package has a sequence number
  • The sender maintain the latest acknowledgment seq number
  • The sender is not allow to send package with seq number >= latest ack + window size
  • This will causing a “sliding window” as the acknowledgment seq number increase

Receiver

1
2
3
4
5
LastReceived : the number of the latest arrived package
accepted : the number of the latest processed package
windowsize : reciever window size

LastReceived - accepted <= windowsize

Accumulative acknowledgement: if some package missing, don’t advance

1
2
recieved : 1, 2 , 3, (4 missing) 5 , 6, 7
ack :    1 , 2 , 3, 3, 3, 3,

Retransmission Strategy

Go back N

Assume the whole window is lost and retransmit the whole window

Selective Repeat

Assume the unacknowledged package is lost and only retransmit only that one package