rephrase part II
solarysystem1
rephrase_2.docxGrouping compatible transactions
The bus owner arbitration decision is the core of the arbitration process in SFP. In simple terms, arbitration decision is nothing but “selecting” a group of arbitrating nodes that can be granted simultaneous access to the bus. The bus owner has a global knowledge about arbitrating nodes, and the properties (size, priority, etc.) of packet transactions that arbitration is done for. For better understanding of the bus owner arbitration decision process, it is necessary to study a few design issues.
Figure 20 shows an indexed line that illustrates an SFP topology where each index represents a node. The end of the topology that has node “1” is called the left end, and the other end that has node “N” is called the right end. A connection (dashed line) between any two nodes, A and B, indicates that a data packet transaction (or simply “transaction”) needs to be established between them (i.e. A wishes to transmit a packet to B, or vice versa). Figure 20 shows several connections, indicating many possible transactions, placed over several rows. Any two transactions that overlap (incompatible) must be placed in different rows (i.e. one above and one below). Non-overlapping (compatible) transactions can be placed in the same row. Compatible data transactions can occur concurrently (i.e. the paths between the corresponding source and destination nodes do not overlap and packet collisions will not occur). In Figure 20, transactions ‘a’ and ‘d’ are incompatible and transactions ‘b’ and ‘c’ are compatible. Since each request packet defines the source and the destination addresses of nodes involved in a transaction, the bus owner is able to envision information as shown in Figure 20.
Figure 20. Grouping compatible requests
3.4.2 Request cache
Each SFP node implements a request cache. A request cache is structured as a two-dimensional source address pool (i.e. there are N slots each holding an N element array of source addresses). N represents the maximum number of nodes the SFP network may support. Each array element is associated with a one-bit flag. In addition, a request cache has three independent N element arrays called packet size array, packet phase array, and packet priority array. Each array respectively stores the values of the packet size field, packet phase field and packet priority field of the received requests. Each received request is identified by its source address field. The source address of a request serves as its unique “signature”. Figure 21 shows a request cache. The following example illustrates how the cache is updated when a request is received. Assume that a request with the following field values is received:
· Source address – 2,
· Destination address – 8,
· Packet Phase – Current,
· Packet length – 1500 bytes, and
· Packet priority – High
For every request, its signature is updated in the slots indexed by its source and destination addresses. Since the source address of this request is 2 its signature is 2. In this example, the signature entry should be made in the slots “2’ and “8” corresponding to the source and the destination addresses. Source and destination addresses are classified as either left address or right address based on their closeness to the left end or right end of the topology. In other words the smaller of source or destination addresses is left address and the other is right address. In this example the source address is left address and the destination address is right address. Signature “2” is entered in the array (in the next non-empty position) of slot “2” and its associated one-bit flag is set to 0 (since source address is left address). Signature “2” is entered in the array of slot “8” (corresponding to the destination address) and its associated one-bit flag is set to 1 (since destination address is right address). The other arrays are updated as:
· Packet phase array [signature] = Current
· Packet size array [signature] = 1500
· Packet priority array [signature] = High
There is also a request counter that stores the number of requests present in the cache. The request cache can be implemented using content addressable memory (CAM). A CAM-based design for a request cache helps SFP nodes in easy update and removal of cache entries and enables the bus owner to make a fast arbitration decision.
Figure 21. Request cache
3.4.3 Bus owner arbitration decision algorithm
The bus owner arbitration decision algorithm has two tasks. The first task is to group the requests into minimum number of sets as shown in Figure 20. The second task is to select a set such that packet priority and fairness properties are respected. Grouping of requests can be done by two methods. The first method involves sorting of requests based on their left address. This method is shown in Figure 22. Initially there is just one empty set (designated as Set1). Each request of the sorted list is assigned to the lowest possible set if it is compatible with the other request in it. If it is not possible to assign the request to any set, then a new set is created and the request is assigned to it.
ALGORITHM Grouping of Requests – Method 1
1. For (each request of the sorted list) do
2. For (each set Seti, i from 1 to current number of sets) do
3. If (the request is compatible with all requests in Seti ) then
4. Assign the request to Seti
5. Else
6. Create a new set Seti +1 and assign the request to it
Figure 22. Grouping of requests – method 1
If there are n requests, then sorting takes O(nlogn) time and grouping of requests takes O(n2) time. So the time complexity of this method is O(n2). Grouping of requests takes O(n2) time because every request is compared to every set and in the worst case (all transactions to the head end) the number of sets can be proportional to n2.
The second method is based on the observation that two requests can be placed in the same set if the left address of one request is greater than or equal to the right address of the other. The second method requires that requests be sorted based on their left and right addresses and scanned in that order. A request cache can ensure that requests are kept in a sorted order (based on their left and right addresses). So the time for sorting is saved. A new stack data structure that stores the signature of requests is created. The requests are scanned in order (i.e the left address of a request is encountered before the right address). Whenever the right address of a request is encountered its signature is pushed onto the stack. Whenever the left address of a request is encountered the stack is checked. If the stack is non-empty then the request is assigned to the same set as the request in the stack top. If the stack is empty then the request is placed in a new set. The use of stack data structure eliminates the need for scanning every already created set. The use of a stack to group requests in this way is adopted from the work [28]. Reference [28] presents a linear time left edge algorithm for channel routing in VLSI circuits. This second method does not involve sorting of requests and requests are grouped in a single sweep of the request cache. The time complexity of the second method is O(n). The SFP bus owner arbitration decision algorithm follows the second method for grouping requests.
The bus owner arbitration decision algorithm is presented in Figure 23. Lines 1-12 of the algorithm deal with partitioning the requests in the cache into a minimal number of sets of compatible requests. This is similar to the grouping of compatible transactions in minimum possible rows as seen in Figure 20. The request cache is scanned from slot 1 to slot N so that requests are scanned in a sorted order (based on their left and right addresses). For each slot, whenever a request signature with the associated flag set to 1 (indicating right address) is encountered it is pushed onto a stack. For each slot, when a request signature with the associated flag set to 0 (indicating left address) is encountered, it is placed in the same set as the request found in the top of the stack or it is placed in a new set if the stack is empty. Grouping requests in this way ensures that they are compacted into a minimal number of sets. In the algorithm, Ri denotes the signature of any request i, where i ranges from 1 to the number of requests in a slot. Index represents the identification of a set, and is initialized to zero. Sindex denotes a set with identification index, and j is a loop counter. In lines 13 – 17 a set of requests is selected for grant to bus access. A set that has the maximum number of requests is selected such that it has one or more of the highest priority level requests present at that time. The three priority classes in SFP and the two phases of arbitration combine to provide six levels of priority as illustrated in Table 2. After selecting a set, the bus owner issues a grant to all the requests (i.e. the corresponding source nodes) in the selected set. The granted source node that is expected to complete its packet transmission in the end will be assigned the role of the next bus owner. The bus owner broadcasts a grant packet with information about the granted nodes and the next bus owner. Arbitration granting is explained in the next section.
ALGORITHM Bus Owner Arbitration Decision
1. For (each slot of the request cache) do
2. For (i=1 to number of requests for this slot) do
3. If (Ri has associated flag set to 1) then
4. Push Ri on the stack
5. For (i=1 to number of requests for this slot) do
6. If (Ri has associated flag set to 0) then
7. If (stack is empty) then
8. index = index + 1
9. Assign Ri to the set Sindex
10. Else
11. Pop R from stack
12. Assign Ri to the same set as R
13. For (j = 1 to number of priority levels) do
14. If (There are any priority j requests) then
15. Select a set containing the maximum requests and at least one priority j request
16. Issue a grant to all requests in the selected set
17. Exit from this algorithm
Figure 23. Bus owner arbitration decision algorithm
Table 2. Priority levels in SFP
|
Priority class |
Arbitration phase |
Priority level |
|
High |
Current |
1 (highest) |
|
|
Next |
2 |
|
Medium |
Current |
3 |
|
|
Next |
4 |
|
Low |
Current |
5 |
|
|
Next |
6 (lowest) |
3.5 Arbitration granting
After making the arbitration decision, the bus owner broadcasts a grant packet. The grant packet is transmitted in the data line. Since the bus owner is the last node to complete its data transmission (among a group of transmitting nodes) it is ensured that the grant packet will not collide with other data packets. Every node makes a local copy of the grant packet and repeats it to the neighbor. The grant packet includes several fields of information whose significance is described below:
· Granted address list: This list contains the address of all source nodes (corresponding to the requests in the selected set) granted by the bus owner. The listed nodes can transmit their data packet immediately on receiving the grant. Based on the granted address list, nodes clear cache entries corresponding to the granted requests.
· Destination address list: This list contains address of all destination nodes whose corresponding source nodes are granted bus access. This knowledge comes from the request packets. Nodes operate in blocking mode when their address is included in this list (it is implied that the next data packet is destined to the listed node).
· Reset status: This field indicates the status of arbitration reset. When the bus owner sees no Current phase requests it performs an arbitration reset by setting this field value to TRUE. If bus owner sees one or more Current phase requests then this field is set to FALSE. When this field is set to TRUE, nodes update their Arbitration_reset flag to TRUE and hence can start arbitrating for the Current phase again.
· Bus owner: This field identifies the address of next bus owner. One of the granted nodes that identifies its address in this field, must take control of the bus owner operation at the end of its data transmission. For each granted source node the present bus owner computes a drain time, Tdrain,
Figure 24. Arbitration sequence in SFP
3.6 Traffic classes in SFP
All data transmissions in SFP are packet based and SFP supports variable sized packets. SFP supports two types of data transactions described as follows:
· Asynchronous transactions: These are unicast transactions that provide reliable data delivery. Each asynchronous packet requires an acknowledgement from the receiver. In FireWire, an acknowledgement packet does not require arbitration and can be transmitted by any node immediately on the receipt of an asynchronous packet. However, acknowledgement packets may or may not require arbitration in SFP. The performance study of tradeoffs between the two methods is left for future study. Asynchronous packets may be assigned to different priority classes and fairness among nodes may be ensured by the SFP fairness mechanism.
· Asynchronous streaming: This work focuses on asynchronous streaming, which is suitable for carrying video and other real-time traffic. These transactions may be unicast or multicast. The scope of this work is limited to unicast asynchronous streaming. Asynchronous streaming is an unreliable service and packets do not require an acknowledgement from the receiver. SFP does not provide support for isochronous service as seen in FireWire. QoS support for time critical applications, such as voice and video, is provided by mapping individual asynchronous stream packets to the different priority classes supported by SFP.
3.7 Summary
The following summarizes the SFP design principles:
· SFP proposes a new physical layer data transmission interface that uses the existing FireWire cable. A communication link uses two twisted pairs (TPA, or data line and TPB, or request line) that operate as two independent half duplex lines. Synchronous request transfer mechanism permits unblocked, overlapped arbitration with data transmission.
· Request packets are informative; containing source address, destination address, packet phase, packet size, and packet priority fields. Caching of request packets enables the bus owner too see multiple requests at the same time and make an intelligent arbitration decision. The request cache has an efficient design permitting easy look-up of requests and quick response time (processing time) for the bus owner.
· SFP preserves the simple repeat path functionality of FireWire and still achieves destination stripping of packets. A data packet does not require destination address look-up (involving a delay overhead) at each node. A grant packet explicitly informs destination nodes to operate in blocking mode.
· SFP supports three priority classes and arbitration ensures fair sharing of bandwidth among like priority nodes. Isochronous service is not supported. Data transactions are asynchronous or asynchronous streaming.
CHAPTER 4
PERFORMANCE EVALUATION OF SFP
Simulation models experiements steps
Two traffic models are used to evaluate performance The first model developed was based on MPEG-2 frame length frequeences from the 1996 Olympic games which include;
a) each run was for 40 minutes which represent a sporting activity and include a total of 20 runs.,
b) the MPEG-2 runs were then were altered into packet sizes with 48 bytes of overhead,
c) a division of MPEG-2 frames into Ethernet packets was anticipated to occur in zero time,
d) a mean data rate of about 5 Mbps.was used.
To invesgitae the different levels of varability and accuracy rate , following steps were carries;
a) 20 different Olympic events were used.,
b) simulated nodes results were i greater than 20, copies of the available frame traces were randomly assigned between nodes.
c) For the 20 MPEG-2 sources, the mean packet length was 1459.7 bytes and the total offered packet load was 101.5 Mbps., however,
a. the frames from multiple sources were not coordinated.
The second traffic model was Poisson arrivals of fixed length packet , wehre the following steps were carried out.
a) the mean packet length of the MPEG-2 video sources unless otherwise specified. This traffic model was synthetically generated with no limit on the number of nodes.
b) MPEG-4 frame length poulation are used for a single experiment. Each MPEG-4 trace was for 60 minutes of a movie sequence and a total of 20 runs were available [10]. The mean data rate of all MPEG-4 sources is 0.67 Mbps and video rate is 25 frames per second. The same packetization method as applied to the MPEG-2 population is used for the MPEG-4 population.
4.2 The simulated configuration
The three simulation models (SFP, IEEE 1394b, and IEEE 1394a) were designed to model a daisy-chained network configuration as shown in Figure 16. Each node is an independent traffic source. Each IEEE 1394b and IEEE 1394a node is assumed to have an infinite capacity buffer for packets being sent on the link. Each SFP node is assumed to have three infinite capacity buffers (corresponding to the three priority classes). The distance between any of pair nodes is equal and fixed at 10 meters. All internode links have equal bandwidth capacity, which is varied between the experiments. Source-destination traffic distributions between the nodes are based on four models as described below. Each model is characterized by a distinct value of spatial reuse factor; S. The value of S represents the average number of concurrent packet transmissions that can occur in the network. The performance of SFP is expected to vary for the different traffic distribution models. However, IEEE 1394b and IEEE 1394a will offer similar performance for all the four models because no spatial reuse is permitted in them.
· Spatial_min: All packets (of all nodes) are destined to the head end, which acts as the sensor fusion node. Since no concurrent packet transmissions are possible S for this model equals 1 (minimum possible).
·
· Spatial_video: For 90% of the time nodes send packets to their right or left neighbors (45% of time to right neighbor and 45% of time to left neighbor). For 10% of the time packets are destined to the head end. It is expected that traffic distribution in a typical video surveillance system will be similar. In a video surveillance system most of the traffic will occur between peer cameras (to track a profiled individual or notify significant events). A communication with the head end is established only for control messages and/or for recording data. S for this model is given as
· Spatial_max: All nodes send packets to their right neighbors. The Nth node in the network is assumed to have a dummy right neighbor. S for this model is N (maximum possible).
4.3 Description of simulation experiments
Preliminary experiment #1: This experiment evaluates the performance of IEEE 1394b and IEEE 1394a. The response variable is queuing delay (mean) and the control variable is the offered packet load on the link, which is increased from 10% to 97%. The number of nodes is fixed at 20. This experiment is performed for Poisson and MPEG-2 sources. For Poisson sources, the link bandwidth is fixed at 100 Mbps.
Preliminary experiment #2: This experiment evaluates the performance of IEEE 1394b for isochronous and asynchronous packet streams. The response variable is queuing delay (mean) and control variable is number of nodes, which is increased from 2 to 19. For isochronous streams, the entire 125-microsecond arbitration cycle is allocated for packet transactions and bandwidth is shared equally among the isochronous nodes. There is no cycle start overhead. Link bandwidth is fixed at 100 Mbps. This experiment is performed for MPEG-2 and MPEG-4 sources.
Load experiment: This experiment evaluates the performance of SFP and IEEE 1394b for different traffic distribution models. The response variable is queuing delay (mean and 99%) and the control variable is the offered packet load (throughput) on the link, which is increased from 10% to as high as 4500%. The number of nodes is fixed at 60 and the link bandwidth at 400 Mbps. This experiment is performed for Poisson sources.
Node count experiment: This experiment evaluates the performance of SFP for different traffic distribution models. The response variable is queuing delay (mean and 99%) and the control variable is the number of nodes, which is increased from 4 to 1000. The link bandwidth is fixed at 100 Mbps. This experiment is performed for Poisson sources. The packet arrival rate () is adjusted so that each node is a 5 Mbps traffic source.
Packet size experiment: This experiment evaluates the throughput performance of SFP for different packet sizes. The response variable is the maximum offered throughput on the link (in factors) and the control variable is the fixed packet size of Poisson sources, which is increased from 100 to 20,000 bytes. The number of nodes is fixed at 100 and the link bandwidth at 400 Mbps. The traffic distribution model used is Spatial_video. This experiment is performed for Poisson sources.
Priority experiment: This experiment evaluates the performance of SFP for different priority traffic. The response variable is queuing delay (mean and 99%) and the control variable is the offered load on the link, which is increased from 10% to 165%. The number of nodes is fixed at 60. Packets are prioritized such that 20% of the packets are High priority, 30% are Medium priority, and 50% are Low priority. This experiment is performed for MPEG-2 and Poisson sources. The traffic distribution model used is Spatial_average.
Packet priority ratio (PPR) experiment: This experiment evaluates the performance of SFP for different PPR. The response variable is the maximum offered throughput (in %) on the link and control variable is PPR. PPR is the ratio of Low to Medium to High priority traffic. The number of nodes is fixed at 60. This experiment is performed for Poisson sources. The traffic distribution model used is Spatial_average.
4.4 Results from the simulation experiments
Figures 25 and 26 show the preliminary experiment #1 results for Poisson and MPEG-2 traffic sources, respectively. In IEEE 1394b and IEEE 1394a mean queuing delays increase with the load. For Poisson sources, IEEE 1394b delay is always a magnitude less than the IEEE 1394a delay. IEEE 1394a reaches the maximum tolerable delay (delay exceeds the tolerance of human response time of 100 milliseconds) at about 92% load. At 97% load IEEE 1394b delay is around 3 milliseconds. IEEE 1394b reaches a bottleneck at about 99% load (not shown in graph). For MPEG-2 sources, the queuing delay trend is similar. However, the IEEE 1394b delay is only slightly lesser than the IEEE 1394a delay until about 90% load. IEEE 1394a delay exceeds 100 milliseconds at 92% load. At 97% load IEEE 1394b delay is 15 milliseconds.
Figure 25. Preliminary experiment #1 results for Poisson source
Figure 26. Preliminary experiment #1 results for MPEG-2 source
Figures 27 and 28 show the preliminary experiment#2 results for MPEG-2 and MPEG-4 traffic sources, respectively. For both traffic sources, the asynchronous delay is always a magnitude less than the isochronous delay and increases at an exponential rate. For both traffic sources, isochronous delay increases at a constant rate. For MPEG-2 traffic, asynchronous delay is 8 milliseconds at 18 nodes, which is one-eighth the corresponding isochronous delay. For MPEG-2 traffic, isochronous delay exceeds the maximum tolerable delay at 19 nodes and asynchronous delay at 20 nodes. Maximum tolerable delay is reached since the total offered bandwidth of the 20 MPEG-2 sources (100 Mbps) is equal to the link capacity (saturated network condition). For MPEG-4 traffic, both isochronous and asynchronous delays stay within 5 milliseconds, even for 20 nodes. This is because the bandwidth of MPEG-4 sources is very small (roughly 8 times less) compared to MPEG-2 sources, and the offered load at 20 nodes is just 13%.
Figure 27. Preliminary experiment #2 results for MPEG-2 source
Figure 28. Preliminary experiment #2 results for MPEG-4 source
Figures 29 and 30 show the load experiment results. Queuing delay increases exponentially with the offered network load. The queuing delay trends of SFP with spatial_min traffic model and IEEE 1394b are very similar and the lines are not distinguishable for mean and 99% results. Both reach a throughput maximum at 98% load. Maximum throughput is implied when queuing delay increases at a large rate and is much higher than the bottleneck value (100 milliseconds). IEEE 1394b offers identical performance for all four traffic models because it does not support spatial reuse. SFP offers no spatial reuse for Spatial_min traffic model, and hence, its performance is similar to IEEE 1394b. SFP reaches a maximum throughput at 165%, 650% and 4250% loads for Spatial_average, Spatial_video and Spatial_max traffic models, respectively. The maximum possible throughput is,
Figure 29. Load experiment results (mean delay)
Figure 30. Load experiment results (99% delay)
Figures 31 and 32 show the node count experiment results. Queuing delay increases exponentially with the node count. It is seen that mean delay of Spatial_min traffic is less than 3 milliseconds, and 99% delay is less than 10 milliseconds up to 19 nodes, and at 20 nodes both exceed 100 milliseconds (reach bottleneck). For the Spatial_average model the bottleneck is reached at 35 nodes (for mean and 99% results). For the Spatial_video model the mean delay is less than 13 milliseconds for 160 nodes and exceeds 100 milliseconds at 165 nodes. For Spatial_video, 99% delay exceeds the maximum tolerable delay at 145 nodes itself. This is due to the unbalanced nature of Spatial_video model. For Spatial_max model mean and 99% delay are less than 3 milliseconds even for 1000 nodes. It is seen that SFP is able to support 19, 34, 145 and more than 1000 nodes for Spatial_min, Spatial_average, Spatial_video and Spatial_max, traffic models respectively. The maximum node capacity is,
where Nmax is the maximum number of nodes and Rnode is the average data rate of a node in bits per second (5Mbps here). Substituting all parameters, the values of Nmax obtained are, 19, 37, 158, and more than 1000 nodes for Spatial_min, Spatial_average, Spatial_video and Spatial_max, traffic models respectively. The theoretical and experimental results match closely for Spatial_min and Spatial_average (variation less than 5%). For Spatial_video, variation between theoretical and experimental maximum nodecount is 10%. This is again due to the unbalanced nature of traffic distribution in Spatial_video.
Figure 31. Node count experiment results (mean delay)
Figure 32. Node count experiment results (99% delay)
Figure 33 shows the results for packet size experiment. It is seen that throughput increases with the packet size. However the rate of increase dampens with the increase in packet size, and throughput gradually reaches a constant value for large packet sizes. For 100 byte packets, throughput is 0.94 (or 94%). This is similar to the throughput of IEEE 1394b. Throughput is 6 (or 600%) and 960% for 1500 and 20,000 byte packets, respectively. After 20,000 bytes the increase in throughput is negligible.
Figure 33. Packet size experiment results
Figures 34, 35, 36 and 37 show the priority experiment results. At low loads the queuing delays of High, Medium, and Low priority traffic are alike. Queuing delay increases with load, however the rate of increase of Low priority delay (mean and 99%) is many magnitudes higher than that of High priority delay. Medium priority delay falls between the High and Low priority delays. For Poisson sources, at 160% load the mean delays are 0.08, 0.3, and 240 milliseconds and 99% delays are 0.18, 1.3 and 2000 milliseconds for High, Medium and Low priority traffic, respectively. For MPEG-2 sources at the same load, the mean delays are 4, 9 and 190 milliseconds and 99% delays are 8, 30, and 2000 milliseconds for High, Medium and Low priority traffic, respectively.
Figure 34. Priority experiment results for Poisson source (mean delay)
Figure 35. Priority experiment results for Poisson source (99% delay)
Figure 36. Priority experiment results for MPEG-2 source (mean delay)
Figure 37. Priority experiment results for MPEG-2 source (99% delay)
Figure 38 shows the results for packet priority ratio (PPR) experiment. PPR is the ratio of Low to Medium to High priority traffic. It is seen that throughput changes with PPR (different combinations of priority traffic), but the variations are a very small factor. Maximum throughput is 162%, seen at PPR of 1.0:0.0:0.0 (Low:Medium:High), 0.0:1.0:0.0 and 0.0:0.0:1.0. Minimum throughput is 154.1% seen at 0.2:0.4:0.4. It is seen that, throughput variations are always lesser than 5% of the maximum value.
Figure 38. Packet priority ratio experiment results
4.5 Discussion of results
IEEE 1394b exhibits considerably less queuing delay than IEEE 1394a. The difference is especially visible at higher loads (over 90% load). The better performance of IEEE 1394b can be attributed to the overlapping of arbitration and data transmission, and the complete elimination of idle arbitration gaps. IEEE 1394b asynchronous stream transactions offer a better delay performance than isochronous transactions for packet-based MPEG-2 and MPEG-4 video transmissions. For a saturated (fully loaded) network the queuing delay of asynchronous stream packets is nearly 15 times less than the queuing delay of isochronous packets. This is a motivation for completely eliminating the isochronous service in SFP.
SFP improves the throughput of IEEE 1394b by a factor of 1.7, 6.8, and 43.9 for Spatial_average, Spatial_video and Spatial_max traffic patterns, respectively. For the Spatial_min traffic pattern (a restricted case that permits no spatial reuse), SFP and IEEE 1394b offer similar performance. A similar improvement is seen in the node capacity of SFP at saturated network conditions. The better performance of SFP can be attributed to the spatial reuse of bandwidth. From the packet size experiment it is clear that SFP offers better throughput for large (mean) packet sizes (greater than 1500 bytes). SFP throughput increases with packet size because the percentage of overhead (arbitration granting overhead) per packet transaction decreases with the increase in packet size. From the results, it is clear that SFP priority arbitration distinctly separates the three priority classes in delay performance. High priority packets offer nearly 6 times lower queuing delay than Medium priority packets, whose delay is more than 100 times lower than Low priority delay. Asynchronous stream packets mapped to the different priority classes can provide a flexible service for MPEG-2 and MPEG-4 video. It is seen that for different combinations of priority traffic the throughput variations are not much and fall within 5% of the maximum value. This makes it clear that SFP does not compromise in (maximizing) throughput while providing service for priority traffic and strikes a good balance.
CHAPTER 5
CONCLUSION
This thesis presented the Spatial reuse FireWire Protocol (SFP), a nnew theory of bus arbitration protocol architected for an acyclic daisy-chained topology. Shared-medium daisy-chained network technologies are necessary to support economical installation of large-scale video surveillance systems. SFP is based upon the IEEE 1394b FireWire architecture and preserves the simple repeat path functionality of FireWire. SFP improves the effective throughput of FireWire by spatial reuse of bandwidth and QoS support for packet video by a real-time priority based bus access mechanism.
5.1 Summary of contributions
This thesis investigated new communication protocols suitable for video surveillance systems, in particular at the medium access control level (bus arbitration) and physical layer. The main contributions of this work are:
· A comprehensive study of the evolution of networks for video surveillance systems was made. FireWire was identified as a potential low-cost technology for video surveillance systems.
· IEEE 1394b FireWire was investigated as a candidate technology for video surveillance. Performance limitations in FireWire, such as lack of spatial reuse and lack of support for priority traffic, were identified. Simulation results demonstrate that FireWire asynchronous stream transactions offer a better delay performance than isochronous transactions for widely used variable bit-rate video like MPEG-2 and MPEG-4. This result motivates the elimination of isochronous service in SFP.
· Designed and evaluated the performance of Spatial reuse FireWire Protocol (SFP). SFP improves the throughput of IEEE 1394b by a factor of seven for a video surveillance traffic pattern and a factor of two for a homogeneous traffic pattern. SFP provides support for variable size packets, asynchronous stream and asynchronous transactions, three classes of priority, and ensures fairness among like priority nodes.
5.2 Future research
In SFP arbitration requesting is overlapped with data transmission. However, arbitration granting overhead (which depends upon the propagation and the repeat path delays) increases with node count. At a high node count, arbitration granting overhead can become considerable. One possible way to minimize this overhead is for the bus owner to issue grants to multiple sets of requests at the same time. Data transmission between consecutive sets must be properly synchronized and the next bus owner should be one of the nodes from the last transmitting set of nodes. Another approach is to have multiple operational bus owner nodes at the same time, each taking care of a certain small portion of the network. For data traffic between distinct portions, the bus owners should carefully synchronize among themselves.
Future research directions include; extension of SFP to accommodate multicast traffic, extension of SFP to support a tree topology network where every node can have two or more ports for branching, improving the robustness of SFP to handle packet losses (especially arbitration request and grant packets), and performance evaluation of higher layer protocols (such as TCP/IP) over SFP.
Slot1
Slot2
SlotN
1
2
N
.
.
.
Slot8
1
Packet Phase array
Packet length array
1
2
8
N
Cur.
1500
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Packet priority array
High
.
.
.
.
.
.
2
0
2
Signature array
Flag
Slot1
Slot2
SlotN
1
2
N
.
.
.
Slot8
1
Packet Phase array
Packet length array
1
2
8
N
Cur.
1500
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Packet priority array
High
.
.
.
.
.
.
2
0
2
Signature array
Flag
prop
n
repeat
hops
pkt
drain
T
D
T
N
R
L
T
+
+
=
repeat
T
=
Asynchronous stream transaction
Arbitration sequence
Arbitration requesting is overlapped with data transmission.
=
Arbitration grant overhead
Concurrent
packet
transmit
=
Asynchronous stream transaction
Arbitration sequence
Arbitration requesting is overlapped with data transmission.
=
Arbitration grant overhead
Concurrent
packet
transmit
prop
T
repeat
T
2
/
N
N
P
P
i
S
1
i
adj
N
i
1
i
head
-
=
=
å
´
´
=
P
head
P
adj
0.1
1
10
100
0102030405060708090
Load (%)
Delay (ms)
IEEE 1394a
IEEE 1394b
0.1
1
10
100
0102030405060708090
Load (%)
Delay (ms)
IEEE 1394a
IEEE 1394b
0
10
20
30
40
50
60
70
02468101214161820
Number of nodes
Delay (ms)
1394b Asynchronous
1394b Isochronous
0
1
2
3
4
02468101214161820
Number of nodes
Delay (ms)
1394b Asynchronous
1394b Isochronous
)
T
T
(
D
R
L
S
R
L
prop
repeat
boss
max
+
+
ú
û
ù
ê
ë
é
=
r
)
T
T
(
D
prop
repeat
boss
+
0.01
0.1
1
10
100
10100100010000
Load (%)
Delay (ms)
Spatial_min
Spatial_max
IEEE 1394b
Spatial_video
Spatial_average
0.01
0.1
1
10
100
10100100010000
Load (%)
Delay (ms)
Spatial_min
IEEE 1394b
Spatial_average
Spatial_video
Spatial_max
)
T
T
(
N
R
L
S
L
R
N
prop
repeat
max
node
max
+
+
´
£
0.01
0.1
1
10
100
101001000
Node count
Delay (ms)
Spatial_video
Spatial_average
Spatial_min
Spatial_max
0.01
0.1
1
10
100
101001000
Node count
Delay (ms)
Spatial_max
Spatial_video
Spatial_min
Spatial_average
0
1
2
3
4
5
6
7
8
9
10
02000400060008000100001200014000160001800020000
Pkt size (bytes)
Throughput (factors)
0.01
0.1
1
10
100
020406080100120140160
Load (%)
Delay (ms)
Low priority
Average
Medium priority
High priority
0.01
0.1
1
10
100
020406080100120140160
Load (%)
Delay (ms)
Low priority
Average
Medium priority
High priority
0.1
1
10
100
020406080100120140160
Load (%)
Delay (ms)
Low priority
Average
Medium priority
High priority
1
10
100
020406080100120140160
Load (%)
Delay (ms)
Low priority
Average
Medium priority
High priority
140
145
150
155
160
165
170
1.0:0.0:0.0 0.8:0.0:0.2 0.8:0.1:0.1 0.8:0.2:0.0 0.6:0.0:0.4 0.6:0.2:0.2 0.6:0.4:0.0 0.4:0.0:0.6 0.4:0.2:0.4 0.4:0.4:0.2 0.4:0.6:0.0
0.33:0.33:0.33
0.2:0.0:0.8 0.2:0.2:0.6 0.2:0.4:0.4 0.2:0.6:0.2 0.2:0.8:0.0 0.0:0.0:1.0 0.0:0.5:0.5 0.0:1.0:0.0
PPR (Low:Medium:High)
Throughput (%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a
b
c
d
e
f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a
b
c
d
e
f
N
rows
= 4
Grouping compatible transactions into minimum no. of rows
N
rows
= 3
Left End
Right End
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a
b
c
d
e
f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a
b
c
d
e
f
N
rows
= 4
Grouping compatible transactions into minimum no. of rows
N
rows
= 3
Left End
Right End
data
rows
T
N
´
total
trans
T
/
N
