Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-12-16
2004-05-04
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C709S238000, C711S202000
Reexamination Certificate
active
06731643
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for routing information packets associated to addresses represented through numerical strings, in routing apparatus, utilized in telecommunication networks, receiving at their input information packets and routing said packets on a plurality of outputs, said method comprising the steps of:
building a first set of numerical strings with variable length, contained in an address table being sorted and associated to a set of references at the outputs, said set of references at the outputs being inserted in a sorted mapping table;
comparing a first address incoming at the input with said first set of numerical strings according to a longest prefix match principle and using a binary search as a method for performing the comparison.
2. Description of the Prior Art
The “longest prefix match” problem occurs in many applications in communication networks, such as a recovery of routing information in switches or ATM (Asynchronous Transfer Mode) switches and in IP (Internet Protocol) networks routers.
For instance, an IP router is an apparatus receiving at its input packets provided with address and routing them according to their address on its various output ports, which will then address them towards various “host computers” or sets of “host computers”. Each “host computer” or router in Internet has an IP address, which codes the number defining the pertaining network and the number defining the computer itself. The configuration originating the IP address is unique and two machines cannot share the same IP address. IP addresses have a 32-bit length and are inserted in the source address and destination address fields of IP packets.
IP addresses are divided, for instance, in four fields with each field being of 8 bits, so that an IP address will be typically expressed with values ranging from 0.0.0.0 to 255.255.255.255.
Each router contains a table inside. Said table contains a list of IP addresses corresponding to a table containing a list of output ports leading to other routers or other host computers.
FIG. 1
shows a basic diagram of a router R according to the known state of the art. A packet PK structured according to Internet Protocol reaches an input port INP. An address A representing one of the available IP addresses, contained in said packet PK, is extracted and sent to an address table T
1
corresponding to an output port mapping table TM. The address table T
1
contains an original set of strings SN, i.e. numerical strings representing addresses, whereas the mapping table TM contains a set of references SP associated to output ports OP. The address table T
1
and the mapping table TM may take for instance the values shown in the Table 1 which is here below.
Values 128, 128.3.4 and 128.0.1.2 indicated therein form an original set of strings SN, while
0
,
1
and
2
represent the references SP associated with the output ports OP.
TABLE 1
T1
TM
128.
0
128.3.4
1
128.0.1.2
2
Considering the above division of IP addresses in 8-bit fields, the length L of the numerical strings ranges from a minimum 8-bit length LMIN to a maximum 32-bit length LMAX. Moreover, it can be noticed that the address A always has a 32-bit length, equal to the maximum length LMAX provided by the system.
A search is usually performed on the original set of strings SN utilizing the well-known longest prefix match criterion, so as to compare each string SN with the address A. A prefix with length L of a numerical string SN means a sequence equal to the first L-bits of the numerical string SN.
Several search methods by the longest prefix match criterion have been suggested. The most obvious one provides a sequential scanning of the whole original set of strings SN contained in the address table T
1
, comparing every element of it with the address A incoming at the input port INP and storing the longest match which is obtained. It is obvious that the complexity of a method of this kind is depending linearly on the number of strings available in the search set contained in the address table T
1
, resulting in its restricted usefulness when such a number of strings increases or in applications requiring an extremely high search speed. Other methods use special data arrangements, such as tree structures. Thus, calculation complexity can be reduced, although the need of using the so-called back-tracking techniques, i.e. storing the choices performed along the path in the tree structure, will considerably reduce the advantages of such a technique. Also the managing and updating difficulties of the data structures employed should be added.
A most efficient method for a complete match search is based on the well-known binary search, also called dichotomy search: once the set of strings to be used for performing the search is sorted, said method allows to check either the presence or absence of a value with a complexity O(log
2
N), where N is the cardinality of the search set. The binary search method will loose much of its efficiency whenever it is used to calculate the longest prefix match; however, there is a possibility of sorting the search set in more subsets according to the length of the numerical strings and carry out more binary searches on such subsets. Such an approach has the drawback of requiring more search iterations to reach the desired result.
SUMMARY OF THE INVENTION
It is the object of the present invention to solve the above drawbacks and provide a method for routing information packets associated to addresses represented through numerical strings, in routing apparatuses, utilized in telecommunication networks, receiving at their input information packets and routing said packets on a plurality of outputs, said method having a more efficient and improved performance.
In this frame, it is the main object of the present invention to provide a method for routing information packets associated to addresses represented through numerical strings, in routing apparatuses, utilized in telecommunication networks, receiving at their input information packets and routing said packets on a plurality of outputs, said method using a binary search procedure for calculating the longest prefix match without requiring repeated iterations of said binary search procedure.
In order to achieve such objects, the present invention provides a method for routing information packets associated to addresses represented through numerical strings, in routing apparatuses, utilized in telecommunication networks, which receive at their input information packets and route said packets on a plurality of outputs, and/or an apparatus of routing information packets in telecommunication networks, incorporating the features of the annexed claims, which form an integral part of the description herein.
Further objects, features and advantages of the present invention will become apparent from the following detailed description and annexed drawings, which are provided by way of exemplifying and non limiting example,
REFERENCES:
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5488608 (1996-01-01), Flammer, III
patent: 5613069 (1997-03-01), Walker
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6385649 (2002-05-01), Draves et al.
patent: 6434144 (2002-08-01), Romanov
patent: 6522632 (2003-02-01), Waters et al.
patent: 6526055 (2003-02-01), Perlman
Cucchi Silvio
Perissinotto Cristian
Alcatel
Phunkulh Bob A.
LandOfFree
Method and apparatus for routing information packets... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for routing information packets..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for routing information packets... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3208856