Unit-I Part-II

 ROUTING ALGORITHMS

1 The Optimality Principle

2 Shortest Path Algorithm
3 Flooding
4 Distance Vector Routing
5 Link State Routing
6 Hierarchical Routing
7 Broadcast Routing
8 Multicast Routing
9 Anycast Routing
10 Routing for Mobile Hosts
11 Routing in Ad Hoc Networks

 CONGESTION CONTROL ALGORITHMS

1 Approaches to Congestion Control

2 Traffic-Aware Routing (Adopting routes to split traffic when
congestion detected)
3 Admission Control(Don’t Allow new connections if
congestion is detected)
4 Traffic Throttling(Give feedback to avoid congestion)
5 Load Shedding (Drop packets)

 QUALITY OF SERVICE

1 Application Requirements
2 Traffic Shaping
3 Packet Scheduling
4 Admission Control
5 Integrated Services
6 Differentiated Services
ROUTING ALGORITHMS

1 The Optimality Principle

o Any sub path of an optimal path is also optimal
o Sink Tree is used in optimal path

2 Shortest Path Algorithm

 Step1:

 Step2:

 Step3:

 Step4:
 Step5:

3 Flooding
o Send every packet to all lines except the one it arrived on
o Large number of duplicate packets
o Should use counter to prevent infinite duplicates
o Should use sequence numbers to identify duplicates
o Will always find shortest path

 Computer networks generally use dynamic routing algorithms that are more
complex than flooding, but more efficient because they find shortest paths for the
current topology.
 Two dynamic algorithms in particular, distance vector routing and link state routing, are the
most popular.

4 Distance Vector Routing

o Each router exchange with its neighbors list of delays to each destination
o Router X estimates delay to router Z
 Router Y is a neighbor to router X
 D (X, Z) =D (X, Y) + D (Y, Z)
The Count-to-Infinity Problem

 The settling of routes to best paths across the network is called convergence.
 Distance vector routing is useful as a simple technique by which routers
o can collectively compute shortest paths, but it has a serious drawback in practice: although it
converges to the correct answer, it may do so slowly.
  Solution to Count to Infinity Problem
o preventing routers from advertising their best paths back to the neighbors from which they
heard
them with the split horizon with poisoned reverse rule discussed in RFC 1058.
o However, none of these heuristics work well in practice despite the colorful names.
o The core of the problem is that when X tells Y that it has a path somewhere, Y has no way of
knowing whether it itself is on the path

5 Link State Routing

 Distance vector routing was used in the ARPANET until 1979, when it was replaced by link state
routing.
 The primary problem that caused its demise was that the algorithm often took too long to
converge after the network topology changed (due to the count-to-infinity problem).
 Consequently, it was replaced by an entirely new algorithm, now called link state routing.
 Variants of link state routing called IS-IS and OSPF are the routing algorithms that are most
widely used inside large networks and the Internet today

Steps in LSR:
 Discover its neighbors and learn their network addresses.
o Send HELLO packet on point-to-point lines
o If routers are connected to a LAN, the LAN can be represented as a node
 Set the distance or cost metric to each of its neighbors.
o Send ECHO packet
o Wait for response
o Measure round-trip-time
o To take load into account: start timer when packet is queued
o To ignore the load: start timer when packet reaches the front of the queue
 Construct a packet telling all it has just learned.
  Send this packet to and receive packets from all other routers.
o Use flooding
o Packet contains sequence number
o When packet is received
 If new, forward to all except coming from
 If duplicate, discard
 If old, rejected
o Use 32-bit sequence numbers
o Include age, decremented once per second

 Compute the shortest path to every other router

o Now Dijkstra’s algorithm can be run locally to construct the shortest paths to all possible
destinations.

6 Hierarchical Routing
 Problems with routing tables
 Routing tables grow with network size
 More router memory
 More CPU time to scan them
 More bandwidth to send updates
 For large networks, better to do routing hierarchically
 Hierarchy can be in multiple levels
o regions
o clusters
o zones
7 Broadcast Routing
 Sending a packet to all destinations simultaneously is called broadcasting.
 Simply sending a distinct packet to each destination is not practical
 An improvement is multidestination routing, in which each packet contains either a list of
destinations.
 However, this scheme still requires the source to know all the destinations, plus it is as much
work for a router to determine where to send one multidestination packet as it is for multiple
distinct packets.
 A better broadcast routing technique: flooding
o Reverse Path Forwarding: Routers when receiving broadcast packets from a source
will forward to next hop only if packet is arrived from optimal path
 Best option: A spanning tree is a subset of the network that includes all the routers but contains
no loops. Sink trees are spanning trees. (Kruskal’s Algorithm, Prim’s Algorithm)

