MSS - Maximum Segment Size
RTT - Round-Trip Time
ICMP - Internet Control Message Protocol

Key concepts:

[ ] Protocol

Layering

Application
Transport
Network
Link
Physical

[ ] Service

[ ] Connectionless vs. connection-oriented communication and services

[ ] Interface

Network architecture

Tier 1 Content Providers IXPs
Tier 2
Tier 3
Clients

[ ] Reference models

[ ] Standards

Circuit vs. packet switching

Circuit switching	Packet switching
resources reserved for duration of communication	resources not reserved
	messages may have to queue
e.g. telephone lines	e.g. Internet

Multiplexing

Frequency-division multiplexing (FTM)	Time-division multiplexing (TDM)
the frequency spectrum is divided among connections	time divided in frames
e.g. for telephone 4kHz band	each frame divided in slots for each connection
e.g. radio	simpler setup
wasteful during silent period	could lose packets

IPv4 vs. IPv6

Key differences

Address size: 32 bit v4, 128 bit v6
v6 - fixed length 40 bit header
v6 - no fragmentation allowed
v6 - checksum removed to reduce processing
v6 - includes ICMPv6

Transition

Dual-stack: IPv6 routers replace IPv4 routers but support protocol and translate packages to older routers
Tunneling: IPv6 datagram carried as payload among IPv4 routers

Application layer:

Principles of network applications

Application architectures
Client-server
P2P
Hybrid
Application requirements
Data loss
Timing
Throughput
Security
Transport protocols
TCP
UDP
Sockets

Client-server vs. peer-to-peer applications

Salient features of widely used Internet applications (e.g. web, DNS)

Web and HTTP - over TCP
- HTTP messages
  request
  response
- Cookies - unique ID generated by server (cookie locally, entry in DB remotely)
  authorization
  shopping carts
  recommendations
  user session
- Web cache
  acts both as client and server
  typically at ISP
  + reduce response time for client
  + reduce traffic
  + enables poor content providers to deliver effectively
FTP :21 - over TCP
- Server opens second TCP connection when file transfer initiated
- Command/response
  commands: ASCI text
  response: status code and phrase
Email :25 - SMTP over TCP
- Components:
  user agents
  mail servers
  SMTP protocol (between mail servers)
- Direct transfer: sending to receiving server
  handshaking
  transfer
  closure
- Command/response
  commands: ASCI text
  response: status code and phrase
DNS
- Decentralized
- Services
  hostname to IP translation
  hostname aliasing
  mail server aliasing
  load distribution - sets of IPs for one canonical name
```
 Root DNS Servers
  /     |    \
com   org   edu ...
 |
e.g. yahoo.com DNS servers ...
```
- 13 root DNS servers worldwide
- Types of DNS servers
  - Top-level Domain (TLD) servers
    responsible for com, org, net, edu, aero, jobs, museums and all country domains
    "Network Solutions" maintains .com TLD
    "Educause" maintains .edu TLD
  - Authoritative DNS servers
    organization's DNS servers - mapping for own servers
    can be maintained by organization or service provider
  - Local namer server
    does not strictly belong to hierarchy
    each ISP has one (a.k.a. DNS)
    acts as proxy

Transport layer:

Multiplexing/demultiplexing

Demultiplexing at rcv host
delivering received segments to correct socket
Multiplexing at send host
gathering data from multiple sockets, enveloping data with headers (used for demux)
Connectionless demultiplexing
- each datagram has source and destination IP address
- each datagram carries one transport-layer segment
- each segment has source and destination port number
Connection-oriented demultiplexing
- TCP socket identified by 4-tuple
  source IP address, port number
  destination IP address, port number
- Server may support many simultaneous TCP sockets
  web servers have sockets for each connecting client
UDP: User Datagram Protocol
- Why UDP?
  no connection establishment (removes delay)
  simple (no states)
  small segment header
  no congestion control (UDP can blast data full speed)
- Uses
  Media - loss tolerant, rate sensitive
  DNS
  SNMP
- Could add reliability at application level
  UDP checksum

Principles of reliable data transfer

Stop-and-Wait
Go-back-N
Selective repeat
window size * 2 < ACK #s

Principles of congestion control and TCP congestion control

End-to-end congestion control
Network layer does not provide any support for congestion control
End systems must infer congestions as no explicit feedback is returned by network
TCP has to employ end-to-end congestion control
Network assisted congestion control
Router sends package indicating congestion or specifying transfer rates
Data feedback:
Direct network feedback - router indicates to client,
Network feedback via receiver.

Example: ATM ABR congestion control
TCP congestion control
TCP controls its data-rate based on the perceived congestion on the network
Self-clocking: TCP adjusts window size based on received ACKs
Congestion control principles
- A lost packet implies congestion and send rate should be reduced
- When an ACK arrives for a previously unacknowledged packet, window could be increased
- Bandwidth probing - increase rate until packet is lost - thus finding optimal send rate
TCP congestion control algorithm
- Slow start
  Start at 1MSS and increase window by 1 for each previously unacknowledged packet
  Effectively grow window exponentially (since +1 holds for each MSS)
  Stop on a loss event and set sstresh to cwnd/2 and cwnd to 1
  Stop when cwnd >= sstresh and go to congestion avoidance mode
  Stop if three duplicate ACKs and go to fast recovery
