Minimum hop flow assignment and routing subject to an average message delay constraint

An algorithm for minimum hop flow assignment and routing in message-switched networks subject to an average message delay constraint is developed and illustrated. The development is based on an analysis of the original problem formulation in terms of the minimum achievable average message delay as a function of the average number of hops. From this analysis, it is found that the problem can be solved via successive application of a modified flow deviation method in which average message delay is minimized subject to a constraint on the average number of hops. The resulting algorithm is simple and efficient. It obtains the desired solution directly if one exists or shows that no solution is possible, the latter occurring when there is no feasible flow assignment and routing which can satisfy the delay constraint. An example involving a network with 10 nodes, 36 links and 40 commodities is given, and directions for future research are indicated.     

DTN中基于节点价值的效用路由算法

为了解决延迟容忍网络(DTN)中传统路由算法中消息被分配的网络资源不均衡及节点负载不均衡问题,结合消息效用值提出了一种基于节点价值的效用路由算法。算法根据动态改变的消息效用值选择最高优先级的消息(具有最小TTL和到目的节点最短距离的消息)进行转发,以使得为每个消息分配的网络资源相对均衡;同时,根据节点的价值(与节点速度和剩余缓存有关)选择下一跳节点,以平衡每个节点的负载;另外,算法还采用了一定的消息管理机制及时清除缓存空间。通过仿真实验及性能分析表明,该算法在传输成功率、传输延迟和网络开销上都有明显的改善。因此,通过充分利用网络资源提高了算法的整体性能。     

An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks

Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.     

Probabilistic flooding in stochastic networks: Analysis of global information outreach

This article investigates probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a received message to all its neighbors with a common network-wide forwarding probability ω. Question is: what is the minimum ω-value each node should use, such that the flooded message is obtained by all nodes with high probability? We first present a generic approach to derive the global outreach probability in arbitrary networks and then focus on Erd?s Rényi graphs (ERGs) and random geometric graphs (RGGs). For ERGs we derive an exact expression. For RGGs we derive an asymptotic expression that represents an approximation for networks with high node density. Both reliable and unreliable links are studied.     

A gradient based routing scheme for street lighting wireless sensor networks

Routing for wireless sensor networks based on gradient is a simple, reliable solution resulting in low information costs for the network package, as well as for the node itself. It is used for convergent traffic, where sensor nodes send messages to the sink node. Due to message transmission failures inherent to wireless sensor networks, researches in this area agree that point-to-point message confirmation in these networks is essential. This work proposes solutions for gradient-based routing using a confirmation mechanism for different neighbors, where four protocol variations are evaluated for sensor networks applications in order to monitor and control electrical variables. Results demonstrate that the protocol based on the longest distance has a satisfactory package delivery rate in severe conditions specified to the application. Furthermore, results show in which situations each routing protocol variation better suits the target application.     

Optimal total exchange in Cayley graphs

Consider an interconnection network and the following situation: Every node needs to send a different message to every other node. This is the total exchange or all-to-all personalized communication problem, one of a number of information dissemination problems known as collective communications. Under the assumption that a node can send and receive only one message at each step (single-port model), it is seen that the minimum time required to solve the problem is governed by the status (or total distance) of the nodes in the network. We present a time-optimal solution for any Cayley network. Rings, hypercubes, cube-connected cycles, and butterflies are some well-known Cayley networks which can take advantage of our method. The solution is based on a class of algorithms which we call node-invariant algorithms and which behave uniformly across the network     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

Secure Node Discovery in Ad-hoc Networks and Applications

Designing secure protocols over ad-hoc networks has proved to be a very challenging task, due to various features of such networks, such as partial connectivity, node mobility, and resource constraints. Furthermore, their lack of physical infrastructures deprives their users of even basic network functions such as message routing, for which nodes are themselves responsible.In this paper we consider a very basic network function, node discovery, in ad-hoc networks, where a node with limited network information would like to establish a session with a given number of other nodes in the network (of which the node may not be aware about). We formally define correctness, security and efficiency properties of node discovery protocols, and investigate the problem of designing such protocols under appropriate network topology assumptions. Here, the security of these protocols is against Byzantine adversaries that can corrupt up to a limited number of nodes in the network and make them arbitrarily deviate from their protocol. After presenting some secure node discovery protocols, we show their application to secure service architectures in ad-hoc networks.     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

Dimensioning of message-switched computer communications networks with end-to-end flow control

A message-switched computer network with end-to-end window flow control is considered. An algorithm for the selection of the best flow-control window settings is developed using heuristics for the numberical solution of such networks. The criterion of performance is the ratio of the network average throughput to the average network delay. An example network demonstrates the results.     

Efficient Broadcasting Using Network Coding and Directional Antennas in MANETs

