Chapter 5 - Link Layer

Link layer: Intro
	hosts and routers are nodes
	communication channels connect adjacent nodes along communication path: links
		wired links
		wireless links
		LANs
	packet: frame, encapsulate datagram

	transfer datagram from 1 node to adjacent node over a links

datagram tranfer by different link protocol over different link
each link protocol provide different service

Service:
	framing, link access
		encapsulate datagram into frame
		channel access if shared medium
		MAC address used in frame header to identify src, dst
	reliable delivery between adjacent nodes:
	flow control
	error detection
	error correction
	half-duplex and full-duplex

implement in adaptor (network interface card - NIC)
	attach into host system buses
	combination of hardware, software, firmware

sending side:
	encapsulate
	add error checking bit, rdt, flow control
receiving side:
	look for errors, rdt, flow control
	extract datagram, pass to upper layer

Error detection:
	EDC: error detection correction bits (redundancy)
		not 100% reliable
		may miss some errors (rarely)
		larger EDC field -> better detection and correction
	parity checking:
		single bit parity
		2-dimensional bit parity

	internet checksum
	checksumming: cyclic redundancy check (CRC)

Multiple Access:
	point-to-point:
		PPP for dial-up access
		point-to-point link between Ethernet switch and host
	broadcast (shared wire or medium)
		old-fashioned Ethernet
		upstream HFC
		802.11 wireless LAN

	single shared broadcast channel
	2 or more simultaneous transmissions by nodes: interference
		collision if node receives 2 or more signals at the same time

	multiple access protocol
		determine how node share channel, when node can transmit
		communication about channel sharing must use channel itself
			no out-of-band channel for coordination

	Ideal Multiple Access Protocol:
		broadcast channel of rate R bps
		when 1 node transmit, it send at rate R
		when M nodes transmit, send at average rate R/MAC
		full decentralized
			no special node to coordinate transmissions
			no sync of clock, slot
		simple

	MAC protocol:
		channel partitioning
			divide into smaller pieces
			allocate piece to node for exclusive use
		random access
			channel not divided, allow collision
			recover from collision
		taking turn
			node take turn
			node with more to send can take longer turn

		TDMA: time division multiple access
			access to channel in rounds
			each station get fixed length slot
			unused slots go idle
		FDMA: frequency division multiple access
			channel spectrum divide into frequency band
			each station assign fixed frequency band
			unused tramission time in frequency band go idle

		Random Access Protocol:
			node have packet to send -> transmit full channel data rate R
			no coordination
			specify:
				how to detect collision
				how to recover from collision
			slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA

		slotted ALOHA
			assume:
				frame same size
				time divided into equal size slots
				node transmit only slot beginning
				node are sync
				if 2 or more nodes transmit in slot, all detect collision
			operation:
				when node obtain fresh frame, transmit in next slot
				if no collision, send new frame in next slot
				if collision, retransmit frame in each subsequent slot with probability p until success
			pros:
				transmit at full rate of channel
				highly decentralized: slot in node need to be in sync
				simple
			cons:
				collision, wasting slot
				idle slot
				may detect collision in less than time to transmit packet
				clock sync
			max efficiency: 1/e = 0.37
			channel used for useful transimissions 37% of time

		pure (unslotted) ALOHA:
			simple, no sync
			when frame arrive, transmit immediately
			collision probability increase
			max efficiency: 1/(2e) = 0.18
			-> worse than slotted ALOHA

		CSMA (Carrier Sense Multiple Access)
			listen before transmit
			if channel sensed idle -> transmit entire frame
			if channel sensed busy -> defer transmissions

			CSMA collision:
				can still occur:
					propagation delay -> may not hear other transmision
				collsion:
					entire packet transmission time wasted

		CSMA/CD (CSMA / Collision Detection)
			carrier sensing, deferral as in CSMA
			collision detect in short time
			collide transmision aborted, reduce channel wastage
			collision detection:
				easy in wired LANs:
					measure signal strength
					compare transmitted
					receive signals
				difficult in wireless LANs:
					received signal strength
					overwhelm by local transmision strength

		channel partitioning:
			channel share efficiently and fairly at high load
			inefficient at low load: delay in channel access, low bandwidth
		random access:
			efficient at low load
			high load: collision overhead

		taking turn MAC protocols:
			polling:
				master node invite slave node to transmit in turn
				use with slave devices
				concern:
					polling overhead
					latency
					single point of failure (master)
			token passing:
				control token passed from 1 node to next sequentially
				token message
				concern:
					token overhead
					latency
					single point of failure (token)
			bluetooth, FDDI, IBM Token Ring

