A User-level Tool for Inferring Router Packet Forwarding Priority

Abstract—Packet forwarding prioritization (PFP) in routers is one of the mechanisms commonly available to network operators. PFP can have a significant impact on the accuracy of network measurements, the performance of applications and the effectiveness of network troubleshooting procedures. Despite its potential impacts, no information on PFP settings is readily available to end users. In this paper, we present an end-to-end approach for PFP inference and its associated tool, POPI(POlarimetric Phase Interferometry). This is the first attempt to infer router packet forwarding priority through end-to-end measurement. POPI enables users to discover such network policies through measurements of packet losses of different packet types. We evaluated our approach via statistical analysis, simulation and wide-area experimentation in PlanetLab. We employed POPI to analyze 156 paths among 162 PlanetLab sites. POPI flagged 15 paths with multiple priorities, 13 of which were further validated through hop-by-hop loss rates measurements. In addition, we surveyed all related network operators and received responses for about half of them all confirming our inferences. Besides, we compared POPI with the inference mechanisms through other metrics such as packet reordering (called out-oforder (OOO)). OOO is unable to find many priority paths such as those implemented via traffic policing. On the other hand, interestingly, we found it can detect existence of the mechanisms which induce delay differences among packet types such as slow processing path in the router and port-based load sharing.




Existing System:-


As an extension of our earlier project r, we compared POPI with the inference mechanisms based on other metrics with less overhead such as packet reordering (called out-of-order (OOO)) in this paper. OOO is unable to find many priority paths such as those implemented via traffic policing. On the other hand, it can detect existence of the mechanisms which induce delay differences among packet types such as slow processing path in the router and port-based load sharing.



Proposed System:-


We proposed to use Average Normalized Ranks (ANR) to group packet types when there is consistent difference. The ANR is the average of the ranks for a packet type over all bursts.


There are a couple of challenges for designing and implementing POPI. First, background traffic fluctuations can severely affect the end-to-end inference accuracy of router properties. Secondly, probe traffic of a relatively large packet bursts are neither independent nor strong correlated. Most existing inference methods have to assume certain independence (i.e. i.i.d. processes) or strong correlation models for inference (e.g. back-to-back probe packets). However, as for the relatively large packet bursts sent by POPI, a good mathematical model is needed to determine whether the loss rates difference between two packet types is the consequence of a random effect or being treated really differently. Thirdly, we want to measure more than two packet types at the same time, so simply determining whether they are treated differently is not enough.


1. The probe overhead of packet loss metric is larger than the other two. Obviously, loss rates difference will not become evident until the associated link (or a sub-link for a traffic class) is saturated and begins to drop packets. This simple observation defines the basis of loss-based inference approach: In order to reveal packet-forwarding priorities, one needs to saturate the path available bandwidth for a given class to produce loss rates difference among different classes.  On the other hand, packet reordering and delay differences can be observed as soon as queue begins to build up. We do not need to send as much traffic as the loss-based approach for the reordering and delay-based approach.



2. Loss difference can be observed for all kinds of QoS mechanisms while the other two cannot. Although using delay and reordering metrics can result in less probe overhead, they can not detect certain router QoS mechanisms simply because those mechanisms do not generate different delays at all




3. Packet delay difference can be caused by many other mechanisms than QoS. As noted in [16], the root cause of packet reordering is the existence of parallel packet forwarding paths. Such paths can be in a router, parallel links between two routers, or different routes over a number of hops. When packets are split to these parallel paths according to their packet types and these paths have different delays, we’ll observe asymmetric packet reordering and delay differences among different packet types.










Modules :-



1. Traffic End-to-end inference of router


The accuracy of end-to-end inference of router properties can be severely affected by background traffic fluctuations. Clearly, if one’s probing introduces relatively small additional traffic, whether the link is saturated or not depends solely on the amount of background traffic. To make our approach more resistant to background traffic fluctuations we opt for sending relatively large amount of traffic to temporarily saturate bottleneck traffic class capacity, which increases the probability of observing loss rates difference. To note, the sender may not be able to saturate the bottleneck link due to limited resources, which is an inherit limitation of this method.