In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks (MANETs) using network coding and directional antennas. Network coding-based broadcasting focuses on reducing the number of transmissions each forwarding node performs in the multiple source/multiple message broadcast application, where each forwarding node combines some of the received messages for transmission. With the help of network coding, the total number of transmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcasting to further reduce energy consumption. A node equipped with directional antennas can divide the omnidirectional transmission range into several sectors and turn some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locally only need to transmit broadcast messages, original or coded, to restricted sectors. We also study two extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performance analysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented.     

Self-organizing and adaptive peer-to-peer network.

In this paper, an algorithm that forms a dynamic and self-organizing network is demonstrated. The hypothesis of this work is that in order to achieve a resilient and adaptive peer-to-peer (P2P) network, each network node must proactively maintain a minimum number of edges. Specifically, low-level communication protocols are not sufficient by themselves to achieve high-service availability, especially in the case of ad hoc or dynamic networks with a high degree of node addition and deletion. The concept has been evaluated within a P2P agent application in which each agent has a goal to maintain a preferred number of connections to a number of service providing agents. Using this algorithm, the agents update a weight value associated with each connection, based on the perceived utility of the connection to the corresponding agent. This utility function can be a combination of several node or edge parameters, such as degree k of the target node, or frequency of the message response from the node. This weight is updated using a set of Hebbian-style learning rules, such that the network as a whole exhibits adaptive self-organizing behavior. The principal result is the finding that by limiting the connection neighborhood within the overlay topology, the resulting P2P network can be made highly resilient to targeted attacks on high-degree nodes, while maintaining search efficiency.     

移动社会网络中基于活动的消息机会转发

针对移动社会网络中节点移动形成的成簇特性和节点参与活动表现的周期特点,提出了一种基于活动的消息机会转发算法（activity-based message opportunistic forwarding,简称AMOF）.算法思想是：当消息携带节点与目的节点存在相同活动时,选择消息交付概率高的中继节点转发消息;当消息携带节点与目的节点不存在相同活动时,选择消息间接交付概率高的链路来转发消息.仿真结果表明,与经典路由算法（如Epidemic,PRoPHET,CMOT和CMTS）比较,所提出的路由算法不仅能够提高消息的传输成功率,还能有效地降低传输时延和网络负载.     

GAER: genetic algorithm-based energy-efficient routing protocol for infrastructure-less opportunistic networks

In infrastructure-less opportunistic networks (Oppnets), the routing of messages is a challenging task since nodes are not aware of the network topology and they look for an opportunity to send the message by finding or predicting a best temporary path at each hop towards the destination. As nodes perform various computations for next hop selection, a lot of battery power gets consumed, which in turn reduces the network lifetime. Thus, there is a clear demand for routing protocols for such networks which are energy-efficient and consume lesser power of nodes in forwarding a message. In this paper, a novel routing protocol named genetic algorithm-based energy-efficient routing (GAER) protocol for infrastructure-less Oppnets is proposed. This protocol uses a node’s personal information, and then applies the genetic algorithm (GA) to select a better next hop among a group of neighbour nodes for the message to be routed to the destination. With the application of GA, optimal results are obtained that help in the selection of the best possible node as the next hop, which in turn, leads to prolonged battery life. Simulation results show that GAER outperforms the Epidemic, PROPHET, and Spray and Wait protocols in terms of messages delivered, overhead ratio, average residual energy, and number of dead nodes. The results obtained for average latency and average buffer time using GAER are comparable to those obtained for the aforementioned protocols.     

A minimum principle/queueing theory approach to routing in message-switched networks

Preliminary results for minimum message-delay routing in message-switched, store-and-forward, data-communication networks are presented using a minimum principle/queueing theory approach. The routing algorithm is a decentralized one which requires only local information. The results are illustrated via an important case of heavy network traffic, and extensions and problems for future research are discussed.     

A new injection limitation mechanism for wormhole networks

Wormhole switching has been widely applied to the interconnection networks of parallel systems as well as System Area Networks, and Local Area Networks, largely because of its efficiency and performance merits. Examples include the Myrinet of Myricom Inc as well as most of the newly developed parallel systems. True Fully Adaptive Routing (TFAR) Algorithms have demonstrated their suitability for wormhole switched networks due to their unrestricted Adaptivity and moderate resource requirements. Wormhole switching has proven to be the most popular switching technique targeted for interconnection networks of message-passing multicomputers as well as SANs, and LANs. TFAR Algorithms have also been gaining favor for application in wormhole switched networks due to their highly adaptive and moderate hardware requirements. Wormhole switched networks have associated drawbacks however, as they generally suffer from performance degradation beyond the saturation point due to channel congestion. Fully adaptive algorithms are vulnerable to cyclic dependencies, which are precursors to deadlock formations. Consequently the frequent occurrence of deadlocks can further degrade the performance and stability characteristics of these networks. Injection limitation techniques were recently introduced in an attempt to countermeasure these drawbacks and effectively contain their impact on the performance of the network. This paper proposes a new injection limitation mechanism and its performance evaluation. The new mechanism is named Congestion Level Injection Control (CLIC). This mechanism attempts to provide a solution for these problems and improve the overall performance of the network. The new mechanism is centered on congestion level estimation in the network using only local information at each node. The mechanism subsequently prevents the injection of new packets if the network is deemed to be highly congested or possibly close to its saturation point. The performance of the CLIC mechanism has been compared with other competing schemes. Our results have shown that CLIC has superior performance when compared to other competing schemes.     

