Transcript CN Unit 3

COMMUNICATION NETWORKS
Mr. DEEPAK P.
Associate Professor
ECE Department
SNGCE
1
DEEPAK.P
UNIT 3
Inter Networking
2
DEEPAK.P
Inter network
3
DEEPAK.P
Inter network
 Internetworking is the practice of connecting a computer
network with other networks through the use of gateways.
 Internetworking is a combination of the words inter
("between") and networking;
 The most common example of internetworking is the
Internet
 Inter networking can be classified in to two
1. Connection oriented or concatenated of virtual circuit
subnets
2. Connectionless or Datagram

4
DEEPAK.P
Connection Oriented Virtual
circuit
5
DEEPAK.P
Virtual Circuit
•
6
A virtual network link is a link that does not consist of a
physical (wired or wireless) connection between two
computing devices but is implemented using methods of
network virtualization.
DEEPAK.P
Concatenated of Virtual Circuit
A
X.25
Routers
ATM
Subnet 3
SNA
M
M
Subnet 1
B
Host
Subnet 2
Multi protocol router
(Gateway)
SNA-System Network Architecture
7
DEEPAK.P
Virtual Circuit Establishment
8
1.
Subnet shows that the destination is remote destination and
builds a virtual circuit to the router nearest to the destination.
2.
It then constructs a virtual circuit from that router to an
external gateway (multi protocol router).
3.
This gateway notes down the existence of this virtual circuit
in its table and builds another virtual circuit to a router which
is in the next subnet.
4.
This process continues until the destination host has been
reached.
DEEPAK.P
Virtual Circuit Establishment
5. After building the virtual circuit, data packets begin to
flow along the path
 Advantage
 Buffer can be reserved in advance
 Shorter header can be used
 Sequencing can be guaranteed
 Drawbacks
 There is no alternate path to avoid congestion
 Router failure creates big problems
9
DEEPAK.P
Connection less
10
DEEPAK.P
Datagram Internetworking
Datagram packets
Path 1
M
M
A
Routers
Subnet 3
Datagram packets
M
M
Subnet 1
B
Path 2
Host
Subnet 2
11
DEEPAK.P
Multi protocol router
(Gateway)
Datagram Internetworking
 The packets that are forwarded across the Internet are known
as IP datagrams
 An IP datagram consists of a header and a payload
 The header contains information that allows Internet routers to
forward the datagram from the source host to the destination
host
12
DEEPAK.P
Datagram Internetworking
 Header contains all information needed to deliver datagrams
to destination computer
1. Destination address
2. Source address
3. Identifier
4. Other delivery information
 Router examines header of each datagram and forwards
datagram along path to destination
13
DEEPAK.P
Advantage& Disadvantage Datagram
 Advantage
 Higher Bandwidth
 Deal with congestion in a better way
 It is robust in Router failure
 Drawbacks
 No guarantee of packets
 Addressing is difficult
 Longer header is needed
14
DEEPAK.P
Datagram forwarding in IP
15
DEEPAK.P
Delivery of an IP datagram
 Internetwork is a collection of LANs or point-to-point links
or switched networks that are connected by routers.
16
DEEPAK.P
IP forwarding Using Datagram
 The IP forwarding algorithm, commonly known as IP
routing.
 It is a specific implementation of routing for IP networks and
gives a more directed approach in forwarding datagram's
over a network.
 In order to achieve a successful transfer of data the algorithm
uses a routing table to select a next-hop router as the next
destination for a datagram.
 The IP address that is selected is known as the next-hop
address.
17
DEEPAK.P
Datagram forwarding in IP
 An IP network is a logical entity with a network number
 We represent an IP network as a “cloud”
18
DEEPAK.P
Networks and IP addressing
 IP address:
 Network part + Host part
 Network:
 Any host can physically be reached by any other host
without intervening router
 All hosts in the same network have the same network
number
19
DEEPAK.P
Forwarding Datagrams
 Header contains all information needed to deliver
datagrams to destination computer
 Destination address
 – Source address
 – Identifier
 – Other delivery information
 Router examines header of each datagram and
