Personal Alan O'Neill
BT
Internet Draft Hongyi Li
Nortel networks
Document: draft-oneill-li-hsr-00.txt
Category: Informational November 2000
Host Specific Routing
<draft-oneill-li-hsr-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. 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.
Abstract
This memo overviews the need for intra-domain Host specific routing
(HSR) in the Internet. Host Specific Routing provides a number of
benefits if route entry and look-up scalability issues can be
adequately addressed. These benefits are the enabling of flat
routing domains that eliminate the need for hierarchy and associated
configuration, and the potential to support rapid movement of IP
addresses through the routing fabric. This draft describes some of
the current work in this area, including TORA and Wireless Internet
Protocol (WIP), and the as yet unresolved research issues associated
with large-scale host routing. This draft requires and makes no
topological assumptions for HSR. Specifically it does not require a
strict tree, as implied by CIP and HAWAII. These micro-mobility
protocols do however share many of the scalability and inter-
protocol issues associated with host specific routes.
1. Introduction
This memo overviews the need for intra-domain Host specific routing
(HSR) in the Internet. Host Specific Routing provides a number of
benefits if route entry and look-up scalability issues can be
adequately addressed. These benefits are the enabling of flat
routing domains that eliminate the need for hierarchy and associated
configuration, and the potential to support rapid movement of IP
addresses through the routing fabric. This draft describes some of
the current work in this area, including TORA Mobile Enhanced
Routing (MER) and Wireless Internet Protocol (WIP), and the as yet
unresolved research issues associated with large-scale host routing.
In section 2 we describe the salient features of Host specific
routing in relation to existing prefix based routing, and the
associated benefits. In addition, we describe some of the technical
advancements in router design which may enable host routing to be
deployed in Internet domains. In section 3 we describe the host specific
routing for supporting IP mobility and then in section 4 we outline a
few of the research issues which need to be undertaken to take the Host
Specific Routing capabilities through to standardisation and deployment.
Section 5 then comments on the wishes of the authors in progressing HSR
in the research and standards areas. Finally, we give brief
overview of two new host specific routing protocols in Appendix.
This draft requires and makes no topological assumptions for HSR.
Specifically it does not require a strict tree, as implied by
Cellular IP and HAWAII. These micro-mobility protocols do however
share many of the scalability and inter-protocol issues associated
with host specific routes.
2. Overview of Host Specific Routing
2.1 Prefix and Host Specific Routing
The existing Internet uses prefix based routing to aggregate the
routes destined to a set of destination hosts on a single routing
table entry [OSPF]. In prefix routing, the packet forwarding is
determined by longest matching of the packet's IP address with the
network prefix recorded in routing table. The route aggregation
effectively reduces the amount of routing information and the size
of the routing tables in the Internet routers. The prefix based
packet forwarding requires hierarchical routing and topological
significant IP address assignment to reflect the actual network
topology.
Subnetting is the technique introduced by IETF [RFC950] to support
the network hierarchy. It overcomes the increasing routing table
size problem by ensuring that the subnet structure of a network is
not visible outside of an organization's private network. Only the
routers within the private organization need to differentiate
between the individual subnets. Early subnetting structure allowed
only three levels of hierarchies in IPv4 <Network-Prefix, Subnet-Number,
Host-Number>. As the introduction of Variable Length Subnet Mask
(VLSM) [RFC1009] and Classless Inter-Domain Routing (CIDR) [RFC
1518], an organization's network can be divided recursively into
multiple levels to enable route aggregation at the higher levels of
the network hierarchy. In IPv6, the global aggregatable unicast
address is defined [RFC2374]. Aggregatable addresses are
organized into a three level hierarchy <Public Topology,
Site Topology, Interface Identifier>. Public topology is the
collection of providers and exchanges who provide public Internet
transit services. Site topology is local to a specific site or
organization which does not provide public transit service to
nodes outside of the site. Interface identifiers identify interfaces
on links.
Host specific routing determines the packet forward route based on
the exact matching of a packet's IP address with the routing table
entry that records the route towards the host. Most of the existing
routers can support a small number of host specific routes in their
routing tables. However, due to the scalability issues and memory
limitation, host specific routing capability has never been widely
used in Internet. By limiting the use of host specific routing to
smaller network domains such as enterprise, metropolitan, and various
access networks, scalability will be less an issue.
Host specific routing has the advantages of supporting host
mobility, fast packet forwarding, and flattening the network
hierarchy. There is a trade-off in selecting host specific routing
or prefix routing for the different network domains. Use prefix
based routing in Internet backbone and host specific routing in
metropolitan area networks, access networks, enterprise networks
could be the ideal solution for optimizing network performance while
increasing the network flexibility. Hybrid approaches of using both
prefix based and host specific routing techniques have also been
proposed in supporting host mobility in single network domain such
as TORA:MER and WIP (described in Appendix).
2.2 HSR for 'Flat' Networking
Use of host specific routing in a network domain (e.g., enterprise
network) can flatten the network hierarchy and ease the network
planning task by allowing more dynamic network address assignment to
the locations where more addresses are required. In a hierarchical
network topology, the deployment of an addressing plan needs careful
thought of the network administrators. They must plan on the number
of subnets and the number of hosts in each subnet that are required
today and in the future. Without good network planning, it is
difficult to accommodate future network changes caused by growing
number of hosts and subnets in a hierarchical network topology.
2.3 HSR for Mobility
The location independent characteristic of Host Specific Routing
makes it an ideal technology to support mobility in the Internet. As
a mobile node moves out of its subnet, its IP address becomes only
an identity that does not have topology significant information.
Most of the existing intra-domain mobility solutions either directly
or indirectly use host specific routing technology for making packet
forward decisions. For example, Cellular IP [CIP] and Hawaii
[HAWAII} micro-mobility protocols directly use the HSR function of
the routers while HMIP[HMIP] and Regional Registration [RREG] indirectly
use HSR in overlay networks that consist of agents (i.e., Foreign or
mobile agents) interconnected by tunnels. Host specific routing is widely
used in the ad-hoc network routing protocols. Due to the dynamics of
network topology, it is difficult to maintain network hierarchy in
an ad-hoc network environment. Therefore, host identify is generally
used as the routing table entries for the ad-hoc network routers.
Host specific routing has been used in several micro-mobility
approaches such as Cellular IP and HAWAII. Cellular IP routers use
route cache to capture the host specific routes for downstream data
packets destining to the mobile hosts. In cellular IP, the upstream
data / control packets are snooped by the routers in the fixed
network. Based on the snooped packets, the routers pin down the
downstream host specific route for the mobile host. When the mobile
host moves, upstream data/control packets are snooped again to pin
down the new downstream route in the network. HAWAII uses the
similar approach like route cache to capture the host specific route
for the mobile hosts. The difference between HAWAII and CIP is that
HAWAII uses a signaling protocol to establish and update the route
cache. Both CIP and HAWAII require a strict tree onto which host
routing state is installed, which limits the scalability of these
approaches as the router at the top of the tree must maintain state
for all active hosts.
In contrast, both TORA:MER and WIP make no assumptions about the
network topology, supporting arbitrary meshing and host route
localization to dramatically improve domain sizes. They also use a
hybrid mix of both host-specific and prefix-based to further enhance
scalability in a network domain. In the hybrid prefix and host
specific routing approach, host specific entries are limited to a
small set of routers thereby reducing the size of routing tables.
Special algorithms are used in these proposals to maintain prefix
routing as much as possible. Only when a host moves out of the
subnet where it initially obtained the topology significant address,
will the algorithms inject host specific routes to a localized
subset of routers within the domain.
2.4 HSR Routing Look-Up
Prefix based packet forwarding requires longest prefix match for each
incoming packet that is one of the major bottlenecks in a router. The
number of memory accesses for finding the matching routing table
entry determines the speed of a route lookup algorithm [KESHAV].
Generally, longest prefix matching algorithms are complex and time
consuming in the sense that multiple memory access operations are
needed. As the memory price drops, people start to question the
traditional router design principles of using sophisticate algorithms
for saving memory space. Nowadays, as high capacity memory becomes
cheaper, it is possible to use a routing table with 4Gb memory to
lookup the entire IPv4 address space (i.e., host specific routes)
based on the assumption that a router has less than 256 interfaces.
In this hardware table lookup scheme, only one memory access is
required for a route lookup in the routing table [GUPTA]. In realty,
much smaller lookup table is required for intra-domain routing in the
enterprise routers.
WIP has proposed using host-specific routing for the network domains
with contiguous address space or multiple contiguous address spaces.
WIP capable routers organize the routing table as an array indexed
by IP address. Suppose the addresses for hosts in the network are of
the form network-prefix.host where the network prefix is n bits and
the host is h bits long. The network prefix is constant for all
hosts in the network. The number of different addresses in the
network domain is at most 2^h. The host specific routing table are
maintained in the form of an array with the i entry in the array
being the forwarding link for a packet with the host part of the
destination IP address having a value equal to i. The entries for
unallocated IP addresses will be empty in the table. When an IP packet is
received, its host portion of destination IP address will be the index value
for looking up the routing table. The packet will be forwarded on the link
indicated by the entry in that location. In this scheme, an index search
requires only one memory operation. The table requires only one byte of
memory per entry assuming that the number of links per router is
less than 256. This gives a memory size of 2 bytes. For 1 million
simultaneous users, where h = 20, and the amount of memory required
per internal cache is approximately 1MB. Hence, the entire
forwarding table can be loaded in very high-speed cache memory. The
routing entries for the subnets can be computed using Internet
routing protocol such as OSPF or RIP. The routing table entry for a
host is obtained by copying the entry for the subnet.
Index based routing table is not suitable for network domains with
non-contiguous address space. An example of this non-contiguous
address space is the IP address assigned by using IPv6 autoconfiguration
that appends the 64 bits MAC address of a host to the network prefixes
advertised by the routers. As the MAC address has 64 bits, there is no
way to index all the MAC addresses in a memory bank nowadays. Other
routing table structure like hashing table or table compaction techniques
can be use to allow efficient table lookup for routers that use host
specific routing.
3. New HSR Protocols for IP Mobility
Mobility of IP addressable devices is primarily being supported
today by the IETF Mobile IP working group [MIPv4}, [MIPv6]. Mobile
IP requires the Mobile Node (MN) to acquire temporary local
addresses as it moves through the Internet. Packets addressed to the
normal global address are tunneled from the home location to the
temporary location to achieve mobility. This is an edge forwarding
solution in that the Internets intra-domain routing protocol is not
aware of the mobility of the Mobile Node. An alternative solution
would be to instead expose the mobility to the routing protocol.
This necessarily requires the routing protocol to support host
specific messaging and state because the movement of each Mobile
Node is uncorrelated and the resulting routes cannot be aggregated
under a prefix.
The apparent and well-known scaling limitations of Host Specific
Routing can be significantly reduced in a mobility system by
appropriate system design, with the following optional techniques
from the Edge Mobility Architecture [EMA] being examples.
Firstly, the MN is only allocated an IP address whilst in-session
(sending/ receiving IP data) and this local IP address is allocated
from the aggregated prefix at the local router. This is called the
Allocating Access Router (AAR). As the MN moves ARs, the allocated
IP address moves with it so that higher-layer sessions are
unaffected. This is accomplished by modifying the intra-domain
routing using host routes to overrule and overwrite the underlying
prefix-based (i.e. aggregate) routing to the AAR
Host specific state is therefore only required as the Mobile Node
moves in-session and associated scaling properties are therefore
governed by in-session 'call' statistics rather than longer term
roaming statistics.
Secondly, localization of these HSR message injections (no of
routers affected by update messages) and the associated state (no of
host routes per router impacts look-up speed and memory costs) is
required for scalability reasons. This is to avoid every router in
the domain having to track the mobility of every MN, which would
necessarily result in very small domains and/or MN populations
Thirdly, when out of session, the routing system itself does not
track the MN, which is instead left to a separate paging and
forwarding system. Mobile IP [EMA-MIP]can be used as a component of
this whereby the MN has a global address, and paging and data
packets are forwarded to the MN using Mobile IP messaging. Receipt
of these packets at the MN causes it to acquire a local IP address
and revert to Host specific routing whilst in-session. The Host
specific routing enables the MN to continue to use the acquired
address in-session instead of updating it at each new router as
required by normal MobileIP. Similarly, the HSR protocol is limited
to tracking intra-domain mobility with Mobile IP used to track
inter-domain mobility.
4. HSR Research Issues
Host specific routing is a promising technology for optimizing the
network performance and easing the network planning and management
in enterprise and metropolitan networks. However, scalability is
still the major issue that prevents from using host specific routing
in large-scale networks. Apart from the size of routing table, Other
factors include the growing demand for CPU power to compute host
specific route and update routing table entries. Further research is
needed in different areas of host specific routing. Following list
gives the areas of host specific routing that require further
research.
New router architectures to support large-scale host specific
routes. For the new router architecture, further research is needed
on routing table compaction techniques, fast table lookup algorithm,
and rapid routing table update algorithm. Different router
architectures might be developed for various types of network such
as metropolitan networks, wireless networks, and enterprise
networks.
Scalable proactive and reactive routing algorithms for
efficiently establishing the host specific routes in large-scale
networks.
As host specific routing forwards data packet based on the host's
identity rather than its address, new and meaningful naming schemes
can be investigated. More research is needed for better naming
schemes that are suitable for host specific routing.
Techniques for using host specific routing over application
layer such as VPN, overlay networks.
Techniques for automatic network configuration and address
allocation that allows simplified network planning and flexible
network address assignment.
Research on mechanisms for providing appropriate Quality of
Service guarantee to the data traffic of network users. The QoS
support mechanism should be compatible with IETF QoS framework.
Fault tolerance algorithms for re-establishing consistent host
specific routes in the event of network node or link failure.
Security issues associated with the loss of topology
significance in the IP address, and in particular the maintenance of
the required binding between ingress filter configuration and
movement of the IP address.
Interactions between QoS, traffic engineering and multicast
protocols with the existence and movement of host routes.
5. Progression of HSR
It is clear that there is an opportunity and a rational to define
host specific routing technology for the Internet. Whilst much work
has already been done, there is clearly a need to examine in detail
the implications of HSR on other protocols and specific deployment
scenario's. The authors of this draft would therefore like to see an
IRTF group established, or an existing group re-chartered, to
provide a forum to undertake some rapid pre-standardization work on
Host Specific Routing.
Appendix A. Overview of TORA Mobile Enhanced Routing
TORA MER is a further proposed solution for intra-domain
mobility and is designed to replace existing Internet routing
protocols through out a mobility domain. In TORA MER, Inter-AR
routing is prefix-based, i.e. each AR advertises a prefix address
into the domain covering a block of host addresses that it controls.
Each host is allocated an interface address covered by the AAR
network prefix. While the host is "at home", packets are routed to
the host via this network prefix. Host-specific routing is required
only when the MN moves away from its AAR. Host-specific state is
injected into the network during handoff to overrule the MN's "at
home" prefix-based route, which redirects packets to that MN's
current AR location. Specifically, as the MN moves away from the
AAR, a host redirect route is locally injected, during handoff
between geographically adjacent ARs. The host route is installed on
the reverse of the shortest path back to the Old AR, from the New
AR. This ensures that any traffic on the aggregated AAR route is
"peeled-off" and redirected to the New AR.
Prefix and Host-specific routing is based on the Temporally Ordered
Routing Algorithm [TORA] being developed by the MANET IETF wg. TORA
uses router IDs to uniquely identify routers separately from their
interfaces. In TORA, routers reactively build Directed Acyclic
Graphs (DAGs) towards a destination router. Each router is assigned
a unique height and no two routers may have the same height. Data
flows from routers with higher heights to routers with lower heights
over "directed" links. Conceptually, data can be thought of as a
fluid that may only flow downhill over downstream links. By
maintaining a set of totally ordered heights at all times, loop-free
multipath routing is assured. Data would have to flow uphill to form
a loop and this is not permitted.
Extensions made to base TORA to create TORA MER, have been the
addition of a proactive route building mode for the support of the
aggregated prefixes, plus the addition of the host specific
messaging, to support packet redirection away from the prefix route.
When the destination of a directed link changes, for example when a
MN moves to a new cell, the TORA routing may be changed locally by
adjusting the heights of various local routers to "inject" a new
"downhill" route towards the new destination.
TORA is lightweight and has the ability to react quickly to route
around link and router failures. This makes its future deployment in
dense, cheap, low bandwidth IP Radio Access Networks more viable
than the use of the existing Internet standard protocol OSPF for
prefix routing, and brings with it the ability to support host
routing.
Appendix B. Overview of the Wireless Internet Protocol (WIP)
WIP uses a different approach in that it works in conjunction with a
standard intra-domain routing protocol such as OSPF, which
undertakes its normal job of routing aggregated prefixes. However,
included in these prefixes are the addresses associated with radio
ports (RPs) to which MNs can connect. WIP works in conjunction with
the intra-domain protocol by maintaining a mapping between these RPs
and the MNs as an IP address mapping. A look-up on a particular MN
IP address will identify the correct next hop according to the
intra-domain protocol, as that towards its present RP.
To maintain this mapping, WIP uses a registration message to
initialize the RP for the MN, and handoff signaling to update a
localized set of routers with the new RP for that MN. This signaling
uses reliable multicast to update the local set of routers which is
known as the Handoff Affected Router Group or HARG. The HARG is
unique for any pair of RPs, and each router knows which HARGs it
must join (HARG specific multicast group) by detecting a different
next hop interface for a pair of RPs in the OSPF tables. The HARG
calculation depends also on whether the WIP protocol is generating
pure host routes, or host redirect routes away from prefix routes.
OSPF is therefore used to provide loop-freedom and topological
information, whilst the WIP overlay (which is good for incremental
deployment) maintains the mapping between the RPs and the MNs so
that host state can be installed at the correct routers as a MN
moves.
WIPs technique of updating all routers affected by the MN movement
(in the HARG group for that pair of RPs), generates and maintains
the shortest hop paths to a MN at all times. This comes at the cost
of greater state and messaging when compared to TORA, which itself
only updates routers on the shortest path back to the Old AR.
References
[OSPF] J. Moy, "OSPF Version 2", Internet RFC 2328, April 1998.
[CIP] A. Campbell, et al., "Cellular IP", Internet-Draft, draft-
ietf-mobileip-cellularip-00.txt (work in progress), January, 2000.
[HAWAII] R. Ramjee, T. La Porta, S. Thuel, K. Varadhan and
L.Salgarelli, ``IP micro-mobility support using HAWAII," Internet
Draft, Work in Progress, June 1999.
[MIPv4] C.E. Perkins, Ed., "IP Mobility Support," Internet RFC
2002, Oct 1996.
[MIPv6] D. Johnson, C. Perkins, "Mobility Support in IPv6",
Internet-Draft, draft-ietf-mobileip-ipv6-12.txt (work in progress),
April, 2000.
[EMA] A. O'Neill, G. Tsirtsis, S. Corson, "Edge Mobility
Architecture", Internet-Draft, draft-oneill-ema-02.txt (work in
progress), July 2000.
[EMA-MIP] A. O'Neill, S. Corson, G. Tsirtsis, "EMA Enhanced Mobile
IPv6/IPv4", Internet-Draft,draft-oneill-ema-mip-00.txt, July 2000.
[statetransfer] A. O'Neill G. Tsirtsis S. Corson, "State transfer
between Access Routes during Handoff", Internet-Draft, draft-oneill-
handoff-statetransfer-00.txt, July 2000
[TORA] V. Park, M. S. Corson, "The Temporally-Ordered Routing
Algorithm", Proc. IEEE INFOCOM '97, Kobe, Japan, April 1997.
[GUPTA] P. Gupta, et.al., "Routing Lookups in Hardware at Memory Access
Speeds," Infocom'98, San Francisco, March 1998.
[KESHAV] S. Keshav and R. Sharma, "Issues and Trends in Router Design," IEEE
Communications Magazine, May 1998.
[HMIP] Karim El Malki, Hesham Soliman, "Hierarchical Mobile IPv4/v6 and Fast
Handoffs" IETF Draft: http://search.ietf.org/internet-drafts/draft-elmalki-
soliman-hmipv4v6-00.txt, March 10, 2000
[RREG] Eva Gustafsson, Annika Jonsson, Charles E. Perkins, "Mobile IP
Regional Registration", IETF DRAFT: http://search.ietf.org/internet-
drafts/draft-ietf-mobileip-reg-tunnel-03.txt, July 2000
[RFC950] J. Mogul, J. Postel, "Internet Standard Subnetting Procedure," IETF
Request for Comments: http://www.ietf.org/rfc/rfc0950.txt?number=950, August
1985
[RFC1009] R. Braden, J. Postel, "Requirements for Internet Gateways"
IETF Request for Comments: 1009,
http://www.ietf.org/rfc/rfc1009.txt?number=1009, June 1987
[RFC1518] Y. Rekhter, T. Li, "An Architecture for IP Address Allocation with
CIDR", IETF Request for Comments: 1518
http://www.ietf.org/rfc/rfc1518.txt?number=1518, September 1993
[RFC2374] R. Hinden, M. O'Dell, S. Deering, "An IPv6 Aggregatable Global
Unicast Address Format," Request for Comments: 2374,
http://www.ietf.org/rfc/rfc2374.txt?number=2374, July 1998
Author's Addresses
Alan O'Neill
BT
(+44) 1473-646459
alan.w.oneill@bt.com
Hongyi Li
Nortel Networks
(+1)-613-763-5966
hyli@nortelnetworks.com
Copyright Notice
Placeholder for ISOC copyright.
Internet Draft Host Specific Routing November 2000
O'Neill, Hongyi Li 1