Computer Networks Midterm

Data Communication Circuit Switching:

End-end resources allocated to, reserved for “call” between - and -.

In a link that has 4 circuits, call gets - circuit in top link and - circuit in right link.

Deducated resources: _ _, circuit-like (guaranteed) performance

Circuit segment _ if not used by _.

Commonly used in traditional _ networks

source, destination, 2nd, 1st, no sharing, guaranteed, idle, call, telephone

Packet Switching - Characteristics:
1. Efficient: - used on - (vs. dedicated path of circuit switching). - -.

2. Generic: can used for - types of applications.

3. Out-of-order delivery: - not guaranteed to be the - for - packets

4. Contention: due to - resources: s-, l-, b-

5. Delay: packets may be -

resources, demand, statistical multiplexing, many, path, same, different, shared, switch, links, bandwidth, queued

Physical Media:
1. Signal: propagates between -/- pairs
2. physical link: what lies - transmitter and receiver.

3. guided media: signals propagate in - -. copper, fiber, coax

4. unguided media: signals propagate -. radio.

5. twisted pair (TP): two insulated - -. Category -: - mbps, - gpbs ethernet. Category -: - gpbs

transmitter, receiver, between, solid media, freely, copper wires, 5, 100, 1, 6, 10

Human protocols: -, -. Specific message -. Specific - taken when messages -, or other events

questions, introductions, sent, actions, received

Network Protocols: - rather than -. all communication - in - governed by a - of -

machines, humans, activity, internet, suite, protocols

protocols define -, - of messages - and - among network entities, and - - on message transmission, receipt - - and -

format, order, sent, received, actions taken, message syntax, semantic

Internet (TCP/IP) Protocol Stack (from top to bottom, order matters) (5):

application, transport, network, link, physical

Application: FTP, SMTP, HTTP

supporting network applications

Transport: TCP, UDP

process-process data transfer

Network: IP, routing protocols

routing of datagrams from source to destination

Link: Ethernet, 802.11 (WiFi), PPP

data transfer between neighboring network elements

Physical

bits “on the wire”

Access Networks: How to connect end systems to edge router?

• residential access nets

• institutional access networks (school, company)

• mobile access networks

Access Networks: Considerations

• bandwidth (bits per second) of access network?

• shared or dedicated?

see image

Internet Structure: Network of Networks

1. End systems connect to Internet via - -

2. Access ISPs in turn must be -. so that any two hosts can send - to each other.

3. Resulting network of networks is very -. Evolution was driven by - and - -.

access ISPs, interconnected, packets, complex, economics, national policies

Option: connect each access ISP to a - - ISP? - and - ISPs have economic agreement

global transit, customer, provider

POP: point-of-prescence

Host: Sends packets of -.

• Host sending function:

• takes - message

• breaks into smaller chunks, aka -, of - L bits

• transmits packet into access network at - rate -.

• link transmission rate aka link -, aka link -

• packet transmission delay = time needed to transmit L-bit packet into link = L (bits)/R (bits/sec)

data, application, packets, length, transmission, R, capacity, bandwidth

Four sources of packet delay:

1. d_proc: nodal processing

2. d_queue: queueing delay

3. d_trans = L/R: transmission delay

4. d_prop  = d/s: propagation delay

Add all those together to make d_nodal

L = packet length (bits), R = link bandwidth (bps), d = length of physical link, s = propagation speed in medium (2×10⁸ m/sec)

Packet Loss:

• Queue (aka buffer) preceding link in buffer has - capacity

• packet arriving to full queue - (aka loss)

• lost packet may be retransmitted by - node, by source - system, or not at all

finite, dropped, previous, end

Throughput: rate (bits/time unit) at which - transferred between -/-

• instantaneous: rate at - point of time

• average: rate over - period of time

bits, sender, receiver, given, longer

Bottleneck link: link on end-end - that constrains end-end -

path, throughput

