Determining flow paths of packets through nodes of a network
A search engine queries a network model for behavior of the entire network, such as data flow, based on combinations of multiple network elements. The search engine provides the state information and/or predicted behavior of the network by searching network objects in a graph-based model or a network state database that satisfy constraints given in a search query. The search engine provides the state information and/or predicted behavior based on regular-expression or plain language search expressions that do not provide packet header information. The search engine parses such search expression into a sequence of atoms that encode forwarding paths of interest to the user. A flow path through the modeled network can be generated dynamically, within the context of the search queries.
1. In a network of devices, a method of determining a flow path between two of the devices in response to a search query, said method comprising:
processing the search query into a plurality of atoms, the plurality of atoms including descriptors for network locations and an action constraint inferred from the descriptors;
extracting source and destination location information from network locations specified by the plurality of atoms in the search query;
determining a first subnet associated with the source location information and a second subnet associated with the destination location information;
upon determining that the first subnet and the second subnet are the same subnet, determining a first flow path between a first device associated with the source location information and a second device associated with the destination location information, using the destination location information and a MAC address of the second device; and
upon determining that the first subnet and the second subnet are not the same subnet, determining a second flow path between the first device and the second device using the destination location information and a MAC address of a gateway device of the first subnet;
wherein the steps of determining the first flow path and determining the second flow path comprise compiling the plurality of atoms into a state machine including a plurality of states and transitions between the plurality of states representing a regular expression of the descriptors and the action constraint.
2. The method of claim 1 , wherein
the source and destination location information includes at least one of an Internet protocol (IP) address, a media access control (MAC) address and a gateway address.
3. The method of claim 1 , wherein
the first flow path starts at the first device and ends with the second device and traverses a first set of devices and the second flow path starts at the second device and ends with the first device and traverses a second set of devices that are different from the first set of devices.
4. The method of claim 3 , wherein
the first set of devices and the second set of devices include a common device that changes state and a change in the state thereof causes the first flow path and the second flow path to traverse through different sets of devices.
5. A non-transitory computer readable medium comprising instructions which when executed in a computer system causes the computer system to carry out a method of determining a flow path between two of the devices in response to a search query, said method comprising:
processing the search query into a plurality of atoms, the plurality of atoms including descriptors for network locations and an action constraint inferred from the descriptors;
extracting source and destination location information from a network locations specified by the plurality of atoms in the search query;
determining a first subnet associated with the source location information and a second subnet associated with the destination location information;
upon determining that the first subnet and the second subnet are the same subnet, determining a first flow path between a first device associated with the source location information and a second device associated with the destination location information, using the destination location information and a MAC address of the second device; and
upon determining that the first subnet and the second subnet are not the same subnet, determining a second flow path between the first device and the second device using the destination location information and a MAC address of a gateway device of the first subnet;
wherein the steps of determining the first flow path and determining the second flow path comprise compiling the plurality of atoms into a state machine including a plurality of states and transitions between the plurality of states representing a regular expression of the descriptors and the action constraint.
6. The non-transitory computer readable medium of claim 5 , wherein
the source and destination location information includes at least one of an Internet protocol (IP) address, a media access control (MAC) address and a gateway address.
7. The non-transitory computer readable medium of claim 5 , wherein
the first flow path starts at the first device and ends with the second device and traverses a first set of devices and the second flow path starts at the second device and ends with the first device and traverses a second set of devices that are different from the first set of devices.
8. The non-transitory computer readable medium of claim 7 , wherein
the first set of devices and the second set of devices include a common device that changes state and a change in the state thereof causes the first flow path and the second flow path to traverse through different sets of devices.