The Network

Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

T HE N ETWORK L AYER Routing

Algorithms

Congestion
Control
Muhammad Adil Raja Algorithms

References

Roaming Researchers, Inc.

August 29, 2014

 The Network
O UTLINE Layer

Muhammad Adil
Raja

Introduction

I NTRODUCTION Network Layer

Design Issues

Routing
Algorithms
N ETWORK L AYER D ESIGN I SSUES Congestion
Control
Algorithms

References
ROUTING A LGORITHMS

C ONGESTION C ONTROL A LGORITHMS

R EFERENCES
 The Network
O UTLINE Layer

Muhammad Adil
Raja

Introduction

I NTRODUCTION Network Layer

Design Issues

Routing
Algorithms
N ETWORK L AYER D ESIGN I SSUES Congestion
Control
Algorithms

References
ROUTING A LGORITHMS

C ONGESTION C ONTROL A LGORITHMS

R EFERENCES
 The Network
O UTLINE Layer

Muhammad Adil
Raja

Introduction

I NTRODUCTION Network Layer

Design Issues

Routing
Algorithms
N ETWORK L AYER D ESIGN I SSUES Congestion
Control
Algorithms

References
ROUTING A LGORITHMS

C ONGESTION C ONTROL A LGORITHMS

R EFERENCES
 The Network
O UTLINE Layer

Muhammad Adil
Raja

Introduction

I NTRODUCTION Network Layer

Design Issues

Routing
Algorithms
N ETWORK L AYER D ESIGN I SSUES Congestion
Control
Algorithms

References
ROUTING A LGORITHMS

C ONGESTION C ONTROL A LGORITHMS

R EFERENCES
 The Network
O UTLINE Layer

Muhammad Adil
Raja

Introduction

I NTRODUCTION Network Layer

Design Issues

Routing
Algorithms
N ETWORK L AYER D ESIGN I SSUES Congestion
Control
Algorithms

References
ROUTING A LGORITHMS

C ONGESTION C ONTROL A LGORITHMS

R EFERENCES
 The Network
I NTRODUCTION I Layer

Muhammad Adil
Raja
I The network layer is concerned with getting packets
from the source all the way to the destination. Introduction

Network Layer
I Getting to the destination may require making many Design Issues

hops at intermediate routers along the way. Routing

Algorithms
I This function clearly contrasts with the function of the Congestion
Control
data link layer. Algorithms

I The data link layer is concerned with only moving References

frames from one end of a wire to the other.

I Thus, the network layer is the lowest layer that deals
with end-to-end transmission.
I To achieve its goals, the network layer must know
about the topology of the network (i.e., the set of all
routers and links).
I It should also choose appropriate paths through the
network, even if it is large.
 The Network
I NTRODUCTION II Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

I It must also take care when choosing routes to avoid Routing

Algorithms
overloading some of the communication lines and Congestion
routes while leaving others idle. Control
Algorithms
I It must also handle problems when source and References

destination are in different networks.

I It is up to the network layer to deal with them.
 The Network
DATA L INK L AYER D ESIGN I SSUES I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms

I Network designers should grapple with certain Congestion

Control
design issues. Algorithms

References
I These issues include the service provided to the
transport layer and the internal design of the network.
 Before starting to explain the details of the network layer, it is worth restating The Network
StheTORE
context- AND -FtheORWARD
in which network layer P
protocols
ACKET S WITCHING
operate. This context canIbe Layer
seen in Fig. 5-1. The major components of the network are the ISP’s equipment Muhammad Adil
Components
(routers connected of
by a computer
transmission network:
lines), shown inside the shaded oval, and the Raja
customers’ equipment, shown outside the oval. Host H1 is directly connected to
one ofHosts (computers, handheld deveices etc.)
I
the ISP’s routers, A, perhaps as a home computer that is plugged into a Introduction
DSL modem.
I Switches. In contrast, H2 is on a LAN, which might be an office Ethernet, Network Layer
with a router, F, owned and operated by the customer. This router has a leased Design Issues
lineIto Routers.
the ISP’s equipment. We have shown F as being outside the oval because Routing
it does not belong to the ISP. For the purposes of this chapter, however, routers Algorithms
on I Wireless
customer access
premises points.
are considered part of the ISP network because they run the Congestion
same algorithms as the ISP’s routers (and our main concern here is algorithms). Control
Algorithms
Router ISP’s equipment
Process P1 P2 References

B
D

A E F

Host H1 LAN H2

C
Packet

Figure 5-1. The environment of the network layer protocols.

F IGURE : The environment of the network layer protocols.
This equipment is used as follows. 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 ISP.
 The Network
S ERVICES P ROVIDED TO THE T RANSPORT Layer

Muhammad Adil
L AYER I Raja

Introduction

Network Layer
I Network layer provides its services to the transport Design Issues

layer at the network layer/transport layer interface. Routing

Algorithms
I What kind of services the network layer provides to Congestion
Control
the transport layer? Algorithms

I The services need to be carefully designed with the References

following goals in mind:

1. The services should be independent of the router
technology.
2. The transport layer should be shielded from the
number, type, and topology of the routers present.
3. The network addresses made available to the
transport layer should use a uniform numbering plan,
even across LANs and WANs.
 The Network
S ERVICES P ROVIDED TO THE T RANSPORT Layer

Muhammad Adil
L AYER II Raja

I These goals allow a lot of freedom to the network Introduction

layer designers in writing detailed specifications of Network Layer
the services to be offered to the transport layer. Design Issues

Routing
I Conflicts of opinions arise among various factions of Algorithms

designers. Congestion
Control
Algorithms
I The debate centers on whether the network layer
References
should provide conection oriented or connectionless
service.
I Internet community argues that the routers’ job is
moving packets around and nothing else.
I In this view the network is inherently unreliable.
I So the hosts should accept this fact and do error
control themselves.
I It leads to the conclusion that the network service
should be connectionless.
 The Network
S ERVICES P ROVIDED TO THE T RANSPORT Layer

Muhammad Adil
L AYER III Raja
I No packet ordering and flow control should be done,
Introduction
as the hosts are going to do that anyway.
Network Layer
Design Issues
I This reasoning is an example of the end-to-end
Routing
argument. Algorithms

I Moreover, each packet must carry the full destination Congestion

Control
address, as each packet is carried independently of Algorithms

its predecessors. References

I ANother camp argues that the network should

provide a reliable, connection-oriented service.
I This camp is represented by the telephone
companies.
I They view quality of service (QoS) as the dominant
factor.
I They view that QoS is difficult to achieve without
connections.
 The Network
I MPLEMENTATION OF C ONNECTIONLESS Layer

Muhammad Adil
S ERVICE I Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
I Packets are injected into the network individually and Congestion
Control
routed independently of each other. Algorithms

I Any advance setup is not required. References

I Packets are called datagrams in this context (in

analogy with telegrams).
I The network is called a datagram network.
in Fig. 5-2 has a long message for P2. It hands the message to the transport layer,
with instructions to deliver it to process P2 on host H2. The transport layer code The Network
IMPLEMENTATION
runs on H1, typically within the OF C
operatingONNECTIONLESS
system. It prepends a transport header Layer
to the front of the message and hands the result to the network layer, probably just Muhammad Adil
S ERVICE
another II
procedure within the operating system. Raja

Router ISP’s equipment Introduction