- Congestion avoidance
  Grow linearly by 1MSS
- Fast recovery
  Grow when double ACK is received (thus recovering from lost packs?)
  Additive-increase, multiplicative-decrease (AIMD)
  Increase by one when ACK, half when loss
Fairness
UDB does not throttle thus may suffocate TCP
Nothing can prevent application from parallel TCP (opening many connections to server)

Internet transport protocols (TCP, UDP)

Network layer:

Virtual circuit vs. datagram networks

Datagram network - network-layer connectionless service (e.g. Internet)
no call setup at network level
packets forwarded using destination host address (packets between same source-dest may take different paths)
routers don't keep state about end-to-end connections (no network-level concept of "connection")
Longest prefix matching - in table use regex to forward ranges of addresses to link interface
Virtual Circuit - network-layer connection service (e.g. ATM)
each packet carries VC id (not destination host address)
every router on source-dest path maintains "state" for each connection
VC number can be changed on each link (new VC number comes from forwarding table)
A VC consists of:
- path from src to dest
- VC numbers, one number for each link along path
- entries in forwarding tables in routers along path

Internet (datagram)	ATM (VC)
data exchange among computers	evolved from telephony
"smart" end systems (control, error recovery)	human conversion (strict timing, reliability, guaranteed service)
many link types (uniform service difficult)	"dumb" end systems (e.g. telephones) - complexity inside network

IP addressing and forwarding

32 bit IP address
20 bytes IP overhead + 20 bytes TCP overhead
Three types of switching fabrics:
- memory
  switching under direct control of CPU
  limited by memory bandwidth (2 bus crossings per datagram)
- bus
  limited by bus bandwidth
  32 Gbps by Cisco 5600: sufficient speed for enterprise
- crossbar (mutliplexer)
  60 Gbps by Cisco 12000: f*ck yeh
Links have MTU (max. transfer size). Some links fragment datagrams and destination reassembles them
When fragmenting, length = data.length + 20 bytes overhead => 4000b = 1480b + 1480b + 1040b, where length = (1500, 1500, 1060)
Offset = data.length/8 = (0, 185, 370)
IPv4 addressing
- Subnets: high order bits, device don't need router to reach each other
- CIDR (Classless InterDomain Routing)
ICMP addressing ()

Routing algorithms

Links State (LS): Dijkstra's algorithm
Given the cost between neighbors, traverse the net and find optimal path
Distance Vector: Dx(y) = min{Cx(v)+Dv(y)}
nodes exchange tables and adjust values

Metric	Link State (LS)	Distance Vector (DV)
Msg complexity	O(nE), n nodes, E links	Msgs between neighbors only
Spd of convergence	O(n^2), may oscillate	varies, count-to-infinity problem
Robustness (rtr malfunction)	node advertises incorrect costs	DV node can advertise incorrect path cost
	each node computes its own table	error propagate through net

Hierarchical algorithm: aggregate routers into regions, "autonomous systems (ASs)"
routers in same region run same protocol, "intra-AS protocol"
gateway router - at edge of AS, has link to router in another AS
Greedy search

Internet routing

Routing Information Protocol (RIP): distance vector algorithm
Distance metric: number of hops
Routing table for router X:

Destination subnet: A
Next router: Y
# hops to dest: n

If no advertisement within 180sec, remove router and destroy links using router. Send updated table to neighbors
RIP routing managed by application-level process called route-d
advertisement sent using UDP, periodically repeated

Open Shortest Path First (OSPF)
publicly available
uses Link State algorithm
advertisements disseminated to entire AS (via flooding)
carried in OSPF messages directly over IP, rather than TCP or UDP
Advantages over RIP:
hierarchical OSFP in large domains
multiple same-cost paths allowed (only one in RIP)
for each link, multiple metrics (e.g. best effort, real-time)
integrated uni- and multi-cast support (MOSPF)
security - all OSPF messages authenticated
Hierarchy
local area: LS advertisements backbone

area border routers: "summarize" distances to nets in local area, advertise to other area border routers backbone routers: run OSPF routing limited to backbone boundary routers: connect to other AS's

Interior Gateway Routing Protocol (IGRP) - Cisco proprietary
the de facto inter-domain routing algorithm (the one that glues the Internet together)
BGP provides each AS means to:
eBGP: obtain subnet reachability information from neighboring ASs
iBGP: propagate reachability to all AS-internal routers
obtain "good" routes to other networks based on reachability information and other policies
Why different Intra- and Inter-AS routing?
- Policy:
  - Inter-AS domain: admin wants control over how its traffic is routed, who routes through its net
  - Intra-AS: single admin, so no policy decisions needed