MAC Addr and ARP:
	MAC (LAN or physical or Ethernet) address
		get frame from 1 interface to another physically connected interface (same network)
		48 bit (most LANs)
		burned in NIC ROM, sometimes software settable

		allocation administered by IEEE
		manufacturer buys portion of MAC address space
		MAC flat addr -> portability
			can move LAN card from 1 LAN to another
		IP hierarchical addr not portable
			depend on IP subnet to which node is attached

	ARP: Addr Resolution Protocol
		Each IP node on LAN has ARP table
		ARP table: IP/MAC addr mapping for some LAN nodes
			TTL (time to live): time after which addr mapping will be forgotten (typically 20 min)

		A want to send to B, B's MAC addr not in A's ARP table
		A broadcast ARP query packet, contain B's IP addr
			dst MAC addr = FF-FF-FF-FF-FF-FF
			all machines on LAN receive ARP query
		B receive ARP packet, reply to A with B's MAC addr
			frame sent to A's MAC addr (unicast)
		A cache IP-to-MAC addr pair in ARP table until time out
			soft state: info time out unless refreshed
		ARP is plug-and-play
			node create their ARP table without intervention from net admin

	send datagram from A to B via R (assume A know B IP addr)
		create IP datagram with src A, dest B
		A use ARP to get R MAC addr
		A create link-layer frame with R MAC addr as dst, frame contain A-to-B IP datagram
		A NIC send frame
		R NIC receive frame
		R remove IP datagram from Ethernet frame, see its destined to B
		R use ARP to get B MAC addr
		R create frame contain A-to-B IP datagram send to B

Ethernet
	dominant wired LAN technology
		cheap for NIC
		first widely used LAN technology
		simpler, cheaper than token LANs and ATM
		kept up with speed race: 10Mbps - 10Gbps

	bus topology -> all node in same collision domain
	star topology
		active switch in center
		each run a seperate Ethernet protocol (no collide with other)

	Frame Structure:
		sending adapter encapsulate IP datagram (or other network layer protocol packet) in Ethernet frame

		preamble -> dest addr -> source addr -> type -> data -> CRC

		Preamble
			7 byte with pattern 10101010 fllowed by 1 onyte with pattern 10101011
			used to sync receiver, sender clock rates
		Addr: 6 bytes
			if match dst addr, or with broadcast addr, pass data in frame to network layer protocol
			otherwise, discard
		Type: indicate higher layer protocol (mostly IP, Novell IPX, AppleTalk)
		CRC: checked at receiver, if error detect, drop

	connectionless: no handshaking between send and receive
	unreliable: receive does not send ACKs or NACKs to send
		can have gap (missing datagram)
		gap will be filled if app using TCP
	MAC protocol: unslotted CSMA/CD

	Ethernet CSMA/CD
		1. NIC receive datagram from network layer, create frame
		2. if NIC sense channel idle, start frame tramission
		   if busy, wait until idle, then transmit
		3. if transmit entire frame without detect another transmision, done
		4. if detect another transmision, abort and send jam signal
		5. after aborting, enter exponential backoff
		   after mth collision, NIC choose K at random from {0, 1, 2, ..., 2^m - 1}. NIC wait K.512 bit times, return to 2

		Jam signal: make sure all other transmitter aware of collision (48 bit)
		Bit time: 1 microsec for 10Mbps Ethernet
					K = 1023, wait time is about 50 msec
		Exponential backoff:
			adapt retransmission attempt to estimated current load
				heavy load: random wait will be longer

		better performance than ALOHA
		simple, cheap, decentralized

		efficiency = 1 / (1 + 5(t_prop / t_trans))
			t_prop: max prop delay between 2 nodes in LAN
			t_trans: time to transmit max-size frame
			efficiency -> 1
				t_prop -> 0, t_trans -> infinitive

	802.3 Ethernet Standards:
		many different Ethernet standard
			common MAC protocol and frame format
			different speed
			different physical layer media: fiber, cable
				copper (twister pair) physical layer
				fiber physical layer