forwards datagram along path to destination
20
DEEPAK.P
Routing tables
 Each router and each host keeps a routing table which tells the
router how to process an outgoing packet
 Main columns:
 1. Destination address: where is the IP datagram going to?
 2. Next hop: how to send the IP datagram?
 3. Interface: what is the output port?
21
DEEPAK.P
IP Frame format
Header
Beginning of Data
Payload
22
DEEPAK.P
IP Header
 ProtocolVersion(4 bits) : This is the first field in the protocol
header.
 This field occupies 4 bits.
 This signifies the current IP protocol version being
used.
 Most common version of IP protocol being used is version 4 while
version 6 is out in market and fast gaining popularity.
23
DEEPAK.P
IP Header
 Header Length(4 bits) : This field provides the length of the
IP header.
 The length of the header is represented in 32 bit words.
 Since this field is of 4 bits so the maximum header length
allowed is 60 bytes.
24
DEEPAK.P
IP Header
 Type of service(8 bits) :
 The first three bits of this field are known as priority bits
and are ignored as of today.
 The next 4 bits represent type of service and the last bit is
left unused.
 The 4 bits that represent TOS are : minimize delay, maximize
throughput, maximize reliability and minimize
monetary cost.
25
DEEPAK.P
IP Header
 Total length(16 bits): This represents the total IP datagram
length in bytes.
 Since the header length (described above) gives the length of
header and this field gives total length so the length of data and its
starting point can easily be calculated using these two fields.
 Since this is a 16 bit field and it represents length of IP datagram
so the maximum size of IP datagram can be 65535 bytes.
26
DEEPAK.P
IP Header
 Identification(16 bits):
 This field is used for uniquely identifying the IP datagrams.
 This value is incremented every-time an IP datagram is sent from
source to the destination.
 This field comes in handy while reassembly of fragmented IP data
grams.
27
DEEPAK.P
IP Header
 Flags(3 bits):
 This field comprises of three bits.
 While the first bit is kept reserved as of now, the next two bits
have their own importance.
 The second bit represents the ‘Don’t Fragment’ bit.
 The third bit represents the ‘More Fragment’ bit.
28
DEEPAK.P
IP Header
 Fragment offset(13 bits):
 In case of fragmented IP data grams, this field contains the offset(
in terms of 8 bytes units) from the start of IP datagram.
 So again, this field is used in reassembly of fragmented IP
datagrams.
29
DEEPAK.P
IP Header
 Time to live(8 bits) :
 This value represents number of hops that the IP datagram will go
through before being discarded.
 The value of this field in the beginning is set to be around 32 or 64
(lets say) but at every hop over the network this field is
decremented by one.
 When this field becomes zero, the data gram is discarded. So, we
see that this field literally means the effective lifetime for a
datagram on network.
30
DEEPAK.P
IP Header
 Protocol(8 bits) :
 This field represents the transport layer protocol that handed over
data to IP layer.
 This field comes in handy when the data is demultiplex-ed at the
destination as in that case IP would need to know which protocol
to hand over the data to.
31
DEEPAK.P
IP Header
 Header Checksum(16 bits) : This fields represents a value that is
calculated using an algorithm covering all the fields in header
(assuming this very field to be zero).
 This value is calculated and stored in header when IP data gram is
sent from source to destination and at the destination side this
checksum is again calculated and verified against the checksum
present in header.
 If the value is same then the datagram was not corrupted else its
assumed that data gram was received corrupted. So this field is
used to check the integrity of an IP datagram.
32
DEEPAK.P
IP Header
 Source and destination IP(32 bits each) :
 These fields store the source and destination address respectively.
 Since size of these fields is 32 bits each so an IP address
os maximum length of 32 bits can be used.
 So we see that this limits the number of IP addresses that can be
used.
 To counter this problem, IP V6 has been introduced which
increases this capacity.
33
DEEPAK.P
IP Header
 Options(Variable length) : This field represents a list of options
that are active for a particular IP datagram.
 This is an optional field that could be or could not be present.
 If any option is present in the header then the first byte is
represented as follows :
34
DEEPAK.P
IP Header
 In the description above, the ‘copy flag’ means that copy this
option to all the fragments in case this IP datagram gets
fragmented.
 The ‘option class’ represents the following values : 0 -> control,
1-> reserved, 2 -> debugging and measurement, and 3 ->
reserved. Some of the options are given below :
35
DEEPAK.P
IP Header
36
DEEPAK.P
IP Header
 Data: This field contains the data from the protocol layer that has
handed over the data to IP layer. Generally this data field contains
the header and data of the transport layer protocols. Please note
that each TCP/IP layer protocol attaches its own header at the
beginning of the data it receives from other layers in case of source
host and in case of destination host each protocol strips its own
header and sends the rest of the data to the next layer.
37
DEEPAK.P
Routing tables
 Next hop and interface column can often be
summarized as one column
 Routing tables are set so that datagrams gets closer to the its
destination.
38
DEEPAK.P
Delivery with routing tables
39
DEEPAK.P
Tunneling
40
DEEPAK.P
Tunneling
 It is used when source and destination networks of same
type are to be connected through a network of different
type.
 Consider an ethernet network to be connected to another
ethetnet through a WAN
 The task is send on IP packet from host A of Ethernet 1 to the
host B of ehernet 2 wia a WAN.
 In this example, the IP packet do not have to deal with
WAN.
41
DEEPAK.P
Tunneling
 The host A&B do not have to deal with WAN
 The multiprotocol routers M1 and M2 will have to understand
about IP and WAN packet.
 Therefore WAN can be imagined to be equivalent to a big
tunnel extending between multiprotocol routers M1 and M2.
 So this technique is called Tunneling
42
DEEPAK.P
Tunneling
WAN
HOST
A
Tunnel
M1
M2
HOST
B
Ethernet 1
Ethernet 2
IP
IP
WAN packet
Header
Ethenet Frame
IP packet is inside the payload field of WAN packet
43
DEEPAK.P
Sequence of events in Tunneling
44
1.
Host A construct a packet containing the IP address of host
B
2.
It then inserts this IP packet in to ethernet frame.
3.
This frame is addressed to the multi protocol router M1.
4.
Host A then puts this frames on Ethernet.
DEEPAK.P
Sequence of events in Tunneling
45
5.
When M1 receives this frames, it removes IP packet, inserts
it in the IP payload packet of the WAN network layer
packet and addresses the WAN packet to M2.
6.
The multi protocol router M2 remeoves the IP packet and
send it to host B in an ethernet frame.
DEEPAK.P
ARP
46
DEEPAK.P
ARP
 Address Resolution Protocol (ARP) is a
telecommunications protocol used for resolution of
network layer addresses into link layer addresses
 ARP was defined by RFC (radio Frequency Committee)
826 in 1982
 If a machine talks to another machine in the same
network, it requires its physical or MAC address.
 ARP is used to convert an IP address to a physical
address such as an Ethernet address
47
DEEPAK.P
ARP
 IP address of the destination node is broadcast and the
destination node informs the source of its MAC address.
 Assume broadcast nature of LAN
 Broadcast IP address of the destination
 Destination replies it with its MAC address.
 Source maintains a cache of IP and MAC address
bindings
48
DEEPAK.P
ARP
49
DEEPAK.P
ARP
TCP
UDP
ICMP
IP
IGMP
ARP
Network
Access
RARP
Media
50
DEEPAK.P
Transport
Layer
Network
Layer
Link Layer
ARP
Send broadcast request
receive unicast response
51
DEEPAK.P
ARP
 A host wishing to obtain a physical address broadcasts an
ARP request onto the TCP/IP network.
 The host on the network that has the IP address in the
request then replies with its physical hardware address.
52
DEEPAK.P
ARP
 Problem: Router A needs to forward an IP datagram to
router B (which is on the same Ethernet LAN)
 Router A knows the IP address of B.
 But the IP datagram must be encapsulated within an
