diff options
| author | mo khan <mo@mokhan.ca> | 2025-09-27 11:35:01 -0600 |
|---|---|---|
| committer | mo khan <mo@mokhan.ca> | 2025-09-27 11:35:01 -0600 |
| commit | 66f39fb4530a6ca1fb6c00f277d66cddbcfdb29c (patch) | |
| tree | 2321813f431557656c7c0e9ad3ee8317d1e739c4 /comp347 | |
| parent | 9834bb9e49491fff614ea729f08570ed70518aac (diff) | |
move assignment files around
Diffstat (limited to 'comp347')
| -rw-r--r-- | comp347/assignment2/assignment2.md | 768 | ||||
| -rw-r--r-- | comp347/assignment3/assignment3.md | 1269 |
2 files changed, 0 insertions, 2037 deletions
diff --git a/comp347/assignment2/assignment2.md b/comp347/assignment2/assignment2.md deleted file mode 100644 index b143cdd..0000000 --- a/comp347/assignment2/assignment2.md +++ /dev/null @@ -1,768 +0,0 @@ -# COMP-347: Computer Networks -## Assignment 2 - -**Student Name:** [Your Name] -**Student ID:** [Your Student ID] -**Time Spent:** [Hours spent on assignment] -**Due:** After completion of Units 3, 4, and 5 - ---- - -## Part 1: Short Answer Questions (30%) - -### 1.1 TCP Reliable Data Transfer (5%) - -TCP provides reliable data transfer over IP's unreliable best-effort service through several key mechanisms: - -#### 1. Sequence Numbers and Acknowledgments -TCP assigns a sequence number to each byte of data sent. The receiver sends acknowledgments (ACKs) back to the sender to confirm successful receipt of data. The ACK number indicates the next expected sequence number, providing cumulative acknowledgment of all bytes received up to that point. - -#### 2. Checksums for Error Detection -Each TCP segment includes a checksum field that covers the header and data. The receiver calculates the checksum and compares it with the received value. If they don't match, the segment is discarded, and no ACK is sent, triggering retransmission. - -#### 3. Timeout and Retransmission -TCP maintains a retransmission timer for each unacknowledged segment. If an ACK is not received within the timeout period, TCP assumes the segment was lost and retransmits it. The timeout value is dynamically calculated based on measured round-trip times (RTT). - -#### 4. Duplicate Detection -Using sequence numbers, TCP can detect and discard duplicate segments that may arrive due to unnecessary retransmissions. This prevents duplicate data from being delivered to the application. - -#### 5. Flow Control -TCP implements a sliding window mechanism using the receive window field in the header. The receiver advertises how much buffer space it has available, preventing the sender from overwhelming the receiver with data. - -#### 6. In-Order Delivery -TCP uses sequence numbers to reorder segments that arrive out of order due to different network paths or processing delays, ensuring the application receives data in the correct sequence. - -#### 7. Connection Management -TCP establishes connections through a three-way handshake and terminates them gracefully, ensuring both endpoints agree on the connection state and that all data has been successfully delivered before closing. - -**Summary:** TCP transforms IP's unreliable service into a reliable one by adding acknowledgments, retransmission, error detection, flow control, and ordering mechanisms, creating a robust communication channel for applications. - -### 1.2 Go-Back-N Protocol (5%) - -While Reliable Data Transfer (RDT) protocols are essentially stop-and-wait protocols that send one packet and wait for acknowledgment before sending the next, Go-Back-N (GBN) achieves higher throughput by allowing multiple packets to be transmitted without waiting for individual acknowledgments. GBN accomplishes this through several key mechanisms: - -#### 1. Sliding Window Mechanism -GBN uses a sliding window of size N that allows the sender to transmit up to N unacknowledged packets. The window "slides" forward as acknowledgments are received, enabling continuous transmission without waiting for each individual ACK. - -#### 2. Sequence Number Space -GBN uses a finite sequence number space (typically modulo 2^k) where packets are numbered sequentially. The sender maintains: -- **base**: oldest unacknowledged packet sequence number -- **nextseqnum**: next sequence number to be used -- **Window boundary**: base ≤ sequence numbers < base + N - -#### 3. Cumulative Acknowledgments -The receiver sends cumulative ACKs, where ACK(n) acknowledges all packets up to and including sequence number n. This allows a single ACK to acknowledge multiple packets, reducing ACK traffic and simplifying the protocol. - -#### 4. Selective Retransmission Strategy -When a timeout occurs or a NAK is received, GBN retransmits all unacknowledged packets starting from the oldest unacknowledged packet (base). This "go-back-N" behavior ensures reliable delivery while maintaining simplicity. - -#### 5. Receiver Window Size of 1 -The receiver maintains a window of size 1, accepting only the next expected packet in sequence. Out-of-order packets are discarded and the receiver sends a duplicate ACK for the last correctly received packet. This maintains simplicity at the receiver. - -#### 6. Timer Management -GBN uses a single timer for the oldest unacknowledged packet. When the timer expires, all unacknowledged packets are retransmitted, and the timer is restarted. - -#### Performance Benefits -- **Pipeline Utilization**: Multiple packets can be "in flight" simultaneously, utilizing available bandwidth more efficiently than stop-and-wait -- **Higher Throughput**: Transmission rate approaches channel capacity when the window size is appropriately chosen relative to the bandwidth-delay product -- **Reduced Idle Time**: Sender doesn't wait for individual ACKs before continuing transmission - -**Key Insight**: GBN trades some efficiency (retransmitting correctly received but out-of-order packets) for simplicity and improved throughput compared to stop-and-wait protocols. - -### 1.3 IPv6 Transition (5%) - -IPv6 was developed to address critical limitations of IPv4 and represents a major advancement in Internet Protocol technology. - -#### Problems IPv6 Was Intended to Solve: - -#### 1. Address Space Exhaustion -The most pressing issue was IPv4's 32-bit address space providing only ~4.3 billion addresses. With the explosive growth of Internet-connected devices (computers, smartphones, IoT devices), IPv4 addresses were rapidly depleting. IPv6's 128-bit address space provides approximately 3.4×10^38 addresses, virtually eliminating address scarcity. - -#### 2. Network Address Translation (NAT) Limitations -IPv4's address shortage forced widespread NAT deployment, which: -- Breaks end-to-end connectivity principles -- Complicates peer-to-peer applications -- Adds processing overhead and complexity -- Creates security and troubleshooting challenges - -IPv6 eliminates the need for NAT by providing abundant address space. - -#### 3. Routing Table Growth -IPv4's classful addressing and fragmented allocation led to routing table explosion, increasing router memory requirements and lookup times. IPv6's hierarchical addressing enables better route aggregation. - -#### 4. Configuration Complexity -IPv4 requires manual configuration or DHCP for address assignment. IPv6 introduces stateless address autoconfiguration (SLAAC), allowing devices to automatically configure addresses using router advertisements. - -#### 5. Security Integration -While IPSec could be retrofitted to IPv4, IPv6 was designed with mandatory IPSec support (though later made optional), providing built-in authentication and encryption capabilities. - -#### IPv4 to IPv6 Transition Methods: - -The transition challenge arises because IPv4 and IPv6 are not directly compatible, and the global Internet cannot switch overnight. - -#### 1. Dual Stack -- **Approach**: Run both IPv4 and IPv6 protocols simultaneously on the same devices -- **Benefits**: Gradual transition, backwards compatibility maintained -- **Challenges**: Requires supporting both protocol stacks, increased complexity - -#### 2. Tunneling -- **6in4 Tunnels**: Encapsulate IPv6 packets within IPv4 packets for transport across IPv4 networks -- **6to4**: Automatic tunneling mechanism using special IPv6 addresses -- **Teredo**: Allows IPv6 connectivity through IPv4 NATs -- **Benefits**: Enables IPv6 communication across IPv4 infrastructure -- **Challenges**: Performance overhead, configuration complexity - -#### 3. Translation/Gateway Mechanisms -- **NAT64**: Translates between IPv6-only and IPv4-only hosts -- **DNS64**: Synthesizes IPv6 addresses for IPv4-only services -- **Benefits**: Allows IPv6-only networks to access IPv4 resources -- **Challenges**: Translation complexity, potential protocol feature loss - -#### Current Transition Status: -The transition has been gradual but accelerating, with major content providers, ISPs, and organizations deploying IPv6 alongside IPv4. The approach typically involves dual-stack deployment followed by eventual IPv4 sunset once IPv6 adoption reaches critical mass. - -**Key Insight**: IPv6 solves fundamental scalability and architectural limitations of IPv4, but the transition requires careful planning and multiple coexistence strategies to maintain Internet connectivity during the prolonged migration period. - -### 1.4 SNMP Protocol (5%) - -Simple Network Management Protocol (SNMP) is a widely-used application layer protocol for monitoring and managing network devices. It operates using seven message types to facilitate communication between network management systems and managed devices. - -#### SNMP GetRequest Message: - -**Purpose:** -- **Data Retrieval**: Requests specific management information from a managed device (agent) -- **Monitoring**: Allows network management stations to query device status, performance metrics, configuration parameters -- **Polling**: Enables periodic collection of network statistics and operational data - -**Operation:** -- Management station sends GetRequest to agent specifying Object Identifiers (OIDs) of desired data -- Agent responds with GetResponse containing the requested values -- Used for retrieving single or multiple related management objects - -**Examples of retrieved data:** -- Interface statistics (bytes sent/received, error counts) -- System information (uptime, CPU usage, memory utilization) -- Device configuration parameters -- Routing table entries - -#### SNMP SetRequest Message: - -**Purpose:** -- **Configuration Management**: Modifies configuration parameters on managed devices -- **Remote Control**: Allows centralized management of distributed network devices -- **Policy Enforcement**: Enables automatic application of network policies and settings - -**Operation:** -- Management station sends SetRequest with OIDs and new values to be configured -- Agent validates the request and applies changes if authorized and valid -- Agent responds with GetResponse confirming success or reporting errors - -**Examples of configuration changes:** -- Modifying interface administrative status (up/down) -- Changing routing table entries -- Updating access control lists -- Setting device operational parameters - -#### Why UDP Was Chosen for SNMP: - -#### 1. Simplicity and Efficiency -- **Lightweight Protocol**: UDP's minimal overhead is suitable for frequent, small management messages -- **No Connection Setup**: Eliminates three-way handshake overhead for simple request-response operations -- **Reduced Processing**: Less CPU and memory overhead on both management stations and managed devices - -#### 2. Network Management Considerations -- **Scalability**: Managing hundreds or thousands of devices simultaneously requires efficient protocols -- **Polling Frequency**: Network monitoring often involves frequent, periodic polling where UDP's efficiency is beneficial -- **Bandwidth Conservation**: UDP's lower overhead preserves network bandwidth for actual data traffic - -#### 3. Fault Tolerance Requirements -- **Network Resilience**: When networks are experiencing problems (the time when management is most needed), TCP's reliability mechanisms might themselves fail -- **Timeout Control**: Applications can implement custom timeout and retry logic suited to network management needs -- **Parallel Operations**: UDP allows simultaneous queries to multiple devices without connection state management - -#### 4. Application-Layer Reliability -- **Custom Reliability**: SNMP applications implement their own retry mechanisms tailored to management needs -- **Selective Reliability**: Not all SNMP operations require guaranteed delivery (e.g., periodic polling) -- **Timeout Strategies**: Management applications can use appropriate timeout values based on network conditions - -**Key Insight**: SNMP's choice of UDP reflects the protocol's emphasis on simplicity, scalability, and efficiency for network management operations, where custom application-layer reliability is often more appropriate than TCP's general-purpose reliability mechanisms. - -### 1.5 SDN-Enabled Devices (5%) - -Software-Defined Networking (SDN) represents a paradigm shift from traditional distributed network control to centralized programmable control. SDN-enabled networking devices possess several key features that distinguish them from conventional network equipment: - -#### 1. Separation of Control and Data Planes - -**Traditional vs. SDN Architecture:** -- **Traditional**: Control plane (routing decisions) and data plane (packet forwarding) are tightly coupled within each device -- **SDN-enabled**: Control plane is centralized in an external controller, while devices focus solely on data plane operations - -**Benefits:** -- Simplified device hardware and software -- Centralized network intelligence and decision-making -- Consistent policy enforcement across the network - -#### 2. OpenFlow Protocol Support - -**Programmable Flow Tables:** -- Devices maintain flow tables that can be programmed remotely by SDN controllers -- Flow entries specify match conditions (headers, ports) and corresponding actions (forward, drop, modify) -- Support for multiple flow table levels with different priorities and capabilities - -**Dynamic Flow Management:** -- Controllers can add, modify, or delete flow entries in real-time -- Enables rapid network reconfiguration without manual device configuration -- Supports fine-grained traffic control and policy implementation - -#### 3. Southbound API Interface - -**Controller Communication:** -- Standardized interface (typically OpenFlow) for communication with SDN controllers -- Secure channel establishment and maintenance with controllers -- Support for multiple simultaneous controller connections for redundancy - -**Control Message Handling:** -- Process controller commands for flow table modifications -- Generate statistics and event notifications to controllers -- Handle controller failover and recovery scenarios - -#### 4. Centralized Management Capabilities - -**Remote Configuration:** -- All device configuration managed through centralized controller -- Elimination of individual device CLI/SNMP management for routing decisions -- Consistent network-wide policies applied automatically - -**Real-time Monitoring:** -- Detailed flow statistics and performance metrics available to controllers -- Network-wide visibility through centralized data collection -- Enhanced troubleshooting and network optimization capabilities - -#### 5. Programmability and Flexibility - -**Application-Aware Networking:** -- Support for application-specific forwarding behavior -- Dynamic service chaining and traffic engineering -- Quality of Service (QoS) policies programmable per flow - -**Rapid Service Deployment:** -- New network services deployable through software updates to controller -- No need for individual device firmware updates for new features -- Faster innovation cycles and service rollout - -#### 6. Network Virtualization Support - -**Multi-Tenancy:** -- Support for network slicing and virtual network overlays -- Isolation between different virtual networks on shared physical infrastructure -- Flexible resource allocation and policy enforcement per tenant - -**Abstraction Capabilities:** -- Present different virtual network topologies to different applications -- Support for network function virtualization (NFV) integration -- Dynamic virtual network creation and modification - -#### 7. Enhanced Security Features - -**Centralized Security Policy:** -- Network-wide security policies enforced consistently -- Rapid response to security threats through centralized control -- Fine-grained access control and traffic inspection capabilities - -**Secure Controller Communication:** -- Encrypted control channels using TLS/SSL -- Certificate-based authentication between devices and controllers -- Protection against control plane attacks and unauthorized access - -**Market Advantages:** -SDN-enabled devices provide organizations with greater network agility, simplified management, reduced operational costs, and the ability to implement innovative networking solutions that respond quickly to changing business requirements. - -**Key Insight**: SDN-enabled devices transform networking from static, distributed control to dynamic, centralized programmability, enabling networks to become more responsive, efficient, and aligned with application requirements. - -### 1.6 BGP Loop Detection (5%) - -Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol used for routing between Internet Service Providers (ISPs) and autonomous systems. As a path-vector protocol operating in a complex, decentralized environment, BGP faces significant challenges with routing loops. - -#### What Are BGP Loops? - -**Definition:** -BGP routing loops occur when routing information creates circular paths, where packets can be forwarded in cycles without ever reaching their destination. In BGP context, loops manifest as circular sequences of autonomous systems (AS) in routing paths. - -**Example Scenario:** -- AS1 advertises a route to AS2 -- AS2 advertises the route to AS3 -- AS3 advertises the route back to AS1 -- This creates a circular path: AS1 → AS2 → AS3 → AS1 - -#### Why Should Loops Be Avoided? - -#### 1. Infinite Routing Cycles -- **Packet Circulation**: Packets caught in loops circulate indefinitely, consuming network resources -- **Resource Exhaustion**: Routers waste CPU cycles and bandwidth processing looped packets -- **Network Instability**: Loops can cause cascading failures and routing table inconsistencies - -#### 2. Convergence Problems -- **Slow Convergence**: Loops prevent BGP from reaching stable routing states -- **Persistent Oscillation**: Routes may continuously change without settling on optimal paths -- **Route Flapping**: Unstable routes cause frequent BGP updates, increasing protocol overhead - -#### 3. Connectivity Loss -- **Unreachable Destinations**: Looped routes prevent legitimate traffic from reaching destinations -- **Service Degradation**: Applications experience timeouts and connectivity failures -- **Economic Impact**: ISPs lose revenue due to service disruptions and inefficient routing - -#### 4. Protocol Scalability Issues -- **Routing Table Pollution**: Invalid looped routes consume memory and processing resources -- **Update Storm**: Loop detection and recovery generate excessive BGP update messages -- **Inter-AS Trust**: Loops can propagate across AS boundaries, affecting global Internet stability - -#### How BGP Detects Loops - -BGP employs the **AS_PATH** attribute as its primary loop detection mechanism: - -#### 1. AS_PATH Attribute -**Structure:** -- Each BGP route announcement includes an AS_PATH attribute -- AS_PATH contains the sequence of autonomous systems the route has traversed -- Each AS prepends its own AS number when forwarding the route - -**Example AS_PATH:** `65001 65002 65003` (route originated in AS 65003, passed through AS 65002, currently at AS 65001) - -#### 2. Loop Detection Algorithm -**Process:** -1. **Route Reception**: When a BGP router receives a route advertisement -2. **AS_PATH Inspection**: Router examines the AS_PATH attribute in the received route -3. **Self-Detection**: Router checks if its own AS number appears anywhere in the AS_PATH -4. **Loop Identification**: If the router's AS number is found in AS_PATH, a loop is detected -5. **Route Rejection**: The router discards the looped route and does not forward it further - -#### 3. Prevention Mechanism -**Automatic Loop Prevention:** -- BGP routers automatically reject routes containing their own AS number -- This prevents routes from being re-advertised back to ASes they've already traversed -- The mechanism works transitively across multiple AS hops - -#### 4. Additional Safeguards -**AS_PATH Length Limits:** -- BGP implementations typically limit AS_PATH length (e.g., 255 AS hops) -- Prevents extremely long paths that might indicate routing anomalies -- Helps detect certain types of routing loops or misconfigurations - -**Route Filtering:** -- ISPs implement route filters to reject invalid or suspicious route advertisements -- Prefix filters prevent advertisement of private or reserved address spaces -- AS_PATH filters can block routes from known problematic sources - -**Key Insight**: BGP's AS_PATH-based loop detection provides a simple but effective mechanism to maintain routing stability in the complex, distributed Internet environment, though it requires careful configuration and monitoring to handle sophisticated routing policies and potential edge cases. - ---- - -## Part 2: Long Answer Questions (70%) - -### 2.1 1's Complement Checksum (10%) - -**Given 8-bit bytes:** 11011001, 01010010, 11001010, 10100100, 01011001 - -#### a) Calculate the 1's complement of the sum - -**Step 1: Add all bytes using binary addition with carry wraparound** - -``` - 11011001 (217 in decimal) -+ 01010010 ( 82 in decimal) ------------ - 100101011 (carry = 1, sum = 00101011) - -Wrap carry: - 00101011 -+ 1 ------------ - 00101100 (44 in decimal) - -+ 11001010 (202 in decimal) ------------ - 100010110 (carry = 1, sum = 00010110) - -Wrap carry: - 00010110 -+ 1 ------------ - 00010111 (23 in decimal) - -+ 10100100 (164 in decimal) ------------ - 10111011 (187 in decimal, no carry) - -+ 01011001 ( 89 in decimal) ------------ - 100010100 (carry = 1, sum = 00010100) - -Wrap carry: - 00010100 -+ 1 ------------ - 00010101 (21 in decimal) -``` - -**Sum of all bytes:** 00010101 - -**Step 2: Calculate 1's complement** -1's complement = flip all bits - -Sum: 00010101 -1's complement: 11101010 - -**Answer:** The 1's complement of the sum is **11101010** - -#### b) Why use 1's complement instead of just the sum? - -UDP and TCP use the 1's complement of the sum rather than just the sum for several important reasons: - -**1. Error Detection Capability** -- The 1's complement provides a **checksum value** that changes predictably when errors occur -- Using just the sum would mean a checksum of all 0s for certain data patterns, providing no error indication -- 1's complement ensures the checksum is never all 0s unless the original sum was all 1s - -**2. Mathematical Properties** -- 1's complement addition is **commutative** - order of addition doesn't matter -- Provides **closure property** - results always fit in the same bit width -- **Self-inverse property** - applying 1's complement twice returns original value - -**3. Zero Representation** -- Handles the dual representation of zero in 1's complement arithmetic (+0 and -0) -- Provides consistent behavior across different implementations - -**4. Implementation Efficiency** -- Simple bitwise NOT operation to compute -- Hardware-friendly calculation requiring minimal processing overhead - -#### c) How does the receiver detect errors? - -**Receiver Error Detection Process:** - -1. **Recalculate Sum:** Receiver adds all received bytes (including the checksum field) -2. **1's Complement:** Takes 1's complement of the calculated sum -3. **Error Check:** - - **No errors:** Result should be all 1s (11111111) - - **Errors detected:** Result will be something other than all 1s - -**Verification with our example:** -- Original bytes sum: 00010101 -- Transmitted checksum: 11101010 -- Receiver adds: 00010101 + 11101010 = 11111111 -- 1's complement of 11111111 = 00000000 -- Since result is all 0s (equivalent to "no errors"), data is assumed correct - -#### d) Error detection analysis - -**1-bit errors:** -- **Always detected:** Any single bit flip will change the sum, making the final result non-zero -- 1's complement checksum **guarantees detection** of all single-bit errors -- This is because changing any single bit changes the overall sum by exactly 1 - -**2-bit errors:** -- **Not always detected:** Some 2-bit error patterns can go undetected -- **Undetected case:** If two bit flips cancel each other out in the sum -- **Example:** Flipping bit 0 from 0→1 (+1) and bit 1 from 1→0 (-2) results in net change of -1, which wraps around in 1's complement arithmetic - -**Detection probability for 2-bit errors:** -- Most 2-bit errors are detected, but not all -- Probability of detection ≈ (2^n - 2)/2^n where n = number of bits -- For 8-bit: ≈ 254/256 = 99.2% detection rate - -**Limitations:** -- **Burst errors:** Multiple consecutive bit errors may cancel out -- **Pattern errors:** Certain systematic error patterns can evade detection -- **Bit order:** Errors that preserve the arithmetic sum may go undetected - -**Key Insight:** 1's complement checksum provides excellent detection for single-bit errors and most multi-bit errors with minimal computational overhead, making it ideal for network protocols where speed and simplicity are crucial. - -### 2.2 Dijkstra's Shortest Path Algorithm (20%) - -#### a) Interpretation of the given table - -**What the table shows:** -The table demonstrates the step-by-step execution of Dijkstra's shortest path algorithm to find the shortest paths from source node **u** to all other nodes in a network. - -**Row meanings:** -- **Step**: Iteration number of the algorithm -- **N'**: Set of nodes for which shortest path has been determined (permanently labeled) -- **Each column D(v),P(v)**: Distance and predecessor for each destination node - -**Column meanings:** -- **D(v)**: Current shortest known distance from source u to node v -- **P(v)**: Previous node (predecessor) in the shortest path from u to v -- **∞**: Indicates no path is currently known to that node - -**Algorithm progression:** -1. **Step 0**: Initialize with source u, direct neighbors get their direct link costs -2. **Each step**: Add the unvisited node with minimum distance to N', update distances to remaining nodes -3. **Final step**: All nodes have been processed, shortest paths determined - -**Example interpretation:** -- Step 1: Node x added to N' (distance 1 from u), distances to w and y updated through x -- Step 2: Node y added to N' (distance 2 from u), distance to z updated through y - -#### b) Dijkstra's algorithm from node x - -**Given network topology from diagram:** -- x connects to: y(5), w(3), s(5) -- y connects to: x(5), z(11), u(1), t(5) -- w connects to: x(3), u(1), v(3) -- u connects to: y(1), w(1), t(9), v(1) -- v connects to: w(3), u(1), t(6), s(1) -- t connects to: y(5), u(9), v(6), s(1), z(3) -- s connects to: x(5), v(1), t(1) -- z connects to: y(11), t(3) - -**Dijkstra's Algorithm Table from source x:** - -| Step | N' | D(y),P(y) | D(z),P(z) | D(u),P(u) | D(t),P(t) | D(v),P(v) | D(w),P(w) | D(s),P(s) | -|------|-------|-----------|-----------|-----------|-----------|-----------|-----------|-----------| -| 0 | x | 5,x | ∞ | ∞ | ∞ | ∞ | 3,x | 5,x | -| 1 | xw | 5,x | ∞ | 4,w | ∞ | 6,w | - | 5,x | -| 2 | xwu | 5,x | ∞ | - | 13,u | 5,u | - | 5,x | -| 3 | xwuy | ∞ | 16,y | - | 10,y | 5,u | - | 5,x | -| 4 | xwuyv | ∞ | 16,y | - | 10,y | - | - | 5,x | -| 5 | xwuyvs | ∞ | 16,y | - | 6,s | - | - | - | -| 6 | xwuyvst | ∞ | 9,t | - | - | - | - | - | -| 7 | xwuyvsttz | - | - | - | - | - | - | - | - -**Step-by-step calculation:** - -**Step 0**: Initialize from x -- Direct neighbors: y(5), w(3), s(5) - -**Step 1**: Add w (minimum distance = 3) -- Update through w: u = min(∞, 3+1) = 4,w; v = min(∞, 3+3) = 6,w - -**Step 2**: Add u (minimum distance = 4) -- Update through u: y = min(5, 4+1) = 5,x (no change); t = min(∞, 4+9) = 13,u; v = min(6, 4+1) = 5,u - -**Step 3**: Add y (minimum distance = 5) -- Update through y: z = min(∞, 5+11) = 16,y; t = min(13, 5+5) = 10,y - -**Step 4**: Add v (minimum distance = 5) -- Update through v: t = min(10, 5+6) = 10,y (no change); s = min(5, 5+1) = 5,x (no change) - -**Step 5**: Add s (minimum distance = 5) -- Update through s: t = min(10, 5+1) = 6,s - -**Step 6**: Add t (minimum distance = 6) -- Update through t: z = min(16, 6+3) = 9,t - -**Step 7**: Add z (minimum distance = 9) -- Algorithm complete - -**Final shortest paths from x:** -- x → w: distance 3, path: x-w -- x → u: distance 4, path: x-w-u -- x → y: distance 5, path: x-y -- x → v: distance 5, path: x-w-u-v -- x → s: distance 5, path: x-s -- x → t: distance 6, path: x-s-t -- x → z: distance 9, path: x-s-t-z - -### 2.3 CIDR Routing (20%) - -**Routing Table:** -- 135.46.56.0/22 Interface 0 -- 135.46.60.0/22 Interface 1 -- 192.53.40.0/23 Router 2 -- Default Router 3 - -#### How CIDR Routers Route Packets: - -CIDR (Classless Inter-Domain Routing) routers use **longest prefix matching** to determine packet forwarding: - -1. **Extract destination IP** from incoming packet -2. **Compare with routing table entries** using subnet masks -3. **Find matching prefixes** - IP address AND subnet mask must match network portion -4. **Select longest matching prefix** - most specific route wins -5. **Forward via corresponding next hop** - interface or router - -#### Analysis of Each IP Address: - -#### a) 135.46.61.10 - -**Binary Analysis:** -- IP: 135.46.61.10 = 10000111.00101110.00111101.00001010 -- Check against each routing entry: - -**Entry 1: 135.46.56.0/22** -- Network: 135.46.56.0 = 10000111.00101110.00111000.00000000 -- Mask: /22 = 11111111.11111111.11111100.00000000 -- IP & Mask: 10000111.00101110.00111100.00000000 = 135.46.60.0 -- Network match: 135.46.56.0 ≠ 135.46.60.0 → **No match** - -**Entry 2: 135.46.60.0/22** -- Network: 135.46.60.0 = 10000111.00101110.00111100.00000000 -- Mask: /22 = 11111111.11111111.11111100.00000000 -- IP & Mask: 10000111.00101110.00111100.00000000 = 135.46.60.0 -- Network match: 135.46.60.0 = 135.46.60.0 → **Match found** - -**Entry 3: 192.53.40.0/23** -- Different network range → **No match** - -**Decision:** Forward via **Interface 1** (longest/only matching prefix) - -#### b) 135.46.53.16 - -**Binary Analysis:** -- IP: 135.46.53.16 = 10000111.00101110.00110101.00010000 - -**Entry 1: 135.46.56.0/22** -- IP & Mask (/22): 10000111.00101110.00110100.00000000 = 135.46.52.0 -- Network match: 135.46.56.0 ≠ 135.46.52.0 → **No match** - -**Entry 2: 135.46.60.0/22** -- IP & Mask (/22): 10000111.00101110.00110100.00000000 = 135.46.52.0 -- Network match: 135.46.60.0 ≠ 135.46.52.0 → **No match** - -**Entry 3: 192.53.40.0/23** -- Different network range → **No match** - -**Decision:** No specific routes match → Forward via **Default Router 3** - -#### c) 192.53.40.6 - -**Binary Analysis:** -- IP: 192.53.40.6 = 11000000.00110101.00101000.00000110 - -**Entry 1 & 2: 135.46.x.x/22** -- Different network range (135.x.x.x vs 192.x.x.x) → **No match** - -**Entry 3: 192.53.40.0/23** -- Network: 192.53.40.0 = 11000000.00110101.00101000.00000000 -- Mask: /23 = 11111111.11111111.11111110.00000000 -- IP & Mask: 11000000.00110101.00101000.00000000 = 192.53.40.0 -- Network match: 192.53.40.0 = 192.53.40.0 → **Match found** - -**Decision:** Forward via **Router 2** - -#### d) 192.53.56.7 - -**Binary Analysis:** -- IP: 192.53.56.7 = 11000000.00110101.00111000.00000111 - -**Entry 1 & 2: 135.46.x.x/22** -- Different network range → **No match** - -**Entry 3: 192.53.40.0/23** -- Network: 192.53.40.0 = 11000000.00110101.00101000.00000000 -- Mask: /23 = 11111111.11111111.11111110.00000000 -- IP & Mask: 11000000.00110101.00111000.00000000 = 192.53.56.0 -- Network match: 192.53.40.0 ≠ 192.53.56.0 → **No match** - -**Note:** /23 mask covers 192.53.40.0 - 192.53.41.255, but 192.53.56.7 falls outside this range - -**Decision:** No specific routes match → Forward via **Default Router 3** - -#### Summary of Routing Decisions: - -| IP Address | Matching Route | Next Hop | Explanation | -|------------|----------------|-----------|-------------| -| 135.46.61.10 | 135.46.60.0/22 | Interface 1 | Falls within 135.46.60.0-135.46.63.255 range | -| 135.46.53.16 | Default | Router 3 | No specific route matches | -| 192.53.40.6 | 192.53.40.0/23 | Router 2 | Falls within 192.53.40.0-192.53.41.255 range | -| 192.53.56.7 | Default | Router 3 | Outside all specific network ranges | - -**Key Insight:** CIDR routing provides efficient address space utilization through variable-length subnet masks, with longest prefix matching ensuring packets are forwarded via the most specific available route. - -### 2.4 TCP Congestion Control (20%) - -**Given:** -- Link capacity: 1 Gbps = 10^9 bps -- Segment size: 1,500 bytes = 12,000 bits -- Round-trip time (RTT): 15 msec = 0.015 seconds -- TCP connection always in congestion avoidance phase -- No link buffering -- Single TCP connection uses entire link - -#### a) Maximum window size (in segments) - -**Bandwidth-Delay Product Calculation:** -The maximum window size is limited by the bandwidth-delay product of the network path. - -BDP = Bandwidth × RTT -BDP = 10^9 bps × 0.015 s = 15 × 10^6 bits - -**Convert to segments:** -Maximum window size = BDP ÷ Segment size -= 15 × 10^6 bits ÷ 12,000 bits/segment -= 1,250 segments - -**Maximum window size = 1,250 segments** - -#### b) Average window size and throughput - -In TCP congestion avoidance phase with no buffering, the congestion window follows a sawtooth pattern: - -**Sawtooth Behavior:** -- Window grows linearly (additive increase) until packet loss occurs -- When loss occurs, window is halved (multiplicative decrease) -- Pattern repeats: W_max → W_max/2 → W_max → W_max/2 - -**Average window size:** -Average = (W_max + W_max/2) ÷ 2 = (3 × W_max) ÷ 4 - -Average window size = (3 × 1,250) ÷ 4 = **937.5 segments** - -**Average throughput calculation:** -Throughput = (Average window size × Segment size) ÷ RTT -= (937.5 segments × 12,000 bits/segment) ÷ 0.015 s -= 11.25 × 10^6 bits ÷ 0.015 s -= 750 × 10^6 bps -= **750 Mbps** - -#### c) Recovery time after packet loss - -In congestion avoidance phase, the window increases by 1 segment per RTT (additive increase). - -**Recovery scenario:** -- Before loss: W_max = 1,250 segments -- After loss: Window drops to W_max/2 = 625 segments -- Recovery target: Return to W_max = 1,250 segments -- Required increase: 1,250 - 625 = 625 segments - -**Time calculation:** -- Increase rate: 1 segment per RTT -- Time to recover: 625 RTTs -- Recovery time = 625 × 0.015 s = **9.375 seconds** - -#### d) Buffer size to keep link busy - -**Problem analysis:** -Without buffering, packet loss occurs when the sending rate exceeds link capacity, causing TCP to reduce its window and underutilize the link during recovery. - -**Buffer sizing strategy:** -To keep the link fully utilized, the buffer should accommodate the "excess" segments sent during the window increase phase. - -**Calculation:** -During congestion avoidance, the window oscillates between W_max/2 and W_max. The buffer needs to handle the excess above the bandwidth-delay product: - -Excess segments = W_max - BDP_segments -= 1,250 - 1,250 = 0 segments (in ideal case) - -However, practical considerations: -- **TCP dynamics**: Buffer should accommodate at least one window worth of data during oscillation -- **Recommended buffer size**: BDP = 1,250 segments - -**Alternative approach (rule of thumb):** -Buffer size = RTT × Bandwidth ÷ √(number of flows) -= 15 ms × 1 Gbps ÷ √1 -= 15 × 10^6 bits = 1,250 segments - -**Justification:** -- **Prevents packet loss**: Buffer absorbs traffic bursts during window increases -- **Maintains link utilization**: Prevents TCP from reducing window due to loss -- **Optimal sizing**: Equals bandwidth-delay product, providing sufficient queuing without excessive delay -- **Single flow consideration**: With one TCP flow, buffer equals BDP for optimal performance - -**Recommended buffer size: 1,250 segments (15 Mb)** - -This buffer size ensures: -1. Link remains fully utilized during TCP sawtooth behavior -2. Minimal additional queuing delay (one RTT worth of data) -3. Sufficient capacity to handle congestion avoidance dynamics -4. Prevention of unnecessary packet drops that reduce throughput
\ No newline at end of file diff --git a/comp347/assignment3/assignment3.md b/comp347/assignment3/assignment3.md deleted file mode 100644 index 26c7796..0000000 --- a/comp347/assignment3/assignment3.md +++ /dev/null @@ -1,1269 +0,0 @@ -# COMP-347: Computer Networks -## Assignment 3 - -**Student Name:** [Your Name] -**Student ID:** [Your Student ID] -**Time Spent:** [Hours spent on assignment] -**Due:** After completion of Units 6 and 7 - ---- - -## Part 1: Short Answer Questions (30%) - -### 1.1 Anchor MSC in GSM Networks (5%) - -The **Anchor MSC (Mobile Switching Center)** plays a crucial role in GSM (Global System for Mobile Communications) networks, particularly in managing mobile subscriber mobility and maintaining service continuity during handovers. - -#### Primary Functions: - -#### 1. Home Location Register (HLR) Interface -- **Subscriber Authentication**: The Anchor MSC maintains the primary connection to the subscriber's HLR, which contains the master copy of subscriber profile data -- **Service Profile Management**: Stores and manages subscriber service capabilities, restrictions, and supplementary services -- **Location Management**: Coordinates with the HLR to track the subscriber's current location area and serving MSC - -#### 2. Call Routing and Management -- **Incoming Call Routing**: Acts as the initial point of contact for incoming calls to a mobile subscriber, routing calls to the current serving MSC -- **Call Continuity**: Ensures seamless call continuation during inter-MSC handovers by maintaining call state information -- **Billing Coordination**: Centralizes billing records and coordinates charging information across multiple serving MSCs - -#### 3. Handover Coordination -- **Inter-MSC Handover Support**: When a mobile subscriber moves between different MSC coverage areas during an active call, the Anchor MSC coordinates the handover process -- **Resource Management**: Maintains circuit connections and manages radio resources during complex handover scenarios -- **Quality Maintenance**: Ensures call quality is preserved during mobility events - -#### 4. Visitor Location Register (VLR) Coordination -- **Registration Management**: Coordinates subscriber registration/deregistration across multiple VLRs as the subscriber roams -- **Authentication Coordination**: Manages authentication procedures when subscribers roam between different MSC areas -- **Temporary Identity Management**: Handles Temporary Mobile Subscriber Identity (TMSI) allocation and management - -#### 5. Network Optimization Benefits -- **Reduced HLR Load**: By serving as an intermediary, the Anchor MSC reduces the number of direct HLR queries from multiple serving MSCs -- **Improved Performance**: Centralized management of subscriber data reduces lookup times and improves call setup performance -- **Enhanced Mobility**: Provides seamless service as subscribers move between different network areas - -#### Operational Scenario: -When a GSM subscriber roams from their home area to a different MSC area: -1. The new serving MSC registers the subscriber's presence -2. The Anchor MSC updates the HLR with the new location information -3. For incoming calls, the HLR directs calls to the Anchor MSC -4. The Anchor MSC then routes calls to the current serving MSC -5. During handovers, the Anchor MSC maintains call state and coordinates resource allocation - -**Key Insight**: The Anchor MSC concept enables efficient mobility management in GSM networks by centralizing subscriber management functions while allowing distributed call processing, thereby optimizing both network performance and subscriber experience during roaming scenarios. - -### 1.2 LTE Network Characteristics (5%) - -**LTE (Long Term Evolution)** represents a significant advancement in cellular network technology, introducing fundamental changes in radio access network architecture and capabilities compared to previous generations. - -#### Main Characteristics of LTE Radio Access Networks: - -#### 1. All-IP Architecture -- **Packet-Switched Only**: LTE eliminates circuit-switched voice calls, using Voice over LTE (VoLTE) for all voice communications -- **Flat Network Architecture**: Simplified network topology with fewer network elements compared to 3G -- **IP Multimedia Subsystem (IMS)**: Integrated multimedia services delivered over IP - -#### 2. OFDMA and SC-FDMA Technologies -- **Orthogonal Frequency Division Multiple Access (OFDMA)**: Used in downlink for efficient spectrum utilization and multi-user access -- **Single Carrier FDMA (SC-FDMA)**: Used in uplink to reduce peak-to-average power ratio and improve battery life -- **Flexible Bandwidth**: Supports 1.4, 3, 5, 10, 15, and 20 MHz channel bandwidths - -#### 3. MIMO Technology -- **Multiple Input Multiple Output (MIMO)**: Uses multiple antennas at both transmitter and receiver -- **Spatial Multiplexing**: Increases data throughput by transmitting multiple data streams simultaneously -- **Diversity Gain**: Improves signal reliability in fading environments - -#### 4. Advanced Radio Resource Management -- **Dynamic Resource Allocation**: Real-time allocation of radio resources based on traffic demand and channel conditions -- **Link Adaptation**: Automatic adjustment of modulation and coding schemes based on channel quality -- **Inter-Cell Interference Coordination (ICIC)**: Coordinates resource usage between neighboring cells - -#### How LTE Differs from Previous Generations: - -#### Architecture Differences: - -**2G/3G Architecture:** -- **Circuit-Switched Core**: Separate networks for voice (circuit-switched) and data (packet-switched) -- **Hierarchical Network**: Multiple network elements (RNC, BSC, MSC) -- **Voice Priority**: Networks primarily designed for voice services - -**LTE Architecture:** -- **All-IP Core**: Single packet-switched network for all services -- **Flat Architecture**: Evolved NodeB (eNodeB) directly connects to core network -- **Data-Centric**: Optimized for high-speed data transmission - -#### Performance Improvements: - -| Aspect | 3G (UMTS) | LTE | -|--------|-----------|-----| -| **Downlink Speed** | Up to 42 Mbps (HSPA+) | Up to 300 Mbps | -| **Uplink Speed** | Up to 5.7 Mbps | Up to 75 Mbps | -| **Latency** | 100-500 ms | <10 ms | -| **Spectral Efficiency** | 1-2 bps/Hz | 3-4 bps/Hz | - -#### Key Technological Advances: - -#### 1. Radio Interface Evolution -- **CDMA → OFDMA**: Transition from Code Division to Orthogonal Frequency Division Multiple Access -- **Advanced Modulation**: Support for 64-QAM and higher-order modulation schemes -- **Adaptive Antenna Systems**: Beamforming and advanced antenna technologies - -#### 2. Protocol Stack Simplification -- **Reduced Layers**: Streamlined protocol stack compared to 3G -- **Header Compression**: More efficient header compression techniques -- **Fast Retransmission**: Hybrid ARQ (HARQ) for rapid error recovery - -#### 3. Mobility Management -- **Seamless Handovers**: Faster handover procedures with minimal service interruption -- **Inter-RAT Mobility**: Smooth transitions between LTE and legacy networks (2G/3G) -- **Self-Organizing Networks (SON)**: Automated network optimization and configuration - -#### 4. Quality of Service (QoS) -- **Evolved Packet System (EPS) Bearers**: Fine-grained QoS control for different traffic types -- **Policy Control**: Dynamic policy enforcement based on subscriber profiles and network conditions -- **Guaranteed Bit Rate (GBR)**: Service-specific bandwidth guarantees - -**Key Insight**: LTE represents a fundamental paradigm shift from circuit-switched, voice-centric networks to an all-IP, data-optimized architecture that provides significantly higher throughput, lower latency, and improved spectral efficiency while supporting seamless multimedia services and enhanced mobility management. - -### 1.3 CSMA/CD Protocol (5%) - -**CSMA/CD** stands for **Carrier Sense Multiple Access with Collision Detection**, a media access control protocol used in traditional Ethernet networks to manage shared medium access among multiple nodes. - -#### How CSMA/CD Works: - -#### 1. Carrier Sense (CS) -- **Listen Before Transmit**: Before transmitting, a node listens to the medium to detect if another transmission is already in progress -- **Channel Assessment**: If the channel is busy, the node waits until it becomes idle -- **Persistence Strategy**: Once idle is detected, the node may wait a brief interframe gap before attempting transmission - -#### 2. Multiple Access (MA) -- **Shared Medium**: Multiple nodes share the same physical transmission medium (bus topology) -- **Contention-Based**: All nodes compete for access to the medium using the same protocol rules -- **Distributed Control**: No central authority controls medium access; all decisions are made locally by each node - -#### 3. Collision Detection (CD) -- **Simultaneous Transmission Monitoring**: While transmitting, nodes continuously monitor the medium to detect collisions -- **Signal Comparison**: Compare transmitted signal with received signal to identify interference from other transmissions -- **Early Abort**: Upon detecting collision, immediately stop transmission to minimize medium occupation time - -#### 4. Collision Handling Procedure -When a collision is detected: -1. **Jam Signal**: Transmit a 32-bit or 48-bit jam signal to ensure all nodes detect the collision -2. **Exponential Backoff**: Each involved node waits a random time before retransmitting -3. **Backoff Algorithm**: Wait time = random(0, 2^n - 1) × slot time, where n = number of consecutive collisions -4. **Retry Limit**: After 16 consecutive collisions, the frame is discarded - -#### Importance of RTT in CSMA/CD: - -The **Round-Trip Time (RTT)** is critical for CSMA/CD's proper operation due to the **collision detection window**: - -#### 1. Collision Detection Window -- **Maximum Detection Time**: RTT represents the maximum time needed to detect a collision anywhere on the network -- **Worst-Case Scenario**: Node A starts transmitting just as Node B (at maximum distance) begins transmission -- **Signal Propagation**: Time for A's signal to reach B plus time for B's collision signal to return to A - -#### 2. Minimum Frame Size Requirement -- **Frame Transmission Time**: Must be ≥ 2 × propagation delay (RTT) -- **Collision Detection Guarantee**: Ensures transmitting node can detect collision before finishing frame transmission -- **Ethernet Standard**: 64-byte minimum frame size ensures collision detection on maximum cable length - -#### 3. Network Diameter Limitation -- **Maximum Cable Length**: RTT limits the physical size of collision domain -- **Signal Attenuation**: Longer cables increase propagation delay and reduce signal strength -- **Timing Constraints**: RTT must remain small enough for reliable collision detection - -#### 4. Slot Time Calculation -- **Slot Time**: Basic timing unit = 2 × maximum propagation delay -- **Backoff Intervals**: Random backoff periods are multiples of slot time -- **Network Synchronization**: Ensures all nodes use consistent timing for collision avoidance - -#### Mathematical Relationship: -``` -Minimum Frame Time ≥ 2 × (Cable Length ÷ Propagation Speed + Processing Delays) -``` - -For traditional Ethernet: -- Maximum cable length: 2.5 km -- Propagation speed: ~2×10^8 m/s -- RTT: ~25 μs -- Minimum frame size: 64 bytes (512 bits) -- Slot time: 512 bit times - -#### Protocol Efficiency Impact: -- **Short RTT**: Allows smaller minimum frames, higher efficiency, larger networks -- **Long RTT**: Requires larger minimum frames, reduces efficiency, limits network size -- **Collision Domain**: RTT determines maximum collision domain size - -**Key Insight**: RTT is fundamental to CSMA/CD because it defines the collision detection window, determines minimum frame size requirements, and limits the physical extent of collision domains, directly affecting network efficiency and scalability. - -### 1.4 CSMA/CA Protocol (5%) - -**CSMA/CA** stands for **Carrier Sense Multiple Access with Collision Avoidance**, a media access control protocol primarily used in wireless networks (such as 802.11 Wi-Fi) where collision detection is impractical due to the wireless medium characteristics. - -#### How CSMA/CA Works: - -#### 1. Carrier Sense (CS) -- **Physical Carrier Sense**: Listen to the wireless medium to detect ongoing transmissions -- **Virtual Carrier Sense**: Use Network Allocation Vector (NAV) from RTS/CTS or other control frames -- **Clear Channel Assessment (CCA)**: Determine if medium is idle before attempting transmission -- **Energy Detection**: Monitor RF energy levels to identify channel activity - -#### 2. Multiple Access (MA) -- **Shared Wireless Medium**: Multiple stations compete for access to the same radio frequency spectrum -- **Hidden Terminal Problem**: Stations may not hear each other due to distance or obstacles -- **Distributed Coordination**: No centralized control; stations coordinate access through distributed algorithms - -#### 3. Collision Avoidance (CA) -Unlike collision detection, CSMA/CA attempts to **prevent collisions** rather than detect them after they occur: - -#### Basic CSMA/CA Operation: -1. **Channel Sensing**: Station senses the medium for a minimum time period (DIFS - Distributed Inter-Frame Space) -2. **Random Backoff**: If medium is idle, station waits a random backoff time before transmitting -3. **Transmission**: If medium remains idle after backoff, station transmits the frame -4. **Acknowledgment**: Receiver sends ACK frame to confirm successful reception -5. **Retransmission**: If no ACK received, sender assumes collision and retransmits after backoff - -#### How Collisions Are Avoided: - -#### 1. Random Backoff Mechanism -- **Contention Window**: Each station selects random backoff time from [0, CW-1] × slot time -- **Exponential Backoff**: After collision, contention window doubles (CW = CW × 2) -- **Collision Probability Reduction**: Random timing reduces likelihood of simultaneous transmission -- **Fairness**: All stations have equal probability of accessing the medium - -#### 2. Inter-Frame Spacing (IFS) -Different frame types use different inter-frame spaces to establish priority: -- **SIFS (Short IFS)**: Highest priority for ACKs and CTS frames -- **DIFS (Distributed IFS)**: Standard priority for data frames -- **EIFS (Extended IFS)**: Used after corrupted frame reception -- **Priority Access**: Critical frames get preferential medium access - -#### 3. Request-to-Send/Clear-to-Send (RTS/CTS) -**Optional mechanism for avoiding hidden terminal collisions:** - -**RTS/CTS Handshake:** -1. **RTS Frame**: Sender transmits Request-to-Send to receiver -2. **CTS Frame**: Receiver responds with Clear-to-Send if medium available -3. **NAV Setting**: Both RTS and CTS set Network Allocation Vector in other stations -4. **Data Transmission**: Sender transmits data frame after successful RTS/CTS exchange -5. **ACK Frame**: Receiver acknowledges data reception - -**Benefits:** -- **Hidden Terminal Solution**: CTS frame alerts hidden terminals about upcoming transmission -- **Collision Reduction**: Reduces collision probability for large data frames -- **Bandwidth Reservation**: Virtual carrier sensing reserves medium for transmission - -#### 4. Network Allocation Vector (NAV) -- **Virtual Carrier Sensing**: Maintains timer indicating when medium will be busy -- **Duration Field**: Frames carry duration information for NAV updates -- **Medium Reservation**: Stations defer transmission while NAV > 0 -- **Collision Avoidance**: Prevents transmissions that would cause collisions - -#### 5. Binary Exponential Backoff -**Collision Response Mechanism:** -- **Initial Window**: Start with minimum contention window (CW_min) -- **Window Doubling**: After each collision, CW = min(CW × 2, CW_max) -- **Random Selection**: Choose backoff = random[0, CW-1] × slot_time -- **Window Reset**: Reset CW to CW_min after successful transmission - -#### 6. Frame Retry and Timeout -- **ACK Timeout**: If ACK not received within specified time, assume collision -- **Retry Limit**: Maximum number of retransmission attempts before frame discard -- **Exponential Backoff**: Apply backoff algorithm for each retry attempt - -#### CSMA/CA vs CSMA/CD Comparison: - -| Aspect | CSMA/CA | CSMA/CD | -|--------|---------|---------| -| **Medium** | Wireless | Wired | -| **Collision Handling** | Avoidance | Detection | -| **Collision Detection** | Not possible | Real-time | -| **Overhead** | Higher (RTS/CTS, ACK) | Lower | -| **Efficiency** | Lower due to avoidance | Higher when collisions are rare | -| **Hidden Terminal** | Addressed by RTS/CTS | Not applicable | - -**Key Insight**: CSMA/CA compensates for the inability to detect collisions in wireless media by implementing sophisticated avoidance mechanisms including random backoff, virtual carrier sensing, RTS/CTS handshakes, and prioritized channel access, trading some efficiency for reliability in challenging wireless environments. - -### 1.5 Data Link Layer Error Detection/Correction (5%) - -The data link layer employs various techniques to handle transmission errors that may occur due to noise, interference, or signal attenuation in communication channels. - -## Error Detection Techniques: - -#### 1. Parity Check -- **Single Parity**: Adds one parity bit to detect single-bit errors -- **Even Parity**: Total number of 1s (including parity bit) is even -- **Odd Parity**: Total number of 1s (including parity bit) is odd -- **Limitation**: Cannot detect even numbers of bit errors - -#### 2. Checksum -- **Internet Checksum**: Sum all data words, take 1's complement (used in IP, TCP, UDP) -- **Fletcher Checksum**: Uses modular arithmetic for improved error detection -- **Advantages**: Simple implementation, good for random errors -- **Limitations**: May miss certain systematic error patterns - -#### 3. Cyclic Redundancy Check (CRC) -- **Polynomial-Based**: Uses generator polynomial to create check sequence -- **Frame Check Sequence (FCS)**: CRC bits appended to frame -- **Detection Capability**: Detects all single-bit, double-bit, odd number of bits, and burst errors ≤ r bits (where r = degree of generator polynomial) -- **Common Polynomials**: CRC-16, CRC-32, CRC-CCITT -- **High Reliability**: Very low probability of undetected errors - -#### 4. Two-Dimensional Parity -- **Block Structure**: Arrange data in rows and columns -- **Row Parity**: Calculate parity for each row -- **Column Parity**: Calculate parity for each column -- **Enhanced Detection**: Can detect and correct single-bit errors, detect some multi-bit errors - -## Error Correction Techniques: - -#### 1. Forward Error Correction (FEC) -**Hamming Codes:** -- **Single Error Correction**: Can correct single-bit errors automatically -- **Redundancy**: Requires 2^r ≥ m + r + 1 (where m = data bits, r = parity bits) -- **Syndrome Decoding**: Uses parity check equations to locate error position -- **Example**: Hamming(7,4) code uses 4 data bits, 3 parity bits - -**Reed-Solomon Codes:** -- **Block Codes**: Operate on symbols rather than individual bits -- **Burst Error Correction**: Excellent for correcting burst errors -- **Applications**: Used in CDs, DVDs, QR codes, satellite communications -- **Capability**: Can correct up to t symbol errors with 2t redundant symbols - -#### 2. Convolutional Codes -- **Continuous Encoding**: Encode data stream continuously using shift registers -- **Memory**: Output depends on current and previous input bits -- **Viterbi Decoding**: Maximum likelihood decoding algorithm -- **Applications**: Widely used in wireless communications, satellite links - -#### 3. Turbo Codes -- **Iterative Decoding**: Uses two or more constituent codes with iterative decoding -- **Near Shannon Limit**: Approaches theoretical maximum error correction capability -- **Applications**: 3G/4G cellular networks, satellite communications -- **Complexity**: Higher computational complexity but superior performance - -## Automatic Repeat Request (ARQ): - -#### 1. Stop-and-Wait ARQ -- **Simple Protocol**: Send one frame, wait for ACK before sending next -- **Positive ACK**: Receiver sends acknowledgment for correctly received frames -- **Timeout**: Sender retransmits if no ACK received within timeout period -- **Sequence Numbers**: Prevents duplicate frame acceptance - -#### 2. Go-Back-N ARQ -- **Sliding Window**: Multiple frames can be outstanding -- **Cumulative ACK**: ACK n acknowledges all frames up to n -- **Error Recovery**: Retransmit all frames from error point onwards -- **Efficiency**: Better throughput than stop-and-wait - -#### 3. Selective Repeat ARQ -- **Individual ACK**: Each frame acknowledged individually -- **Selective Retransmission**: Only retransmit errored frames -- **Buffer Requirements**: Receiver must buffer out-of-order frames -- **Optimal Efficiency**: Best throughput but most complex - -## Hybrid Techniques: - -#### 1. Hybrid ARQ (HARQ) -- **FEC + ARQ Combination**: Uses error correction with retransmission backup -- **Type I HARQ**: FEC for error correction, ARQ for error detection -- **Type II HARQ**: Incremental redundancy - additional parity bits sent on retransmission -- **Applications**: LTE, 5G, and other modern wireless systems - -#### 2. Adaptive Error Control -- **Dynamic Selection**: Choose error control method based on channel conditions -- **Channel Quality Feedback**: Adjust redundancy based on measured error rates -- **Optimization**: Balance between throughput and reliability - -## Implementation Considerations: - -| Technique | Detection | Correction | Overhead | Complexity | Applications | -|-----------|-----------|------------|----------|------------|--------------| -| **Parity** | Limited | No | Low | Very Low | Simple systems | -| **Checksum** | Good | No | Low | Low | Internet protocols | -| **CRC** | Excellent | No | Medium | Medium | Ethernet, Wi-Fi | -| **Hamming** | Good | Single-bit | High | Medium | Memory systems | -| **Reed-Solomon** | Excellent | Multiple | High | High | Storage, broadcast | -| **ARQ** | Perfect | Perfect | Variable | Medium | Most data networks | - -**Key Insight**: Data link layer error control combines detection techniques (parity, checksum, CRC) with correction methods (FEC, ARQ) to provide reliable data transmission, with the choice of technique depending on channel characteristics, performance requirements, and acceptable complexity trade-offs. - -### 1.6 Wi-Fi Network Standards (5%) - -Modern Wi-Fi technology encompasses several IEEE 802.11 standards that have evolved to provide higher data rates, improved reliability, and enhanced features for today's wireless networking needs. - -## Current Wi-Fi Standards in Industry Use: - -### 1. 802.11n (Wi-Fi 4) - 2009 -**Link Characteristics:** -- **Frequency Bands:** 2.4 GHz and 5 GHz (dual-band) -- **Channel Bandwidth:** 20 MHz and 40 MHz channels -- **Data Rates:** Up to 600 Mbps (theoretical maximum) -- **MIMO Technology:** Up to 4×4 spatial streams -- **Range:** ~70m indoor, ~250m outdoor -- **Modulation:** OFDM with up to 64-QAM -- **Backward Compatibility:** Compatible with 802.11a/b/g - -### 2. 802.11ac (Wi-Fi 5) - 2013 -**Link Characteristics:** -- **Frequency Band:** 5 GHz only -- **Channel Bandwidth:** 20, 40, 80, and 160 MHz channels -- **Data Rates:** Up to 6.93 Gbps (theoretical maximum) -- **MIMO Technology:** Up to 8×8 MU-MIMO (Multi-User MIMO) -- **Range:** ~35m indoor, ~120m outdoor -- **Modulation:** OFDM with up to 256-QAM -- **Beamforming:** Explicit beamforming for improved signal focus -- **Wave 1 vs Wave 2:** Wave 2 adds MU-MIMO and 160 MHz channels - -### 3. 802.11ax (Wi-Fi 6/6E) - 2019/2020 -**Link Characteristics:** -- **Frequency Bands:** 2.4 GHz, 5 GHz, and 6 GHz (Wi-Fi 6E) -- **Channel Bandwidth:** 20, 40, 80, and 160 MHz channels -- **Data Rates:** Up to 9.6 Gbps (theoretical maximum) -- **MIMO Technology:** Up to 8×8 MU-MIMO (uplink and downlink) -- **Range:** Similar to 802.11ac but more efficient in dense environments -- **Modulation:** OFDMA with up to 1024-QAM -- **Key Features:** OFDMA, Target Wake Time (TWT), BSS Coloring - -### 4. 802.11be (Wi-Fi 7) - 2024 (Emerging) -**Link Characteristics:** -- **Frequency Bands:** 2.4 GHz, 5 GHz, and 6 GHz (tri-band) -- **Channel Bandwidth:** Up to 320 MHz channels -- **Data Rates:** Up to 46 Gbps (theoretical maximum) -- **MIMO Technology:** Up to 16×16 MU-MIMO -- **Advanced Features:** Multi-Link Operation (MLO), 4K-QAM modulation - -## Detailed Standard Comparison: - -| Standard | Year | Frequency | Max Bandwidth | Max Rate | MIMO | Key Features | -|----------|------|-----------|---------------|----------|------|--------------| -| **802.11n** | 2009 | 2.4/5 GHz | 40 MHz | 600 Mbps | 4×4 | First MIMO, dual-band | -| **802.11ac** | 2013 | 5 GHz | 160 MHz | 6.93 Gbps | 8×8 | MU-MIMO, 256-QAM | -| **802.11ax** | 2019 | 2.4/5/6 GHz | 160 MHz | 9.6 Gbps | 8×8 | OFDMA, 1024-QAM, TWT | -| **802.11be** | 2024 | 2.4/5/6 GHz | 320 MHz | 46 Gbps | 16×16 | MLO, 4K-QAM | - -## Technical Characteristics by Standard: - -### Physical Layer Features: -**802.11n:** -- **Guard Interval:** 400ns and 800ns options -- **Frame Aggregation:** A-MSDU and A-MPDU for efficiency -- **Space-Time Block Coding (STBC):** Improved reliability -- **Greenfield Mode:** 802.11n-only operation for maximum efficiency - -**802.11ac:** -- **Wider Channels:** 80 MHz and 160 MHz for higher throughput -- **More Spatial Streams:** Up to 8 spatial streams -- **Advanced Beamforming:** Standardized explicit beamforming -- **Downlink MU-MIMO:** Simultaneous transmission to multiple clients - -**802.11ax:** -- **OFDMA:** Orthogonal Frequency Division Multiple Access for efficiency -- **Uplink MU-MIMO:** Multi-user transmission in both directions -- **BSS Coloring:** Reduces interference between overlapping networks -- **Target Wake Time:** Power management for IoT devices - -### Industry Applications: - -**Enterprise Networks:** -- **802.11ax:** Predominant choice for new installations -- **High-Density Environments:** Airports, stadiums, conference centers -- **OFDMA Benefits:** Better performance with many connected devices - -**Home Networks:** -- **802.11ac:** Still widely deployed in existing installations -- **802.11ax:** Becoming standard for new home routers -- **Backward Compatibility:** Support for legacy devices - -**IoT and Industrial:** -- **2.4 GHz Bands:** Better wall penetration and range -- **Low Power Features:** TWT for battery-powered devices -- **Mesh Networks:** Wi-Fi 6 mesh systems for whole-home coverage - -**Public Wi-Fi:** -- **6 GHz Band:** Wi-Fi 6E reduces congestion in crowded areas -- **Higher Capacity:** Support for more simultaneous users -- **Quality of Service:** Better traffic prioritization - -### Performance Characteristics: - -**Range Considerations:** -- **5 GHz vs 2.4 GHz:** 5 GHz offers higher speeds but shorter range -- **6 GHz Band:** Highest speeds but most limited range -- **Beamforming:** Improves range and reliability across all modern standards - -**Interference Handling:** -- **Channel Bonding:** Wider channels increase susceptibility to interference -- **Dynamic Frequency Selection (DFS):** Avoids radar interference on 5 GHz -- **BSS Coloring:** Wi-Fi 6 feature reduces co-channel interference - -**Key Insight:** Modern Wi-Fi standards have evolved from simple OFDM-based systems to sophisticated multi-user, multi-band technologies that optimize spectrum efficiency, reduce latency, and support diverse applications from high-bandwidth streaming to low-power IoT devices, with each generation addressing specific limitations of previous standards while maintaining backward compatibility. - ---- - -## Part 2: Long Answer Questions (70%) - -### 2.1 Code Division Multiple Access (CDMA) (15%) - -Code Division Multiple Access (CDMA) is a sophisticated channel access method that enables multiple users to share the same frequency spectrum simultaneously by assigning unique codes to each user. This research examines CDMA technology, focusing on Wideband CDMA (W-CDMA) used in 3G UMTS networks. - -## CDMA Technology Overview - -CDMA differs fundamentally from Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA) by using mathematical coding techniques rather than time slots or frequency separation to distinguish between users. All users transmit simultaneously on the same frequency band, with separation achieved through orthogonal or quasi-orthogonal spreading codes. - -## Selected CDMA Scheme: Wideband CDMA (W-CDMA) - -**W-CDMA** is the air interface standard used in 3G UMTS (Universal Mobile Telecommunications System) networks, standardized by 3GPP (3rd Generation Partnership Project). This scheme represents an evolution from earlier CDMA implementations like IS-95. - -### How W-CDMA Works: - -#### 1. Spreading Process -**Direct Sequence Spread Spectrum:** -- Each user's data stream is multiplied by a unique spreading code (channelization code) -- The spreading code has a much higher bit rate (chip rate) than the original data -- W-CDMA uses a chip rate of 3.84 Mcps (Mega-chips per second) -- This spreads the signal across a 5 MHz bandwidth - -**Mathematical Representation:** -``` -Transmitted Signal = Data Stream × Spreading Code × Scrambling Code -``` - -#### 2. Channelization Codes -**Orthogonal Variable Spreading Factor (OVSF) Codes:** -- Uses Walsh-Hadamard codes that are perfectly orthogonal -- Variable length codes support different data rates -- Spreading factors range from 4 to 512 -- Higher spreading factors = lower data rates but better interference resistance - -**Code Tree Structure:** -- Codes organized in a binary tree structure -- Parent-child codes are orthogonal to each other -- Enables flexible bandwidth allocation - -#### 3. Scrambling Codes -**Gold Codes:** -- Long pseudo-random sequences (2^18 - 1 = 262,143 chips) -- Used to separate different cells and users -- Provide quasi-orthogonal separation -- Enable soft handoff between cells - -#### 4. Power Control -**Fast Power Control:** -- Adjusts transmission power 1500 times per second -- Compensates for near-far effect and fading -- Critical for maintaining signal quality and minimizing interference -- Uses feedback from receiver to base station - -### Detailed Operation: - -#### Uplink (Mobile to Base Station): -1. **Voice/Data Encoding:** User data is channel coded and interleaved -2. **Spreading:** Data multiplied by user-specific OVSF channelization code -3. **Scrambling:** Result multiplied by mobile-specific scrambling code -4. **Power Control:** Transmission power adjusted based on base station commands -5. **Transmission:** Signal transmitted across 5 MHz bandwidth - -#### Downlink (Base Station to Mobile): -1. **Code Allocation:** Base station assigns OVSF codes to different users -2. **Spreading:** Each user's data spread with their assigned code -3. **Scrambling:** All users' signals scrambled with cell-specific code -4. **Combining:** All spread signals combined and transmitted simultaneously -5. **Reception:** Mobile uses correlation with its assigned codes to extract data - -### Advanced W-CDMA Features: - -#### 1. Rake Receiver -- **Multipath Combining:** Combines multiple delayed copies of the same signal -- **Finger Assignment:** Each "finger" processes a different multipath component -- **Diversity Gain:** Improves signal quality by combining multipath signals -- **Adaptive:** Automatically tracks and combines strongest multipath components - -#### 2. Soft Handoff -- **Multiple Base Stations:** Mobile simultaneously connected to multiple cells -- **Seamless Transition:** No break in communication during handoff -- **Macro Diversity:** Combines signals from multiple base stations -- **Quality Improvement:** Better coverage at cell boundaries - -#### 3. Variable Data Rates -- **Multi-Rate Services:** Supports different data rates simultaneously -- **Code Rate Adaptation:** Changes spreading factor based on required data rate -- **Dynamic Allocation:** Real-time adjustment of resources based on demand - -## Advantages of CDMA over TDM and FDM: - -### 1. Capacity Benefits -**Statistical Multiplexing:** -- Multiple users share the same spectrum simultaneously -- Capacity limited by interference rather than fixed time slots or frequencies -- Better utilization of available spectrum -- Graceful degradation as load increases - -**Voice Activity Factor:** -- Takes advantage of natural pauses in speech -- Users only interfere when actually transmitting -- Effective capacity gain of 2-3x over continuous transmission systems - -### 2. Security and Privacy -**Spread Spectrum Security:** -- Difficult to intercept or jam due to spreading -- Signals appear as noise to unauthorized receivers -- Each user has unique code sequence -- Inherent encryption through spreading process - -### 3. Quality Benefits -**Interference Averaging:** -- Each user sees interference from all other users as white noise -- Better error performance compared to single-user interference -- Soft capacity limit rather than hard blocking - -**Multipath Resistance:** -- Rake receivers exploit multipath propagation -- Converts multipath fading into diversity gain -- Better performance in urban environments - -### 4. Flexibility -**Dynamic Resource Allocation:** -- No fixed time slots or frequency assignments -- Adaptive data rates based on channel conditions and requirements -- Seamless integration of voice and data services -- Support for multimedia applications - -## Comparison with TDM and FDM: - -| Aspect | CDMA | TDM | FDM | -|--------|------|-----|-----| -| **Separation Method** | Unique codes | Time slots | Frequency bands | -| **Spectrum Efficiency** | High (statistical multiplexing) | Medium (fixed slots) | Low (guard bands) | -| **Capacity** | Soft limit, interference-limited | Hard limit, slot-limited | Hard limit, bandwidth-limited | -| **Near-Far Effect** | Critical issue, needs power control | Minimal impact | Minimal impact | -| **Multipath Handling** | Beneficial (Rake receiver) | Requires equalization | Requires equalization | -| **Security** | High (spreading codes) | Low (time-based) | Low (frequency-based) | -| **Implementation** | Complex (correlation, power control) | Medium (synchronization) | Simple (filtering) | - -## Sources and References: - -1. **3GPP Technical Specifications:** TS 25.213 (Spreading and modulation), TS 25.214 (Physical layer procedures) -2. **Viterbi, A.J.** "CDMA: Principles of Spread Spectrum Communication" - Addison-Wesley, 1995 -3. **Holma, H. and Toskala, A.** "WCDMA for UMTS: Radio Access for Third Generation Mobile Communications" - Wiley, 2004 -4. **IEEE Communications Magazine:** Various articles on CDMA evolution and implementation (1995-2005) -5. **ITU-R Recommendation M.1457:** "Detailed specifications of the radio interfaces of International Mobile Telecommunications-2000" - -**Key Insight:** W-CDMA represents a sophisticated evolution of CDMA technology that achieves superior spectrum efficiency and service flexibility compared to traditional TDM/FDM approaches by leveraging advanced signal processing, power control, and code design techniques, though at the cost of increased implementation complexity and the critical need for precise power management. - -### 2.2 Two-Dimensional Checksum (15%) - -**Given payload:** 1011 0110 1010 1011 - -**Objective:** Design a minimal-length two-dimensional checksum using even parity that can detect and correct any single-bit error. - -## Step 1: Determine Optimal Data Arrangement - -**Given data:** 16 bits total -**Arrangement:** For optimal checksum length, arrange in a rectangular matrix - -**Testing arrangements for minimal checksum overhead:** - -### Option 1: 4×4 arrangement -``` -1 0 1 1 | Row parity -0 1 1 0 | -1 0 1 0 | -1 0 1 1 | -───────── -Col parity -``` -- Row parity bits: 4 bits -- Column parity bits: 4 bits -- Total checksum: 8 bits (50% overhead) - -### Option 2: 2×8 arrangement -``` -1 0 1 1 0 1 1 0 | Row parity -1 0 1 0 1 0 1 1 | -───────────────── -Col parity (8 bits) -``` -- Row parity bits: 2 bits -- Column parity bits: 8 bits -- Total checksum: 10 bits (62.5% overhead) - -### Option 3: 8×2 arrangement -``` -1 0 | Row parity -1 1 | -0 1 | -1 0 | -1 0 | -1 0 | -1 0 | -1 1 | -────── -Col parity -``` -- Row parity bits: 8 bits -- Column parity bits: 2 bits -- Total checksum: 10 bits (62.5% overhead) - -**Optimal Choice:** 4×4 arrangement provides minimum checksum length (8 bits) - -## Step 2: Calculate Checksum Values - -### Data Matrix Arrangement: -``` -Position: (row, col) -1 0 1 1 (positions: 1,1 1,2 1,3 1,4) -0 1 1 0 (positions: 2,1 2,2 2,3 2,4) -1 0 1 0 (positions: 3,1 3,2 3,3 3,4) -1 0 1 1 (positions: 4,1 4,2 4,3 4,4) -``` - -### Row Parity Calculation (Even Parity): -- **Row 1:** 1⊕0⊕1⊕1 = 1 → **Row parity R₁ = 1** -- **Row 2:** 0⊕1⊕1⊕0 = 0 → **Row parity R₂ = 0** -- **Row 3:** 1⊕0⊕1⊕0 = 0 → **Row parity R₃ = 0** -- **Row 4:** 1⊕0⊕1⊕1 = 1 → **Row parity R₄ = 1** - -### Column Parity Calculation (Even Parity): -- **Col 1:** 1⊕0⊕1⊕1 = 1 → **Column parity C₁ = 1** -- **Col 2:** 0⊕1⊕0⊕0 = 1 → **Column parity C₂ = 1** -- **Col 3:** 1⊕1⊕1⊕1 = 0 → **Column parity C₃ = 0** -- **Col 4:** 1⊕0⊕0⊕1 = 0 → **Column parity C₄ = 0** - -### Complete Transmission Block: -``` -Data Matrix: Parity -1 0 1 1 R₁ = 1 -0 1 1 0 R₂ = 0 -1 0 1 0 R₃ = 0 -1 0 1 1 R₄ = 1 -───────── ───── -C₁C₂C₃C₄ P -1 1 0 0 -``` - -### Overall Parity Calculation: -**P = R₁⊕R₂⊕R₃⊕R₄ = 1⊕0⊕0⊕1 = 0** - -**Final Checksum Field:** **1100 1010 0** -- Row parities: 1010 -- Column parities: 1100 -- Overall parity: 0 -- **Total checksum length: 9 bits** - -## Step 3: Prove Minimality - -### Theoretical Lower Bound: -For single error correction capability with n data bits: -- **Hamming bound:** 2^k ≥ n + k + 1 (where k = parity bits) -- For n = 16: 2^k ≥ 16 + k + 1 = 17 + k -- Minimum k = 5 bits (since 2^5 = 32 ≥ 21) - -### Two-Dimensional Parity Analysis: -**Our scheme uses 9 bits vs theoretical minimum of 5 bits** - -**Justification for additional overhead:** -1. **Error Localization:** Two-dimensional parity provides exact error position -2. **Correction Capability:** Automatic correction without retransmission -3. **Implementation Simplicity:** Simple XOR operations vs complex syndrome decoding -4. **Practical Minimum:** For rectangular arrangement with integer dimensions - -### Alternative Arrangements Comparison: -- 1×16: Requires 1 + 16 + 1 = 18 parity bits -- 2×8: Requires 2 + 8 + 1 = 11 parity bits -- 4×4: Requires 4 + 4 + 1 = 9 parity bits ← **MINIMAL** -- 8×2: Requires 8 + 2 + 1 = 11 parity bits -- 16×1: Requires 16 + 1 + 1 = 18 parity bits - -**Proof of minimality:** 4×4 arrangement provides the shortest checksum length among all possible rectangular matrix arrangements. - -## Step 4: Prove Single-Bit Error Detection and Correction - -### Error Detection Mechanism: -1. **Row parity mismatch** indicates error in that row -2. **Column parity mismatch** indicates error in that column -3. **Intersection** of failing row and column identifies exact error position -4. **Overall parity** distinguishes between single-bit and parity-bit errors - -### Error Correction Examples: - -#### Example 1: Data bit error at position (2,3) -**Received data with error:** -``` -1 0 1 1 R₁ = 1 ✓ -0 1 0 0 R₂ = 1 ✗ (should be 0) -1 0 1 0 R₃ = 0 ✓ -1 0 1 1 R₄ = 1 ✓ -───────── -1 0 0 0 C₃ = 1 ✗ (should be 0) -``` - -**Error localization:** Row 2 fails, Column 3 fails → Error at (2,3) -**Correction:** Flip bit at position (2,3): 0 → 1 - -#### Example 2: Parity bit error (R₂ error) -**Received data with parity error:** -``` -1 0 1 1 R₁ = 1 ✓ -0 1 1 0 R₂ = 1 ✗ (should be 0) -1 0 1 0 R₃ = 0 ✓ -1 0 1 1 R₄ = 1 ✓ -───────── -1 1 0 0 All column parities ✓ -``` - -**Error detection:** Only row parity fails, columns are correct → Parity bit error -**Correction:** Correct R₂ parity bit - -### Comprehensive Error Coverage: -- **Data bit errors:** Detected by row AND column parity failures -- **Row parity errors:** Detected by row failure, columns correct -- **Column parity errors:** Detected by column failure, rows correct -- **Overall parity errors:** Detected by overall parity mismatch - -**Conclusion:** The two-dimensional checksum with 9-bit overhead (4×4 arrangement) provides minimal-length error detection and correction for the given 16-bit payload, with 100% single-bit error detection and correction capability. - -### 2.3 CSMA/CD Ethernet Analysis (20%) - -**Given:** -- 1 Gbps Ethernet -- 180 m cable with 3 repeaters -- Propagation speed: 2×10^8 m/sec -- Frame size: 1,024 bits -- Backoff intervals: multiples of 512 bits -- Repeater delay: 20-bit transmission time each -- Post-collision: A draws K=0, B draws K=1 -- Jam signal: 48 bits - -## Part (a): One-way propagation delay and delivery time - -### Step 1: Calculate one-way propagation delay - -**Physical propagation time:** -- Cable length: 180 m -- Propagation speed: 2×10^8 m/sec -- Physical delay = 180 m ÷ (2×10^8 m/sec) = 0.9 μs - -**Repeater delays:** -- 3 repeaters × 20-bit transmission time each -- At 1 Gbps: 1 bit time = 1 ns -- Total repeater delay = 3 × 20 bits × 1 ns/bit = 60 ns = 0.06 μs - -**Total one-way propagation delay:** -Total delay = Physical delay + Repeater delays -Total delay = 0.9 μs + 0.06 μs = **0.96 μs** - -### Step 2: Timeline analysis for collision scenario - -**t = 0**: Both A and B start transmitting simultaneously - -**Collision detection and jam signal:** -- Collision occurs immediately since both start at t=0 -- Jam signal duration: 48 bits = 48 ns -- Jam signal completes at t = 48 ns - -**Exponential backoff:** -- A draws K=0 → Backoff time = 0 × 512 bits = 0 bits = 0 ns -- B draws K=1 → Backoff time = 1 × 512 bits = 512 bits = 512 ns - -### Step 3: Calculate A's complete packet delivery time - -**Timeline for A's successful transmission:** -- t = 0: Initial collision occurs -- t = 48 ns: Jam signal ends -- t = 48 ns: A waits 0 ns (K=0), B waits 512 ns -- t = 48 ns: A starts retransmission (B still in backoff) -- t = 48 ns + 1,024 ns: A finishes transmission = 1,072 ns -- t = 1,072 ns + 960 ns: Signal propagates to B = 2,032 ns - -**A's packet is completely delivered at B at t = 2,032 ns = 2.032 μs** - -## Part (b): Switches instead of repeaters with 8-bit processing delay - -### Modified scenario: -- Only A has packet to send -- 3 switches replace repeaters -- Each switch: 8-bit processing delay + store-and-forward delay -- Store-and-forward delay = 1,024 bits (full packet) - -### Switch delay calculation: -**Per switch delay:** -- Processing delay: 8 bits = 8 ns -- Store-and-forward delay: 1,024 bits = 1,024 ns -- Total per switch: 8 + 1,024 = 1,032 ns - -**Total switch delays:** -- 3 switches × 1,032 ns = 3,096 ns = 3.096 μs - -**Physical propagation delay:** -- Same as before: 0.9 μs - -### Timeline for switch-based transmission: -- t = 0: A starts transmission -- t = 1,024 ns: A completes transmission to first switch -- t = 1,024 + 1,032 = 2,056 ns: First switch forwards -- t = 2,056 + 1,032 = 3,088 ns: Second switch forwards -- t = 3,088 + 1,032 = 4,120 ns: Third switch forwards -- t = 4,120 + 900 = 5,020 ns: Signal reaches B - -**A's packet is delivered at B at t = 5.020 μs** - -## Detailed CSMA/CD Analysis - -### Collision Detection Process: -1. **Initial Transmission**: Both nodes detect carrier as free and begin transmission -2. **Collision Occurrence**: Signals interfere when they meet on the medium -3. **Collision Detection**: Each node detects voltage levels exceeding normal thresholds -4. **Jam Signal**: Both nodes transmit 48-bit jam signal to ensure all nodes detect collision -5. **Backoff Algorithm**: Exponential backoff with binary exponential backoff (BEB) - -### Why RTT is Critical for CSMA/CD: -- **Collision Detection Window**: Must detect collision within one round-trip time -- **Minimum Frame Size**: Frame transmission time must exceed RTT to ensure collision detection -- **Network Diameter Limit**: RTT constrains maximum network size -- **Slot Time**: Backoff intervals based on worst-case RTT scenarios - -### Performance Considerations: -- **Efficiency**: η = 1/(1 + 6.44 × a) where a = RTT×bandwidth/frame_size -- **Throughput Degradation**: Higher collision rates reduce effective throughput -- **Network Utilization**: Optimal performance requires balanced frame size vs. propagation delay - -**Key Insight**: CSMA/CD performance is fundamentally limited by propagation delay, which determines collision detection capabilities and minimum frame sizes. The replacement of repeaters with switches eliminates collision domains but introduces store-and-forward delays that can significantly impact end-to-end latency for larger networks. - -### 2.4 802.11 RTS/CTS Transmission (10%) - -**Given:** -- 802.11 station configured to always use RTS/CTS -- 1024 bytes of data to transmit -- All other stations idle at t = 0 -- Station wants to transmit at t = 0 - -## 802.11 Frame Specifications - -**Standard 802.11 frame sizes and timing parameters:** -- **RTS frame:** 20 bytes (160 bits) -- **CTS frame:** 14 bytes (112 bits) -- **ACK frame:** 14 bytes (112 bits) -- **Data frame:** 1024 bytes payload + 28 bytes header = 1052 bytes (8416 bits) -- **SIFS (Short Interframe Space):** 10 μs -- **DIFS (Distributed Interframe Space):** 50 μs -- **Slot time:** 20 μs -- **Data rate:** 11 Mbps (802.11b standard assumption) - -## RTS/CTS Protocol Sequence - -### Step 1: Channel Access and RTS Transmission - -**t = 0:** Station wants to transmit -- **DIFS wait:** Station must wait DIFS before accessing idle channel -- **t = 0 to 50 μs:** Station waits DIFS period -- **t = 50 μs:** Station begins RTS transmission - -**RTS transmission time:** -- RTS frame size: 160 bits -- Transmission time = 160 bits ÷ 11 Mbps = 14.55 μs -- **t = 50 μs to 64.55 μs:** RTS transmission - -### Step 2: CTS Response - -**SIFS wait after RTS:** -- **t = 64.55 μs to 74.55 μs:** SIFS period (10 μs) -- **t = 74.55 μs:** Access Point begins CTS transmission - -**CTS transmission time:** -- CTS frame size: 112 bits -- Transmission time = 112 bits ÷ 11 Mbps = 10.18 μs -- **t = 74.55 μs to 84.73 μs:** CTS transmission - -### Step 3: Data Transmission - -**SIFS wait after CTS:** -- **t = 84.73 μs to 94.73 μs:** SIFS period (10 μs) -- **t = 94.73 μs:** Station begins data transmission - -**Data frame transmission time:** -- Data frame size: 8416 bits (1024 bytes payload + 28 bytes header) -- Transmission time = 8416 bits ÷ 11 Mbps = 765.09 μs -- **t = 94.73 μs to 859.82 μs:** Data transmission - -**Station completes transmission at t = 859.82 μs** - -### Step 4: ACK Reception - -**SIFS wait after data:** -- **t = 859.82 μs to 869.82 μs:** SIFS period (10 μs) -- **t = 869.82 μs:** Access Point begins ACK transmission - -**ACK transmission time:** -- ACK frame size: 112 bits -- Transmission time = 112 bits ÷ 11 Mbps = 10.18 μs -- **t = 869.82 μs to 880 μs:** ACK transmission - -**Station receives acknowledgment at t = 880 μs** - -## Complete Timeline Summary - -| Time (μs) | Event | Duration (μs) | -|-----------|-------|---------------| -| 0 - 50 | DIFS wait | 50.00 | -| 50 - 64.55 | RTS transmission | 14.55 | -| 64.55 - 74.55 | SIFS wait | 10.00 | -| 74.55 - 84.73 | CTS transmission | 10.18 | -| 84.73 - 94.73 | SIFS wait | 10.00 | -| 94.73 - 859.82 | Data transmission | 765.09 | -| 859.82 - 869.82 | SIFS wait | 10.00 | -| 869.82 - 880.00 | ACK transmission | 10.18 | - -## Answers to Questions - -### When does the station complete transmission? -**The station completes transmission at t = 859.82 μs** - -This represents the end of the data frame transmission. The actual data payload has been fully transmitted to the access point. - -### When can the station receive the acknowledgment? -**The station receives the acknowledgment at t = 880.00 μs** - -This marks the successful completion of the entire RTS/CTS/Data/ACK sequence. - -## Protocol Analysis - -### RTS/CTS Benefits Demonstrated: -1. **Hidden Node Protection:** RTS/CTS sequence reserves the channel for the entire data transmission -2. **Collision Avoidance:** Other stations hear either RTS or CTS and defer transmission -3. **Channel Reservation:** Duration field in RTS/CTS frames reserves channel for complete sequence -4. **Efficiency for Large Frames:** Overhead is justified for larger data frames like the 1024-byte payload - -### Timing Overhead Analysis: -- **Total sequence time:** 880 μs -- **Actual data transmission time:** 765.09 μs -- **Protocol overhead time:** 114.91 μs (13.1% overhead) -- **Overhead breakdown:** - - DIFS: 50 μs (5.7%) - - RTS/CTS frames: 24.73 μs (2.8%) - - SIFS periods: 30 μs (3.4%) - - ACK frame: 10.18 μs (1.2%) - -### Performance Considerations: -- **Efficiency:** 86.9% channel utilization for data transmission -- **Latency:** 880 μs total time for 1024-byte frame transmission -- **Throughput:** Effective data rate ≈ 9.3 Mbps (considering protocol overhead) - -**Key Insight:** The RTS/CTS mechanism trades modest protocol overhead (13.1%) for robust collision avoidance and hidden node protection, making it particularly valuable in wireless environments with potential hidden nodes or high collision probability. - -### 2.5 Bluetooth Frame Format Analysis (10%) - -## Bluetooth Technology Overview - -Bluetooth is a short-range wireless communication technology operating in the 2.4 GHz ISM band, designed for personal area networks (PANs). Originally developed by Ericsson in 1994, Bluetooth uses frequency-hopping spread spectrum (FHSS) and time division duplex (TDD) to enable multiple devices to communicate within a small coverage area. - -## Bluetooth Frame Format Structure - -### Basic Frame Components - -Bluetooth frames consist of three main components arranged in the following structure: - -``` -[Access Code] [Header] [Payload] - 72 bits 54 bits 0-2745 bits -``` - -### 1. Access Code (72 bits) -The Access Code serves multiple critical functions: - -**Structure:** -- **Preamble:** 4 bits (fixed pattern for synchronization) -- **Sync Word:** 64 bits (derived from master device's clock and ID) -- **Trailer:** 4 bits (optional, used for better correlation) - -**Functions:** -- **Device Identification:** Uniquely identifies the piconet master -- **Synchronization:** Enables receiver clock and frequency synchronization -- **Packet Detection:** Allows devices to distinguish Bluetooth signals from noise -- **Piconet Separation:** Different piconets use different access codes - -**Types of Access Codes:** -- **Channel Access Code (CAC):** Used for regular data transmission -- **Device Access Code (DAC):** Used during inquiry and paging procedures -- **Inquiry Access Code (IAC):** Used for device discovery - -### 2. Header (54 bits) -The Header contains control and addressing information: - -**Header Fields:** -- **AM_ADDR (3 bits):** Active Member Address - identifies active devices in piconet -- **TYPE (4 bits):** Packet type specification -- **FLOW (1 bit):** Flow control for stop-and-wait ARQ -- **ARQN (1 bit):** Automatic Repeat Request acknowledgment -- **SEQN (1 bit):** Sequence number for packet ordering -- **HEC (8 bits):** Header Error Check for error detection - -**Header Encoding:** -- The 18-bit header is encoded with a 1/3 rate FEC (Forward Error Correction) -- Results in 54 transmitted bits for enhanced error protection -- Uses repetition coding where each bit is repeated three times - -### 3. Payload (0-2745 bits) -The Payload carries actual user data and varies by packet type: - -**Payload Structure:** -- **Payload Header:** Contains length and flow control information -- **Payload Body:** User data (voice, text, files, etc.) -- **CRC (Cyclic Redundancy Check):** Error detection for payload data - -## Detailed Frame Analysis - -### Packet Types and Payload Sizes - -**Control Packets:** -- **ID packets:** 0 bits payload (only Access Code and Header) -- **NULL packets:** 0 bits payload (used for acknowledgment) -- **POLL packets:** 0 bits payload (used to poll slave devices) - -**SCO (Synchronous Connection-Oriented) Packets:** -- **HV1:** 80 bits payload (voice data, 1/3 FEC protection) -- **HV2:** 160 bits payload (voice data, 2/3 FEC protection) -- **HV3:** 240 bits payload (voice data, no FEC protection) - -**ACL (Asynchronous Connectionless) Packets:** -- **DM1:** 136 bits payload (medium data rate, 2/3 FEC) -- **DH1:** 240 bits payload (high data rate, no FEC) -- **DM3:** 968 bits payload (medium data rate, 2/3 FEC) -- **DH3:** 1464 bits payload (high data rate, no FEC) -- **DM5:** 1784 bits payload (medium data rate, 2/3 FEC) -- **DH5:** 2744 bits payload (high data rate, no FEC) - -### Frame Features and Characteristics - -#### 1. Error Protection Mechanisms -**Forward Error Correction (FEC):** -- **1/3 Rate FEC:** Each bit repeated three times (used for header and some payloads) -- **2/3 Rate FEC:** Uses (15,10) shortened Hamming code -- **ARQ (Automatic Repeat Request):** Stop-and-wait protocol for reliable transmission - -**Error Detection:** -- **Header Error Check (HEC):** 8-bit CRC for header protection -- **Payload CRC:** 16-bit CRC for payload data integrity - -#### 2. Addressing and Flow Control -**Active Member Address (AM_ADDR):** -- **3-bit field:** Supports up to 7 active devices (0 reserved for broadcast) -- **Temporary Assignment:** Assigned by master when device becomes active -- **Limitation Factor:** This is the primary reason for the 8-device limit - -**Flow Control:** -- **FLOW bit:** Implements stop-and-wait flow control -- **ARQN/SEQN:** Provides reliable data transfer with acknowledgments - -#### 3. Frequency Hopping Integration -- **Access Code synchronization:** Enables proper frequency hop timing -- **Hop Selection:** Based on master's clock and device ID -- **79 Frequencies:** Uses 79 different frequencies in 2.4 GHz band -- **1600 hops/second:** Changes frequency every 625 μs - -## Analysis of Eight-Device Limitation - -### Why is Bluetooth Limited to Eight Active Nodes? - -The limitation to eight active nodes in a Bluetooth piconet is **directly imposed by the frame format**, specifically the AM_ADDR field: - -#### 1. AM_ADDR Field Constraint -- **Field Size:** 3 bits in the frame header -- **Possible Values:** 2³ = 8 possible combinations (000 to 111) -- **Reserved Value:** 000 is reserved for broadcast messages -- **Available Addresses:** 7 addresses available for individual devices (001 to 111) -- **Total Active Devices:** 7 active slaves + 1 master = 8 total devices - -#### 2. Frame Format Impact -**Why the AM_ADDR field is this small:** -- **Header Size Optimization:** Bluetooth was designed for low-power, low-complexity devices -- **Overhead Minimization:** Smaller addressing reduces frame overhead -- **Processing Simplicity:** 3-bit addresses simplify hardware implementation -- **Battery Life:** Shorter frames mean less transmission time and lower power consumption - -#### 3. Alternative Addressing Mechanisms -**Parked Devices:** -- Use different addressing scheme with 8-bit Parked Member Address (PM_ADDR) -- Can support up to 255 parked devices -- Parked devices cannot actively communicate without becoming active -- Must transition from parked to active state to participate in data exchange - -**Device Access Code (DAC):** -- Each device has unique 48-bit BD_ADDR (Bluetooth Device Address) -- Used during connection establishment, not regular data transmission -- Would create excessive overhead if used in every frame - -### Comparison with Other Wireless Technologies - -| Technology | Max Active Devices | Addressing Mechanism | Address Size | -|------------|-------------------|---------------------|--------------| -| **Bluetooth** | 8 (7 active slaves) | AM_ADDR in frame header | 3 bits | -| **Wi-Fi** | 2007+ devices | MAC addresses | 48 bits | -| **Zigbee** | 65,000+ devices | Network + device addresses | 16 + 64 bits | - -## Limitations and Design Trade-offs - -### Frame Format Limitations - -#### 1. Addressing Constraints -**Limited Active Devices:** -- Only 8 devices can actively participate in data transmission -- Additional devices must be in parked or standby states -- Requires complex state management for larger networks - -**No Mesh Networking:** -- Frame format designed for star topology only -- Master-slave architecture inherent in addressing scheme -- Cannot support native mesh networking without protocol modifications - -#### 2. Overhead Considerations -**High Overhead for Small Payloads:** -- Access Code (72 bits) and Header (54 bits) = 126 bits fixed overhead -- For small payloads, overhead percentage is very high -- Example: ID packet has 126 bits overhead with 0 bits payload - -**FEC Redundancy:** -- 1/3 FEC triples header size (18 → 54 bits) -- Trades bandwidth efficiency for error resilience -- Appropriate for noisy 2.4 GHz environment - -#### 3. Scalability Issues -**Piconet Size Limitation:** -- Inherently limits network scalability -- Requires scatternet formation for larger networks -- Complex inter-piconet communication protocols needed - -**Master Bottleneck:** -- All communication must pass through master device -- Single point of failure for the entire piconet -- Master must manage all slaves' timing and addressing - -### Design Strengths - -#### 1. Error Resilience -**Robust Error Protection:** -- Multiple layers of error detection and correction -- Suitable for industrial and interference-prone environments -- Automatic retransmission ensures reliability - -#### 2. Low Power Design -**Efficient Power Management:** -- Short frames reduce transmission time -- Simple addressing minimizes processing requirements -- Frequency hopping provides interference resistance - -#### 3. Simplicity -**Implementation Efficiency:** -- Simple frame structure reduces hardware complexity -- Fixed field sizes enable fast processing -- Minimal protocol overhead for basic operations - -## Conclusion - -**The Bluetooth frame format reflects design priorities of the 1990s:** low power consumption, simple implementation, and reliable short-range communication. The eight-device limitation is a **direct consequence** of the 3-bit AM_ADDR field in the frame header, which was chosen to minimize overhead and complexity. - -**Key Trade-offs:** -- **Simplicity vs. Scalability:** Chose simple addressing over large network support -- **Reliability vs. Efficiency:** Emphasized error protection over bandwidth efficiency -- **Power vs. Performance:** Optimized for battery life over high data rates - -**Modern Context:** While these limitations restrict Bluetooth's use in large-scale networking applications, they make it ideal for personal area networks, IoT devices, and applications requiring reliable, low-power, short-range communication. The frame format limitations have been partially addressed in newer Bluetooth versions (BLE, mesh networking) while maintaining backward compatibility with the original design principles.
\ No newline at end of file |