Optical: systems and elements – Deflection using a moving element – Using a periodically moving element
Reexamination Certificate
1998-10-29
2003-03-25
Pascal, Leslie (Department: 2633)
Optical: systems and elements
Deflection using a moving element
Using a periodically moving element
C359S199200, C359S199200, C370S370000
Reexamination Certificate
active
06538777
ABSTRACT:
BACKGROUND OF THE INVENTION
Optical fiber networks comprise a plurality of nodes connected together by bundles of optical fibers. Until recently, optical fiber communication technology could support only one wavelength per fiber, so making a connection through a network was a matter of selecting a series of links and particular fibers in the series of links.
Recent improvements in technology have made it possible to transmit multiple carriers of different wavelengths through a single fiber. Current technology should soon provide up to about 80 wavelengths on a single fiber, enabling a single fiber to carry 80 times as much traffic as a single-wavelength fiber. It is predicted that capacity may go as high as 128 to 160 wavelengths.
Thus routing takes on an extra dimension. Not only must a link and a fiber within that link be chosen, but an available wavelength must also be selected. Wavelength changers, which take a signal at one wavelength and convert it to another wavelength, are available, albeit they are complex and expensive.
Various routing algorithms for multiple-wavelength fiber networks have been developed in attempts to make the network operate efficiently. These algorithms are based on the current state of the network. For example, a “First to Fit” algorithm may choose the path with the lowest available wavelength, or if the path is already determined, pick the lowest available wavelength on that path. A “Most Used” algorithm selects a wavelength that is already used on the most fibers. A random algorithm selects a wavelength randomly in a uniform manner. The “Least Loaded Routing” algorithm selects a wavelength-path, that is, a wavelength and series of links, with the least congested link.
SUMMARY OF THE INVENTION
A typical problem which may result from prior algorithms is that the utilization of the particular wavelength-path chosen by the algorithm may remove from availability the only remaining link capable of providing a connection between some other pair of nodes, thereby unnecessarily reducing the availability of the network. To maximize the ability of the network to provide as many connections as possible, the present invention assigns channels such as wavelengths, and paths based, at least in part, on the state of the network after possible assignments. Where current methods look only at the current state of the candidate paths, the present invention tries to leave the network overall in a “better” or more flexible state.
In accordance with the present invention, candidate channel-paths are allocated to connections in a network, where a candidate channel-path comprises a candidate path and candidate channel along the candidate path, by determining individual effects on the network of selecting candidate channel-paths. These include effects on at least one channel-path, other than a candidate channel-path, which shares a link with the candidate path. Candidate channel-paths are selected based on the determined effects and allocated.
In a preferred embodiment, determination of the effects on the network is based on path capacity. The embodiment can be used where a single connection has been requested, or alternatively, where multiple connections have been requested.
A max-sum embodiment selects candidate channel-paths by first calculating a sum of path capacity-dependent values of a set of paths in the network for each of plural network states resulting from candidate channel-path allocations, and then selecting the candidate channel-paths yielding a maximum sum.
In a preferred embodiment, each path capacity dependent value is a path capacity multiplied by a weight associated with the path. In one alternative, the weight associated with a path p is the inverse of the path capacity of path p prior to allocating channel-paths. In another alternative, the weight for a path p is an inverse of the path capacity of network path p in its empty state with no connections. In yet another alternative, each path capacity dependent value is the path capacity associated with the path, i.e. all weights are 1. In still another embodiment, the weight for a path p is based on a prediction of the future traffic load of path p, for example, an average of past traffic load, or usage, of path
In a preferred embodiment, selecting the candidate channel-paths is based on a difference, for each of plural network states resulting from channel-path allocations, of path-capacities before and after the allocation. Determining the difference comprises determining a count, for each candidate channel-path, of paths in the network whose capacities are decreased by one.
Where the network is a ring network, determining the count for a candidate channel-path further comprises, for each value i between 1 and the number of links n in the candidate channel-path: determining a minimum capacity k
i
for a first i links of the candidate channel-path; determining a minimum capacity g
i
for a last i links of the candidate channel-path; determining a first gap value h
i
(l)
equal to a number of links from the first link in candidate channel-path in a first direction to a link with link capacity less than k
i
; and determining a second gap value h
i
(r)
equal to a number of links from a last link i in a second direction to the first link with link capacity less than g
i
. Then h
i
(l)
, h
i
(r)
, the number of links in the candidate channel-path, and the total number of links in the network, are used to calculate the count.
Alternatively, determining the count for a candidate channel-path further comprises, for each candidate channel-path: determining a set of paths such that all paths in the set have a minimum capacity link in common with the candidate path at the candidate channel, and using the size of the set of paths as the count.
A max-min embodiment determines and selects the candidate channel-paths by first determining a minimum path capacity of a set of paths in the network for each possible configuration of candidate channel-path allocations, and then selecting the candidate channel-paths yielding a largest minimum.
The present invention is designed for optical fiber networks, preferably with a plurality of fibers within each link, however it is applicable to other types of networks as well. In the preferred embodiments, channels correspond to wavelengths. However, the present invention is not limited to wavelength channels in optical fiber networks. For example, in alternative embodiments, the network could use time division multiple access (TDMA) where channels correspond to time slots.
The present invention also provides benefits to networks having channel changers, in which case channel-paths can be assigned to hops between channel changers or between channel changers and source or destination nodes.
In a preferred embodiment, multiple channels are available in a single path.
In yet another embodiment, paths are preselected and only candidate channels must be allocated.
REFERENCES:
patent: 5566014 (1996-10-01), Glance
patent: 5612805 (1997-03-01), Fevrier et al.
patent: 5751454 (1998-05-01), MacDonald et al.
patent: 5781537 (1998-07-01), Ramaswani et al.
patent: 5959749 (1999-09-01), Danagher et al.
patent: 5999290 (1999-12-01), Li
patent: 6073248 (2000-06-01), Doshi et al.
patent: 6084858 (2000-07-01), Matthews et al.
patent: 6108304 (2000-08-01), Abe et al.
patent: 6108311 (2000-08-01), Ramaswani et al.
patent: 6215763 (2001-04-01), Doshi et al.
Subramaniam, S. and Barry, R., “Wavelength Assignment in Fixed Routing WDM Networks,” inProc. IEEE ICC,Montreal, P.Q., Canada, pp. 406-415, (Nov. 1997).
Jeong, G. and Ayanoglu, E., “Comparison of Wavelength-Interchanging and Wavelength-Selective Cross-Connects in Multiwavelength All-Optical Networks,” inProc. IEEE INFOCOM'96, San Francisco, CA, pp. 156-163 (Mar. 1996).
Mokhtar, A. and Azizoglu, M., “Adaptive Wavelength Routing in All-Optical Networks,” submitted toIEEE/ACMTransactions on Networking.
Kovacevic, M. and Acampora, A., “Benefits of Wavelength Translation in All-Optical Clear-Channel Networks,”IEEE Journal on Selected Areas in
Barry Richard A.
Subramaniam Suresh
Hamilton Brook Smith & Reynolds P.C.
Massachusetts Institute of Technology
Pascal Leslie
Phan Hanh
LandOfFree
Method for establishing connections by allocating links and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for establishing connections by allocating links and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for establishing connections by allocating links and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028019