Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-05-19
2004-12-14
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S235000, C370S229000, C709S239000, C709S241000
Reexamination Certificate
active
06831895
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed at relieving “congestion” in communications networks. In particular, the present invention is directed at relieving congestion in a network which uses “shortest path” routing techniques to manage data which is traversing, and congesting, the network.
The Internet is one example of such a network.
The Internet is a vast array of interconnected computers and computer systems. The ability to connect one personal computer to potentially a million other personal computers making up the Internet, requires a hierarchy of more sophisticated computers whose job is to “route” messages to and from these millions of computers in an efficient, fast and cost effective manner. These more sophisticated computers are aptly called “routers”. With the explosive growth of the Internet has come a need to use more sophisticated routers to insure that communications between computers on the Internet remains relatively trouble free. Problems due to “congestion,” which occurs, broadly speaking, when there are not enough communication channels or available bandwidth on such channels to handle the volume of messages being sent, have begun to occur. When congestion occurs it usually results in an increase in connection and response time, where it takes longer to connect to the Internet and/or receive responses to a search or message.
Within a specific geographic area many routers are placed into a group called an “autonomous system” (“AS”). Usually, each AS is controlled by an entity known as an Internet Service Provider (“ISP”). Thus, a message sent from Washington, D.C. to Philadelphia, Pa., for example, will typically travel over a number of ISPs each comprising their own array of routers. The routing of messages between ISPs connected to each other is typically performed using known “routing protocols”. These protocols allow the respective routers within each ISP to “talk” with each other. There are a number of protocols which may be used to allow such communications.
More specifically, it is important for a router to know where an incoming message is supposed to be sent. Each message has associated with it a destination Internet protocol (“IP”) address. Upon receiving the destination address, a router will use its embedded routing protocol to determine how best to forward the message to its final destination. Between the router which receives the message and the final destination of the message are any number of routers. Each successive router must select the next router in the chain of routers leading to the final destination. These next routers may be referred to as “next hops”. The particular protocol used by a router will determine the “next hop” for the message. Once the message has been sent to a next hop router, this new router will repeat the process.
One class of routing protocols is known as a “link state” protocol. Routers using this type of protocol each share a combined database of information concerning all of the other routers within the same ISP. The information typically consists of the “network topology” and the “weight” of each communication “link”. By network topology is meant the “road map” of complex connections between each router in an ISP. Each connection may in turn comprise a number of smaller links. Each link has a given “weight” which governs the amount of “traffic” or number of messages which may flow across each link depending on a variable, such as cost. A “path” from one router to another may be created by “stringing” a number of “weighted” links together. Because each router has access to information about all of the links within an ISP, each router is able to determine a “shortest path” from one router to another. Such a shortest path may include traversing a number of weighted links. Between each router there may exist a number of shortest paths or “equal cost paths” (“ECPs”).
Some specific link state protocols are “Open Shortest Path First” and “Intermediate System-Intermediate System” protocols.
There may be hundreds, if not thousands of routers, in a pathway between the origin of a message and its eventual destination. Determining the shortest path through such an array of routers can be a daunting task; a task which is made even worse once this vast network of routers begins to become congested with traffic. Traditional approaches to managing congestion have faced two significant challenges. First, it has been thought that to effectively “manage congestion” through a given router, the amount of traffic through each and every router in an AS must be known at any given period of time. More precisely, this would require each router to analyze each message coming into it by looking at each messages “origin” and “destination” address. Taking it one step further, because a given link consists of an “origin” router and a “destination” router (called an origin/destination or “O/D” pair) it has been thought that what is needed is the ability to measure traffic flow (by origin and destination address) into and out of both the origin and destination routers. Even in a simple routing network, this task becomes insurmountable because of the thousands, if not millions, of messages and corresponding potential origin/destination addresses. If a router was asked to perform this task, its throughput would be greatly affected leading to a slower, less efficient pathway
etwork.
The second challenge relates to changing link weights. Again, a link's weight affects the amount of traffic which will traverse the link. An increase or decrease in a link's weight will increase or decrease traffic flow across that link. However, because each link is potentially a part of a million (for example) different paths, a simple change in one link may affect the traffic flow throughout each and every path which happens to include that link. Thus, attempts to decrease congestion through one link by changing its link weight would result in simply shifting the congestion to another link or path. Worse yet, the size and complex nature of the millions of paths connecting distant routers together makes the shifting of this congestion extremely unpredictable. Simply shifting traffic from one link to another may end up congesting a line of other links.
As mentioned initially, the Internet is only one type of network which utilizes routers and attempts to control congestion by looking at the “shortest paths” between two O/D routing pairs. In general, congestion is a problem in many networks using multiple routers. When data traverses from one router to the next it is sometimes referred to as going “hop-by-hop” or “next hop to next hop.” In data communications, a single message may be broken up into “packets” of information which are routed “hop-by-hop”.
To those skilled at the art, therefore, the problem becomes how to relieve congestion in hop-by-hop, routed packet networks. Accordingly, it is an object of the invention to provide for methods and devices which relieve congestion in hop-by-hop routed packet networks, such as the Internet.
It is another object of the invention to provide for such methods and devices which assume, contrary to present day wisdom, that the traffic flow through a pair of O/D routers in a given path cannot be determined and is, therefore, an unknown.
It is a further object of the present invention to provide for methods and devices which shift traffic flow from a congested link without congesting any additional links by either adjusting “splitting factors” associated with the congested link and alternative paths or, when no such alternative paths exist, by creating new alternative paths and then adjusting the respective alternative paths.
It is yet a further object of the present invention to provide for programs for adjusting splitting factors and creating alternative paths which make use of “virtual” networks.
It is still another object of the invention to provide for unique programs for deleting alternate paths which are no longer needed.
Other objectives, features and advantages of the present inventio
Ji Hongbin
Kodialam Muralidharan Sampath
Wang Yung-Terng
LandOfFree
Methods and devices for relieving congestion in hop-by-hop... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and devices for relieving congestion in hop-by-hop..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and devices for relieving congestion in hop-by-hop... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321156