Packet forwarding method and system
View Patent ↗Forwarding decisions for Internet Protocol packets/frames are provided. An IP address from received packets/frames is extracted and split into portions or parts, a prefix, offset and suffix. A prefix table is used to identify an entry with a longest match to the prefix. A base address is retrieved from the identified entry to generate an identifier used to locate another entry in another table. The other identified entry provides receiver data or information regarding the intended destination.
1. A method of determining receiver data by a networking device, the method comprising:
receiving information conforming to an Internet Protocol (IP) on an ingress router leg of the networking device;
extracting an IP address from the information;
identifying, by the networking device, an entry in a first table having a plurality of entries each comprising a destination IP address including a prefix and an offset, a first value corresponding to a number of bits of the destination IP address that are in the prefix indicating the length of the prefix, a second value corresponding to a number of bits in the offset indicating the length of the offset, and a base address, the entries being organized according to the length of the prefix and the identified entry having the longest prefix matching at least a portion of the extracted IP address;
generating, by the networking device, an entry identifier by performing a predetermined mathematical operation on the base address of the identified entry and a portion of the IP address defined by the prefix length and the offset length of the identified entry;
locating, by the networking device, an entry in a second table at the generated entry identifier;
extracting, by the networking device, receiver data from the located entry in the second table; and
supplying the information conforming to the Internet Protocol to an egress router leg of the networking device based on the receiver data.
2. The method of claim 1 wherein each prefix is stored in a location having a same number of bits and the first value indicating the length of the prefix indicates the number of bits in the prefix used in the identifying the entry in the first table.
3. The method of claim 1 wherein the identifying the entry in the first table comprises comparing a number of bits in the IP address indicated by the prefix length to the prefix.
4. The method of claim 3 wherein the comparing utilizes bits positioned at a beginning of the IP address.
5. The method of claim 4 wherein the generating the entry identifier utilizes the second value indicating the length of the offset of the identified entry positioned immediately after the first value indicating the length of the prefix of the identified entry.
6. The method of claim 1 wherein the predetermined mathematical operation is addition.
7. The method of claim 1 further comprising extracting data describing one of a Destination Media Access Control address (DMAC) and a destination port from the located entry in the second table.
8. The method of claim 1 further comprising identifying at least one of a Source Media Access Control address (SMAC) and a Virtual Local Area Network Identification (VID).
9. The method of claim 8 further comprising identifying the at least one of the SMAC and the VID in an entry in a third table by using an identifier in the located entry in the second table.
10. The method of claim 9 further comprising editing the information to include at least one of a Destination Media Access Control address (DMAC), the SMAC, and the VID.
11. The method of claim 10 further comprising:
deriving additional information from the information; and
identifying in a fourth table an entry having data fields that correspond to the additional information.
12. The method of claim 11 wherein the additional information comprises at least one of the DMAC and the VID.
13. The method of claim 12 further comprising determining handling of the information from the identified entries in the third and fourth tables.
14. The method of claim 13 wherein the determined handling of the information comprises at least one of deleting the information, outputting the information, analyzing the information, performing statistical analysis on the information and related information, and alerting an operator.
15. The method of claim 1 further comprising:
reserving a number of entries in the second table for a predetermined use,
identifying entries in the first table where a result of the predetermined mathematical operation performed on the base address of the entry and a corresponding portion of the IP address lies within the reserved entries, and
altering the base addresses in the identified entries so that a result of the predetermined mathematical operation performed on the altered base address of the entry and a possible corresponding portion of the IP address falls outside the reserved entries of the second table.
16. The method of claim 15 wherein the predetermined use is multicasting.
17. The method of claim 1 wherein each entry in the first table further comprises a valid field and where the identifying the entry in the first table only identifies entries having a valid field value indicating a valid entry.
18. The method of claim 1 wherein the plurality of entries in the first table are arranged according to prefix length.
19. The method of claim 1 wherein the first table includes a default entry having a first value indicating a length of zero and that matches all values of the extracted IP address.
20. The method of claim 1 wherein the portion of the IP address defined by the prefix length and the offset length of the identified entry is a number bits indicated by the offset of the identified entry that are disjunctive from the bits of the extracted IP address matched to the prefix of the identified entry.