Network topology control method and apparatus

• US 5,084,870 A
• Filed: 09/19/1990
• Issued: 01/28/1992
• Est. Priority Date: 07/25/1988
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Hawe, William, Yang, Henry, Hutchison, Jerry
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/584,802
• Time in Patent Office: 496 Days
• Field of Search: 370/85.1, 370/85.13, 370/85.14, 370/94.1, 370/94.3, 370/60, 370/60.1, 370/85.15
• US Class Current: 370/258
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A method and apparatus for detecting invalid network topologies in a local area network (LAN). The stations comprising the LAN include single attachment stations (SAS), dual attachment stations (DAS), wire concentrators (WC), and DAS/WC combination stations. Adjacent stations exchange connection type information identifying a type of physical connection of the station sending the connection information. A station receiving the connection information determines whether the connection is valid for its physical connection type using a connection matrix. Invalid connections can result in a network topology where stations are physically connected, but are not logically connected, because the stations do not all form a primary ring. Invalid connections may be rejected and bypassed in each station. Alternately, a station detecting an invalid connection may reconfigure itself using an internal data switch. The actions of each station, taken together, achieve a globally designated primary ring.

Claims

1. A method for controlling the topology of a local area network (LAN) having a plurality of stations, each of the stations being any one of a single attachment station (SAS), a dual attachment station (DAS), a wire concentrator station (WC), a SAS/WC station, or a DAS/WC station, the plurality of stations each being interconnected by duplex point to point physical connections, the method comprising the steps of:

exchanging station connection information over the physical connections only between adjacent stations;

determining, in each of the stations, by analysis of said exchanged connection information, the validity of all connections to each of said adjacent stations according to a predetermined connection list;

identifying, in each of the stations, valid and invalid connections according to said connection list; and

performing, in each of the stations, actions relating to the interconnections of the station, based on the results of the identifying step for the station, the actions of all the stations achieving a globally designated primary ring.

2. The method of claim 1 wherein said step of exchanging includes a step of exchanging three distinct types of messages.

3. The method of claim 1 wherein each of the physical connections of a station has two links and said step of determining includes a step of identifying one or both of said links of each of the duplex point to point physical connections to form a globally designated primary ring.

4. The method of claim 1 wherein said physical connections define a primary ring including at least a first one of the stations and also define a second ring including at least a second one of the stations, and wherein said performing step includes a step of internally reconfiguring the first station, thereby allowing the second station to communicate over said globally designated primary ring.

5. The method of claim 1 wherein said performing step includes the steps of rejecting said invalid connections and preventing, via an internal reconfiguration of the station, the transmission or reception of user data over said rejected connections.

6. The method of claim 1 wherein each SAS has a physical connection of connection type "S", each DAS has physical connections of a connection type "A" and a connection type "B", each WC has a plurality of physical connections of a connection type "M", and each DAS/WC has physical connections of a connection type "A", a connection type "B" and a plurality of connection type "M", and wherein said step of exchanging includes exchanging information indicating the connection type of said physical connections of said adjacent stations.

7. The method of claim 6 wherein said step of exchanging includes exchanging messages corresponding to each of said connection types.

8. The method of claim 1 wherein said step of determining includes a step of deciding the validity of said connection to each of said adjacent stations based upon the connection type of physical connection of the station sending said connection information and the connection type of the physical connection receiving said connection information.

9. The method of claim 8 wherein said step of determining includes a step of validating said connections according to the following connection matrix:

space="preserve" listing-type="tabular">______________________________________ "OTHER "MY END" END" A B M S ______________________________________ A I V V I B V I I I M RULE I I V S I I V V ______________________________________ V = VALID I = INVALID

wherein the columns of said matrix correspond to the connection type of a physical connection of a first one of the stations at an end of a physical connection designated MY END, and the rows of said matrix correspond to the connection type sent by a second one of the stations at an end of a physical connection designated OTHER END, and wherein said RULE permits as valid a connection type "A" at the MY END to a connection type "M" at the OTHER END if and only if no connection type "M" or connection type "B" of said first one of the stations at the MY END is connected to a connection type "A" for said second one of the stations at the OTHER END.

