Transcript ppt

CDA 6505 Network Architecture
and Client/Server Computing
Lecture 16
Exterior Routing Protocols
And Multicasting
by
Zornitza Genova Prodanoff
Lect1..ppt - 03/28/05
Outline
• Path-Vector Protocols: BGP and IDRP
• Muticasting
ZGP002
Problems with Distance-Vector and Link-State Routing
• Neither distance-vector (RIP) nor link state (OSPF)
protocols effective for exterior routing
• Distance vector and link state protocols assume all
routers share common metric
• Priorities and restrictions may differ between ASs
• Flooding of link state information may become
unmanageable
ZGP003
Path Vector Routing
• Dispense with routing metrics
• Provide information about:
– Which networks can be reached by given router
– Which ASs must be crossed to get there
• No distance or cost element
• Routing information includes all Ass visited to reach
destination
– Allows policy routing
ZGP004
Boarder Gateway Protocol (BGP)
• Allows routers (gateways) in different ASs to
exchange routing information
• Messages sent over TCP
– See next slide
• Three functional procedures
– Neighbour acquisition
– Neighbour reachability
– Network reachability
ZGP005
BGP v4 Messages
• Open
– Start neighbour relationship with another router
• Update
– Transmit information about single route
– List multiple routes to be withdrawn
• Keepalive
– Acknowledge open message
– Periodically confirm neighbour relationship
• Notification
– Send when error condition detected
ZGP006
Neighbour Acquisition
• Neighbours attach to same subnetwork
• If in different ASs routers may wish to exchange
information
• Neighbour acquisition is when two neighbouring
routers agree to exchange routing information
regularly
– Needed because one router may not wish to take
part
• One router sends request, the other acknowledges
– Knowledge of existence of other routers and need
to exchange information established at
configuration time or by active intervention
ZGP007
Neighbour Reachability
• Periodic issue of keepalive messages
• Between all routers that are neighbours
ZGP008
Network Reachability
• Each router keeps database of subnetworks it can
reach and preferred route
• When change made, router issues update message
• All BGP routers build up and maintain routing
information
ZGP009
BGP Message Formats
• Marker:
– Reserved for
authentication
• Length:
– In octets
• Type:
– Open, Update,
Keepalive,
Notification
ZGP0010
Neighbour Acquisition Detail
• Router opens TCP connection with neighbour
• Sends open message
– Identifies sender’s AS and gives IP address
– Includes Hold Time
• As proposed by sender
• If recipient prepared to open neighbour relationship
– Calculate hold time
• min [own hold time, received hold time]
• Max time between keepalive/update messages
– Reply with keepalive
ZGP0011
Keepalive Detail
• Header only
• Often enough to prevent hold time expiring
ZGP0012
Update Detail
• Information about single route through internet
– Information to be added to database of any
recipient router
– Network layer reachability information (NLRI)
• List of network portions of IP addresses of
subnets reached by this route
– Total path attributes length field
– Path attributes field (next slide)
• List of previously advertised routes being withdrawn
• May contain both
ZGP0013
Path Attributes Field
• Origin
– Interior (e.g. OSPF) or exterior (BGP) protocol
• AS_Path
– ASs traversed for this route
• Next_Hop
– IP address of boarder router for next hop
• Multi_Exit_disc
– Information about routers internal to AS
• Local_Pref
– Tell other routers within AS degree of preference
• Atomic_Aggregate, Aggregator
– Uses subnet addresses in tree view of network to reduce
information needed in NLRI
ZGP0014
Withdrawal of Route(s)
• Route identified by IP address of destination
subnetwork(s)
ZGP0015
Notification Message
• Error notification
• Message header error
– Includes authentication and syntax errors
• Open message error
– Syntax errors and option not recognised
– Proposed hold time unacceptable
• Update message error
– Syntax and validity errors
• Hold time expired
• Finite state machine error
• Cease
– Close connection in absence of any other error
ZGP0016
Diagram for BGP Routing Information Exchange
ZGP0017
BGP Routing Information Exchange
• R1 constructs routing table for AS1 using OSPF
• R1 issues update message to R5 (in AS2)
– AS_Path: identity of AS1
– Next_Hop: IP address of R1
– NLRI: List of all subnets in AS1
• Suppose R5 has neighbour relationship with R9 in AS3
• R9 forwards information from R1 to R9 in update
message
– AS_Path: list of ids {AS2,AS1}
– Next_Hop: IP address of R5
– NLRI: All subnets in AS1
• R9 decides if this is preferred route and forwards to
neighbours
ZGP0018
Inter-Domain Routing Protocol (IDRP)
•
•
•
•
•
Exterior routing protocol for IPv6
ISO-OSI standard
Path-vector routing
Superset of BGP
Operates over any internet protocol (not just TCP)
– Own handshaking for guaranteed delivery
• Variable length AS identifiers
• Handles multiple internet protocols and address
schemes
• Aggregates path information using routing domain
confederations
ZGP0019
Routing Domain Confederations
• Set of connected AS
• Appear to outside world as single AS
– Recursive
• Effective scaling
ZGP0020
Multicasting
• Sending message to multicast address
– Multicast address refers to a group of hosts
• Multimedia
• Teleconferencing
• Databases
• Distributed computation
• Real-time workgroup
ZGP0021
Multicasting within LAN
• MAC level multicast addresses
– IEEE 802 uses highest order bit 1
• All stations that recognise the multicast address
accept the packet
• Works because of broadcast nature of LAN
• Packet only sent once
• Much harder on internet
ZGP0022
Example
Configuration
for Multicast
Internet
ZGP0023
Broadcast
•
•
•
•
Assume location of recipients not know
Send packet to every network
Packet addressed to N3 traverses N1, link L3, N3
Router B translates IP multicast address to MAC
multicast address
• Repeat for each network
• Generates lots of packets
– In example, 13
ZGP0024
Multiple Unicast
• Location of each member of multicast group known to
source
• Table maps multicast address to list of networks
• Only need to send to networks containing members of
multicast group
• Reduced traffic (a bit)
– In example, 11
ZGP0025
True Multicast
• Least cost path from source to each network
containing member of group is determined
– Gives spanning tree configuration
• For networks containing group members
only
• Source transmits packet along spanning tree
• Packet replicated by routers at branch points
of spanning tree
• Reduced traffic
– In example, 8
ZGP0026
Multicast Transmission Example
ZGP0027
Requirements for Multicasting (1)
• Router must forward two or more copies of incoming
packet
• Addressing
– IPv4 uses class D
• Start 1110 plus 28 bit group id
– IPv6 uses 8 bit prefix of all 1s, 4 bit flags field, 4 bit scope
field 112 bit group id
• Node must translate between multicast address and
list of networks containing members of group
• Router must translate between IP multicast address
and subnet multicast address to deliver to destination
network
ZGP0028
Requirements for Multicasting (2)
• Multicast addresses may be permanent or dynamic
• Individual hosts may join or leave dynamically
– Need mechanism to inform routers
• Routers exchange information on which subnets
contain members of groups
• Routers exchange information to calculate shortest
path to each network
– Need routing protocol and algorithm
• Routes determined based on source and destination
addresses
– Avoids unnecessary duplication of packets
ZGP0029
Internet Group Management Protocol (IGMP)
• Type: Membership query (general or group specific),
membership report, leave group, max. response time
• Checksum: uses IPv4 algorithm
• Group address: zero for request, valid IP multicast
for report or leave
ZGP0030
IGMP Operation
• Host uses IGMP to make itself know as member of
group to other hosts and routers
• To join, send IGMP membership report message
– Send to multicast destination of group being joined
• Routers periodically issue IGMP query
– To all-hosts multicast address
– Hosts respond with report message for each group
to which it belongs
• Only one host in group needs to respond to keep
group alive
• Host keeps timer and reponds if no other reply
heard in time
• Host sends leave group message
– Group specific query from router determins if any
members remain
ZGP0031
Group Membership with IPv6
• Function incorporated in ICMPv6
• Includes all ICMPv4 plus IGMP
– Includes group membership query and report
– Addition of new group membership termination
message
ZGP0032
Multicast Extension to OSPF (MOSPF)
• Enables routing of IP multicast datagrams within
single AS
• Each router uses MOSPF to maintain local group
membership information
• Each router periodically floods this to all routers in
area
• Routers build shortest path spanning tree from a
source network to all networks containing members of
group (Dijkstra)
– Takes time, so on demand only
ZGP0033
Forwarding Multicast Packets
• If multicast address not recognised, discard
• If router attaches to a network containing a member
of group, transmit copy to that network
• Consult spanning tree for this source-destination pair
and forward to other routers if required
ZGP0034
Equal Cost Multipath Ambiguities
• Dijkstra’ algorithm will include one of multiple equal
cost paths
– Which depends on order of processing nodes
• For multicast, all routers must have same spanning
tree for given source node
• MOSPF has tiebreaker rule
ZGP0035
Interarea Multicasting
• Multicast groups amy contain members from more
than one area
• Routers only know about multicast groups with
members in its area
• Subset of area’s border routers forward group
membership information and multicast datagrams
between areas
– Interarea multicast forwarders
ZGP0036
Inter-AS Multicasting
• Certain boundary routers act as inter-AS multicast
forwarders
– Run and inter-AS multicast routing protocol as well
as MOSPF and OSPF
– MOSPF makes sure they receive all multicast
datagrams from within AS
– Each such router forwards if required
– Use reverse path routing to determine source
• Assume datagram from X enters AS at point
advertising shortest route back to X
• Use this to determine path of datagram through
MOSPF AS
ZGP0037
MOSPF Routing Illustration
ZGP0038
Multicast Routing Protocol Characteristics
• Extension to existing protocol
– MOSPF v OSPF
• Designed to be efficient for high concentration of
group members
• Appropriate with single AS
• Not for large internet
ZGP0039
Protocol Independent Multicast (PIM)
• Independent of unicast routing protocols
• Extract required routing information from any
unicast routing protocol
• Work across multiple AS with different unicast
routing protocols
ZGP0040
PIM Strategy
• Flooding is inefficient over large sparse
internet
• Little opportunity for shared spanning trees
• Focus on providing multiple shortest path
unicast routes
• Two operation modes
– Dense mode
• For intra-AS
• Alternative to MOSPF
– Sparse mode
• Inter-AS multicast routing
ZGP0041
Spares Mode PIM
• A spare group:
– Number of networks/domains with group members
present significantly small than number of
networks/domains in internet
– Internet spanned by group not sufficiently
resource rich to ignore overhead of current
multicast schemes
ZGP0042
Group Destination Router Group Source Router
• Group Destination Router
– Has local group members
– Router becomes destination router for given group
when at least one host joins group
• Using IGMP or similar
• Group source router
– Attaches to network with at least one host
transmitting on multicast address via that router
ZGP0043
PIM Approach
• For a group, one router designated rendezvous point
(RP)
• Group destination router sends join message towards
RP requesting its members be added to group
– Use unicast shortest path route to send
– Reverse path becomes part of distribution tree for this RP
to listeners in this group
• Node sending to group sends towards RP using
shortest path unicast route
• Destination router may replace group-shared tree
with shortest path tree to any source
– By sending a join back to source router along unicast
shortest path
• Selection of RP dynamic
– Not critical
ZGP0044
Example of PIM Operation
ZGP0045