CS432 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Booklet of Network Modeling and Simulation

📖 Overview: This lecture, extracted from the course booklet for CS432 (Network Modeling and Simulation), introduces the fundamental structure and expectations of the course. It outlines the instructor, lecturing style, and evaluation criteria, providing students with a clear roadmap for the semester. Understanding this overview is critical for academic planning and success in the simulation-related modules.

🗂️ Topics Covered

This lecture covers the course code and credit hours, the instructor’s identity (Dr. Ali Hammad Akbar), the short-duration video lecturing style (5-7 minutes each), and the comprehensive evaluation scheme including quizzes, assignments, simulation modules, and the mid-term and final examinations.

📝 Lecture Summary

[No explicit section headings — the lecture is structured as a course overview booklet]

The lecture begins by presenting the course code CS432 and specifying the credit hours as 3+0, indicating three hours of theory without a separate lab. The instructor is identified as Dr. Ali Hammad Akbar, who employs a lecturing style consisting of video lectures of short duration, typically 5–7 minutes each, designed to facilitate focused learning.

The evaluation section details the assessment components: quizzes, assignments, and simulation modules (practical modeling tasks), culminating in a mid-term and final examination. This structure emphasizes both theoretical understanding and practical application through simulation work.

💡 Why this matters: This overview establishes the course’s blended learning approach, combining concise video content with hands-on simulation, and clarifies how student performance will be measured across multiple components.

⭐ Key Takeaways

The most critical points for a student to remember are: the course code is CS432 with 3+0 credit hours; the instructor is Dr. Ali Hammad Akbar; all lectures are delivered as short (5–7 minute) videos; evaluation includes quizzes, assignments, simulation modules, plus a mid-term and final exam; and this is not a lab-based course (0 in credits). Understanding this structure allows students to allocate study time appropriately for both theory and simulation work.

🧠 Quick Revision Questions

1. What is the course code for Network Modeling and Simulation?
2. Who is the instructor for this course?
3. What is the typical duration of each video lecture?
4. What are the four main components of the evaluation scheme?
5. What do the “3+0” credit hours indicate about the lab component?

📘 Lecture 2 — The complex world of networks

📖 Overview: This lecture introduces the fundamental concepts of Network Modeling and Simulation (NeMS), explains why it is needed in the rapidly evolving technology landscape, and provides a comprehensive guide to the OMNeT++ simulation framework. It covers everything from basic simulation principles to practical implementation using OMNeT++, including the TicToc tutorial and INET framework.

🗂️ Topics Covered

The lecture covers the need for NeMS in the context of evolving communications systems, user demands, and service provider expansion. It then defines what NeMS is, explains the simulation building process, types of simulations, when to simulate, common mistakes, and simulation inaccuracies. The second half introduces OMNeT++ in detail, covering its architecture, NED language, configuration, the TicToc tutorial series, simulation analysis, and the INET framework for modeling real-world protocols.

📝 Lecture Summary

Need for NeMS

Network Modeling and Simulation (NeMS) is motivated by the rapidly evolving technology landscape which includes fast-changing communications systems, high-performance user demands, and service providers expanding their network infrastructure. Network researchers face a "protocol war" developing new techniques, while equipment vendors release increasingly complex devices. The approaches to satisfy these needs include prototyping & empirical testing, trial field deployment, Modeling and Simulation (M&S), and analysis — ordered by decreasing costs but increasing abstraction.

What is NeMS?

Simulation is the imitation of behavior of a real-world system or computational re-enactment according to rules described in a model. Modeling is a step that precedes simulations; together they form an iterative process approximating real-world systems. A model is the logical representation of a complex entity, system, phenomena, or process. Computer simulation is the execution of computer software that reproduces behavior with a certain degree of accuracy to provide visual insight. Formally, simulations are pieces of computer software that implement algorithms, take inputs, and give outputs.

🔑 Definition — Model: The logical representation of a complex entity, system, phenomena, or a process. In communications, it could be analytical representation, mathematical form as a state machine, or closed/approximate form.

Model definitions can be descriptive, analytical, mathematical, or algorithmic. Computer models can be stochastic vs deterministic, continuous vs discrete, steady state vs dynamic, local or distributed, linear or nonlinear, and open or closed. It is important to model only what you understand and no more, so that it is neither underdefined nor overdefined.

Simulation Building Process

