Procedures for merging the mediation device protocol with a network layer protocol

• US 20030007461A1
• Filed: 12/18/2001
• Published: 01/09/2003
• Est. Priority Date: 05/15/2001
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Huang, Jiang, Maeda, Masahiro, Callaway, Edgar H. Jr., Shi, Qicai, Huang, Yan, Bourgeois, Monique, Chen, Priscilla
• Granted Patent: US 7,251,222 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04J 3/0638 Clock or time synchronisation among nodes; Internode synchronisation synchronization for ring networks H04L12/422; data switching networks with synchronous transmission H04L12/43
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]

Abstract

A process for merging and using the Mediation Device Protocol with a network layer protocol. Under the merged protocol, each device joining a network enters into two stages: the Set-Up Stage and the Normal Operational Stage. During the Set-Up Stage, the device identifies its neighbors, builds a neighborhood list, obtains a Logical ID, and picks a parent node in the network. After the Set-Up Stage is complete, the device enters the Normal Operational Stage where it will send/receive control and data messages, invite and help new nodes to join the network, recover from broken links or topology changes, and other normal network operations.

Claims

1. A method for adding a new network node to a network, said method comprising:

operating said new network node to discover neighboring nodes in the network;

confirming symmetric communication links to neighboring nodes in the network;

obtaining a logical identifier and selecting a parent node in the network for the new network node; and

operating said new network node to broadcast status information to the neighboring nodes in the network.

2. A method an accordance with claim 1, wherein said operating said new network node to discover neighboring nodes in the network comprises:

listening to messages transmitted between neighboring nodes in the network;

collecting information about its immediate neighbors by listening to the messages; and

recording the information in an initial neighborhood list.

3. A method in accordance with claim 2, wherein said information collected includes the neighboring nodes'"'"' logical identifiers and the times they will receive or transmit messages.

4. A method in accordance with claim 3, wherein said information collected includes the depth information of the neighboring nodes if available and load information of the neighboring nodes if available.

5. A method in accordance with claim 1, wherein each node has a plurality of transmit periods and receive periods and wherein said confirming symmetric communication links to neighboring nodes in the network comprises:

causing said new network node to send out an alarm message, informing neighboring nodes to suspend transmission for a period;

causing said new network node send a “

Connection Request”

message to the neighboring nodes; and

causing the neighboring nodes to send a “

Connection Response”

message in their next transmit periods, thereby confirming that a symmetric link is in place.

6. A method in accordance with claim 5, wherein said “

Connection Response”

message from a neighboring node comprises the logical identifier, the next receive and transmit times, and the Depth and Load Parameters of the neighboring node.

7. A method in accordance with claim 5, further comprising updating the neighborhood list of the new network node according to information in the said “

Connection Response”

message and according to which neighboring nodes do not send a “

Connection Response”

message.

8. A method in accordance with claim 1, wherein said network includes a cluster of nodes having a Cluster Head and operating under a Cluster Tree Protocol and wherein said obtaining a logical identifier and selecting a parent node in the network for the new network node comprises:

selecting a node from the neighborhood list as the parent node;

causing said new network node to send a “

Logical ID Request”

message to the Cluster Head;

causing said Cluster Head to send a “

Logical ID Response”

message to the parent node; and

causing the parent node to relay the “

Logical ID Response”

message to the new network node.

9. A method in accordance with claim 1, wherein said network includes a cluster of nodes having a Cluster Head and operating under a Cluster Tree Protocol and wherein said obtaining a logical identifier and selecting a parent node in the network for the new network node comprises:

identifying a neighboring node that is a Dedicated Mediation Device;

sending a “

Neighborhood List Request”

message to the Dedicated Mediation Device;

receiving a “

Neighborhood List Response”

message from the Dedicated Mediation Device, the “

Neighborhood List Response”

message providing a list of the Dedicated Mediation Device neighbors;

deleting nodes from the neighborhood list that do not appear on the Dedicated Mediation Device'"'"'s neighborhood list;

selecting a node from the neighborhood list as the parent node;

causing said new network node to send a “

Logical ID Request”

message to the Cluster Head;

causing said Cluster Head to send a “

Logical ID Response”

message to the parent node; and

causing the parent node to relay the “

Logical ID Response”

message to the new network node.

10. A method in accordance with claim 9, further comprising storing deleted node information in a non-synchronized neighborhood list of the new network node.

11. A method in accordance with claim 1, wherein said network includes a cluster of nodes having a Cluster Head and operating under a Cluster Tree Protocol and wherein said obtaining a logical identifier and selecting a parent node in the network for the new network node comprises:

selecting a node with the least depth from neighborhood list as the parent node;

causing said new network node to send a “

Logical ID Request”

message to the Cluster Head;

causing said Cluster Head to send a “

Logical ID Response”

message to the parent node; and

causing the parent node to relay the “

Logical ID Response”

message to the new network node.

12. A method in accordance with claim 11, wherein if more than one node from the neighborhood list has the least depth, a node with the least load is selected as the parent node.

13. A method in accordance with claim 1, where in said network includes a cluster of nodes having a Cluster Head and operating under a Cluster Tree Protocol and wherein said obtaining a logical identifier and selecting a parent node in the network for the new network node comprises:

identifying a neighboring node that is a Dedicated Mediation Device;

sending a “

Neighborhood List Request”

message to the Dedicated Mediation Device;

receiving a “

Neighborhood List Response”

message from the Dedicated Mediation Device, said “

Neighborhood List Response”

message providing a list of the Dedicated Mediation Device'"'"'s neighbors;

