Comprehensive Study Notes on Switched Networks and Network Layer Operations

Taxonomy and Overview of Switched Networks

• Definition of Switching: Switches are network devices capable of creating temporary connections between two or more devices linked to the switch. In a switched network, specific internal nodes act as switches to route data, while external nodes connect to end systems (such as computers, telephones, or terminal stations).

• Taxonomy of Switched Networks: Switched networks are broadly categorized into three distinct architectures based on their operational switching mechanisms:

  • Circuit-Switched Networks: Physical links are allocated to create dedicated end-to-end connections for the entire duration of communication.

  • Packet-Switched Networks: Messages are divided into discrete units called packets, which are individually routed across the network. Packet-switched networks are further divided into:

  • Datagram Networks: Connectionless operation where each packet is routed independently based on destination address.

  • Virtual-Circuit Networks: Connection-oriented operation where a logical preplanned path is established prior to packet transmission.

  • Message-Switched Networks: Complete messages are transmitted as a single unit from switch to switch using store-and-forward mechanisms.

Circuit-Switched Networks

• Fundamental Architecture: A circuit-switched network consists of a set of interconnected switches connected by physical links. Each physical link is divided into $n$ channels.

• Channel Multiplexing Techniques: Division of a physical link into $n$ individual channels is achieved using physical layer multiplexing techniques:

  • Frequency-Division Multiplexing (FDM): Bandwidth is divided into distinct frequency bands.

  • Time-Division Multiplexing (TDM): Time is divided into recurring time slots.

• Operational Phases: Communication over a circuit-switched network requires three mandatory consecutive phases:

  1. Establishment (Setup Phase): A dedicated end-to-end circuit (path) across intermediate switches is reserved between the sender and receiver before any data transfer begins.

  2. Data Transfer Phase: Data flows continuously through the dedicated established circuit from source to destination.

  3. Disconnect (Teardown Phase): Dedicated resources across links and switches are released after data transfer is completed, making the channels available for other connections.

• Resource Allocation and Efficiency: In circuit switching, network resources (such as channel bandwidth and switch capacity) are reserved during the setup phase and remain strictly dedicated for the entire duration of the data transfer phase until teardown. Because resources remain reserved even during periods of silence or idle transmission, circuit switching is inefficient compared to packet-switched methods.

• Application: Physical layer switching in traditional public switched telephone networks (PSTN) utilizes the circuit-switching approach.

• Mathematical Formulation of Circuit-Switched Delay:

  • Transmission Delay ($T_D$): Time required to push data bits onto the physical medium.

  • Propagation Delay ($P_D$): Time required for a signal bit to propagate across the physical medium.

  • Setup Time ($ST$): Includes the request packet transmission and propagation delays ($T_s + P_s$) plus acknowledgment packet transmission and propagation delays ($T_D + P_D$):     $ST = T_s + P_s + T_D + P_D$

  • Data Transfer Time ($DT$): Sum of data transmission time ($T_{\text{data}}$) and data propagation time ($P_{\text{data}}$):     $DT = T_{\text{data}} + P_{\text{data}}$

  • Disconnect Time ($DCT$): Combined transmission delay and propagation delay of the teardown signal:     $DCT = T_D + P_D$

  • Total Delay: Calculated as the sum of setup, transfer, and disconnect delays (ignoring intermediate switch processing time):     $\text{Total Delay} = ST + DT + DCT$

Packet-Switched Networks

• Packetization Principles: If a message is transmitted across a packet-switched network, it must be divided into smaller individual units called packets of fixed or variable size. The exact packet size is determined by network specifications and governing protocols.

• Datagram Networks:

  • Independent Routing: Each packet is treated as an independent datagram, completely isolated from other packets belonging to the same message.

  • Dynamic Path Selection: Packets can take any available practical route through the network switches (routers).

  • Delivery Characteristics: Datagrams may arrive at the destination out of sequence, experience varying delays, or be lost entirely.

  • End-System Responsibility: It is strictly the responsibility of the receiving end-system protocols to re-order out-of-sequence packets and recover missing data.

  • Addressing: Switches in a datagram network are traditionally referred to as routers. The destination address in the header of a datagram remains completely unchanged throughout its entire journey across the network.