Consider a one-hop communication scenario between two wireless notebooks connected through a WiFi AP. The simulation entities include wireless computers and their packets (multiple instances), WiFi AP (single instance), and a traffic generator (single instance). The states include WiFi AP (idle or busy). Events include wireless computer creation, packet generation, and wireless AP activity. Queues schedule events and contain frames waiting in output queues. Randomizations include random realizations of packet lengths, number of frames, number of computers, BER (and PER), and packet drop ratio. Distributions include Uniform and Gaussian.

How Does The Simulation Run?

The simulation executes these steps: inputs are created/initialized, events of transmission, reception, and noise occur, randomness causes queues to behave and err, packet successes/failures are recorded, and simulation logs are compiled and presented as output in desirable formats.

Components of a Simulator

A simulator consists of: a self-contained program, event queue, simulation clock, state variables, event routines, input routine, report generation routine, initialization routine, and main program.

Types of Simulations

The main types include Monte Carlo simulation, trace driven, discrete events, and continuous events.

When to Simulate

Simulate when: the analytical model is not feasible (too complex), not possible (too simple), or to verify analysis. Otherwise, simulations are unnecessary.

When Not to Simulate

Do not simulate when: an analytical model gives a good enough representation, simulation takes months, is expensive, or is non-scalable.

General Mistakes

Common mistakes include: inappropriate levels of details, improper programming language selection, unverified models, improper initial conditions, short run times, poor random number generators, inadequate time estimates, no achievable goals, incomplete mix of essential skills, inadequate user participation, and inability to manage simulation projects.

Inappropriate levels of details means including only what is relevant; too fine simulations are computationally heavy with many interdependent parameters. Improper programming language depends on scope and type, considering object-oriented vs procedural, interpreted vs compiled. Unverified models can produce wrong or misleading results; modular verification is a must. Improper initial conditions that are not steady state can yield surprisingly wrong results and may never converge. Short run times have strong dependence on initial conditions and may not achieve true steady state. Poor random number generators lacking pseudo-random sequences lead to predictability; wrong seed values can cause inadvertent correlation between processes.

Simulation Inaccuracies

Two key sources: over-reliance on link budget methods for abstraction (link budget losses are overly static, fair for steady state but not dynamic analysis) and overly simplistic modeling of radio layers (lowest layer often ignored, no bit-level BER and delay, leading to wrong results in highly dynamic use cases).

Development Process

The development process consists of: problem formulation (identify controllable and uncontrollable inputs), data collection and analysis (what to collect, how much, cost-accuracy tradeoff), simulation development (codify), model validation, verification, and calibration, "what-if" analysis (performance measures with different inputs), and sensitivity analysis (relative importance of parameters).

🔑 Definition — Validation: "Is it the right system?" — Emulates real phenomenon. 🔑 Definition — Verification: "Are we building the system right?" — Implementation must correspond to the model. 🔑 Definition — Calibration: Parameter estimation, tweaking/tuning to ensure simulated data follows real data.

Recommended Text and References

NeMS covers well-known mathematical models, equations, forms, widely used simulation tools, and code reusability. It does not cover mathematical derivations from scratch or programming dexterity. Key references include Mohsen Guizani et al. (2010), Jack Burbank et al. (2011), and John A. Sokolowski & Catherine M. Banks (2010).

Introduction to OMNET++

OMNeT++ stands for Objective Modular Network Testbed in C++. It consists of a simulation kernel and component-based simulation library. It is a framework, not a simulator, designed to create and simulate any network. OMNeT++ comes with an Eclipse-based Simulation IDE.

Compile & Install

On Windows, compile by entering the OMNeT++ folder and running Mingwenv.cmd. In the terminal, enter ./configure then make. Debug mode does not optimize, allows accurate breakpoints and step-through. Release mode enables optimizations and generates instructions without debug data.

Design of OMNET++

The model consists of modules that communicate with message passing. Modules are C++ files implementing simulation class library running in simulation kernel. Simple modules are active modules; compound modules group simple modules. Modules communicate through gates (connections) — directly between modules or through intermediaries. Channels are connection types with specific properties. A message is a tuple (time stamp, arbitrary data, ...). A network is a compound module with no external gates. Module parameters pass configuration data to simple modules (string, numeric, boolean, constants, random numbers).

Internal Architecture of OMNET++

Model Component Library consists of compiled simple and compound modules. Simulation Kernel & SIM Class Library instantiates modules and builds concrete simulation, covering common tasks like random number generation, queues, messages, and routing. Envir, Cmdenv, and Tkenv Libraries define where input data comes from, where results go, debugging output, and control simulation execution.