Process P1 P2
Network Layer
B Design Issues
D
4
Routing
1 Algorithms
A E F
3 2 Congestion
Host H1 LAN H2 Control
Algorithms
C
References
Packet

A’s table (initially) A’s table (later) C’s table E’s table
A – A – A A A C
B B B B B A B D
C C C C C – C C
D B D B D E D D
E C E B E E E –
F C F B F E F F
Dest. Line

Figure 5-2. Routing within a datagram network.

F IGURE : Routing within a datagram network.
Let us assume for this example that the message is four times longer than the
maximum packet size, so the network layer has to break it into four packets, 1, 2,
 The Network
I MPLEMENTATION OF C ONNECTION -O RIENTED Layer

Muhammad Adil
S ERVICE I Raja

Introduction
I We require a virtual-circuit (VC) network.
Network Layer
I The idea behind VCs is to avoid having to choose a Design Issues

Routing
new route for every packet sent. Algorithms

I When a connection is established a route between Congestion

Control
source and destination is chosen and stored within Algorithms

the tables inside the routers. References

I That route is used for all traffic flowing over the

connection.
I This is exactly similar to the telephone system.
I When the connection is released, VC is also
terminated.
I With connection-oriented service, each packet
carries an identifier telling which virtual circuit it
belongs to.
 The Network
Ibearing connection identifier 1 comes in from H1, it is to be sent to router C and
MPLEMENTATION OF C ONNECTION -O RIENTED
given connection identifier 1. Similarly, the first entry at C routes the packet to E,
Layer

also with
S ERVICE IIconnection identifier 1. Muhammad Adil
Raja

P3 Introduction

Network Layer
Design Issues
Router ISP’s equipment
P2 Routing
Algorithms
B
H3 D Congestion
Control
Process P1 1 Algorithms
A 4 E F
2 References
3 LAN H2

C
Packet

Host H1
A’s table C’s table E’s table
H1 1 C 1 A 1 E 1 C 1 F 1
H3 1 C 2 A 2 E 2 C 2 F 2
In Out

Figure 5-3. Routing within a virtual-circuit network.

F IGURE : Routing within a virtual-circuit network.
Now let us consider what happens if H3 also wants to establish a connection
 The Network
I MPLEMENTATION OF C ONNECTION -O RIENTED Layer

Muhammad Adil
S ERVICE III Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms

Congestion
Control
I This is also called label switching. Algorithms

I An example is Multi Protocol Label Switching References

(MPLS).
 5.1.5 Comparison of Virtual-Circuit and Datagram Networks
The Network
C OMPARISON
Both virtual circuitsOF V IRTUAL
and datagrams -Csupporters
have their IRCUIT andAND
their detractors. Layer

We will now attempt to summarize both sets of arguments. The major issues are Muhammad Adil
Dlisted
ATAGRAM N ETWORK I
in Fig. 5-4, although purists could probably find a counterexample for Raja
everything in the figure.
Introduction

Issue Datagram network Virtual-circuit network Network Layer

Design Issues
Circuit setup Not needed Required
Addressing Each packet contains the full Each packet contains a Routing
Algorithms
source and destination address short VC number
State information Routers do not hold state Each VC requires router Congestion
information about connections table space per connection Control
Algorithms
Routing Each packet is routed Route chosen when VC is
independently set up; all packets follow it References

Effect of router failures None, except for packets All VCs that passed
lost during the crash through the failed
router are terminated
Quality of service Difficult Easy if enough resources
can be allocated in
advance for each VC
Congestion control Difficult Easy if enough resources
can be allocated in
advance for each VC

Figure 5-4. Comparison of datagram and virtual-circuit networks.

F IGURE : Comparison of datagram and virtual-circuit networks.
Inside the network, several trade-offs exist between virtual circuits and data-
grams. One trade-off is setup time versus address parsing time. Using virtual cir-
 The Network
C OMPARISON OF V IRTUAL -C IRCUIT AND Layer

Muhammad Adil
DATAGRAM N ETWORK II Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
Tradeoffs: Congestion
Control
I Setup time versus address parsing time. Algorithms

References
I Longer destination addresses in datagram networks
(overhead for smaller packets).
I Table space required in router memory.
 The Network
ROUTING A LGORITHMS I Layer

Muhammad Adil
Raja
I Routing packets from source to destination is the
main function of the network layer. Introduction

Network Layer
I A routing algorithm decides which output line an Design Issues

incoming packet should be transmitted on. Routing

Algorithms
I A new decision for every packet is required in a Congestion
Control
datagram network. Algorithms

I A new decision is required only when a new virtual References

circuit is being set up.

I It is important to distinguish between routing and
forwarding.
I Forwarding is to look up the outgoing line to use for a
packet (as it arrives) in a routing table.
I Routing is to fill in and update the routing tables.
I Desirable properties of a routing algorithm:
1. Correctness.
 The Network
ROUTING A LGORITHMS II Layer

Muhammad Adil
Raja

Introduction

Network Layer
2. Simplicity. Design Issues

3. Robustness. Routing
Algorithms
4. Robustness. Congestion
5. Stability. Control
Algorithms
6. Fairness.
References
7. Efficiency.
I Classification of Routing algorithms
1. Adaptive algorithms – State routing.
2. Nonadaptive algorithms – Dynamic routing.
 The Network
ROUTING A LGORITHMS III Layer

Muhammad Adil
364 THE NETWORK LAYER CHAP. 5 Raja

Introduction
A B C
Network Layer
Design Issues

Routing
Algorithms

X X′ Congestion
Control
Algorithms

References

A' B' C'

Figure 5-5. Network with a conflict between fairness and efficiency.

F IGURE : Network with a conflict between fairness and
efficiency.
measurements or estimates of the current topology and traffic. Instead, the choice
of the route to use to get from I to J (for all I and J) is computed in advance, off-
line, and downloaded to the routers when the network is booted. This procedure
is sometimes called static routing. Because it does not respond to failures, static
routing is mostly useful for situations in which the routing choice is clear. For ex-
ample, router F in Fig. 5-3 should send packets headed into the network to router
E regardless of the ultimate destination.
Adaptive algorithms, in contrast, change their routing decisions to reflect
 The Network
T HE O PTIMALITY P RINCIPLE I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms

Congestion
I A statement about optimal routes without regard to Control
Algorithms
network topology.
References
I Directed Acyclic Graphs (DAG) – have no loops.
 The Network
S HORTEST PATH A LGORITHM I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Criteria: Design Issues

Routing
I Minimum number of hops. Algorithms

I Minimum geographic distance in kilometers. Congestion

Control
Algorithms
I End-to-end delay.
References
I Bandwidth.
I Average traffic.
I Communication cost.
I measured delay.
 line, or link. To choose a route between a given pair of routers, the algorithm just
finds the shortest path between them on the graph.
The concept of a shortest path deserves some explanation. One way of The Network
S HORTEST PATH A LGORITHM II
measuring path length is the number of hops. Using this metric, the paths ABC
and ABE in Fig. 5-7 are equally long. Another metric is the geographic distance
Layer

in kilometers, in which case ABC is clearly much longer than ABE (assuming the Muhammad Adil
Dijkstra’s algorithm.
figure is drawn to scale). Raja

B 7 C B (2, A) C (∞, −) Introduction

2 3
2 3 Network Layer
E 2 F E (∞, −)
A D A F (∞, −) D (∞, −) Design Issues
1 2
6 4 2

