The two basic tasks of an intermediate node in a packet switched network are[#!Illus!#]: to forward packets, maintaining as far as economically possible, appropriate timing relationship between packets provided that they meet the service contract; and to deliver them along the appropriate route to the destination.
The Internet[#!IP!#][#!TCP!#] has hitherto defined a simple service model that does not offer any definition of the timing model, and it has sufficed to provide a single FIFO queue in a router. In contrast, the path selection mechanisms in the Internet have been rich, typically permitting rapid deployment of new routers, and rapid response to changes in traffic patterns.
This has been achieved by making a hop-by-hop, packet-by-packet, routing lookup. Some people confuse this with a routing decision - in fact, the routing decision is made when a path computation is done, which is typically whenever new routing information is available to each node, and is a management task, that often operates somewhat slower than the route lookup/forwarding decision.
However, to give flexibility, IP packets all contain source and destination information, which permits a choice of route.
Recently, to add further services, the Internet Standards have been enhanced[#!white!#] to provide a signalling protocol, and a family of service models based on the theory in Parekh's work[#!gps1!#][#!gps2!#]. This shows how a Weighted Fair Queueing system can provide bounded delays for variable length packet flows, provided that the traffic is constrained by a leaky bucket, and that an admission test (for the appropriate leaky bucket specification) is carried out at the edge (or at each hop) of the path - this is known as a ``flow specification'', and subsequent packets are matched to the admitted flow by classifying them based on the source, destination and transport level ports (application level multiplexing I-D's). [#!Giga!#] This is the Integrated Services Internet.
There has been some doubt about whether it is possible to build routers fast enough to classify packets according to their flow-spec, and to carry out a WFQ insertion.
In contrast to this, two other hybrid approaches to building a fast Internet have been proposed:
The first approach envisages a network provided (presumably) by telecommunications carriers made up of traditional virtual circuit based packet switches based around either Frame Relay (today) or ATM (tomorrow). Routers would operate between site networks, and act as access devices. Here there is a clear division of slow changing, backbone provisioning, and more rapid changing edge networks - this is not terribly different from todays systems, although there could be more flexible access to differential services from the routers (e.g. interaction between RSVP requests to routers, and router access via say Q.2931 to backbone QoS support).
The second approach is a more integrated approach, attempting to capitalise on the benefits of virtual circuits at one level, and on the flexibility advantages of dynamic IP routing at another. All nodes provide both functions in some manner. There are four main proposals for how to achieve this latter architecture.
The principal performance gain that is expected from all the proponents of these schemes is that the switch designers for ATM capitalises on the fixed size header, with the short VCI/VPI field, that permits simple tables for the lookup for forwarding, and the small fixed size cell, that permits low latency, and jitter, in combining bursty flows for forwarding. Sometimes, there is a mistaken claim that the queue insertion procedure could be faster than for Integrated Services IP - in fact, recent work by Hui Zhang[#!wf2q!#][#!scaleswitch!#] shows that this is not at all the case.
This approach simply uses normal IP routing for forwarding packets, but shreds them, so that the store-and-forwarding latency is much lower.
This is a smart technique for matching a flow of IP packets onto a virtual circuit, dynamically, Essentially, flow characteristics are pre-programmed into a recogniser, which only opens VCs for individual flows that are expected to persist long enough. Short flows are bundled onto a default VC.
All routes from the routing table are used to generate tags, which are then used in the backbone to indicate a VC to follow.
All backbone egress points are used to generate tags which are used to bundle together like minded flows onto a VC.
There are a number of problems with all these hybrid approaches, including: VC setup times; Exhausting VCI/VPI tables; management complexity; difficulty supporting mobility; difficulty supporting multicast (many-to-many); possible lack of fault tolerance.