19-03-2024

Module-3: The Network Layer: Network Layer Design Issues, Routing

Algorithms, Congestion Control Algorithms, QoS.

Textbook 1: Ch 5.1 to 5.4

Laboratory Component:

1. Implement transmission of ping messages/trace route over a network

topology consisting of 6 nodes and find the number of packets dropped

due to congestion in the network.

2. Write a program to find the shortest path between vertices using

bellman-ford algorithm

Network Layer Design Issues:

Store-and-forward packet switching
NETWORK LAYER DESIGN ISUES ISP

1. Store-and-Forward Packet Switching

2. Services Provided to the Transport Layer
3. Implementation of Connectionless Service
4. Implementation of Connection-Oriented Service • A host with a packet to send transmits it to the nearest router.

5. Comparison of Virtual-Circuit and Datagram • The packet is received, verified, and stored.
Subnets
• Then it is forwarded to the next router.

• This step can be repeated many times.

• Finally the packet reaches the destination host.

 19-03-2024

Network Layer Design Issues: Network Layer Design Issues:

Services provided to the transport layer Services provided to the transport layer
• Two-type of services:
• The network layer services should been designed with the following goals
– Connection-less services:
in mind.

– The services should be independent of the router technology • 40+ years of experience with the computer network,

– The transport layer should be shielded from the number, type, unreliable internet, hosts doing error control and flow
and topology of the routers present. control.
– The network addresses made available to the transport layer should – Connection-oriented services:
use a uniform numbering plan, even cross LANs and WANs.
• 100+ years of experience with the worldwide telephone
• Two types of network layer services:
system, quality of service.
– Connection-oriented service vs connected-less service
 Connection-less + connection-oriented services.

Network Layer Design Issues:

Services provided to the transport layer Network Layer Design Issues:
• Implementation of connectionless services Implementation of Connectionless Service
– No advance setup is needed.

– Packets are injected into the subnet individually and routed

independently of each other.

– The packets are frequently called datagrams (in analogy with

telegrams) and the subnet is called a datagram subnet.
• Implementation of connection-oriented services
– A path from the source router to the destination router must be
established before any data packets can be sent.

– This connection is called a VC (virtual circuit), similar to physical

circuits set up by the telephone system,
– The subnet is called a virtual-circuit subnet.
 19-03-2024

Network Layer Design Issues: Network Layer Design Issues:

Implementation of Connectionless Service Implementation of Connection-Oriented Service

P1 on H1  P2 on H2 Routing within a virtual-circuit subnet

• P1:application layer  H1: transport layer

• H1:transport layer  H1: network layer (disassemble)

• H1:network layer  H2: network layer

– The routes for packets 1,2,3 H1
 A  C  E  F  H2
– The routes for packets 4
H1  A  B  D  E  F  H2

• H2: network layer  H2: transport layer (assemble)

• H2: transport layer  P2: application layer

Network Layer Design Issues:

Comparison of Virtual-Circuit and Datagram Subnets
ROUTING ALGORITHMS

1. The Optimality Principle

2. Shortest Path Routing
3. Flooding
4. Distance Vector Routing
5. Link State Routing
6. Hierarchical Routing
7. Broadcast Routing
8. Multicast Routing
9. Anycast Routing
[Link] for Mobile Hosts
[Link] in Ad Hoc Networks
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Introduction Introduction
• The main function of the network layer is to route • A router performs two tasks:

packets from the source machine to the destination machine. – To forward the incoming packet according to the routing table
(Forwarding)
• The routing algorithm is used to decide which output line an
– To fill in and update the routing table (Routing)
incoming packet should be transmitted on
• Desirable properties in a routing algorithm:
– For datagram networks, this decision must be made anew
– Correctness , simplicity : no comment
for every arriving data packet since the best route may have
– Robustness : The routing algorithm should cope with changes in the
changed since last time. topology and traffic without requiring all processes in all hosts to be
– For virtual-circuit networks, this decision is made only aborted and the network to be rebooted every time some router crashes.
when a new virtual circuit is being set up. Thereafter, data – Stability: A stable algorithm reaches equilibrium and stays there.
packets just follow the previously established route. – Fairness Efficiency: Conflict between fairness and efficiency.

RoutingAlgorithms:
Introduction
Routing Algorithms: Introduction
• Classes of routing algorithms

Conflict between fairness and efficiency. – Nonadaptive algorithms do not base their routing decisions on
measurements or estimates of the current traffic and topology.
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.

– Adaptive algorithms, in contrast, change their routing decisions

