Route optimization and traffic management in an ATM network using neural computing

• US 6,411,946 B1
• Filed: 08/28/1998
• Issued: 06/25/2002
• Est. Priority Date: 08/28/1998
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Inventors: Chaudhuri, Aloke
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/143,687
• Time in Patent Office: 1,397 Days
• Field of Search: 706/21, 705/40
• US Class Current: 706/21
• CPC Class Codes: G06Q 20/102 Bill distribution or payments
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence

Abstract

Neural computing techniques are used to optimize route selection in a communication network, such as an ATM network. Output measurements of the network are used to provide optimal routing selection and traffic management. Specifically, link data traffic is monitored in the network to obtain traffic history data. An autoregressive backpropagation neural network is trained using the traffic history data to obtain respective predicted traffic profiles for the links. Particular links are then selected for carrying data based on the predicted traffic profiles. A cost function, limits on network parameters such as link cost and cell rate, and other quality of service factors are also considered in selecting the optimal route.

Claims

1. A method for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising the steps of:

monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links;

providing the respective predicted traffic profiles to a route discovery engine;

providing topology information of said communication network to said route discovery engine; and

processing the respective predicted traffic profiles and topology information at said route discovery engine utilizing a shortest-path algorithm to select at least one of said particular links for communicating the data in said communication network.

2. The method of claim 1, comprising the further step of:

communicating information indicative of the selected link(s) to particular node(s) associated therewith.

3. The method of claim 2, wherein:

said information is communicated as routing table update information.

4. The method of claim 1, wherein:

said respective predicted traffic profiles account for at least one of user-designated (a) notified exceptions and (b) logical exceptions.

5. The method of claim 1, wherein said neural network is an autoregressive backpropagation network, and said training step comprises the further steps of:

determining respective feedback weights and feedforward weights for at least particular ones of said nodes;

iteratively updating said respective feedback weights and feedforward weights to minimize an output error of said neural network.

6. The method of claim 1, wherein:

said at least one of said particular links is selected at a user-to-network interface.

7. The method of claim 1, wherein:

said at least one of said particular links is selected at a network-to-network interface.

8. The method of claim 1, comprising the further steps of:

providing a plurality of candidate routes comprising said links for communicating data in said communication network;

providing a set of “

n”

network parameters <

c₁, . . . , c_n>

for each of said candidate routes;

calculating a cost function for each of said candidate routes according to a weighted sum of the network parameters thereof; and

selecting one of said candidate routes according to the associated cost function for communicating data in said communication network.

9. The method of claim 8, comprising the further steps of:

providing limits for at least some of the network parameters for each of said candidate routes;

determining whether the network parameters are within the associated limit; and

selecting one of said candidate routes according to whether the network parameters thereof are within the associated limits.

10. The method of claim 8, wherein said network parameters include at least one of:

link cost;

peak cell rate;

sustainable cell rate;

intrinsic burst tolerance;

cell delay variation;

maximum allocated cell delay variation tolerance;

cell loss ratio; and

route length.

11. The method of claim 1, wherein:

the data traffic is transmitted in the communication network using Asynchronous Transfer Mode (ATM).

12. An apparatus for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising:

means for monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

means for training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links; and

means for processing the respective predicted traffic profiles and topology information of said communication network utilizing a shortest-path algorithm to select at least one of said particular links for communicating the data in said communication network.

13. The apparatus of claim 12, further comprising:

means for communicating information indicative of the selected link(s) to particular node(s) associated therewith.

14. The apparatus of claim 13, wherein:

said information is communicated as routing table update information.

15. The apparatus of claim 12, wherein:

said respective predicted traffic profiles account for at least one of user-designated (a) notified exceptions and (b) logical exceptions.

16. The apparatus of claim 12, wherein said neural network is an autoregressive backpropagation network, and said training means comprises:

means for determining respective feedback weights and feedforward weights for at least particular ones of said nodes; and

means for iteratively updating said respective feedback weights and feedforward weights to minimize an output error of said neural network.

17. The apparatus of claim 12, wherein:

said at least one of said particular links is selected at a user-to-network interface.

18. The apparatus of claim 12, wherein:

said at least one of said particular links is selected at a network-to-network interface.

19. The apparatus of claim 12, further comprising:

means for providing a plurality of candidate routes comprising said links for communicating data in said communication network;

means for providing a set of “

n”

network parameters <

c₁, . . . ,c_n>

for each of said candidate routes;

means for calculating a cost function for each of said candidate routes according to a weighted sum of the network parameters thereof; and

means for selecting one of said candidate routes according to the associated cost function for communicating data in said communication network.

20. The apparatus of claim 19, further comprising:

means for providing limits for at least some of the network parameters for each of said candidate routes;

means for determining whether the network parameters are within the associated limit; and

means for selecting one of said candidate routes according to whether the network parameters thereof are within the associated limits.

21. The apparatus of claim 19, wherein said network parameters include at least one of:

link cost;

peak cell rate;

sustainable cell rate;

intrinsic burst tolerance;

cell delay variation;

maximum allocated cell delay variation tolerance;

cell loss ratio; and

route length.

22. The apparatus of claim 12, wherein:

the data traffic is transmitted in the communication network using Asynchronous Transfer Mode (ATM).

23. An apparatus for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising:

a route discovery engine;

a monitoring facility; and

a neural network associated with said route discovery engine and said monitoring facility;

wherein;

said monitoring facility is adapted to monitor data traffic of at least particular ones of said links to obtain respective traffic histories thereof, and to provide a corresponding signal to said neural network;

said neural network is adapted to receive the signal corresponding to the traffic histories for use in calculating respective predicted traffic profiles of said particular links, and to provide a corresponding signal to said route discovery engine; and

