Network Working Group XingWei. Wang Internet-Draft XiuShuang. Yi Intended status: Standards Track Yu. Wang Expires: May 21, 2010 Ming. Dong Qiang. Chen NEU November 17, 2009 Self-organizing network model draft-xwwang-sonnetworkmodel-02.txt Abstract In this paper, a swarm intelligence based self-organizing network model was introduced to network providers. The problems of the existing network as well as the characteristics of the NGI (Next Generation Internet) were described to illustrate the motivation of the proposed self-organizing network model. A network architecture model based on swarm intelligence was introduced, the used technical terms was defined. The network parameters, network behaviors and node stability under the proposed model were described. Especially, some important QoS routing elements under the proposed model, such as the user QoS routing requirements, link satisfaction degree, utility computation, unicast path and multicast tree evaluation, mathematical model of QoS route optimization and small-world behaviors, were introduced. Status of this Memo This Internet-Draft is submitted to IETF 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. Wang, et al. Expires May 21, 2010 [Page 1] Internet-Draft Self-organizing network model November 2009 This Internet-Draft will expire on May 21, 2010. Copyright Notice Copyright (c) 2009 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 BSD License. Wang, et al. Expires May 21, 2010 [Page 2] Internet-Draft Self-organizing network model November 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Term . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Motives and existent problems . . . . . . . . . . . . . . . . 8 5. Related issues . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Swarm Intelligence . . . . . . . . . . . . . . . . . . . . 10 5.2. QoS Routing . . . . . . . . . . . . . . . . . . . . . . . 12 6. Self-organizing Network Design Paradigm . . . . . . . . . . . 15 6.1. DESIGN LOCAL BEHAVIOR RULES THAT ACHIEVE GLOBAL PROPERTIES . . . . . . . . . . . . . . . . . . . . . . . . 15 6.2. EXPLOIT IMPLICIT COORDINATION . . . . . . . . . . . . . . 15 6.3. MINIMIZE LONG-LIVED STATE INFORMATION . . . . . . . . . . 15 6.4. DESIGN PROTOCOLS THAT ADAPT TO CHANGES . . . . . . . . . . 15 7. Network Model . . . . . . . . . . . . . . . . . . . . . . . . 17 7.1. Network Parameters . . . . . . . . . . . . . . . . . . . . 17 7.2. Network Self-organization Behavior Design . . . . . . . . 17 7.3. Node Stability Degree . . . . . . . . . . . . . . . . . . 20 8. Routing Request . . . . . . . . . . . . . . . . . . . . . . . 23 8.1. User QoS Unicast Routing Request . . . . . . . . . . . . . 23 8.2. User QoS Multicast Routing Request . . . . . . . . . . . . 23 9. Link QoS Evaluation . . . . . . . . . . . . . . . . . . . . . 24 9.1. Link Parameter Membership Degree . . . . . . . . . . . . . 24 9.2. QoS Satisfaction Degree . . . . . . . . . . . . . . . . . 25 9.3. Link QoS Evaluation . . . . . . . . . . . . . . . . . . . 27 10. Utility Calculation and Gaming Analysis . . . . . . . . . . . 28 10.1. Cost and Price . . . . . . . . . . . . . . . . . . . . . . 28 10.2. Utility . . . . . . . . . . . . . . . . . . . . . . . . . 30 10.3. Gaming . . . . . . . . . . . . . . . . . . . . . . . . . . 30 11. Unicast Path and Multicast Tree Evaluation . . . . . . . . . . 32 12. Mathematical Model . . . . . . . . . . . . . . . . . . . . . . 33 12.1. Unicast Mathematical Model . . . . . . . . . . . . . . . . 33 12.2. Multicast Mathematics Model . . . . . . . . . . . . . . . 33 13. Small World Behavior . . . . . . . . . . . . . . . . . . . . . 35 14. Route Strategies . . . . . . . . . . . . . . . . . . . . . . . 39 15. Security Considerations . . . . . . . . . . . . . . . . . . . 40 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41 17. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 42 Appendix A. References . . . . . . . . . . . . . . . . . . . . . 43 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 45 Wang, et al. Expires May 21, 2010 [Page 3] Internet-Draft Self-organizing network model November 2009 1. Introduction In this paper, a swarm intelligence based self-organizing network model was introduced to network providers. The problems of the existing network as well as the characteristics of the NGI (Next Generation Internet) were described to illustrate the motivation of the proposed self-organizing network model. A network architecture model based on swarm intelligence was introduced, the used technical terms was defined. The network parameters, network behaviors and node stability under the proposed model were described. Especially, some important QoS routing elements under the proposed model, such as the user QoS routing requirements, link satisfaction degree, utility computation, unicast path and multicast tree evaluation, mathematical model of QoS route optimization and small-world behaviors, were introduced. Wang, et al. Expires May 21, 2010 [Page 4] Internet-Draft Self-organizing network model November 2009 2. Requirements The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in thisdocument are to be interpreted as described in RFC 2119 . Wang, et al. Expires May 21, 2010 [Page 5] Internet-Draft Self-organizing network model November 2009 3. Term The used terms in this document are defined as follows. Pay attention: because they may have other definitions out of the self- organizing network, these terms only have the defined specific meaning in this document, thus not universal. Self-organization originated from simply local interaction between entities, possessing system-wide adaptive structure and function emergence. Swarm intelligence referring to the characteristics of the advanced intelligent behavior generations by cooperation among simple individuals. Router referring to the smart routing node with the characteristics of the biological behaviors and the capabilities of packet forwarding and processing. Link referring to the communication media providing interconnections among routers and end systems. QoS referring to the aggregated effect of the service performance, reflecting the user satisfaction degree on the service. It can be described by a set of parameters, such as bandwidth, delay, delay jitter and error rate. Bandwidth referring to the amount of the transferred data per unit time, that is, the data transferring capability of the link. In this paper, the overall bandwidth and the available bandwidth of the link are considered. Delay referring to the elapsed time by transferring packet from one place to another. Delay-Jitter Wang, et al. Expires May 21, 2010 [Page 6] Internet-Draft Self-organizing network model November 2009 referring to the difference between the maximum and the minimum of the delay for transferring packet from one place to another. Error Rate referring to the ratio of the amount of the corrupted data to the total amount of the transferred data. It has nothing to do with the service type and only have relations with the link type and the current network status. Node stability referring to the degree of the node status remaining relatively invariable. The nodes with stronger stabilities are preferred when routing. User requirements referring to the demand of the user on the network QoS. They are described fuzzily with intervals. Satisfaction degree of the user to the link referring to the satisfaction degree of the user to the QoS provided by his used link. Cost referring to the expense of the consumed resources when the network provider offered the service to the user. Pricing referring to the network service price charged by the network provider to the user. Small world edges referring to the frequently used paths when a pair of nodes communicated. They are so-called preferred 'short-cut' when routing. Wang, et al. Expires May 21, 2010 [Page 7] Internet-Draft Self-organizing network model November 2009 4. Motives and existent problems With the growing network scale and the increasing network dynamics, there exist huge challenges to the existing network models and routing schemes. The expanded scale asks the network to possess the strong self-organizing and self-management capabilities at the same time the highly dynamics desires the distributed and adaptive routing without network-wide global information. With the convergence of various networking technologies, numerous computers, mobile terminals, and sensors around the world are connected to the Internet with a variety of fixed, mobile, wireless, optical and other broadband internet access scheme, making the network scale grow continuously. At the same time, network applications are becoming pervasive around individuals, homes, offices, vehicles, buildings and wider areas. All these have increased the time and space complexities of the network topologies and dynamics dramatically, thus aggravated the management burdens of the network administrators even and the users. In order to help them get rid of the complex network management works and minimize the network administration staff, the so-called self-organizing network should be designed and developed. Self-organizing phenomenon is prevalent in our lives and around the world. In the natural world, fish swarms with good structures swims in the seas and rivers, ant colonies find their food along the shortest route. Such these are good examples of self-organizing behaviors. In fact, all participating entities establish an organizational structure without a coordination center when self- organizing. Instead, these entities interact directly and react to changes in their local environment continuously. Self-organizing does not just mean distributed and localized control; in fact, it is also the results of structures and functionalities of the independent individuals and the relationships among them. In the self-organizing systems, the simple actions of these individuals at microscope level can lead to the complex behaviors system-wide. This kind of phenomenon is known as the "emerging". Another important feature of self-organizing system is its adaptation to its environmental changes. In fact, it continuously adapts to changes implicitly. For example, it often makes restructuring to react to its internal or external changes. By doing so, it tries to converge to the desired good structure and avoid the bad one. Combining its inherent properties of adaptation and distribution, the self-organizing system will be robust to failures and corruptions. There does not exist single failure point and it can self-repair and self-correct errors without external help. Therefore, it will not Wang, et al. Expires May 21, 2010 [Page 8] Internet-Draft Self-organizing network model November 2009 collapse suddenly; when some problems occurred, it still runs with degraded performance. At present, the complexity of the communications network has become an increasingly serious problem. Recent progresses of the self- organizing system are indicating that some answers may be found to this problem. Self-organizing network model is based on the building up characteristics and behaviors of self-organizing. In this paper, a network model with characteristics and behaviors of the self- organizing system is established and called self-organizing network model. Wang, et al. Expires May 21, 2010 [Page 9] Internet-Draft Self-organizing network model November 2009 5. Related issues Routing is important in the network. With the expansion of the network scale and emergence of multimedia and real-time services, the user requirements on QoS (Quality of Service) become higher and higher, and QoS routing with various performance parameters considered is becoming one essential issue to be handled in any network model. Due to strong self-organizing feature inherent in swarm intelligence, the swarm intelligence based algorithms and strategies can be used to solve QoS routing under the self-organizing network environment. Thus, some basic knowledge on swarm intelligence and QoS routing are introduced at first before the proposed self-organizing network model is described. 5.1. Swarm Intelligence Swarm intelligence refers to the generation of complex intelligent behavior through cooperation among simple individuals. A significant milestone to indicate that the concept of swarm intelligence was formally put forward was the publication by Oxford University Press in 1999 of the monograph named "Swarm Intelligence: From Natural to Artificial System" authored by E Bonabeau, M Dorigo and others. The concept of swarm intelligence comes from the observations on the behaviors of some kinds of insects in the natural world, such as ants and bees. One single ant's intelligence is not high, however, if a few ants come together, they can convey the foods to their nests, which they found on the road. If there is a crowd of ants, they can work together to build a strong and beautiful nest, to resist the external threatens，and to multiply and bring-up their offspring. This kind of intelligent behaviors emerged from such social living beings are known as the swarm intelligence. For swarm intelligence, the following five basic principles should be obeyed: Proximity Principle: Swarm can carry out simple calculation on space and time. Quality Principle: Swarm is able to respond to the quality factors in its environment. Wang, et al. Expires May 21, 2010 [Page 10] Internet-Draft Self-organizing network model November 2009 Principle of Diverse Response: The acting scope of the swarm should not be too narrow. Stability Principle: Swarm should not change their behavior whenever its environment changes. Adaptability Principle: Swarm can change its behavior in due situation in case of not too high cost incurred. Swarm intelligence has following characteristics: Control is distributed without any center. It can adapt to the current network status more easily. It is more robust and individual failure can not affect the problem- solving capability of the swarm. Each individual in the swarm can affect its environment. This is a way of indirect communication between individuals, called as stigmergy. As the information transmission and individual cooperation can be done in indirect communication in swarm intelligence, the communication overhead increases slowly with the individual number, thus there exists better scalability in swarm intelligence. The individual's ability and its followed rules in the Swarm intelligence are very simple. Thus, the realization of swarm intelligence is easy with simplicity. The complex behaviors of the swarm emerge from the interactions among simple individuals, thus, the swarm has the feature of self- organizing. Internet is a loosely-connected network to interconnect various sub- networks around connectivity. In Internet, routing has essentially got rid of the centralized control existed in traditional telecommunications networks with some taste of self-organization. However, self-organizing only reflects at router level. There are a variety of different routing protocols with different routing algorithms running in the router. In order to make network operate coordinately, a large number of information on link and network status need to be exchanged among routers, their routing tables are calculated and updated, leading to poor scalability. The deficiency of the existing routing architecture on scalability and robustness Wang, et al. Expires May 21, 2010 [Page 11] Internet-Draft Self-organizing network model November 2009 emerged with the rapid growth of Internet. In order to meet the requirements of new network applications, scalable routing architecture and efficient routing algorithm need to be developed. At present, with network scale expanded, sub-networks diversified and speed increased, simplifying network node organization and management is becoming one of the critical ways to reduce network cost, improve network utilization and enhance network reliability. By applying swarm intelligence to network routing, routing agents can be created at network nodes and cooperate along certain rules to find the optimal route with network scalability, adaptability and robustness improved. 5.2. QoS Routing With the internet scale expanded and multimedia and real-time service emerged, the user QoS requirement is improved. Research on QoS can help to improve network efficiency and reduce network cost. By QoS mechanisms, the network provider can provide differentiated services according to different user QoS requirements with user satisfaction degree and network provider profit improved. Thus, QoS support is essential in self-organizing network. There are mainly two ways to enhance QoS. One is node control and the other is network-wide or local network control. Routing affect network performance directly and thus QoS routing is critical to provide QoS. The main goal of QoS routing is to choose one route with user QoS requirement met at the same time ensure network resource efficiency. QoS routing involves the following two aspects: 1. Choosing Measurement parameters Measurement parameters are routing metrics and affect routing algorithm complexity directly. They can be divided into three categories: convex, additive and multiplicative parameters. 2. Routing According to the given metrics and current network status, try to find an route to guarantee QoS. There are mainly three kinds of routing strategies: source, distributed and hierarchical routing. Wang, et al. Expires May 21, 2010 [Page 12] Internet-Draft Self-organizing network model November 2009 Source routing changes the distributed problem to the centralized one. It is easy to be implemented and can avoid loop when routing. However, a huge amount of global network status need to be exchanged and reserved, transmission and calculation overhead is too heavy especially for large scale network. In addition, the obsolete and inaccurate global status information even may lead to routing failed. Distributed routing has shorter response time and routing algorithm is scalable. However, it may lead to loop due to only local information used when routing decision made. Hierarchical routing can not only reduce information exchanged but also avoid loop generated when routing. It is scalable, however, it is difficult to deal with QoS parameter aggregation properly. According to the destination number, routing can be divided into two categories: unicast and multicast, correspondingly unicast and multicast routing algorithm. For QoS routing, there are two basic problems: optimization and bounded performance. The former tries to find a route with the optimal QoS metric values, asking for optimal solution; the latter tries to find a route with the bounded QoS metric values, only asking for the feasible solution. QoS routing algorithms usually have the following characteristics: 1. Non-NP Usually QoS routing is NP-complete. It often needs to be solved using intelligent optimization or heuristic algorithm. 2. Adaptation It should adapt to network status change automatically, promoting load balancing and avoid network congestion. 3. Deal with inaccurate routing information The information used when routing, for example, the network status and the user QoS requirement, often is fuzzy. 4. Fairness The billing paid by the user should be proportional to his received QoS level. For multicast, the billing maybe need to be apportioned among its members fairly. Wang, et al. Expires May 21, 2010 [Page 13] Internet-Draft Self-organizing network model November 2009 5. Robustness It can do re-routing or has one or multiple alternative path(s) when failure occurred. Wang, et al. Expires May 21, 2010 [Page 14] Internet-Draft Self-organizing network model November 2009 6. Self-organizing Network Design Paradigm 6.1. DESIGN LOCAL BEHAVIOR RULES THAT ACHIEVE GLOBAL PROPERTIES To design a network function that establishes a global property, this paradigm is to distribute the responsibility among the individual entities: no single entity is "in charge" of the overall organization, but each contributes to a collective behavior. Following this paradigm, localized behavior rules must be deviced, if applied in all entities, automatically lead to the desired global property (or at least approximate it). "localized" mean that entities have only a local view of the network and interact with their neighbors and changes in the network have initially only local consequences. 6.2. EXPLOIT IMPLICIT COORDINATION Implicit coordination means that coordination information is not communicated explicitly by signaling messages, but is inferred from the local environment. A node observes other nodes in its neighborhood; based on these observations, it draws conclusions about the status of the network and reacts accordingly. 6.3. MINIMIZE LONG-LIVED STATE INFORMATION To achieve a higher level of self-organization, the amount of long- lived state information should be minimized. In general, the more localized the interactions are and the less coordination is needed, the less state information must be maintained. 6.4. DESIGN PROTOCOLS THAT ADAPT TO CHANGES The need for the capability of nodes to react to changes in the network and its environment typically arises from changed resource constraints, changed user requirements, node mobility, or node failures. Since there are no centralized entities that could notify the nodes about changes, each node has to continuously monitor its local environment and react in an appropriate manner. Three levels of adaptation can be distinguished. Level 1: A protocol is designed so that it can cope with changes, such as failure and mobility. Level 2: Wang, et al. Expires May 21, 2010 [Page 15] Internet-Draft Self-organizing network model November 2009 A protocol is designed to adapt its own parameters (e.g., value of timers, cluster size) as a reaction to changes in order to optimize system performance. Level 3: A protocol is designed so that it realizes if the changes are so severe that the currently employed mechanism is no longer suitable. To detect such situations the environment is observed, and significant changes in major parameters trigger a fallback or alternative solution. Typically, these levels of adaptation are combined using control loops. There are also advanced levels of adaptation (e.g., learning algorithms) that effectively change the algorithms in the nodes. Here, these algorithms are not included for self-organized networking, as their application in a dynamic network is typically quite complex and difficult to predict. In addition, dynamically changing algorithms might lead to difficulties in implicit communication, as the interpretation of the environment depends on the knowledge of their behavior. Wang, et al. Expires May 21, 2010 [Page 16] Internet-Draft Self-organizing network model November 2009 7. Network Model Self-organizing network model can be denoted as a graph G(V, E), V is node set, representing the routers which have the characteristics of biological behaviors and have the capabilities of information transmission and processing in the network; E is edge set, representing the links in the network. 7.1. Network Parameters In order to describe the network status, certain parameters are introduced as follows: To the edge, consider the following parameters: total bandwidth (tbw), available bandwidth (abw), delay (dl), delay jitter (jt) and error rate (ls). It is assumed that the specific delay, delay jitter and error rate experienced by the service through the link have nothing to do with the service type, only having relations with the link type and the current network status. To the node, consider the following parameters: Stability degree (st). 7.2. Network Self-organization Behavior Design Nodes in self-organizing network have characteristics of biological diversity. In this document, the following network self-organization behaviors are introduced: 1. Incarnation A new node is generated with certain necessary information initialized. 2. Environment Awareness A node is aware of parameters of its connected links, for example, their total bandwidth, available bandwidth, delay, delay jitter and error rate. A node is aware of the status of its neighboring nodes, for example, their load and stability degree. Wang, et al. Expires May 21, 2010 [Page 17] Internet-Draft Self-organizing network model November 2009 3. Relation establishment/elimination Efficient and directly-connected edge establishment With routing continuously, a node in the network will gradually memorize some frequently-used paths to other nodes. Such paths are called small world edges. If some small world edge is frequently used as the next hop in some route when routing, a directly-connected edge should be established between the two end nodes of this small world edge whenever possible, so that the efficiency of routing and transmission. Here, the main consideration is the used frequency of a small world edge as one hop when routing. Only when its used frequency is above one preset threshold during certain period of time, does it be considered to establish one directly connected link between its two end nodes. A node maintains a counter for each of its memorized small world edges. Every times when a small world edge used as one hop on a route successfully, its corresponding counter should be increased by 1, and when its value is above the preset threshold, a request to establish a directly connected edge is issued. In order to keep the state refresh, all counters will be reset periodically. Enhanced edge establishment When one edge is often rejected as one hop on a route due to its inability of meeting the user QoS requirement, its performance should be enhanced to provide better QoS. A node sets one rejection counter for each of its connected edge, and whenever the edge is rejected as the next hop, the corresponding counter is increased by 1. If the counter value is above the preset threshold, a request to enhance the corresponding edge's performance is issued. Edge deletion When any edge is never be used after an enough long time period (a measurement period), it should be deleted. A node maintains a timer for each of its connected edges. The timer's initial value is set as the measurement period. If the edge was used before its corresponding timer time out, the timer is reset; otherwise, once the timer timed out, an request to delete its corresponding edge will be issued. Wang, et al. Expires May 21, 2010 [Page 18] Internet-Draft Self-organizing network model November 2009 When a node died, its connected edges are deleted. 4. Load migration In order to balance the network load and thus efficiently use network resources, load migration is introduced for node. It is realized by proper load apportion among these neighboring nodes not by physically changing node location. According to the trigger manner, it can be classified into active and passive migration. Passive migration It is such a situation that a node was forced to migrate a fraction of its load to its neighboring node(s) if permitted because it is overloaded. A node monitors its own load. When its load is above the preset threshold for the preset time period delta(t2), the node issue a request to its neighboring nodes for load migration. They determine if this request can be accepted and the amount of the migrated load based on their own loads. Active migration It is such a situation that when it is light-loaded continuously, a node begins to probe whether its neighboring nodes are overloaded, and actively accept the whole or partial amount of volunteering migrated load by the overloaded node(s) based on its own conditions. A node monitors its own load. When it is light-loaded, that is, below a preset threshold, for a preset time period delta(t3), the node begins to observe the load status of its neighboring nodes. If some of them are found to be overloaded for a preset time period delta(t1), the active migration is initiated. Here, delta(t1) < delta(t2) < delta(t3). 5. Cloning Cloning means copying routing information from one node to another. The cloning-generated node can not only replace the cloned node to work, but also can be used to share its load. Wang, et al. Expires May 21, 2010 [Page 19] Internet-Draft Self-organizing network model November 2009 6. Reproduction Reproduction means that two or more nodes transfer their routing information integratedly into a node. Thus, the reproduced node can not only replace their parent nodes to work, but also can be used to share their loads. 7. Dormancy When a node does not run any task over a time period above a preset threshold, it becomes dormant to reduce its power consumption. 8. Coma A node enters into the so called coma state temporally if it can not act normally due to some in-vital errors, for example, bugs in routing software, occurred. A coma node will restore after a period of self healing or by certain external forces. 9. Wake up Wake up the coma or dormant node to resume their work. If in the routing process, a node can not find the proper next hop routing from its neighbors, it will wake up its coma or dormant neighbor if any. 10. vivification A coma or dormant node self-restore to resume its work. 11. succour A coma node restores to resume its work with external intervention. 12. death A node can work no longer due to vital failure occurred, for example, some unrepairable hardware failures. 7.3. Node Stability Degree 1. Factors related with node stability degree Many behaviors in self-organizing network can lead to node instability, for example, node migration, dormancy, coma and Wang, et al. Expires May 21, 2010 [Page 20] Internet-Draft Self-organizing network model November 2009 death and so on, and in most cases these behaviors have relations with node loads. The factors related with node instability are described as follows. External factors It mainly refers to neighboring node load. It has great effect on node migration behavior and thus affects node stability degree severely. Internal factor It mainly refers to a node's own load. Overloaded may lead to coma even migration and light-loaded migration even death. 2. Stability calculation Based on the above, when node stability degree calculated, a node's own and its neighbors' load should be taking into account with emphasis. Introduce the following four parameters for each node: total CPU cycles TCPU, available CPU cycles ACPU, total buffer size TBUF and available buffer size ABUF. Then, define CPU and buffer availability ratio as follows: RAC=ACPU/TCPU (Formula 1) RAB=ABUF/TBUF (Formula 2) Define node load descriptor as follows: LD=1/(a/(RAC) + b/(RAB)) (Formula 3) Here, a and b are tuning factors to reflect relative significance degrees of CPU and buffer utilization on node load, a,b>0, a + b = 1. Apparently, 0 <= LD <=1, and the smaller the LD, the much light the node load. Define node stability degree as follows: ST=a*LD(nb)+b*(1 -2*|1/2-LD|) (Formula 4) Here, a and b are tuning factors to reflect relative significance degrees of neighboring node load and node's own load on node stability, a, b > 0, a + b = 1. A node may have several neighboring nodes. If so, LD(nb) is the LD of the Wang, et al. Expires May 21, 2010 [Page 21] Internet-Draft Self-organizing network model November 2009 node with the heaviest load. Apparently, 0 <= ST <=1. According to formula, the smaller the ST, the much stable the node. When its neighboring node load becomes much light, the stability degree of a node becomes higher, because the possibility of its light-loaded neighbors migrating load to it becomes lower; otherwise, the stability degree of a node becomes lower. When the node load varies from its median value, its node stability degree becomes lower; the much approaching the median value, the much stable the node, because the possibility of migrating load between it and its neighbors become lower. Wang, et al. Expires May 21, 2010 [Page 22] Internet-Draft Self-organizing network model November 2009 8. Routing Request Because it is difficult to describe user QoS requirement exactly, the interval is used to describe it. 8.1. User QoS Unicast Routing Request Define user QoS unicast routing request as R(v( , s), v( , d), delta( , bw), delta( , dl), delta( , jt), delta( , ls), p). Here, v(s) belongs to V and is its source node; v(d) belongs to V and is its destination node, delta(bw)=[bw_r(L), bw_r(H)] is its bandwidth constraint interval, delta(dl)=[bl_r(L, ), bl_r(H, )] is its delay constraint interval, delta(jt)=[jt_r(L, ), jt_r(H, )] is its delay jitter constraint interval, delta(ls)=[ls_r(L, ), ls_r(H, )] is its error rate constraint interval, p is the upper bound of the price the user willing to pay. 8.2. User QoS Multicast Routing Request At first, consider a user heterogeneous QoS multicast routing request, that is, each multicast member has different QoS requirement and the upper bound of the price he is willing to pay, denoted as R(v( , s), v(d), delta(d, bw), delta(d, dl), delta(d, jt), delta(d, ls), p(d, )). delta(d, bw)=[bw_r(L, d), bw_r(H, d)], delta(d, dk)=[dl_r(L, d), dl_r(H, d)], delta(d, jt)=[jt_r(L, d), jt_r(H, d)], delta(d, ls)=[ls_r(L, d), ls_r(H, d)] and p(d, ) is corresponding to the multicast member v(d).the ceiling of the cost what the users want to pay. For a homogeneous one, each member has the same QoS requirement and the upper bound of the price he is willing to pay. Wang, et al. Expires May 21, 2010 [Page 23] Internet-Draft Self-organizing network model November 2009 9. Link QoS Evaluation It is difficult to measure network status exactly, thus fuzzy information handling is necessary. 9.1. Link Parameter Membership Degree 1. Bandwidth membership degree Assume the available bandwidth abw(l) of the link e(l) belongs to [abw(L, l), abw(H, l)], the membership degree function of the actually occupied bandwidth bw by a user on e(l) to it is defined as follows: f(l, abw, bw)=1, bw<=abw(L, l) f(l,abw,bw)=1/2-1/2*sin{pi/ [abw(H,l)-abw(L,l)]*[bw-(abw(L,l)+abw(H,l))]/2}, abw(L,l)abw(H, l) (Formula 5) The above formula assumes that the bandwidth membership degree function is subject to the smaller form of the mountain-shaped distribution. 2. Delay membership degree Assume the delay dl(l) of the link e(l) belongs to [dl(L, l, dl(H, l))], the membership degree function of the actually experienced delay dl by a user on e(l) to it is defined as follows: f(l, dl, dl)=1 ,dl<=dl(L, l) f(l, dl, dl)=1/2+1/2*sin{pi/ [dl(H,l)-dl(L,l)]*[dl- (dl(L,l)+dl(H,l))/2]} ,dl(L,l)dl(H, l) (Formula 6) The above formula assumes that the delay membership degree function is subject to the larger form of the mountain-shaped distribution. 3. Delay-Jitter membership degree Assume the delay jitter jt(l) of the link e(l) belongs to [jt(L, l, jt(H, l))], the membership degree function of the Wang, et al. Expires May 21, 2010 [Page 24] Internet-Draft Self-organizing network model November 2009 actually experienced delay jitter jt by a user on e(l) to it is defined as follows: f(l, jt, jt)=1 ,jt<=jt(L, l) f(l, jt, jt)=1/2+1/2*sin{pi/ [jt(H,l)-jt(L,l)]*[jt- (jt(L,l)+jt(H,l))/2]} ,jt(L,l)jt(H, l) (Formula 7) The above formula assumes that the delay jitter membership degree function is subject to the larger form of the mountain- shaped distribution. 4. Error Rate membership degree Assume the error rate ls(l) of the link e(l) belongs to [ls(L, l, ls(H, l))], the membership degree function of the actually experienced error rate ls by a user on e(l) to it is defined as follows: f(l, ls, ls)=1 ,ls<=ls(L, l) f(l, ls, ls)=1/2+1/2*sin{pi/ [ls(H,l)-ls(L,l)]*[ls- (ls(L,l)+ls(H,l))/2]} ,ls(L,l)ls(H, l) (Formula 8) The above formula assumes that the error rate membership degree function is subject to the larger form of the mountain- shaped distribution. 9.2. QoS Satisfaction Degree The satisfaction degree functions of the user to his actually received QoS from the link are defined as follows. 1. Bandwidth The satisfaction degree function of the user to his actually occupied bandwidth bw from the link e(l) is defined as follows: S(l,bw,bw)=0 ,bw=bw_r(H, )(Formula 9) According to the above formula, a user become much satisfied with bw increased. When bw reaches bw_r(H, ), he becomes the most satisfied. 2. Delay The satisfaction degree function of the user to his actually experienced delay dl(l) from the link e(l) is defined as follows: S(l,dl,dl)=1 ,dl=dl_r(H, ) (Formula 10) According to the above formula, a user become much satisfied with dl(l) decreased. When dl(l) decreases to dl_r(L, ), he becomes the most satisfied. 3. Delay jitter The satisfaction degree function of the user to his actually experienced delay jitter jt(l) from the link e(l) is defined as follows: S(l,jt,jt)=1 ,jt=jt_r(H, ) (Formula 11) According to the above formula, a user become much satisfied with jt(l) decreased. When jt(l) decreases to jt_r(L, ), he becomes the most satisfied. 4. Error rate The satisfaction degree function of the user to his actually experienced error rate ls(l) from the link e(l) is defined as follows: S(l,ls,ls)=1 ,ls=ls_r(H, ) (Formula 12) According to the above formula, a user become much satisfied with ls(l) decreased. When ls(l) decreases to ls_r(L, ), he becomes the most satisfied. 9.3. Link QoS Evaluation The evaluation function of the user on the link provided bandwidth, delay, delay jitter and error rate and the comprehensive one on the link provided QoS are defined as follows: g(l, bw) = f(l, bw, ubw)*S(l, bw, ubw) (Formula 13) g(l, dl) = f(l, dl, udl)*S(l, dl, udl) (Formula 14) g(l, jt) = f(l, jt, ujt)*S(l, jt, ujt) (Formula 15) g(l, ls) = f(l, ls, uls)*S(l, ls, uls) (Formula 16) W(l) = a(bw)*g(l, bw) + a(dl)*g(l, dl) + a(jt)*g(l, jt) + a(ls)*g(l, ls) (Formula 17) Here, a(bw), a(dl), a(jt) and a(ls) are weights of bandwidth, delay, delay jitter and error rate, indicating their relative importance on the user QoS requirement, 0<=a(bw), a(dl), a(jt), a(ls)<=1, a(bw) + a(dl) + a(jt) + a(ls) = 1. W(l) in [0, 1], and the bigger it is, the higher evaluation the user on the link provided QoS. Wang, et al. Expires May 21, 2010 [Page 27] Internet-Draft Self-organizing network model November 2009 10. Utility Calculation and Gaming Analysis According to economics principles, commodity pricing should be based on supply and demand relations at market at the same time commodity prices have effects on supply and demand relations. In order to improve communication quality, users want to occupy bandwidth on the link as much as possible, however, this will lead to network resource shortage. In this case, network providers will raise their resource prices, and then users have to pay more for network usage. In order to increase their revenue, network providers want to increase network resource prices, however, some users will abort to use their network resources no longer, and thus leading to their revenue down. As a result, network providers have to cut down their resource prices to attract their users back. In general, How much resources users consume should be based on their own conditions and resource pricings in order to maximize their own interests while resource prices should be determined by their providers based on current supply and demand relations at market so that their profits maximized. Not only bandwidth but also delay, delay jitter and error rate should be considered when routing. Thus, delay, delay jitter and error rate have effects on resource pricing and then on users interests and network providers revenue. 10.1. Cost and Price Cost refers to resource expense network provider suffered for providing service. Here, network resource only refers to bandwidth. Assume bandwidth cost per unit is cb on the link el. For the provided bandwidth ubw, cost suffered by the network provider is as follows: Cost(l) = c(b) * ubw (Formula 18) Price refers to charge user pay for consuming network resource. If the occupied bandwidth on link el by user is ubw, price paid by the user is as follows: Pay(l)=p*ubw +p(fk) (Formula 19) p is bandwidth base-price and is related with bandwidth utilization. When bandwidth utilization is high, its provider may consider to increase p, and when it is low, its provider may consider to decrease p. Wang, et al. Expires May 21, 2010 [Page 28] Internet-Draft Self-organizing network model November 2009 p=p(min), h uu(i(*)j) ,i(*) =1,2,...,m un(ij) => un(ij(*)) ,i(*)=1,2,...,n (Formula 26) If such a element found, its corresponding strategy pair (ubw(i), P(j)) is the one with Nash equilibrium achieved when the user and the network provider play game on the link. However, such a element may not exist and multiple such elements may exist simultaneously. In this case, Pareto dominance, defined as follows, need to be compared further. pareto(ij)=a/uu(ij)+b/un(ij) (Formula 27) a and b are preference weights for user and network ultilities, a, b > 0, a+b=1. Apparently, a element with smaller Pareto dominance is more Pareto optimal. A strategy pair with the smallest Pareto dominance is chosen as the optimal one (if multiple such ones exist, choose one at random). Wang, et al. Expires May 21, 2010 [Page 31] Internet-Draft Self-organizing network model November 2009 11. Unicast Path and Multicast Tree Evaluation When a unicast path or multicast tree is evaluated, there are two factors considered significantly: user and network provider utility. The objective of routing optimization is to try to maximize user utility, network provider utility and their sum simultaneously, so that their utility win-win are prompted. The evaluation functions of the unicast path P and the multicast tree T are defined as follows: J(p)=a(up)/UU(P) + a(np)/UN(P) (Formula 28) J(T)=a(ut)/UU(T) + a(nt)/UN(T) (Formula 29) UU(P)=sigma(uu(l), l belonging to P) / L(P) (Formula 30) UU(T)=sigma(sigma(uu(i, l), l belonging to (s-i)), l belonging to T) (Formula 31) UN(P)=sigma(un(l), l belonging to P)/L(P) (Formula 32) UN(T)=sigma(un(l), l belonging to T)/L(T) (Formula 33) Here, UU(P) and UU(T) are user utilities on P and T respectively, UN(P) and UN(T) are network provider utilities on P and T respectively, L(P) and L(T) are hop numbers of P and T respectively, a(up) and a(ut) are user utility preference weights, a(np) and a(nt) are network provider preference weights respectively, 0 max{UU(P)} (Formula 34) UN(P) -> max{UN(P)} (Formula 35) UU(P) + UN(P) -> max{UU(P) + UN(P)} (Formula 36) s.t. main({abw}, e(l) is belonging to P(sd)) => bw_r( , l) (Formula 37) sigma(dl( , l), e(l) is belonging to P(sd)) <= dl_r( , h) (Formula 38) sigma(jt( , l) <= jt_r( , h), e(l) is belonging to P(sd))(Formula 39) 1-pi((1-ls( , l)) e(l) is belonging to P(sd))(Formula 40) pay( , p) <= p (Formula 41) 12.2. Multicast Mathematics Model The objective of the QoS multicast routing optimization is as follows: with the QoS requirement and the upper bound of the willing- to-pay price of each multicast member satisfied, try to maximize the user utility, the network provider utility and their sums on the tree. Its corresponding mathematical model is described as follows: UU(T) -> max{UU(T)} (Formula 42) UN(T) -> max{UN(T)} (Formula 43) UU(T) + UN(T) -> max{UU(T) + UN(T)} (Formula 44) s.t. main({abw(d, l)}, e(l) is belonging to P(sd)) => bw_r(d, l) (Formula 45) sigma(dl(d, l), e(l) is belonging to P(sd)) <= dl_r(d, h) (Formula 46) Wang, et al. Expires May 21, 2010 [Page 33] Internet-Draft Self-organizing network model November 2009 sigma(jt(d, l) <= jt_r(d, h), e(l) is belonging to P(sd))(Formula 47) 1-pi((1-ls(d, l)) e(l) is belonging to P(sd))(Formula 48) pay(d, p) <= p(d, ) (Formula 49) The above is about heterogeneous multicast. For homogeneous one, the values of bw_r(d, l), dl_r(d, h), jt_r(d, h), ls_r(d, h) and p(d) of all multicast members are the same. Wang, et al. Expires May 21, 2010 [Page 34] Internet-Draft Self-organizing network model November 2009 13. Small World Behavior 1. Small world behavior has the following characteristics High variability of node degree distribution can help to get short route and high clustering coefficient; When node degree distribution variability is not very high, it can not alone lead to small world behavior; Local connection preference can lead to small world behavior, especially in router-level network topology. Self-organizing network has behaviors with biological characteristics. Node and edge are changing dynamically and they can be established, changed even removed, thus node degree distribution is variable. In addition, in self- organizing network, interactions between nodes are localized, and then there exists local connection preference. However, it needs an evolution process from a randomly generated network to a network with small world behaviors, and during this process the so-called small world behaviors can not be directly taken into use when routing. Another point, in existing small world network models, node connection refers to directly connection and its distribution variability is regarding to such directly connected edge. In this document, the frequently-used indirectly connected edge (see the mentioned small world edge section) substitutes the directly connected one to produce small world behaviors and guides the establishment of the efficient directly connected edge, taking advantage of small world behaviors. For example, a node A is directly connected with nodes A1, A2, A3 and A4, and routes with A as their source node and D1, D2 and D3 as their destination nodes have been established. If these three routes are frequently used in other routes successfully, three small word edges are considered to exist from A to D1, D2, D3. When calculate node degree of A, these three small world edge are included. Therefore, node degree distribution variability can be supported. Of course, use a path as an edge can bring some problems. After all, the complexity of dealing with a path is not the same as that of dealing with an edge when routing. In addition, although a route often can be found in short time with small world edge used, its hop number may be larger and thus is not the optimal one. For example, there are small world edges between S and M and between M and D. If used when Wang, et al. Expires May 21, 2010 [Page 35] Internet-Draft Self-organizing network model November 2009 routing from S to D, a route is found very quickly with only two routing operations done. However, the found route has 8 hops. If S->A->B->D are chosen as the route without small world edge used, it only has 3 hops. In addition, small world edge recording also brings router extra storage overhead. In order to avoid the above problems appearing frequently when routing, not only the times of using small world edges when routing should be limited, for example, only at the last hop use a small world edge, that is, only use the small world edge with destination node reachable, but also a small world edge's hop number should be bounded when it is established. 2. Small world behavior realization in self-organizing network Table 2 List of worldlet Edge destination intermediate hop used node node sequence count times ------------------------------------------------------- D(1) (N(1),...) 5 m(1) D(2) (N(4),...) 3 m(2) D(3) (N(4),...) 3 m(3) ... ... ... ... Figure 2 When routing in self-organizing network, to find even a sub- optimal route quckly is often preferred to find a optimal one with much more time. Thus, it is necessary to efficiently establish and use small world edge in routing. Small world edge usage With routing continuously, each routing node gradually accumulates some small world edges, and then convenient and short-cut reachable information to other nodes become more and more. There is no doubt that using these well-known small world edges when routing can shorten routing time. Each routing node records these small world edges from which depart as in table 2. Table initialization: each routing node maintains a small world edge registration node shown as table 2. At the beginning, it is initialized as an empty table. Wang, et al. Expires May 21, 2010 [Page 36] Internet-Draft Self-organizing network model November 2009 Small world edge adding: It is carried out by routing algorithm. Whenever a route is found successfully, if it is eligible to become a small world edge, its related information will be added to the registration table and its corresponding "used times" is set to be 0. Used times: Whenever a small world edge is successfully used in routing, its used times is increased by 1. Update: The registration table is scanned onec every delta(t(swp)), during which those small world edges with zero used times will be deleted and each remaining one's used times is reset to be 0. Routing success ratio It refers to the percentage of successful routing times in total routing times in a routing node. Nodes with higher success ratio should be preferred when routing. Two counters are equipped with each node: successful routing times counter rcs(i) and total routing times counter rct(i). Every time when routing is done, increase rct(i) by 1, and every time when routing is successful, increase rcs(i) by 1. rcs(i) and rct(i) are periodically refreshed, that is, every delta(t(rc)) time, they are reset to be 0. The routing success ratio for node i is calculated as follows: I(i) = rcs(i) / rct(i) (Formula 50) Address similarity degree Nodes with the same IP address prefix are likely to be located at neighborhood and close to each other. The longer such the same prefix, the closer neighborhood these nodes located at. For example, 202.118.1.64 and 202.118.1.206 have the same prefix 202.118.1, the nodes with these two highly similar IP address should be very close to each other. The percentage of the length of the same prefix of two addresses in the address length is defined as the so called address similarity degree. It can be gotten as follows: from left to right two addresses are compared bitwise, counting the times of the same bits appearing in the two addresses and record it as D, until different bits appeared. Assume the address length is T, their address similarity degree is Wang, et al. Expires May 21, 2010 [Page 37] Internet-Draft Self-organizing network model November 2009 calculated as follows: S=D/T (Formula 51) When routing, the address similarity degree between each candidate next hop node and the destination node is compared, and the node with the highest similarity degree should be preferred as the next hop because it should be nearest to the destination node. Doing so can help to reduce both routing time and route hop count. Wang, et al. Expires May 21, 2010 [Page 38] Internet-Draft Self-organizing network model November 2009 14. Route Strategies At the initial phase of self-organizing network operating, the distributed routing algorithm is adopted to adapt to high network dynamics and variations. At this phase the network-wide, especially backbone topology and routing information are collected gradually and then the self-organizing network will enter into relatively-stable phase with such information remaining invariable or varying little for a long time. At this time, the centralized algorithm can be used to optimize routing and improve routing efficiency. According to its situation of dynamics and variation, the distributed and centralized algorithm is used alternatively. Wang, et al. Expires May 21, 2010 [Page 39] Internet-Draft Self-organizing network model November 2009 15. Security Considerations Security is a big problem in self-organizing network. Routing nodes in self-organizing networks directly interact among them in distributed peer-to-peer manner. Each node contributes to complex network behavior with its own simple action. Under such a situation, identity authentication and behavior monitoring become more difficult while detecting and defending malicious intrusion become harder. If the new security architecture and technique are not developed for self-organizing network, the network will become more vulnerable. In this document, the focus is on the basic architecture and QoS routing technique in self-organizing network, and security issues and techniques are not discussed. Wang, et al. Expires May 21, 2010 [Page 40] Internet-Draft Self-organizing network model November 2009 16. IANA Considerations This document has no actions for IANA. Wang, et al. Expires May 21, 2010 [Page 41] Internet-Draft Self-organizing network model November 2009 17. Acknowledgments The author would like to thank Zhankao Wen, Weidong Wang, Weixin Wu, Jun Liu, Dengke Zhang, Jan Wu, Xiaolei Huang, Xiaofeng Liu, Yao Fu, Jun Hu, Guilin Liu, Peiyu Qin, Yulei Wu, Hanrui Wang and the rest of the Adaptive Routing Working Group for the ideas and support they have given to this project. Wang, et al. Expires May 21, 2010 [Page 42] Internet-Draft Self-organizing network model November 2009 Appendix A. References 1. Christian Prehofer, Christian Bettstetter. Self-Organization in Communication Networks: Principles and Design Paradigms[J], IEEE Communications Magazine, 2005: 78-84. 2. Sudhir Dixit, Amardeo Sarma. Advance in self-organizing networks[J], IEEE Communications Magazine, 2005: 76-77. 3. R. Ghnemat, C. Bertelle, G.H.E. Duchamp. Self-Organization Simulation over Geographical Information System Based on Multi- Agent Platform[A], The European Simulation and modeling Conference[C], 2006: 23-25. 4. Beni, G., Wang, J. Swarm intelligence[A], In Proceedings of the Seventh Annual Meeting of the Robotics Society of Japan[C], 1989: 425-428. 5. Susan Hackwood, Gerardo Beni. Self organization of sensors for swarm intelligence[A], proceedings of the 1992 IEEE international conference on robotics and automation[C], 1992: 819-825. 6. M. Dorigo, E. Bonabeau, G. Theraulaz. Ant algorithms and stigmergy[J], Future Generation Computer System, 2000, 16(8): 851-871. 7. YingHua Min. Computer network routing survey[J], computer Journal, 2003, 26(6): 642-648. 8. Wu Jiang, HuiLing Zhao. Next generation IP backbone network technology- Multi-protocol Label Switching [M], 2001, 21-41. 9. Brunilde Sanso, Andre Girard, Florent Mobiot. Integrating reliability and quality of service in networks with swhiched virtual circuits [J], Computers and Operations Research, 2005, 32(1): 35-58. 10. C Bouras, A Gkamas, A Karaliotas, et al. Architecture and performance evaluation for redundant multicast transmission supporting adaptive QoS [J], Multimedia Tools and Applications, 2005, 25(1): 85-110. 11. Brunilde Sanso, Andre Girard, Florent Mobiot. Integrating reliability and quality of service in networks with swhiched virtual circuits [J], Computers and Operations Research, 2005, 32(1): 35-58. Wang, et al. Expires May 21, 2010 [Page 43] Internet-Draft Self-organizing network model November 2009 12. Zhong Fan, E S Lee. Multiple QoS constrained routing with inaccurate state information [J], Electronics Letters, 1999, 35 (21): 1807-1808. 13. Li Wang, ZengZhi Li, ChengQian Song and so on. a dynamic multicast routing algorithm[J].2004, 32(8): 1245-1247. 14. Ariza, E. Casilari, F. Sandoval. QoS routing with outdated network knowledge [J], Electronics Letters, 2000, 36(15): 1332- 1334. 15. Xavier Masip Bruin, Sergio Sanchez Lopez, Josep Sole Pareta, et al. A QoS routing mechanism for reducing the routing inaccuracy effects [J], LNCS 2601, 2003: 90-102. 16. F P Kelly, A Maulloo, D Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability [J], Operational Research Society, 1998, 49(3): 237-252. 17. Tadashi Nakano, Tatsuya Suda. Applying biological principles to designs of network services[J]. Applied Soft Computing, 2006: 1-9. Wang, et al. Expires May 21, 2010 [Page 44] Internet-Draft Self-organizing network model November 2009 Authors' Addresses XingWei Wang Northeastern University No.11, Lane 3, WenHua Road, HePing District Shenyang, Liaoning, China 110004 Phone: Email: wangxw@mail.neu.edu.cn URI: Yi XiuShuang Northeastern University Phone: Email: xsyi@mail.neu.edu.cn URI: Yu Wang Northeastern University Phone: Email: wangy@mail.neu.edu.cn URI: Ming Dong Northeastern University Phone: Email: dongm@mail.neu.edu.cn URI: Qiang Chen Northeastern University Phone: Email: URI: Wang, et al. Expires May 21, 2010 [Page 45]