Ethernet frame, whose Ethernet destination address is the
address of B’s NIC
 How can A discover the Ethernet Address of B’s NIC?
53
DEEPAK.P
ARP
54
DEEPAK.P
ARP
 A uses the Address Resolution Protocol (ARP) to discover
B’s NIC Ethernet address.
 A broadcasts an Ethernet frame on the LAN.
 The payload of the frame is an ARP request: who has
address 148.4.20.10 (B’s IP address).
 All computers in the LAN hear the broadcast.
 The computer whose IP address is 148.4.20.10 (B) replies
to A: my ethernet address is aa:bb:cc:dd:ee:ff.
55
DEEPAK.P
ARP
 Now A has the ethernet address of B ’s NIC, and can send
the IP datagram to B encapsulated within an Ethernet
frame with destination address aa:bb:cc:dd:ee:ff.
56
DEEPAK.P
ARP request/reply Ethernet Frame
57
DEEPAK.P
ARP Header format
58
DEEPAK.P
ARP Header
 Hardware type (HTYPE)
 This field specifies the network protocol type.
 Example: Ethernet is 1.
 Protocol type (PTYPE)
 This field specifies the internetwork protocol for which the
ARP request is intended.
 For IPv4, this has the value 0x0800. The permitted PTYPE
values share a numbering space with those for Eather type
 Hardware length (HLEN) Length (in octets) of a hardware
address.
 Ethernet addresses size is 6.
59
DEEPAK.P
ARP Header
 Protocol length (PLEN)
 Length (in octets) of addresses used in the upper layer
protocol. (The upper layer protocol specified in PTYPE.) IPv4
address size is 4.
 Operation Specifies the operation that the sender is
performing: 1 for request, 2 for reply.
 Sender hardware address (SHA) media address of the sender.
60
DEEPAK.P
ARP Header
 Sender protocol address (SPA) internetwork address of the
sender.
 Target hardware address (THA) media address of the
intended receiver.
 This field is ignored in requests.
 Target protocol address (TPA) internetwork address of the
intended receiver.
 ARP protocol parameter values have been standardized and
are maintained by the Internet Assigned Numbers
Authority (IANA).
61
DEEPAK.P
ICMP
62
DEEPAK.P
ICMP
 Data delivery using IP datagram is the best delivery
scheme but it has two deficiencies.
 Lack of error control
 Lack of assistance mechanism.
 These ICMP can compensate these deficiencies.
 It is a companion to IP protocol
63
DEEPAK.P
ICMP
Network Layer
IGMP
IP
ICMP
ARP
RARP
64
DEEPAK.P
ICMP
 Internet Control Message Protocol
 It is a network layer protocol
 Used mostly for error reporting at the IP level.
 But its message is not passed directly to the data link layer
 The messages are first encapsulated inside IP datagram
before going to the lower layer
65
DEEPAK.P
Encapsulation of ICMP messages
66
DEEPAK.P
ICMP
ICMP MESSAGE
ERROR REPORTING
67
DEEPAK.P
QUERY
ICMP
 The error reporting message reports problems occurred at
router or a host.
 The query message , which occurs in pairs , help a host or
a network manager to get specific information from a
router or another host
 ICMP does not correct errors , it simply reports them.
68
DEEPAK.P
ICMP error reporting
Error reporting
Destination
Source
un reachable Quench
Time
exceeded
Paramete
r
problems
Source quench--- Flow control to IP
Re direction
Parameter problem– Any ambiguity in the header part
Re direction--- Host routing table updation is caaried out
69
DEEPAK.P
ICMP
 For example, if the TTL of the IP datagram reaches 0
when it reaches a router, the datagram is dropped by
the router, and the router sends an ICMP message back
to the source of the datagram to inform it that the
datagram was dropped because its TTL reached 0 (Time
Exceeded)
 If a router does not know how to route an IP
datagram, it drops the datagram an send an ICMP
message back to the source (Destination
unreachable).
70
DEEPAK.P
ICMP Messages with message number
71
DEEPAK.P
ICMP header
72
DEEPAK.P
ICMP header
 Type field defines the type of message
 Code field specifies reason for particular message
 Checksum for error reporting