NED Language

NED (Network Description Language) creates network topologies in OMNeT++. Typical ingredients include network definitions, compound module definitions, and simple module declarations. NED supports inheritance (modules and channels can be subclassed) and interface instantiation (module and channel interfaces can be placeholders for concrete types determined at runtime). Packages address name clashes between models.

Configuring OMNET++ Simulations

Separation of model and experiments is good practice: model topology (NED file, MSG file) and model behavior (C++ code) are separate. INI files (omnet.ini) provide a mechanism to specify run-to-run variables. The INI file is an ASCII text file consisting of key-value pairs.

Building Simulation Programs

Using GUI Project Builder or Mingwenv: with source files (*.ned, *.msg, *.cc, *.h) in a directory, change to that directory and type $ opp_makemake then $ make.

Running Simulations

The IDE supports single runs, batch runs, run numbers, graphical mode (Tkenv), command mode (Cmdenv), simulation configuration, recording event logs, and debug support.

Tkenv is a graphical runtime interface providing network visualization, message flow animation, log of message flow, display of textual module logs, inspectors, visualization of statistics, and event log recording.

Organizing and Performing Experiments

Experiments must be: repeatable (fellow researcher can repeat), unbiased (results not specific to scenario), rigorous (scenarios truly representative), and statistically sound (don't violate mathematical principles).

Terminology hierarchy: Model (executable, invariant) → Study (one or more experiments) → Experiment (exploration of parameter space) → Measurement (set of simulation runs with same parameters but different seeds) → Replication (one repetition) → Run (one instance).

Event Log Tables

An event log file contains tabulated log of messages sent during simulation. Control includes amount of data recorded, start/stop time, and which modules to include. Set record-eventlog = true in INI file.

Sequence Charts display event log files graphically, helping focus on causes and consequences of events/messages. The Timeline maps simulation time onto the horizontal axis in various ways: linear, event number, step, or nonlinear.

TicToc Tutorial

The tutorial walks through building a simulation from basic two-node communication to complex networks with statistics collection:

• TicToc with 2-nodes: Two nodes (Tic and Toc), one initializes by sending a message, each node sends it back upon receipt
• Add State Variables: Add a counter, delete message after 10 exchanges
• Adding parameters: Make count a user-defined parameter, add boolean parameter for initialization
• Using Inheritance: Create base module, derive Tic and Toc with different parameter values
• Modeling processing delay: Use timer to send self-message for processing delay
• Random numbers: Introduce random packet loss and random delay
• Timeout, cancelling timers: Implement stop-and-wait protocol
• Retransmitting same message: Keep a copy of the original message for retransmission
• More than 2 nodes: Create multiple tic modules connected in a network
• Channels & inner type definitions: Improve connection section with typed channels
• Using two-way connections: Reduce coding by using inout gates instead of separate in and out
• Defining our message class: Add destination address to message
• Displaying packets sent/received: Track and display counts at each node
• Adding statistics collection: Collect hop count statistics (average, max, min)

Analyzing Results

Result analysis is done using Analysis File (.anf) which automates loading, filtering, and transforming data. Datasets describe input data, processing applied, and charts. Compute Vectors and Compute Scalars nodes compute new values from other statistics.

Simulation Models and INET

OMNeT++ is a framework that allows other simulation frameworks to be created and simulated. Simulation models implement protocols. Well-known types include:

• INET Framework: Standard protocol model library with TCP, UDP, IPv4, IPv6, OSPF, BGP, Ethernet, 802.11, etc.
• OverSim: Overlay and P2P network simulation (Chord, Kademlia, Pastry, GIA)
• Veins: Inter-Vehicular Communication framework
• INETMANET: Fork of INET for mobile ad-hoc networks
• MIXIM: For mobile wireless, fixed wireless, WSNs, BANs, VANs, ad-hoc networks
• Castalia: For networks of low-power embedded devices

Top-down Approach to Modelling and Simulation

The top-down approach involves phased roll-out of model-simulate cycle iteratively. Design goodness (QoE — Quality of Experience) is user-centric.

QoE—Usability

Usability (Ub) is the ease of use with which network users can access the network and services. Ub ∝ 1/Ue (use effort). Usability is expressed as a function of network devices; assessment of overall usability must be based on performance of hubs/switches and routers/gateways.

QoE—Scalability

Scalability refers to the ability to grow (or add) factors like number of applications, sites, users, servers. Efficiency decreases with increasing factors. Execution time varies with problem size.

📐 Formula — Relative Efficiency: E_Relative = T₁ ÷ (No. of hosts × T_{No of hosts}) 📐 Formula — Relative Speed-up: S_Relative = No. of hosts × E₁ 📐 Formula — Execution Time: Time_Execution = T_Compute + T_Comm + T_Idle 📐 Formula — Message Time: T_msg = t_s + t_wL

QoE—Expanding Access to Data

Metcalfe's Law states that the community value of a network grows as the square of the number of its users. 📐 Formula — Metcalfe's Law: n(n-1)/2 or O(n²) connections between "n" nodes

QoE—Constraints on Scalability

Maximum scaled network is given by MinMax decision rule: Min(N_max, O_max, M_max, S_max). The strength of the chain is determined by the weakest link.

QoE—Availability

Availability is the degree to which a system, subsystem, or equipment is in a specified operable and committable state. It is measured as percent uptime per year/month/week/day to total time. Applications may require different levels (real-time vs non-real time). Availability differs from reliability (ability to complete function accurately), capacity, redundancy, and resiliency.

QoE—Disaster Recovery

The question is how to allocate redundancy to IT functions to maximize survivability while keeping cost under budget. An IT function can be implemented by multiple IT assets; it fails against disaster only when all selected solutions fail simultaneously.

QoE—Specifying Requirements

Availability measured as percentage per annum (99.70% = 30 mins downtime, 99.95% = 5 mins downtime), in calendar year context, or in spurts.

QoE—Five Nines Availability

99.999% availability means 5 minutes downtime per year, which might require triple redundancy (one active, one hot standby, one in standby/maintenance).

QoE—Cost of Downtime

40% of companies that shut down for three days failed within 36 months. Step-wise approach: identify business continuity components (people, property, systems, data), define what you protect, prioritize business functions, classify outage types, calculate cost. 📐 Formula: Frequency × Duration × Hourly Cost = Lost Profits

QoE—MTBF AND MTTR

MTBF (Mean Time Between Failure) and MTTR (Mean Time To Repair) are used to calculate availability. 📐 Formula — Availability: Availability = MTBF/(MTBF + MTTR) Example: 4,000/4,001 = 99.98% availability

QoE—Network Performance

An overall working, composite metric that is end-to-end. Performance can be modeled, simulated, and measured.

QoE—Optimum Network Utilization

Selection of the best element with regard to some criteria. Typical value is 70%; exceeding this results in performance degradation. WAN link utilization is more crucial than LAN.

QoE—Throughput

Throughput = Goodput + Badput (quantity of error-free data transmitted per second). Erroneous transmissions are futile. Device throughput depends on packet size (TCP/IP: packets per second, ATM: cells per second). Cisco claims 400 million pps for Catalyst 6500 switch.

QoE—Application Layer Throughput

Application layer throughput = goodput + badput. Badput is contributed by retransmissions and headers. 📐 Formula — Fraction of packets that collided/lost: Fc = C/N or Fc = L/N

Factors affecting goodput include end-to-end error rates, protocol functions, protocol parameters, device pps rate, lost packets, workstation/server performance (disk access, caching, device driver, bus, CPU, memory, OS, application).

QoE—Accuracy

Data sent and received should be the same. Factors include packet reordering, power surges, impedance mismatch, poor connections, failing devices, noise. 📐 Formula — Accuracy: Accuracy = [(Real value – Error) / Real value] × 100

📐 Formula — Frequency-weighted Accuracy: A = 1 - [Σ_i freq(E_i) × |real(E_i) - sim(E_i)| / real(E_i)] / Σ_i freq(E_i)

QoE—Efficiency

Factors include access protocols and frame size. If scale capacity more slowly than throughput while holding response time constant, channel efficiency increases.

📐 Formula — Average Efficiency of Network G: E(G) = [1/n(n-1)] × Σ_i≠j∈G [1/d(i,j)] Where n = total nodes, d(i,j) = shortest path between node i and j.

QoE—Delay and Jitter

Sources of packet delay include processing delay, queuing delay, transmission delay, and propagation delay. Jitter is the amount of time average delay varies. Voice, video, and audio are intolerant of delay variation.

📐 Formula — Queue Depth: Queue depth = Utilization/(1 - Utilization)

Acceptable jitter variation is 1-2% of the delay. Delay jitter bounds maximum difference in total delay of different packets (for interactive communication). Rate jitter bounds difference in packet delivery rates (for real-time applications like video broadcast).

QoE—Response Time

Amount of time between request and response. Measurement points include user at client, client host, network, and server. Response time analysis uses ceiling function for maximum number of pre-emptions.

QoE—Security

Protection of information systems from threat, avoiding disruption and misdirection. Trusted Computing Base is the set of all critical hardware, firmware, and software components. Bell-Lapadula Model uses subjects (users) and predicates (devices/data as objects) with process algebra.

QoE—Reconnaissance Attacks

Intruder engages with targeted system to gather vulnerability information. Types include active reconnaissance (port scanning) and passive reconnaissance (sniffing, war driving, war dialing).

📐 Formula — Targeted Threat Index: TTI = Method × Implementation

QoE—Security Requirements

Includes confidentiality, integrity, authorization, authenticity, availability, and encryption. Common Vulnerability Scoring System provides repeatable quantitative scores.

QoE—Manageability

Level of human effort required for deployment, configuration, upgrading, tuning, backup, failure recovery.

📐 Formula — Manageability Metric: M = 1 / [Σ_i (Time_i × Steps_i)]

QoE—DoS Attack

Denial of Service attack makes resources unavailable temporarily or indefinitely. Uses TCP SYN flooding or server crashing. 📐 Formula — Attack Success Probability: P = 1 - (1 - 1/Q)ⁿ Where Q = queue depth, n = attack packets.

Making Network Design Tradeoffs

Balance between desirable and incompatible features. Example: through put vs fairness, implemented through weighted scheduling. Can be modeled as a knapsack problem.

Problem Set 1 — Effect of Topology Factors, Routing Protocols, Deployment/Protocol Behaviors, Queuing Behaviors, Understanding Network Design

Practice problems include calculating total data rate, application load, routing packet bit rate, data center location, data rates, firewall router placement, broadcast impact, and queuing behavior calculations.

Simulate FTP Scenario

Factors affecting goodput for FTP include end-to-end error rates, protocol functions, parameters, device pps rate, workstation/server performance factors. Implementation in INET uses BulkTransfer example.

Simulating DoS Attack

Modeling includes configuring "Ping of Death" attack with parameters for packet size, send interval, hop limit, count, start/stop time.

Application Layer Roll-out for M&S

RTP (Real-time Transport Protocol) delivers audio/video over IP networks. Inet provides RTPHost model for simulation.

Client Server Architectures

One known server, always-on, permanent IP address. 📐 Formula — Distribution Time (Client-Server): D_cs = max{NF/u_s, F/d_min}

Web Server Modeling

Handles multiple HTTP requests. Characterized by buffer size per client, number of clients, file size, processing time, timeout.

HTTP Modeling

Non-Persistent Connections: Requires 2 RTTs per object. Total time = N×2RTT + N×TransmitTime. Persistent Connections: Requires 1 RTT per object. Total time = (N+1)×RTT + N×TransmitTime.

Cache Response Time

Cache reduces response time and traffic on access link. Example: with 40% hit rate, utilization reduced from 100% to 60%, average delay improved from 2 sec + minutes to approximately 1.4 secs.

FTP Efficiency

Computational efficiency measured as: TCPU = Total CPU seconds, ICPU = Idle CPU seconds, with MIPS rating and transfer rate.

SMTP Scalability

Mail delivery time must be normalized when comparing at different traffic volumes using relative efficiency and speed-up formulas (same as for scalability).

DNS Load Distribution & Loss

Health metrics include: Incoming Bandwidth Consumption (IBC) (Mbit/s), Incoming Traffic Variation (ITV), Traffic Tolerance (TT) (RTT in seconds), DNS Requests per Second (DNSR), Rate of Repeated Queries (RRQ).

Peer to Peer Scalability

No always-on server, peers directly communicate. 📐 Formula — Distribution Time (P2P): D_P2P = max{F/u_s, F/d_min, NF/(u_s + Σu_i)}

Torrents Efficiency

Factors include heterogeneous upload capacity, neighbor selection mechanisms, geographical distribution, downloading rates, peer selection policy.

Reliability of Circular DHT

Redundancy handles failures. Cost of reliability includes leaf-set keepalive messages every T seconds (2 messages for probe and response) and routing table probes every T_rt.

Problem Set 2 — Network Latencies, HTTP Performance, P2P Protocols, User Activity Monitoring

Practice problems include caching response time calculation, HTTP connection timing, DHT successor state updates, and probability calculations for user activity.

Simulate HTTP Persistence

HTTP 1.1 is persistent by default OMNeT++ supports HttpBrowser module with random request mode (statistical distributions) and scripted mode (predefined web sites).

Simulate DNS Query Response

DNS support in OMNeT++ implements RFC 1035 with name servers, authoritative servers, caching servers, and DNS clients.

Simulate TCP Threading

INET supports RFC 793, 896, 1122, 1323, 2018, 2581, 2883 with full TCP states, connection setup/teardown, segment processing, receive buffer.

Transport Services

Transport layer manages end-to-end delivery. Multiplexing/demultiplexing uses port numbers.

📐 Formula — Multiplexing Capacity Overhead: ρ = percentage increase in resource requirement of practical vs optimal scheme

📐 Formula — Gain in Statistical Multiplexing: With each user generating 100 kb/s when active 10% of time, strict multiplexing supports 10 users; statistical multiplexing with 35 users has < 0.0004 probability of > 10 active.

Checksum

Divides M-bit data into N-bit chunks (total M/N chunks). Checksum is N-bit. Total sums = M/N + 1. Undetected errors include reordering, inserting/deleting zero-valued bytes, and multiple errors summing to zero.

Go Back N

Retransmission strategy (ARQ) where no need to buffer at receiver. 📐 Formula — Efficiency without errors: If N > S/D_TP, E = min{1, N×D_TP/S}

Selective Repeat

Retransmission strategy (ARQ) where no need to retransmit all after loss, but buffer requirements at receiver. 📐 Formula — Efficiency without errors: Same as Go Back N 📐 Formula — Efficiency with errors: E = 1 - P Sender buffer limit: number of un-ACKed packets ≤ W. Receiver buffer limit: number of un-ACKed packets cannot differ by more than W.

RTT Estimation and Timeout — Fixed Window

Case 1 (WS/R > RTT + S/R): ACK returns before window's worth of data sent. Case 2 (WS/R < RTT + S/R): Wait for ACK after sending window's worth of data. K = number of windows covering object.

⭐ Key Takeaways

1. Network Modeling and Simulation (NeMS) is an iterative process where modeling precedes simulation, and together they approximate real-world systems — it's essential when analytical models are infeasible, too simple, or need verification, and it's cost-effective compared to prototyping and field deployment.
2. OMNeT++ is a component-based, modular simulation framework (not a simulator itself) that uses NED language for topology description, C++ for module behavior, and INI files for experiment configuration — supporting various simulation types including discrete events, Monte Carlo,

📘 Lecture 15 — TCP Timeout Value

📖 Overview: This lecture examines TCP reliability mechanisms, focusing on timeout estimation, flow control, and connection management. It explains how TCP balances throughput with reliable data delivery through careful timing and window management, and introduces congestion control principles that prevent network collapse.

🗂️ Topics Covered

This lecture covers TCP timeout value estimation using SampleRTT and EstimatedRTT, the relationship between timeout intervals and round-trip time variation, reliable data transfer mechanisms including error, flow, and congestion control, handling loss scenarios including premature timeout and delayed ACKs, flow control through advertised windows, sender window calculations, TCP connection management policies for persistent HTTP, state transitions for clients and servers, and principles of congestion control including infinite/finite buffer scenarios and combat strategies.

📝 Lecture Summary

TCP Timeout Value

TCP timeout values must be longer than RTT (Round Trip Time). As RTT varies, choosing the wrong timeout creates problems. If the timeout is too short, premature timeout occurs causing unnecessary retransmissions. If the timeout is too long, there is slow reaction to segment loss, reducing throughput.

Estimating RTT

SampleRTT is measured as the time from segment transmission until ACK receipt. It ignores retransmissions. EstimatedRTT provides a "smoother" value by averaging several recent measurements rather than using just the current SampleRTT.

Relationship Between TimeOut and Estimated RTT

📐 Formula: EstimatedRTT = (1-α)EstimatedRTT + αSampleRTT → The new estimated RTT is a weighted average of the previous estimate and the current sample.

📐 Formula: TimeoutInterval = EstimatedRTT + 4*DevRTT → The timeout adds a safety margin of four times the deviation of RTT to avoid premature timeouts.

Reliable Data Transfer

TCP offers data reliability through three control mechanisms: Error Control, Flow Control, and Congestion Control. Reliability comes at the cost of reduced throughput. With slow start and Fast Retransmit/Fast Recovery (FRFR), throughput is given by:

📐 Formula: Throughput = 1.22 * MSS / (RTT * √LossRate) → This formula shows the relationship between throughput, maximum segment size, round trip time, and packet loss rate.

Handling Loss

TCP handles Early TimeOut scenarios and uses Delayed Ack (Delayed Acknowledgment) strategies. A delayed ACK means the receiver waits to send an acknowledgment, potentially combining it with acknowledgments for multiple received segments.

💡 Why this matters: Proper handling of loss and acknowledgments directly impacts TCP's efficiency—premature timeouts waste bandwidth through unnecessary retransmissions, while delayed ACKs can improve throughput by reducing overhead.

Flow Control

Introduction The receiver throttles the sender by advertising a window not larger than the amount of data it can buffer. On the receive side, TCP must keep: 🔑 LastByteRcvd − LastByteRead ≤ MaxRcvBuffer

Implication If the local process reads data as fast as it arrives, LastByteRead increments at the same rate as LastByteRcvd, so the AdvertisedWindow stays open (AdvertisedWindow = MaxRcvBuffer). If the receiving process falls behind, the advertised window grows smaller with every arriving segment until it eventually goes to 0.

🔑 Definition — Advertised Window: The amount of free buffer space the receiver has available, communicated to the sender to prevent buffer overflow.

Sender Window 🔑 Definition — Effective Window: The actual amount of data the sender can transmit at any given time. 📐 Formula: LastByteSent − LastByteAcked ≤ AdvertisedWindow

📐 Formula: EffectiveWindow = AdvertisedWindow − (LastByteSent − LastByteAcked) → The sender can only transmit data that fits within both the advertised window and its own send buffer.

Relationship between Max_Send and Max_Receive Buffer 📐 Formula: LastByteWritten − LastByteAcked ≤ MaxSendBuffer → The sender also limits how much unacknowledged data it can have, based on its own buffer size.

TCP Connection Management

Cost and Feasibility Model Reference: Cohen, Edith, Haim Kaplan, and Jeffrey Oldham. "Managing TCP connections under persistent HTTP." Computer Networks 31.11 (1999): 1709-1723.

Holding Time Upon receiving an HTTP request r, the server decides on a holding-time interval T(r). The server leaves the connection open for at most T(r) seconds from when it received r. If a new request r' arrives within the next T(r) seconds, a new holding-time interval T(r') takes effect. Otherwise, the connection is terminated after T(r) seconds.

