LM CCN Section 2.2: Alternative Approaches to Routing
Computer and Communication Networks
Alternative Approaches to Routing John Easton
1
Learning Objectives
! Alternative approaches to routing – Flood routing
– Deflection routing
– Source routing
! Gradient approaches
! Congestion control and its impacts on routing
2
Alternative Routing Approaches
! Most routing is based on shortest path (and variants) ! Other approaches may be used:
– Flooding
– Deflection routing – Source routing
– Gradient routing
3
1
LM CCN Section 2.2: Alternative Approaches to Routing
Flooding
! Switches flood packets to all ports except the one that received it
! Pros:
– Good for survivability of packet (e.g. military)
! Cons:
– Exponential growth of traffic
! Mitigations:
– Add TTL to packet, set to network diameter
– Add switch identifier to packet when seen, don’t forward if
identifier present
– Add source & sequence number to packet, switches log forwarded combinations, reject if seen
4
Flooding (Cont.)
1
4 2
3
6
5
5
Flooding (Cont.)
1
2
3
6
4
5
6
2
LM CCN Section 2.2: Alternative Approaches to Routing
Flooding (Cont.)
1
2
3
6
4
5
7
Deflection Routing
! Also known as “hot potato” routing
! Switches maintain multiple paths to destination
– If preferred path is congested, use the alternative
– Works well in Manhattan-style topologies ! Pros:
– Switches can have reduced buffer sizes (less likely to queue)
! Cons:
– Time to delivery and packet ordering on receipt have increased variability
! Very good for optical devices (buffers expensive)
8
Deflection Routing (Cont.)
0,0 0,1
1,0
2,0
3,0
0,2 0,3
Source
Target
Busy Route
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
9
3
LM CCN Section 2.2: Alternative Approaches to Routing
Deflection Routing (Cont.)
0,0 0,1
1,0
2,0
3,0
0,2 0,3
Source
Target
Busy Route
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
10
Deflection Routing (Cont.)
0,0 0,1
1,0
2,0
3,0
0,2 0,3
Source
Target
Busy Route
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
11
Source Routing
! Sender specifies the complete route to destination – Adds information to header of datagram
! Nodes strip off their identifier on receipt, and forward packet to next in path
! Pros:
– Less load on intermediate nodes
– Avoid particular hosts (e.g. known heavy loadings)
! Cons:
– Sender must know routes to all hosts if network is to be
reachable
– Link failures more disruptive
12
4
LM CCN Section 2.2: Alternative Approaches to Routing
Source Routing (Cont.)
13
1,3,6,B
A
6
2
4
5
B
13
Source Routing (Cont.)
13
3,6,B
1,3,6,B
A
6
2
4
5
B
14
Source Routing (Cont.)
13
3,6,B
1,3,6,B
6,B
A
6
2
4
5
B
15
5
LM CCN Section 2.2: Alternative Approaches to Routing
Source Routing (Cont.)
13
3,6,B
1,3,6,B
A
6,B
6
B
2
4
5
B
16
Gradient Descent Routing
! Gradient built around a single sink node ! Nodes only pass messages to lower tiers ! Gradient broadcast adds path diversity
! Gradients also allow
– Energy management using elevation
0
1 2
3
17
RPL
! RoutingProtocolforLowPowerandLossyNetworks
! IPv6meshnetworkwithnode-by-noderouting
! BasedonDestinationOrientedDirectedAcyclic
Graphs (DODAGs)
! Twomodestoallowforlowpower/capacitydevices
– Storingnodes
– Non-storingnodes
! DAGInformationObjects(DIO)usedtomonitorroutestoDODAGroot
! DestinationAdvertisementObjects(DAO)usedforreportingdownward
routes
! Storingnodemodeusesmorepowerandmemoryonnodes…
– …butcanroutedirectly
! Non-storingnodemodemustrouteviaDODAGroot
DIO Flow
DAO Flow
18
6
LM CCN Section 2.2: Alternative Approaches to Routing
RPL Rank and Metrics
Rank 1 Rank 2 Rank 3 Rank4
! Example metrics include: – Hop count
– Latency
– Link Quality Level – RSSI
– Link Colour
– Node Energy
– Throughput
19
Routing Information Protocol
! The Routing Information Protocol (RIP) is a popular distance vector routing protocol
! Based on “routed” in BSD Unix
! Commonly uses # hops as metric
! Hops limited to 15
– 16 used for “unreachable”
! RIP messages used to monitor topology
– UDP
– Request issued to neighbours ~30 seconds – Response expected within ~180 seconds
– No response? Assumed unreachable
20
RIP Messages
! Format shown in table ! Command
Command Version Address Family Identifier IP Address
Metric
…
– Purpose of message, route request or response ! Version
– Version of RIP protocol used ! Address family
– Address type – currently only IP defined ! IP address
– Address of target of message ! Metric
– Cost to destination, usually in hops
21
7
LM CCN Section 2.2: Alternative Approaches to Routing
RIP Routing Table
! Nodes use RIP responses to build a routing table ! Example shows RIP routes to all subnets from B
xy
uC2 vC2A wC2B xA2z yA2 z-1wu
Destination Next Router Subnet
Hops to Destination
Cv
22
Congestion
! Congestion can have a serious impact on routing – In the worst cases, it can be a self-escalating
problem
! Congestion control aims to reduce or eliminate
congestion at a NE, between a source and a
receiver
! Larger buffers may not be the answer
– When congestion occurs it is more severe and lasts longer
! Two approaches: – Open-loop
– Closed-loop
23
Open-loop Congestion Control
! Prevent congestion occurring (no feedback)
! Assumption that if a traffic source is accepted (based on QoS criteria), it will not
congest the network
! Admission control
– New source reports a traffic descriptor at connection setup
! e.g. peak traffic rate, avg. traffic rate, max burst size etc.
– Required bandwidth is calculated and reserved
! If this is available, the source is admitted and can transmit
! Policing
– If source violates contract, traffic is tagged, and is first to be rejected if
congestion occurs
– “Leaky bucket” algorithm (outflow at known rate, avoid overflow)
! Traffic shaping
– A source may control it’s traffic to match the profile it advertised if incoming
profile is unknown
– Implement internal leaky buckets to manage upstream traffic flow
24
8
LM CCN Section 2.2: Alternative Approaches to Routing
Closed-loop Congestion Control
! Regulate traffic based on state of network (feedback)
! TCP uses a congestion window to control congestion between sender and
receiver
– Senders may not transmit more than the minimum congestion window
advertised
! At start of session, window is set to a maximum segment size
! The congestion control algorithm adjusts the window by set amounts during the
transmission process, allowing adaption of window size based on traffic state
– If an acknowledgement is received, the segment is increased by one (rate is
increased each time – 2, 4, etc.)
– If not, congestion avoidance begins, increases limited to linear steps
– If congestion is still detected, window is set to half previous value
– If congestion continues, window is set to 1 segment and process restarts from the beginning
25
Summary
! Alternative approaches to routing – Flood routing
– Deflection routing
– Source routing
! Gradient approaches
! Congestion control and its impacts on routing
26
9