• Routing Table Operation in Datagram Switches:

  • Every router in a datagram network maintains a dynamic routing table that maps a packet's destination address to a specific outgoing port.

• Example Routing Table entries:

  • Destination address $1232$ \rightarrow Output port $1$

  • Destination address $4150$ \rightarrow Output port $2$

  • Destination address $9130$ \rightarrow Output port $3$

  • Delay in Datagram Networks:

• Datagram delay includes transmission delays ($T$), propagation delays ($P$), and buffer waiting times ($w_i$) at intermediate switches.

• For a path traversing 3 switches (3 hops), total delay is given by:     $\text{Total Delay} = 3 \times T + 3 \times P + w_1 + w_2$

• Virtual-Circuit Networks:

  • Preplanned Path: A logical preplanned route is established before any data packets are sent.

  • Signaling Handshake: Connection setup is accomplished using explicit call-request and call-accept signaling packets.

  • Addressing & Identifiers: Instead of carrying the full global destination address in every packet header, each packet carries a small local Virtual Circuit Identifier (VCI) or tag. Switches inspect and update the tag at each hop.

Network Delay Components and Formulas

• Network Delay Definition: Network delay refers to the total duration of time required for a data bit or packet to travel from a source node (Point A) to a destination node (Point B).

• Four Primary Components of Network Delay:

  1. Propagation Delay: The time required for a single bit to travel from one end of a physical link to the other. Propagation delay depends strictly on the physical distance ($D$) between sender and receiver and the propagation speed ($S$) of the signal in the medium:      $\text{Propagation Delay} = \frac{D}{S}$

  2. Transmission Delay: The time required to transmit all bits of a packet onto the outgoing link medium. Transmission delay depends on packet length ($L$) in bits and link capacity or bandwidth ($B$) in bits per second ($ ext{bps}$):      $\text{Transmission Delay} = \frac{L}{B}$

  3. Queuing Delay: The time a packet spends sitting in switch buffers/queues waiting to be processed and transmitted. Queuing delay varies dynamically based on incoming packet arrival rate, outgoing link transmission capacity, and traffic congestion.

  4. Processing Delay: The time required by a switch or router to process the packet header, check for bit-level errors, and determine the output port from the routing table. Processing delay depends directly on the processor speed of the switching hardware.

Computational Examples and Quantitative Exercises

• Example 1: Propagation Delay vs. Transmission Delay Calculation

  • Parameters:

  • Distance between Source A and Destination B ($D$) = $48{,}000\,\text{km} = 48{,}000 \times 10^3\,\text{m} = 4.8 \times 10^7\,\text{m}$.

  • Data size ($L$) = $1500\,\text{bytes} = 1500 \times 8\,\text{bits} = 12{,}000\,\text{bits}$.

  • Transmission Rate / Bandwidth ($B$) = $100\,\text{Mbps} = 100 \times 10^6\,\text{bps}$.

  • Propagation Speed ($S$) = $2.4 \times 10^8\,\text{m/s}$.

  • Calculations:     $\text{Propagation Delay} = \frac{48000 \times 10^3\,\text{m}}{2.4 \times 10^8\,\text{m/s}} = 0.200\,\text{s} = 200\,\text{ms}$     $\text{Transmission Delay} = \frac{1500 \times 8\,\text{bits}}{100 \times 10^6\,\text{bps}} = 0.00012\,\text{s} = 0.12\,\text{ms}$