Connection Management Policy (1 of 3) Policy A is an algorithm that determines an interval T(r) for every request r. For a request sequence s:

• Profit (PA) = number of requests that did not require opening a new connection (hits)
• Misses (MA) = number of requests requiring opening a new connection
• Open-cost (HA) = total time connections are open

What to model? The trade-off between open-cost and number of misses—keeping connections open longer reduces misses but increases open-cost.

Principles of Congestion Control

Introduction Congestion occurs when too many sources send too much data too fast for the network to handle. Manifestations include lost packets (buffer overflow at routers) and long delays (queuing in router buffers).

🔑 Definition — Congestion Collapse: The situation where network throughput drops dramatically as load increases, due to excessive retransmissions and buffer overflow.

Infinite Buffer Scenario With infinite buffers, no packets are lost, but delays become very large when congested. Maximum achievable throughput depends on network capacity.

Finite Buffer Scenario With finite buffers, congestion causes packet loss. Three scenarios exist: a. No loss — ideal condition b. Perfect loss — all packets that would overflow are dropped cleanly c. Imperfect loss — some packets are lost even before full buffer utilization, reducing efficiency

Combat Strategies (1 of 2) Two main approaches exist:

• End-end congestion control: No explicit feedback from network; congestion inferred from end-system observed loss and delay. This is the approach taken by TCP.
• Network-assisted congestion control: Routers provide feedback to end systems via a single bit indicating congestion (SNA, DEC bit, TCP/IP ECN, ATM) or an explicit rate the sender should use.

