UNIT-III

The Network Layer

 Network Layer is majorly focused on getting packets from
the source to the destination, routing, error handling and
congestion control.
Addressing:
Maintains the address at the frame header of both source
and destination and performs addressing to detect various
devices in network.
Packeting:
This is performed by Internet Protocol. The network layer
converts the packets from its upper layer.
Routing:
It is the most important functionality. The network layer
chooses the most relevant and best path for the data
transmission from source to destination.
Inter-networking:
It works to deliver a logical connection across multiple
devices.
 Network Layer Design Isues

• Store-and-Forward Packet Switching

• Services Provided to the Transport Layer
• Implementation of Connectionless Service
• Implementation of Connection-Oriented Service
• Comparison of Virtual-Circuit and Datagram Subnets
1)Store-and-Forward Packet Switching

fig 5-1

The environment of the network layer protocols.

• The major components of the network are the carrier’s
equipment(routers connected by transmission lines) and customers’s
equipment
• Host H1 is directly connected to one of the ISP’s routers, A, perhaps
as a home computer that is plugged into a DSL modem.
• Host H2 is on a LAN which might be an office Ethernet, with a
router F, owned and operated by customer.
• A host with a packet to send transmits it to the nearst router,either on
its own LAN or over a point-to-point link to the ISP.
• A host with a packet to send transmits it to the nearest router, either
on its own LAN or over a point-to-point link to the carrier.
• The packet is stored until it has fully arrived and the link has finished
its processing by verifying the checksum.
• Then it is forwarded to the next router along the path until it reaches
the destination host, where it is delivered.
• This mechanism is called store-and-forward packet switching
2)Services Provided to the Transport Layer

Through the network/transport layer interface, the network layer

transfers it’s services to the transport layer.

Logical Addressing − Network layer adds header to incoming packet

which includes logical address to identify sender and receiver.

Routing − It is the mechanism provided by Network Layer for routing

the packets to the final destination in the fastest possible and efficient
way.
Based on the connections there are 2 types of services
provided :

•Connectionless – The routing and insertion of packets

into subnet is done individually. No added setup is
required.

•Connection-Oriented – Subnet must offer reliable

service and all the packets must be transmitted over a
single route.
 What is a subnet?
 A subnet, or subnetwork, is a network
inside a network.
 Subnets make networks more efficient.
 Through subnetting, network traffic
can travel a shorter distance without
passing through unnecessary routers
to reach its destination.
 3) Implementation of Connectionless
Service
a) When connectionless service is offered, packets are
frequently called Datagrams (just like telegrams)
because individual packets are injected to the subnet
and are routed individually.
b) No advance setup is required. Subnets are called
Datagram subnets.
c) When Connection oriented service is provided, then
before any packet is sent a path from source router to
destination router is established.
d) This connection is called Virtual Circuit and the subnet
is called Virtual Circuit subnet.
Step 1 − Suppose there is a process P1 on host H1 and is having a message to deliver to P2 on host H2. P1 hands the message to the transport layer along with instructions to be delivered to P2 on H2.

Step 2 − Transport Layer code is running on H1 and within the operating system. It prepends a transport header to the message and the end result is given to the network layer.

Step 3 − Let us assume for this example a packet which is four times heavier than the maximum size of the packet, then the packet is broken to four different packets and each of the packet is sent to the router A using point to point protocol
and from this point career takes over.

Step 4 − Each router will have an internal table saying where packets to be sent. Every table entry is a pair consisting of a destination and outgoing line to use for that destination. Only directly connected lines can be used.
 Step 5 − For example A has only two outgoing lines to B and C,
therefore every incoming packet must be sent to one of these
routers, even if the ultimate destination will be some other router.

Step 6 − As the packets arrived at A, packet 1,2,3 and 4 were

stored in brief. Then every packet is moved to C as per A’s table.
Packet 1 is forwarded to E and then moved to F. When packet 1 is
moved to F, then it will be encapsulated in a data link layer and
sent to H2 over to LAN. Packet 2 and 3 will also follow the same
route.

Step 7 − When packet 4 reaches A, then it was sent to router B,

even if the destination was F. For some purpose A decided to send
packet 4 through a different route. It was because of the traffic jam
in ACE path and the routing table was updated. Routing Algorithm
decides routes, makes routing decisions and manages routing

24.12
Implementation of Connectionless Service

Routing within a diagram subnet.

4)Implementation of Connection Oriented service:

• To use a connection-oriented service, first we

establishes a connection, use it and then release it.
• In connection-oriented services, the data packets are
delivered to the receiver in the same order in which
they have been sent by the sender.
Virtual Circuit Switched Connection
• The data stream is transferred over a packet switched
network, in such a way that it seems to the user that
there is a dedicated path from the sender to the
receiver.
• A virtual path is established here. While, other
connections may also be using the same path.
Implementation of Connection-Oriented Service

