waashk/dblp huggingface dataset:
gradually reconfiguring virtual network topologies based on estimated traffic matrices. traffic matrix is essential to traffic engineering (te) methods. because it is difficult to monitor traffic matrices directly, several methods for estimating them from link loads have been proposed. however, estimated traffic matrix includes estimation errors which degrade the performance of te significantly. in this paper, we propose a method that reduces estimation errors while reconfiguring the virtual network topology (vnt) by cooperating with the vnt reconfiguration. in our method, the vnt reconfiguration is divided into multiple stages instead of reconfiguring the suitable vnt at once. by dividing the vnt reconfiguration into multiple stages, our traffic matrix estimation method calibrates and reduces the estimation errors in each stage by using information monitored in prior stages. we also investigate the effectiveness of our proposal using simulations. the results show that our method can improve the accuracy of the traffic matrix estimation and achieve an adequate vnt as is the case with the reconfiguration using the actual traffic matrices.
cell breathing techniques for load balancing in wireless lans. maximizing network throughput while providing fairness is one of the key challenges in wireless lans (wlans). this goal is typically achieved when the load of access points (aps) is balanced. recent studies on operational wlans, however, have shown that ap load is often substantially uneven. to alleviate such imbalance of load, several load balancing schemes have been proposed. these schemes commonly require proprietary software or hardware at the user side for controlling the user-ap association. in this paper we present a new load balancing technique by controlling the size of wlan cells (i.e., ap's coverage range), which is conceptually similar to cell breathing in cellular networks. the proposed scheme does not require any modification to the users neither the ieee 802.11 standard. it only requires the ability of dynamically changing the transmission power of the ap beacon messages. we develop a set of polynomial time algorithms that find the optimal beacon power settings which minimize the load of the most congested ap. we also consider the problem of network-wide min-max load balancing. simulation results show that the performance of the proposed method is comparable with or superior to the best existing association-based methods.
taking the skeletons out of the closets: a simple and efficient topology discovery scheme for large ethernet lans. we propose a simple and efficient algorithmic solution for discovering the physical topology of large, heterogeneous ethernet lans that may include multiple subnets as well as uncooperative network elements, like hubs. our scheme utilizes only generic mib information and does not require any hardware or software modification of the underlying network elements. by rigorous analysis, we prove that our method correctly infers the network topology and has low communication and computational overheads. our simulation results show that the scheme successfully infers the complete topology in the vast majority of the cases, including many instances that cannot be inferred by other methods. finally, our proof-of-concept implementation demonstrates the practicality of the proposed scheme for network management.
complexity of wavelength assignment in optical network optimization. we study the complexity of a set of design problems for optical networks. under wavelength division multiplexing (wdm) technology, demands sharing a common fiber are transported on distinct wavelengths. multiple fibers may be deployed on a physical link. our basic goal is to design networks of minimum cost, minimum congestion and maximum throughput. this translates to three variants in the design objectives: 1) min-sumfiber: minimizing the total cost of fibers deployed to carry all demands; 2) min-maxfiber: minimizing the maximum number of fibers per link to carry all demands; and 3) max-throughput: maximizing the carried demands using a given set of fibers. we also have two variants in the design constraints: 1) chooseroute: here we need to specify both a routing path and a wavelength for each demand; 2) fixedroute: here we are given demand routes and we need to specify wavelengths only. the fixedroute variant allows us to study wavelength assignment in isolation. combining these variants, we have six design problems. previously we have shown that general instances of the problems min-sumfiber-chooseroute and min-maxfiber-fixedroute have no constant-approximation algorithms. in this paper, we prove that a similar statement holds for all four other problems. our main result shows that min-sumfiber-fixedroute cannot be approximated within any constant factor unless np-hard problems have efficient algorithms. this, together with the previous hardness result of min-maxfiber-fixedroute, shows that the problem of wavelength assignment is inherently hard by itself. we also study the complexity of problems that arise when multiple demands can be time-multiplexed onto a single wavelength (as in time-domain wavelength interleaved networking (twin) networks) and when wavelength converters can be placed along the path of a demand.
broadcasting in sensor networks: the role of local information. flooding based querying and broadcasting schemes have low hop-delays of θ (1/r(n) to reach any node that is a unit distance away, where r(n) is the transmission range of any sensor node. however, in sensor networks with large radio ranges, flooding based broadcasting schemes cause many redundant transmissions leading to a broadcast storm problem. in this paper, we study the role of geographic information and state information (i.e., memory of previous messages or transmissions) in reducing the redundant transmissions in the network. we consider three broadcasting schemes with varying levels of local information where nodes have: (i) no geographic or state information, (ii) coarse geographic information about the origin of the broadcast, and (iii) no geographic information, but remember previously received messages. for each of these network models, we demonstrate localized forwarding algorithms for broadcast (based on geography or state information) that achieve significant reductions in the transmission overheads while maintaining hop-delays comparable to flooding based schemes. we also consider the related problem of broadcasting to a set of "spatially uniform" points in the network (lattice points) in the regime where all nodes have only a local sense of direction and demonstrate an efficient "sparse broadcast" scheme based on a branching random walk that has a low number of packet transmissions. thus, our results show that even with very little local information, it is possible to make broadcast schemes significantly more efficient.
performance analysis of contention based medium access control protocols. this paper studies the performance of contention based medium access control (mac) protocols. in particular, a simple and accurate technique for estimating the throughput of the ieee 802.11 dcf protocol is developed. the technique is based on a rigorous analysis of the markov chain that corresponds to the time evolution of the back-off processes at the contending nodes. an extension of the technique is presented to handle the case where service differentiation is provided with the use of heterogeneous protocol parameters, as, for example, in ieee 802.11e edca protocol. our results provide new insights into the operation of such protocols. the techniques developed in the paper are applicable to a wide variety of contention based mac protocols.
ddc: a dynamic and distributed clustering algorithm for networked virtual environments based on p2p networks. this paper presents a dynamic and distributed algorithm for the clustering of peers in a networked virtual environment (nve) based on a fully distributed peer-to-peer (p2p) network.the main idea is to classify connections in short intra-cluster connections and long inter-cluster connections. the insertion of new peers or the deletion of existing peers can result in the merging of two clusters or the split of one cluster in two parts.
leds: providing location-aware end-to-end data security in wireless sensor networks. providing desirable data security, i.e., confidentiality, authenticity and availability, in wireless sensor networks (wsns) is challenging, as wsns usually consist of a large number of resource constraint sensor nodes, deployed in unattended/hostile environments, and hence are exposed to many types of severe insider attacks due to node compromise. existing security designs mostly provide a hop-by-hop security paradigm and thus are vulnerable to such attacks. furthermore, existing security designs are also vulnerable to various dos attacks, such as report disruption attacks and selective forwarding attacks and thus put data availability at stake. in this paper, we seek to overcome these vulnerabilities for large-scale static wsns. we come up with a location-aware end-to-end security framework in which secret keys are bound to geographic locations. this location-aware property effectively limits the impact of compromised nodes only to their vicinity without affecting end-to-end data security. the proposed multi-functional key management framework assures both node-to-sink and node-to-node authentication along the report forwarding routes. moreover, the proposed data delivery approach guarantees efficient en-route bogus data filtering, and is highly robust against dos attacks. the evaluation demonstrates that the proposed design is highly resilient against an increasing number of compromised nodes and effective in energy savings.
media streaming via tfrc: an analytical study of the impact of tfrc on user-perceived media quality. tcp-friendly rate control (tfrc) is being adopted in internet standards for congestion control of streaming media applications. in this paper, we consider the transmission of prerecorded media from a server to a client by using tfrc, and analytically study the impact of tfrc on user-perceived media quality, which is roughly measured by calculating the rebuffering probability. a rebuffering probability is defined to be the probability that the total duration of all rebuffering events experienced by a user is longer than a certain threshold. several approaches are presented to help an application determine an appropriate initial buffering delay and media playback rate in order to achieve a certain rebuffering probability under a given network condition. first, we derive a closed-form expression to approximate the average tfrc sending rate, which could be used as the maximum allowed playback rate of a media stream. second, we develop a queueing model for a tfrc client buffer with the traffic described by a markov-renewal-modulated deterministic process (mrmdp), which captures the fundamental behavior of tfrc that predicts the immediate future tcp sending rate based on the history of past loss intervals. we present a closed-form solution and a more accurate iterative method to solve the queueing model and calculate the rebuffering probability.
dual-resource tcp/aqm for processing-constrained networks. this paper examines congestion control issues for tcp flows that require in-network processing on the fly in network elements such as gateways, proxies, firewalls and even routers. applications of these flows are increasingly abundant in the future as the internet evolves. since these flows require use of cpus in network elements, both bandwidth and cpu resources can be a bottleneck and thus congestion control must deal with "congestion" on both of these resources. in this paper, we show that conventional tcp/aqm schemes can significantly lose throughput and suffer harmful unfairness in this environment, particularly when cpu cycles become more scarce (which is likely the trend given the recent explosive growth rate of bandwidth). as a solution to this problem, we establish a notion of dual-resource proportional fairness and propose an aqm scheme, called dual-resource queue (drq), that can closely approximate proportional fairness for tcp reno sources with in-network processing requirements. drq is scalable because it does not maintain per-flow states while minimizing communication among different resource queues, and is also incrementally deployable because of no required change in tcp stacks. the simulation study shows that drq approximates proportional fairness without much implementation cost and even an incremental deployment of drq at the edge of the internet improves the fairness and throughput of these tcp flows. our work is at its early stage and might lead to an interesting development in congestion control research.
delay and capacity trade-offs in mobile ad hoc networks: a global perspective. since the original work of grossglauser and tse, which showed that mobility can increase the capacity of an ad hoc network, there has been a lot of interest in characterizing the delay-capacity relationship in ad hoc networks. various mobility models have been studied in the literature, and the delay-capacity relationships under those models have been characterized. the results indicate that there are trade-offs between the delay and capacity, and that the nature of these trade-offs is strongly influenced by the choice of the mobility model. some questions that arise are: (i) how representative are these mobility models studied in the literature? (ii) can the delay-capacity relationship be significantly different under some other "reasonable" mobility model? (iii) what sort of delay-capacity trade-off are we likely to see in a real world scenario? in this paper, we take the first step toward answering some of these questions. in particular, we analyze, among others, the mobility models studied in recent related works, under a unified framework. we relate the nature of delay-capacity trade-off to the nature of node motion, thereby providing a better understanding of the delay-capacity relationship in ad hoc networks in comparison to earlier works.
achieving 100% throughput in reconfigurable optical networks. we study the maximum throughput properties of dynamically reconfigurable optical network architectures having wavelength and port constraints. using stability as the throughput performance metric, we outline the single-hop and multi-hop stability regions of the network. our analysis of the stability regions is a generalization of the bvn decomposition technique that has been so effective at expressing any stabilizable rate matrix for input-queued switches as a convex combination of service configurations. we consider generalized decompositions for physical topologies with wavelength and port constraints. for the case of a single wavelength per optical fiber, we link the decomposition problem to a corresponding routing and wavelength assignment (rwa) problem. we characterize the stability region of the reconfigurable network, employing both single-hop and multi-hop routing, in terms of the rwa problem applied to the same physical topology. we derive expressions for two geometric properties of the stability region: maximum stabilizable uniform arrival rate and maximum scaled doubly substochastic region. these geometric properties provide a measure of the performance gap between a network having a single wavelength per optical fiber and its wavelength-unconstrained version. they also provide a measure of the performance gap between algorithms employing single-hop versus multi-hop electronic routing in coordination with wdm reconfiguration.
packet pacing in short buffer optical packet switched networks. in the absence of a cost-effective technology for storing optical signals, emerging optical packet switched (ops) networks are expected to have severely limited buffering capability. to mitigate the performance degradation resulting from small buffers, this paper proposes that optical edge nodes "pace" the injection of traffic into the ops core. our contributions relating to pacing in ops networks are three-fold: first, we develop real-time pacing algorithms of poly-logarithmic complexity that are feasible for practical implementation in emerging high-speed ops networks. second, we provide an analytical quantification of the benefits of pacing in reducing traffic burstiness and traffic loss at a link with very small buffers. third, we show via simulations of realistic network topologies that pacing can significantly reduce network losses at the expense of a small and bounded increase in end-to-end delay for real-time traffic flows. we argue that the loss-delay tradeoff mechanism provided by pacing can be instrumental in overcoming the performance hurdle arising from the scarcity of buffers in ops networks.
wireless operators in a shared spectrum. cellular networks are notoriously difficult to design and operate; in particular, defining the optimal location of the base stations and fine tuning their configuration parameters is very challenging. for this reason, government agencies (such as the fcc for the us) usually sell or rent, for example by auction, each operator a frequency band for its exclusive usage in a given country or region. only a small part of the whole spectrum is allocated as a shared spectrum, in which networks function in the same (unlicensed) frequency band.
gre encapsulated multicast probing: a scalable technique for measuring one-way loss. we develop techniques for estimating one-way loss from a measurement host to network routers which exploit commonly implemented features on commercial routers and do not require any new router capabilities. the work addressesthe problem of scalably performing one-way loss measurements across specific network paths.
overhead and performance study of the general internet signaling transport (gist) protocol. the general internet signaling transport (gist) protocol is currently being developed as the base protocol compo-nent in the ietf next steps in signaling (nsis) protocol stack to support a variety of signaling applications. we present our study on the protocol overhead and performance aspects of gist. we quantify network-layer protocol overhead and observe the effects of enhanced modularity and security in gist. we developed a first open source gist implementation at the university of göttingen, and study its performance in a linux testbed. a gist node serving 45 000 signaling sessions is found to consume average only 1.1 ms for processing a signaling message and 2.4 kb of memory for managing a session. individual routines in the gist code are instrumented to obtain a detailed profile of their contributions to the overall system processing. important factors in determining performance, such as the number of sessions, state management, refresh frequency, timer management and signaling message size are further discussed. we investigate several mechanisms to improve gist performance so that it is comparable to an rsvp implementation.
connectivity-based localization of large scale sensor networks with complex shape. we study the problem of localizing a large sensor network having a complex shape, possibly with holes. a major challenge with respect to such networks is to figure out the correct network layout, that is, avoid global flips where a part of the network folds on top of another. our algorithm first selects landmarks on network boundaries with sufficient density, then constructs the landmark voronoi diagram and its dual combinatorial delaunay complex on these landmarks. the key insight is that the combinatorial delaunay complex is provably globally rigid and has a unique realization in the plane. thus an embedding of the landmarks by simply gluing the delaunay triangles properly recovers the faithful network layout. with the landmarks nicely localized, the rest of the nodes can easily localize themselves by trilateration to nearby landmark nodes. this leads to a practical and accurate localization algorithm for large networks using only network connectivity. simulations on various network topologies show surprisingly good results. in comparison, previous connectivity-based localization algorithms such as multidimensional scaling and rubberband representation generate globally flipped or distorted localization results.
maximizing restorable throughput in mpls networks. mpls recovery mechanisms are increasing in popularity because they can guarantee fast restoration and high qos assurance. their main advantage is that their backup paths are established in advance, before a failure event takes place. most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. however, this so-called spare capacity allocation (sca) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. in this paper, we present a comprehensive study on restorable throughput maximization in mpls networks.we present the first polynomial-time algorithms for the splittable version of the problem. for the unsplittable version, we provide a lower bound for the approximation ratio and propose an approximation algorithm with an almost identical bound. we present an efficient heuristic which is shown to have excellent performance. one of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice.
cross-layer rate control in wireless networks with lossy links: leaky-pipe flow, effective network utility maximization and hop-by-hop algorithms. we take a cross-layer design approach to study rate control in multihop wireless networks. due to the lossy nature of wireless links, the data rate of a given flow becomes smaller and smaller along its routing path. as a result, the data rate received successfully at the destination node (the effective rate) is typically lower than the transmission rate at the source node (the injection rate). in light of this observation, we treat each flow as a "leaky-pipe" flow and introduce the notion of "effective utility" associated with the effective rate (not the injection rate) of each flow. we then explore rate control through effective network utility maximization (enum) in this study. two network models are studied in this paper: 1) enum with link outage constraints with a maximum error rate at each link; 2) enum with path outage constraints where there exists an end-to-end outage requirement for each flow. for both models, we explicitly take into account the "thinning" feature of data flows and devise distributed hop-by-hop rate control algorithms accordingly. our numerical examples corroborate that higher effective network utility and better fairness can be achieved by the enum algorithms than the standard num.
mac for networks with multipacket reception capability and spatially distributed nodes. the physical layer of future wireless networks will be based on novel radio technologies such as uwb and mimo. one of the important capabilities of such technologies is the ability to capture a few packets simultaneously. this capability has the potential to improve the performance of the mac layer. however, we show that in networks with spatially distributed nodes, reusing backoff mechanisms originally designed for narrow-band systems (e.g., csma/ca) is inefficient. it is well known that when networks with spatially distributed nodes operate with such mac protocols, the channel may be captured by nodes that are near the destination, leading to unfairness. we show that when the physical layer enables multipacket reception, the negative implications of reusing the legacy protocols include not only such unfairness, but also a significant throughput reduction. we present alternative backoff mechanisms and evaluate their performance via markovian analysis, approximations, and simulation. we show that our alternative backoff mechanisms can improve both overall throughput and fairness.