⭐ Key Takeaways

TCP timeout estimation balances between premature retransmissions (wasted bandwidth) and slow loss recovery. The EstimatedRTT uses exponential weighted moving averaging, while the TimeoutInterval adds a 4*DevRTT safety margin. Flow control uses the advertised window mechanism to prevent receiver buffer overflow, while the sender window and effective window calculations control transmission. Connection management through holding-time policies optimizes the trade-off between open-cost and connection misses. Congestion control prevents network collapse through either end-end inference (TCP approach) or network-assisted feedback, with the fundamental throughput formula showing the inverse relationship between throughput and both RTT and loss rate.

🧠 Quick Revision Questions

1. What are the consequences of setting TCP timeout too short versus too long?
2. Write the formula for EstimatedRTT and explain what each term represents.
3. Under what condition does the advertised window stay fully open, and when does it decrease to zero?
4. In TCP connection management, what is the trade-off between open-cost and number of misses?
5. What are the two main strategies for congestion control, and which one does TCP use?

📘 Lecture 22 — ATM ABR Congestion Control

📖 Overview: This lecture covers two distinct congestion control mechanisms: the Available Bit Rate (ABR) service in ATM networks and the classic TCP Congestion Control algorithm. Understanding ABR provides insight into network-assisted, rate-based congestion management, while TCP’s end-to-end approach is foundational to the modern Internet’s data transmission reliability.

