Fast scaleable methods and devices for layer four switching

• US 6,212,184 B1
• Filed: 07/15/1998
• Issued: 04/03/2001
• Est. Priority Date: 07/15/1998
• Status: Expired due to Term

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Venkatachary, Srinivasan, Suri, Subhash, Varghese, George, Waldvogel, Marcel, Adiseshu, Hari
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/115,886
• Time in Patent Office: 993 Days
• Field of Search: 370/238, 370/408, 370/392, 370/401, 370/393, 370/402, 370/403, 370/404, 370/405, 370/466, 370/467, 711/202, 711/216, 709/239, 709/241, 340/825.02, 714/819
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

Fast, scalable methods and devices are provided for layer four switching in a router as might be found in the Internet. In a first method, a grid of tries, which are binary branching trees, is constructed from the set of routing filters. The grid includes a dest-trie and a number of source tries. To avoid memory blowup, each filter is stored in exactly one trie. The tries are traversed to find the lowest cost routing. Switch pointers are used to improve the search cost. In an extension of this method, hash tables may be constructed that point to grid-of-tries structures. The hash tables may be used to handle combinations of port fields and protocol fields. Another method is based on hashing, in which searches for lowest cost matching filters take place in bit length tuple space. Rectangle searching with precomputation and markers are used to eliminate a whole column of tuple space when a match occurs, and to eliminate the rest of a row when no match is found. Various optimizations of these methods are also provided. A router incorporating memory and processors implementing these methods is capable of rapid, selective switching of data packets on various types of networks, and is particularly suited to switching on Internet Protocol networks.

Claims

1. A method for routing a data packet through an electronic routing device having an input data link and a plurality of output data links, the data packets having at least a first field and a second field, the method comprising:

a) searching a first trie in a memory of the electronic routing device for a record containing a longest prefix match of the first field of the data packet;

b) searching a second trie associated with the longest prefix matching record of the first trie for a record containing a lowest cost match of the second field of the data packet; and

c) routing the data packet on an output data link corresponding to the lowest cost matching record.

2. The method of claim 1 wherein the step of searching a first trie includes the step of searching a multi-bit trie.

3. The method of claim 1, wherein the data packet comprises at least one additional field, and wherein there are a plurality of first tries and a plurality of hash tables in a memory of the router, the hash tables containing entries referencing individual ones of the first tries and being indexed by entries of the at least one additional field;

and further comprising;

searching each of the hash tables for a matching entry to the at least one additional field;

searching each grid-of-tries referenced by the matching entries in each hash table for a lowest cost match corresponding to each hash table;

selecting a final lowest cost match of all of the lowest cost matches found; and

routing the data packet to the output data link corresponding to the final lowest cost match of the lowest cost matches.

4. The method of claim 3, further comprising searching a default database for an additional lowest cost match.

5. A method for routing a data packet through an electronic routing device having an input data link and a plurality of output data links, the data packets having at least a first field and a second field, wherein each record of a first trie corresponding to a prefix match of the first field of the data packet references an associated second trie containing only records corresponding to filters exactly matching the prefix match of the first field, the method comprising:

a) searching the first trie in a memory of the electronic routing device for a record containing a prefix match of a first field of the data packet;

b) searching a second trie associated with the record found in step (a) for a record containing a minimum cost match of a second field of the data packet, the record containing a reference to one of the output data links;

c) repeating steps (a) and (b) until all of the matching prefixes in the first trie and the corresponding minimum cost matches of the second field of the data packet are found;

d) selecting the lowest cost match of the minimum cost matches; and

e) routing the data packet to the output data link referenced by the record which is the lowest cost match.

6. The method of claim 5 wherein the repeating step comprises backtracking up the first trie.

7. The method of claim 6 wherein at least one of the second tries (T2A) associated with a record (R1) in the first trie comprises at least one record containing a switch pointer pointing to a second trie (T2B) having a top record associated with ancestor record (R2) in the first trie, and the step of backtracking up the first trie comprises following the switch pointer from trie T2A to trie T2B.

8. A method for routing a data packet through an electronic routing device having an input data link and a plurality of output data links, the data packets having at least a first field and a second field, the method comprising:

a) mapping a filter database B comprising N filters, into a rectangular hash table T, where each entry T[i,j] contains all filters F matching i symbols of the first field and j symbols of the second field of a data packet, and includes records containing associated costs for the filters F;

b) for each pair of values i and j in hash table T;

extracting i symbols from the first field of the data packet and j symbols from the second field of the data packet, finding a matching entry in hash table T corresponding to a filter matching the i symbols of the first field and the j symbols of the second field of the data packet and determining the cost associated with each matching filter;

c) selecting the matching filter having the least cost; and

d) routing the data packet to the data link corresponding to the selected matching filter having the least cost.

