Routing Schemes for Hybrid Communication Networks

2025-05-03 0 0 1.06MB 56 页 10玖币

侵权投诉

Routing Schemes for Hybrid Communication

Networks

Sam Coy !

University of Warwick, UK

Artur Czumaj !

University of Warwick, UK

Christian Scheideler !

University of Paderborn, Germany

Philipp Schneider !

University of Freiburg, Germany

Julian Werthmann !

University of Paderborn, Germany

Abstract

Hybrid communication networks provide multiple modes of communication with varying characteris-

tics. The

HYBRID

model was introduced to allow theoretical study of such networks. It combines

local

mode, which restricts communication among nodes to a given graph and a

global

mode

where any two nodes may communicate in principle, but only very little such communication can

take place per unit of time. For an example consider an ad-hoc wiﬁ network among mobile devices

supplemented with comparatively limited communication via the cellular network.

We consider the problem of the computation of

routing schemes

, where nodes have to compute small

labels and routing tables that allow for eﬃcient routing of messages in the local network, which

typically oﬀers the majority of the throughput. Recent work has shown that using the

HYBRID

model admits a signiﬁcant speed-up compared to what would be possible if either communication

mode were used in isolation. Nonetheless, if general graphs are used as local graph the computation

of routing schemes still takes polynomial rounds in the HYBRID model.

We bypass this lower bound by restricting the local graph to unit-disc-graphs with few “radio holes”

and solve the problem deterministically with running time, label size, and size of routing tables all

(

|H|2

log n

)where

|H|

is the number of such radio holes. Our work builds on that of [Coy et

al., OPODIS’21], which obtains this result if no radio holes are present thus making the graph much

simpler (topologically similar to a tree). We develop new techniques to achieve this, a decomposition

of the local graph into path-convex regions, where each region contains a shortest path for any pair

of nodes in it. We continue to investigate properties of shortest paths algorithms on grid graphs,

which can be utilized as simpler representations of unit-disc-graphs.

2012 ACM Subject Classiﬁcation Theory of computation →Distributed algorithms

Keywords and phrases

Hybrid networks, overlay networks, unit-disk graphs, routing schemes

Funding

Sam Coy: Research supported in part by the Centre for Discrete Mathematics and its

Applications (DIMAP) and an EPSRC studentship.

Artur Czumaj: Research supported in part by the Centre for Discrete Mathematics and its Appli-

cations (DIMAP), EPSRC award EP/V01305X/1, and the Simons Foundation Award No. 663281

granted to the Institute of Mathematics of the Polish Academy of Sciences for the years 2021–2023.

Christian Scheideler: This work was partially supported by the German Research Foundation

(DFG) within the Collaborative Research Centre

On-The-Fly Computing (GZ: SFB 901/3)

under

the project number 160364472

Julian Werthmann: This work was partially supported by the German Research Foundation (DFG)

within the Collaborative Research Centre

On-The-Fly Computing (GZ: SFB 901/3)

under the

project number 160364472

Acknowledgements

We would like to thank Martijn Struijs for valuable discussions concerning the

geometric insights of the paper. Any errors remain our own.

arXiv:2210.05333v2 [cs.DC] 13 Mar 2023

2 Routing Schemes for Hybrid Communication Networks

1 Introduction

The

HYBRID

model was introduced in [

] as a means to study distributed systems which

leverage multiple communication modes of diﬀerent characteristics. Of particular interest

are networks that combine a

local

communication mode, which has a large bandwidth but

is restricted to edges of a

graph

on the nodes of the network, with a

global

communication

mode where any two nodes may communicate in principle, but very little such communication

can take place per unit of time. This concept captures various real distributed systems,

notably networks of cellphones that combine high bandwidth but locally restricted wireless

communication on a

unit-disc-graph

with data transmission via the cellular network.

Routing Schemes

are one of the most fundamental distributed data structures, most promi-

nently employed in the Internet, and are used to forward packets among connected nodes

in a network in order to facilitate data exchange between any pairs of nodes. In the dis-

tributed variant of the problem the nodes initially only know their incident neighbors in the

