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 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 . 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 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