Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5251205
Callon , ; et al.
October 5, 1993
Title
Multiple protocol routing
Abstract
A method for connecting a network so that TCP/IP and OSI 8473 packets may be routed in the same domain. The independence of the addresses is maintained: one device in the network may be assigned only a TCP/IP address, and another device may be assigned only a ISO 8473 address. Furthermore, all of the routers share link state information by using a common link state packet format (such as the ISO 10589 format); thus routes through the network may be computed without regard for the protocols supported by the routers along the route. Where necessary, packets are encapsulated and forwarded through routers which are not capable in the protocol of the packet. In some disclosed embodiments, all of the routers in a given area support a given protocol (or, in fact, have identical capabilities, in which case encapsulation is not required). In these embodiments, the encapsulation is performed by suitable modifications to each router's packet forwarding procedures. In other disclosed embodiments, these topological restrictions are removed, and the network is expanded to support additional protocols. In these embodiments, the Dijkstra algorithm is also modified to generate information on how to encapsulate and forward packets through the network.
Inventors:
Callon; Ross W.
(Bedford,
MA
)
, Perlman; Radia J.
(Acton,
MA
)
, Rosen; Eric C.
(Arlington,
MA
)
, Harper; John
(Reading,
GB2
)
Assignee:
Digital Equipment Corporation
(Maynard,
MA
)
Appl. No.:
577437
Filed:
September 4, 1990
Current U.S. Class:
370/392
Field of Search:
370/94.1,85.13,85.14,60,79,54
U.S. Patent Documents
4706081
November 1987
Hart et al.
4831620
May 1989
Conway et al.
4893307
January 1990
McKay et al.
5018133
May 1991
Tsukakoshi et al.
5031174
July 1991
Natsume
Other References
John M. McQuillan et al.; "The New Routing Algorithm for the ARPANET"; IEEE; vol. Com-28, No. 5; May 1980. .
E. W. Dijkstra; "A Note on Two Problems in Connexion with Graphs"; Numerische Mathmatik; pp. 269-271 1959. .
"Protocol for Providing the Connectionless-Mode Network Service"; ISO 8473; Mar. 1987. .
"Intermediate system to Intermediate system Intra-Domain routeing exchange protocol for use in Conjunction with the Protocol for providing the Connectionless-mode Network Service"; ISO 10589; Oct. 15, 1989. .
"Information processing systems-Telecommunications and information exchange between systems-End system to Intermediate system routeing exchange protocol for use in conjunction . . . ;" ISO 9542; Mar. 26, 1988. .
"Internet Protocol," Darpa Internet Program, Protocol Specification; RFC 791; Sep. 1981. .
J. Postel; "Internet Control Message Protocol," Darpa Internet, Program Protocol Specification; RFC 792; Sep. 1981. .
R. Braden, J. Postel; "Requirements for Internet Gateways," RFC 1009; Jun. 1987. .
J. Moy; "The OSPF Specification," RFC 1131; Oct. 1989. .
C. L. Hedrick, L. Bosack; "An Introduction to IGRP," Jul. 26, 1989. .
Callon et al., "Routing in an Internetwork Environment," pp. 4-9. .
Shoch et al., "Mutual Encapsulation of Internetwork Protocols," IEN 140, Apr. 1980..~
Primary Examiner:
Olms; Douglas W.
Assistant Examiner:
Jung; Min
Attorney, Agent or Firm:
Fish & Richardson
Claims
What is claimed is:
1. A method of calculating routes for sending user data packets via information handling devices which forward data packets through a communications network, comprising
including in at least a first and a second user data packet, destination address information conforming to two or more different addressing conventions of two or more different independent protocol suites,
determining routes for said first and said second user data packets using a route calculation algorithm corresponding to a single routing protocol, chosen from an arbitrary protocol suite, regardless of the addressing convention to which the destination address information in said user data packet conforms,
said route being determined using the destination address information in said user data packets without converting said destination address information from the addressing convention to which it forms to another addressing convention.
2. The method of claim 1 wherein there are exactly two said protocol suites.
3. The method of claim 1 or 2 further comprising
sending to said information handling devices link state packets conforming to said routing protocol, and
calculating said route based on information contained in said link state packets.
4. The method of claim 1 or 2 wherein said routing protocol comprises OSI IS-IS rotating protocol.
5. A method for calculating routes for sending user data packets via information handling devices which forward data packets through a communications network, said information handling devices including (a) single-protocol information handling devices capable of recognizing and forwardly only user data packets which conform to a single protocol suite, and (b) multi-protocol information handling devices capable of recognizing and forwarding user data packets which conform to any one of two or more protocol suites, comprising
using a routing protocol to automatically predetermine whether to encapsulate a packet, at which information handling devices to encapsulate and to decapsulate said packet, and which protocol to use to encapsulate said packet, wherein
said information handling devices are organized in areas and all of said information handling devices within a single said area are at least capable of recognizing and forwarding user data packets which conform to the same one of said protocol suites.
6. The method of claim 5 wherein the one of said protocol suites for which the information handling devices of one of said area are capable differs from the one of said protocol suites for which the information handling devices of another one of said areas are capable.
7. A method for calculating routes for sending user data packets via information handling devices which forward data packets through a communications network, said information handling devices including (a) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a single protocol suite, and (b) multi-protocol information handling devices capable of recognizing and forwarding user data packets which conform to any one of two or more protocol suites, comprising
using a routing protocol to automatically predetermine whether to encapsulate a packet, at which information handling devices to encapsulate and to decapsulate said packet, and which protocol to use to encapsulate said packet, wherein
said network includes (a) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a first protocol suite, (b) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a second different protocol suite, and (c) at least one multi-protocol information handling device capable of recognizing and forwarding user data packets which conform to at least said first and second protocol suites.
8. The method of claim 7 wherein one of said multi-protocol information handling devices within a given area of said network is capable of recognizing and forwarding user data packets which conform to every protocol suite that is used by any other information handling device in said given area.
9. The method of claim 5, 6, 7 or 8 wherein one of said protocol suites comprises the TCP/IP protocol suite and another of said protocol suites comprises the OSI protocol suite.
10. The method of claim 9 further comprising
sending to said information handling devices, link state packets conforming to said one of said routing protocols, and
calculating said route based on information contained in said link state packets.
11. The method of claim 9 wherein said routing protocol used to automatically predetermine at which information handling devices to encapsulate and to decapsulate a given packet comprises OSI IS-IS routing protocol.
12. The method of claim 5, 6, 7 or 8 wherein there are exactly two of said protocol suites.
13. The method of claim 12 wherein one of said protocol suites comprises TCP/IP and the other of said protocol suites comprises OSI.
14. The method of claim 13 further comprising
sending to said information handling devices, link state packets conforming to said one of said routing protocols, and
calculating said route based on information contained in said link state packets.
15. The method of claim 13 wherein said routing protocol used to automatically predetermine at which information handling devices to encapsulate and to decapsulate a given packet comprises OSI IS-IS routing protocol.
16. The method of claim 12 further comprising
sending to said information handling devices, link state packets conforming to said one of said routing protocols, and
calculating said route based on information contained in said link state packets.
17. The method of claim 12 wherein said routing protocol used to automatically predetermine at which information handling devices to encapsulate and to decapsulate a given packet comprises OSI IS-IS routing protocol.
18. The method of claim 5, 6, 7 or 8 further comprising
sending to said information handling devices, link state packets conforming to said one of said routing protocols, and
calculating said route based on information contained in said link state packets.
19. The method of claim 5, 6, 7 or 8 wherein said routing protocol used to automatically predetermine at which information handling devices to encapsulate and to decapsulate a given packet comprises OSI IS-IS routing protocol.
20. A method for calculating routes for sending user data packets via information handling devices which forward data packets through a communications network, said information handling devices including (a) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a single protocol suite, and (b) multi-protocol information handling devices capable of recognizing and forwarding user data packets which conform to any one of two or more protocol suites, comprising
using a routing protocol to automatically predetermine whether to encapsulate a packet, at which information handling devices to encapsulate and to decapsulate said packet, and which protocol to use to encapsulate said packet, wherein
said routing protocol determines multiple routes from a starting information handling device to an ending information handling device, and
different protocols are recognized by corresponding devices on different routes,
such that the automatic predetermination depends upon the route used.
21. A network of information handling devices which forward user data packets through communications links each said packet including an address indicating the packet's destination, said network comprising
a first information handling device capable of interpreting addresses formatted in accordance with a first addressing scheme, said first addressing scheme defining one or more address fields that are assigned values to form an address,
a second information handling device capable of interpreting addresses formatted in accordance with a second addressing scheme, said second addressing scheme defining different address fields than said first addressing scheme, wherein
at least one address formatted in accordance with said first addressing scheme dose not identify the same destination as any address formatted in accordance with said second addressing scheme, and
said first and second devices exchange control packets which specify:
the links connected to the device which originates the control packet,
the addresses, formatted in accordance with said first addressing scheme, of those destinations that are attached to the originating device and have an address corresponding to said first addressing scheme, and
the addresses, formatted in accordance with said second addressing scheme, of those destinations that are attached to the originating device and have an address corresponding to said second addressing scheme.
22. The network of claim 21 wherein
said first device is capable of interpreting addresses formatted in accordance with said second addressing scheme, and
as part of forwarding at least one given packet addressed in accordance with said first addressing scheme, said first device encapsulates said given packet inside a header addressed in accordance with said second addressing scheme, and transmits the encapsulated packet to said second device.
23. The network of claim 22 wherein
said network is organized into areas comprising routers and links which connect said routers, and
every device in a given area is capable of interpreting addresses formatted in accordance with at least one common addressing scheme.
24. The network of claim 21, 22, or 23 wherein
said first and second devices are configured to transmit a hello packet on a link when the link is connected thereto, said hello packet identifying the device originating the hello packet and indicating the addressing schemes in which the originating device is capable of interpreting addresses.
Description
BACKGROUND OF THE INVENTION
This invention relates to routing algorithms which support multiple protocols.
The end systems (e.g., computers or printers) which form a computer network are interconnected by devices known as routers. Each end system is attached to one of the network's routers and each router is responsible for forwarding communications to and from its attached end systems.
The routers transfer information to and from the end systems and among themselves along communications links in formatted packets. For example, when an originating end system wishes to transmit information to a destination end system, it generates a packet header in an appropriate format (this header includes, among other information, the address of the destination end system), and then fills the remainder of the packet with the information to be transmitted. (In the following description, the term "user data packet" will refer to the entire packet, i.e. the formatted header and the information that is to be transmitted from end system to end system.) The completed user data packet is then provided to the router attached to (and responsible for) the originating end system, which forwards it toward the destination end system. Packets transmitted among the routers themselves (which will be referred to as "control packets") are similarly formatted and forwarded.
When a router receives a user data packet, it reads the user data packet's destination address from the user data packet header, and then transmits the user data packet on the link leading most directly to the user data packet's destination. Along the path from source to destination, a user data packet may be transmitted along several links and pass through several routers, each router on the path reading the user data packet header and forwarding the user data packet accordingly.
To determine how user data packets should be forwarded, each router typically knows the locations of the network's end systems (i.e., which routers are responsible for which end systems), the nature of the connections between the routers, and the states (e.g., operative or inoperative) of the links forming those connections. Using this information, each router can compute effective routes through the network and avoid, for example, faulty links or routers. A procedure for performing these tasks is generally known as a "routing algorithm".
In popular routing algorithms such as that described in "The New Routing Algorithm for the ARPANET" by McQuillan et al., IEEE Transactions on Communications, May, 1980, each router determines which end systems are attached to it, what links to other routers are available, the states of those links, and the identities of the routers on the other ends of those links. To initialize the network, each router places this information in a control packet known as a Link State packet (LSP), and transmits this LSP to all of the other routers in the network (i.e., "advertises" its neighbors and end systems to the network). Later, when changes in the network occur (e.g., a link fails), one or more routers may generate new LSPs which supersede previously generated LSPs.
As long as the most recent LSPs are propagated reliably to all of the routers, each router will have complete information about the topology of the network and can generate a routing database describing routes through the network (for example, using the algorithm described in "A Note on Two Problems in Connexion with Graphs" by Edsgar Dijkstra, Numerische Mathematik, Vol. 1, 1959, pages 269-271).
In order for user data packets to be delivered to their destinations, each end system on the network must have an unambiguous address. There are several independent standards organizations which document and promulgate address allocation schemes, as well as control and user data packet formats which may be used for communicating under these schemes. Several networks of routers have been configured according to these addressing schemes and formats.
In what follows, the term "routing protocol" will be used to describe the combination of an address allocation scheme and a format (or a group of related formats) that describes control packets and other information to be exchanged among routers, and which is used to calculate the paths which the user data packets will take between routers. Routing protocols are often associated with their own routing algorithms, each routing algorithm being documented and promulgated by the standards organization responsible for the associated routing protocol.
Further, the term "protocol suite" will be used to describe the comprehensive set of protocols that is designed to work together to coherently provide complete communication capabilities. Two examples of protocol suites are the TCP/IP protocol suite and the OSI protocol suite. Each of these protocol suites includes one or more network layer protocols which define the format used for control and user data packets that are to be transferred by the network routers. For example, the IP protocol of the TCP/IP protocol suite defines the network layer protocol which makes up the format of the user data packets that are forwarded by the IP routers. Similarly, the OSI routers forward user data packets following the ISO 8473 network layer protocol.
The Transmission Control Protocol (TCP) RFC 793, Internetwork Protocol (IP) RFC 791, the Internet Control Message Protocol RFC 792, and the TCP/IP protocol suite which is described in RFC 1122, "Requirements for Internet Hosts--Communication Layers," RFC 1123, "Requirements for Internet Hosts--Application and Support," RFC 1100, "IAB Official Protocol Standards," and RFC 1009, "Requirements for Internet Gateways," and associated other RFCs, all available from SRI International, DDN Network Information Center, Room EJ291, 333 Ravenswood Avenue, Menlo Park, Calif. 94025, have recently been growing in importance as a multi-vendor communications architecture, and many networks are based on them. (TCP/IP terminology refers to routers as "gateways", and end systems as "hosts".) At the same time, however, existing networks also use the Open Systems Interconnection (OSI) protocols such as described in International Organization for Standardization (ISO) 7498, "Information Processing Systems--Open Systems Interconnection--Basic Reference Model," ISO 8473, "Protocol for Providing the Connectionless-mode Network Service," ISO 9542, "End System to Intermediate System Routing Exchange Protocol," and ISO DP 10589 "Intermediate System to Intermediate System Intradomain Routing Exchange Protocol," all available from BSi Standards, 2 Park Street, London England, W1A 2BS, and more are expected to be created as OSI is further developed.
Because the several existing protocols (in particular TCP/IP and OSI) have been developed independently, they are largely incompatible.
Networks having incompatible protocols cannot make their links and routers available to each other, which may result in excess redundancy and reduced efficiency. Also, each of the networks must be maintained independently, increasing the total management effort over what would be required by a single, universally compatible network.
One known way to share routing resources among networks having incompatible protocols is known as gateway encapsulation. In gateway encapsulation, a network using protocol A is provided with a path through a second network that uses protocol B. To form the path, two routers are manually configured to provide gateways from protocol A to protocol B, and back.
Each gateway router is configured to be fluent in both protocol A and protocol B. When a user data packet formatted in protocol A is received, at a gateway router, the gateway router "encapsulates" the user data packet in a protocol B header (i.e., generates a protocol B header and places the protocol A user data packet, including the protocol A header, into the data area of the protocol B user data packet). The encapsulated protocol A user data packet is then addressed to the second gateway router, and transmitted through the protocol B network.
When the encapsulated protocol A user data packet is received at the second gateway router, the protocol B encapsulation header is removed, and the protocol A user data packet is forwarded to its destination through the protocol A network.
The routing algorithm used in the protocol A network is suitably modified to make the protocol A routers aware of the gateway, so that user data packets destined to routers at the other end of the gateway are forwarded to one of the gateway routers.
One disadvantage of gateway encapsulation is that the gateway must be manually configured, and thus must also be manually maintained. If a change to the gateway path is desired, or if an additional gateway path is added, the gateway routers must be manually adjusted to effect the desired changes. Furthermore, the gateway path is only available to the protocol A network as long as the gateway routers themselves are operational. If a gateway router fails, the pre-established path through the protocol B network is severed, and communications must be re-routed through the protocol A network.
Another way to route multiple incompatible protocols is known as "ships in the night" (SIN). In the SIN approach, the same physical resources (e.g., routers and links) are used to route completely separate protocols. The shared resources multiplex between the supported protocols, and the protocols themselves operate more or less independently.
With SIN, there is some degree of competition for resources, because implementing two protocols requires additional programming time as well as additional CPU and memory resources in the routers. Furthermore, SIN requires that two complete sets of control packets be distributed through the two independent networks, which doubles the control traffic overhead over that of a single integrated network. Finally, configuring and managing multiple independent networks is less efficient than configuring and managing a single integrated network of the same total size: multiple networks must be configured independently, increasing overhead; and multiple networks cannot be managed as efficiently as a single network because the implicit interactions between the networks (such as the shared loads placed on routers and links) cannot be well characterized and controlled.
SUMMARY OF THE INVENTION
In one aspect, the invention features a method of calculating routes for sending user data packets through an interconnected network of information handling devices. Each of the user data packets includes destination address information conforming to an addressing convention of any one of two or more different independent protocol suites. The routes for user data packets are always calculated using a single route calculation algorithm corresponding to the same routing protocol (which is chosen from an arbitrary protocol suite) regardless of the addressing convention to which the user data packet conforms. This calculation does not involve converting the destination information from one addressing convention to another.
Preferred embodiments of this aspect include the following features.
There are exactly two protocol suites.
Link state packets conforming to the routing protocol used to compute routes are sent to the information handling devices, and routes are calculated based on information contained in the link state packets.
The OSI IS-IS routing protocol is used to compute routes.
In another aspect, the invention features a method for calculating routes for sending user data packets via information handling devices which are interconnected in a communications network. The information handling devices include (a) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a single protocol suite, and (b) multi-protocol information handling devices capable of recognizing and forwarding user data packets which conform to any one of two or more protocol suites. A routing protocol is used to automatically predetermine at which information handling devices to encapsulate and to decapsulate a given packet.
Preferred embodiments of this aspect include the following features.
The information handling devices are organized in areas and all of the information handling devices within a single area are at least capable of recognizing and forwarding user data packets which conform to the same one of the protocol suites. This common protocol suite may be different for different areas.
A given area may include (a) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a first protocol suite, (b) single-protocol information handling devices capable of recognizing and forwarding only user data packets which conform to a second different protocol suite, and (c) at least one multi-protocol information handling device capable of recognizing and forwarding user data packets which conform to the first and second protocol suite (and/or every other protocol suite that is used by any other information handling device in the area).
There are exactly two protocol suites, one which is the TCP/IP protocol suite and another which is the OSI protocol suite.
Link state packets conforming to the routing protocol used to compute routes are sent to the information handling devices, and routes are calculated based on information contained in the link state packets.
The OSI IS-IS routing protocol is used to compute routes and determine at which information handling devices to encapsulate and to decapsulate.
In another aspect, the invention features a method of enabling user data packets to be forwarded from one local area network to another by a device which is capable of acting as a router to recognize and forward user data packets which conform to a first protocol suite and is capable of acting as a bridge to recognize and forward user data packets which conform to at least a second protocol suite. For a user data packet which conforms to the first protocol suite and is addressed to a single address which is not an address of the device, the devices acts as a bridge rather than as a router.
Other features and advantages of the invention will be apparent from the following description of the preferred embodiments and from the claims.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
We first briefly describe the drawings.
FIG. 1A is a diagram of a dual-protocol network segregated on a per-area basis which does not require encapsulation.
FIG. 1B is a flow diagram of the user data packet receiving algorithm to be followed by the routers of FIG. 1A.
FIG. 1C is a flow diagram of the user data packet forwarding algorithm to be followed by the routers of FIG. 1A.
FIG. 2A is a diagram of a dual-protocol network segregated on a per-area basis which requires encapsulation.
FIG. 2B is a flow diagram of the user data packet receiving algorithm to be followed by the dual-protocol routers of FIG. 2A.
FIG. 2C is a flow diagram of the user data packet forwarding algorithm to be followed by the dual-protocol routers of FIG. 2A.
FIG. 3 is a diagram of a dual-protocol network which is not segregated on a per-area basis.
FIG. 4A is a flow diagram of an algorithm used to build routing trees.
FIG. 4B is a diagram of a routing tree.
FIG. 5A is a diagram of a data structure of the routing tree of FIG. 4B as used in a dual-protocol router of FIG. 3.
FIG. 5B is a flow diagram of an algorithm for initializing the routing trees in the dual-protocol routers of FIG. 3.
FIG. 5C is a flow diagram of an algorithm for building the routing trees in the dual-protocol routers of FIG. 3.
FIG. 6 is a flow diagram of the user data packet forwarding algorithm to be followed by the dual-protocol routers of FIG. 3.
FIG. 7A illustrates a three-protocol network which does not have an all-protocol router.
FIG. 7B illustrates a three-protocol network having an all-protocol router.
FIG. 8A is a diagram of a data structure of the routing tree of FIG. 4B as used in a dual-protocol router of FIG. 7B.
FIG. 8B is a flow diagram of an algorithm for initializing the routing trees in the dual-protocol routers of FIG. 7B.
FIG. 8C is a flow diagram of an algorithm for building the routing trees in the dual-protocol routers of FIG. 7B.
FIG. 9 is a flow diagram of the user data packet forwarding algorithm to be followed by the dual-protocol routers of FIG. 7B.
FIG. 10A is a diagram of a data structure of the routing tree of FIG. 4B as used in the all-protocol router of FIG. 7B.
FIG. 10B is a flow diagram of an algorithm for initializing the routing tree in the all-protocol router of FIG. 7B.
FIG. 10C is a flow diagram of an algorithm for building the routing tree in the all-protocol router of FIG. 7B.
FIG. 11 is a flow diagram of the user data packet forwarding algorithm to be followed by the all-protocol router of FIG. 7B.
FIG. 12 illustrates a common area structure.
FIG. 13 illustrates a brouter.
GENERAL DESCRIPTION
Before discussing the invention, it will be useful to define some terminology.
A router that is fluent in only one of the protocols supported by the multi-protocol network will be generally referred to as a "single-protocol" router. Where necessary, the protocol supported by a single-protocol router may be indicated by explicit reference to the protocol. For example, a single-protocol router which is fluent in only protocol P1 may be referred to as a "P1-only" router.
Routers that are fluent in more than one of the supported protocols interconnect the dissimilar single-protocol routers. A router that is fluent in more than one of the supported protocols will be generally referred to as a "multi-protocol" router. Routers that are fluent in two protocols will be referred to as "dual-protocol" routers; routers that are fluent in three protocols will be referred to as "three-protocol" routers, and so on. Multi-protocol routers that are fluent in all of the protocols supported by a given network will be referred to as "all-protocol" routers. (Note that where only two protocols are supported, the terms multi-protocol, dual-protocol, and all-protocol are synonymous; however, this synonymity does not apply when more than two protocols are supported.)
There are two types of multi-protocol routers. A "simple multi-protocol router". will route user data packets conforming to two or more protocols. However, a simple multi-protocol router is only able to forward the user data packets; it is not able to perform encapsulation or decapsulation to make user data packets in one protocol compatible with another protocol. An "enhanced multi-protocol router" will not only route user data packets conforming to two or more protocols, but is also able to perform encapsulation or decapsulation to make user data packets in one protocol compatible with another protocol. The extent to which enhanced multi-protocol routers may or may not support complex combinations of the other three types of routers is described in detail below.
Note that there is a distinction between the capabilities of a particular router, and its operation at any one time. For example, a router may be a multi-protocol router, but may be configured to operate as a single-protocol router. This would allow it to interoperate with other single-protocol routers in a network which only supports one protocol. The term P1-capable will be used to refer to any router which is able to forward user data packets formatted (and addressed) in accordance with protocol P1. Thus the set of P1-capable routers includes P1-only routers and any multi-protocol routers which include P1 among the set of protocols that they are capable of handling.
Also, note that an end system that communicates with routers and other end systems in accordance with a given protocol can only be connected to a router that is capable in that protocol. For example, an end system designed to communicate in protocol P1 can only connect to routers that are P1-capable. This has implications on the network architectures, as will be seen more fully below.
In one particular embodiment, the invention is applied to a dual-protocol network supporting the TCP/IP protocol suite defined by the Internet Engineering Task Force (IETF) as well as the OSI protocol suite defined by ISO. The following discussion will be directed to this particular set of protocols, although the invention is not limited to these protocols, and the inventive concepts set forth below may be applied to other groups of protocols.
To apply the invention to TCP/IP and OSI, these protocols are slightly modified. Primarily, the format of various control packets such as the link state packets and the router to router "hello" packets are normalized so that all of the routers can connect to each other and become aware of the full topology of the multi-protocol network. In one embodiment, the common format comprises the current ISO DP 10589 format, with additional fields appended to the format, as allowed by the current format. In particular, additional optional fields are added to the hello packets, link state packets, and sequence number packets. The other packet formats (in particular user data packet formats defined by ISO 8473 and IP, as well as control packet formats for router to end system communications), and the addressing schemes of the various different protocols, are not modified. ISO 9542 defines the control packet formats that are used for communications between routers and end systems in an OSI environment. Since one particular type of ISO 9542 packet format (the Intermediate System Hello packet) performs "double duty", and is also used for communications between routers over point-to-point links, this packet type will be modified by the addition of information in a manner that routers can interpret correctly, and that standard OSI end systems will ignore.
Particular modifications to the protocols suitable for one embodiment of the invention will be discussed under the heading "Detailed Description", below. The following general discussion of the invention will assume that the modifications described above have been made to the underlying protocols. Therefore, any reference to a particular protocol should be understood as a reference to the protocol as modified to conform with the goals of the preceding paragraph.
In an IP-OSI dual-protocol network, the types of routers discussed above can be further defined as follows:
(1) An "IP-only router" can understand and forward only user data packets conforming to RFC 791. Such a router conforms to the requirements for Internet gateways (as currently defined in RFC 1009, available from SRI International at the above address). However, an IP-only router will not be able to forward 8473 packets, and may operate without regard for ISO packet and addressing standards, except that IP-only routers may use OSI 10589 as their routing protocol.
(2) An "OSI-only" router can understand and forward only user data packets conforming to OSI 8473. Such a router conforms to the other requirements for OSI routers (including the end system-intermediate system protocol, ISO 9542, available from BSi Standards at the above address). However, an OSI-only router will not forward TCP/IP packets, and may operate without regard for IETF packet and addressing standards.
(3) A "simple dual-protocol router" can understand and forward both 8473 and IP user data packets simultaneously. However, a simple dual-protocol router is not be able to encapsulate IP user data packets inside OSI user data packets for transmission through an OSI-only router, or alternatively, encapsulate OSI user data packets inside IP user data packets for transmission through an IP-only router.
(4) An "enhanced dual-protocol router" can understand and forward both 8473 and IP user data packets simultaneously. In addition, an enhanced dual-protocol router can encapsulate IP user data packets inside OSI user data packets for transmission through an OSI-only router, and similarly can encapsulate OSI user data packets inside IP user data packets for transmission through an IP-only router. The way in which the encapsulation is performed will be discussed below.
Note that, of the four types of routers described above, types 1, 3, and 4 are all IP-capable. Similarly, types 2, 3, and 4 are all OSI-capable.
Even though dual-protocol routers are more flexible than IP-only or OSI-only routers, some vendors may still wish to implement single-protocol routers. Thus, even in a dual-protocol network, there may be IP-only and OSI-only routers, which will have to connect to and coexist with dual-protocol routers, and with each other. A main issue that must be confronted is how to control this interaction to provide for the correct forwarding of user data packets. Several options are proposed below.
The most direct way to allow interaction between the protocols is on a "per-area" basis. Referring to FIGS. 1A and 2A, large networks are often organized hierarchically; that is, partitioned into smaller networks 90, 92, 94, 137, 139. For the purposes of this discussion, these smaller partitions of the large network will be referred to as "areas"; routing within an area will be referred to as Level-1 routing, and routing between areas will be referred to as Level-2 routing.
TCP/IP routers and OSI routers are arranged into a common area structure. (Maintenance of an independent two level hierarchy for the two protocols is possible, but is complex, and does not benefit from the advantages of a common area structure discussed below.) The detailed description, which follows later, discusses methods for creating a common area structure while allowing independent use of the existing addressing schemes and packet formats, e.g., OSI and TCP/IP addressing schemes and packet formats, without requiring modification of those addressing schemes and packet formats. In the following general description, it will be assumed that a suitable method has been employed to create such a common area structure.
In FIGS. 1A and 2A, those routers that are OSI-only, and the end systems designed to communicate with the OSI protocols, are indicated by circles. Those routers that are IP-only, and the end systems designed to communicate with the TCP/IP protocols, are indicated by squares. Those routers that are dual-protocol (either simple dual or enhanced dual) are indicated by circles within squares. The Level-1 routers (which reside within the areas 100) are marked with a "1". The Level-2 routers which connect the areas 100 are marked with a "2". The end systems are marked with an "E".
In a hierarchical network such as in FIGS. 1A and 2A, the Level-1 routers need not share link state information with all of the other Level-1 routers, rather, this information is only shared with those Level-1 routers in the same area. To permit routing of user data packets between areas, end system addresses are assigned such that, by observing an end system address, the routers in an area can determine whether the end system having that address is in the local area. (Typically this observation involves reading the more significant bits of the address and/or applying bit masks to the address). When a user data packet is sent from an end system in a given area to another end system in the same area, the user data packet is forwarded via Level-1 routing. Otherwise, if the user data packet is sent to an end system in another area, Level-1 routers in the originating area forward the user data packet to an appropriate Level-2 router in their area. In the most common embodiment, this involves forwarding to the nearest Level-2 router in their area. Level- 2 routers then forward the user data packet to the nearest Level-2 router in the destination area. Then the user data packet again travels via Level-1 routing to the destination end system.
There are several embodiments of the invention which organize the dual-protocol network on a per-area basis. Two of these embodiments are illustrated in FIGS. 1A and 2A.
In the embodiment illustrated in FIG. 1A, the topology of the network is restricted such that no user data packet encapsulation is required. In each area, one of the following is true: (1) every router in the area operates as OSI-only (e.g., the area 90 on the left of FIG. 1A); (2) every router in the area operates as IP-only (e.g., the area in the center of FIG. 1A); or (3) every router in the area operates as dual-protocol (e.g., the area 94 on the right of FIG. 1A). Similarly, the Level-2
backbone operates entirely as IP-only, entirely as OSI-only, or entirely as dual-protocol.
In some embodiments, all areas operate as dual-protocol. In other embodiments, some areas operate as OSI-only, and some as dual-protocol. In other embodiments, some areas operate as IP-only, and others as dual-protocol. As illustrated in FIG.
1A, in some embodiments, some areas operate as IP-only, some areas as OSI-only, and some areas as dual-protocol. Any of these combinations are possible as long as (i) the Level-2 backbone operates in dual-protocol mode (as in FIG. 1A) or (ii) the protocol which is not supported by the Level-2 backbone is prohibited from operating outside of the individual areas.
In the architecture of FIG. 1A, there is no need for encapsulation, and thus all of the dual-protocol routers are "simple dual" routers. It may not be immediately evident that encapsulation is not necessary in the architecture of FIG. 1A; therefore, some discussion will be dedicated to this point.
First, note that encapsulation is only necessary if some of the paths that may be followed by a user data packet pass through routers that are not capable in the protocol of the user data packet. If every router in the path is capable in the protocol of the user data packet, then every router can forward the user data packet in accordance with that protocol, and the user data packet will successfully reach its destination without being encapsulated.
Given the above paragraph, it is clear by inspecting FIG. 1A that any path that may be taken by a TCP/IP user data packet or an OSI user data packet can only pass through IP-capable or OSI-capable routers, respectively. Therefore, there will never be any need to encapsulate user data packets.
To be more rigorous with the above proof (this discussion will be of use in analyzing more complex multi-protocol networks to be presented below) note that, in any dual-protocol network, the first router on any path followed by an OSI-formatted user data packet must be OSI-capable. To prove this assertion, remember that OSI-formatted user data packets can only be generated by OSI end systems or (in some special cases) by OSI-capable routers. Because all OSI end systems must be connected to OSI-capable routers, the first router on any path followed by an OSI-formatted user data packet must be an OSI-capable router. For similar reasons, the last router on any path followed by an OSI-formatted user data packet must be OSI-capable. This is true because an OSI-formatted user data packet must be addressed to an OSI end system or (in some special cases) to an OSI-capable router. (A non-OSI end system or router could not interpret or use the contents of an OSI-formatted user data packet, and even if it could, the address of a non-OSI end system or router would not be an OSI address and could not be placed in an OSI user data packet header). Again, because all OSI end systems must be connected to OSI-capable routers, the last router on a path followed by any OSI-formatted user data packet must be OSI-capable.
For the reasons given above, the first and last routers along any path followed by an OSI-formatted user data packet must be OSI-capable. For similar reasons, the first and last routers along any path followed by an IP-formatted user data packet must be IP-capable.
Now note that, within any given area in FIG. 1A, all of the routers have the same capabilities. As stated above, the first router in the path of a user data packet must be capable in that user data packet's protocol: because all of the routers in an area have the same capabilities, this means that all of the routers in the area originating a user data packet must be capable in that user data packet's protocol. Similarly, the last router in the path of a user data packet must be capable in that user data packet's protocol; because all of the routers in an area have the same capabilities, this means that all of the routers in the area to which a user data packet is addressed must be capable in that user data packet's protocol. Thus all of the routers in the areas where a user data packet starts and ends (which may be the same) are capable in that user data packet's protocol. The only other routers through which the user data packet travels are the Level-2 routers, and the Level-2 routers have sufficient capability to forward any user data packets that may be presented to them: either the Level-2 routers are dual-protocol, or, if they are not dual-protocol, the protocol which is not supported by the Level-2 routers is prohibited from operating outside of the individual areas. Thus, in the FIG. 1A architecture, all of the routers along any user data packet's path must be capable in that user data packet's protocol, and no encapsulation is required.
One algorithm that may be used by the routers of FIG. 1A when receiving user data packets is illustrated in FIG. 1B. Referring to FIG. 1B, when a router of FIG. 1A receives 102 (either from another router or from an attached end system) a user data packet addressed to an end system Z, the receiving router first reviews 104 the LSPs it has stored to determine if there is a router that has "advertised" a connection to end system Z. The router connected to end system Z will be called router A (note that, if end system Z is not in the same area as the receiving router, router A is the nearest level-2 router in the local area). Next, the receiving router checks 106 if router A is itself, i.e., if end system Z is connected to the receiving router. If not, the user data packet is forwarded 108 to the appropriate next router on the path to router A. However, if end system Z is connected to the receiving dual-protocol router, then the receiving dual-protocol router delivers 110 the user data packet to the appropriate end system.
Referring to FIG. 1C, when a dual-protocol router forwards 108 a user data packet toward router A, it determines 111 the first router in the path to router A and then sends 112 the user data packet on the link to that first router.
The operation of the algorithms discussed above can best be shown by example. Two examples of routing in the network of FIG. 1A are provided below. The first example does not involve Level-2 routing; the second example does.
In the first example, OSI end system 101 wishes to send a user data packet to OSI end system 103. To this end, it generates an OSI header addressed to end system 103, and forwards the user data packet to OSI-only router 105. Following the flow charts of FIGS. 1B and 1C, router 105 determines that the user data packet should be forwarded to OSI-only router 107, because router 107 has advertised a connection to end system 103 in its most recent LSP. Therefore, router 105 forwards the user data packet to router 107. Following the flow chart of FIG. 1B, router 107 determines that the user data packet is addressed to one of the end systems connected to it, and thus delivers the user data packet to end system 103.
In the second example, OSI end system 103 wishes to forward a user data packet to OSI end system 109. To this end, end system 103 generates a user data packet in OSI format, which it forwards to OSI-only router 107. Following the flow charts of FIGS. 1B and 1C, router 107 determines that the user data packet is not addressed to an end system in the local area, and thus it determines that the user data packet should be forwarded to dual-protocol router 111, which is the nearest Level-2 router in router 107's local area. Thus, router 107 forwards the user data packet on the link to OSI-only router 105 (which leads most directly to router 111). Following the flow charts of FIGS. 1B and 1C, router 105 then independently determines that the user data packet is not addressed to an end system in the local area, and thus determines that the user data packet should be forwarded to dual-protocol router 111. Thus router 105 forwards the user data packet on the link to router 111. Router 111, following the flow charts of FIGS. 2B and 2C, recognizes that the OSI user data packet should be forwarded toward the area router 115. The user data packet is then
forwarded through the Level-2 dual-protocol routers 113 and 115, eventually arriving at dual-protocol router 117. Following the flow charts of FIGS. 1B and 1C, router 117 determines that the user data packet is addressed to an OSI end system which is attached to it. Therefore, it delivers the user data packet to end system 109.
Before discussing other possible embodiments of the invention which involve encapsulation, it is useful to make the following observation: most of the complications associated with single-protocol routers occur when more than one type of single-protocol router appears in the same area. If there is only one type of single-protocol router in an area, all user data packets can be placed in the protocol of the single-protocol routers (by encapsulation if necessary), and then easily routed within the area.
Therefore, referring to FIG. 2A, a second embodiment of the invention explicitly prohibits the use of IP-only and OSI-only routers in the same area. In each area, one of the following is true: (1) the area is an "OSI-preferred area", and every router in the area operates as OSI-only or dual-protocol (e.g., the area 137 on the left of FIG. 2A); or (2) the area is an "IP-preferred area", and every router in the area operates as IP-only or dual-protocol (e.g., the area 139 in the right of FIG.
2A). Although the areas are designated as OSI-preferred or IP-preferred, because both types of areas include dual-protocol routers, there may be an IP end system in an OSI area (e.g., IP end system 135), and vice-versa. As a result, IP user data packets will be transmitted through OSI areas, and vice-versa. These packets may need to be encapsulated to traverse the single-protocol routers within the areas. For this reason, in the embodiment of FIG. 2A, all of the dual-protocol routers are "enhanced dual" routers.
The Level-2 backbone may be composed entirely of dual-protocol routers, as illustrated in FIG. 2A. Alternatively, the Level-2 router in an area may be single-protocol if the protocol not supported by the Level-2 router will be not be routed outside the area. One restriction that ensures that this will be the case is as follows: the Level-2 routers for an area must support the protocol used by any end system in the area. For example, for an area to have an IP-only Level-2 router, all of the end systems in that area must be IP. This restriction ensures that the single-protocol Level-2 routers will never be expected to perform Level-2 routing on a user data packet having an incompatible protocol (because all user data packets travelling into or out of an area must be to or from and end system in the area). However, it may be desireable to allow an area to use a protocol which is not supported by its Level-2 router(s), for example if the protocol is still being tested and has not been universally adopted. In the embodiments illustrated in FIG. 2A, there must be one common protocol which is supported by all Level-2 routers. For example, it is not permitted to have an OSI-only Level-2 router and an IP-only Level-2 router in the same routing domain (this topological restriction is removed in other embodiments of the invention).
Encapsulation is necessary within areas of the architecture of FIG. 2A because, within an area, all of the routers do not have the same capabilities. In addition, if there are single-protocol Level-2 routers, encapsulation may also be necessary at Level-2, because not all of the Level-2 routers would have the same capabilities. (Compare this situation to the discussion of FIG. 1A above, where all of the routers within an area and at Level-2 have the same capabilities, and because of this, encapsulation is not required.)
The following discussion of encapsulation will be directed to encapsulation at Level-1. However, for embodiments which have single-protocol routers at Level-2, the same techniques may be used to encapsulate at Level-2. To implement encapsulation, several issues must be confronted. First, there must be a way for routers to decide when encapsulation is necessary.
In known routing algorithms, when a router seeks to forward a user data packet, it consults a network map (generated from the link state packets) to determine the "best" path for the user data packet to follow to its destination. The user data packet is then forwarded on the link connecting to the first router on this path. (Note that the first router on the path must be on the other end of a link connected to the forwarding router.) Here, the user data packet's path is mapped in a similar manner; however, the mapping is done without regard for the protocols supported by the routers on the path.
Once the user data packet's path is chosen, the forwarding router attempts to forward the user data packet to the first router on the path. If the first router on the path does not support the user data packet's protocol, then encapsulation is required, and the forwarding router encloses the user data packet in a suitable encapsulation header before the user data packet is forwarded.
Note that only dual-protocol routers need to perform the analysis of the previous paragraph. The analysis of the previous paragraph is not necessary in single-protocol routers because they cannot encapsulate user data packets. Furthermore, the restrictions on the topology of FIG. 2A prevent any circumstances in which a single-protocol router would need to perform encapsulation (these circumstances can also be prevented in less restricted architectures, as discussed below), as follows: (1) any user data packet being forwarded by a single-protocol router is by definition formatted in the protocol supported by the single protocol router; (2) the topology of FIG. 2A prevents single-protocol routers from being connected to other routers which do not support their protocol. Thus, there are no circumstances in which a single-protocol router would need to encapsulate a user data packet.
Once a dual-protocol router decides that a user data packet needs to be encapsulated, it must have some way to address the encapsulation header so that the user data packet will arrive at the router which is expected to decapsulate the user data packet, and this destination router will know to do so. Such a mechanism prevents the user data packet from being lost in the network, and prevents the destination router from treating an encapsulated user data packet as an ordinary, non-encapsulated user data packet, and accidentally misinterpreting its contents or forwarding it without decapsulating it. To achieve these goals, encapsulated user data packets are uniquely addressed, in a manner consistent with the encapsulating protocol.
One possible way to properly address encapsulated user data packets is to assign a "dummy" end system address to each dual-protocol router (only dual-protocol routers are capable of decapsulating user data packets, therefore, only dual-protocol routers need to have such addresses). The link state packets of the dual-protocol routers "advertise" their dummy end system addresses along with other "real" end system addresses. Thus, within the LSPs, the dummy addresses are treated the same way as the addresses of real end systems connected to the dual-protocol router. When a dual-protocol router wishes to encapsulate a user data packet (only dual-protocol routers encapsulate user data packets) and send it to another dual-protocol router, it generates an encapsulation header, which it addresses to the dummy address for the destination router (the dummy address is placed in a predetermined location in the dual-protocol routers' LSPs, for example, it can be added to the beginning or end of the list of real end system addresses).
Between the encapsulating router and the decapsulating router, the encapsulated user data packet may pass through many other single- or dual-protocol routers. Each of these routers simply reads the user data packet's encapsulation header and, because the LSP of the destination router advertised the dummy address as an end system to which it is connected, the intermediate routers simply forward the encapsulated user data packet toward the destination router, in the same manner that ordinary, unencapsulated user data packets are forwarded.
When the encapsulated user data packet arrives at the destination router, the destination router recognizes the dummy address as indicating that the user data packet is encapsulating another user data packet. The destination router then removes the encapsulation header, and interprets the contents of the user data packet as a newly received user data packet.
Although the above methods determine when to encapsulate, and illustrate how to address user data packets so that they can be recognized and decapsulated, the dual-protocol router encapsulating a user data packet must also know where to send the encapsulated user data packet, i.e., which of the other dual-protocol routers to which the encapsulated user data packet should be addressed. Remember that the encapsulating router maps out the path the user data packet should follow to its destination before it decides if the user data packet should be encapsulated. Once a decision to encapsulate has been made, to minimize the number of encapsulations and decapsulations, the encapsulated user data packet should be addressed so that it passes through as many routers as possible before it needs to be decapsulated. However, the user data packet cannot travel through a router that does not support the encapsulating protocol. Therefore, the user data packet must be encapsulated before the first router on the path which does not support the encapsulating protocol. In the following, the router on the path just prior to the first router which does not support the encapsulating protocol will called the "last capable router on the path" (because this router is the last router in the chain of routers, starting at the router encapsulating the user data packet, which support the encapsulating protocol).
In some architectures (in particular, the architecture of FIG. 2A) the above-described "last capable router along the path" will always be the router to which the destination end system is connected. This is an advantage of the FIG. 2A architecture because, as discussed above, even in known networks which do not support dual-protocol protocols, routers forwarding user data packets must first determine the router to which the destination end system is connected. Thus, in the FIG. 2A architecture, this computation not only determines how to forward the user data packet, it also determines how to address the encapsulation header. (In other multi-protocol architectures--see the discussion of FIG. 3 below--the "last capable router along the path" will not always be the router to which the destination end system is connected. In these architectures, extra computation is required to determine how to address the encapsulation header).
Because the single-protocol routers in FIG. 2A do not perform encapsulation and therefore need not determine when to encapsulate, the algorithm used by the routers in FIG. 1A, i.e., that illustrated in FIGS. 1B and 1C, can be used by the single-protocol routers in FIG. 2A.
However, the dual-protocol routers of FIG. 2A must use a more complex algorithm for receiving and forwarding user data packets. Referring to FIG. 2B, when a dual-protocol router of FIG. 2A receives 120 (either from another router or from an attached end system) a user data packet addressed to an end system Z, the receiving dual-protocol router first reviews 122 the LSPs it has stored to determine if there is a router that has "advertised" a connection to end system Z. The router connected to end system Z will be called router A. If end system Z is not in the same area as the receiving dual-protocol router, router A is the nearest Level-2 router in the local area. Next, the receiving dual-protocol router checks 124 if router A is itself, i.e., if end system Z is connected to the receiving dual-protocol router. If not, the user data packet is forwarded 126 to the appropriate next router on the path to router A. However, if end system Z is connected to the receiving dual-protocol router, then the receiving dual-protocol router checks 128 if end system Z is the "dummy" end system, i.e., if the user data packet is an encapsulated user data packet. If not, the user data packet is delivered 132 to the appropriate end system. However, if the user data packet is an encapsulated user data packet, the encapsulation header is removed 130, and the user data packet contained therein is treated as a newly received user data packet by returning to step 120.
Referring to FIG. 2C, when a dual-protocol router forwards 126 a user data packet toward router A, it first determines 133 the first router in the path to router A. The dual-protocol router then checks 134 whether the first router in the path to router A is an OSI router, an IP router, or a dual IP-OSI router.
If the first router is a dual IP-OSI router, the forwarding router directly sends 140 the user data packet on the link to that first router without the need for any encapsulation.
If the first router is IP-only, the forwarding router checks 136 if the user data packet is formatted in IP. (The detailed description below discusses how the user data packet protocols may be properly recognized.) If not, the user data packet is encapsulated 138 in an IP header, which is addressed to router A. Note that, if the destination end system is in the local area, then router A is the "last capable router on the path", as discussed above. However, if the destination end system is not in the local area, then router A is the nearest Level-2 router in the local area, which will decapsulate the user data packet (the Level-2 router must be dual-protocol if OSI and IP traffic is being routed outside the local area) and forward it via Level-2 routing to the correct area (which may involve additional encapsulations and decapsulation) where the Level-1 routing will deliver the packet (possibly after further encapsulation and decapsulation) to the destination end system. Regardless of whether the user data packet is encapsulated, it is sent 140 on the link to the first router in the path to router A.
Similarly, if the first router is OSI-only, the forwarding router checks 142 if the user data packet is formatted in OSI. If not, the user data packet is encapsulated 144 in an OSI header, which is addressed to router A. Regardless of whether the user data packet is encapsulated, it is sent 140 on the link to the first router in the path to router A.
The use of the above algorithms can be best shown by example. Two examples of routing in this architecture are provided below; the first example does not involve encapsulation, whereas the second requires encapsulation.
In the first example, TCP/IP end system 121 wishes to forward a user data packet to TCP/IP end system 123. To this end, end system 121 forms an IP user data packet addressed to end system 123. This user data packet is forwarded to IP-only router 125. Router 125, following the flow charts of FIGS. 1B and 1C, determines that the user data packet should be forwarded toward dual-protocol router 127. The user data packet is then forwarded to dual-protocol router 129, which is the first router on the path to router 127. Router 129 receives the user data packet, and following the flow charts of FIGS. 2B and 2C, also determines that the user data packet should be forwarded toward dual-protocol router 127, and that it need not be encapsulated because the next route is IP-capable (router 125 did not need to decide whether to encapsulate the user data packet because it is an IP-only router). In this way, the user data packet eventually arrives at dual-protocol router 127. Router
127 then follows the flow chart of FIG. 2B and determines that lp end system 123 is attached to it, and that the address of end system 123 is not its dummy address. Therefore, it delivers the user data packet to end system 123.
In the second example, TCP/IP end system 135 wishes to forward a user data packet to TCP/IP end system 123. To this end, end system 135 generates a user data packet in IP format, which it forwards to dual-protocol router 131. Following the flow chart of FIG. 2B, dual-protocol router 131 determines that the user data packet is not addressed to an end system in the local area, and thus it determines that the user data packet should be forwarded to dual-protocol router 133, which is the nearest Level-2 router in router 131's local area. Also, router 131 determines that the user data packet should be encapsulated because the next router is OSI-only and the user data packet is formatted for IP. Thus, router 131 generates an encapsulation header addressed to router 133's dummy address, and forwards the user data packet on one of the links leading to router 133. The OSI-only and dual-protocol routers in router 133's area then forward the user data packet as any other OSI user data packet until it reaches dual-protocol router 133. Router 133, following the flow chart of FIG. 2B, determines that the user data packet is addressed to its dummy address, and therefore is an encapsulated user data packet. The encapsulation header is removed, and router 133 analyzes the internal user data packet. Following the flow charts of FIGS. 2B and 2C, router 133 then recognizes that the IP user data packet should be forwarded toward the nearest Level-2 router in the destination area (i.e., router 141). The user data packet is then forwarded, without encapsulation, through the Level-2 dual-protocol routers, eventually arriving at router 141 (alternatively, where there are single-protocol routers at Level-2, there may also be encapsulation at Level-2). Following the flow charts of FIGS. 2B and 2C, router 141 determines that the user data packet should be forwarded toward router 127, and that it need not be encapsulated because the next router can understand IP. Therefore, router 141 forwards the user data packet toward router 127. When the user data packet arrives at router 127, it follows the flow chart of FIG. 2B and determines that TCP/IP end system 123 is attached to it, and that the address of end system 123 is not its dummy address. Therefore, it delivers the user data packet to end system 123.
In two simplified forms of the embodiment illustrated in FIG. 2A, either OSI-only or IP-only routers are prohibited from the network. In these embodiments, FIG. 2C can be simplified by simplifying the check at step 134, and removing either steps
142 and 144, or steps 136 and 138. In either embodiment, the Level-2 backbone may operate as all dual-protocol, or may be a mixture of dual-protocol and single-protocol routers, as long as the restriction discussed above is met (i.e., that any protocol not supported by an area's Level-2 router cannot be routed outside that area).
One advantage of the "per-area" embodiments discussed above is that they allow for a graceful evolution of the network from one protocol to another. Currently, TCP/IP is the dominant protocol suite (at least in most environments in the United States). Thus it is likely that, initially, users would choose to implement a network of IP-only and dual-protocol routers. These will operate together in a graceful manner (for example, where necessary, encapsulation will occur automatically). As OSI becomes more important, the IP-only routers would be upgraded to dual-protocol routers, probably eventually resulting in an all-dual routing domain. Assuming that OSI will eventually supersede TCP/IP, then during the last step of migration, users will gracefully replace some of the dual-protocol routers with OSI-only routers, and/or add additional OSI-only routers. All of this will be quite graceful, as long as OSI-only and IP-only routers are never placed in the same area.
The per-area embodiments of the invention described above are quite flexible and have several advantages which have been disclosed. One drawback of these embodiments is that they have topological restrictions, namely, OSI-only and IP-only routers cannot be placed in the same area. However, if there are three types of routers (IP-only, OSI-only, and dual-protocol), some users may desire (and can be expected) to connect the routers together in the same area regardless of the restrictions imposed by the routing algorithm. Therefore, in another embodiment of the invention, these per-area topological restrictions are eliminated.
The embodiment of the invention illustrated in FIG. 3 has fewer topological restrictions than the preceding embodiments, in particular, OSI-only and IP-only routers are allowed to coexist in a given area. The network of FIG. 3 may represent one area of a larger network, or it may represent the Level-2 backbone of a network, where the depicted routers reside in local areas. (Note that if FIG. 3 represents an area, the Level-2 router in the area must be dual-protocol if both OSI and IP traffic is to be routed outside of the local area.)
The topology of FIG. 3 is more flexible than the topologies of FIGS. 1A or 2A, but routing user data packets through this topology is more complicated. Specifically, the following complications arise when OSI-only and IP-only routers are mixed within an area.
A first complication is that users may accidentally connect links between routers that do not support a common protocol. There must be a mechanism to ensure that such links are never recognized or used by the routers, because all user data packets sent along such links will be lost. For example, the erroneously connected link between OSI-only router 166 and IP-only router 168 (indicated by a dotted line) must never be used. There are several possible ways to prevent such links from being used.
One solution is to configure the OSI-only and IP-only routers to use different values in the protocol data unit (PDU) type field (see Section 9 of the above-referenced 10589 specification) of their hello packets. Therefore, OSI-only routers would think that the hello packets sent by the IP-only routers are invalid, and vice-versa.
Another solution is to encapsulate the hello packets sent by IP-only routers inside other IP packets, so that they are ignored by OSI-only routers.
A third solution is to alter the sub-network dependent link initialization procedures in IP-only routers or OSI-only routers (or both), so as to prevent the link from becoming valid. It may be more convenient to perform these modifications in the IP-only routers because, currently, the IP specification is less rigid.
A second complication with the FIG. 3 embodiment is that IP-only and OSI-only routers can occur on the same LAN. (Note that if a LAN spans two areas, ISO 10589 ensures than the Level-1 routers from different areas on the LAN will ignore each other. This ensures that this issue does not arise in the previous "per-area" embodiments.) Providing dual protocols on LANs raises several issues that must be confronted.
Each LAN has an elected "designated router". The designated router is responsible for updating the LAN routers about the LAN topology. Although the actual topology is a single link connecting all of the routers, the topology reported by the designated router is a star, where the center of the star is a "pseudonode". (The designated router generates a link state packet for the pseudonode indicating a star connection to all of the other routers on the LAN.) As a result, the first router on the path to the user data packet's destination is always the pseudonode, and the second router on the path is the router to which the user data packet should be directly transmitted. The pseudonode is a notational convention--when transmitting a user data packet over a LAN, the user data packet is typically forwarded to the second router on the path to its destination, rather than to the first router.
The above mechanism works properly when the routers on the LAN all support one of the protocols. For example, if there are no IP-only routers on the LAN, then OSI-only routers may forward user data packets on the LAN in the normal fashion (because any user data packets forwarded by an OSI-only router must be formatted for OSI, and all routers on the LAN support OSI). Also, dual-protocol router may forward user data packets on the LAN in the manner described above (i.e., OSI user data packets are forwarded in the normal fashion, and IP user data packets are encapsulated if the next router is OSI-only). The designated router may be chosen to be an OSI-only or dual-protocol router, because either will be able to exchange control packets with the remainder of the routers on the LAN, and thus learn the full topology of the LAN. The situation is similar where there are no OSI-only routers on the LAN.
If there are OSI-only and IP-only routers on the LAN, then several difficulties arise. First, an appropriate "designated router" must be elected for the LAN. IP-only routers cannot correctly interpret fields in control packets exchanged with OSI-only routers (and vice-versa); therefore, the designated router cannot be either IP-only or OSI-only, because neither can correctly learn the entire LAN topology and generate the appropriate link state packet for the pseudonode. There are two possible solutions.
The first solution is to elect a dual-protocol router as the designated router. The dual-protocol router can correctly exchange control packets with all of the other routers, and thus can learn the entire LAN topology. To do this, the dual-protocol designated router send two sets of hello packets, one of which is interpreted by dual-protocol and IP-only routers and one of which is interpreted by dual-protocol and OSI-only routers. Once it has learned the LAN topology, the dual-protocol router then generates a link state packet for the pseudonode, which lists all of the routers on the LAN, regardless of their protocol capabilities. Note that if there are no single-protocol routers on the LAN, the dual-protocol routers send hello packets in a "preferred" format, for example the OSI format, elect one dual-protocol router as designated router, and use the "preferred" format for control and user data packets on the LAN.
The first solution can only be used if there is a dual-protocol router on the LAN. If there are no dual-protocol routers on the LAN, the second solution must be used. In the second solution, two designated routers are elected, one which is IP-capable and one which is OSI-capable. To do this, the IP-capable routers on the LAN exchange control packets with other IP-capable routers, and elect one as an IP-capable designated router, and similarly, the OSI-capable routers exchange control packets with other OSI-capable routers, and elect one as an OSI-capable designated router. (If there is a dual-protocol router on the LAN and the second solution is chosen, then the dual-protocol router may be elected as both pseudonodes.) The IP-capable and OSI-capable pseudonodes then exchange control packets with the other IP-capable or OSI-capable routers, respectively, and learn that portion of the LAN topology which is capable in their protocol. Next, the two pseudonodes generate two link state packets, one for an "IP pseudonode" and one for an "OSI pseudonode". The IP pseudonode link state packet lists only the IP-capable routers on the LAN, and the OSI pseudonode link state packet lists only the OSI-capable routers on the LAN. (If there is one or more dual-protocol router on the LAN and the second solution is chosen, then the dual-protocol router(s) will be listed in both pseudonode link state packets.)
When IP-only and OSI-only routers occur on the same LAN, the forwarding of user data packets on that LAN may also be more complicated.
As discussed above, when forwarding a user data packet on a LAN, typically the user data packet is sent to the second router on the path to its destination (i.e., the packet is sent to the router after the pseudonode). To allow OSI-only and IP-only routers on the same LAN, the following restrictions are added: (i) if the router doing the forwarding is dual-protocol, it first determines whether the user data packet is compatible with the second router--if not, it encapsulates the packet before forwarding it; (ii) if the router doing the forwarding is a single-protocol router, and there are two pseudonodes, then all routers that the single-protocol router is aware of (i.e., those listed in the appropriate pseudonode LSP) will be capable in the protocol of the single-protocol router, and the user data packet can be forwarded in the normal fashion; however (iii) if the router doing the forwarding is a single-protocol router, and there is only one pseudonode, then it is possible that the second router (i.e., the router after the pseudonode) may be a single-protocol router supporting the wrong protocol suite. Therefore, in this case the single-protocol router forwards the user data packet to a dual-protocol router on the LAN (perhaps to the designated router, which must be dual), rather than to the second router. The dual-protocol router can then encapsulate the packet if required.
A third complication with the FIG. 3 embodiment is that encapsulation is more complex. Note that, in the topology of FIG. 3, user data packets may need to be encapsulated to traverse the single-protocol routers within the areas; therefore, all of the dual-protocol routers must be "enhanced dual" routers. For example, consider an OSI user data packet which needs to traverse a path from OSI end system 155 connected to OSI-only router 154 to OSI end system 157 connected to OSI-only router 156. The user data packet (at minimum) must be encapsulated by dual-protocol router 162, so that it can traverse IP-only router 163. Also, the user data packet must be decapsulated by router 164 before it can be sent to router 166, however, it must remain encapsulated if it is to be sent through router 168 and then decapsulated at router 170.
In the above discussion of FIG. 2A, it was asserted that, to minimize the number of encapsulations and decapsulations, an encapsulated user data packet should be addressed so that it passes through as many routers as possible before it needs to be decapsulated, i.e., to the last router along the path that supports the encapsulating protocol. It was also noted that, in more complex architectures, the "last capable router along the path" will not always be the router to which the destination end system is connected. This is clear from the above example, as the "last capable router on the path" may be router 164 (if it is desirable to route through router 166), or it may be router 170 (if it is desirable to route through router 168).
The encapsulation header must be addressed to the "last capable router along the path" for the user data packet to be correctly decapsulated. To allow this, the above-referenced Dijkstra algorithm must be modified so that it not only indicates which neighboring router to forward the user data packet to, but (where necessary) also specifies which destination address needs to be used for the encapsulating header (i.e., which router is the "last capable router along the path").
A routing tree such as illustrated in FIG. 4B is generated by the Dijkstra algorithm of FIG. 4A. Referring to FIGS. 4A and 4B, to initialize the Dijkstra algorithm, the router generating the tree first creates 180 (FIG. 4A) a node 181 (FIG. 4B) representing itself at the root of the tree. Next, nodes 183 representing the neighbors of the router generating the tree are placed 182 below the root of the tree as "tentative". The relationship of node 181 to 183 is a parent-child relationship. In the following, the node further from the root node 181 may be referred to as the "child", and the node closer to the root node 181 may be referred to as the "parent".
When a node representing a router is placed on the tree tentatively, it indicates that one path through the network to the router has been located (namely, the path through the routers represented by the nodes between the tentative node and the root node 181). As will be seen below, tentative nodes are made permanent once the Dijkstra algorithm verifies that the tentative path to the represented router is the best possible path. To perform this verification, the algorithm performs a loop, locating permanent paths to each router in the network, until paths to all routers have been determined. The routing tree in FIG. 4B represents a tree in the midst of construction. The nodes in FIG. 4B with a dark outline are permanent, whereas the nodes in FIG. 4B with a light outline are tentative--nodes 187 have been added as tentative nodes, and node 189 has been made permanent.
In each pass of the Dijkstra loop, the "closest" tentative node to the root node 181 is located 184 and made permanent (the length, or "cost", of a path from the router represented by the root node to the router represented by another node is calculated using a suitable metric such as link delay times). The closest tentative node may be made permanent because the path from the root to the closest tentative node must be the best path to the router represented by the tentative node; any other possible paths to the represented router would have to pass through one of the other tentative nodes, and thus would by definition be "longer" paths (because links never have negative cost).
Once the closest tentative node is made permanent, the routers which neighbor the router represented by the newly permanent node are added 186 tentatively to the tree as children of the newly permanent node. However, if any of these neighboring routers is already represented by permanent node on the tree, then a tentative node representing the neighboring router is not added to the tree (because a better path to the neighboring router has already been found). Also, if any of the neighboring routers is already represented by a tentative node on the tree, then a comparison is made between the existing path to the neighboring router (i.e., the path represented by the existing tentative node) and the new path to the neighboring router. If the new path is "shorter" (in the sense discussed above) than the existing path, a new tentative node representing the new path is added to the tree, and the existing tentative node is removed. Otherwise, the existing tentative node is retained, and no new tentative node is added.
There is the possibility that two paths to the same router will be equal in "length" or very similar in length. In these cases, it is necessary and/or useful to implement a tie-breaking routine, which breaks such ties or near ties in a well-behaved manner. This can help to share network traffic loads between paths of equal or almost-equal cost.
Finally, 188, the algorithm checks if there are any tentative nodes left (i.e., if there are any routers to which paths have been established, but to which best paths have yet to be determined). If not, the algorithm ends. Otherwise, the algorithm proceeds to step 184, and makes another tentative node permanent.
Referring to FIG. 5A, several fields of data may be contained in each of the node data structures of the tree of FIG. 4B. Fields 190 contain general information useful for performing the Dijkstra algorithm.
The name field 192 contains the name of the router which a node represents. The name of the router represented by a node is placed in the name field when the node is first created.
The first hop field 194 contains the name of the first router on the path from the router generating the routing tree to the router which the node represents. This field is used by the router generating the routing tree to determine where (i.e., to which of its neighboring routers) a user data packet should be forwarded. This information is generated as follows: when a node 183 representing a router which directly neighbors the router generating the routing tree (represented by node 181) is added to the tree (step 182, FIG. 4A), the name of the neighboring router (i.e., the router represented by the node 183) is placed in the name field 192 and in the first hop field 194 of the node 183. Thereafter, when another tentative node is added to the tree (step 186, FIG. 4A) below a parent permanent node, the first hop field 194 in the new node is set to the value of the first hop field 194 in the parent node. In this way, the first hop values are established when the nodes 183 are added to the tree, and these values are maintain throughout the branches of the tree leading from the nodes 183.
The status field 196 indicates whether the router represented by a node is in operation, and may also represent the level of operability of the router or its links. This information may be used to route user data packets around faulty routers, or to wait for a router to become operable before sending user data packets.
The cost field 198 indicates the total cost of the route from the router represented by the root node 181 to the router represented by the node. This information is used when comparing two tentative nodes to determine which is closer to the root node 181. The cost information may be derived from one of many well known metrics. The cost is determined by adding the cost of the link from the parent node to a new child node to the cost of the parent node. The cost of the root node 181 is defined to be zero, or another predetermined value.
Fields 190 contain enough information to generate a routing tree from LSPs, and to forward user data packets along a path having the lowest cost according to the selected cost metric. However, as discussed above, the embodiment illustrated in FIG. 3 is complex because, if encapsulation is required, it is necessary for the Dijkstra algorithm also to specify which destination address needs to be used for the encapsulating header.
To this end, additional fields 200 are added to the node data structures. These fields contain information used in encapsulation, and are filled out as described below. Because single-protocol routers in FIG. 3 do not perform encapsulation, the single-protocol routers generate a routing tree having only the fields 190. However, dual-protocol routers in FIG. 3 also generate fields 200, because they perform encapsulation.
The encapsulation router (ER) field 202 indicates the name of the last router along the path to the router represented by the node which supports the encapsulating protocol. This is the router to which the encapsulating header should be addressed.
To clarify this idea, refer to the example of FIG. 3, where an OSI user data packet was being sent from OSI end system 155 to OSI end system 157. For the purpose of this example, assume that the lowest cost path passes from OSI-only router 154
through routers 162, 163, 159, 158, 164, 166, 170, and 156. Then dual-protocol router 162 must encapsulate the user data packet in an IP header, and address the IP header to dual-protocol router 164, because dual-protocol router 164 is the last router along the path which supports the IP protocol.
Now assume that the lowest cost path passes from OSI-only 154 through routers 162, 163, 159, 158, 164, 168, 170, and 156. In this case, dual-protocol router 162 must still encapsulate the user data packet in an IP header, but the header must be addressed to dual-protocol router 170, because router 170 is now the last router along the path which supports the IP protocol.
Note that alternative encapsulation methods are possible: for example, user data packets can be encapsulated to the first dual-protocol router along the path to the use data packet's destination. In this case, router 162 would address the IP encapsulation header to dual-protocol router 164. However, if the lowest cost path passed through router 168, router 164 would remove the header, determine that the user data packet should be forwarded through router 168, and then add a new encapsulation header addressed to dual-protocol router 170, and finally forward the user data packet to router 168. This method involves an additional encapsulation and decapsulation, which is avoided by sending the encapsulated user data packet to the "last capable router along the path".
Note that the "last capable router along the path" may simply be the last router along the path. For example, consider a user data packet being sent from OSI end system 155 to OSI end system 169. In this case, when dual-protocol router 162
encapsulates the user data packet in an IP header, the last capable router along the path will be dual-protocol router 164. Therefore, the encapsulation header should be addressed to dual-protocol router 164.
Furthermore, note that a dual-protocol router may not always need to encapsulate a user data packet. For example, consider an OSI user data packet being forwarded from OSI end system 155 to OSI end system 172. In this case, when the user data packet arrives at dual-protocol router 162, there is no need for encapsulation, and it can be simply forwarded in OSI format to router 167. Therefore, for some destination routers, there is no "last capable router along the path", simply because every router along the path is capable.
A value of "?" in the ER field indicates that the value for the "last capable router along the path" is not needed. This may be because, even though encapsulation is required, the last router along the path is the last capable router (as in the embodiment of FIG. 2A), or, alternatively, because encapsulation is not required.
Referring to FIG. 5A, as the routing tree is being generated, two flags are used to determine whether encapsulation is required, and which router "is the last capable router along the path". These flags are referred to as the IP flag 204 (which indicates whether the first router along the path is IP-capable) and the OSI flag 206 (which indicates whether the first router along the path is OSI-capable). These flags are used to determine the value of the ER field as the routing tree is built.
Referring to FIG. 5B, during step 182 of the Dijkstra algorithm, nodes for the routers neighboring the router generating the tree are added to the tree. For dual routers, this step involves updating the ER field and the OSI and IP flags. A loop is initialized 210 at the first neighbor, and for each neighbor, the loop analyzes 212 if the neighbor is already tentative. If there is not an existing tentative node for the neighbor, then a new tentative is added 218 to the tree. If there is a tentative node for the neighbor, then the cost of the known path to the neighbor (as represented by the tentative node) is compared 214 to the cost of the new path to the neighbor. If the new path is shorter, the existing tentative is deleted 216, and a new tentative is added 218 to the tree. If the new path is longer, then the new path is ignored by skipping to step 228. A tie-breaking mechanism is used to choose between paths having equal or near equal cost. (See the discussion of FIG. 5C below for a review of the considerations involved in tiebreakers).
When a node for the new neighbor is added 218 to the tree, the ER field for the new node is set to "?". This is because all of the nodes added to the routing tree in FIG. 5B are the immediate neighbors of the router generating the tree. For these nodes, the ER field will always be set to "?" because immediate neighbors are the only routers along the path to themselves, and thus must be the "last capable router along the path". That is, there is never a need to encapsulate user data packets which are destined to an immediately neighboring router, because the end system to which the user data packet is direct must be capable in the user data packet's protocol, and the neighbor must be capable in the protocol of the end system because the end system is connected to it.
After the ER field is set to "?", the IP and OSI flags are set for future use. If 220 the neighbor supports OSI, the OSI flag is set 221, otherwise the OSI flag is cleared 222. If 224 the neighbor supports IP, the IP flag is set 225, otherwise the IP flag is cleared 226.
After the node is created and the ER field and IP flag are initialized (or after it is determined in step 214 that a known path to the neighbor is shorter than the new path to the neighbor), the algorithm of FIG. 5B checks 228 whether there are additional neighbors that may be added to the tree. If not, the algorithm ends 229, otherwise, the algorithm moves 230 to the next neighbor and returns to step 212.
During each loop of the Dijkstra algorithm, the neighbors of a newly permanent node are added as tentative nodes below the newly permanent node (step 186, FIG. 4A). In the dual-protocol routers of FIG. 3, step 186 also involves manipulating the ER field and the IP flag.
Referring to FIG. 5C, an algorithm for adding new tentative nodes forms a loop similar to that of FIG. 5B. The loop is initialized 240 at the first neighbor. For each neighbor, the loop checks 242 if the neighbor is already permanent on the routing tree. If the neighbor is already permanent on the routing tree, then the shortest path to the neighbor has already been located, and the new path is ignored by skipping to step 264. (Note that the algorithm of FIG. 5B does not check if nodes are already permanent because none could be permanent at that point in the Dijkstra algorithm).
However, if the neighbor is not already permanent, the loop checks 244 if a tentative node for the neighbor already exists. As in FIG. 5B, if no tentative node for the neighbor exists, a new tentative node for the neighbor is added 250. If a tentative node for the neighbor already exists, the loop checks 246 if the new path to the neighbor has a lower cost than the known path to the neighbor. If the known path is shorter, then the new path is ignored by skipping to step 264. Otherwise, the existing tentative is removed 248, and a new tentative is added 250.
A tiebreaking mechanism is used in step 246 to choose between paths of equal or near equal cost. However, this tiebreaking mechanism must be carefully selected, to avoid the possibility that routers between the source of an encapsulated user data packet and the destination of the user data packet disagree over the outcome of the tiebreak, and thus route the user data packet in a manner not anticipated by the encapsulating router. If a disagreement occurs, user data packets may accumulate more than one encapsulation header on the way to their destination.
For example, referring to FIG. 3, consider an OSI user data packet that is to be transmitted from OSI-only router 155 to OSI-only router 157. The user data packet is forwarded unencapsulated to dual-protocol router 162, at which point it must be encapsulated to travel through IP-only router 163. There are two paths from IP-only router 163 to dual-protocol router 164. The first path travels through IP-only routers 159 and 158, and the second path through dual-protocol router 174 and OSI-only router 160. Assume that these paths are very close in cost, and that dual-protocol router 162 has performed a tiebreaker to determine that the path through IP-only routers 158 and 159 should be used.
As a result, dual-protocol router 162 generates an IP encapsulation header addressed to dual-protocol router (assume that the shortest path to OSI end system 157 passes through IP-only router 168, and thus dual-protocol router 170 is the last IP-capable router on the path to router 156). This IP header is prepended to the OSI user data packet, and the user data packet is forwarded to IP-only router 163.
On receipt of the IP user data packet addressed to router 170 (i.e., the encapsulated OSI user data packet), IP-only router 163 consults its routing tree. Assume that IP-only router 163 has also performed a tiebreaker to determine which path to use to forward user data packets toward dual-protocol router 164. However, IP-only router 163 has decided that the path through dual-protocol router 174 and OSI-only router 160 should be used. Therefore, on receipt of the IP user data packet addressed to router 170, IP-only router 163 forwards the user data packet to dual-protocol router 174.
Dual-protocol router 174, on receipt of the IP user data packet addressed to router 170, also consults its routing tree. Its routing tree indicates that the best path to router 170 is through OSI-only router 160, dual-protocol router 164, and IP-only router 168. Therefore, not realizing that the received IP user data packet is in fact an encapsulated OSI user data packet, dual-protocol router places an OSI encapsulation header on top of the IP encapsulation header already present on the user data packet. This second encapsulation header is addressed to router 164 because router 164 is the last OSI capable router along the path to router 170. The doubly-encapsulated user data packet is then forwarded to router 160.
OSI-only router 160 then forwards the doubly-encapsulated user data packet to dual-protocol router 164. Dual-protocol router 164, recognizing the user data packet as addressed to its dummy encapsulation address, removes the outer OSI header, and analyzes the inner encapsulation header, which is addressed to router 170. Dual-protocol router 164 then consults its routing tree, and determines that the best route to dual-protocol router 170 is through IP-only router 168. As the user data packet is already formatted in IP, it is forwarded without encapsulation to router 1 68. Router 168 then forwards the user data packet to router 170, which removes the IP encapsulation header and forwards the OSI user data packet to router 156 and from there to OSI end system 157.
The difficulty with the above scenario is that the OSI user data packet accumulated two encapsulation headers in the course of its transmission. This increases the overhead at the dual-protocol routers, and also increases the load on the links because the user data packet size is larger. The extra headers were caused by the fact that two of the routers in the network (in particular, routers 162 and 163) disagreed on how to break a tie between equal cost paths. Thus, to prevent extra headers, the tiebreaking algorithm must be consistent, i.e., all of the routers in the network must agree on which path wins a tie. (See the discussion of FIG. 6 below for a description of other ways that tiebreak algorithms that are not consistent can also be used.)
One consistent tiebreaking mechanism breaks ties based on the names of the routers involved in the paths. For example, consider the case where two paths through the network join at router A, and the two paths have equal (or near equal) cost. On the first path, the router just before router A is router B, and on the second path, the router just before router A is router C. This tie is broken by comparing the names of routers B and C, for example, the tie can be broken in favor of the path passing through router B because B is alphabetically prior to C. (Router names may be interpreted as multi-bit characters or as binary strings; in either case the names are unique and can be used to break ties.)
In the algorithm of FIG. 5C, when two paths join, one of the paths is chosen at step 246. For example, consider the following sequence of events: first, a node representing router C is made permanent on the routing tree, and a node representing router A is then added as a tentative node below the node representing router C. Later, a node representing router B is made permanent on the routing tree, and the algorithm of FIG. 5C attempts to add a node representing router A below the node representing router B. The algorithm would then notice (at step 244) that there is already a tentative node for router A, and would compare (at step 246) the cost of the known path to the existing tentative (i.e., the path through C) to the cost of the new path (i.e., the path through B). Noting that these paths are equal (or nearly equal), the algorithm then breaks the tie by comparing the names of two parents. Because the parent of the existing tentative is router C, whereas the parent of the new tentative would be router B, the algorithm breaks the tie in favor of the new path, and continues to step 248.
Note that all of the routers in the network will break ties in the same way if the above mechanism is used, and therefore, assuming that the LSPs are reliably propagated to all routers, all of the routing trees will be consistent. Also, note that this mechanism cannot be used in FIG. 5B because, in FIG. 5B, all of the routers added directly neighbor the router generating the routing tree, and thus the "parents" of the two tentative nodes are the same. However, the tiebreaking mechanism used in FIG. 5B may be selected at will (for example, it may be random) because there are no routers between the source and destination that could disagree over the outcome of the FIG. 5B tiebreakers.
Returning to FIG. 5C, when a new tentative node is added 250, the ER field, IP and OSI flags are initialized to their values in the parent of the new tentative node. This is done so later comparisons can determine whether the "last capable router along the path" has been located. First, the loop checks 252 if the ER field is set to "?". If not, then the "last capable router along the path" has already been located, and there is no need for further analysis, so the loop skips to step 262. However, if the ER field is set to "?", then the loop analyzes if the "last capable router along the path" has now been located.
To determine if the "last capable router along the path" has been located, the loop first checks 254 if the IP flag is set. If the IP flag is set and the ER field is "?", it indicates that all of the routers along the path from the router generating the tree to the router which is currently being added to the tree are IP-capable routers. This continuous chain of IP-capable routers will be broken only if the router currently being added to the tree is not IP-capable. Therefore, if the IP flag is set, the loop checks 256 if the neighbor currently being added to the tree is IP-capable--if it is, then the chain of IP-capable routers remains unbroken, and the loop skips to step 262. However, if the router currently being added to the tree does not support IP, the chain of IP-capable routers has been broken, and the "last capable router along the path" is the parent of the new tentative node (i.e., the node most recently made permanent in step 184, FIG. 4A). Therefore, the ER field is set
258 to the name of the parent of the new tentative node.
Similarly, if the IP flag is cleared, then the OSI flag must be set (because the IP flag will only be cleared if the first router along the path was OSI-only). If the IP flag is cleared and the ER field is "?", it indicates that all of the routers along the path from the router generating the tree to the router which is currently being added to the tree are OSI-capable routers. This continuous chain of OSI-capable routers will be broken only if the router currently being added to the tree is not OSI-capable. Therefore, if the IP flag is cleared, the loop checks 260 if the neighbor currently being added to the tree is OSI-capable--if it is, then the chain of OSI-capable routers remains unbroken, and the loop skips to step 262. However, if the router currently being added to the tree does not support OSI, the chain of OSI-capable routers has been broken, and the "last capable router along the path" is the parent of the new tentative node (i.e., the node most recently made permanent in step 184, FIG. 4A). Therefore, the ER field is set 258 to the name of the parent of the new tentative node.
Note that, if the first router along the path is a dual-protocol router, no encapsulation is necessary, and both the OSI and IP flags will be set. However, the above algorithm will treat this case as if the first router along the path were IP-only; i.e., the algorithm will set the ER field to the last IP-capable router on the path. However, as encapsulation will not be done, this value will never be used, and it is merely an artifact of the algorithm's implementation. Alternative algorithms could avoid determining a value for ER when the first router on the path is dual-protocol. For example, a "dual" flag, indicating whether the first router on the path was dual-protocol, could be added to the node data structure--this flag could then be checked before any other tests were made, and the tests skipped if the flag is set. The same function could be achieved without storing an additional flag by simply checking if both the IP and OSI flags are set, and skipping the rest of the operations if they are. However, these alternative algorithms involve data storage and true/false comparisons not required by the algorithm presented.
After the ER field is modified as appropriate, a new tentative node for the neighbor is added 262 to the routing tree. Then (or after it is determined in either steps 242 or 246 that a better path to the neighbor is already known) the algorithm checks 264 whether there are additional neighbors that may be added to the tree. If not, the algorithm ends 265, otherwise, the algorithm moves 266 to the next neighbor and returns to step 242.
The above algorithms are used by the dual-protocol routers of FIG. 3 to generate their routing trees. The single protocol routers of FIG. 3 do not encapsulate user data packets, and thus do not include the fields 200 (FIG. 5A) in their routing tree, and do not perform the more complex algorithms of FIGS. 5B and 5C to form their routing trees.
The single-protocol routers of FIG. 3 receive and forward user data packets in accordance with the algorithms of FIG. 1B and 1C. The dual-protocol routers of FIG. 3 receive user data packets in accordance with the algorithm of FIG. 2B, and forward user data packets (step 126, FIG. 2B) in accordance with the algorithm of FIG. 6.
Referring to FIG. 6, when a user data packet is to be forwarded from a dual-protocol router, the router first determines 270 if the user data packet is OSI. If the user data packet is OSI, the OSI flag of the node in the routing tree which represents router A is checked 272. If the user data packet is not OSI, the IP flag of the node in the routing tree which represents router A is checked 274. If the respective flag is set at step 272 or step 274, then the first router along the path to router A is capable in the protocol of the user data packet, and that the user data packet is forwarded unencapsulated at step 276.
However, if the respective flag is not set at step 272 or 274, then the first router along the path to router A is not capable in the protocol of the user data packet. Therefore the user data packet must be encapsulated.
If the user data packet is OSI and router A's OSI flag is not set, then the algorithm checks 278 if router A's ER is set to "?". If ER is "?", then there is no encapsulation router (as discussed above), and the user data packet can be encapsulated directly to router A. Therefore, if ER is "?" an IP encapsulation header addressed to router A is generated 280. Otherwise, an IP encapsulation header addressed to the encapsulation router is generated 282.
Similarly, if the user data packet is IP and router A's IP flag is not set, then the algorithm checks 284 if router A's ER is set to "?". If ER is "?", then there is no encapsulation router (as discussed above), and the user data packet can be encapsulated directly to router A. Therefore, if ER is "?" an OSI encapsulation header addressed to router A is generated 280. Otherwise, an OSI encapsulation header addressed to the encapsulation router is generated 282.
After the encapsulation header is generated, the user data packet is encapsulated 290 in the header, and the encapsulated user data packet is forwarded on the next link to router A.
As described above, if an inconsistent tiebreaking mechanism (such as a random mechanism) is used in generating the network's routing trees, there is the possibility that user data packets gain multiple encapsulation headers as they are forwarded through the network.
One way to avoid this situation is to modify the forwarding algorithm of FIG. 6 so that, before user data packets are encapsulated, the algorithm checks whether the user data packet is already encapsulated. If there is already an encapsulation header on the user data packet, and the encapsulation header is incompatible with the next router's protocol, the user data packet can be made compatible by simply removing the previous encapsulating header, instead of adding a second header. In this way, multiple encapsulations can be avoided even where inconsistent tiebreaking mechanisms are used.
For this scheme to be feasible, there must be a mechanism for marking user data packets so that they can be recognized as encapsulated user data packets.
One way this can be done is to check if the user data packet is addressed to a "dummy address". (The dummy address appears in a predetermined position of the LSPs, and thus can be distinguished from real addresses.)
Another way this can be done is by marking all encapsulated user data packets so they may be immediately recognized as such. User data packets can be marked in several ways, depending on the encapsulating protocol. OSI user data packets can be marked by reserving one of the possible values of the 8473 select field ("SEL"). When the SEL field is set to this reserved value, it is an indication that the OSI header is encapsulating another user data packet. TCP/IP user data packets can be marked by reserving one of the possible values of the IP "User Protocol" field, which appears in an IP user data packet header. Again, when the User Protocol field is set to this reserved value, it is an indication that the IP header is encapsulating another user data packet.
The routing trees in the network may disagree even if a consistent tiebreaking algorithm is used. For example, the network topology (particularly the location or cost of links) may change, and while the changes are being propagated (via new LSPs) to all of the routers in the network, the routing trees of the various routers will be inconsistent. As a result, user data packets may temporarily follow loops in the network, and may accumulate extra encapsulation headers. Temporary packet looping is a well-known side effect of topological changes, and will occur regardless of whether the network uses dual protocols. However, the accumulation of extra encapsulation headers is an effect peculiar to dual-protocol networks, and can be avoided by the modification of the FIG. 6 algorithm described above.
The above embodiments, which support two protocols, may be enhanced to support three or more protocols. Because of their topological restrictions and resulting simplicity, it is most straightforward to add a third protocol (which will be referred to as "P3") to the per-area embodiments of FIGS. 1A and 2A. However, it is more complex to add a third protocol to the less restricted embodiment of FIG. 3.
To adapt the FIG. 1A embodiment for a third protocol, areas routing in the third protocol may simply be added to the network, and the Level-2 backbone reconfigured to support all three protocols (if routing in the third protocol is not allowed outside of the local areas, this latter step is not necessary). Note that, with three protocols, there are four possible types of multi-protocol routers: OSI-IP dual-protocol routers, OSI-P3 dual-protocol routers, IP-P3 dual-protocol routers, and OSI-IP-P3 triple-protocol routers. However, as in the two protocol embodiment illustrated in FIG. 1A, all routers in a given area must have the same capabilities--thus an area having an OSI-P3 dual-protocol router cannot also have an IP-P3 dual-protocol router, because their capabilities are not the same, even though both are dual-protocol.
Subject to the above, a third protocol may be easily added to the FIG. 1A architecture. Encapsulation is not required, for the same reasons as set forth in the discus