Low Earth Orbit (LEO) satellite constellations face ground segment bottlenecks due to uneven user demand, which overloads Ground-to-Satellite Links (GSLs). The common practice of routing traffic to the nearest Ground Station (GS) to minimize latency often causes severe load imbalance. This paper proposes a load-aware assignment strategy that minimizes the maximum GSL utilization by routing traffic to non-nearest GSs via inter-satellite links. To maintain service quality, assignments are constrained by a latency threshold relative to the nearest-GS baseline. We formulate this as a mixed-integer linear program. Preliminary results using realistic Starlink constellation parameters show the proposed solution can reduce average maximum GSL utilization, mitigating ground segment congestion.

Emerging mega-constellations with numerous Low Earth Orbit (LEO) satellites actively provide pervasive Internet services worldwide, which are usually considered crucial components of Non-Terrestrial Networks (NTNs). However, the high mobility and limited coverage of LEO satellites introduce frequent handovers, causing network interruptions and degrading Quality of Service (QoS). While many efforts have been made to alleviate the impact of handovers on service provisioning from NTNs, they usually assume channel conditions are pre-determined and remain unchanged as satellites move, which is different from real situations and thus may experience significant performance degradation compared to theoretical analysis. In this paper, we proposeOracleto promise QoS-aware service provisioning in NTNs under dynamic channel conditions. Specifically, we mathematically formulate a channel model to characterize dynamic channel conditions in NTNs and develop a QoS maximization problem considering handover frequency and transmission capacity. To accommodate the dynamic nature of NTNs, we introduce a Model Predictive Control (MPC)-based controller to predict future network status and generate control strategies correspondingly, and leverage Digital Twin (DT) for real-time network status consideration. For higher efficiency, we further employ Generative Artificial Intelligence (GAI) with a safe transfer learning-based framework to enhance model adaptivity to environmental uncertainties and ensure feasible control decisions in real-world NTNs. Extensive simulation results under the real-world constellation demonstrate thatOraclecan enhance up to$3\times $QoS during online service provisioning.

Delivering seamless network services (e.g., video streaming, AR/VR, and cloud gaming) in Wide Area Networks (WANs) relies on flexible traffic management, which is facilitated by Software-Defined Wide Area Networks (SD-WANs), or SDN in WANs. In SD-WANs, control and data traffic usually share the same links for cost savings, a practice known as in-band control. The SDN controller can periodically send control messages to switches via control channels for routing policy updates to maintain satisfactory network performance. However, when a link failure occurs, control channels become disconnected. Since the controller can no longer communicate with the switches, the desired flexible traffic management cannot be promised. Although backup paths can be preconfigured to reconnect some control channels, high control latency may be introduced due to the meandering routes. Fortunately, commercial Low-Earth Orbit (LEO) mega-constellations, which provide pervasive and low-latency Internet services, present a promising solution to this control resiliency issue. Inspired by the rapid deployment of these LEO constellations, we propose a novel control plane design calledSpaceHelperto leverage the LEO satellite network for improving SD-WANs’ control resiliency.SpaceHelpersmartly integrates the LEO satellite network with terrestrial SD-WAN to reconnect control channels during link failure, which is formulated as an optimization problem to minimize overall control latency. A heuristic algorithm is proposed to solve the problem efficiently and guarantee prompt control channel reconnection. Performance evaluations are conducted using the Starlink constellation and real-world WAN topologies. Compared to the state-of-the-art in-band solution, we show thatSpaceHelpercan not only provide 100% resiliency, but also significantly reduce average control latency by up to 72.6% and 70.2% under GÉANT and Abilene topologies, respectively.

Emerging Low-Earth Orbit (LEO) mega-constellations face challenges such as limited bandwidth and highly variable user demand, which can degrade network performance and lead to inefficient satellite resource utilization. One promising solution is to enable Content Delivery Networks (CDNs) within LEO satellites by deploying cache-equipped satellites. However, many existing approaches rely on inter-satellite links, which are not widely used in practice and are typically activated only when terrestrial ground station coverage is insufficient. Furthermore, the dynamic coverage patterns of satellites and diverse regional content preferences add to the complexity of efficient CDN deployment in space. To address these challenges, we proposeSpaceCache+, a satellite-based CDN framework. We introduce a new metric,user benefit, that jointly captures user coverage and latency reduction to assess the effectiveness of cache satellite deployment. Recognizing that deployment typically occurs incrementally, we formulate theUser Benefit-centric Cache Satellite Deploymentproblem and design an efficient heuristic solution. To enhance content placement, we also propose a cache replacement policy based on zero-shot meta-learning, which adapts to both regional content popularity and satellite mobility. We evaluate the performance ofSpaceCache+using real-world constellation settings with CDN traces. Compared with benchmark strategies,SpaceCache+improves user benefit and cache hit ratio by up to 66.29% and 77.12%, respectively.

With the increasing deployment scale of Low Earth Orbit (LEO) mega-constellations, more satellites are expected to become visible to users simultaneously, bringing a new opportunity to optimize the network performance by properly assigning users to satellites. In this paper, we consider LEO mega-constellations without Inter-Satellite Links (ISLs) while assuming there are enough ground relays for inter-satellite communications. To establish a path from a user terminal to the nearest ground station (which serves as a gateway to the Internet), shortest path routing is usually adopted. To focus on the problem of user-satellite assignment, as well as to make routing more scalable, we divide the routing process into two parts: assigning the user terminal to a visible satellite, and finding a path from the satellite to the nearest ground station. For simplicity, shortest path routing is assumed in the second part. Aiming at minimizing the Maximum Satellite Utilization (MSU), a Mixed Integer Linear Programming (MILP), called Optimal User-Satellite Assignment (OUSA), is formulated. Performance evaluations are conducted based on Starlink Phase I mega-constellation and AWS ground station locations. As compared with the existing solutions, we show that the average load balancing performance can be improved by up to 33.29%.

Emerging Low Earth Orbit (LEO) mega-constellations face the challenge of limited bandwidth when providing global Internet services to users. Constructing Content Delivery Networks (CDNs) in LEO mega-constellations is viewed as a feasible solution to address this issue. However, deploying cache satellites, or satellites with CDN servers, for practical and pervasive content delivery is costly and challenging. To overcome this challenge, we consider LEO mega-constellations without inter-satellite links and formulate an integer linear programming problem called User Coverage-aware Cache Satellite Deployment, which aims to maximize the minimum user coverage among all time intervals with a given number of cache satellites. To efficiently solve this problem, a heuristic algorithm called SpaceCache is also proposed. Performance evaluations are conducted based on the Starlink mega-constellation with ground station locations and real-world CDN traces. Compared with benchmark algorithms, we show that the minimum user coverage performance can be improved by up to 41.82% and the cache hit ratio by up to 24.83%.

The growth of vehicular applications will inevitably require Base Stations (BSs) to simultaneously serve more Connected Vehicles (CVs) within limited bandwidth resources, which imposes a great challenge in interference management. Effective management of this interference is crucial for reliable Vehicle-to-Everything (V2X) communication, and necessitates accurate Channel State Information at the Transmitter (CSIT). In practice, the dynamic and unpredictable nature of CV movements prevents BS from obtaining perfect CSIT, leading to outdated information and threatening communication performance. In this study, we propose a Rate-Splitting Multiple Access (RSMA)-enabled V2X communication system to efficiently manage interference channels. We leverage a 1-layer RSMA scheme to relax the stringent requirement for perfect CSIT and enhance robustness to outdated information. Furthermore, we introduce Gruformer, a transformer-based model for improved CSIT prediction utilizing historical data. While longer forecasting horizons decrease accuracy, we present a game theory-based approach that significantly reduces processing time for power allocation, enabling timely decisions before CSIT becomes outdated. Simulation results reveal that Gruformer allows for more accurate predictions during rapid changes in channel conditions. Leveraging this high-quality CSIT, the proposed V2X system achieves a 20% increase in Weighted Ergodic Sum-Rate (WESR). Furthermore, the game theory-based approach delivers a 60% reduction in processing time while maintaining near-optimal performance.

In distributed training, workers collaboratively refine the global model parameters by pushing their updates to the Parameter Server and pulling fresher parameters for the next iteration. This introduces high communication costs for training at scale, and incurs unproductive waiting time for workers. To minimize the waiting time, existing approachesoverlap communication and computationfor deep neural networks. Yet, these techniques not only require the layer-by-layer model structures, but also need significant efforts in runtime profiling and hyperparameter tuning. To make the overlapping optimizationsimpleandgeneric, in this article, we propose a new Parameter Server framework. Our solutiondecouplesthe dependency between push and pull operations, and allows workers toeagerlypull the global parameters. This way, both push and pull operations can be easily overlapped with computations. Besides, the overlapping manner offers a different way to address the straggler problem, where the stale updates greatly retard the training process. In the new framework, with adequate information available to workers, they can explicitly modulate the learning rates for their updates. Thus, the global parameters can be less compromised by stale updates. We implement a prototype system in PyTorch and demonstrate its effectiveness on both CPU/GPU clusters. Experimental results show that our prototype saves up to 54% less time for each iteration and up to 37% fewer iterations for model convergence, achieving up to 2.86× speedup over widely-used synchronization schemes.

Smartwatch is a potential candidate for the Internet-of-Things (IoT) hub. However, the performance of smartwatch antennas is severely restricted by the smartwatch structure, especially when the antennas are designed by traditional methods. For adapting smartwatches to the role of IoT hub, a novel method of designing the multiband smartwatch antenna is presented in this article, aiming at increasing the number of frequency bands, omnidirectivity, and structural suitability. First, the fundamental structure (including the full screen and the system PCB) of the smartwatch is analyzed as a whole by characteristic mode analysis (CMA). Thus, abundant resources of characteristic modes are introduced. The fundamental structure is then modified as the radiator of a multiband antenna. Then, a nonradiating capacitive coupling element (CCE) excites the desired four 0.5${\lambda }$modes from this structure. This method could fully utilize the intrinsic modes of the smartwatch structure itself, thus exhibiting multiple advantages: significantly small size, smaller ground, omnidirectional radiation, and fitting to the full-screen smartwatch structure.

Load balance is an important issue in datacenter networks. The flowlet-based algorithms can balance the traffic with fine granularity and does not suffer the packet mis-sequencing problem. But their performances are rather limited or require extra communication overhead. In this paper, we propose a local load-aware algorithm called Dynamic Roulette Wheel (DRW). In DRW, the roulette wheel is adopted to select a new path for the flowlet according to the local load. Each source of multipath balances the traffic to all its egress links without the communication overhead. Moreover, the granularity of flowlet can be dynamically tuned from a single packet to the whole flow. Finally, the Capacity Aggregation (CA) mechanism is designed for the case of link or switch failure. We prove in theory that DRW can achieve the optimal global load balancing. The simulation results also show that DRW provides almost the best delay performance and the least packet out-of-order proportion overall among all existing flowlet switching algorithms.

We consider a hybrid segment routing (SR) network consisting of both IP routers and SR routers. We focus on exploiting the source routing capability of SR to enhance the performance of IP fast reroute. In particular, an IP router detects a local link failure, it can immediately reroute the affected packets by tunneling them to a SR router. The SR router will then forward the rerouted packets along a SR path such that when they exit the SR domain, they can reach the destination without traversing the failed link. In order to maximize the percentage of links that can be protected by fast reroute, two Integer Linear Programming (ILP) formulations are proposed for finding optimal repair paths for rerouted packets. ILP1 aims at minimizing the repair path length and ILP2 focuses on balancing the traffic load in the network. We further show that as the number of SR routers increases, the average repair path length will be shortened and the load balancing performance will be improved.

In segment routing, a packet is forwarded along a path identified by a segment list. A segment list consists of segment identifiers (SIDs). A node-SID identifies a shortest-path segment, and an adjacency-SID identifies a link segment. A K-segment path is a path with no more than K segments. In this paper, we study the problem of finding a set of K-segment paths to carry all the flows in a given traffic matrix such that the maximum link utilization in the network is minimized. We first show that the solutions found by K-LP, an existing linear programming (LP) approach, are not optimal because K-LP does not support adjacency-SIDs. Focusing on 2-segment paths, a new LP formulation, denoted by e2-LP, is designed to support adjacency-SIDs in part. To fully support adjacency-SIDs, a mixed integer linear programming (MILP), denoted by K-MILP, is designed. Since solving K-MILP is time-consuming, a simplified version (K-sMILP) is also proposed. Finally, K-sMILP is extended to prevent excessive flow splitting or using paths that are too long.

Segment routing is an emerging networking technology, where an arbitrary forwarding path can be identified using a list of segments. In this article, we study network monitoring in segment routing based on monitoring trails. Unlike the existing monitoring cycle, a trail is more flexible because it can be either open or closed (i.e., a cycle). Consider a network with a given set of k monitors, which are devices responsible for network monitoring. A monitoring trail must start and end at a monitor. The k-monitor cover problem is to cover every link in the network using trails such that each trail has no more than K segments and the total length of all trails is minimized. In this article, we prove that the k-monitor cover problem is NP-hard. To solve it, the first ILP is formulated and an efficient heuristic algorithm (k-MCA) is designed.

We focus on the problem of selecting a smallest subset of IP routers for upgrading to SDN switches to protect all single link failures in a given network, or the SDN candidate selection problem. In solving the problem, we also aim at minimizing the repair path length for reducing the delay experienced by the rerouted traffic and saving network bandwidth. The key enabler is a novel tunneling mechanism for constructing multi-tunnel repair paths by leveraging multiple SDN switches. Multi-tunnel repair paths provide additional flexibility in rerouting and a new SDN candidate selection (SCS) algorithm is then designed to take advantage of them. To further reduce the repair path length, we propose to replace the link-based tunneling adopted by fault-detection routers by destination-based tunneling. If the network traffic distribution is available, we further show that destination-based tunneling can be used to avoid network congestion.

For a given network topology and traffic matrix, we study the problem of finding a set of K-segment paths to carry all the traffic such that the maximum link utilization is minimized. A K-segment path is a path that can be identified by no more than K segment identifiers (SIDs). A SID can be either a node-SID or an adjacency-SID. But existing linear programming based solutions only support node-SIDs. In this paper, we first enhance an existing linear programming formulated for 2-segment paths only to support adjacency-SIDs. We call it e2-LP. Then a mixed integer linear programming, or K-MILP, is formulated for optimal solutions using K-segment paths. To reduce the complexity of K-MILP, a simplified formulation (K-sMILP) is also designed. Numerical results show that our proposed linear programs consistently outperform the existing solutions.

In routerless network-on-chip (NoC), any pair of cores are directly connected via at least one isolated ring, such that high-cost routers can be entirely abandoned. In this paper, we focus on the problem of designing a set of rings that guarantee the connectivity and minimize the average hop count for all core pairs. We propose the first optimal integer linear programing (ILP) to design rings for any n×m chips under any given wiring constraint, i.e., the maximum number of wires allowed between any adjacent cores. Numerical results show that our ILP performs much better and is more flexible than the existing algorithms. But our ILP is time-consuming to solve and future work should focus on reducing its complexity.

Multipath networks are widely used in data centers and load balancing is one of the most important technologies to improve their performances. Due to the ever-increasing in data center network size, existing load balancing algorithms face the challenges of efficiency and scalability. In this paper, we propose a new load balancing algorithm for large-scale, multi-tier fat-tree based data center networks. Different from the conventional architectures, a multi-tier fat-tree is divided into multiple routing domains according to the topology, and the routing processes in different domains are independent. The devices outside a routing domain can only access the specific interfaces provided by this domain. It is thus very convenient for deployment and modular upgrade. We also design a distributed and data-driven feedback mechanism, with which the routing decision is based on the global load information. We prove that the new algorithm can achieve perfect load balancing in multipath networks and show that the new algorithm outperforms all other load balancing algorithms in performance.

The emerging cloud applications require group communications. For these applications, multicast is a better choice than unicast, because it can significantly improve the performance by eliminating the duplicated packets generated by servers. However, existing multicast schemes for datacenters are either based on IP multicast or centralized scheduling. IP multicast is inefficient for datacenters as it cannot take full advantage of the multipath property. And centralized schemes suffer from single-point failure and scalability problems. To solve these problems, we propose MiniForest, a distributed multicast framework for large-scale datacenter networks. It consists of new routing algorithms and a dynamic group management mechanism. A new address mapping solution is then designed for compatibility to existing upper-layer applications. Based on the mapping solution, we propose an efficient load balancing strategy, with which a minimal forest is constructed for all multicast trees. To study the performance of the new multicast scheme in theory, we further provide an analytical model for Clos-based datacenter networks and analyze the overloading behaviors from a new perspective. We show that the distributed scheme can be used in any size of datacenters. It has much lower complexity and better performance than centralized schemes.

We consider an N×N input-queued switch with N dedicated unicast virtual output queues (VOQs) and one shared multicast queue (MQ) at each input port. An efficient two-bit single-iteration (2BSI) scheduling algorithm is proposed to concurrently schedule both unicast and multicast traffic. In the request phase, a two-bit request message is used to indicate not only the type of the request (unicast/multicast) but also its importance (strong/weak). In the grant phase, multicast request is granted first, then strong unicast request, and finally weak unicast request. To minimize inconsistencies in the distributed arbitration process, the notion of preferred unicast/multicast relationship is adopted to desynchronize/synchronize the arbitration decisions made by different inputs/outputs. As compared to the existing schedulers, our 2BSI is one of the simplest algorithms to implement, and yet extensive simulation results show that it provides one of the best delay-throughput performances.

We consider scheduling mixed unicast and multicast traffic with variable-size packets in an input-queued switch. When variable-size packets arrive at a switch input port, they will be segmented into cells (fixed-size packets), sent across the switch fabric, and reassembled at outputs. A scheduling algorithm should focus on optimizing packet performance rather than cell performance. In this paper, packet-mode scheduling is adopted such that cells of the same packet are sent back-to-back in consecutive slots. For efficiency, an iterative scheduling algorithm called three-bit single-iteration (3BSI) is proposed to concurrently schedule both unicast and multicast traffic. To the best of our knowledge, 3BSI is the first packet-mode scheduling algorithm for handling mixed traffic with variable-size packets. Despite its simplicity, extensive simulation shows that 3BSI provides excellent delay-throughput performance.

A monitoring-cycle can be easily implemented using segment routing and subject to a given maximum segment list size. In this paper, we propose the first ILP formulation (ILP1) to optimally solve the problem of covering every link in the network using monitoring-cycles and with minimum cycle cover length. To further conserve network bandwidth, we extend ILP1 to jointly minimize the total segment list size needed (ILP2). Since the time required to detect a network failure is affected by the longest cycle, we also extend ILP1 to jointly minimize the length of the longest cycle (ILP3). Finally, since all the existing network monitoring algorithms need to maintain a dedicated monitoring topology, we evaluate the gain brought by the monitoring topology using our ILPs. We found that the gain is limited, therefore we argue that maintaining a dedicated monitoring topology for monitoring-cycle construction is unnecessary.

Literature on coflow-aware packet scheduling for input-queued switches is limited. Yet most of them are offline algorithms, requiring (unrealistic) a priori knowledge of all coflows and solving (time-consuming) linear programming (LP) problems for determining their expected coflow completion times (CCTs). In this paper, we propose an efficient online packet scheduling algorithm called Critical Line First (CLF). In CLF, coflows are ordered based on their easy-to-find ideal CCTs, or would-be-CCTs. In scheduling, coflows with the smallest would-be-CCTs are considered first; for each coflow chosen, packets on most heavily loaded rows/columns, i.e., critical lines, of the coflow traffic matrix are scheduled first. To avoid starvation, we propose to limit the number of times a coflow can be preempted by other coflows. Extensive simulation results show that our CLF outperforms all existing algorithms.

To implement the new restricted access window (RAW) medium access control mechanism in IEEE 802.11ah, stations (STAs) must be assigned to RAW slots based on their association IDs (AIDs). In this paper, we first identify the fixed subgroup problem with the current round-robin slot assignment. To address it, a novel AID shuffle mechanism is proposed for each STA to distributedly find a different and distinct temporary AID in each RAW. Each STA then reuses the round-robin slot assignment with its temporary AID. As a result, the set of STAs assigned to each subgroup/slot are randomized, yet with the same subgroup size. Simulation results show that the transmission fairness problem with the original round-robin assignment is solved and the system throughput is also improved.

Network monitoring is important to guarantee the reliable end-to-end communications. Segment routing can be used to reduce network monitoring cost. The associated minimum cycle cover problem is to find a set of cycles such that (a) all cycles pass through a given monitor/source node, (b) each link in the network belongs to at least one cycle, (c) each cycle has a segment list no bigger than a given threshold K, and (d) the cycle cover length is minimized. To the best of our knowledge, SCMon is the first network monitoring scheme based on segment routing. But instead of directly minimizing the cycle cover length, SCMon focuses on reducing the number of cycles required. In this paper, four new algorithms, denoted by A, B, C and D, are proposed to solve the minimum cycle cover problem. Among them, algorithm A is a simple extension of SCMon by focusing on reducing the cycle cover length. Algorithm B adopts a new notion of symmetric cycles. Algorithm C enhances B by using a new path metric for constructing cycles. Algorithm D enhances C with a parallel cycle construction process. We show that all four algorithms outperform SCMon and when K is large, algorithms B, C and D can always find optimal solutions.

We consider a software defined network with a single controller communicating with all switches using a spanning tree rooted at the controller, or a controller tree. Depending on the availability of a backup link, a switch can be either protected or unprotected. A protected switch can bypass the failure of its parent switch by rerouting its traffic to its backup link, whereas an unprotected switch, together with its descendants in the tree, will be disconnected from the controller. The weight of a switch is the number of switches that will be disconnected if its parent switch fails. The weight of a controller tree is the total weight of all switches. The problem of finding a minimum weight controller tree is NP-hard. In this paper, we first introduce a new switch protection mechanism called sibling protection. Then an efficient controller tree construction algorithm called Distance-Degree Ordered Tree (DDOT) is proposed. A distinct feature of DDOT is that the tree is constructed and refined based on the controller-switch distance and the number of non- tree links a switch has. Compared with an existing tree construction algorithm, we show that DDOT can always find controller trees with close-to-optimal weight and bounded controller-switch distance.

We consider a software defined network (SDN) with a single controller communicating with all switches through a spanning tree rooted at the controller, or a controller tree. When a switch fails, its immediate downstream switch(es) will detect the failure. A downstream switch is protected if it has a neighbor whose path to the controller is not affected by this failure. By rerouting its traffic to this neighbor, the protected switch will bypass the failure (of its parent). On the other hand, an unprotected switch cannot bypass the failure using the local rerouting above; and the subtree rooted at the unprotected switch will be disconnected from the controller. Let the weight of an unprotected switch be the number of switches in the subtree. Then the weight of a controller tree is the total weight of all unprotected switches. In this paper, we focus on the problem of finding the minimum weight controller tree (mwCT). We first introduce a new switch protection mechanism called sibling protection. We then prove that the mwCT problem is NP-hard. To solve it, we formulate the first Integer Linear Programming (ILP). We show that the solutions obtained by an existing heuristic are far from optimal.

Traffic generated by sensors can be classified into three types, periodic, on-demand, and alarm-triggered. In an IEEE 802.11ah WLAN, AP needs to support up to 8,000 sensors. To alleviate the channel contention, two new mechanisms, target wake time (TWT) and restricted access window (RAW), are introduced to facilitate channel reservation. While TWT is tailor-made for periodic traffic, a RAW-based paging scheme is designed in this paper for contention-free scheduling of on-demand traffic. Notably, alarm events (e.g., fire) are unpredictable and yet alarm reporting is time-critical. It is thus inefficient to handle alarm-triggered traffic by a channel reservation scheme. To this end, we propose to enhance the contention-based DCF by using a standard-compliant timer mechanism called limited local extension (LLE). With LLE, when a sensor with a pending alarm-report detects an alarm-report sent by another sensor, it extends its own backoff timer by a random duration. The random duration is chosen such that the total amount of extension is bounded by the current contention window size. Based on an existing alarm event propagation model, simulation results show that LLE can greatly shorten the alarm-reporting time.

Prediction of stock market is a challenging task that has attracted researchers in various fields including the computational intelligence and finance. Since stock market data sets are intrinsically large, nonlinear and time-varying, it is extremely difficult to design models for forecasting the future directions with an acceptable accuracy. In this paper, an integrative and intelligent machine learning framework is proposed through combining cloud computing, machine learning and heuristic optimization. Essentially, the Support Vector Machine (SVM) method is extended with the Grid Search (GS) or Chemical Reaction Optimization (CRO) as a heuristic optimization method together with Principal Component Analysis (PCA) and Feature Noise Filter (FNF) to construct quantitative investment forecasting models for efficient executions on cloud computing platforms. To demonstrate the effectiveness of the proposed framework, the Hang Seng Index and some major stocks listed on the Hong Kong Exchange are predicted using the constructed models on a daily basis. The empirical results clearly indicate that the proposed integrative approach is promising and gives impressive performance in terms of the prediction accuracy.

In fat-tree data center networks, routing a packet from its source to destination includes two phases, upstream (i.e. from source to watershed switch) and downstream (i.e. from watershed switch to destination). The throughput/non-blocking performance of networks hinges much on the effects of two phases above. In this paper, we propose a new routing algorithm called Global Round Robin (GRR) for fat-tree data center networks. In the upstream of GRR, each packet is sent to a toppest switch based on the GRR relationship between its source and toppest switches. Then the packet can arrive at a toppest switch in a single time slot without any blocking and buffering en route. In the downstream of GRR, the packet is routed to its destination using self-routing. The simulation results show that GRR provides the best delay/throughput performance among the existing routing algorithms for data center networks.

We focus on designing efficient integrated schedulers for handling mixed unicast and multicast traffic. We consider an input-queued switch with a multicast-capable switch fabric. At each input port of the switch, there are N dedicated unicast VOQs and one shared multicast queue (MQ). An existing approach to the design of integrated scheduler (i.e., a sequential scheduler) is to run two component schedulers, one for multicast and one for unicast, sequentially in each time slot. To minimize the head-of-line blocking of multicast traffic, the multicast scheduler always runs first. But sequentially running two schedulers in each time slot is challenging, especially when the slot duration is small. In this paper, we first propose a pipelined integration of the two component schedulers (i.e., a pipelined scheduler), which allows twice the amount of time for each scheduler to execute. We then extend an existing single-bit- single-iteration unicast scheduler to ensure that even in the presence of multicast traffic, unicast traffic will be starvation-free. This is achieved by giving unicast traffic priority over multicast periodically. Finally, we present arguably the first single-bit-single-iteration multicast scheduling algorithm. Extensive simulation results show that our pipelined scheduler is efficient and provides delay-throughput performance comparable to the sequential scheduler.

We focus on designing efficient flow monitoring algorithms in SDN/OpenFlow by fully exploiting all three polling mechanisms, poll-single, poll-some and poll-all. Notably, the poll-some mechanism has not been adopted by any existing flow monitoring algorithm due to the inflexible match structure standardized in the early version of the OpenFlow specification. To enable the poll-some mechanism, we need to find out the minimum number of match structures required to exactly match all not-yet-covered flows at a switch. An efficient heuristic called Critical Column First (CCF) is then proposed for solving the Minimum Match Structure (MMS) problem. The idea is to consider the column of the flow matrix that can potentially identify the largest number of not-yet-covered flows first. With CCF, an existing flow monitoring algorithm called LFF [1] is extended to support all three polling mechanisms. We call it LFF+ algorithm. As compared with LFF, simulation results show that LFF+ can cut down the communication cost by about 54%.

Multicast becomes essential in data center networks, since more and more applications require group communication. The existing multicast scheduling algorithms in data center are Internet-based or centralized, which are either not efficient or not scalable. In this paper, we propose a Distributed and Dynamic Multicast (DDM) solution for fat-tree data center networks. It includes multicast initialization, routing algorithm and load-balancing policy. As DDM does not need the central controller, it is more scalable and much simpler. Moreover, each host can dynamically join in or quit from an existing multicast group without suspending the live traffic in this group. Our simulation results show that DDM provides the better delay/throughput performance than the existing centralized multicast scheduling algorithm.

An efficient iterative scheduling algorithm for input-queued switches, called round robin with longest queue first (RR/LQF), is proposed in this paper. RR/LQF consists of three phases: report, grant, and accept. In each phase, only a single-bit message per port is sent for reporting a packet arrival, granting an input for packet sending, or accepting a grant. In both the grant and accept phases, scheduling priority is given to the preferred input-output pairs first and the longest virtual output queuing (VOQ) next. The notion of the preferred input-output pair is to keep a global RR schedule among all the inputs and the outputs. By serving the preferred input-output pairs first, the match size tends to be maximized. By serving the longest VOQ next, the match weight is also boosted. When RR/LQF is executed for a single iteration (i.e., RR/LQF-1), we show by simulations that RR/LQF-1 outperforms all the existing single-bit-single-iteration scheduling algorithms. When RR/LQF is executed up to N iterations (i.e., RR/LQF-N), we prove that under any admissible traffic pattern, RR/LQF-N is stable with a speedup of 2-1/N, where N is the switch size. To the best of our knowledge, this is the first work showing that an iterative scheduling algorithm is stable with a speedup less than 2. We then generalize RR/LQF to become a class of algorithms that have the same speedup bound of 2-1/N. Efforts are then made to further reduce the implementation complexity of RR/LQF. To this end, the pipelined RR/LQF and RR/RR, a simpler variant of RR/LQF, are proposed.

A fat-tree network is scalable, but the probability of network faults also increases with the fat-tree size. Faulttolerant routing in fat tree is thus particularly important. Instead of relying on a time-consuming centralized recovery process, a fast local rerouting algorithm is highly desirable. A deflection based fast local rerouting algorithm, which we call it Local Rerouting by Deflection (LRD), was recently proposed to handle the network fault locally and dynamically. However, in LRD, all rerouted packets need to follow an elongated recovery path, which incurs extra propagation delay and additional network congestion. Aiming at addressing the inefficiency of LRD, a new local rerouting algorithm, called Local Rerouting by Backtracking (LRB), is proposed in this paper. With LRB, the faultdetecting switch immediately reroutes the affected packets back to where they came from until a V-turn switch is found. A V-turn switch is a switch from where an alternate minimal path to the destination is found. We show that LRB can minimize packet loss, incur no penalty in path length (except the small amount of backtracked in-flight packets), and treat backtracked packets as implicit fault notification. To ensure efficient implementation of our LRB algorithm, a simple self-routing (instead of table lookup) mechanism is devised to simplify the switch operation. As compared with LRD, we show by simulations that our LRB can minimize the TCP performance degradation caused by network faults.

The feedback-based switch [1] is a load-balanced switch consisting of two stages of crossbar switch fabrics. Each crossbar switch fabric is configured according to a predetermined and periodic seuqence of switch configurations. This eliminates the need for a central scheduler and makes it an excellent candidate for connecting tens of thousands of servers in a data center. But implementing feedback-based switch at the data center scale is challenging. A major issue is that crossbar switch fabrics are not scalable. In this paper, two scalable implementations of the feedback-based switch, dualbanyan network and Clos-banyan network, are proposed. With the dual-banyan implementation, the two crossbar switch fabrics are replaced by two modular banyan networks. To further reduce the dual-banyan network complexity, we merge the last stage of switch modules in the first banyan, the middle-stage ports, and the first stage of switch modules in the second banyan, to form a single stage of shared-memory switch modules. We call the resulting network Clos-banyan. We prove that the feedback-based switch implemented using either dual-banyan or Clos-banyan can realize all the switch configurations required by the original crossbarbased implementation, but at a much lower hardware cost. Since the packet scheduling algorithm is independent of how switch configurations are being realized, different implementations of the feedback-based switch provide the same excellent delaythroughput performance, as that already reported in [1].

A probabilistic quorum system (PQS) allows distributed services to be replicated on only a subset (quorum) of servers. The replicas can be kept consistent with high levels of assurance as long as any two quorums intersect with very high probability. PQS thus provides a means to trade off levels of consistency against the scalability and efficiency of a quorum system. When quorums are constructed by choosing members of the subset uniformly at random, the non-intersection probability can be easily computed. On a distributed system with n servers, uniform sampling is often conducted using random walk of length O(log n). To collect multiple uniform samples naively would require as many random walks. A number of works have relied on analytical results based on the Chernoff bound to reduce the number of random walks needed to collect multiple samples. Controlled flooding is another efficient method to collect multiple samples. In this paper we evaluate both methods analytically and found that quorums formed using either method cannot satisfy the non-intersection probability bound associated with quorum formed by uniform sampling. Our contributions are: (1) to show that overlay topology can be constructed to cache multiple random walks, (2) to show that repeated use of this cache to obtain multiple uniform samples leads to degradation of sample uniformity over time, and (3) to propose and evaluate graph re-wiring as a simple method to keep the cache fresh, to take advantage of overhead reduction of random walk caching while alleviating the degradation in sample uniformity.

To allow mobile devices to conserve energy, IEEE 802.11 standard specifies a power save mode (PSM). A station in PSM, i.e. a PSM-STA, will wake up at a predefined listen interval (LI) to receive frames buffered at the access point (AP) while it is sleeping. When a PSM-STA wakes up to receive a beacon and finds that there are no buffered frames, the PSM-STA experiences an unnecessary wakeup. In case of an unnecessary wakeup, the associated mode transition energy (i.e. from doze to awake and from awake back to doze) is wasted. According to the IEEE 802.11 standard, each STA chooses its own LI at the time of association, and the value chosen remains unchanged throughout its association duration. If LI=1, a STA wakes up at every beacon interval (BI). As a result, the data frame delay is minimized but the chance of unnecessary wakeup can be high. On the other hand, if a larger LI is used, the chance of unnecessary wakeup is reduced but the delay performance will suffer. Aiming at minimizing unnecessary wakeup without sacrificing delay performance, a dynamic listen interval (DLI) scheme is proposed in this paper. In essence, a STA increases its LI by one for every unnecessary wakeup experienced, and reset its LI to one when a necessary wakeup occurs. While more sophisticated schemes can be designed, we prefer this simple scheme for its compatibility with the existing standard. Simulation results show that when traffic is bursty, total energy consumption can be reduced without noticeable degradation in delay performance.

In an 802.11 WLAN, it can be observed that the shared wireless channel has a rush hour right after the periodic beacon frames. This is because mobile stations in power save mode (i.e. PSM-STAs) will wake up to retrieve data frames arrived at the access point (AP) while they are sleeping. PSM-STAs will stay awake until all buffered frames are retrieved. Notably, if the channel is congested, having all PSM-STAs staying awake will not improve the system delay performance but consume more power. Aiming at saving battery power while not affecting delay-throughput performance, a novel delayed wakeup (DW) scheme is proposed in this paper. Specifically, we divide a beacon interval (BI) into n sub-BIs. Then based on the amount of backlogged traffic, AP identifies and instructs “excess” stations to sleep immediately and wake up at a non-congested sub-BI later on. “Instructions” are judiciously encoded inside the modified traffic indication map (TIM) in the beacon frame. We show that our modifications are fully transparent to legacy stations. Last but not least, a seamless association procedure is designed to allow coexistence of legacy and DW-capable stations.

An efficient iterative scheduling algorithm for input-queued switches, called Round Robin with Longest Queue First (RR/LQF), is proposed in this paper. RR/LQF only needs a single bit for request, grant and accept messages respectively. The scheduling priority is given to the preferred input/output pairs first. Each single-bit request is actually an indication of a new packet arrival at the specific VOQ. Based on them, each output keeps track of the size of N VOQs destined to it. In the granting phase, if the preferred input's VOQ is empty, an output port j grants the (non-preferred) input that has the longest VOQ (among N VOQs destined to output j). In the accepting phase, if the preferred VOQ is not empty, input port accepts it directly. Otherwise, an input port i accepts the grant received by the long VOQ (among input i). When RR/LQF is executed for a single iteration, we show that RR/LQF outperforms SRR [15] in all simulations conducted. When RR/LQF is executed (up to N iterations) until finding the maximal size matching in input-queued switches, we prove that RR/LQF is stable with a speedup of 2-1/N, where N is the switch size. To the best of our knowledge, this is the first work showing that an iterative scheduling algorithm for input-queued switches can achieve a speedup requirement less than 2. Though the improvement is just 1/N we successfully tighten the speedup bound.

In a data center with TCP/IP communications, it is generally believed that packet-based load balancing is not suitable because the associated packet out-of-order problem will significantly lower the network utilization. In this paper, we first show that if packet-based load balancing is performed properly in a fat-tree based data center, the packet out-of-order problem is not as severe as most researchers believed. This is due to the fact that multiple (minimal) paths between any given pair of servers in a fat-tree are of the same hop count. If packets are evenly routed onto different paths, they will experience similar delay performance. As a result, the packet out-of-order arrivals at the receiver are usually within a small sequence number range. Notably, the fast retransmit (FR) algorithm in TCP will be triggered for resending the “lost” packet if three duplicate ACKs are received (i.e. FR threshold is three). To provide leeway for out-of-order packet arrivals due to packet-based load balancing, we propose to judiciously increase the FR threshold. Simulation results show that FR threshold values between 6 and 9 can effectively suppress unnecessary fast retransmits and at the same time, the impact to real packet losses is minimal. Compared to a flow-based load balancing scheme, we found that our packet-based load balancing with modified TCP consistently provides higher goodput and noticeably smaller delay.

Streaming layered video over peer-to-peer (P2P) networks has been recognized as an efficient way to address the receiver heterogeneity problem. The distinctive characteristics of layer encoded video also introduce complexities to data scheduling. In this paper, we propose a new data scheduling algorithm for layered P2P video-on-demand (VoD) streaming networks. Our algorithm consists of two parts: 1) layer adaptation, where peers adaptively adjust the number of subscribed layers to ensure a continuous playback of the highest possible video quality; and 2) piece selection, in which a peer selects a missing data piece to request based on its utility. The piece utility is calculated based on the playback constraint and the layer dependency of a piece. Through extensive packet-level simulations we show that our proposed data scheduling algorithm can effectively enhance the video playback quality.

Two major challenges in designing high-speed multicast switches are the expensive multicast switch fabric and the highly complicated central scheduler. While the recent load-balanced switch architecture uses simple unicast switch fabric and does not require a central scheduler, it is only good at handling unicast traffic. In this paper, we extend an existing load-balanced switch called feedback-based two-stage switch to support multicast traffic. In particular, an efficient multicast scheduling algorithm (FTMS) is designed. With FTMS, head-of-line (HOL) packet blocking at each input port is eliminated by adopting “pointer” queues. To cut down queuing delay, packet replication is carried out at middle-stage ports. As compared with other multicast scheduling algorithms, simulation results show that our FTMS always provides the highest throughput.

The feedback-based two-stage switch does not require a central scheduler and can provide close to 100% throughput [3]. But the number of crosspoints required for the two stages of switch fabric is 2N2, and the average packet delay performance (even under light traffic load) is on the order of O(N) slots, where N is the switch size. To improve the performance of feedback-based two-stage switch when N is large, we adopt the Clos network for constructing a large switch from a set of smaller feedback-based switch modules. We call it a Clos-feedback switch. The potential problem of packet mis-sequencing is solved by using application-flow based load balancing. With recursive decomposition, a Clos network can degenerate into a Benes network. We show that for a Clos-feedback switch, the number of crosspoints required is reduced to 4N(2 log2N-1) and the average packet delay is cut down to O(log2N) slots.

IP fast reroute (IPFRR) mechanisms are efficient in providing protection against link or router failure by invoking locally determined backup paths. But in the presence of a transient network failure, the path oscillates between backup and original paths, causing frequent packet out-of-order arrivals at a TCP receiver. Duplicate acknowledgments (DUP_ACKs) generated by the receiver will then trigger unnecessary TCP congestion control at the sender. In this paper, we propose a novel yet simple algorithm called duplicate acknowledgement suppression (DAS) for enhancing the TCP performance in the presence of IPFRR. DAS only requires a minor modification to the TCP implementation at the receiver side while leaving the sender intact. The key idea is to use the time-to-live field of an out-of-order packet to infer the cause of its out-of-order arrival. If that is deemed due to a transient network failure, no DUP_ACK will be generated. Simulation results show that our DAS algorithm yields noticeable goodput improvement.

Unlike peer-to-peer (P2P) file sharing, P2P live streaming systems have to meet real-time playback constraints, which makes it very challenging yet crucial to maximize the peer uplink bandwidth utilization so as to deliver content pieces in time. In general, this is achieved by adopting tailor-made piece selection and request-peer selection algorithms. The design philosophy is to regulate the network traffic and to balance the load among peers. In this paper, we propose a new request-peer selection algorithm. In particular, a peer in the network estimates the service response time (SRT) between itself and each neighboring peer. An SRT is measured from when a data piece request is sent until the requested piece arrives. When a peer makes a piece request, the neighbor with smaller SRT and fewer data pieces would be favored among potential providers. This is because smaller SRT implies excess serving capacity and fewer data pieces suggests less piece requests received. We evaluate the performance of our request-peer selection algorithm through extensive packet level simulations. Our simulation results show that the traffic load in the network is better balanced in the sense that the difference of the normalized number of data packets uploaded by each peer is getting smaller and the number of repeated piece requests generated by each peer (due to request failure) is significantly reduced. We also found that the load of streaming server is reduced, and the overall quality of service, measured by playback continuity, startup delay etc, is improved as well.

A general approach of designing input-queued multicast switch is to employ multicast switch fabric, where packets can be replicated inside the switch fabric. As compared with unicast switch fabric, the achievable traffic rate region of a switch can be increased, but it is still less than the admissible traffic rate region. In other words, achieving 100% throughput for any admissible multicast traffic pattern is not possible. In this paper, we first revisit the fundamental problems faced by input-queued switch in supporting multicast traffic. We then argue that multicast switch fabric is not necessary if a load-balanced approach is followed. Accordingly, an existing load-balanced two-stage switch architecture [12], consisting of unicast switch fabrics, can be adopted to provide 100% throughput for any admissible multicast traffic pattern. Since the two-stage switch requires no speedup in both switch fabric and packet buffers, we consider it a two-stage input-queued switch. It can be seen that its implementation complexity is much lower than conventional (single-stage) input-queued multicast switches. As compared with the work in [12], our approach is more systematic and we propose a more effective load balancing mechanism.

Communication overhead should be minimized when designing iterative scheduling algorithms for input-queued packet switches. In general, the overall communication overhead is a function of the number of iterations required per time slot (M) and the data bits exchanged in an input-output pair per iteration (B). In this paper, we aim at maximizing switch throughput while minimizing communication overhead. We first propose a single-iteration scheduling algorithm called Highest Rank First (HRF). In HRF, the highest priority is given to the preferred input-output pair calculated in each local port at a RR (Round Robin) order. Only when the preferred VOQ(i,j) is empty, input i sends a request with a rank number r to each output. The request from a longer VOQ carries a smaller r. Higher scheduling priority is given to the request with a smaller r. To further cut down its communication overhead to 1 bit per request, we design HRF with Request Compression (HRF/RC). The basic idea is that we transmit a single bit code in request phase. Then r can be decoded at output ports from the current and historical codes received. The overall communication overhead for HRF/RC becomes 2 bits only, i.e. 1 bit in request phase and 1 bit in grant phase. We show that HRF/RC renders a much lower hardware cost than multi-iteration algorithms and a single-iteration algorithm π-RGA [11]. Compared with other iterative algorithms with the same communication overhead (i.e. SRR [10] and 1-iteration iSLIP [6]), simulation results show that HRF/RC always produces the best delay-throughput performance.

Peer-to-peer (P2P) based video-on-demand (VoD) streaming service has been gaining popularity recently. Unlike live streaming, a VoD peer always starts its playback from the beginning of a stored video. The playback-points of different peers, as well as the amount of video contents/pieces they cached, depend on when they join the video session, or their viewing ages. As a result, the upload bandwidth of younger peers tends to be underutilized because older peers are not interested in their cached video pieces. The collaborative piece exchange among peers is undermined due to the unbalanced supply and demand. To address this issue, a playback-point based request peer selection algorithm is proposed in this paper. Specifically, when a peer requests a particular video piece, among the set of potential providers, a request is sent to the peer that has the smallest playback-point difference with itself. We call this request peer selection algorithm closest playback-point first (CPF). With CPF, peers with similar available content can be loosely grouped together for a more balanced collaborative piece exchange. Extensive packet-level simulations show that with CPF, the video playback quality is enhanced and the VoD server load is significantly reduced.

Capacity efficiency is a key issue in designing survivable Wavelength Division Multiplexing (WDM) networks. In this paper, we propose a two-step routing algorithm for dynamic lightpath protection in a WDM mesh network that is subject to wavelength continuity constraint. In other words, upon each call arrival a pair of link-disjoint active and backup lightpaths is to be found for carrying the call. To enhance the capacity efficiency, the resources on the backup lightpath can be shared for protecting different active lightpaths. Owing to the very different natures of active and backup lightpaths, active lightpath is found using the widest-shortest path (WSP) routing and backup lightpath is found using the shortest-widest path (SWP) routing. A distinct feature of our design is that we require both active and backup lightpaths of a call to use the same wavelength. Two major advantages of this feature are: a) source node can use the same laser for both active and backup lightpaths, and b) the scalability issue related to route advertisement is solved. As compared with some existing schemes, we show that our two-step routing algorithm yields noticeably higher capacity efficiency and lower call blocking probability.

Due to the massive use of parallel and distributed operations of inputs and outputs, iterative scheduling algorithms are attractive in finding a maximal size matching for an input-queued switch. For constructing a large high-speed switch, a distributed multi-chip implementation of an iterative scheduling algorithm should be followed. Since different chips may locate on different switch linecards and linecards can be separated by tens of meters, the propagation delay between chips/linecards is non-negligible. This calls for a pipelined implementation of a single-iteration scheduling algorithm. In this paper, an efficient, pipelined single-iteration algorithm called Distributed Longest Queue First (D-LQF) is proposed. In D-LQF, exhaustive service policy is adopted for reusing the matched input-output pairs in the previous time slot. To avoid incorrectly granting an empty VOQ from transmission (caused by inter-chip latency), each output keeps track of the lengths of all VOQs destined to it. As compared with other single-iteration scheduling algorithms, extensive simulation results show that D-LQF provides the best delay-throughput performance.

In this paper, we discuss the opportunistic multicast scheduling (OMS) in a wireless network using erasure codes. Originally proposed for channels with erasures such as internet, erasure codes are found useful in wireless multicast to achieve better tradeoff between multiuser diversity and the multicast gain. In this work we investigated how to design an opportunistic multicast scheduling scheme which can efficiently improve the per user throughput capacity in a wireless network using erasure codes. Aiming at maximize the throughput, we proposed a maximal OMS (M-OMS) scheme which is inspired by the unicast maximal opportunistic scheduling. We build a system model and provide theoretical analysis on proposed M-OMS scheme. The proposed scheme shows substantial improvement over existing fixed selection ratio opportunistic multicast scheduling schemes (F-OMS).

An m-cycle is an optical loop-back pre-cross connection of a supervisory wavelength. In a cycle-based link failure detection scheme, a monitor transmits supervisory signals onto the m-cycle, receives them back, and compares with the one sent for fault detection. In this paper, we propose the notion of super monitor for cutting down the hardware cost of monitors. Instead of having a dedicated monitor for each m-cycle, a super monitor is placed at the junction of a set of m-cycles. Supervisory signals from a single laser source are split simultaneously onto multiple m-cycles using an optical splitter. As the cost of a monitor is usually dominated by the laser, co-locating conventional monitors to form a super monitor for cost reduction makes sense. To this end, we formulate the problem of determining the optimal number of super monitors as well as their locations as an add-on feature of any existing cycle-based link failure detection scheme. We call it monitor placement problem. We follow a two-step approach for its solution, where in the first step, we enumerate each candidate cycle-set (i.e., a set of m-cycles where the super monitor can be placed); and in the second step, a simple integer linear programming (ILP) is constructed for placing super monitors at some candidate cycle sets. Numerical results show that by properly placing super monitors, considerable amount of monitoring cost can be saved.

Source-independent broadcasting protocols select a subset of nodes in a network as broadcasting nodes to cover the entire network. The selection of broadcasting nodes is performed prior to actual message transmission. These broadcasting nodes collectively form a connected dominating set or CDS. Aiming at finding a minimum CDS, a source-independent broadcasting protocol consists of two phases. In this paper, we propose to add a third phase to eliminate unnecessary nodes in a CDS while ensuring all remaining CDS nodes are still connected. We call it the redundant node screening phase. This paper shows that this new phase is a very important element that has been ignored by existing source-independent broadcasting protocols. When applying the new phase on existing broadcasting protocols,the savings in terms of number of nodes in the CDS could be as high as 21% in a 1000m x 1000m network of 20 nodes.

A typical broadcasting protocol for wireless network usually involves fixed transmission power that covers, for example an area within 250 meters (m). However, it is often unnecessary to broadcast using fixed power because a node that needs to be covered may just be 100m away. By reducing the transmission power enough to cover this node, energy expenditure would be reduced, thus, prolonging the lifetime of battery-powered wireless networks such as Mobile Ad Hoc Networks (MANETs) and Wireless Sensor Networks (WSNs). Existing source-dependent broadcasting protocols do not have any mechanisms for adjusting the transmission power of nodes. Therefore, this paper proposes some effective mechanisms based on local neighborhood knowledge, while ensuring the overall network is still covered. Results of extensive simulations confirm the effectiveness of the proposed protocols in reducing energy consumption.

A hybrid electro-optic router is attractive, where packet buffering and table lookup are carried out in electrical domain and switching is done optically. In this paper, we propose a load-balanced optical switch (LBOS) fabric for a hybrid router. LBOS comprises N linecards connected by an N-wavelength WDM fiber ring. Each linecard i is configured to receive on channel λi. To send a packet, it can select and transmit on an idle channel based on where the packet goes. The packet remains in the optical domain all the way from an input linecard/port to an output linecard/port. Meanwhile, the loading in the ring network is perfectly balanced by spreading the packets for different destinations to use different wavelengths, and packets for the same destination to use different time slots. With the pipelined operation of the LBOS, we show that LBOS is an optical counterpart of an efficient load-balanced electronic switch, and close-to-100% throughput can be obtained. To address the ring-fairness problem under the inadmissible traffic patterns, an efficient throughput-fair scheduler for LBOS is also devised.

In this paper, we study opportunistic multicast scheduling (OMS) in a wireless network with a central base station (BS) broadcasting a common packet to multiple users with different instantaneous channel conditions. Our objective is to minimize the broadcast latency, which is defined as the total transmission time required for all intended users in a multicast group to receive the packet. Based on the instantaneous channel conditions, BS can send a packet at different transmission rates. Sending at a higher rate allows a shorter packet transmission time, but only a limited number of users with sufficient channel quality can receive the packet. To reach all users in a multicast group, the packet must be transmitted multiple times. We can see that the broadcast latency depends on the transmission rate used and the number of transmissions required. In this paper, we formulate the problem of minimizing broadcast latency as a dynamic programming problem, and a close-loop optimal opportunistic multicast scheduling scheme (OOMS) is derived.

The retransmission timeout (RTO) timer used in TCP has long been standardized by the IETF in RFC2988, referred to as the TCP-RFC in this paper. Over the years, various deficiencies have been identified. In this paper, we focus on the implicit RTO offset problem, where the exact timeout limit of each packet is stretched by restarting the timer using the current timer value on the arrival of each acknowledgement (that acknowledges some new data). It would result in a slow timeout detection which unavoidably degrades the TCP throughput. In this paper, we first present a review of the TCP-RFC with special focus on the implicit RTO offset problem. Based on the insights obtained, we propose an enhanced RTO timer implementation, called E-RTO, for TCP. The implicit RTO offset is removed by mimicking the operation of a multi-timer implementation using a single timer. We then compare our E-RTO with TCP-RTO by simulations. We show that the faster timeout detection of our E-RTO leads to a throughput improvement of up to 3%.

Deterministic approach to broadcasting in Mobile Ad Hoc Networks (MANETs) is effective in reducing redundant broadcasting. In this approach, a transmitting node selects a subset of its immediate or 1-hop neighbors to rebroadcast the message such that all its 2-hop neighbors will receive the message, or being covered. In order to reduce redundant broadcasting, the set of 1-hop neighbors to be covered should be reduced as much as possible. Another important aspect that affects the effectiveness of a deterministic broadcasting protocol is the termination condition that inhibits a node from transmitting a particular message unnecessarily. However, existing termination conditions are not optimized. We propose a new covered/uncovered termination condition where each node is assigned with covered/uncovered status. In this paper, we show that our covered/uncovered termination condition ensures full network coverage, does not incur any control message overhead, and yet requires the least number of rebroadcasting nodes. When we apply the termination condition to some existing deterministic broadcasting protocols, the saving in the number of broadcasting nodes can be as significant as 45% when there are 100 nodes randomly distributed in an area of 1000 × 1000 m2.

With the increasing popularity of wireless mesh networks (WMNs), broadcasting traffic (e.g. IP-TV) will contribute a large portion of network load. In this paper, we consider a multi-channel multi-interface WMN with real time broadcast call arrivals. Aiming at maximizing the call acceptance rate of the network, an efficient broadcast tree construction algorithm, called Schedule-based Greedy Expansion (S-Expand), is designed. Unlike the existing time fraction approach, which focuses on assigning time fractions to tree links to guarantee the existence of a feasible schedule, we follow the approach of joint routing and scheduling. The proposed S-Expand algorithm packs non-interfering transmissions to use the same time slots; this would allow more flexibility in accepting future calls. Simulation results show that S-Expand achieves higher call acceptance rate than the traditional time fraction approach.

In TCP, a spurious packet retransmission can be caused by either spurious timeout (STO) or spurious fast retransmit (SFR). The “lost” packets are unnecessarily retransmitted and the evoked congestion control process causes network underutilization. In this paper, we focus on spurious retransmission detection. We first present a survey on some important and interesting spurious retransmission detection algorithms. Based on the insights obtained, we propose a novel yet simple detection algorithm called split-and-retransmit (SnR). SnR only requires a minor modification to the TCP sender while leaving the receiver intact. The key idea is to split the retransmitted packet into two smaller ones before retransmitting them. As the packet size is different, the ACK triggered will carry different ACK numbers. This allows the sender to easily distinguish between the original transmission and the retransmission of a packet without relying on, e.g., TCP options. We then compare our SnR with STODER, F-RTO and Newreno under both loss-free and lossy network environments. We show that our SnR is resilient to packet loss and yields good performance under various simulation settings.

Broadcasting in mobile ad hoc networks (MANETs) usually involve fixed transmission power that covers, for example an area within 250 meters. However, it is often unnecessary to broadcast using fixed power because a node that needs to be covered may just be 100 meters away. By reducing the transmission power enough to cover this node, energy expenditure would be reduced, thus, prolonging the lifetime of a battery-powered MANET. Existing works on variable power broadcasting based on local information are effective in achieving this objective. However, they are not optimized and can be improved by dynamically adjusting the transmission power based on where a broadcast message comes from. This paper proposes simple mechanisms based on local knowledge to adjust the transmission power dynamically and incorporates a timer suppression mechanism to further enhance the effectiveness of the protocols in reducing energy expenditure. Results of simulation studies confirm the effectiveness of the proposed enhancements.

A framework for designing feedback-based scheduling algorithms is proposed for elegantly solving the notorious packet missequencing problem of a load-balanced switch. Unlike existing approaches, we show that the efforts made in load balancing and keeping packets in order can complement each other. Specifically, at each middle-stage port between the two switch fabrics of a load-balanced switch, only a single-packet buffer for each virtual output queueing (VOQ) is required. Although packets belonging to the same flow pass through different middle-stage VOQs, the delays they experience at different middle-stage ports will be identical. This is made possible by properly selecting and coordinating the two sequences of switch configurations to form a joint sequence with bothstaggered symmetry propertyandin-order packet delivery property. Based on the staggered symmetry property, an efficient feedback mechanism is designed to allow the right middle-stage port occupancy vector to be delivered to the right input port at the right time. As a result, the performance of load balancing as well as the switch throughput is significantly improved. We further extend this feedback mechanism to support the multicabinet implementation of a load-balanced switch, where the propagation delay between switch linecards and switch fabrics is nonnegligible. As compared to the existing load-balanced switch architectures and scheduling algorithms, our solutions impose a modest requirement on switch hardware, but consistently yield better delay-throughput performance. Last but not least, some extensions and refinements are made to address the scalability, implementation, and fairness issues of our solutions.

In this paper, we consider the problem of constructing bandwidth-guaranteed multicast tree in multi-channel multi-interface wireless mesh networks. We focus on the scenario of dynamic multicast call arrival, where each call has a specific bandwidth requirement. A call is accepted if a multicast tree with sufficient bandwidth on each link can be constructed. Intuitively, if the carried load on both the most-heavily loaded channel and the most-heavily loaded node is minimized, the traffic load in the network will be balanced. If the network load is balanced, more room will be available for accommodating future calls. This would maximize the call acceptance rate in the network. With the above notion of load balancing in mind, an Integer Linear Programming (ILP) formulation is formulated for constructing bandwidth-guaranteed tree. We show that the above problem is NP-hard, and an efficient heuristic algorithm called Largest Coverage Shortest-Path First (LC-SPF) is devised. Simulation results show that LC-SPF yields comparable call acceptance rate as the ILP formulation, but with much shorter running time.

Broadcasting is a process of delivering a message to all nodes in a network. While it is important to ensure that all nodes get a copy of the broadcast message, minimizing the number of sending nodes is equally important especially in resource-constrained wireless networks. Existing broadcasting protocols based on self-pruning are ineffective in achieving these objectives. Therefore this paper proposes two protocols based on simple timer mechanisms to prioritize broadcasting of messages such that node with most uncovered neighbors rebroadcast first. Additionally a timer suppression mechanism is proposed to further enhance the effectiveness of the broadcasting protocol. Compared with an existing protocol, extensive simulation experiments confirm that the proposed protocols achieve better performance.

We consider multi-channel multi-interface wireless mesh networks with a schedule-based MAC protocol, where conflict-free transmission is ensured by requiring links assigned with the same channel and within the mutual interference range of each other to be active at different time slots. When a (point-to- multipoint) multicast call arrives, the call is accepted if a multicast distribution tree can be established for connecting the source node with all the receiving nodes, and with sufficient bandwidth reserved on each link. Otherwise, the call is rejected. To maximize the call acceptance rate, the multicast tree must be constructed judiciously upon each call arrival. Aiming at minimizing the carried load on the most-heavily loaded channel, and maximizing the residual capacity of the most heavily loaded node, an integer linear program (ILP) is formulated for multicast tree construction. Since solving ILP can be time-consuming, an efficient heuristic algorithm is then proposed. We compare the two tree construction algorithms by simulations. We found that both algorithms give comparable call acceptance rate, but the heuristic algorithm requires much shorter running time.

We introduce Cooperative Fast Protection (CFP) as a novel protection scheme in WDM networks. CFP achieves capacity-efficient fast protection with the features of node-autonomy and failure-independency. It differs from p-cycle by reusing the released working capacity of the disrupted lightpaths (i.e. stubs) in a cooperative manner. This is achieved by allowing all the failure-aware nodes to switch the traffic, such that the disrupted lightpaths can be protected even if the end nodes of the failed link are not on the protecting cycles. CFP also differs from FIPP p-cycle by not requiring the source node of the disrupted lightpath on the protecting cycle. By jointly optimizing both working and spare capacity placement, we formulate an ILP for CFP design. Numerical results show that CFP significantly outperforms p-cycle by achieving faster protection with much higher capacity efficiency.

This paper presents a distributed polynomial algorithm for finding the maximum bandwidth path in Wireless Mesh Networks (WMNs). Our proposed algorithm can be applied for designing the proactive hop-by-hop routing protocol with bandwidth guarantee. To the best of our knowledge, our work is the first distributed path calculation algorithm in WMNs.

Widest spanning tree is a broadcast tree with its bottleneck link bandwidth maximized. It provides a cost effective broadcasting solution in multi-channel multi-interface wireless mesh networks. To find the widest spanning tree, existing algorithms jointly consider channel assignment, routing and scheduling while assuming the number of network interface cards (NICs) at each node is given. In this paper, we treat the number of NICs at each node as a design parameter, whereas the total number of NICs in the system is given. By properly placing more NICs to more "critical" nodes, the bandwidth of the spanning tree can be further increased. To this end, a new integer linear programming (ILP) is formulated for solving the widest spanning tree problem based on joint optimization of interface placement, channel assignment, routing and scheduling. Numerical results show that interface placement provides a significant boost to the bandwidth of the widest spanning tree found.

The capacity of an IEEE 802.11-based multi-hop wireless network is limited. By effectively utilizing multiple non-overlapping channels and multiple interfaces, collision and co-channel interference can be reduced. This allows more concurrent transmissions and thus enhances the network capacity. In this paper, we introduce an efficient distributed joint channel assignment and routing protocol, called J-CAR1. Unlike existing schemes, J-CAR allows a data interface to dynamically change its working mode between send and receive on a call-by-call basis, which enhances the utilization of both interface and channel. In J-CAR, channels are negotiated and assigned to active links in conjunction with the on-demand routing process. At each hop, J-CAR conducts a local optimization by selecting the least interfered channel according to the channel interference index. The channel interference index is designed by taking both the protocol and physical interference models into consideration. To find the least interfered path for network load balancing on a global scale, J-CAR employs a length-constrained widest-path routing. The “width” of a path is determined by the interference level of its bottleneck link. With an adjustable threshold on the path length (with respect to the shortest-path), the excessively long path can also be avoided. We show that with a comparable complexity as the existing schemes, J-CAR provides much higher system goodputs and shorter end-to-end packet delays.

With the enhancement in channel bandwidth and mobile devices, more broadcast applications will be deployed in the wireless mesh networks (WMNs). While traditional approaches focus on finding a single broadcast tree in the network, we aim at maximizing the number of broadcast trees/calls that can be carried. In this paper, we first formulate an Integer Linear Program (ILP) for solving the minimum-channel-utilization broadcast tree problem in multi-channel multi-interface WMNs. In our ILP, channel assignment, routing, and scheduling are jointly considered for finding a broadcast tree that can minimize the maximum channel utilization. Intuitively, this balances all the accepted traffic load in the network, which in turn maximizes the chance of accepting future calls. However, solving ILP usually takes time and is less suitable for a system with real-time call arrival. An efficient heuristic algorithm is then designed. Our simulation results show that the proposed heuristic gives real-time response and provides comparable good performance as the ILP approach.

We consider optical layer monitoring schemes for fast link failure localization in WDM mesh networks. A new concept monitoring trail (m-trail) is proposed. It differs from the existing monitoring cycle (m-cycle) concept by removing the cycle constraint. As a result, m-trail provides a more flexible all-optical monitoring structure which includes simple, non-simple m-cycles and open trails as special cases. Aiming at minimizing the total monitoring cost, an integer linear program (ILP) is formulated for m-trail design. Numerical results show that the m-trail based scheme significantly outperforms its m-cycle based counterpart.

In the past few years, many new development toolkits such as the Nebula2 and/or mobile technologies including the WiFi or mobileTV have opened up exciting learning opportunities on mobile devices. On top of it, new technologies continue to fuel the rapid growth of newly merged fields of research like the edutainment for educational entertainment. In a recent teaching development project, we have developed an interactive game platform to facilitate learning and more importantly the spirit of teamwork for collaborative problem-solving on desktop and pocket PCs. With the great challenges imposed by globalization, we strongly believe that learning to collaboratively analyze and then apply the ldquoappropriaterdquo knowledge to solve a specific problem is always the key to success. In this paper, we discuss about an on-going work, and share our relevant experience in system development. Furthermore, evaluation strategies will be thoroughly examined. After all, our work shed light on many interesting directions for future exploration.

The concept ofp-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. Compared to a simpler-cycle, a non-simplep-cycle can traverse a node or span multiple times. As a result, non-simplep- cycles can better explore mesh connectivity of a network. On the other hand, the recently proposed PXT (Pre-Cross-Connected Trail) concept removes the cycle constraint by allowing arbitrary protection trails. In this paper, we carry out a comparative study among these fast protection schemes, and formulate ILPs (Integer Linear Programs) for non-simplep-cycle and PXT design. As far as we know, our ILP for non-simplep-cycle design is the first one without candidate cycle enumeration, and our ILP for PXT design is the first one proposed in this area. Based on our ILPs, we find simple, non-simplep-cycle and PXT solutions for a simple network. We show that the required spare capacity for 100% protection in each scheme is reduced in the same order above.

Efficient broadcast schemes are essential in wireless mesh networks (WMNs) for minimizing the content update time. In this paper, we consider the widest spanning tree problem in a multi-channel multi-interface WMN, where the width of a tree is determined by the bottleneck link bandwidth. To the best of our knowledge, we present the first effort in solving the widest spanning tree problem using mathematical formulation. In our model, we jointly consider and solve the problems of channel assignment, routing, scheduling and server/root placement. Unlike other spanning tree approaches, we allow WMN nodes to have heterogeneous number of network interface cards (NICs), and multiple NICs of a node can share the same assigned set of channels. To find a practical schedule, we also introduce the channel conflict graph and NIC constraint graph, and show that the associated scheduling problem is equivalent to the classic graph coloring problem.

In multi-channel multi-interface mobile ad hoc networks (MANETs), channel assignment and routing can be conducted jointly to improve network capacity. In this paper, we first extend an existing joint channel assignment and routing scheme (J-CAR) to support bidirectional path setup. Compared with unidirectional path setup schemes, the amount of broadcast control traffic and path setup delay is roughly halved. Then, a new channel interference index is designed to facilitate channel selection at each hop. Since both distance and the number of interfering sources are considered, the new interference index allows channels with better quality to be selected first. To further improve network capacity, the loading in the network should be balanced. To this end, a new length-constrained widest-path routing algorithm is designed, where the "width" of a path is determined by the interference level of its bottleneck link. With an adjustable threshold on the path length (with respect to the shortest path), the excessively long path can also be avoided. Simulation results show that, due to the improved load balancing and channel selection performance, our new joint channel assignment and routing algorithm (J-CAR/widest) outperforms the existing J-CAR and its two variants (J-CAR+index and J-CAR+widest) by delivering higher system goodputs and lower end-to-end packet delays.

Fast link failure detection in all-optical networks (AONs) can be achieved using monitoring cycles (m-cycles). An m-cycle is a loop-back optical connection of supervisory wavelengths with a dedicated monitor. Compared to the channel-based or link-based monitoring schemes, m-cycle based schemes require much less number of monitors. In this paper, we propose an ILP (Integer Linear Program) formulation for m-cycle design to minimize the network cost. Our contributions are two-fold: 1) non-simple m-cycles are enabled; and 2) an efficient tradeoff is allowed between the monitor cost and the bandwidth cost. Numerical results show that our algorithm outperforms existing algorithms with a significant performance gain. © 2007 IEEE.

The concept of p-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. To construct p-cycles, conventional algorithms need to enumerate all the candidate cycles in the network before ILP (Integer Linear Program) can be applied to find the optimal solution. To reduce the size of the candidate set and thus speed up the optimization process, heuristic algorithms are proposed for candidate cycle pre-selection at the cost of lower solution quality. Recently, some interesting ILP formulations were proposed to construct p-cycles without candidate cycle enumeration/preselection. But they tend to require a long running time. Following the approach of no candidate cycle enumeration, we formulate a new ILP based on flow conservation in this paper. Numerical results show that our new ILP runs much faster than the existing ones.

In this paper, we evaluate the performance of New- reno analytically by explicitly modeling its slow-start, congestion avoidance, fast retransmit, fast recovery and retransmission timeout mechanisms. Two packet loss models, bursty and independent, are adopted in our study. The accuracy of our proposed New-reno model is verified by simulations. The performance of New-reno is then compared with Sack using the derived analytical models. We show that New-reno outperforms Sack when the round trip time is short and the bursty loss event probability is low.

Assume the reliability of a connection is determined by the number of distinct risks associated with the path. We study the most reliable routing for WDM networks with arbitrary risk distribution in this paper. We first focus on the min-risk single path (MRSP) problem, in which a single most reliable path is to be established between a given source-destination pair. To solve MRSP, a simple label-setting (Simple-LS) algorithm is proposed by iteratively setting every node with a diminishing path-risk set (i.e. the label of a node). We then extend Simple-LS to find up to K lowest risk paths in each iteration, called K-path LS algorithm. Comparing to existing algorithms, we show that K-path LS can find paths with much fewer risks. We then define the original most reliable path pair (MRPP) problem. In MRPP, a pair of risk-disjoint paths must be established for each connection request. Unlike existing path pair routing problems, absolute priority is given to minimizing the risk number on active path. To solve MRPP, we extend K-path LS algorithm to K-pair LS, in which a joint search for risk-disjoint and most reliable path pairs is conducted. Comparing with algorithms with similar nature, we show that K-pair LS finds more risk-disjoint paths and with fewer risks.

Burst loss and delay are two main issues in optical burst switching (OBS) networks. In OBS, if the hop-count between the source-destination node pair can be reduced, both the control packet and the corresponding data burst will suffer less risk of contention, and the delay caused by offset time will be reduced as well. Therefore, it is meaningful to overlay OBS upon a virtual topology with reduced network diameter and average hop-count. In this paper, a novel algorithm LWMD (Least Weight Minimum Diameter) is proposed to construct virtual topology for this goal. Based on the virtual topology obtained, two traffic accommodation schemes are also designed to provision wavelengths for a given traffic matrix. This provides a comprehensive solution to improve the performance of OBS networks.

The notion of p-cycle (preconfigured protection cycle) allows capacity efficient schemes to be designed for fast span protection in WDM mesh networks. Conventional p-cycle construction algorithms need to enumerate/pre-select candidate cycles before ILP (integer linear program) can be applied. In this paper, we propose a new algorithm which is only based on ILP. When the required number of p-cycles is not too large, our ILP can generate optimal/suboptimal solutions in reasonable amount of running time.

A novel feedback mechanism is proposed in this paper to enhance the performance of load-balanced two-stage switches. The key idea is to properly select and coordinate the two sequences of TV deterministic configurations used by the two stages of switch fabrics, thereby forming a joint sequence with bothstaggeredsymmetrypropertyandin-orderpacketdeliveryproperty. With a single-packet-buffer-per-middle-stage VOQ, a joint sequence with both properties is first constructed. Then based on it, an efficient feedback mechanism is designed to allow the right piece of middle-stage port occupancy information to be delivered to the right input port at the right time. In each time slot, an input selects a packet for sending based on its port-based scheduling algorithm. To this end, three simple port-based scheduling algorithms, RR, LQF and EDF, are also proposed. Simulation results show that with our proposed feedback mechanism, the three scheduling algorithms gives an unbeatable delay-throughput performance under various traffic conditions.

We propose an efficient joint channel assignment and routing protocol (J-CAR) for multi-channel multi-interface mobile ad hoc networks (MANETs). Aiming at overcoming the limitations of the existing channel assignment and routing algorithms, J-CAR negotiates a channel at each active link during the route setup process. It has the following major features: (a) a pre-determined common control channel is used by every node for routing and channel negotiation; (b) control packets for data transmission (RTS, CTS & ACK) are carried by the associated data channels; (c) the spare capacity on the control channel can be used for data transmission; (d) an interface is free to change its working modes between send and receive; and (e) an interface can tune to any data channels for data sending or receiving at the cost of switching overhead. With J-CAR, a more flexible assignment of interfaces, channels, and the working mode of each interface can be rendered. The performance gain brought by J-CAR is substantiated by extensive simulation results.

A novel feedback-based two-stage switch architecture is presented in for solving the packet mis-sequencing problem in designing two-stage switches. With this architecture, each middle- stage port j piggybacks an N-bit VOQ occupancy vector to an output port k in each time slot. As output k and input k reside on the same line-card, input k schedules a packet for sending in the next time slot based on the N-bit feedback. In this paper, we focus on designing efficient packet scheduling algorithms for cutting down the number of feedback bits required while minimizing the negative impact to switch performance. The basic idea is to partition N VOQs at a middle-stage port into M non-overlapped sets. In each time slot, only the queue occupancies of selected sets are sent. By exploiting the otherwise wasted bandwidth in the first-stage switch, each input port is also allowed to piggyback its VOQ status to middle-stage ports. This allows each middle-stage port to intelligently select the sets of VOQs for feedback. Extensive simulation results show that among our proposed scheduling algorithms, the set-feedback scheduler provides the best performance under various traffic conditions.

A hybrid electronic/optical packet switch consists of electronically buffered line-cards interconnected by an optical switch fabric. It provides a scalable switch architecture for next generation high-speed routers. Due to the non-negligible switch reconfiguration overhead, many packet scheduling algorithms are invented to ensure performance guaranteed switching (i.e. 100% throughput with bounded packet delay), at the cost of speedup. In particular, minimum delay performance can be achieved if an algorithm can always find a schedule of no more than N configurations for any input traffic matrix, where N is the switch size. Various minimum delay scheduling algorithms (MIN, alphai-SCALE and QLEF) are proposed. Among them, QLEF requires the lowest speedup bound. In this paper, we show that the existing speedup bound for QLEF is not tight enough. A new bound which is 10% lower than the existing one is derived.

Light-trail has emerged as a promising candidate for enabling IP over WDM networks. The problem of static light- trail assignment is to find a set of light-trails to cover the given traffic demands, such that the total number of light-trails required is minimized. Because of the power loss caused by splitting at each hop, the length of a light-trail is limited. Existing light-trail assignment algorithms adopt ILP (Integer Linear Programming) approach. Due to the high complexity of ILP, such algorithms are not scalable. In this paper, we propose an efficient heuristic algorithm LTA (Light-Trail Assignment) to solve this problem. In LTA, each light-trail is judiciously assigned based on the request discreteness, the shortest path length and the traffic volume of each request. A reference node mechanism is also designed to enhance the solution. Numerical results show that LTA always returns sub-optimal solutions.

To achieve fast link failure detection in all-optical networks, the notion of monitoring-cycle (m-cycle) is introduced. The best known m-cycle construction algorithm (HST [7]) adopts a spanning tree-based approach. In this paper, we propose a new algorithm M2-CYCLE to construct a set of minimum-length m- cycles (or m2-cycles) for more efficient link failure detection. We prove that the performance of M2-CYCLE is never worse than any spanning tree-based approach. Comparing M2-CYCLE to the existing algorithms, we show that it uses the least amount of network resources (measured by the number of cycles, cover length and monitoring wavelength requirement) to achieve the most accurate link failure detection (measured by localization degree).

Aiming at providing 100% throughput with bounded packet delay, we consider traffic scheduling in high-speed routers with optical switch fabrics. Because of the switch reconfiguration overhead, a speedup in the switch fabric is essential. For a given packet delay bound, our objective is to minimize the overall speedup S = Sreconfiguretimes Sscheduleso as to lower the implementation cost. Leveraging on the existing ADAPTIVE and DOUBLE algorithms, we show the speedup can be reduced by improving scheduling efficiency. Specifically, following the traffic matrix decomposition in ADAPTIVE and DOUBLE, we shift some packets from the residue matrix R to the quotient matrix Q, while keeping the number of configurations required to cover each matrix the same. We reduce the number of time slots required to send the diminished residue matrix. In case of DOUBLE, this translates into a 12.5% cut in Sschedule(from 2 to 1.75). We call the resulting algorithm Scheduling Residue First (SRF).

To deploy a multi-cell 802.11 wireless local area network (WLAN), access point (AP) placement and channel assignment are two primary design issues. For a given pattern of traffic demands, we aim at maximizing not only the overall system throughput, but also the fairness in resource sharing among mobile terminals. A novel method for estimating the system throughput of multi-cell WLAN is proposed. An important feature of this method is that co-channel overlapping is allowed. Unlike conventional approaches that decouple AP placement and channel assignment into two phases, we propose to jointly solve the two problems for better performance. The optimal solution can be found using exhaustive searching. Due to the high computational complexity involved in exhaustive searching, an efficient local searching algorithm, called patching algorithm, is designed. Numerical results show that for a typical indoor environment, patching algorithm can provide a close-to-optimal performance with much lower time complexity than exhaustive searching

Overlay multicast tree construction and maintenance is a major challenge in designing application layer multicast protocols. In this paper, we focus on improving the joining and maintenance procedures of an overlay multicast tree. Unlike the existing direct-tree protocols, our proposed overlay multicast tree protocol (OMTP) has the following characteristics. First, by leveraging on the IP hierarchical addressing locality, we can speed up the formation of overlay multicast tree and enhance the efficiency of the tree maintenance. Second, we take both bandwidth availability and round-trip-time (RTT) into consideration when a newcomer selects its parent node. Finally, an effective mechanism is designed to disperse the simultaneous rejoin crowds in the tree repair phase. Simulation results show that with our proposed protocol, the join latency can be reduced by as large as 50% as compared with a popular direct-tree protocol HMTP.

A virtual private network (VPN) is a private data network where remote sites are connected over a shared provider network. In order to provide secure communications between customer sites, predetermined paths are used to forward data packets. To support quality of service (QoS), bandwidth has to be reserved on these paths. Then, finding appropriate paths in order to optimize the bandwidth used becomes an important problem. In this paper, we study the routing problem of VPNs under the hose model, where VPN endpoints specify the maximum bandwidth they need in sending and receiving data. Some previous works considered the problem under the assumption that all links have infinite capacities. We remove this constraint in our studies and develop enhancement to existing algorithms. Our simulation results show that our algorithm works very well in networks where link capacities are tight.

We study bulk data distribution schemes for content distribution networks (CDNs) using application-level overlay. Given the outbound bandwidth of all the CDN edge servers, a fluid-flow based analytical model is constructed to derive the optimal bandwidth allocations at the origin server and among all the edge servers. From which, a lower bound on the content update time is obtained. In order to have an efficient and practical scheme for bulk data distribution, ServerCast is designed to take advantages of the analytical results. Simulations are conducted to evaluate the performance of ServerCast. We show that ServerCast not only outperforms the two existing schemes, fastreplica and multiple unicast, but also yields a content update time within 18% of the derived lower bound.