10. The method of claim 8 wherein said step of deciding includes the step of validating the connecting of a connection type "A" of a first one of the stations to a connection type "B" of a second one of the stations, invalidating the connecting of a connection type "A" of a first one of the stations to a connection type "A" of a second one of the stations and invalidating the connecting of a connection type "B" of a first one of the stations to a connection type "B" of a second one of the stations.

11. The method of claim 8 wherein said step of deciding includes the steps of invalidating the connecting of a connection type "B" of a first one of the stations to a connection type "M" of a second one of the stations, and validating the connecting of a connection type "A" of a first one of the stations to a connection type "M" of a second one of the stations if and only if no connection type "M" or connection type "B" of said first one of the stations is connected to a connection type "A" of said second one of the stations.

12. The method of claim 8 wherein said step of deciding includes a step of invalidating the connecting of a connection type "M" of a first station to a second station which is a DAS or DAS/WC when a connection type "A" or "B" of said first station is connected to a connection type "M" of a third station.

13. The method of claim 9 wherein said physical connections define a primary ring and also define a second ring including a tree of DAS/WC stations, each having an invalid physical connection of connection type "M", and wherein said performing step includes, for each DAS/WC station in a tree, a step of internally reconfiguring the DAS/WC stations, thereby allowing the stations to communicate over said globally designated primary ring.

61. The method of claim 6 wherein said step of determining includes a step of deciding the validity of a first connection between a first station and a second station based upon the connection types of the first connection and the connection types of a second connection between the first station and a third station.

62. The method of claim 1 wherein the determining step includes the steps of sending, by each of said physical connections of a connection type "A", connection information of a first message type;

sending, by each of said physical connections of a connection type "B", connection information of a second message type;

sending, by each of said physical connections of a connection type "M", connection information of a third message type; and

sending, by each of said physical connections of a connection type "S", connection information of a fourth message type.

14. A local area network (LAN) having a self controlling topology comprising:

a plurality of stations, each of said stations being any one of a single attachment station (SAS), a dual attachment station (DAS), a wire concentrator station (WC), an SAS/WC station or a DAS/WC station;

a plurality of duplex point to point physical connections interconnecting said stations;

means, in each station, for exchanging station connection information, including connection type information for the physical connections, over said physical connections only between adjacent stations;

means for determining, in each of the stations by analysis of said exchanged information, the validity of all connections to each of said adjacent stations according to a predetermined connection list;

means, in each station, responsive to the determining means, for identifying valid and invalid connections according to said connection list; and

means, in each station, responsive to the identifying means, for performing actions relating to the interconnection of the station, the actions of all the stations achieving a globally designated primary ring.

15. The LAN of claim 14 wherein said means for exchanging includes means for exchanging connection information including three distinct types of messages.

16. The LAN of claim 14 wherein each of said physical connections of a station has two links and said means for determining includes means for identifying as valid one or both of said links of each of the duplex point to point physical connections that form a globally designated primary ring.

17. The LAN of claim 14 wherein said means for performing includes means for rejecting, via an internal reconfiguration of the station, said invalid connections, thus preventing the transmission or reception of user data over said rejected connections.

18. The LAN of claim 14 wherein said connections define a primary ring including at least a first one of the stations and also define a second ring including at least a second one of the stations, and wherein said means for performing includes means for internally reconfiguring the first station, thereby allowing the second station to communicate over said primary ring.

19. The LAN of claim 16 wherein each said SAS includes a physical connection of connection type "S", each said DAS includes physical connections of a connection type "A" and a connection type "B", each said WC includes a plurality of physical connections of a connection type "M", and each said DAS/WC includes physical connections having a connection type "A", a connection type "B", and a plurality of connections type "M".

20. The LAN of claim 19 wherein said exchanged information indicates the connection type of said adjacent station.

21. The LAN of claim 19 wherein said means for exchanging includes means for exchanging messages corresponding to said connection type.

22. The LAN of claim 16 wherein said means for determining includes means for deciding the validity of said connection to each of said adjacent stations based upon the connection type of the physical connection of the station sending said connection information and the connection type of the physical connection receiving said connection information.

23. The LAN of claim 19 wherein said means for determining includes means for validating said connections according to the following connection matrix:

space="preserve" listing-type="tabular">______________________________________ "OTHER "MY END" END" A B M S ______________________________________ A I V V I B V I I I M RULE I I V S I I V V ______________________________________ V = VALID I = INVALID

wherein the columns of said matrix correspond to the connection type of a physical connection of a first one of the stations at an end of a physical connection designated MY END and the rows of said matrix correspond to the connection type signaled by a second one of the stations at an end of a physical connection designated OTHER END, and wherein said RULE permits as valid a connection type "A" at the MY END to a connection type "M" at the OTHER END if and only if no connection type "M" or connection type "B" of said first one of the stations at the MY END is connected to a connection type "A" for said second one of the stations at the OTHER END.

24. The LAN of claim 22 wherein said means for deciding includes means for validating the connecting of a connection type "A" of a first one of the stations to a connection type "B" of a second one of the stations, invalidating the connecting of a connection type "A" of a first one of the stations to a connection type "A" of a second one of the stations and invalidating the connecting of a connection type "B" of a first one of the stations to a connection type "B" of a second one of the stations.

25. The LAN of claim 22 wherein said means for deciding includes means for invalidating the connecting of a connection type "B" of a first one of the stations to a connection type "M" of a second one of the stations, and validating the connecting of a connection type "A" of a first one of the stations to a connection type "M" of a second one of the stations if and only if no connection type "M" or connection type "B" of said first one of the stations is connected to a connection type "A" of said second one of the stations.

26. The LAN of claim 22 wherein said means for deciding includes means for invalidating the connecting of a connection type "M" of a first station to a second station which is a DAS or DAS/WC when a connection type "A" or "B" of said first station is connected to a connection type "M" of a third station.

27. The LAN of claim 14 wherein said means for determining includes means associated with each of said physical connections of a connection type "A" for sending a first message type, means in each of said physical connections of a connection type "B" for sending a second message type, means in each of said physical connections of a connection type "M" for sending a third message type, and means in each of said physical connections of a connection type "S" for sending a fourth message type.

28. The LAN of claim 27 wherein said means for determining includes means in each of said physical connections of said connection type "A" for accepting as valid said second and third message type, means in each of said physical connections of said connection type "B" for accepting as valid said first message type, means in each of said physical connections of said connection type "M" for accepting as valid said first and fourth message types, and means in each of said physical connections of said connection type "S" for accepting as valid said third and fourth message types.

29. The LAN of claim 27 wherein said second and third messages are identical.

30. The LAN of claim 28 wherein said second and third messages are identical.

31. The LAN of claim 22 wherein each of said DAS/WC stations includes means for reconfiguring the station when the validity of a connection between adjacent stations is determined to be invalid.

32. The LAN of claim 31 wherein said connections define a primary ring including at least one of the stations and also define a second ring including at least a second one of the stations having a physical connection with a connection type "M", and wherein said means for reconfiguring includes means for internally reconfiguring the station, therefore allowing the station to communicate over said primary ring.

33. A local area network (LAN) station having one or more duplex point to point physical connections capable of interconnecting the station and other stations in the LAN, comprising:

a PHY layer interface for connecting the station to the physical connections of the station;

means for sending station connection information over said physical connections;

means for receiving only adjacent station connection information from said physical connections;

means for determining by analysis of said received station connection information, the validity of all connections to adjacent stations according to a predetermined connection list;

means for identifying invalid connections according to said connection list; and

means, responsive to the identifying means, for performing actions relating to the interconnection of the station, achieving a globally designated primary ring.

34. The station of claim 33 wherein said means for sending includes means for exchanging connection information including three types of messages.

35. The station of claim 33 wherein each of the physical connections of the station has two links and said means for determining includes means for identifying as valid one or both of said links of each of the physical connections that form a globally designated primary ring.

36. The station of claim 33 wherein said means for identifying includes means for rejecting said invalid connections.

37. The station of claim 35 wherein said connections define a primary ring including at least the station and also define a second ring including at least a second station, and wherein said means for performing includes means for internally reconfiguring the station, thereby allowing the second station to communicate over said primary ring.

38. The station of claim 37 further including a connection of a predetermined connection type to said physical connection.

39. The station of claim 38 wherein the station is a single attachment station (SAS) having a physical connection with a connection type "S".

