776  Network Topologies: Analysis and Metrics

776.1 Learning Objectives

By the end of this section, you will be able to:

• Apply Graph Theory to Networks: Use connectivity, node degree, and path length metrics
• Analyze Failure Modes: Identify single points of failure and calculate availability
• Evaluate Routing Overhead: Compare routing protocol bandwidth consumption across topologies
• Calculate Scalability: Determine connection counts and bandwidth requirements
• Design for Fault Tolerance: Apply redundancy strategies to meet reliability targets

NoteRelated Chapters

Deep Dives: - Network Topologies Overview - Chapter index and navigation - Basic Topology Types - Fundamental topology concepts - Communication Patterns - Data flow patterns - Hybrid Design - Real-world hybrid topologies

Advanced Topics: - Routing Fundamentals - Routing protocols and algorithms - WSN Fundamentals - Wireless sensor topologies

776.2 Prerequisites

Before diving into this chapter, you should be familiar with:

• Basic Topology Types: Understanding of star, bus, ring, and mesh topologies
• Basic Mathematics: Familiarity with logarithms and combinatorics helps with scalability calculations

---

776.3 Graph Theory Fundamentals

Network topologies can be analyzed using graph theory, where devices are nodes and connections are edges. Understanding these mathematical properties helps predict network behavior.

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'background': '#ffffff', 'mainBkg': '#2C3E50', 'secondBkg': '#16A085', 'tertiaryBkg': '#E67E22'}}}%%
graph TD
    subgraph Star["Star: k=1, Avg Path=2"]
        S_Hub["Hub<br/>degree=4"] --- S1["D1<br/>deg=1"]
        S_Hub --- S2["D2<br/>deg=1"]
        S_Hub --- S3["D3<br/>deg=1"]
        S_Hub --- S4["D4<br/>deg=1"]
        S_Eq["Edges: n-1 = 4<br/>Diameter: 2"]
    end

    subgraph Mesh["Full Mesh: k=3, Avg Path=1"]
        M1["N1<br/>deg=3"] --- M2["N2<br/>deg=3"]
        M1 --- M3["N3<br/>deg=3"]
        M1 --- M4["N4<br/>deg=3"]
        M2 --- M3
        M2 --- M4
        M3 --- M4
        M_Eq["Edges: n*(n-1)/2 = 6<br/>Diameter: 1"]
    end

    subgraph Partial["Partial Mesh: k=2"]
        P1["Core<br/>deg=3"] --- P2["N2<br/>deg=2"]
        P1 --- P3["N3<br/>deg=2"]
        P1 --- P4["N4<br/>deg=3"]
        P2 --- P4
        P3 --- P4
        P_Eq["Edges: 5<br/>Redundant paths"]
    end

    subgraph Tree["Tree: k=1, Depth=2"]
        T1["Root<br/>deg=2"] --- T2["L1a<br/>deg=3"]
        T1 --- T3["L1b<br/>deg=3"]
        T2 --- T4["Leaf<br/>deg=1"]
        T2 --- T5["Leaf<br/>deg=1"]
        T3 --- T6["Leaf<br/>deg=1"]
        T3 --- T7["Leaf<br/>deg=1"]
        T_Eq["Edges: n-1 = 6<br/>Max depth: log2(n)"]
    end

    classDef hubStyle fill:#2C3E50,stroke:#E67E22,stroke-width:4px,color:#fff
    classDef deviceStyle fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef meshStyle fill:#E67E22,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef treeStyle fill:#7F8C8D,stroke:#2C3E50,stroke-width:2px,color:#fff

    class S_Hub hubStyle
    class S1,S2,S3,S4 deviceStyle
    class M1,M2,M3,M4 meshStyle
    class P1,P2,P3,P4 meshStyle
    class T1,T2,T3,T4,T5,T6,T7 treeStyle

