Method and system for initializing host location information across smart bridge topology changes

• US 7,558,217 B2
• Filed: 08/15/2003
• Issued: 07/07/2009
• Est. Priority Date: 08/15/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark D., Rodeheffer, Thomas Lee, Thekkath, Chandramohan A.
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Rutkowski; Jeffrey M
• Application Number:
  US10/642,002
• Publication Number:
  US 20050036500A1
• Time in Patent Office: 2,153 Days
• Field of Search: 370/254, 370/255, 370/256, 370/401, 370/408, 709/249, 709/242, 709/223, 709/224
• US Class Current: 370/255
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A network includes multiple segments and bridges interconnecting the segments, with hosts coupled to the segments. The bridges are smart bridges that each perform a host location initialization function. The host location initialization function in one bridge is performed in corporation with all other bridges in the bridged network via an instance through a propagation order spanning tree (POST). The initialization method includes obtaining prior host location information which is at least a partial representation of the host locations in the bridged network before the network topology change, obtaining hints on host location changes resulting from the network topology change, and modifying the prior host location information according to the hints to construct host location information for initialization. Location information for at least a portion of the hosts in the bridged network is preserved or discovered quickly each time when the network topology changes.

Claims

1. In a bridged network having a plurality of hosts coupled to a plurality of segments interconnected by at least one bridge, a method for initializing host location information in response to a network topology change, comprising:

obtaining prior host location information, said prior host location information being at least a partial representation of host locations in the bridged network before the network topology change, and said prior host location information comprising segment identifier information;

obtaining hints about changes in host locations as a result of the network topology change;

modifying the prior host location information according to said hints to obtain initial host location information, said initial host location information comprising at least a valid host location or a value indicative of an unknown host location, after the network topology change;

wherein the bridged network includes a root bridge and at least one other bridge, and obtaining hints about host location changes comprises;

receiving from the at least one other bridge local topology information associated with the at least one other bridge; and

inferring segment-renaming hints from the received local topology information and local topology information associated with the root bridge;

wherein obtaining prior host location information comprises extracting host location information stored in the root bridge;

wherein obtaining the prior host location information further comprises sending from the root bridge to the at least one other bridge a request for additional host location information and receiving from the at least one other bridge the additional host location information; and

wherein the host location information stored in the root bridge includes a list of hosts each mapped to an identifier of a segment to which the host was coupled before the network topology change, and wherein the request for additional host location information includes a list of segment identifiers in the host location information stored in the root bridge.

2. The method of claim 1, further comprising:

distributing the initial host location information in the bridged network.

3. The method of claim 1, wherein the additional host location information is determined by the at least one other bridge based on the list of host identifiers received from the root bridge and host location information stored in the at least one other bridge.

4. The method of claim 1, wherein the request for additional host location information is sent via a spanning tree having the root bridge as the root of the spanning tree, and wherein sending from the root bridge to the at least one other bridge a request for additional host location information further comprises:

sending from the root bridge to a first bridge a request for additional host location information not stored in the root bridge;

extracting from host location information stored in the first bridge an additional list of segment identifiers not included in the request;

adding the additional segment identifiers to the request; and

sending the request from the first bridge to a second bridge.

5. The method of claim 4, wherein the additional host location information is received from the at least one other bridge via a spanning tree with the root being the root of the spanning tree, and wherein receiving from the at least one other bridge additional host location information further comprises:

extracting from the host location information stored in the second bridge a first piece of host location information;

receiving from the second bridge in the first bridge the first piece of additional host location information;

extracting from the host location information stored in the first bridge a second piece of host location information;

compiling the first and second pieces of additional host location information to form a third piece of host location information;

receiving from the first bridge the third piece of host location information.

6. The method of claim 1, wherein obtaining hints about host location changes further comprises:

identifying segment identifiers that were in the previous network topology and no longer exist after the network topology change.

7. The method of claim 6, wherein modifying the prior host location information includes changing the identified segment identifiers in the prior host location information to a predetermined default name.

