CompNet 3

Noise

no consistency in data Multi-access Schemes: phase / polarisation / spin / CDMA

Networks

ISPs (backbone/edge), Enterprises (core/edge), Datacenters (top-of-rack/aggregation & core) (+all border)

Switches

Enterprise/Edge (24-48 ports), Aggregation (192+), Backbone (fewer), Border (very few)

Forwarding

'data plane' directing packet to outgoing link, single router using routing state

Routing

'control plane' computing paths packets will follow, routers communicate, jointly create routing state

Network Service Model

eg guaranteed delivery (with max time), in order delivery, guaranteed min bandwidth etc

Network layer connectionless service

provided by datagram network, no end-end connection, use addresses, 'elastic' service, no timing req, 'smart' end systems (control/recovery), simple network, non-uniform

Network layer connection service

provided by a virtual circuit - a connection-oriented network

Virtual Circuit

source-dest path, ≈ telephone circuit, setup & teardown, packets carry VC#, router with state for each connection, link & router resources may be allocated to VC giving predictable service, links can change VC#, strict timing & reliability req, guaranteed service, complexity inside network not at end systems.

Longest Prefix Match

route on entry with highest number of bits from start which match - most specific

Switching via Memory

direct CPU control, packet copied to memory, then read, 2 bus crossing, limited by mem B

Switching via Bus

input port - output port via shared bus, bus contention, speed limited by bus bandwidth

Switching via Interconnection Network

no bus bandwidth limitations, may fragment datagram into cells

Output Port Queuing

arrival rate via switch > output line speed, can lead to queuing delay or loss (overflow)

Input Port Queuing

fabric slower than total arrival rate, Head-of-line blocking, front datagram stops others behind

Buffer Size

2TxC in general, (2T x C) / √n for small, O(log W) for tiny, T is RTT, C is capacity, n is #flows, W is window

IPv4 Packet

4b version, 4b header length (#32b words), 8b type of service, 16b total length, 16b identifier (tell which fragments belong together), 3b flags (ReservedF, DontfragF, MoreF - not last), 13b frag offset (part of datagram), 8b time to live (decrement each hop, if 0 discard & send time exceeded msg to src, prevents loops), 8b protocol (TCP=6,UDP=17), 16b header checksum (every router checks), 32b source IP, 32b dest IP, options (trcrt)

IP Address

32-bit identifier for host/router/interface has subnet part then host part, allocated by ICANN

Interface

Connection between host/router & physical link Subnet Mask: Number of bits in subnet part

Subnet

device interfaces with same subnet part, can physically reach each other without intervening router

Classless InterDomain Routing

subnet part of arbitrary length Classful Routing: A/B/C/D/E - 8/16/24

Dynamic Host Configuration Protocol

dynamically get address from server alternative to hard-coded in file. Addresses leased, hosts renew leases, allows reuse of addresses. Dynamic reallocation, can move around

Hierarchical Addressing

route aggregation allows efficient advertisement of routing information

Network Address Translation (NAT)

all datagrams leaving local network have same NAT IP address but diff port#s, use NAT translation table with map of (sourceIP,port#)(NAT IP, new port#), use for incoming datagrams, outside client cant connect to server behind NAT because must use single visible IP, must statically configure NAT to fix, could use Universal Plug n Play Internet Gateway Device to allow NATed host to learn public IP & add/delete port#s. NAT & FTP have a control channel which violates layers.

Relaying

NATed client establishes connection to relay, external client connect to relay, relay bridges pkts between

Internet Control Message Protocol

communicate network level info: errors, echo req/reply, carried in IP datagrams

Traceroute

uses TTL + odd port, on expiry ICMP message with name & IP, calc RTTx3, stop on host unreachable msg

IPv6

version, traffic class, flow label, payload length, next header, hop limit, source address, dest address. No fragmentation (end-end), no header len (fixed size), no checksum (other layers), new options - next header (fix size), 64 bit addresses, flow label (resource allocation to flows, handle different types of service)

Tunneling

IPv6 carried as payload in IPv4 datagram among IPv4 routers

Improvements

accountability & anonymity (source address), different packet header at edge/core, payment field

'Valid' Global Routing State

iff forwarding decisions deliver pkts to dest, no dead ends/loops, goal of rting protocols

Source / Destination Routing

paths from 2 sources can be very different, even if they pass through same nodes

Destination Based Routing

paths to same destination must coincide once they overlap, unless they never cross

Delivery Tree

set of paths to destination, must cover every node exactly once, spanning tree routed at destination

Route Computation

learn from observation / centralised computation (1 node has entire network map) / pseudo-centralised computation (all nodes have entire network map) / distributed computation (no nodes have entire map)

Self-learning route computation

topology where loops impossible (eg spanning tree), only 1 path to destinations, use 'learning switches' to discover paths, switches send flood packets to all ports on spanning tree, all nodes covered, switches learn by remembering where flooding packets that arrive at it originated, can use packet source IDs stored with TTL, if unknown destination then forward to all other ports and learn from response

Self-learning route computation algorithm

packet arrives; index table; if entry {if destPort == arrivePort drop else forward } else flood. - requires loop-free topology (spanning tree), slow to react to failure (TTL), little control over paths (no computation)

Data-link Layer

responsibility of transferring datagram from one node to adjacent node over a link

Frame

layer-2 packet, encapsulates datagram

Link Layer Channel Services

framing, link access (encapsulates datagram into frame + header, trailer; channel access if shared medium, uses MAC addresses in headers for source & dest) reliable delivery between adjacent nodes (little error checking on low bit-error links (fibre, twisted pair) higher error rates for wireless) flow control (pacing between send & receive) error detection (signal attenuation, noise, receiver detects errors - signals for retransmit or drops) error correction (identifies & correct bit errors) half & full duplex (half - both nodes can transmit, not at same time)

Link Layer Implementation

in adaptor (network interface card) attaches to system buses, hard+soft+firmware

Encoding

encryption, error detection, compression, analog

Non-return-to-zero

1/0 = high/low, no neutral or rest position

Non-return-to-zero-mark

transition on clock edge if bit is one, no transition is bit is zero

Non-return-to-zero-inverted

transition at clock mid-point if bit is one, no transition is bit is zero

Manchester code

transition at period mid-point, low-high if 1, high-low if 0, data xor clock = value, 2 clock/period

Quad-level code

4 levels, represent 2 bits per period

Baud rate

number of voltage changes per second Bit rate: number of bit changes per second

Code Division Multiple Access

unique code per user, all share same frequency but have different 'chipping' sequence to encode data, signal = data X 'chipping' sequence, decoding - inner product of signal & sequence

Even Parity

add bit such that #1s even, detect 1b errors 2D Bit Parity: detect & correct 1b errors

Cyclic Redundancy Check

detects more errors than parity eg 2 bit, multiplication & binary division, parameterised by n bit divisor P

Forward Error Correction

replace erroneous data by its closest error-free data

Error Correction/Detection Advantages & Disadvantages

Correction: + no resend - more check bits, false recovery possible

Detection: + less check bits - resend