Routing within a virtual-circuit subnet.

a) For connection oriented service , we need a virtual circuit network.
b) With connection oriented service, each packet carries an identifier
telling which virtual circuit it belongs.
Comparison of Virtual-Circuit and
Datagram Subnets

5-4
 Routing
 Routing is the process of determining paths through a network
for sending data packets.
 Routing ensures that data moves effectively from source to
destination, making the best use of network resources and
ensuring consistent communication.
 The process of routing involves making various routing decisions
to ensure reliable & efficient delivery of the data packet by finding
the shortest path using various routing metrics

24.18
Types of Routing

 Routing is typically of 3 types, each serving its

purpose and offering different functionalities.
 1. Static Routing

 Static routing is also called as “non-adaptive

routing”. In this, routing configuration is done
manually by the network administrator.
 Let’s say for example, we have 5 different
routes to transmit data from one node to
another, so the network administrator will have
to manually enter the routing information by
assessing all the routes.
.

24.20
 Advantages of Static
Routing
 No routing overhead for the router CPU
which means a cheaper router can be
used to do routing.
 It adds security because only an only
administrator can allow routing to
particular networks only.
 No bandwidth usage between routers.

24.21
 Disadvantage of Static
Routing
 For a large network, it is a hectic task for
administrators to manually add each route for
the network in the routing table on each
router.
 The administrator should have good
knowledge of the topology. If a new
administrator comes, then he has to manually
add each route so he should have very good
knowledge of the routes of the topology

24.22
 Dynamic Routing
 Dynamic routing makes automatic adjustments of the
routes according to the current state of the route in the
routing table.
 Dynamic routing uses protocols to discover network
destinations and the routes to reach them. RIP and OSPF
are the best examples of dynamic routing protocols.
 Automatic adjustments will be made to reach the network
destination if one route goes down. A dynamic protocol has
the following features:
 The routers should have the same dynamic protocol
running in order to exchange routes.
 When a router finds a change in the topology then the
router advertises it to all other routers.
 Advantages of Dynamic Routing
Easy to configure.

More effective at selecting the best route to a

destination remote network and also for

discovering remote networks.
Disadvantage of Dynamic Routing
Consumes more bandwidth for communicating

with other neighbors.

Less secure than static routing.

24.24
 Routing Algorithms
• Shortest Path Routing
• Flooding
• Distance Vector Routing
• Hierarchical Routing
• Broadcast Routing
• Multicast Routing
 Routing Algorithm
 A routing algorithm is a procedure that lays down
the route or path to transfer data packets from
source to the destination.
 They help in directing Internet traffic efficiently.
 After a data packet leaves its source, it can choose
among the many different paths to reach its
destination.
 Routing algorithm mathematically computes the
best path, i.e. “least – cost path” that the packet
can be routed through.

24.26
 Shortest path algorithm
(Non Adaptive)
 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

24.27
 Mark the source node as permanent.
 Designate the source node as the working node.
 Set the tentative distance to all other nodes to infinity.
 While some nodes are not marked permanent
 Compute the tentative distance from the source to all
nodes adjacent to the working node.
 If this is shorter than the current tentative distance replace
the tentative distance of the destination and record the
label of the working node there.
 Examine ALL tentatively labeled nodes in the graph. Select
the node with the smallest value and make it the new
working node. Designate the node permanent.
 Shortest Path Routing

The first 5 steps used in computing the shortest path from A to D.

The arrows indicate the working node.
 Flooding

a) It is a static algorithm
b) Every incoming packet is sent out on every outgoing line except the
one it arrived on.
c) Many duplicates
Rule used at each node:
• Sends an incoming message on to all other neighbors
• Remember the message so that it is only flood once
  Flooding is a non-adaptive routing
technique following this simple method:
when a data packet arrives at a router, it is
sent to all the outgoing links except the
one it has arrived on.

 For example, let us consider the network

in the figure, having six routers that are
connected through transmission lines.
24.31
 An incoming packet to A, will be sent to B,
C and D.

B will send the packet to C and E.

C will send the packet to B, D and F.

D will send the packet to C and F.

E will send the packet to F.

F will send the packet to C and E.

24.32
 Applications of Flooding
a) Military applications
b) Distributed database applications
c) Wireless networks
Distance Vector Routing
(DVR)
Distance Vector Routing (DVR) Protocol is a method used by
routers to find the best path for data to travel across a network.
 Each router keeps a table that shows the shortest distance to every
other router, based on the number of hops (or steps) needed to
reach them.
 Routers share this information with their neighbors, allowing them
