Luleå algorithm
Encyclopedia
The Luleå algorithm of computer science
, designed by , is a patent
ed technique for storing and searching internet
routing table
s efficiently. It is named after the Luleå University of Technology
, the home institute of the technique's authors. The name of the algorithm does not appear in the original paper describing it, but was used in a message from Craig Partridge to the Internet Engineering Task Force
describing that paper prior to its publication.
The key task to be performed in internet routing is to match a given IPv4
address
(viewed as a sequence of 32 bits) to the longest prefix
of the address for which routing information is available. This prefix matching problem may be solved by a trie
, but trie structures use a significant amount of space (a node
for each bit of each address) and searching them requires traversing a sequence of nodes with length proportional to the number of bits in the address. The Luleå algorithm shortcuts this process by storing only the nodes at three levels of the trie structure, rather than storing the entire trie.
The main advantage of the Luleå algorithm for the routing task is that it uses very little memory, averaging 4–5 bytes per entry for large routing tables. This small memory footprint often allows the entire data structure to fit into the routing processor's cache, speeding operations. However, it has the disadvantage that it cannot be modified easily: small changes to the routing table may require most or all of the data structure to be reconstructed.
To look up the datum for a given address x in the first level of the data structure, the Luleå algorithm computes three values:
The sum of these three values provides the index to use for x in the array of items.
If there are few enough different pieces of routing information associated with a chunk, the chunk just stores the list of these routes, and searches through them by a single step of binary search followed by a sequential search. Otherwise, an indexing technique analogous to that of the first level is applied.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, designed by , is a patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
ed technique for storing and searching internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
routing table
Routing table
In computer networking a routing table, or Routing Information Base , is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics associated with those routes. The routing table contains information about the...
s efficiently. It is named after the Luleå University of Technology
Luleå University of Technology
Luleå University of Technology or Luleå tekniska universitet of Sweden is Scandinavia's northernmost university of technology. It has four campuses, located in Luleå , Kiruna , Skellefteå and Piteå .-History:The university was founded on 1 June 1971 at Porsön in Luleå as...
, the home institute of the technique's authors. The name of the algorithm does not appear in the original paper describing it, but was used in a message from Craig Partridge to the Internet Engineering Task Force
Internet Engineering Task Force
The Internet Engineering Task Force develops and promotes Internet standards, cooperating closely with the W3C and ISO/IEC standards bodies and dealing in particular with standards of the TCP/IP and Internet protocol suite...
describing that paper prior to its publication.
The key task to be performed in internet routing is to match a given IPv4
IPv4
Internet Protocol version 4 is the fourth revision in the development of the Internet Protocol and the first version of the protocol to be widely deployed. Together with IPv6, it is at the core of standards-based internetworking methods of the Internet...
address
IP address
An Internet Protocol address is a numerical label assigned to each device participating in a computer network that uses the Internet Protocol for communication. An IP address serves two principal functions: host or network interface identification and location addressing...
(viewed as a sequence of 32 bits) to the longest prefix
Prefix
A prefix is an affix which is placed before the root of a word. Particularly in the study of languages,a prefix is also called a preformative, because it alters the form of the words to which it is affixed.Examples of prefixes:...
of the address for which routing information is available. This prefix matching problem may be solved by a trie
Trie
In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...
, but trie structures use a significant amount of space (a node
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
for each bit of each address) and searching them requires traversing a sequence of nodes with length proportional to the number of bits in the address. The Luleå algorithm shortcuts this process by storing only the nodes at three levels of the trie structure, rather than storing the entire trie.
The main advantage of the Luleå algorithm for the routing task is that it uses very little memory, averaging 4–5 bytes per entry for large routing tables. This small memory footprint often allows the entire data structure to fit into the routing processor's cache, speeding operations. However, it has the disadvantage that it cannot be modified easily: small changes to the routing table may require most or all of the data structure to be reconstructed.
First level
The first level of the data structure consists of- A bit vector consisting of 216 = 65536 bits, with one entry for each 16-bit prefix of an IPv4IPv4Internet Protocol version 4 is the fourth revision in the development of the Internet Protocol and the first version of the protocol to be widely deployed. Together with IPv6, it is at the core of standards-based internetworking methods of the Internet...
address. A bit in this table is set to one if there is routing information associated with that prefix or with a longer sequence beginning with that prefix, or if the given prefix is the first one associated with routing information at some higher level of the trie; otherwise it is set to zero.
- An array of sixteen-bit words for each nonzero bit in the bit vector. Each datumDatumA geodetic datum is a reference from which measurements are made. In surveying and geodesy, a datum is a set of reference points on the Earth's surface against which position measurements are made, and an associated model of the shape of the earth to define a geographic coordinate system...
either supplies an index that points to the second-level data structure object for the corresponding prefix, or supplies the routing information for that prefix directly.
- An array of "base indexes", one for each consecutive subsequence of 64 bits in the bit vector, pointing to the first datum associated with a nonzero bit in that subsequence.
- An array of "code words", one for each consecutive subsequence of 16 bits in the bit vector. Each code word is 16 bits, and consists of a 10-bit "value" and a 6-bit "offset". The sum of the offset and the associated base index gives a pointer to the first datum associated with a nonzero bit in the given 16-bit subsequence. The 10-bit value gives an index into a "maptable" from which the precise position of the appropriate datum can be found.
To look up the datum for a given address x in the first level of the data structure, the Luleå algorithm computes three values:
- the base index at the position in the base index array indexed by the first 10 bits of x
- the offset at the position in the code word array indexed by the first 12 bits of x
- the value in maptable[y][z], where y is the maptable index from the code word array and z is bits 13–16 of x
The sum of these three values provides the index to use for x in the array of items.
Second and third levels
The second and third levels of the data structure are structured similarly to each other; in each of these levels the Luleå algorithm must perform prefix matching on 8-bit quantities (bits 17–24 and 25–32 of the address, respectively). The data structure is structured in "chunks", each of which allows performing this prefix matching task on some subsequence of the address space; the data items from the first level data structure point to these chunks.If there are few enough different pieces of routing information associated with a chunk, the chunk just stores the list of these routes, and searches through them by a single step of binary search followed by a sequential search. Otherwise, an indexing technique analogous to that of the first level is applied.