An Efficient Protocol for Call Setup and Path Migration in IEEE 802.6 Based Personal Communication Networks.
AbstractRecently, DQDB (IEEE 802.6) MAN has been proposed as a component of Personal Communication Networks, in which base stations of wireless infrastructures are connected by a number of DQDBs which in turn are connected via bridges. We propose a protocol for call setup and path migration in a cluster of DQDBs. The protocol uses a link-state-like routing method for path selection and a source-routing-based scheme for path establishment. In addition, we propose a labeling scheme that makes it possible to carry the path information needed by the source routing protocol in a single 53-octet DQDB slot. Without such a labeling scheme, source routing would be inefficient for our purpose.
Introduction
Personal Communication Networks (PCN) provide ubiquitous communication coverage, enabling
people to call people, regardless of physical locations [7, 9]. The coverage area of PCN is divided
into radio cells, each having a Base Station (BS) to exchange radio signals with mobile hosts.
Base stations are connected by wired networks to exchange control information.
Recently, the IEEE 802.6 Distributed Queue Dual Bus (DQDB) MAN has been proposed
as a component of PCN [9, 10, 14]. A typical DQDB-based PCN infrastructure is illustrated in
Fig. 1, where BS's are connected by DQDBs, and DQDBs are connected by MAN bridges to form
a cluster. Clusters of DQDBs are connected to ATM networks via gateways. It is believed that
the compatibility between the IEEE 802.6 DQDB MAN and ATM cell structures will simplify the
interworking between DQDBs with ATM networks [14].
In an IEEE 802.6 DQDB MAN [11], the basic unit of data transfer is 53-octet slot. There
are two kinds of slots: Queued Arbitrated (QA) slots and Pre-Arbitrated (PA) slots. PA slots
are used to transfer isochronous service octets. A PA slot consists of a 20-bit virtual Channel
isochronous service octets. An isochronous service octet is specified by
(vci,loc), where vci is the VCI of the PA slot and loc is the location of the isochronous service octet
in the PA slot. As PA slots are periodically generated, an isochronous channel can be supported
by a sequence of isochronous service octets specified by (vci, loc). Each DQDB has a bandwidth
manager (BMN) in charge of reservation and release of isochronous channels.
We assume that each voice call is supported by a "path." Depending on the caller's and
callee's locations in the PCN, a path may be in one of three forms:
ffl If the caller and the callee are in the same DQDB, the path consists of only that DQDB.
An isochronous channel in that DQDB suffices to support the call.
ffl If the caller and the callee are in different DQDBs of the same cluster, a path will be a
sequence of adjacent DQDBs (two DQDBs are adjacent if they are connected by a bridge).
In this case, setting up the path entails reservation of an isochronous channel in each DQDB
on the path.
ffl If the caller and the callee are in different DQDB clusters, a path will consist of three parts:
a subpath in the caller's DQDB cluster, a virtual connection in the ATM backbone network,
bandwidth manager
MAN bridge
base station
Networks
Gateway
A cluster of DQDB MANs
(a) PCN infrastructure (b) A cluster of DQDB MANs

Figure