🗂️ Topics Covered

This lecture introduces the ATM ABR service model, its elastic nature, and its congestion control mechanism using explicit rate cells and EFCI bits. It then transitions to TCP’s end-to-end congestion control philosophy, where the sender dynamically adjusts its transmission window (CongWin) based on perceived network congestion without explicit network feedback.

📝 Lecture Summary

Introduction

Available Bit Rate (ABR) is a service category used in ATM networks where the source and destination do not need to be synchronized. ABR does not guarantee against delay or data loss. Instead, it allows the network to allocate available bandwidth fairly over all present ABR sources.

Operation

ABR is an elastic service. If the sender’s path is underloaded, the sender uses the available bandwidth. If the sender’s path is congested, the sender is throttled down to a minimum guaranteed rate.

💡 Why this matters: Elastic services like ABR adapt to network conditions without requiring strict timing, making them efficient for bursty data traffic.

🔑 Definition — Elastic service: A service that can adjust its transmission rate in response to network congestion, using available bandwidth when the path is clear and reducing to a minimum rate when congestion is detected.

Combat Congestion

Congestion is combated using a two-byte ER (explicit rate) field in the RM (resource management) cell. A congested switch may lower the ER value in the cell as it passes through. The sender’s send rate is thus set to the minimum supportable rate available on the path. Additionally, the EFCI (Explicit Forward Congestion Indication) bit in data cells is set to 1 in a congested switch. If a data cell preceding an RM cell has the EFCI bit set, the sender sets the CI (Congestion Indication) bit in the returned RM cell.

