👉 👉

Module 3 ACN
Network as a Graph

1.1 Graph Theory Fundamentals in Networking

A computer network can be represented as a graph:

• Vertices (Nodes): Routers, switches, or hosts.
• Edges (Links): Physical connections (cables, wireless).
• Weights: Metrics like cost, distance, delay, or bandwidth.

1.2 Types of Network Graphs

Directed vs. Undirected Graphs

• Directed Graph: Links have a direction (e.g., satellite link one-way).
• Undirected Graph: Links are bidirectional (e.g., Ethernet, fiber optic).

Connected vs. Disconnected Graphs

• Connected Graph: A path exists between any two nodes.
• Disconnected Graph: Some nodes cannot reach others.

1.3 Graph Properties in Routing

• Path: Sequence of nodes and links from source → destination.
• Simple Path: No repeated nodes.
• Elementary Path: No repeated links.
• Shortest Path:
Path with minimum total weight (distance, cost, or delay).
Used by routing algorithms to find the best routes.
• Spanning Tree:
Subgraph that connects all nodes without loops.
Used in bridging protocols (like STP – Spanning Tree Protocol) to prevent network loops.
-------------------
4. Routing Metrics

When routers choose the best path, they use metrics (values) to compare different routes.

4.1 Types of Metrics

Static Metrics (fixed values, do not change often)

• Hop Count → Number of routers (hops) between source and destination.
• Administrative Distance (AD) → Manual preference setting; smaller AD =
more trusted.
 • Path Cost → Fixed cost given to links.

Dynamic Metrics (change depending on network condition)

• Bandwidth → Link capacity (higher bandwidth = better path).
• Delay → Time taken (propagation + queuing).
• Load → How busy the link is (utilization).
• Reliability → Error rate and availability.
• MTU (Maximum Transmission Unit) → Maximum packet size supported by
the link.

4.2 Metric Calculation

OSPF Cost Calculation

Formula:
Reference Bandwidth
Cost= ---------------------
Interface Bandwidth

• Default Reference Bandwidth = 100 Mbps

• Examples:
• Ethernet (10 Mbps): Cost = 100/10 = 10
• Fast Ethernet (100 Mbps): Cost = 100/100 = 1
• Gigabit Ethernet (1000 Mbps): Cost = 100/1000 = 1
Composite Metrics (IGRP/EIGRP)

4.3 Metric Considerations

• Bandwidth-based Metrics
Advantage: Reflects link capacity.
✘ Disadvantage: May not reflect current congestion.
• Delay-based Metrics
Advantage: Considers real transmission time.
✘ Disadvantage: May cause oscillation (frequent route changes).
• Load-based Metrics
Advantage: Adapts to current traffic.
✘ Disadvantage: Can cause instability (routes keep changing).
------------
IPv6 packet header format.

IPv6 Packet Header

IPv6 is the next-generation Internet Protocol.

Every IPv6 packet has a fixed-size header of 40 bytes.
This header tells routers how to deliver the packet.

IPv6 Header Fields

1. Version (4 bits)
• Identifies the IP version.
• Always 6 for IPv6.
2. Traffic Class (8 bits)
• Like a “priority tag.”
• Used for Quality of Service (QoS) → video, voice can get priority over
normal data.
 normal data.
3. Flow Label (20 bits)
• Groups packets into a “flow.”
• Example: a video call’s packets can be marked, so routers treat them
the same way (low delay).
4. Payload Length (16 bits)
• Size of the data after the header (in bytes).
• Tells how much actual content (like TCP/UDP data) is inside.
5. Next Header (8 bits)
• Tells which protocol comes next.
• Example: 6 → TCP, 17 → UDP, 58 → ICMPv6.
• Can also point to extension headers (security, routing, etc.).
6. Hop Limit (8 bits)
• Maximum number of routers the packet can cross.
• Each router reduces it by 1.
• If it becomes 0 → packet is discarded. (Prevents endless loops).
7. Source Address (128 bits)
• IPv6 address of the sender.
• Very large (128-bit), enough for all devices on Earth!
8. Destination Address (128 bits)
• IPv6 address of the receiver.
9. Data (Payload)
• The actual content being delivered (application data, TCP/UDP
segment, etc.).

Key Points
• IPv6 header size = 40 bytes fixed (IPv4 header was variable, 20–60 bytes).
• Simplified design → faster routing and better performance.
• Removes IPv4 fields like checksum and fragmentation (done differently in
IPv6).
• Supports extension headers (added only when needed).

⸻
5. The Global Internet

5.1 Internet Structure

The Internet is not one single network, but a network of networks organized in a hierarchy:

1. Tier 1 ISPs (Top Level)

• These are the backbone providers of the Internet.
• They connect directly with each other worldwide.
 • They connect directly with each other worldwide.
• Example: AT&T, Tata Communications, NTT, Level 3.
• They don’t pay anyone for connectivity because they peer with other Tier 1
ISPs.

2. Tier 2 ISPs (Regional Level)

• They buy connections from Tier 1 ISPs.
• Provide Internet at a regional/national scale.
• Example: Airtel (India), Comcast (USA).

3. Tier 3 ISPs (Local Level)

• They buy connections from Tier 2 ISPs.
• Provide Internet to homes, schools, offices.
• Example: Local broadband or mobile data providers (like ACT, BSNL FTTH).

4. End Users
• Final consumers of the Internet:
• Individuals (mobile data, Wi-Fi at home).
• Organizations (companies, universities, government offices).

Internet Exchange Points (IXPs)

• Physical meeting points where different ISPs connect and exchange traffic.
• Reduce latency (faster connection) and costs (less dependence on Tier 1).
• Example: DE-CIX in Mumbai, AMS-IX in Amsterdam.

5.2 Internet Routing Architecture

To organize routing globally, the Internet is divided into Autonomous Systems (ASes).

Autonomous System (AS)

• A group of networks under one administration.
• Identified by a unique AS Number (ASN).
• Example:
• Google = AS15169
• Reliance Jio = AS55836

Each AS decides its own routing policies.

Routing Protocols in ASes

1. Interior Gateway Protocols (IGPs) – Used inside one AS
 1. Interior Gateway Protocols (IGPs) – Used inside one AS
• Example:
• OSPF (Open Shortest Path First)
• RIP (Routing Information Protocol)
• IS-IS
• EIGRP (Cisco proprietary)
2. Exterior Gateway Protocols (EGPs) – Used between ASes
• Main protocol: BGP (Border Gateway Protocol).
• BGP makes the global Internet routing possible.

5.3 Internet Growth Challenges

As the Internet grows, it faces some scalability issues:

Problems
1. Routing Table Growth
• Each router must store more and more routes → requires large memory.
2. Processing Overhead
• Routers take more time to calculate best paths.
3. Higher Memory Needs
• Large routing tables consume expensive hardware resources.

Solutions
• Route Aggregation: Combine multiple small networks into one bigger route.
• Example: Instead of listing [Link]/24, [Link]/24,
[Link]/24, advertise only [Link]/16.
• Hierarchical Addressing: Divide IP addresses in a structured way (CIDR,
subnets).
• Policy-Based Routing: Control routing decisions based on policies, not just shortest
path (e.g., avoiding costly ISPs).
⸻
6. Routing Areas

In large networks, routers exchange a lot of information.

If every router knew about every other router, the routing tables would be huge and updates
would take too much bandwidth.

Solution: Hierarchical Routing with Areas (used in OSPF).

6.1 Hierarchical Routing Concept

Why divide the network into areas?

• Scalability → Reduces routing table size. Each router doesn’t need to know
about every single route in the entire network.
• Administrative Control → Different policies can be applied in different areas.
• Fault Isolation → Problems (like flapping routes) stay within an area, not
affecting the whole network.
• Reduced Overhead → Fewer routing updates between areas.

Think of it like a country divided into states: each state manages its own
internal roads, but only shares summarized information with the central government.

6.2 OSPF Areas Implementation

In OSPF (Open Shortest Path First), areas are implemented with special routers:
1. Area Border Router (ABR)
• Connects one area to another.
• Maintains a separate database for each area.
• Performs inter-area routing.
• Summarizes routes between areas (reduces size).
2. Autonomous System Boundary Router (ASBR)
• Connects OSPF network to external networks (like BGP, RIP).
• Redistributes external routes into OSPF.
• Generates Type 5 LSAs for external routes.
3. Designated Router (DR)
• Works on multi-access networks (like Ethernet).
• Reduces LSA flooding (only DR shares updates, others just connect to
it).
• Generates Type 2 LSAs (Network LSAs).
• Backup DR (BDR) takes over if DR fails.

6.3 Area Types

Different area types help manage complexity:

1. Standard Area
• Allows all LSA types.
• Full routing information inside.
• Requires more memory and processing.
 2. Stub Area
• Blocks Type 4 & Type 5 LSAs (external routes).
• Uses default route to reach external destinations.
• Saves memory and reduces processing.
3. Not-So-Stubby Area (NSSA)
• Like a stub area, but allows redistribution.
• Uses Type 7 LSAs (converted to Type 5 at ABR).
• Compromise between stub and standard area.

Example:
• A company’s head office (Standard area) connects to the internet.
• A branch office (Stub area) doesn’t need full routing tables, just a default
route.
• A remote site (NSSA) needs to inject local routes but doesn’t want all
external routes.
6.4 Area Design Guidelines
1. Single-Area Design
• Suitable for small networks (< 50 routers).
• Simple to configure and troubleshoot.
• No need for complex features.
2. Multi-Area Design
• Needed for large networks (> 50 routers).
• Improves scalability and performance.
• Provides better fault isolation and administrative control.
---------------
7. Border Gateway Protocol (BGP)

7.1 BGP Overview

• Purpose: BGP is the inter-domain routing protocol used on the Internet.
• Algorithm: It uses a Path Vector Algorithm.
• Policy-based: Unlike OSPF or RIP (which pick shortest path), BGP decisions
are based on policies set by network administrators.
• Scalable: Handles the huge number of routes on the Internet
BGP Characteristics
• Runs over TCP (port 179) for reliability.
• Shares network reachability information.
• Provides fine policy control (you can choose which routes to accept, prefer,
or advertise).

7.2 BGP Operation

To establish communication, two BGP routers (peers) form a BGP session:

1. TCP Connection → Establishes reliable transport between peers.
2. OPEN Message → Exchange capabilities (AS number, identifiers, etc.).
3. UPDATE Message → Exchange routing information.
4. KEEPALIVE Message → Maintain the session (like heartbeats).
5. NOTIFICATION Message → Sent if errors occur; closes the session.

BGP Message Types:

• OPEN → Starts the session.
• UPDATE → Advertises new routes or withdraws old ones.
• KEEPALIVE → Keeps the session alive.
• NOTIFICATION → Reports errors.

7.3 BGP Path Attributes

BGP decides best routes using Path Attributes (PAs).

Well-Known Mandatory (must be present)

• ORIGIN → How route entered BGP (IGP, EGP, or Incomplete).
• AS_PATH → Sequence of ASes a route passed through (helps avoid loops).
• NEXT_HOP → Next hop IP address.

Well-Known Discretionary
• LOCAL_PREF → Preference value inside AS (higher = better).
• ATOMIC_AGGREGATE → Indicates route summarization.

Optional Transitive
• AGGREGATOR → Router & AS that aggregated the route.
• COMMUNITY → Grouping of routes for applying policies.

Optional Non-Transitive
• MULTI_EXIT_DISC (MED) → Suggests preferred entry point into an AS
(lower = better).
• ORIGINATOR_ID → Router ID of route originator.

7.4 BGP Route Selection Process

When multiple routes exist, BGP selects the best path using this order:
1. Weight (Cisco only) → Higher preferred.
2. Local Preference → Higher preferred.
3. Locally Originated → Locally learned route preferred.
4. AS_PATH Length → Shorter path preferred.
5. Origin Code → IGP > EGP > Incomplete.
6. MED → Lower is better.
7. eBGP over iBGP → Prefer external routes.
8. IGP Metric to Next Hop → Lower cost preferred.
9. Router ID → Lower ID preferred (tiebreaker).

7.5 Types of BGP

1. External BGP (eBGP)
• Between routers in different Autonomous Systems (ASes).
• TTL = 1 (directly connected by default).
• Administrative Distance = 20.
2. Internal BGP (iBGP)
 • Between routers in the same AS.
• Requires full mesh or Route Reflectors.
• TTL = 255 (multi-hop possible).
• Administrative Distance = 200.

7.6 BGP Scaling Techniques

Since BGP is used on the Internet, scalability is crucial:

1. Route Reflectors (RRs)
• Remove need for full-mesh iBGP.
• Clients only peer with RR.
• Prevent loops with “Cluster IDs.”
2. Confederations
• Break a large AS into sub-ASes.
• Each sub-AS runs iBGP internally.
• Between sub-ASes → eBGP with private AS numbers.
3. Route Filtering & Aggregation
• Filter unwanted routes at AS boundaries.
• Summarize multiple routes into one.
• Reduces routing table size.

⸻
Mobility and Mobile IP

9.1 Mobility Concepts

Mobility means moving devices, users, or sessions from one place to another while staying
connected.

Types of Mobility:
1. Device Mobility – A laptop or phone moves from one network to another.
2. Personal Mobility – A user logs in from different devices (phone, PC, tablet).
3. Session Mobility – An ongoing call or video keeps working even when you
move.
4. Service Mobility – Your subscribed services (like email, streaming) follow
you everywhere.

Challenges:
• Addressing – IP addresses depend on the current network → hard to keep
the same identity when moving.
• Routing – Finding the device when it changes location.
 • Handoff – Smooth transfer between networks (e.g., Wi-Fi to mobile data).
• Security – Must ensure authentication and data protection.

9.2 Mobile IPv4

Mobile IP is a protocol that allows a device to move between networks but keep the same
permanent IP address.

Components:
• Mobile Node (MN) – The moving device (laptop, phone).
• Home Agent (HA) – A router in the home network that tracks the mobile
node.
• Foreign Agent (FA) – A router in the visited (new) network.
• Correspondent Node (CN) – The device communicating with the mobile
node.

Key Concepts:
• Home Address – Permanent IP (identity).
• Care-of Address (CoA) – Temporary IP in foreign network.
• Binding – Link between home address and CoA.

Operation:
1. Registration Phase
• MN gets CoA in the foreign network (via FA).
• MN registers CoA with HA.
• HA stores the mapping (Home Addr ↔ CoA).
2. Data Delivery
• Forward direction: CN → HA → FA → MN (via tunneling).
• Reverse direction: MN → CN directly.
• Problem: Triangle routing (longer, inefficient path).

9.3 Mobile IPv6

IPv6 improves Mobile IP to remove inefficiencies.

Improvements:
• No Foreign Agent (MN configures CoA itself).
• Built-in Route Optimization (packets go directly to MN, not via HA).
• Neighbor Discovery instead of ARP.
 • IPSec Security is mandatory.

Addresses:
• Home Address – Permanent IPv6 address.
• Care-of Address – Temporary IPv6 in visited network.
• Link-local Address – For local communication.

Operation:
1. MN gets a link-local address.
2. Configures CoA automatically (stateless autoconfig).
3. Registers with HA (Binding Update).
4. HA updates binding cache.
5. Optionally, CN also updates → sends packets directly to MN (route
optimization).