Hybrid units for a communication network

• US 5,491,692 A
• Filed: 12/23/1993
• Issued: 02/13/1996
• Est. Priority Date: 06/14/1991
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment International Limited
• Inventors: Shand, Ian M. C., Gunner, Christopher W., Harper, John A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/173,719
• Time in Patent Office: 782 Days
• Field of Search: 370/60, 370/94.1, 370/85.13, 370/85.14, 370/8.15, 370/94.3, 370/94.2, 340/825.5
• US Class Current: 370/402
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A communication network consists of end units (EUs) and distribution units (DUs) coupled together by links which may include local area networks (LANs). The units maintain neighbor tables by sending out Hello messages which indicate the unit type and contain the network service access point (NSAP) IDs or addresses of the units. Data messages (packets) mainly originate and end at EUs. An EU maintains only partial routing information about neighbors, while the DUs collectively maintain complete information about all NSAPs. So if an EU wants to send a packet to an EU which is not a neighbour (and sometimes even if it is), it need merely send it to a neighboring DU; that DU, along with the other DUs, must find a route to the destination EU. This invention provides a hybrid unit (HU), which acts as a DU to EUs but as an EU to DUs. The HU provides DU-like message forwarding but only on a local basis within a subnetwork of EUs and HUs.

Claims

1. A communication network comprising:

end units (EUs) and distribution units (DUs) coupled together by communication links, each end unit having one or more network service access points (NSAP) and each distribution unit including routing tables for routing data packets through the network between end units, the end units and distribution units maintaining knowledge of their neighboring end units and distribution units by exchanging EU-Hello and DU-Hello messages which indicate whether the sender is either an end unit or a distribution unit, and the EU-Hello and DU-Hello messages containing the NSAP(s) of the end units and distribution units, the DUs collectively maintaining complete information about all NSAPs; and

a hybrid unit (HU) having one HUE link and a plurality of HUD links, said HUE link coupled with one of said distribution units, each one of said HUD links coupled with one of said end units, said hybrid unit sending on the HUE link EU-Hello messages containing the NSAPs of all EUs from which it receives EU-Hello messages on its HUD links, and sending on the HUD links DU-Hello messages.

2. The communications network as in claim 1, wherein said communication links by which said end units and distribution units are coupled include local area networks (LANs).

3. The communications network as in claim 1 or claim 2, wherein said hybrid unit

maintains forwarding information of neighboring end units and distribution units.

4. The communications network as in claim 1 wherein said hybrid unit further comprises an NSAP table which contains a list of all NSAPs contained in EU-Hello messages received by said hybrid unit, and a distribution unit table which contains a list of distribution units to which said hybrid unit is linked.

5. The communications network as in claim 4, said hybrid unit further comprising:

a routing look-up engine, responsive to said hybrid unit receiving a packet on a first link, said first link equal to a first one of said plurality of HUD links, for forwarding said packet onto a second link, said second link equal to a second one of said plurality of HUD links, said forwarding based on forwarding information in said distribution unit table and said NSAP table, and for generating a redirect message containing a destination NSAP and forwarding information matching said destination NSAP when said packet is forwarded onto the same link on which it was received because said first link is the same as said second link.

6. The communications network as in claim 5, said hybrid unit further comprising:

an end unit table;

an EU-Hello message receiver, coupled with said end unit table, for receiving EU-Hello messages, and for storing said received EU-Hello messages in said end unit table; and

an EU-Hello generator, coupled with said end unit table, for generating EU-Hello messages based on the contents of said end unit table.

7. The communications network as in claim 1, wherein said hybrid unit is reconfigurable to change the assignations of its links, such that said HUE link may be reconfigured to become an HUD link, and such that any of said HUD links may be reconfigured to become an HUE link.

8. A hybrid unit according to claim 7 wherein the hybrid unit is manually reconfigurable.

9. A hybrid unit according to claim 7 wherein the hybrid unit is automatically reconfigurable.

10. A hybrid unit according to claim 9 wherein the hybrid unit, in cooperation with other hybrid units in the communication network, implements a spanning tree algorithm which selects a single hybrid unit from a connected subnetwork of said other hybrid units as a root unit presenting HUD links to all neighboring hybrid units, said selected root unit neighboring a distribution unit if said connected subnetwork of said other hybrid units is not isolated.

11. A communication network comprising:

End Units and Distribution Units coupled together by communication links, each End Unit having one or more Network Service Access Points, and each Distribution Unit including routing tables for routing data packets through the network between End Units, the End Units and Distribution Units maintaining knowledge of their neighboring End Units and Distribution Units by exchanging End Unit Hello and Distribution Unit Hello messages which indicate whether the sender is either an End Unit or a Distribution Unit, and the End Unit Hello and Distribution Unit Hello messages containing the Network Service Access Points of the End Units and Distribution Units, the Distribution Units collectively maintaining information about all Network Service Access Points; and