network and need to communicate as eﬃciently as possible using their available means of

communication such that subsequently each node knows its label and a routing table with

the following properties. Given a packet with the label of the receiver node in the header,

any node must be able to forward this packet in the network using the label and its routing

table such that the packet eventually reaches the intended receiver. Algorithms for routing

schemes in hybrid networks are of increasing importance, as contemporary communication

standards support such settings, one prominent example being the 5G standard [

]. Formally

we deﬁne routing schemes as follows.

IDeﬁnition 1

(Routing Schemes)

A routing scheme on a connected graph

= (

V, E

)

consists of labels

(

)and routing functions (aka routing table)

ρv

for each

v∈V

ρv

maps

labels to neighbors of

, such that the following holds. Let

s, t ∈V

. Let

and

vi+1

ρvi

(

)) for

i≥

1. Then there is an

`∈N

, such that

. A routing scheme is an

approximation with

stretch α

`st ≤α·hop

(

s, t

)for all

s, t ∈V

, where

hop

(

s, t

)is smallest

number of edges of any

-path, and

`st

is the length of the induced routing path from

Since typically large amounts of packets are exchanged between senders and receivers as

part of simultaneously ongoing sessions we concentrate on routing schemes for the local

network graph, which oﬀers much larger throughput that than what is possible on the global

network, since the latter either involves higher costs or is more restricted as infrastructure

is shared, like communicating via the cellular network (however, we need very little local

communication to actually compute the routing scheme).

Our ﬁrst goal is to optimize the round complexity of computing such a routing scheme, which

is important since frequent changes in the topology of a local network among mobile devices

necessitates its fast re-computation. The second goal is to minimize the size of the labels

and local routing tables as these must be shared in advance (e.g. via the global network) to

initiate a session between two nodes. The third goal is to minimize the stretch of the routing

path between sender and receiver, minimizing latency and alleviating congestion.

Note that minimizing hop-distance in a unit-disc-graph essentially minimizes the Euclidean distance

that the path covers, thus graph weights are not required. This is due to the fact that there is always a

shortest path Πthat covers distance at least 1 with every two hops. Thus, if

(Π) is the distance in

the UDG measured by the euclidean length of its edges then dG(Π) ≤ |Π| ≤ 2dG(Π).

S. Coy A. Czumaj C. Scheideler P. Schneider J. Werthmann 3

We consider the above problem in the

HYBRID

model of computing that has received

increasing attention during the last few years [

]. Formally, the

HYBRID

model builds on the classic principle of synchronous message passing:

IDeﬁnition 2

(Synchronous message passing, cf. [

])

We have

computational nodes with

some initial state and unique identiﬁers (IDs) in [

] :=

{

, . . . , n}

. Time is slotted into

discrete rounds. In each round, nodes receive messages from the previous round; they perform

(unlimited) computation based on their internal states and the messages they received so far;

and ﬁnally, based on those computations, they send messages to other nodes in the network.

Note that the synchronous message passing model focuses on the analysis of round complexity

of a distributed problem (the number of rounds required to solve it). The

HYBRID

model

restricts which nodes may communicate in a given round and to what extent.

IDeﬁnition 3

(

HYBRID

model, cf. [

])

The

local

communication mode is modeled as a

connected graph, in which each node is initially aware of its neighbors and is allowed to

send a message of size

bits to each neighbor in each round. In the

global

communication

mode, each round each node may send or receive

bits to/from every other node that can be

addressed with its ID in [

]in case it is known. If any restrictions are violated in a given

round, we assume a strong adversary selects the messages that are dropped.

In this paper, we consider a weak form of the

HYBRID

model, which sets

λ∈O

(

log n

)

and

γ∈O

(

log2n

), which corresponds to the combination of the classic distributed models

CONGEST2

as local mode, and

NODE CAPACITATED CLIQUE

(

NCC

)

as global mode.

The distributed problem of computing routing schemes on the local communication graph is

an excellent ﬁt for the

HYBRID

model, since the problem is known to require

Ω

(

)rounds of

communication (where

O, e

Ω

hides

polylog n

factors) if only

either

communication via the local

mode

the global mode is permitted, see [

]. The lower bound for the local communication

mode holds even if the input graph is a path and even for unbounded local communication.

It is natural to wonder if adding a modest amount of global communication on top of a local

network signiﬁcantly improves the required number of communication rounds to establish a

routing scheme in the network. This question was recently answered positively by [

], where

it was shown that routing schemes with small labels can be computed in

(

n1/3

)rounds

for

arbitrary

local graphs. However, [

] also shows that a polynomial number of rounds

is required to solve the problem even approximately (in particular, an exact solution with

labels up to size O(n2/3)requires e

Ω(n1/3)rounds).

To mitigate this lower bound, [

] considers local communication networks that are restricted

to certain interesting classes of graphs for which they can compute routing schemes in

just

(

log n

)rounds. In this article we will continue this line of work and consider local

communication graphs that are unit-disk graphs (UDGs). Such a UDG

= (

V, E

)satisﬁes

the property that nodes are embedded in the Euclidean plane and are connected iﬀ they are

at distance at most 1 (see Def. 6). Note that UDGs have been extensively studied as a model

capturing how multiple devices using wireless ad-hoc connections communicate (see, e.g.,

[5, 6, 9, 16, 17, 18], all of which handle routing schemes in such UDGs).

2Some previous papers that consider hybrid models use λ=∞, i.e., the LOCAL model as local mode.

Our approach works for the stricter

NCC0

model where only incident nodes in the local network and

those that have been introduced can communicate globally.

4 Routing Schemes for Hybrid Communication Networks

In [

] it was shown that the nodes of a UDG can together simulate a much simpler

grid graph

(see Def. 7) structure with constant overhead in round complexity, such that the connectivity,

the hole-freeness, and the hop distance up to a constant factor are preserved. Furthermore,

[

] shows that a routing scheme on a grid graph can eﬃciently be transformed into a routing

scheme for the underlying UDG, which introduces only a constant overhead on label size

and local routing information and takes only a constant number of additional rounds.

This allows them to consider the much simpler grid graphs for the computation of routing

schemes to generate good routing schemes for UDGs. However, their actual algorithm for

computing a routing scheme for a grid graph comes with a caveat: it works only for grid

graphs

without holes

, which, loosely speaking, are points in the grid without nodes on them

that are enclosed by a cycle in the grid graph (more formally in Deﬁnition 13), which implies

routing schemes only for UDGs without “radio holes”, which roughly correspond to areas

enclosed by the UDG that are not covered by nodes (see [

] for the formal deﬁnition of radio

holes in UDGs).

In this work we extend the solution to UDGs with such radio holes. Note that the transfor-

mations given in [

] from UDGs to grid graphs work even if there are holes, which essentially

allows us to focus on the computation routing schemes for grid graphs with holes, which gives

the same for arbitrary UDGs. Our algorithm is asymptotically as eﬃcient (in computation

time, and label and table sizes of the resulting routing scheme) as the algorithm of [

] if the

number of holes |H| is small.

We stress that it is

signiﬁcantly

more challenging to compute routing schemes on grid graphs

with such holes than on grid graphs without holes. In the paper of Coy et al. ([

]) the authors

heavily exploit the property that any

-path can be deformed into any other

-path: this is

not true

in our setting. In particular, it is easy to come up with examples of grid graphs

with

|H|

holes for which there are at least 2

|H|

“reasonable”

classes of

-paths (intuitively:

paths which do not completely encircle or spiral around holes) which cannot be deformed into

each other. Worse still, we can make all-but-one of these classes of paths almost arbitrarily

long, and so it is not the case that we can consider just one arbitrary class of

-paths and

obtain an approximate shortest path. Therefore we must determine the class in which an

exact shortest

-path lies, and this seems to require a sparsifying structure which scales in

complexity with the number of holes.

1.1 Contributions

Our main contribution is the following result.

ITheorem 4

(Main Result for Grid Graphs)

Given a grid graph Γwith a set

of holes (see

Def. 13), we can compute an exact routing scheme for Γin

(

|H|2

log n

)rounds in the

HYBRID

model. The labels are of size

(

log n

); nodes need to locally store

(

|H|2log n

)bits.

This result acts as an extension of the result presented in Coy et al., [

], which assumes

that no holes are present making the graph structure much simpler. Note that [

] showed

that grid graphs approximate unit-disk graphs well (we brieﬂy summarize this in Section 2),

which leads to the following corollary:

By a reasonable path we mean a path which does not completely encircle a hole or spiral around one:

such a path can clearly be shortened.

S. Coy A. Czumaj C. Scheideler P. Schneider J. Werthmann 5

ICorollary 5

(Main Result for UDGs)

The above routing scheme can be transformed into

a routing scheme which yields constant-stretch shortest paths for unit-disk graphs. Round

complexity, label size, and local storage are asymptotically the same as above.

We believe that several of our technical contributions are of independent interest. Our main

technical contribution is a decomposition of a grid graph into

simple, path-convex

regions

which have useful properties for routing. We also provide a small skeleton structure of the

UDG called a landmark graph with the property that shortest paths in the landmark graph

are topologically the same (i.e., circumnavigate holes in the same way) as in the original

graph, which may be useful when solving shortest paths on grid graphs and UDGs in

HYBRID

or for similar problems in other models of computation. Furthermore we give an

(

log n

)

round algorithm for solving SSSP exactly in simple grid graphs and an

(

log n

)round

algorithm for ﬁnding the distance from every node in a simple grid graph to a portal.

1.2 Overview

For an end-to-end overview of our approach, following an example graph, see Appendix A.

In Section 3, we give an algorithm that solves SSSP in hole-free grid graphs (see Deﬁnition 7

and Deﬁnition 15) in

(

log n

)rounds deterministically. We create two helper graphs, one

representing its horizontal connections and one for the vertical connections, and we prove

that SSSP solutions for these two graphs suﬃce to solve SSSP in the original grid graph.

Further, we present a scheme that allows us to compute shortest paths of nodes to

portal

sets (i.e., a connected straight path in the grid graph).

In Section 4, we show that a grid graph can be decomposed into regions such that each

region is simple (contains no holes) and path-convex (for any nodes

s, t

in a region, a shortest

-path lies entirely in their region), and with overlap only in portals (speciﬁcally called

gates). We do this in stages: we decompose the graph into simple regions; we decompose

these regions further so that they are “tunnel” shaped (i.e., bounded by at most 2gates);

and ﬁnally we decompose them further still to ensure they are path-convex. We show that

we can perform this decomposition quickly and the number of resulting regions is low.

In Section 5, we give a skeleton structure on this decomposition to facilitates routing. We

mark vertices which lie on many shortest paths as

landmarks

. We connect some landmarks

in the same region to each other to form a

landmark graph

, and show it can be computed

quickly. Finally, we prove that for any grid nodes

and

, a shortest

-path goes through

the same regions as the shortest path from a landmark near sto a landmark near t.

In Section 6, we combine our results to construct the routing scheme, ﬁrst showing that

each node can eﬃciently learn the whole landmark graph. We then show that the region

which a packet should enter next can be determined by combining information about the

landmark graph, the target node’s label, and local information about the region the message

is currently in. Nodes forward received packets to their neighbor which is closest to the

packet’s next region. We repeat this until the packet arrives at the target region, switching

then to the routing scheme of [9].

1.3 Related Work

Shortest Paths in Hybrid Networks.

Previous work in the

HYBRID

model has mostly

focused on shortest path problems [

]. In the

-sources shortest path (

-SSP)

problem, all nodes must learn their distance in the (weighted) local network to a set of

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RoutingSchemesforHybridCommunicationNetworksSamCoy!UniversityofWarwick,UKArturCzumaj!UniversityofWarwick,UKChristianScheideler!UniversityofPaderborn,GermanyPhilippSchneider!UniversityofFreiburg,GermanyJulianWerthmann!UniversityofPaderborn,GermanyAbstractHybridcommunicationnetworksprovidemultipl...

展开>> 收起<<

Routing Schemes for Hybrid Communication Networks.pdf

共56页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Routing Schemes for Hybrid Communication Networks

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: