Method and apparatus for determining communication path over network by using spanning tree and circuit detection

• US 7,301,912 B2
• Filed: 10/30/2003
• Issued: 11/27/2007
• Est. Priority Date: 11/09/2002
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Lee, Heyung Sub, Lee, Hyeong Ho, Hong, Kang Woon
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): Russell; Wanda Z
• Application Number:
  US10/699,139
• Publication Number:
  US 20040090926A1
• Time in Patent Office: 1,489 Days
• Field of Search: 370/256, 370/402, 370/408, 709/238
• US Class Current: 370/256
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method and apparatus for determining a communication path over a network are provided. The method involves generating a spanning tree having connection devices over a network as vertices and having links among the connection devices as edges; allotting predetermined vertex information to each vertex on the spanning tree; detecting all circuits having a plurality of communication paths among the connection devices over the network corresponding to the spanning tree; and applying rapid ring spanning tree protocol (RRSTP) to links corresponding to the detected circuits and applying rapid spanning tree protocol (RSTP) to links not corresponding to the detected circuits.

Claims

1. A method of determining a communication path over a network, the method comprising:

(a) generating a spanning tree having connection devices over a network as vertices and having links among the connection devices as edges;

(b) allotting predetermined vertex information to each vertex on the spanning tree;

(c) detecting all circuits having a plurality of communication paths among the connection devices over the network corresponding to the spanning tree; and

(d) applying rapid ring spanning tree protocol (RRSTP) to links corresponding to the detected circuits and applying rapid spanning tree protocol (RSTP) to links not corresponding to the detected circuits.

2. The method of claim 1, wherein (a) comprises:

(a1) selecting one vertex and including the selected vertex in the spanning tree;

(a2) selecting a link having a smallest weight among all the links attached to vertices on the spanning tree, and including the selected link in the spanning tree;

(a3) including the other vertex of the selected link that is yet to be included in the spanning tree in the spanning tree; and

(a4) repeatedly carrying out (a2) and (a3) until all vertices are included in the spanning tree.

3. The method of claim 1, wherein (a) comprises:

(a1) storing the vertices on a predetermined untagged vertex list;

(a2) storing all links attached to each of the vertices on a predetermined untagged edge list for the corresponding vertex;

(a3) arbitrarily selecting and deleting one vertex from the untagged vertex list and storing the selected vertex on a predetermined tagged vertex list;

(a4) selecting a link that has a smallest weight and does not exist on the tagged edge list for a corresponding vertex on the tagged vertex list from among all the links attached to the vertices on the tagged vertex list;

(a5) storing the selected link on a tagged edge list for the corresponding vertex;

(a6) deleting a neighbor vertex connected to the corresponding vertex via the selected link from the untagged vertex list and storing the neighbor vertex on the tagged vertex list; and

(a7) repeatedly carrying out steps (a4) through (a6) until no vertex remains on the untagged vertex list.

4. The method of claim 1, wherein (b) comprises:

(b1) selecting a root vertex of the spanning tree as a parent vertex;

(b2) allotting predetermined vertex information to the parent vertex;

(b3) selecting child vertices of the selected parent vertex that are connected to the parent vertex by links included in the spanning tree from among all child vertices of the parent vertex on the spanning tree; and

(b4) repeatedly carrying out steps (b2) and (b3) until all the vertices on the spanning tree are selected as parent vertices.

5. The method of claim 4, wherein vertex information of a root vertex has an initial value, vertex information of other vertices has a value obtained by shifting their parent vertices'"'"' vertex information value leftward by as much as a predetermined number of bits and adding a predetermined index value to the shift result, and the index value is increased by 1 whenever the vertex is selected.

6. The method of claim 1, wherein (c) comprises:

(c1) selecting the root vertex of the spanning tree as an ancestor vertex;

(c2) selecting child vertices of the ancestor vertex that are connected to the ancestor vertex by links not included in the spanning tree;

(c3) searching the spanning tree for a common ancestor vertex shared by the ancestor vertex and the selected child vertices using location word values of the selected vertices and the ancestor vertex;

(c4) detecting a circuit having a plurality of communication paths between the ancestor vertex and the selected child vertices using a location word value of the common ancestor vertex;

(c5) repeatedly carrying out steps (c3) and (c4) on other child vertices of the ancestor vertex; and

(c6) repeatedly carrying out steps (c2) through (c5) while sequentially selecting each of the vertices on the spanning tree as an ancestor vertex.

7. An apparatus for determining a communication path over a network, the apparatus comprising:

a spanning tree generator which generates a spanning tree having connection devices over a network as vertices and having links among the connection devices as edges;

a vertex information allotter which allots predetermined vertex information to each vertex on the spanning tree;

a circuit detector which detects all circuits having a plurality of communication paths among the connection devices over the network corresponding to the spanning tree; and

a spanning tree protocol applier which applies RRSTP to links corresponding to the detected circuits and applying RSTP to other links not corresponding to the detected circuits.

8. A computer-readable recording medium on which a program enabling a method of determining a communication path over a network is recorded, wherein the method comprises:

(a) generating a spanning tree having connection devices over a network as vertices and having links among the connection devices as edges;

(b) allotting predetermined vertex information to each vertex on the spanning tree;

(c) detecting all circuits having a plurality of communication paths among the connection devices over the network corresponding to the spanning tree; and

(d) applying rapid ring spanning tree protocol (RRSTP) to links corresponding to the detected circuits and applying rapid spanning tree protocol to other links not corresponding to the detected circuits.