to update their tables and find the most efficient routes. This
protocol helps ensure that data moves quickly and smoothly
through the network.
 The protocol requires that a router inform its neighbors of topology
changes periodically. Historically known as the old ARPANET
routing algorithm (or known as the Bellman-Ford algorithm).
 How Distance Vector
Algorithm works?
 A router transmits its distance vector to each of
its neighbors in a routing packet.
 Each router receives and saves the most
recently received distance vector from each of
its neighbors.
 A router recalculates its distance vector when:
 It receives a distance vector from a neighbor
containing different information than before.
 It discovers that a link to a neighbor has gone
down.
24.35
 where,
dx(y) - The least distance from x to y

c(x,y)-Node x‘s cost from each of its neighbor v

dv(y)- Distance to each node from initial node

min -selecting shortest distance

24.36
24.37
  The distance to reach a destination
B from router A is:

 A= min{(A->B+B->A),(A->D+D-
>B}= min{8+0,5+infinity} =
min{8,infinity}= 8(B)

24.38
 Distance Vector Routing

(a) A subnet. (b) Input from A, I, H, K, and the new

routing table for J.
Distance Vector Routing (2)

The count-to-infinity problem.

 Link State Routing
Each router must do the following:
1. Discover its neighbors, learn their network address.
2. Measure the delay or cost to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to all other routers.
5. Compute the shortest path to every other router.
 Learning about the Neighbors

(a) Nine routers and a LAN. (b) A graph model of (a).

 Measuring Line Cost

A subnet in which the East and West parts are connected by two lines.
Building Link State Packets

(a) A subnet. (b) The link state packets for this subnet.
Distributing the Link State Packets

The packet buffer for router B in the previous slide (Fig. 5-13).
Hierarchical Routing

Hierarchical routing.
 Broadcast Routing

Reverse path forwarding. (a) A subnet. (b) a Sink tree. (c) The
tree built by reverse path forwarding.
 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.
 Routing for Mobile Hosts

A WAN to which LANs, MANs, and wireless cells are attached.

Routing for Mobile Hosts (2)

Packet routing for mobile users.

 Routing in Ad Hoc Networks

Possibilities when the routers are mobile:

1. Military vehicles on battlefield.
– No infrastructure.

2. A fleet of ships at sea.

– All moving all the time
3. Emergency works at earthquake .
– The infrastructure destroyed.
4. A gathering of people with notebook computers.
– In an area lacking 802.11.
 Route Discovery

a) (a) Range of A's broadcast.

b) (b) After B and D have received A's broadcast.
c) (c) After C, F, and G have received A's broadcast.
d) (d) After E, H, and I have received A's broadcast.
Shaded nodes are new recipients. Arrows show possible reverse routes.
 Route Discovery (2)

Format of a ROUTE REQUEST packet.

Route Discovery (3)

Format of a ROUTE REPLY packet.

 Route Maintenance

(a) D's routing table before G goes down.

(b) The graph after G has gone down.
Node Lookup in Peer-to-Peer Networks

(a) A set of 32 node identifiers arranged in a circle. The shaded ones

correspond to actual machines. The arcs show the fingers from
nodes 1, 4, and 12. The labels on the arcs are the table indices.
(b) Examples of the finger tables.
 Congestion Control Algorithms
• General Principles of Congestion Control
• Congestion Prevention Policies
• Congestion Control in Virtual-Circuit Subnets
• Congestion Control in Datagram Subnets
• Load Shedding
• Jitter Control
 Congestion

 A state occurring in network layer when the

message traffic is so heavy that it slows
down network response time.

 Effects of Congestion
• As delay increases, performance decreases.
• If delay increases, retransmission occurs,
making situation worse.


24.58
 How Congestions Happens

Incoming packets from multiple inputs need to go to same

output line; queue builds up
If insufficient memory, packets lost

Adding memory helps to some point

Even with ∞ memory, congestion gets worse

 delayed packets timeout, retransmitted

 duplicates increase load
 Congestion collapse: load exceeds capacity

24.59
 Congestion

When too much traffic is offered, congestion sets in and

performance degrades sharply.
How Congestions Happens
 Slow processors
 CPU slow in doing bookkeeping tasks
 queues build up

 Low bandwidth lines

 can’t forward packets same as arriving speeds
 Mismatch between system parts
 upgrading some parts only shifts bottleneck

Congestion VS Flow Control

 Congestion control
 make sure subnet is able to carry offered traffic
 global, involve behavior of all hosts

 all factors that diminish carrying capacity

 Flow control
 traffic between a given sender & given receiver
 ensure fast sender not overwhelm slow receiver

 involve feedback from receiver to sender

6
 Approaches to Congestion
Control