2. Packet loss model and insensitive to loss correlations


Probe traffic of a relative large packet bursts are neither independent nor strongly correlated. Once the loss rate for each packet type is obtained, we need to determine whether the loss rates difference among them is large enough to conclude that they are treated differently. When packet

losses can be described with a good mathematical model, e.g. independent and identical distribution (i.i.d) process, we can determine if the loss rates of different packet types were evidently different or not by comparing all pi, the loss rate of packet type i, using parametric statistical methods. However, our probe packets are sent in large packet bursts. Packet losses in one burst are not independent but correlated. We are not aware of any well-known model for packet losses in a large packet burst in the Internet. Hence, we employ a nonparametric method based on ranks, which is independent to underlying packet loss model and insensitive to loss correlations.


3. Grouping is needed for multiple packet types


Grouping is needed for multiple packet types probing. If we only probe two packet types at one time, simply determining whether they are treated differently is enough. However, we sometimes probe more than two packet types and need to group them based on their priorities. Here, we assign a rank-based metric to each packet type and use hierarchical clustering method to group them. In summary, POPI saturates the link with relatively large amount of traffic and clusters packet types based on their loss ranks. Such an approach gives POPI better resistance against background traffic fluctuations, allows it to cope with the inherent characteristics of its measurement traffic, and enables it to measure more than two packet types at one time




4. Background on Priority Mechanisms


Network administrators can enforce priority/link-sharing mechanisms in a router by defining a traffic class (usually IP protocol and TCP/UDP port number) and associating with it a particular queuing/scheduling mechanism .

• Priority Queuing (PQ).

This allows users to assign arbitrarily defined packet classes to queues with different priorities. Since queues are served based on their priority, this allows specified packet types to be always sent before other packet types.


• Proportional Share Scheduling (PSS).


With PSS each traffic class is given a weight. Bandwidth is allocated to

classes in proportion to their respective weights. There is no strict priority difference between classes. There are different ways to implement this scheduling mechanism, e.g. Weighted Fair Queuing (WFQ), Weighted Round- Robin (WRR). In Cisco routers, the CBWFQ is Class- Based WFQ and the Custom Queuing is WRR based.


• Policing.

 This restricts the maximum rate of a traffic class. Traffic that exceeds the rate parameters is usually dropped. The traffic class cannot borrow unused bandwidth from others. Only the first mechanism sets absolute priorities between traffic classes. There is no absolute priority difference between the other two classes, and the loss experienced by one class depends on whether its traffic rate exceeds its allocated bandwidth.




5. Choosing Inference Metric

Three basic end-to-end performance metrics, loss, delay and out-of-order, can all be used as inference metrics. This is because these metrics of different packet types can become different when a router is configured to treat them differently. Consider a PQ of two priorities, where the high priority queue is always served first. Low priority packets will experience larger loss rates and longer queueing delays than the high priority packets. Besides, a low priority packet may arrive earlier than a high priority packet but leave after it while the contrary will never happen. The reordering events between them are asymmetric. Here, the loss, delay, and reordering can all be used as a metric to infer priority settings. In this paper, we’ll use the loss, delay and OOO (Out-Of-Order) based method to name the inference methods based on these metrics.


Essentially, the delay and reordering metrics are equivalent because when a packet gets lagged behind another packet, its delay should be larger than the other. In the following,  we discuss the pros and cons between loss metric and the other two metrics and the reason why we choose packet loss eventually.







Hardware Requirements:


  • System                 : Pentium IV 2.4 GHz.
  • Hard Disk               : 40 GB.
  • Floppy Drive       : 1.44 Mb.
  • Monitor                 : 15 VGA Colour.
  • Mouse                  : Logitech.
  • Ram                        : 512 Mb.





Software Requirements:-


          Language: JAVA, Swing

          OS: Window XP








Tags :
Your rating: None Average: 4.5 (2 votes)