Data Communication & Network: Unit - 3

Thiruvalluvar University Model Constituent
College of Arts and Science

Tittagudi – 606 106
Data Communication & Network
Unit -3
Network Layer
Dr. S. P. Ponnusamy
Assistant Professor
1
Department of Computer Science Data & Communication Network
• Network Layer
 Design issues
 Routing Algorithms
 Shortest path routing
 Flooding
 Broadcast
 Multicast routing
• Congestion Control
• Internetworking.
2
2.1 Design Issues of Network Layer
3
2.1 Network Layer – Design Issues

• Store-and-forward packet switching
• Services provided to transport layer
• Implementation of connectionless service
• Implementation of connection-oriented service
• Comparison of virtual-circuit and datagram networks
4
2.1 Data Link Layer – Design Issues

The data link layer has a number of specific
functions it can carry out. These functions include
1. Providing a well-defined service interface to
the network layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow
receivers are not swamped by fast senders.
5
2.1 Store-and-Forward Packet Switching
6
7
8

Cut-Through Switch
9

Comparison of Switching Techniques
10
Services Provided to the Transport Layer
1. Services independent of router technology.

2. Transport layer shielded from number, type,
topology of routers.
3. Network addresses available to transport
layer use uniform numbering plan
– even across LANs and WANs
11
2.1 Implementation of Connectionless Service - Datagram
12
2.1 Implementation of Connectionless Service
13
2.1 Implementation of Connection-Oriented Service –

Virtual Circut
Routing within a virtual-circuit network

14
2.1 Comparison of Virtual-Circuit and Datagram Networks
15
2.2 Routing Algorithms

• Optimality principle
• Shortest path algorithm
• Flooding
• Distance vector routing
• Link state routing
• Routing in ad hoc networks
• Broadcast routing
• Multicast routing
• Anycast routing
• Routing for mobile hosts
• Routing in ad hoc networks
16

Router
• A router is located at the gateway

• it routes packets as they travel from one network
to another network(s).
• A router can be hardware device with a software
application
• The router is connected to at least two networks
17

Router
• What does a router do?

 find path
 forward packet, forward packet, forward packet, forward
packet...
 find alternate path
 forward packet, forward packet, forward packet, forward
packet…
 repeat until powered off
18

Router – Routing Vs Forwarding
• Routing = building maps and giving directions

• Forwarding = moving packets between
interfaces according to the “directions”
19

Router – Network Performance
• Two Performance Measures
– Quantity of Service (Throughput)
• How much data travels across the net?
• How long does it take to transfer long files?
– Quality of Service (Average packet delay)
• How long does it take for a packet to arrive at its destination?
• How responsive is the system to user commands?
• Can the network support real-time delivery such as audio
and video?
20

Fairness vs. Efficiency
 Quantity of service versus quality of service.

 To optimize throughput, saturate paths between A and A’, B
and B’, and C and C’, but what happens to the response time
from X to X’?
Network with a conflict between fairness and efficiency.
21

Types of routing algorithm
• Nonadaptive (static)
– Do not use measurements of current conditions
– Static routes are downloaded at boot time
• Adaptive Algorithms(dynamic)
– Change routes dynamically
• Gather information at runtime
 locally
 from adjacent routers
 from all other routers
• Change routes
 When load changes
 When topology changes
22

a. Shortest Path Routing (non-adaptive algorithm)
• Given a network topology and a set of weights
describing the cost to send data across each
link in the network
• Find the shortest path from a specified source
to all other destinations in the network.
• Shortest path algorithm first developed by E.
W. Dijkstra
23

a. Shortest Path Routing (non-adaptive algorithm)
24

b. Flooding (non-adaptive algorithm)
• No network information is required
• Packet send by node to every neighbor
• Incoming packets retransmitted on every link without
incoming link
• Eventually a numbers of copies will arrives at destination
• Each packet is uniquely numbered so duplicate can be
discarded
• Nodes can remember packets already forwarded to keep
network load in bounds
25

26

• All nodes are visited
• All possible routes are tried
• Selective Flooding
– Flood only in the direction of the destination
• Practical example
– Mobile when user 1 dial number to call user 2,the mobile
station/company searches for user 2 in whole country if
user 2 is out of reach. Then this process take few seconds
– Distributed Databases
27

