Optical: systems and elements – Deflection using a moving element – Using a periodically moving element
Reexamination Certificate
1999-01-21
2002-04-30
Negash, Kinfe-Michael (Department: 2633)
Optical: systems and elements
Deflection using a moving element
Using a periodically moving element
C359S199200, C370S403000
Reexamination Certificate
active
06381046
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the routing of traffic on communication networks of the kind known as ring networks. More particularly, the invention relates to ring networks that support multiple channels, such as multiple wavelength channels, and to routing methods that seek efficient use of a fixed number of such channels.
BACKGROUND OF THE INVENTION
FIG. 1
depicts, in schematic fashion, a typical ring network including nodes
10
.
1
-
10
.
6
, clockwise links
15
.
1
-
15
.
6
, and counterclockwise links
20
.
1
-
20
.
6
. (The physical medium, such as an optical fiber, that embodies a link may carry signals bidirectionally. However, for convenience in the following discussion, it is helpful to represent even bidirectional links as pairs of directed links. A network that can be described in this manner is referred to as a “directed ring network.”) A route or connection is a contiguous sequence of links leading from an initial node to a terminal node. For example, route
25
of
FIG. 1
is a clockwise route from node
10
.
2
to node
10
.
4
.
Ring networks have the well-known advantage that when an accident or malfunction causes a link to be cut, thus interrupting traffic, the interrupted traffic can often be carried over alternative routes having the opposite circulatory direction. (I.e., clockwise-routed traffic is re-routed counterclockwise, or vice versa.) As a consequence, practitioners in the field of communication network architecture have regarded ring networks as attractive for many applications.
For any given routing and any given directed link of a ring network, we use the term link load to refer to the number of connections routed through the given link. We use the term ring load to refer to the maximum link load (in either circulatory direction) over the entire network.
It is typical for the links of a ring network to have some maximum capacity; that is, an upper limit on the number of routed demands that can pass through a given link in a given direction. In order to make efficient use of such a ring network, it is advantageous to route the demands in such a way that the ring load is kept as low as possible. Otherwise, there is a danger that some link will too soon reach its maximum capacity, so that no further routing can be made through that link.
Thus, there is a need for a procedure that optimally routes a given set of demands; that is, a procedure that achieves a routing having the minimum possible ring load. Moreover, it is desirable for such a routing to be achievable within a computational time period short enough for practical use in handling real-time traffic. As a general rule, this means that the computational time should be less than an exponential function of the network size.
By way of example, if an optimal routing were computed by exhaustive search and the number of nodes in the network were on the order of fifty or more, the time required for the computation would be prohibitive in applications directed to handling real-time traffic.
Until now, there has been no known procedure for solving the optimal routing problem on a ring network within less than exponential time.
In some types of ring networks, a fixed number of multiple channels are available for carrying signals on each link. These channels may be embodied in various ways, including respective optical fibers, respective electrical conductors, or respective wavelengths of light. For purposes of illustration, we will now discuss optical WDM ring networks, in which each link comprises multiple wavelength channels. However, it should be noted that the principles to be discussed apply generally to other multiple-channel ring networks.
To establish a logical connection between nodes in such a network, an administrative entity first chooses a route, and then it assigns a wavelength to the connection for each link in the route. The network is referred to as wavelength selective (WS) if all of these assigned wavelengths are the same (for the given connection), and wavelength interchanging (WI) if different links (for the given connection) may be assigned different wavelengths. In a WI network, a device which we refer to as a wavelength translator would typically be available at the various nodes to intercept incoming signals on one set of respective wavelengths and re-transmit them, as outgoing signals, on a different set of respective wavelengths.
WS networks will generally be less expensive than WI networks of the same size, because they do not require wavelength translators. However, if the number of available wavelengths is fixed, the WI network will generally have more capacity, because it can reuse the same wavelength on two or more overlapping routes (although of course not on overlapping links). As a consequence, adding a new connection does not necessarily result in utilizing a new wavelength, even if the new route overlaps all of the previously established routes.
Thus, in practice, there will be a tradeoff between the cost advantages of the WS network and the capacity advantages of the WI network.
In WDM ring networks of both kinds, it is advantageous to carry out the task of wavelength assignment (in a general context, this may be thought of as “channel” assignment) using as few wavelengths (or “channels”) as possible. If the total number of available wavelength channels is limited, this assures that the capacity of the network is being used efficiently. If the least possible number of wavelengths is used, we say that the wavelength assignment is optimal.
In WI networks, given a particular route set, optimal wavelength assignment is readily carried out in less than exponential time, provided enough nodes are equipped with wavelength translators. A practical method for optimal routing is advantageous in this context because it can be used to minimize (over all possible route sets) the number of wavelengths needed.
In WS networks, the problem of optimal wavelength assignment (for a given route set) is an NP-complete problem. In other words, there is no known way to carry out such an assignment in less than exponential time, and it is extremely unlikely that any procedure for doing so will ever be found.
Under these circumstances, it is highly advantageous to have a wavelength-assignment procedure that can perform, with some performance guarantee, within a practical period of time, such as polynomial time. In general, as the estimated cost (according to the performance guarantee) goes down, the procedure becomes more useful, because it will appear cost-effective to apply it to a wider range of practical problems. A practical method for optimal routing is advantageous in this context because if a wavelength-assignment procedure has a performace guarantee (for a given route set), optimal routing can be used to minimize the estimated cost over all possible route sets. By making the estimated cost as small as possible, the utility of the wavelength-assignment procedure is enhanced.
SUMMARY OF THE INVENTION
We have invented a routing procedure, for directed ring networks, that achieves optimal routing in polynomial time.
When our routing procedure is combined with an appropriate procedure for optimally assigning wavelength channels in WI networks, wavelengths can be assigned in a manner that is optimal over all possible route sets.
When our routing procedure is combined with an appropriate procedure for assigning wavelength channels in WS networks, wavelengths can be assigned, in polynomial time, with a performance guarantee. This guarantee is that the total number of wavelengths used will be no more than twice the ring load obtained by optimal routing, less one.
In one aspect, the invention involves a method for routing a set of demands in a ring network that comprises nodes interconnected by directed links, in which each demand may be routed clockwise or counterclockwise.
According to our method, a linear program is solved to obtain a set of routing variables that minimize an objective function. Each routing variable corresponds to a respective one of the demands, and
Wilfong Gordon Thomas
Winkler Peter M.
Finston Martin I.
Lucent Technologies - Inc.
Negash Kinfe-Michael
LandOfFree
Routing method for ring networks, such as WDM ring networks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing method for ring networks, such as WDM ring networks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing method for ring networks, such as WDM ring networks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847229