1: PCN infrastructure: ATM networks and peripheral DQDB subnetworks.
and a subpath in the callee's DQDB cluster. The path is set up if and only if all of the three
subpaths are set up and put together.
To set up a path to a mobile host, it is necessary to first find out its location. Many schemes have
been proposed for this problem (e.g., [15]).
In this paper, we assume that the callee has been located and we are in the process of setting
up a path. As setting up virtual connections in ATM networks has been widely discussed in the
literature (e.g., [17]), we will focus on the setup of a path (or subpath) in a cluster of DQDBs. As
mentioned above, such a path passes through one or more DQDBs and requires an isochronous
channel in each of the DQDBs (on the path). As there are only a limited number of isochronous
channels in each DQDB, it is desirable to select an "efficient" path for each voice call so that more
calls can be supported. A nontrivial question is, what paths are efficient? Intuitively, a shorter
path seems more efficient than a longer one since it consumes a smaller number of isochronous
channels. We will argue that that is not necessarily true. For instance, a longer path avoiding
all congested areas might be more efficient than a shorter one that goes through congested areas.
We will define efficient paths, taking into consideration the issue of congestion control.
For at least two reasons an efficient path may become inefficient while the call is still in
progress. First, an efficient path may become inefficient when traffic changes. Second, when the
caller or the callee roams from the area covered by a DQDB to the area covered by another DQDB
(a phenomenon called inter-DQDB handoff), the path that supports the call must be extended
from the current DQDB to the new DQDB; i.e., a path between the current and the new DQDBs
must be established and connected to the old path. As the mobile user moves from DQDB to
DQDB and the path is extended and extended, the path is likely to become inefficient. (In the
extreme case, the path will contain a loop if a mobile user moves back to a DQDB on its original
path.) When a path becomes inefficient for whatever reason, it is desirable to replace it with a
more efficient one. This process, called path migration, is considered a challenging problem [10].
Huang and Chen [13] proposed a solution to the path migration problem. In their scheme,
called distributed parallel branch and bound (DPBB), each DQDB bandwidth manager (BMN)
maintains a routing table that, as in the distance vector routing method, records shortest distances
to other DQDBs via neighboring DQDBs. To establish a new path, a search message is selectively
flooded over the DQDB cluster. The DPBB scheme has several drawbacks: (1) it selects paths
without consideration of congestion control; (2) it reserves a large number of isochronous channels
in the process of parallel search; (3) path setup is slow due to the "stop and consult" routing
without an efficient way to specify paths, the scheme often requires multiple DQDB
slots to deliver a message, further slowing down the path migration process.
In this paper, we propose an efficient path setup and path migration protocol that overcomes
all of the above mentioned drawbacks. In the proposed scheme, a link-state-like routing method
is used for path selection, and a source-routing-based protocol for path establishment. To set up
a path, the BMN at the caller's DQDB first selects an ``efficient'' path to the callee's DQDB,
and then sends out a setup message along the selected path, which is specified in the message.
For path selection, it is desirable that the selected path avoid congested areas and its length be
minimized. We define efficient paths with the considerations of traffic condition and resource
requirement so that the selection of the most efficient path will achieve both congestion control
and better resource utilization. For path establishment, it is desirable that the setup message
be specified in a single 53-octet slot, or the message will have to be repeatedly assembled and
disassembled at each bridge along the path. If a path is specified as a sequence of MAN IDs and
bridge IDs, as in the case of IEEE source routing bridges, it will be very hard to fit into a DQDB
slot. To attack this problem, we propose a method to considerably shorten the length of path
specifications. A path will be specified as a sequence of labels, each of which uniquely denotes
the flow from a DQDB to a neighboring DQDB. Because of the locality property of the labels,
each label can be uniquely represented by a few bits. Consequently, a path consisting of dozens
of DQDBs can be easily specified in a single DQDB slot.
To evaluate the performance of our path setup and migration protocol, we compare it with the
DPBB scheme. Our simulation results show that the proposed protocol considerably outperforms
the DPBB scheme in terms of blocking rate and path setup delay. Besides, our scheme is far
simpler than DPBB, which, we believe, is a big advantage.
The paper is organized as follows. The Distributed Parallel Branch and Bound scheme is
briefly discussed in section 2. Section 3 introduces the path setup protocol. Second 4 proposes
the new labeling scheme. Path migration is discussed in section 5. Simulation results are shown
in section 6. Section 7 concludes the paper.
Previous Work
The Distributed Parallel Branch and Bound (DPBB) scheme for path migration has been proposed
for the IEEE 802.6 based PCN [13]. We briefly review this scheme and discuss its drawbacks.
2.1 The DPBB Scheme
The DPBB scheme is based on the distance-vector routing algorithm. Each DQDB i maintains
at its BMN a routing table RT i and a path table PT i . The routing table RT i is a set of distances
ij denotes the cost of the shortest path from DQDB i to DQDB j via neighboring
DQDB k. There is an entry in the table for each destination DQDB, j, and each neighbor, k, of i.
Each BMN attempts to maintain the up-to-date routing table by exchanging information with its
counterparts in the neighboring DQDBs. The path table PT i keeps information about the paths
currently in use. For each call originated from DQDB i, there is an entry
in PT i , where PID is the path identifier, DCA is the destination DQDB address, and c ij is the
cost of the path. When a path is extended because of the inter-DQDB handoff occurred to the
destination mobile host, the source BMN will be notified by the new destination BMN, and the
corresponding entry in the path table will be updated to reflect the current destination address
and current cost of that path. When a path is extended because of the inter-DQDB handoff
occurred to the source mobile host, a new entry will be added to the path table of the current
source BMN and the corresponding entry in the previous source BMN will be deleted.
Periodically, the BMN of DQDB i examines tables RT i and PT i to recognize inefficient paths
originated from i. A path p ij is deemed inefficient if
ij for some k. Such a neighbor v k is
called a candidate migration vertex. (Each vertex represents a DQDB.) Once an inefficient path
is recognized, a so-called parallel branch-and-bound procedure is invoked to search for a more
efficient path. Specifically, a search message is flooded to all the candidate migration vertices.
When an intermediate BMN a receives the search message, it reserves an isochronous channel in
its DQDB, searches its routing table, and forwards the search message to (the BMNs of) all of its
candidate migration vertices. Thus, it is DQDB BMNs, not bridges, that route messages from the
source DQDB to the destination DQDB. As a search message travels toward the destination, it
records the path traversed. On receiving the first copy of a search frame, the destination DQDB
BMN sends a confirm message back to the source DQDB BMN, by way of the path recorded in
the first arrived search frame. When the source DQDB BMN receives the confirm message, it can
migrate the traffic from the old path to the new one.
2.2 Drawbacks of the DPBB Scheme
The distance vector routing method, on which the DPBB scheme is based, is well known to have
the drawback of forming short-lived and long-lived loops [5]. This is because nodes choose their
next-hops in a completely distributed fashion based on possibly stale or even incorrect information.
There are loop avoidance techniques available in the literature; they normally require inter-node
coordination. The DPBB scheme alleviates the loop as well as stale information problem by
parallel search. There are, however, still several drawbacks, which we discuss in the following.
First, there is no congestion control in DPBB. The goal of the scheme's parallel search is
to locate a shortest path, regardless of its traffic condition. Some DQDBs may be congested in
the sense that they have only few available isochronous channels. Unless really necessary, a path
should get around such DQDBs. Unnecessarily passing a congested DQDB, just because it is
shorter, will worsen its congestion and increase the chance of later being unable to support a new
call from or to a station in that DQDB. For instance, suppose DQDB i has only one available
isochronous channel, and suppose there are two possible paths from A to B. Path 1 has i as an
intermediate DQDB and path 2 doesn't pass through any congested DQDB. Even if path 1 is
much shorter that path 2, we should choose path 2. The only channel available in DQDB i should
be saved for a call that originates from or destined for DQDB i.
Second, isochronous channels may be unnecessarily reserved in the search process. Each
DQDB BMN reserves an isochronous channel when it receives a search message. Once reserved,
the channel is not available for any other path until it is released. Given that search messages are
normally forwarded through multiple paths, isochronous channels are reserved in a lot of DQDBs,
many of them unnecessary (a reservation in a DQDB is unnecessary if that DQDB is not on the
selected path). This kind of reservation is undesirable especially on congested DQDBs.
Third, both DQDB BMNs and bridges are involved in passing search messages. A search
message is sent from the source BMN to a bridge via QA slots. The bridge then forwards the
message to the BMN of the next DQDB, again using QA slots. The later BMN consults its
routing table and forwards the search message to appropriate bridges, and so forth. This "stop
and consult" routing style is slow and may degrade the quality of service during inter-DQDB
handoff.
Last, in the DPBB scheme, a search message has to record the path it traversed, and a
confirm message has to specify the entire return path. Without an efficient path representation
method, one DQDB slot may not be long enough to carry the path information. Multiple DQDB
slots may be required to deliver a message, which will further slow down the path setup process.
A path must be set up before two parties can start communication or path migration can take
place. Conceptually, path setup involves two tasks: path selection and path establishment.
Path selection is to decide on a sequence (DQDB
goes from the caller's DQDB to the callee's. Path establishment is to reserve an isochronous
channel in each DQDB on the selected path, and to add an entry to the VCI conversion table in
each bridge on the path. The two tasks may be carried out together at one time, or they may be
done separately (and sequentially). In either approach, it is important to select an efficient path
and to establish it quickly without unnecessary reservation of isochronous channels.
Efficient path selection is a key to reducing the call blocking rate. A call is blocked if it doesn't
get the needed channels. Given that there are only a limited number of isochronous channels in
a cluster of DQDBs, the previous work [13] attempts to choose a shortest path for each call so
as to minimize the number of isochronous channels consumed. This strategy, in a sense, assumes
the same cost for all isochronous channels in all DQDBs. Its flaw is obvious, for isochronous
channels in congested DQDBs are definitely more expensive than those in non-congested areas
and should be used more discriminately. As in other networks, traffic conditions must be taken
into consideration in path selection.
Fast path establishment is important in terms of the quality of service in real time mobile
communications. As mobile hosts roam from one DQDB to another, fast path extension and path
migration are essential to supporting smooth inter-DQDB handoffs. Otherwise, users will feel the
degradation of the quality of service.
It is a desired property that no isochronous channels be unnecessarily reserved during the
setup process.
In this section, we propose a path setup protocol that enjoys the above desired properties.
We first discuss the pros and cons of various routing schemes that could be used for path selection.
Then we describe a link-state-like routing algorithm and offer a new definition of efficient path.
Last, we propose a source-routing-based protocol for fast path establishment without reserving
too many isochronous channels.
3.1 Different Approaches to Routing
The basis of any path selection scheme is a routing algorithm. In search for an appropriate routing
algorithm for our setting of networks (DQDB MANs connected by bridges), four widely used
methods immediately recommend themselves: the spanning-tree routing algorithm as adopted by
the IEEE 802.1 group, the source routing algorithm as developed by the IEEE 802.5 committee,
the distance-vector routing algorithm, and the link-state routing algorithm. We examine each of
these methods in the following.
Transparent bridges and source routing bridges are the two IEEE standardized routing
bridges. The spanning-tree routing algorithm assumes that LANs or MANs are connected by
transparent bridges [3]. A spanning tree is constructed on a bipartite graph where each node
represents a LAN or a bridge. All messages are delivered via edges of the tree. As such, there is a
fixed path between any two LANs (there is a unique path between any two nodes on a tree). That
is, for any pair of source and destination LANs, the spanning-tree routing algorithm always uses
the same path for message delivery (unless the topology of the internetwork changes). The inefficiency
of relying on fixed paths on a spanning tree, regardless of traffic conditions and without
load balancing, is obvious even for regular bridged LANs. In a cluster of DQDBs which serves as
a component of the personal communication network, the performance degradation due to such
inefficiency in routing will be even more severe (because each DQDB only has a limited number of
isochronous channels for isochronous service). Transparent bridge and its accompanying spanning
tree routing algorithm are thus not suitable for our application.
The source routing algorithm assumes that LANs or MANs are connected by source routing
bridges [8]. When a source station sends a frame, it specifies how the frame is to be routed. There
are four different routing directives [18]: null, nonbroadcast, single-route broadcast, and all-route
broadcast. An optimal path from the source station to a destination can be found by all-route
broadcast. For example, the source node can send a request frame to the intended destination
using all-route broadcast directive. The frame is thus routed through all possible paths to the
destination; along the way, each copy of the frame records the route it takes. On receiving each
of these frames, the destination returns a response frame along the recorded path. The source
then chooses an optimal path and records it in a routing table. Later on the source's messages to
that destination can be routed through that specific path, using the nonbroadcast directive. The
quality of the paths taken by nonbroadcast frames depends on the frequency of update to the
routing table. Given the instantaneous change of traffic conditions over the LANs or MANs, unless
the update is extremely frequent (which unfortunately is expensive and undesirable), the paths
recorded in the routing table are most likely to be outdated and inefficient. In our application, an
outdated path may even not be available any more because of the sudden lack of an isochronous
channel in an intermediate DQDB.
Distance vector and link-state are two general next-hop routing approaches [4]. In the distance
vector routing approach, each node maintains a routing table of the shortest distance to
other nodes through its neighboring nodes. By periodically exchanging information with its neighboring
nodes, each node attempts to keep its routing table up-to-date. Although the distance
vector approach is computationally more efficient, easier to implement and requires less storage
space than the link-state approach, it is well known that it can cause the formation of routing
loops because each node updates its routing table in a distributed fashion based on possibly stale
or even incorrect information [5]. When applied to a cluster of DQDBs, the distance vector ap-
DQDB node
bridge node
DQDB Status Table Cluster Graph

Figure

2: Each DQDB BMN maintains the DQDB status table and the cluster graph
proach naturally resulted in a scheme like DPBB [13]. As discussed in the previous section, it has
several drawbacks.
In the link-state approach, each node maintains a view of the network topology with a cost
for each link. Periodically, each node broadcasts the costs of its outgoing links to all other
nodes using a protocol such as flooding. Once a node receives this information, it updates its
view of the network topology and computes an optimal path to each destination. The link state
method has been used in various wide-area networks, where its major drawbacks are relatively
high communication cost for maintaining up-to-date link state information and relatively high
computation cost for computing optimal paths.
Each routing scheme has its strengths and weaknesses. When a scheme is applied to a cluster
of DQDBs, some of its strengths and weaknesses may become non-substantial. A desired routing
scheme for our purpose is one that, when applied to a cluster of DQDBs, keeps its strengths but
circumvents the weaknesses. Of the four schemes surveyed above, only the link-state approach
seems to have this property. We will show that it indeed does, and will choose it as the basis of
our path selection protocol.
3.2 Selecting Efficient Paths
We propose a link-state-like routing scheme that enables DQDB BMNs to compute optimal paths
without incurring high communication/computation costs. The basic idea is to keep the number
of state changes small. To this aim, each DQDB BMN maintains a DQDB status table and a
cluster graph (Fig. 2). The DQDB status table records the current state of each DQDB, while
the cluster graph indicates the current topology of the DQDB cluster.
CONGESTED
av >=
d
d
av <= 1av > 0

Figure

3: DQDB status transition graph (av:available channels).
Depending on the number of isochronous channels still unused, a DQDB is in one of three
possible states: NORMAL, CONGESTED, or FULL. Initially, each DQDB is in NORMAL state.
When the number of available channels decreases and reaches a threshold the DQDB's state
changes from NORMAL to CONGESTED. In CONGESTED state, if the number of isochronous
channels increases to the DQDB changes state from CONGESTED to NOR-
MAL. (Notice that the two thresholds are distinct. The reason for this is that a state
transition from CONGESTED to NORMAL is likely to cause a surge of requests for isochronous
channels in that DQDB. It is important to have a small pool of isochronous channels to smooth
the sudden surge of requests. By making ffi 2 larger than ffi 1 , we prevent the DQDB from frequently
moving forth and back between NORMAL and CONGESTED.) The DQDB changes state from
CONGESTED to FULL when the number of available isochronous channels drops to zero; and
it changes from FULL to CONGESTED when the number of available isochronous channels is
greater than 0 (Fig. 3).
Whenever a DQDB changes state, the new state is broadcast to other DQDBs. The above
design was aimed at reducing the number of state transitions. There are two advantages in doing
this: (1) the cost of broadcasting state information will be considerably reduced; (2) the DQDB
status tables will be accurate for most of the time. It is an important design issue on how to
choose the values for ffi 1 and ffi 2 . We will show in section 6 that difference values of ffi 1 and ffi 2 have
great impact on the system performance.
The cluster graph is the graphical representation of the current topology of the the DQDB
cluster. It is an undirected bipartite graph
is the set of DQDBs and the set of bridges. An edge e ij exists between a
DQDB node d i and a bridge node b j if and only if bridge b j is attached to DQDB d i . Note that
a bridge may attach to more than two DQDBs.
With such a graph representation, a path is simply a sequence of DQDBs and bridges,
is a DQDB and b i a bridge connecting DQDB d i\Gamma1 and
DQDB d i . For bridge b i , d i\Gamma1 is its previous DQDB, and d i its next DQDB. d 0 is the source
DQDB and d n the destination DQDB. We define the length of the path to be n.
new path can be set up that includes a FULL DQDB. We thus define a (new) path to
be feasible if none of the DQDBs on the path is FULL. A feasible path could be congested or
non-congested. It is congested if at least one of the DQDBs on the path is CONGESTED; it is
non-congested if all DQDBs on the path are NORMAL.
Given two feasible paths P and Q between the same source and destination nodes,
path P is more efficient than path Q if
ffl P is non-congested and Q is congested; or
ffl P is shorter than Q if both are non-congested.
ffl P contains fewer congested DQDBs than Q if both are congested.
Thus, a non-congested path is more efficient than a congested one; and the most efficient path
between two DQDBs is the shortest non-congested path between them, or the path containing the
smallest number of congested DQDBs if there is no non-congested path between the two DQDBs.
The above definition of efficient path is different from that of [13] mainly in that here we take
into consideration the traffic condition along a path, while [13] considers only its length.
When a new path to a destination DQDB is needed, the source BMN will compute the most
efficient path to the destination. By selecting the most efficient path, congested DQDBs are
avoided unless there is no non-congested path, and least congested DQDBs will be selected in the
new path. This way, the few isochronous channels still available in a congested DQDB are saved
for those calls which really need these channels, for instance, the calls originated from or destined
for that DQDB.
To facilitate the computation of most efficient paths, we assign a weight or cost to each edge
as follows:
where T is an integer greater than the maximal length of any paths. The most efficient path
between two DQDB nodes is simply the shortest weighted path between them. Such a path can
be computed in O(jEj) time.
3.3 Fast Path Establishment
As was remarked earlier, fast path establishment is important in real time mobile communications.
The issue here is how to quickly forward the path request message from the source DQDB to the
destination DQDB. Using a next-hop approach as in the original link-state or distance-vector
routing algorithm will suffer the "stop and consult" problem as described in the third item of
Section 2.2. Thus, we propose to use a source-routing-based protocol for path establishment,
assuming that DQDBs are interconnected via source routing bridges.
A path request message, carrying specification of the selected path
is forwarded from the BMN of d 0 to bridge b 1 using QA slots on DQDB d 0 . After that, the
message is forwarded from bridge to bridge along the specified path, without consulting BMNs
of the intermediate DQDBs. When b i forwards the message to b i+1 (via DQDB d i ), the BMN
of d i also receives a copy of it. BMNs are responsible for channel reservations, but they are not
involved in forwarding the message. A major problem in the proposed source routing protocol is
how to specify a path in a 53-octet DQDB slot. As the physical address of a DQDB or bridge is
multi-byte long, it is not easy to accommodate the specification of a whole path in one slot. For
clarity in presentation, we defer this issue until the next section. Here we assume it is possible to
carry each message in one slot and describe the path establishment protocol.
Four types of messages are used: request, confirm, abort and release. The request message
is used by the source DQDB BMN to establish a path. The destination DQDB BMN will reply
with a confirm message if the path establishment is successful. Any DQDB BMN on the path
may generate an abort message if it is not able to reserve an isochronous channel for this path. A
release message is issued by the source or destination DQDB BMN when the communication is
over.
Each message carries the information: [P ID; path; length; counter]. PID is the path iden-
path is a sequence of "labels" that specifies the selected path; length is the length of the
selected path; and counter, updated by each bridge on the path, indicates which "label" in the
path specification is to be used by the next bridge.
As in the DPBB scheme, the BMN of each DQDB maintains a path table PT i that records
the already-established paths originating from DQDB i. Each entry in PT i is a tri-tuple
is the path identifier, DCA is the destination DQDB address, and
ij is the cost of the path. When a path is established, the source DQDB BMN will add a new
entry to the path table. When a path is released, the corresponding entry is removed from the
table.
Each bridge has a mapping table. It has an entry (PID, vci 0
, loc 00
for each path that
has been established and that passes through the bridge. Here, PID is the path identification;
indicates the location of the isochronous service octet in an incoming PA slot; and
(vci 00
indicates the location of the isochronous service octet in an outgoing PA slot.
Messages are processed at bridges and DQDB BMNs on the specified path as follows:
request message:
When a DQDB BMN receives a request message, it reserves an isochronous channel in that
DQDB. If unable to reserve a channel, the BMN sends an abort message to the source and
destination DQDB BMNs by way of the path being constructed. The destination DQDB
BMN generates a confirm message after it has successfully reserved a channel (or an abort
message if it fails to make a reservation).
When a bridge receives a request message, it first checks if it is on the path carried by
the message. If so, a temporary entry of the mapping table is created and the message is
broadcast to the next DQDB on the path.
ffl confirm message
When a bridge on the path receives a confirm message, it waits until the channel reservations
in its previous and next DQDBs are successful. Then it copies the temporary entry into its
mapping table and the message is forwarded to its previous DQDB.
When the source DQDB BMN receives a confirm message, the path is established and the
communication can start.
ffl abort message
When a DQDB BMN receives an abort message, it releases the channel reserved for the
path.
When a bridge on the path receives an abort message, it deletes the (temporary) entry of
the mapping table, and forwards the message.
ffl release message
When a DQDB BMN receives a release message, it releases the channel reserved for the
path.
When a bridge receives a release message, it deletes the entry from the mapping table and
forwards the message to next DQDB.
3.4

Summary

In summary, we have proposed a protocol for path selection and path establishment. It has the
following desirable properties compared with the DPBB scheme.
ffl Congestion Control: Source DQDB BMN selects the most efficient path with the consideration
of congestion control. Congested DQDBs are avoided whenever possible.
Fast Setup: With the selected path specified in the path request message, the message is
forwarded from bridge to bridge, without involving the BMNs of the intermediate DQDBs.
parallel search, no isochronous channels are unnecessarily
reserved.
4 Labeling Scheme
The efficiency of the proposed source-routing-based protocol for path establishment hinges on the
assumption that each message can be accommodated in a DQDB slot. If it takes more than one
DQDB slot to carry a message, the message will need to be assembled and disassembled at each
bridge along the path, which will slow down the process of path establishment. Examining the
content of each type of message used in the proposed protocol, we find that path is the only field
that may be too long to fit in a slot.
An offset routing protocol [1, 14] was proposed to alleviate this problem. Instead of listing
the full physical address of each network segment, only an offset (i.e. a part) of it is used to
achieve a shorter path representation. There are two drawbacks of the "offset" method. First,
the effectiveness of the method is unpredictable. For this scheme to work, the set of offsets must
be unambiguous. It is possible that, given a set of physical addresses, the only unambiguous set
of offsets is the set of the physical addresses itself. Second, the set of offsets is liable to change in
network topology. An addition of a new network segment may introduce ambiguity and entails
the selection of a new set of offsets.
We propose a labeling scheme that will considerably shorten the path representation. A path
that goes from DQDB d 0 to DQDB d n by way of bridges b 1
will be represented by a sequence of n labels L=(l serving as a routing
direction from DQDB d i\Gamma1 to DQDB d i via bridge b i . A routing direction (label) l i should
unambiguously indicate an ordered pair (d scheme along this line of
reasoning would be assigning a unique label to each ordered pair (p; q), where p and q are any two
DQDBs interconnected by a bridge. If bridge i has k i ports, i.e., it is attached to k i DQDBs, this
approach will require
different labels, where i ranges over all bridges in the cluster
of DQDBs in question. The problem with this straightforward label assignment is that each label
has to be globally unique in the cluster. In the following, we present a simpler labeling scheme
that can be done locally and independently at each DQDB. As before, the scheme assigns a label
to each ordered pair of DQDBs, but it does not require cluster-wise uniqueness.
Consider a k-port bridge attached to k DQDBs. For each DQDB connected to the bridge,
there is a Bridge Interface Unit (BIU) in the bridge that is responsible for receiving slots from
that DQDB and, if necessary, forwarding them to other DQDBs. For example, in a three-port
bridge (Fig. 4), BIU 0 inspects every slot on DQDB d 0 and only forwards those slots whose next
hop is DQDB d 1 or DQDB d 2 .
Each DQDB is connected to a certain number of other DQDBs via bridges. Consider a DQDB
d 0 which is connected with m other DQDBs, d . For each DQDB d i
which is connected to d 0 by bridge b i , a BIU in b i is responsible for routing slots from DQDB d 0
to d i . (Note that b i and b j will refer to the same bridge if d i and d j are both connected to d 0
via the same bridge.) There are exactly m "outlets" from d 0 to its neighboring DQDBs, namely,
message posted to d 0 , if it is not destined for a station in d 0 , will be
d
d
BIU
BIU
BIU1d
bridge2
Figure

4: A three-port bridge and BIUs.
forwarded to one of its neighboring DQDB via one of these outlets. Our labeling scheme assigns
a label l i to each outlet (d are all different. In practice, these labels
will be assigned by the BMN of d 0 . For simplicity, we will say that these labels are defined by d 0 .
A label defined by a DQDB, d, represents a tri-tuple (d, b 0 , d 0 ) which indicates the unidirectional
flow of slots from d to d 0 via bridge b 0 . All the labels defined by the same DQDB share one
common feature: they indicate the traffic flow from this DQDB to neighboring DQDBs through
attached bridges. It is important that labels defined by the same DQDB are all distinct. However,
there is no need to distinguish between labels defined by different DQDBs. Even if two labels
defined by different DQDBs are identical, they will not raise ambiguity because they are used in
different DQDBs. Thus, our labeling scheme requires only local uniqueness. We refer to this as
the locality property of the labeling scheme, in the sense that labels can be locally defined.
It is the locality property of the labels that makes it possible to denote each label with only a
few bits. Suppose there are k DQDBs, say d in a cluster, and each DQDB d i needs
to distinguish between s i labels. Our labeling scheme will need no more than logfmax s i g bits.
Thus, with four bits for each label, for instance, our scheme will allow each DQDB to connect to
up to 16 two-port, or eight three-port, bridges.
Since a path a flow from the source DQDB to the
destination DQDB via n bridges, it can be represented as a sequence of n labels
n) is defined by DQDB d j \Gamma1 and represents the tri-tuple (d j
example, in Fig. 5, path represented as defined
by DQDB d i\Gamma1 and it denotes the unidirectional flow of slots from DQDB d i\Gamma1 to DQDB d i via
d
l
l
d2

Figure

5: Labeling: a path is sequence of labels.
bridge b i Consequently, a path can be easily fit into a DQDB slot using the proposed
labeling scheme. For example, suppose 20 bytes in a DQDB slot are used to specify the path and
each label is specified by four bits, then a path as long as 40 (20   8=4) can be specified in a single
slot using four-bit labels.
Now we establish the correctness of the proposed labeling scheme.
l is a label for the tri-tuple (d; b; d 0 ).
Definition 3 Two labels l 0 and l 00 are successive with respect to DQDB d if there exist DQDBs
00 such that l
Definition 4 A sequence of labels with respect to DQDB d 0 if there
are DQDBs d are successive with respect to d i\Gamma1 for all
Hence, a path of length one is specified by a single label; a path of length two is specified by
two adjacent labels; and a path of length n by a legal sequence of n labels. We prove that, given
the set of all possible legal sequences of labels with respect to DQDB d and the set of all possible
paths starting at DQDB d, there is a one to one correspondence with the two sets.
Theorem 1 Each path can be specified by one and only one legal
sequence of labels with respect to d 0 .
Proof. By induction. When
specified by l 1 . Assume it is true for any k ! n.
Given a path we know, from the hypothesis, that there is one and
only one legal sequence of labels L 0
respect to d 0 that specifies the subpath
l n are successive
with respect to DQDB d n\Gamma2 , one and only one legal sequence of labels
that specifies path P .
Theorem 2 Each legal sequence of labels respect to DQDB d 0 uniquely
defines a path.
Proof. According to the definition of legal sequence of labels, there are DQDBs d
bridges such that 8i, l
is the path specified by the legal sequence of labels L.
Suppose
n ) is another path specified by L. Let k be the smallest
subscription that b j 6= b 0
. Then, in DQDB d k\Gamma1 , the same label l k is used to represent two
different tri-tuples (d
k ), this contradicts the fact that labels defined by
the same DQDB are distinct. Therefore, L specifies one and only one path.
It is clear from the above theorems that, given a path, there is one and only one legal sequence
of labels at the source DQDB that specifies the path. And the legal sequence of labels specifies
the given path only. Given any legal sequence of labels L at DQDB d, a slot carrying L can reach
its destination from DQDB d. Thus, we prove the correctness of the proposed labeling scheme.
5 Path Migration
While a call is still in progress, an efficient path may become inefficient. For better resource
utilization, path migration is sometimes desirable [10, 16]. It consists of four steps:
1. Recognize the inefficient path.
2. Set up a new path, independent of the old one.
3. Transfer the flow of user information from the old path to the new path while meeting
certain performance objectives.
4. Release the old path. isochronous channels.
Setup of a new path (step 2) and release of the old path (step 4) can be accomplished using the
proposed path setup protocol. For traffic migration from the old path to the new path (step 3),
interested readers are referred to [13, 16] for discussions.
In this section, we discuss when to initiate a path migration (step 1). In general, there are
two types of path migration:
forced migration, which takes place when a path cannot be extended during an inter-DQDB
handoff.
voluntary migration, which takes place when a path becomes inefficient.
In the literature, only simple cases of voluntary migration have been observed. Here we address
forced migration and more sophisticated cases of voluntary migration.
5.1 Voluntary Path Migration
The purpose of voluntary path migration is to migrate inefficient paths to more efficient ones.
(The notion of more efficient paths was defined in Definition 1.) Periodically, each DQDB BMN
examines its path table. For each path in the table, it computes the most efficient path between
the source and destination DQDBs under current traffic condition. If the newly computed path
is (considerably) more efficient than the one in use, a voluntary path migration may be desired.
A simple case where a path becomes inefficient is illustrated in Fig. 6. Initially, a path exists
between two mobile hosts X and Y . When mobile host Y roams to a neighboring DQDB, the
path is elongated and becomes inefficient. A migration to the shorter path (the dotted one) is
desirable. This kind of occasion that calls for path migration has been discussed in [13]
Even without handoff, a path may become inefficient and entails a migration. Figure 7
illustrates two such scenarios. In the first case, an efficient path become inefficient when a DQDB
on the path becomes CONGESTED or FULL. In Fig. 7(a), a shortest path exists between mobile
hosts X and Y . When DQDB A becomes congested, the path is migrated to a longer but more
efficient one (Fig. 7(b)). In the second case, a non-shortest path is chosen for the connection
between mobile hosts X and Y because DQDB A is in FULL/CONGESTED state (Fig. 7(c)).
elongated path
migrated path
(a) a path between X and Y (b) elongated path and migrated path
bridge

Figure

Voluntary path migration I: due to inter-DQDB handoffs
A
A
(a) DQDB A is NORMAL (b) DQDB A is CONGESTED
A
A
(c) DQDB A is FULL/CONGESTED (d) DQDB A is NORMAL

Figure

7: Voluntary path migration II: due to DQDB state change.
Later, after some isochronous channels in DQDB A are released, the state of DQDB A changes to
NORMAL. In this case, a more efficient path exists and a voluntary path migration is initiated
(Fig. 7(d)).
5.2 Forced Path Migration
There are occasions when path migration is necessary or a call (connection) will have to be
dropped. This occurs when a path currently in use cannot be extended during an inter-DQDB
handoff. For instance, in Fig. 8, mobile host Y roams from DQDB A to DQDB B. A and B are
not directly connected by bridges. The path must be extended via either DQDB C or DQDB D,
but both C and D are FULL. Instead of tearing down the connection, a forced path migration
will save the connection.
A
Y
Y

Figure

8: Forced path migration

Figure

6 Simulation
In order to evaluate the performance of the proposed path setup and path migration protocol in
comparison with the DPBB scheme, we simulate both protocols in the same simulation model
with the same assumptions [13]. A Manhattan-style network model with a size of 10   10 is
considered here as shown in Fig. 9. The rectangle mesh topology is chosen because cables are
likely installed under streets, which is likely to happen in the real world. Each vertex represents
a DQDB cluster, and each edge represents a bridge connecting two neighboring DQDBs.
We assume that the inter-arrival time between two consecutive new calls and the service
time of each call are both exponentially distributed with mean IATM and SVTM, respectively.
To simulate the handoffs of mobile hosts, we assume that the inter-handoff time between two
consecutive handoffs is also exponentially distributed with mean IHTM. Messages for path setup
service time (SVTM)
channels per DQDB 100

Figure

10: Simulation Parameters
are sent via asynchronous slots (QA slots), and we assume the delay in delivering a QA slot in
a DQDB subnetwork is exponentially distributed with mean DELAY. Without loss of generality,
we assume the total number of available isochronous channels at each DQDB is 100. In the
simulation, we let When the number of available channels in a DQDB is
reduced to ffi 1 , the DQDB state is changed from NORMAL to CONGESTED; when the number
available channels in a DQDB is increased to ffi 2 , the DQDB state is changed from CONGESTED
to NORMAL (Fig. 10).
To compare the performance of the proposed protocol and the DPBB scheme, the measurements
of (1) blocking rate, and (2) delay in path setup are investigated. As shown in Fig. 11,
the proposed protocol outperforms the DPBB scheme in both blocking-rate and path setup delay.
And the improvement is not negligible. The lower blocking rate results mainly from (1) the choice
of most efficient path with congestion control and (2) minimization of channel reservation during
path setup. The lower path setup delay results from the fact that path establishment in the proposed
protocol only involves source routing bridges. In DPBB scheme, both bridges and BMNs
are involved in message forwarding. Messages are forwarded in the "stop and consult" manner.
In the above simulation, the values of ffi 1 and ffi 2 are carefully chosen with the consideration of
congestion control. To see the importance of this, we run two groups of simulations of the proposed
protocol. In the first group, we fixed the value of ffi 1 and use different values of ffi 2 . When ffi 1 is
fixed, a little buffer (i.e. reduce the blocking rate dramatically (Fig. 12(a)). In the
second group, we use different values for 2. We can see that when congestion
control is not considered (ffi the blocking rate is much higher (Fig. 12(b)). Selection of the
most efficient path instead of the shortest path improves the performance significantly.
blocking
rate
number of call requests per hour
source_routing
avegrage
delay
for
call
setups
(in
terms
of
number of call requests per hour
source_routing
(a) (b)

Figure

11: Comparison of (a) blocking rate and (b) path setup delay.0.050.150.250.35280 320 360 400 440 480
blocking
rate
number of call requests per hour (delta1=8)
delta2=8
blocking
rate
number of call requests per hour (delta2=delta1+2)
delta1=0
delta1=4
delta1=8
(a) (b)

Figure

12: Comparisons of different values.
7 Conclusion
We have proposed an efficient protocol for path setup and path migration in a cluster of DQDBs.
We applied a link-state-like routing method for path selection and a source-routing-based protocol
for path establishment. Both congestion control and better resource utilization can be achieved
by selecting efficient paths. A labeling scheme was proposed to facilitate the carrying of path
information in a single DQDB slot. Compared with a previous scheme, our protocol is simpler,
and performs better in terms of blocking rate and setup delay.
Although the proposed labeling scheme and path setup protocol were presented in the setting
of DQDB networks, they are actually applicable to other bridge-connected LANs/MANs such as
FDDI-II [2] and FDDI Follow on LAN [12].



--R

A. Routing Strategy for Interconnecting High-Speed
FDDI and FDDI-II : Architecture
Transparent Bridges for Interconnection of IEEE 802 LANs.
Data Networks.

Introduction to Algorithms.
Personal Communications-A Viewpoint

Cellular Packet Communications.
Network Control for Wireless Communications.
IEEE 802.6 Working Group.
A Review of High Performance Protocols for the FDDI Follow on LAN.
A Distributed Paths Migration Scheme for IEEE 802.6 Based Personal Communication Networks.
A Personal Communication Nework Architecture Using the IEEE 802.6 MAN.
Two User Location Strategies for Personal Communications Services.
Path Optimization Procedures for Efficient Routing of Information after an Inter-Switch Handover
Asynchronous Transfer Mode - Solution for Broadband ISDN

--TR
routing;DQDB;path migration;isochronous channels;call setup