Routing in a hybrid network

Patent metadata

Field	Value
Publication number	US-2017195218-A1
Application number	US-201514985359-A
Country	US
Kind code	A1
Filing date	Dec 30, 2015
Priority date	Dec 30, 2015
Publication date	Jul 6, 2017
Grant date	—

Abstract

A hybrid network may include a mix of different network technologies and devices. A multi-interface device, such as a hybrid device, may provide for bridging of frames between different networks. Some routing schemes may not be suitable for a hybrid network. In this disclosure are various concepts for a routing scheme suitable for a hybrid network. In accordance with a routing scheme, one or more routing trees may be determined based on a topology map for the hybrid network. The topology map may include nodes to represent different interfaces of at least one multi-interface device. A routing tree determined based, at least in part, on the topology map may be used to manage routing of frames in the hybrid network.

First claim

What is claimed is:

1 . A method for communicating via a network, the method comprising:
determining, at a first device, a topology map for the network having a plurality of devices including at least one multi-interface device, wherein the topology map includes interface-specific nodes to represent different interfaces of the at least one multi-interface device; determining a routing tree for the network based, at least in part, on the topology map, the routing tree having a root node associated with one of the plurality of devices, wherein the routing tree defines routes from the root node to one or more destination nodes; determining, for a frame originated from the root node, whether the first device is in a route from the root node to the one or more destination nodes based, at least in part, on the routing tree; and forwarding the frame from the first device to the one or more destination nodes in accordance with the routing tree in response to a determination that the first device is in the route.

2 . The method of claim 1 , wherein determining the topology map comprises:
obtaining topology information identifying the different interfaces of the at least one multi-interface device, the topology information including a list of neighbor devices associated with each of the different interfaces.

3 . The method of claim 1 , wherein the topology map includes link costs between the different interfaces of the at least one multi-interface device and each neighbor device of a list of neighbor devices.

4 . The method of claim 1 , wherein the topology map includes either a forwarding or non-forwarding capability associated with each of the interface-specific nodes.

5 . The method of claim 1 , wherein determining the routing tree comprises:
determining the routing tree using a shortest path algorithm for unicast routes; determining broadcast delivery options in the topology map; for each broadcast delivery option:
selecting a broadcast path with a lowest path cost from the first device to a target device, and
adding the broadcast path to the routing tree as a route from the first device to the target device in response to a determination that the broadcast path has a lower total cost to reach nodes associated with the broadcast path than existing routes to those nodes and that the broadcast path does not reach a legacy device that already has a unicast route in the routing tree, and
pruning any unicast routes that terminates at one of a plurality of nodes associated with the broadcast path, wherein the unicast route is pruned to a previous node not in the plurality of nodes.

6 . The method of claim 1 , wherein the topology map includes a first link cost from a first node representing a first interface of the at least one multi-interface device to a second node representing a second interface of the at least one multi-interface device.

7 . The method of claim 6 , wherein the first link cost is nominal when the first interface and the second interface are in a same multi-interface device.

8 . The method of claim 1 , wherein determining the routing tree comprises:
defining a set of unvisited nodes in the topology map, the set of unvisited nodes including only nodes that have forwarding capabilities; selecting the root node as a current node; determining routes from the current node to neighbor nodes of the current node, wherein determining the routes comprises, for each neighbor node that has at least one link to the current node:
determining a first link from the current node to the neighbor node,
adding the first link to the routing tree as a new route from the current node to the neighbor node in response to a determination that the routing tree does not have an existing route to the neighbor node or that the new route has a lower path cost from the root node to the neighbor node than an existing route to the neighbor node, wherein the existing route is replaced by the new route, and
removing the current node from the set of unvisited nodes; and selecting, from the set of unvisited nodes, a next node having a lowest path cost to the root node; and repeating said determining routes using the next node as the current node.

9 . The method of claim 1 , further comprising:
optimizing the routing tree, wherein said optimizing includes pruning a unicast route that terminates at a particular device in response to adding a broadcast route to the routing tree that will reach the particular device.

10 . The method of claim 1 , wherein determining whether the first device is in the route comprises:
receiving the frame at a first interface of the first device, the frame having a source address associated with the root node and having a destination address associated with the one or more destination nodes; and determining whether the first interface is in one of the routes of the routing tree from the root node to the one or more destination nodes.

11 . The method of claim 10 , further comprising:
discarding the frame based, at least in part, on a determination that the first interface of the first device is not in one of the routes of the routing tree.

12 . The method of claim 1 , wherein the routing tree comprises a common routing tree that is used by the plurality of devices of the network to route a frame having at least one member of the group consisting of an unknown source address, an unknown destination address, a broadcast address, and an indicator associated with routing frames with an unknown address.

13 . The method of claim 12 , further comprising:
sending routing information from the first device to a second device, the routing information usable by the second device to determine the common routing tree.

14 . The method of claim 1 , wherein the routing tree comprises a first routing tree used for unicast traffic, the method further comprising:
determining a second routing tree for the network based, at least in part, on the topology map, the second routing tree used for broadcast traffic, wherein the second routing tree includes at least one broadcast node, wherein the at least one broadcast node can represent either a physical layer (PHY) broadcast domain or a broadcast-to-unicast conversion broadcast domain.

15 . The method of claim 14 , wherein the second routing tree is optimized to reach each device of the plurality of devices, without regard to which interface of each device is used to reach each device, and wherein the topology map comprises a device-internal node to represent each device separately from the interface-specific nodes.

16 . The method of claim 1 , wherein the first device is a central coordinator for the network, the method further comprising sending the routing tree from the central coordinator to the plurality of devices.

17 . The method of claim 1 , further comprising:
determining a plurality of routing trees, each routing tree having a different root node that is specific to a source interface of one of the plurality of devices; and upon receiving the frame, selecting a first routing tree of the plurality of routing trees based, at least in part, on a source address in the frame being associated with the source interface corresponding to the root node for the first routing tree; and routing the frame in accordance with the first routing tree.

18 . The method of claim 17 , further comprising:
receiving the frame and determining that the frame contains an address that is not in the topology map; selecting one of the plurality of routing trees using a common sel

Assignees

• Qualcomm Inc

Inventors

• Schrum Jr Sidney Brower
• Yonge Iii Lawrence Winston
• Newman Richard Ernest

Classifications

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/488

  using root node determination · CPC title