24.62
Network Provising

 If more traffic is directed but a low-bandwidth

link is available, definitely congestion occurs.
 Sometimes resources can be added
dynamically like routers and links when there
is serious congestion.
 This is called provisioning, and which
happens on a timescale of months, driven by
long-term trends.
 Traffic Aware Routing
 The first approach we examine is traffic
aware routing.
 These schemes adapted to change in
topology, but not change the load.
 The goal of taking a load into to make most
existing network capacity, routs can be
tailored to traffic patterns that change
during the day as network users wake and
sleep in different zones.
24.65
 • Which is divide into two parts east and west
connect by two links CF and EL.
• Suppose most traffic is between east and west use
connection CF and result in this connection is
heavily loaded with a long delay.
• Include queuing in the weight used for short path
calculation will make EL more attractive.
• New routing tables have been installed, most of the
east-west traffic will go over EL, loading this link CF
will appear to be the shortest path.

24.66
 Admission Control

 It is one of techniques that is widely used in

virtual-circuit networks to keep congestion at bay.
 The idea is do not set up a new virtual circuit
unless the network can carry the added traffic
without becoming congested.
 Admission control can also be combined with
traffic aware routing by considering routes around
traffic hotspots as part of the setup procedure.

24.67
 Suppose a host attached to router A
wants to set up a connection to a
host attached to router B. Normally
this connection passes through one
of the congested routers.

Step 2 − To avoid this situation, we

can redraw the network as shown in
figure (b), removing the congested
routers and all of their lines.

Step 3 − The dashed line indicates a

possible route for the virtual circuit
that avoids the congested routers.

24.68
 Traffic throttling

 Traffic throttling is one of the approaches for

congestion control.
 In the internet and other computer networks,
senders trying to adjust the transmission need to
send as much traffic as the network can readily
deliver.
 Slow down when congestion is approaching
 Monitor resource usage
 utilization of output links
 buffering of queued packets inside router
 number packets lost for lack of buffer space
 Traffic Throttling

 Choke Packets
 most direct way, tell sender directly
 send choke packet back to source
host
 original packet is tagged, so will not
generate another choke packet,
then forwarded as usual

24.70
 Hop‐by‐hop backpressure
 affect every hop it passes through
 provide quick relief at the point of
congestion

24.71
 Hop-by-Hop
Choke Packets

(a) A choke packet that affects

only the source.

(b) A choke packet that affects

each hop it passes through.
  Explicit Congestion Notification
(ECN)
 Step 1 − Instead of generating additional packets to
warn of congestion, a router can tag any packet it
forwards by setting a bit in the packet header to signal
that it is experiencing congestion.

 Step 2 − When the network delivers the packet, the

destination can note that there is congestion and inform
the sender when it sends a reply packet.

 Step 3 − The sender can then throttle its transmissions

as before.

 Step 4 − This design is called explicit congestion

notification and is mostly used on the Internet.
24.73
24.74
Load Shedding

•It is one of the approaches to congestion control.

•Router contains a buffer to store packets and route it to
destination.
•When the buffer is full, it simply discards some packets. It chooses
the packet to be discarded based on the strategy implemented in
the data link layer. This is called load shedding
•Load shedding will use dropping the old packets than new to avoid
congestion. Dropping packets that are part of the difference is
preferable because a future packet depends on full frame.
•To implement an intelligent discard policy, applications must mark
their packets to indicate to the network how important they are.
• When packets have to be discarded, routers can first drop packets
General Principles of Congestion Control

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.
Congestion Prevention Policies

5-26

Policies that affect congestion.

Congestion Control in Virtual-Circuit
Subnets

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

congestion and a virtual circuit from A to B.
 24-5 QUALITY OF SERVICE

Quality of service (QoS) is an internetworking issue

that has been discussed more than defined. We can
informally define quality of service as something a
flow seeks to attain.

Topics discussed in this section:

Flow Characteristics
Flow Classes

24.79
 Figure 24.15 Flow characteristics

24.80
24.81
 24-6 TECHNIQUES TO IMPROVE QoS

In Section 24.5 we tried to define QoS in terms of its

characteristics. In this section, we discuss some
techniques that can be used to improve the quality of
service. We briefly discuss four common methods:
scheduling, traffic shaping, admission control, and
resource reservation.
Topics discussed in this section:
Scheduling
Traffic Shaping
Resource Reservation
Admission Control

24.82
 Scheduling

 Packets from different flows arrive at a

switch or router.
 A good scheduling technique treats the
different flows in a fair and appropriate
manner.
 Several scheduling techniques are designed
to improve QoS
 FIFO Queuing

 Priority Queuing

 Weighted Fair Queuing

24.83
 FIFO Queuing

 In FIFO Queuing, packets wait in a buffer

