CS432 — Final Term Summary (Lectures 23–26)

📘 Lecture 23 — Operation

📖 Overview: This lecture covers TCP congestion control mechanisms and quality of service concepts in IP networks. It explains how TCP manages data transmission rates after loss events and introduces key QoS models like IntServ and DiffServ along with fair queuing techniques.

🗂️ Topics Covered

The lecture covers TCP congestion control mechanisms including AIMD, slow start, and conservative responses to timeout events. It then examines traffic management techniques through leaky bucket and token bucket algorithms. Quality of Service concepts are explored including IntServ and DiffServ models, hard versus soft QoS guarantees, and fair queuing systems for managing network resources.

📝 Lecture Summary

Operation

Loss events in TCP are triggered by timeout or 3 duplicate ACKs. After a loss event, the TCP sender reduces its rate (CongWin) . Three mechanisms govern this behavior: AIMD (Additive Increase Multiplicative Decrease) , Slow start, and Conservative after timeout events.

💡 Why this matters: TCP’s congestion control prevents network collapse by dynamically adjusting transmission rates based on network conditions.

The congestion window behavior is illustrated with a graph showing values changing over time at 8 Kbytes, 16 Kbytes, and 24 Kbytes.

Leaky Bucket and Token Bucket

Leaky Bucket provides buffering of traffic to manage and control the flow of packets onto and through the network. The term “leaky” means a buffer that is constantly flowing.

Operation: Traffic enters the buffers and is tagged based on the amount of packets allowed by the carrier. If a user exceeds the allowed packet flow per increment, the buffer fills and begins to empty out the bottom side at a constant rate.

Token Bucket allows many traffic sources to be defined by the scheme. It provides a concise description of load imposed by a flow and makes it easy to determine resource requirements.

Operation: It provides input parameters to a policing function. An IP packet may be processed if there are sufficient octet tokens to match the IP data number of tokens. If insufficient tokens are available, the packet is relegated to best-effort service. To transmit a packet through a router, one token must be removed. If the token bucket is empty, the packet is queued waiting for the next token. If there is a backlog of packets with an empty bucket, packets are emitted smoothly.

Quality of Service

Background: Broadband IP packet networks are multiservice, all-purpose communications platforms that have spurred QoS efforts. The simplest strategy beyond one-size-fits-all best-effort service is to divide traffic into classes and provide different levels of service to these different classes.

Introduction: QoS is a non-issue for circuit-switched networks. There are Layer 2 and 3 QoS approaches. ATM and Frame Relay provide L2 QoS and offer circuit-like emulation through traffic agreements, traffic control, connection admission control, congestion notification, and fragmentation.

QoS at Network Layer

IP QoS is concerned with end-to-end internetwork with every hop L3 QoS parameters mapping to L2 QoS. The Type of Service (TOS) field provides the initial IP network class of service mechanism. Three precedence bits classify eight categories of services. Lower precedence packets are dropped for higher precedence packets during congestion. Network equipment vendors rarely use precedence bits.

QoS Models

Two QoS models exist for IP packet networks:

• IntServ: Simulates the “virtual circuit” of ATM or frame relay on L3 by setting up an end-to-end route with fixed QoS parameters
• DiffServ: Defines several common classes of service, each with associated queue priorities and drop precedence on a per-hop basis

Hard vs Soft QoS

Hard guarantee: Applications will receive their requested QoS with certainty. Soft guarantee: Applications will receive their requested QoS with high probability.

Fair Queues

First In First Out (FIFO) is presented as the baseline queuing method.

Motivation for FQ

During periods of congestion, FIFO queuing benefits UDP flows over TCP flows. A bursty flow can consume the entire buffer space of a FIFO queue. PQ totally favours TCP over UDP.

Introduction

FQ (Fair Queuing) is the foundation for scheduling disciplines designed to ensure that each flow has fair access to network resources. It prevents a bursty flow from consuming undue bandwidth share. It is also called per-flow or flow-based queuing.

