Method and apparatus for adaptive routing in packet networks
AssigneeLucent Technologies Inc.
InventorAntonio Rodriguez-Moral
Life of this patent
Estimating the term…
Abstract
A system for routing data packets in a packet network. Packets are classified as either type-1 or type-2. Each type is routed to its destination on a smallest-delay path. However, each type can experience a different time delay between nodes in the network. Thus, the smallest-delay path for a type-1 packet may be different from that for a type-2 packet, even if the origin and destination of both types are the same. Further, these time delays can change. The invention monitors the changes, and continually identifies the smallest-delay paths for the packets.
Claims10
In a node in a computer network, the improvement comprising:
- a) a computer for receiving data packets, of first and second types, from other nodes;
- and
- b) program means for
- i) queuing packets of the first and second types into respective first and second queues;
- ii) routing packets in the first queue according to a first routing table;
- and
- iii) routing packets in the second queue according to a second routing table;
- iv) measuring average delay time taken by packets when they cross links, and using the average delay time to update the first routing table;
- and
- v) measuring average utilization of links, and using the average utilization to update the second routing table.
A method of operating a computer network, which comprises nodes, at least some of which maintain access to both
- (1) a first table for type-1 packets, and
- (2) a second table for type-2 packets, both tables being of the next-hop routing type, comprising the following steps:
- a) receiving, at nodes, data packets, each bearing a tag identifying it as type-1 or type-2;
- b) routing the type-1 packets along respective paths which result in an average transit time T1;
- c) routing the type-2 packets along respective paths which result in an average transit time T2, which exceeds T1,
- d) measuring average delay time, ADT, of packets across links, and updating the first routing table using measured ADT;
- and
- e) measuring utilization of links, and updating the second routing table using measured utilization.
A method for routing data packets among nodes in a network, comprising the steps of:
- a) classifying each packet as either type-1 or type-2;
- b) tagging each packet with a destination node;
- c) for each node, maintaining, for each outgoing link from the node
- i) a queue for type-1 packets, and
- ii) a queue for type-2 packets;
- d) for each node, maintaining
- i) a next-hop routing table for type-1 packets, and
- ii) a next-hop routing table for type-2 packets;
- e) at each node, placing each incoming type-1 packet into the node's type-1 queue, and placing each incoming type-2 packet into the node's type-2 queue;
- f) at each node,
- i) withdrawing a packet from the type-1 queue;
- ii) ascertaining the destination node of the type-1 packet withdrawn;
- iii) based on the node's type-1 routing table and the destination node, ascertaining the next hop of the type-1 packet;
- iv) transmitting the type-1 packet to the node corresponding to the next hop;
- v) withdrawing a packet from the type-2 queue;
- vi) ascertaining the destination node of the type-2 packet withdrawn;
- vii) based on the node's type-1 routing table and the destination node, ascertaining the next hop of the type-2 packet;
- viii) transmitting the type-2 packet to the node corresponding to the next hop;
- ix) repeating (i) through (viii) as long as packets remain in the queues;
- g) at intervals, measuring average delays for type-1 packets for each link;
- h) at intervals, measuring average utilizations for each link;
- i) updating the routing tables for type-1 packets, using the average delays;
- and
- j) updating the routing tables for type-2 packets, using the average utilizations.
In a network, comprising nodes which are connected by data links, in which routing tables are used to find lowest-cost paths between nodes, the improvement comprising the following steps:
- a) for each link, computing two costs, LL1 and LL2, using the following expressions:
- LL1 ik ( t + ε ) = [ 1 + INTEGER { ( 1 - α ) Q D [ D1 ik ( t ) ] + α LL1 ik ( t ) } IF [LeftBracketingBar] LL1 ik ( t + ε ) - LL1 ik ( t ) LL1 ik ( t ) [RightBracketingBar] ≥ 0.75 LL1 ( t ) otherwise ] LL2 ik ( t + ε ) = [ 1 + INTEGER { ( 1 - β ) Q U [ U ik ( t ) ] + β LL2 ik ( t ) } IF [LeftBracketingBar] LL2 ik ( t + ε ) - LL2 ik ( t ) LL2 ik ( t ) [RightBracketingBar] ≥ 0.15 LL2 ( t ) otherwise ]
- in which
- 0≦α≦1.0
- 0≦β≦1.0
- QD(x)=1+INTEGER(97.5x)
- QV(x)=1+INTEGER(x103)
- epsilon, ε, represents an iteration interval
- U represents utilization of respective links
- D represents delay of respective links subscripts, ik, identify respective links,
- b) deriving two routing tables:
- a TABLE-1 based exclusively on costs LL1, and a TABLE-2 based exclusively on costs LL2;
- c) at intervals, repeating steps (a) and (b) and
- d) routing data packets of a first type, using TABLE-1, and routing data packets of a second type, using TABLE-2.
Dependencies are inferred from the claim text.