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

• US 7,251,222 B2
• Filed: 12/18/2001
• Issued: 07/31/2007
• 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, Huang, Yan, Bourgeois, Monique, Callaway, Jr., Edgar H., Maeda, Masahiro, Chen, Priscilla, Shi, Qicai
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US10/022,935
• Publication Number:
  US 20030007461A1
• Time in Patent Office: 2,051 Days
• Field of Search: 370/256, 370/408, 370/432, 370/469
• US Class Current: 370/256
• 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;

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.

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 neighboring nodes'"'"' logical identifiers and times they will receive or transmit messages.

4. A method in accordance with claim 3, wherein said information collected includes 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 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.

6. 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.

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

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 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.

9. A method in accordance with claim 8, 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.

10. 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.

11. A method in accordance with claim 10, 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.

12. 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.

13. A method in accordance with claim 12 wherein said “

1^st Hello”

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

14. A method in accordance with claim 13, wherein said “

1^st Hello”

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

15. A method in accordance with claim 13, wherein said “

1^st Hello”

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

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

17. A method in accordance with claim 15, 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.

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

19. 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;

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.

20. A method in accordance with claim 19, further comprising:

periodically listening to network messages;

retrieving information from said network messages; and

updating the neighborhood list according to said information.

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

22. A method in accordance with claim 20, further comprising transmitting a “

Hello”

or “

W”

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

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

Query”

messages.

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

25. A method in accordance with claim 19, 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.

26. 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.