🔑 Definition — Fair Queuing: A scheduling discipline that ensures each flow has fair access to network resources.

Operation

Packets are first classified into flows by the system. They are assigned to a queue dedicated to that flow. Queues are then serviced one packet at a time in round-robin order. Empty queues are skipped.

Benefits

The primary benefit of FQ is that an extremely bursty or misbehaving flow does not degrade QoS delivered to other flows. Each flow is isolated into its own queue. If a flow attempts to consume more than its share of bandwidth, only its queue is affected.

Performance

Allocation of a single resource amongst N users:

• Total resource: μTotal
• Each user i requests ρi
• Each user i receives μi

Conditions:

1. No user receives more than its request
2. No other user satisfying condition 1 has a higher minimum allocation
3. Above condition remains recursively true as we remove the minimal user and reduce total resource
   • μTotal ← μTotal – μi

Conditions continued:

• μi = Min(μFair – ρi)
• Above condition remains recursively true as we remove the minimal user and reduce total resource
• μTotal = Σ μi

⭐ Key Takeaways

TCP manages congestion through AIMD, slow start, and conservative responses to timeouts, using loss events (timeout or 3 duplicate ACKs) to trigger rate reduction. Leaky bucket and token bucket algorithms provide different approaches to traffic shaping, with leaky bucket maintaining constant output rates and token bucket allowing bursts up to a token limit. Quality of Service in IP networks relies on either IntServ (establishing fixed end-to-end paths) or DiffServ (per-hop classification with priorities). Fair Queuing prevents any single flow from monopolizing bandwidth by isolating flows into separate queues serviced in round-robin order, with the allocation following recursive fairness conditions.

🧠 Quick Revision Questions

1. What three mechanisms does TCP use after a loss event to manage congestion?
2. How does the leaky bucket algorithm differ from the token bucket algorithm in handling traffic bursts?
3. What are the two QoS models for IP packet networks and how do they differ?
4. What is the primary motivation for using Fair Queuing instead of FIFO queuing during congestion?
5. State the first condition for fair resource allocation among N users in Fair Queuing performance analysis.

📘 Lecture 25 — Priority Queues

📖 Overview: This lecture introduces Priority Queues, a fundamental scheduling mechanism designed to support differentiated service classes in networking. It explains how packets are classified, placed into different queues, and scheduled based on priority to meet the Quality of Service (QoS) requirements for diverse traffic types like voice, video, and interactive data.

🗂️ Topics Covered

The lecture begins by establishing the motivation for using priority queues to support different service classes. It then explains the standard operation of priority queuing, including packet classification and the strict scheduling rule. Key formulas for resident time and service time are introduced. The lecture concludes with a discussion of two important variants: strict priority queuing and rate-controlled priority queuing.

📝 Lecture Summary

Motivation

Priority queues are designed to provide a relatively simple method of supporting differentiated service classes. The goal is to provide respective services to interactive traffic, voice, video, and best effort traffic, ensuring that time-sensitive or critical applications receive preferential treatment over less urgent data.

Operation

In a priority queue system, packets are first classified and placed into different priority queues. The scheduler then operates under a strict rule: packets are scheduled from the head of a queue only if all queues of higher priority are empty. Within each of the priority queues, packets are scheduled in FIFO (First-In-First-Out) order.

Key Formulas

🔑 Definition — Resident Time (Trj): The time an item ( j ) spends waiting in queue ( k ). 🔑 Definition — Service Time (Tsi): The time required for the system to process an item ( i ).

Variants

Two main variants of priority queuing are discussed:

Strict Priority Queuing: In this variant, packets in a high-priority queue are always scheduled before packets in lower-priority queues. This ensures highest priority traffic always gets serviced first but can lead to starvation for lower-priority traffic under heavy load.

Rate-Controlled Priority Queuing: In this variant, the high-priority queue is scheduled before lower-priority queues, but only if the amount of traffic in the high-priority queue stays below a user-configured threshold. This modification helps protect lower-priority traffic from complete starvation during periods of high-priority traffic bursts.