until the node is ready to process them
 If the average arrival rate is more than the
processing rate , the queue will fill up and
new packets will be discarded

24.84
 Figure 24.16 FIFO queue

24.85
 Priority Queuing

 In Priority Queuing, packets are first

assigned to a priority class.
 Each priority class has its own queue.
 The packets in the highest priority queue
are processed first.
 The packets in the lowest priority queue
are processed last.
 It can provide better QoS than FIFO
Queue

24.86
 Figure 24.17 Priority queuing

24.87
 Disadvantage

 If there is a continuous flow in high-

priority queue, the packets in the
lower priority queues will never have
a chance to be processed. This is
called starvation

24.88
 Weighted fair queuing

 In this technique, the packets are still

assigned to different classes and admitted
to different queues.
 The queues are waited based on the priority
of the queues.
 The system processes packets in each
queue in a round robin fashion with number
of packets selected from each queue based
on the corresponding weight.

24.89
 Figure 24.18 Weighted fair queuing

24.90
 Traffic Shaping

 Traffic Shaping is a mechanism to control

the amount and rate of the traffic sent to
the network.
 Two techniques can shape traffic:
 Leaky bucket

 Token bucket

24.91
 Leaky bucket

Leaky Bucket Algorithm mainly controls the total amount and the
rate of the traffic sent to the network.
Step 1 − Let us imagine a bucket with a small hole at the bottom

where the rate at which water is poured into the bucket is not
constant and can vary but it leaks from the bucket at a constant
rate.
Step 2 − So (up to water is present in the bucket), the rate at which

the water leaks does not depend on the rate at which the water is
input to the bucket.
Step 3 − If the bucket is full, additional water that enters into the

bucket that spills over the sides and is lost.

Step 4 − Thus the same concept applied to packets in the network.

24.92
 Figure 24.19 Leaky bucket

24.93
  In the figure, we assume that the network has
committed a bandwidth of 3 Mbps for a host. The
use of the leaky bucket shapes the input traffic to
make it conform to this commitment.
 In Figure the host sends a burst of data at a rate of
12 Mbps for 2 s, for a total of 24 Mbits of data. The
host is silent for 5 s and then sends data at a rate of
2 Mbps for 3 s, for a total of 6 Mbits of data.
 In all, the host has sent 30 Mbits of data in 10 s. The
leaky bucket smooths the traffic by sending out data
at a rate of 3 Mbps during the same 10 s.

24.94
 Figure 24.20 Leaky bucket implementation

24.95
 Note

A leaky bucket algorithm shapes bursty

traffic into fixed-rate traffic by averaging
the data rate. It may drop the packets if
the bucket is full.

24.96
 Token bucket algorithm
 The leaky bucket algorithm enforces output patterns at the
average rate, no matter how busy the traffic is. So, to deal
with the more traffic, we need a flexible algorithm so that
the data is not lost. One such approach is the token bucket
algorithm.
 Let us understand this algorithm step wise as given below
−
• Step 1 − In regular intervals tokens are thrown into the
bucket f.
• Step 2 − The bucket has a maximum capacity f.
• Step 3 − If the packet is ready, then a token is removed
from the bucket, and the packet is sent.
• Step 4 − Suppose, if there is no token in the bucket, the
packet cannot be sent.
24.97
 Note

The token bucket allows bursty traffic at

a regulated maximum rate.

24.98
 Figure 24.21 Token bucket

24.99
24.100
  In figure (a) the bucket holds two tokens, and three packets
are waiting to be sent out of the interface.
 In Figure (b) two packets have been sent out by consuming
two tokens, and 1 packet is still left.
 When compared to Leaky bucket the token bucket
algorithm is less restrictive that means it allows more traffic.
The limit of busyness is restricted by the number of tokens
available in the bucket at a particular instant of time.
 The implementation of the token bucket algorithm is easy −
a variable is used to count the tokens. For every t seconds
the counter is incremented and then it is decremented
whenever a packet is sent. When the counter reaches
zero, no further packet is sent out.

24.101
24.102
 Jitter Control

(a) High jitter. (b) Low jitter.

Integrated Services( IntServ)

•Integrated service is flow-based QoS model and

designed for IP.

In integrated services, user needs to create a flow in

the network, from source to destination and needs to
inform all routers (every router in the system
implements IntServ) of the resource requirement.
Integrated Services
Intserv is a framework developed by the IETF to
provide individualized QoS guarantees to
individual application sessions.
Two key features lie at the heart of Intserv:
 Reserved resources :A router is supposed to
know what amounts of its resources (buffers,
link b/w) are already reserved for ongoing
sessions
 Call setup : A session requiring QoS