Figure 776.1: Graph theory analysis of network topologies. Node degree: number of connections per device. Connectivity (k): minimum nodes to remove to disconnect network. Diameter: maximum path length between any two nodes. Star has k=1 (single point of failure), mesh has k=n-1 (maximum resilience).

776.3.1 Key Graph Metrics

Topology	Edges (n nodes)	Avg Node Degree	Connectivity (k)	Diameter	Path Length
Star	n - 1	~2	1	2	2.0 hops
Bus	n - 1	~2	1	n - 1	(n+1)/2
Ring	n	2	2	floor(n/2)	n/4 hops
Full Mesh	n(n-1)/2	n - 1	n - 1	1	1.0 hop
Tree (binary)	n - 1	~3	1	2*log2(n)	log2(n)
Partial Mesh	2n to n^2/4	2-6	2-4	2-4	1.5-2.5 hops

776.3.2 Scalability Impact

Understanding how topologies scale is critical for IoT deployments:

• Star: O(n) connections - scales linearly, but hub bandwidth is bottleneck
• Full Mesh: O(n^2) connections - for 100 nodes = 4,950 edges (unmanageable)
• Partial Mesh: O(n*k) where k = avg degree - for 100 nodes with k=4 = 200 edges (feasible)
• Tree: O(n) connections - scales well, but depth increases as O(log n)

Real Numbers:

Nodes	Full Mesh Connections	Partial Mesh (k=4)	Reduction
10	45	20	56%
50	1,225	100	92%
100	4,950	200	96%
500	124,750	1,000	99.2%

---

776.4 Failure Analysis and Fault Tolerance

Different topologies respond dramatically differently to node and link failures. Understanding failure modes is critical for IoT reliability engineering.

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'background': '#ffffff', 'mainBkg': '#2C3E50', 'secondBkg': '#16A085', 'tertiaryBkg': '#E67E22'}}}%%
graph TD
    subgraph Normal["Normal Operation"]
        N_Star["Star<br/>All connected<br/>via hub"]
        N_Ring["Ring<br/>Bidirectional<br/>paths"]
        N_Mesh["Mesh<br/>Multiple<br/>paths"]
    end

    subgraph NodeFail["Hub/Node Failure"]
        F_Star["Star Hub Fails<br/>100% outage<br/>All devices isolated"]
        F_Ring["Ring Node Fails<br/>Linear topology<br/>2x latency"]
        F_Mesh["Mesh Node Fails<br/>Routes around<br/>less than 5% impact"]
    end

    subgraph LinkFail["Link Failure"]
        L_Star["Star Link Fails<br/>1 device lost<br/>25% capacity"]
        L_Ring["Ring Link Fails<br/>Network partitions<br/>50% isolated"]
        L_Mesh["Mesh Link Fails<br/>Alternate path<br/>less than 5% latency increase"]
    end

    subgraph Metrics["Reliability Metrics"]
        M1["Star MTBF:<br/>8,760 hrs<br/>(hub SPOF)"]
        M2["Ring MTBF:<br/>2,920 hrs<br/>(any link)"]
        M3["Mesh MTBF:<br/>greater than 50,000 hrs<br/>(redundancy)"]
    end

    Normal --> NodeFail
    NodeFail --> LinkFail
    LinkFail --> Metrics

    classDef normalStyle fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef failStyle fill:#E67E22,stroke:#2C3E50,stroke-width:3px,color:#fff
    classDef criticalStyle fill:#C0392B,stroke:#2C3E50,stroke-width:3px,color:#fff
    classDef okStyle fill:#27AE60,stroke:#2C3E50,stroke-width:2px,color:#fff

    class N_Star,N_Ring,N_Mesh normalStyle
    class F_Star,L_Ring criticalStyle
    class F_Ring,L_Star failStyle
    class F_Mesh,L_Mesh,M3 okStyle