8. The method of claim 1, further comprising receiving from the at least one other bridge other segment-renaming hints.

9. The method of claim 8, wherein the at least one other bridge provides the other segment-renaming hints in response to changes in identifiers of segments coupled to the at least one other bridge.

10. In a bridged network having a plurality of hosts each coupled to one of a plurality of network segments interconnected by a plurality of bridges, each host having a location in the bridged network, each bridge storing a piece of host location information, a method for initializing host location information stored in each bridge, comprising:

detecting changes in network topology;

in response to a detected change in network topology, sending a request for host locations initialization from one bridge to other bridges in the bridged network;

receiving responses from said other bridges;

constructing initial host location information based on said responses and on host location information stored in said one bridge, said initial host location information comprising at least a valid host location or a value indicative of an unknown host location in the bridged network after the change in network topology, and further comprising segment identifier information; and

sending said initial host location information to said other bridges;

wherein each bridge stores a total network report, said total network report being a description of bridge-to-network connections in the bridged network, wherein said responses comprise information of bridge-to-network connections associated with said other bridges, and wherein constructing initial host location information comprises;

constructing a new total network report based on said responses;

inferring segment-renaming hints by comparing said new total network report with said total network report stored in said one bridge that has received said responses; and

constructing said initial host location information based on said inferred hints, said responses, and host location information stored in said one bridge.

11. The method of claim 10, wherein sending a request for host locations initialization further comprises:

sending said request to a first group of neighbor bridges, said first group of neighbor bridges being coupled to a same network segment as said one bridge; and

in response to one of said first group of neighbor bridges having received said request, sending a sub-request for host locations initialization from said one of said first group of neighbor bridge to a second group of neighbor bridges, said second group of neighbor bridges being coupled to a same network segment as said one of said first group of neighbor bridges.

12. The method of claim 11, wherein receiving responses from said other bridges further comprises:

receiving in one of said first group of neighbor bridges sub-responses from said second group of neighbor bridges; and

receiving a response from said one of said first group of neighbor bridges, said response comprising a combination of said sub-responses.

13. The method of claim 12, wherein said sub-responses comprise host location information extracted from said second group of neighbor bridges, and wherein said responses comprise host location information extracted from said first group of neighbor bridges and from said second group of neighbor bridges.

14. The method of claim 12, wherein said sub-responses comprise other segment-renaming hints associated with network segments coupled to said second group of neighbor bridges, and wherein said responses comprise additional segment-renaming hints associated with said first group of neighbor bridge and with said second group of neighbor bridges.

15. The method of claim 11, wherein said piece of host location information stored in each bridge comprises a list of host identifiers each identifying a host and each mapped to a segment identifier identifying a network segment to which said identified host is coupled, and wherein said request includes a list of segment identifiers extracted from the piece of host location information stored in said one bridge sending said request.

16. The method of claim 15, wherein said sub-request includes a list of segment identifiers extracted from said one of said first group of neighbor bridges sending said sub-request.

17. A bridged network, comprising:

a plurality of network segments;

a plurality of hosts, each coupled to a network segment; and

a plurality of smart bridges, each having memory spaces for storing a host locations table, and configured to initiate a host locations initialization instance upon detecting a change in network topology, said host location initialization instance comprising;

sending a request for host locations initialization from one bridge to other bridges in the bridged network;

receiving responses from said other bridges;

constructing initial host location information based on said responses and on said host locations table in said one bridge, said initial host location information comprising at least a valid host location or a value indicative of an unknown host location in the bridged network after the change in network topology, and further comprising segment identifier information;

sending said initial host location information to said other bridges; and

rewriting said host location table in each bridge in accordance with said initial host location information;

wherein each bridge includes memory spaces for storing a total network report, said total network report being a description of bridge-to-network connections in the bridged network, wherein said responses comprise information of bridge-to-network connections associated with said other bridges, and wherein said one bridge receiving said responses is configured to;

construct a new total network report based on said responses;

infer segment-renaming hints by comparing said new total network report with said total network report stored in said one bridge; and

