Network flow switching and flow data report

• US 7,260,518 B2
• Filed: 08/23/2004
• Issued: 08/21/2007
• Est. Priority Date: 05/28/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kerr, Darren R., Bruins, Barry L
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US10/924,710
• Publication Number:
  US 20050027506A1
• Time in Patent Office: 1,093 Days
• Field of Search: 703/20, 703/27, 370/379, 370/382, 370/389
• 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 computer-implemented method, comprising:

receiving a first packet in a set of packets to be transmitted between a source and a destination;

based on the first packet, identifying a source address, a destination address, a source port, a destination port, and a protocol type;

determining that a cache does not include a first entry that corresponds to the set of packets, based on the source address, the destination address, the source port, the destination port, and the protocol type;

adding to the cache a second entry that corresponds to the set of packets;

based on the first packet in the set of packets, updating the second entry to include information;

receiving a second packet in the set of packets;

based on the second packet, identifying the source address, the destination address, the source port, the destination port, and the protocol type;

determining that the cache includes the second entry that corresponds to the set of packets, based on the source address, the destination address, the source port, the destination port, and the protocol type; and

based on the second packet in the set of packets, updating the second entry to include information.

2. A method as recited in claim 1, further comprising:

obtaining routing information for the first packet, based on the source address, the destination address, the source port, the destination port, and the protocol type;

based on the routing information, routing the first packet;

updating the second entry to include the routing information;

based on the second entry in the cache, obtaining the routing information for the second packet; and

based on the routing information, routing the second packet.

3. A method as recited in claim 1, wherein the set of packets is a flow;

the cache is flow cache;

the method is performed by a routing device; and

the method further comprises;

determining a flow key based on the source address, the destination address, the source port, the destination port, and the protocol type; and

including the flow key in the second entry.

4. A method as recited in claim 1, wherein the set of packets is a stream.

5. A method as recited in claim 1, further comprising reserving a specific amount of bandwidth for the set of packets based on determining that the cache does not include the first entry.

6. A method as recited in claim 1, further comprising creating and storing information that specifies accesses using HTTP protocol to World Wide Web pages at particular sites based on the set of packets.

7. A method as recited in claim 1, further comprising giving priority to the set of packets, based on the cache including the second entry and that the set of packets uses fewer network resources as compared to a threshold value that specifies an amount of network resources used.

8. A method as recited in claim 1, further comprising:

examining a third entry in the cache corresponding to an additional set of packets;

comparing a current time with a last time of the third entry corresponding to when a last packet of the additional set of packets was routed; and

when the current time and the last time differ by at least a selected timeout, deleting the third entry from the cache.

9. A method as recited in claim 1, further comprising:

examining a third entry in the cache corresponding to an additional set of packets;

comparing a current time with a first time of the third entry corresponding to when a first packet of the additional set of packets was routed; and

when the current time and the first time differ by at least a selected timeout, deleting the third entry from the cache.

10. A method as recited in claim 1, further comprising:

examining a third entry in the cache corresponding to an additional set of packets;

determining that “

next hop”

information in the third entry has changed; and

deleting the third entry from the cache.

11. A method as recited in claim 1, further comprising:

examining a third entry in the cache corresponding to an additional set of packets;

determining that access control list information in the third entry has changed such that a source endpoint associated with the set of packets no longer has access to a destination endpoint associated with the set of packets; and

deleting the third entry from the cache.

12. A method as recited in claim 1, further comprising:

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

deleting a third entry in the cache corresponding to an additional set of packets when the additional set of packets is least-recently-used as determined based upon the third entry.

13. A method as recited in claim 1, wherein the cache includes a set of buckets;

each bucket in the set of buckets includes a linked list of one or more entries; and

each entry of the one or more entries includes information about a particular set of packets.

14. A method as recited in claim 1, wherein the second entry includes information that specifies an output port number for routing packets in the set of packets.

15. A method as recited in claim 1, wherein the second entry includes information that specifies whether access is permitted for packets in the set of packets.

16. A method as recited in claim 1, wherein the second entry includes information that specifies a cumulative count for a number of packets in the set of packets.

17. A method as recited in claim 1, wherein the second entry includes information that specifies a cumulative count for a number of bytes in the set of packets.

18. A method as recited in claim 1, further comprising:

collecting historical information about the set of packets; and

recording the historical information in a table.

19. A method as recited in claim 18, further comprising:

determining a size of the table;

comparing the size of the table with a selected size value; and

when the size of the table exceeds the selected size value, reporting the historical information about the set of packets.

20. A method as recited in claim 18, further comprising:

generating an information packet, based on the historical information about two or more sets of packets in the table; and

transmitting the information packet to a selected destination device that updates a database in a format for the RMON protocol, based on the information packet.

21. A method as recited in claim 18, further comprising:

generating an information packet, based on the historical information about all sets of packets in the table; and

transmitting the information packet to a selected destination device that updates a database in a format for the RMON protocol, based on the information packet;

wherein the selected destination device is queried by a reporting device that generates a report about a condition of a network.

22. A method as recited in claim 1, wherein a plurality of protocol types are used, and further comprising determining how many sets of packets use each protocol type of the plurality of protocol types.

23. A computer-implemented method, comprising:

receiving a first packet in a stream;

based on the first packet, identifying a source address, a destination address, a source port, a destination port, and a protocol type;

determining that a cache does not include a first entry that corresponds to the stream, based on the source address, the destination address, the source port, the destination port, and the protocol type;

adding to the cache a second entry that corresponds to the stream;

based on the source address, the destination address, the source port, the destination port, and the protocol type, obtaining routing information for the first packet;

based on the routing information, routing the first packet;

receiving a second packet in the stream;

based on the second packet, identifying the source address, the destination address, the source port, the destination port, and the protocol type;

determining that the cache includes the second entry that corresponds to the stream, based on the source address, the destination address, the source port, the destination port, and the protocol type;

retrieving the routing information for the second packet from the second entry in the cache; and

based on the routing information, routing the second packet.

24. A method as recited in claim 23, further comprising:

determining a flow key for the set of packets based on the source address, the destination address, the source port, the destination port, and the protocol type;

wherein adding to the cache the second entry further comprises including the flow key in the second entry, wherein the stream is a flow, and wherein the cache is a flow cache.