routing
Click on the red underlined text to get to the source
... address ownership" policy to every individual site or organization
that connects to the Internet results in a non-scalable routing.
...
... Public Internet. The document also
recommends that organizations that do not provide a sufficient degree
of routing information aggregation, but wish to obtain access to the
Internet ...
... aggregation, but wish to obtain access to the
Internet routing services should be strongly encouraged to use this
policy to gain access to the services ...
... IP address is the sole piece
of information about the node injected into the routing system.
...
... address is its ability to
interact with the Public Internet routing service and thereby
exchange data with the remainder of the Internet ...
... environment (the Internet) and its continued operation, including its
routing system, which gives an IP address its intrinsic value, rather
than the inverse. Consequently, if the Public Internet ...
... IP address its intrinsic value, rather
than the inverse. Consequently, if the Public Internet routing system
ceases to be operational, the service disappears, and the addresses ...
... Hierarchical routing and its implication on address allocation ...
...
Hierarchical routing [Kleinrock 77] is a mechanism that improves the
scaling properties of a routing system ...
... Hierarchical routing [Kleinrock 77] is a mechanism that improves the
scaling properties of a routing system. It is the only proven
mechanism for scaling routing to the current size of the Internet ...
... scaling properties of a routing system. It is the only proven
mechanism for scaling routing to the current size of the Internet.
...
...
Hierarchical routing requires that addresses be assigned to reflect
the actual network topology ...
... addresses be assigned to reflect
the actual network topology. Hierarchical routing works by taking the
set of addresses covered by a portion of the topology ...
... addresses covered by a portion of the topology, and generating
a single routing advertisement (route) for the entire set. Further,
hierarchical routing ...
... routing advertisement (route) for the entire set. Further,
hierarchical routing allows this to be done recursively: multiple
advertisements (routes) can be combined into a single advertisement
(route ...
... (route). By exercising this recursion, the amount of information
necessary to provide routing can be decreased substantially.
...
... network, a switch
need not keep detailed routing information about every possible
subscriber in a distant area code. Instead, the switch ...
... subscriber in a distant area code. Instead, the switch usually knows
one routing entry for the entire area code.
...
... subscriber in the world needs O(n) space for n worldwide
subscribers. Now consider the case of hierarchical routing. We can
break n down into the number of subscribers in the local area (l),
...
... country code (a) and other country codes (c). Using this
notation, hierarchical routing has space complexity O(l + e + a + c).
Notice that each of these factors is much, much less than n, and
grows very slowly, if at all. This implies that a phone switch ...
...
The fundamental property of hierarchical routing that makes this
scalability possible is the ability to form abstractions: here, the
...
... subscribers into exchanges, area codes and country
codes. Further, such abstractions must provide useful information for
the ability to do routing. Some abstractions, such as the group of
users with green phones, are not useful when it comes time to route ...
...
Since the information that the routing system really needs is the
location of the address within the topology ...
... location of the address within the topology, for hierarchical
routing, the useful abstraction must capture the topological location
of an address ...
... Scaling the Internet routing system ...
... Public Internet places a heavy load on the
Internet routing system. Before the introduction of CIDR the growth
rate had doubled the size of the routing table ...
... routing system. Before the introduction of CIDR the growth
rate had doubled the size of the routing table roughly every nine
months. Capacity of computer technology doubles roughly every 24
months. Even if we could double the capacities of the routers ...
... routers in the
Internet every 24 months, inevitably the size of the routing tables
is going to exceed the limit of the routers. Therefore, to preserve
...
... uninterrupted continuous growth of the Public Internet, deploying
mechanisms that contain the growth rate of the routing information is
essential.
...
...
Lacking mechanisms to contain the growth rate of the routing
information, the growth of the Internet would have to be either
limited or frozen, or the Internet ...
... Internet would have to be either
limited or frozen, or the Internet routing system would become
overloaded. The result of overloading routing ...
... routing system would become
overloaded. The result of overloading routing is that the routing
subsystem will fail: either equipment (routers ...
... overloaded. The result of overloading routing is that the routing
subsystem will fail: either equipment (routers) could not maintain
...
...
Classless Inter-Domain Routing (CIDR) [RFC1518, RFC1519 ...
... deployed since late 1992 in the Public Internet as the primary
mechanism to contain the growth rate of the routing information -
without CIDR the Internet ...
... without CIDR the Internet routing system would have already
collapsed. For example, in October 1995, within AlterNet (one of the
major Internet Service Providers ...
... Internet - a saving of 2395 routes (75%) [Partan 95]. In October 1995
the Internet Routing Registry (IRR) contained 61,430 unique prefixes
listed, not counting prefixes ...
...
CIDR is an example of the application of hierarchical routing in the
Public Internet, where subnets ...
... are some possible levels in the hierarchy. For example, a router
within a site need not keep detailed routing information about every
possible host in that site. Instead, the router ...
... possible host in that site. Instead, the router maintains routing
information on a per subnet basis. Likewise, a router within a
...
... router within a
provider need not keep detailed routing information about individual
subnets within its subscribers ...
... subscribers. Instead, the router could maintain
routing information on a per subscriber basis. Moreover, a router
...
... router
within a provider need not keep detailed routing information about
stub (single home) subscribers of other providers by maintaining
...
... stub (single home) subscribers of other providers by maintaining
routing information on a per provider basis.
...
... addressing information be formed along some hierarchy. As a result,
many exceptions will be injected into the routing system in the
future, besides those exceptions that currently exist. Each exception
added to the routing system ...
... routing system in the
future, besides those exceptions that currently exist. Each exception
added to the routing system deters the scalability of the routing
system. The exact number of exceptions that can be tolerated is
...
... added to the routing system deters the scalability of the routing
system. The exact number of exceptions that can be tolerated is
dependent on the technology used to support routing. Unbridled growth
...
... scalability of the routing
system. The exact number of exceptions that can be tolerated is
dependent on the technology used to support routing. Unbridled growth
in the number of such exceptions will cause the routing system to
...
... dependent on the technology used to support routing. Unbridled growth
in the number of such exceptions will cause the routing system to
collapse.
...
... Address allocation and management and the scalability of the routing
system are interrelated - only certain address allocation and
management ...
... address allocation and
management policies yield scalable routing. The Internet routing
system is subject ...
... management policies yield scalable routing. The Internet routing
system is subject to both technological and fundamental constraints.
...
... these addresses to gain access to the Internet routing services,
regardless of where the organization connects to the Internet ...
... Internet changes.
(b) By definition, hierarchical routing assumes that addresses
reflect the network topology ...
...
Therefore, the only presently known practical way to satisfy both
scalable hierarchical routing and address ownership for everyone is
to assume that the topology ...
... address owned by the
end users from those used by the Internet routing, and provide
mechanisms to translate between the two). In the absence of new
mechanisms, if we have address ...
... address ownership ("portable" addresses) for
everyone, then the routing overhead will lead to a breakdown of the
routing system ...
... routing overhead will lead to a breakdown of the
routing system resulting in a fragmented (partitioned) Internet.
Alternately, we can have a routable Internet ...
... under the loan. This document recommends a grace period of at least
30 days. Further, to contain the routing information overhead, this
document suggests that a grace period ...
... provider's block, then the provider can advertise a single address
prefix. This reduces the routing information that needs to be carried
by the Internet routing system ...
... routing information that needs to be carried
by the Internet routing system (for more information, see Section
5.3.1 of RFC1518hist). As the subscriber ...
... new provider's existing blocks, no new routes need to be introduced
into the routing system.
...
... constraints on address allocation policies
imposed by hierarchical routing, and thus promotes a scalable routing
system. Thus, the "address lending" policy, if applied
...
... address allocation policies
imposed by hierarchical routing, and thus promotes a scalable routing
system. Thus, the "address lending" policy, if applied
appropriately, could play an important role ...
...
To be able to scale routing in other parts of the hierarchy, the
"lending" policy may also be applied hierarchically, so that
addresses ...
...
Observe that the goal of hierarchical routing in the Internet is not
to reduce the total amount of routing information ...
... hierarchical routing in the Internet is not
to reduce the total amount of routing information in the Internet to
the theoretically possible minimum, but just to contain the volume of
...
... Internet to
the theoretically possible minimum, but just to contain the volume of
routing information within the limits of technology,
price/performance, and human factors. Therefore, organizations that
...
... default-free
part of the Internet routing system, regardless of where they connect
to the Internet. Therefore, using the "address ...
... reachability information they inject into the
Internet routing system should be subject to hierarchical
aggregation ...
... difficult, if not impossible. This, in turn, has a very detrimental
effect on the Internet routing system. To prevent the collapse of the
Internet routing system ...
... routing system. To prevent the collapse of the
Internet routing system, for such organizations, this document
recommends using the "address lending" policy. Consequently, when
...
... prefixes that the organization would
otherwise inject into the Internet routing system. This applies to
the case where the organization takes its addresses out of its direct
...
...
Carrying routing information has a cost associated with it. This
cost, at some point, may be passed back in full to the organizations
that inject the routing information ...
... routing information has a cost associated with it. This
cost, at some point, may be passed back in full to the organizations
that inject the routing information. Aggregation of addressing
...
... its direct provider) by limiting the distribution scope of its
routing information to its direct provider. Connectivity to the rest
of the Internet ...
... gateways eliminates the need for renumbering,
and avoids burdening the Internet routing system with non-
aggregatable addressing information; however they have other
...
... Both renumbering (due to the "address lending" policy), and non-
aggregated routing information (due to the "address ownership"
policy), and the use of mediating gateways ...
... scalability of the Public Internet routing system. Among all of the
possible address allocation and management ...
... address allocation and management policies only the ones
that yield a scalable routing system are feasible. All other policies
are self-destructive in nature, as they lead to a collapse of the
Internet ...
... are self-destructive in nature, as they lead to a collapse of the
Internet routing system, and therefore to the fragmentation
(partitioning) of the Public Internet ...
... scalability of the Internet
routing system. Such policies are almost certain to exhaust the
scalability of the Internet ...
... scalability of the Internet routing system well before we approach
the exhaustion of the IPv4 address space and before we can make
...
... rate and current technology, the notion that everyone can own address
space and receive Internet-wide routing services, despite where they
connect to the Internet ...
... address allocation policies in the Public Internet. Second,
organizations that do not provide a sufficient degree of routing
information aggregation to obtain access to the Internet routing ...
... routing
information aggregation to obtain access to the Internet routing
services should be strongly encouraged to use this policy to gain
...
... Kleinrock, L., and K. Farouk, K., "Hierarchical Routing for Large Networks," Computer Networks 1 (1977), North- Holland Publishing Company ...
... Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy ...