Computer Networks

Table of Contents

1 lecture 2

1.1 TODO Read chapter 1

  • REC: request for comment
  • Routers can be connected in arbitrary topology; switches are cheap and fast, lack software to deal with arbitrary configuration, hence connected in tree like formation.

1.2 TODO Read about FM/AM

2 lecture 3

2.1 Cable Network

  • designed for broadcast/one way communication
  • shared wire
  • data is also broadcasted, modem recognizes which data is requires; drops rest
  • uploading is more complicated - no central transmitter
    • uploading is done using control signal to gain uploading right
  • each line in digital ISP diagram can be an abstraction over analog network (slide 16)

2.2 Wireless access networks

  • wireless LAN
    • overlapping channels
      • protocol designed to take turns to transmit data
    • 802.11 b/g/n : 11 54 150
  • wide area wireless access
    • provided by cellular
    • 3g,4g LTE

2.3 Physical Media

  • difference between Cat wires is due to insulation - wire can carry more signal cat 5: 10Mbps, cat 6:

2.4 Network core

2.4.1 Packet switching

  • circuit switching use for phone
    • not suitable for digital data:
      • burst of data
      • not fixed sized

3 lecture 4

3.1 numerical comparison: circuit switch v/s packet switch

Circuit switching: 10 users, 100kbps per user -> 1Mbps

Packet Switching: N, active users a = k, 0 <= k <= N prob{a=k} = (n,K) 0.1k 0.9 ^ (n-k) prob{a<=10} = ∑k=010 prob{a=k} N = 35 prob{a<=10} = 1 - 0.04%

3.2 Circuit switch implemented over packet switching (Virtual Circuit)

3.3 Routing

  • aka forwarding

4 lecture 5, 6

  • traceroute: implemented using TTL (time to live)
  • network layer has server address
  • link layer has local address (maybe router address)

4.1 Internet protocol stack (pramatic view):

  • Router implements till network

4.1.1 Application

HTTP

4.1.2 transport   OS implemented

TCP, UDP

4.1.3 network

routing

4.1.4 link

deals with 1 data pack if there is interference due to other signals, it handles it. Askes sender to resend

4.1.5 physical

deals with synchronizing frq

4.2 many physical, application layer design but one network layer

  • transport layer: 2 (TCP, UDP)
  • glass hour architecture

4.3 OSI/ISO reference model (Internet protocol + additional layers):

  • ideal layer model
  • can be implemented in application layer

4.3.1 Presentation:

allow application to interpret meaning

4.3.2 session:

take where left from

4.4 buffer overflow attack

4.5 Chapter 2: Application layer

4.5.1 Architecture

  1. Client - Server
  2. Peer to Peer

4.5.2 File sharing

  1. Napster like

    central server

  2. Kazaa

    flooding traffic

  3. Bit torrent
    • chop file into pieces
    • share pieces among peers
    • Incentive mechanism build in

5 lecture 7

5.1 Application layer (continued)

5.1.1 Sockets

5.1.2 TCP and UDP

  • TCP: does not provide timing, minimum toughput gurantee
  • UDP: not reliable

5.1.3 HTTP

  • http is full ascii text
    • binary if sent, has to be encoded
  • Persistent (HTTP 1.1) and non-persistent (HTTP 1.0)

6 lecture 8: HTTP continued

6.1 HTTP request message

  • full ascii
    • if we want to send/receive binary, encode into ascii

7 lecture 11: Socket Programming

  • TCP - reliable, stream oriented
  • UDP - unreliable

8 Structured Peer to Peer networks

8.1 Chord

8.1.1 ID space considered as ring

  • take modulo after N
  • ID: hash of the address
  • each node (Peer) responsible for it's previous node
  • segment can have different length: hashing may not be uniform
  • for each file, it's hash is calculated, and stored in graph
  • node keeps track for the file before it.

8.1.2 operations

  1. Structure
  2. Neighbors
    • number of neighbors = O(log2 n)
  3. lookup for a file
  4. Insert a peer Finding neighbors is similar to finding file
  5. Delete a peer
    • Tell everyone to delete files owned by the node
    • Tell the predecessor to take over as owner of the files
    • Fault - what if system crashes
      • replication to neighbor he will take care of cleaning and acting as file owner

8.1.3 Variation

  1. neighbor O(log2 n), lookup O(log3 n)
  2. neighbor O(k logk n), lookup O(logk n)
    • instead of dividing into 1/2; divide in 1/3

