Transcript Intradomain routing protocols

Intradomain Routing Protocols
By
Behzad Akbari
These slides are based in part upon slides of Prof. Shivkumar (Rpi university) and Sanjay Rao
(Purdue university)
Outline

Intradomain routing protocols

Distance Vector


Link State


RIP, RIPv2, EIGRP
OSPF, IS-IS
Intradomain Traffic Engineering
RIP: Routing Information Protocol


Uses hop count as metric (max: 16 is infinity)
Tables (vectors) “advertised” to neighbors every 30 s.


Each advertisement: up to 25 entries
No advertisement for 180 sec: neighbor/link declared dead





routes via neighbor invalidated
new advertisements sent to neighbors (Triggered updates)
neighbors in turn send out new advertisements (if tables changed)
link failure info quickly propagates to entire net
poison reverse used to prevent ping-pong loops (infinite distance = 16
hops)

If Z routes through Y to get to X :


Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z)
60
will this completely solve count to infinity problem?
x
4
y
50
1
z
RIPv1 Problems (Continued)

Split horizon/poison reverse does not
guarantee to solve count-to-infinity
problem



Broadcasts consume non-router
resources


16 = infinity => RIP for small networks
only!
Slow convergence
It sends updates as broadcasts on
255.255.255.255
RIPv1 does not support subnet masks
(VLSMs)

It does not send subnet mask
information in its updates.

It does not support authentication
RIPv2


Why ? Installed base of RIP routers
Provides:





VLSM support
Authentication
Multicasting
Uses reserved fields in RIPv1 header.
First route entry replaced by authentication
info.
EIGRP (Interior Gateway Routing Protocol)




CISCO proprietary; successor of RIP (late 80s)
Several metrics (delay, bandwidth, reliability, load
etc)
Uses TCP to exchange routing updates
Loop-free routing via Distributed Updating Alg.
(DUAL) based on diffused computation





Freeze entry to particular destination
Diffuse a request for updates
Other nodes may freeze/propagate the diffusing
computation (tree formation)
Unfreeze when updates received.
Tradeoff: temporary un-reachability for some destinations
Link State vs. Distance Vector

Link State (LS) advantages:





More stable (aka fewer routing loops)
Faster convergence than distance vector
Easier to discover network topology,
troubleshoot network.
Can do better source-routing with link-state
Type & Quality-of-service routing (multiple route
tables) possible
Link State Protocols

Key: Create a network “map” at each node.

1. Node collects the state of its connected links and
forms a “Link State Packet” (LSP)
2. Flood LSP => reaches every other node in the
network and everyone now has a network map.
3. Given map, run Dijkstra’s shortest path algorithm
(SPF) => get paths to all destinations
4. Routing table = next-hops of these paths.
5. Hierarchical routing: organization of areas, and
filtered control plane information flooded.




Link State Issues


Reliable Flooding: sequence #s,
age
LSA types, Neighbor discovery
and maintenance (hello)


Efficiency in Broadcast LANs,
NBMA, Pt-Mpt subnets:
designated router (DR) concept
Areas and Hierarchy


Area types: Normal, Stub, NSSA:
filtering
External Routes (from other ASs),
interaction with inter-domain
routing.
Sending Link States by Flooding

X Wants to Send Information




C
B
X
A
D
C
B
(a)
D
(b)
Send on all links other than Z
Naïve Approach:

A
Sends on all outgoing links
When Node Y Receives
Information from Z

X
Floods indefinitely.
Prevent through sequence
numbers
X
A
C
B
(c)
D
X
A
C
B
(d)
D
OSPF Reliable Flooding

Transmit Link State
Advertisements



Originating Router
List of directly connected
neighbors of that node with the
cost of the link to each one
Sequence Number


Incremented each time
sending new link information
Link State Age

Packet expires when a
threshold is reached,
OSPF Flooding Operation

Node X Receives LSA from Node Y



With Sequence Number q
Looks for entry with same origin/link ID
Cases

No entry present


Entry present with sequence number p < q


