# US 9,883,507 B2 · Timeslot distribution in a distributed routing protocol for deterministic wireless networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,883,507 B2
- Document ID: US9883507B2
- Status: Granted
- Kind: B2
- Application number: 15/335,945
- Filed: 2016-10-27
- Published: 2017-02-16
- Granted: 2018-01-30
- Earliest claimed: 2014-05-08
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Pascal Thubert; Jean-Philippe Vasseur; Patrick Wetterwald
- Web page: https://patentgrep.com/patent/US9883507B2

## CPC

- H04L 45/121: by minimising delays
- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/48: Routing tree calculation
- H04W 28/04: Error control
- H04W 40/22: using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
- H04W 72/0446: Resources in time domain, e.g. slots or frames
- H04W 72/541: using the level of interference
- H04W 74/085: {collision avoidance}
- Y02B 70/30: Systems integrating technologies related to power network operation and communication or information technologies for improving the carbon footprint of the management of residential or tertiary loads, i.e. smart grids as climate change mitigation technology in the buildings sector, including also the last stages of power distribution and the control, monitoring or operating management systems at local level
- Y02D 30/70: in wireless communication networks
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- Y02B: CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO BUILDINGS, e.g. HOUSING, HOUSE APPLIANCES OR RELATED END-USER APPLICATIONS
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

In one embodiment, a particular node operates a distributed routing protocol in a shared-media communication network, and distributes timeslot allocations using the routing protocol, where the particular node as a parent node allocates a pool of timeslots available to child nodes of the parent node. The parent node specifically allocates particular timeslots from the pool to particular child nodes according to particular flows from a source to a target in the shared-media communication network in order to meet a defined time budget for a resultant time-synchronized path from the source to the target.

## Claims

### Claim 1

A method, comprising:
operating, at a particular node, via a distributed routing protocol in a shared-media communication network;
distributing timeslot allocations using the distributed routing protocol, where the particular node as a parent node allocates a pool of timeslots available to child nodes of the parent node;
transmitting a request for a time-synchronized path, the request carrying:
an absolute time of cycle for a message from a source to reach a target, and
a relative time (TC) initialized to the absolute time and decremented at each hop toward the source; and
dynamically allocating particular timeslots from the pool to particular child nodes according to particular flows from the source to the target in the shared-media communication network in order to meet a defined maximum delay time budget for a resultant time-synchronized path from the source to the target.

### Claim 2 (depends on 1)

The method as in claim 1, further comprising:
determining a hop-distance (N) of the parent node from a root node of the shared-media communication network; and
determining the pool of timeslots available to child nodes of the parent node as timeslots that are multiples of an (N+2)th prime number.

### Claim 3 (depends on 1)

The method as in claim 1, further comprising:
determining whether a particular timeslot is empty prior to allocating that particular timeslot.

### Claim 4 (depends on 1)

The method as in claim 1, further comprising:
resolving timeslot collisions with another node based on an amount of traffic at the parent node and the other node.

### Claim 5 (depends on 4)

The method as in claim 4, wherein the amount of traffic is based on a number of child nodes of the parent node and the other node, respectively.

### Claim 6 (depends on 1)

The method as in claim 1, further comprising:
receiving link slot information;
determining that a particular remote node is outside an interference range;
allowing use of timeslots associated with the particular remote node within the pool of available timeslots; and
removing the particular remote node from propagated information from the parent node.

### Claim 7 (depends on 1)

The method as in claim 1, further comprising:
reserving as many timeslots as are expected to be used prior to actual allocation of the particular timeslots.

### Claim 8 (depends on 1)

The method as in claim 1, further comprising:
preventing use of problematic timeslots within the pool of available timeslots.

### Claim 9 (depends on 1)

The method as in claim 1, further comprising:
negotiating, with a particular child node, a particular corresponding timeslot to allocate from the parent node to the particular child node such that the particular corresponding timeslot (TPC) is less than TC.

### Claim 10 (depends on 9)

The method as in claim 9, wherein the particular child node selects an alternate parent node P′ and negotiates with P′ a second particular corresponding timeslot TP′C from P′ to the particular child node such that the second particular corresponding timeslot (TP′C) is less than TC.

### Claim 11 (depends on 10)

The method as in claim 10, further comprising:
negotiating, with the alternate parent node P′, a timeslot from the parent node to the alternate parent node P′ (TPP′) and from the alternate parent node P′ to the parent node (TP′P) such that TP′P is less than TPC and such that TPP′ is less than TP′C.

### Claim 12 (depends on 1)

The method as in claim 1, further comprising:
transmitting a reply for the time-synchronized path, the reply carrying a total expected delay to reach the target.

### Claim 13 (depends on 10)

The method as in claim 10, wherein primary and backup time-synchronized paths meet the maximum delay time budget and do not conflict timeslot-wise.

### Claim 14

An apparatus, comprising:
one or more network interfaces to communicate as a particular node within a shared-media communication 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 operable to:
operate via a distributed routing protocol in the shared-media communication network;
distribute timeslot allocations using the distributed routing protocol, where the particular node as a parent node allocates a pool of timeslots available to child nodes of the parent node;
transmit a request for a time-synchronized path, the request carrying:
an absolute time of cycle for a message from a source to reach a target, and
a relative time (TC) initialized to the absolute time and decremented at each hop toward the source; and
dynamically allocate particular timeslots from the pool to particular child nodes according to particular flows from the source to the target in the shared-media communication network in order to meet a defined maximum delay time budget for a resultant time-synchronized path from the source to the target.

### Claim 15 (depends on 14)

The apparatus as in claim 14, wherein the process when executed is further operable to:
determine a hop-distance (N) of the parent node from a root node of the shared-media communication network; and
determine the pool of timeslots available to child nodes of the parent node as timeslots that are multiples of an (N+2)th prime number.

### Claim 16 (depends on 14)

The apparatus as in claim 14, wherein the process when executed is further operable to:
negotiate, with a particular child node, a particular corresponding timeslot to allocate from the parent node to the particular child node such that the particular corresponding timeslot (TPC) is less than TC.

### Claim 17 (depends on 14)

The apparatus as in claim 14, wherein primary and backup time-synchronized paths meet the maximum delay time budget and do not conflict timeslot-wise.

### Claim 18

A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:
operate, at a particular node, via a distributed routing protocol in a shared-media communication network;
distribute timeslot allocations using the distributed routing protocol, where the particular node as a parent node allocates a pool of timeslots available to child nodes of the parent node;
transmit a request for a time-synchronized path, the request carrying:
an absolute time of cycle for a message from a source to reach a target, and
a relative time (TC) initialized to the absolute time and decremented at each hop toward the source; and
dynamically allocate particular timeslots from the pool to particular child nodes according to particular flows from a source to a target in the shared-media communication network in order to meet a defined maximum delay time budget for a resultant time-synchronized path from the source to the target.

### Claim 19 (depends on 18)

The tangible, non-transitory, computer-readable media as in claim 18, wherein the process when executed is further operable to:
determine a hop-distance (N) of the parent node from a root node of the shared-media communication network; and
determine the pool of timeslots available to child nodes of the parent node as timeslots that are multiples of an (N+2)th prime number.

### Claim 20 (depends on 18)

The tangible, non-transitory, computer-readable media as in claim 18, wherein the process when executed is further operable to:
negotiate, with a particular child node, a particular corresponding timeslot to allocate from the parent node to the particular child node such that the particular corresponding timeslot (TPC) is less than TC.