Bad guys: attack server, Network Infrastructure

• Denial of Service (DoS): Attackers make resources (server, bandwidth) unavailable to legitimate traffic by overwhelming resource with - -.

  • 1. Select -

  • 2. break into - around the network

  • 3. send - to target from - hosts

bogus traffic, target, hosts, packets, compromised

P2P Architecture

• - always-on server

• arbitrary end systems directly -

• peers request service from other peers, provide service in return to other peers

  • Self scalability: new peers bring new service -, as well as new service -

• peers are intermittently - and change - addresses

  • Complex management

no, communicate, capacity, demands, connected, IP

TCP Service: - - between sending and receiving process

reliable transport

TCP Service: sender wont overwhelm receiver

flow control

TCP Service: throttle sender when network overloaded

congestion control

TCP Service: - - - timing, minimum throughput guarantee, security

does not provide

TCP Service: setup required between client and server processes

connection-oriented

UDP Service: - - - between sending and receiving process

unreliable data transfer

UDP Service: - - -: reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup

does not provide

Protocol for Web Surfing: HTTP (hyper-text transfer protocol)

• web page consists of -

• object can be HTML file, JPEG image, Java applet, audio file,…

• web page consists of base - which includes - - objects

• each object is addressable by a -

objects, HTML-file, several referenced, URL

non-persistent HTTP issues:

• requires 2 - per object

• OS overhead for - TCP connection

• browsers often open - TCP connections to fetch - -

RTTs, each, parallel, referenced objects

persistent HTTP:

• server leaves connection - after sending response

• subsequent HTTP messages between - client/server sent over open connection

• client sends - as soon as it encounters a referenced object

• as little as one - for all the referenced objects

open, same, requests, RTT

Uploading Form Input:

• POST method:

  • - - often includes form input

  • input is uploaded to - in entity -

web page, server, body

Uploading Form Input:

• URL method:

  • uses - method

  • input is uploaded in URL - of request line

GET, field

Transport Services and Protocols:

• provide - - between app processes running on different hosts. App requires different -.

• Transport protocols run in end systems

  • - side: breaks app messages into -, passes to - layer

  • - side: reassembles segments into -, passes to - layer

