Working Group Name Mingwei Xu Internet Draft Chunmei Xia Intended status: Informational Tsinghua University Expires: March 8,2013 September 10, 2012 RRCP:A Receiver-Driven and Router-Feedback Congestion Control Protocol for ICN draft-xu-rrcp-00.txt Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on March 8,2009. Xu, et al Expires March 8,2013 [Page 1] Internet-Draft draft-xu-rrcp-00 September 2012 Copyright Notice Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Abstract Currently, Information-Centric networking (ICN) becomes the hot spot to meet the new requirements accessing a large amount information through networks. ICN exists congestion which isn't well solved. The congestion control protocols in IP network aren't suitable for ICN transport, so we provide a new congestion control protocol-RRCP. RRCP based on XCP and ICN transport characteristics raises a receiver-driven, router-feedback, multi-request windows and timeout mechanisms. RRCP shows efficient, fair and stable via simulation results. Table of Contents 1. Introduction ................................................ 3 2. ICN Transport ............................................... 7 3. RRCP Design ................................................. 8 3.1. RRCP Framework ......................................... 8 3.2. The Congestion Header................................... 9 3.3. The RRCP Sender........................................ 10 3.4. The RRCP Receiver...................................... 10 3.5. The RRCP Router........................................ 10 3.5.1. The Efficiency Controller(EC) .....................11 3.5.2. The Fairness Controller(FC) .......................11 3.6. Timeout Mechanism...................................... 12 4. Security Considerations..................................... 12 5. IANA Considerations ........................................ 12 6. Conclusions ................................................ 12 7. References ................................................. 13 8. Acknowledgments ............................................ 14 Xu, et al Expires March 8,2013 [Page 2] Internet-Draft draft-xu-rrcp-00 September 2012 1. Introduction Network requirements are evolved from data communications between two hosts to accessing a large amount of information through networks, which gives a new challenge to the current address-centric network architecture. Under the requirements based on accessing a large amount of information, the users show concern for the contents, not for the hosts' addresses. The current address-centric network has no high efficiency and produces a lot of redundant datum due to not suitable for the requirement. Given this fact, Information- Centric networking (ICN) becomes the hot spot to meet the new requirements. Currently, some ICN schemes are advanced, such as CCN[1],NetInf[2,3], DONA[4]. These schemes give a preliminary research on the framework, but don't discuss some details such as the routing optimization algorithm, troubleshooting algorithm and congestion control protocol. This draft mainly discusses the congestion control protocol. As we all know, the congestion in IP is composed of two parts. One is the terminal congestion. Because the sending rate is higher than the receiving rate, the receiver can't handle the input packages in time. This leads to package losses. The other is the network congestion. When the handling rate of router is lower than the sending rate, this will lead the input queue in routers to overflow so that the package drops and RTT becomes longer. ICN still exists the congestion. The congestion in ICN is slightly different from that in IP. Because ICN is pull based transport where when the receiver sends a request, the sender responds a data, the terminal congestion doesn't appear in ICN. ICN routes the packages based on the information name. When the forwarding rate of router is lower than the input rate of the packages, the input queue will overflow after a long time. This obviously leads to the input packages?losses and the network congestion. For example, Fig.1 shows a topology. Because the Router2 which has three input and one output only deals with one input package each time , the other two input packages is put into the input queue. Every time the Router2 stores two packages into the input queue, after a long time, the input queue will overflow. At this time, the Router2 can't receive the new input package and only drops them so that the network congestion appears. In Fig.1, the link between Router1 and Router2 is a bottleneck. Xu, et al Expires March 8,2013 [Page 3] Internet-Draft draft-xu-rrcp-00 September 2012 +---+ +---+ | |---------- ----------| | +---+ | | +---+ Receiver1 | | Sender1 +---+ +---+ +---+ +---+ | |---------| |--------| |--------| | +---+ +---+ +---+ +---+ Receiver2 Router1 Router2 Sender2 +---+ | | +---+ | |----------- ----------| | +---+ +---+ Receiver3 Sender3 Figure 1 an example of congestion in ICN We must provide the appropriate congestion control protocol for ICN congestion. There are many congestion control protocols in IP network such as TCP Tahoe[5], TCP Reno[6], TCP NewReno[7], TCP Sack[8], TCP Vegas[9], XCP[10]. Unlike other congestion control protocols, XCP is a feedback protocol. Since ICN transport is different from IP transport, all congestion control protocols in IP network can't directly be applied to ICN. Firstly, ICN is pull based transport. When the receiver sends a request, the sender gives a response. The sender in ICN doesn't know who will request the data and what it will request in the next time. Accordingly, the transport driver in ICN is the receiver. The congestion control protocols in IP network are sender-driven, so aren't suitable for the transport based on pull. Secondly, the intermediate routers in ICN have caches which might become the unpredictable sources. ICN deploys caches which store the contents of the information for increasing the transport efficiency. When Interest package passes it, the intermediate router looks up the cache at first. If cache has the responding data, the Data package is returned directly from the router. The Interest package needn't be sent to the original source. However, the datum in cache change continuously. The changes make the cache become an unpredictable source. This increases the complexity of the design of congestion control protocol. The above congestion control protocols are designed for IP network. The IP network has no cache in the intermediate routers, so the design of the congestion control protocols for IP network doesn't consider the unpredictable sources. The protocols aren't suitable for ICN. Xu, et al Expires March 8,2013 [Page 4] Internet-Draft draft-xu-rrcp-00 September 2012 Finally, ICN sends a request from the host to the network, not from the host to the host. The receiver requests the data, whileas the router selects the information source according to the information's name, so the receiver doesn't know where the information sources are. That is to say, the receiver doesn't know the transport channel in the beginning because the information sources are decided by the router. Still using Fig.1 as an example, assume Receiver1 to send Interest(D1) package where D1 is the requested information's name. When requesting the information, the receiver doesn't know where the information sources are and how to arrive at the information sources. When the Router1 receives the Interest package, Router1 knows the three information sources Sender1, Sender2 and Sender3, then Router1 selects one source or more sources to download the data according to the routing policy. During the download, the intermediate routers Router1 and Router2 cache the information. The caches might become the next information source for the same request. In the process, the Receiver1 only waits for the returned data and doesn't know which the datum come from. However, after a response, the receiver will know the situation about the information sources and the split requests via some returned label. We may add the label field, such as requestID, to identify the channels and information sources. The congestion control protocols in IP network only design for the transport with a channel per a request, not for the transport with multiple channels per a request. According, the current congestion control protocols of IP network aren't suitable for ICN. We should study a new protocol or modify the current protocols to satisfy the ICN transport. At present, the congestion control mechanism in ICN is already discussed, such as ConTug[11], RDITP[12]. These schemes advance different congestion control mechanisms for different schemes. ConTug based on TCP provides a receiver-driven congestion control mechanism. Due to the apparent unpredictability of cache sources, ConTug raises a multi-window mechanism which allocates multiple windows according to the information source. Since ICN uses pull based transport model where the senders transmit the packages passively, ConTug suggests the receiver-driven transport mechanism. Based on an identified segment source, ConTug defines a split window which implements TCP protocol, The general window is a sum of all split windows. RDITP also provides a receiver-driven congestion control mechanism which is similar with TCP. The two schemes based on TCP and the ICN transport features don't decouple utilization control from fairness control. This leads to each other's influence so that efficiency and fairness can't achieve the best. The two schemes start handling the unpredictable cache sources after a rtt. The reaction rate is slow. When adding a window for the source, the source may disappear. The lagging handle leads to error. In Xu, et al Expires March 8,2013 [Page 5] Internet-Draft draft-xu-rrcp-00 September 2012 addition, given a cache source, ConTug will create a new window, this increases the complexity of the system. The slow start in the two schemes has a low utilization for the high bandwidth-delay network which will be common in ICN core. If a package is lost during slow start, the two schemes drop into AIMD which has worse utilization than slow start. For example, given a transport where link bandwidth is 10Gb/s, RTT is 200ms and the payload is 1460B, and assuming no loss during the transport, the link utilization in slow start is 8.5%. This value isn't very good. Moreover, the window's oscillation between initial value and the maximum value leads to bad stability. This draft advances a congestion control protocol RRCP which is suitable for ICN. RRCP based on XCP and ICN's transport characteristics remains high efficiency, fairness and stability. Due to ICN's pull based transport, RRCP still uses receiver-driven pattern. In the intermediate routers ICN has cache which is an unpredictable information source whose contents change continuously according to the policy. We design a router-feedback mechanism for the unpredictable cache sources. The feedback value and location are set according to the cache, spare bandwidth, queue and flow. ICN supports the multi-source concurrent distribution for a request. In RRCP, we needn't create a new window for each channel, because we adopt the feedback mechanism. We need only create a new window for each Interest package. If an Interest package is divided into multiple Interest packages for the multi-source distribution, RRCP will start a new window for each Interest package. The receiver can know how to separate the Interest package via the returned Data packages and start the responding windows. In RRCP, Each window independently implements transport control. The general window is a sum of all split windows for all split requests. In RRCP, the routers deploy fairness controller and efficiency controller which compute the feedback. We decouple utilization control from fairness control. This allows a more flexible and analytically tractable protocol design. The feedback is put into the new defined congestion header instead of the router. This ensures stateless in the intermediate router and shows good scalability. In RRCP, we adopt the feedback mechanism because the feedback mechanism accurately reflects the real change of the network. When there is the unpredictable cache in the channel, the Data package is returned directly from the router with the cache source. The routers receiving the Data package compute the new feedback and put the feedback into the congestion header of the Data package. The feedback is a totalized value of feedbacks of all routers along the path. If the path is changed, the feedback will change. So the feedback can show not only the change of the flows, but also the change of the channel. Accordingly, a uncertain cache source brings Xu, et al Expires March 8,2013 [Page 6] Internet-Draft draft-xu-rrcp-00 September 2012 about the change of the channel, while the change of the channel will bring about the change of the feedback. The feedback mechanism can quickly reflect the channel's change so that it is suitable for ICN with the unpredictable cache source. RRCP may solve the following problems: a) RRCP is suitable for pull based ICN. b) RRCP solves multi-channel transport modal. c) RRCP distinguishs error losses from congestion losses and solves the drops roughly by the timeout mechanism. d) RRCP solves the unpredictable cache sources. e) RRCP ensures the fairness and efficiency simultaneously. 2. ICN Transport 1) Because ICN often uses multi-source distribution, the information is responded to a receiver via multiple channels. ICN often uses the multi-source distribution algorithm for higher transport efficiency. The main idea of this algorithm is responding different data blocks of the information to the receiver from multiple sources at the same time. In the multi-source transport mechanism, the routers select the information sources and divide the Interest package for the information into several Interest packages for different blocks of information. These split Interest packages are sent to the different information sources via the different channels so that the sources can respond to the different parts of information to the receiver. The receiver reconstructs the blocks into the complete information. Accordingly, in the multi-source transport, a request package will be divided into several request packages. Each request has a window to control the channel's transport. We should independently consider the congestion control of each request. Otherwise, this will lead to disturb each other and increase the complexity of the congestion control protocol. 2) The intermediate nodes have caches which store the information in ICN. The datum in the caches change continuously over time. This will lead to unpredictable sources which bring uncertainty for information transport. Adding the cache into the routing is the apparent feature in ICN. The cache makes a tradeoff between storage costs and transport efficiency. It is proved by the practice and theory that the caches bring higher efficiency and less resources' use. But the cache also leads to the complexity of the congestion control protocol. During Xu, et al Expires March 8,2013 [Page 7] Internet-Draft draft-xu-rrcp-00 September 2012 the transport process, the channel might change at any time due to the cache. TCP is hard to adapt to the change. We should advance a sensitive congestion control protocol for the unpredictability of cache sources. 3) ICN uses pull based transport. The information sources passively respond to the receiver. The current IP network uses push based transport, the sender proactively sends the datum to the receiver. In ICN, a receiver pulls the datum from the network, not a single server. The source doesn't know who requests the datum and which data is requested in the next time. Accordingly, the resulting congestion control protocol is necessarily receiver-driven. Given the upper facts, we should design the congestion control protocol for each feature. The resulting congestion control protocol is necessarily suitable for ICN. 3. RRCP Design In the congestion control protocol, timeout and drops become a sign of congestion. In fact, the timeout and drops are a necessary condition of congestion, not a sufficient condition. In the congestion control protocol, we should consider a true feedback selecting congestion losses or error losses. This draft provides a receiver-driven router-feedback congestion control protocol-RRCP. RRCP based on XCP and the ICN transport features remains efficiency, fairness and stability. 3.1. RRCP Framework Fig. 2 shows the RRCP framework. Firstly, we design the multi- window mechanism for the multi-request transport in ICN. In this mechanism, each request i sets a congestion control window cwndi. The receiver sends the request packages according to cwndi. We uses cwndi to control the transport of the channel of the request i and avoid congestion of the channel. Secondly, ICN is pull based transport. Accordingly, RRCP controls congestion window via the receiver. The receiver sends Interest according to window, while the sender gives a response according to the Interest's rate. We adopts receiver-driven to control transport and avoid congestion. At last, we address a router-feedback mechanism for the changing cache sources. In the router, we set the efficiency controller and fairness controller which compute the spare bandwidth and the feedback per flow regularly. When the Data packages return, the feedback is put into the congestion header of Data package. In each Xu, et al Expires March 8,2013 [Page 8] Internet-Draft draft-xu-rrcp-00 September 2012 router along the path, the feedback is recalculated until the Data package returns the receiver. The resulting feedback is an accumulated value. The router-feedback mechanism may precisely show the congestion of network and select the feedback location based on the cache sources so that it can handle the unpredictability of the cache sources in ICN. Data package with feedback <------------------------------------------ +---+ +---+ -------| |-------------- | |---------------- | +---+ +---+ Channel1 router router | -----------------------------------------> +---+ Interest package | | . +---+ . receiver . Data package with feedback | <------------------------------------------ Channeln +---+ +---+ --------| |---------------| |---------------- +---+ +---+ router router ------------------------------------------> Interest package Figure 2 RRCP framework 3.2. The Congestion Header In RRCP, the feedback is put into the congestion header, not the router. Fig. 3 defines the congestion header. The field H_cwnd is the general congestion window, whileas H_cwndi is the congestion window of the request i. The field rtti is the rtt of the channel of request i, whileas requestID is the ID of the request. These fields are filled by the receiver and never modified in transit. The remaining field, H_feedback, is the feedback of the router. The data is a totalized value. The initial value is provided by the receiver, while the routers along the path modify the value to directly control congestion window of the receiver. Xu, et al Expires March 8,2013 [Page 9] Internet-Draft draft-xu-rrcp-00 September 2012 +-------------------+ | H_cwnd | +-------------------+ | H_cwndi | +-------------------+ | H_rtti | +-------------------+ | RequestID | +-------------------+ | H_feedback | +-------------------+ Figure 3 The congestion header 3.3. The RRCP Sender In RRCP, since we adopt the receiver-driven congestion control, the sender isn't the driver of the congestion control. The RRCP sender is similar to a TCP receiver except that it copies the congestion header from Interest package to Data package. What's more, in ICN, cache might uncertainly give a response to the receiver as an information source. In RRCP, due to the precise feedback, the routers along the path give a feedback when Data package returns from cache. During the process, a new channel's congestion control is naturally formed between the receiver and the cache source. 3.4. The RRCP Receiver The receiver controls the transport rate of network as a driver of congestion control in RRCP. In the beginning, the receiver doesn't know how to divide the Interest package. The fields H_cwndi, H_rtti, and RequestID are not filled. After several responses, the receiver knows the division of Interest package. When the receiver knows the n requests, it set the field requestID from 1 to n, then, it splits H_cwnd into n H_cwndi and set the initial values for each H_cwndi and H_rtti. After a rtt, H_cwndi and H_rtti are set to true values, the two values isn't modified during the transport. When the receiver gets the new feedback, it recalculates H_cwndi and H_rtti. If the feedback is positive, H_cwndiis increased. If the feedback is negative, H_cwndi is decreased. H_cwnd is a sum of all H_cwndi. 3.5. The RRCP Router In RRCP, the job of the router is to compute the feedback to cause the system to converge to optimal efficiency and min-max fairness. Xu, et al Expires March 8,2013 [Page 10] Internet-Draft draft-xu-rrcp-00 September 2012 We set the efficiency controller and the fairness controller in the router and decouple efficiency control from fairness control. The efficiency controller computes aggregate traffic and uses MIMD. The fairness controller uses AIMD and computes the feedback per flow. The efficiency control and the fairness control independently handle the flow in order to get the best utilization and fairness. The router computes the feedback per average RTT. Estimating the feedback over intervals longer than average RTT leads to sluggish response, while estimating the feedback over shorter intervals leads to erroneous estimates. 3.5.1. The Efficiency Controller(EC) EC computes the spare aggregate traffic to ensure the maximum link utilization. The spare aggregate traffic is associated with the spare bandwidth, the queue size. In the average RTT's interval, the aggregate feedback F is increased when the spare bandwidth is increased, while the aggregate feedback F is decreased when the persistent queue size is increased. We may judge if network is congested via F. If F>0, the network is underutilized and the resource of the router is spare. At this time, the receiver may increase the requests' frequency to utilize the spare traffic as much as possible. Eventually, network transport efficiency is increased. If F<0, the network is congested. The congestion window is decreased due to negative feedback. This decreases the resource utilization, then, relieves the network congestion. Generally speaking, because RRCP is a feedback mechanism, the stable spot should remain close to the cliff of curve, not over the cliff. Thus, RRCP doesn't drop packages. In this draft, we raise timeout mechanism to solve the drops seldom appeared. 3.5.2. The Fairness Controller(FC) FC considers the fairness of each flow. The purpose of EC is to maximum the spare resource's utilization, while FC allocates the spare resource to each flow. FC ensures min-max fairness. Thus, we compute the per-flow feedback according to the policy: If F>0, allocate it so that the increase in throughput of all flows is the same. If F<0, allocate it so that the decrease in throughput of a flow is proportional to its current throughput. For example, if flow 1 accounts for 0.4 of all flows, the feedback is 0.4*F. When F = 0, the system is stable, then, the feedback is always 0. This may result in convergence stalling. We still use the bandwidth shuffling to defend convergence stalling. The bandwidth of 10% are Xu, et al Expires March 8,2013 [Page 11] Internet-Draft draft-xu-rrcp-00 September 2012 simultaneously allocated and deallocated so that the total traffic rate doesn't change. 3.6. Timeout Mechanism RRCP seldom drops packages, but if the network shows the drops, we provide the timeout handling mechanism. If the network has losses, the receiver sets the congestion window a half to relieve the network congestion and control the losses. When the congestion is relieved after a RTT or several RTTs, the routers will return the new feedback. Then, the network enters the state of a new feedback. If the network shows losses over the timeout, the router will forward the same Interest, while in the timeout, the router will drop the same Interest which is repeated forwarding. Dropping the repeated Interest defends the loop. RRCP as a feedback mechanism may differentiate the dropping cause. If the feedback is positive, the network is fluent. At this time dropping packages is resulted from the error. If the feedback is negative, the network is congested. At this time dropping packages is resulted from the congestion. RRCP uses the feedback to distinguish the erroneous losses from the congested losses, this solves that all losses are handled by the timeout. 4. Security Considerations Security considerations to be provided. 5. IANA Considerations This document requires the allocation of one protocol number by the IANA. This document requires that IANA will maintain the registry of ICNnamespaces. 6. Conclusions ICN exists congestion which isn't well solved. The existing congestion control protocols in IP network aren't suitable for ICN transport. Accordingly, we must study a novel protocol or modify a current protocol to control the congestion in ICN. In this draft, we advance a congestion control protocol-RRCP for ICN transport. RRCP based on XCP and ICN transport features raises the receiver- driven, router-feedback, and multi-window mechanisms. We design the timeout mechanism for ensuring RRCP work normally under the scenarios of drops. Xu, et al Expires March 8,2013 [Page 12] Internet-Draft draft-xu-rrcp-00 September 2012 7. References [1] Van Jacobson, Diana K.Smetters, James D. Thornton, Michael F. Plass, Nicholas H. Briggs, Rebecca L. Braynard. Networking Named Content. CoNEXT'09, December 1-4, 2009. [2] BengtAhlgren, MatteoD'Ambrosio, Christian Dannewitz, Marco Marchisio, Ian Marsh, BorjeOhlman, Design Considerations for a Network of Information, ReArch'08, December 9, 2008. [3] BojeOhlman, BengtAhlgren, Marcus Brunner and etc. First NetInf architecture description, FP7-ICT-2007-1-216041-4WARD / D-6.1, April 1,2009. [4] TeemuKoponen, MohitChawla, Byung-Gon Chun, AndreyErmolinskiy, Kye Hyun Kim, Scott Shenker, Ion Stoica, A Data-Oriented (and Beyond) Network Architecture. SIGCOMM'07, August 27-31, 2007. [5] Postel, J. (ed.), "Transmission Control Protocol -DARPA Internet Program Protocol Specification", RFC 793, Information Sciences Institute/USC, September 1981. [6] W. Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001, Jan. 1997. [7] S. Floyd and T. Henderson. The NewRenoModification to TCP's Fast Recovery Algorithm. RFC2582, April 1999. [8] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. TCP Selective Acknowledgment Options. RFC 2018, October 1996. [9] L. Brakmo, S. O'Malley, and L. Peterson. TCP Vegas: New techniques for congestion detection and avoidance. In Proceedings of ACM SIGCOMM 1994. [10] Dina Katabi, Mark Handley, and Charlie Rohrs. Congestion Control for High Bandwidth-Delay Product Networks, In: Proceedings on ACM Sigcomm2002. [11] Arianfar, S., Eggert, L., Nikander, P., Ott, J., and Wong, W. Contug: A receiver-driven transport protocol for content- centric networks. Under submission, 2010. [12] S. Salsano, A. Detti, Receiver driven trasport protocol for CONET ICN, draft-salsano-rditp-00, Internet Draft, http://tools.ietf.org/id/draft-salsano-rditp-00.txt. Xu, et al Expires March 8,2013 [Page 13] Internet-Draft draft-xu-rrcp-00 September 2012 8. Acknowledgments The authors thank to the funding supports of the CERNET, CNGI- CERNET2, CNGI Research and Development, China "863" and China "973"projects. Xu, et al Expires March 8,2013 [Page 14] Internet-Draft draft-xu-rrcp-00 September 2012 Authors' Addresses Mingwei Xu Dept. of Comp Sci. & Tech., Tsinghua University ROOM4-104, FIT Building, Tsinghua University Beijing 100084 CN Email: xmw@cernet.edu.cn Chunmei Xia Dept. of Comp Sci. & Tech., Tsinghua University ROOM9-402, East Main Building, Tsinghua University Beijing 100084 CN Email: xcm19770312@sina.cn Xu, et al Expires March 9,2013 [Page 15]