guarantees must first be able to reserve
sufficient resources at each network router on
its source-to-destination path to ensure that
its end-to-end QoS requirement is met.

105
Call Setup Process
QoS call Signaling setup

Request/Reply

106
RSVP : Resource Reservation Protocol
The RSVP protocol allows applications to reserve bandwidth for
their data flows. To implement RSVP the RSVP software must
be present on the receivers, senders and routers.
Principle characteristics:
 Provides reservations for bandwidth in multicast trees (unicast
is handled as a degenerate case of multicast)
 Is receiver-oriented, that is, the receiver of the data flow
initiates and maintains the resource reservation used for that
flow.
Data Flow

Merged Reservations Merged Reservations

Reservation message

107
 RSVP-The ReSerVation Protocol

(a) A network, (b) The multicast spanning tree for host 1.

(c) The multicast spanning tree for host 2.
RSVP-The ReSerVation Protocol (2)

(a) Host 3 requests a channel to host 1. (b) Host 3 then requests a

second channel, to host 2. (c) Host 5 requests a channel to host 1.
 Differentiated Services

 Differentiated Services Code Point (DSCP) is a

means of classifying and managing network
traffic and of providing quality of service (QoS) in
modern Layer 3 IP networks.
 It uses the 6-bit Differentiated Services (DS) field
in the IP header for the purpose of packet
classification.
 Differentiated services (DiffServ) is a computer
networking architecture that specifies a simple
and scalable mechanism for classifying and
managing network traffic and providing quality of
service (QoS) on modern IP networks.
24.110
24.111
24.112
24.113
24.114
24.115
  Expedited forwarding (EF)—
Provides a low-loss, low-latency,
low-jitter, assured-bandwidth, end-
to-end service.

24.116
 Expedited Forwarding

Expedited packets experience a traffic-free network.

Assured forwarding (AF)—Provides a group of values you can
define and includes four subclasses—AF1, AF2, AF3, and AF4
—each with three drop probabilities (low, medium, and high).
 Assured Forwarding

A possible implementation of the data flow for assured forwarding.

 Label Switching and MPLS

Transmitting a TCP segment using IP, MPLS, and PPP.

 Internetworking
• How Networks Differ
• How Networks Can Be Connected
• Concatenated Virtual Circuits
• Connectionless Internetworking
• Tunneling
• Internetwork Routing
• Fragmentation
Connecting Networks

A collection of interconnected networks.

 How Networks Differ

5-43

Some of the many ways networks can differ.

How Networks Can Be Connected

(a) Two Ethernets connected by a switch.

(b) Two Ethernets connected by routers.
Concatenated Virtual Circuits

Internetworking using concatenated virtual circuits.

Connectionless Internetworking

A connectionless internet.
 Tunneling

Tunneling a packet from Paris to London.

 Tunneling (2)

Tunneling a car from France to England.

 Internetwork Routing

(a) An internetwork. (b) A graph of the internetwork.

 Fragmentation

(a) Transparent fragmentation. (b) Nontransparent fragmentation.

 Fragmentation (2)

Fragmentation when the elementary data size is 1 byte.

(a) Original packet, containing 10 data bytes.
(b) Fragments after passing through a network with maximum
packet size of 8 payload bytes plus header.
(c) Fragments after passing through a size 5 gateway.
 The Network Layer in the Internet

• The IP Protocol
• IP Addresses
• Internet Control Protocols
• OSPF – The Interior Gateway Routing Protocol
• BGP – The Exterior Gateway Routing Protocol
• Internet Multicasting
• Mobile IP
• IPv6
 Design Principles for Internet
1. Make sure it works.
2. Keep it simple.
3. Make clear choices.
4. Exploit modularity.
5. Expect heterogeneity.
6. Avoid static options and parameters.
7. Look for a good design; it need not be perfect.
8. Be strict when sending and tolerant when receiving.
9. Think about scalability.
10. Consider performance and cost.
What is an IP Address?
 An IP address is a numerical label
assigned to the devices connected to
a computer network that uses the IP
for communication.
 IP address act as an identifier for a
specific machine on a particular
network. It also helps you to develop
a virtual connection between a
destination and a source.
  Identifying network portion and host portion in an IP address is
the first step of Subnetting. Subnetting can only be done in
host portion. Subnet mask is used to distinguish the network
portion from host portion in an IP address.

 An IP address and a subnet mask both collectively provide a

numeric identity to an interface. Both addresses are always
used together. Without subnet mask, an IP address is an
ambiguous address and without IP address a subnet mask is
just a number.

 Both addresses are 32 bits in length. These bits are divided in

four parts. Each part is known as octet and contains 8 bits.
Octets are separated by periods and written in a sequence .

24.135
 Collection of Subnetworks

The Internet is an interconnected collection of many networks.

 The IP Protocol

The IPv4 (Internet Protocol) header.

• Version − Version no. of Internet Protocol used (e.g. IPv4).
• IHL − Internet Header Length; Length of entire IP header.
• DSCP − Differentiated Services Code Point; this is Type of Service.
• ECN − Explicit Congestion Notification; It carries information about the congestion seen in the
route.
• Total Length − Length of entire IP Packet (including IP header and IP Payload).
• Identification − If IP packet is fragmented during the transmission, all the fragments contain
same identification number. to identify original IP packet they belong to.
• Flags − As required by the network resources, if IP Packet is too large to handle, these ‘flags’
tells if they can be fragmented or not. In this 3-bit flag, the MSB is always set to ‘0’.
• Fragment Offset − This offset tells the exact position of the fragment in the original IP
Packet.
• Time to Live − To avoid looping in the network, every packet is sent with some TTL value set,
which tells the network how many routers (hops) this packet can cross. At each hop, its value
is decremented by one and when the value reaches zero, the packet is discarded.
• Protocol − Tells the Network layer at the destination host, to which Protocol this packet
belongs to, i.e. the next level Protocol. For example protocol number of ICMP is 1, TCP is 6
and UDP is 17.
• Header Checksum − This field is used to keep checksum value of entire header which is
then used to check if the packet is received error-free.
• Source Address − 32-bit address of the Sender (or source) of the packet.
• Destination Address − 32-bit address of the Receiver (or destination) of the packet.
• Options − This is optional field, which is used if the value of IHL is greater than 5. These
options may contain values for options such as Security, Record Route, Time Stamp, etc.
 IP Addressing and Forwarding
14
0
 Routing Table Requirements
 For every possible IP, give the next hop
 But for 32-bit addresses, 232 possibilities!
 Too slow: 48GE ports and 4x10GE needs 176Gbps
bandwidth
DRAM: ~1-6 Gbps; TCAM is fast, but 400x cost of DRAM
 Hierarchical address scheme
 Separate the address into a network and a host
0 31
Pfx Network Host

Known by Known by
all routers edge (LAN)
 Classes of IP Addresses
14
1
0 1 8 16 24 31
Example: MIT
 Class A 0 Ntwk Host
18.*.*.*

1-126
0 2 8 16 24 31
Example: NEU
 Class B 1 Network Host
0 129.10.*.*
128-191
0 3 8 16 24 31
Example:
 Class C 11 Network Host
0 216.63.78.*

192-223
Classful IPv4 addressing

• Class A:
• For very large organizations
• 224 = 16 million hosts allowed
• Class B:
• For large organizations
• 216 = 65 thousand hosts allowed
• Class C
• For small organizations
• 28 = 255 hosts allowed
• Class D
• Multicast addresses
• No network/host hierarchy
Classless IPv4 addressing

• Also called classless inter-domain routing (CIDR)

• Key idea: Network component of the address (ie: prefix) can
have any length (usually from 8—32)
• Address format: a.b.c.d/x, where x is the prefix length
• Customary to use 0s for all suffix bits

network host
part part
11001000 00010111 00010000 00000000
200.23.16.0/23
CIDR

• An ISP can obtain a block of addresses 200.8.0.0/16

and partition this further to its customers
• Say an ISP has 200.8.0.0/16 address
(65K addresses).
200.8.0.0
• The ISP has customer who needs only
200.8.0.1
64 addresses starting from 200.8.4.128 200.8.4.128/26
…
• Then that block can be specified as 200.8.1.0
200.8.4.128/26 200.8.1.1
…
• 200.8.4.128/26 is “inside” 200.8.0.0/16
200.8.255.25
5
 Two Level Hierarchy
14
5

Networ
Pfx Host
k

…
Subtree
size …
determin
ed by
 Class Sizes
14
6

Way too big

Clas Prefi Networ Number of Classes Hosts per Class
s x k Bits
Bits
A 1 7 27 – 2 = 126 224 – 2 = 16,777,214
(0 and 127 are (All 0 and all 1 are
reserved) reserved)
B 2 14 214 = 16,398 216 – 2 = 65,534
(All 0 and all 1 are
reserved)
C 3 21 221 = 2,097,512 28 – 2 = 254
(All 0 and all 1 are
Too many Tooreserved)
small
network
Total: IDs
2,114,036 to be useful
 Subnets
14
7
 Problem: need to break up large A and B
classes
 Solution: add another layer to the hierarchy
 From the outside, appears to be a single network
 Only 1 entry in routing tables
 Internally, manage multiple subnetworks
 Split the address range using a subnet mask
Ntw
Pfx Subnet Host
k
11111111 11111111 11000000 00000000
Subnet Mask:
 Subnet Example