💡 Why this matters: The choice between strict and rate-controlled priority queuing represents a fundamental trade-off between guaranteeing performance for high-priority traffic versus ensuring fairness for all traffic classes.

⭐ Key Takeaways

Priority queues are essential for supporting differentiated service classes like voice, video, and interactive traffic in networks. The core operation involves classifying packets into queues and scheduling them strictly from the highest priority queue first before servicing lower-priority queues. Two key performance metrics are resident time (waiting time in queue) and service time (processing time). The two main variants—strict and rate-controlled priority queuing—offer different trade-offs between guaranteeing high-priority service and preventing complete starvation of lower-priority traffic. Understanding these mechanisms is critical for designing networks that meet diverse Quality of Service (QoS) requirements.

🧠 Quick Revision Questions

1. What is the primary motivation for using priority queues in networking?
2. In strict priority queuing, when can a packet be scheduled from a lower-priority queue?
3. What is the difference between resident time (Trj) and service time (Tsi)?
4. How does rate-controlled priority queuing differ from strict priority queuing?
5. What is the intended benefit of adding a user-configured threshold in rate-controlled priority queuing?

📘 Lecture 26 — Static Window Modeling

📖 Overview: This lecture provides a comprehensive summary of network performance modeling and analysis, covering static and dynamic window flow control, queuing theory using Little's Theorem and M/M/1 systems, TCP receiver and departure behavior, and forwarding operations in routers. It also explores advanced topics like Quality of Service (QoS) routing, traffic engineering, packet framing, and multiple access protocols, making it a foundational review for computer networking.

🗂️ Topics Covered

The lecture begins with static and dynamic TCP window modeling, then defines Little’s Theorem and its applications in flow control. It covers Poisson arrivals and M/M/1 queuing systems, TCP receive buffer and departure occupancy distributions, and TCP performance under bit error rates (BER). The text then transitions to virtual circuit and datagram networks, router input/output processing, and active queue management with RED. Routing algorithms (link state, distance vector, and hierarchical) are detailed, followed by QoS routing, packet framing (character-based, bit-oriented, and with errors), and multiple access protocols including ALOHA, CSMA/CD, and Ethernet frame sizing. The lecture ends with a brief overview of access technologies (WiFi, Mobile IP, cable, WiMax, DSL, WPAN).

📝 Lecture Summary

Static Window Modeling

This section models a simple network with one link between client and server. The assumption is a fixed congestion window of W segments (MSS), no retransmissions, and a link rate of R. The server sends W segments back-to-back, then sends one segment for each ACK received until the object is sent.

• First Case: The server receives the ACK for the first segment before finishing the transmission of the first window. This occurs when WS/R > RTT + S/R. The total delay is 2RTT + O/R.
• Second Case: The server finishes transmitting the first window before receiving the first ACK. This occurs when WS/R < RTT + S/R (propagation delay dominates). The total delay is 2RTT + O/R + (K-1)[S/R + RTT – WS/R], where K is the number of windows.

📌 Example: For a 15-segment object (O/S = 15) with a window size that causes idling, K = 4 windows, and Q = 2 idle times. The server idles P = min{K-1, Q} = 2 times.

Dynamic Window Modeling

This models actual TCP congestion dynamics, where the server starts with a congestion window of one segment. When an ACK is received, the congestion window doubles (it increases to two segments, then four, etc.), effectively doubling every RTT.

📌 Example: For an object of 15 segments, the window grows as 1, 2, 4, 8 segments per window, leading to K = 4 windows. The server idles P = 2 times between windows.

End-to-End Windows

End-to-end window flow control has limitations: it cannot guarantee a minimum rate for a session and is not suited for real-time traffic like voice and video. There is a tradeoff: window size must limit the number of packets in the subnet but also allow for full-speed transmission and maximum throughput.

Node-by-Node Windows