8 Multicast Routing

 Sending a message to such a group is called multicasting.

 All multicasting schemes require some way to create and destroy groups and to identify which
routers are members of a group
 Multicast routing schemes build on the broadcast routing schemes.
  Now what's the diff. between MST and SPT

9 Anycast Routing
 In Anycast, a packet is delivered to the nearest member of a group.

10 Routing for Mobile Hosts

 Encapsulation: putting the packet with a new header and sending to the care of
address. This mechanism is called tunneling.
11 Routing in Ad Hoc Networks

 Networks of nodes that just happen to be near each other are called ad hoc networks or MANETs.
Well Known routing protocols are AODV and DSR. Both DSR and AODV are demand-driven
protocols which form a route on demand when a transmitting computer desires a route.

AODV (Adhoc On-demand Distance Vector)
o It is a relative of the distance vector algorithm that has been adapted to work in a mobile
environment, in which nodes often have limited bandwidth and battery lifetimes.
o AODV is an on demand routing protocol. This protocol finds routes for a node only when
it has data packet for transmission.
o AODV routing consists of three phases: route discovery, data transmission and route
maintenance
 Routing REQuest message (RREQ) is broadcasted by a node requiring a route to
another node,
 Routing REPly message (RREP) is unicasted back to the source of RREQ, and
 Route ERRor message (RERR) is sent to notify other nodes of the loss of the
link. HELLO messages are used for detecting and monitoring links to neighbors.

 Another well-known on demand scheme is DSR (Dynamic Source Routing).

o The packet sender lists the route in the packet’s header so that the next node to which the
packet has to be transmitted can be identified by the address on the way to the destination
host.
 A different strategy based on geography is explored by GPSR (Greedy Perimeter Stateless
Routing)
 CONGESTION CONTROL ALGORITHMS

Why???
 The routing schemes adapted to changes in topology, but not to changes in load.
 Shift traffic away from places which contribute to congestion.
 Simple technique is to assign weights to paths.

 Too many packets present in (a part of) the network causes packet delay and loss that degrades
performance. This situation is called congestion.
 The network and transport layers share the responsibility for handling congestion

Congestion Collapse: A point where performance drops as the offered load increases beyond the
capacity.
Goodput: It is the rate at which useful packets are delivered by the network.

 Congestion Control vs. Flow Control

o Congestion control has to do with making sure the network is able to carry the offered
traffic. It is a global issue, involving the behavior of all the hosts and routers.
o Flow control, in contrast, relates to the traffic between a particular sender and a particular
receiver. Its job is to make sure that a fast sender cannot continually transmit data faster
than the receiver is able to absorb it.
1 Approaches to Congestion Control

 The most basic way to avoid congestion is to build a network that is well matched to the traffic
that it carries. This is called Provisioning and happens on a time scale of months, driven by long-
term traffic trends.
 Traffic-Aware Routing: routes can be tailored to traffic patterns that change during the day as
network users wake and sleep in different time zones.
o The first is multipath routing, in which there can be multiple paths from a source to a
destination.
o The second one is for the routing scheme to shift traffic across routes slowly enough that
it is able to converge.
o Internet routing protocols do not generally adjust their routes depending on the load.
Instead, adjustments are made outside the routing protocol by slowly changing its inputs.
This is called Traffic Engineering.

 New connections can be refused if they would cause the network to become congested. This is
called Admission Control.
o measurements of past behavior that capture the statistics of transmissions can be used to
estimate the number of circuits to admit.
 Traffic Throttling: The network aims to operate just before the onset of congestion. When
congestion is imminent, it must tell the senders to throttle back their transmissions and slow
down. (also called congestion avoidance)
o Approaches to throttling traffic
 First, routers must determine when congestion is approaching, ideally before it
has arrived. Routers use queuing delay as follows:
 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 dnew = αdold + (1 - α)s where the constant α
determines how fast the router forgets recent history. This is called an
EWMA (Exponentially Weighted Moving Average).
  The second problem is that routers must deliver timely feedback to the senders
that are causing the congestion. Using Choke Packets, Explicit Congestion
Notification and Hop by Hop Backpressure
 Choke Packets: In this approach, the router selects a congested packet
and sends a choke packet back to the source host, at a low rate. When the
source host gets the choke packet, it is required to reduce the traffic
sent to the specified destination, for example, by 50%.
 Explicit Congestion Notification (ECN): Instead of generating
additional packets to warn of congestion, a router can tag any packet it
forwards (by setting a bit in the packet’s header) to signal that it is
experiencing congestion.

 Hop by Hop Backpressure: An alternative approach is to have the