said route discovery engine is adapted to receive and process the signal corresponding to the predicted traffic profiles and a signal indicative of a topology of said communication network utilizing a shortest-path algorithm to select at least one of said particular links for communicating the data in said communication network.

24. The apparatus of claim 23, further comprising:

a transmitter associated with said route discovery engine;

said transmitter transmitting information indicative of the selected links(s) to particular node(s) associated therewith.

25. The apparatus of claim 23, further comprising:

a routing table update function associated with said route discovery engine for communicating routing table update information indicative of the selected link(s) to particular node(s) associated therewith.

26. The apparatus of claim 23, wherein:

said neural network is adapted to receive a signal indicative of at least one of user-designated (a) notified exceptions and (b) logical exceptions for use in calculating said respective predicted traffic profiles.

27. The apparatus of claim 23, wherein said neural network is an autoregressive backpropagation network, said neural network comprising:

a processor for determining respective feedback weights and feedforward weights for at least particular ones of said nodes, and for iteratively updating said respective feedback weights and feedforward weights to minimize an output error of said neural network.

28. The apparatus of claim 23, wherein:

said at least one of said particular links is selected at a user-to-network interface.

29. The apparatus of claim 23, wherein:

said at least one of said particular links is selected at a network-to-network interface.

30. The apparatus of claim 23, wherein said route discovery engine evaluates a plurality of candidate routes comprising said links for communicating data in said communication network according to a set of “

n”

network parameters <

c₁, . . . , c_n>

for each of said candidate routes, said route discovery engine comprising;

a processor adapted to calculate a cost function for each of said candidate routes according to a weighted sum of the network parameters thereof;

wherein;

said route discovery engine is adapted to select one of said candidate routes according to the associated cost function for communicating data in said communication network.

31. The apparatus of claim 30, wherein said route discovery engine is responsive to limits for at least some of the network parameters for each of said candidate routes, said route discovery engine comprising:

a processor adapted to determine whether the network parameters are within the associated limit;

said route discovery engine adapted to select one of said candidate routes according to whether the network parameters thereof are within the associated limits.

32. The apparatus of claim 30, wherein said network parameters include at least one of:

link cost;

peak cell rate;

sustainable cell rate;

intrinsic burst tolerance;

cell delay variation;

maximum allocated cell delay variation tolerance;

cell loss ratio; and

route length.

33. The apparatus of claim 23, wherein:

the data traffic is transmitted in the communication network using Asynchronous Transfer Mode (ATM).

34. A method for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising the steps of:

monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links, said respective predicted traffic profiles accounting for at least one of user-designated (a) notified exceptions and (b) logical exceptions;

providing the respective predicted traffic profiles to a route discovery engine;

providing topology information of said communication network to said route discovery engine; and

processing the respective predicted traffic profiles and topology information at said route discovery engine to select at least one of said particular links for communicating the data in said communication network.

35. An apparatus for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising:

means for monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

means for training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links, said respective predicted traffic profiles accounting for at least one of user-designated (a) notified exceptions and (b) logical exceptions; and

means for processing the respective predicted traffic profiles and topology information of said communication network to select at least one of said particular links for communicating the data in said communication network.

36. An apparatus for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising:

a route discovery engine;

a monitoring facility; and

a neural network associated with said route discovery engine and said monitoring facility;

wherein;

said monitoring facility is adapted to monitor data traffic of at least particular ones of said links to obtain respective traffic histories thereof, and to provide a corresponding signal to said neural network;

said neural network is adapted to;

(1) receive the signal corresponding to the traffic histories for use in calculating respective predicted traffic profiles of said particular links, said respective predicted traffic profiles accounting for at least one of user-designated (a) notified exceptions and (b) logical exceptions; and

(2) provide a corresponding signal to said route discovery engine; and

said route discovery engine is adapted to receive and process the signal corresponding to the predicted traffic profiles and a signal indicative of a topology of said communication network to select at least one of said particular links for communicating the data in said communication network.

37. A method for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising the steps of:

monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links;

providing the respective predicted traffic profiles to a route discovery engine;

providing topology information of said communication network to said route discovery engine; and

processing the respective predicted traffic profiles and topology information at said route discovery engine to select at least one of said particular links for communicating the data in said communication network, wherein at least one of said particular links is selected at a network-to-network interface.

38. A method for determining an optimal route for transmission of data in a communication network comprising a plurality of nodes and associated links connected thereto, comprising the steps of:

monitoring data traffic of at least particular ones of said links to obtain respective traffic histories thereof;

training a neural network using said traffic histories to obtain respective predicted traffic profiles of said particular links;

providing the respective predicted traffic profiles to a route discovery engine;

providing topology information of said communication network to said route discovery engine;

processing the respective predicted traffic profiles and topology information at said route discovery engine to select at least one of said particular links for communicating the data in said communication network;

providing a plurality of candidate routes comprising said links for communicating said data in said communication network;

providing a set of “

n”

network parameters <

C₁, . . . , C_n>

for each of said candidate routes;

calculating a cost function for each of said candidate routes according to a weighted sum of the network parameters thereof; and

selecting one of said candidate routes according to the associated cost function for communicating said data in said communication network.

39. The method of claim 38, comprising the further steps of:

providing limits for at least some of the network parameters for each of said candidate routes;

determining whether the network parameters are within the associated limits; and

selecting one of said candidate routes according to whether the network parameters thereof are within the associated limits.

40. The method of claim 38, wherein said network parameters include at least one of:

link cost;

peak cell rate;

sustainable cell rate;

intrinsic burst tolerance;

cell delay variation;

maximum allocated cell delay variation tolerance;

cell loss ratio; and

route length.