- Scale:
  - Hierarchical routing saves table size, reduced update traffic
- Performance:
  - Inter-AS: policy may dominate over performance
  - Intra-AS: can focus on performance

Link layer:

Error detection and correction

Parity checking
Single bit parity
Two dimensional bit parity: detect and correct single bit error
Internet checksum: detect errors in transmitted packet
Cyclic Redundancy Check (CRC)
Packet - <D,R>
Generator - G; G.length = r+1
R s.t. <D,R> divisible by G
Receiver divides <D,R> by G, if non-zero reminder - error!

Multiple access protocols

Link types:
point-to-point - dial-up, Ethernet
broadcast - old-fashioned Ethernet, Wi-Fi, etc.
Multiple Access Protocols
single shared broadcast channel
two or more simultaneous transmissions by nodes
distributed algorithm that determines how nodes share channel, i.e. determine when nodes can transmit
communication about channel sharing must use channel itself
Ideal Multiple Access Protocol
1. efficient - channel speed - R bps, 1 node, send at rate R
2. fair - M nodes send at R/M
3. fully decentralized - no special node to coordinate transmission, no sync of clocks, slots
4. simple

MAC protocols

Channel Partitioning:

divide channel into smaller pieces (time slots, frequency, code)
allocate piece to node for exclusive use
a priory decision assuming the works case in terms of #users and uniform use by all users

Time Division Multiple Access (TDMA)
access to channels in "rounds"
each gets fixed length sloth
unused slots stay idle

Frequency Division Multiple Access (FDMA)
channel spectrum divided into freq bands
each station assigned fixed band
unused transmission time in freq band goes idle

Random Access

channel not divided, collisions allowed
"recover" from collisions

Slotted ALOHA

Assumptions	Operation
all frames same size	when node obtains frame, transfers in next slot
time divided into equal slots	no collision: send in next slot
nodes start to transmit only at slot beginning	collision: node retransmits in each cons. slot until
nodes are synchronized
if >=2 nodes transm. in same slot, all detect collision

Pros	Cons
single active node transmit at full speed	collisions, wasting slots
decentralized: only slots in nodes need be in sync	idle slots
simple	nodes may detect collision in less than time to transm
	clock sync

Efficiency - long-run fraction of successful slots, many nodes, many frames to send
NB: At best channel used 37% if the time!

Pure (unslotted) ALOHA
simpler
no synchronization
when frame first arrives - transmit immediately
NB: At best channel used 18% if the time! Even worse!

Carrier Sense Multiple Access (CSMA)
listen before transmit
if channel sensed idle - transmit frame
else - deffer transmission

CSMA\CD (Collision Detection)
collision detected within short time
colliding transmissions aborted, reducing channel wastage
CD easy with wired LAN (signal strength), difficult in wireless LAN

"Taking Turns"

nodes take turns, nodes with more to send may take longer turns
"adaptive round-robin"

Polling
Master node invites Slave nodes to transmit in turns
typically used with dumb slaves
Concerns: polling overhead, latency, single point of failure (master)

Token Passing
control token passed from one node to another sequentially
Concerns: token overhead, latency, single point of failure (token)

Ethernet

Many different Ethernet standards
Common MAC protocol and frame format
Different speed: 1 Mbps, 10Mbps, 100Mbps, 1Gbps, 10Gbps
different physical layer media: fiber, cable
Star topology: switch in center, each client runs on separate line

Preamble used to sync sender and receiver clock rates
Manchester Encoding - each bit has voltage transition, allows for clock sync

Connectionless: no handshake between sending and receiving NICs
unreliable: no ACKs or NACKs. Gaps are possible - to be filled if using TCP
Ethernet's MAC protocol: unslotted CSMA/CD

Hubs vs. switches vs. routers

Hubs - physical-layer repeaters
bits coming in one ling go out all other links at same rate
all nodes can collide with one another
no frame buffering
no CSMA/CD, host NICs detect collisions
Switches - link-layer device - smarten than hubs, take active role
store and forward Ethernet frames
examine incoming frame's MAC address, selectively forward to one-or-more links, use CSMA/CD
transparent - hosts are unaware of presence of switches
plug-and-play, self-learning - switches do not need to be configured

allow multiple simultaneous transmissions
hosts have dedicated direct connection to switch
switch buffers packets
full duplex

learning of MAC addresses:
1. record link associated with sending host
2. index switch table using MAC dest address
3. if entry found - send or update
  else - flood (forward on all but receiving interface)
Switches vs. Routers
Both store-and-forward devices:

Routers	Switches
network-level	link-level
maintain routing tables	maintain switch tables
implement routing algorithms	implement filtering and learning algorithms

VLANs
Port-based VLAN: switch port grouped by software so that single physical switch operates as multiple virtual switches.
traffic isolation: frames to/from some port range can only reach these ports. Can also define VLAN based on MAC addresses of endpoints.
dynamic membership: ports can be dynamically assigned among VLANs.
forwarding between VLANs: done via routing (just as with separate switches)

koshov/COMN.md