Ryerson Computer Science CPS706: Computer Networking

(go back)

1 Access networks

Network Edge

  • DSL, Cable, Home Network
  • Physical Media:Twisted pair, coax, fiber, radio

Network Core

  • Packet Switching
    - allows more users on the network
    - some queuing delay; transmission delay dependent on packet size
  • Circuit Switching: circuit is created from source to destination
    - no queuing delay
    - takes some time to establish the connection
  • Packet vs Circuit Switching Example
    - Assume 1Mb/s link
    - Assume avg 100kp/s usage per user
    - with Cct switching, max of 1Mbps/0.1Mbps = 10 users
    - if there are 35 users, the probability of > 10 using at same time is: $\sum {35 \choose i} p^i(1-p)^{35-i}$, where i is 11 ? = 0.0004
    - so low probability that the bandwidth will be regularly exceeded even though there are more than 3x number of users in the packet-switched case

1 Packet-Switching: Loss & Delay

Packet Loss

packets may be dropped if the buffer of a node becomes full (ie, if the avg rate of packet arrival is > the avg rate of transmit)

Packet Delay = PROCESSING + QUEUEING + TRANSMISSION + PROPAGATION

  • dtrans = L/R [ the time for a packet to exit from a node ]
    - Packet must be fully received by the node before it can be forwarded; so smaller packet sizes are generally desireable
    - L is the number of bits in the Packet
    - R is the rate in Bits per Second

    End to End Transmission delay can be calculated:
    $[\frac{TotalSize}{NumPackets} / R] \cdot (NumHops + NumPackets - 1)$

    Rough diagram from notes
  • dprop = d/s [ the time to travel over the wire ]
    d is distance in meters
    s is speed; usually ~ 2x10^8 m/s

2 Application Layer Protocols

Internet Protocol Stack

As messages traverse down through the layers, they generally accumulate additional headers from each layer

  1. Application
  2. Transport
  3. Network
  4. Link
  5. Physical

HTTP Protocol (port 80)

  • Persistent vs non-persistent (header setting)
  • Web server caching: Last-Modified, If-Modified-Since
  • Methods: GET, POST, UPDATE, DELETE
  • Conditional Get:
    Browser includes the header if-modified-since: date & time
    - If page has not been modified since requested date, server returns no content with http code 304
    - If page has been modified, the server returns the whole page

Others App Protocols:

  • FTP (TCP, 2 connections, port 21), SMTP, POP3

2 DNS - domain name system

Hierarchy:

Root -> TLD (top-level domain) -> individual ISP-level servers

DNS Records

  • Type A - the other types must each be followed by a Type A record
  • Type CName - canonical name
  • Type NS - name server
  • Type MX - mail exchange

