Browsing by Author "Wong, Wing Shing"

Now showing 1 - 5 of 5

Delay-Constrained Input-Queued Switch
(2018-11-01)
Deng, Lei
;
Wong, Wing Shing
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Hou, Hanxu
In this paper, we study the delay-constrained input-queued switch, where each packet has a deadline and it will expire if it is not delivered before its deadline. Such new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. The delay-constrained input-queued switch is completely different from the well-understood delay-unconstrained one and thus poses new challenges. We focus on three fundamental problems centering around the performance metric of timely throughput: (i) how to characterize the capacity region? (ii) how to design a feasibility/throughput-optimal scheduling policy? and (iii) how to design a network-utility-maximization scheduling policy? We use three different approaches to solve these three fundamental problems. The first approach is based on Markov Decision Process (MDP) theory, which can solve all three problems. However, it suffers from the curse of dimensionality. The second approach breaks the curse of dimensionality by exploiting the combinatorial features of the problem. It gives a new capacity region characterization with only a polynomial number of linear constraints. The third approach is based on the framework of Lyapunov optimization, where we design a polynomial-time maximum-weight T-disjoint-matching scheduling policy which is proved to he feasibility/throughput-optimal. Our three approaches apply to the frame-synchronized traffic pattern but our MDP-based approach can be extended to more general traffic patterns.
Partially user-irrepressible sequence sets and conflict-avoiding codes
(2016-03)
Lo, Yuan-Hsun
;
Wong, Wing Shing
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
In this paper we give a partial shift version of user-irrepressible sequence sets and conflict-avoiding codes. By means of disjoint difference sets, we obtain an infinite number of such user-irrepressible sequence sets whose lengths are shorter than known results in general. Subsequently, the newly defined partially conflict-avoiding codes are discussed.
Poster: Delay-Constrained Input-Queued Switch
(2018-01-01)
Deng, Lei
;
Wong, Wing Shing
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
交大名義發表
We study delay-constrained input-queued switches where each packet has a deadline that will expire if it is not delivered before its deadline. Such a new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. One fundamental problem centering around the performance metric of timely throughput is how to characterize the capacity region. In this work, for the frame-synchronized traffic pattern, we characterize the capacity region by a polynomial number of linear constraints.
The Global Packing Number of a Fat-Tree Network
(2017-08-01)
Lo, Yuan-Hsun
;
Zhang, Yijin
;
Chen, Yi
;
Fu, Hung-Lin
;
Wong, Wing Shing
Data centers play an important role in today's Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N subset of V(G) be a set of nodes. A path system P of G with respect to N consists of |N|(|N|-1) directed paths, one path to connect each of the source-destination node pairs in N. The global packing number of a path system P, denoted by Phi(G, N, P), is the minimum integer k to guarantee the existence of a mapping phi : P -> {1, 2, . . . , k}, such that phi(P) not equal phi((P) over cap) if P and (P) over cap have common arc(s). The global packing number of (G, N), denoted by Phi (G, N), is defined to be the minimum Phi (G, N, P) among all possible path systems P. In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (T-n, N), where T-n denotes the topology of the n-ary fat-tree network, and N is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links.
The undirected optical indices of complete m-ary trees
(2020-10-15)
Lo, Yuan-Hsun
;
Fu, Hung-Lin
;
Zhang, Yijin
;
Wong, Wing Shing
;
應用數學系
The routing and wavelength assignment problem arises from the investigation of optimal wavelength allocation in an optical network that employs Wavelength Division Multiplexing (WDM). Consider an optical network that is represented by a connected, simple graph G. An all-to-all routing R in G is a set of paths connecting all pairs of vertices of G. The undirected optical index of G is the minimum integer k to guarantee the existence of a mapping phi : R -> {1, 2, ..., k}, such that phi(P) not equal phi(P') if P and P' have common edge(s), over all possible routings R. A natural lower bound of the undirected optical index of G is the (undirected) edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible all-to-all routings. In this paper, we first derive the exact value of the optical index of the complete m-ary trees, and then investigate the gap between undirected optical and edge-forwarding indices. (C) 2020 Elsevier B.V. All rights reserved.