G H G (6, A) H (∞, −) Routing

(a) (b) Algorithms

B (2, A) C (9, B) B (2, A) C (9, B) Congestion

Control
E (4, B) E (4, B) Algorithms
A F (∞, −) D (∞,−) A F (6, E) D (∞,1)
References
G (6, A) H (∞, −) G (5, E) H (∞, −)
(c) (d)

B (2, A) C (9, B) B (2, A) C (9, B)

E (4, B) E (4, B)
A F (6, E) D (∞,−) A F (6,E) D (∞,−)

G (5, E) H (9, G) G (5, E) H (8, F)

(e) (f)

Figure 5-7. The first six steps used in computing the shortest path from A to D.
F IGURE : TheThefirst six steps used in computing the shortest path
arrows indicate the working node.

from A to D. The arrows indicate the working node.

 The Network
F LOODING I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
I In flooding every incoming packet is sent out on Congestion
every outgoing line except the one it arrived on. Control
Algorithms
I Generate vast number of duplicates packets. References

I It is robust but has computing and communication

overheads.
 The Network
D ISTANCE V ECTOR ROUTING I Layer

Muhammad Adil
Raja
I Each router maintains a table (i.e., a vector).
Introduction
I It gives the best known distance to each destination Network Layer
and which link to use to get there. Design Issues

Routing
I The tables are updated by exchanging information Algorithms

with the neighbors. Congestion

Control
I Every router knows the best link to reach each Algorithms

References
destination.
I Each router maintains a routing table indexed by, and
containing one entry for each router in the network.
I The entry has two parts:
1. The preferred outgoing line to use for that
destination.
2. An estimate of the distance to that destination.
I The distance might be measured as the number of
hops or using another metric.
 The Network
D ISTANCE V ECTOR ROUTING II Layer

Muhammad Adil
Raja

Introduction

Network Layer
I The router is assumed to know the “distance” to each Design Issues
of its neighbors. Routing
Algorithms
I If the metric is hops, the distance is just one hop. Congestion
Control
I If the metric is propagation delay, the router can Algorithms

measure it directly with special ECHO packets that References

the receiver just timestamps and sends back as fast

as it can.
I Pseudonyms: Distributed Bellman-Ford routing
algorithm, RIP.
 first four columns of part (b) show the delay vectors received from the neighbors
of router J. A claims to have a 12-msec delay to B, a 25-msec delay to C, a 40- The Network
D ISTANCE V ECTOR ROUTING III
msec delay to D, etc. Suppose that J has measured or estimated its delay to its Layer
neighbors, A, I, H, and K, as 8, 10, 12, and 6 msec, respectively.
Muhammad Adil
Raja
New estimated
Router delay from J
A B C D To A I H K Line Introduction
A 0 24 20 21 8 A
B 12 36 31 28 20 A Network Layer
C 25 18 19 36 28 I Design Issues
F G D 40 27 8 24 20 H
E H
E 14 7 30 22 17 I Routing
F 23 20 19 40 30 I Algorithms
G 18 31 6 31 18 H
H 17 20 0 19 12 H Congestion
I J K L
I 21 0 14 22 10 I Control
J 9 11 7 10 0 − Algorithms
K 24 22 22 0 6 K
L 29 33 9 9 15 K References
JA JI JH JK
delay delay delay delay New
is is is is routing
8 10 12 6 table
for J
Vectors received from
J's four neighbors
(a) (b)

Figure 5-9. (a) A network. (b) Input from A, I, H, K, and the new routing table for J.
F IGURE : (a) A network. (b) Input from A, I, H, K, and new
routing table for
Consider J.J computes its new route to router G. It knows that it can get to
how
A in 8 msec, and furthermore A claims to be able to get to G in 18 msec, so J
knows it can count on a delay of 26 msec to G if it forwards packets bound for G
 The Network
D ISTANCE V ECTOR ROUTING IV Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues
The Count-to-Infinity Problem: Routing
Algorithms
I The settling of routes to the best paths across the
Congestion
network is called convergence. Control
Algorithms
I Distance vector routing is useful as a simple References

technique by which routers can collectively compute

shortest paths.
I Split horizon with poisoned reverse.
reports a short delay to X, the router just switches over to using the line to A to
send traffic to X. In one vector exchange, the good news is processed. The Network
DISTANCE V
To see how fast ECTOR R
OUTING
good news propagates, V
consider the five-node (linear) net- Layer

work of Fig. 5-10, where the delay metric is the number of hops. Suppose A is Muhammad Adil
down initially and all the other routers know this. In other words, they have all Raja

recorded the delay to A as infinity.

Introduction
A B C D E A B C D E
Network Layer
• • • • Initially 1 2 3 4 Initially Design Issues
1 • • • After 1 exchange 3 2 3 4 After 1 exchange Routing
1 2 • • After 2 exchanges 3 4 3 4 After 2 exchanges Algorithms
1 2 3 • After 3 exchanges 5 4 5 4 After 3 exchanges
Congestion
1 2 3 4 After 4 exchanges 5 6 5 6 After 4 exchanges Control
7 6 7 6 After 5 exchanges Algorithms
7 8 7 8 After 6 exchanges
.. References
.
• • • •
(a) (b)

Figure 5-10. The count-to-infinity problem.

F IGURE : The count-to-infinity problem.
When A comes up, the other routers learn about it via the vector exchanges.
For simplicity, we will assume that there is a gigantic gong somewhere that is
struck periodically to initiate a vector exchange at all routers simultaneously. At
the time of the first exchange, B learns that its left-hand neighbor has zero delay
to A. B now makes an entry in its routing table indicating that A is one hop away
to the left. All the other routers still think that A is down. At this point, the rout-
ing table entries for A are as shown in the second row of Fig. 5-10(a). On the next
 The Network
L INK S TATE ROUTING I Layer

Muhammad Adil
I Each router must do the following things to make it Raja
work:
Introduction
1. Discover its neighbors and learn their network
Network Layer
addresses. Design Issues
2. Set the distance or cost metric to each of its Routing
neighbors. Algorithms

3. Construct a packet telling all it has just learned. Congestion

Control
4. Send this packet to and receive packets from all Algorithms

other routers. References

5. Compute the shortest path to every other router.
I In effect, the complete topology is distributed to
every router.
I The Dijkstra’s algorithm can be run at each router to
find the shortest path to every other router.
I Variants:
1. IS-IS.
2. OSPF.
I The five steps are discussed as follows:
 The Network
L INK S TATE ROUTING II Layer

Muhammad Adil
Raja
(1) Learning About the Neighbors
Introduction
I When a router is booted, its first task is to learn who
Network Layer
its neighbors are. Design Issues

Routing
I It accomplishes this goal by sending special HELLO Algorithms
packet on each point-to-point line. Congestion
Control
I The router on the other end is expected to send back Algorithms

a reply giving its name. References

I These names must be globally unique because

when a distant router later hears that three routers
are all connected to F , it is essential that it can
determine whether all three mean the same F .
I When two or more routers are connected by a
broadcast link (e.g., a switch, ring, or classic
Ethernet), the situation is slightly more complicated.
 When two or more routers are connected by a broadcast link (e.g., a switch,
ring, or classic Ethernet), the situation is slightly more complicated. Fig. 5-11(a) The Network
L S
INK a TATE
illustrates R OUTING
broadcast LAN III
to which three routers, A, C, and F, are directly con-
Layer

