Method and apparatus for adaptive routing in packet networks

• US 6,260,072 B1
• Filed: 06/12/1997
• Issued: 07/10/2001
• Est. Priority Date: 06/12/1997
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rodriguez-Moral, Antonio
• Primary Examiner(s): Geckil, Mehmet B.
• Assistant Examiner(s): Vaughn, Jr., William C.
• Application Number:
  US08/873,608
• Time in Patent Office: 1,489 Days
• Field of Search: 709/218, 709/223, 709/224, 709/239, 709/240, 709/241, 709/242, 709/238, 709/235, 370/238, 370/237, 370/351, 370/372, 370/389, 370/400, 370/412, 370/235, 370/231, 370/388, 370/390, 370/413, 370/234, 370/255, 370/230, 370/236, 710/53
• US Class Current: 709/241
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service

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.

Claims

1. 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.

2. The network according to claim 1, and further comprising

c) means for selecting packets alternately from the first and second queues, and routing the selected packets to respective other nodes.

3. The network according to claim 1, in which each packet contains an identifier indicating its type.

4. The network according to claim 1, and further comprising

c) means for updating the routing tables at intervals.

5. The network according to claim 4, in which different parameters are used to update the two tables.

6. 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.

7. Method according to claim 6, in which the next-hop routing tables are updated at intervals, thereby changing the respective paths.

8. 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.

9. 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;

${\mathrm{LL1}}_{\mathrm{ik}}<br><br>\left(t+\mathrm{\epsilon <br><br>}\right)=\left[\begin{array}{cc}1+\mathrm{INTEGER}<br><br>\left\{\left(1-\mathrm{\alpha <br><br>}\right)<br><br>Q_D<br><br>\left[{\mathrm{D1}}_{\mathrm{ik}}<br><br>\left(t\right)\right]+\mathrm{\alpha <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{LL1}}_{\mathrm{ik}}<br><br>\left(t\right)\right\}& \mathrm{IF}<br><br><br><br>\frac{{\mathrm{LL1}}_{\mathrm{ik}}<br><br>\left(t+\mathrm{\epsilon <br><br>}\right)-{\mathrm{LL1}}_{\mathrm{ik}}<br><br>\left(t\right)}{{\mathrm{LL1}}_{\mathrm{ik}}<br><br>\left(t\right)}<br><br>\ge <br><br>0.75\\ \mathrm{LL1}<br><br>\left(t\right)& \mathrm{otherwise}\end{array}\right]$${\mathrm{LL2}}_{\mathrm{ik}}<br><br>\left(t+\mathrm{\epsilon <br><br>}\right)=\left[\begin{array}{cc}1+\mathrm{INTEGER}<br><br>\left\{\left(1-\mathrm{\beta <br><br>}\right)<br><br>Q_U<br><br>\left[U_{\mathrm{ik}}<br><br>\left(t\right)\right]+\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{LL2}}_{\mathrm{ik}}<br><br>\left(t\right)\right\}& \mathrm{IF}<br><br><br><br>\frac{{\mathrm{LL2}}_{\mathrm{ik}}<br><br>\left(t+\mathrm{\epsilon <br><br>}\right)-{\mathrm{LL2}}_{\mathrm{ik}}<br><br>\left(t\right)}{{\mathrm{LL2}}_{\mathrm{ik}}<br><br>\left(t\right)}<br><br>\ge <br><br>0.15\\ \mathrm{LL2}<br><br>\left(t\right)& \mathrm{otherwise}\end{array}\right]$

in which

10. Method according to claim 9, and further comprising the step of

d) recording the routing tables;

and

e) maintaining recorded routing tables in a historical record.