73
DEEPAK.P
DHCP
74
DEEPAK.P
DHCP
 Dynamic Host Configuration Protocol
 Allows a computer to obtain an IP address and other parameters
from a DHCP server
 A DHCP server is a program running in some fixed computer in the
LAN that has been configured to assign IP addresses from a given
range to other computers in the LAN that request them
 The DHCP server also provides things like default routes, and DNS
server addresses
75
DEEPAK.P
DHCP
 DHCP requests are broadcasted within the local LAN (frame dest
ff:ff:ff:ff:ff:ff)
 If the DHCP server is in a different LAN, the request won’t reach
that server.
 One way around this is to configure some other computer in the
LAN as a dhcp relay agent : the relay will intercept the DHCP
request and forward it to the DHCP server on the other LAN
 Simplifies management, as only one DHCP sever needs to be
configured for the entire network, rather than having to configure
separate DHCP servers for each LAN
76
DEEPAK.P
Subnetting
77
DEEPAK.P
Subnet
 A sub network, or subnet, is a logically visible subdivision of an IP
network.
 The practice of dividing a network into two or more networks is called
subnetting.
 All computers that belong to a subnet are addressed with a common,
identical, most-significant bit-group in their IP address
78
DEEPAK.P
Subnet
 Subnetting an IP Network can be done for a variety of reasons,
including organization, use of different physical media (such as
Ethernet, FDDI, WAN, etc.), preservation of address space, and
security.
 The most common reason is to control network traffic.
79
DEEPAK.P
IP Packet
80
DEEPAK.P
IP Packet
81
DEEPAK.P
IP Packet
An IP packet has two fundamental components:

IP header
1.



Payload
2.


82
IP header contains many fields that are used by routers to forward the packet from
network to network to a final destination.
Contains layer 3 info
Fields within the IP header identify the sender, receiver, and transport protocol
and define many other Parameters.
Represents the information (data) to be delivered to the receiver by the sender.
Contains data & upper-layer info
DEEPAK.P
IP Versions
83
DEEPAK.P
IPV4
84
DEEPAK.P
IPV4
 Internet Protocol is one of the major protocol in TCP/IP
protocols suite.
 This protocol works at Network layer of OSI model and at
Internet layer of TCP/IP model.
 Thus this protocol has the responsibility of identification of
hosts based upon their logical addresses and to route data
between/among them over the underlying network.
 IPv4 is a connectionless protocol for use on packet-switched
networks.
85
DEEPAK.P
IPV4
 Internet Protocol version 4 (IPv4) is the fourth version in
the development of the Internet Protocol (IP) Internet, and
routes most traffic on the Internet.
 However, a successor protocol, IPv6, has been defined and is
in various stages of production deployment.
 IPv4 is described in IETF publication RFC 791
 It operates on a best effort delivery model, in that it does not
guarantee delivery, nor does it assure proper sequencing or
avoidance of duplicate delivery.
86
DEEPAK.P
IPV4
 IPv4 uses 32-bit (four-byte) addresses, which limits the address
space to 4294967296 (232) addresses.
87
DEEPAK.P
IPv4 - Packet Structure
 The encapsulated data is referred to as IP Payload.
 IP header contains all the necessary information to deliver the
packet at the other end.
88
DEEPAK.P
IPv4 - Packet Structure
89
DEEPAK.P
IPv4 - Addressing
 IPv4 supports three different type of addressing modes:
 Unicast Addressing Mode:
 In this mode, data is sent only to one destined host.
 The Destination Address field contains 32- bit IP address of the
destination host.
 Here client sends data to the targeted server
90
DEEPAK.P
IPv4 – Unicast Addressing
91
DEEPAK.P
IPv4 – Broadcast Addressing Mode:
 In this mode the packet is addressed to all hosts in a network
segment.
 The Destination Address field contains special broadcast address i.e.
255.255.255.255.
 When a host sees this packet on the network, it is bound to process it.
 Here client sends packet, which is entertained by all the Servers:
92
DEEPAK.P
IPv4 – Broadcast Addressing Mode:
93
DEEPAK.P
IPv4 – Multicast Addressing Mode:
 This mode is a mix of previous two modes, i.e. the packet
sent is neither destined to a single host nor all the host on
the segment.
 In this packet, the Destination Address contains special address which
starts with 224.x.x.x and can be entertained by more than one host.
94
DEEPAK.P
IPv4 – Multicast Addressing Mode:
95
DEEPAK.P
IPV6
96
DEEPAK.P
IPV6
 Internet Protocol version 6 (IPv6) is the latest revision of the
Internet Protocol (IP), the communications protocol that
provides an identification and location system for
computers on networks and routes traffic across the
Internet.
 IPv6 was developed by the Internet Engineering Task Force
(IETF) to deal with the long-anticipated problem of IPv4 address
exhaustion.
 IPv6 is an Internet Layer protocol for packet-switched
internetworking and provides end-to-end datagram transmission
across multiple IP networks,
97
DEEPAK.P
IPV6
98
DEEPAK.P
IPV6 & IP V 4
99
DEEPAK.P
IPV6 & IP V 4
100
DEEPAK.P
Routing
101
DEEPAK.P
Routing
 Routing means finding a suitable path for a packet from sender to
destination
102
DEEPAK.P
Routing
 Routing is the main function of the network layer.
 Network layer protocols responsible for deciding which output
line an incoming packet should be transmitted on.
 Routing is usually performed by a dedicated device called a
router.
 The path with lowest cost is considered as best.
103
DEEPAK.P
Routing
 The routing algorithm is the part of a network layer software responsible






104
for deciding which output line a packet should be transmitted on
Each router stores information about forwarding in a routing table
– Initialized at system initialization
– Must be updated as network topology changes
A routing table contains a list of destination networks and next hop for each
destination
Note that a router has several IP addresses!
– One IP address per interface
DEEPAK.P
Classification of Routing
 Routing schemes differ in their delivery semantics:
 Unicast: delivers a message to a single specific node.
 Broadcast: delivers a message to all nodes in the network.
 Multicast: delivers a message to a group of nodes that have
expressed interest in receiving the message.
 Anycast: delivers a message to any one out of a group of
nodes, typically the one nearest to the source.
 Geocast: delivers a message to a geographic area.
105
DEEPAK.P
Classification of Routing
 Routing can be classified in to two
 Static Routing or Non adaptive
 Do not consider measurement and estimate of current
traffic and topology on their routing decisions
 Eg. Flooding, Flow based routing, Shortest path
 Dynamic Routing or Adaptive
 Change routing decisions to reflect changes in topology
 Eg. Distance vector routing , Link state routing
