Networks,  Random remarks (last update 02SEP2017)

Each level append it's own header. 

"Switch" is link layer device so to understand "message" it should implement Phsical Layer & Link layer.

Problems and solutions with reliable and fast communication

 1. ACK/NACK can be corrupted. Moreover there is no way to check that last message in communication have been delivered properly.

2. It's possible to not use NACK and use sequence number for numerate packets. Moreover sequence number still are needed to make reliable transfering more complicated then naive implementation.

3.   RTT is big (it is very big for very far away end points). 

We can not wait until L/R + RTT, because RTT can be big. 

So we send packets, even we didn't receive ACKs.

The core idea is to transmit several packets on fly for impl. reliable data transfer.

3.1. Go-Back-N (GBN) -- sender send up to N acked packets. Receiver send ACK for the largest received packets. No buffering. Sender has only one timer - it is a timer for the last unACK packet.

3.2. Selective repeat (SP) -- send up to N packets. Received packet which have been received in out-of-order, but within a window, will be buffered. It's more better schema, comparing with GBN, but it also more costly to impl. such logic because e.g. - we need more timers.

In both case there are various problems with sequnce numbers, and it's more better to have big space of sequence numbers.

4. Timeout is need to understand when the packet have been lost. Too long or too short timeout is both bad thing.

UDP

- Possible lost.

- Out of order.

- Conntectionless (RFC 768).

No connection establishment, no connection state,  

small segment header (source port , dst port, length in bytes of segment with header, checksum), no congestion control.

checksum - summation of 16bit integeres with "CF" append to result in each summ, and then also in the end flip bits.

TCP. Key characteristics and details.

0-1023 -- well known ports (RFC 1700)

1024-65535 -- other ports

Full duplex, flow controlled, congestion controlled. 

Sequence number in TCP is not number of packets, but represent number of bytes which have been sent.

In TCP there are two numbers: SEQ and ACK. And they each time swaped during communication.

ACK number say what sender of this packet which contains (SEQ,ACK) wants from receiver in terms of the following number of byte.

TCP use cumulative ACK-knowledgement.

TCPv4: ports is 16bit number, SEQ and ACK number is 32 bits number, receive window 16 bit number measured in bytes,

1. Unicast - one sender, one receiver.

2. Provides reliable in-order byte stream.

3. There is handshake step which setups connection. 3-way handshake: 

    > SYN client to => server

    > SYN+ACK from server to => client

    > ACK client to => server.

Special term to not allocate buffer until last ACK is not received in server side is Syn Cookies.

And then data starts to be transfering. 

To allow not not kill server via SYN's - it is allowable to not allocate real resources until last 3rd ACK.

4. There is 4 steps process to close connection. First thing client and server understand the connection can be closed. 

    > Client send FIN to => server

    > Server receive FIN and respond to with ACK to => client. 

        Start closing connection and send FIN to => client. So server send ACK and FIN packet.

    > When client received ACK then client wait for FIN and then send ACK to server. And start timed wait. 

        After this timeout the connection will be closed.

   > Server received ACK and move connection from closing => to => closed state 

5. Full duplex. Information is sending in both direction.

6. Flow control. Limit sender speed to not overwhelm the receiver. Implemented by evaluated "rcvBuffer - senderInBuffer". We have never sent data more then receiver can receive. Implemented in receive window header field of TCP.

7. Congestion control. Senders can limit sender speed to not overwhelm the whole network. TCP do it from point of view of End systems, but there is exist other protocols e.g. ATM which do it from point of view of the network (i.e. routers manage it).

Limiting send rate is doing via limiting number of UN-ACKED bytes in the pipeline. I.e.

LastByteSent-LastByteAcked <= cwnd (congestion window)

We want make cwnd as big as possible, but not bigger. 

Solution - TCP always increase sending rate lineary until ACK's start to loose. 

Increase exponentially by factor 2 in slowstart(1st phase) and then in congestion avoidance (2nd phase) increase lineary.

When ACKs start to loose we decrease sending rate by two. Two common implementaions with a bit more subtleties:

  -- TCP Reno

  -- TCP Tahoe

8. TCP used sequence number in both in ACK and in sending. Sequence number is number of byte, not number of packet.

9. Sequence number of sender and receiver is swapped during communication.

10. In fact Sequence number - is the number of bytes in the stream, and Ack.number - is the number of the next expected byte.

11. TCP doesn't not specify how receiver handle out-of-order segments. It's up to implementor how to handle it.

12. Timeout selection.  Formulate for estimate RTT is moving avergage model. It eliminates huge spikes during data transfering.

Sample RTT - is a just time for this segment.

Moving average: EstimatedRtt = (1-alpha)*EstimatedRtt + alpha*SampleRtt

                            EstimateDevdRtt = (1-beta)*EstimateDevdRtt + beta*|SampleRtt-EstimatedRtt|

Typically: alpha=0.25, beta=0.25

TimeoutInterval = EstimatedRtt + 4*EstimateDevdRtt.

