Transcript Publish-Subscribe Internet Routing Paradigm

PSIRP Inter-domain Topology Formation (ITF)
Prof. Sasu Tarkoma
University of Helsinki
Partially based on slides by Walter Wong and Kari Visala.
14.10.2008
1
Contents
•
•
•
•
•
14.10.2008
Current Inter-domain routing
PSIRP fundamentals
Interdomain Topology Formation
Interdomain routing
Conclusions
2
Evolution of IP routing
• Class-based routing
– A ,B and C classes
– Routing tables carried entries for all nets
– No topological aggregation (only network address
boundaries)
• Classless routing
– Using the variable length subnet mask to aggregate
addresses
– Routers forward mask (longest prefix)
• Too many small networks requiring multiple class C addresses
– C class has max 254 hosts
– Huge routing tables
CIDR
• CIDR (Classless Interdomain Routing)
– Routing prefixes carry topology information
– Contiguous blocks of C-class addresses
– Smaller routing tables
– How to handle multi-homing (and mobility?)
• Solves two problems
– Exhaustion of IP address space
– Size and growth rate of routing tables
• Address format <IP/prefix bits>
CIDR and Route Summarization
• The difference between CIDR and route summarization
– Route summarization is generally done within a
classful boundary
– CIDR combines several classful networks
• Examples of classless routing protocols
– RIP version 2 (RIPv2), OSPF, Intermediate Systemto-Intermediate System (IS-IS), and Enhanced
Interior Gateway Routing Protocol (EIGRP)
CIDR and IPv6
• CIDR present in IPv6 (fully classless)
• 128bit IPv6 address has two parts: network and host
– includes the prefix-length
– a decimal value indicating the number of higher-order
bits in the address that belong to the network part
• ISP aggregates all its customers' prefixes into a single
prefix and announces that single prefix to the IPv6
Internet
BGP
• BGP (Border Gateway Protocol) first became an Internet
standard in 1989.
• BGP selects AS-level paths for inter-domain routing. Each
AS may have multiple paths offered by neighbouring ASs.
• BGP-4 supports Classless Inter Domain Routing (CIDR) and
is the routing protocol that is used today to route between
autonomous systems.
• BGP uses TCP to establish a reliable connection between
two BGP speakers on port 179.
• A path vector protocol, because it stores routing information
as a combination of a destination and attributes of the path to
that destination.
• The protocol uses a deterministic route selection process to
select the best route from multiple feasible routes
BGP
• Characteristics such as delay, link utilization or router hops
are not considered in this process.
• BGP runs in two modes: EBGP and IBGP. EBGP (Exterior
BGP) is run between different autonomous systems, and
IBGP (Interior BGP) is run between BGP routers in the same
autonomous system
• BGP only recalculates routing information relative to these
updates, there is no regular process that must update all of
its routing information like the SPF calculations in OSPF or
IS-IS
BGP cont.
• When the BGP router receives its neighbors' full BGP routing table
(100k routes),
– Requires approx. 70 MB.
– With the AS_PATH filters applied to inbound updates
• 32k routes in 28 MB. 60% decrease from optimal routing.
• Problems
– multihomed customers forget to stop reannouncing
routes from upstream A to upstream B
– peer networks leak full tables to their peers
– A misconfigured router leaks out all internal more
specific routes (/48, /64, /128 prefixes)
• A network black hole is often used to improve aggregation of the BGP
global routing table.
BGP Problems
• Convergence time
• Limited policies
• Security problems
BGP IPv4 Table Growth
Source: http://www.cidr-report.org
BGP IPv6 Table Growth
Source http://bgp.potaroo.net/v6/as2.0/index.html
AS Numbers
• 16-bit AS numbers
• Current estimate is that limit will be reached on
February 2011
• IETF standards action in November 2006
– IANA extended the AS number field to 32 bits
• 65536 to 4,294,967,296 values
• From Jan, 2007 32bit values have been available from the
Regional Internet Number Registries (RIR)
Topology in address vs. routing table
Reactive
AD HOC
(MANET)
routing
ATM
PSIRP? PNNI
Pure source routing
(minimal state in
intermediate nodes)
Proactive
ad hoc
(MANET)
routing
Original
CIDR IP routing
Host-based hop-byhop (more state in
intermediate nodes)
Difficult Issues
• Convergence time of routing information
• State in the network
– Per-connection state is bad? (e.g. NAT)
• Independence of directories
• Security of routing information
– Whom to trust? How to represent authorization?
• QoS routing
PSIRP Fundamentals
14.10.2008
18
Main PSIRP design principles
•
Information is multi-hierarchically organised
– Higher-level information semantics are constructed in
the form of directed acyclic graphs (DAGs), starting
with semantic free forwarding labels towards higher
level concepts (e.g., ontologies).
•
Information
Hierarchies
Information
reachability/
scoping
Information scoping
– Mechanisms are provided that allow for limiting the
reachability of information to the parties having
access to the particular mechanism that implements
the scoping.
•
Scoped information neutrality
– Within each scope of information, data is only
forwarded based on the given (scoped) identifier.
•
The architecture is receiver-driven
Communication Model
– No entity receive data unless it has agreed to receive
the data beforehand, through appropriate signalling
methods.
14.10.2008
19
Where we are going
Higher Layers
Observations
Pub/Sub layer
Rendezvous
Routing
No topological addresses, only labels
No explicit layering (blackboard pattern)
Security enhanced using self-certification
End-to-end reachability, control in the network
Fragmentation
Natural support for multicast, it is the norm
Forwarding
Support for broadcast and all-optical labelswitching technologies
Dynamic state is introduced into the network
Link Layer
14.10.2008
How do we make it scale?
20
Publish / Subscribe
Metadata
(source is implementation-dependent)
Data
Includes...
Application Identifiers
(AId)
Includes...
Scope Identifiers
(SId)
Associated
with...
Resolved to...
Rendezvous Identifiers
(RId)
Resolved to...
Forwarding Identifiers
(FId)
Define...
Network Transit Paths
Scopes
Data: Mail
Data: Picture
Governance
policy
Scope Company A
Governance
policy
Scope Family
Scope Friends
Spouse
14.10.2008
Father
Friend
Governance
policy
Colleague
22
Forwarding Design
• Fast path
– In-packet Bloom filters
– Line-rate forwarding
• Slow path (Rendezvous)
– Content-centric functions
– Policies
– Caching configuration
– Security
14.10.2008
23
Intra-domain Forwarding
• Characteristics
– Links have identifiers (Link IDs)
– Source routing mechanism
– Install forwarding state on demand (traffic
aggregation)
• Topology Manager
– Network topology graph and its maintenance
– Constructs Bloom filter-based forwarding identifiers
zFilter – Summary
• Efficient flat identifier based forwarding
– Currrent zFilter size 256 bits
– Link IDs are added in the zFilter (OR operation)
– Verification requires one comparison (AND
operation)
• Limitations
– Possible false positives
– Wrong forwarding path
AS: Rendezvous
Publish
Forwarding
node
Subscriber
AS: Rendezvous
AS: Topology
Forwarding
node
AS: Topology
Forwarding
edge node
Data Forwarding
Forwarding
node
Subscribe
Forwarding
node
Publisher
Create
delivery
path
Configure
Forwarding
path
Rendezvous
• The network is defined in terms of domains and their
interconnections
– Interconnections between domains include upstream, transit,
downstream
• Rendezvous is the central primitive
– Rendezvous on multiple layers
– Builds forwarding paths
• We utilize the notion of completeness to optimize processing and
mobility updates
– Complete / incomplete dissemination structures between
rendezvous points
– A structure is complete when the operation (sub, adv) has
been processed by all elements that should process it 
typically partial in a global network
– Completeness can be used for network diagnostics
14.10.2008
27
Rendezvous Interconnect Architecture
●
●
●
●
DONA does not appear to be scalable for global-level rendezvous as it
stores a copy of all advertisements in all tier-1 domains.
ROFL uses a DHT to achieve scalability, but the peer-to-peer nature of the
system creates incentive problems.
PSIRP investigates a 2-tier system where a hierarchical DHT based
rendezvous interconnect network joins multiple rendezvous networks
together for global reachability.
●
Typically only scopes are advertised in the interconnect.
●
Hierarchical structure guarantees locality for the communication.
Local rendezvous networks and rendezvous interconnect nodes can
cache results for individual public (SId, RId) pairs and subscribe to the
changes by forming a multicast tree using the DHT routing alg.
Phases of Communication
Inter-domain Topology Formation
14.10.2008
30
ITF Motivation
• Current Internet structure is the starting point
– BGP and inter-AS relationships
• PSIRP network model
– Autonomous domains as in BGP
– Controlled by different organizations
– Organizational policies
• The pub/sub inter-as connections may result in different
inter-AS relations than observed today
– Multicast and caching
14.10.2008
31
Inter-domain Topology Formation (ITF)
• Helps building the forwarding information
– Based on policies set by operators and users
– Both senders, network, and receivers can set
policies
• Manages edge routers between domains
– Protection against policy violations
– Protect domain internals
Motivation – Inter-domain Routing
• There are approximately 10 tier-1 operators on the
Internet
– Full connectivity on tier-1
• Relationships
– Customer-provider
– Peer-peer
– Sibling-sibling
• Tier-1operators
– Peer with each other and do not buy traffic from other
operators
– Something that looks like a monopoly
Topology Management/Formation
• The Topology Manager (TM) is responsible
for path creation/computation/management
between data subscribers and publishers
– The TM abstracts the location of the entities at
network edges (they deal only with
data/information).
• Topology Manager
– Interested in receiving information about the
network
– Computes paths from publishers to subscribers
– Creates/Manages forwarding paths
• Creates ZFilters
Topology Manager (TM)
• One or more TM per domain
• Nodes (router)
– Local bootstrapping with HELLO messages
– Collect local connectivity with link quality and
forwarding capabilities
– Publish local connectivity information to the TM
• TM
– Reconstructs the overall forwarding level
topology in the network
Topology Management
• Intra-domain Topology Management
–
–
–
–
Local network topology generation
Intra-domain forwarding structures management
Computes network states
Updates forwarding information
• Inter-domain Topology Management
– Topology formation in the domain level
– Between administrative domains
– Configuring and maintaining inter-domain
topology based on policies
Intra-domain Forwarding & zFilters
• zFilter requirement
– Knowledge of the individual links composing the
forwarding path
• LIDs list generated based on the Sid and Rid
– Domain-specific end-points for data delivery
– Builds a forwarding graph between end-points
• Intra-domain TM
– Identifying possible virtual trees (constantly used
paths)
– Traffic pattern evaluation for virtual tree creation
– Lifetime and tree management (state in the
router)
Inter-domain Topology Formation
• Goals
– Stores forwarding information pertaining to domains
– Builds forwarding paths based on operator’s policies
across domains
– Connect Internet domains
Inter-domain Topology Formation
• Connect multiple intra-domain Topology Managers
• Communication between local topology formation and
inter-domain topology formation
• Offline route computation
– Faster approach
• Path construction between publishers and subscribers
through different domains
ITF – Design Requirements
• Flexible control of the routing policies
– Packets with different Rids should have different
routing policies
• High granularity
– Customers should be able to define per-Rid policies
• Multi-homing, multi-path routing, and partial data transit
support
• Operators are able to hide their internal topology
Inter-domain Topology Formation
Routing and Forwarding
ITF – Information Gathering
• Prior to publications
– Rendezvous (RVS) informs status of subscribers
regarding Sid/Rids (quench)
• Depends on granularity of information in the RVS
– Forwarding network identifiers
• ITF has to know a list of network identifiers to connect
publishers to subscribers
– Landmark identifiers
• Some landmark close to the subscriber knows how to deliver
publications
– Forwarding tree identifiers
• Construct partial distribution trees in anticipation of
publications
ITF – Pub/sub approach benefits

ITF components can subscribe to route changes
• There is no need to sequentially notify each domain
• Multicast support in pub/sub
– Simultaneous delivery to all ITF through common scope
• Avoids route flapping (convergence problem)
• Avoids propagation problems (when to stop)
Canopy: Using Upgraphs for Pub/Sub
• The NIRA system used upgraphs for
– Allowing more control for receiver
– Finding best paths for unicast
• Canopy uses upgraphs for pub/sub
– Upgraphs combined at receiver-side rendezvous point
– Can take both subscriber & publisher policies into
account,
– Supports multi-path routing
– Result is a policy-compliant multicast structure
– Can be used for both overlays and on the network layer
– Works with in-packet Bloom filter-based forwarding
14.10.2008
45
Canopy Overview
7. Forward subscription to matching
rendezvous points
R
6. Propagate
subscription
R
3. Propagate
rendezvous information
8. Combine
upgraphs and
perform path
selection
R
2. Send upgraph to
rendezvous point
5. Issue
subscription
4. Determine upgraph
S
Use the best
path for delivery
P
1. Determine upgraph
Conclusions
• Rendezvous
– Connecting subscribers and publishers (scopes,
Rids)
– Setting of policies
– 2-tier approach with rendezvous interconnect
• Interdomain Topology Formation (ITF)
– Understanding global network topology
– Domains reflecting physical and organizational
boundaries
– Needed for route computations (for ZFilter)
– Pub/sub for route updates (with scopes)
– Upgraphs for policy-compliant paths (Canopy)
14.10.2008
47