Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-07-06
2003-04-29
Vincent, David (Department: 2732)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C710S104000
Reexamination Certificate
active
06556543
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for determining a hop count, and more particularly, to a method for determining the maximum hop count in a bus having a tree structure.
2. Description of the Related Art
The IEEE-1394 for digital network interfaces is currently being standardized. The IEEE-1394 bus has a digital bus protocol for connecting personal computers and digital electric home equipment to each other. The IEEE-1394 bus protocol is widely applied to equipment such as digital video cameras (DVC), hard disc drives (HDD), printers, and personal computers (PC). Also, the IEEE-1394 bus protocol is being extended from a bus protocol for simply connecting peripheral equipment of computers, to a network protocol for performing data transmission among various systems such as PCs.
FIG. 1A
is a block diagram showing an example of on IEEE-1394 bus having a tree structure. Referring to
FIG. 1A
, a plurality of apparatuses
100
through
108
which satisfy the IEEE-1394 standard are connected to the IEEE-1394 bus by 1394 cable. Here, the 1394 cable should not have loops. Namely, there should be only one 1394 cable path connecting one apparatus to another.
FIG. 1B
illustrates the structure of ports connected to the IEEE-1394 bus. Referring to
FIG. 1B
, the apparatus connected to the IEEE-1394 bus includes ports (port
0
through port
2
) to which the cable is connected. A node ID is designated to the apparatus. When an apparatus transmits data to, and receives data from, another apparatus, node IDs are used as the addresses of the concerned apparatuses. Node IDs are re-assigned whenever the bus is reset.
FIG. 2
schematically shows a protocol stack used in the IEEE-1394 standard. The protocol stack shown in
FIG. 2
is necessary in order to operate the IEEE-1394 bus. Here, a physical layer
200
and a link layer
202
are realized as hardware in the form of an integrated circuit (IC) chip. A transaction layer
204
and a node manager
206
are realized as software.
The network connected by the IEEE-1394 bus is changed from a normal bus operation state to a bus reset state when a new apparatus is connected to the network through an arbitrary port on the network, or when a connected apparatus is removed from the network. Such a state transition is detected by the physical layer shown in FIG.
2
. When a state transition is detected, a bus re-alignment process having the following sequence is performed.
In a bus reset state, a tree identification step is performed. In this step, it is sensed whether loops are formed in the connected state of a bus, and a root node for forming a tree is determined. Then, a self-identification step is performed. Each node determines the IEEE-1394 node ID thereof and broadcasts this to other nodes. Then, an isochronous manager determining step is performed to determine a node for managing an isochronous resource. Finally, a manager determining step is performed to determine a node for managing bus configuring information items. In this step, a topology map and a speed map are established and a gap count is optimized. The gap count is optimized by obtaining the maximum of the node to node hop counts for every possible combination of pairs of the bus in the topology map, obtaining the gap count using a table of the IEEE-1394 standard using the maximum value, and designating the gap count of the nodes using a physical layer configuring packet.
As mentioned above, the maximum hop count is used for extracting the gap count of the IEEE-1394 bus. The gap count is broadcast to the respective nodes by the physical layer configuring packet, thus determining the subaction gap of the bus as the optimal value. Therefore, the process of obtaining the maximum hop count is essential for effectively using the bandwidth of the 1394 bus. Such a gap count optimizing process is currently specified in the IEEE-1394 standard. However, methods of determining hop counts among all nodes and the maximum value among the hop counts are not specified in the IEEE-1394 standard at present. Therefore, for obtaining the maximum hop count, at present, the hop counts among all the nodes should be determined simply. There is a problem in that the amount of calculation is very large when many nodes are connected to the bus.
There is an algorithm for the shortest path of every possible combination of pairs or a method provided in the U.S. Pat. No. 5,687,319 by Cook, in another conventional method for solving this problem. According to the methods provided in the above references, the amount of calculation is reduced by some degree. However, the amount of calculation is still large since the calculation is performed in proportion to the square of the number of nodes.
SUMMARY OF THE INVENTION
To solve the above problem, it is an objective of the present invention to provide a method of quickly determining the maximum hop count.
Accordingly, to achieve the above objective, there is provided a method of determining the maximum hop count in a bus having a tree structure, comprising the steps of (a) obtaining hop counts with respect to all the child nodes of each node, obtaining hop counts with respect to all the possible combinations of node pairs in a sub tree in which each node is used as a root node, and obtaining the maximum value among the obtained hop counts as the first maximum value, (b) obtaining the sum of the upper two hop counts having the largest values among the hop counts to a leaf node in the sub tree, as the second maximum value, with respect to all the child nodes of each hop, and (c) determining a larger value between the first maximum value and the second maximum value as the maximum hop count, wherein the maximum value among the maximum hop count values of the respective nodes is determined as the maximum hop count of the bus tree by performing the steps (a) through (c) with respect to all the nodes.
To achieve the above objective, there is provided another method of determining the maximum hop count in a bus having a tree structure, comprising the steps of (a) configuring a first tree by setting an arbitrary node as a root node, (b) searching for the child node having the maximum length among the child nodes of the root node by scanning all the child nodes in the first tree, (c) configuring a second tree by setting the child node searched for in the step (b) as a new root node, (d) obtaining the maximum length by scanning all the child nodes in the second tree configured in the step (c), and (e) setting the maximum length obtained in the step (d) as the maximum hop count.
REFERENCES:
patent: 5687319 (1997-11-01), Cook et al.
patent: 5844902 (1998-12-01), Perlman
patent: 5890173 (1999-03-01), Yoda
patent: 6122248 (2000-09-01), Murakoshi et al.
Beck Chang-kyu
Park Chang-won
Samsung Electronics Co,. Ltd.
Sughrue & Mion, PLLC
Vincent David
LandOfFree
Method for determining maximum hop count in bus having tree... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining maximum hop count in bus having tree..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining maximum hop count in bus having tree... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004613