9. A method for routing a data packet through an electronic routing device having an input data link and a plurality of output data links, the data packets having at least a first field and a second field, the data packets being routed in accordance with preselected routing filters each having an associated cost and output data link, the method comprising:

a) selecting a lower left corner tuple of a rectangle of tuples having r rows and c columns, the selected tuple becoming a current tuple;

b) searching for a filter keyed by bits of fields of the data packet corresponding to the current tuple;

c) until a first row or last column is reached, selecting a next tuple of the rectangle of tuples in an adjacent row above and in a same column as the current tuple when the searching step is unsuccessful, and selecting a next tuple of the rectangle of tuples in the same row as, and in an adjacent column to the right of the current tuple if the search is successful, wherein the current tuple ceases to be the current tuple and the selected tuple thereby becomes the current tuple;

d) selecting a filter of those found in the searching step having a lowest associated cost; and

e) routing the data packet to the output data link corresponding to the filter selected in the filter selecting step.

10. The method of claim 9 and further comprising precomputing the rectangle of tuples so each tuple in the rectangle is more specific than any other tuples in the rectangle of tuples that are both to its right and below it.

11. The method of claim 10, and further comprising precomputing and storing, in association with each tuple T containing at least one filter and having at least one tuple in the rectangle of tuples to the upper left of tuple T, a filter of least cost of all filters to the upper left of tuple T containing at least one filter.

12. The method of claim 11, wherein searching for a filter comprises searching a hash table keyed by a concatenation of a number of bits of fields of the data packet corresponding to the current tuple.

13. The method of claim 12, wherein a set of all lengths of all the filters in the hash table forms a proper subset of all possible lengths.

14. The method of claim 11, and further comprising:

constructing a first field hash table in memory, the first field hash table having records containing expanded prefixes of matching first fields in the filters;

constructing second field hash tables in memory, the hash tables each containing expanded prefixes of matching second fields in the filters, each second field hash table containing records reflecting lowest cost matching filters corresponding to records in the first field hash table; and

associating pointers with each record in the first field hash table to a corresponding second field hash table containing lowest cost matching filters for the record in the first field hash table;

and wherein the searching for a filter comprises searching the first field hash table for a match to a first field of the data packet, and searching the second field hash table pointed to by the pointer associated with the match in the first field hash table for a match to a second field of the data packet corresponding to a lowest cost filter.

15. The method of claim 14, wherein a set of all lengths of all the filters in the hash tables form a proper subset of all possible lengths.

16. The method of claim 15, wherein the data packet is an Internet data packet in accordance with Internet Protocol (IP), the first field is a destination field and the second field is a source field.

17. A method for routing a data packet through an electronic routing device having an input data link and a plurality of output data links, the data packets having at least a first field and a second field, the data packets being routed in accordance with preselected routing filters each having an associated cost and output data link, the method comprising:

a) selecting a lower left corner tuple of a rectangle of tuples having r rows and c columns, the selected tuple becoming a current tuple;

b) searching for a filter keyed by bits of fields of the data packet corresponding to the current tuple;

c) until a first row or last column is reached, selecting a next tuple of the rectangle of tuples in a row above and in a same column as the current tuple when the searching step is unsuccessful, and selecting a next tuple of the rectangle of tuples in the same row as, and in a column to the right of the current tuple in accordance with a rope value associated with the current tuple when the searching step is successful, wherein the current tuple ceases to be the current tuple and the selected tuple thereby becomes the current tuple;

d) selecting a filter of those found in the searching step having a lowest associated cost; and

e) routing the data packet to the output data link corresponding to the filter selected in the filter selecting step.

18. A method of routing a data packet using a set of filters that are based upon bit fields within the data packet, the bit fields including a destination field and a source field, each filter also specifying, or having been replicated so as to specify, a specific value of protocol field, and each filter also specifying an output port and having an associated cost, the method comprising:

a) dividing the set of filters into four groups, a first group of filters consisting of filters specifying neither a source field value nor a destination field value;

a second group of filters consisting of filters specifying a destination field value but no source field value, a third group of filters consisting of filters specifying a source field value but no destination field value, and a fourth group of filters specifying both a source field value and a destination value;

b) for each group of filters, constructing a corresponding hash table storing, as records, all source field value and destination field value combinations in the group, including concatenated protocol field specifications;

c) for each record in the hash tables, storing a pointer to a grid of tries data structure including a plurality of tries storing all filters matching the record;

d) for each data packet received, searching each of the hash tables for a match to a record keyed to the bit fields within the data packet;

e) for each matching hash table record, searching the trie pointed to for a matching entry for the destination field value and source field value of the data packet;

f) routing the packet to the data port specified by the filter corresponding to a matching entry found in the searches of the grid of tries having a lowest cost.

19. The method of claim 18, wherein the grids of tries comprises nodes including switch pointers, and searching the grid of tries comprises:

updating a best matching filter cost variable in memory whenever a match is found at a node in the searched trie;

searching down the searched trie for a longer match to the destination field value and source field value until the searched trie terminates; and

when searching does the searched tries fails to provide a longer match, searching a trie pointed to by a switch pointer associated with the last matched node in the searched trie.

20. A method of routing a data packet using a set of filters that are based upon bit fields within the data packet, the bit fields including a destination field and a source field, each filter also specifying, or having been replicated so as to specify, a specific value of protocol field, and each filter also specifying an output port and having an associated cost, the method comprising:

a) dividing the set of filters into four groups, a first group of filters consisting of filters specifying neither a source field value nor a destination field value;

a second group of filters consisting of filters specifying a destination field value but no source field value, a third group of filters consisting of filters specifying a source field value but no destination field value, and a fourth group of filters specifying both a source field value and a destination field value;

b) constructing rectangular databases of tuples, one for each of the four groups of filters, the rows and columns of the rectangles corresponding to a number of bits of the destination field, source port field, protocol field, and port numbers that form a hash key for searching a tuple at a specified row and column;

c) associating each filter to a unique one of the tuples;

d) associating a precomputed stored cost and stored filter for each filter in each tuple; and

e) for each received data packet, and for each rectangular database of tuples starting at a last row and first column of each rectangular database of tuples, performing a rectangular search for a lowest cost matching filter;

f) selecting, of the lowest cost matching filters found corresponding to each rectangular database of tuples, the one of these matching filters having the lowest cost; and

g) routing the data packet in accordance to the matching filter selected in step f) above.

21. A device for routing a data packet having at least a first and a second field, the device comprising:

an input data link at which the input data packet arrives;

a plurality of output data links;

memory containing a first trie of records and a set of second tries of records associated with records of the first trie;

means coupled to the input data link for receiving the data packet and for searching the first trie of records in memory for a record having a longest prefix match of the first field of the data packet;

means, responsive to the means for receiving and for searching the first trie of records, for searching a second trie of records in memory associated with the matched record in the first trie of records for a lowest cost match of the second field of the data packet;

and means, responsive to the means for searching a second trie of records, for routing the data packet to the output data link corresponding to the lowest cost match.

22. A device for routing a data packet having at least a first and a second field, the device comprising:

an input data link at which the data packet arrives;

a plurality of output data links;

memory containing a first trie of records and a set of second tries of records associated with records of the first trie, with records in the set of second tries including references to output data links;

first means coupled to the input data link for receiving the data packet and for searching the first trie in the memory for a record containing a prefix match of the first field in the data packet;

second means, responsive to the first means, for searching a second trie associated with the record, found by the first means, to find a record containing a minimum cost match of the second field in the data packet and a reference to one of the output data links;

third means, coupled to the first means and the second means, for causing the first and second means to repeat their respective functions until all matching prefixes in the first trie and corresponding minimum cost matches of the second field of the data packet are found;

fourth means, responsive to the second means, for selecting the lowest cost match of the minimum cost matches and for selecting the corresponding reference to one of the output data links; and

fifth means, responsive to said fourth means, for routing the data packet to the output data link referenced by the lowest cost match of the minimum cost matches.

23. The device of claim 22, wherein at least one of the second tries (T2A) associated with a record (R1) in the first trie comprises at least one record containing a switch pointer pointing to a second trie (T2B) having a top record associated with ancestor record (R2) in the first trie, and further wherein:

the third means comprises means for backtracking up the first trie including means for following the switch pointer from trie T2A to trie T2B.

24. A device for routing a data packet having at least a first field and a second field, the device comprising:

an input data link;

a plurality of output data links;

memory for a routing database;

first means for mapping a filter database B comprising N filters into a rectangular hash table T in the memory, where each entry T[i,j] contains all filters F matching i symbols of the first field and j symbols of the second field of a data packet, including records containing associated costs for the filters of F;

second means coupled to the input data link and the memory for receiving the data packet and, for each pair of values i and j in hash table T in memory, extracting i symbols from the first field of the data packet and j symbols from the second field of the data packet and finding a matching entry in hash table T corresponding to a filter matching the i symbols of the first field and the j symbols of the second field of the data packet and determining the cost associated with each matching filter;

third means, responsive to the second means, for selecting the matching filter having the least cost; and

fourth means, responsive to the third means, for routing the data packet to the data link corresponding to the matching filter selected by the third means as having the least cost.

25. A device for routing a data packet having at least a first field and a second field, the device comprising:

an input data link at which the data packet arrives;

a plurality of output data links;

memory for a routing database containing a rectangle of tuples having r rows and c columns and associated filters;

first means for selecting tuples of the rectangle of tuples, initially a lower left corner tuple;