c. Broadcast Routing
• Send a separate packet to each destination
• Use flooding
• Use multi-destination routing
– Each packet contains a list of destinations
– Routers duplicate packet for all matching outgoing lines
• Use spanning tree routing
– a subset of the subnet that includes all routers but
contains no loops.
28

c. Broadcast Routing – Spanning Tree Broadcasting
• Uses the minimum
number of packets
necessary
• Routers must be able to
compute spanning tree
– Available with link state
routing
(a) A subnet. (b) A sink tree.
– Not available with
distance vector routing
29

• Reverse Path Forwarding
– Use When knowledge of a spanning tree is not available
– Provides an approximation of spanning tree routing
– Routers check to see if incoming packet arrives from the
same line that the router uses to route outgoing packets
to the broadcast source
• If so, the router duplicates the packet on all other outgoing
lines
• Otherwise, the router discards the packet
30

tree built by reverse path forwarding

31

d. Multicast Routing
• A method to broadcast packets to well defined
groups
• Hosts can join multicast groups.
– They inform their routers
– Routers send group information throughout the subnet
• Each router computes a spanning tree for each
group. The spanning tree includes all the routers
needed to broadcast data to the group
32

d. Multicast Routing
(a) A network. (b) A spanning tree for the leftmost router.

(c) A multicast tree for group 1. (d) A multicast tree for group 2.
33
2.3 Congestion Control Algorithms
34
• General Principles of Congestion Control

• Congestion Prevention Policies
• Congestion Control in Virtual-Circuit Subnets
• Congestion Control in Datagram Subnets
• Load Shedding
• Jitter Control
35

Congestion
 very high traffic
 a queue build up (3 in
& 1 out)
 Increase buffer, gets
worse
 Slow processors
 low-bandwidth lines
When too much traffic is offered, congestion sets in and

performance degrades sharply.
36

General Principles
1. Monitor the system .

• detect when and where congestion occurs.
2. Pass information to where action can be
taken.
3. Adjust system operation to correct the
problem.
37

General Principles
• Analogy with Control Theory:
 Open-loop, and
 Closed-loop approach.
• Open-loop approach
 Attempt to prevent problems rather than correct them
 Does not utilize runtime feedback from the system
 Problem is solved at the design cycle
 Once the system is running midcourse correction are NOT made.
 Tools for doing open-loop control:
o Deciding when to accept new traffic,
o Deciding when to disregard packets and which ones.
o Making scheduling decision at various points in the network.
o Note that all those decisions are made without regard to the current state of
the network.
38

General Principles
 Closed-loop approach
 Uses feedback (measurements of system performance) to make
corrections at runtime.
 It is based on the principle of feedback-loop. The approach has
three parts when applied to congestion control:
 Monitor the system to detect when and where congestion occurs,
 Pass this information tot places where action can be taken
 Adjust system operation to correct the problem.
39

General Principles
40

Congestion Prevention Policies
Policies that affect

congestion.
41

Congestion Control in Virtual – Circuit Subnets
(a) A congested subnet. (b) A redrawn subnet, eliminates

congestion and a virtual circuit from A to B.
42

Congestion Control in Virtual – Circuit Subnets
• admission control.
 once congestion has been signaled, no more virtual circuits are
set up until the problem has gone away.
 Thus, attempts to set up new transport layer connections fail.
• Negotiate an agreement between the host and subnet when
a virtual circuit is set up.
• This agreement normally specifies the volume and shape of
the traffic, quality of service required, and other parameters.
• To keep its part of the agreement, the subnet will typically
reserve resources along the path when the circuit is set up.
43

Congestion Control in Datagram Subnets
44

Congestion Control in Datagram Subnet - Methods

 The Warning Bit
 Choke Packets
 Load Shedding
 Random Early Detection
 Jitter Control
45

Warning Bit
 A special bit in the packet header is set by the router
to warn the source when congestion is detected.
 When the packet arrived at its destination, the
transport entity copied the bit into the next
acknowledgement sent back to the source.
 The source then cut back on traffic.
46

Warning Bit / Backpressure
47

Choke Packets
 A specialized packet that is used for flow control along a network.
 A router detects congestion by measuring the percentage of buffers
in use, line utilization and average queue lengths.
 When it detects congestion, it sends choke packets across the
network to all the data sources associated with the congestion.
 The original packet is tagged (a header bit is turned on) so that it
will not generate any more choke packets farther along the path and
is then forwarded in the usual way.
 When the source host gets the choke packet,
 it is required to reduce the traffic sent to the specified