106
DEEPAK.P
Routing Protocols
Routing Protocols
Interior (Routing
inside an
autonomous System)
OSPF(Open
shortest path
first
107
DEEPAK.P
RIP(Routing
information
Protocol
Exterior (Routing
between autonomous
system)
BGP (Border
gateway Protocol)
Desirable Properties of Routing
Algorithms
108
DEEPAK.P
Static Routing
109
DEEPAK.P
Flooding
 It is a static algorithm
 Every incoming packet is sent out on every
outgoing line except the one it arrived on.
 It will generate vast no of duplicate packets.
110
DEEPAK.P
Flooding
111
DEEPAK.P
Application of Flooding
 Military application
 Distributed database application
 Wireless network
112
DEEPAK.P
Selective Flooding
 Variation of flooding is selective flooding
 Do not send every incoming packet out on every
line.
 It sends to the line that are going
approximately in the right direction.
113
DEEPAK.P
Flow-based Routing
 Similar in spirit to minimum distance, but takes
traffic flow into consideration.
 From the known average amount of traffic and the
average length of a packet you can compute the
mean packet delays using queuing theory.
 Flow-based routing then seeks to find a routing
table to minimize the average packet delay
through the subnet.
114
DEEPAK.P
Flow-based Routing
 Assume that traffic is huge from A to B
B
C
D
A
E
G
F
H
TAKE THE ROUTE AGEFC INSTEAD OF ABC
115
DEEPAK.P
Shortest path
 Links between routers have a cost associated
with them.
 In general it could be a function of
 Distance
 Bandwidth
 Average traffic
 Communication cost
 Mean queue length
 Measured delay
 Router processing speed
116
DEEPAK.P
Shortest path algorithms
 The shortest path algorithm just finds the least expensive
path through the network, based on the cost function.
 Dijkstras algorithms
 Bellman-ford algorithms
117
DEEPAK.P
Dynamic Routing
118
DEEPAK.P
Distance vector Routing
119
DEEPAK.P
Distance Vector Routing
 In this routing each router 'telling the neighbors about the
whole network'.
 Each router maintains a table called vector.
 Each router periodically shares its knowledge about the
entire network with its neighbors.
 The working principle of distance vector routing includes
 Knowledge about the whole network
 Routing only to neighbors
 Information sharing at regular intervals
120
DEEPAK.P
Distance Vector Routing
121
DEEPAK.P
Distance Vector Routing
 In distance vector algorithms, each router has to follow the
following steps:
 It counts the weight of the links directly connected to it
and saves the information to its table.
 In a particular period of time, the router sends its table to its
neighbor routers (not to all routers) and receives the
routing table of each of its neighbors.
 Based on the information the router receives from its neighbors'
routing tables, it updates its own.
122
DEEPAK.P
Distance Vector Routing
 Distance vector routing is also called
 Distributed bellman- ford algorithm
 Ford-Fulkerson algorithm

 In distance vector routing Cost is based on
 Hop count
 Time delay
 No of packets in a queue.
123
DEEPAK.P
Distance Vector Routing
124
DEEPAK.P
Distance Vector Routing
 The cost of each link is set to 1.
 Thus, the least cost path is simply the path with the fewer
hops.
 The table below represents each node’s knowledge about the
distance to all other nodes:
125
DEEPAK.P
Distance Vector Routing
 Initially, each node sets a cost of 1 to its directly connected
neighbors and infinity to all the other nodes.
 Below is shown the initial routing table at node A:
126
DEEPAK.P
Distance Vector Routing
 During the next step, every node sends a message to its
directly connected neighbors. That message contains the
node's personal list of distances.
127
DEEPAK.P
Distance vector Routing
128
DEEPAK.P
A
H
K
J
0
24
20
21
8
A
12
36
31
28
20
A
25
18
19
36
28
I
40
27
8
24
20
H
14
7
30
22
17
I
23
20
19
40
30
I
18
A
17
31
6
31
18
H
20
0
19
12
H
21
0
14
22
10
I
9
11
7
10
0
-
24
22
22
0
6
K
29
33
9
9
15
K
JA delay is 8
129
I
JI delay is
10
DEEPAK.P
JH delay is
12
JK delay is
6
New Routing Table for J
Distance Vector Routing
 Problem (assume that cost is 1 for each link)
130
DEEPAK.P
Link state Routing
131
DEEPAK.P
Link state Routing
 Link state algorithms are sometimes characterized informally as
each router 'telling the other router about its
neighbors'.
 The concept has 5 parts
 Discover it’s neighbors and learn their network address
 Measure the delay or cost to each of it’s neighbors.
 Construct a packet telling all it has learned.
 Send this packet to all other routers.
 Compute the shortest path to every other router.
132
DEEPAK.P
Link state Routing
neighbor to all routers
neighbor to all routers
neighbor to all routers
neighbor to all routers
neighbor to all routers
133
DEEPAK.P
neighbor to all routers
Routing for Mobile
Hosts
134
DEEPAK.P
Routing for mobile Hosts
 Wireless hosts are often mobile, changing location over time
 This mobility of a wireless host may cause the host to connect to
Different networks at different points of time.
135
DEEPAK.P
CIDR
136
DEEPAK.P
CIDR
137
DEEPAK.P
CIDR
138
DEEPAK.P