to reflect changes in the topology, and usually the traffic as well.
They differ in
• where they get their information, • what metric is used for
• when they change the routes, optimization.
 19-03-2024

RoutingAlgorithms:
The optimality principle

• Optimality principle: If router J is on the optimal path from

router I to router K (IJK), then the optimal path from J to K
also falls along the same route.
• Sink tree : The set of optimal routes from all sources to a given
destination form a tree rooted at the destination.
(a) A subnet. (b) A sink tree for router B.

RoutingAlgorithms: Routing Algorithms:

Flooding Shortest path routing
• Flooding: Every incoming packet is sent out on every outgoing line
except the one it arrived on. • The idea is to build a graph of the subnet,

• How to damp the flooding process: – with each graph node representing a router and

– One is to have a hop counter contained in the header of each – each graph edge representing a communication line.
packet, which is decremented at each hop. • To choose a route between a given pair of routers, the algorithm just
– The other is to keep track of which packets have been flooded, to finds the shortest path between them.
avoid sending them out a second time. • How to measure path length:
• A variation of flooding that is slightly more practical is selective
– Hops , Physical distance, Bandwidth, traffic, cost , measured
flooding.
delay , mean queue length and
• Flooding is not practical in most applications, but it does have
– Other factors or combinations of these factors.
some uses such as military applications.
 19-03-2024

RoutingAlgorithms: Routing Algorithms:

Shortest path routing Shortest path routing
• Use Dijkstra's algorithm to compute the shortest path.

– Each node is labeled with its distance from the source node along
the best known path.

– Initially, no paths are known, so all nodes are temporarily

labeled with infinity.

– As the algorithm proceeds and paths are found, the labels may
change, reflecting better paths. A label may be either temporary
or permanent.

– When it is discovered that a label represents the shortest possible

path from the source to that node, it is made permanent and never
A->B->E->F->H->D
changed thereafter.

RoutingAlgorithms: RoutingAlgorithms:
Shortest path routing Shortest path routing
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Distance vector routing Distance vector routing
• Assume that
• Distance vector routing(Bellman-Ford routing):
– delay is used as a metric and that the router knows the delay to each of its
– Each router maintains a vector or table giving
neighbors.
• the best known distance to each destination and – Once every Tmsec, each router sends to each neighbor a list of its estimated

• which line to use to get there. delays to each destination. It also receives a similar list from each neighbor.

• Imagine
– These tables are updated by exchanging information with the
– one of these tables has just come in from neighbor X, with Xi being’s
neighbors. To update these tables
estimate of how long it takes to get to router i.
• Measure its distance to its neighbors
– If the router knows that the delay to X is m msec,
• Receive the vectors from its neighbors – Then it can reach router i via X in Xi + m msec.
• Compute its own new vector. • By performing this calculation for each neighbor, a router can find out which
estimate seems the best and use that estimate and the corresponding link in its

RoutingAlgorithms: Routing Algorithms:

Distance vector routing Distance vector routing
The count-to-infinity problem
• Since the Bellman-Ford algorithm is unable to prevent loops, the
fundamental problem with Distance Vector Routing (DVR) protocols is
Routing Loops.
• A routing loop is a situation where a packet keeps getting routed
between two or more routers because of problems in the routing table.
• In case of distance vector protocols, the fact that these protocols route
by rumor and have a slow convergence time can cause routing loops.
• The Count to Infinity Problem is brought on by this routing loop in the
DVR network. When two routers deliver updates simultaneously or
when an interface goes down, routing loops frequently happen.
(a) A subnet.
(b) Input from A, I, H, K, and the new routing table for J.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Distance vector routing Distance vector routing
The count-to-infinity problem The count-to-infinity problem

• Distance-vector routing has the drawback that while cost increases (bad
news) propagate slowly, cost decreases (positive news) propagate quickly.
• Distance-vector routing takes some time for all other routers to become
aware of a broken connection (cost becomes infinity), which is necessary
So in this example, the Bellman-Ford algorithm will converge for
for a routing protocol to function properly.
• Counting to infinity is the name given to the issue. each router, they will have entries for each other. B will know that it

• A broken link's cost may not always be registered as infinite by all routers can get to C at a cost of 1, and A will know that it can get to C via B
until numerous updates have passed. at a cost of 2.

The count-to-infinity problem : It reacts rapidly to good

news, but leisurely to bad news.

RoutingAlgorithms: RoutingAlgorithms:
Distance vector routing Distance vector routing
The count-to-infinity problem