Figure 776.2: Topology failure analysis. Star: hub failure causes 100% outage (MTBF 8,760 hours). Ring: link failure partitions network (MTBF 2,920 hours). Mesh: survives multiple failures with minimal impact (MTBF >50,000 hours).

776.4.1 Single Point of Failure (SPOF) Identification

Topology	SPOF Type	Failure Impact	Mitigation Strategy	Cost Multiplier
Star	Central hub	100% network outage	Dual-hub with failover	2x
Bus	Backbone cable	100% network outage	Redundant bus (dual cable)	2x
Ring	Any single link	50% devices isolated	Dual ring (FDDI-style)	2x
Tree	Root node	100% outage; branch = subtree	Redundant root + meshing	1.5-3x
Full Mesh	None	Isolated device only	N/A (already redundant)	1x
Partial Mesh	Depends on design	10-50% devices affected	Increase connectivity (k>=3)	1.2-1.5x

776.4.2 Quantitative Availability Calculations

Availability = MTBF / (MTBF + MTTR)

Star with single hub (MTBF=8760h, MTTR=4h):
  Availability = 8760/(8760+4) = 99.95%
  Annual downtime = 4.38 hours

Star with dual-hub failover (MTBF=87600h, MTTR=0.5h):
  Availability = 87600/(87600+0.5) = 99.9994%
  Annual downtime = 0.5 hours

Mesh with k=3 (MTBF=50000h, MTTR=1h):
  Availability = 50000/(50000+1) = 99.998%
  Annual downtime = 0.88 hours

---

776.5 Message Complexity and Routing Overhead

Routing overhead varies dramatically by topology. This affects bandwidth consumption, energy usage, and latency.

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'background': '#ffffff', 'mainBkg': '#2C3E50', 'secondBkg': '#16A085', 'tertiaryBkg': '#E67E22'}}}%%
graph LR
    subgraph Star["Star: O(1) Routing"]
        S1["Device"] -->|"Direct<br/>No routing"| S_Hub["Hub"]
        S_Hub -->|"Direct"| S2["Device"]
        S_RT["Routing Table:<br/>1 entry<br/>0% overhead"]
    end

    subgraph Ring["Ring: O(n) Routing"]
        R1["Node A"] -->|"Hop 1"| R2["Node B"]
        R2 -->|"Hop 2"| R3["Node C"]
        R3 -->|"Hop 3"| R4["Node D"]
        R_RT["Routing Table:<br/>n entries<br/>2-5% overhead<br/>Distance vector"]
    end

    subgraph Mesh["Mesh: O(n squared) Discovery"]
        M1["Sensor"] -.->|"LSA flood"| M2["Router"]
        M2 -.->|"LSA flood"| M3["Router"]
        M1 -->|"Optimal path"| M3
        M_RT["Routing Table:<br/>n squared link states<br/>15-30% overhead<br/>Link-state"]
    end

    subgraph Tree["Tree: O(log n) Routing"]
        T1["Root"] --> T2["Parent"]
        T2 --> T3["Child"]
        T2 --> T4["Child"]
        T_RT["Routing Table:<br/>log(n) entries<br/>1-3% overhead<br/>Hierarchical"]
    end

    classDef starStyle fill:#2C3E50,stroke:#16A085,stroke-width:3px,color:#fff
    classDef ringStyle fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef meshStyle fill:#E67E22,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef treeStyle fill:#7F8C8D,stroke:#2C3E50,stroke-width:2px,color:#fff

    class S1,S_Hub,S2,S_RT starStyle
    class R1,R2,R3,R4,R_RT ringStyle
    class M1,M2,M3,M_RT meshStyle
    class T1,T2,T3,T4,T_RT treeStyle

Figure 776.3: Routing overhead analysis. Star: O(1) routing (no overhead). Ring: O(n) distance-vector (2-5% bandwidth). Mesh: O(n^2) link-state discovery (15-30% overhead). Tree: O(log n) hierarchical routing (1-3% overhead).

776.5.1 Routing Protocol Overhead by Topology

