Access Network Design

David Tipper
Associate Professor
Department of Information Science and
Telecommunications
University of Pittsburgh
Slides 6
[Link]

Access Network Design

• Backbone or Wide Area Networks connect major sites.
– Backbone networks (UUNET, Verizon)
– Corporate VPN
– Campus backbone
• Access networks connect “small” sites to the backbone
network.
– Access networks are the “ends” and “tails” of networks that
connect the smallest sites into the network.
– In some cases access networks only function if they are attached
to a backbone.
– LAN, Metro networks, VLAN, cellular networks, Wireless LAN
Local access in phone network, Bank ATM machines
– Historically informal back of the envelope design procedures –
becoming more mathematical based

TELCOM 2110 5

1
 Access Network Example
• Can make Access/Backbone analogy with transportation
networks
• Visit to Gauley River for whitewater rafting in WV
• The trip involves 4 segments:
– Travel from home in Pittsburgh via city streets to interstate
– Then traverse the 279, 79 Interstate backbone to the location
closest to Gauley River - U.S. Highway 19 exit
– Then you travel on U.S. highway 19 to get to Summersville, WV
(this is like a concentrator – is a four lane highway (with traffic
lights etc)
– Travel local state highways roads from Summersville to get to
Gauley River

TELCOM 2110 6

Access Network Example

See similar – access to backbone behavior in networks

For example, LAN segments connecting to campus backbone

TELCOM 2110 7

2
 Access Network Design

• Backbone/access division is efficient for

transportation networks and efficient for
telecommunications networks.
• Access network collect traffic from small
sites into the high speed backbone
network.
• Sharing high speed links, enjoy economy
of scale benefit.
• Local access often represents most of the
total network cost – e.g, telephone network
TELCOM 2110 8

A Simple Access Design Problem

• A problem with 6 access locations
and 1 backbone site N1 Traffic is
symmetric and shown table .
• Piecewise linear cost function
• Using Leased Lines :
• Cost=$400 + ($3.00/km/month
for the first 300km and a cost of
$1.75/km/month after 300km)

Cost Matrix for 56Kbps Lines

TELCOM 2110 9

3
 Star Design

• Cost=$9650; Maximum Utilization=23.2%

TELCOM 2110 10

One Concentrator
• N2 serves as a concentrator for N6 and N7.
• Shorter less expensive links are used from N6 and N7
• Cost=$8660; Maximum Utilization=46.4%

TELCOM 2110 11

4
 Two Concentrators
• N2 for N6 and N7; N4 for N3.
• Cost=$8158; Maximum Utilization=46.4%

TELCOM 2110 12

MST Design
• Using MST algorithm, chooses N7, N4 as concentrators
• Cost=$7659; Maximum Utilization=46.4%

TELCOM 2110 13

5
 MSTs Are Not Always Optimal Access Designs

• When traffic grows 50%, MST costs

$10,616 and the links to concentrators
N4 and N7 must have two links to keep
utilization below 50%.

TELCOM 2110 14

Access Design Problems

AUC EIR
• Can roughly categorize
HLR
access design problems
VLR
IBM

– One speed one center

Bay Networks Centillion 1400
SD
MSC
design
• For example, local loop in
ETHER LIN K RS232C I NS ACT AL
M
* 8x5
P 0 RST
OOO13 0
AO N
6

PCC ARD

SD

Bay Networks Centillion 1400

ALM
PW R AL
M
FAN0 FAN1 PWR0 PW R1

* 8x5
P 0
ETHER LIN K RS232C I NS ACT AL
M
RST
OOO13 0
AO N
6

PCC ARD

ALM
PWR AL
M FAN0 FAN1 PWR0 PWR1

BSC
BSC

telephone network
SD

Bay Networks Centillion 1400

* 8x5
P 0
ETHER LIN K RS232C I NS ACT AL
M
OOO13 0
RST
AO N
6

PCC ARD

ALM
PWR AL
M FAN0 FAN1 PWR0 PWR1

BSC

– Multi-speed access design

BS3

BS3 BS2 BS4

• For example, LAN design
BS2 BS4 BS1
from variety of hosts
BS1

– Multi-center Design
BS7
BS5

BS7
BS5 BS6

BS6
• For example, cellular
networks with multiple base
station controllers

TELCOM 2110 15

6
 One-speed One-Center Design

Problem: Connecting sites to one backbone node (switch, router)

all links with the same capacity

OR OR

TELCOM 2110 16

Approaches

• Shortest Path Tree (Dijkstra’s Algorithm)

– Expensive, low utilizaton, good delay
• Minimum Spanning Tree (Prim’s Algorithm)
– Cheap, possibly high delay due to longer path length
• Comprise (Prim-Dijkstra Algorithms)
– Better results, harder to determine
• Exhaustive Search (consider all possible trees)
– Cayley’s Theorem: Given n nodes, there are nn-2
different spanning trees.
– For 20 nodes, there are 2018=2.621*1023 different
trees. – obviously this approach won’t scale
TELCOM 2110 17

7
 One-speed One-Center Example

• Problem: Connect a large number of sites

to a hub
– 19 nodes that are to be connected to a hub
– N14 is the hub location
– Up to 4 sites can share a line
– Traffic to and from each node Ni is 1200bps
– Capacity of the links is 9600bps
– Limit the utilization to 50%
• Compare different solution approaches
TELCOM 2110 18

SPT(Star)

• Cost= $26358
• Very low link utilization and expensive

TELCOM 2110 19

8
 MST

• Cost= $18,730
• More cost effective but has higher delays

TELCOM 2110 20

Prim-Dijkstra with α=0.3

• Cost= $15930.
• N11 should connect to N4, Two clusters based at N18 and N9.
• Better results but higher complexity of calculation

TELCOM 2110 21

9
 Capacitated Minimum Spanning Tree (CMST)

• CMST problem:
Given
a center node N0
set of other nodes (N1, …, Nn),
set of weights(w1,…,wn) for each node,
the capacity of each link, W
cost matrix Cost(i,j),
• Find: a set of trees T1, …, Tk such that each Ni belongs to exactly
one Tj and each Tj contains N0 and the following holds

∑w
i∈T j ,i > 0
i < Wi

min ∑ ∑ Cost (end1 , end 2 )

l l
Trees l∈Links
TELCOM 2110 22

The Esau-Williams Algorithm

• Heuristic Algorithm but guarantees the tree meets
the capacity constraint
• Each node starts off in a tree with 1 node.
• Compute the tradeoff function for each node:
Tradeoff(Nk)=minj Cost(Nk, Nj)-Cost(Comp(Nk), Center N0)

– Tradeoff function for merging components Nk and Nj

computes the potential savings of going to a neighbor
instead of going to the center node.
• If the tradeoff is negative, a merge is attractive
• Pick the node with smallest tradeoff value for
merger with nearest neighbor
TELCOM 2110 24

10
 The Esau-Williams Algorithm
• Merger is allowed if the link capacity is not
exceeded – that is weight of nodes less than link
speed
weight(Comp(NK )) + weight(Comp(NJ )) ≤ W

• If the merger is disallowed one moves to the node with

the next smallest tradeoff value
• Algorithm terminates when all tradeoffs are positive or
the list of possible merges is exhausted
• Since Heuristic - solution is not always optimal

TELCOM 2110 25

Esau-Williams Example
• W=3, each node has wi=1
• Tradeoff(1)=minj Cost(N1,NJ)-
Cost(Comp(N1),Center) Initial topology
=minj Cost(N1,N3) - (Comp(N1) dashed lines
contains N0)
=3-5= -2 (pick closest neighbor, N3) 2
• Tradeoff(2)=4-6= -2
• Tradeoff(3)=3-9= -6 8
5
6
• Tradeoff(4)=5-12= -7 4 12 4
• Tradeoff(5)=6-15= -9
7
12
6
• Tradeoff(5) is the smallest 0
15 5

9 6
• Accept link(5,3) merger to the solution
3
since weight constraint on component 5
10 8
tree with nodes 5 and 3 is not violated. 3
Σwi =w5+w3=2<=W=3
1

TELCOM 2110 26

11
 Esau-Williams Example
• Next Iteration
– Tradeoff(1)=3-5= -2
– Tradeoff(2)=4-6= -2 Topology after 1
– Tradeoff(3)=3-9= -6 iteration
– Tradeoff(4)=5-12= -7 2
– Update Tradeoff(5)=7-9= -2
next shortest link out of 5 is (5,4) 8
5
6
(Comp(5)=9,node 5 goes through 4 12 4
node 3 to center)
7
– Tradeoff(5)=7-9= -2 12
6
15 5
0
• Pick Tradeoff(4) as smallest 9 6
• Accept (4,2) merger since 3
weight constraint on component 5
10 8

trees with nodes 4 and 2 is not 3

violated.
Σwi =w4+w2=2<=W=3 1

TELCOM 2110 27

Esau-Williams Example
• Next iteration
– Tradeoff(1)=3-5= -2 Topology after iteration 2
– Tradeoff(2)=4-6= -2
– Tradeoff(3)=3-9= -6 2
– Update Tradeoff(4)=6-6= 0
5
– Tradeoff(5)=7-9= -2 6
8

– Pick Tradeoff(3) 4 12 4
7
• Accept link (3,1) since 12
6
weight constraint on 0
15 5

component 9 6

with nodes 1, 3 and 5 are 5

10 8
3

not violated. 3

Σwi =w1+w3 +w5 =3<=W=3

1

TELCOM 2110 28

12
 Esau-Williams Example
• Next Iteration
– Tradeoff(1)=4-5= -1 Topology after iteration 3
– Tradeoff(2)=4-6= -2
– Tradeoff(3)=6-5= 1 which is Final topology
– Tradeoff(4)=6-6=0
– Since nodes 5 and 3 now go 2
through node 1 to Center,
update Tradeoff(5)=7-5=2 5
8
• Tradeoff(2) is lowest but 6
adding link(2,1) results a 4 12 4
component 7
with 4 nodes violate Σwi<=3. 12
6
• Reject(2,1) 0
15 5
recompute Tradeoff(2)=6-6=0
9 6
• Reject(1,2) similar reason.
Recompute Tradeoff(1)=5-5=0 10 8
3
5
• The access network is complete 3

TELCOM 2110 29

Example 2

• Consider the grid network below.

– This network can occur in a cellular network in a downtown urban
environment. Where the nodes represent base stations and the
hub/central node a base station controller
– For the example Node 0 is the central node.
– The weight of each individual node is 1, except for nodes 4 and 5, which
have a weight of 2. The cost function C(i,,j) is given by the physical
distance between nodes i and j. W=3
– Design a capacitated access tree using Esau-Williams algorithm.

0 1 2
1
3 4 5
1
6 7 8

TELCOM 2110 1 1 30

13
 Example 2
Tradeoff(i)=minj Cost(Ni,NJ) -Cost(Comp(Ni),Center)
Tradeoff(1) = 1 -1 = 0
Tradeoff(2) = 1 -2 = -1
Tradeoff(3) = 1 – 1 = 0
Tradeoff(4) = 1 – sqrt(2) = -.414
Tradeoff(5) = 1 – sqrt(5) = -1.236
Tradeoff(6) =1-2 = -1
Tradeoff(7) = 1-sqrt(5) = -1.236
Tradeoff(8) = 1-sqrt(8) = - 1.828
Pick 8 to merge with either 7 or 5
0 1 2
Pick 7 since it has lower weight = 1 1
Checking capacity w7+w8 = 2 ≤ W = 3 4
3 5
1
6 7 8

1 1
TELCOM 2110 31

Example 2
Iteration 2
Tradeoff(1) = 1 -1 = 0
Tradeoff(2) = 1 -2 = -1
Tradeoff(3) = 1 – 1 = 0
Tradeoff(4) = 1 – sqrt(2) = -.414
Tradeoff(5) = 1 – sqrt(5) = -1.236
Tradeoff(6) =1-2 = -1
Tradeoff(7) = 1-sqrt(5) = -1.236
Tradeoff(8) = 1-sqrt(5) = - 1.236
Pick 5 to merge with node 2
0 1 2
Note node 4 or 8 merge is not allowed 1
by capacity constraint 4
3 5
Checking capacity w5+w2 = 3 ≤ W = 3 1
6 7 8

1 1
TELCOM 2110 32

14
 Example 2
Iteration 3
Tradeoff(1) = 1 -1 = 0
Tradeoff(2) = 1 -2 = -1
Tradeoff(3) = 1 – 1 = 0
Tradeoff(4) = 1 – sqrt(2) = -.414
Tradeoff(5) = 1 – 2 = -1 – not allowed
Tradeoff(6) =1-2 = -1
Tradeoff(7) = 1-sqrt(5) = -1.236
Tradeoff(8) = 1-sqrt(5) = - 1.236
Pick 7 to merge with node 6
0 1 2
Note node 4 is not allowed by capacity 1
constraint 4
3 5
Checking capacity w6+w7 + w8= 3 ≤ W 1
6 7 8

1 1
TELCOM 2110 33

Example 2
Iteration 4
Tradeoff(1) = 1 -1 = 0
Tradeoff(2) = 1 -2 = -1 not allowed
Tradeoff(3) = 1 – 1 = 0
Tradeoff(4) = 1 – sqrt(2) = -.414
Tradeoff(5) = 1 – 2 = -1 not allowed
Tradeoff(6) =1-2 = -1 not allowed
Tradeoff(7) = 1-2 = -1 not allowed
Tradeoff(8) = 1-2 = -1 not allowed
Pick 4 to merge with node 3 or 1
0 1 2
Checking capacity w3+w4 = 3 ≤ W 1
Note all allowed merges have positive 4
3 5
Tradoffs so final topology with cost 10 1
6 7 8

1 1
TELCOM 2110 34

15
 Esau-Williams Algorithm

• How Good is solution?

1-exchange test: Given a set of sites N and a
capacitated tree T, we check that no cheaper
link can be substituted for an existing link
without violating the capacity constraints.

TELCOM 2110 35

Esau-Williams and Inhomogeneous Traffic

• Algorithm does
as well if the sites
have a variety of
different traffic.
• Links are
9600bps
• 50% of sites
require 2400bps
• Others require
4800bps

TELCOM 2110 36

16
 Line Crossings in Access Designs

• A 20 node Esau-Williams design – sometimes has line crossings

TELCOM 2110 37

Sharma’s Algorithm

• Heuristic algorithm to create networks with no lines crossing

Useful when physical constraints (duct for running cable) dictate
that no lines cross
1. Compute the angle θs from each site S to the central site C. If S and
C have the same coordinate, set θs = 0.
2. Sort the angles θs from smallest to largest
3. Beginning at a site Sfirst, create a set of nodes clockwise (or
counterclockwise) from Sfirst. A set is complete when adding the
next node would put Σsetw(site) > W. The next set starts with that
node.
4. The design is completed by building a MST on each set with the
addition of the central node C.
Comment
If the angles θs are distinct, then if the cost function is a linear or
piecewise linear metric, Sharma’s algorithm builds CMSTs without
crossings provided that all the central angles are less than π.

TELCOM 2110 38

17
 Example of Sharma’s algorithm

• Consider the grid network below.

– This network can occur in a cellular network in a downtown urban
environment. Where the nodes represent base stations and the
hub/central node a base station controller
– For the example Node 0 is the central node.
– The weight of each individual node is 1, except for nodes 4 and 5, which
have a weight of 2. The cost function C(i,,j) is given by the physical
distance between nodes i and j. W=3

0 1 2
1
3 4 5
1
6 7 8

TELCOM 2110 1 1 39

Example of Sharma’s algorithm

Angle of each node

θ1 = 0,
θ2 = 0
θ3 = -90
θ4 = -45
θ5 = -22.5
θ6 = -90
θ7 = -72.5
θ8 = -45 0 1 2
1
Sorted angles
3 4 5
{θ1 θ2 θ5 θ4 θ8 θ7 θ3 θ6 } 1
6 7 8

1 1
TELCOM 2110 40

18
 Example of Sharma’s algorithm

From Sorted angles {θ1 θ2 θ5 θ4 θ8 θ7 θ3 θ6 }

Form Sets {θ1 θ2 } note θ5 not included
because sum of weight of nodes would
exceed capacity constraint.
{θ1 θ2 } , { θ5 θ8}, { θ4 θ7}, { θ3 θ6}

Running MST for each set yields the

following topology
Cost of topology is 11 which is 0 1 2
1
greater than E-W design but no
4
crossed lines. 3 5
1
6 7 8

1 1
TELCOM 2110 41

Sharma’s Algorithm Example

Consider 20 node network, node 16 is hub, W = 4
Working counter clockwise on angles Sorted Angles
17
19 13
12
5
18
6
5
1
6 8
1
14 18 19
14
13
9 12
8
17 9
4
15
11 0 15
7
16 3 2
10
10 3
7 4
2 11
0
TELCOM 2110 42

19
 Sharma’s Algorithm Design
• Cost= $16021, Sfirst = N17

TELCOM 2110 43

The Creditability of Sharma Designs

• Designs look nice but most of them fail the
creditability test.
• Much higher failure rate than Esau-Williams’.

TELCOM 2110 44

20
 Sharma vs. Esau-Williams
• EW_Ratio=SharmaCost/EWCost;
S_Ratio=EWCost/SharmaCost
• In general use Esau- Williams unless require no lines cross

TELCOM 2110 45

Access Design

AUC EIR • Considered One

HLR IBM

VLR
speed one center
MSC design
Bay Networks

* 8x5
P

AO N
6
0
OOO13 0
RST

PW R
ETHER

AL
M
LIN K RS232C

ALM
FAN0 FAN1 PWR0 PW R1
I NS ACT AL
M

PCC ARD
Centillion 1400
SD

Bay Networks

* 8x5
P

6
0
OOO13
AO N
0
RST

PWR
ETHER

AL
M
LIN K RS232C

ALM
FAN0 FAN1 PWR0 PWR1
I NS ACT AL
M

PCC ARD
Centillion 1400
SD

• Local loop in
telephone network
BSC
BSC
SD

Bay Networks Centillion 1400

* 8x5
P 0
ETHER LIN K RS232C I NS ACT AL
M
OOO13 0
RST
AO N
6

PCC ARD

ALM
PWR AL
M FAN0 FAN1 PWR0 PWR1

• Cellular network
BSC

BS3 BS2
BS3

BS4
connecting BS to BSC
BS2

BS1
BS4 BS1
• LAN, host to hub or
switch
BS7
BS5

BS7
BS5 BS6

BS6

• Two algorithms
1. Esau-Williams
2. Sharma
TELCOM 2110 46

21