Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1998-08-28
2002-06-25
Powell, Mark R. (Department: 2122)
Data processing: artificial intelligence
Neural network
Learning task
C705S040000
Reexamination Certificate
active
06411946
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for using neural computing techniques, also known as neural networks, to optimize route selection in a computer communication network. The invention is particularly suitable for use with ATM networks, but can be used in other networks with Quality of Service requirements, such as IP and the OSI family of protocols.
The following acronyms are used:
ABR—Available Bit Rate
ARBP—Autoregressive Backpropagation
ARIMA—Autoregressive Integrated Moving Average
ARMA—Autoregressive Moving Average
ATM—Asynchronous Transfer Mode
B-ISDN—Broadband Integrated Services Digital Network
CAC—Connection Admission Control
CBR—Constant Bit Rate
CDV—Cell Delay Variation
IBT—Intrinsic Burst Tolerance
IP—Internet Protocol
NNI—Network-to-Network Interface
OSI—Open Systems Interconnection
PCR—Peak Cell Rate
PVC—Permanent Virtual Circuit
QoS—Quality of Service
SCR—Sustainable Cell Rate
SVC—Switched Virtual Circuit
TCP—Transmission Control Protocol
UBR—Unspecified Bit Rate
UNI—User-to-Network Interface
UPC—Usage Parameter Control
VBR—Variable Bit Rate
Computer networks continue to carry increasing amounts of data traffic for various purposes. For example, the popularity of the Internet for educational, business and entertainment purposes is rapidly increasing. Moreover, local area networks, metropolitan area networks, and wide area networks have also become increasingly popular for use by corporations, the government, universities and the like. Furthermore, integration of networks that carry audio, video and other data is occurring.
Accordingly, different data transmission protocols have been developed in an attempt to manage the flow of data in these networks to avoid congestion and increase system throughput.
In particular, the ATM protocol is designed to provide a high-speed, low-delay multiplexing and switching network that supports any type of user traffic, such as voice, data, or video applications. ATM is an underlying technology for B-ISDN, which can offer video on demand, live television from multiple sources, full motion multimedia electronic mail, digital music, LAN interconnection, high-speed data transport for science and industry, and other services via an optical fiber telephone line.
Since ATM is a connection-oriented protocol, a virtual circuit is established prior to sending data. The virtual circuit defines the travel path for the data, e.g., which switches and transmission links are to be traversed. User traffic is segmented into small, fixed-length cells of 53 bytes each with cell headers that identify the virtual circuit. During transmission, high-speed switches read the cell header to relay the traffic to the next designated destination.
To optimize network resources and control congestion, various factors must be considered in selecting a virtual circuit. For example, an ATM network is required to perform a set of actions called Connection Admission Control (CAC) during a call setup to determine if a user connection will be accepted or rejected. However, traffic management through CAC offers a significant challenge to the designer. Complexity arises from the need to support the natural bit rates of all multi-application traffic being serviced in different consumer classes (e.g., CBR, UBR, VBR and ABR) through optimal sharing of bandwidth.
Additionally, various QoS parameters must be met. These parameters relate to cell error ratio, severely-errored cell block ratio, cell loss ratio, cell mis-insertion rate, cell transfer delay, mean cell transfer delay, and cell delay variation, for example.
Accordingly, an appropriate routing technique must be used to select an optimum virtual circuit and manage network traffic. Conventional routing techniques include nonadaptive algorithms (e.g., static routing) that do not base their routing decisions on real-time measurements or estimates of the current traffic and topology. The optimal route can therefore be computed in advance, off-line, and downloaded to the appropriate routers.
Static techniques includes shortest path routing, flooding, and flow-based routing.
In contrast, adaptive or dynamic routing algorithms change their routing decisions real-time to reflect changes in the topology and/or traffic. Dynamic routing techniques include distance vector routing and link state routing.
With the shortest path routing technique for selecting a virtual circuit, the shortest physical path between the source machine and the destination machine is selected. The routing decision is generally made once when a virtual circuit is being set up, and maintained for the remainder of the session. However, using shortest path routing on a per-request basis often leads to sub-optimal or even highly congested network solutions, and is not considered a good design practice.
Generally, in any given ATM network, the links with varying amounts of bandwidth can support a multitude of services using both point-to-point and point-to-multipoint routing mechanisms. Each of these services, when multiplexed over a common stream, needs optimal allocation of network resources based on global information across the entire network. From a network provider perspective, the routing strategy can be planned in a number of different ways to maximize revenue generation.
The present invention is concerned with finding an optimal routing solution that ensures minimum cost of routing with maximum bandwidth usage, while maintaining the QoS parameters within the user-specified threshold values.
Unlike conventional source (e.g., static) routing or dynamic routing schemes, the route discovery engine of the present invention constantly changes its decision based on the current traffic profile across all the links in the network. The engine uses a priori knowledge of the traffic pattern so that the decisions can be made in a real-time system without any significant delay.
Some researchers have tried to address this type of time-series prediction problem through expert systems. Their biggest drawback is the inflexibility caused by static, rule-based algorithms that require a priori knowledge of the system dynamics, and the need for human expertise to improve their performance. Moreover, statistical interpolation methods (e.g., using ARMA/ARIMA models) have limited success in certain situations, but the underlying assumption of linear system dynamics renders the model ineffective in most cases involving complex traffic patterns, which are highly non-linear.
The present invention is concerned with addressing the above issues by adapting an artificial neural network-based learning and prediction strategy to provide optimal routing selection and traffic management in a communication network.
Research efforts to date have produced various neural network-based approaches for parameter estimation and trend analysis of dynamic systems. The majority of these methods are based on state feedback, an approach limited by the availability of system states. However, in a typical communication network, such as an ATM network, the states are difficult to measure without employing elaborate, model-dependent state estimators and sensing devices. This makes the implementation of the traffic prediction algorithms based on state feedback very difficult.
These drawbacks have motivated the present research towards development of a neural network-based prediction scheme that makes use of only output measurements as they become available from sensor readings.
The Backpropagation Algorithm is a known neural network learning technique that looks for the minimum of an error function in weight space using the method of gradient descent. The combination of weights which minimizes the error function is considered to be a solution of the learning problem. However, ordinary backpropagation networks are unable to learn temporal and context sensitive patterns.
Accordingly, it would be desirable to provide a neural network-based prediction scheme employing a variant of the backpropagation network that makes use of only output measurements of a n
General Instrument Corporation
Lipsitz Barry R.
Powell Mark R.
Starks Wilbert
LandOfFree
Route optimization and traffic management in an ATM network... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route optimization and traffic management in an ATM network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route optimization and traffic management in an ATM network... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2908139