If the link between B and C is disconnected, then B will know that it

can no longer get to C via that link and will remove it from its table.
Before it can send any updates it’s possible that it will receive an
update from A which will be advertising that it can get to C at a cost of
2. B can get to A at a cost of 1, so it will update a route to C via A at a
cost of 3. A will then receive updates from B later and update its cost
to 4. They will then go on feeding each other bad information toward
infinity which is called as Count to Infinity problem.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Link State routing Link State routing
• Problems with distance vector routing • Step 1: Learning about the neighbors

– The delay metric was queue length, thus it did not take line – When a router is booted, its first task is to learn who its
bandwidth into account when choosing routes. neighbors are.
– The algorithm often took too long to converge. – It accomplishes this goal by sending a special HELLO packet on
 Link state routing: The idea behind link state routing is fairly each point-to-point line.
simple and can be stated as five parts. Each router must do the
following: – The router on the other end is expected to send back a reply
1. Discover its neighbors, learn their network address.
giving its name.
2. Set the distance or cost metric to each of its neighbors.
– These names must be globally unique because when a distant
3. Construct a packet containing all it has just learned.
router later hears that three routers are all connected to F, it is
4. Send this packet to and receive packets from all other routers.
essential that it can determine whether all three mean the same F.
5. Compute the shortest path to every other router.

RoutingAlgorithms: RoutingAlgorithms:
Link State routing Link State routing
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) • Step 2: Setting Link Costs
illustrates a broadcast LAN to which three routers, A, C, and F, are directly
– To determine the delay is to send over the line a special
connected. Each of these routers is connected to one or more additional routers, as
shown ECHO packet that the other side is required to send back
• A better way to model the LAN
is to consider it as a node itself, immediately.
as shown in Fig. 5-11(b).
• Here, we have introduced a new, – By measuring the round-trip time and dividing it by 2, the
artificial node, N, to which A, C,
and F are connected. sending router can get a reasonable estimate of the delay.
• One designated router on the
LAN is selected to play the role – Average delay value can be better.
of N in the routing protocol.
• The fact that it is possible to go
from A to C on the LAN is
represented by the path ANC
here.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Link State routing Link State routing
• Steps 3: Building link state packets
• The cost to each neighbor is also given.
• An example network is presented in Fig. 5-12(a) with costs shown as labels
– Each router builds a packet containing all the data.
on the lines.
• The corresponding link state packets for all six routers are shown in Fig. 5-
– The packet starts with the identity of the sender, followed by 12(b).
a sequence number and age and a list of neighbors.

– To build them is easy, but when to build them is difficult

to determine:

• To build them periodically (at regular intervals)

• 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.

RoutingAlgorithms: RoutingAlgorithms:
Link State routing Link State routing
• Steps 4: Distributing the link state packets This algorithm has a few problems, but they are manageable.
– The fundamental idea is to use flooding to distribute the link state packets to all • First, if the sequence numbers wrap around, confusion will reign.
routers. • The solution here is to use a 32-bit sequence number. With one link
– To keep the flood in check, each packet contains a sequence number that is state packet per second, it would take 137 years to wrap around, so this
incremented for each new packet sent. possibility can be ignored.

– Routers keep track of all the (source router, sequence) pairs they see. When a • Second, if a router ever crashes, it will lose track of its sequence

new link state packet comes in, it is checked against the list of packets already number. If it starts again at 0, the next packet it sends will be rejected as
seen. a duplicate.

– If it is new, it is forwarded on all lines except the one it arrived on. If it is a • Third, if a sequence number is ever corrupted and 65,540 is received

duplicate, it is discarded. instead of 4 (a 1-bit error), packets 5 through 65,540 will be rejected as

– If a packet with a sequence number lower than the highest one seen so far ever obsolete, since the current sequence number will be thought to be

arrives, it is rejected as being obsolete as the router has more recent data. 65,540.
 19-03-2024

RoutingAlgorithms:
RoutingAlgorithms:
Link State routing
Link State routing
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 not fully processed,
The solution to all these problems is to include the age of each link state packet. The table records where the packet originated, its sequence number and
age, and the data. In addition, there are send and acknowledgement flags for each of B’s
packet after the sequence number and decrement it once per three links (to A, C, and F, respectively). The send flags mean that the packet must be sent
on the indicated link. The acknowledgement flags mean that it must be acknowledged
second. When the age hits zero, the information from that router there.

is discarded. The packet buffer for router B

