Internet DRAFT - draft-bates-multihoming
draft-bates-multihoming
HTTP/1.1 200 OK
Date: Mon, 08 Apr 2002 22:45:38 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Wed, 09 Jul 1997 16:13:00 GMT
ETag: "2e7d9a-6391-33c3b88c"
Accept-Ranges: bytes
Content-Length: 25489
Connection: close
Content-Type: text/plain
Network Working Group Tony Bates
Internet Draft Cisco Systems
Expiration Date: January 1998 Yakov Rekhter
Cisco Systems
Scalable support for multi-homed multi-provider connectivity
draft-bates-multihoming-01.txt
1. Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working doc-
uments of the Internet Engineering Task Force (IETF), its areas, and
its working groups. Note that other groups may also distribute work-
ing 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 mate-
rial or to cite them other than as ``work in progress.''
To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
2. Abstract
This document describes addressing and routing strategies for multi-
homed enterprises attached to multiple Internet Service Providers
(ISPs) that are intended to reduce the routing overhead due to these
enterprises in the global Internet routing system.
Bates, Rekhter [Page 1]
Internet Draft draft-bates-multihoming-01.txt July 1997
3. Motivations
An enterprise may acquire its Internet connectivity from more than
one Internet Service Provider (ISP) for some of the following rea-
sons. Maintaining connectivity via more than one ISP could be viewed
as a way to make connectivity to the Internet more reliable. This way
when connectivity through one of the ISPs fails, connectivity via the
other ISP(s) would enable the enterprise to preserve its connectivity
to the Internet. In addition to providing more reliable connectivity,
maintaining connectivity via more than one ISP could also allow the
enterprise to distribute load among multiple connections. For enter-
prises that span wide geographical area this could also enable better
(more optimal) routing.
The above considerations, combined with the decreasing prices for the
Internet connectivity, motivate more and more enterprises to become
multi-homed to multiple ISPs. At the same time, the routing overhead
that such enterprises impose on the Internet routing system becomes
more and more significant. Scaling the Internet, and being able to
support a growing number of such enterprises demands mechanism(s) to
contain this overhead. This document assumes that an approach where
routers in the "default-free" zone of the Internet would be required
to maintain a route for every multi-homed enterprise that is con-
nected to multiple ISPs does not provide an adequate scaling. More-
over, given the nature of the Internet, this document assumes that
any approach to handle routing for such enterprises should minimize
the amount of coordination among ISPs, and especially the ISPs that
are not directly connected to these enterprises.
There is a difference of opinions on whether the driving factors
behind multi-homing to multiple ISPs could be adequately addressed by
multi-homing just to a single ISP, which would in turn eliminate the
negative impact of multi-homing on the Internet routing system. Dis-
cussion of this topic is beyond the scope of this document.
The focus of this document is on the routing and addressing strate-
gies that could reduce the routing overhead due to multi-homed enter-
prises connected to multiple ISPs in the Internet routing system.
The strategies described in this document are equally applicable to
both IPv4 and IPv6.
Bates, Rekhter [Page 2]
Internet Draft draft-bates-multihoming-01.txt July 1997
4. Address allocation and assignment
A multi-homed enterprise connected to a set of ISPs would be allo-
cated a block of addresses (address prefix) by each of these ISPs (an
enterprise connected to N ISPs would get N different blocks). The
address allocation from the ISPs to the enterprise would be based on
the "address-lending" policy [RFC2008]. The allocated addresses then
would be used for address assignment within the enterprise.
One possible address assignment plan that the enterprise could employ
is to use the topological proximity of a node (host) to a particular
ISP (to the interconnect between the enterprise and the ISP) as a
criteria for selecting which of the address prefixes to use for
address assignment to the node. A particular node (host) may be
assigned address(es) out of a single prefix, or may have addresses
from different prefixes.
5. Routing information exchange
The issue of routing information exchange between an enterprise and
its ISPs is decomposed into the following components:
a) reachability information that an enterprise border router
advertises to a border router within an ISP
b) reachability information that a border router within an ISP
advertises to an enterprise border router
The primary focus of this document is on (a); (b) is covered only as
needed by this document.
5.1. Advertising reachability information by enterprise border routers
When an enterprise border router connected to a particular ISP deter-
mines that the connectivity between the enterprise and the Internet
is up through all of its ISPs, the router advertises (to the border
router of that ISP) reachability to only the address prefix that the
ISP allocated to the enterprise. This way in a steady state routes
injected by the enterprise into its ISPs are aggregated by these
ISPs, and are not propagated into the "default-free" zone of the
Internet.
When an enterprise border router connected to a particular ISP deter-
mines that the connectivity between the enterprise and the Internet
through one or more of its other ISPs is down, the router starts
Bates, Rekhter [Page 3]
Internet Draft draft-bates-multihoming-01.txt July 1997
advertising reachability to the address prefixes that was allocated
by these ISPs to the enterprise. This would result in injecting addi-
tional routing information into the "default-free" zone of the Inter-
net. However, one could observe that the probability of all multi-
homed enterprises in the Internet concurrently losing connectivity to
the Internet through one or more of their ISPs is fairly small. Thus
on average the number of additional routes in the "default-free" zone
of the Internet due to multi-homed enterprises is expected to be a
small fraction of the total number of such enterprises.
The approach described above is predicated on the assumption that an
enterprise border router has a mechanism(s) by which it could deter-
mine (a) whether the connectivity to the Internet through some other
border router of that enterprise is up or down, and (b) the address
prefix that was allocated to the enterprise by the ISP connected to
the other border router. One such possible mechanism could be pro-
vided by BGP [BGP]. In this case border routers within the enterprise
would have an IBGP peering with each other. Whenever one border
router determines that the intersection between the set of reachable
destinations it receives via its EBGP (from its directly connected
ISP) peerings and the set of reachable destinations it receives from
another border router (in the same enterprise) via IBGP is empty, the
border router would start advertising to its external peer reachabil-
ity to the address prefix that was allocated to the enterprise by the
ISP connected to the other border router. The other border router
would advertise (via IBGP) the address prefix that was allocated to
the enterprise by the ISP connected to that router. This approach is
known as "auto route injection".
As an illustration consider an enterprise connected to two ISPs, ISP-
A and ISP-B. Denote the enterprise border router that connects the
enterprise to ISP-A as BR-A; denote the enterprise border router that
connects the enterprise to ISP-B as BR-B. Denote the address prefix
that ISP-A allocated to the enterprise as Pref-A; denote the address
prefix that ISP-B allocated to the enterprise as Pref-B. When the
set of routes BR-A receives from ISP-A (via EBGP) has a non-empty
intersection with the set of routes BR-A receives from BR-B (via
IBGP), BR-A advertises to ISP-A only the reachability to Pref-A.
When the intersection becomes empty, BR-A would advertise to ISP-A
reachability to both Pref-A and Pref-B. This would continue for as
long as the intersection remains empty. Once the intersection becomes
non-empty, BR-A would stop advertising reachability to Pref-B to ISP-
A (but would still continue to advertise reachability to Pref-A to
ISP-A). Figure 1 below describes this method graphically.
Bates, Rekhter [Page 4]
Internet Draft draft-bates-multihoming-01.txt July 1997
+-------+ +-------+ +-------+ +-------+
( ) ( ) ( ) ( )
( ISP-A ) ( ISP-B ) ( ISP-A ) ( ISP-B )
( ) ( ) ( ) ( )
+-------+ +-------+ +-------+ +-------+
| /\ | /\ | /\ |
| || | || | Pref-A (connection
| Pref-A | Pref-B | Pref-B broken)
| || | || | || |
+-----+ +-----+ +-----+ +-----+
| BR-A|------|BR-B | | BR-A|------|BR-B |
+-----+ IBGP +-----+ +-----+ IBGP +-----+
non-empty intersection empty intersection
Figure 1: Reachability information advertised
Although strictly an implementation detail, calculating the intersec-
tion could potentially be a costly operation for a large set of
routes. An alternate solution to this is to make use of a selected
single (or more) address prefix received from an ISP (the ISP's back-
bone route for example) and configure the enterprise border router to
perform auto route injection if the selected prefix is not present
via IBGP. Let's suppose ISP-B has a well known address prefix, ISP-
Pref-B for its backbone. ISP-B advertises this to BR-B and BR-B in
turn advertises this via IBGP to BR-A. If BR-A sees a withdraw for
ISP-Pref-B it advertises Pref-B to ISP-A.
The approach described in this section may produce less than the full
Internet-wide connectivity in the presence of ISPs that filter out
routes based on the length of their address prefixes. One could
observe however, that this would be a problem regardless of how the
enterprise would set up its routing and addressing.
5.2. Further improvements
The approach described in the previous section allows to signifi-
cantly reduce the routing overhead in the "default-free" zone of the
Internet due to multi-homed enterprises. The approach described in
this section allows to completely eliminate this overhead.
An enterprise border router would maintain EBGP peering not just with
the directly connected border router of an ISP, but with the border
router(s) in one or more ISPs that have their border routers directly
connected to the other border routers within the enterprise. We
Bates, Rekhter [Page 5]
Internet Draft draft-bates-multihoming-01.txt July 1997
refer to such peering as "non-direct" EBGP.
An ISP that maintains both direct and non-direct EBGP peering with a
particular enterprise would advertise the same set of routes over
both of these peerings. An enterprise border router that maintains
either direct or non-direct peering with an ISP advertises to that
ISP reachability to the address prefix that was allocated by that ISP
to the enterprise. Within the ISP routes received over direct peer-
ing should be preferred over routes received over non-direct peering.
Likewise, within the enterprise routes received over direct peering
should be preferred over routes received over non-direct peering.
Forwarding along a route received over non-direct peering should be
accomplished via encapsulation [GRE].
As an illustration consider an enterprise connected to two ISPs, ISP-
A and ISP-B. Denote the enterprise border router that connects the
enterprise to ISP-A as E-BR-A, and the ISP-A border router that is
connected to E-BR-A as ISP-BR-A; denote the enterprise border router
that connects the enterprise to ISP-B as E-BR-B, and the ISP-B border
router that is connected to E-BR-B as ISP-BR-B. Denote the address
prefix that ISP-A allocated to the enterprise as Pref-A; denote the
address prefix that ISP-B allocated to the enterprise as Pref-B. E-
BR-A maintains direct EBGP peering with ISP-BR-A and advertises
reachability to Pref-A over that peering. E-BR-A also maintain a non-
direct EBGP peering with ISP-BR-B and advertises reachability to
Pref-B over that peering. E-BR-B maintains direct EBGP peering with
ISP-BR-B, and advertises reachability to Pref-B over that peering.
E-BR-B also maintains a non-direct EBGP peering with ISP-BR-A, and
advertises reachability to Pref-A over that peering.
When connectivity between the enterprise and both of its ISPs (ISP-A
and ISP-B is up, traffic destined to hosts whose addresses were
assigned out of Pref-A would flow through ISP-A to ISP-BR-A to E-BR-
A, and then into the enterprise. Likewise, traffic destined to hosts
whose addresses were assigned out of Pref-B would flow through ISP-B
to ISP-BR-B to E-BR-B, and then into the enterprise. Now consider
what would happen when connectivity between ISP-BR-B and E-BR-B goes
down. In this case traffic to hosts whose addresses were assigned out
of Pref-A would be handled as before. But traffic to hosts whose
addresses were assigned out of Pref-B would flow through ISP-B to
ISP-BR-B, ISP-BR-B would encapsulate this traffic and send it to E-
BR-A, where the traffic will get decapsulated and then be sent into
the enterprise. Figure 2 below describes this approach graphically.
Bates, Rekhter [Page 6]
Internet Draft draft-bates-multihoming-01.txt July 1997
+---------+ +---------+
( ) ( )
( ISP-A ) ( ISP-B )
( ) ( )
+---------+ +---------+
| |
+--------+ +--------+
|ISP-BR-A| |ISP-BR-B|
+--------+ +--------+
| /+/ |
/\ | Pref-B /+/ |
|| | /+/ \./
Pref-A| /+/ non- /.\
|| | /+/ direct |
| /+/ EBGP |
+------+ +-------+
|E-BR-A|-----------|E-BR-B |
+------+ IBGP +-------+
Figure 2: Reachability information advertised via non-direct EBGP
Observe that with this scheme there is no additional routing informa-
tion due to multi-homed enterprises that has to be carried in the
"default-free" zone of the Internet. In addition this scheme doesn't
degrade in the presence of ISPs that filter out routes based on the
length of their address prefixes.
Note that the set of routers within an ISP that maintain non-direct
peering with the border routers within an enterprise doesn't have to
be restricted to the ISP's border routers that have direct peering
with the enterprise's border routers. The non-direct peering could be
maintained with any router within the ISP. Doing this could improve
the overall robustness in the presence of failures within the ISP.
5.3. Combining the two
One could observe that while the approach described in Section 5.2
allows to completely eliminate the routing overhead due to multi-
homed enterprises in the "default-free" zone of the Internet, it may
result in a suboptimal routing in the presence of link failures. The
sub-optimality could be reduced by combining the approach described
in Section 5.2 with a slightly modified version of the approach
described in Section 5.1. The modification consists of constraining
the scope of propagation of additional routes that are advertised by
an enterprise border router when the router detects problems with the
Bates, Rekhter [Page 7]
Internet Draft draft-bates-multihoming-01.txt July 1997
Internet connectivity through its other border routers. A way to con-
strain the scope is by using the BGP Community attribute [RFC1997].
5.4. Better (more optimal) routing in steady state
The approach described in this document assumes that in a steady
state an enterprise border router would advertise to a directly con-
nected ISP border router only the reachability to the address prefix
that this ISP allocated to the enterprise. As a result, traffic orig-
inated by other enterprises connected to that ISP and destined to the
parts of the enterprise numbered out of other address prefixes would
not enter the enterprise at this border router, resulting in poten-
tially suboptimal paths. To improve the situation the border router
may (in steady state) advertise reachability not only to the address
prefix that was allocated by the ISP that the router is directly con-
nected to, but to the address prefixes allocated by some other ISPs
(directly connected to some other border routers within the enter-
prise). Distribution of such advertisements should be carefully con-
strained, or otherwise this may result in significant additional
routing information that would need to be maintained in the "default-
free" part of the Internet. A way to constrain the distribution of
such advertisements is by using the BGP Community attribute
[RFC1997].
6. Comparison with other approaches
CIDR [RFC1518] proposes several possible address allocation strate-
gies for multi-homed enterprises that are connected to multiple ISPs.
The following briefly reviews the alternatives being used today, and
compares them with the approaches described above.
6.1. Solution 1
One possible solution suggested in [RFC1518] is for each multi-homed
enterprise to obtain its IP address space independently from the ISPs
to which it is attached. This allows each multi-homed enterprise to
base its IP assignments on a single prefix, and to thereby summarize
the set of all IP addresses reachable within that enterprise via a
single prefix. The disadvantage of this approach is that since the
IP address for that enterprise has no relationship to the addresses
of any particular ISPs, the reachability information advertised by
the enterprise is not aggregatable with any, but default route.
results in the routing overhead in the "default-free" zone of the
Internet of O(N), where N is the total number of multi-homed enter-
prises across the whole Internet that are connected to multiple ISPs.
Bates, Rekhter [Page 8]
Internet Draft draft-bates-multihoming-01.txt July 1997
As a result, this approach can't be viewed as a viable alternative
for all, but the enterprises that provide high enough degree of
addressing information aggregation. Since by definition the number of
such enterprises is likely to be fairly small, this approach isn't
viable for most of the multi-homed enterprises connected to multiple
ISPs.
6.2. Solution 2
Another possible solution suggested in [RFC1518] is to assign each
multi-homed enterprise a single address prefix, based on one of its
connections to one of its ISPs. Other ISPs to which the multi-homed
enterprise is attached maintain a routing table entry for the organi-
zation, but are extremely selective in terms of which other ISPs are
told of this route and would need to perform "proxy" aggregation.
Most of the complexity associated with this approach is due to the
need to perform "proxy" aggregation, which in turn requires addi-
tional inter-ISP coordination and more complex router configuration.
7. Discussion
The approach described in this document assumes that addresses that
an enterprise would use are allocated based on the "address lending"
policy. Consequently, whenever an enterprise changes its ISP, the
enterprise would need to renumber part of its network that was num-
bered out of the address block that the ISP allocated to the enter-
prise. However, these issues are not specific to multihoming and
should be considered accepted practice in todays internet. The
approach described in this document effectively eliminates any dis-
tinction between single-home and multi-homed enterprise with respect
to the impact of changing ISPs on renumbering.
The approach described in this document also requires careful address
assignment within an enterprise, as address assignment impacts traf-
fic distribution among multiple connections between an enterprise and
its ISPs.
Both the issue of address assignment and renumbering could be
addressed by the appropriate use of network address translation
(NAT). The use of NAT for multi-homed enterprises is the beyond the
scope of this document.
Use of auto route injection (as described in Section 5.1) increases
the number of routers in the default-free zone of the Internet that
could be affected by changes in the connectivity of multi-homed
enterprises, as compared to the use of provider-independed addresses
Bates, Rekhter [Page 9]
Internet Draft draft-bates-multihoming-01.txt July 1997
(as described in Section 6.1). Specifically, with auto route injec-
tion when a multi-homed enterprise loses its connectivity through one
of its ISPs, the auto injected route has to be propagated to all the
routers in the default-free zone of the Internet. In contrast, when
an enterprise uses provider-independent addresses, only some (but not
all) of the routers in the default-free zone would see changes in
routing when the enterprise loses its connectivity through one of its
ISPs.
To supress excessive routing load due to link flapping the auto
injected route has to be advertised until the connectivity via the
other connection (that was previously down and that triggered auto
route injection) becomes stable.
Use of the non-direct EBGP approach (as described in Section 5.2)
allows to eliminate route flapping due to multi-homed enterprises in
the default-free zone of the Internet. That is the non-direct EBGP
approach has better properties with respect to routing stability than
the use of provider-independent addresses (as described in Section
6.1).
8. Applications to multi-homed ISPs
The approach described in this document could be applicable to a
small to medium size ISP that is connected to several upstream ISPs.
The ISP would acquire blocks of addresses (address prefixes) from its
upstream ISPs, and would use these addresses for allocations to its
customers. Either auto route injection, or the non-direct EBGP
approach, or a combination of both could be used by the ISP when
peering with its upstream ISPs. Doing this would provide routability
for the customers of such ISP, without advertsely affecting the over-
all scalability of the Internet routing system.
9. Security Considerations
Security issues are not discussed in this document.
Bates, Rekhter [Page 10]
Internet Draft draft-bates-multihoming-01.txt July 1997
10. Acknowledgments
The authors of this document do not make any claims on the original-
ity of the ideas described in this document. Anyone who thought about
these ideas before should be given all due credit.
11. References
[RFC2008]
Y. Rekhter, T. Li, "Implications of Various Address Allocation
Policies for Internet Routing", RFC2008, BCP7, October 1996.
[RFC1918]
Y. Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot & E. Lear,
"Address Allocation for Private Internets", RFC1918, February 1996.
[BGP]
Rekhter, Y., and Li, T., "A Border Gateway Protocol 4 (BGP-4)",
RFC1771, March 1995.
[GRE]
S. Hanks, T. Li, D. Farinacci, P. Traina, "Generic Routing Encapsu-
lation over IPv4 networks", RFC1773, October 1994.
[RFC1997]
R. Chandra, P. Traina, T. Li, "BGP Communities Attribute", RFC1997,
August 1996
[RFC1518]
Y. Rekhter & T. Li, "An Architecture for IP Address Allocation with
CIDR", RFC1518, September 1993.
Bates, Rekhter [Page 11]
Internet Draft draft-bates-multihoming-01.txt July 1997
12. Author's Addresses
Tony Bates
Cisco Systems, Inc.
170 West Tasman Drive
San Jose, CA 95134
email: tbates@cisco.com
Yakov Rekhter
Cisco Systems, Inc.
170 West Tasman Drive
San Jose, CA 95134
email: yakov@cisco.com
Bates, Rekhter [Page 12]