Network trust management in emergency situations

We study the unique trust management, and more precisely reputation management and revocation of malicious nodes in the context of ad hoc networks used for emergency communications.Unlike in centralized systems, reputation management and revocation in ad hoc networks is non-trivial. This difficulty is due to the fact that the nodes have to collaboratively calculate the reputation value of a particular node and then revoke the node if the reputation value goes below a threshold. A major challenge in this scheme is to prevent a malicious node from discrediting other genuine nodes. The decision to revoke a node has to be communicated to all the nodes of the network. In traditional ad hoc networks the overhead of broadcasting the message throughout the network may be very high. We solve the problem of reputation management and node revocation in ad hoc networks of cell phones by using a threshold cryptography based scheme. Each node of the network would have a set of anonymous referees, which would store the reputation information of the node and issue reputation certificates to the node with timestamps. The misbehavior of a particular cell phone is reported to its anonymous referees, who issue certificates which reflect the positive and negative recommendations.     

HiMAC:一种用于消息认证和加密的分层安全协议

为检测并阻止恶意节点伪装成新的可信节点攻击移动自组织网络,该文提出了一种用于消息认证和加密的分层安全协议(HiMAC)。该协议将分层消息认证码用于保护移动Ad-Hoc网络中的数据传播。在源和目标之间的由中间节点转发分组时动态地计算可信路由,在每个中间节点对数据包进行签名和加密,防止攻击者篡改数据包或修改其跳数,实现数据可信传输。在NS2模拟器中,运用Crypto++库中的RSA算法对HiMAC进行测试。结果表明:HiMAC可以检测和阻止对MANET节点和数据包的攻击;与原有的A-SAODV安全机制相比, HiMAC平均跳数减少了47.1%,平均队列长度减小了35.5%,节点数据包数量降低2.5倍,其性能明显优于A-SAODV。尽管HiMAC的密码操作给路由协议带来了额外的开销,但由于HiMAC采用基于信任机制动态建立安全路由,使得节点能够动态地选择路径上的下一个节点,不必始终保持安全路由,使得HiMAC中的增减开销可以相互抵消达到平衡。     

Information networks: A probabilistic model for hierarchical message transfer

A strictly hierarchical message transfer scheme requires that a message follow a specified referral path unless finally it is either rejected or filled at any one of the information centers of the network. Thus at each node in the network three decisions can be made: satisfy, reject, or refer the message to the succeeding node in the hierarchy. By associating probabilities and costs with each of these decisions, we develop a Markovian model for the total network cost. The mean and variance of total cost are derived. Applicability of the model is discussed by considering the problems related to the estimation of necessary parameters. In particular, a queue-theoretic model is developed for estimating response time for a message at an information center.     

ML-SOR: Message routing using multi-layer social networks in opportunistic communications

Opportunistic networks are a generalization of DTNs in which disconnections are frequent and encounter patterns between mobile devices are unpredictable. In such scenarios, message routing is a fundamental issue. Social-based routing protocols usually exploit the social information extracted from the history of encounters between mobile devices to find an appropriate message relay. Protocols based on encounter history, however, take time to build up a knowledge database from which to take routing decisions. While contact information changes constantly and it takes time to identify strong social ties, other types of ties remain rather stable and could be exploited to augment available partial contact information. In this paper, we start defining a multi-layer social network model combining the social network detected through encounters with other social networks and investigate the relationship between these social network layers in terms of node centrality, community structure, tie strength and link prediction. The purpose of this analysis is to better understand user behavior in a multi-layered complex network combining online and offline social relationships. Then, we propose a novel opportunistic routing approach ML-SOR (Multi-layer Social Network based Routing) which extracts social network information from such a model to perform routing decisions. To select an effective forwarding node, ML-SOR measures the forwarding capability of a node when compared to an encountered node in terms of node centrality, tie strength and link prediction. Trace driven simulations show that a routing metric combining social information extracted from multiple social network layers allows users to achieve good routing performance with low overhead cost.