nected. Each of these routers is connected to one or more additional routers, as Muhammad Adil
Raja
shown.
Introduction
H Router
Network Layer
Design Issues
B D E
Routing
D E G I G H Algorithms
B
Congestion
A C F C Control
Algorithms
A
F I
References

LAN N

(a) (b)

F IGUREFigure
: (a)5-11.
Nine (a) Nine routers and a broadcast LAN. (b) A graph model of (a).
routers and a broadcast LAN. (b) A graph
model of (a).
The broadcast LAN provides connectivity between each pair of attached rout-
ers. However, modeling the LAN as many point-to-point links increases the size
 The Network
L INK S TATE ROUTING IV Layer

Muhammad Adil
Raja
(2) Setting Link Costs
Introduction
I The link state routing algorithm requires each link to
Network Layer
have a distance or cost metric for finding shortest Design Issues

paths. Routing
Algorithms
I The cost to reach neighbors can be set Congestion
Control
automatically, or configured by the network operator. Algorithms

I A common choice is to make the cost inversely References

proportional to the bandwidth of the link.

I For example, 1-Gbps Ethernet may have a cost of 1
and 100-Mbps Ethernet a cost of 10.
I This makes higher-capacity paths better choices.
I If the network is geographically spread out, the delay
of the links may be factored into the cost so that
paths over shorter links are better choices.
 The Network
L INK S TATE ROUTING V Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
I The most direct way to determine this delay is to Algorithms
send over the line a special ECHO packet that the Congestion
Control
other side is required to send back immediately. Algorithms

References
I By measuring the round-trip time and dividing it by
two, the sending router can get a reasonable
estimate of the delay.
 The Network
L INK S TATE ROUTING VI Layer

Building Link State packets Muhammad Adil

Raja
I Once the information needed for the exchange has
Introduction
been collected, the next step is for each router to Network Layer
build a packet containing all the data. Design Issues

Routing
I The packet starts with the identity of the sender, Algorithms

followed by a sequence number and age (to be de- Congestion

Control
scribed later) and a list of neighbors. Algorithms

References
I The cost to each neighbor is also given.
I Building the link state packets is easy.
I The hard part is determining when to build them.
I One possibility is to build them periodically, that is, at
regular intervals.
I Another possibility is to build them when some
significant event occurs, such as a line or neighbor
going down or coming back up again or changing its
properties appreciably.
 step is for each router to build a packet containing all the data. The packet starts The Network
L INK
with theSidentity
TATEof RtheOUTING VII
sender, followed by a sequence number and age (to be de- Layer
scribed later) and a list of neighbors. The cost to each neighbor is also given. An
Muhammad Adil
example network is presented in Fig. 5-12(a) with costs shown as labels on the Raja
lines. The corresponding link state packets for all six routers are shown in Fig. 5-
12(b). Introduction

Link State Packets Network Layer

B 2 C Design Issues
A B C D E F
4 3 Seq. Seq. Seq. Seq. Seq. Seq. Routing
Age Age Age Age Age Age Algorithms
A D
1 6 B 4 A 4 B 2 C 3 A 5 B 6 Congestion
5 7 Control
E 5 C 2 D 3 F 7 C 1 D 7
Algorithms
E 8 F F 6 E 1 F 8 E 8
References
(a) (b)