• more than one transport protocols available to apps

  • internet: TCP (in-order, reliable) and UDP (unordered, unreliable

logical communication, services, send, segments, network, receive, messages, app

handle data from multiple sockets, add transport header (later used for demultiplexing).

multiplexing at sender

use header info to deliver received segments to correct socket.

de-multiplexing at receiver

TCP socket identified by a 4-tuple

• -/- IP address

• -/- port number

source, dest

receiver uses all four values to direct segment to appropriate socket

de-mux

web servers have - sockets for each connecting client

• non-persistent HTTP will have - socket for each request

different

server host may support - simultaneous TCP sockets

many

memorize format

UDP Checksum

• Goal: - "errors” (flipped bits) in transmitted segment

detect

UDP Checksum

• Sender:

  • treat segment contents, including header fields, as sequence of _-bit integers

  • Checksum: _ (1-complement sum) of segment contents

  • sender puts checksum _ into UDP checksum field

16, addition, value

UDP Checksum

• Receiver: (if received checksum is not all 0s)

  • _ checksum of received segment

  • check if computed checksum equals checksum field value:

    • No = _ detected

    • Yes = no _ detected

compute, error

Principles of Reliable Data Transfer

• important in application, transport, link layers

• What does rdt stand for?

• characteristics of - channel will determine - of rdt

reliable data transfer protocol, unreliable, complexity

rdt2.0: Channel with Bit Errors:

• underlying channel may flip bits in packet

• how to recover from errors?

  • - (ACKs): receiver explicitly tells sender that pkt received OK

  • - - (NAKs): receiver explicitly tells sender that pkt had errors

• New mechanisms in rdt2.0

  • - detection with checksum

  • -: controls msgs (ACK, NAK) from receiver to sender

acknowledgements, negative acknowledgements, error, feedback

rdt2.0 has a Fatal Flaw:

• if ACK/NAK gets corrupted, sender doesnt know what happened at receiver and transmits current pkt if ACK/NAK corrupted which may lead to _ packets

• handling and detection

  • sender adds - - to each packet

  • receiver checks - - and discards (doesnt deliver up) the -ed packet

duplicate, sequence number

sender sends one packet, then waits for receiver response (stops packet duplication)

stop and wait

rdt2.2: a NAK-free Protocol

• same functionality as rdt2.1, using _ only

• instead of _, receiver sends ACK for last pkt received OK.

• duplicate ACK at sender results in same action as NAK: _ current pkt

ACKs, NAK, retransmit

rdt3.0: Channels with Errors and Loss

• New assumption:

  • underlying channel can also lose packets (data, ACKs)

• Approach:

  • sender waits “-” amount of time for ACK.

  • retransmits if no ACK received in this time

  • if pkt (or ACK) just delayed (not lost):

    • - will be duplicate, but seq. #’s already handles this

    • receiver must specify seq $ of pkt beind ACKed

    • requires - -

reasonable, retransmission, countdown timer

Performance of rdt3.0:

• correct but _

• network protocol limits use of _ resources

• need to identify the cause and fix it: why _ is so low?

stinks, physical, utilization

Pipelined Protocols:

• -: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts

  • range of seq. #’s must be increased

  • buffering at sender and/or receiver

• no more stop and wait

• generic form of ‘- -’ protocols

pipelining, sliding window

Pipelining Protocols:

• _-_-_: sender can have up to N unack’ed packets in pipeline

  • receiver only sends _ ack

  • sender has timer for oldest unack’ed packet and when it expires, retransmit all unack’ed packets

go-back-N, cumulative

Pipelining Protocols:

• - -: sender can have up to N unack’ed packets in pipeline

  • rcvr sends - ack for each packet

  • sender maintains timer for each unack’ed packet and when it expires, retransmit only that unack’ed packet

selective repeat, individual

retransmit packet n and all higher seq # pkts in window

timeout(n)

TCP: Overview

_-_-_: one sender, one receiver

point-to-point

TCP: Overview

reliable, in-order _ stream: no “message boundaries”

byte

TCP: Overview

-: TCP congestion and flow control set window size, sliding window

pipelined

TCP: Overview

- - -: bi-directional data flow in same connection. MSS: maximum segment size

full duplex data

TCP: Overview

- -: sender will not overwhelm receiver 

flow controlled

TCP: Overview

_-_: handshaking (exchange of control msgs) initialized sender, receiver state before data exchange

connection-oriented

see image

TCP - -: byte stream “number” of first byte in segment’s data

sequence numbers

TCP -: seq # of next byte expected from other side. cumulative ACK

acknowledgements

how receiver handles out-of-order segments?

TCP spec doesnt say, up to implementation

TCP Round Trip Time, Timeout

• timeout interval = - + - (safety margin)

estimatedRTT, 4*DevRTT

-: informally: “too many sources sending too much data too fast for network to handle”, different from flow control! caused by lost - and long -

congestion, packets, delays

TCP Congestion Control: additive increase

increase cwnd (congestion window) by 1 MSS every RTT until loss detected

TCP Congestion Control: multiplicative decrease

cut cwnd in half after loss

TCP Congestion Control: approach

sender increases transmission rate (window size), probing for usable bandwidth, until loss occurs

TCP Slow Start:

When connection begins, - rate - until first loss event

increase, exponentially

TCP: Detecting, Reacting to Loss

• loss indicated by timeout: cwnd set to 1 - (TCP Tahoe) or is cut in - (TCP Reno). window then grows exponentially to threshold, then grows linearly

• loss indicated by 3 duplicate ACKs: dup ACKs indicate network capable of delivering some segments → move to - recovery state. cwnd is set to threshold + -

• threshold is set to 1/2 of - in both cases of loss

MSS, half, fast, 3, cwnd

Why is TCP fair?

- - -:

• additive increase gives slope of 1, as throughput increases

• multiplicative decrease decreases throughput proportionally

two competing sessions

-: determine route taken by packets from source to dest.

routing

-: move packets from router’s input to appropriate router output

forwarding

- network provides network-layer - service

datagram, connectionless

_-_: network provides network-layer _ service

virtual-circuit, connection

analogous to TCP/UDP connection-oriented/connectionless transport layer services, but:

• -: host-to-host

• - -: network provides only one

• -: in network core

service, no choice, implementation

Virtual Circuits:

• “source-to-dest path behaves like - circuit”

  • performance-wise

  • network actions along source-to-dest path

• call setup, teardown for each call before data can flow

• each packet carries VC identifier (not destination host address)

• every router on source-dest path maintains “state” for each passing connection

• link, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)