RoutingAlgorithms: RoutingAlgorithms:
Link State routing Link State routing
• Steps 5: Computing the new routes • Link state, distance vector, and other algorithms rely on processing at all the

– Once a router has accumulated a full set of link state packets, it routers to compute routes.
• Problems with the hardware or software at even a small number of routers can
can construct the entire subnet graph because every link is
wreak havoc across the network.
represented.
• For example, if a router claims to have a link it does not have or forgets a link it
– Dijkstra’s algorithm can be run locally to construct the shortest does have, the network graph will be incorrect.

path to all possible destinations. The results of this algorithm can • If a router fails to forward packets or corrupts them while forwarding them, the
route will not work as expected.
be installed in the routing tables.
• Finally, if it runs out of memory or does the routing calculation wrong, bad
– Some applications things will happen.
• IS-IS (Intermediate System – Intermediate System) • As the network grows into the range of tens or hundreds of thousands of nodes,
the probability of some router failing occasionally becomes non negligible.
• OSPF (Open Shortest Path First)
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Hierarchical routing Hierarchical routing
• When hierarchical routing is used, the routers are divided into what
• As networks grow in size, the router routing tables grow
we will call regions.
proportionally.
• Two level routing:Every router knows
• Not only is router memory consumed by ever-increasing tables, but – all the details about how to route packets to
more CPU time is needed to scan them and more bandwidth is destinations within its own region
needed to send status reports about them. – but knows nothing about the internal structure of other regions.

• At a certain point, the network may grow to the point where it is • Multiple-level routing: For huge networks, a two-level hierarchy

no longer feasible for every router to have an entry for every may be insufficient; it may be necessary to group the regions into

other router, so the routing will have to be done hierarchically, clusters, the clusters into zones, the zones into groups, and so on,

as it is in the telephone network. until we run out of names for aggregations.

– Regions  clusters zones groups …

RoutingAlgorithms: RoutingAlgorithms:
Hierarchical routing Hierarchical routing
• When a single network becomes very large, an interesting question is
Reduction of routing tables ‘‘how many levels should the hierarchy have?’’
• For example, consider a network with 720 routers. If there is no
hierarchy, each router needs 720 routing table entries.
• If the network is partitioned into 24 regions of 30 routers each, each
router needs 30 local entries plus 23 remote entries for a total of 53
entries.
• If a three-level hierarchy is chosen, with 8 clusters each containing 9
regions of 10 routers, 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.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Hierarchical routing Broadcast routing

• Broadcasting: to send a packet to all destinations simultaneously.

• Kamoun and Kleinrock (1979) discovered that the optimal number
– In some applications, hosts need to send messages to many or all
of levels for an N router network is ln N, requiring a total of e ln N
other hosts.
entries per router.
– For example, a service distributing weather reports, stock market
updates, or live radio programs might work best by sending to all
machines and letting those that are interested read the data.

– Sending a packet to all destinations simultaneously is called

broadcasting.

– Various methods have been proposed for doing it.

RoutingAlgorithms: RoutingAlgorithms:
Broadcast routing Broadcast routing
– Reverse path forwarding:
• Broadcasting: to send a packet to all destinations
simultaneously. • When a broadcast packet arrives at a router, the router checks
to see if the packet arrived on the line that is normally used for
– The source simply sends a distinct packet to every destination.
sending packets to the source of the packets.
– Flooding.
• If so, there is an excellent chance that the broadcast packet
– Multidestination routing (each packet contains either a list of
itself followed the best route from the router and is therefore
destinations or a bit map indicating the desired destinations.) (One
the first copy to arrive at the router. Then the router forwards
router pays full fare and the rest ride free.)
copies of it onto all lines except the one it arrived on.
– To make use of the sink tree for the router initiating the broadcast.
• If no, it is discarded as a duplicate.
– Reverse path forwarding.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Broadcast routing Multicast routing
• Multicasting : to send messages to well-defined groups that are
Reverse path forwarding.
numerically large in size but small compared to the network as whole.
(a) A subnet.
(b) a Sink tree. – Group management: Some way is needed to create and destroy

(c) The tree built by reverse path forwarding. groups, and to allow processes to join and leave groups.

– Computing a spanning tree covering all other routers.

– Multicast routing is to prune the spanning tree.

• When a process sends a multicast packet to a group,

• The first router examines its spanning tree

• and prunes it, removing all the lines that do not lead to hosts that
are members of the group.

RoutingAlgorithms: RoutingAlgorithms:
Multicast routing Multicast routing

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