Topology	Routing Type	Table Size	Update Frequency	Bandwidth Overhead	Convergence Time
Star	None (direct)	1 entry	N/A	0%	Instant
Ring	Distance-vector	n entries	30-60 sec	2-5%	30-90 sec
Tree	Hierarchical	log2(n) entries	60 sec	1-3%	10-30 sec
Partial Mesh	Link-state	n*k entries	5-10 min	5-15%	1-5 min
Full Mesh	Link-state/flooding	n^2 entries	5-10 min	15-30%	1-10 min

776.5.2 Example: 50-Node Industrial IoT Network

Star topology (1 hub + 49 sensors):
  Routing overhead: 0 bytes/sec
  Each sensor -> hub -> destination (2 hops maximum)

Ring topology (50 sensors in ring):
  Routing updates: 50 nodes x 100 bytes x (1/60 Hz) = 83 bytes/sec
  Average path: 50/4 = 12.5 hops

Partial mesh (50 sensors, k=4 avg degree):
  Link-state updates: 50 nodes x 800 bytes x (1/300 Hz) = 133 bytes/sec
  Average path: 1.5-2.5 hops (much better than ring!)

Full mesh (50 sensors, all-to-all):
  Link-state updates: 50 x 2450 bytes x (1/300 Hz) = 408 bytes/sec
  Direct paths: 1 hop always

---

776.6 Real-World IoT Protocol Examples

Understanding how real IoT protocols map to topologies helps with practical design decisions.

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'background': '#ffffff', 'mainBkg': '#2C3E50', 'secondBkg': '#16A085', 'tertiaryBkg': '#E67E22'}}}%%
graph TB
    subgraph SmartHome["Smart Home (Star)"]
        SH_Hub["Wi-Fi/Zigbee Hub<br/>100 Mbps<br/>SPOF"] --- SH1["15-50 devices"]
        SH_Hub --- SH2["Lights"]
        SH_Hub --- SH3["Sensors"]
        SH_Hub --- SH4["Cameras"]
        SH_Note["Topology: Star<br/>Range: 30m<br/>Cost: $50-200 hub"]
    end

    subgraph Industrial["Industrial (Mesh)"]
        IND_Coord["Zigbee Coordinator"] --- IND_R1["Router"]
        IND_R1 --- IND_R2["Router"]
        IND_R1 --- IND_R3["Router"]
        IND_R2 --- IND_R3
        IND_R2 --- IND_S1["50-200 sensors"]
        IND_R3 --- IND_S2["End devices"]
        IND_Note["Topology: Mesh<br/>Redundancy: k=3-4<br/>Self-healing"]
    end

    subgraph LoRaWAN["LoRaWAN (Star-of-Stars)"]
        LNS["Network Server"] --- LGW1["Gateway 1<br/>1000+ devices"]
        LNS --- LGW2["Gateway 2"]
        LNS --- LGW3["Gateway 3"]
        LGW1 -.-> LD1["Devices<br/>10km range"]
        LGW2 -.-> LD1
        LGW3 -.-> LD1
        L_Note["Topology: Star-of-stars<br/>Uptime: 99.99%<br/>Battery: 10 years"]
    end

    subgraph Thread["Thread/Matter (IPv6 Mesh)"]
        TBR["Border Router<br/>To Internet"] --- TR1["Router"]
        TR1 --- TR2["Router"]
        TR1 --- TR3["Router"]
        TR2 --- TR3
        TR2 --- TS1["250+ devices"]
        TR3 --- TS2["Sleepy end devices"]
        T_Note["Topology: Mesh<br/>Hops: 2-4 typical<br/>IPv6 native"]
    end

    classDef hubStyle fill:#2C3E50,stroke:#E67E22,stroke-width:4px,color:#fff
    classDef meshStyle fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    classDef gwStyle fill:#E67E22,stroke:#2C3E50,stroke-width:3px,color:#fff
    classDef deviceStyle fill:#7F8C8D,stroke:#2C3E50,stroke-width:1px,color:#fff

    class SH_Hub,LNS hubStyle
    class IND_Coord,IND_R1,IND_R2,IND_R3,TR1,TR2,TR3,TBR meshStyle
    class LGW1,LGW2,LGW3 gwStyle
    class SH1,SH2,SH3,SH4,IND_S1,IND_S2,LD1,TS1,TS2 deviceStyle

