 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention relates to routing data in a large communications
network that has at least two smaller networks, called stubs, connected
together by an intervening public data network. In particular, the present
invention relates to a robust and efficient dynamic method for determining
optimal or "shortcut" communication paths across the public data network
between nodes in different stubs.
BACKGROUND OF THE INVENTION
FIG. 1 depicts a communications network 10 called an internet. The internet
10 includes a number of stubs 20, 30, 40, and 50. Each stub 20, 30, 40,
and 50 is a smaller, subsumed communications network. The stub 20
comprises the nodes 21,22,23, the stub 30 comprises the nodes 31,32,33,34,
the stub 40 comprises the nodes 41,42, and the stub 50 comprises the nodes
51,52. The nodes 21-23, 31-34, 41-42, and 51-52 within each stub 20, 30,
40, and 50 are interconnected by a respective subnetwork 25, 35, 45, or 55
of the stub. For example, the nodes 21-23 are interconnected by the
subnetwork 25 of the stub 20. As used herein, the term "subnetwork" refers
to the communications lines, switches, etc. necessary for establishing
internodal communication amongst the nodes interconnected by that
particular subnetwork. For example, the subnetwork 25 can establish
communications between any of the nodes 21-23 within the stub 20.
FIG. 2 depicts a node, e.g., the node 32 of the internet 10, in greater
detail. As depicted, each node comprises a CPU or processor 71, a memory
72, and one or more input/output ports 73-1, 73-2, . . . , 73-n which are
interconnected to one another via a bus 74. The input/output ports 73-1,
73-2, . . . , 73-n may be connected to the input/output ports of another
node (e.g., the node 31) via a subnetwork (e.g., the subnetwork 35). The
processor 71, among other things, controls the transmission of data
between the memory 72 and the input/output ports 73-1, 73-2, . . . , 73-n.
The processor 71 also controls the transmission of data from the
input/output ports 73-1, 73-2, . . . , 73-n to other nodes. For example,
the processor 71 can cause data stored in the memory 72, to be transmitted
via the bus 74 to a particular input/output port, e.g., the input/output
port 73-2. The processor 71 can then cause the input/output port 73-2 to
transmit the data via the subnetwork 35 to a second node, e.g., the node
31. The data may be received in an input/output port at the node 31 and
then transferred via the bus at that node 31 into the memory thereat under
the control of the processor of the node 31.
It is also possible to transmit data from the node 31 to the node 32 by
transmitting the data from the node 31 to the node 33, and then from the
node 33 to the node 32. The transmission between each pair of nodes, e.g.,
from the node 31 to the node 33, is achieved in the above described
manner.
The node at which data is initially generated and transmitted (e.g., the
node 32) is called the source node. The node to which the data is
ultimately destined (e.g., the node 31) is called the destination node.
All other nodes between the source and destination node through which the
data may pass (e.g., the node 33) are referred to as intermediary nodes.
Illustratively, data transmitted between nodes via a subnetwork within a
particular stub is organized into packets. Such a packet 80 is depicted in
FIG. 3. The packet contains one or more headers 81, 82 and data 83. One
header 81 of the packet 80 is associated with the subnetwork over which
the packet is to be transmitted and is called the subnetwork header. This
subnetwork header contains control information including information
necessary to direct the packet to its destination within that particular
stub. Each node connected to the subnetwork is assigned a subnetwork
address or identifier which is recognized by every other node connected to
the subnetwork. The subnetwork header typically contains the subnetwork
address of the source node, called the source address, and the subnetwork
address of the destination node, called the destination address.
When a source node transmits a packet to a destination node in the same
stub, the source node places its subnetwork address in the subnetwork
source address field 81-1 (FIG. 3). Furthermore, the source node places
the subnetwork address of the destination node in the subnetwork
destination address field 81-2 of the packet 80. Thus, the source node
must know or determine the subnetwork address of the destination node. In
the case that the stub containing the source and destination nodes is an
Ethernet network, the source node may already store the subnetwork address
of the destination node in the memory of the source node. If the source
node does not already store the destination address, the source node can
transmit a query message to all nodes of the stub. The query message
identifies the destination node and requests that the destination node
transmit its subnetwork address to the source node. Upon receiving the
query message, the destination node transmits its subnetwork address to
the source node. All other nodes in the stub ignore the query message.
Using the subnetwork address of the destination node, the source node then
transmits its packet to the destination node.
When a packet is received at a node, the processor at the node
illustratively determines if the node has the same subnetwork address as
the destination address of the packet. If so, the processor at the node
determines that the packet has reached its destination within that
particular stub. If the destination address is different from the node's
subnetwork address, the processor determines that the packet is not at its
destination within that stub. The processor then determines the
appropriate manner for transmitting the packet so that the packet reaches
its destination node.
Often it is desirable to transmit packets from a source node in one stub to
a destination node in another stub in the internet 10 of FIG. 1. To that
end, each stub 20, 30, 40 and 50 has one or more access point nodes 21,
31, 34, 41, and 51, respectively, which are interconnected by a separate
transit or backbone subnetwork called a public data network or PDN 60. A
transit or backbone subnetwork is a subnetwork which may be used for
transmitting packets between stubs. Thus, it is possible to transmit a
packet from the node 23 in the stub 20 to the node 33 in the stub 30 by
first transmitting the packet from the node 23 to the node 21 via the
subnetwork 25. The packet is then transmitted from the node 21 to the node
31, via a backbone subnetwork in the form of the PDN 60, and from the node
31 to the node 33 via the subnetwork 35 in the stub 30. An access point
node which receives a packet from a stub and retransmits the packet via
the PDN 60, e.g., the node 21, is referred to as an entry point node of
the PDN 60. An access point node which receives a packet from the PDN 60
and retransmits the packet via the subnetwork of a stub, e.g., the node
31, is referred to as an exit point node of the PDN 60.
In the internet 10, it is assumed that packets may not be transmitted from
an access point node in a first stub to an access point node in a second
stub via the subnetwork of a third stub. In other words, if a packet is
received at an access point node of a third stub from the PDN 60 it may
only be retransmitted therefrom via the subnetwork of the third stub to a
destination node in that stub. If such a received packet is destined to a
node in another stub, it may only be retransmitted from the access point
node of the third stub via the PDN 60.
The PDN 60 may be a connection-less or a connection oriented subnetwork. An
example of a connection oriented PDN 60 would be a telephone network.
Like the subnetworks 25, 35, 45 and 55, the PDN 60 provides a PDN
subnetwork address for each access point node 21, 31, 34, 41, and 51.
Typically, the subnetworks 25, 35, 45, 55 and the PDN subnetwork 60
utilize different addressing schemes. Thus, each node 21-23, 31-34, 41-42,
and 51-52 of the internet 10 is further assigned an internet address.
Furthermore, packets may be transmitted with internet headers containing
the internet addresses of the source and destination nodes. Such an
internet packet 90 is depicted in FIG. 4 with a subnetwork header 91, an
internet header 92 and data 93. The internet header 92 contains the
internet address of the source and destination nodes in an internet source
address field 92-1, and internet destination address field 92-2,
respectively.
Subnetwork addresses are recognizable only by the nodes connected to that
particular subnetwork. Internet addresses have significance over the
entire internet 10. The internet address of a packet's destination node
may be used to determine whether the packet must be transmitted via the
PDN 60 in order to reach the destination node. The internet address of a
packet's destination node may also be used at a first access point node to
direct a received packet to a second access point node via the PDN 60.
That is, suppose a first entry point node receives a packet via a first
stub but must transmit the packet to a second exit point node in a second
stub via the PDN 60. The first access point node may use the internet
destination address of the packet to determine the PDN subnetwork address
of the second access point node. For example, suppose the node 21
receives, via the subnetwork 25, a packet from the node 23 having the
internet destination address for the node 42. When the node 21 receives
the packet, the node 21 uses the internet destination address in the
internet destination address field 92-2 (FIG. 4) of the packet to
determine over which subnetwork to retransmit the packet. In this case,
the node 21 determines that the packet must be retransmitted via the PDN
60 to reach the node 41, which is the next node on the path to the node
42. If the node 21 determines that the packet must be retransmitted via
the PDN 60, then the node 21 uses the internet destination address of the
packet to determine the PDN subnetwork address of the next node on the
path to the node 42. In this case, the node 21 determines the PDN
subnetwork address of the node 41.
In order for an entry point node, such as the node 21, to make these two
determinations, each access point node illustratively stores an internet
routing table, such as the internet routing table 85 shown in FIG. 5. FIG.
5 shows an illustrative internet routing table at the node 21, having an
entry 85-1, 85-2, 85-3, 85-4, 85-5, 85-6, 85-7, 85-8, 85-9, 85-10, and
85-11 for each node of the internet 10. In the alternative, where there
are many nodes on the internet 10, each node stores entries for only some
of the nodes or provides individual entries for different subsets of
nodes, or both. In FIG. 5, each entry has a first field which stores the
internet destination address of a different node. The subscript I is used
to designate internet addresses, i e., "31.sub.I " means the internet
address of the node 31. Each entry has a second field which stores the PDN
subnetwork address of the next node on the path to the destination node
having the corresponding internet destination address. In FIG. 5, the
subscript PDN is used to designate PDN subnetwork addresses, i e.,
"31.sub.PDN " means the PDN subnetwork address of the node 31.
Furthermore, each entry has a third field which stores an indicator of the
subnetwork over which a packet must be retransmitted. The entries 85-9,
85-10, and 85-11 correspond to nodes 21-23 which are connected to the node
21 via the subnetwork 25, not the PDN 60 as indicated by the third field
of these entries. The second field of each of these entries is not used
for routing the packets (rather, the packets are routed within the stub 20
as discussed above) as indicated by "don't care" in FIG. 5.
Continuing with the above example wherein a packet is transmitted from node
23, to node 21, to node 41, to node 42, the processor at the node 21
searches the table 85 for the entry corresponding to the internet
destination address contained in the packet, i.e., the entry 85-6 which
stores the internet address of the node 42. The processor of the node 21
examines the third field of this entry 85-6 and determines that the packet
must be retransmitted via the PDN 60. The processor at the node 21 then
uses the PDN subnetwork address stored in the next node field of the
retrieved entry 85-6 to retransmit the packet to the next node on the path
to the node 42, i.e., the node 41, via the PDN 60.
In the alternative, the entry point node 21 may not know the PDN subnetwork
address of the exit point node 41. In other words, the node 21 does not
know the direct optimal path between the entry point node 21 and the exit
point node 41. Instead, the entry point node 21 must transmit the packet
to the exit point node 41 via a sequence of at least one intermediary
access point node. For instance, instead of the PDN subnetwork address of
the exit point node 41, the entry 85-6 may store the PDN subnetwork
address of the access point node 31 in its next node field. The entry
point node 21 would thus transmit the packet to a first intermediary
access point node, i.e., to the access point node 31. The access point
node 31 then illustratively consults its internet routing table to
determine if it knows the PDN subnetwork address of the exit point node
41. If so, the packet is transmitted directly to the exit point node 41.
If not, the intermediary access point node 31 may transmit the packet to
yet another intermediary access point node in a similar fashion as
described above. Thus, the packet is transmitted from intermediary access
point node to intermediary access point node in the PDN 60 until it
arrives at an intermediary access point node which knows the PDN
subnetwork address of the exit point node 41.
The overhead in determining, at the entry point node, the PDN subnetwork
address of the exit point node of a packet (i.e., the optimal path across
the PDN 60) depends on the size of the internet. In the case of small,
broadcast local area networks (LANs), the determination of the LAN
subnetwork address of any desired destination node is a simple task. See,
D. Plummer, "An Ethernet Address Solution Protocol--or--Converting Network
Protocol Addresses to 48 bit Ethernet Addresses for Transmission on
Ethernet Hardware," RFC 826 USC Information Sciences Institute, November,
1982. This is because broadcast LANs interconnect a small number
(hundreds) of nodes and posses a simple, low overhead mechanism for
"searching" for the LAN subnetwork addresses of other nodes. However, on a
very large, general topology PDN subnetwork, the task of determining
subnetwork destination addresses is more difficult. The Public Data
Network (PDN) may be connected to tens of thousands of nodes rendering the
task of distributing up-to-date PDN subnetwork addresses about each node
to each other node highly inefficient. Thus, in a large PDN, the nodes can
only maintain the PDN subnetwork address of a subset of nodes. This means
that an entry point node often does not know the PDN subnetwork address of
the exit point node and thus cannot transmit a packet directly thereto via
the optimal path. Instead, the packet must be transmitted from the entry
point node to the exit point node via a sequence of intermediary access
point nodes of the PDN as described above. Moreover, although any access
point node should be capable of communicating with any other access point
node via the PDN, most access point nodes are unlikely to communicate with
the majority of the other access point nodes. It is thus unnecessary for
each access point node to maintain information about every other access
point node.
Several solutions for the above problem been proposed, i.e., for
determining, at an entry point node, the PDN subnetwork address of the
exit point node. See, International Standards Organization, "End System to
Intermediate System Routing Information Exchange Protocol for Use in
Conjunction with ISO 8878," ISO 10030. A first solution has been proposed
for an internet having stubs which are each connected with a PDN by only
one access point node. The internet address assigned to each node contains
the PDN subnetwork address of the corresponding access point node. Thus,
it is a simple matter to determine, at an entry point node, the PDN
subnetwork address of the exit point node which connects the stub
containing the destination node. The entry point node simply examines the
internet address of the destination node of the packet and extracts the
PDN subnetwork address of the exit point node therefrom.
In a second solution, a small number of nodes are designated as "route
server nodes". All non-route server nodes of the internet advertise the
subnetworks and stubs they can reach to the route server nodes to which
they are connected. The route server nodes, in turn, exchange this
received information with other route server nodes.
The second solution works as follows. Suppose a non-route server node X is
an access point node to the PDN for a source node S which desires to
transmit a packet to a destination node D in another stub. In such a case,
the source node S transmits a packet to the access point node X via a
subnetwork. The node X transmits the packet to the route server node with
which it is connected. The route server node determines the PDN subnetwork
address of the exit point node Y that connects the stub containing the
destination node D with the PDN, for example, by consulting its internet
routing table (FIG. 5). The route server node then transmits the packet to
this node Y (which in turn transmits the packet to the node D). In
addition, the route server node transmits a redirect packet back to the
node X which contains the PDN subnetwork address of the node Y. The node X
stores the subnetwork address of the node Y for later use in transmitting
other packets to the node D. Thus, the node X can now transmit a packet
directly to the node Y (i.e., via the optimal path).
Each of these solutions has drawbacks. In the first solution, the internet
addresses must be very large. Thus, the solution is not applicable to many
widely deployed subnetworks, such as those employing the DECNET, Appletalk
or Novell IPX protocols which restrict the size of addresses. Furthermore,
it is not possible to embed the PDN subnetwork address of the exit point
node in the internet destination address if the PDN has stubs that have
more than one access point node each to the PDN. This is significant
because it is prudent to connect two nodes of even small stubs with the
PDN for purposes of reliability,
The second solution places a heavy load on the route server nodes in terms
of handling routing updates, storing routes, forwarding packets and
redirecting router nodes. Thus, each route server node is a potential
bottleneck.
It is therefore an object of the present invention to provide for routing
data in a PDN subnetwork of an internet which overcomes the disadvantages
of the prior art.
SUMMARY OF THE INVENTION
This and other objects are achieved by the present invention. In one
embodiment, the PDN has a sparse communications map which includes at
least one path, called a base path, for transmitting packets between any
two access point nodes connected via the PDN. Typically, the base path is
not an optimal or direct path between the access point nodes but instead
includes one or more intermediary access point nodes. According to this
embodiment, a method is provided for transmitting a packet from a source
node in a first stub to a destination node in a second stub. The first
stub is connected with the PDN by a first access point node and the second
stub is connected with the PDN by a second access point node. The method
includes the following steps:
(1) routing the packet from the source node to the first access point node
using the subnetwork of the first stub,
(2) at the first access point node, writing the PDN subnetwork address of
the first access point node in a shortcut header of the packet,
(3) transmitting the packet via a base path, which typically includes a
sequence of one or more intermediary access point nodes, until the second
access point node is reached,
(4) at the second access point node, receiving the packet via the base path
and storing the PDN subnetwork address of the first access point node
(contained in the packet) in a shortcut table at the second access point
node, and
(5) routing the packet from the second access point node to the destination
node using the subnetwork of the second stub.
More specifically, the source node in a first stub routes a packet to the
first access point node of the PDN. When the first access point node
receives a packet from the source node, the first access point node writes
its PDN subnetwork address in the packet, e.g., in a shortcut header of
the packet. The first access point node then routes the packet via a base
path to the second access point node, which base path typically includes
the first access point node, a sequence of one or more intermediary access
point nodes, and the second access point node. To that end, the first
access point node illustratively uses an internet address of the
destination node (contained in the packet) to retrieve an entry from an
internet routing table maintained at the first access point node, which
entry corresponds to the destination node. The first access point node
uses the PDN subnetwork address in the next node field of the retrieved
internet routing table entry to transmit the packet to the next access
point node on the base path.
The next access point node receives the packet and determines if it
connects the second stub (which contains the destination node) with the
PDN. For example, the access point node can retrieve the entry of its
internet routing table corresponding to the packet's internet destination
address. If the entry stores an indication that the packet must be
retransmitted via the subnetwork of a stub, rather than via the PDN
subnetwork, then the access point node must connect the second stub with
the PDN. In such a case, the access point node is the exit point node
(i.e., the second access point node). Otherwise, the access point node is
merely an intermediary access point node, which intermediary access point
node transmits the packet to the next access point node on the base path
to the second access point node. To that end, the intermediary access
point node accesses its internet routing table to retrieve the entry
corresponding to the packet's internet destination address (if it has not
done so already to determine if it is the exit point node). Like the first
access point node, the intermediary access point node uses the PDN
subnetwork address in the next node field of the retrieved entry to
transmit the packet to the next access point node on the base path to the
second access point node. This process is repeated at each successive
intermediary access point node on the base path to the second access point
node until the packet is received at the second access point node.
Eventually, the packet arrives at the second access point node. The second
access point node first determines that it is the exit point node, i.e.,
connected with the stub containing the destination node. The second access
point node then retrieves the PDN subnetwork address of the first access
point node contained in the packet and stores this address as a shortcut
address in a shortcut table maintained at the second access point node.
The shortcut address is stored in a shortcut table entry corresponding to
the internet address of the packet's source node. The second access point
node thereafter routes the packet to the destination node via the
subnetwork of the second stub.
The above method for transmitting a packet from the first access point node
to the second access point node causes the second access point node to
learn a return, direct or optimal shortcut path back to the first access
point node. Thereafter, if the second access point node has a packet to
transmit to the first access point node, the second access point node can
transmit the packet directly to the first access point node via the
optimal shortcut path stored in the shortcut table rather than via the
base path. For example, the second access point node can transmit a packet
back to the first access point node by:
(1) at the second access point node, retrieving the entry from the shortcut
table, and
(2) transmitting the packet to the first access point node using the PDN
subnetwork address of the first access point node stored in the retrieved
entry.
It is also possible for the second access point node to write its PDN
subnetwork address in a packet transmitted from the second access point
node to the first access point node. In this fashion, when the packet
arrives at the first access point node, the first access point node learns
the optimal shortcut path to the second access point node. The PDN
subnetwork address contained in the packet is then stored in a shortcut
table maintained at the first access point node in an entry corresponding
to the internet address of the source of the packet. Thereafter, the first
access point node can retrieve the shortcut path from its shortcut table
for transmitting a packet to the second access point node using the second
access point node's PDN subnetwork address stored in the retrieved entry.
In short, a simple, dynamic method is provided for automatically
discovering shortcut paths across a PDN between two access point nodes.
Shortcut paths are only stored at access point nodes that have previously
communicated with each other thereby reducing the storage requirements at
each access point node. In addition, the invention is not dependent on the
particular addressing scheme used in any subnetwork and operates
transparently of each subnetwork protocol. The invention is thus easy to
implement in an existing internet.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 depicts a prior art internet communications network.
FIG. 2 depicts a prior art node of the internet network of FIG. 1 in
greater detail.
FIG. 3 depicts a prior art packet with a subnetwork header.
FIG. 4 depicts a prior art packet with an internet header.
FIG. 5 depicts a prior art internet routing table.
FIG. 6 depicts an internet network with a sparse communications map.
FIG. 7 depicts an internet network with asymmetric base paths.
FIG. 8 depicts an internet routing table of the node Ra in the internet
depicted in FIG. 6.
FIG. 9 depicts a packet with a shortcut header.
FIG. 9A depicts a second packet with a shortcut header.
FIG. 10 depicts an internet routing table of the node Rb in the internet
depicted in FIG. 6.
FIG. 11 depicts a shortcut routing table of the node Rd depicted in FIG. 6.
FIG. 12 depicts a modified shortcut routing table of the node Rd according
to another embodiment of the present invention.
DETAILED DESCRIPTION OF THE INVENTION
FIG. 6 shows an internet 200 which uses shortcut routing in accordance with
the invention. The internet 200 comprises the stubs
300,301,302,303,304,305,306, and 307. Each stub contains one or more
nodes, e.g., the stub 300 contains the nodes Ra, S and S1, and a
subnetwork, e.g., the subnetwork 340, connecting the nodes Ra, S and S1
within that stub 300. The internet 200 also comprises the PDN subnetwork
210 for interconnecting the stubs 300-307. Illustratively, the PDN 210
includes the connections P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12, and P13.
According to one embodiment of the invention, it is presumed that each stub
(e.g., the stub 300) is connected by at least one access point node (e.g.,
Ra) with the PDN. To reduce the amount of routing information maintained
at the nodes that connect each stub with the PDN 210, it is advantageous
to hierarchically cluster or group the stubs. For example, as shown in
FIG. 6, The stubs 300, 301, 302, 303, 304, 305, 306 and 307 are grouped
into four clusters 310, 320, 330, and 360. The node Ra is designated the
access point node for the cluster 310, the node Rb is designated the
access point node for the cluster 320, the node Rc is designated the
access point for the cluster 360 and the node Rd is designated the access
point node for the cluster 330. Therefore, the nodes A1 (in the stub 301),
A2 (in the stub 303), A3 (in the stub 304), and A4 (in the stub 307) do
not serve as access point nodes to the PDN 210. As such, the connections
P7-P13 are not used and may be ignored.
After the access point nodes Ra,Rb,Rc, and Rd are chosen, each cluster is
illustratively assigned an internet address prefix and each node of each
stub is assigned an internet address which includes the prefix of its
corresponding cluster. For example, | | |
