3B SE

ECE358 - Computer Networks

I will formally learn Computer Networks through this class. Though it’s in 1 year from now.

Resources

• Book: Computer Networking - A Top-down Approach, 8th Edition
• Other people’s notes
  • https://zandershah.github.io/notes/ece358/ece358.html
• http://gaia.cs.umass.edu/kurose_ross/online_lectures.htm
  • interactive version: http://gaia.cs.umass.edu/kurose_ross/lectures.php
• goated channel https://www.youtube.com/@PowerCertAnimatedVideos/featured
• http://gaia.cs.umass.edu/kurose_ross/knowledgechecks/index.php

How is data transmitted? Several mediums

• Twisted Pair
• Coaxial Cable
• Fiber Optics
• Terrestrial Radio Channels
• Satellite Radio Channels

3 most important protocols:

1. TCP
2. BGP
3. IP

Concepts

• TCP
• UDP
• IP
• Transmitter

Midterm:

• Determine packet-switching calculation p.53??
• Figure out how to compute CRC

Example - ASCII (8-bit): • character: 7-bits data, 1-bit even parity • raw BER of channel = 10^{-4} • What is the probability that a character is sent in error to the layer above when no parity bit? $1-(1-BER{)}^7$ • What is the probability that a character is sent in error to the layer above when a single-bit parity (8-bits), $1-[(1-BER{)}^8+8BER(1-BER{)}^7]$ • parity-bit gives 3 orders of magnitude improvement in a simple case (note that we apply it to characters). However it is expensive: the overhead is 1/7=14%!

Chapter 1

Nuts and bolts of the internet

Hosts = end systems Packet switches = forward data packets

• includes routers, switches

There are 3 important characteristics of a transmission system:

1. Propagation delay
2. Bandwidth/rate
3. Bit error rate

There are a few physical media through which the link can be “implemented”:

1. Twisted Pair
   • two insulated copper cables. This is used for like ethernet
2. Coaxial Cable
   • Two concentric copper cables. Enables broadband, multiple frequency channels on cable
3. Fiber Optics
   • Carries light pulses. Has low error rate over long distances. High speed operation
4. Wireless Radio (it is Half-Duplex)

How to connect end systems to edge router?

• There are residential access networks
• Institutional access networks (school, company)
• Mobile Access networks (4G/5G)

Residential access networks

1. Digital-subscriber line
2. Cable-based access

Fiber to the home.

There’s the Digital Subscriber Line.

Two competing optical technologies

• Passive Optical network (PON) 
• Active Optical Network (AON): switched Ethernet

Switching

This is a pretty important topic.

There are 3 ways:

1. Fully meshed
2. Everything connected to a central switch
3. Hierarchical network with inter-switch links

The Network Core

• mesh of interconnected routers

The network core has 2 main functions:

1. Forwarding
2. Routing

packet-switching: hosts break application-layer messages into packets

• network forwards packets from one router to the next, across links on path from source to destination
• A packet from your computer to a server might cross many many routers (and links)

There’s packet switching and circuit switching?

• We call it packet switching because the host breaks the application-layer messages into packets

Packet transmission delay = L/R

• L (bits)
• R (bits/sec)

store and forward: entire packet must arrive at router before it can be transmitted on next link

Smaller packets are nicer because you can get pipelining behavior.

• The pipelining effect: packets shouldn’t be too big, better break up a big file into small ones.

The alternative is circuit switching:

• network resources are statically divided into small pieces called circuits (once and for all)

• Circuit is a logical path established through multiple physical links and switches, connecting two endpoints for the duration of a call.

Can parts of the circuit be shared? YES!

The circuit established for a phone call is not entirely composed of dedicated, exclusive physical lines. Instead, the circuit is a combination of dedicated segments (like your home line to the central office) and shared segments.

for circuit switching, you divide into 2 things:

• FDM (frequency-division multiplexing) - divide into frequency bands
• TDM (time-division multiplexing) - divide into different time slots

Circuit switching is not super efficient because users get a dedicated bandwidth.

• circuit segment idle if not used by call

In circuit switching, why can't the bandwidth be dynamically allocated?

In circuit switching, there is no mechanism to continuously monitor and reallocate bandwidth in real-time. The design is static in nature.

