Propagating an intelligent walker agent in a network to perform a computation

{
  "publication_number": "US11025702B2",
  "country": "US",
  "kind": "B2",
  "title": "Propagating an intelligent walker agent in a network to perform a computation",
  "abstract": "In one embodiment, a device in a network receives a path computation agent configured to determine a path in the network that satisfies an objective function. The device executes the path computation agent to update state information regarding the network maintained by the path computation agent. The device selects a neighbor of the device in the network to execute the path computation agent based on the updated state information regarding the network. The device instructs the selected neighbor to execute the path computation agent with the updated state information regarding the network. The device unloads the path computation agent from the device after selecting the neighbor of the device to execute the path computation agent.",
  "claims": [
    "1. A method comprising: determining, by a device in a network, that the device is incapable of performing a particular computation; generating, by the device, an executable agent configured to perform the particular computation; sending, by the device, the executable agent to one or more other devices in the network to be propagated within the network until the executable agent is received by the one or more other devices capable of executing the executable agent, wherein the one or more other devices in the network execute the executable agent to perform the particular computation and determine a result of the particular computation; and receiving, at the device, the result of the particular computation from at least one of the one or more other devices in the network that execute the executable agent.",
    "2. The method as in claim 1, wherein determining that the device is incapable of performing the particular computation comprises: determining, by the device, that the device does not have sufficient resources available to perform the particular computation or does not satisfy a policy associated with the computation.",
    "3. The method as in claim 1, wherein generating the executable agent configured to perform the particular computation comprises: including, by the device, state information with the executable agent for use when determining the result of the particular computation.",
    "4. The method as in claim 1, wherein sending the executable agent to the one or more other devices in the network comprises: including, by the device, one or more execution constraints with the sent executable agent that control whether a given receiving device executes the executable agent.",
    "5. The method as in claim 4, wherein the one or more execution constraints comprise at least one of: a time limit to return the result to the device or a path distance to the device.",
    "6. The method as in claim 1, wherein sending the executable agent to the one or more other devices in the network comprises: sending, by the device, the executable agent to a neighbor of the device in the network for execution.",
    "7. The method as in claim 6, wherein the neighbor of the device determines that it is incapable of executing the executable agent and propagates the executable agent within the network until the executable agent is received by a device capable of executing the executable agent.",
    "8. The method as in claim 1, further comprising: splitting, by the device, the particular computation into a plurality of sub-computations; generating, by the device, a plurality of executable agents to perform the sub-computations; and sending, by the device, the plurality of executable agents to the one or more other devices in the network for execution.",
    "9. An apparatus, comprising: one or more network interfaces to communicate with a network; a processor coupled to the network interfaces and configured to execute one or more processes; and a memory configured to store a process executable by the processor, the process when executed configured to: determine that the apparatus is incapable of performing a particular computation; generate an executable agent configured to perform the particular computation; send the executable agent to one or more other devices in the network to be propagated within the network until the executable agent is received by the one or more other devices capable of executing the executable agent, wherein the one or more other devices in the network execute the executable agent to perform the particular computation and determine a result of the particular computation; and receive the result of the particular computation from at least one of the one or more other devices in the network that execute the executable agent.",
    "10. The apparatus as in claim 9, wherein the apparatus determines that the apparatus is incapable of performing the particular computation by: determining that the apparatus does not have sufficient resources available to perform the particular computation or does not satisfy a policy associated with the computation.",
    "11. The apparatus as in claim 9, wherein the apparatus generates the executable agent configured to perform the particular computation by: including state information with the executable agent for use when determining the result of the particular computation.",
    "12. The apparatus as in claim 9, wherein the apparatus sends the executable agent to the one or more other devices in the network by: including one or more execution constraints with the sent executable agent that control whether a given receiving device executes the executable agent.",
    "13. The apparatus as in claim 12, wherein the one or more execution constraints comprise at least one of: a time limit to return the result to the apparatus or a path distance to the apparatus.",
    "14. The apparatus as in claim 9, wherein the apparatus sends the executable agent to the one or more other devices in the network by: sending the executable agent to a neighbor of the apparatus in the network for execution.",
    "15. The apparatus as in claim 9, wherein the neighbor of the apparatus determines that it is incapable of executing the executable agent and propagates the executable agent within the network until the executable agent is received by a device capable of executing the executable agent.",
    "16. The apparatus as in claim 9, wherein the process when executed is further configured to: split the particular computation into a plurality of sub-computations; generate a plurality of executable agents to perform the sub-computations; and send the plurality of executable agents to the one or more other devices in the network for execution.",
    "17. A non-transitory, computer-readable medium storing program instructions that, when executed by a device in a network to perform a process comprising: determining, by the device in the network, that the device is incapable of performing a particular computation; generating, by the device, an executable agent configured to perform the particular computation; sending, by the device, the executable agent to one or more other devices in the network to be propagated within the network until the executable agent is received by the one or more other devices capable of executing the executable agent, wherein the one or more other devices in the network execute the executable agent to perform the particular computation and determine a result of the particular computation; and receiving, at the device, the result of the particular computation from at least one of the one or more other devices in the network that execute the executable agent.",
    "18. The non-transitory computer readable medium as in claim 17, wherein sending the executable agent to the one or more other devices in the network comprises: including, by the device, one or more execution constraints with the sent executable agent that control whether a given receiving device executes the executable agent.",
    "19. The non-transitory computer readable medium as in claim 17, wherein generating the executable agent configured to perform the particular computation comprises: including, by the device, state information with the executable agent for use when determining the result of the particular computation.",
    "20. The non-transitory computer-readable medium as in claim 17, wherein sending the executable agent to the one or more other devices in the network comprises: including, by the device, one or more execution constraints with the sent executable agent that control whether a given receiving device executes the executable agent."
  ],
  "description_excerpt": "The present disclosure relates generally to computer networks, and, more particularly, to intelligent walker agents in a network.\n\nLow power and Lossy Networks (LLNs), e.g., sensor networks, have a myriad of applications, such as Smart Grid and Smart Cities. Various challenges are presented with LLNs, such as lossy links, low bandwidth, battery operation, low memory and/or processing capability of a device, etc. Changing environmental conditions may also affect device communications. For example, physical obstructions (e.g., changes in the foliage density of nearby trees, the opening and closing of doors, etc.), changes in interference (e.g., from other wireless networks or devices), propagation characteristics of the media (e.g., temperature or humidity changes, etc.), and the like, also present unique challenges to LLNs.\n\nAn example implementation of an LLN is the “Internet of Things” (IoT), which may be used by those in the art to refer to uniquely identifiable objects/things and their virtual representations in a network-based architecture. In particular, the IoT involves the ability to connect more than just computers and communications devices, but rather the ability to connect “objects” in general, such as lights, appliances, vehicles, window shades and blinds, doors, locks, etc.\n\nMany traditional computing approaches are not applicable to LLNs and the IoT. For example, to optimize a metric along a path using a traditional routing approach, the prerequisite is that the topology and the relevant metric are known by the device performing the computation.",
  "cpc": [
    "H04L 67/04",
    "H04L 41/046",
    "H04L 41/0893",
    "H04L 41/0894",
    "H04L 41/0895",
    "H04L 41/40",
    "H04L 43/08",
    "H04L 43/20",
    "H04L 45/12",
    "H04L 45/121",
    "H04L 45/125",
    "H04L 45/44",
    "H04L 45/563",
    "H04L 67/10",
    "H04L 67/12",
    "H04W 4/70",
    "Y04S 40/00",
    "Y04S 40/18"
  ],
  "ipc": [
    "H04L 45/121",
    "H04L 45/125",
    "H04L 45/60"
  ],
  "assignees": [
    "Cisco Technology Inc"
  ],
  "inventors": [
    "Eric Levy-Abegnoli",
    "Pascal Thubert",
    "Patrick Wetterwald",
    "Jean-Philippe Vasseur"
  ],
  "filing_date": "2019-09-27",
  "publication_date": "2021-06-01",
  "grant_date": "2021-06-01",
  "priority_date": "2017-06-15",
  "application_number": "US-201916585761-A",
  "family_id": "64658533",
  "cited_by_count": 1,
  "citations": [
    "US6477563B1",
    "US20030140165A1",
    "US7096251B2",
    "US20040006589A1",
    "US7834754B2",
    "US20070019594A1",
    "US7593376B2",
    "US20080198787A1",
    "US20100150019A1",
    "US20120057456A1",
    "US9135133B2",
    "US9311108B2",
    "US20130010615A1",
    "US20130185235A1",
    "US20140029445A1",
    "US9071535B2",
    "US20140351310A1",
    "US20150235337A1",
    "US20170208127A1",
    "US20160292303A1",
    "US20170024329A1",
    "US20170034285A1",
    "US20170371829A1"
  ]
}