13. Fast retransmit in TCP - When sender recieve 3 duplicate ACKS the sender immediately assume that the next packet after ACK have been lost. And sender retransmit it, even timeout is not expired.

14. As a part of protocol also receiver set "rwnd" for sender with info how many buffer size it has.

15. TCP also has 

  Congestion control - to rule the situation when a lot of packets in the network. 

  Flow control - save receiver from the fast sender.

In fact in big network each drop which have been made in last stage make the previous attempts of previous routers that have already done their work as a waste of time.

In TCP sender and receiver evaluate lost packets implicitly. ACK not received - maybe it's due to congestion of the network. Limitation of send rate - limit the number of not acknowledged bytes of the sender. (cwnd)

Idea - probing strategy - increase send rate until we start to to loss packets and then decrease send rate.

> Slowstart -- send speed increase exponentially.

> Then we reach "sstresh" cwnd size.

> Increase Lineary by 1*MSS each round

Couple events:

> Timeout for packet -- cut cwnd = 1*MSS (maximum segment size)

> Duplicate ACKS -- cwnd /= 2

IP and network layer. 

IP realy bundle to interface, not to computer/host.

CIDR ip format: a.b.c.d/x -- means x high bits are dedicated for network address and 32-x is for ip address within subnet.

1. Goals of network layer

  a. Forwarding packet from end-to-end

  b. Routing (global forwarding)

2. Connection service between host (end-to-end)

3. IP is connection-less or Datagram protocol. For IP there is no such thing as virtual circuit/reservation of the resources. So in IP really there are no guarantees about delivering.

DHCP is implemented via using UDP. And it provides:

-- automatic way to receive IP address via Discover, Offer, Request, DHCP Ack messages.

-- default gateway

-- DNS server

-- subnet mask

Roating algorithms

Dejkstra - impl. is based on well-known graph shortest-path algo. Global algorithm. Routers broadcast information. Robustness is better then in "Distance Vector Algorithm".

Distance Vector Algorithm - impl. idea is based on Bellman-Ford algorithm. Decetralized. Information is exchange with 1-ring neighbors. Algorithm is iterative, distributed, asynchronous. During update metric update "Bad news propagate badly!"

RIP (Routing inforamtion protocol) - distance vector algorithm and distance metric is number of hops. Send distance vector every 30 seconds. If you don't advertise until 180 seconds (6 rounds) then it means that you died. RIP implemented via UDP/IP.

OSPF (Open Shortest Path First) - link state algorithm based on Dijkstra Algorithm. Algorithm of OSPF is complex. Allow multiple same-cost paths, multiple cost metrics, hierarchical OSPF. Support level hierarchy in routers.

BGP (Border Gateway Protocol) - allow obtain subnet reachability, determine "'good" routers. Information is propagating via TCP.

Link layer

CRC - goal is to find R(r bits long) s.t. if combine sending data D with it then long bit number <D,R> will be divisible by G (generator r+1 bit long). 

I.e.  D * 2^r (xor) R = nG <=>D * 2^r (xor) R (xor) R = nG (xor) R <=> D * 2^r  = nG (xor) R <=>(can be proved I think) R=remainer(D * 2^r/G)

Taxonomy of ways to communicate hosts connect with each other in the media:

1. Channel partitioning -- Time/Frequency

2. Random access -- ALOHA, S-ALOHA, CSMA/CD, CSMA, CSMA/CA (used in 802.11)

3. Taking turns -- polling, token passing (Bluetooth, FDDI, IBM Token Ring)

IP addr. is 32bits long and is like steet address in human life, 

MAC address is is 48 bits long (wifi 802.11 and ethernet 802.3) is like Social Security Number for people in US.

Manchester encoding - each bit has a transition - 1 high to low, 0 is low to high, if compare with naive way to send signal by levels this encoding has in it global clock, and receiver can perform syncronnization with the sender.

CSMA/CD - in case of finding collision m-th thimes we wait random K from {0,1,2,...,2^m}, Wait K 512 bits data.

Routers vs Switches

Both perform store and forward.

Routers work in network layer contains routing table which is build by routing algorithm based on topology of whole network.

Switches work on link layer (under link layer is only physical layer) internally switches also has switch table. But the way how it is filling is relatively simpler compare with routers - it is filling based on filtering and self learning alorithms. Records in this table by the way has TTL.

Wifi (802.11)

802.11a -- 5-6 GHz, up to 54 Mbps

802.11b -- 2.4-5 GHz, up to 11 Mbps

802.11g -- 2.4-5 GHz, up to 54 Mbps

802.11n -- 2.4-5 GHz, up to 200 Mbps

Base Station (BS) - is similar to what is Access Point (AP)

Base Service Sell or Cell (BSS) - is AP and host which is connected to it

In link layer there is an impl of CSMA/CA. 

CSMA/CD is impossible in principle in wireless communication.

Optionally in BSS can be used RTC+CTS schema with polite access to the media from the hosts.

Couple advanced capabilities are: 

  - Rate adaptation (change base stattion, change modulation technique(there are lot of them))

  - Power management