network layer Flashcards
Network layer addresses:
How to get from A to B
How to connect to multiple networks
Hot to manage network resources (congestion, quality of service)
the router
device that enables new features through new protocols
Who performs store-and-forwarding switching?
router
routing
finding a path through a network
important properties of routing
correctness
simplicity
robustness
stability
fairness
efficiency
routing tables
tells us for each packet on which link to forward it
distance vector routing
send distance vector to neighbours
update routing table based on incoming distance vectors
good news: propagation
problem: count to infinity when machine fails
link state routing
does not suffer from the count to infinity problem, but more is complex
replaces distance vectors in ARPANET 1979
uses a shortest path algorithm
link state routing steps
- routers only send packets with information about their direct neighbours
- these packets are flooded over the network
- routers build an overview of the network using these packets and run a shortest path algorithm
What can go wrong with flooding link state packets?
hierarchical routing
reducing routing table sizes for large newtorks
inter-netwroking
getting packets to their destinations across multiple networks
challenges for sending packets end-to-end over multiple networks (inter-networking)
technological:
different protocols
different maximum packet sizes
different QoS guarantees
political:
different costs
privacy concern
competition/disputes
inter-networking with autonomous systems
routing inside an Autonomous System:
intradomain routing, uses Interior Gateway Protocol, ex: OSPF
routing between Autonomous Systems:
interdomain routing, uses an Exterior Gateway Protocol, ex: BGP
OSPF
Open Shortest Path First
routing within an autonomous system
uses a form of link state routing
build a graph representation of the network
uses a hierarchy called areas to manage large networks
areas in OSPF
all areas are connected to Area 0 (backbone)
are border router exchanges summarised routing info between areas
boundary routers connect to another AS; uses both interior and exterior gateway protocol
routers only know topology of the area they are in
for destinations not in area: through backbone
BGP
Border Gateway Protocol
routing between large independent networks
-supports arbitrary policies put in place by ISPs, companies, organisations, etc. autonomous systems connect at IXPs
stub networks do not need BGP: only one way to send outgoing packets
AS1 provides transit service
uses a path vector protocol (form of distance vector routing)
routing policies of BGP
peer above transit: routes learned from peers are preferred over routes learned from transit providers
hot potato routing: nearest exit point from the network as quickly as possible
shortest AS path: the path with the fewest Autonomous System (AS) hops is preferred
connecting networks with different protocols
if source and destination networks use different protocols, they cannot communicate
tunneling
if an intermediate networks uses different protocols, they can communicate by tunneling
used to route IPv6 packets over IPv4 networks
routers support multiple types of networks
data wrapped in header form multiple networking layers
network layer packet used as payload for other network-layer packet
packet fragmentation
packet size can be limited by hardware, software, protocols, law, etc.
transparent fragmentation
nontransparent fragmentation
avoiding packet fragmentation
MTU discovery
IP
The Internet Protocol
data transfer protocol at network layer
challenges of IP
error detection/correction -> header checksum
preventing permanently looping packages -> time to live
globally identifying computers -> NAT
carrying packets over links with different size requirements -> total length, fragment offset
IP version 4
frame header-32 bits
time to live: counter, prevents infinite loops, the time the packet can spend in the network
identification
fragment offset: allows for the packet to be sent in fragments, all fragments have an identification number-offset
total length = header + data
-16 bit length field → packet size can reach 64KiB
header checksum
- uses checksum
- computed by adding all 16-bit half-words in the header
802.3 → 802.1Q
- VLAN type > 1500 interpreted as type
- maximum frame sizes differs across link-layer protocols
IPv4 addresses
uses 32-bit addresses
written in dotted decimal notation
32-bit address gives 2^32 > 4 billion addresses
How are packets routed to IPv4 addresses with latencies in the order of msec?
by reducing routing table sizes using hierarchical routing
routing used in IP
nontransparent fragmentation + MTU (avoiding)
NAT
Network Address Translation
IP version 6
- many more addresses
- simplified header - improves bandwidth/latency
- easier to add options in the header
- improved security support
IPv6 header
32 bits
value 0x06 indicates IPv6
hop limit = time to live
next header: specifies transport layer protocol or extension header
Addressing the Problem of Too Many Addresses
managing the size of the routing tables
Internet Protocol Prefixes and Subnets
routing algorithms can calculate routes to prefixes, instead of to every individual address
prefixes handed out by a single organisation: ICANN
organisations can further subdivide their prefix to create subnets
CIDR
Classless InterDomain Routing
….
ICMP
Internet Control Message Protocol
if something goes wrong, routers send these messages to seders
examples:
- destination unreachable
- time exceed - used by the program traceroute
- “echo” and “echo reply” - used by program ping
- router advertisment/solicitation
- packet needs fragmentation/packet too big
DHCP
Dynamic Host Configuration Protocol
- MAC addresses are built into NICs but network addresses are not
- used to configure other settings such as: network mask, addresses of default getaways, DNS, time servers, etc.
DHCP discover
DHCP offer
ARP
Address Resolution Protocol
problem: we don’t know which value of ad and ed go together
request is broadcast over Ethernet
ARP packets wrapped in Ethernet headers
service types
connectionless
connection-oriented
connectionless service
- datagrams
- routers are routing algorithms to decide where to send each packet individually
- used by the IP
connection-oriented service
-virtual circuits
- decide fixed route during connection setup
- all packets part of the connection follow this route
- ISPs can use this on top of IP
service comparison
datagrams:
- no setup required
- router failures have low impact
- packets contain full addressing information
- routers are stateless
virtual circuits:
- easy congestion control
- easy quality of service guarantees
- packets contain VC numbers
- routers keep track of active VCs
Congestion control
combined responsibility of network and transport layers
goodput
rate of useful packets arriving at the receiver
approaches to congestion control
simplest: resource over-provisioning
traffic-aware routing
admission control
traffic throttling
admission control
- if there is congestion, new traffic has to wait
- allows new traffic load only if the network has sufficient capacity
- Can you find a path that doesn’t result in congestion?Yes → allow trafficNo → traffic must wait
traffic-aware routing
- if link costs are static, all traffic is routed over lowest-cost links
- using dynamic cost calculation can prevent congestion
- calculate link cost as a function of current load
- need to prevent oscillations
- small cost updates
- multiple paths
traffic throttling
- send messages in the opposite direction to explicitly indicate network congestion
- most common implementation
- set special bits in IP packet
- inform sender of congestion through TCP
- end-to-end
- send back a “choke” signal; when the source receives this packet, it slows down transmission
- used in TCP/IP via Explicit Congestion Notification (ECN)
- link-by-link
- send back a “choke” signal; every router that receives this packet slows down transmission
traffic shaping
regulating network resource usage
challenge: limit available data rate, but allow bursty traffic
regulates rate and burstiness of data entering the network
token bucket
outgoing rate between 0 and B
average outgoing rate equal to R
sending n bytes requires n tokens
bucket can store limited number of tokens (B)
incoming token rate: R
tokens come at constant rate
Load Shedding
choosing partial failure over total system failure
RED
Random Early Detection
- drop packets randomly if buffer space is almost full
- sends an implicit signal to the sender: slow down!
- works if transmission errors are unlikely cause of packet loss
- wired links are reliable (errors are unlikely)
- wireless channels (and other unreliable ones) need to solve transmission errors on the data link layer to hide them from network layer
Quality of Service aspects
bandwidth: maximum data rate [bps]
delay: time it takes to get from src to dst
jitter: variation in packet delay; 0 jitter means delay is constant
packet loss: probability of packets being dropped
different apps have different requirements
file sharing: bandwidth
audio on demand: jitter
video on demand: bandwidth, jitter
telephony: delay, jitter
videoconferencing: bandwidth, delay, jitter