• Example 2: Store-and-Forward Transfer Delay Across Switches

  • Parameters:

  • Sender and Receiver separated by 1 store-and-forward switch (2 links total).

  • Link Capacity ($B$) = $1\,\text{Gbps} = 10^9\,\text{bps}$.

  • Packet Size ($L$) = $5000\,\text{bits}$.

  • Per-link Propagation Delay ($P$) = $10\,\mu\text{s}$.

  • Switch Operation: Store-and-forward (starts forwarding only after receiving the complete packet). Queuing delay is ignored.

  • Single Switch Calculation (2 links, 1 switch):     $\text{Transmission Time per Link} = \frac{5000\,\text{bits}}{10^9\,\text{bps}} = 5 \times 10^{-6}\,\text{s} = 5\,\mu\text{s}$     $\text{Total Transfer Delay} = 2 \times \text{Transmission Delay} + 2 \times \text{Propagation Delay}$     $\text{Total Transfer Delay} = 5\,\mu\text{s} + 5\,\mu\text{s} + 10\,\mu\text{s} + 10\,\mu\text{s} = 30\,\mu\text{s}$

  • Three Switches Extension Calculation (4 links, 3 switches):     $\text{Total Transfer Delay} = 4 \times \text{Transmission Delay} + 4 \times \text{Propagation Delay}$     $\text{Total Transfer Delay} = (4 \times 5\,\mu\text{s}) + (4 \times 10\,\mu\text{s}) = 20\,\mu\text{s} + 40\,\mu\text{s} = 60\,\mu\text{s}$

• Example 3: Datagram Output Port Lookup Exercise

  • Given a switch routing table with the following port mappings:

  • Destination Address $1233$ \rightarrow Output Port $3$

  • Destination Address $1456$ \rightarrow Output Port $2$

  • Destination Address $3255$ \rightarrow Output Port $1$

  • Destination Address $4470$ \rightarrow Output Port $4$

  • Destination Address $7176$ \rightarrow Output Port $2$

  • Destination Address $8766$ \rightarrow Output Port $3$

  • Destination Address $9144$ \rightarrow Output Port $2$

  • Routing Output Results for incoming packets:

  • Packet 1 (Destination Address $7176$) \rightarrow Output Port $2$

  • Packet 2 (Destination Address $1233$) \rightarrow Output Port $3$

  • Packet 3 (Destination Address $8766$) \rightarrow Output Port $3$

  • Packet 4 (Destination Address $9144$) \rightarrow Output Port $2$

• Example 4: Relative Arrival Times and Ordering of Multiple Datagrams

  • System Conditions:

  • Five equal-sized datagrams leave the source at time $t = 0\,\text{ms}$ (transmission time is negligible).

  • Signal Propagation Speed ($S$) = $2 \times 10^8\,\text{m/s}$.

  • Per-switch delays (combined waiting and processing delays):

    • Switch 1 Delay = $3\,\text{ms}$

    • Switch 2 Delay = $10\,\text{ms}$

    • Switch 3 Delay = $20\,\text{ms}$

    • Switch 4 Delay = $7\,\text{ms}$

    • Switch 5 Delay = $20\,\text{ms}$

  • Path Table Data & Total Delay Calculations:

  • Datagram 1: Path Length = $3200\,\text{km}$; Visited Switches = $1, 3, 5$.       $\text{Propagation Time} = \frac{3200 \times 10^3\,\text{m}}{2 \times 10^8\,\text{m/s}} = 0.016\,\text{s} = 16.0\,\text{ms}$       $\text{Switch Delays} = 3\,\text{ms} + 20\,\text{ms} + 20\,\text{ms} = 43.0\,\text{ms}$       $\text{Total Delay}_1 = 16.0\,\text{ms} + 43.0\,\text{ms} = 59.0\,\text{ms}$

  • Datagram 2: Path Length = $11{,}700\,\text{km}$; Visited Switches = $1, 2, 5$.       $\text{Propagation Time} = \frac{11700 \times 10^3\,\text{m}}{2 \times 10^8\,\text{m/s}} = 0.0585\,\text{s} = 58.5\,\text{ms}$       $\text{Switch Delays} = 3\,\text{ms} + 10\,\text{ms} + 20\,\text{ms} = 33.0\,\text{ms}$       $\text{Total Delay}_2 = 58.5\,\text{ms} + 33.0\,\text{ms} = 91.5\,\text{ms}$

  • Datagram 3: Path Length = $12{,}200\,\text{km}$; Visited Switches = $1, 2, 3, 5$.       $\text{Propagation Time} = \frac{12200 \times 10^3\,\text{m}}{2 \times 10^8\,\text{m/s}} = 0.061\,\text{s} = 61.0\,\text{ms}$       $\text{Switch Delays} = 3\,\text{ms} + 10\,\text{ms} + 20\,\text{ms} + 20\,\text{ms} = 53.0\,\text{ms}$       $\text{Total Delay}_3 = 61.0\,\text{ms} + 53.0\,\text{ms} = 114.0\,\text{ms}$

  • Datagram 4: Path Length = $10{,}200\,\text{km}$; Visited Switches = $1, 4, 5$.       $\text{Propagation Time} = \frac{10200 \times 10^3\,\text{m}}{2 \times 10^8\,\text{m/s}} = 0.051\,\text{s} = 51.0\,\text{ms}$       $\text{Switch Delays} = 3\,\text{ms} + 7\,\text{ms} + 20\,\text{ms} = 30.0\,\text{ms}$       $\text{Total Delay}_4 = 51.0\,\text{ms} + 30.0\,\text{ms} = 81.0\,\text{ms}$

  • Datagram 5: Path Length = $10{,}700\,\text{km}$; Visited Switches = $1, 4, 3, 5$.       $\text{Propagation Time} = \frac{10700 \times 10^3\,\text{m}}{2 \times 10^8\,\text{m/s}} = 0.0535\,\text{s} = 53.5\,\text{ms}$       $\text{Switch Delays} = 3\,\text{ms} + 7\,\text{ms} + 20\,\text{ms} + 20\,\text{ms} = 50.0\,\text{ms}$       $\text{Total Delay}_5 = 53.5\,\text{ms} + 50.0\,\text{ms} = 103.5\,\text{ms}$

  • Arrival Order (Sorted by Total Delay):

  1. Datagram 1 ($59.0\,\text{ms}$) — Arrives 1st (Earliest)

  2. Datagram 4 ($81.0\,\text{ms}$) — Arrives 2nd

  3. Datagram 2 ($91.5\,\text{ms}$) — Arrives 3rd

  4. Datagram 5 ($103.5\,\text{ms}$) — Arrives 4th

  5. Datagram 3 ($114.0\,\text{ms}$) — Arrives 5th (Last)