(c) A multicast tree for group 1. (a)Core-based tree for group 1.
(d) A multicast tree for group 2. (b)Sending to group 1.
 19-03-2024

RoutingAlgorithms: RoutingAlgorithms:
Anycast routing Routing the mobile hosts

• In anycast, a packet is delivered to the nearest member of a

group. Schemes that find these paths are called anycast
routing.

RoutingAlgorithms: Routing
in Ad Hoc Networks
Routing in Ad Hoc Networks: Route discovery

(a) Range of A's broadcast.

CONGESTION CONTROLALGORITHMS
(b) After B and D have received A's broadcast.
• Approaches to Congestion Control
(c) After C, F, and G have received A's broadcast.
• Traffic-Aware Routing
(d) After E, H, and I have received A's broadcast.
• Admission Control
Shaded nodes are new recipients. Arrows show possible reverse routes.
• Traffic Throttling

• Load Shedding
 19-03-2024

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Introduction Introduction
• Too many packets present in (a part of) the network causes packet delay
and loss that degrades performance. This situation is called congestion. When too much traffic is offered, congestion sets in and
• The network and transport layers share the responsibility for handling performance degrades sharply.
congestion.
• 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.
• However, the most effective way to control congestion is to reduce the
load that the transport layer is placing on the network.
• This requires the network and transport layers to work together.
• In this chapter we will look at the network aspects of congestion.

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Introduction Introduction
Congestion causes: Congestion control and flow control
• We would like to design networks that avoid congestion where • Congestion control has to do with making sure the network is able to
possible and do not suffer from congestion collapse if they do
carry the offered traffic.
become congested.
• Unfortunately, congestion cannot wholly be avoided. • It is a global issue, involving the behavior of all the hosts and routers.
• Burst packets on one output line. • Flow control, in contrast, relates to the traffic between a particular
– If all of a sudden, streams of packets begin arriving on three or sender and a particular receiver.
four input lines and all need the same output line, a queue will
build up. • Its job is to make sure that a fast sender cannot continually transmit data
– If there is insufficient memory to hold all of them, packets will faster than the receiver is able to absorb it
be lost. Adding more memory will not help a little but not much.
To see the difference between these two concepts, consider a network made up
• Mismatch between parts of the system of 100-Gbps fiber optic links on which a supercomputer is trying to force feed a
– Insufficient memory. large file to a personal computer that is capable of handling only 1 Gbps.
– Slow CPU. Although there is no congestion (the network itself is not in trouble), flow
control is needed to force the supercomputer to stop frequently to give the
– Low bandwidth. personal computer a chance to breathe
 19-03-2024

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Introduction Approaches to Congestion Control

Congestion control and flow control • Time scales of approaches to congestion control
At the other extreme, consider a network with 1-Mbps lines and 1000 large – Network provisioning: months
computers, half of which are trying to transfer files at 100 kbps to the other – Traffic-aware routing: hours
half. Here, the problem is not that of fast senders overpowering slow – Admission control: minutes
receivers, but that the total offered traffic exceeds what the network can – Traffic throttling: seconds
– Load shedding: seconds
handle.

• Similarity: Both congestion control and flow control can tell the sender
to slow down
– because the receiver cannot handle the load or
– because the network cannot handle it.

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Approaches to Congestion Control Approaches to Congestion Control
• The most basic way to avoid congestion is to build a network that is well
• To make the most of the existing network capacity, routes can be
matched to the traffic that it carries. If there is a low-bandwidth link on the
tailored to traffic patterns that change during the day as network users
path along which most traffic is directed, congestion is likely.
wake and sleep in different time zones.
• Sometimes resources can be added dynamically when there is serious
• For example, routes may be changed to shift traffic away from heavily
congestion, for example, turning on spare routers or enabling lines that are
used paths by changing the shortest path weights.
normally used only as backups (to make the system fault tolerant) or
• Some local radio stations have helicopters flying around their cities to
purchasing bandwidth on the open market.
report on road congestion to make it possible for their mobile listeners
• More often, links and routers that are regularly heavily utilized are
to route their packets (cars) around hotspots.
upgraded at the earliest opportunity.
• This is called traffic-aware routing.
• This is called provisioning and happens on a time scale of months, driven
• Splitting traffic across multiple paths is also helpful.
by long-term traffic trends.
 19-03-2024

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Approaches to Congestion Control Approaches to Congestion Control

• However, sometimes it is not possible to increase capacity. • At a finer granularity, when congestion is imminent the network
• The only way then to beat back the congestion is to decrease the load. can deliver feedback to the sources whose traffic flows are

