IP routing scalability is based on hierarchical routing, which requires that the IP address hierarchy be aligned with the physical topology. Both site multi-homing and switching ISPs without renumbering break this alignment, resulting in large routing tables. This paper presents CRIO: a new approach to IP scalability for both global and VPN routing. Using tunneling and virtual prefixes, CRIO decouples address hierarchy and physical topology, effectively giving ISPs the ability to trade-off routing table size for path length. Though CRIO is a new routing architecture, it works with existing data-plane router mechanisms. Through static simulation on a Rocketfuel-measured Internet topology and traffic data from a Tier 1 ISP, we show that CRIO can shrink the BGP RIB by nearly two orders of magnitude, the global FIB by one order of magnitude, and the VPN FIB by ten to twenty times, all with very little increase in overall path length.

Major computer arithmetic systems are based on the concept of realizing only terminate rationals in positional notation. This paper proposes a new arithmetic scheme of indicating periodicity in the radix representation of a mantissa to realize recurring rationals as well as terminate rationals. A new arithmetic system adopting the scheme, called the “FLP/R* arithmetic system”, is proposed. Properties of the FLP/R* numbers and the procedure of the FLP/R* arithmetic are described.