Bi-directional WDM transmission is a technique that allows wavelengths to be transmitted simultaneously in both directions in a single fiber. Compared with unidirectional WDM systems, it not only saves the cost of deploying extra fibers, but also allows more flexible bandwidth provisioning. To exploit the advantages brought by this flexibility, we investigate path protection based on bi-directional WDM transmission system in this paper. With path protection, a call is accepted if and only if an active data path together with a disjointed backup path can be found in the network. With bi-directional WDM, backup resources sharing in both directions of a fiber is possible. To encourage resources sharing, new cost functions are judiciously designed. Based on them, two original path protection schemes are proposed in this paper, BiPro and BiProLP, where BiProLP aims at further economizing the hardware cost incurred by BiPro. In contrast to the traditional unidirectional schemes, we show that both BiPro and BiProLP can yield noticeably lower call blocking probability, higher system capacity and shorter active/backup path length

For performance guaranteed OPS switches with reconfiguration overhead, it has been shown that packet delay can be minimized by using N switch configurations (where N is the switch size) to schedule the traffic. However, this usually involves an exorbitant speedup requirement, which makes it impractical under current technology. In this paper, a new minimum-delay scheduling algorithm QLEF (quasi largest-entry-first) is proposed. We prove that QLEF pushes the required speedup bound to the lowest known level. As an example, when N=950, QLEF only requires a speedup of Sschedule=21.33 instead of 42.25 for MIN (B. Towles and W.J. Dally, 2003) and 30.27 for ai-SCALE (B. Wu and K.L. Yeung, 2005). This gives a 50% improvement over MIN and 30% over ai-SCALE

An optical packet switch (OPS) is called performance guaranteed if it can achieve 100% throughput with bounded packet delay. Presently, high speedup requirement and large packet delay are two main disadvantages in designing performance guaranteed OPS. Survivability is another important issue that must be considered for real OPS implementations. In this paper, we propose a two-layer parallel OPS architecture together with an efficient scheduling scheme to address all the above issues. The tradeoff between speedup and packet delay under this new parallel architecture is also formulated to provide more design flexibility. Compared to the single-layer OPS, our proposed solution can simultaneously reduce both speedup and packet delay. For example, a delay of 4/spl delta/N slots can be achieved with a speedup of 2 in our solution (where N is the switch size and /spl delta/ is the switch reconfiguration overhead), whereas the single-layer OPS needs a speedup of 6 for a delay of 7/spl delta/N slots. We show that this significant improvement benefits from a careful overall design rather than simply adding an extra switching layer.

Despite the rich literature on modeling TCP, we find two common deficiencies with the existing approaches. First, none of the work gives sufficient treatment to slow-start, although almost all of them show that retransmission timeout events are common. Second, the probability that retransmission timeout occurs has been underestimated, because retransmission timeout is coupled with fast recovery but fast recovery has not been properly modeled in the previous work. In this paper, new analytical models for predicting the steady state throughput of TCP flows are proposed. All major TCP mechanisms, including slow-start, congestion avoidance, fast retransmit, and fast recovery, are jointly considered under both bursty and independent loss models. We show that our proposed throughput models capture TCP performance more accurately.

This paper focuses on designing autonomous device discovery algorithms for Bluetooth networks. We first extend the conventional asymmetric Bluetooth link model to three point-to-point symmetric link models. Their performances are compared analytically. To achieve proximity awareness among a group of Bluetooth devices, three control information exchanging methods are also proposed. Combining with the three link models, this gives 9 possible variants of autonomous device discovery algorithm. A comprehensive comparative study based on these 9 variants is then carried out using Bluehoc simulator.

In order to achieve the minimum traffic delay in a performance guaranteed optical packet switch (OPS) with reconfiguration overhead, the switch fabric has to use the minimum number of configurations (i.e. N configurations where N is the switch size) for traffic scheduling. This requires a very high speedup in the switch fabric to compensate for the loss in scheduling efficiency. The high speedup requirement makes the idea of using N configurations (to schedule the traffic) impractical under current technology. In this paper, we propose a new scheduling algorithm called /spl alpha//sup i/-SCALE to lower the speedup required. Compared with the existing MIN algorithm B. Towles, et al., 2003, /spl alpha//sup i/-SCALE succeeds in pushing the speedup bound (i.e. worst-case speedup requirement) to a much lower level. For example, when N=200, the speedup bound required to compensate the loss in scheduling efficiency is 30.75 for MIN, whereas 23.45 is sufficient for our /spl alpha//sup i/-SCALE.

To deploy a multi-cell IEEE 802.11 wireless local area network (WLAN), access point (AP) placement and channel assignment are two primary design issues. For a given pattern of traffic demands, we aim at maximizing not only the overall system throughput, but also the fairness in resource sharing among mobile terminals. A novel method for estimating the system throughput of a multi-cell WLAN is proposed. An important feature of this method is that cochannel overlapping is allowed. Unlike conventional approaches that decouple AP placement and channel assignment into two phases, we propose to solve the two problems jointly for better performance. Due to the high computational complexity involved in exhaustive searching, an efficient local searching algorithm, called patching algorithm, is also designed. Numerical results show that for a typical indoor environment, the patching algorithm can provide a close-to-optimal performance with much lower time complexity.

Providing QoS guarantees for Internet services is very important. It evokes the issue that packet switches should provide guaranteed performance (i.e. 100% throughput with bounded worst-case delay). Optical switching technology is widely considered as an excellent solution for packet switches in future networks. However, to achieve guaranteed performance in optical packet switches, an internal speedup is required due to the existence of reconfiguration overhead. How to reduce the internal speedup is the main concern for making these switches practical. In this paper, we first derive the internal speedup S as a function of the number of switch configurations N/sub S/ and the reconfiguration overhead /spl delta/, or S=f(N/sub S/,/spl delta/). We show that the recently proposed ADJUST algorithm is flawed. Based on the internal speedup function we derived, a new algorithm (ADAPTIVE), with time complexity of O((/spl lambda/-1)N/sup 2/logN), is proposed to minimize S.

Explicit control protocol (XCP) is a promising transport layer protocol for satellite IP networks. Nevertheless, two problems of XCP can be identified: low throughput under high link error rate conditions; output link underutilization in the presence of rate-limited connections. To address the first problem, we propose to maintain the transmission rate of an XCP sender when triple duplicate ACK is detected. To solve the second problem, we propose to adjust the aggregated feedback based on the ratio of the number of rate-limited connections to the total number of connections sharing the link. We then combine our proposed solutions to form a new protocol, called P-XCP. Simulation results show that P-XCP overcomes the two problems of XCP. When packet error rate is over 0.1, P-XCP is shown to enjoy a throughput almost double that of XCP.

Based on the concept of most popular prefix first, two efficient algorithms for BGP route configuration are proposed. The first algorithm MPPF/spl I.bar/SES is designed for solving the single egress selection (SES) problem, and the second algorithm MPPF/spl I.bar/MES is for multiple egress selection (MES). MPPF/spl I.bar/MES has two variants, one aims at minimizing the total amount of resources consumed for carrying the transit traffic, and the other tries to minimize the egress link capacity required. Compared with the existing algorithms, a comparable performance in terms of network resources consumed can be obtained. In case of SES, our MPPF/spl I.bar/SES can earn a given traffic load with much lower egress link capacity requirement. In case of MES, our MPPF/spl I.bar/MES tends to provide a more stable performance. Last but not the least, our proposed algorithms have a much lower time complexity than the existing approach.

To effectively manage the traffic distribution inside a network, traffic splitting is needed for load sharing over a set of equal-cost-multi-paths (ECMPs). In this paper, a new traffic splitting algorithm, called Table-based Hashing with Reassignments (THR), is proposed. Based on the load sharing statistics collected, THR selectively reassigns some active flows from the over-utilized paths to under-utilized paths. The reassignment process takes place in such a way that the packet out-of-order problem is minimized. As compared with the existing traffic splitting algorithms, THR provides close-to-optimal load balancing performance, less than 2% of packets arrived out-of- order, and a very small end-to-end packet delay performance. Although additional traffic monitoring function is needed by THR, we show that the extra complexity incurred is marginal.

Aiming at minimizing the combined bandwidth cost of a pair of disjoint active and backup paths, a popular approach to designing restorable dynamic QoS routing schemes is based on integer linear programming (ILP) formulation. Owing to the very different natures of active and backup paths, we found this approach problematic. In this paper, we propose a simple alternative approach, called two-step routing. In the first step, active path is found using the widest-shortest path (WSP) routing. In the second step, the corresponding backup path is determined using one of the three variants of shortest-widest path (SWP) routing, basic-SWP, approximate-SWP and composite-SWP. Combining both steps, three novel restorable routing algorithms, SBW, SAW and SCW, are obtained. Comparing with the existing best-known algorithms, we show that our two-step routing approach yields noticeably lower call blocking probability, shorter active path length, and adjustable backup path length (depending on the SWP variant adopted). Besides, our two-step routing approach gives a much shorter running time than the ILP approach, which makes it more attractive for dynamic routing.

In this paper, a new layered multicast protocol, called fast-response receiver-driven layered multicast (FRLM), is proposed. The differences between our FRLM and the original RLM are only at the receivers. Our design allows the receivers to track the available network bandwidth faster; this enables the receivers to converge to their optimal number of subscribed layers quicker, and to respond to the network congestion prompter. An early trigger mechanism for shortening IGMP leave latency is also designed. We show that FRLM can avoid several potential problems with the original RLM, which have been overlooked previously. Last but not the least, FRLM is a practical scheme that can be readily implemented in today's best-effort Internet.

Focusing on a general wireless network where a wireless link can be at any link along the sender-to-receiver path, a new TCP enhancement scheme, called Generalized-Snoop (G-Snoop), is proposed. Since many existing applications are built on top of TCP, it is essential that any TCP enhancement scheme should be transparent to the end-systems as well as the fixed networks. To achieve this, G-Snoop only needs to be implemented at the wireless gateways, no other parts of the network require modifications. With G-Snoop, TCP senders are shielded from noncongestion packet loss and thus no unnecessary congestion control mechanisms will be performed. Simulation results show that significant throughout gain can be obtained with G-Snoop.

A new transport layer protocol called TCP-Swift is proposed for enhancing the TCP performance over satellite IP networks. TCP-Swift replaces the conventional TCP slow start and fast recovery algorithms by speedy start and speedy recovery. With speedy start, a TCP-Swift sender opens up its congestion window in only two round trip times. This significantly shortens the time needed in probing the network for equilibrium state. With speedy recovery, we can infer the cause of a packet loss by observing the ACK stream received at the sender. If the loss is due to wireless transmission error, the sender's congestion window can be reopened up more aggressively to fully utilize the available satellite link bandwidth. We show that TCP-Swift outperforms existing TCP schemes by simulations.

Data exchange within a Bluetooth piconet is master-driven. The channel/slot utilization thus depends on the efficiency of the scheduling algorithm adopted by the master. In this paper, a novel MAC layer scheduling algorithm, called floating threshold (FT), is proposed. Unlike existing approaches, FT allows the master to estimate the backlog queue status at each slave accurately based only on a single feedback bit and a floating threshold. The master can then derive an optimized packet transmission schedule. Using simulations, we show that FT outperforms existing algorithms in terms of channel utilization, packet delay and packet dropping probability.

TCP is a reliable transport protocol tuned to perform well in traditional networks made up of links with low bit-error rates. Networks with higher bit-error rates, such as those with wireless links and mobile hosts, violate many of the assumptions made by the transmission control protocol (TCP), causing degraded end-to-end performance. We propose a two-layer hierarchical cache architecture for enhancing TCP performance over heterogeneous networks with both wired and wireless links. A new network-layer protocol, called new snoop (NS), is designed. The main idea is to cache the unacknowledged packets at both the mobile switch center (MSC) and base station (BS), to form a two-layer cache hierarchy. If a packet is lost due to transmission errors in the wireless link, the BS takes the responsibility to recover the loss. When a handoff occurs, the packets cached at the MSC can help to minimize the latency of retransmissions due to temporal disconnection. NS can preserve the end-to-end TCP semantics and is compatible with existing TCP applications. Its implementation only requires code modification at the BS and MSC. Simulation results show that NS is significantly more robust in dealing with unreliable wireless links and handoffs as compared with the original snoop scheme, as well as some other existing TCP enhancements.

A novel router flow control scheme, called IRED, is proposed for supporting both guaranteed bandwidth (GB) and best-effort (BE) flows in the Internet. In IRED, network resources are reserved for each GB flow using resource reservation protocol (RSVP). At each router, packet scheduling behavior is established to meet the QoS requirements of each GB flow. For supporting BE flows, a router senses incipient congestion by monitoring the average buffer occupancy of BE packets with respect to the total buffer space available for BE traffic. When a pre-defined occupancy threshold is exceeded, IRED randomly drops BE packets to notify the selected senders to slow down their transmission rates. Our extensive simulation results reveal that IRED can provide QoS guarantee on delay and packet dropping probability for GB flows, and can achieve excellent throughput performance for BE flows. We also find that IRED can protect BE flows from the harassment of unfriendly greedy GB flows as well as non-adaptive BE flows.