Figure 5-12. (a) A network. (b) The link state packets for this network.
F IGURE : ((a) A network. (b) The link state packets for this
network.
 The Network
L INK S TATE ROUTING VIII Layer

Distributing the Link State Packets Muhammad Adil

Raja

I The trickiest part of the algorithm is distributing the Introduction

link state packets. Network Layer
Design Issues
I All of the routers must get all of the link state packets Routing
quickly and reliably. Algorithms

Congestion
I If different routers are using different versions of the Control
Algorithms
topology, the routes they compute can have
References
inconsistencies such as loops, unreachable
machines, and other problems.
I The fundamental idea is to use flooding to distribute
the link state packets to all routers.
I To keep the flood in check, each packet contains a
sequence number that is incremented for each new
packet sent.
I Routers keep track of all the (source router,
sequence) pairs they see.
 The Network
L INK S TATE ROUTING IX Layer

Muhammad Adil
Raja

Introduction

Network Layer
I When a new link state packet comes in, it is checked Design Issues

against the list of packets already seen. Routing

Algorithms

I If it is new, it is forwarded on all lines except the one Congestion

Control
it arrived on. Algorithms

References
I If it is a duplicate, it is discarded.
I If a packet with a sequence number lower than the
highest one seen so far ever arrives, it is rejected as
being obsolete as the router has more recent data.
 The data structure used by router B for the network shown in Fig. 5-12(a) is
depicted in Fig. 5-13. Each row here corresponds to a recently arrived, but as yet The Network
L
not
INK S
fully processed, R
TATE linkOUTING X
state packet. The table records where the packet ori- Layer
ginated, its sequence number and age, and the data. In addition, there are send
Muhammad Adil
and acknowledgement flags for each of B’s three links (to A, C, and F, re- Raja
spectively). The send flags mean that the packet must be sent on the indicated
link. The acknowledgement flags mean that it must be acknowledged there. Introduction
Send flags ACK flags Network Layer
Design Issues
Source Seq. Age A C F A C F Data
Routing
A 21 60 0 1 1 1 0 0 Algorithms

F 21 60 1 1 0 0 0 1 Congestion
Control
E 21 59 0 1 0 1 0 1 Algorithms

C 20 60 1 0 1 0 1 0 References

D 21 59 1 0 0 0 1 1

Figure 5-13. The packet buffer for router B in Fig. 5-12(a).

FInIGURE : The packet buffer for router B in FIGURE. 10 (a)
Fig. 5-13, the link state packet from A arrives directly, so it must be sent to
C and F and acknowledged to A, as indicated by the flag bits. Similarly, the pack-
et from F has to be forwarded to A and C and acknowledged to F.
However, the situation with the third packet, from E, is different. It arrives
twice, once via EAB and once via EFB. Consequently, it has to be sent only to C
but must be acknowledged to both A and F, as indicated by the bits.
If a duplicate arrives while the original is still in the buffer, bits have to be
changed. For example, if a copy of C’s state arrives from F before the fourth
entry in the table has been forwarded, the six bits will be changed to 100011 to in-
 The Network
L INK S TATE ROUTING XI Layer

Muhammad Adil
Computing the New Routes Raja

I Once a router has accumulated a full set of link state Introduction

packets, it can construct the entire network graph Network Layer
Design Issues
because every link is represented.
Routing
I Every link is, in fact, represented twice, once for each Algorithms

Congestion
direction. Control
Algorithms
I The different directions may even have different
References
costs.
I The shortest-path computations may then find
different paths from router A to B than from router B
to A.
I Now DijkstraÕs algorithm can be run locally to
construct the shortest paths to all possible
destinations.
I The results of this algorithm tell the router which link
to use to reach each destination.
 The Network
L INK S TATE ROUTING XII Layer

Muhammad Adil
I This information is installed in the routing tables, and Raja

normal operation is resumed. Introduction

I Compared to distance vector routing, link state Network Layer

Design Issues
routing requires more memory and computation. Routing
Algorithms
I For a network with n routers, each of which has k
Congestion
neighbors, the memory required to store the input Control
Algorithms
data is proportional to kn, which is at least as large References
as a routing table listing all the destinations.
I Also, the computation time grows faster than kn,
even with the most efficient data structures, an issue
in large networks.
I Nevertheless, in many practical situations, link state
routing works well because it does not suffer from
slow convergence problems.
I Link state routing is widely used in actual networks.
 The Network
L INK S TATE ROUTING XIII Layer

Muhammad Adil
I Many ISPs use the IS-IS (Intermediate Raja
System-Intermediate System) link state protocol.
Introduction
I OSPF (Open Shortest Path First) is the other main Network Layer
Design Issues
link state protocol.
Routing
I It was designed by IETF several years after IS-IS and Algorithms

adopted many of the innovations designed for IS-IS. Congestion

Control
Algorithms
I These innovations include a self-stabilizing method
References
of flooding link state updates, the concept of a
designated router on a LAN, and the method of
computing and supporting path splitting and multiple
metrics.
I As a consequence, there is very little difference
between IS-IS and OSPF.
I The most important difference is that IS-IS can carry
information about multiple network layer protocols at
the same time (e.g., IP, IPX, and AppleTalk).
 The Network
L INK S TATE ROUTING XIV Layer

Muhammad Adil
Raja
I OSPF does not have this feature, and it is an
Introduction
advantage in large multi-protocol environments.
Network Layer
I Link state, distance vector, and other algorithms rely Design Issues

on processing at all the routers to compute routes. Routing

Algorithms
I Problems with the hardware or software at even a Congestion
Control
small number of routers can wreak havoc across the Algorithms

network. For example, if a router claims to have a References

link it does not have or forgets a link it does have, the

network graph will be incorrect.
I If a router fails to forward packets or corrupts them
while forwarding them, the route will not work as
expected.
I Finally, if it runs out of memory or does the routing
calculation wrong, bad things will happen.
 The Network
L INK S TATE ROUTING XV Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

I As the network grows into the range of tens or Routing

Algorithms
hundreds of thousands of nodes, the probability of Congestion
Control
some router failing occasionally becomes Algorithms
non-negligible. References

I The trick is to try to arrange to limit the damage when

the inevitable happens.
 The Network
H IERARCHICAL ROUTING I Layer

Muhammad Adil
Raja

Introduction
I As networks grow in size, the router routing tables
Network Layer
grow proportionally. Design Issues

I Not only is router memory consumed by Routing

Algorithms
ever-increasing tables, but more CPU time is needed Congestion
to scan them and more bandwidth is needed to send Control
Algorithms
status reports about them. References

I At a certain point, the network may grow to the point

where it is no longer feasible for every router to have
an entry for every other router, so the routing will
have to be done hierarchically, as it is in the
telephone network.
I When hierarchical routing is used, the routers are
divided into what we will call regions.
 The Network
H IERARCHICAL ROUTING II Layer

Muhammad Adil
I Each router knows all the details about how to route Raja

packets to destinations within its own region but

Introduction
knows nothing about the internal structure of other Network Layer
regions. Design Issues

Routing
I When different networks are interconnected, it is Algorithms

natural to regard each one as a separate region to Congestion

Control
free the routers in one network from having to know Algorithms

the topological structure of the other ones. References

I For huge networks, a two-level hierarchy may be

insufficient.
I It may be necessary to group the regions into
clusters, the clusters into zones, the zones into
groups, and so on.
I As an example of a multilevel hierarchy, consider
how a packet might be routed from Berkeley,
California, to Malindi, Kenya.
 The Network
H IERARCHICAL ROUTING III Layer

Muhammad Adil
Raja
I The Berkeley router would know the detailed
topology within California but would send all Introduction

out-of-state traffic to the Los Angeles router. Network Layer

Design Issues
I The Los Angeles router would be able to route traffic Routing
Algorithms
directly to other domestic routers but would send all
Congestion
foreign traffic to New York. Control
Algorithms
I The New York router would be programmed to direct References
all traffic to the router in the destination country
responsible for handling foreign traffic, say, in Nairobi.
I Finally, the packet would work its way down the tree
in Kenya until it got to Malindi.
I When a single network becomes very large, an
interesting question is “how many levels should the
hierarchy have?”
I consider a network with 720 routers.
 The Network
H IERARCHICAL ROUTING IV Layer

Muhammad Adil
Raja

Introduction
I If there is no hierarchy, each router needs 720
Network Layer
routing table entries. Design Issues

Routing
I If the network is partitioned into 24 regions of 30 Algorithms

routers each, each router needs 30 local entries plus Congestion

Control
23 remote entries for a total of 53 entries. Algorithms

References
I If a three-level hierarchy is chosen, with 8 clusters
each containing 9 regions of 10 routers.
I Each router needs 10 entries for local routers, 8
entries for routing to other regions within its own
cluster, and 7 entries for distant clusters, for a total of
25 entries.
380 THE NETWORK LAYER CHAP. 5
The Network
H IERARCHICAL ROUTING V Layer

Full table for 1A Hierarchical table for 1A Muhammad Adil

Raja
Dest. Line Hops Dest. Line Hops
Region 1 Region 2 1A – – 1A – –
Introduction
1B 2A 2B 1B 1B 1 1B 1B 1
1C 1C 1 1C 1C 1 Network Layer
1A Design Issues
2A 1B 2 2 1B 2
1C 2C 2D
2B 1B 3 3 1C 2 Routing
Algorithms
2C 1B 3 4 1C 3
2D 1B 4 5 1C 4 Congestion
Control
3A 4A 5B 5C 3A 1C 3
Algorithms
5A 3B 1C 2
4B 4C
3B 5D 4A 1C 3 References
5E
4B 1C 4
Region 3 Region 4 Region 5
4C 1C 4
5A 1C 4
5B 1C 5
5C 1B 5
5D 1C 6
5E 1C 5
(a) (b) (c)

Figure 5-14. Hierarchical routing.

F IGURE : Hierarchical routing
5.2.7 Broadcast Routing
suited for ordinary point-to-point communication, it rates serious consideration for
broadcasting. However, it turns out that we can do better still once the shortest The Network
BROADCASTING
path OUTING
routes for regular packets have R
been computed. I Layer
The idea for reverse path forwarding is elegant and remarkably simple once Muhammad Adil
it has been pointed out (Dalal and Metcalfe, 1978). When a broadcast packet ar- Raja
rives When messages need toifbe
the sent
packet to many orlink
allthat
other
I
at a router, the router checks to see arrived on the is
normally used for sending packets toward the source of the broadcast. If so, there
hosts. Introduction
is an excellent chance that the broadcast packet itself followed the best route from
Network Layer
Multidestination
theIrouter and is therefore therouting.
first copy to arrive at the router. This being the Design Issues
case, the router forwards copies of it onto all links except the one it arrived on. If,
I Reverse
however, pathpacket
the broadcast forwarding.
arrived on a link other than the preferred one for Routing
Algorithms
reaching the source, the packet is discarded as a likely duplicate.
Congestion
B C B C I Control
A D A D Algorithms
F E F F H J N References
E
I G I G
A D E K G O M O
J
H N H J
L
L N E C G D N K
O O
K K H B L H
M M
L B

(a) (b) (c)

Figure 5-15. Reverse path forwarding. (a) A network. (b) A sink tree. (c) The
: Reverse
F IGUREtree built by reversepath forwarding. (a) A network. (b) A sink
path forwarding.
tree. (c) The tree built by reverse path forwarding.
An example of reverse path forwarding is shown in Fig. 5-15. Part (a) shows
a network, part (b) shows a sink tree for router I of that network, and part (c)
shows how the reverse path algorithm works. On the first hop, I sends packets to
 The Network
M ULTICAST ROUTING I Layer

Muhammad Adil
I Sending messages to a selected group of hosts. Raja

I Multicast OSPF (MOSF). Introduction

I Distance Vector Multicast Routing Protocol Network Layer

Design Issues
(DVMRP). Routing
Algorithms
I Protocol
384
Independent Multicast (PIM). CHAP. 5
THE NETWORK LAYER Congestion
Control
Algorithms
2 1 2 1
References
1, 2 1, 2
1, 2
1, 2
2
2 2 2

1
1
1
1
(a) (b)

1 2
1 2 2 2

1
1
(c) (d)
 The Network
M ULTICAST ROUTING II Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
F IGURE : (a) A network. (b) A spanning tree for the leftmost Congestion
router. (c) A multicast tree for group 1. (d) A multicast tree for Control
Algorithms
group 2. References
 want to anycast to the members of group 1. They will all be given the address
’’ instead of different addresses. Distance vector routing will distribute vectors
The Network
A NYCAST
usual, ROUTING
and nodes will I
choose the shortest path to destination 1. This will result Layer
nodes sending to the nearest instance of destination 1. The routes are shownMuhammad
in Raja Adil
. 5-18(a).
I AThis procedure works because the routing protocol
packet is delivered to the nearest member of a does not realize
t there are multiple instances of destination 1. That is, it believes that allIntroduction
group. the
tances of node 1 are the same node, as in the topology shown in Fig. 5-18(b). Network Layer
Design Issues
1 Routing
Algorithms

Congestion
Control
1 1 Algorithms

1 References

1
1
(a) (b)

FFigure 5-18. (a) Anycast routes to group 1. (b) Topology seen by the routing protocol.
IGURE : (a) Anycast routes to group 1. (b) Topology seen by
the routing protocol.
This procedure works for link state routing as well, although there is the
ded consideration that the routing protocol must not find seemingly short paths
t pass through node 1. This would result in jumps through hyperspace, since
 The Network
ROUTING FOR M OBILE H OSTS I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues
I The basic idea used for mobile routing in the Internet Routing
Algorithms
and cellular networks is for the mobile host to tell a
Congestion
host at the home location where it is now. Control
Algorithms
I This host, which acts on behalf of the mobile host, is References
called the home agent.
I Once it knows where the mobile host is currently
located, it can forward packets so that they are
delivered.
 The Network
ROUTING FOR M OBILE H OSTS II Layer

388 THE NETWORK LAYER CHAP. 5 Muhammad Adil

Raja

Introduction

Network Layer
Design Issues
2: Sen
d to ho
me ad Routing
Sender dress
Algorithms
4: Reply
5: Tunnel to sender Congestion
to care of f add ress Control
address ister care o Algorithms
1: Reg
ddress Home agent at
re of a
References
n el to ca home address
3: Tun

Mobile host at
care of address

Figure 5-19. Packet routing for mobile hosts.

F IGURE : Packet routing for mobile hosts.
When the encapsulated packet arrives at the care of address, the mobile host
unwraps it and retrieves the packet from the sender. The mobile host then sends
its reply packet directly to the sender (step 4). The overall route is called triangle
routing because it may be circuitous if the remote location is far from the home
location. As part of step 4, the sender may learn the current care of address. Sub-
more complicated, with buildings, hills, and other obstacles that block communi-
cation, and nodes for which A is connected to B but B is not connected to A be- The Network
R OUTING
cause A has a moreIN A H
D transmitter
powerful OC than ETWORKS N
B. However, for simplicity, we will I Layer

assume all connections are symmetric. Muhammad Adil

Raja
ToI describe
MANETs the (Mobile
algorithm, Ad
consider the newly formed ad hoc network of
hoc NETworks).
Fig. 5-20. Suppose that a process at node A wants to send a packet to node I. The Introduction
AODV AODV (Adhoc
I algorithm maintainsOn-demand
a distance vectorDistance Vector).
table at each node, keyed by desti-
Network Layer
nation,
I giving information
Route discovery. about that destination, including the neighbor to which Design Issues
to send packets to reach the destination. First, A looks in its table and does not Routing
find an
I entry
Routefor I. It now has to discover a route to I. This property of discover-
maintenance. Algorithms
ing routes only when they are needed is what makes this algorithm ‘‘on demand.’’ Congestion
Control
Range of Algorithms
A’s broadcast
References

A B A B A B A B
C C C C

D D D D
E E E E
F F F F
G G G G

H I H I H I H I
(a) (b) (c) (d)

Figure 5-20. (a) Range of A’s broadcast. (b) After B and D receive it. (c) After
F IGURE ((a)G Range
C, F,: and receive it.of
(d)AÕs broadcast.
After E, (b)it.After
H, and I receive B and
The shaded D are
nodes
new it.
receive recipients. The dashed
(c) After C, F, lines
andshow possible reverse
G receive it. (d)routes.
AfterTheE,solid lines I
H, and
show the discovered route.
 The Network
ROUTING IN A D H OC N ETWORKS II Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
receive it. The shaded nodes are new recipients. The dashed Congestion
Control
lines show possible reverse routes. The solid lines show the Algorithms
discovered route. References
 The Network
C ONGESTION C ONTROL A LGORITHMS I Layer

Muhammad Adil
Raja
I Too many packets present in (a part of) the network
Introduction
causes packet delay and loss that degrades
Network Layer
performance. Design Issues

I This situation is called congestion. Routing

Algorithms
I The network and transport layers share the Congestion
Control
responsibility for handling congestion. Algorithms

References
I Since congestion occurs within the network, it is the
network layer that directly experiences it and must
ultimately determine what to do with the excess
packets.
I However, the most effective way to control
congestion is to reduce the load that the transport
layer is placing on the network.
I This requires the network and transport layers to
work together.
 The Network
C ONGESTION C ONTROL A LGORITHMS II Layer

Muhammad Adil
I This chapter looks at the network aspects of Raja
congestion.
Introduction
I When the number of packets hosts send into the Network Layer
network is well within its carrying capacity, the Design Issues

Routing
number delivered is proportional to the number sent. Algorithms

I If twice as many are sent, twice as many are Congestion

Control
delivered. Algorithms

References
I However, as the offered load approaches the
carrying capacity, bursts of traffic occasionally fill up
the buffers inside routers and some packets are lost.
I These lost packets consume some of the capacity,
so the number of delivered packets falls below the
ideal curve.
I The network is now congested.
I Unless the network is well designed, it may
experience a congestion collapse.
 The Network
C ONGESTION C ONTROL A LGORITHMS III Layer

Muhammad Adil
Raja
I In this situation performance plummets as the offered
load increases beyond the capacity. Introduction

I This can happen because packets can be sufficiently Network Layer

Design Issues
delayed inside the network that they are no longer Routing
Algorithms
useful when they leave the network.
Congestion
I Unfortunately, congestion cannot wholly be avoided. Control
Algorithms
I If all of a sudden, streams of packets begin arriving References

on three or four input lines and all need the same

output line, a queue will build up.
I If there is insufficient memory to hold all of them,
packets will be lost.
I Adding more memory may help up to a point, but
Nagle (1987) realized that if routers have an infinite
amount of memory, congestion gets worse, not
better.
 The Network
C ONGESTION C ONTROL A LGORITHMS IV Layer

Muhammad Adil
Raja
I This is because by the time packets get to the front
of the queue, they have already timed out Introduction

(repeatedly) and duplicates have been sent. Network Layer

Design Issues
I This makes matters worse, not better – it leads to Routing
Algorithms
congestion collapse.
Congestion
I Low-bandwidth links or routers that process packets Control
Algorithms
more slowly than the line rate can also become References
congested.
I In this case, the situation can be improved by
directing some of the traffic away from the bottleneck
to other parts of the network.
I Eventually, however, all regions of the network will be
congested.
I In this situation, there is no alternative but to shed
load or build a faster network.
 The Network
C ONGESTION C ONTROL A LGORITHMS V Layer

Muhammad Adil
Raja

I It is worth pointing out the difference between Introduction

Network Layer
congestion control and flow control, as the Design Issues
relationship is a very subtle one. Routing
Algorithms
I Congestion control has to do with making sure the Congestion
network is able to carry the offered traffic. Control
Algorithms
I It is a global issue, involving the behavior of all the References

hosts and routers.

I Flow control, in contrast, relates to the traffic
between a particular sender and a particular receiver.
I Its job is to make sure that a fast sender cannot
continually transmit data faster than the receiver is
able to absorb it.
 The Network
C ONGESTION C ONTROL A LGORITHMS VI Layer

Muhammad Adil
Raja
I To see the difference between these two concepts,
consider a network made up of 100-Gbps fiber optic Introduction

links on which a supercomputer is trying to force feed Network Layer

Design Issues
a large file to a personal computer that is capable of Routing
handling only 1 Gbps. Algorithms

Congestion
I Although there is no congestion (the network itself is Control
Algorithms
not in trouble), flow control is needed to force the References
supercomputer to stop frequently to give the
personal computer a chance to breathe.
I At the other extreme, consider a network with 1-Mbps
lines and 1000 large computers, half of which are
trying to transfer files at 100 kbps to the other half.
I Here, the problem is not that of fast senders
overpowering slow receivers, but that the total
offered traffic exceeds what the network can handle.
 The Network
C ONGESTION C ONTROL A LGORITHMS VII Layer

Muhammad Adil
I The reason congestion control and flow control are Raja

often confused is that the best way to handle both Introduction

problems is to get the host to slow down. Network Layer
Design Issues
I Thus, a host can get a “slow down” message either Routing
because the receiver cannot handle the load or Algorithms

Congestion
because the network cannot handle it. Control
Algorithms
I Congestion Collapse: Performance plummets as References
the offered load increases beyond the capacity.
I If routers have an infinite amount of memory,
congestion gets worse not better.
I This is because by the time packets get to the front
of the queue, they have already timed out
(repeatedly) and duplicates have been sent.
I This makes matters worse, not better – it leads to
congestion collapse.
 The Network
C ONGESTION C ONTROL A LGORITHMS VIII Layer

Muhammad Adil
Raja

Introduction
I It is important to differentiate between congestion
Network Layer
control and flow control. Design Issues

Routing
I Congestion control has to do with making sure the Algorithms
network is able to carry the offered traffic. Congestion
Control
I It is a global issue, involving the behavior of all the Algorithms

hosts and routers. References

I Flow control, in contrast, relates to the traffic

between a particular sender and a particular receiver.
I Its job is to make sure that a fast sender cannot
continually transmit data faster than the receiver is
able to absorb it.
 CONGESTION CONTROL ALGORITHMS The Network
C ONGESTION C ONTROL A LGORITHMS IX Layer

Muhammad Adil
Raja

Ideal
Introduction
Capacity of
Goodput (packets/sec)

Network Layer
the network Design Issues

Desirable Routing
Algorithms
response Congestion
Control
Algorithms
Congestion
Onset of collapse
References

congestion

Offered load (packet/sec)

Figure 5-21.
F IGURE With
: With tootoo much
much traffic,
traffic, performance
performance dropsdrops sharply.
sharply.

he network is well designed, it may experience a congestion collap

best way to handle both problems is to get the host to slow down. Thus, a host
The Network
can
Aget a ‘‘slow down’’ TO
PPROACHES message either because theCreceiver
C ONGESTION ONTROL cannotI handle the Layer
load or because the network cannot handle it. We will come back to this point inMuhammad Adil
Chap. 6. Raja
We The
I will presence
start of congestion
our study of congestion means
control that at
by looking the theload is
approaches that
can be used at different time
(temporarily) scales.
greater thanThen
theweresources
will look at(inapproaches
a part ofto pre-Introduction
venting congestion from occurring in the first place, followed by approaches forNetwork Layer
the network) can handle. Design Issues
coping with it once it has set in.
ITwo solutions come to mind: increase the resources Routing
Algorithms
5.3.1 Approaches to Congestion
or decrease the load. Control Congestion
Control
As shown
I presence
The in Fig. 19,
of congestion these
means that solutions are usuallygreater thanAlgorithms
the load is (temporarily)
the resources (in a part
applied of the network)
on different timecan handle.
scales to Two solutions
either preventcome to mind:References
increase the resources or
congestion ordecrease
react totheit load.
once As shown
it has in Fig. 5-22, these solu-
occurred.
tions are usually applied on different time scales to either prevent congestion or
react to it once it has occurred.
Network Traffic-aware Admission Traffic Load
provisioning routing control throttling shedding

Slower Faster
(Preventative) (Reactive)

Figure 5-22. Timescales of approaches to congestion control.

F IGURE : Timescales of approaches to congestion control.
The most basic way to avoid congestion is to build a network that is well
 The Network
A PPROACHES TO C ONGESTION C ONTROL II Layer

Muhammad Adil
I The most basic way to avoid congestion is to build a Raja

network that is well matched to the traffic that it

Introduction
carries. Network Layer
Design Issues
I If there is a low-bandwidth link on the path along
Routing
which most traffic is directed, congestion is likely. Algorithms

I Sometimes resources can be added dynamically Congestion

Control
when there is serious congestion, for example, Algorithms

References
turning on spare routers or enabling lines that are
normally used only as backups (to make the system
fault tolerant) or purchasing bandwidth on the open
market.
I More often, links and routers that are regularly
heavily utilized are upgraded at the earliest
opportunity.
I This is called provisioning and happens on a time
scale of months, driven by long-term traffic trends.
 The Network
A PPROACHES TO C ONGESTION C ONTROL III Layer

Muhammad Adil
I To make the most of the existing network capacity, Raja

routes can be tailored to traffic patterns that change Introduction

during the day as network users wake and sleep in Network Layer
Design Issues
different time zones.
Routing
I For example, routes may be changed to shift traffic Algorithms

Congestion
away from heavily used paths by changing the Control
Algorithms
shortest path weights.
References
I Some local radio stations have helicopters flying
around their cities to report on road congestion to
make it possible for their mobile listeners to route
their packets (cars) around hotspots.
I This is called traffic-aware routing.
I Splitting traffic across multiple paths is also helpful.
I However, sometimes it is not possible to increase
capacity.
 The Network
A PPROACHES TO C ONGESTION C ONTROL IV Layer

Muhammad Adil
I The only way then to beat back the congestion is to Raja
decrease the load.
Introduction
I In a virtual-circuit network, new connections can be Network Layer
refused if they would cause the network to become Design Issues

Routing
congested. Algorithms

I This is called admission control. Congestion

Control
Algorithms
I At a finer granularity, when congestion is imminent
References
the network can deliver feedback to the sources
whose traffic flows are responsible for the problem.
I The network can request these sources to throttle
their traffic, or it can slow down the traffic itself.
I Two difficulties with this approach are how to identify
the onset of congestion, and how to inform the
source that needs to slow down.
I To tackle the first issue, routers can monitor the
average load, queueing delay, or packet loss.
 The Network
A PPROACHES TO C ONGESTION C ONTROL V Layer

Muhammad Adil
I In all cases, rising numbers indicate growing Raja
congestion.
Introduction
I To tackle the second issue, routers must participate Network Layer
in a feedback loop with the sources. Design Issues

Routing
I For a scheme to work correctly, the time scale must Algorithms

be adjusted carefully. Congestion

Control
Algorithms
I If every time two packets arrive in a row, a router
References
yells STOP and every time a router is idle for 20
?sec, it yells GO, the system will oscillate wildly and
never converge.
I On the other hand, if it waits 30 minutes to make
sure before saying anything, the congestion-control
mechanism will react too sluggishly to be of any use.
I Delivering timely feedback is a nontrivial matter.
I An added concern is having routers send more
messages when the network is already congested.
 The Network
A PPROACHES TO C ONGESTION C ONTROL VI Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
I Finally, when all else fails, the network is forced to Algorithms

discard packets that it cannot deliver. Congestion

Control
Algorithms
I The general name for this is load shedding.
References
I A good policy for choosing which packets to discard
can help to prevent congestion collapse.
 The Network
Q UALITY OF S ERVICE (Q O S) I Layer

Muhammad Adil
Raja

I One of the ways to provide QoS is to over-provision Introduction

the network. Network Layer
Design Issues
I Four issues must be addressed to ensure quality of
Routing
service: Algorithms
1. What applications need from the network – Congestion
Control
Application requirements. Algorithms
2. How to regulate the traffic that enters the network – References
traffic shaping.
3. How to reserve resources at routers to guarantee
performance – traffic scheduling.
4. Whether the network can safely accept more traffic –
admission control.
I Integrate services.
I RSVP – The resource reservation protocol.
I Differentiated services.
 retransmissions, and some amount of jitter can be smoothed by buffering The Network
ts Q
at UALITY S ERVICE
the receiver.OFHowever, there(Q O S) IIapplications can do to remedyLayer
is nothing
uation if the network provides too little bandwidth or too much delay. Muhammad Adil
Raja

Application Bandwidth Delay Jitter Loss Introduction

Email Low Low Low Medium Network Layer

Design Issues
File sharing High Low Low Medium Routing
Web access Medium Medium Low Medium Algorithms

Congestion
Remote login Low Medium Medium Medium Control
Algorithms
Audio on demand Low Low High Low
References
Video on demand High Low High Low
Telephony Low High High Low
Videoconferencing High High High Low

Figure 5-27. Stringency of applications’ quality-of-service requirements.

F IGURE : Stringency of applications’ quality-of-service
requirements.
he applications differ in their bandwidth needs, with email, audio in all
, and remote login not needing much, but file sharing and video in all forms
ng a great deal.
More interesting are the delay requirements. File transfer applications, in-
g email and video, are not delay sensitive. If all packets are delayed uni-
 Try to imagine a bucket with a small hole in the bottom, as illustrated in
Fig. 5-28(b). No matter the rate at which water enters the bucket, the outflow is at The Network
Q UALITY OF S ERVICE (Q O S) III
a constant rate, R, when there is any water in the bucket and zero when the bucket
Layer

is empty. Also, once the bucket is full to capacity B, any additional water enter- Muhammad Adil
Raja
ing it spills over the sides and is lost.
Introduction

Host Network Layer

Design Issues
Rate
Put in R Routing
Packets
water Algorithms

Check B Congestion
Take out
bucket Control
water/tokens B Algorithms
here
Rate References
R
Network
(a) (b) (c)

Figure 5-28. (a) Shaping packets. (b) A leaky bucket. (c) A token bucket.
F IGURE : (a) Shaping packets (b) A leaky bucket (c) A token
bucket.
This bucket can be used to shape or police packets entering the network, as
shown in Fig. 5-28(a). Conceptually, each host is connected to the network by an
interface containing a leaky bucket. To send a packet into the network, it must be
possible to put more water into the bucket. If a packet arrives when the bucket is
full, the packet must either be queued until enough water leaks out to hold it or be
discarded. The former might happen at a host shaping its traffic for the network
as part of the operating system. The latter might happen in hardware at a provider
 The Network
I NTERNETWORKING I Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms
I Interoperability of heterogenous networks.
Congestion
I How networks can be connected. Control
Algorithms
I Tunneling. References

I Internetwork routing.
I Packet fragmentation.
 The Network
T HE N ETWORK L AYER IN THE I NTERNET I Layer

Muhammad Adil
Raja
A few design principles:
Introduction
1. Make sure it works. Network Layer
Design Issues
2. Keep it simple.
Routing
3. Make clear choices. Algorithms

Congestion
4. Exploit modularity. Control
Algorithms
5. Expect heterogeneity. References

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.

I The IP Version 4 Protocol.

on both transmission and reception.) In retrospect, little endian would have been
a better choice, but at the time IP was designed, no one knew it would come to The Network
T N
HE computing.
dominate ETWORK AYER IN THE NTERNET L I II Layer

Muhammad Adil
32 Bits Raja

Version IHL Differentiated services Total length Introduction

D M Fragment offset
Network Layer
Identification F F Design Issues
Time to live Protocol Header checksum Routing
Algorithms
Source address
Congestion
Destination address Control
Algorithms

Options (0 or more words) References

Figure 5-46. The IPv4 (Internet Protocol) header.

F IGURE : The IPv4 (Internet Protocol) header.
The Version field keeps track of which version of the protocol the datagram
belongs to. Version 4 dominates the Internet today, and that is where we have
started our discussion. By including the version at the start of each datagram, it
I Internet
becomes possible toControl Protocols.
have a transition between versions over a long period of time.
In fact, IPv6, the next version of IP, was defined more than a decade ago, yet is
I ICMP – Internet COntrol Message Protocol.
only just beginning to be deployed. We will describe it later in this section. Its
use will
I ARPeventually
– Thebe forced when each
Address almost 231 people has a desk-
of China’sProtocol.
Resolution
top PC, a laptop, and an IP phone. As an aside on numbering, IPv5 was an exper-
imental real-time stream protocol that was never widely used.
 The Network
T HE N ETWORK L AYER IN THE I NTERNET III Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
I Label Switching and MPLS. Algorithms

I OSPF – An Interior gateway Routing Protocol. Congestion

Control
Algorithms
I BGP – The Exterior Gateway Routing Protocol.
References
I Internet Multicasting.
I Mobile IP.
 The Network
R EFERENCES Layer

Muhammad Adil
Raja

Introduction

Network Layer
Design Issues

Routing
Algorithms

Congestion
The inspiration and figures for these slides have been Control
Algorithms
taken from, Computer Networks, Andrew S. Tanenbaum, References
5th Edition.