Figure 776.4: Real-world IoT topologies. Smart Home: star (Wi-Fi/Zigbee hub, 15-50 devices, SPOF). Industrial: Zigbee mesh (50-200 sensors, k=3-4 redundancy, self-healing). LoRaWAN: star-of-stars (1000+ devices/gateway, 10km range, 99.99% uptime). Thread/Matter: IPv6 mesh (250+ devices, 2-4 hops, sleepy end devices).

776.6.1 Protocol-to-Topology Mapping

IoT Protocol	Topology	Typical Scale	Key Characteristics	Real-World Use Case
Wi-Fi	Star	15-50 devices	Hub bandwidth 100-1000 Mbps, 30m range, SPOF at AP	Smart home cameras, voice assistants
Zigbee	Mesh	50-200 nodes	k=3-4 redundancy, self-healing, coordinator-based	Industrial sensors, smart lighting
Thread	Mesh	100-250 nodes	IPv6 native, border router, 2-4 hops typical	Matter smart home, building automation
LoRaWAN	Star-of-stars	1000+ devices/GW	10km range, 99.99% uptime (multi-GW), 10-year battery	Smart city parking, agriculture
BLE Mesh	Mesh	30-100 nodes	Flooding-based, managed flooding, provisioner	Retail beacons, asset tracking
Z-Wave	Mesh	232 nodes max	Source routing, 4 hops max, controller-based	Home security, door locks
NB-IoT	Star	50,000+ devices/cell	10km range, licensed spectrum, 99.9% uptime	Utility meters, asset tracking

---

776.7 Deployment Examples

776.7.1 Smart Home Example (Hybrid Star)

Topology: Star around Wi-Fi router + Zigbee hub

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
graph TD
    Router["Wi-Fi Router<br/>(Star Hub)"]

    subgraph WiFi["Wi-Fi Star Network (~15/100 Mbps)"]
        C["4x Cameras<br/>8 Mbps total"]
        V["2x Voice Assistants<br/>1 Mbps streaming"]
        TV["Smart TV<br/>5 Mbps avg"]
        ZHub["Zigbee Hub<br/>100 Kbps"]
    end

    subgraph Zigbee["Zigbee Mesh (45 devices, 3 hops avg)"]
        Bulbs["30x Smart Bulbs<br/>(mesh routers)"]
        Motion["10x Motion Sensors<br/>(end devices)"]
        Switches["5x Smart Switches<br/>(routers)"]
    end

    Router --> C
    Router --> V
    Router --> TV
    Router --> ZHub
    ZHub --> Bulbs
    ZHub --> Motion
    ZHub --> Switches
    Bulbs --- Switches

    style Router fill:#2C3E50,stroke:#16A085,stroke-width:3px,color:#fff
    style C fill:#16A085,stroke:#2C3E50,color:#fff
    style V fill:#16A085,stroke:#2C3E50,color:#fff
    style TV fill:#16A085,stroke:#2C3E50,color:#fff
    style ZHub fill:#E67E22,stroke:#2C3E50,color:#fff
    style Bulbs fill:#7F8C8D,stroke:#2C3E50,color:#fff
    style Motion fill:#7F8C8D,stroke:#2C3E50,color:#fff
    style Switches fill:#7F8C8D,stroke:#2C3E50,color:#fff

Figure 776.5: Smart home hybrid topology: Wi-Fi star (Navy) for high-bandwidth devices, Zigbee mesh (Gray) for low-power sensors. Total bandwidth: ~15 Mbps Wi-Fi + 45-device self-healing mesh.

