Network Working Group P. Kim Internet-Draft Korea Polytechnic University Intended status: Experimental J. Yoon Expires: Jan 2, 2009 H. Kim KT Infra R&D Center July 03, 2008 A Packet Partition Scheduling Mechanism for Bandwidth Aggregation through Multiple Network Interfaces draft-pskim-mext-bagg-scheduling-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of 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 Jan 2, 2009. Copyright Notice Copyright (C) The IETF Trust (2008). Kim et al. Expires Jan 2, 2009 [Page 1] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 Abstract This draft considers a packet partition scheduling mechanism for effective bandwidth aggregation over end-to-end multi-path through multiple network interfaces. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Bandwidth Aggregation . . . . . . . . . . . . . . . . . . . . 3 3. Mechanism Operation . . . . . . . . . . . . . . . . . . . . . 4 3.1 Operation Example . . . . . . . . . . . . . . . . . . . . . . 5 4. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 7 Intellectual Property and Copyright Statements . . . . . . . . . . 8 1. Introduction To access the Internet, today's mobile computers often have more than one network interfaces such as WiBro(802.16e), 3G(GPRS, CDMA2000), WLAN(802.11), Bluetooth, etc. These mobile computers are called "multi-homing capable" because they can connect to multiple networks. In recent, to explain the motivations for mobile nodes using multiple network interfaces and the scenarios where this may end up using multiple global addresses on their interfaces, the multi-homing has been investigated from an end-node point of view not from a site point of view [1]. It is essential for the next generation "wireless" communication devices to seamlessly utilize multiple network interfaces simultaneously to achieve the following: high end-to-end throughput, glitch free communication experience, connectivity in the presence of heterogeneous wireless networks, ability to aggregate bandwidth over multiple network interfaces. On the other hand, a restricting usage to one single interface at a time limits the flexibility available to the end user in making the best use of all available resources on his interfaces. Once multiple network interfaces are offered, users may want to select the most appropriate set of network interface(s) depending on the network environment, particularly in wireless networks which are mutable and less reliable than wired networks. Users may also want to select the most appropriate interface per communication type or to combine a set of interfaces to get sufficient bandwidth or more bandwidth. Kim et al. Expires Jan 2, 2009 [Page 2] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 This draft considers a new wireless communication access paradigm called the "bandwidth aggregation" mechanism which combines a set of interfaces to provide end-to-end multi-path communication in order to improve the end users' communication experience. As shown in [2], in the bandwidth aggregation, the bandwidth offered by the multiple network interfaces can be aggregated to improve quality or support demanding applications that need high bandwidth. Through the bandwidth aggregation, users can accumulate enough bandwidth to meet their exact needs by combining more than one single Internet connection. The bandwidth aggregation scheme consists of two main functional mechanisms; the bandwidth estimation mechanism and the packet partition scheduling mechanism. The bandwidth estimation mechanism has to measure or predict the available bandwidth of an end-to-end path which is its remaining capacity, that is, the amount of traffic that can be sent along the path without congesting it. The packet partition scheduling mechanism has to effectively partition packets on the appropriate end-to-end path through the corresponding network interface. This draft proposes a packet partition scheduling mechanism. In the proposed mechanism, each interface is considered to have a "partition counter" associated with it. This partition counter is used to determine if an interface has enough credits to partition a packet. It is initialized to the quantum which is number of credits in bytes added to the interface. This quantum is determined proportionately to its weighting according to estimated available bandwidths of end-to-end multi-path through multiple network interfaces. It is thus called the "weighted quantum". In this draft, it is assumed that the available bandwidth of end-to-end path can be estimated from existing estimation mechanisms and thus known. 2. Bandwidth Aggregation The bandwidth aggregation is one of multiple access services enabled by simultaneous use of multiple network interfaces and the multi-path communication. In the bandwidth aggregation, the bandwidth offered by the multiple network interfaces can be aggregated to improve quality or support demanding applications that need high bandwidth. The bandwidth aggregation scheme consists of two main mechanisms; the bandwidth estimation mechanism and the packet partition scheduling mechanism. Kim et al. Expires Jan 2, 2009 [Page 3] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 The bandwidth estimation mechanism has to measure or predict the available bandwidth of an end-to-end path which is its remaining capacity, that is, the amount of traffic that can be sent along the path without congesting it. Recently, the area of end-to-end available bandwidth estimation has attracted considerable interest. Basically because the available bandwidth is an important metric for several applications such as overlay networks, dynamic server selection, and inter-domain path monitoring. As a result, several estimation techniques and tools based on active measurements have been developed and thus can be applied for the bandwidth aggregation in the architecture to supporting multi-path communication. The packet partition scheduling mechanism not only has to effectively partition packets on the appropriate end-to-end path through the corresponding network interface, but also minimize delay experienced by packets due to potential reordering caused by varying characteristics (delay, bandwidth, loss) of the multiple paths. Thus, essential to such a packet partition scheduling mechanism is the scheduler that partitions incoming packets to multiple interfaces in consideration of available bandwidth of end-to-end path through corresponding network interface. It is necessary for the scheduler to partition incoming packets in fairness so that the multi-interfaced node can achieve its full bandwidth aggregation potential. 3. Mechanism Operations Consider the multi-interfaced node which effectively aggregates bandwidths of end-to-end multi-path through multiple network interfaces. In the proposed packet partition scheduling mechanism, each interface is considered to have a "partition counter" associated with it. This partition counter is used to determine if an interface has enough credits to partition a packet. It is initialized to the quantum. The quantum is number of credits in bytes added to the interface. In the current mechanism, this quantum is determined proportionately to its weighting according to the estimated available bandwidth of end-to-end path through corresponding interface. It is thus called the "weighted quantum" in this draft. The weighed quantum is operated at the byte level and is added more to the interface with higher weight than that with less weight. The operation procedure is as follows. The scheduler moves on the first interface. The scheduler partitions packets on the current interface when corresponding partition counter is greater than the incoming packet's size. If it is lower, then the partition counter Kim et al. Expires Jan 2, 2009 [Page 4] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 is increased by the weighted quantum and packets are partitioned on the current interface. Then partition counter is decreased by the size of packets being partitioned. If the partition counter is still lower than the packet's size, packets held back until the scheduler moves on the next interface. 3.1 Operation Example In this example, the multi-interfaced node has three network interfaces. These interfaces are called the high (Green), medium (Yellow), low (Red) speed interfaces, respectively. Since this draft focuses on the packet partition scheduling scheme, these interfaces are assumed to have "known" weighted quantum (WQ) 1024, 512, 256 bytes, respectively. That is, available bandwidths for three paths through corresponding interfaces are assumed to have fixed ratio 4:2:1. All partition counters (PCs) for each interface are set with 0. Incoming Packet Queue /> Green IF (WQ : 1024 byte) ------------------ / | Packet / C C B C B D A | -- Partition ----> Yellow IF (WQ : 512 byte) | Scheduler \ ------------------ \ \> Red IF (WQ : 256 byte) Packet Types : A(1024 bytes), B(768 bytes), C(512 byte), D(256 byte) - 1st Round Incoming Packet Queue : C C B C B D A At Green IF, If A > PC(g), then add WQ, thus PC(g)=1024; If A < PC(g), then partition A to Green IF, thus PC(g)=0; Total partitioned packets through Green IF : 1024 bytes Incoming Packet Queue : C C B C B D At Yellow IF If D > PC(y), then add WQ, thus PC(y)=512; If D < PC(y), then partition D to Yellow IF, thus PC(y)=256; Total partitioned packets through Yellow IF : 256 bytes Incoming Packet Queue : C C B C B At Red IF If B > PC(r), then add WQ, thus PC(r)=256; If B > PC(r), then move to Green IF, thus PC(r)=256; Total partitioned packets through Red IF : 0 bytes Kim et al. Expires Jan 2, 2009 [Page 5] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 - 2nd Round Incoming Packet Queue : C C B C B At Green IF If B > PC(g), then add WQ, thus PC(g)=1024; If B < PC(g), then partition A to Green IF, thus PC(g)=256; Total partitioned packets through Green IF : 1792 bytes Incoming Packet Queue : C C B C At Yellow IF If C > PC(y), then add WQ, thus PC(y)=768; If D < PC(y), then partition C to Yellow IF, thus PC(y)=256; Total partitioned packets through Yellow IF : 768 bytes Incoming Packet Queue : C C B At Red IF If B > PC(r), then add WQ, thus PC(r)=512; If B > PC(r), then move to Red IF, thus PC(r)=512; Total partitioned packets through Red IF : 0 bytes - 3nd Round Incoming Packet Queue : C C B At Green IF If B > PC(g), then add WQ, thus PC(g) = 1280; If B < PC(g), then partition B to Green IF, thus PC(g)=512; Total partitioned packets through Green IF : 2560 bytes Incoming Packet Queue : C C At Yellow IF If C > PC(y), then add WQ, thus PC(y)=768; If C < PC(y), then partition C to Yellow IF, thus PC(y)=256; Total partitioned packets through Yellow IF : 1280 bytes Incoming Packet Queue : C At Red IF If C < PC(r), then partition C to Red IF, thus PC(r)=0; Total partitioned packets through Red IF : 512 bytes The above operation procedure is repeated when there are incoming packets. Through computer simulations, the proposed packet partition scheduling mechanism has been verified for the multi-path communication with three network interfaces. As mentioned before, available bandwidths for three paths through corresponding interfaces are assumed to have fixed ratio 4:2:1, which determines weighted quantum for each interface. To make a clearer verification, 30 simulations are performed and each simulation generates randomly 100 packets with four kinds of packet type with different sizes such as 256, 512, 768, 1024 bytes. The average Kim et al. Expires Jan 2, 2009 [Page 6] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 ratio of partitioned packets for each interface is shown to be 4.05:1.97:1. This result shows that the proposed mechanism can partition well randomly incoming packets for the multi-path communication. 4. References 4.1. Informative references [1] Ernst, T. et al, "Motivations and Scenarios for Using Multiple Interfaces and Global Addresses", draft-ietf-monami6-multihoming-motivation-scenario-03 (work in progress), November. [2] Krueger, M. et al, "Small Computer Systems Interface protocol over the Internet (iSCSI) Requirements and Design Considerations", RFC 3347, July 2002. Authors' Addresses Pyungsoo Kim Department of Electronics Engineering, Korea Polytechnic University, 2121 Jungwang-Dong, Shiheung City, Gyeonggi-Do 429-793 KOREA Phone: +82 31 8041 0489 EMail: pskim@kpu.ac.kr Joo-Young Yoon Infra Lab., KT 17 Woomyeon-dong, Seocho-gu Seoul, 137-792 KOREA Phone: +82 2 526 6244 Email: jyyoon@kt.com Han-Lim Kim Infra Lab., KT 17 Woomyeon-dong, Seocho-gu Seoul, 137-792 KOREA Phone: +82 2 526 6189 Email: nangel@kt.com Kim et al. Expires Jan 2, 2009 [Page 7] Internet-Draft A Packet Partition Scheduling Mechanism July 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Kim et al. Expires Jan 2, 2009 [Page 8]