📌 Example: If a sender transmits an RM cell, and the data cell immediately before it encounters a congested switch that sets its EFCI bit to 1, the sender will set the CI bit in the RM cell when it returns. The switch that sees the CI bit may then instruct the sender to reduce its rate.

TCP Congestion Control

TCP uses end-end control (no network assistance). The sender limits its transmission using the rule: LastByteSent - LastByteAcked <= CongWin. CongWin is dynamic and a function of perceived network congestion.

🔑 Definition — CongWin (Congestion Window): A dynamic variable at the TCP sender that limits the amount of unacknowledged data in the network, adjusted based on perceived congestion.

📐 Formula: LastByteSent - LastByteAcked <= CongWin → The sender cannot have more unacknowledged bytes in transit than the current congestion window size.

⭐ Key Takeaways

• ABR is a rate-based, network-assisted congestion control for ATM that uses explicit rate (ER) fields in RM cells and EFCI bits in data cells to manage congestion.
• In ABR, the sender’s rate is the minimum supportable rate along the path, and congestion is indicated by lowering the ER or setting the CI bit.
• TCP congestion control is end-to-end, requiring no network assistance; the sender dynamically adjusts its transmission window (CongWin) based on perceived congestion.
• The fundamental TCP rule is that unacknowledged data cannot exceed the CongWin, ensuring the sender does not overwhelm the network.
• Both mechanisms aim to fairly and efficiently allocate bandwidth among active flows, but they achieve this through fundamentally different approaches (network-assisted vs. host-based).

🧠 Quick Revision Questions

1. What does ABR stand for, and what is its primary purpose in ATM networks?
2. How does a congested switch communicate the need to reduce a sender’s rate in ABR?
3. In the context of ABR, what role do the EFCI and CI bits play?
4. What is the fundamental equation that governs a TCP sender’s transmission rate limit?
5. How does TCP’s congestion control differ from ABR’s in terms of network assistance?