Dynamic Routing for QoS and Active Networks
Present-day IP networks are still based on static routing methods.
Dynamic routing is one of the key technologies that cuts across the whole spectrum of the next generation networks. Although routing is at the heart of any computer network, advances in routing have not kept pace with other developments. IP routing today is still based on longest prefix matching. Routes are exchanged with the assumption that they will be static, and in fact, routes which change repeatedly are called route-flaps and are regarded as a serious error condition.
The algorithms used for route convergence are based on the shortest path; all traffic is forced through it and unless considerable attention is paid to network engineering, the shortest path often is the most congested one. Routers drop packets when their input queues overflow, and dropped packets cause TCP to switch into congestion avoidance mode.
Congestion avoidance acts by reducing throughput (sometimes to zero), then cautiously ramping up. The time scale for this ramp up can be several minutes on a cross-country link. The net effect of all of this is to make end-to-end performance highly unpredictable and distinctly sub-optimal. While such unpredictability can be tolerated in services such as e-mail, it can cause severe problems in applications such as distributed simulation and instrument control, which demand predictability, and high performance computing, which demands high bulk throughput.
Dynamic routing is needed now for many applications:
- Quality of Service (QoS)
- Large distributed simulations
- Data transfers to and from high performance machines
- Control of sensors and robots over networks
If today's routing methods are inadequate for static networks, they are totally unable to deal with networks which may have to be dynamic. For example, in optical networks, where the inter-exchange carriers are proposing to broker bandwidth and service, the price, latency, and route could all vary as a function of time-of-day.
Finally, the connectivity in ad-hoc networks could be quite varied, and networks deployed in field operations may have to be self-configuring. In view of the next generation networks, we need routing methods that (i) automatically detect and maintain the state of the network, (ii) compute optimal routes to send messages, and (iii) implement the data flows via these optimal routes.
ORNL researchers are developing solutions to these problems (slides). For more information, contact the Networking Research Group of Computer Science and Mathematics Division.