In packet switching, the bandwidth is dynamically allocated. Multiple users can share the same link.

In circuit switching, each user has dedicated resources, which results in a waste of capacity when users are not fully utilizing their connections. In packet switching, users share the link capacity dynamically, allowing the network to efficiently handle many more users as long as their active usage periods do not overlap significantly.

Internet Structure

Hosts connect to Internet via access Internet Service Providers (ISPs).

There are global ISPs, since connecting ISPs to each other is not super feasible…

There are also content provider networks - these connect their data centers to the internet bypassing tier1

QoS defines the quality of service, how reliable do you want your network to be? Some metrics:

• packet loss
• Delay
• privacy
• security

It’s expensive to support.

Packet loss happens when the buffer holding queued packets fills up.

Packet delay, 4 sources:

1. Transmission
2. Nodal processing
3. Queuing
4. Propagation

Packet queuing delay is revisited: queuing delay = L * a / R

• L is packet length
• a is average packet arrival rate
• R is the link bandwidth (bit transmission rate)

If La/R ~ 0 → queuing delay is small If La/R = 1 → delay is large If La/R > 1 → more work is arriving than can be serviced!

Layers of Internet

See layers of ip. Why do you have layers?

• Explicit structure allows identification, relationship of system’s pieces
• Modularization eases maintenance

Layers of the internet protocol:

• Application Layer: support network applications
  • HTTP, IMAP, SMTP, DNS
• Transport layer: process
  • TCP and UDP
• Network layer
  • IP, routing protocols
• Link layer: data transfer between neighbouring network elements
  • Ethernet: 802.11
• physical layer
  • Bits on the wire

Chapter 2

Understand principles behind link layers.

There are 2 types of links:

1. Point-to-point
2. Point-to-multipoint

A frame encapsulates a datagram.

There’s this analogy:

• transportation analogy:
• trip from Waterloo to Lausanne
  • limo: Waterloo to YYZ
  • plane: YYZ to Geneva
  • train: Geneva to Lausanne
• tourist = datagram
• each transport leg = communication link
• transportation mode = link-layer protocol
• travel agent = routing algorithm

framing, link access (compulsory):

• encapsulate datagram into frame, adding header, trailer
• channel access if shared medium
• “MAC” addresses in frame headers identify source, destination (different from IP address!)

Framing is a common approach.

There is that one problem where your flag could appear in the payload. So you implement bit stuffing to ensure that your payload doesn’t contain the flag.

• Bit Stuffing

flag or idle pattern in data:

• if 5 successive 1s, insert 0 (bit stuffing)
• unstuff at receiver

Error detection is done at all layers (l2 link, l3 network, l4 transport)

error detection (not even compulsory):

• errors caused by signal attenuation, noise
• receiver detects errors, signals retransmission, or drops frame

error correction:

• receiver identifies and corrects bit error(s) without retransmission

Error detection is pretty complicated, the simplest is by doing parity checking.

You can also do a 2d parity check.

Then, the teacher goes through examples of how to calculate this.

Then, there’s the Cyclic Redundancy Check, which allows you to check for errors

• more powerful error-detection coding
• D: data bits
• G: bit pattern

Error correction is much harder Correction technique: correct error at receiver

• computationally expensive
• high overhead
• may be useful for real-time communication or for long, fat pipes or for very noisy channels.

Packet vs. frames?

Sending the data in frames is common.

• Wait, in chapter 1, we were talking about packets. This is lower level, it’s frames?
• It’s a 1-to-1 relationship between packets and frames

Retransmission

So if you don’t correct, you can consider retransmitting.

Stop and Wait

Stop and wait is the simplest mechanism: sender sends one packet (in a frame), then waits for receiver response.

We will need:

• acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
• negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors (sender retransmits pkt on receipt of NAK)
• maybe other things to be discovered

Performance of stop-and-wait (umm im not sure if i need to know this)

• U sender: utilization – fraction of time sender busy sending
• G: goodput – # of successful data received/sec (unit of packet/sec, bit/sec etc.)
• L: length of frame carrying data
• A: length of frame carrying ACK

Pipelined retransmission mechanisms

Go-back-N: big picture:

