Pipeline forwarding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Pipeline forwarding (PF) [1] applies to packet forwarding in computer networks the basic concept of pipelining, which has been widely and successfully used in computing — specifically, in the architecture of all major central processing units (CPUs) — and manufacturing — specifically in assembly lines of various industries starting from automotive to many others. Pipelining is known to be optimal independent of the specific instantiation. In particular, PF is optimal from various points of view:

  1. High efficiency in utilization of network resources, which enables accommodating a larger amount of traffic on the network, thus lowering operation cost and being the foundation for accommodating the exponential growth of modern networks.
  2. Low implementation complexity, which enables the realization of larger and more powerful networking systems at low cost, thus offering further support to network growth.
  3. High scalability, which is an immediate consequence of the above two features.
  4. Deterministic and predictable operation with minimum delay and no packet loss even under full load condition, which is key in supporting the demanding requirements of the new and valuable services that are being deployed, or envisioned to be deployed, on modern networks, such as telephony, videoconferencing, virtual presence, video on demand, distributed gaming.

Various aspects of the technology are covered by several patents issued by both the United States Patent and Trademark Office and the European Patent Office.[citation needed]

Operating principles[edit]

As in other pipelining implementations, a common time reference (CTR) is needed to perform pipeline forwarding. In the context of global networks the CTR can be effectively realized by using UTC (coordinated universal time) that is globally available via GPS (global positioning system) or Galileo in the near future. For example, the UTC second is divided into fixed duration time frames, which are grouped into time cycles so that in each UTC second there is a predefined integer number of time cycles. Alternatively, or complementary, the CTR can be obtained through the network by means of synchronization protocols such as IEEE 1588.

Packets are forwarded from node to node according to predefined schedules, as shown in the figure below, i.e., each node forwards packets of a certain flow during predefined time frames. The time cycles define the periodic re-occurrence of the various predefined schedules. The periodic scheduling within each node results in a periodic packet forwarding across the network, which is referred to as pipeline forwarding for the ordered, step-by-step fashion with which packets travel toward their destination.

Pipeline Forwarding Example

Through a resource reservation procedure transmission capacity is booked for a flow on each link it traverses during the time frame (or time frames) predefined for its forwarding, thus setting up a synchronous virtual pipe (SVP). The capacity during each time frame can be is partially or totally reserved to one or more flows. Consequently, the time cycle provides the basis for a periodic repetition of the reservation that ensures enough transmission resources to be available on each link to forward the packets of each flow, which prevents delays due to resource contention and loss resulting to congestion.

Forwarding options[edit]

As exemplified in the figure above, which depicts the journey of a packet from node A to node D along three pipeline forwarding switches, the forwarding delay may have different values for different nodes, due to different propagation delays on different links (e.g., Tab, Tbc, and Tcd), and different packet processing and switching times in heterogeneous nodes (e.g., Tbb and Tcc). Moreover, two variants of the basic pipeline forwarding operation are possible. When node n deploys immediate forwarding the forwarding delay has the same value for all the packets received by node n on input link i and it is the minimum necessary to accommodate the packet propagation, processing, and switching time. When implementing non-immediate forwarding, node n may use different forwarding delays for different packets.

Two implementations of the pipeline forwarding were proposed: Time-Driven Switching (TDS) - a.k.a. Fractional lambda switching (FλS) in the context of optical networks - [2] and time-driven priority (TDP) [3] and can be used to create pipeline forwarding parallel network in the future Internet .[4]

References[edit]

  1. ^ Baldi, M.; Marchetto, G.; Ofek, Y. (2007), "A Scalable Solution for Engineering Streaming Traffic in the Future Internet", Computer Networks (COMNET) 51 (14): 4092–4111, doi:10.1016/j.comnet.2007.04.019 
  2. ^ Baldi, M.; Ofek, Y. (2004), "Fractional Lambda Switching - Principles of Operation and Performance Issues" (PDF), SIMULATION: Transactions of the Society for Modeling and Simulation International 80 (10) 
  3. ^ Li, C.-S.; Ofek, Y.; Yung, M. (1996), "Time-driven priority flow control for real-time heterogeneous internetworking", IEEE Int. Conf. on Computer Communications (INFOCOM 1996) (PDF), IEEE 
  4. ^ Baldi, M.; Ofek, Y. (2009), "Time for a 'Greener' Internet", 1st International Workshop on Green Communications (GreenComm'09) in conjunction with the IEEE International Conference on Communications (IEEE ICC 2009) (PDF), IEEE