Chapter 4 - Network Layer

Network layer:
	transport segment from sending to receiving host

Forwarding and routing:
	Forwarding: Packet arive at router's input link -> the router move the packet to the appropriate output link
				Example: Packet arrive from host H1 to router R1 must be forwarded to the next router on a path to H2
	Routing: The network layer must determine the route or path taken by packets as they flow from a sender to a receiver.
			 Use Routing algorithms (determine the path along which packets flow from H1 to H2)

	Forwarding: router-local action of transferring a packet from an input link interface to the appropriate output link interface
	Routing: network-wide process that determines the end-to-end paths that packets take from source to destination

Network service model:
	Guaranteed delivery
	Guaranteed delivery with bounded delay

	Flow of packets:
		In-order packet delivery
		Guaranteed minimal bandwidth
		Guaranteed maximum jitter
		Security services

Internet = Best-effort service = no service at all

ATM network:
	Constant bit rate (CBR) ATM network service
	Available bit rate (ABR) ATM network service

Network layer connection and connectionless service:
	datagram network provide network connectionless service
	VC provide network connection servicee
	analogous to transport layer service, but:
		service: host-to-host
		no choice: network provide 1 or the other
		implementation: in network core

virtual-circuit (VC) networks:
	only a connection service at the network layer
datagram networks:
	only a connectionless service at the network layer

Internet = datagram network
ATM, frame relay = VC network

VC network:
	maintain connection state information for the ongoing connections
	each time a connection is established across a router, a new connection entry must be added to the router's forwarding table
	each time a connection is released, an entry must be removed from the table

	call setup, teardown for each call before data can flow
	each packet carry VC identifier (not destination host addr)
	every router on source-dest maintain state for each passing connection
	link, router resources may be allocated to VC

	consist of:
		path from src to dest
		VC number, 1 number for each link along the path
		entries in forwarding table in router along path

	packet belong to VC carry VC number
	VC number can be change on each link

	phases:
		VC setup
		Data transfer
		VC teardown

	routers along the path between 2 end systems are involved in VC setup
	each router is fully aware of all the VCs passing through it

	Initial call -> Incoming call -> Accept call -> Call connected -> Data flow begins -> Receive Data

	signaling messages: set up the VC
	signaling protocols: exchanges signaling messages

	forwarding table modified when an existing connection through the router is set up or torn down

Datagram network
	router matches a prefix of the packet's destination addr with the entries in the table
	longest prefix matching rule

	no call setup at the network layer
	no state about end-to-end connections

	packet forward using dest host addr

	connectionless
	maintain forwarding state information in their forwarding tables

	forwarding tables are modified by routing algorithm, update 1 - 5 min

Forwarding Table
	forwarding = switching

	Input ports
	Switching fabric
		Switching via memory
		Switching via a bus
		Switching via an interconnection network

	Output ports
	Routing processor

	forwarding table = router forwarding plane
	router control plane

	Queue
		packet loss, drop tail
		packet scheduler -> quality-of-service guarantees
		active queue management (AQM)
		random early detection (RED)
		head-of-the-line (HOL) blocking

Internet: datagram
	data exchange among computers
		elastic service, no strict timing
	smart end systems
		can adapt, perform control, error recovery
		simple inside network, complexity at edge
	many link types
		different characteristics
		uniform service difficult

ATM: VC
	evolve from telephony
	human conversation:
		strict timing, reliability requirements
		need for guaranteed service
		dumb end systems
			telephone
			complexity inside network

Router:
	run routing algorithm/protocol (RIP, OSPF, BGP)
	forwarding datagram from incoming to outgoing link

	input port function:
		given datagram dest, look up output port using forwarding tabnle in input port memory
		goal: complete input port processing at line speed
		queuing if datagram arrive faster than forwarding rate into switch fabric

	Switching fabric:
		memory, bus, crossbar

	output port:
		buffering required when datagram arrive from fabric faster than the transmission rate
		scheduling discipline choose among queue datagram for transmission



IP
	datagram
		Version number
		Header length (20 bytes)
		Type of service
		Datagram length (16 bits)
		identifier, flags, fragmentation offset
		time-to-live
		upper layer protocol
		header checksum
		source and dest IP addr
		options
		payload

		20 bytes header
		IP/TCP: 40 bytes header

	fragment

IPv4
	interface
	dotted-decimal notation
	subnet, subnet mask

	IP addr:
		32 bit for host, router interface
		interface:
			router have multiple interface
			host have 1 interface
			IP addr associate with each interface

	Classless Interdomain Routing (CIDR)
		prefix

	classful addressing

	DHCP: Dynamic Host Configuration Protocol
		encapsulated in UDP, IP, 802.1 Ethernet
		temporary IP addressing
		plug-and-play protocol

		DHCP server discovery: DHCP server message
		DHCP server offer: DHCP offer message, address leave time
		DHCP request: DHCP request message
		DHCP ACK: DHCP ACK message

		can return more than just allocated IP addr on subnet
			addr of first-hop router for client
			name and IP addr of DNS server
			network mask (indicate network versus host portion of addr)

	NAT (Network Address Translation)
		real with private addr
		NAT translation table
		connection reversal - NAT traversal

		controversial:
			router should onlhy process up to layer 32
			violate end-to-end argument
			addr shortage should be solved by IPv6

	UPnP: Universal Plug and Play
		allow NATed host to:
			learn public IP addr
			add, remove port mappings (with lease times)