deleting nodes from the neighborhood list that do not appear on the list of the Dedicated Mediation Device'"'"'s neighbors;

selecting a node with the least depth from the neighborhood list as the parent node;

causing said new network node to send a “

Logical ID Request”

message to the Cluster Head;

causing said Cluster Head to send a “

Logical ID Response”

message to the parent node;

causing the parent node to relay the “

Logical ID Response”

message to the new network node.

14. A method in accordance with claim 13, wherein if more than one node from the neighborhood list has the least depth, a node with the least load is selected as the parent node.

15. A method in accordance with claim 1, where in said network includes a cluster of nodes have a Cluster Head and operating under a Cluster Tree Protocol, wherein said operating said new network node to broadcast status information to the neighboring nodes in the network comprises:

operating said new network node to monitor message between neighboring nodes in the network;

updating the timing information from the neighboring nodes in the network; and

sending a “

1^st Hello”

message to each neighbor node.

16. A method in accordance with claim 15 wherein said “

1^st Hello”

message includes the new network node'"'"'s logical identifier.

17. A method in accordance with claim 16, wherein said “

1^st Hello”

message includes the new network node'"'"'s depth and load parameters and, optionally, the identifier of its parent node.

18. A method in accordance with claim 16, wherein said “

1^st Hello”

message includes the logical identifier of a Dedicated Mediation Device in the area of the new network node.

19. A method in accordance with claim 18, wherein neighboring nodes having the same Dedicated Mediation Device as the new network node add the new network node to their neighborhood lists.

20. A method in accordance with claim 18, wherein neighboring nodes have Non-synchronized neighborhood lists and neighboring nodes having a different Dedicated Mediation Device to the new network node add the new node to their Non-synchronized neighborhood list.

21. A method in accordance with claim 1, wherein said status information comprises the logical identifier and the depth and load parameters of the new network node, and, optionally, the identifier of the parent node.

22. A method for adding a new network node to a network, said method comprising:

identifying neighboring nodes that have symmetric communication links with the new network node;

generating a neighborhood list of neighboring nodes that have symmetric communication links with the new network node;

operating said new network node to broadcast status information to the neighboring nodes in the network; and

operating said new network node to send messages to said neighboring nodes and to receive messages from said neighboring nodes.

23. A method in accordance with claim 22, further comprising:

periodically listening to network messages;

retrieving information from said network messages; and

updating the neighborhood list according to said information.

24. A method in accordance with claim 23, wherein said information includes the identifiers and the receive and transmit times of said neighboring nodes.

25. A method in accordance with claim 23, further comprising transmitting a “

Hello”

or “

W”

message from said new network node to all of the neighboring network nodes.

26. A method in accordance with claim 23, wherein said network messages include “

Query”

messages.

27. A method in accordance with claim 22, wherein the new network node operates as a Distributed Mediation Device.

28. A method in accordance with claim 22, wherein the network includes at least one Dedicated Mediation Device and wherein said neighborhood list comprises a first neighborhood list containing information about nodes sharing the same Dedicated Mediation Device as the new network node and a second neighborhood list containing information about nodes having a different Dedicated Mediation Device.

29. A method in accordance with claim 28, wherein said updating the neighborhood list comprises:

transmitting a “

Req. Sync All”

message from the new network node to the Dedicated Mediation Device;

causing the Dedicated Mediation Device to request all nodes in its area to synchronize with the new network node for the next period;

transmitting a “

Hello”

message from new network node to neighboring network nodes that are within both the new network node'"'"'s range and the Dedicated Mediation Device'"'"'s range; and

causing the neighboring network nodes to update their neighborhood lists accordingly.

30. A method in accordance with claim 28, wherein said updating the neighborhood list comprises:

transmitting a “

Req. Sync All”

message from the new network node to the Dedicated Mediation Device;

causing the Dedicated Mediation Device to request all nodes in its area to synchronize with the new network node for the next period;

transmitting a “

Hello”

message from new network node to the Dedicated Mediation Device;

forwarding said “

Hello”

message from the Dedicated Mediation Device to neighboring network nodes within the range of the new network node; and

causing the neighboring network nodes to update their neighborhood lists accordingly.

31. A method in accordance with claim 28, further comprising:

operating said new network mode as a temporary Mediation Device; and

checking the status of all nodes in the second neighborhood list.

32. A method in accordance with claim 22, wherein operating said new network node to send messages to said neighboring nodes comprises:

transmitting a “

Req. Sync”

message from said new network node to a Mediation Device;

transmitting an “

Ack”

message from the Mediation device back to the new network node; and

relaying the “

Req. Sync”

message to the appropriate neighboring network node.

33. A method for a new network node to identify Mediation Devices in a network containing normal and non-synchronized neighboring nodes, said method comprising:

determining if a neighboring node switch between being a non-synchronized neighboring node and a normal neighboring node;

determining the Mediation Devices to be a Dedicated Mediation Device if the neighboring node does not switch between being a non-synchronized neighboring node and a normal neighboring node; and

determining the Mediation Devices to be a Distributed Mediation Device if the neighboring node switches between being a non-synchronized neighboring nodes and a normal neighboring node.

34. A method for a new network node to identify Mediation Devices in a network containing normal and non-synchronized neighboring nodes, said method comprising:

providing each Dedicated Mediation Devices with a special logical identifier;

determining a Mediation Devices to be a Dedicated Mediation Device if it has a special logical identifier; and

determining the Mediation Devices to be a Distributed Mediation Device if it does not have a special identifier.