Apparatus and method for automatically determining the topology of a local area network

In a communication network arrangement having a plurality of communication hubs coupled together wherein each of said hubs contains a plurality of communication ports for coupling with other hubs of said plurality of hubs, an apparatus for determining a topology of said communication network, said apparatus comprising:

• circuitry for transmitting a plurality of first identifying messages, each of said first identifying messages originating from an originator hub and destined to other of said plurality of hubs, each of said plurality of first identifying messages comprising an address of said originator hub;
• logic for recording into a link identification dataset for said each hub, a list associating individual ports of said each hub with addresses of originator hubs that originated identifying messages that were received over said individual ports;
• and
• logic for generating said topology of said communication network based on said link identification datasets, said logic for generating said topology comprising logic for analyzing said identification datasets to construct an ancestor dataset comprising a topology level number and an ancestor list for individual hubs.

In a communication network arrangement having a plurality of communication hubs coupled together wherein individual hubs contain a plurality of communication ports for coupling with other hubs of said plurality of hubs, a computer implemented method for determining a topology of said communication network, said method comprising the steps of:

• transmitting a plurality of first identifying messages, each of said first identifying messages originating from an originator hub and destined to other of said plurality of hubs, each of said plurality of first identifying messages comprising an address of said originator hub;
• recording into a link identification dataset for said each hub, a list associating each particular port of said each hub with addresses of originator hubs that originated identifying messages that were received over said each particular port;
• and
• generating said topology of said communication network based on link identification datasets of said plurality of hubs, said step of generating said topology comprising the further step of analyzing said identification datasets to construct an ancestor dataset comprising a topology level number and an ancestor list for said each hub.

In a communication network arrangement having a plurality of communication hubs coupled together wherein individual hubs contain a plurality of coupling ports for coupling with other of said plurality of hubs, an apparatus for determining a topology of said communication network, said apparatus comprising;

• means for transmitting a plurality of first identifying messages, each of said first identifying messages originating from an originator hub and destined to other of said plurality of hubs, each of said plurality of first identifying messages comprising an address of said originator hub;
• means for receiving said plurality of first identifying messages over particular ports of said hubs;
• means for recording, into a link of identification dataset for each hub, a list associating particular ports of said each hub with addresses of originator hubs that originated identifying messages that were received over said particular ports of said hubs;
• and
• means for generating said topology of said communication network based on said link identification datasets comprising:
• means for receiving an individual link identification dataset from individual hubs of said communication network;
• means for determining a root hub of said individual hubs of said communication network;
• means for constructing an ancestor table based on each link identification dataset received, said ancestor table including, for each individual hub, a topology level number and a list of ancestor hubs;
• and
• means for constructing a topology of said communication network based on said ancestor table and said root hub.

In a communication network arrangement having a plurality of communication hubs coupled together wherein each of said hubs contains a plurality of communication ports for coupling with other hubs of said plurality of hubs, an apparatus for determining a topology of said communication network, said apparatus comprising:

• (1) means for constructing a link dataset for each hub of said plurality of hubs, said means for constructing a link dataset operable within said each hub and comprising:
• (a) means for generating identification messages from said each hub and to other of said plurality of hubs, each identification message comprising an origination address specifying said each hub that originated said identification message;
• (b) means for receiving identification messages that originated from other hubs through particular ports of said each hub;
• and
• (c) means for recording a listing, for said each hub, associating port numbers of said particular ports with origination addresses of identification messages that were received over said particular ports of said each hub;
• and
• (2) means for generating said topology of said communication network based on each link dataset constructed comprising:
• (a) means for generating an ancestor table based on said transmitted link datasets wherein said ancestor table comprises, for said each hub, an ancestor list and a topology level number;
• and
• (b) means for generating said topology of said hubs of said communication network based on said ancestor table.

In a communication network arrangement having a plurality of communication hubs coupled together wherein each of said hubs contains a plurality of coupling ports for coupling with other of said plurality of hubs, a computer implemented method for determining a topology of said communication network, said method comprising the steps of:

• transmitting a plurality of first identifying messages, each of said first identifying messages originating from an originator hub and destined to other of said plurality of hubs, each of said plurality of first identifying messages comprising an address of said originating hub;
• receiving said plurality of first identifying messages over particular ports of said hubs;
• recording, into a link identification dataset, a list associating particular ports of said each hub with addresses of originator hubs that originated identifying messages that were received over said particular ports of said hubs;
• and
• generating said topology of said communication network based on said link identification datasets by:
• (a) receiving an individual link identification dataset from individual hubs of said communication network;
• (b) determining a root hub of said plurality of hubs of said communication network;
• (c) constructing an ancestor table based on each link identification dataset received, said ancestor table including, for individual hub, a topology level number and a list of ancestor hubs;
• and
• (d) constructing a topology of said communication network based on said ancestor table and said root hub.

In a communication network arrangement having a plurality of communication hubs coupled together wherein each of said hubs contains a plurality of coupling ports for coupling with other of said plurality of hubs, a computer implemented method for determining a topology of said communication network, said method comprising the steps of:

• transmitting a plurality of first identifying messages, each of said first identifying messages originating from an originator hub and destined to other of said plurality of hubs, each of said plurality of first identifying messages comprising an address of said originating hub;
• receiving said plurality of first identifying messages over particular ports of said hubs;
• recording, into a link identification dataset, a list associating particular ports of said each hub with addresses of originator hubs that originated identifying messages that were received over said particular ports of said hubs;
• and
• generating said topology of said communication network based on said link identification datasets by:
• (a) receiving said link identification dataset;
• (b) determining a root hub of said plurality of hubs;
• and
• (c) onstructing an ancestor table based on said link identification dataset, said ancestor table including, for each hub, a topology level and a list of ancestors;
• and
• (d) constructing a topology of said communication network based on said ancestor table.

In a communication network arrangement having a plurality of communication hubs coupled together wherein individual hubs contain a plurality of communication ports for coupling with other hubs of said plurality of hubs, a method for determining a topology of said communication network, said method comprising the steps of:

• (1) constructing link dataset for each hub of said plurality of hubs, said step of constructing a link dataset operable within said each hub and comprising the further steps of:
• (a) generating identification messages from said each hub that are destined to other of said plurality of hubs, each identification message comprising an origination address specifying a hub that originated said identification message;
• (b) receiving identification messages that originated from other hubs through particular ports of said each hub;
• and
• (c) recording a listing, for said each hub, associating port numbers of said particular ports with origination addresses of said identification messages that were received over said particular ports;
• and
• (2) generating said topology of said communication network based on each link dataset by:
• (a) generating an ancestor table based on said transmitted link datasets wherein said ancestor table comprises, for said each hub, an ancestor list and a topology level number;
• and
• (b) generating said topology of said hubs of said communication network based on said ancestor table.

A method of generating a topology representing a configuration of hubs coupled within a communication network, individual hubs having a plurality of ports, said method comprising the steps of:

• generating and sending identification messages from individual hubs to other hubs in said network, said identification messages identifying the generating hub;
• receiving, at individual hubs, identification messages generated by other hubs from the network, said identification messages received via ports of said individual hubs;
• creating individual listing datasets for individual hubs by associating each port of an individual hub with identifications of all generating hubs that generated identifying messages which were received over said each port;
• collecting each listing dataset from individual hubs over the network;
• and
• generating a topology based on each listing dataset by:
• (a) creating an ancestor dataset based on each listing dataset for individual hubs, said ancestor dataset comprised of a listing of ancestor hubs and topology level for said individual hubs;
• and
• (b) generating a topology of said network based on said ancestor dataset.