Side_1_360

that are traversed along the path from node ito
node j. The links traversed are implicitly
defined. If node eis included on the path π(i,j)k,
e∈π(i,j)kis true. The set of links traversed along
the path π(i,j)kis defined by the function

The path shown in Figure 4.1 is denoted by
π(1,7) 1 = (1, 2, 9, 11, 6, 7). The set of links on the
path is given by χ(π(1,7) 1 ) = {(1, 2), (2, 9),
(9, 11), (11, 6), (6, 7)}.

The routing algorithm determines the actual path
a packet follows through the network domain.
The conceptual model will not be used to specify
the routing algorithm.

4.4 Packets, Events and Sets

Events that occur to packets traversing the net-
work domain, G= (V, E), form the basis for all
measurement data that can be collected. Set the-
ory is applied to describe sets of events that
occur in the network domain.

First, the fundamental events experienced by
packets in a packet-switched network are de-
scribed. A packet enters the network domain at
an ingress node, follows a given path π(i,j)k
through the network and a successfully9)carried
packet leaves the network domain at an egress
node. A packet is delayed through each node
n∈π(i,j)kand link l∈χ(π(i,j)k) along the path.
The delay along a given path consists of process-
ing delay, queueing delay, transmission time and
propagation delay.

Network congestion causes buffer overflow in
nodes and leads to packet loss. Further, nodes
may also drop packets intentionally. Packets can
be dropped by buffer management and packet
scheduling algorithms at intermediate nodes or
dropped at the receiver’s end if the end-to-end
delay is too large. In the conceptual model, packet
loss includes both lost and dropped packets.

Packets can also be lost because of transmission
errors on the links. The transmission error rate is
normally not significant in backbone networks

with optical links. On the other hand, radio links

can experience a high transmission error rate.

In order to describe the events occurring in the

network domain in a precise and concise way,

three fundamental set types that form the foun-

dation for creating supersets and subsets of

events that satisfy more complex properties,

are defined. For a given time interval the events

that have occurred at each node are classified in

the following three fundamental sets10):

• Rn(t 1 , t 2 ) represents the set of packets received
  by node n∈Vin time window [t 1 ,t 2 >.


• Sn(t 1 , t 2 ) denotes set of packets sent from node
  n∈Vin time window [t 1 , t 2 >.


• Xn(t 1 , t 2 ) denotes set of packets lost at node
  n∈Vin time window [t 1 , t 2 >.

The fundamental sets of events are illustrated in

Figure 4.2.

Note that the sets of events observed by a node

can be specialized depending on the internal

architecture of the node.

In addition, at a given point in time packets can

be in transit between two nodes or already lost

due to transmission errors on the link.

Figure 4.1 An example of a

path from node 1 to node 7

9. In this context, a successfully carried packet is a packet that was neither lost in a node nor on a

link. That is, the content of the packet is not evaluated.
10)Note that the membership of packets in a certain set is a matter of definition.

Network

domain

1

12

3

5

10

14

13

8

7

11

2

9

4

6

χ(π(i,j)k)=

{

(n 1 ,n 2 )∈E|n 1 ,n 2 ∈π(i,j)k

}

.