destination by X percent
48

Choke Packets
49

Choke Packets
 Since other packets aimed at the same destination are probably
already under way and will generate yet more choke packets,
 the host should ignore choke packets referring to that
destination for a fixed time interval.
 After that period has expired, the host listens for more choke
packets for another interval.
 If one arrives, the line is still congested, so the host reduces the
flow still more and begins ignoring choke packets again.
 If no choke packets arrive during the listening period, the host may
increase the flow again.
50

Choke Packets / hop-by-hop

 Over long distances or at high speeds choke packets are not
very effective.
 A more efficient method is to send to choke packets hop-by-
hop.
 This requires each hop to reduce its transmission even
before the choke packet arrive at the source.
51

Choke Packets / hop-by-hop
52

Load Shedding
 When buffers become full, routers simply discard packets.
 Which packet is chosen to be the victim depends on the
application and on the error strategy used in the data link
layer.
 For a file transfer, for, e.g. cannot discard older packets
since this will cause a gap in the received data.
 For real-time voice or video it is probably better to throw
away old data and keep new packets.
 Get the application to mark packets with discard priority.
53

Random Early Detection

 This is a proactive approach in which the router discards one or
more packets before the buffer becomes completely full.
 Each time a packet arrives, the RED algorithm computes the
average queue length, avg.
 If avg is lower than some lower threshold, congestion is assumed to
be minimal or non-existent and the packet is queued.
 If avg is greater than some upper threshold, congestion is assumed
to be serious and the packet is discarded.
 If avg is between the two thresholds, this might indicate the onset
of congestion. The probability of congestion is then calculated.
54
55

Jitter Control
 For applications such as audio and video streaming, it does not
matter much if the packets take 20 msec or 30 msec to be
delivered, as long as the transit time is constant.
 The variation (i.e., standard deviation) in the packet arrival times is
called jitter.
 When a packet arrives at a router, the router checks to see how
much the packet is behind or ahead of its schedule.
 This information is stored in the packet and updated at each hop.
 If the packet is ahead of schedule, it is held just long enough to get
it back on schedule.
 If it is behind schedule, the router tries to get it out the door
quickly.
56

Jitter Control
57
End
58

Data Communication & Network: Unit - 3

Uploaded by

Copyright:

Available Formats

Data Communication & Network: Unit - 3

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Communication & Network: Unit - 3

Uploaded by

Copyright:

Available Formats

Thiruvalluvar University Model Constituent

College of Arts and Science

Data Communication & Network

2.1 Design Issues of Network Layer

2.1 Network Layer – Design Issues

2.1 Data Link Layer – Design Issues

2.1 Store-and-Forward Packet Switching

2.1 Store-and-Forward Packet Switching

2.1 Store-and-Forward Packet Switching

2.1 Store-and-Forward Packet Switching

2.1 Store-and-Forward Packet Switching

Services Provided to the Transport Layer

1. Services independent of router technology.

2.1 Implementation of Connectionless Service - Datagram

2.1 Implementation of Connectionless Service

2.1 Implementation of Connection-Oriented Service –

Routing within a virtual-circuit network

2.1 Comparison of Virtual-Circuit and Datagram Networks

2.2 Routing Algorithms

2.2 Routing Algorithms

• A router is located at the gateway

2.2 Routing Algorithms

• What does a router do?

2.2 Routing Algorithms

• Routing = building maps and giving directions

2.2 Routing Algorithms

2.2 Routing Algorithms

 Quantity of service versus quality of service.

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

2.2 Routing Algorithms

tree built by reverse path forwarding

2.2 Routing Algorithms

2.2 Routing Algorithms

(a) A network. (b) A spanning tree for the leftmost router.

2.3 Congestion Control Algorithms

2.3 Congestion Control Algorithms

• General Principles of Congestion Control

2.3 Congestion Control Algorithms

When too much traffic is offered, congestion sets in and

2.3 Congestion Control Algorithms

1. Monitor the system .

2.3 Congestion Control Algorithms

2.3 Congestion Control Algorithms

2.3 Congestion Control Algorithms

2.3 Congestion Control Algorithms

Policies that affect

2.3 Congestion Control Algorithms

(a) A congested subnet. (b) A redrawn subnet, eliminates

2.3 Congestion Control Algorithms

2.3 Congestion Control Algorithms