-------------------------------------------------
IP ROUTING
originally from Dr. Sidnie Feit.
--------------------------------------------------
Contents
--------------------------------------------------
Part 1. IP Routing Protocols
Part 2. RIP & RIP ver 2
Part 3. IGRP & EIGRP
Part 4. OSPF
Part 5. OSI, EGP, BGP
--------------------------------------------------
OSI ROUTING
(Part 5, OSI Routing)
OSI uses the term Intermediate System rather than router or
gateway. The OSI routing protocol, IS-IS originally was
defined to support OSI Routers but then was extended to IP.
Like OSPF, IS-IS, originally was defined to support OSI
Router, but then was extended to IP.
IS-IS has two types of of routers: level 1 for local routing and
level 2 for routing to destination outside the area. (Level
2 routers could be viewed as analogous to routers in OSPF
backbone.) A level 1 intermediate system, forwards a traffic
bound for destination outside its area to its nearest level
2 router. Traffic is then routed to another level 2 router
that is connected to the destination area.
Many of the mechanism used in OSPF were based on similar
(but not identical) mechanism in IS-IS, for example, the use
of link state advertisements, flooding, and sequence
numbers.
Some IS-IS proponents believe that it is better to route IP
and OSI traffic using this single integrated protocol
instead of using separate router-to-router protocols.
EXTERIOR GATEWAY PROTOCOLS
Recall by that definition, an interior Gateway Protocol is
used within an Autonomous System. Different Autonomous
System are free to choose the protocol and metric that suits
them best. But how can we make a reasonable routing
decission about traffic that travels between two different
Autonomous Systems?
For many years, the simple Exterior Gateway Protocol (EGP)
was used on the Internet to enable an autonomous system to
route information to external. networks. EGP is widely
available. A very simple design is used. EGP Routers in
neighboring Autonomous Systems tell one another what network
they can reach.
EGP was designed in early 1980s when the internet was still
fairly small and had a simple topology consisting of a
backbone and a set of networks directly connected to the
backbone. As the internet evolved to its present, mesh like
topology, EGP began to pass reachability information trough
a certain trough a certain chain of Autonomous Systems.
EGP does not disclose the routes that are followed by
datagrams that are travelling to external locations. It even
hides which Autonomous Systems are traversed along the way.
EGP's simple reachability has proved to be inadequate in the
modern environment. Use of EGP is diminishing rapidly.
The protocol will br describe briefly here.
EGP Model
An EGP router is configured with the IP address of one or
more exterior neighbors are connected to a common
multiaccess network or are joined from point-to-point link.
EGP enables a router to find out which network can be
reached trough its exterior neighbors. EGP has the following
ingridients:
* Neighbor Acquisition
A router sends a Neighbor Acquisition Request. The
reciever sends back both a Neighbor Acquisition Response
and a Neighbor Acquisition Request message.
* Neighbor Release
To terminate being a neighbor, a router sends a Neighbor
Cease message. The receiver sends back a neighbor cease
message.
* Neighbor Reachability
The relationship between acquired neigbors is kept alive
by periodically exchanges of Hello and I Heard You
messages.
* Network Reachability
A router sends a poll to exterior neighbor, requesting
information on reachable networks. The neighbor responds
with a network Reachability message.
The content of Network Rechability messages needs a litle
more explanation. If the exterior neighbors are connected by
a point-to-point link, the messages will identify networks
that can be reached via the sender, A hop count to each
destination is also provided. See figure bellow; it
illustrates this configuration -- Router A reports reachable
destination to router X.
______ ____
( ) ( )
__( __ )__ __( )
__| |__| |__|A |__|X | )
|__| |__| |__| |__| )
( ) ( )
(______) (____)
AS150 AS 321
As shown below, sometimes, several router in diferent
Autonomous System share a common multiaccess network. In
this case, EGP router A will inform EGP router X of the
networks reaced via A, B and C repectively.
___ ___ ___
| | | | |EGP| networks reached via A
| C | | B | | A | networks reached via B
|___| |___| |___|..networks reached via C
| | | :
||_|_____|_____|___:___________________||
|| _|v_ _|_ _|_ ||
|EGP | | | | |
| X | | Y | | Z |
|____| |___| |___|
Efficient exchanges of EGP information
Router X and A are direct neighbours, but the router B and C
are indirect neighbors of Router X.
If router A were to crash, router X could try to acquire one
of its indirect neighbors, B or C as a direct EGP neighbors.
EGP messages are carried directly inside IP datagrams whose
protocol field is set to 8.
BGP
The Border Gateway Protocol (BGP) is in wide use on the
Internet. The current version is BGP-4.
In today's Internet, there are many Service Providers, and
they're joined together by a mesh interconnections. Traffic
often transmits the networks of several different service
providers on way to its destination. For example, the route
bellow starts within JVNC and then traverses MCI, SPRINT and
NYSERNET routers before reaching its destination.
> traceroute nyu.edu
traceroute to CMCL2.NYU.EDU (128.122.128.2), 30 hops max, 40 byte packets
1. nomad-gateway.jvnc.net (128.122.128.2) 3ms 3ms 2ms
2. liberty-gateway.jvnc.net (128.121.50.50) 49ms 10ms 21ms
3. border2.hssi2-0.NewYork.mci.net (204.70.45.9) 13ms 12ms 19ms
4. sprint-nap.NewYork.mci.net (204.70.45.6) 33ms 25ms 19ms
5. s1-pen-2-F4/0.sprintlink.net (192.157.69.9) 33ms 25ms 19ms
6. ny-nyc-2-H1/0-T3.nysernet.net (144.288.62.2) 24ms 21ms 21ms
7. ny-nyc-3-F0/0.nysernet.net (169.130.10.3) 31ms 23ms 20ms
8. ny-nyu-1-h1/0.nysernet.net (169.130.13.18) 21ms 34ms 19ms
9. NYU.EDU (128.122.128.2) 19ms 22ms 21ms
The purpose of BGP is to support routing accross a chain of
Autonomous System while preventing loops from forming. To do
this, BGP systems exchange information that describes paths
to the networks that they can reach. Unilke EGP, BGP reveals
the entire of chain of autonomous system that must be
traversed to reach a network.
In addition to reporting paths to indovidual networks, BGP
can identify aggregate sets of networks using CIDR previxes.
BGP Route Aggregation
An Internet route consists of a destination and instructions
on how to get there. There has been explosive growth in the
number of routes because of the rapid increase and in the
number of networks.
An interim solution has gotten routing under control. The
current method of route reduction is to assign a block of
address with a common prefix to a Service Provider. The
provider assigns subblocks to its customer networks.
The size of the service provider prefix is identified by a
number that identicates the length in bits of the IP prefix.
Traffic can be sent from external ASs to the provider and
its customer by means of a single route that corresponds to
the prefix. The provider can then use longer prefixes to
forward a traffic to each of its customer's ASs.
This is simple for incoming traffic, but we have to reverse
the scenario to see what a service provider must do on an
ongoing basis with outgoing advertisemets. Client ASs will
inform their service Providers of routes to their internal
networks. The service provider will aggregate routes with a
common prefix into single routing entries before advertising
them to the outside worlds.
BGP Mechanisms
BGP sytem open a TCP connection to well-known port 179 at a
BGP Neighbor. Each opening messages identifies sender's
autonomous system and BGP Identifier and may include
authentication information.
Once the connetion is open, the peers exchange their routes
information. The connection remains open, and updates are
sent as needed. To make sure that they are still in contact,
the systems periodically exchanges Keep-Alive messages
usually every 30 seconds.
A service provider network carries traffic between
Autonomous System and is very likely to include multiple
systems that speak BGP. These systems will communicate with
one another via internal BGP connection. An external BGP
connection is used to communicate to a BGP peer system in a
different Autonomous System (This connection referred to as
links, even though they are TCP connection that might
possibly pass trough intermediate routers).
One big difference between BGP and other routing protocol is
that the systems that exchange the routing protocol can be
hosts -- they do not have to be routers. One possible
configuration is to give a host a job of talking to all
external BGP systems in neighbouring Autonomous Systems. The
host could be used as a route server, passing information to
boundary routers in its own AS.
Contents of BGP Update Message
A BGP update message can containat most of one feasible
route. But it also can include a list of one or more
withdrawn routes, which are routes that should not longer in
be used.
A route description is made up of a sequence of path
attritbutes which include:
* Origin of Path Information:
One of source was the IGP of original AS. Source was BGP.
* AS Path:
Path along this update was carried
* Next Hop
IP Address of boundary router that should be used as the
next hop to the destination. This might be a router
belonging to the local Autonomous System or an external
router that is directly connected to both the sender and
the recipient for this update
* Multi-exit Discriminator
If I have multiple exit points that connect me to my
neighbour's Autonomous System, my neighbor can assign
numbers indicates a better route.
* Local Preference
Purely Internal Information, used as sending BGP updates
to system in local AS. Where there are multiple BGP
routers to a destination. A bigger number is preferred.
* Atomic Aggregate
Indicates that an Autonomoous System has agregated several
destination into a single route entry.
* Aggregator
The IP address and AS number of the last system that
aggregated several destination into a single route entry.
* A list of prefixes for networks that can be rached via
this route.
* Reachable Nets
A list of prefixes for networks that can be rached via
this route.
Figure below illustrates the diffrence between the
Multi-exit Descriminator and Local Preference. System in AS
117 want to reach network N in AS 433. AS 654 has two routes
to that destination, and AS 654 announces that the one
trough router E is better. However AS 117 has an internally
assigned local preferrence for the route to Network N via
119.
.......
: :
: AS 433 :
: Network :
: N :_______ .......
/:.......: \____: :
........ / : AS 119 :
: |: : :
: AS _|_: __ ... __ / .....:
: 654___| E |__________|B | |A |
: __/ |___| |__|_ |__|
: | | ___ : _________:__ \__/ :
: |__|\_| D |_/ |C |_| | :
:......|___| |__| |__| :
: AS 117 :
:.......:
Illustration, Preferred route
Using Aggregation
The purpose of route agregation is to Avoid including a lot
of unecessary information in remote routing tables. A
service provider can aggregate the routes reported by its
client Autonomous Systems.
_________
( AS 650 )
( 193.20.0 )
( s/d )_____
( 193.20.31 ) \
(_________) \
\
_________ \ ___
( AS 651 ) \ ( )
( 193.20.32 ) \ +----------+ ( )
( s/d )___________\___| AS 117 |_________( )
( 193.20.63 ) / |193.20.0.0| ( )
(_________) / +----------+ (___)
/ Atomic Agregate
_________ /
( AS 652 ) /
( 193.20.64 ) /
( s/d )_____/
( 193.20.127)
(_________)
Illustration of aggregating routes
As shown above, BGP routers in AS 650, 651 and 652 can
report their routes, but the provider in 117 aggregates them
into one entry. The fact that this has been done by the
Atomic Aggreagate attribute.
Note an AS 652 might be a local Service provider and might
already be aggregating its customer's route, so it is
possible that more of the route is hidden from remote
systems. Each of the aggregating Autonomous system routers
will forward trafic to the custmers destinations based on
their own routing tables.
Withdrawing BGP Routes
A route is tereminated when:
- It is on list of withdrawn routes sent too an update.
- An update provides a replacement route
- BGP system closes its connection. All rouutes learned via
that system are avoided.
(
geocities.com/gandautama)