Update entry, propagate to all neighbors other than Y
Entry present with sequence number p > q



Add entry, propagate to all neighbors other than Y
Send entry back to Y
To tell Y that it has out-of-date information
Entry present with sequence number p = q

Ignore it
Flooding Issues

When Should it be Performed


Periodically
When status of link changes


Detected by connected node
What Happens when Router Goes Down & Back Up

Sequence number reset to 0




Other routers may have entries with higher sequence numbers
Router will send out LSAs with number 0
Will get back LSAs with last valid sequence number p
Router sets sequence number to p+1 & resends
Flooding Issues (Cont.)

What if Sequence Number Wraps Around

Use circular comparison

a
OSPF v1
b
a
Max 0
a<b

b
Max 0
a<b
Force sequence number back to 0


OSPF v2
With 32-bit counter, doesn’t happen very often
OSPF Load Balancing
E
Table for B
Dst


Cst
3
C
1
Hop
A
3
A
B
0
B
C
2
F
D
3
D,F
D
E
4
A,F
F
F
1
F
1
F
1
6
1
A
3
3
B
Modification to Dijkstra’s algorithm
 Keep track of all links giving optimum cost d(v)
 Only get multiple routes when exactly same cost
Routing
 Alternate link used
 Tends to cause packets to arrive out of order
D
Type of Service (TOS) Metrics

Link Characteristic Vary in Multiple Dimensions





Latency
Throughput
Cost
Reliability
Example

Satellite link


Fiber optic link


High throughput, long latency
High throughput, low latency
Routing Requirements Vary


Typing at terminal: minimize latency for short packet
Sending video data: maximize throughput
Proposed OSPF Support for TOS

Support up to Five Different Routing Metrics

Normal service


Minimize cost





Don’t do anything extreme
For networks that charge for traffic
Maximize reliability
Maximize throughput
Minimize delay
Link Can Have Different LSA for each TOS


Expressed in units where lower value is better
Path cost either sum or maximum of link costs
Designated Router (DR)

Dijkstra algo view
Encoding of LSAs,
Flooding/DB sync model
New Question: Who creates the network-LSA?
Designated Router (…)

One router elected as a designated router (DR) on
LAN



Each router maintains flooding adjacency with the DR, I.e.,
sends acks of LSAs to DR
DR informs each router of other routers on LAN
DR generates the network-LSA on subnet’s behalf after
synchronizing with all routers
Primary/Backup: DR, BDR (…)



Backup DR (BDR) also syncs with all routers, and takes
over if DR dies (typically 5 s wait)
Total: 2N – 1 adjacencies
DR election:



First router on net = DR, second = BDR
RouterPriority: [0, 127] indicated in Hello packet=> highest
priority router becomes DR
If network is partitioned and healed, the two DRs are reduced
to one by looking at RouterPriority
Hierarchical Routing
Why Hierarchy?

Information hiding (filtered) => computation,
bandwidth, storage saved => efficiency => scalability


But filtering in control plane, not data plane
Address abstraction vs. Topology Abstraction

Multiple paths possible between two adj. areas

Area


Configured area ID
A set of address prefixes



Do not have to be contiguous
So a prefix can be in only one area
A set of router IDs

Router functions may be interior, inter-area, or
external
Hierarchical OSPF




Two-level hierarchy: local area, backbone.
 Link-state advertisements only in area
 each nodes has detailed area topology; only know direction
(shortest path) to nets in other areas.
 Two-level restriction avoids count-to-infinity issues in backbone
routing.
Area border routers (ABR): “summarize” distances to nets in
own area, advertise to other Area Border routers.
Backbone routers: uses a DV-style routing between backbone
routers
Boundary routers (AS-BRs): connect to other ASs (generate
“external” records)
Hierarchical OSPF
Sample Area Configuration
10.2.0.0/24
IS-IS Overview




