Information Technology Reference

In-Depth Information

other. Mathematically, the distinct representatives of

Ω
,

Ω
,
⋅⋅⋅
,

Ω
are

z
,

z
,
⋅⋅⋅
,

z

≤ ≤
and
j
≠
. An efficient polynomial-time

algorithm for finding distinct representatives is given in [26].

Our channel assignment method consists of three main steps and they are described in the

following.

Step 1. Transformation

Node
i
requires

z
∈Ω
and

z
≠
for all
1

in

where

i

i

i

j

N

≡
∑

≡
∑

N

channels to the hub and

channels from the hub,

c

d

r

d

i

ij

i

ji

j

=

1

j

=

1

i
rW

i
cW

⎡

⎤

⎡

⎤

so it requires

⎥
fibers to the hub and

⎥
fibers from the hub. Overall, the hub

⎢

⎢

has

incoming fibers and

outgoing fibers, so it has

∑

N

∑

N

∑

N

rW

rW

=
⎡

⎤

=
⎡

⎤

=
⎡

⎤

cW

⎢

⎥

⎢

⎥

⎢

⎥

i

i

j

i

1

i

1

j

1

passive combiners. We first transform
D
to a matrix
D

demultiplexers and

∑

N

⎡

cW

⎤

⎢

⎥

j

j

=

1

which specifies the number of channels required from every demultiplexer to every passive

combiner. This is done as follows: for all
1

≤ ≤
, if

iN

i
r
>
, we divide row
i
into

i
rW

i
rW

⎡

⎤

⎡

⎤

⎥
rows such that each of these

⎥
rows has a row sum of at most
W
and the

⎢

⎢

sum of the
j
th
element of these

i
rW

for all
1

≤≤
; for all

jN

⎡

⎤

d

⎥
rows is equal to

⎢

ij

1

≤≤
, if

jN

j
cW

>

, we divide column
j
into

⎥
columns such that each of these

⎡

j
cW

⎤

⎢

⎥
columns has a column sum of at most
W
and the sum of the
i
th
element of these

⎡

⎤

j
cW

⎢

∑

N

⎥
columns is equal to

d

for all

. Then we add dummy row(s) or

1

≤≤

i

⎡

r

W

⎤

⎡

⎤

j
cW

⎢

⎥

⎢

ij

k

k

=

1

column(s) to
D
such that the resulting
D
has
M
rows and
M
columns where

∑∑
, and add dummy values to some elements in
D
such

that all row sums and column sums are equal to
W
.

Step 2. Solving the Transformed Problem

For the
M
× matrix
D
with equal row sum and column sum, there exists
M
distinct

representatives such that each distinct representative appears in one distinct row and one

distinct column [26]. We apply this property to get a conflict-free channel assignment at each

distinct wavelength based on
D
. Specifically, we form
M
sets
Ω
,
Ω
,
⋅⋅⋅
,
Ω
where

Ω
contains the column numbers of the non-zero elements in row
i
of
D
, and execute the

distinct representatives algorithm [26] to determine
M
distinct representatives

N

N

M

=

max(

rW

,

⎡

c W

⎤

)

⎡

⎤

⎢

⎥

⎢

⎥

i

j

i

=

1

j

=

1

z
,
⋅⋅⋅
,

z
,

z

of these
M
sets. We use these distinct representatives to form a tentative conflict-free

M

λ
: assign a wavelength channel at

λ
to connect demultiplexer
i
to passive

assignment at

z
for all
1

≤≤
. We record this tentative assignment at

iM

λ
by the
assignment

combiner

i
d
′
by 1 for all

{

}

. Then we update
D
by deducting

set

Α=

(

)

(1,

z

),(2,

z

),

⋅⋅⋅

,(

Mz

,

)

1

1

2

M

i

1

≤≤
. The resulting
D
still has equal row sum and column sum. We repeat the above

iM