• Sender can have up to N unacked pkts in pipeline
• Rcvr only sends cumulative ACKs and does not keep pkts out of order (receive buffer size = 1)
  • Doesn’t keep packet if there’s a gap
• Sender has timer for oldest unacked pkts
  • If timer expires, retransmit all unacked packets

Selective Repeat: big picture

• Sender can have up to N unacked pkts in pipeline
• Rcvr keeps packets out of order, acknowledges individual frames (no more a request but a real ACK)
• Sender maintains timer for each unacked pkt • When timer expires, retransmit only unack pkt

For go-back-n

Sender

• sender: “window” of up to N, consecutive transmitted but unACKed packet
• cumulative ACK: ACK(n): ACKs all packets up to, including seq # n
  • on receiving ACK(n): move window forward to begin at n+1
• timer for oldest in-flight packet
• timeout(n): retransmit packet n and all higher seq # packets in window

When there’s a timeout, the sender sends the window out again.

ACK-only: always send ACK for correctly-received packet so far, with highest in-order seq #

• may generate duplicate ACKs
• need only remember rcv_base on receipt of out-of-order packet:
• discard (doesn’t buffer) out of order pkts
• re-ACK pkt with highest in-order seq #

Selective repeat

In selective repeat, the receiver individually acknowledges all correctly received packets and manages a received window

• buffers packets, as needed, for eventual in-order delivery to upper layer
• sender times-out/retransmits individually for unACKed packets
  • sender maintains timer for each unACKed pkt
• sender window
  • N consecutive seq#s
  • limits seq#s of sent, unACKed packets Sender and receiver Sender data from above:
• if next available seq # in window, send packet timeout(n):
• resend packet n, restart timer ACK(n) in its window:
• mark packet n as received
• if n smallest unACKed packet, advance window base to next unACKed seq #

Receiver packet $n$ in its window

• send ACK(n)
• out-of-order: buffer
• in-order: deliver (also deliver buffered, in-order packets), advance window to next not-yet-received packet packet $n$ in [rcvbase-N,rcvbase-1]
• ACK(n) otherwise:
• ignore

SN Numbering (Sequence numbering) Given N (typically $N=2^n$), we need $m>2N-1$ distinct SNs. Difficult to prove. Instead, we will show that if m=2N-1, the protocol does not work.

What is N and m here?

N represents the size of the window, and m represents the range of sequence numbers that are available.

Multiple Access Protocols

Multiple Access Mechanism

distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit communication about channel sharing must use channel itself!

• no out-of-band channel for coordination.

There are 2 broad classes:

1. scheduling via a control node (centralized)
2. random access (decentralized)
   • allow collisions
   • “recover” from collisions

The ancestor of scheduling was polling, where the master invites other nodes to transmit in turn.

Scheduling

The time is divided in time slots and there is a repeating cycle (unfortunately called a frame): in the drawing the frame is made of 6 time slots.

Which time slots are allocated to a station depend on the controller. The controller can allocate time-slots in a static or dynamic way.

In the dynamic case, the allocation information is sent through maps that are broadcast regularly (e.g., every 10 ms)

Random Access

Random access protocols This is to deal with the situation where two or more nodes want to transmit at the same time.

There is no a priori coordination among nodes.

random access MAC protocol specifies:

• the degree of politeness
• how to detect collisions
• how to recover from collisions (e.g., via delayed retransmissions)

There are 2 main random access MAC protocols that are covered in class:

1. ALOHA
2. CSMA

Slotted ALOHA assumptions:

• all L2 frames same size
• time divided into equal size slots (time to transmit 1 L2 frame)
• nodes start to transmit at slot beginning
• nodes are synchronized
• if 2 or more nodes transmit in slot, all nodes detect collision at the end of the slot (before the next slot) and all data is useless

operation:

• when node obtains fresh L2 frame, transmits in next slot and focuses on that frame till success
• if no collision: node is done with that frame and can send another one if any
• if collision: node retransmits frame in each subsequent slot with probability $p$ until success ($p=\frac{1}{e}$ from my internet research)

efficiency: long-run fraction of successful slots (many nodes, all with many frames to send)