• In a virtual-circuit network, new connections can be refused if they responsible for the problem.

would cause the network to become congested. • The network can request these sources to throttle their traffic,
or it can slow down the traffic itself.
• This is called admission control.

• Finally, when all else fails, the network is forced to discard packets
that it cannot deliver.
• The general name for this is load shedding.
• A good policy for choosing which packets to discard can help to
prevent congestion collapse

Congestion ControlAlgorithms: Congestion ControlAlgorithms:

Traffic-Aware Routing Traffic-Aware Routing
• The first approach we will examine is traffic-aware routing. Consider the network of Fig. 5-23, which is divided into two parts, East and West, connected
by two links, CF and EI. Suppose that most of the traffic between East and West is using link
• The routing schemes we looked at in Sec 5.2 used fixed link weights.
CF, and, as a result, this link is heavily loaded with long delays. Including queueing delay in
• These schemes adapted to changes in topology, but not to changes in
the weight used for the shortest path calculation will make EI more attractive. After the new
load. routing tables have been installed, most of the East-West traffic will now go over EI, loading
• The goal in taking load into account when computing routes is to shift this link. Consequently, in the next update, CF will appear to be the shortest path. As a result,
the routing tables may oscillate wildly, leading to erratic routing and many potential
traffic away from hotspots that will be the first places in the network to
problems.
experience congestion.
• The most direct way to do this is to set the link weight to be a function of
A subnet in which the East
the (fixed) link bandwidth and propagation delay plus the (variable) and West parts are connected
by two lines.
measured load or average queuing delay.
• Least-weight paths will then favour paths that are more lightly loaded, all
else being equal.
 19-03-2024

Congestion Control Algorithms: Congestion Control Algorithms:

Admission control Admission control

• Traffic is often described in terms of its rate and shape.

• A commonly used descriptor that captures this effect is the

leaky bucket or token bucket.

• Armed with traffic descriptions, the network can decide

whether to admit the new virtual circuit.

(a) A congested subnet. (b) A redrawn subnet, eliminates
congestion and a virtual circuit
from A to B.

Congestion Control Algorithms: Congestion Control Algorithms:

Traffic Throttling Traffic Throttling
• In the Internet and many other computer networks, senders adjust their
• Each router monitors the utilization of its output lines and other
transmissions to send as much traffic as the network can readily deliver. resources.
• Whenever u moves above the threshold, the output lines enters a
1. Routers must determine when congestion is approaching, “warning stat”.
ideally before it has arrived. • To maintain a good estimate of the queueing delay, d, a sample of
the instantaneous queue length, s, can be made periodically and d
updated according to
• To do so, each router can continuously monitor the
resources it is using.
where the constant α determines how fast the router forgets recent history.
• Three possibilities are the utilization of the output links,
2. Routers must deliver timely feedback to the senders that are causing
the buffering of queued packets inside the router, and the
the congestion.
number of packets that are lost due to insufficient
– Warning bits
buffering.
– Choke packets
– Hop-by-hop choke packets
 19-03-2024

Congestion Control Algorithms: Congestion Control Algorithms:

Traffic Throttling Traffic Throttling
Choke Packets Choke Packets
• The most direct way to notify a sender of congestion is to tell it directly. • When the source host gets the choke packet, it is required to reduce the
• In this approach, the router selects a congested packet and sends a choke traffic sent to the specified destination, for example, by 50%.
packet back to the source host, giving it the destination found in the • In a datagram network, simply picking packets at random when there is

packet. congestion is likely to cause choke packets to be sent to fast senders, because
they will have the most packets in the queue.
• The original packet may be tagged (a header bit is turned on) so that it
• The feedback implicit in this protocol can help prevent congestion yet not
will not generate any more choke packets farther along the path and then
throttle any sender unless it causes trouble
forwarded in the usual way.
• To avoid increasing load on the network during a time of congestion, the
router may only send choke packets at a low rate.

Congestion Control Algorithms: Congestion Control Algorithms:

Traffic Throttling Traffic Throttling
Congestion Control in Datagram Subnets
Congestion Control in Datagram Subnets Hop-by-hop choke packets
Explicit Congestion Notification
• At high speeds or over long distances, sending a choke packet to the
• Two bits in the IP packet header are used to record whether
the packet has experienced congestion. source hosts does not work well because the reaction is so slow.
• If any of the routers they pass through is congested, that
– For example, a host in San Francisco (router A) sends packets to a host in New
router will then mark the packet as having experienced
congestion as it is forwarded. York at 155Mbps.
• The destination will then echo any marks back to the sender – When the New York host begins to run out of buffers, it will take about
as an explicit congestion signal
40msec for a choke packet to get back to San Francisco to tell it to slow
down.
– In those 40 msec, another 6.2 megabits will have been sent.