8.2 CAN (Content address network)

  • n dimension ID space
  • each node has n co ordinate
    • x = H1(a), y = H2(a)
  • overflows are modulo(tated)
  • Peer responsible for area
  • Neighbor: who share the boundary of space
  • Finding a file
    • shortest path among neighbors
  • Complexity
    • lookup
      • O(n1/2): for 2 dimension
      • O(n1/k): for k dimension
    • neighbors
      • O(n1/k): for 2 dimension
      • O(3 × n1/k): for k dimension
  • Deletion
    • who owns area after node deletion
      • voluntary give up area to neighbor

9 Pastry

10 Chapter 3: Transport layer (contd)

  • missed last class (AoA Exam)
  • read about post letter example in book for TCP v network problem

10.1 Pipelined Protocol

10.1.1 go-back-N

  • receiver expects a number:
    • if that number is not received, reject it.
    • if expected number received, accept, send ack
  • corrupted ack

10.1.2 Seleiictive repeat

  • each packet has it's own timer
  • Receiver has more than 1 size buffer

11 TCP

11.1 Sequence Number and accumulative ack

  • sequence number is per byte
  • ack means ack - 1 is received, ack is expected

11.2 Window size and data throughput

window size determines data throughput 

r = \dfrac{W}{RTT}
  • how to set initial window size:
    • slow start and exponential growth

11.3 Slow start and exponential growth

  • We don't know the network congestion, start with one and probe network.
  • Double the sending if successful ack
  • when to stop doubling:
    • OS limit
    • network limit - network starts dropping packet.

11.4 Measurement of network status

11.4.1 Mild congession: triple duplicate acks

packets are going through but some are lost.

  • cut window size by half.
  • send only leading packet

11.4.2 Severe congession: timeout

  • almost all packets are dropped
  • cut size to 1
    • and start doing exponential growth

11.5 TCP lifecycle (slow start & AIMD)

  • exponential increase till threshold, then additive incrase till we hit tripple congestion
  • multiplicative decrease when we hit triple ack, then cut to half and additive incrase
  • faced timeout:
    • drop to window 1.
    • exponential growth
    • threshold to half of original threshold
      • then additive incrase
  • initial threshold is set by OS

11.6 Fairness

  • Reason of using multiplicative decrease (why do we cut to half instead of decreasing by 1)
  • Person using higher bandwidth will dec by half, that's half of larger bandwidth Contrasting with person using less bandwidth
    • if you earn more, you pay more

11.7 TCP segment structure

  • two way communication
    • acknowledgment number can be used to piggy back with data segment

11.8 Three way handshake

11.8.1 reset command

11.8.2 SYN

  • snync ack number
  • ack sync
  • ack

11.8.3 FIN

  • to finish connection
    • if receiver also send FIN, then close connection

11.8.4 Timeout interval

TimeoutInterval = EstimatedRTT + 4 \times DevRTT
where
DevRTT = (1 - \beta) \times DevRTT + \beta \times SampleRTT - EstimatedRTT

11.8.5 actual handshake

  1. Connection Establish
    1. -> SYNbit = 1, Seq = x
    2. <- SYNbit = 1, Seq = y ACKbit = 1, ACKnum = x + 1
    3. -> ACKbit = 1, ACKnum = y + 1
  2. Connection Close
    1. -> FINbit = 1, seq = x
    2. <- ACKbit = 1, ACKnum = x + 1
    3. <- FINbit = 1, seq = y
    4. -> ACKbit = 1, ACKnum = y + 1

11.9 Flow control

  • put in remaining buffer size in Window field in segment

11.10 Misc

11.10.1 Faster TCP

  • negotiate for larger segment size
  • make parallel TCP connection - each get equal share
  • hack into to increase the Additive increase to more than one
  • f1/f2 = (RTT2/RTT1)2 (rate is inversely proportional to RTT)

11.10.2 RTT and fairness

if RTT is larger then additive increase will more frequent rate ∝ 1/RTT2

12 Stop and wait

One buffer space for sender and receiver.

12.1 pkt corrupted -> checksum -> retransmission

12.2 ACK corrupted -> sequence number -> 0/1 only required in this case

12.3 pkt lost -> timeout

12.3.1 how to set appropriate timeout

measure RTT (round trip time) delay.

12.4 ACK lost -> timeout + sequence number

12.5 NACK free design

