Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-20
2001-10-30
Hsu, Alpus H. (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S352000, C370S236000
Reexamination Certificate
active
06310881
ABSTRACT:
TECHNICAL FIELD
The present invention is related generally to data communication systems and, in particular, to network control of data communication systems.
BACKGROUND OF THE INVENTION
Data communication systems generally consist of multiple networks that are linked together with bridges, switches, routers, or other devices. These linking devices direct data packets along various paths from an origination to a destination. Since a data communication system tends to be large with many networks and interconnecting links, typically a data packet can take many paths from its origination to its destination. A goal of a network traffic director system is to direct the journey of each data packet from its origination to its destination so that the capacity of the network is efficiently utilized.
Traditional network traffic director systems utilize a plurality of network routers based on Internet Protocol (IP). The IP routing approaches are based on a Shortest Path (SP) method in which packets are sent to their destinations along the shortest paths in the network. There are various methods to determine shortest paths among the IP routing approaches. However, these approaches all share a common assumption that if each packet travels along the shortest path, then the overall workload required for the routing will remain as small as possible.
The assumption of traditional routing systems would hold true if the overall performance of a routing system could be adequately measured solely on the basis of the total number of decisions that routers need to perform. However, other factors are involved in the overall performance of a routing system. One of these factors is the amount of congestion in a data communication system. Some theoretical proposals exist which attempt to address the congestion of network traffic director systems. These approaches, however, are impractical in providing adequate solutions to the congestion problem. The end result of some of these approaches produces, on average, flows that are little different than the shortest path methods of IP routing taking congestion into account. Another theoretical approach to congestion is intended for environments having predefined aspects, such as loading and network topology. However, a data communication system is seldom sufficiently predictable for these predefined approaches.
Other theoretical approaches attempt to address an aspect of the stochastic (random) nature of flows in a data communication system by allowing for randomness in the arrival times of individual data packets into a linking device. These approaches, however, are still formulated in a deterministic manner by requiring that demand or load rates and flow rates in other parts of the communication system be known in advance of their actual occurrence.
These prior art deterministic approaches are not ideally suited for data communication system environments in which demands or loads and flows in other portions of the data communication system have stochastic distributions due to changing demands or loads of individual users or due to any multiplexing involved. This means that not only are the arrival times of individual packets random, but also the rates of the demands or loads and flows in other portions of the data communication system are random and not known before their actual occurrence.
An effective optimization method must not only minimize congestion in the data communication system but it must be robust enough to adapt to sudden changes in conditions of the data communication system such as packet arrival, loading on the system, and system topology without predefined scenarios of when or how these changes will occur.
In data communication systems, loading changes quickly and dramatically due to such influences as changing demands or loads of individual users and multiplexing methods such as time division multiplexing (TDM) where time slots of system use are divided among individual users. With TDM, a data communication system constantly changes the particular users on the system at any given moment, thus loading changes rapidly. Network topology can also have rapid stochastic changes due to situations such as equipment failures or weather conditions.
Also, whereas the prior art systems and methods focus on a single indicator, Such as shortest path or average delay, as a basis to optimize data flow, there are many additional factors. These include average queue length at various data communication system linking devices, variance or standard deviation in individual delays of data packets traveling from an origination to a destination, and average and variance of the individual utilized capacity of links and linking devices in a data communication system. Thus, a system and method is greatly desired which optimizes packet flow in a data communication system based on numerous factors while being robust enough to effectively adapt to unexpected events.
SUMMARY OF THE INVENTION
The present invention is directed to a network traffic director system in a data communication system having network traffic with randomly distributed demands and flows. In one aspect of the present invention the network traffic director system includes router modules configured to direct data packets in the data communication system, each router module being a home router module including a neighborhood supervisor. The neighborhood supervisor is configured to send home potentials of the home router module to neighborhood supervisors of neighboring router modules and to receive neighbor potentials of the neighboring router modules from neighborhood supervisors of neighboring router modules. The home router module further includes a dynamic load balancer configured to determine flows based on the home and neighbor potentials. The dynamic load balancer adjusts the home potentials if first conditions including flow conditions are not met. The dynamic load balancer also updates routing tables if second conditions based on the adjusted home potentials are met. The home router module also includes a dynamic data flow splitter configured to receive data packets from networks and router modules. The dynamic data flow splitter selects a portion of the data communication system for each data packet received based on the updated routing tables. Each received data packet is transmitted to the portion of the data communication system selected by the dynamic data flow splitter for the received data packet.
Another aspect of the invention includes the home potentials of each home router module being associated with a pair of nodes of the data communication system including an origination node and a destination node. The home potentials of each router module are also associated with a quality of service level. The neighborhood supervisor is configured to send the home potentials to neighborhood supervisors of neighboring router modules when the flow conditions are not met. The flow conditions include conservation of flows. The dynamic load balancer is configured to determine flows by using a response function associated with optimizing at least one of a penalty function or a merit function for stochastic demands or flows of the data communication system. The dynamic data flow splitter is configured to select the portion of the data communication system for each packet received further based on either a Markov protocol, a Routing Wheel protocol, previously selected portions of the data communication when an address for a received data packet is a same type as an address stored in the dynamic data flow splitter, or on a quality of service level associated with a data packet.
In a further aspect of the invention the neighborhood potentials are stored according to an aggregation scheme. The merit or penalty functions are at least locally approximated by a quadratic function of the flows. The ideal data flows are further based on resistance of arcs associated with the router module wherein each resistance of an arc is configured to be a function of either arc capacity or a function of flows of the arc.
Sowizral Henry Adam
Zikan Karel
Blakely Sokoloff Taylor and Zafman
Hsu Alpus H.
Nguyen Brian
Terabeam Corporation
LandOfFree
Method and apparatus for network control 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 and apparatus for network control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for network control will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2560585