This addresses the unfairness problem of end-to-end windows, where long sessions with larger windows take precedence at intermediate devices. In virtual circuit windowing, a separate window is maintained for every VC between each pair of adjacent nodes, creating a backpressure effect to slow down sender permits.

💡 Why this matters: Node-by-node windows prevent a single long flow from dominating buffers, improving fairness.

Little's Theorem

This foundational theorem answers two big questions: What is the average number of customers (N) in the system, and what is the average delay per customer (T)?

🔑 Definition — Little's Theorem: N = λ * T, where N is the average number of customers in the system, λ is the average arrival rate, and T is the average time a customer spends in the system.

The theorem expresses "crowdedness": a large N is associated with long delays (T) and vice versa. It is a "law" that is not influenced by the specific distributions of arrivals or service, making it highly robust. It has a probabilistic interpretation for stationary processes where time averages can be replaced by statistical averages.

📌 Example (Application): Little's theorem helps understand the relationship between window size, delay, and throughput in end-to-end flow control. For n flow-controlled sessions with fixed window sizes W1...Wn, the average delay per packet increases approximately linearly with the number of active sessions when the network is heavily loaded, while total throughput stays approximately constant.

Arrivals as Poisson

This section introduces the M/M/1 queuing system as a model for a single transmission line. It consists of a single queue and a single server.

🔑 Definition — Poisson Process: A counting process A(t) where the number of arrivals in any interval of length t is Poisson distributed with parameter λt. It is considered a good model for the aggregate traffic of a large number of similar and independent users

• Properties: Arrivals in disjoint time intervals are independent. Merging n independent arrival processes (each with rate λ/n) yields an aggregate Poisson process with rate λ.

Service Statistics

Service refers to the activities at a receiving device (e.g., MAC processing, lookup, forwarding at a router). Customer (packet) service times have an exponential distribution with parameter μ (the service rate).

🔑 Definition — Memorylessness: The additional time needed to complete a customer's service in progress is independent of when the service started. Similarly, the time until the next arrival is independent of when the previous arrival occurred.

Arrival Occupancy Distribution

This describes the state of the system (number of packets) as seen by an arriving customer. For M/M/1 systems, an arriving customer finds the system in a "typical" state, meaning the probability of finding n customers in the system upon arrival (a_n) equals the overall probability of n customers in the system (p_n). This is because future arrivals are independent of the current number in the system.

Simulating TCP Receive Buffer

RFC 1122 requires a receive buffer to cache sequenced data. The key window definition is: Receiver Window = LastByteSent – LastByteAcked, representing the amount of free space in the receive buffer. INET simulation support provides functions like getAmountOfBufferedBytes() and getAmountOfFreeBytes().

Departure Occupancy Distribution

Similar to arrival occupancy, this describes the state of the system as seen by a departing customer. For M/M/1 systems, the probability of finding n customers upon departure (d_n) also equals p_n. This balances the system: for each increase from n to n+1 due to an arrival, there is a corresponding decrease from n+1 to n due to a departure.

TCP BER Performance

TCP's operation after a timeout (RFC 2581) is to reduce the slow start threshold. The function recalculateSlowStartThreshold() sets ssthresh = max(flight_size/2, 2*MSS), where flight_size = min(snd_cwnd, snd_wnd). This is designed to recover from packet loss, which TCP interprets as a sign of congestion, but can be wrongly triggered by PHY-layer bit errors.

Virtual Circuit Networks

In a virtual circuit (VC) network, source-to-destination paths behave like a telephone circuit, providing guaranteed performance. A call setup and teardown is required before data flow. Each packet carries a VC identifier, and every router on the path maintains "state" (e.g., bandwidth, buffers) for each passing connection. Performance guarantees are a key feature.

Datagram Networks

In a datagram network, two packets from the same user pair can travel along different routes. A routing decision is required for each individual packet. A link state routing algorithm, like Dijkstra's, has complexity O(n²) for finding best paths. Given these costs, finding new routes can result in oscillations.