along with ack, send which was the last correct segment

13 Go back N

  • sequence number is 0 to n. (total n + 1(buffer space + 1); 1 extra to wrap around)
  • sender has buffer size n; receiver has buffer size 1
  • ack of sequence number received
  • problems:
    • pkt corruption: drop pkt; send last successful received packet seq number (called as accumulative ack); timeout -> go back n
    • pkt lost: trash unexpected packets; do accumulative ack (ack only most recent successful pkt);
    • out of order: trash until expected packets; update expected packet
    • ack corruption: cumulative ack; thus when next ack is received, assumed corrupted ack is good
    • ack loss: same as above
    • ack re-order: same as above; when earlier ack arrives: (prof says can't handle)
      • keep sequence number so large, wrap around doesn't happend in same transfer session

14 Selective repeat

  • requires 2N sequence number
  • receiver (and sender) buffer size n
  • timer for each packet
    • since packet can be sent independent of each other
  • problems:
    • ack lost: mark the rest of the ack as received and after timer of that packet timesout, resend
      • packets cannot be delivered out of order, do not delivery until all packets are received
  • why 2N
    • what if all ack are lost
      • new expected seq wrapped around (multiple expected seq)
      • individual timer timeout
      • it will re transmit, it will fit the expected seq

15 RTT and window size Chap 4: Network Layer

15.1 r ∝ 1/RTT2

  • one comes from window size - window size is doubled on RTT
  • one comes from rate: in one RTT, 2 windows are sent

15.2 Network Layer

15.2.1 Forwarding

15.2.2 Routing

15.3 forwarding table

Header Value output Link
   

16 Inside Router

16.1 2 functions of router:

  1. Run routing algorithm
  2. Forward datagrams

16.2 IP Protocol

16.2.1 Datagram

16.2.2 TTL:

each router reduces TTL by 1

16.2.3 IP fragmentation and re-assembly

  • offset field in packet

16.3 IP Addressing

16.3.1 Class A

00000001.X.X.X ^-–—^|^-—^ network| host address| Addr

128 class A address ^ divide into Class B 214 Class B address ^ divide into class C first 3 bytes fixed

16.3.2 Private IP

  • 10.X.X.X class A
  • 192.X.X.X class B
  • something Class C

These are not assigned to anyone, so everyone can use it.

16.3.3 TODO Subnet

  • 223.1.4.1/24 - first 24 bits are subnet bits
    • alternate representation: 223.1.4.1/255.255.255.0 ^------–—^ first 24 bits are 1

16.3.4 DHCP: dynamic host configuration protocol

16.3.5 NAT: network address translation

  • router does translation and reverse tranalation
  • IP + port number

17 IPv6

17.1 v/s IPv4

  • IPv4: 32 bit address
  • IPv6: 40 byte header
    • IPv6 has virtual circuit switching
    • Removed checksum

17.2 Tunneling

Transitioning from IPv4 to IPv6: IP in IP -> IP tunneling

17.3 Running algrorithm

  • Link State
  • Distance Algorithm

17.4 Routing Algorithm:

  • Dijkstra
  • Bellman Ford

18 Network Layer, routing algorithms:

18.1 Bellman Ford

18.2 count-to-infinity, poisoned-reverse

do not solve all problems. Use max hop limit

18.3 Hierarchical Routing

  • if every router broadcasts routing info, then the network will clog by the routing messages.
  • whole network acts as a single node
  • Called as autonomous system
  • if two routers in a domain are not connected
    • they open TCP connection between themselves and do routing.

18.3.1 Inter and Intra domain routing

19 Interior gateway protocols (IGP)

19.1 RIP: Routing information protocol

19.2 EGBG

20 Hamming code and Cyclic redundancy check

20.1 Hamming code

  • can detect only a bit error
  • saves number of parity bit

20.2 CRC

  • noise can affect consecutive bits
  • when 1 bit corrupt, there is good chance next bit (nearby bit) will also get corrupted. CRC detects burst error
  • parity bit cannot detect even number of bit error

20.3 MAC protocols

20.3.1 TDMA: time division multiple access

21 Slotted Aloha, CSMA for ethernet/ wifi

21.1 Slotted aloha: max throughput 37%

21.2 Taking turns

  • what if node with token crashed

Author: Anurag Peshne

Created: 2017-04-05 Wed 22:11

Emacs 25.1.1 (Org mode 9.0.5)

Validate