ICMP: Internet Control Message Protocol
	error report, echo request/reply
	carry in IP datagram

IPv6
	expanded addressing capabilities: 128 bit addr
		anycast addr
	streamlined 40-byte header
	flow labeling and priority

	datagram format
		version
		priority (traffic class)
		flow label
		payload length
		next header
		hop limit
		source and dest addr
		data

		NO: fragmentation, reassembly, checksum, options

	ICMPv6

Translation from IPv4 to IPv6
	dual-stack
	tunneling

IPsec: IP security
	cryptographic agreement
	encryption of IP datagram payloads
	data integrity
	origin authentication

Routing Algorithm
	Global:
		all routers have complete topology, link cost info
		link state algorithms
	Decentralized:
		router know physically connected neighbor, link cost to neighbor
		iterative process of computation, exchange of info with neighbor
		distance vector algorithm

	Static:
		route change slowly over time
	Dynamic:
		routes change more quickly
			periodic update
			in response to link cost changes

	Link-State Routing Algorithm
		Dijkstra algorithm
			net topology, link cost known to all nodes
			compute least cost path from 1 node to other node
				give forwarding table for that node
			iterative: after k iterations, know least cost path to k dest

	Distance Vector Algorithm
		Bellman-Ford Equation
		from time-to-time, each node send its own distance vector estimate to neighbors
		asynchronous

		iterative, asynchronous
			each local iteration caused by
				local link cost change
				update message from neighbor
		distributed
			each node notify neighbor when it change
				neighbor then notify their neighbor if need

		each node:
			wait for change from neighbor
			recompute estimate
			if distance vector to any dest change, notify neighbor

	Compare Link-State and Distance Vecotr:
		Message Complexity:
			LS: with n nodes, E links -> O(nE) message send
			DV: exchange between neighbor only (convergence time vary)
		Speed of Convergence:
			LS: O(n^2) require O(nE) messages
			DV: vary (routing loop, count-to-inf problem)
		Robustness
			LS: node can advertise incorrect link cost
				each node computes only its own tabnle
			DV: DV can advertise incorrect path cost
				each node table used by others

	Hierarchical Routing:
		scale: with 200 million dest
			can't store all in routing table
		administrative autonomy
			each network admin may want to control routing in its own network

		aggregate router into regions: autonomous system (AS)
		router in same AS run same routing protocol
			intra-AS routing protocol

		forwarding table configured by both intra and inter AS routing algorithm
			intra AS set entry for internal dest
			inter AS and intra AS set entry for external dest

Intra AS routing:
	IGP: Interior Gateway Protocol
		RIP: Routing Information Protocol
		OSPF: Open Shortest Path First
		IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

	RIP: distance vector algorithm
		distance vector: exchange among neighbor every 30 sec via Response message (advertisment)

		if no advertisment heard after 180sec
			neighbor/link declare dead
			routes via neighbor invalidate
			new ads sent to neighbors
			neighbor sed new ads (if table change)
			link failure info quickly propagate to entire net
			poison reverse use to prevent ping pong loop

		manage by application-level called route-d (daemon)
		ads sent in UDP packet, periodically repeat

	OSBF: link state
		carry 1 entry per neighbor router
		ads dissemninate to entire AS (via flooding)
		sent directly over IP

		security: all message authenticate
		multiple same-cost path allow (RIP only 1 path)
		for each link, multiple cost metric for different TOS
		integrate uni and multicast support
		hierarchical OSPF in large domain

		hierarchical OSPF:
			2-level hierarchy: local area, backbone
				link state ads only in area
				each node has detail area topology, only now direction (shortest path) to net in other area
			area border router
			backbone router
			boundary router

	BGP: Border Gateway Protocol: de facto standard
		TCP
		message:
			OPEN: open TCP connection to peer and authenticate sender
			UPDATE: advertise new path
			KEEPALIVE: keep connection alive in absence of UPDATE, also ACKs OPEN request
			NOTIFICATION: report error in previous message, also use to close connection

Difference between Intra and Inter AS routing:
	policy:
		inter: admin want control over how its traffic route, who route
		intra: singlel admin, no policy decision deed
	scale:
		hierarchical routing save table size, reduce update traffic
	performance:
		intra AS: can focus on performance
		inter: policy may dominate over performance

Broadcast routing:
	deliver packet from source to all other node
	source duplication is inefficient

	flooding: when node receive broadcast packet, send copy to all neighbor
		-> circle and broadcast storm
	controlled flooding: node only broadcast if it hasn't broadcast same packet before
		keep track of packet already broadcast
		RPFL reverse path forwarding:
			only forward if it arrive on shorteest path between node and src
		spanning tree:
			no redundant packet receive by any node

Multicast Routing:
	find a tree connecting routers having local multicast group member
	source base tree: one tree per source
		shortest path tree
		reverse path forwarding
	group share tree: group use 1 tree
		minimal spanning (steiner)
		center base tree