second means, coupled to the first means, the memory, and the input data link, for receiving the data packet and for searching the memory for a filter keyed by bits of fields of the data packet corresponding to the current tuple;

third means, coupled to the first means and responsive to the second means, for causing the first means to select a next tuple of the rectangle of tuples in an adjacent row above and in a same column as a previously selected tuple when the searching performed by the second means is unsuccessful, and for causing the first means to select a next tuple of the rectangle of tuples in the same row as, and in an adjacent column to the right of the previously selected tuple when the searching performed by the second means is successful;

fourth means, coupled to the second means, for selecting a filter found by the second means having a lowest associated cost; and

fifth means, responsive to the fourth means, for routing the data packet to an output data link corresponding to the filter selected by the fourth means.

26. A device for routing a data packet having at least a first field and a second field, the device comprising:

an input data link at which the data packet arrives;

a plurality of output data links;

memory for a routing database containing a rectangle of tuples having r rows and c columns and associated filters;

first means for selecting tuples of the rectangle of tuples, initially a lower left corner tuple;

second means, coupled to the first means, the memory, and the input data link, for receiving the data packet and for searching the memory for a filter keyed by bits of fields of the data packet corresponding to the current tuple;

third means, coupled to the first means and responsive to the second means, for causing the first means to select a next tuple of the rectangle of tuples in a row above and in a same column as a previously selected tuple when the searching performed by the second means is unsuccessful, and for causing the first means to select a next tuple of the rectangle of tuples in the same row as, and in a column to the right of the previously selected tuple when the searching performed by the second means is successful;

fourth means, coupled to the second means, for selecting a filter found by the second means having a lowest associated cost; and

fifth means, responsive to the fourth means, for routing the data packet to an output data link corresponding to the filter selected by the fourth means.

27. A device for routing a data packet having bit fields, the bit fields including a destination field, and a source field, the device comprising:

an input data link at which the data packet arrives;

a plurality of output data links;

memory containing a set of filters, each filter either specifying or being replicated so as to specify a specific value of a protocol field, an output port, and an associated cost, and also containing a grid-of-tries data structure including a plurality of tries storing all of the filters;

first means coupled to the memory for dividing the set of filters in memory into four groups in memory, including a first group of filters consisting of filters specifying neither a source field value nor a destination field value, a second group of filters consisting of filters specifying a destination field value but no source field value, a third group of filters consisting of filters specifying a source field value but but no destination field value, and a fourth group of filters specifying both a source field value and a destination value;

second means, coupled to the memory, for constructing in memory, for each group of fields, a corresponding hash table of records of all source field value and destination field value combinations in the group, including concatenated protocol field specifications;

third means, coupled to the memory, for storing, for each record in the hash tables, a pointer to the grid of tries data structure including a plurality of tries storing all filters matching the record;

fourth means, coupled to the input data port and the memory, for searching each of the hash tables for a match to a record keyed by the bit fields within the data packet;

fifth means, coupled to the fourth means and the memory, for searching in memory, for each matching hash table record found by the fourth means, the trie pointed to by the hash table record for a matching entry for the destination field value and source field value of the data packet; and

sixth means, coupled to the fifth means and the input data link, for routing the packet to the data port specified by the filter corresponding to a matching entry found in the searches of the grid of tries having a lowest cost.

28. A device for routing a data packet having bit fields, the bit fields including a destination field, and a source field, the device comprising:

an input data link at which the data packet arrives;

a plurality of output data links;

memory containing a set of filters, each filter either specifying or being replicated so as to specify a specific value of a protocol field, an output port, and an associated cost, and also containing a grid-of-tries data structure including a plurality of tries storing all of the filters;

first means coupled to the memory for dividing the set of filters in memory into four groups in memory, including a first group of filters consisting of filters specifying neither a source field value nor a destination field value, a second group of filters consisting of filters specifying a destination field value but no source field value, a third group of filters consisting of filters specifying a source field value but but no destination field value, and a fourth group of filters specifying both a source field value and a destination value;

second means, coupled to the memory, for constructing in memory, for each group of fields, a rectangular database of tuples, the rows and columns of the rectangles corresponding to a number of bits of the destination field, source port field, protocol field, and port numbers that form a hash key for searching a tuple at a specified row and column;

third means coupled to the memory for associating each filter in memory to a unique one of the tuples;

fourth means coupled to the memory for associating a precomputed stored cost and stored filter for each filter in each tuple;

fifth means, coupled to the input data link and the memory, for performing, for each received data packet and for each rectangular database of tuples starting at a last row and first column, a rectangular search for a lowest cost matching filter;

sixth means, coupled to the fifth means, for selecting, of the lowest cost matching filters found by the fifth means corresponding to each rectangular database of tuples, the one of these matching filters having the lowest cost; and

seventh means, coupled to the input data link and the sixth means, for routing the data packet in accordance to the matching filter found by the sixth means.