Technical Overview

Similarly to other Diffserv models, at the architectural level, LIRA consists of the following components:

• a service profile between each customer (user) and the Internet Service Provide (ISP) that defines the commitment of the ISP to the user
• two bits in the header of each packet. The first bit, called the preferred bit, is set by the application or user and indicates the dropping preference of the packet. The second bit, called the marking bit, is set by ingress nodes (see below)
• ingress nodes at the edge of the ISP network that police the aggregate traffic from each user in order to comply to its service profile. More precisely, when a preferred packet arrives at an ingress node, the node marks it if the user has not exceeded its profile; otherwise the packet is left unmarked
• network nodes inside the ISP core which implement a variant of weighted RED that, when the link is congested, drops the unmarked packets first

In LIRA, each user is assigned a service profile characterized by a resource token bucket (r, b), where r represents the resource token rate, and b represents the token depth. Unlike traditional token buckets where each preferred bit entering the network consumes exactly one token, with resource token buckets the number of tokens consumed by a bit is a dynamic function of the path it traverses.

Ingress Node Algorithm The operations performed by an ingress node, when a marked packet arrives, are shown above. The cost of a marked packet is computed as the product between the length of the packet and the total cost of forwarding a bit on each link along the path. Note that other cost functions can also be used. For example, the cost to forward a bit can be defined as the maximum, instead of the sum, over the costs of all links along the path. Another example would be to add a per packet cost to account for the packet processing overhead at the nodes along the path.

Link Cost Computation One of the main goal of LIRA is to ensure high service assurance, i.e., to avoid marked packets being dropped. Since in the worst case all users can compete for the same link at the same time, a necessary condition is that the link cost to exceed the total number of tokens in the system when the link utilization approaches unity.

Among many possible cost function with this property we choose c(t) = a / (1 - u(t)), where a is the fixed cost associating with using the link, and u(t) is the link utilization at time t. Since this cost function is very sensitive as the utilization approaches unity, to avoid instability we use the following iterative formula to compute c

where R(t', t'') represents the average arrival rate of the marked traffic in the interval [t', t''), and C represents the link capacity.

Path Cost Computation Since in LIRA, the cost of a a marked bit over a path is the sum of all links' costs on the path, we can simply compute it by leveraging existing routing protocols.

Load Balancing and Route Pinning LIRA is able to take advantage on multiple routing, by distributing the load over alternate routes. To avoid oscillations and packet reordering, LIRA employs two key techniques

1. Probabilistic Binding If multiple path are available, ingress nodes bind probabilistically each flow to a path. Among the available paths (computed by traditional routing protocols) the ingress node picks a path with a probability that depends on the path cost. By carefully choosing this probability it is possible to achieve both load balancing and stability. (For details see Section 2.4.2 in [1].)

2. Path Pining In LIRA each path is identified by a label which is defined as the XOR over the identifiers (IP address) of its nodes. When a packet arrives at an ingress node, the node labels the packet with the identifier of the path to which the flow was previously binded. In turn, each node use this label to forward the packet. At the same time the node XORs the packet label with its identifier to obtain the identifier of the remaining sub-path to the destination.

The example below illustrates the use of the above techniques. The destination is node adr5. In addition, we assume that the flow to which the packet belongs was binded to the path of cost 7.