Manchester encoding:
	used in 10BaseT
	each bit has a transition
	allow clock in send and receive node to sync to each other
		no need for a centralized, clobal clock among node
	physical layer stuff

Hub:
	physical layer (dumb) repeater
		bit coming in one link, go out all other link at same rate
		all node connected to hub can collide with other
		no frame buffer
		no CSMA/CD at hub: host NICs detect collision

Switch:
	link layer device: smarter than hubs, take active role
		store and forward Ethernet frame
		examine incoming frame MAC addr
		selectively forward frame to 1-or-more outgoing links
		use CSMA/CD to access segment
	transparent
		host unaware of presence of switches
	plug and play, self-learning
		no need to be configure

	allow multiple simultaneous transmission
		host have dedicated, direct connection to switch
		switch buffer packets
		Ethernet protocol use on each incoming link, no collision
		full-duplex
		switch simulatenously, without collision

	each switch has a switch table (MAC addr of host, interface to reach host, time stamp)

	switch learn which hosts can be reached through which interface
		when frame receive, switch learn location of sender, incoming LAN segment
		record sender/location pair in switch table

	switch frame filtering/forwarding:
		when frame received:
			record link associated with send host
			index switch table use MAC dst addr
			if entry found for dest:
				if dst on segment from which frame arrived
					drop
				else forward the frame on interface indicated
			else flood (forward on all but the interface on which the frame arrived)

		frame dst unknown: flood
		dst A location known: selective send

		switch can be connected together

	switch vs. router
		store-and-forward device
			router: network layer device
			switch: link layer device
		router maintain routing table, implement routing algorithm
		swithc maintain switch table, implement filtering, learning algorithm

VLAN: Virtual local area network
	switch support VLAN can be configured to define multiple virtual LANs over single physical LAN infrastructure

	port-based VLAN: switch ports grouped (by switch managment software) so that single physical switch
		operate as multiple virtual switch
		traffic isolation
		dynamic membership
		forwarding between VLANs
		trunk port: carry frame between VLANs define over multiple physical switches:
			802.1 can't be forward within VLAN between switch
			802.1Q add/remove additional header for frame forward between trunk port

	802.1 frame:
		preamble -> dst addr -> src addr -> type -> data -> CRC
	802.1Q frame:
		preamble -> dst addr -> src addr -> tag protocol identifier -> tag control info -> type -> data -> CRC

Point-to-point data link control
	1 sender, 1 receiver, 1 link: easier than broadcast link
		no media access control
		no need for explicit MAC addr
	protocol:
		PPP (point-to-point protocol)
		HDLC (high level data link control)

PPP:
	packet framing: encapsulation of network layer datagram
	bit transparency
	error detection (no correction)
	connection liveness
	network layer addr negotiation

	data frame:
		flag -> addr -> control -> protocol -> info ->> check
		data transparency requirement:
			data field must be allowed to include flag pattern 01111110

	before exchange data:
		configure PPP link (max frame length, authentication)
		learn/configure network

Virtualization:
	Internetwork Architecture:
		2 layers of address: internetwork and local network
		new layer (IP) make everything homogeneous at internetwork layer
		underlying locla network technology:
			cable, satellite, ATM, MPLS
		invisible at internetwork layer

	ATM and MPLS:
		seperate network in their own right
			different service model, addressing, routing from Internet
		viewed by internet as logical link connecting IP router

	ATM: Asynchronous Transfer Mode
		integrated, end-end transport of cary voice, video, data
		packet switching using virtual circuit

	MPLS: Multiprotocol label switching
		speed up IP forwarding by using fixed length label (instead of IP addr) to do forwarding
			IP datagram still keep IP addr
			borrow idea from Virtual Circuit (VC)