Network Working Group D. Jen
Internet-Draft M. Meisel
Intended status: Informational D. Massey
Expires: January 3, 2008 L. Wang
B. Zhang
L. Zhang
July 2, 2007
APT: A Practical Transit Mapping Service
draft-jen-apt-00.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 3, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
The size of the global routing table is a rapidly growing problem.
Several solutions have been proposed. These solutions commonly
divide the Internet into two parts, one for customers and one for
providers, where only provider addresses are globally routable.
Packets destined for customer addresses are tunneled through provider
Jen, et al. Expires January 3, 2008 [Page 1]
Internet-Draft Transit Mapping July 2007
space. For this process to work, there must be a mapping service
that can supply an appropriate provider-edge address for any given
customer address. We present a design for such a mapping service.
We adhere to a "do no harm" design philosophy: maintain all desirable
features of the current architecture without negatively affecting its
security or reliability. Our design aims to minimize delay and
prevent loss in packet encapsulation, minimize the number of new or
modified devices, and keep the level of control traffic manageable.
Table of Contents
1. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. The Mapping Service . . . . . . . . . . . . . . . . . . . . . 5
4.1. A Mapping Example . . . . . . . . . . . . . . . . . . . . 6
5. Multihoming Support . . . . . . . . . . . . . . . . . . . . . 7
5.1. Using Alternate ETRs During Failures . . . . . . . . . . . 8
5.1.1. Handling TS Prefix Failure . . . . . . . . . . . . . . 9
5.1.2. Handling Single TS Address Failure . . . . . . . . . . 9
5.1.3. Handling User-to-TR Link Failure . . . . . . . . . . . 10
5.2. Summary of Requirements for Multihoming Support . . . . . 11
6. Exchanging Mappings Between ASes . . . . . . . . . . . . . . . 11
6.1. In Defense of BGP . . . . . . . . . . . . . . . . . . . . 12
7. Security and Robustness . . . . . . . . . . . . . . . . . . . 13
7.1. Detecting Misconfigurations . . . . . . . . . . . . . . . 13
7.2. ICMP Mapping Packets . . . . . . . . . . . . . . . . . . . 14
7.3. Other ICMP Packets . . . . . . . . . . . . . . . . . . . . 14
7.4. Default Mapper Scalability . . . . . . . . . . . . . . . . 15
8. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 15
9. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 16
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
11. Security Considerations . . . . . . . . . . . . . . . . . . . 17
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
12.1. Normative References . . . . . . . . . . . . . . . . . . . 17
12.2. Informative References . . . . . . . . . . . . . . . . . . 17
Appendix A. BGP Mapping Announcement Fields . . . . . . . . . . 18
Appendix B. ICMP Mapping Message Fields . . . . . . . . . . . . 19
Appendix C. ICMP Border Link Failure Fields . . . . . . . . . . 19
Appendix D. Hidden Backup Mappings . . . . . . . . . . . . . . . 19
Appendix D.1. Hidden Backup Mapping Protocol . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21
Intellectual Property and Copyright Statements . . . . . . . . . . 23
Jen, et al. Expires January 3, 2008 [Page 2]
Internet-Draft Transit Mapping July 2007
1. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
2. Introduction
The unexpected, explosive growth of the Internet is causing a greater
and greater strain on its infrastructure. This problem has been
well-documented in [RAWS][AddrAlloc]. Several solutions have been
proposed to address this problem [EFIT][CRIO][LISP], most of which
involve separating the Internet into two parts -- one for user
networks and one for transit providers. Routers in transit space
would only need to know how to route to transit prefixes, which are
stable and conducive to topological aggregation. When a packet is
sent from user address A to destination user address B, A's provider-
edge router (the ingress tunnel router, or "ITR", as defined in
[LISP]) encapsulates the packet and sends it through transit space to
B's provider-edge router (the egress tunnel router, or "ETR"). B's
ETR decapsulates the packet and forwards it to the appropriate
recipient, B.
When encapsulating a packet, A's ITR must somehow determine B's ETR's
transit-space address and include it in the outer header. In
general, any ITR must be able to map any given user-space address to
a corresponding ETR transit-space address for proper tunneling
through transit space. This illustrates the need for a mapping
service that can provide this address. The design details of this
mapping service will play a large part in determining the
effectiveness of any proposed implementation of a user/transit
provider address space separation. The mapping service also presents
an exciting opportunity to enhance the services currently offered by
the Internet, which is further reason to carefully consider how this
service should be implemented. Should mapping information be
distributed via a push or a pull model? What additional information,
if any, should be obtained along with the mapping information? Can
we satisfy the mapping requirement without sacrificing any services
or packet delivery quality?
Our answers to these questions are rooted in a "do no harm" design
philosophy: improve routing scalability without sacrificing any
desirable features in the current architecture or negatively
affecting its security and reliability. To this end, we present APT,
A Practical Transit mapping service designed with the following goals
in mind.
Jen, et al. Expires January 3, 2008 [Page 3]
Internet-Draft Transit Mapping July 2007
o Minimize delay and prevent loss in packet encapsulation.
o Minimize the number of devices that need to be modified to support
our new design.
o Minimize the number of devices that will require additional
resources or complexity.
o Keep the design modular so that the method used to propagate
mapping information is independent from the method used to
retrieve mapping information for tunneling.
APT is designed for use with eFIT [efitID][EFIT], one of the major
proposals for user/transit provider address space separation.
However, APT should be generally applicable to other proposals of the
same class.
3. Terminology
User Network (UN) - A network that pays another organization to
deliver its packets through the Internet. Each user network is a
customer of some Transit Network (see definition below). "User
network" holds the same meaning as it does in the eFIT proposal.
Transit Network (TN) - An AS whose business is to provide packet
delivery services for its customers. Transit Networks serve as
providers for user networks. As a rule of thumb, if the AS appears
in the middle of any ASPATH in a BGP route today, it is considered a
transit network.
Transit Space (TS) - The address space used by transit networks.
Nodes within a transit network are assigned TS addresses. Sometimes
the term "transit space" will refer to the non-edge area of the
Internet where TS prefixes are routable.
User Space (US) - The address space used by user networks. Nodes
within a user AS are assigned user-space addresses. Sometimes the
term "user space" will refer to the edges of the Internet whose
prefixes are not routable in transit space (though packets to those
addresses are deliverable through transit space). We assume that TS
and US addresses can be clearly distinguished.
Border Link - A link that crosses the boundary between transit space
and user space.
Default Mapper - A new device required by our mapping service. Each
transit network MUST have at least one default mapper. A default
Jen, et al. Expires January 3, 2008 [Page 4]
Internet-Draft Transit Mapping July 2007
mapper carries a complete mapping table. In other words, given any
user-space address, default mappers can return the TS address of a
provider-edge router corresponding to that address. To support the
growing trend towards multihoming, default mapping entries will map a
user-space prefix to a non-empty SET of TS destinations, all of which
have a direct connection to the destination network in user space.
Tunnel Router (TR) - These devices will replace all current provider-
edge routers, located at the provider end of border links. Like ITRs
and ETRs in LISP [LISP], TRs provide the encapsulation and
decapsulation services required for tunneling user packets through
transit space. A TR has both ITR and ETR functionality, meaning that
any TR can perform both encapsulation and decapsulation of packets.
To properly encapsulate any given user-space packet, TRs can query
the default mappers for mapping information. TRs also cache commonly
used mapping entries locally. Note that TR cache entries are NOT
identical to the mappings stored at default mappers (see the
definitions of "mapping" and "mapping entry" below). TRs are
designed to be as simple and as fast as possible, adding only what is
necessary for proper tunneling functionality.
APT Node - A general term referring to any new device type introduced
by APT. This includes both default mappers and TRs.
Router - These are ISP-owned non-border routers that exist today.
Other than minor configuration changes, these routers need no
alteration or replacement, and can be used just as they are used
currently.
Mapping - A mapping contains a user-space prefix and a non-empty SET
of ETR TS addresses associated with the prefix. Mappings also
include related information such as the user's public key and
priority rankings for each of the ETRs in the set. Default mappers
store mappings.
Mapping Entry - A mapping entry contains a user-space prefix and any
SINGLE ETR TS address associated with the prefix. Any mapping entry
is a subset of the complete mapping for its user-space prefix. TRs
store mapping entries along with an associated TTL. A mapping entry
is removed once its TTL expires.
4. The Mapping Service
To minimize the latency introduced by encapsulation, APT seeks to
store mapping information as close to the ITR as possible. However,
the global mapping table is likely to grow very large over time. To
avoid undue memory requirements for ITRs while still keeping mapping
Jen, et al. Expires January 3, 2008 [Page 5]
Internet-Draft Transit Mapping July 2007
information within reach, we introduce the concept of default
mappers.
A TR does not need to store the entire global mapping table.
Instead, it queries a default mapper for mapping information and
caches recently used mapping entries.
Default mappers are the only devices in the network that need to
store the complete global mapping table. As we will see in the
following example, TRs only use default mappers in the event of a
cache miss. This means that, given large enough caches at the TRs,
network latency will not heavily depend upon default-mapper
performance. Additionally, we propose the use of anycast to reach
default mappers within an AS. Each TN AS need only have a single
default mapper, but the use of anycast makes it easy for a TN to
deploy more. The result is a robust, scalable default mapping
system.
4.1. A Mapping Example
_ _
/ \ / \
/ A \ / B \________
\___/ \___/ |
| | | User Space
- - - - -|- - - - - - - - - - - - - -|- - - - -|- - - - - - - - - - - -
| | | Transit Space
.--+---. .--+---. |
_-| ITR1 |-_ _-| ETR1 |-_ |
/ '------' .`--. .--'. '------' .`--+--.
| ____ | X |--------| X | ____ | ETR2 |
| | M1 | '-;-' '-:-' | M2 | '-;----'
\ '-/\-' / \ '----' /
\___/ \___/ \__________/
______/ \____________________
| User Net | TS Addr | Priority |
|----------|----------|----------|
| ... | ... | ... |
|----------|----------|----------|
| B | ETR1 | 10 |
| | ETR2 | 20 |
|----------|----------|----------|
| ... | ... | ... |
'--------------------------------'
Figure 1. This is a simple topology for demonstrative purposes. A
and B are user networks addressable via user-space prefixes, ITR1,
Jen, et al. Expires January 3, 2008 [Page 6]
Internet-Draft Transit Mapping July 2007
ETR1, and ETR2 are TRs, any node labeled "X" is a router, and M1 and
M2 are default mappers. A portion of the mapping table for M1 is
shown.
In this section, we illustrate how TRs and default mappers interact
within an AS to properly tunnel user-space packets through transit
space.
In Figure 1, assume a node in network A sends a packet to a user-
space address in network B. When this packet arrives at ITR1, ITR1
looks up the destination user-space address in its mapping cache. If
a matching prefix is present in its cache, ITR1 simply encapsulates
the packet with the corresponding TS destination address and send it
across transit space. If a matching prefix is not present, ITR1 will
send the packet through its default mapper. It does this by
encapsulating the packet with the anycast address for default mappers
in its AS as the destination.
This packet will arrive at M1, the only default mapper in ITR1's AS.
When M1 receives the packet, it decapsulates it and examines the
user-space destination address. Since default mappers store the
full, global mapping table, a default mapper will always be able to
encapsulate the packet with a valid TS destination address. All
packets encapsulated by a default mapper MUST contain the default
mapper's TS address as the source address.
In addition to forwarding the packet to an appropriate ETR (ETR1, in
this case), M1 also treats the incoming packet as an implicit request
from ITR1 for mapping information. M1 responds to ITR1 with an ICMP
packet containing a mapping entry that maps B to ETR1. This allows
ITR1 to add this mapping entry to its cache so that ITR1 can tunnel
further packets destined for B directly to ETR1. The mapping entry
also contains a time to live (TTL) that is set by M1. The TTL
ensures that ITR1 will occasionally re-request this mapping
information from M1. At this time, if the mapping information
changed in any way since ITR1's prior request, M1 can respond with an
updated mapping entry. Without this TTL, ITR1's cached information
may become inaccurate over time.
5. Multihoming Support
In the example above, the observant reader may have noted that B is
multihomed. That is, B can be reached through both ETR1 and ETR2.
Multihoming provides B with both enhanced reliability in case of a
connectivity failure and the flexibility to split incoming traffic
across different ETRs.
Jen, et al. Expires January 3, 2008 [Page 7]
Internet-Draft Transit Mapping July 2007
In accordance with our design goals, all of the logic for selecting a
destination for a multihomed user is contained within default
mappers. Default mappers will store mappings containing all of the
ETRs for a given user-space prefix, and ITRs will only store a single
mapping entry per user-space prefix. When an ITR requests a mapping
entry for a multihomed user, it is up to the default mapper to decide
which one to return.
Many users will want to have some control over which ETR is used for
incoming traffic. To allow this, we let users assign a priority
value to each of the mapping entry for their prefixes, making it
available to all default mappers throughout the transit space (see
Section Section 6). The number is to be treated like a ranking -- an
ETR with a lower priority value is more preferable.
At the same time, a transit network may also has its own preference
regarding which of the ETRs to use for a given user-space prefix.
Default mappers can use a combination of locally configured routing
policies and the user priority information to choose from a set of
valid ETR addresses. Going back to Figure 1, assume that ITR1 does
not have a mapping entry for B in its cache. When A sends B a
packet, ITR1 will send the packet to M1. If M1 has no preference
between ETR1 and ETR2, it will examine the priority values in B's
mapping and select ETR1, B's most preferred ETR. M1 forwards the
packet to ETR1 and returns the appropriate mapping entry to ITR1,
which stores the mapping entry in its cache.
In the case of a priority value tie, the default mapper can break the
tie by picking the ETR to which it has the shortest path. If some
ETRs are tied in terms of both lowest priority value and shortest
path, the default mapper is free to break the tie arbitrarily. The
address of the selected ETR will be used as the destination address
when encapsulating the packet.
We envision that users will be able to manipulate their incoming
traffic load by setting appropriate priority values in their mapping.
A user who wants load balancing can assign the same priority value to
all of his mapping entries. A user who wants to have one TN as a
primary provider and another only as a backup can simply assign a
higher priority value to his ETR at his backup provider.
5.1. Using Alternate ETRs During Failures
When a network failure has caused an ETR to become unreachable, an
affected multihomed user will expect his traffic to be temporarily
routed through alternate ETRs. There are three general types of
failures that would require an ITR to use an alternate ETR: (1) an
ITR may discover via BGP that it can no longer reach the TS prefix
Jen, et al. Expires January 3, 2008 [Page 8]
Internet-Draft Transit Mapping July 2007
containing the address of the intended ETR, (2) an ITR may learn via
ICMP Destination Unreachable packets that its intended ETR is
unreachable, and (3) the link between a user network and its TR may
be down, a new problem introduced by the tunneling architecture. We
will explain how to handle each of these failure types below, using
Figure 1 as a reference. We assume that, at the time of failure, all
TN ASes are using ETR1 to reach B.
To assist in handling these failures, we include a time till retry
(TTR) for each mapping entry in every mapping stored in default
mappers. Normally, the TTR for each mapping entry is set to zero,
indicating that it is usable. Any mapping entry with a non-zero TTR
value is considered invalid. We will refer to the action of setting
a mapping entry's TTR as "invalidating the entry." Mapping entries
that map to unroutable destinations are also considered invalid. So
long as a mapping entry is invalid, default mappers will not use this
entry as a destination address or include it in mapping responses.
The role of the TTR for handling failures will become clear in the
explanations below.
5.1.1. Handling TS Prefix Failure
For failures of type (1), ITR1 has no route to ETR1. Assume a host
in network A attempts to send a packet to a host in network B. If
ITR1 does not have B's mapping in its cache, it will forward the
packet to M1 (see Section Section 4.1). If ITR1 does have B's
mapping in its cache, it will see that it has no path to ETR1, and
send the packet to M1 instead. M1 will also see that it has no route
to ETR1, and thus select the next-most-preferred ETR for B, ETR2. If
it has a route to ETR2, it sends the packet with ETR2 as the TS
destination address and replies to ITR1 with the corresponding
mapping entry. M1 can assign a relatively short TTL to the mapping
entry in its response. Once this TTL expires, ITR1 will forward the
next packet for B to the default mapper, which will respond with the
most-preferred mapping entry that is routable at that time. This
allows ITRs to quickly go back to using ETR1 once it becomes routable
again.
5.1.2. Handling Single TS Address Failure
In the second case, the TS prefix containing ETR1 is still routable
from ITR1, but ETR1 is unreachable from ITR1. Thus, ITR1 will
receive an ICMP Destination Unreachable message in response to any
packet sent to ETR1. ITR1 will need to turn to its default mapper
for an alternate TS destination address for B. M1 will send an
alternate valid mapping entry (if available) to ITR1. For this to
work, TRs MUST forward all received ICMP Destination Unreachable
messages to their default mappers. Default mappers MUST then
Jen, et al. Expires January 3, 2008 [Page 9]
Internet-Draft Transit Mapping July 2007
invalidate ALL mapping entries that map to the unreachable TS
destination address. To allow this, default mappers will have a
reverse-mapping table to go along with their mapping table. These
reverse-mapping tables map TS addresses to their corresponding user-
space prefixes. Now default mappers can look up the unreachable TS
address in their reverse-mapping tables, and temporarily invalidate
all entries that map to that TS address.
5.1.3. Handling User-to-TR Link Failure
The final case involves a failure of the link connecting ETR1 to B.
In the previous two cases, current Internet standards were in place
to allow ITR1 to know that a failure occurred. This case, on the
other hand, is a new type of failure that does not exist in today's
infrastructure. Therefore, it will require a new type of failure
message. These messages will take the form of a new ICMP message
type, which will include the user-space prefix that was not
reachable. TRs MUST be configured to forward all border link failure
ICMP messages to their default mappers, in the same fashion that TRs
forward all destination unreachable ICMP messages to their default
mappers.
Going back to our example, when ETR1 discovers it cannot forward the
packet to B due to a border link failure, it will send ITR1 an ICMP
packet of our new type stating that B's prefix is currently
unreachable. ITR1 will forward the border link failure ICMP message
to its default mapper, which will invalidate that mapping entry. If
the mapping entry is already invalid, it will reset the entry's TTR.
If the prefix has an alternate valid mapping entry, M1 will send this
mapping entry to ITR1.
Furthermore, to minimize packet losses, ETR1 should not simply drop
the packet addressed to the unreachable user network. Instead, ETR1
should send this packet to M2 in hopes of finding an alternate ETR
that can reach the user network. However, M2 will then look up a TS
destination address for B and choose ETR1 again. This is
undesirable, since we are seeking an alternative destination.
Therefore, when encapsulating packets for forwarding, default mappers
MUST check if the chosen TS destination address is the same as the TS
sender address in the packet's original TS header. If so, this
indicates that the TS-to-user link is down at this ETR. In such
cases, default mappers MUST invalidate the corresponding mapping
entry and seek an alternative.
To complete our example, ETR1 sends an ICMP message to ITR1 and also
sends the data packet to M2. M2 looks up a destination TS address
for the packet and finds ETR1. M2 then compares this TS address with
the TS address of the original sender of the packet, which is also
Jen, et al. Expires January 3, 2008 [Page 10]
Internet-Draft Transit Mapping July 2007
ETR1. Since they are the same, M2 invalidates this mapping entry and
finds an alternate destination, ETR2. M2 then forwards the packet to
ETR2.
5.2. Summary of Requirements for Multihoming Support
TR cache entries MUST include a TTL value, which will be provided by
their default mapper.
In default mappers, every TS destination address in a mapping MUST
include a time until retry (TTR). Usable mapping entries have a TTR
of zero. When a mapping entry becomes unreachable due to failures,
the TTR MUST be set to a pre-configured value. An alternate entry in
the same mapping MUST be used in place of an invalid mapping entry if
available.
Default mappers MUST be able to invalidate all mapping entries that
map to a particular TS destination address that has become
unreachable. This can be implemented using a reverse-mapping table.
We will use a new type of ICMP message to indicate border link
failure.
TRs MUST forward all ICMP destination unreachable and border link
failure messages to their default mapper.
If an ETR cannot send a packet due to a border link failure, it MUST
send this packet to its default mapper. This ETR MUST use its own TS
address as the source TS address of the packet.
Upon receipt of any data packet, default mappers MUST check if the
chosen TS destination address is the same as the TS source address in
the packet's original TS header. If so, default mappers MUST
invalidate the corresponding mapping entry and look for an alternate
ETR for the packet.
6. Exchanging Mappings Between ASes
In order for default mappers to store a full, global mapping table,
there must be some way for them to receive mappings from other ASes.
To avoid introducing latency or packet loss when encapsulating
packets, the default mappers must have a full set of mappings
available locally. To accomplish this, we distribute mappings using
a push method. Default mappers MUST regularly announce the mappings
for all of their customers to the rest of the network.
When a default mapper receives new mappings, it stores them in its
Jen, et al. Expires January 3, 2008 [Page 11]
Internet-Draft Transit Mapping July 2007
mapping table, replacing any existing mappings. When a TR receives
new mappings, it simply deletes any matching cache entries. Any
further communication with the formerly cached host will require the
use of a default mapper. This ensures that only the default mappers
need to validate mapping announcements and enforce policy.
Mapping messages will be flooded throughout the network via BGP. A
new BGP attribute will be required for this purpose.
We have selected BGP initially in order to ease incremental
deployment and minimize the changes required to existing routers.
However, mapping announcements could easily be distributed via a
different reliable broadcast protocol at a later date. Transitioning
mapping distribution to a different protocol will not affect any
other aspect of APT.
6.1. In Defense of BGP
Despite the use of BGP, mapping announcements will not cause the same
problems that BGP routing announcements do in the Internet today for
the following reasons.
First, for routing announcements, the path taken to reach each router
is a crucial piece of information. For mapping announcements, the
path taken to reach each APT node is not meaningful. This means that
only a single copy of each mapping announcement needs to reach each
APT node, providing an opportunity to prune duplicates, or even to
make use of a spanning tree. This also means that path exploration
and its repercussions do not exist for mapping announcements.
Second, mapping announcements only require processing at default
mappers and, to a lesser extent, TRs. Other routers in the network
need only pass these announcements along to their peers. Thus, the
processing burden placed on other routers by excessive routing
updates is completely avoided.
Finally, there will be far fewer mapping announcements than there are
routing announcements. TNs rarely change the addresses of their
equipment, and customers are generally under a monthly contract with
their provider TNs. Therefore, permanent mapping changes are
unlikely to occur more than once per month per customer.
Furthermore, transient failures do not cause mapping announcements in
APT. The most common cause of mapping announcements will be regular
refresh announcements, which should never need to be sent more than
every other day in most cases.
Jen, et al. Expires January 3, 2008 [Page 12]
Internet-Draft Transit Mapping July 2007
7. Security and Robustness
Using BGP to distribute mapping announcements guarantees that they
are only accepted from manually configured BGP peers. This ensures
that mapping announcements are no less secure than routing
announcements today. When applied to the eFIT architecture, however,
the security of this scheme is greatly increased. This is due to the
fact that eFIT TS addresses are not addressable from user space
[efitID][EFIT]. This turns out to be a major boon for the BGP trust
model, since only other TS nodes are valid BGP peers.
The complete separation of the eFIT TS address space provides another
security benefit: malicious users cannot attack equipment that they
cannot address. End users simply cannot affect the TS nodes that
their packets travel through within transit space.
Despite these benefits, there are some additional issues introduced
by APT. Manually configured mappings provide an opportunity for
human error, our reliance on ICMP packets provides an opportunity for
spoofing and cache poisoning, and storing the entire global mapping
table at default mappers poses a threat to long-term scalability.
The remainder of this section will address each of these issues in
turn.
7.1. Detecting Misconfigurations
Due to the fact that only TNs will have access to transit space,
false mapping updates are far more likely to be the result of
accidental misconfigurations than malicious attacks. With this in
mind, we present a simple, extensible authentication scheme that can
detect and, in some cases, prevent accidental misconfigurations.
The types of misconfigurations that could potentially be harmful are
those that result in one provider accidentally interfering with the
mapping for another provider's customer. This can happen whenever a
provider accidentally announces a mapping for the wrong user-space
prefix. These types of accidental conflicts fall into three
categories: (1) a provider announces a mapping for a prefix owned by
another provider's customer, (2) a provider announces a mapping for a
shorter user-space prefix that contains a longer user-space prefix
owned by owned by another provider's customer, and (3) a provider
announces a mapping for a longer user-space prefix that is a subset
of a shorter user-space prefix owned by another provider's customer.
The first category of conflicts is the only one that we intend to
actively prevent. Clearly, the user that owns a particular user-
space prefix should be the ultimate authority for his mapping
information. However, user networks do not announce their mappings
Jen, et al. Expires January 3, 2008 [Page 13]
Internet-Draft Transit Mapping July 2007
to the network directly, but rather through their providers. In
order to ensure a mapping update for a user-space prefix is approved
by its rightful owner, we must include some sort of user
authorization string in each announcement. To this end, we introduce
a public-key field into each mapping. This field SHOULD contain a
cryptographically valid public key, but it will only rarely need to
be used as such. In the normal case, when a default mapper receives
a new mapping announcement that would replace an existing one, it
only needs to ensure that the public key has not changed. (This
scheme is similar in spirit to the way that OpenSSH uses its
'known_hosts' file.) However, as long as all of a UN's providers
store the corresponding private key, the distribution of public keys
also introduces the possibility of using cryptographic signatures for
any number of purposes within transit space.
For the other two categories, it is less clear that such an
announcement is the result of a misconfiguration. It is possible,
for example, that the owner of a /16 user-space prefix has resold
some of the contained /24 prefixes to other UNs. In such cases, only
the administrators will know if the announcement is valid. It is for
this reason that (in the spirit of PHAS [PHAS]) we do not attempt to
prevent such changes, but only detect and notify interested parties.
Since legitimate mapping changes are infrequent, notifying interested
parties of mapping changes via e-mail is a perfectly viable option.
These notifications could also prove useful in debugging the mapping
service, or a particular provider's configuration.
7.2. ICMP Mapping Packets
ICMP mapping packets are used exclusively by default mappers to send
mapping entries to the TRs within their AS. Therefore, there is no
reason that these ICMP packets should ever need to travel between
ASes. In order to prevent cache poisoning through spoofing, these
ICMP packets simply MUST be dropped at all border routers within
transit space.
7.3. Other ICMP Packets
Our mapping service also depends on two other types of ICMP packets:
existing ICMP Destination Unreachable messages, and our new ICMP
Border Link Failure messages. Both of these packet types must
traverse AS boundaries. Again note that, under the eFIT
architecture, these packets are already more trustworthy than ICMP
packets in the current infrastructure -- they can only be generated
by hosts in transit space. However, if this level of security is
deemed insufficient, the keys used for detecting misconfigurations
could be used to cryptographically sign such packets, ensuring that
they are coming from the appropriate sender.
Jen, et al. Expires January 3, 2008 [Page 14]
Internet-Draft Transit Mapping July 2007
7.4. Default Mapper Scalability
Theoretically, the global mapping table could grow to contain a
separate mapping for every user-space prefix. In the case of IPv6
prefixes, the total number of mappings would be on the order of
10^18, far more than we can expect to be able to store on a single
device. If the global mapping table were to approach such gargantuan
proportions, a few simple changes to the default-mapper model would
allow APT to scale gracefully.
Instead of each default mapper storing the full, global mapping
table, each default mapper would store only a subset of the table.
This subset would be aggregatable by user-space prefix. For
addresses outside of this subset, a default mapper would store
mappings that mapped short, artificially aggregated prefixes to the
TS addresses of other default mappers. Like virtual prefixes in CRIO
[CRIO], the user-space prefixes in these mappings would not
necessarily correspond to actual user prefixes.
Each virtual prefix would be announced by the default mapper
responsible for the corresponding subset of the global mapping table.
In order to ensure complete coverage of the user address space, some
central authority would need to assign these virtual prefixes to
individual transit networks.
This scheme allows for a tradeoff between latency and default mapper
storage requirements. (For more discussion of the characteristics of
such a tradeoff, see [CRIO].) However, this scheme also requires
some providers to become authoritative sources for mappings owned by
other providers' customers. Both this requirement and the need to
involve a central authority could prove problematic for deployment.
Therefore, we do not recommend using this scheme unless the size of
the global mapping table demands it.
8. Incremental Deployment
Clearly, the deployment of APT will coincide with the deployment of
eFIT (or a similar architecture). Though incremental deployment of
the eFIT architecture itself is beyond the scope of this document, we
must at least show that APT will behave properly under partial
deployment.
Under the eFIT architecture, addresses outside of transit space will
not change. This means that user-space prefixes will initially share
the existing IP address space. This fact provides us with a simple
method for delivering packets to addresses for which no mapping is
available. Presumably, the only such addresses will be those
Jen, et al. Expires January 3, 2008 [Page 15]
Internet-Draft Transit Mapping July 2007
connected to providers who have not yet adopted the new architecture.
In order to deliver such packets, APT nodes can simply return them to
the old infrastructure, and they will be routed as they are today.
In order to support this feature, default mappers will respond to TRs
with an ICMP mapping packet that indicates that no entry exists for
the given user-space prefix. TRs will keep a negative cache entry
for such prefixes so that they can forward such packets directly to a
non-TS router.
In discussing incremental deployment, we must also address the issue
of how new default mappers will acquire the complete mapping table
when they are first connected to transit space. Since our mapping
service design requires that all ASes re-announce all of their
mappings at a regular interval, commissioning a new default mapper
only requires connecting it to the network and waiting for all other
TS ASes to re-announce their mappings. Yet, this introduces a
potential problem -- if there is no upper bound on the regular
refresh interval, there will be no upper bound on how long a new
default mapper needs to wait until its mapping table is complete.
Therefore, there needs to be an upper bound on the refresh interval
for mappings. An appropriate value would be once a week. This would
mean that a newly deployed default mapper would be able to reach the
entire transit space one week later (with the exception of any ASes
that failed to follow protocol).
9. Future Work
Optimally, any design paper should include an evaluation section. In
the future, we will examine traces of Internet activity to determine
the characteristics of the tradeoff between TR cache size and default
mapper workload, the amount of traffic overhead that would be
incurred by our push-based design, and any other results that the
community deems useful.
We are also considering automating user mapping updates. Under our
current design, whenever a user needs to update his mapping
information (he may add, subtract, or change providers, or change his
priority values), the user must contact his providers offline and
request that they announce the updated mapping information. It is
then up to the providers to update the mapping information. As we
have seen with DNS updates, human involvement introduces the
possibility of human error and delay. We hope to provide UNs with an
automated way to manage their mapping information.
Jen, et al. Expires January 3, 2008 [Page 16]
Internet-Draft Transit Mapping July 2007
10. IANA Considerations
This memo includes no request to IANA.
11. Security Considerations
Security considerations for APT are discussed in Section Section 7.
12. References
12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
12.2. Informative References
[efitID] Massey, D., Wang, L., Zhang, B., and L. Zhang, "A Proposal
for Scalable Internet Routing and Addressing", Internet Dr
aft, http://www.ietf.org/internet-drafts/
draft-wang-ietf-efit-00.txt, 2 2007.
[EFIT] Massey, D., Wang, L., Zhang, B., and L. Zhang, "A Scalable
Routing System Design for Future Internet", SIGCOMM IPv6
Workshop , 8 2007.
[LISP] Farinacci, D., Fuller, V., and D. Oran, "Locator/ID
Separation Protocol (LISP)", Internet Draft, http://
www.ietf.org/internet-drafts/draft-farinacci-lisp-00.txt,
2007.
[PHAS] Lad, M., Massey, D., Pei, D., Wu, Y., Zhang, B., and L.
Zhang, "PHAS: A Prefix Hijack Alert System", USENIX
Security .
[AddrAlloc]
Meng, X., Xu, Z., Zhang, B., Huston, G., Lu, S., and L.
Zhang, "IPv4 Address Allocation and BGP Routing Table
Evolution", ACM SIGCOMM Computer Communication Review
(CCR) special issue on Internet Vital Statistics, Volume
35, Issue 1, p71-80.
[RAWS] Meyer, D., Zhang, L., and K. Fall, "Report from the IAB
Workshop on Routing and Addressing", Internet Draft, http:
//www.ietf.org/internet-drafts/
draft-iab-raws-report-02.txt, 2007.
Jen, et al. Expires January 3, 2008 [Page 17]
Internet-Draft Transit Mapping July 2007
[CRIO] Zhang, X., Francis, P., Wang, J., and K. Yoshida, "Scaling
IP Routing with the Core Router-Integrated Overlay", Proc.
International Conference on Network Protocols , 11 2005.
Appendix A. BGP Mapping Announcement Fields
Address Type - This field specifies the type of user-space addresses
used for the user-space prefixes in the announcement. All user-space
prefixes in a single mapping announcement MUST be of the same address
type. Currently, this is expected to be either IPv4 or IPv6, but any
other address type is possible provided that it is supported by the
APT nodes in the ASes that wish to use it. APT nodes MUST ignore
mapping announcements for address types that they do not understand.
Total Length - This field specifies the total number of bytes used by
all mappings in the announcement. Each mapping announcement can
contain mappings for multiple prefixes, each with multiple mapping
entries.
Each mapping in the announcement is described by the following
fields:
User-space Prefix - This is the user prefix for the mapping.
Public Key - This is a public key that can be used to verify
signatures, decrypt data, and prevent misconfigurations for the
corresponding user-space prefix. See Section Section 7.1 for more
information.
Time To Live (TTL) - This is the amount of time in hours that this
mapping should persist in default mappers before being considered
obsolete and erased. This value MUST be set to at least three times
the regular refresh interval lest the corresponding user-space prefix
become unreachable. The TTL is specified in hours to prevent
misconfigurations from causing excessive mapping updates.
TS Address Count - This is the total number of TS addresses that the
corresponding user-space prefix maps to.
TS Address Set - This is a set of TS addresses, each with a priority.
The total number of addresses is specified by the previous field.
Priorities are arbitrary integers that only have meaning in reference
to each other. Addresses with lower priority values are considered
more preferable.
Jen, et al. Expires January 3, 2008 [Page 18]
Internet-Draft Transit Mapping July 2007
Appendix B. ICMP Mapping Message Fields
User-space Prefix - This prefix is used to match the input address
for mapping cache lookups.
TS Address - This is the destination that the user-space prefix maps
to.
TTL - This is the time that the entry stays in the cache. Its value
is determined by the default mapper.
Appendix C. ICMP Border Link Failure Fields
Prefix - This field contains the user-space prefix that cannot be
reached as a result of the border link failure.
Signature - This field can optionally contain a signature generated
using the UN's private key. It can then be used to verify the
legitimacy of the message.
Appendix D. Hidden Backup Mappings
As mentioned in our mapping section, our design allows users to
assign backup providers and perform traffic engineering through
appropriate assignment of their TN priority values. Of course, this
method will only prove effective if all transit networks generally
respect these priority values. This may not be the case in practice.
User networks may be negatively affected if priorities are not
respected. For example, imagine that a user has a cheap primary
provider and an expensive backup provider. If enough transit
networks ignore the UN's preference and send his traffic through the
backup provider, the financial impact on the user could be
significant. For this reason, users may not want to depend on other
ASes to respect their priority values.
In today's Internet, multihomed user networks can use BGP trickery to
hide their backup providers unless they are needed. The backup
provider simply does not announce a route to the UN's prefix unless
it receives a withdrawal for that prefix from the UN's primary
provider. At this point, the backup provider will announce its path
to the UN's prefix. Once it receives a new announcement for the
prefix from the primary provider, the backup provider withdraws its
path to the UN's prefix, putting it back into hiding.
In accordance with our "do no harm" design philosophy, we present a
Jen, et al. Expires January 3, 2008 [Page 19]
Internet-Draft Transit Mapping July 2007
method for including a hidden backup feature into APT. Hidden backup
support introduces new ICMP packets, mapping tables, and state into
APT. We leave it as an open question whether this feature should be
included at all. If transit networks are willing to respect the
priority values included with mapping entries, hidden backup support
(and its complexity) can be omitted entirely from APT.
Appendix D.1. Hidden Backup Mapping Protocol
A user would want to activate his hidden backup provider in the same
three failure situations that require switching to an alternate
provider (see Section Section 5.1). We will explain how to handle
each of these failure types.
Situation (1) is detectable by the backup provider via BGP. When the
backup provider learns that there are no routes to the UN's primary
provider, he MUST announce his own backup mapping and begin servicing
the user network. If the UN's primary provider later becomes
reachable, the backup provider MUST re-announce the original mapping.
The responsibility to re-announce the original mapping lies with the
backup provider in order to prevent route flapping from causing
mapping flapping. The backup provider SHOULD wait until the primary
provider has been stable for a set period of time before re-
announcing the original mapping. Also note that these mapping
announcements are indistinguishable from those generated by permanent
mapping changes, leaving default mappers throughout transit space no
choice but to respect them.
Situation (2) is detectable by the primary provider via IGP. When
the primary provider learns that one of his TRs is down, he MUST
inform the backup providers for the affected user networks. This
could be done via BGP flooding, but it seems excessive to flood the
entire core with a message that is only relevant to a handful of
providers. Instead of flooding, the primary provider needs to inform
the relevant backup providers directly. To support this, primary
providers MUST store a "backup-mapping table" that maps each of their
customers to their corresponding backup providers. This table should
not be very large, since each provider will only store entries for
his own customers. Furthermore, customers who do not have a hidden
backup can be excluded from the backup-mapping table.
When a TR goes down, one of the provider's default mappers can use
its reverse-mapping table (see Section Section 5.1) to determine
which user prefixes are affected. It can then use its backup-mapping
table to determine which backup providers need to be notified. The
rest of the communication will be implemented using two new ICMP
message types, "Primary Provider Failure" and "Primary Provider
Recovery". Each of these types will require an acknowledgment (ACK)
Jen, et al. Expires January 3, 2008 [Page 20]
Internet-Draft Transit Mapping July 2007
flag to ensure delivery.
Primary providers MUST send an ICMP "Primary Provider Failure"
message to each of the appropriate backup providers. These messages
MUST contain the relevant mapping entry. Upon receipt of such a
message, a backup provider MUST respond with an identical packet,
except that it MUST set the ACK flag. Then, it MUST announce a
backup mapping entry. When the customer's primary provider detects a
recovery, it MUST send an ICMP "Primary Provider Recovery" message to
the appropriate backup providers. The backup providers MUST
acknowledge the message, and re-announce the original mapping. As in
situation (1), re-announcing of the original mapping is left to the
backup providers to prevent mapping flapping.
Situation (3) is detectable by the TR whose link to a user has gone
down. The TR MUST inform his default mapper of this failure via the
new ICMP type described in Section Section 5.1.3. At this point, the
primary provider can lookup the affected user in his backup-mapping
table, and proceed as in situation (2).
The ICMP communication described above is essential to hidden backup
functionality. Thus, these messages must be secure and reliable.
Security can be achieved with public-private key cryptography (see
Section Section 7.3). For reliability, the primary provider MUST
continue to send "Primary Provider Failure" and "Primary Provider
Recovery" ICMP packets periodically until it receives an
acknowledgment from the backup provider. Backup providers MUST
always acknowledge these types of ICMP messages, regardless of the
state of the corresponding mapping.
Mapping announcements and ICMP communication will be carried out by
default mappers unless otherwise specified. Backup-mapping tables
are also stored in the default mappers.
Authors' Addresses
Dan Jen
Email: jenster@cs.ucla.edu
Michael Meisel
Email: meisel@cs.ucla.edu
Jen, et al. Expires January 3, 2008 [Page 21]
Internet-Draft Transit Mapping July 2007
Dan Massey
Email: massey@cs.colostate.edu
Lan Wang
Email: lanwang@memphis.edu
Beichuan Zhang
Email: bzhang@cs.arizona.edu
Lixia Zhang
Email: lixia@cs.ucla.edu
Jen, et al. Expires January 3, 2008 [Page 22]
Internet-Draft Transit Mapping July 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Jen, et al. Expires January 3, 2008 [Page 23]