• suppose: N nodes with many frames to send, each transmits in slot with probability p. How to choose p?
• prob that given node has success in a slot = $p(1-p{)}^{N-1}$
• prob that any node has a success = $Np(1-p{)}^{N-1}$
• max efficiency: find p* that maximizes $Np(1-p{)}^{N-1}$ (easy to show that p*=1/N)
• for many nodes, take limit of $Np\ast (1-p\ast {)}^{N-1}$ as N goes to infinity, gives:
• max efficiency = 1/e = .37
• at best: channel used for useful transmissions 37% of time!

unslotted Aloha: simpler, no synchronization

• when frame first arrives: transmit immediately
• collision probability increases with no synchronization:
  • frame sent at t0 collides with other frames sent in [t0-L/R,t0+L/R]
• If a collision occurs (when two or more stations transmit simultaneously), the users wait for a random amount of time and then retransmit.
• pure Aloha efficiency: 18%

CSMA (carrier sense multiple access) simple CSMA: listen before transmit:

• if channel sensed idle: transmit entire frame
• if channel sensed busy: defer transmission
• human analogy: don’t interrupt others!

collisions can still occur with carrier sensing:

• propagation delay means two nodes may not hear each other’s just-started transmission
• collision: entire packet transmission time wasted
• distance & propagation delay play role in determining collision probability

That’s why you have an improvement with CSMA/CD, where CD stands for collision detection.

CSMA/CD reduces the amount of time wasted in collisions

• transmission aborted on collision detection

Old-fashioned Ethernet CSMA/CD algorithm

1. NIC receives datagram from network layer, creates L2 frame
2. NIC senses channel:
   • if idle: start frame transmission.
   • if busy: wait until channel idle, then transmit
3. If NIC transmits entire frame without collision, NIC is done with frame !
4. If NIC detects another transmission while sending: abort, send jam signal
5. After aborting, NIC enters binary (exponential) backoff: it creates time-slots of 512 bit times (minimum frame size is 512 bits)
   • after m-th collision (m<16), NIC chooses K at random from $\{0,1,2,\dots ,2^m-1\}$. NIC waits K·512 bit times, returns to Step 2
   • more collisions: longer backoff interval
   • m=16 → abort sending of frame

How does the jam signal work?

The jam signal is typically 32 to 48 bits in length. These bits are transmitted to deliberately create a pattern that disrupts the normal operation of the shared medium.

T_p = max prop delay between 2 nodes in LAN t_trans = time to transmit max-size frame

efficiency = $\frac{1}{1+5T_p/t_{trans}}$

efficiency goes to 1

• as Tp goes to 0
• as ttrans goes to infinity better performance than ALOHA: and simple, cheap, decentralized!

Scheduling

• by time, frequency or both: cellular (and latest)
• polling from central site (Bluetooth)

random access

• Aloha (still in use)
• CSMA: carrier sensing
• Collision detection easy in some technologies (wire), hard in others (wireless). CSMA/CD used in Ethernet

Can you compare them?

MAC Address

MAC addresses are administered by the IEEE.

Manufacturers buys portion of MAC address space.

• 48-bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
• hexadecimal (base 16) notation
• (each “numeral” represents 4 bits)
  • e.g.: 1A-2F-BB-76-09-AD

how to determine interface’s MAC address, knowing its IP address?

• There’s an ARP table

IP/MAC address mappings for some LAN nodes.

A wants to send datagram to B

• B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address

IMPORTANT

Unlike IP addresses which are not portable (it depends on IP subnet to which node is attached), MAC addresses are, which means that we can move interface from one LAN to another.

ARP Protocol

ARP table: each node (host, router) on LAN has table

• IP/MAC address mappings for some LAN nodes: < IP address; MAC address; TTL>
• TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)

example: A wants to send datagram to B

• B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address

The routing mechanism is also super interesting.

When I go to google.com, idk the MAC address of it?? So how does this work

Because it is an IP address outside of the current network, your computer will send the traffic to the gateway (generally 192.168.1.1), and you’ll get the MAC address of the gateway (through the ARP Table). Then, the gateway will do some logic and forward whatever.

• Your machine only needs to know the MAC address of devices on the local network (like your router). Once the packet leaves your network, routers only care about IP addresses.