construct said initial host location information based on said inferred hints, said responses, and host location information stored in said one bridge.

18. The bridged network of claim 17, wherein sending a request for host locations initialization further comprises sending said request to a first group of neighbor bridges, each one of said first group of neighbor bridges being coupled to a same network segment as said one bridge, and being configured to, in response to receiving said request, send a sub-request for host locations initialization to a second group of neighbor bridges, said second group of neighbor bridges being coupled to a same network segment as said one of said first group of neighbor bridges.

19. The bridged network of claim 18, wherein receiving responses from said other bridges further comprises receiving in one of said first group of neighbor bridges sub-responses from said second group of neighbor bridges, and wherein the one of said first group of neighbor bridges being configured to send a response to said one bridge sending the request, said response comprising a combination of said sub-responses.

20. The bridged network of claim 18, wherein said host locations table stored in each bridge comprises a list of host identifiers each identifying a host and each mapped to a segment identifier identifying a network segment to which said identified host is coupled, and wherein said request includes a list of segment identifiers extracted from the piece of host location information stored in said one bridge sending said request.

21. The bridged network of claim 20, wherein said sub-request includes a list of segment identifiers extracted from said one of said first group of neighbor bridges sending said sub-request.

22. The bridged network of claim 18, wherein said sub-responses comprising host location information extracted from said second group of neighbor bridges, and wherein said responses comprising host location information extracted from said first group of neighbor bridges and from said second group of neighbor bridges.

23. The bridged network of claim 18, wherein said sub-responses comprising other segment-renaming hints associated with network segments coupled to said second group of neighbor bridges, and wherein said responses comprising additional segment-renaming hints associated with said first group of neighbor bridge and with said second group of neighbor bridges.

24. A smart bridge in a bridged network having network segments and hosts coupled to said network segments, comprising:

a plurality of bridge ports, at least a portion of the bridge ports being connected to at least a portion of said network segments, each bridge port providing transmit and receive services for the smart bridge;

at least one segment inventory module coupled to said bridge ports and configured to detect network topology changes associated with said portion of said network segments;

a host locations initialization module coupled to said segment inventory modules and configured to initiate a host locations initialization instance in response to detected change in network topology;

a memory unit storing a host location table, said host location table being a description of locations of said hosts in said bridged network; and

wherein said host locations initialization instance comprising;

transmitting a request to join said instance to said bridged network via said bridge ports;

receiving responses from said bridged network via said bridge ports;

constructing initial host location information based on said responses and on said host locations table, said initial host location information comprising at least a valid host location or a value indicative of an unknown host location in the bridged network after the change in network topology, and further comprising segment identifier information;

sending said initial host location information to said bridged network via said ports; and

rewriting said host location table in said smart bridge in accordance with said initial host location information;

wherein said host locations initialization module is further configured to, in response to receiving a first request to join a host locations initialization instance, transmit a second request to join said instance to the bridged network via said bridge ports.

25. The smart bridge of claim 24, further comprising a location revision module configured to update said host location table based on data packets received by said smart bridge from said hosts in the bridged network.

26. The smart bridge of claim 24, further comprising a topology acquisition module configures to provide a total network report after said change in network topology, said total network report being a description of bridge-to-network connections in said bridged network.

27. The smart bridge of claim 26, wherein constructing initial host location information further comprises:

inferring segment-renaming hints based on said total network report; and

constructing initial host location information based on said responses, said host locations table, and said segment-renaming hints.

28. The smart bridge of claim 26, further comprising:

a communications initialization module configured to create a network topology representation based on said total network report and to determine a routing path for forwarding a data packet received by said smart bridge based on said host locations table; and

a communications operation module configured forward said data packet based on said determination by said communication initialization module.

29. The smart bridge of claim 24, wherein said host location table comprises a list of host identifiers each identifying a host and each is mapped to a segment identifier identifying a segment to which the identified host is coupled, and wherein said request to join said instance includes a list of segment identifiers extracted from said host location table.