Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Fast-Convergence Routing of the Hot-Potato
62
0
0.0
(
0
)
Added by
Jean-Romain Luttringer
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Jean-Romain Luttringer
Ask ChatGPT about the research
No Arabic abstract
Interactions between the intra- and inter-domain routing protocols received little attention despite playing an important role in forwarding transit traffic. More precisely, by default, IGP distances are taken into account by BGP to select the closest exit gateway for the transit traffic (hot-potato routing). Upon an IGP update, the new best gateway may change and should be updated through the (full) re-convergence of BGP, causing superfluous BGP processing and updates in many cases. We propose OPTIC (Optimal Protection Technique for Inter-intra domain Convergence), an efficient way to assemble both protocols without losing the hot-potato property. OPTIC pre-computes sets of gateways (BGP next-hops) shared by groups of prefixes. Such sets are guaranteed to contain the post-convergence gateway after any single IGP event for the grouped prefixes. The new optimal exits can be found through a single walk-through of each set, allowing the transit traffic to benefit from optimal BGP routes almost as soon as the IGP converges. Compared to vanilla BGP, OPTICs structures allow it to consider a reduced number of entries: this number can be reduced by 99% for stub networks. The update of OPTICs structures, which is not required as long as border routers remain at least bi-connected, scales linearly in time with its number of groups.
rate research
Read More
In this paper we present new general convergence results about the behaviour of Distributed Bellman-Ford (DBF) family of routing protocols, which includes distance-vector protocols (e.g. RIP) and path-vector protocols (e.g. BGP). First, we propose a new algebraic model for abstract routing problems which has fewer primitives than previous models and can represent more expressive policy languages. The new model is also the first to allow concurrent reasoning about distance-vector and path-vector protocols. Second, we explicitly demonstrate how DBF routing protocols are instances of a larger class of asynchronous iterative algorithms, for which there already exist powerful results about convergence. These results allow us to build upon conditions previously shown by Sobrinho to be sufficient and necessary for the convergence of path-vector protocols and generalise and strengthen them in various ways: we show that, with a minor modification, they also apply to distance-vector protocols; we prove they guarantee that the final routing solution reached is unique, thereby eliminating the possibility of anomalies such as BGP wedgies; we relax the model of asynchronous communication, showing that the results still hold if routing messages can be lost, reordered, and duplicated. Thirdly, our model and our accompanying theoretical results have been fully formalised in the Agda theorem prover. The resulting library is a powerful tool for quickly prototyping and formally verifying new policy languages. As an example, we formally verify the correctness of a policy language with many of the features of BGP including communities, conditional policy, path-inflation and route filtering.
Content Delivery Networks (CDN) are witnessing the outburst of video streaming (e.g., personal live streaming or Video-on-Demand) where the video content, produced or accessed by mobile phones, must be quickly transferred from a point to another of the network. Whenever a user requests a video not directly available at the edge server, the CDN network must 1) identify the best location in the network where the content is stored, 2) set up a connection and 3) deliver the video as quickly as possible. For this reason, existing CDNs are adopting an overlay structure to reduce latency, leveraging the flexibility introduced by the Software Defined Networking (SDN) paradigm. In order to guarantee a satisfactory Quality of Experience (QoE) to users, the connection must respect several Quality of Service (QoS) constraints. In this paper, we focus on the sub-problem 2), by presenting an approach to efficiently compute and maintain paths in the overlay network. Our approach allows to speed up the transfer of video segments by finding minimum delay overlay paths under constraints on hop count, jitter, packet loss and relay processing capacity. The proposed algorithm provides a near-optimal solution, while drastically reducing the execution time. We show on traces collected in a real CDN that our solution allows to maximize the number of fast video transfers.
This paper considers the problem of secure packet routing at the maximum achievable rate in a Quantum key distribution (QKD) network. Assume that a QKD protocol generates symmetric private keys for secure communication over each link in a multi-hop network. The quantum key generation process, which is affected by noise, is assumed to be modeled by a stochastic counting process. Packets are first encrypted with the available quantum keys for each hop and then transmitted on a point-to-point basis over the communication links. A fundamental problem that arises in this setting is to design a secure and capacity-achieving routing policy that accounts for the time-varying availability of the quantum keys for encryption and finite link capacities for transmission. In this paper, by combining the QKD protocol with the Universal Max Weight (UMW) routing policy, we design a new secure throughput-optimal routing policy, called Tandem Queue Decomposition (TQD). TQD solves the problem of secure routing efficiently for a wide class of traffic, including unicast, broadcast, and multicast. One of our main contributions in this paper is to show that the problem can be reduced to the usual generalized network flow problem on a transformed network without the key availability constraints. Simulation results show that the proposed policy incurs a substantially smaller delay as compared to the state-of-the-art routing and key management policies. The proof of throughput-optimality of the proposed policy makes use of the Lyapunov stability theory along with a careful treatment of the key-storage dynamics.
Owing to the increasing need for massive data analysis and model training at the network edge, as well as the rising concerns about the data privacy, a new distributed training framework called federated learning (FL) has emerged. In each iteration of FL (called round), the edge devices update local models based on their own data and contribute to the global training by uploading the model updates via wireless channels. Due to the limited spectrum resources, only a portion of the devices can be scheduled in each round. While most of the existing work on scheduling focuses on the convergence of FL w.r.t. rounds, the convergence performance under a total training time budget is not yet explored. In this paper, a joint bandwidth allocation and scheduling problem is formulated to capture the long-term convergence performance of FL, and is solved by being decoupled into two sub-problems. For the bandwidth allocation sub-problem, the derived optimal solution suggests to allocate more bandwidth to the devices with worse channel conditions or weaker computation capabilities. For the device scheduling sub-problem, by revealing the trade-off between the number of rounds required to attain a certain model accuracy and the latency per round, a greedy policy is inspired, that continuously selects the device that consumes the least time in model updating until achieving a good trade-off between the learning efficiency and latency per round. The experiments show that the proposed policy outperforms other state-of-the-art scheduling policies, with the best achievable model accuracy under training time budgets.
Reactive routing protocols are gaining popularity due to their event driven nature day by day. In this vary paper, reactive routing is studied precisely. Route request, route reply and route maintenance phases are modeled with respect to control overhead. Control overhead varies with respect to change in various parameters. Our model calculates these variations as well. Besides modeling, we chose three most favored reactive routing protocols as Ad-Hoc on Demand Distance Vector (AODV), Dynamic Source Routing (DSR) and Dynamic MANET on Demand (DYMO) for our experiments. We simulated these protocols using ns-2 for a detailed comparison and performance analysis with respect to mobility and scalability issues keeping metrics of throughput, route delay and control over head. Their performances and comparisons are extensively presented in last part of our work.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
