COMPUTER COMMUNICATION NETWORKS
MITE-Moodabidri
1
Module-4
MITE-Moodabidri
2
CO-Comprehend the Network Layer Protocols and Apply the Unicast Routing Protocols
Module-4
Network Layer Protocols: Internet Protocol (IP): Datagram Format, Fragmentation, Options, Security of IPv4 Datagrams, ICMPv4: Messages, Debugging Tools, Mobile IP: Addressing, Agents, Three Phases, Inefficiency in Mobile IP.
Unicast Routing: Introduction, Routing Algorithms: Distance Vector Routing, Link State Routing, Path vector routing, Unicast Routing Protocol: Internet Structure, Routing Information Protocol, Open Shortest Path First, Border Gateway Protocol Version 4.
Total lecture hours-10
MITE-Moodabidri
3
4.1 Internet Protocol (IP):
Position of IP and other network-layer protocols in TCP/IP protocol suite
MITE-Moodabidri
4
4.1.1Datagram Format
MITE-Moodabidri
5
4.1.2 Fragmentation
Maximum Transfer Unit (MTU)
Fields Related to Fragmentation
MITE-Moodabidri
6
4.1.3 Options
Single-Byte Options
Multliple-Byte Options
No Operation
End of Option
Record Route
Strict Source Route
Loose Source Route
Timestamp
MITE-Moodabidri
7
4.1.4 Security of IPv4 Datagrams
Packet Sniffing
Packet Modification
IP Spoofing
IPSec
MITE-Moodabidri
8
4.2 ICMPv4
4.2.1 MESSAGES
MITE-Moodabidri
9
4.2 ICMPv4
4.2.1 MESSAGES
Error Reporting Messages
Destination Unreachable
Source Quench
Redirection Message
Parameter Problem
Query Messages
MITE-Moodabidri
10
4.2 ICMPv4
4.2.2 Debugging Tools
Ping
Traceroute or Tracert
MITE-Moodabidri
11
4.3 MOBILE IP
4.3.1 Addressing
Stationary Hosts
The original IP addressing was based on the assumption that a host is stationary,
attached to one specific network. A router uses an IP address to route an IP datagram.
MITE-Moodabidri
12
4.3 MOBILE IP
4.3.1 Addressing
Mobile Hosts
Changing the Address
Two Addresses
MITE-Moodabidri
13
4.3 MOBILE IP
4.3.2 Agents
Home agent and foreign agent
MITE-Moodabidri
14
4.3 MOBILE IP
4.3.3 Three Phases
MITE-Moodabidri
15
4.3 MOBILE IP
4.3.3 Three Phases
i.Agent Discovery
Agent advertisement
MITE-Moodabidri
16
4.3 MOBILE IP
4.3.3 Three Phases
ii. Registration
1. The mobile host must register itself with the foreign agent.
2. The mobile host must register itself with its home agent. This is normally done by the foreign agent on behalf of the mobile host.
3. The mobile host must renew registration if it has expired.
4. The mobile host must cancel its registration (deregistration) when it returns home.
MITE-Moodabidri
17
4.3 MOBILE IP
4.3.3 Three Phases
iii. Registration Request and Reply
Registration reply format
Registration request format
MITE-Moodabidri
18
4.3 MOBILE IP
4.3.3 Three Phases
iv. Data Transfer
MITE-Moodabidri
19
4.3 MOBILE IP
4.3.4 Inefficiency in Mobile IP
Double Crossing
MITE-Moodabidri
20
4.3 MOBILE IP
4.3.4 Inefficiency in Mobile IP
Triangle Routing (dog-leg routing)
MITE-Moodabidri
21
4.3 MOBILE IP
4.3.4 Inefficiency in Mobile IP
Solution
One solution to inefficiency is for the remote host to bind the care-of address to the home address of a mobile host. For example, when a home agent receives the first packet for a mobile host, it forwards the packet to the foreign agent; it could also send an update binding packet to the remote host so that future packets to this host could be sent to the care-of address. The remote host can keep this information in a cache
MITE-Moodabidri
22
4.4 Unicast Routing
4.4.1 General Idea
An internet and its graphical representation
An Internet as a Graph
MITE-Moodabidri
23
4.4 Unicast Routing
4.4.2 Least-Cost Routing
Least-cost trees for nodes in the internet
Least-Cost Trees
MITE-Moodabidri
24
4.5 ROUTING ALGORITHMS
4.5.1 Distance-Vector Routing
In distance-vector routing, a router continuously tells all of its neighbors what it knows about the whole internet
Bellman-Ford Equation
The heart of distance-vector routing is the famous Bellman-Ford equation
The following shows the general case in which Dij is the shortest distance and Cij is the cost between nodes i and j.
In distance-vector routing, normally we want to update an existing least cost with a least cost through an intermediary node, such as z, if the latter is shorter. In this case,the equation becomes simpler, as shown below:
MITE-Moodabidri
25
4.5.1 Distance-Vector Routing
Distance Vectors
The distance vector corresponding to a tree
MITE-Moodabidri
26
4.5.1 Distance-Vector Routing
Distance Vectors
The first distance vector for an internet
MITE-Moodabidri
27
4.5.1 Distance-Vector Routing
Distance Vectors
Updating distance vectors
MITE-Moodabidri
28
4.5.1 Distance-Vector Routing
Distance-Vector Routing Algorithm
MITE-Moodabidri
29
4.5.1 Distance-Vector Routing
Distance-Vector Routing Algorithm
MITE-Moodabidri
30
4.5.1 Distance-Vector Routing
Count to Infinity
Two-node instability
Split Horizon
Poison Reverse
MITE-Moodabidri
31
4.5.2 Link-State Routing
To create a least-cost tree with this method, each node needs to have a complete map of the network, which means it needs to know the state of each link. The collection of states for all links is called the link-state database (LSDB)
Example of a link-state database
MITE-Moodabidri
32
4.5.2 Link-State Routing
LSPs created and sent out by each node to build LSDB
MITE-Moodabidri
33
4.5.2 Link-State Routing
Formation of Least-Cost Trees
To create a least-cost tree for itself, using the shared LSDB, each node needs to run the famous Dijkstra Algorithm. This iterative algorithm uses the following steps:
1. The node chooses itself as the root of the tree, creating a tree with a single node, and sets the total cost of each node based on the information in the LSDB.
2. The node selects one node, among all nodes not in the tree, which is closest to the root, and adds this to the tree. After this node is added to the tree, the cost of all other nodes not in the tree needs to be updated because the paths may have been changed.
3. The node repeats step 2 until all nodes are added to the tree.
MITE-Moodabidri
34
4.5.2 Link-State Routing
Formation of Least-Cost Trees
MITE-Moodabidri
35
4.5.2 Link-State Routing
Formation of Least-Cost Trees
MITE-Moodabidri
36
4.5.2 Link-State Routing
Formation of Least-Cost Trees
MITE-Moodabidri
37
4.5.3 Path-Vector Routing
The best route is determined by the source using the policy it imposes on the route. In other words, the source can control the path. Although path-vector routing is not actually used in an internet, and is mostly designed to route a packet between ISPs,
MITE-Moodabidri
38
4.5.3 Path-Vector Routing
Spanning Trees
In path-vector routing, the path from a source to all destinations is also determined by the best spanning tree. The best spanning tree, however, is not the least-cost tree; it is the tree determined by the source when it imposes its own policy
MITE-Moodabidri
39
4.5.3 Path-Vector Routing
Creation of Spanning Trees
Path-vector routing, like distance-vector routing, is an asynchronous and distributed routing algorithm. The spanning trees are made, gradually and asynchronously, by each node. When a node is booted, it creates a path vector based on the information it can obtain about its immediate neighbor.
Path vectors made at booting time
MITE-Moodabidri
40
4.5.3 Path-Vector Routing
Creation of Spanning Trees
Updating path vectors
MITE-Moodabidri
41
4.5.3 Path-Vector Routing
Path-Vector Algorithm
MITE-Moodabidri
42
4.5.3 Path-Vector Routing
Path-Vector Algorithm
MITE-Moodabidri
43
4.6 Unicast Routing Protocol
4.6.1 Internet Structure
MITE-Moodabidri
44
4.6 Unicast Routing Protocol
4.6.1 Internet Structure
Hierarchical Routing
Autonomous Systems
Stub AS
Multihomed AS
Transient AS
MITE-Moodabidri
45
4.6.2 Routing Information Protocol (RIP)
The Routing Information Protocol (RIP) is one of the most widely used intradomain routing protocols based on the distance-vector routing algorithm we described earlier. RIP was started as part of the Xerox Network System (XNS), but it was the Berkeley Software Distribution (BSD) version of UNIX that helped make the use of RIP widespread.
MITE-Moodabidri
46
4.6.2 Routing Information Protocol (RIP)
Hop Count
MITE-Moodabidri
47
4.6.2 Routing Information Protocol (RIP)
Forwarding Tables
MITE-Moodabidri
48
4.6.2 Routing Information Protocol (RIP)
Rip implementation
RIP message format
MITE-Moodabidri
49
4.6.2 Routing Information Protocol (RIP)
Rip Algorithm
address of the sending router. We call each route in the modified forwarding
table the received route and each route in the old forwarding table the old route.
(mostly using the longest prefix first).
MITE-Moodabidri
50
4.6.3 Open Shortest Path First (OSPF)
Open Shortest Path First (OSPF) is also an intradomain routing protocol like RIP, but it is based on the link-state routing protocol.
Metric
MITE-Moodabidri
51
4.6.3 Open Shortest Path First (OSPF)
Forwarding tables in OSPF
MITE-Moodabidri
52
4.6.3 Open Shortest Path First (OSPF)
Areas
MITE-Moodabidri
53
4.6.3 Open Shortest Path First (OSPF)
Link-State Advertisement
MITE-Moodabidri
54
4.6.3 Open Shortest Path First (OSPF)
OSPF Implementation
OSPF Messages
MITE-Moodabidri
55
4.6.4 Border Gateway Protocol Version 4 (BGP4)
The Border Gateway Protocol version 4 (BGP4) is the only interdomain routing protocol used in the Internet today. BGP4 is based on the path-vector algorithm
A sample internet with four ASs
MITE-Moodabidri
56
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Operation of External BGP (eBGP)
MITE-Moodabidri
57
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Combination of eBGP and iBGP sessions in our internet
MITE-Moodabidri
58
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Finalized BGP path tables
MITE-Moodabidri
59
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Forwarding tables after injection from BGP
MITE-Moodabidri
60
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Format of Path attribute
Path Attributes
ORIGIN (type 1)
AS-PATH (type 2)
NEXT-HOP (type 3)
MULT-EXIT-DISC (type 4)
LOCAL-PREF (type 5)
ATOMIC-AGGREGATE (type 6)
AGGREGATOR (type 7).
MITE-Moodabidri
61
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Route Selection
MITE-Moodabidri
62
4.6.4 Border Gateway Protocol Version 4 (BGP4)
Messages