Interior Routing(within one AS)
Current Routing Algorithms
(a) "Distance Vector Routing"--Each router shares its knowledge(distance
to destination networks) about the entire network(in an AS) with its neighbors-Example:
RIPv2
***EVERYTHING to NEIGHBORS ONLY***
(b) "Link State Routing"-Each router shares its knowledge about its
links to the neighbors(link state) with every routers in the area.-Example:
OSPF
***LINK STATES to EVERYBODY***(b) OSPF(Open Shortest Path
First)
(a) this was covered before
(b) Link State Routing--Example: OSPF(Open Shortest Path First)
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/ospf.htm
-OSPF is an IGP(Interior Gateway Protocol) developed by IETF-- http://www.csl.sony.co.jp/cgi-bin/hyperrfc?2328
-Currently Version 2---also has a version for IPv6
-Open(spec. on public domain)
-OSPF has features not in RIP and is suitable for a large network
-Based on Dijkstra's algorithm
-OSPF is an intra-AS protocol
-Autonomous System(A group of networks and routers under the authority of a
single administration) is divided into Areas(A collection of networks,
hosts, and routers all contained within an autonomous system). An AS is made
up of several Areas.
-3 kinds of routers in OSPF--(1) Intra-Area routers (2) Area Border routers
(3) AS Boundary routers
-Routers inside an Area flood the Area with routing information--information
is exchanged to all routers in an Area by Flooding(actually multicasting)--all
routers in an area maintain the same topology database
-This area concept limits the size of the topology database that must be held
by all routers in the area
-At the border of an area, special routers called Area border routers collect
and summarize the information about each area it is attached to
and send the summary to other areas.
-One of the areas into which all areas have a connection is called Backbone(all
OSPF networks must contain at least one area, the Backbone) which
is assigned an area identifier of 0.0.0.0(meaning Area 0--not an IP address)
-Routers inside a backbone are called Backbone routers--Backbone routers operate
identically to other Intra-Area routers and maintain full topology
databases for the backbone area
-Autonomous Systems are connected via AS Boundary Routers--they exchange reachability
information with routers in other ASs using an Exterior Gateway
Protocol.
-OSPF is "Link State Routing"
-OSPF protocol allows the administrator to assign a cost(metric) to each route:
OSPF Cost--from http://www.cisco.com/warp/public/104/2.html#1.0
"The cost (also called metric) of an interface in OSPF is an indication
of the overhead required to send packets across a certain interface. The cost
of an interface is inversely proportional to the bandwidth of that interface.
A higher bandwidth indicates a lower cost. There is more overhead (higher cost)
and time delays involved in crossing a 56k serial line than crossing a 10M ethernet
line. The formula used to calculate the cost is:
cost= 10000 0000/bandwith in bps
For example, it will cost 10 EXP8/10 EXP7 = 10 to cross a 10M Ethernet line
and will cost 10 EXP8/1544000 = 64 to cross a T1 line.
By default, the cost of an interface is calculated based on the bandwidth; you
can force the cost of an interface by using the ip ospf cost <value> interface
sub-command."
-The cost can also be based on a type of service(minimum delay, maximum throughput,
…)---OSPF can calculate a separate route for each IP type-of-service
but this feature was recently dropped
-OSPF protocol defines a number of stages which must be executed by individual
routers:
-Discovering neighbors--"Hello"
packet is sent, then the neighbors will reply and a link is established between
them
-Establishing Adjacencies(=called
Database Exchange)--A router establishes adjacencies by sending "Database
description packet
-Electing the "Designated
router"--When more than 1 routers are connected to the same network one
of them is elected
as "Designated"
-Link State Advertisements--All
Routers exchange the state of each link to every routers(by sending a multicast
message--224.0.0.5=means
"AllSPFRouters") in the Area every 30 minutes--called LSA(Link State
Advertisement)
-Calculating routing tables--Each
router in an area builds up a topology database(from validated link state advertisements)
and uses them to calculate the network connection map for the area. From the
map the router can
determine the best route for each destination and insert the link into its routing
table. Dijkstra's algorithm is used
to calculate a shortest path.
-OSPF packet types:
-A router also sends a short greeting packet to a neighbor periodically, if
the neighbor does not respond then a malfunction is assumed and
alerts the rest of network
-Area border routers know the routes in both Areas and relay(flood) the information
from one Area to other Area
Summary:OSPF is important because it has many features that are not found in
other interior gateway protocols such as RIP.
OSPF is the preferred protocol for large networks.
-Allows site partitioning using Areas
-More secure using Authentication between routers
-Link State is more accurate than Hop Count
-OSPF supports subnetting
-Supports "host-specific routes" as
well as "network-specific routes"
-Reduces table maintenance overhead by implementing
a "designated router"
-Allows "virtual links"
-Will import RIP and EGP routes into its database
Other Interior Gateway Protocols(other than RIP & OSPF)
IGRP(Interior Gateway Routing Protocol)
=Improved version of RIP from CISCO
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/igrp.htm
The key differences between RIP and IGRP are in the
-Metrics
-Poison Algorithm
-Use of Default Gateway
IGRP uses a combination (vector) of metrics. Internetwork delay, bandwidth,
reliability, and load are all factored into the routing decision. Network administrators
can set the weighting factors for each of these metrics. IGRP uses either the
administrator-set or the default weightings to automatically calculate optimal
routes.
IGRP provides a number of features that are designed to enhance its stability.
These include hold-downs, split horizons, and poison-reverse updates.
EIGRP(Enhanced Interior Gateway Routing Protocol)
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/en_igrp.htm
The Enhanced Interior Gateway Routing Protocol (EIGRP) represents an evolution
from its predecessor IGRP ("Interior Gateway Routing Protocol)." This
evolution resulted from changes in networking and the demands of diverse, large-scale
internetworks. Enhanced IGRP integrates the capabilities of link-state protocols
into distance-vector protocols. Enhanced IGRP provides compatibility and seamless
interoperation with IGRP routers.
RoutingProtocols can be divided into (a) Interior Gateway Protocols(between
ISs within an AS) (b) Exterior Gateway Protocols(between routers on different
ASs--between border gateways)
RIP, OSPF, IGRP, EIGRP are IGPs
Exterior Gateway Protocols
A protocol used for exchange of routing information between exterior gateways.--There
are two protocols--(a) EGP(Exterior Gateway Protocol) (b) BGP(Border Gateway
Protocol)
(a) EGP(Exterior Gateway Protocol)
-Inter-AS(Autonomous System) protocol used in Internet---old protocol
-RFC 904(1984)
-Replaced by BGP(Border Gateway Protcol) & CISCO's IDRP(Inter-Domain Routing
Protocol)
(b) BGP-4(Border Gateway Protocol version 4)--RFC 1771
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/bgp.htm
http://www.csl.sony.co.jp/cgi-bin/hyperrfc?rfc1771.txt
-An Inter-Autonomous System Routing Protocol
-Based on a routing method called "path vector routing"--this is used
because both the "Distance vector routing" & "Link State
routing" are not good candidate for Inter-AS routing
-Distance vector is not a good candidate because there are occasions in which
the route with the smallest hop count is not the preferred route--hop count
is not accurate and also you may not want the particular route due to security
reasons, long delays(ex. satellite links), etc. Also Distance vector routing
has the problem of instability
-Link state routing is not a good candidate because the way LSAs(Link State
Advertisements) are sent--they are flooded--to the entire Internet routers?
BGP Speakers and AS Relationship diagram
BGP speaker=A system running BGP
BGP neighbors=A pair of BGP speakers exchanging inter-AS routing information.
From: http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/bgp.htm
********************************************************************
Figure 35-1 illustrates core routers using BGP to route traffic between autonomous
systems.
Figure 35-1: Core routers can use BGP to route traffic between autonomous systems.
BGP is specified in several Request For Comments (RFCs):
RFC 1771 ---Describes BGP4, the current version of BGP
RFC 1654---Describes the first BGP4 specification
RFC 1105, RFC 1163, and RFC 1267---Describes versions of BGP prior to BGP4
BGP Operation
BGP performs three types of routing: interautonomous system routing, intra-autonomous
system routing, and pass-through autonomous system routing.
Interautonomous system routing occurs between two or more BGP routers in different
autonomous systems. Peer routers in these systems use BGP to maintain a consistent
view of the internetwork topology. BGP neighbors communicating between autonomous
systems must reside on the same physical network. The Internet serves as an
example of an entity that uses this type of routing because it is comprised
of autonomous systems or administrative domains. Many of these domains represent
the various institutions, corporations, and entities that make up the Internet.
BGP is frequently used to provide path determination to provide optimal routing
within the Internet.
Intra-autonomous system routing occurs between two or more BGP routers located
within the same autonomous system. Peer routers within the same autonomous system
use BGP to maintain a consistent view of the system topology. BGP also is used
to determine which router will serve as the connection point for specific external
autonomous systems. Once again, the Internet provides an example of interautonomous
system routing. An organization, such as a university, could make use of BGP
to provide optimal routing within its own administrative domain or autonomous
system. The BGP protocol can provide both inter- and intra-autonomous system
routing services.
Pass-through autonomous system routing occurs between two or more BGP peer
routers that exchange traffic across an autonomous system that does not run
BGP. In a pass-through autonomous system environment, the BGP traffic did not
originate within the autonomous system in question and is not destined for a
node in the autonomous system. BGP must interact with whatever intra-autonomous
system routing protocol is being used to successfully transport BGP traffic
through that autonomous system. Figure 35-2 illustrates a pass-through autonomous
system environment:
Figure 35-2: In pass-through autonomous system routing, BGP pairs with another
intra-autonomous system-routing protocol.
BGP Routing
As with any routing protocol, BGP maintains routing tables, transmits routing
updates, and bases routing decisions on routing metrics. The primary function
of a BGP system is to exchange network-reachability information, including information
about the list of autonomous system paths, with other BGP systems. This information
can be used to construct a graph of autonomous system connectivity from which
routing loops can be pruned and with which autonomous system-level policy decisions
can be enforced.
Each BGP router maintains a routing table that lists all feasible paths to
a particular network. The router does not refresh the routing table, however.
Instead, routing information received from peer routers is retained until an
incremental update is received.
Network Next Router Path
----------- ------------ ----------------------
N01 R01
AS14,
AS23, AS67
N02 R05
AS22,
AS67, AS05, AS89
N03 R06
AS67,
AS89, AS09, AS34
N04 R12
AS62,
AS02, AS09
For the assignment of AS numbers, read RFC 1930(Guidelines for creation, selection,
and registration
of an Autonomous System (AS))
BGP devices exchange routing information upon initial data exchange and after
incremental updates. When a router first connects to the network, BGP routers
exchange their entire BGP routing tables. Similarly, when the routing table
changes, routers send the portion of their routing table that has changed. BGP
routers do not send regularly scheduled routing updates, and BGP routing updates
advertise only the optimal path to a network.
BGP uses a single routing metric to determine the best path to a given network.
This metric consists of an arbitrary unit number that specifies the degree of
preference of a particular link. The BGP metric typically is assigned to each
link by the network administrator. The value assigned to a link can be based
on any number of criteria, including the number of autonomous systems through
which the path passes, stability, speed, delay, or cost.
******************************************************************
Example of a router:
CISCO AGS+ supports Routing Protocols;
- IGRP(IP, OSI)
- RIP (IP)
- OSPF(IP)
- BGP(IP)
- EGP(IP)
- ES-IS(OSI)
- IS-IS(OSI)