A new class of quality of service (QoS) measures, EB(p), p/spl ges/1 for WDM optical transport networks is proposed in this paper. Compared with the traditional overall average blocking probability (OABP), EB(p) is a composite measure that is unbiased, makes reference to the QOS requirements, one-sided, and takes the potential revenue loss into consideration. In particular, EB(1) can be identified as (revenue) weighted average excessive blocking, and EB(2) as mean square (revenue) weighted excessive blocking. The effectiveness of this new composite measure is compared with OABP based on several existing routing and wavelength assignment algorithms.

A multigigabit IP router may receive several million packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet's next-hop. In this paper, we present an efficient hardware solution for the IP address lookup problem. We model the address lookup problem as a searching problem on a binary-trie. The binary-trie is partitioned into four levels of fixed size 255-node subtrees. We employ a hierarchical indexing structure to facilitate direct access to subtrees in a given level. It is estimated that a forwarding table with 40 K prefixes will consume 2.5 Mbytes of memory. The searching is implemented using a hardware pipeline with a minimum cycle of 12.5 ns if the memory modules are implemented using SRAM. A distinguishing feature of our design is that forwarding table entries are not replicated in the data structure. Hence, table updates can be done in constant time with only a few memory accesses.

A set of packet scheduling algorithms are proposed for improving the performance of an iterative longest port first (iLPF) algorithm for virtual output queueing (VOQ) switches. In our proposed algorithms, scheduling priority is given according to different criteria that include input port occupancy, output port occupancy and critical port in VOQ. One of the proposed algorithms, called longest input port first with throughput maximization (LIPF with TM), gives significant performance improvement in mean packet delay and throughput when compared with iLPF. We found that for a 16/spl times/16 switch with input load p=0.85, the mean packet delay is 7.08 slots for iLPF and 3.21 slots for LIPF with TM. This represents a 55% cut in mean packet delay.

A novel proactive base station flow control algorithm, called forced duplicate acknowledgement (FDA), is proposed for extending TCP over wireless networks. FDA is implemented at the base station (BS) of a wireless network. It works in conjunction with existing TCP enhancement schemes such as Snoop or New Snoop. In FDA, if the average occupied buffer size at a BS exceeds a pre-defined threshold, an incipient congestion is detected. Then three forced duplicate ACKs, functioning as a congestion notification, will be generated by the BS and forwarded to a set of selected TCP senders. Upon receiving the forced duplicate ACKs, a sender reduces its transfer rate as a result of performing the fast retransmit procedure. To prevent multiple packet dropping due to buffer overflow at the BS, a quality guaranteed cache release policy is designed. The idea is to make room for the on-the-fly packets by releasing some cached but not-yet-acknowledged packets at the BS in advance. The performance of the proposed FDA is evaluated by simulations. We found that under various traffic and system configurations, FDA can not only fairly allocate the available wireless bandwidth among all TCP connections, but also achieves the highest throughput as compared to other schemes we have investigated.

Two efficient time slot assignment algorithms, called the two-phase algorithm for the nonhierarchical and the three-phase algorithm for the hierarchical time-division multiplex (TDM) switching systems, are proposed. The simple idea behind these two algorithms is to schedule the traffic on the critical lines/trunks of a traffic matrix first. The time complexities of these two algorithms are found to be O(LN/sup 2/) and O(LM/sup 2/), where L is the frame length, N is the switch size, and M is the number of input/output users connected to a hierarchical TDM switch. Unlike conventional algorithms, they are fast, iterative and simple for hardware implementation. Since no backtracking is used, pipelined packet transmission and packet scheduling can be performed for reducing the scheduling complexity of a transmission matrix to O(N/sup 2/) and O(M/sup 2/), respectively. Extensive simulations reveal that the two proposed algorithms give close-to-optimal performance under various traffic conditions.

In this paper, we propose a two-layer hierarchical cache architecture for enhancing TCP performance over heterogeneous networks with both wired and wireless links. A new network-layer protocol, called New Snoop, is designed. The main idea is to cache the unacknowledged packets at both the mobile switch center (MSG) and base station (BS), thus forming a two-layer cache hierarchy. If a packet is lost due to transmission errors in the wireless link, the BS takes the responsibility to recover the loss. When a handoff occurs during a TCP connection session, the packets cached in MSC can help to minimize the latency of retransmissions due to temporal disconnection. Simulation results show that using New Snoop is significantly more robust in dealing with unreliable wireless inks and handoffs as compared with the Snoop scheme (Balakrishnan et al. 1995) as well as other existing TCP enhancements.

Active reliable multicast (ARM) is a newly proposed loss recovery scheme for reliable multicast over the Internet. For a given amount of total cache available at each active router, the performance of ARM depends on how the amount of cache is partitioned to each multicast session. We call it the cache-partitioning problem. Following the approach of minimizing the total loss recovery traffic in the backbone network, an optimal cache-partitioning scheme is proposed and an analytical model is constructed. The performance of using the proposed optimal cache partitioning is compared with that using uniform cache partitioning and proportional partitioning. A significant performance improvement is found.

Local loss recovery for reliable multicast can provide significant performance improvement in terms of loss recovery latency, bandwidth consumption and network throughput. An analytical model for studying the optimal cache allocation for active reliable multicast (ARM) is constructed using standard optimization techniques, the optimal cache allocation pattern can be found. Our numerical results show that using optimal cache allocation yields significantly smaller loss recovery latency than using uniform cache allocation. To further enhance the loss recovery performance when the amount of cache at an active router is limited, we propose a probabilistic caching policy. We derive the optimal caching probabilities for each active router in a given multicast tree with a given cache allocation pattern. We show that with the use of probabilistic caching policy, a further reduction in loss recovery latency can be obtained.

A new push-and-pull hybrid data broadcast scheme is proposed for providing wireless information services to three types of clients, general, pull and priority clients. Only pull and priority clients have the back channel for sending requests to the broadcast server. There is no scalability problem with the hybrid scheme because the amount of pull and priority clients is very small. Based on the requests collected from pull and priority clients, the server estimates the interest pattern changes of the whole client population. Then the broadcast schedule on the push channel for the next broadcast cycle is adjusted. Besides the push channel, a small amount of broadcast bandwidth is allocated to a pull channel. The data to be broadcast on the pull channel is decided by the server in real-time and priority is given to requests from priority clients. Simulations show that with a time-varying client interest pattern, the average data access time for all three types of clients can be minimized. Because of the priority in using the pull channel, priority clients can achieve the lowest access time and pull clients can achieve a lower access time than general clients. To further improve the performance, the hybrid scheme with local client cache is also investigated.

A novel LEO/MEO two-tier satellite communication system with inter-satellite links (ISLs) is proposed for providing multimedia services to global mobile users. This two-tier system architecture can reduce the transmission delay for long-distance users via MEO satellites while keeping the benefits of using LEO satellites as the service access nodes. The routing and re-routing during a handoff operation is simplified. Since the physical topology of the underlying network is time-dependent, routing is crucial for guaranteeing the delay and delay variation performance for interactive applications. We decompose the routing problem into two parts, routing in the access network and routing in the core MEO ISL network. For the access network, a new routing algorithm called the maximum holding access protocol (MHAP) is proposed for minimizing the number of LEO handoffs. For core MEO ISL network, both minimum transmission delay routing (MTDR) and minimum transmission time jitter routing (MTTJR) are investigated. Using computer simulations, we show that the proposed routing algorithms can reduce the probability of call re-routing and thus are very suitable for providing interactive multimedia services.

An efficient self-adaptive packet queueing policy, called Queueing with Output Address Grouping (QOAG), is proposed for optimizing the performance of an input buffered packet switch. Each input port of the N/spl times/N switch under consideration has Q queues and each queue has B packet buffers, where 1<Q

An efficient coset based symbol-by-symbol soft in/soft-out a posteriori probability (APP) decoding algorithm is presented for the Golay code. Its application in the iterative decoding of concatenated Golay codes is examined.

This paper is concerned with the decoding technique and performance of multi-dimensional concatenated single-parity-check (SPC) code. A very efficient sub-optimal soft-in-soft-out decoding rule is presented for the SPC code, costing only 3 addition-equivalent-operations per information bit. Multi-dimensional concatenated coding and decoding principles are investigated. Simulation results of rate 5/6 and 4/5 3-dimensional concatenated SPC codes are provided. Performance of BER=10/sup -4/-10/sup -5/ can be achieved by the MAP and max-log-MAP decoders, respectively, with E/sub b//N/sub 0/ only 1 and 1.5 dB away from the theoretical limits.

Node placement problem in ShuffleNets is a combinatorial optimization problem. In this paper an efficient node placement algorithm, called the gradient algorithm, is proposed. A communication cost function between a node pair is defined and the gradient algorithm places the node pairs one by one, based on the gradient of the cost function. Then two lower bounds on the traffic weighted mean internodal distance h are proposed. The performance of the gradient algorithm is compared to the lower bounds as well as to some algorithms in the literature. Significant reduction of h is obtained with the use of the gradient algorithm, especially for highly skewed traffic distributions. For a ShuffleNet with N=64 nodes, the h found is only 22% above the lower bound for the uniform random traffic distribution, and 14.7% for a highly skewed traffic distribution with skew factor /spl gamma/=100.

This paper presents a symbol-by-symbol decoding method for the F/sub 24/ code. It forms the core part of an iterative Max-Log-MAP filtering algorithm for the product F/sub 24/ code and noticeable coding gain is observed by simulation The complexity of the proposed algorithm is very modest. The relatively short frame length of the product F/sub 24/ code can be an advantage for its applications in some communication systems.

This paper focuses on designing efficient multicast time slot assignment (MTSA) algorithms for TDM switching systems, Based on a packet compatibility matrix, the MTSA can be transformed to the well-known graph-coloring problem. We show that the MTSA problem is NP-complete. A lower bound on the frame length of a multicast time slot assignment is then found to be the clique number of the MTSA equivalent graph. Two efficient MTSA algorithms, called the contention-based ordering (CBO) algorithm and the hybrid ordering algorithm, are proposed. Their performance is compared with the three existing algorithms and the lower bound through extensive simulations. We found that the CBO algorithm, which has one of the lowest computational complexities, gives the best performance among all five algorithms studied. The average frame length generated by the CBO algorithm is within 1% above the lower bound. We also show that (i) the previously reported DAC algorithm has the poorest performance despite its highest complexity, and (ii) the previously reported CCBO algorithm has only a comparable performance to the simple greedy algorithm.

Since call termination as a result of handoff failure is considerably less desirable from the user's viewpoint than the blocking of a new call, a prioritized handoff scheme is essential. Especially for microcellular systems where the mobile cell boundary crossing rate is high. Therefore an efficient DCA should give priority to handoff calls. Two DCA strategies for prioritized handoff are proposed based on a DCA called BDCL (borrowing with directional channel locking): (i) FCA with BDCL for handoff calls, and (ii) BDCL with channel reservation. FCA with BDCL for handoff calls allows a handoff call to borrow a channel using BDCL strategy if no free nominal channel in the call arrival cell is available. In BDCL with channel reservation, both the new call and handoff call can use a borrowed channel. But a fixed number of nominal channels in a cell are reserved for exclusive use of handoff calls. To study the performance of the two proposed strategies, a widely accepted mobility model is adopted. Based on this model, we derive the handoff call arrival rates and channel holding time from the given mean mobile speed. The performance of the two proposed algorithms is studied by simulations and we found that they are very effective in reducing the handoff call blocking probability while not affecting the new call performance.

In a two-tier microcell/macrocell cellular system, to keep the handoff rate at an acceptable level, low mobility users (with speed /spl upsi/V/sub 0/) should undergo handoffs at macrocell boundaries. We propose a procedure by which the mobile determines user mobility from microcell sojourn times and uses it for micro-macro cell selection at call origination and handoff. The probability of erroneous assignment of a mobile to a microcell or macrocell is shown to be significantly lower than previous approaches.

We develop a simple but very accurate analytical model for a channel borrowing based dynamic channel assignment strategy in linear microcellular systems. Our approach is to decouple a particular cell together with its neighbors, i.e., those cells under its interference range, from the rest of the system for finding the blocking probability of that cell. We call this the cell group decoupling analysis. This analysis is applicable to both homogeneous and heterogeneous traffic distributions. We show that the effect of this decoupling causes the blocking probability so obtained to be an upper bound. The bound is found to be very tight when compared with simulation results. Besides, this analysis gives accurate results to boundary cells as well as inner cells, and is therefore quite different from the other approaches which neglect boundary effects.>

In this paper, we propose the phantom cell analysis for dynamic channel assignment. This is an approximate analysis that can handle realistic planar systems with three-cell channel reuse pattern. To find the blocking probability of a particular cell, two phantom cells are used to represent its six neighboring cells. Then by conditioning on the relative positions of the two phantom cells, the blocking probability of that particular cell can be found. We found that the phantom cell analysis is not only very accurate in predicting the blocking performance but also very computationally efficient. Besides, it is applicable to any traffic patterns and any cellular layouts.>