choke packet take effect at every hop it passes through.
 When all else fails, the network is forced to discard packets that it cannot deliver. The general
name for this is Load Shedding
o The key question for a router drowning in packets is which packets to drop, old (a file
transfer) or new (real-time media). The preferred choice may depend on the type of
applications that use the network. More intelligent load shedding requires cooperation
from the senders.
o Random Early Detection: discard packets before all the buffer space is really exhausted.
To determine when to start discarding, routers maintain a running average of their queue
lengths. When the average queue length on some link exceeds a threshold, the
link is said to be congested and a small fraction of the packets are dropped at random.
RED is used when hosts cannot receive explicit signals.

QUALITY OF SERVICE
 we continue our study of network performance, but now with a sharper focus on ways to provide
quality of service that is matched to application needs.
 Solutions: An easy solution to provide good quality of service is to build a network with
enough capacity for whatever traffic will be thrown at it. The name for this solution is
 overprovisioning. Drawback: The trouble with this solution is that it is expensive. Quality of
service mechanisms let a network with less capacity meet application requirements just as well at
a lower cost.
 Four issues must be addressed to ensure quality of service:
1. What applications need from the network.
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.

 Application Requirements: A stream of packets from a source to a destination is called a

flow. 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, and loss. Together, these determine the QoS (Quality of Service) the flow requires.

Note: High, Medium and Low determines sensitivity

o File transfer applications, including email and video, are not delay sensitive.
 Real-time applications, such as telephony and videoconferencing, have strict
delay requirements.
o The variation (i.e., standard deviation) in the delay or packet arrival times is called jitter.
 Video and especially audio are extremely sensitive to jitter.
 Traffic Shaping: It is a technique for regulating the average rate and burstiness
of a flow of data that enters the network.
o The goal is to allow applications to transmit a wide variety of traffic that suits their needs.
o Sometimes this agreement is called an SLA (Service Level Agreement).
o Packets in excess of the agreed pattern might be dropped by the network, or
they might be marked as having lower priority.
o Monitoring a traffic flow is called traffic policing
 o How to drop packets Two algorithms, Leaky and Token Buckets
o Leaky Bucket Algorithm: No matter the rate at which water enters the bucket, the
outflow is at a constant rate, R, when there is any water in the bucket and zero when the
bucket is empty. Also, once the bucket is full to capacity B, any additional water entering
it spills over the sides and is lost. 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.
o Token Bucket Algorithm: The tap is running at rate R and the bucket has a
capacity of B, as before. Now, to send a packet we must be able to take water, or
tokens, as the contents are commonly called, out of the bucket (rather than putting
water into the bucket). No more than a fixed number of tokens, B, can accumulate
in the bucket, and if the bucket is empty, we must wait until more tokens arrive
before we can send another packet. This algorithm is called the token bucket
algorithm.

 Packet Scheduling: Algorithms that allocate router resources among the packets of a
flow and between competing flows are called packet scheduling algorithms.
1. Bandwidth.
2. Buffer space.
3. CPU cycles can be reserved
Routers used FCFS or FIFO model for dropping packets. A better way is fair queuing.
o Fair queuing: It is the algorithm used by routers to maintain separate queues for
each output line for sending packets. It is fair in the sense that all flows get to send
packets at the same rate. Drawback: large packets get more bandwidth. Hence
improvement is byte-by-byte round robin instead of packet-by-packet round robin.
o WFQ (Weighted Fair Queueing): For giving different priority to diff
applications.
 Admission Control:
o The reservations must be made at all of the routers along the route that the packets
take through the network. QoS guarantees for new flows may still be accommodated
by choosing a different route for the flow that has excess capacity. This is called QoS
routing.
o Because many parties may be involved in the flow negotiation (the sender, the
receiver, and all the routers along the path between them), flows must be described
accurately in terms of specific parameters that can be negotiated. A set of
such parameters is called a flow specification.
 Integrated Services: It is an architecture for streaming multimedia. Under multicast
conditions, the approach of having the senders reserve bandwidth in advance does not work
well, since it would require each sender to track all entries and exits of its audience.
 RSVP—The Resource Reservation Protocol:
o This protocol is used for making the reservations; RSVP allows multiple senders to
transmit to multiple groups of receivers.
o It permits individual receivers to switch channels freely, and optimizes bandwidth
use while at the same time eliminating congestion.
o The only difference from normal multicasting is a little extra information that is
multicast to the group periodically to tell the routers along the tree to maintain certain
data structures in their memories.
 Differentiated Services:
o It is a class based service.
o If a customer subscribes to differentiated services, customer packets entering the
domain are marked with the class to which they belong.
 Expedited Forwarding:
o The expedited packets should be able to transit the network as though no other
packets were present.