초록 ▼

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 d

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.

대표청구항 ▼

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 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

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 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 results 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 results 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. 2. A method as in claim 1, wherein the flow key is determined based on a source IP address and port, destination IP address and port, and protocol type for the packet.3. A method as in claim 2, wherein determining how to treat the packet includes determining how to route the packet from the router.4. A method as in claim 3, wherein determining how to treat the packet further includes determining whether access is allowed for the packet.5. A method as in claim 3, wherein determining how to treat the packet further includes determining encryption treatment for the packet.6. A method as in claim 1, further comprising the step of entering accounting information in the flow cache for the flow.7. A method as in claim 1, wherein the IP address cache is an M-trie having a branching width of at least 16, said M-trie having a set of nodes including a root node, each said node having a pointer and a node/leaf indicator included within a data word, said node/leaf indicator determining whether said pointer points to an inferior node or to a leaf data structure, each leaf data structure including information associated with one IP address, said pointer to said inferior node being located at an offset in an array of nodes, said offset within an Nth level of said M-trie corresponding to an associated value represented by an Nth byte of said IP address, wherein because said set of IP addresses are clustered, said M-trie is smaller, by a factor of about five to a factor of about ten, than if said set of IP addresses were randomly distributed.8. A router that determines how to treat packets, comprising:links for receiving packets from at least one source device and routing those packets to at least one destination device; a processor for executing instructions; and a memory for storing data and said instruction, said data including a flow cache and an IP address cache, and said instructions including the steps of (a) determining a flow and a flow key for a packet, (b) performing a first lookup in the 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, (c) if the flow is old, using results of the first lookup to determine how to treat the packet, and (d) if the flow is new, performing a second lookup in the IP address cache, with results 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 the same manner as the packet. 9. A router as in claim 8, wherein the flow key is determined based on a source IP address and port, destination IP address and port, and protocol type for the packet.10. A router as in claim 9, wherein determining how to treat the packet includes determining how to route the packet from the router.11. A router as in claim 10, wherein determining how to treat the packet further includes determining whether access is allowed for the packet.12. A router as in claim 10, wherein determining how to treat the packet further includes determining encryption treatment for the packet.13. A router as in claim 8, wherein the instructions further comprise the step of entering accounting information in the flow cache for the flow.14. A router as in claim 8, wherein the IP address cache is an M-trie having a branching width of at least 16, said M-trie having a set of nodes including a root node, each said node having a pointer and a node/leaf indicator included within a data word, said node/leaf indicator determining whether said pointer points to an inferior node or to a leaf data structure, each leaf data structure including information associated with one IP address, said pointer to said inferior node being located at an offset in an array of nodes, said offset within an Nth level of said M-trie corresponding to an associated value represented by an Nth byte of said IP address, wherein because said set of IP addresses are clustered, said M-trie is smaller, by a factor of about five to a factor of about ten, than if said set of IP addresses were randomly distributed.15. A memory storing instructions for causing a router to determine how to treat packets, the instructions 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 results 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 results 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 the same manner as the packet. 16. A memory as in claim 15, wherein the flow key is determined based on a source IP address and port, destination IP address and port, and protocol type for the packet.17. A memory as in claim 16, wherein determining how to treat the packet includes determining how to route the packet from the router.18. A memory as in claim 17, wherein determining how to treat the packet further includes determining whether access is allowed for the packet.19. A memory as in claim 17, wherein determining how to treat the packet further includes determining encryption treatment for the packet.20. A memory as in claim 15, wherein the instructions further comprise the step of entering accounting information in the flow cache for the flow.21. A memory as in claim 15, wherein the IP address cache is an M-trie having a branching width of at least 16, said M-trie having a set of nodes including a root node, each said node having a pointer and a node/leaf indicator included within a data word, said node/leaf indicator determining whether said pointer points to an inferior node or to a leaf data structure, each leaf data structure including information associated with one IP address, said pointer to said inferior node being located at an offset in an array of nodes, said offset within an Nth level of said M-trie corresponding to an associated value represented by an Nth byte of said IP address, wherein because said set of IP addresses are clustered, said M-trie is smaller, by a factor of about five to a factor of about ten, than if said set of IP addresses were randomly distributed.22. A router that determines how to treat packets, comprising:means for determining a flow and a flow key for a packet; means for 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; means for using, if the flow is old, results of the first lookup to determine how to treat the packet; and means for performing, if the flow is new, a second lookup in an IP address cache, with results of the second lookup used to determine how to treat the packet and to make an entry for the flow in the 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.