14
8
 Extract network:
IP Address: 10110101 11011101 01010100 01110010
Subnet Mask: & 11111111 11111111 11000000 00000000
Result: 10110101 11011101 01000000 00000000

 Extract host:
IP Address: 10110101 11011101 01010100 01110010
Subnet Mask: & ~(11111111 11111111 11000000
Result: 00000000 00000000 0001010000000000)
01110010
 N-Level Subnet Hierarchy
14
9
Networ
Pfx Subnet Host
k

…
…
• Tree does not have a fixed
depth
• Increasingly specific
subnet masks

Subtree size
determined
by length of
…
subnet mask
IP Addresses

IP address formats.
The IP Protocol (2)

5-54

Some of the IP options.

IP Addresses (2)

Special IP addresses.
 Subnets

A campus network consisting of LANs for various departments.

24.154
 CIDR

 CIDR or Class Inter-Domain Routing was

introduced in 1993 to replace classful
addressing. It allows the user to use VLSM or
Variable Length Subnet Masks.

24.155
 CIDR notation:

 In CIDR subnet masks are denoted by /X.

For example a subnet of 255.255.255.0
would be denoted by /24.

 To work a subnet mask in CIDR, we have

to first convert each octet into its
respective binary value. For example, if
the subnet is of 255.255.255.0. then :

24.156
  With CIDR, we can create Variable
Length Subnet Masks, leading to less
wastage of IP addresses. It is not
necessary that the divider between the
network and the host portions is at an
octet boundary. For example, in CIDR a
subnet mask like 255.224.0.0 or
11111111.11100000.00000000.000000
00 can exist.

24.157
CDR – Classless InterDomain Routing

5-59

A set of IP address assignments.

NAT – Network Address Translation

Placement and operation of a NAT box.

  NAT stands for network address translation.
 It’s a way to map multiple local private
addresses to a public one before transferring
the information.
 Organizations that want multiple devices to
employ a single IP address use NAT, as do most
home routers.

24.160
  Network Address Translation (NAT) is a process that
enables one, unique IP address to represent an entire
group of computers.
 In network address translation, a network device, often a
router or NAT firewall, assigns a computer or computers
inside a private network a public address.
 In this way, network address translation allows the single
device to act as an intermediary or agent between the
local, private network and the public network that is the
internet.
 NAT’s main purpose is to conserve the number of public
IP addresses in use, for both security and economic
goals.

24.161
24.162
Internet Control Message Protocol

5-61

The principal ICMP message types.

ARP– The Address Resolution Protocol

Three interconnected /24 networks: two Ethernets and an FDDI ring.

  Address Resolution Protocol (ARP) is a
communication protocol used to find the MAC
(Media Access Control) address of a device
from its IP address.
 This protocol is used when a device wants to
communicate with another device on a Local
Area Network or Ethernet.

24.165
 This process is as follows−
 When a host tries to interact with another host, an ARP
request is initiated. If the IP address is for the local
network, the source host checks its ARP cache to find out
the hardware address of the destination computer.
 If the correspondence hardware address is not found, ARP
broadcasts the request to all the local hosts.
 All hosts receive the broadcast and check their own IP
address. If no match is discovered, the request is ignored.
 The destination host that finds the matching IP address
sends an ARP reply to the source host along with its
hardware address, thus establishing the communication.
The ARP cache is then updated with the hardware address
of the destination host.

24.166
Dynamic Host Configuration Protocol

Operation of DHCP.
 OSPF (2)

The relation between ASes, backbones, and areas in OSPF.

24.169
 OSPF (3)

5-66

The five types of OSPF messeges.

 How does OSPF work?
 Step 1: The first step is to become OSPF neighbors. The
two connecting routers running OSPF on the same link
creates a neighbor relationship.

 Step 2: The second step is to exchange database

information. After becoming the neighbors, the two
routers exchange the LSDB information with each other.

 Step 3: The third step is to choose the best route. Once

the LSDB information has been exchanged with each
other, the router chooses the best route to be added to a
routing table based on the calculation of SPF.

24.171
BGP – The Exterior Gateway Routing
Protocol

(a) A set of BGP routers. (b) Information sent to F.

  BGP stands for Border Gateway
Protocol. It is a standardized
gateway protocol that exchanges
routing information across
autonomous systems (AS).
 When one network router is linked
to other networks, it cannot decide
which network is the best network to
share its data to by itself.
24.173
The Main IPv6 Header

The IPv6 fixed header (required).

Extension Headers

5-69

IPv6 extension headers.

 Extension Headers (2)

The hop-by-hop extension header for large datagrams (jumbograms).

Extension Headers (3)

The extension header for routing.