40. The station of claim 38 wherein the station is a dual attachment station (DAS) having physical connections of a connection type "A" and a connection type "B".

41. The station of claim 38 wherein the station is a wire concentrator (WC) having a plurality of physical connections of a connection type "M".

42. The station of claim 38 wherein the station is a DAS/WC having physical connections of a connection type "A", a connection type "B", and a plurality of connections type "M".

43. The station of claims 41 or 42 wherein said means for reconfiguring includes means for allowing a station having a physical connection of a connection type "M" to communicate over said primary ring.

44. The station of claim 43 wherein each of said physical connections has a data path switch element connected to said physical connection.

45. The station of claim 38 wherein said received information indicates the connection type of said adjacent station.

46. The station of claim 38 wherein said means for sending includes means for sending messages corresponding to said connection type.

47. The station of claim 38 wherein said means for receiving includes means for receiving messages corresponding to a connection type of said adjacent station.

48. The station of claims 39, 40, 41, or 42 wherein said means for determining includes means for deciding the validity of a connection to an adjacent station based upon said connection type of the station and said connection type indicated by said received station connection information.

49. The station of claim 48 wherein said means for determining includes means for validating said connections according to the following connection matrix:

space="preserve" listing-type="tabular">______________________________________ "OTHER "MY END" END" A B M S ______________________________________ A I V V I B V I I I M RULE I I V S I I V V ______________________________________ V = VALID I = INVALID

wherein the columns of said matrix correspond to the connection type of a physical connection of the station at an end of a physical connection designated MY END, and the rows of said matrix correspond to the connection type signaled by an adjacent station at an end of a physical connection designated OTHER END, and wherein said RULE permits as valid a connection type "A" of the station at the MY END to a connection type "M" of said adjacent station at the OTHER END if and only if no connection type "M" or connection type "B" of the station at the MY END is connected to a connection type "A" of said adjacent station at the OTHER END.

50. The station of claim 48 wherein said means for deciding includes means for validating the connecting of a connection type "A" of the station to a connection type "B" of said adjacent station, invalidating the connecting of a connection type "A" of the station to a connection type "A" of said adjacent station and invalidating the connecting of a connection type "B" of the station to a connection type "B" of said adjacent station.

51. The station of claim 48 wherein said means for deciding includes means for invalidating the connecting of a connection type "B" of the station to a connection type "M" of said adjacent station, and validating the connecting of a connection type "A" of the station to a connection type "M" of the adjacent station if and only if no connection type "M" or connection type "B" of the station is connected to a connection type "A" of said adjacent station.

52. The station of claim 48 wherein said means for deciding includes means for invalidating the connecting of a connection type "M" of the station to a second station which is a DAS or DAS/WC when a connection type "A" or "B" of the station is connected to a connection type "M" of a third station.

53. The station of claim 38 wherein said means for sending includes signaling means for sending a first message type indicating a connection type "A", a second message type indicating a connection type "B", a third message type indicating a connection type "M", and a fourth message type indicating a connection type "S".

54. The station of claim 53 wherein said means for determining includes means in each of the physical connections of said connection type "A" for accepting as valid said first, second and fourth message types, means in each of the physical connections of said connection type "B" for accepting as valid said first message type, means in each of the physical connections of said connection type "M" for accepting as valid said first, second and fourth message types, and means in each of the physical connections of said connection type "S" for accepting as valid said second, third and fourth message types.

55. The station of claim 53 wherein said second and third messages are identical.

56. The station of claim 54 wherein said second and third messages are identical.

57. The station of claim 48 wherein said DAS/WC station includes means for internally reconfiguring the station to provide that stations communicate on a particular ring when the connection to an adjacent station is determined to be invalid.

58. The station of claim 57 wherein said means for reconfiguring includes means for reconfiguring the station having a physical connection to allow a station having a connection type "M" to communicate over said primary ring.

59. The station of claim 58 wherein said means for reconfiguring includes a data path switch having a plurality of data path switch elements, each connected to a physical connection to the station.

60. The station of claim 59 further including a loop shaped data path connecting to each of said data path switch elements, and wherein each data path switch element includes means for locating one of the physical connections in either of a first position that would allow communication over a primary ring and a second position that would allow communication over a secondary ring in said network.