Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-08-01
2004-07-27
Vincent, David (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S351000
Reexamination Certificate
active
06768718
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to routing schemes in communication networks and, more particularly, to a courteous routing scheme.
BACKGROUND OF THE INVENTION
Routing in a telecommunication network is a critical function that shapes the design and operation of the network. The routing function in circuit-switched and data networks has been extensively studied. In particular, routing schemes in circuit-switched networks, such as the public switched telephone network (PSTN), have been enhanced over the past few decades. However, circuit-switched networks are not, at present, undergoing any significant changes, and currently-employed routing schemes, such as classical hierarchical routing and the variety of flat-routing schemes including those known as adaptive routing, dynamic routing and high-performance routing, are likely to remain unchanged. Data networks, in contrast, are undergoing significant changes. In particular, the Internet has experienced very rapid growth in coverage and capacity. In addition to coverage and capacity expansion, it is now widely recognized that quality control is a major requirement for an effective global Internet. The manner in which quality-of-service (QoS) and grade-of-service (GoS) are controlled is determined primarily by schemes employed for routing and traffic allocation. A node controlling QoS or GoS should have an ability to allocate traffic loads among alternative outgoing routes.
A network may be modeled as comprising nodes that are fully or partially interconnected by (transmission) links, where the links may have different capacities and different associated costs. As well, the number of links emanating from each node may vary from one node to another. The term “node”, as used herein, is used for a router or switch responsible for routing and traffic allocation. A route is a link or a chain of links connecting a source node to a sink node where a source node is the node supporting traffic sources (the origins of traffic) and a sink node is the node supporting traffic sinks (the destinations of traffic). A node functioning as a router determines a subjective “best route” to another node based on various factors which may be combined to determine a cost factor. The factors may include qualities such as reliability and delay. A node may function as a source node and a sink node for distinct streams of traffic.
A source node and a sink node form a “node-pair”. For a particular node-pair, each member of an associated “route set” is a different route between the source node and the sink node that comprise the node-pair. The routes within each route set may be selected to have different first links and may be ranked according to such criteria as total cost and route intersection levels. Conventionally, the route sets for different node-pairs are, however, determined independently without considering the level of intersection among routes connecting different sources to sinks.
Upon arrival of a connection request at a particular node, a controller of that particular node may allocate the requested connection to one of the routes in a route set associated with the node-pair comprising the particular node and the sink node specified by the connection request. In one routing scheme, the route to which the requested connection is allocated may be, for instance, the highest ranked route that has sufficient free capacity, where the routes of a route set are ranked by cost.
In many routing schemes, a particular route in a route set may further have an x associated “static route capacity” which is representative of the full capacity of the link in the route that has least capacity. By definition, the “full capacity” of a link is the maximum data rate that can be supported by the link. The static route capacity of a particular route in a route set may be included in the same data structure that identifies the path of each route in the route set, or may otherwise be made available to a source node. However, the full capacity of one link in the particular route may not always be available to a source node considering allocation of a connection to the particular route.
Traffic allocated to routes in distinct route sets may compete for the capacities of common links. This results in two undesirable effects. The first is that a high proportion of connection attempts may fail to use the best route, leading to use of other routes in respective route sets for the node-pairs and increasing the required computational effort. The second is that haphazard redirection of a connection away from its best route may lead to a connection being allocated to a next best route in a meager route set (i.e., a route set with few members). Where one connection between a first node-pair has been allocated to a first route, the next best route in the meager route set of a second node-pair may be significantly more costly than the next best route in the route set for the first node-pair.
SUMMARY OF THE INVENTION
The routing scheme of the present invention is called “courteous” because the node-pair that suffers the least by a diversion of a part of its traffic to a higher-cost route yields the use of a potentially overloaded link to node-pairs that suffer more by redirecting traffic. The method of the present invention involves providing nodes with route-adaptation information including a route set for each node-pair, and a load-adaptation vector to associate with each route set. A route set includes a number of alternate routes from a source node to a sink node and a load-adaptation vector influences the allocation of traffic to individual routes within the route set with which it is associated. The method uses a minimum-penalty criterion with minimum route-intersection to resolve conflicting objectives. The route-adaptation information may, periodically, be updated in response to a metric representative of traffic change exceeding a threshold.
In accordance with an aspect of the present invention there is provided, at a controller of a network, the network including nodes and links between the nodes, a method of distributing routing information to the nodes, the method including receiving traffic information from the nodes and, based on the received traffic information, determining adaptive routing information corresponding to each node. The method further includes transmitting to each node the corresponding adaptive routing information for use by each node in making traffic routing decisions. In a further aspect of the present invention, there is provided a software medium that permits a general purpose computer to carry out this method.
In accordance with a further aspect of the present invention there is provided, in a network including nodes interconnected by links, where each of the nodes has a route set corresponding to each other of the nodes in the network, and each route set comprises a set of routes to the each other of the nodes in the network, a method of route capacity allocation, including transmitting, to each of the nodes, node-specific adaptive routing information for use by each of the nodes in route capacity allocation, and receiving traffic information from the nodes. The method further includes, responsive to a determination that, based on the received traffic information and the node-specific adaptive routing information, traffic allocated to two or more routes having a common link may overload the common link, altering the node-specific adaptive routing information such that a proportion of traffic allocated to a given route of the two or more routes having the common link is re-directed to an alternate route where the given route is in a given route set in which a cost differential between the given route and the alternate route is a minimum. The method also includes transmitting the altered node-specific adaptive routing information to each of the nodes to which the altered node-specific adaptive routing information corresponds.
In accordance with a further aspect of the present invention there is provided, at a first node in a ne
Beshai Maged E.
Blouin François J.
Nortel Networks Limited
Vincent David
LandOfFree
Courteous routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Courteous routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Courteous routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211115