Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-04-22
2003-10-28
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395310
Reexamination Certificate
active
06639897
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communication carried out via a plurality of nodes comprising a network, and to the selection of the shortest route in a network. It relates in particular to a shortest route selection technique which finds an alternative route to one which cannot be used.
2. Description of Related Art
In order to communicate via a network, a route has to be selected between a source and a destination. Transfer of information through a network can involve circuit switching or packet switching. If circuit switching is employed, a destination address carried in a circuit setup signal is used during circuit setup to select a route. If packet switching is employed, a destination address carried in the header of a packet is used to select a route. Note however that if the packet switching involves setting up a virtual circuit rather than using datagrams, the route selection (routing) is carried out when such a circuit is set up.
In both circuit switching and packet switching, routing can be broadly divided into two types in accordance with when a route is selected. The first type involves hop-by-hop routing. In the other type, a source edge node of the network specifies a route all the way to the destination address. In hop-by-hop routing, a setup message for establishing the connection is sent to nodes, which successively select, as the next portion of the route, a hop on which there is surplus bandwidth, the bandwidth requirement being written in the setup message. The term “edge node” can denote either a source node or a destination node.
The second method is called source routing, and its implementation presupposes that a source edge node knows the topology of the network. Packet transfer based on source routing involves forwarding packets via the bridges or LANs indicated by routing information that follows the source address. A source edge node selects and sets up the shortest route to a destination on the basis of network topology information.
The Private Network-Network Interface (PNNI), the specification of which has been established by the ATM Forum, is a representative example of a source routing protocol. A header format which supports source routing is defined in IPv6, which is the standard for the next generation internet protocol (see document RFC1883). Source routing is also carried out by source edge nodes in the burst circuit-switched network disclosed in our prior U.S. application Ser. No. 09/205,612, filed Dec. 4, 1998, the contents of which are incorporated hereinto by reference.
To perform source routing, a source edge node has to know the topology of the network. In the present specification, the “topology of the network” means the configuration of the network. Network topologies include bus, ring, star and mesh configurations. Now suppose that a fault has occurred in a link. If a source edge node performs routing while information to this effect is still propagating towards that node, the routing will be based on out-of-date topology information and it may be impossible to transfer data to the desired destination. Or, if a link on a route is being used by other users, it may be necessary to wait until that link becomes available.
A way to ensure that data transfer can continue under such circumstances is for intermediate nodes on a route to calculate an alternative route. However, a problem has been encountered with this solution, and this will now be described with reference to
FIGS. 1
to
5
.
FIG. 1
illustrates a conventional alternative route selection scheme.
FIG. 2
gives an example of a network.
FIG. 3
shows an example of a network in which faults have occurred.
FIG. 4
gives another example of a network.
FIG. 5
shows another example of a network in which a fault has occurred. In
FIG. 1
, node B lies on the shortest route from node A to node C. Although only nodes A, B and C are shown, it is assumed that there are other nodes between these. In
FIG. 1
, the shortest route from node B to node C constitutes part of the shortest route from node A to node C. If the link from node B to node C cannot be used, node B could calculate the second shortest route between nodes B and C and select that route. However, as explained below, this method will sometimes result in the formation of a closed-loop route and in a packet being unable to reach the desired destination address.
FIG. 2
shows a network comprising nodes A to L and links
1
to
16
. Assuming that the length of each link is the same and that a route is to be selected from node A to node E, the shortest route will be A-B-C-D-E. Node A, which is the source edge node, selects this shortest route and begins the data transfer. Now suppose that due to congestion or fault, link
3
joining nodes B and C cannot be used. This situation is illustrated in FIG.
3
. Because link
3
, which is part of the shortest route to node E, cannot be used, node B reselects B-F-G-D-E, which is the second shortest route from node B to node E.
Next, when the route selection has reached node F, if link
8
joining node F and node G cannot be used, node F reselects F-H-B-C-D-E, which is the second shortest route from node F to node E. However, because link
3
joining node B and node C cannot be used, when the route selection has arrived back at node B, the route to node F is selected once again, with the result that a closed-loop route is formed.
FIG. 4
shows a network which is the same as the network of
FIG. 2
except that node G and links
8
and
9
have been removed. In this example, let us assume that when node B learns that link
3
cannot be used, it selects the route to node F, as shown in FIG.
5
. However, if node F does not know that link
3
cannot be used, it will select F-H-B as the second shortest route, and so again a closed-loop route forms. Closed-loop routes form in this manner because nodes capable of routing do not know the state of links other than those to which they are directly connected.
SUMMARY OF THE INVENTION
Given this background, it is an object of the present invention to provide a routing system which, when a link on a route to a destination becomes unusable due to congestion, fault or the like, is still capable of selecting a route to the desired destination. It is a further object of the present invention to provide a routing system capable of increasing network throughput. It is yet another object of the present invention to provide a routing system capable of selecting a route to a target destination even during the signal propagation delay from when a link has become congested or faulty, to the time when information to this effect has been transmitted between all the nodes.
In the present invention, nodes notify each other of the link availability situation, so that if a link becomes unavailable due to congestion or fault, this fact is reflected in network topology information held by each node. When a source edge node is preparing routing information, it uses its network topology information to construct a virtual network in which the unavailable link has been removed, and on this basis selects the shortest route.
However, during the time when the information that a link has become unavailable is being transmitted to the source edge node, there is temporarily a situation in which an unsuccessful route might be selected. To be prepared for this eventuality, the intermediate nodes on the current route likewise construct a virtual network and are able to reselect a shortest route to the desired destination. If a node discovers that a link on this route is unavailable, it uses its network topology information to construct a virtual network in which the unavailable link has been removed. It also removes, from this virtual network, all the nodes lying between the source and the unavailable link, together with any links directly connected to those nodes. In the virtual network thus formed, the shortest route to the destination is selected from the node immediately before the link which has become unavailable. In
Shiomoto Kohei
Yamanaka Naoaki
Chin Wellington
Nippon Telegraph and Telephone Corporation
Pillsbury & Winthrop LLP
Schultz William
LandOfFree
Communication network of linked nodes for selecting the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication network of linked nodes for selecting the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication network of linked nodes for selecting the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124801