Transcript 2009125182350Y5

Path Vector Routing
NETE0514
Presented by
Dr.Apichan Kanjanavapastit
Interconnected ASes
3c
3a
3b
AS3
1a
2a
1c
1d
1b
Intra-AS
Routing
algorithm
2c
AS2
AS1
Inter-AS
Routing
algorithm
Forwarding
table
2b
• forwarding table
configured by both
intra- and inter-AS
routing algorithm
– intra-AS sets entries for
internal dests
– inter-AS & Intra-As sets
entries for external dests
Inter-AS tasks
AS1 must:
1. learn which dests
reachable through
AS2, which through
AS3
2. propagate this
reachability info to all
routers in AS1
Job of inter-AS routing!
• suppose router in AS1
receives datagram dest
outside of AS1
– router should forward
packet to gateway
router, but which
one?
3c
3b
3a
AS3
1a
2a
1c
1d
1b
2c
AS2
AS1
2b
Example: Setting forwarding table in router
1d
• suppose AS1 learns (via inter-AS protocol) that subnet x
reachable via AS3 (gateway 1c) but not via AS2.
• inter-AS protocol propagates reachability info to all internal
routers.
• router 1d determines from intra-AS routing info that its
interface I is on the least cost path to 1c.
– installs forwarding table entry (x,I)
x
3c
3a
3b
AS3
1a
2a
1c
1d
1b AS1
2c
2b
AS2
Example: Choosing among multiple ASes
• now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.
• to configure forwarding table, router 1d must determine
towards which gateway it should forward packets for
dest x.
– this is also job of inter-AS routing protocol!
x
3c
3a
3b
AS3
1a
2a
1c
1d
1b
2c
AS2
AS1
2b
Example: Choosing among multiple ASes
• now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.
• to configure forwarding table, router 1d must determine
towards which gateway it should forward packets for
dest x.
– this is also job of inter-AS routing protocol!
• hot potato routing: send packet towards closest of two
routers.
Learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways
Use routing info
from intra-AS
protocol to determine
costs of least-cost
paths to each
of the gateways
Hot potato routing:
Choose the gateway
that has the
smallest least cost
Determine from
forwarding table the
interface I that leads
to least-cost gateway.
Enter (x,I) in
forwarding table
Why different Intra- and Inter-AS routing ?
Policy:
• Inter-AS: admin wants control over how its traffic routed,
who routes through its net.
• Intra-AS: single admin, so no policy decisions needed
Scale:
• hierarchical routing saves table size, reduced update
traffic
Performance:
• Intra-AS: can focus on performance
• Inter-AS: policy may dominate over performance
Why path vector routing is needed?
• Distance vector routing is subject to
instability if there is more than a few hops
in the domain of operation
• Link state routing needs a huge amount of
resources to calculate routing tables. It
also creates heavy traffic because of
flooding
• There is a need for a third protocol which
we call path vector routing
Path Vector Routing
• The principle of path vector routing is similar to
distance vector routing
• In path vector routing, we assume that there is
one node (in practice there can be more) in each
autonomous system that acts on behalf of the
entire autonomous system. Let us call it the
speaker node
• The speaker node in an AS creates a routing
table and advertises it to speaker nodes in the
neighboring Ass
• A speaker node advertises the path, not the
metric of the nodes, in its AS or other ASs
Initialization
• At the beginning, each speaker node can know
only the reachability of nodes inside its
autonomous system
Sharing
• A speaker in an AS shares its table with
immediate neighbors
Updating
• When a speaker node receives information from a
neighbor, it updates its own table by adding the nodes
that are not in its routing table and adding its own AS
and the AS that sent the table
• After a while each speaker has a table and knows how to
reach each node in other ASs
Loop Prevention
• The instability of distance vector routing
and the creation of loops can be avoided
in path vector routing
• When a router receives a message, it
checks to see if its AS is in the path list to
the destination
• If it is, looping is involved and the
message is ignored
Aggregation
• The path vector routing protocols normally support CIDR
notation and the aggregation of addresses
• Note that a range may also include a block that may not
be in the corresponding AS
• However, if this network exists in some other Ass, it
eventually becomes part of the routing table due to the
longest prefix principle
Policy Routing
• Policy routing can be easily implemented
through path vector routing
• When a router receives a message, it can check
the path
• If one of the AS listed in the path is against its
policy, it can ignore that path and that
destination
• It does not update its routing table with this path,
and it does not send this message to its
neighbors
Optimum Path
• We definitely cannot include metrics in a route because
each AS that is included in the path may use a different
criteria for the metric
• One system may use, internally, RIP, which defines hop
count as the metric; another may use OSPF with
minimum delay defined as the metric
• The optimum path is the path that fits the organization
• In the example figure, each AS may have more than one
path to a destination. For the table, we chose the one
that had the smaller number of Ass, but this is not always
the case
• Other criteria such as security and safety, and reliability
can also be applied
Internet inter-AS routing: BGP
• BGP (Border Gateway Protocol): the de facto
standard
• BGP provides each AS a means to:
1. Obtain subnet reachability information from
neighboring ASs.
2. Propagate reachability information to all AS-internal
routers.
3. Determine “good” routes to subnets based on
reachability information and policy.
• allows subnet to advertise its existence to rest of
Internet: “I am here”
Types of Autonomous Systems
• Stub AS. A stub AS has only one connection to
another AS
• Multihomed AS. A multihomed AS has more
than one connection to other ASs, but it is still
only a source or sink for data traffic. It can
send/receive data traffic from more than one AS,
but there is no transient traffic
• Transit AS. A transit AS is a multihomed AS that
also allows transient traffic
BGP Sessions
• The exchange of routing information between 2
routers using BGP takes place in a session
• A session is a connection that is established
between 2 BGP routers only for the sake of
exchange routing information
• The create a reliable environment, BGP uses the
service of TCP. In other words, a session at the
BGP level, as an application program, is a
connection at the TCP level
BGP Sessions (cont.)
• When a TCP connection is created for BGP, it
can last for a long time, until something unusual
happens.
• For this reason, BGP sessions are sometimes
referred to as semi-permanent connections
Note:
BGP uses the services of TCP
on port 179.
External and Internal BGP
• BGP can have 2 types of session: external BGP (E-BGP)
and internal BGP (I-BGP) sessions
• The E-BGP session is used to exchange information
between 2 speaker nodes belonging to 2 different Ass
• The I-BGP session is used to exchange routing
information between 2 routers inside an AS
Distributing reachability info
• using eBGP session between 3a and 1c, AS3 sends
prefix reachability info to AS1.
– 1c can then use iBGP do distribute new prefix info
to all routers in AS1
– 1b can then re-advertise new reachability info to
AS2 over 1b-to-2a eBGP session
• when router learns of new prefix, creates entry for
prefix in its forwarding table.
eBGP session
3c
3a
3b
AS3
1a
AS1
iBGP session
2a
1c
1d
1b
2c
AS2
2b
Path Attributes
• The path presents in a list of ASs in the previous
example, in fact, it is a list of attributes
• Each attribute gives some information about the
path. The list of attributes helps the receiving
router make a better decision when applying its
policy
• Attributes are divided into 2 broad categories:
well-known and optional. A well known attribute
is one that every BGP router must recognize. An
optional attributes is one that needs not be
recognized by every router
Path Attributes (cont.)
• Well-known attributes are themselves divided into 2
categories: mandatory and discretionary
• A well-known mandatory attribute is one that must
appear in the description of a route
• A well-known discretionary attribute is one that must be
recognized by each router, but is not required to be
included in every update message
• Two important attributes:
– AS-PATH: contains ASs through which prefix advertisement has
passed
– NEXT-HOP: is the router interface that begins the AS-PATH
Why AS-PATH is needed?
• AS1 and AS2 are connected by 2 peering links.
A router in AS1 could learn about 2 different
routes to the same prefix x. These 2 routes
could have the same AS-PATH to x, but could
have different NEXT-HOP values corresponding
to the different peering link. Using the AS-PATH
values and the intra-AS routing algorithm, the
router can determine the cost of the path to each
peering link, and then apply hot potato routing to
determine the appropriate interface
BGP route selection
• router may learn about more than 1 route
to some prefix. Router must select route.
• elimination rules:
1. local preference value attribute: policy
decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
BGP routing policy
legend:
B
W
X
A
provider
network
customer
network:
C
Y
• A,B,C are provider networks
• X,W,Y are customer (of provider networks)
• X is dual-homed: attached to two networks
– X does not want to route from B via X to C
– .. so X will not advertise to B a route to C
BGP routing policy (2)
legend:
B
W
X
A
provider
network
customer
network:
C
Y
• A advertises path AW to B
• B advertises path BAW to X
• Should B advertise path BAW to C?
– No way! B gets no “revenue” for routing CBAW since
neither W nor C are B’s customers
– B wants to force C to route to w via A
– B wants to route only to/from its customers!
Types of Packets
• BGP uses 4 different type of messages: open, update,
keepalive, and notification
– OPEN: opens TCP connection to peer and authenticates sender
– UPDATE: advertises new path (or withdraws old)
– KEEPALIVE keeps connection alive in absence of UPDATES;
also ACKs OPEN request
– NOTIFICATION: reports errors in previous msg; also used to
close connection
Packet Format
• All BGP packets share the same common header. The
fields of this header are as follows:
– Marker. The 16-byte marker field is reserved for authentication
– Length. The 2-byte field defines the length of the total message
including the header
– Type. This 1-byte field defines the type of the packet
Open Message
• To create a neighborhood relationship, a
router running BGP opens a TCP
connection with a neighbor and sends an
open message
• If the neighbor accepts the neighborhood
relationship, it responds with a keepalive
message, which means that a relationship
has been established between the 2
routers
Open Message (cont.)
• My autonomous system. This defines the AS number
• Hold time. This defines the maximum number of seconds
that can elapse until one of the parties receives a
keepalive or update message from the other. If a router
does not receive one of these message during the hold
time period, it considers the other party dead
• BGP identifiers. This defines the IP address of the router
that sends the open message
Update Message
• The update message is the heart of the BGP protocol. It is used by a
router to withdraw destination that have been advertised previously,
announce a route to a new destination, or both
Update Message (cont.)
• The update message fields are listed below:
– Unfeasible routes length. This defines the length of
the next field
– Withdrawn routes. This fields lists all the routes that
must be deleted from the previously advertised list
– Path attributes length. This defines the length of the
next field
– Path attributes. This defines the attributes of the path
to the network whose reachability is being announced
in this message
– Network layer reachability information (NLRI). This
defines the network that is actually advertised by this
message
Keepalive Message
• The routers (called peers in BGP parlance)
running the BGP protocols exchnage keepalive
messages regularly (before their hold time
expires) to tell each other that they are alive
Notification Message
• A notification message is sent by a router
whenever an error condition is detected or a
router wants to close the connection
Notification Message (cont.)
• The fields making up the notification message
follow:
– Error code, Error subcode, and error data