Computer Networks (Final)

Lecture 12 and beyond (for final; I don't remember if it's cumulative).

Network layer

• Highest level layer that is present in hosts and routers

• performs addressing, forwarding, and routing, etc.

Autonomous System/Domain

region of a network under a single administrative entity (routers/switches); can make decisions within itself as long as everyone uses IP routing protocol; assigned unique identifier (ASN)

Local forwarding

directing a packet to the correct interface so that it progresses to its destination via reading address from packet header & search forwarding table (in memory)

Global routing

Setting up network-wide forwarding tables to enable end-to-end communication

Forwarding (data plane)

directing one data packet and each router uses local routing state

Routing (control plane)

compute the forwarding tables that guide packets

• jointly computed by routers using a distributed system

IP packet header/IP header

present in all devices

• IP version number (4 bits), packet length (16 bits)

• destination’s IP address (32 bits)

• TTL (8 bits)

• checksum (16 bits)

• fragmentation fields (32 bits)

• ToS (8 bits), options (variable length)

IP header checksum

router discards if checksum is invalid; checksum recalculated at every router

ToS (Type of Service)/Differentiated Service

allows packets to be treated differently based on needs (e.g. indicate priority, congestion notification)

IP header option field examples

• record route

• strict source route

• loose source route

• timestamp

IP header protocol byte

tells destination what to do with the received packet (transport layer protocol)

IPv4 fragmentation fields

• identifier: which fragments belong together

• flags: (reserved: ignore, DF: don’t fragment, MF: more fragments coming)

• offset: portion of original payload this fragment contains

Router capacity

number of external router ports * speed of a port

What’s inside a router?

linecards & interconnect/switching fabric

Input linecard

• Receive incoming packets (physical layer)

• update the IP header

• lookup the output port for the destination IP address

• queue the packet at the switch fabric

Router hardware processing

• packet classification: map packets to flows

• buffer management: decide when and which packet to drop

• scheduler: decide when and which packet to transmit

Max-min fairness

How round-robin routers attempt to service flows in a fair fashion assuming packets are of same size

Fair queuing

How round-robin routers attempt to service flows fairly with packets of varyinig sizes

Explicit Congestion Notification

packet header, set by congested routers (serves as early indicator of congestion to avoid delays)

Valid routing state

• produces forwarding decisions that always deliver packets to their destinations

• no dead ends & no loops

Flooding

node sends its link-state info (edge + cost to reach) out on all of its links, the next node forwards the info on all of its links (except the one the info originated from)

What causes flooding?

• topology change (e.g. link/node failure/recovery)

• configuration change (e.g. link cost change)

• periodically

Link-state routing protocols

• OSPF: open shortest path first (uses IP as opposed to TCP or UDP)

• IS-IS: intermediate system to intermediate system

Distance vector routing protocol

each node tells its neighbors about its global view

Link-state routing protocol

each node broadcasts its local information

Border Gateway Protocol

extends distance-vector ideas to accommodate policy (autonomy, policy, privacy)

IP addressing hierarchy

Network: 23 bits prefix (inter-domain routing uses this)

Host: 9 bits suffix

Subnet mask

a group of machines that share the same IP address prefix

BGP route selection

controls whether/how traffic leaves the network

BGP route export

controls whether/how traffic enters the network

Gao-Rexford

rules for determining how to export routes

eBGP sessions

sessions between border routers in different ASes (learn routes to external destinations)

iBGP session

sessions between border routers and other routers within the same AS (distribute externally leraned routes internally)

IGP (Interior Gateway Protocol)

provide internal reachability

Messages in BGP

• open: establishes BGP session (it uses TCP)

• notification: report unusual conditions

• update: inform neighbor of new routes & old routes that become inactive

• keep-alive: inform neighbor that connection is still viable

Route selection priority order

based on the attributes provided in BGP, it determines which route is chosen