CSCI357 - Final (only new content)

Node

host or router

Link

channel between nodes

L2 Packet

Frame

L2’s Role

Move datagrams across some physical link to an adjacent neighbor

L2 Services

• framing

• channel access

• reliable delivery

• flow control

• error handling

• half or full duplex communication

L2 Services - framing

adds headers and trailers which signify the end of transmission. Needed in case of noise

L2 Services - channel access

if shared medium → determines who’s using in order to avoid collision.

L2 Services - flow control

prevents overflow of buffers

L2 Services - Reliable Delivery

• Also happens w/ TCP and transport layer

• Good for high error links → prevent trip to transport layer

L2 Services - err handling

• retrans on err detection

• tries to err correction to avoid retrans

What tends to cause L2 transmission errors?

Noise or attenuation

L2 Services - Half or full duplex communication

• bidirectional data flow

• Half duplex - only one host can send at a time

• Full duplex - simultaneous two-way communication

Where is L2 Implemented?

• At the router/hosts

• some sw/hw/fw in the network adaptor (NIC)

Network Sending Adaptor

• encapsulates the L3 datagram

• provides/adds L2 services

Network Receiving Adaptor

• handles services

• passes datagram to L3

Bit Errors

• This is what error detection and correction is for

• 1’s and 0’s getting corrupted in transmission

Error Detection - Parity Bit

• append 1 bit per word to have even # of 1’s

• Will be able to detect 1-bit errors in a word, but not which bit

• this is purely error detection

Error Correction - 2D Parity

• have one parity bit per row and column

• allows for detection and correction but more overhead

• detects isolated single bits

Reality of Errors

• they are bursty

• tend to not happen in isolation but in groups

Cyclic Redundancy Check (CRC)

• choose a polynomial generator G of degree n

• we are looking to find a remainder R (bit size r) from data D

1. Sender shifts the data by r bits

2. divides shifted data by G

3. adds that remainder to the shifted data

4. Recv divides whole msg by G, if 0 → valid data, corrupt if else

• can detect up to n bit error bursts

Reed-Solomon Codes

• error correction method

• k bytes → k coefficients

• k coefficients determine the polynomial, but n = k + t are provided.

• Detect up to t errors

• correct up to t/2 errors

• correct up to t erasures

Point-to-Point Link

Direct private connection between two endpoint

Broadcast Links

• anything sent on the link will go to everyone connected

• lots of simultaneous signals → interference

Collision

When a node receives multiple signals simultaneously

MAP - Distributed Algorithms

• This is the ideal vision

• All communication is done on the channel

• ideally with link rate R and M nodes → transmit at R/M

• decentralized

• simple

MAP - Time Division Multiple Access

• each node has a time frame to send during

• requires connected nodes to by synched up

• if node doesn’t have anything to send → time slot wasted

MAP - Frequency Division Multiple Access

• Allocate bands of frequency to each node

• speeds get really slow the more nodes connected

MAP - Random Access

• Just try to send at the full rate R whenever node has data

• protocol needs to specify collision detection and recovery

MAP - Slotted ALOHA

• Random Access protocol

• assumes nodes are sync’d and frames equal size

• timeslots are the size of a frame

• Just try to send during a time slot → assumes everyone knows if there’s a collision before end of slot

• if collision → retry at the next time slot with a prob of P

• easy to implement but makes a lot of assumptions and inefficient

MAP - Pure ALOHA

• just transmit whenever ready

• no need to sync

• performs even worse than slotted

Carrier Sense Multiple Access (CSMA)

• listen to channel → only send if no one is talking

• collision still possible → prop delay - if someone starts talking in the time it takes to check → collision

• smaller d_prop → smaller collision window

CSMA + CD - Wired

• only send if no one is talking

• create frame → carrier sense → send and monitory → if collision → immediately stop transmitting → send jam signal to alert others + binary exponential backoff

MAP - Polling

• Taking turn MAP

• Have central controller in charge or inviting devices to transmit

MAP - Polling - pros

• keeps non-controller devices simple

• no time lost on idle devices

• no collisions

MAP - Polling - cons

• single point of failure (controller)

• latency - need to wait for everyone to be given a chance (bad for single senders)

• overhead

MAP - Token Passing Protocol

• Have a token ring that’s required for a device to talk

• has a max transmissions before needing to pass

MAP - Token Passing Protocol - pros

• no collisions

• no need to go back to controller (little time lost on idle devices)

MAP - Token Passing Protocol - cons

• token becomes single point of failure

• overhead from token passing

MAP types

• channel partitioning: time, frequency, code

• random access: handle collisions

• taking turns: decides who talks

L2 addressing

• MAC/LAN/Ethernet addrs

• not hierarchical

• set in the hardware/firmware

• addrs are unique within LAN

How to send within LAN?

given IP addr, need MAC addr → ARP

Address Resolution Protocol (ARP)

• protocol used for facilitating communication w/in LAN

• each node in LAN as an ARP table to store IP to MAC mappings

ARP - process

• if node’s ARP table doesn’t have entry →

• broadcast ARP query →

• target node recv broadcast & replies →

• cache reply info

ARP - table entries

(IP, MAC, TTL)

ARP - Broadcast ARP

used when a node’s ARP table doesn’t have IP MAC mapping

contains:

• TO: FF:FF:...:FF

• FROM: src MAC

• Who has: target IP

• Tell: src IP

How to send outside LAN?

• Initial sender knows IP addr of dest and IP addr of next hop to B

1. Create datagram

   1. src IP

   2. dest IP

2. Frame it

   1. src MAC

   2. dst MAC of next hop

3. Transmit

4. Rcvr removes datagram and does forwarding lookup → encapsulates in new frame

LAN topology - Bus

• multiple nodes one wire

• any node connected to same wire → collision domain

• popular in 90s

Collision Domain

• arises because of Bus LAN topology

• any node connected to the same wire whose transmissions can collide

LAN Topology - Star

• central switch

• one wire per node from central switch

Ethernet Frames

Ethernet Frame - type field

This will typically indicate IPv4, IPv6, ARP, or packet length

Ethernet Frame - Preamble

• 8 bytes of alternating 10 w/ 1 on each end

• wakes up the recv and syncs clock rates

Ethernet properties

• Connectionless: no ACKs or handshakes

• Unreliable: if corruption → drop pack, let L3 handle

Ethernet Hub

• more like a repeater

• makes star topology possible by broadcasting incoming frames to all ports

• generates a lot of traffic

Ethernet switch

• stores and forwards ethernet frames

• reads L2 hdr and forwards selectively to output link using CSMA/CD if necessary

• self-learning: observes traffic to build switching table, if dest ever unknown → flood

Ethernet switch vs routers

• both store and forward and use forwarding tables

• differ

• L2 vs L3 hdrs

• flooding/learning/MAC addrs vs routing algs

Attack models

• Goal of these attacks is to recover the key

• if you have the key → you can decrypt everything

Cipher-text only Attack

• Attack model

• only have the cipher c

• just use statistical analysis to break (look for common letters etc.)

• most difficult

Known-plaintext Attack

• attack model

• if you have both c and m

• this can happen if attacker knows data is a pdf/known standard for what the message starts with → can reverse engineer

Chosen Plaintext attack

• attack model

• “encryption oracle”

• when attacker has access to feed m into encryptor → test for patterns to learn key structure

Side-channel attack - Timing Attack

• attack the hardware rather than deducing keys/encryptor

• CPU takes diff amount of time to measure 0 v 1 → time the CPU to guess the bits