Filtering and route lookup in a switching device

Patent metadata

Field	Value
Publication number	US-9813339-B2
Application number	US-201514985081-A
Country	US
Kind code	B2
Filing date	Dec 30, 2015
Priority date	Apr 17, 2000
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Methods and devices for processing packets are provided. The processing device may include an input interface for receiving data units containing header information of respective packets; a first module configurable to perform packet filtering based on the received data units; a second module configurable to perform traffic analysis based on the received data units; a third module configurable to perform load balancing based on the received data units; and a fourth module configurable to perform route lookups based on the received data units.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a device, a data packet;
dividing, by the device, the data packet into data units;
transferring, by the device, the data units to an input switch of the device;
extracting, by the input switch of the device, key information from the data units;
storing, by the input switch of the device, the key information in a buffer;
routing, by the input switch of the device, the data units to memory banks;
sending, by the device, a lookup request to a controller of the device,
the lookup request comprising the key information;

generating, by the controller of the device, destination information based on the lookup request,
generating the destination information including:
performing, by the controller of the device, a plurality of chained lookup operations,
the plurality of chained lookup operations including a filtering operation, and

generating, by the controller of the device, the destination information based on performing the plurality of chained lookup operations;

sending, by the controller of the device, the destination information to an output switch; and
transferring, by the device, the data units from the memory banks to the output switch.

2. The method of claim 1 , where routing the data units to the memory banks comprises:
routing the data units in a time division multiplexed manner.

3. The method of claim 1 , further comprising:
computing, by the device, offsets for the data units routed to the memory banks,
the offsets indicating next contiguous memory banks into which next data units are to be written.

4. The method of claim 3 , further comprising:
determining, by the device, a length of the data packet; and
creating, by the device, indirect data units when the length of the data packet exceeds a threshold,
where creating the indirect data units when the length of the data packet exceeds the threshold comprises:
storing old indirect data units in the memory banks, and
creating new indirect data units based on the offsets.

5. The method of claim 1 , where the destination information comprises at least one of:
a destination port,
an address,
offset information, or
a next hop index.

6. The method of claim 1 , where transferring the data units from the memory banks to the output switch comprises:
transferring a data unit, of the data units, to each of a plurality of multi-function multiports.

7. The method of claim 1 , where transferring the data units from the memory banks to the output switch comprises:
issuing read requests to the memory banks in a time division multiplexed fashion.

8. A device, comprising:
a multi-function multiport to:
receive a data packet,
divide the data packet into data units,
transfer the data units to an input switch;

the input switch to:
extract key information from the data units,
store the key information in a buffer,
route the data units to memory banks, and
compute offset information associated with the data units in the memory banks; and

a controller to:
receive a lookup request,
the lookup request including the key information and the offset information,

perform, based on the lookup request, a plurality of chained lookup operations,
the plurality of chained lookup operations including a filtering operation,

generate, based on performing the plurality of chained lookup operations, destination information based on the lookup request, and
send the destination information to an output switch,
the data units being transferred from the memory banks to the output switch.

9. The device of claim 8 , where, when computing the offset information associated with the data units in the memory banks, the input switch is to:
compute an offset between a data unit, of the data units, and a next contiguous memory bank.

10. The device of claim 8 , where the input switch is further to:
determine a length of the data packet,
indirect data units being created when the length of the data packet exceeds a threshold; and
determine whether a number of data units exceeds a number of available offsets in an indirect data unit of the indirect data units,
storing an old indirect data unit in the memory banks when the number of data units exceeds the number of available offsets in the indirect data unit, and
creating a new indirect data unit based on the offset information when the number of data units exceeds the number of available offsets in the indirect data unit.

11. The device of claim 8 , where, when sending the destination information to the output switch, the controller is to:
transfer multi-function multiport identifiers to the output switch with the data units.

12. The device of claim 11 , where the output switch is further to:
transfer a single data unit to each of one or more destination multi-function multiports.

13. The device of claim 12 , where the one or more destination multi-function multiports are to:
couple the single data unit with media header information; and
stream the single data unit to a destination.

14. The device of claim 8 , where the input switch is further to:
issue read requests to the memory banks,
the read requests being issued as one request per data unit in the memory banks; and
where, when transferring the data units from the memory banks to the output switch, the memory banks are to:
receive the read requests, and
transfer the data units and multi-function multiport identifiers based on the read requests.

15. A system comprising:
a device including memory banks and a plurality of components, the plurality of components to:
receive a data packet;
divide the data packet into fixed length data units;
extract key information from the fixed length data units;
store the key information in a buffer;
route the fixed length data units to the memory banks;
compute offset information associated with the fixed length data units in the memory banks;
determine a length of the data packet,
indirect data units being created when the length of the data packet exceeds a threshold;

determine whether a quantity of the fixed length data units exceeds a quantity of offsets in a first indirect data unit of the indirect data units,
a second indirect data unit being created based on the offset information when the quantity of the fixed length data units exceeds the quantity of offsets in the first indirect data unit;

generate a lookup request,
the lookup request comprising the key information and the offset information;

perform, based on the lookup request, a plurality of chained lookup operations,
the plurality of chained lookup operations including a filtering operation;

generate, based on performing the plurality of chained lookup operations, destination information based on the lookup request;
send the destination information to an output switch; and
transfer the fixed length data units from the memory banks to the output switch.

16. The system of claim 15 , where, when creating the second indirect data unit based on the offset information, the plurality of components is to:
store the first indirect data unit;
associate the offset information with new data units received at an input switch; and
create the second indirect data unit based on the offset information.

17. The system of claim 15 , where, when computing the offset information, the plurality of components is to:
associate offsets with next contiguous memory banks.

18. The system of claim 15 , where, when determining the length of the data packet, the

Assignees

• Juniper Networks Inc

Inventors

• Ferguson Dennis C
• Patel Rajiv
• Cheung Gerald
• Sindhu Pradeep

Classifications

• H04L47/10

  Flow control; Congestion control · CPC title

• H04L47/20

  Traffic policing · CPC title

• H04L45/745 Primary

  Address table lookup; Address filtering · CPC title

• H04L63/1458

  Denial of Service · CPC title

• H04L45/00

  Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) · CPC title