2 DNS - domain name system (cont'd)

DNS Messaging

  • UDP protocol, port 53
  • See message format with questions, answers, etc
    • answer field MUST have at least 1 TypeA record with IP address

Basic setup, small business (example, Networkutopia.com)

  • DNS Server, Web Server, Mail Server
  • TLD Server has records:
    • (networkutopia.com, dns1.networkutopia.com, NS)
    • (dns1.networkutopia.com, 212.212.212.1, A)
  • Then local DNS (dns1.networkutopia.com) has these records for Web and Mail servers:
    • (networkutopia.com, www.networkutopia.com, CNAME)
    • (www.networkutopia.com,212.212.212.2, A)
    • (networkutopia.com, mail.networkutopia.com, MX)
    • (mail.networkutopia.com, 212.212.212.3, A)

2 Peer-to-Peer

Performance vs client-server

  • Client-server: Time to distribute files via client-server increases linearly with the number of clients
  • P2P: Time to distribute files via p2p tapers off as number of clients increases

Architecture

  • Tracker: contains a small amount of info to track participants (ip addresses, but not data)
  • DHT: distributed hashtable, among the peers
  • Rarest First: peers try to get the rares chunks of the file in order to distribute evenly amongst each other

Algorithm: tit-for-tat

  • unchokes users with high upload rate (adds to client's "top 4")
  • chokes users with low upload rate

Distributed Hash Table

  • each peer needs to be assigned an integer (node)
  • key is assigned to the node with closest ID (or next largest)
  • each peer only knows the ID/IP of the previous and next peer in the circle, arranged by ID

3 Transport Layer

  • logical comms between processes in a host
  • as opposed to Network Layer which is logical comms between hosts
  • does multiplexing and demultiplexing
  • at the mercy of the Network Layer

UDP - unreliable, connectionless (but fast)

  • Used by: DNS, SNMP...
  • connectionless: ie, no initial or final handshaking

TCP - reliable, connection-oriented

  • 4 properties: src port, src IP, dest port, dest IP
  • Connection Management
    • client: Socket clientSocket = new Socket("hostname", "portnum");
    • Client sends TCP SYN
    • Server responds to SYN
    • Then client can send data...
    • SYN Flooding attack
    • Upon clientSocket.close(); server receives FIN, replies with ACK and also a FIN
    • MSS = Maximum Segment Size; set to ensure that
  • Reliable Data Transport
    • correctness
    • performance
    • scalability

    RDT basically involves having the sender get an acknowledgment that each segment was properly received; each segment does not have to be individually acknowledged.

    Acknowledging each segment before sending the next would be too slow, so we have Pipelined Protocols

Flow Control (TCP)

  • if receiver's buffer fills up, the receiver responds to the sender with rwnd = 0; (this is in the textbook, not slides)

Congestion Control (TCP)

  • two basic approaches
    1. End to end congestion control
    2. network-assisted congestion control
  • when reached 3 duplicated ACK's, the congestion window is cut in half
  • when a timeout occurs, the congestion window is cut all the way down to 1, then starts the slow-start again
  • Sender limits transmission: LastByteSent - LastByteAcked ≤ Min(cwnd, rwnd)
    • rwnd is almost never the constraint; cwnd is dynamic
  • rate ~ cwnd / RTT bytes per sec
  • TCP Slow Start - used only at the start of the connection, or after a timeout
  • Congestion Avoidance... or Additive Increase Multiplicative Decrease

Round-trip Estimation, Deviation, and TCP Timeout setting

  • EstimatedRTT = (1 - α)*EstimatedRTT + α*SampleRTT; // RHS EstimatedRTT is the old value; α is usually 1/8 = 0.125
  • Dev_RTT = (1 - B) * Dev_RTT + B * | SampleRTT - EstimatedRTT |; // B is usually 0.25
  • TimeoutInterval = EstimatedRTT + 4 * Dev_RTT
  • Avg_throughput = 0.75 *

Pipelined protocols

  • Go-back-N
    • Max of N un-ACK'd segments can be sent
      gobackn
    • Receiver has no extra buffer, so if packets come out of order, they all have to be re-sent from the last in-order segment
    • Receiver can send cumulative ACK because only in-order segments are accepted
    • Sender has one timer: for oldest un-acked packet
    • receipt of each packet ACK clears that packet's watchdog timer
  • Go-back-N (cont'd)
    • See PDF: GBN sender extended FSM: ...
      • In the event of a timeout, all the yellow packets need to be re-sent
      • *** Sender keeps 1 timer; timing since the earliest sent unacknowledged packet; Timer gets reset when the wrong ACK seq # is received; stupid ***
    • See PDF: GBN receiver extended FSM
      • expected sequence number should be initialized to 0
      • Receiver is dumb; can only buffer 1 packet, so if they come out of order, the sender is forced to resend all the packets previously sent
  • Selective Repeat
    • Max of N un-ACK'd segments can be sent
    • Receiver has some buffer space, so out-of order packets can be ACK'd; requires that the sender only re-send lost packets
    • N is not allowed to be unlimited for the purposes of flow control and congestion control
    • sender has timer for each un-acked packet
    • Window size must be less ≤ half the size of the sequence number space for SR protocols
    • number of seq #s must be at least 2x the window size; but since its unknown, the rule in the internet: do not repeat same sequence number within 3 minutes of a single tcp connection

TCP Segment Structure

tcp sender (simplified) timer doesn't restart repeatedly for duplicates

More on Reliability

  • When NextSeqNumer is SendBase, then the window is empty
  • Ack from receiver, "Y", says that everything less than Y has been received; now send me Y.
  • SendBase is the first Unack'd segment at the Sender!!
  • Acknowledgments can be cumulative; if Ack100 is lost, then Ack120 is received by the sender, the sender moves forward without resending Seq100.
  • after 3 duplicated ACK's, repeat the packet; symptom of mild congestion
  • timeouts are symptom of severe congestion

Network Layer

Network Service Model

Q: what service model for "channel" transporting datagrams from sender to receiver

cellular phones: after first base station, voice packets enter parallel network that belongs to cellular network

For Internet, network layer service model offers no guarantees for bandwidth, loss, order, or timing

  • datagram forwarding: when looking to match forwarding table entry with a destination address, use the entry with the longest prefix