Method network flow switching and flow data export

• US 20050027506A1
• Filed: 08/23/2004
• Published: 02/03/2005
• Est. Priority Date: 05/28/1996
• Status: Active Grant

• Current Assignee: Barry L. Bruins, Darren R. Kerr
• Original Assignee: Barry L. Bruins, Darren R. Kerr
• Inventors: Bruins, Barry L., Kerr, Darren R.
• Granted Patent: US 7,260,518 B2
• Time in Patent Office: Days
• US Class Current: 703/27
• 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/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The invention provides a method and system for switching in networks responsive to message flow patterns. A message “flow” is defined to comprise a set of packets to be transmitted between a particular source and a particular destination. When routers in a network identify a new message flow, they determine the proper processing for packets in that message flow and cache that information for that message flow. Thereafter, when routers in a network identify a packet which is part of that message flow, they process that packet according to the proper processing for packets in that message flow. The proper processing may include a determination of a destination port for routing those packets and a determination of whether access control permits routing those packets to their indicated destination.

Claims

1. A method in a router for determining how to treat packets, comprising the steps of:

determining a flow and a flow key for a first packet;

performing a first lookup in a flow cache based on the flow key, with the flow determined to be old if the first lookup is successful and determined to be new if the first lookup is unsuccessful;

if the flow is old, using a result of the first lookup to determine how to treat the first packet;

if the flow is new, performing a second lookup in an IP address cache and using a result of the second lookup to determine how to treat the packet and to make a first entry for the flow in the flow cache such that if a next packet in the flow is received, the flow is identified as old, and the next packet is treated in a same manner as the first packet; and

maintaining the flow cache by collecting and recording information about the flow in the flow cache when the flow is new.

2. The method as in claim 1, further comprising reserving specific amounts of bandwidth for the flow, if the flow is new.

3. The method as in claim 1, further comprising creating and storing usage information specifying accesses using HTTP protocol to World Wide Web pages at particular sites, based on the flow. (page 14-15)

4. The method as in claim 1, further comprising giving priority to the flow if the flow is old and if the flow uses fewer network resources, based on a threshold value specifying an amount of network resources used, than another flow.

5. The method as in claim 1, wherein maintaining the flow cache includes:

examining a second entry in the flow cache corresponding to a particular flow;

comparing a current time with a first time a particular packet, in the particular flow corresponding to the second entry, was routed; and

if the difference between the current time and the first time exceeds a selected timeout, deleting the first entry from the flow cache.

6. The method as in claim 1, wherein maintaining the flow cache includes:

examining a second entry in the flow cache corresponding to a particular flow;

determining that “

next hop”

information in the second entry has changed; and

deleting the second entry from the flow cache.

7. The method as in claim 1, wherein maintaining the flow cache includes:

examining a second entry in the flow cache corresponding to a particular flow; and

deleting the second entry from the flow cache if the second entry indicates that changes in access control lists have occurred such that a source endpoint associated with the packet no longer has access to a destination endpoint associated with the packet.

8. The method as in claim 1, wherein maintaining the flow cache includes:

determining that a size of the flow cache has reached a certain threshold size; and

deleting a second entry in the flow cache corresponding to a particular flow if the second entry indicates that the particular flow is a least-recently-used flow in the flow cache.

9. The method as in claim 1, wherein the flow cache comprises memory that includes a set of buckets, wherein each bucket in the set of buckets includes a linked list of entries, wherein each entry in the linked list of entries comprises routing information;

access control information;

accounting information;

special treatment information for packets in said particular flow; and

a pointer to information about treatment of packets, in the particular flow, to a destination device for the particular flow.

10. The method as in claim 9, wherein the routing information comprises an output port number for routing packets in the particular flow.

11. The method as in claim 9, wherein the access control information comprises information whether access is permitted for packets in the particular flow.

12. The method as in claim 11, wherein the accounting information comprises a first timestamp for a first packet in the particular flow;

a second timestamp for a most recent packet in the particular flow;

a first cumulative count for the number of packets in the particular flow; and

a second cumulative count for the number of bytes in the particular flow.

13. A method in a router for determining how to treat packets, comprising the steps of:

determining a flow and a flow key for a packet;

performing a first lookup in a flow cache based on the flow key, with the flow determined to be old if the first lookup is successful and determined to be new if the first lookup is unsuccessful;

if the flow is old, using a result of the first lookup to determine how to treat the packet; and

if the flow is new, performing a second lookup in an IP address cache, with a result of the second lookup used to determine how to treat the packet and to make an entry for the flow in the flow cache such that if a next packet in the flow is received, the flow is identified as old, and the next packet is treated in a same manner as the packet,

wherein the router collects and records information about the flow in the flow cache.

14. The method as in claim 13, wherein the router collects historical information about the flow and records the historical information in a flow data table.

15. The method as in claim 13, wherein the router further determines a size of the flow data table;

compares said size with a selected size value; and

if said size exceeds the selected size value, reports the historical information about the flow.

16. The method as in claim 15, wherein the router further builds an information packet responsive to the historical information about all flows in the flow data table;

and transmits the information packet to a selected destination device, wherein the selected destination device receives the information packet and updates a database in a format for the RMON protocol.

17. The method as in claim 16 wherein the selected destination device is determined by an operating parameter of the router.

18. The method as in claim 16 wherein a reporting device queries the selected destination device for information about flows;

builds a report about a condition of a network, wherein the network comprises of at least one network link, at least one source endpoint, at least one destination endpoint, and the router; and

transmits or displays the report about the condition of the network.

19. The method as in claim 13, wherein the router saves the packet if the packet is part of a particular selected flow that meets certain selected parameters.