The Intermediate Systems to Intermediate System
Routing Protocol (IS-IS) was originally designed to route the
ISO Connectionless Network Protocol (CLNP) . (ISO10589 or
RFC 1142)
Adapted for routing IP in addition to CLNP (RFC1195) as
Integrated or Dual IS-IS (1990)
IS-IS is a Link State Protocol similar to the Open Shortest Path
First (OSPF). OSPF supports only IP
IS-IS competed neck-to-neck with OSPF.
 OSPF deployed in large enterprise networks
 IS-IS deployed in several large ISPs
IS-IS Terminology
Intermediate system (IS) - Router
Designated Intermediate System (DIS) - Designated Router
Pseudonode - Broadcast link emulated as virtual node by DIS
End System (ES) - Network Host or workstation
Network Service Access Point (NSAP) - Network Layer Address
Subnetwork Point of attachment (SNPA) - Datalink interface
Packet data Unit (PDU) - Analogous to IP Packet
Link State PDU (LSP) - Routing information packet
Level 1 and Level 2 – Area 0 and lower areas
Functional Comparison

Protocols are recognizably similar in function
and mechanism (common heritage)






Link state algorithms
Two level hierarchies
Designated Router on LANs
Widely deployed (ISPs vs. enterprises)
Multiple interoperable implementations
OSPF more “optimized” by design (and
therefore significantly more complex)
Sample comparison points

Encapsulation



OSPF runs on top of IP=> Relies on IP fragmentation for
large LSAs
IS-IS runs directly over L2 (next to IP) => fragmentation
done by IS-IS
Media support



Both protocols support LANs and point-to-point links in
similar ways
IS-IS supports NBMA in a manner similar to OSPF pt-mpt
model: as a set of point-to-point links
OSPF NBMA mode is configuration-heavy and risky (all
routers must be able to reach DR; bad news if VC fails)
Packet Encoding

OSPF is “efficiently” encoded




Positional fields, 32-bit alignment
Only LSAs are extensible (not Hellos, etc.)
Unrecognized types not flooded. Opaque-LSAs recently
introduced.
IS-IS is mostly Type-Length-Value (TLV) encoded




No particular alignment
Extensible from the start (unknown types ignored but still
flooded)
All packet types are extensible
Nested TLVs provide structure for more granular extension
IS-IS LS Database: Generic Packet Format
No. of Octets
R
Intra-domain Routing Protocol Discriminator
1
Length Indicator
1
Version/Protocol ID Extension
1
ID Length
1
R
R
PDU Type
1
Version
1
Reserved
1
Maximum Area Addresses
Packet-Specific Header Fields
TLV Fields
1
Traffic Engineering: Motivation


TE: “…that aspect of Internet network engineering
dealing with the issue of performance evaluation
and performance optimization of operational IP
networks …’’
90’s approach to TE was by changing link weights in
IGP (OSPF, IS-IS) or EGP (BGP-4)


Performance limited by the shortest/policy path nature
Assumptions: Quasi-static traffic, knowledge of demand
matrix
111
BB
14
1
A
A
11
CC
22
222
D
D
E EE
Links AB and BD are overloaded
Links
Can AC
not and
do this
CD are
withoverloaded
OSPF
Traffic Engineering

What is traffic engineering?


Control and optimization of routing, to steer traffic through the
network in the most effective way
Two fundamental approaches to adaptation

Adaptive routing protocols



Adaptive network-management system



Distribute traffic and performance measurements
Compute paths based on load, and requirements
Collect measurements of traffic and topology
Optimize the setting of the “static” parameters
Big debates still today about the right answer
QoS routing = optimization of user QoS objectives
TE = optimization of user AND network QoS objectives
Outline: Three Alternatives

Load-sensitive routing at packet level




Load-sensitive routing at circuit (or aggregate) level




Routers receive feedback on load and delay
Routers re-compute their forwarding tables
Fundamental problems with oscillation
Routers receive feedback on load and delay
Router compute a path for the next circuit
Less oscillation, as long as circuits last for a while
Traffic engineering as a management problem



Routers compute paths based on “static” values
Network management system sets the parameters to influence
the mapping of traffic to paths
Acting on network-wide view of traffic and topology