MAC addresses are used for local (same network) communications, while IP addresses are used for routing across different networks.

Ethernet

This is quite interesting.

When Ethernet first got started, it was a bus, which would results in lots of collisions, and each computer needed to coordinate with each other. Seems like a real pain. And then mechanisms to check collisions (ALOHA or CSMA)

bus: popular through mid 90s

• all nodes in same collision domain (can collide with each other)
• bus: coaxial cable switched
• switched: prevails today
• active link-layer 2 switch in center
• each “spoke” runs a (separate) Ethernet protocol (nodes do NOT collide with each other)

Ethernet Frame Structure

addresses: 6 byte source, destination MAC addresses

• if adapter receives frame with matching destination address, or with broadcast address (e.g., ARP frame), it passes data in frame to network layer protocol or ARP
• otherwise, adapter discards frame
• type: indicates higher layer protocol
  • mostly IP but others possible, e.g., Novell IPX, AppleTalk
  • a special value for ARP
  • used to demultiplex up at receiver CRC: cyclic redundancy check (4 bytes)
• error detected: frame is dropped

The maximum datagram size is 1500 bytes (MTU, max transmission unit).

Switch is a link-layer device: takes an active role

• stores, forwards Ethernet frames
• examines incoming frame’s MAC address, selectively forwards frame to one-or-more outgoing links, uses CSMA/CD to access each link
• transparent: hosts unaware of presence of switches
• plug-and-play, self-learning
  • switches do not need to be configured

entry:

• (MAC address of host, interface to reach host, time stamp)

• looks like a routing table!

• connectionless: no handshaking between sending and receiving NICs

• unreliable: receiving NIC doesn’t send ACKs or NAKs to sending NIC

• data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost

• Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff

Switches have multiple transmissions.

Switches vs. routers

• Routers are network-layer devices
• Switches are link-layer devices

Both have forwarding tables

• routers: compute tables using routing algorithms, IP addresses
• switches: learn forwarding table using flooding, learning, MAC addresses
  • What do they mean by flooding here?

Chapter 3

Network Layer

There are 2 planes (i remember this from Ericsson!!):

1. Data Plane
2. Control Plane

The data plane: the Internet Protocol

• IPv4: datagram format
• IPv4: addressing
• IPv4: network address translation
• middleboxes
• IPv6

What’s inside a router? →The control plane: ICMP, Routing

transport segment from sending to receiving host

• sender: encapsulates segments into datagrams, passes to link layer
• receiver: delivers segments to transport layer protocol

Network layer protocols in every Internet device: hosts, routers

What do routers do?

• examines header fields in all IP datagrams passing through it
• moves datagrams from input interfaces to output interfaces to transfer datagrams along end-end path

Network-layer functions

1. forwarding: move packets from a router’s input link to appropriate router output link: very common task (for all datagrams) done very fast (a few nanoseconds)
2. routing: network-wide process that determines route taken by packets from source to destination to fill forwarding tables (done in the background and not triggered by datagrams arrivals, time-scale is few seconds) > - routing algorithms

A modern view of the network layer breaks it down into the data plane and control plane.

Data plane:

• local, per-router function
• determines how datagram arriving on router input interface is forwarded to router output interface

Control Plane

• network-wide logic
• determines how datagram is routed among routers along end-end path from source host to destination host
• two control-plane approaches:
  1. traditional routing algorithms: implemented in routers (both planes are implemented monolithically within a router)
  2. software-defined networking (SDN): explicitly separate the two planes by implementing the control plane as a service in (remote) servers

Main difference between ipv4 and ipv6?

• ipv4 uses 32-bit address format
• ipv6 uses 128-bit address format

Ipv4 and Ipv6

• initial motivation: 32-bit IPv4 address space would be completely allocated additional motivations:
• speed processing/forwarding: 40-byte fixed length header
• enable different network-layer treatment of “flows”
• enables better mobility management

how will network operate with mixed IPv4 and IPv6 routers?

tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers (“packet within a packet”)

• tunneling used extensively in other contexts (4G/5G)

Then, we get into talking about switches.

There are three major types of switching fabrics:

1. memory
2. bus
3. interconnection network

• CRS is the carrier routing system