a Hybrid Unit having one link behaving as an End Unit Link and coupled with one of said Distribution Units, and a plurality of links behaving as Distribution Unit Links, each one of said plurality of links behaving as Distribution Unit links coupled with one of said End Units, said Hybrid Unit sending End Unit Hello messages on said link behaving as an End Unit Link, said End Unit Hello messages containing the Network Service Access Points of all End Units from which said Hybrid Unit receives End Unit Hello messages on said plurality of links behaving as Distribution Unit Links, and said Hybrid Unit sending Distribution Unit Hello messages on said plurality of links behaving as Distribution Unit links.

12. The communications network as in claim 11, wherein said coupling of said Hybrid Unit link behaving as an End Unit Link with said one of said Distribution Units is via one of said communication links.

13. The communications network as in claim 11, wherein said coupling of said plurality of Hybrid Unit links behaving as Distribution Unit Links with said End Units is via a corresponding plurality of said communication links.

14. A communication network comprising:

a plurality of communication links;

one or more End Units, each of said one or more End Units coupled with one of said plurality of communications links, each one of said one or more End Units having one or more Network Service Access Points, each one of said one or more End Units transmitting End Unit Hello Messages containing said one or more Network Service Access Points, and receiving End Unit Hello Messages and Distribution Unit Hello Messages, each one of said End Units maintaining knowledge of those of said one or more End Units and those of one or more Distribution Units that are neighbors to said one of said End Units;

each one of said one or more Distribution Units coupled with one of said plurality of communication links, each one of said one or more Distribution Units having routing tables for routing packets through said communications network between said one or more End Units, each one of said one or more Distribution Units transmitting Distribution Unit Hello Messages and receiving End Unit Hello Messages and Distribution Unit Hello Messages, each one of said one or more Distribution Units maintaining knowledge of those of said one or more End Units and said one or more Distribution Units that are neighbors of said one of said one or more Distribution Units, and said one or more Distribution Units collectively maintaining information about all Network Service Access Points; and

a Hybrid Unit having one End Unit link and a plurality of Distribution Unit links, said End Unit link coupled with one of said one or more Distribution Units, each one of said Distribution Unit links coupled with one of said one or more End Units, said hybrid unit sending EU-Hello messages onto said End Unit link, said EU-Hello messages containing the NSAPs of all End Units from which said Hybrid Unit receives EU-Hello messages on said plurality of Distribution Unit links, and said Hybrid Unit sending DU-Hello messages onto said plurality of Distribution Unit links.

15. The communication network as in claim 14, wherein said End Unit link in said Hybrid Unit is coupled with said one of said one or more Distribution Units via one of said plurality of communication links.

16. The communication network as in claim 15, wherein said each one of said plurality of Distribution Unit links in said Hybrid Unit are coupled with said one of said one or more End Units via a corresponding one of said plurality of communication links.

17. The communication network of claim 16, said Hybrid Unit further sending HU-Hello control messages on said End Unit link and said plurality of Distribution Unit links, said HU-Hello control messages allowing neighboring Hybrid Units to recognize said Hybrid Unit as a Hybrid Unit.

18. The communication network of claim 17, said HU-Hello control messages containing information which allows said Hybrid Unit and said neighboring Hybrid Units to use a spanning tree algorithm.

19. The communication network of claim 18, said one or more End Units and said one or more Distribution Units ignoring said HU-Hello control messages.

20. The communications network of claim 19, each one of said HU-Hello control messages including a cost field, said cost field containing the accumulated cost of the path from said Hybrid Unit to a Root Hybrid Unit, said Root Hybrid Unit determined by running of said spanning tree algorithm.

21. The communication network as in claim 20 wherein said Hybrid Unit further comprises an NSAP table which contains a list of all NSAPs contained in EU-Hello messages received by said Hybrid Unit.

22. The communication network as in claim 21 wherein said Hybrid Unit further comprises a distribution unit table which contains DU-Hello messages received on said HUE link.

23. The communications network as in claim 22, said Hybrid unit further comprising:

a routing look-up engine, responsive to said hybrid unit receiving a packet on a first link, said first link equal to a first one of said plurality of HUD links, for forwarding said packet onto a second link, said second link equal to a second one of said plurality of HUD links, said forwarding based on forwarding information in said distribution unit table and said NSAP table, and for generating a redirect message containing a destination NSAP and forwarding information matching said destination NSAP when said packet is forwarded onto the same link on which it was received because said first link is the same as said second link.