Why hybrid? - Cameras need high bandwidth (Wi-Fi star provides 100 Mbps centralized) - Lights tolerate multi-hop latency (Zigbee mesh provides fault tolerance) - Zigbee mesh survives individual bulb failures (lights stay functional) - Wi-Fi AP is single point of failure (but cameras are monitoring, not life-safety)

776.7.2 Industrial Mesh Example (Zigbee in Factory)

Topology: Partial mesh with k=3-4 average degree

50-sensor factory floor monitoring:
- 10 Zigbee routers (always-on, AC-powered)
- 40 temperature/vibration sensors (battery-powered end devices)
- Each router connects to 3-4 other routers (redundant paths)
- Coordinator connects to SCADA system via Ethernet

Mesh properties:
- Connectivity k=3 (survives 2 simultaneous router failures)
- Average path length: 2.3 hops
- Routing overhead: 8% (link-state updates every 5 min)
- Self-healing: 30 sec convergence after router failure
- Battery life: 5 years (sensors sleep 99% of time, wake every 60 sec)

Failure scenario: - 1 router fails -> 3 redundant paths remain -> 0% data loss - 2 routers fail -> some sensors use 3-hop paths -> <5% latency increase - 3 routers fail -> network partitions -> SCADA alarm triggers

776.7.3 LoRaWAN Example (Star-of-Stars)

Topology: Star-of-stars (devices -> gateways -> network server)

Smart city parking (1000 sensors):
- 1000 parking sensors (Class A LoRaWAN)
- 3 gateways (10km range each, overlapping coverage)
- 1 network server (cloud-based)

Sensor transmits every 5 minutes:
- Uplink: 20 bytes (occupied/vacant + battery level)
- Airtime: 200 ms (SF7, 125 kHz bandwidth)
- Battery life: 10 years (2x AA batteries)

Gateway diversity:
- 75% of sensors heard by 2+ gateways (redundancy)
- Network server deduplicates packets
- If 1 gateway fails, 90% sensors still connected
- 99.99% uptime (multiple gateways cover same area)

Scalability:
- Each gateway handles 1000+ devices (duty cycle <1%)
- 3 gateways provide redundancy + load balancing
- Total cost: 3x $1000 gateways + $1000 server = $4K infrastructure

---

776.8 Summary

Network topology analysis uses graph theory to predict network behavior and make informed design decisions.

776.8.1 Key Metrics

Graph Theory: - Connectivity (k): Star k=1, Ring k=2, Full Mesh k=n-1 - Scalability: Star O(n) edges, Mesh O(n^2), Partial Mesh O(n*k) - Path Length: Star 2 hops, Mesh 1 hop, Ring n/4 hops average - 100-node comparison: Full mesh 4,950 edges vs Partial mesh (k=4) 200 edges (96% reduction)

Failure Analysis: - Star MTBF: 8,760 hours (99.95% availability, 4.38h annual downtime) - Mesh MTBF: >50,000 hours (99.998% availability, 0.88h annual downtime) - Dual-hub failover: 99.9994% availability (0.5h annual downtime)

Routing Overhead (50-node network): - Star: 0% overhead (direct paths) - Ring: 2-5% overhead (distance-vector, 30-60 sec updates) - Partial Mesh: 5-15% overhead (link-state, 5-10 min updates) - Full Mesh: 15-30% overhead (flooding)

776.8.2 Design Guidelines

1. Use connectivity (k) to determine fault tolerance requirements
2. Calculate edge count to estimate infrastructure cost
3. Measure routing overhead for bandwidth-constrained networks
4. Model failure scenarios before deployment

---

776.9 What’s Next

In the next chapter, Communication Patterns, we’ll explore data flow patterns in IoT networks including unicast, broadcast, multicast, and the many-to-one patterns common in sensor networks.