|
 |
|
|||||
|
|||||||
|
Internet Protocol Table Look-up as a Geometric Problemby Marco Pellegrini Ongoing research at the CNR Institute for Informatics and Telematics in Pisa deals with the IP table look-up problem, a critical bottleneck for high-bandwidth Internet routers. The novelty lies in mapping an essentially discrete (digital) matching problem into a continuous search over points on the real line; this permits us to invoke powerful tools from continuous mathematics. New sectors of the economy and the public administration, ranging from e-commerce and e-entertainment to e-government, offer (or promise) consumers and citizens of the developed world a growing range of high-quality low-cost services. The hidden danger is that the underlying physical infrastructure (Internet) might not be able to cope with the increased demand for its basic delivery utilities upon which these user-oriented services are built. Already, the ever increasing number of computers and devices connected to Internet is pushing the inadequate IPv4 32-bit length standard for addresses towards the new IPv6b 128-bit length standard. At a high level, Internet is a large network of interconnected computers and devices, where some elements, called routers, are specialized in managing the traffic of fixed-size chunks of data called packets. The raw power of an internet router is measured in packets-per-second that the router is able to receive and redirect towards neighbouring routers. The IP table look-up operation is at the core of this process and consists of finding the entry of the routing table, stored in the router, that matches the address of an incoming packet and deciding on the appropriate exit route. Since the early 90’s, the IP table look-up problem has been recognized as a bottleneck and a variety of hardware and software solutions have been proposed. A general criticism of the state-of-the-art is that most if not all schemes proposed achieve efficiency through exploitation of the particular distribution of the entries of existing routing tables, based on the present configuration of Internet. The evolution of Internet and the much longer address format of IPv6 will radically change such assumptions and will force a reconsideration of all existing table look-up algorithms. At the present, it is a matter of conjecture how the interconnetivity of Internet will evolve on the medium time scale.
In our approach to the IP table look-up problem we map the distribution of entries in a routing table to a distribution of segments on the real line. Thus the problem of matching a table entry and an incoming address maps to the purely geometric problem of finding the shortest segment that contains a point. When we see the IP table look-up problem embedded in the continuum of the real line we can call upon sophisticated probabilistic techniques, in particular urn models, that make it possible to analyze various properties of the distribution of balls into bins. Statistical tests can be used to learn approximately the input distribution and to decide on an optimal decomposition of the line into buckets to speed up the on-line search. The objective is to endow the table look-up mechanism with the capability to adapt and fine tune with long term shifts in the distribution of the entries of routing tables. It has been known for a long time that (non-uniform) grids of buckets on a line can be used to test the hypothesis that a given set of points follows a certain distribution. The new twist is to add a second phase in which we also determine the uniform bin structure that is most suitable for the construction of a small depth and small memory search trees. In addition to long term shifts, the IP table must also respond to frequent local updates that are needed to keep the overall network load balanced. The need for frequent, efficient updates of the routing tables discourages the use of powerful, but essentially off-line optimization strategies, such as dynamic programming or other heavy optimization tools. Instead, we rely on simpler local rules well grounded in mathematical theory to decide the structure of the search tree to be used in the look-up. The three main quantities to balance are: speed of the search (worst case and average), memory consumption, and speed of updating the routing table. The optimal solution will thus consist of a profile, or work-load curve that the router operator can exploit when choosing a working profile. In a typical scenario, depending on the local time, certain parts of the world wide web are more active than others. Thus, it might be convenient over a 24-hour period to make certain parts of the routing table faster by using more storage locally, and other parts slower by using less storage, in order to cope with peak demands while keeping the total storage consumption unchanged. Please contact: |