Input Processing

Two key router functions are routing (running routing algorithms) and forwarding (moving datagrams from input to output). Input processing involves looking up the output port using the forwarding table. If the switching fabric is slower than the combined input rates, input port queuing occurs, causing delay and potential packet loss.

Output Processing

Output ports buffer datagrams arriving from the fabric that are faster than the transmission rate. A scheduling discipline chooses among queued datagrams for transmission. The amount of buffer needed is typically the average RTT times the link capacity C (e.g., for C=10 Gbps, approx 2.5 Gbit buffer). With N flows, this buffering can be reduced.

Head of Line Blocking

Head of Line (HOL) blocking occurs in input ports when the queued datagram at the front of the queue prevents others in the queue from moving forward, even if their output port is free.

Random Early Detection

Random Early Detection (RED) is an active queue management (AQM) technique. Unlike drop tail (which drops packets only when a buffer is full, causing unfairness and network congestion), RED monitors the average queue size and drops packets based on a probability.

🔑 Definition — RED Operation:

• If the average queue size is below a minimum threshold (min_th), all packets are accepted.
• If between min_th and max_th, packets are dropped with a probability that increases as the queue grows.
• If above max_th, all incoming packets are dropped (P = 1).

RED with In & Out (RIO)

RIO is similar to RED but with two separate probability curves for two classes of traffic: "In" (assured) and "Out" (best-effort). The "Out" class has a lower minimum threshold, so its packets are dropped first. This can lead to assured traffic starving best-effort traffic as the average queue length grows.

Routing Algorithms

A routing algorithm determines the end-to-end path through the network, which populates the forwarding table. A graph abstraction is used: G = (N, E) where N is the set of routers and E is the set of links. The cost of a path is the sum of individual link costs (e.g., 1, inversely related to bandwidth or congestion).

Complexity of Link State

Link state is a global routing algorithm where every node has complete topology and link cost information. Each node constructs a graph and independently calculates the best path (e.g., using Dijkstra's algorithm) to every destination. Its complexity is O(n²) for n nodes.

Complexity of Distance Vector

Distance Vector is a distributed routing algorithm where each router knows only its physically-connected neighbors and link costs. It iteratively computes paths by exchanging distance vector estimates with neighbors using the Bellman-Ford equation.

Count to Infinity Problem

While good news travels fast (link cost decreases), bad news travels slow (link cost increases). A large increase can cause a routing loop where nodes bounce packets between each other.

Solution: Poisoned Reverse. If Z routes through Y to get to X, Z tells Y that its distance to X is infinite. This "lie" prevents the loop. Limitation: Poisoned reverse does not work if more than 3 neighbors are involved in the loop.

Hierarchical Routing; Complexity

In practice, routers are not identical. The solution is to collect routers into Autonomous Systems (AS). Within an AS, an intra-AS routing protocol runs (e.g., OSPF, RIP). Between ASes, an inter-AS routing protocol runs (e.g., BGP). A gateway router at the edge of an AS connects to a router in another AS. The forwarding table is configured by both intra- and inter-AS algorithms.

Elastic Aggregates & TE

Traffic engineering (TE) deals with aggregates of traffic. The offered load (ρ) is the average rate at which download requests arrive: ρ = λ * EV, where λ is the average arrival rate and EV is the average file size.

Optimal Routing

A feasible route must have the sum of all flows on a link be less than or equal to its capacity (C). The spare capacity on a link is z = C - sum(flows). Optimal routing is the one that maximizes the smallest spare capacity (z) across all links, increasing the chance that future demands find sufficient free capacity.

Limitations of Min Hop Routing

Shortest path (min-hop) routing minimizes resource consumption. However, it can lead to non-utilization of direct links, effectively "partitioning" the network.

Minimum Interference Routing

Route interference occurs when a chosen route for one flow reduces the capacity available for other flows. The goal is minimum interference, ideally zero, which means the path used for one demand does not share any link with the set of paths available for another demand. The problem is to maximize the smallest maxflow value among all other (s, t) pairs after routing a demand.

QoS Routing

A single stream session comes with a bandwidth requirement and an end-to-end delay requirement. The goal is to find a "good" route. There's a tradeoff between network operator objectives (e.g., minimizing total bandwidth consumed) and end-to-end QoS.

• Nonadditive Metrics: Cannot be summed over links (e.g., bandwidth). The path metric is the minimum link value.
• Additive Metrics: Can be summed over links (e.g., end-to-end delay).

Non-Rate-Based Multiplexers

For non-rate-based multiplexers, other requirements emerge like bit error rate and packet loss probability. The multi-constrained feasibility problem is to find a path that satisfies all m additive constraints. This problem is NP-hard.

Efficient Longest Prefix Match

At a router, route lookup is a search problem to find the entry in the forwarding table with the longest prefix match (LPF) for a destination IP address. A common data structure is a Binary Trie, which is a binary tree where each vertex at level k corresponds to a k-bit prefix. Route lookup traces the 32-bit address in the trie to find the deepest matching vertex.

Level-Compressed Tries

To speed up lookup, level compression compresses a subtree of height k into one level. Instead of a two-way branch for each bit, there is a 2^k-way branch for groups of contiguous bits.

Flooding; ARPANET Algorithm

Flooding is an algorithm where a node broadcasts a message to all neighbors, who then forward it to all of their neighbors. Without a control mechanism, this creates an indefinite flood. The ARPANET solution uses sequence numbers. When a node receives a message, it checks if the sequence number is greater than the last one received from the origin. If yes, it stores and forwards the message. If not, it discards it.

• Need-based Updates: Periodic updates are not needed under normal circumstances, but a zero sequence number is allowed only when a node is recovering from a crash.

Character-based Framing

In character-based framing, special characters like SYN (for idle fill), STX (start of text), and ETX (end of text) delimit frames. A problem occurs if the payload contains an ETX character. The solution is transparent mode, where a DLE (data link escape) character is inserted before any intentional control character in the payload to signal it is not a delimiter.

Bit-oriented Framing

Bit-oriented protocols use a flag (e.g., 01111110) to delimit frames. Bit stuffing is used to prevent this flag from appearing in the data. When the DLL detects five consecutive 1s in the user data, it inserts a 0. The receiver removes the stuffed 0s.

📌 Example: Bit-stuffed frame: ... 01111110 ... (data). After stuffing: ... 011111010 ... (extra 0 inserted). The frame never contains more than five consecutive 1s, ensuring the end flag is uniquely recognizable.

Framing with Errors

Errors in framing information (flags or length fields) can cause problems. If a flag is lost, two frames might be perceived as one, and the receiver might interpret part of the payload as a CRC, leading to undetected errors. Length fields can also be corrupted, causing the receiver to look for the CRC in the wrong place. Partial solutions include using a fixed-length header with its own CRC (DECNET) or placing the length field in the trailer of the preceding frame.

Throughput of MAC

The effective throughput of a Medium Access Control (MAC) protocol depends on the number of active users, resources, channel access method, and traffic volumes.

Channel Partitioning

This divides the channel into smaller pieces (time, frequency, code, space).

• TDM (Time Division Multiplexing): Each station gets a fixed-length slot. Unused slots go idle.
• FDM (Frequency Division Multiplexing): Each station gets a fixed frequency band. Unused bands go idle.

Random Access Protocols

In random access, a node transmits at full channel rate when it has a packet, with no a priori coordination.

• ALOHA: The simplest protocol, where a node transmits whenever it wants. The maximum throughput is very low (approx. 18% for pure ALOHA).
• Slotted ALOHA: Time is divided into slots, and nodes must start transmission at the beginning of a slot, reducing collisions. The maximum efficiency is 1/e ≈ 0.37.

CSMA/CD

Carrier Sense Multiple Access with Collision Detection (CSMA/CD) improves on ALOHA by listening before transmitting (carrier sensing). If the channel is idle, it transmits. If a collision is detected, the transmission is aborted to reduce channel wastage. The binary exponential backoff algorithm is used for retransmission: after mth collision, a random backoff time is chosen from a set that doubles in size.

• Efficiency: Goes to 1 as propagation delay goes to 0 or as transmission time goes to infinity. The formula is Efficiency = 1/(1 + 5*tprop/ttrans).

Min & Max Frame Size Computation

• Minimum Frame Size: Ethernet recommends 64 bytes. The frame must be long enough to allow collision detection before the transmission ends. At 10 Mbps LAN with a max length of 2500m, the min frame is 512 bits or 64 bytes. If data is less than 46 bytes, padding is used.
• Maximum Frame Size: Ethernet recommends 1500 bytes. This limit is a tradeoff considering overhead (for small frames), pipelining (shorter frames allow for pipeline effects), and transmission errors (larger frames have a higher error probability).

📌 Example (Pipelining): For two empty links, a single large packet takes 2*(L/R) + 2*propagation delay. Splitting it into two smaller packets reduces total delay to 1.5*(L/R) + 2*propagation delay due to pipelining.

Fixed Frame Size Computation

Fixed-size frames (e.g., ATM's 53-byte cells) provide predictable performance (low latency and jitter) but trade off payload efficiency due to padding.

Multi-Protocol Label Switching

MPLS is a fast packet switching and routing mechanism. The main idea is "route once and switch many times." Packets are labeled before being forwarded, and the network layer header is not processed at each hop. Its main goal is to support traffic engineering and QoS.

Correctness of Stop and Wait

Stop and Wait is a step-locked communication: the client sends a request and waits for a response. Problems occur with unnumbered packets and ACKs. However, the use of sequence numbers in the packets and ACKs solves these issues.

Efficiency of Go Back N

The efficiency of Go Back N (and Stop and Wait) is limited by the bandwidth-delay product. For a 1 Gbps link, a 1KB packet sent over a 30ms RTT results in very low utilization.

📐 Formula: U_sender = (L/R) / (RTT + L/R)

📌 Example: For L=8000 bits, R=1 Gbps, RTT=30ms: U_sender = 0.00081. The throughput is 33 kB/sec over a 1 Gbps link.

Limitations of Go Back N

Retransmissions occur due to errors in the forward and feedback directions, but also due to long frames in the reverse direction. If the ACK for a packet doesn't arrive before a timeout, the entire window may be retransmitted.

⭐ Key Takeaways

The lecture integrates core network modeling, queuing theory, and protocol mechanics. Little's Theorem (N=λT) is a fundamental law for analyzing system occupancy and delay, independent of arrival/service distributions, and is crucial for understanding flow control trade-offs. The M/M/1 model provides a baseline for performance analysis, while static and dynamic window models explain the fundamental delay-throughput tradeoffs in TCP. Understanding framing methods (character-based with DLE, bit-oriented with bit-stuffing, and length-based with errors) and MAC protocols (ALOHA, Slotted ALOHA, CSMA/CD) is essential for grasping how reliable, efficient communication is achieved at the link layer. Finally, the tradeoffs between circuit-like (VC, MPLS) and datagram networks, as well as between global (Link State) and distributed (Distance Vector) routing algorithms, form the basis of modern internet architecture.

🧠 Quick Revision Questions

1. State Little's Theorem and explain how it can be used to relate the average number of packets in a router queue to the average packet delay.
2. Compare the two cases of Static Window Modeling for TCP. What condition determines whether the sender idles between windows, and what is the resulting delay formula for each case?
3. What is the "count to infinity" problem in Distance Vector routing? Describe the Poisoned Reverse technique and its limitation.
4. Explain the difference between additive and nonadditive link metrics in the context of QoS routing. Give an example of each.
5. In Ethernet (CSMA/CD), why is there a minimum frame size of 64 bytes? How is this size computed based on the properties of a 10 Mbps LAN?