Network Layer Services

• Core Functions of Network Layer: Logical addressing, source computer packet processing, intermediate router forwarding, and destination computer reassembly.

• Services Provided at the Source Computer:

1. Packetize: Accepts upper layer data (Data, Length Len, Destination Logical Address DA, Protocol ID PI, Service Type ST) and encapsulates it into a Network Layer datagram.

2. Find Next-Hop Logical Address: Consults the Routing Table using Destination Address (DA) to obtain the Next-Hop Logical Address (NA).

3. Find Next-Hop MAC Address: Uses Address Resolution Protocol (ARP) to map the Next-Hop Logical Address (NA) to a Next-Hop physical MAC address (MAC).

4. Fragment: Queries the Maximum Transfer Unit (MTU) Table using Link ID to get MTU limits. Breaks the datagram into smaller fragments if the datagram size exceeds the link MTU, attaching datagram header (H) and MAC information to each fragment before passing to the Data Link Layer.

• Processing at Each Intermediate Router:

1. Receives incoming frame from the Data Link Layer of the incoming interface.

2. Validates datagram integrity (Valid datagram?). If invalid ([false]), discards the datagram.

3. If valid ([true]), determines Next-Hop Logical Address (NA) by looking up Destination Address (DA) in the Routing Table.

4. Obtains Next-Hop Physical Address (MAC) using ARP lookup.

5. Checks outgoing link MTU table; fragments datagram if required, appends header H and MAC address, and passes fragments to the Data Link Layer of the outgoing interface.

• Processing at the Destination Computer:

1. Receives frame from Data Link Layer.

2. Verifies datagram validity (Valid datagram?). If invalid ([false]), discards the datagram.

3. Depacketize: Extracts datagram fragments and stores payload data for each fragment.

4. Fragment Reassembly:

   • Evaluates fragment completeness (All fragments arrived?).

   • If incomplete ([false]), checks whether the reassembly timer has expired (Reassembly timer expired?).

     • If timer expired ([true]), discards all received fragments.

     • If timer active ([false]), waits for remaining fragments to arrive.

   • If complete ([true]), reassembles all payload fragments into unified upper-layer data and passes it up to Transport or higher-layer processes.