telephone

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address

longest prefix matching

Router Architecture Overview:

• two key router functions:

  • - - algorithms/protocol (RIP, OSPF, BGP) (software)

  • - datagrams from incoming to outgoing link (hardware

run routing, forwarding

IP Fragmentation, Reassembly:

• network links have MTU (- - -) - largest possible link-level frame. different link types, different MTUs

• Large IP datagram divided “fragmented” within net. one datagram becomes several datagrams. “reassembly” only at - destination. IP header used to identify, order related fragments

max transfer size, final

IP Addressing:

• CIDR (c- i-d- r-)

• - portion of address of arbitrary length

• address format: a.b.c.d/x, where x is # bits in - subnet portion of address

classless interdomain routing, subnet

IP Addressing: CIDR

• How to obtain the subnet part of an IP address?

using a subnet mask

DHCP: (d- h- c- p-)

• -: allow host to dynamically obtain its IP address from network server when it joins network

  • can renew its lease on address in use

  • allows reuse of addresses (only hold address while connected/”on”)

  • support for mobile users who want to join network 

dynamic host configuration protocol, goal

DHCP overview:

• hosts broadcasts “DHCP -” msg [optional]

• DHCP server responds with “DHCP -” msg [optional]

• host requests IP address: “DHCP -” msg

• DHCP server sends address: “DHCP -” msg

discover, offer, request, ack

DHCP can return more than just allocated IP address on subnet:

• address of first-hop - for client

• name and IP address of - server

• - - (indicating network versus host portion of address)

router, DNS, network mask

NAT router must:

• for - datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #)

• for - datagrams: replace (NAT IP address, new port #) in dest fields of every incoming datagram with corresponding (source IP address, port #) stored in NAT table

• remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pair

outgoing, incoming

see image

ICMP stands for

internet control message protocol

• ICMP is used by hosts & routers to communicate network-level information

  • - -: unreachable host, network, port, protocol

  • - -/-: used by ping

• network-layer “-” IP: ICMP msgs carried in IP datagrams

• ICMP message: -, - plus first 8 bytes of IP datagram causing error

error reporting, echo request/reply, above, type, code

IPv6 Motivation:

• - -: 32-bit address space soon to be completely allocated

• IPv6 d- f-:

  • fixed-length 40 byte header

  • no fragmentation allowed

initial motivation, datagram format

Transition form IPv4 to IPv6:

• IPv6 datasgram carried as payload in IPv4 datagram among IPv4 routers is known as -

• not all routers can be - simultaneously

  • no “- -”

tunneling, upgraded, flag days

Input Port Queueing:

• fabric - than input ports combined → queuing may occur at input queues

  • queuing delay and loss due to input buffer -!

slower, overflow

Input Port Queueing:

• _-_-_-_ (HOL) -: queued datagram at front of queue prevents others in queue from moving forward

head-of-the-line blocking