• To have the choke packet take effect at every hop it passes

through.
 19-03-2024

Congestion Control Algorithms: Congestion Control Algorithms:

Traffic Throttling Load Shedding
• Hop-by-Hop Choke Packets b. A choke packet that affects each • Load shedding is a fancy way of saying when routers are being
(a) A choke packet that affects only the hop it passes through.
source. drowned by packets that they cannot handle, they just throw them
away. (Electricity)
• The key question for a router drowning in packets is which packets to
drop. The preferred choice may depend on the type of applications that
use the network.
• For a file transfer, an old packet is worth more than a new one. This is because
dropping packet 6 and keeping packets 7 through 10, for example, will only force
the receiver to do more work to buffer data that it cannot yet use.
• In contrast, for real-time media, a new packet is worth more than an old one. This
is because packets become useless if they are delayed and miss the time at which
they must be played out to the user.

Congestion Control Algorithms: Congestion Control Algorithms:

Load Shedding Load Shedding
• RED (Random Early Detection)
• Which packets to drop? – Why early?
– At random • Dealing with congestion after it is first detected is more effective
– Application: To drink wine (old is better than new) or milk (new is than letting it gum up the works and then trying to deal with it.
better than old)? • Try to discard packets before all the buffer space is really
– Compression: full frame or modification? exhausted.
– Priority: High or low? (Unless there is some significant – Why random?
incentive to mark packets as anything other than VERY • Since the router probably cannot tell which source is causing
IMPORTANT – NEVER NEVER DISCARD, nobody will do it. most of the trouble, picking a packet at random from the queue
that triggered the action is probably as good as it can do.
 19-03-2024

Quality Of Service

QUALITY OF SERVICE • Quality of service mechanisms let a network with less capacity
meet application requirements just as well at a lower cost.
• Requirements of QoS • With quality of service mechanisms, the network can honor the
• Techniques for QoS performance guarantees that it makes even when traffic spikes,

• Integrated Services at the cost of turning down some requests

• Differentiated Services Four issues must be addressed to ensure quality of service:

1. What applications need from the network.
• Label Switching and MPLS
2. How to regulate the traffic that enters the network.
3. How to reserve resources at routers to guarantee performance.
4. Whether the network can safely accept more traffic.

Quality Of Service: Quality Of Service: Requirements

Requirements
• A stream of packets from a source to a destination is called a flow. How stringent the quality-of-service requirements are.
• A flow might be all the packets of a connection in a connection-
oriented network, or all the packets sent from one process to another
process in a connectionless network.
• The needs of each flow can be characterized by four primary
parameters:
 bandwidth,
 delay,
 jitter,
The variation (i.e., standard deviation) in the delay or packet arrival
 loss. times is called jitter. T
• Together, these determine the QoS (Quality of Service) the flow
requires
 19-03-2024

Quality Of Service: Quality Of Service:

Traffic shaping Traffic shaping
• The goal is to allow applications to transmit a wide variety of traffic
• Before the network can make QoS guarantees, it must know what
that suits their needs, including some bursts, yet have a simple and useful
traffic is being guaranteed.
way to describe the possible traffic patterns to the network.
• However, traffic in data networks is bursty.
• When a flow is set up, the user and the network (i.e., the customer and the
• It typically arrives at non uniform rates as the traffic rate varies (e.g.,
provider) agree on a certain traffic pattern (i.e., shape) for that flow.
videoconferencing with compression), users interact with applications
• Sometimes this agreement is called an SLA (Service Level Agreement),
(e.g., browsing a new Webpage), and computers switch between tasks.
especially when it is made over aggregate flows and long periods of time,
• Bursts of traffic are more difficult to handle than constant-rate traffic
such as all of the traffic for a given customer.
because they can fill buffers and cause packets to be lost.
• As long as the customer fulfills her part of the bargain and only sends
• Traffic shaping is a technique for regulating the average rate and
packets according to the agreed-on contract, the provider promises to
burstiness of a flow of data that enters the network.
deliver them all in a timely fashion

Quality Of Service: Quality Of Service:

Traffic shaping Traffic shaping

• Traffic shaping reduces congestion and thus helps the network live up to its
• We have already seen one way to limit the amount of data an
promise.
application sends: the sliding window, which uses one parameter to
• However, to make it work, there is also the issue of how the provider can
limit how much data is in transit at any given time, which indirectly
tell if the customer is following the agreement and what to do if the
limits the rate.
customer is not.
• Now we will look at a more general way to characterize traffic, with
• Packets in excess of the agreed pattern might be dropped by the network, the leaky bucket and token bucket algorithms.
or they might be marked as having lower priority.
• The formulations are slightly different but give an equivalent result.
• Monitoring a traffic flow is called traffic policing.
 19-03-2024

Quality Of Service: Quality Of Service:

Traffic shaping • This bucket can be used to shape or Traffic shaping
police packets entering the network,
as shown in Fig. 5-28(a).
• A different but equivalent formulation is to imagine the
• Conceptually, each host is connected network interface as a bucket that is being filled, as
to the network by an interface
containing a leaky bucket. shown in Fig. 5-28(c).
• To send a packet into the network, it
must be possible to put more water
• The tap is running at rate R and the bucket has a
into the bucket. capacity of B, as before.
• If a packet arrives when the bucket
is full, the packet must either be • Now, to send a packet we must be able to take water, or
(a) Shaping packets. (b)A leaky bucket queued until enough water leaks out
to hold it or be discarded.
tokens, as the contents are commonly called, out of the
Try to imagine a bucket with a small hole in the • The former might happen at a host bucket (rather than putting water into the bucket).
shaping its traffic for the network as (c) AToken bucket
bottom, as illustrated in Fig. 5-28(b). No matter the
part of the operating system. • No more than a fixed number of tokens, B, can
rate at which water enters the bucket, the outflow is • The latter might happen in hardware
at a provider network interface that
accumulate in the bucket, and if the bucket is empty, we
at a constant rate, R, when there is any water in the
is policing traffic entering the must wait until more tokens arrive before we can send
bucket and zero when the bucket is empty. Also, network.
once the bucket is full to capacity B, any additional • This technique was proposed by another packet.
Turner (1986) and is called the leaky
water entering it spills over the sides and is lost. bucket algorithm.
• This algorithm is called the token bucket algorithm.

Quality Of Service: Quality Of Service:

Traffic shaping Traffic shaping
• Leaky and token buckets limit the long-term rate of a flow but allow
short term bursts up to a maximum regulated length to pass through (a) Traffic from a host.
unaltered and without suffering any artificial delays.
• Large bursts will be smoothed by a leaky bucket traffic shaper to
reduce congestion in the network. Output shaped by a token
bucket of rate 200 Mbps and
• As an example, imagine that a computer can produce data at up to capacity
1000 Mbps (125 million bytes/sec) and that the first link of the (b) 9600 KB,
network also runs at this speed. (c) 0 KB.
 19-03-2024

Quality Of Service:
Traffic shaping
Quality Of Service: Packet
Scheduling
Token bucket level for • Resource reservation
shaping with rate 200 – Suppose there is a specific route for a flow, it
Mbps and capacity becomes possible to reserve resources along the route
(d) 16000 KB, to make sure the needed capacity is available.
(e) 9600 KB, and • What resources to reserve?
(f) 0KB.. – Bandwidth
– Buffer space
– CPU cycles

Quality Of Service: Packet Scheduling Quality Of Service: Packet Scheduling

(a)Weighted Fair Queueing.
(b)Finishing times for the packets.
Round-robin Fair Queuing
 19-03-2024

Quality Of Service: Admission Control Quality Of Service: Admission Control

Bandwidth and delay guarantees with token buckets
An example flow specification and WFQ.

Quality Of Service: Integrated Quality Of Service: Integrated

services services
• How to stream multimedia?
– Integrated services (Flow-based algorithms) (a) A network, (b) The multicast spanning tree for host 1.
– Differential services (Class-based algorithms) (c) The multicast spanning tree for host 2.
• How about having the senders reserve bandwidth in
advance? Too many destinations
• RSVP (Resource reSerVation Protocol): to allow
multiple senders to transmit to multiple groups of
receivers, permits individual receivers to switch
channels freely, and optimizes bandwidth use while at
the same time eliminating congestion.
 19-03-2024

Quality Of Service: Integrated services Quality Of Service: Differential services

(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. Expedited (.畅通的, 迅速的) packets experience a
traffic-free network. (RFC 3246)

Quality Of Service: Differential

Quality Of Service:
services
Label switching and MPLS

• Assured Forwarding (确定转发) (RFC2597)

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