Research of Queueing Theory

這篇主要是想寫「誰在研究排隊理論？」，我有詢問過ycwang老師，他是說有幾個地方，記得沒錯的話，會在下面列出來。為什麼要知道呢？其實做任何事都會有個憧憬，總是想去某個地方看看，而這個地方具有其重要性、指標性的意義。

比方說想到浪漫，就會想去歐洲看看；想到設計，就會想到北歐看看；想到美國，就想去紐約看看...等等。有點類似朝聖的味道，排隊理論也是如此，總想去那個研究特別發達的學校或是單位看看，看他們在做些什麼。

全世界研究Queueing Theory可以分為兩類，一個是理論(Theory) ，另一個是應用(Application)，美國偏向應用，歐洲偏向理論，大致上是這樣。台灣呢？是偏向"代工"嗎...。

有個國外網站專門蒐集排隊理論的資訊，請參考http://web2.uwindsor.ca/math/hlynka/queue.html

以下為有研究Queueing Theory的知名單位：(陸續補充)

台灣(Taiwan)
National Tsing Hua University
國立清華大學http://www.nthu.edu.tw/


美國(United States of America, USA)
University of Illinois at Urbana-Champaign
伊利諾大學香檳分校，http://illinois.edu/

法國(France)
the French national institute for research in computer science and control
法國國家電腦科學與控制研究院，簡稱INRIA
http://www.inria.fr/index.en.html

荷蘭(Netherlands)


德國(Germany)

SimEvents Library

先將SimEvents中的Library整理成清單，之後會用到，依照字母排列，也剛好是Simulink的排列方式：

• Attributes
  
  • Get Attribute
  • Set Attribute
    
• Entity Management
  
  • Entity Combiner
    
  • Entity Splitter
    
• Event Translation
  
  • Entity Departure Event to Function-Call Event
    
  • Signal-Based Event to Function-Call Event
    
• Gates
  
  • Enabled Gate
    
  • Release Gate
    
• Generators
  
  • Entity Generators
    
    • Event-Based Entity Generator
      
    • Time-Based Entity Generator
      
  • Event Generators
    
    • Entity-Based Function-Call Event Generator
      
    • Signal-Based Function-Call Event Generator
      
  • Signal Generators
    
    • Event-Based Random Number
      
    • Event-Based Sequence
      
• Probes
  
  • Entity Departure Counter
    
• Queues
  
  • FIFO Queue
    
  • LIFO Queue
    
  • Priority Queue
    
• Routing
  
  • Input Switch
    
  • Output Switch
    
  • Path Combiner
    
  • Replicate
    
• Servers
  
  • Infinite Server
    
  • N-Server
    
  • Single Server
    
• Signal Management
  
  • Initial Value
    
  • Singal Latch
    
• SimEvents Ports and Subsystems
  
  • Conn
    
  • Din
    
  • Discrete Event Subsystem
    
  • Dout
    
  • Subsystem Configuration
    
• SimEvents Sinks
  
  • Attribute Scope
    
  • Discrete Event Signal to Workspace
    
  • Entity Sink
    
  • Instantaneous Entity Counting Scope
    
  • Instantaneous Event Counting Scope
  • Signal Scope
    
  • X-Y Attribute Scope
    
  • X-Y Signal Scope
    
• SimEvents User-Defined Functions
  
  • Attribute Function
    
• Timing
  
  • Cancel Timeout
    
  • Read Timer
    
  • Schedule Timeout
    
  • Start Timer

中文呢？有沒有統一的中文翻譯，似乎沒有。那就自己翻譯吧！

SimEvents Lesson 1

當你開始玩SimEvents這套軟體時，有兩個是你要知道的概念，一個是Entity，另一個是Event。整套SimEvents主要是模擬Discrete-Event Simulation (DES)的情境，其中模擬的主體是Entity，而Entity之間的動作是由Event所控制。

Entity

什麼是Entity(中文，翻譯成實體、個體、本質，以下用"實體"說明)呢？DES主要是涉及離散項目(discrete items)的模擬，而此離散項目則稱之為Entity。依照模擬的環境不同，其Entity的實物也不一樣，比方說你要模擬網路行為，則Entity就是封包(packet)，如果你要模擬等公車的時間，則Entity就是乘客(passenger)。

這麼解釋好了，DES將現實環境中的情形映射(mapping)到simulation當中來處理，抽象層面的項目是Entity，具體層面的項目則是你看得到的東西。

另外你要注意的地方有，Entity在SimEvents軟體中是看不到的，沒有任何表是符號(graphical representation)來顯示Entity，那你要如何知道有沒有動作呢？要藉由其他統計(statistics)的方式來觀察。還有，Entity可以攜帶其他資料，由稱之為Attribute的項目附加在Entity當中來攜帶資料，有點像物件導向(Object-Oriented)的概念，Entity像是類別(Class)的實體(instance)，而Attribute像是欄位(field)。

Event

什麼是Event(事件)？DES中的瞬間變化(instantaneous discrete incident)則稱之為Event，白話一點的講法就是動作(action)，讓Simulation的系統產生一些變動。Event可以改變Entity、Entity中的Attribute、或是激發其他Event。我認為SimEvents中較難學的是Event這個部分，需要比較久的時間來學習才會有感覺。

Event可能會同時發生，這種事件稱之為Simultaneous Events，即使電腦上的運作是sequential的方式來執行，在多數情況下這不會有多大問題(User Guide中說的...)，這時候就要注意Event的processing sequence(要去設定Generation Event Priority)。

用物件導向(Object-Oriented)的概念來說，Event就像是方法(method)，你可以利用Event去控制實體(instance)或是欄位(field)，或是呼叫其他方法(method)。

同樣的，Event在SimEvents軟體中是看不到的，沒有任何表是符號(graphical representation)來顯示Event，要觀察有沒有動作，要從其他間接的方式來觀察。

Cause of Interview

這是西元2004年5月的訪問資料，放在www上做為記錄，期待未來可以做為歷史的佐證。內容說明當時選擇訪問老師的理由，是從我的檔案庫中翻閱出來的一段歷史資料，經過四年多，至今我還是尊崇我的老師，以及感謝他對學生們的指導。當時我是大學二年級(二下)。

下述內容從我當時「生涯發展與選擇」期末作業中節錄出來。

<內容開始>

我所選擇的受訪者是我目前的班級導師，他是我們二年級上學期的時候開始擔任我們班上的導師，在那時候他有開一門選修的課程，課程名稱叫做「電腦網路」，當時我對這方面完全不了解，想說去聽聽看，我記得第一次上課的時候，老師用投影片大概講述電腦網路內容，聽完之後覺得很有興趣，於是就繼續修這門課程。

老師不管是在敬業與專業方面，我認為都是可以值得學習的地方。在專業方面，他之前有在外面的公司上班過，因此擁有豐富的實務經驗，他曾說過他有做過大系統的經驗，從無到有的完成一個大系統。另外，理論方面他了解很透徹，他能夠用很簡單的話講述一個原理，讓我們學習更加愉快，我認為如果老師沒有很了解的話，大概也很難真正表達一個原理，可見老師真的是很厲害。

在敬業方面，老師授課都有製作投影片，並且利用投影片輔助教學，課堂上也常常利用黑板圖解說明原理，對教學做了充分的準備。此外，我比較佩服的是他不是一位要求成績的老師，而是一位要求「誠信」的老師，我們上課定期都有作業，他要求作業要自己寫，寫多少算多少，不要抄襲別人的，他認為如果現在就學會抄襲別人的，以後畢業之後到職場上也會如此，所以他不希望我們這麼做。這一點讓我很佩服與尊敬，因為現在是利益導向的社會，誠信往往是被人忽略的，導致一些問題產生。

我認為他在為人處世方面都是一位值得學習的對象，而且和老師相處的過程，他讓我感覺很愉快，可能是他對事情的態度都很樂觀吧！還有一點，我覺得他的價值觀都很「健康」，我很認同他的一些想法。

綜觀以上的一些因素，我選擇他作為這次訪談的對象，加上電腦網路也是電機領域的一部分，我可以更深入了解老師以前工作的職務內容，作為我未來選擇職業的參考依據。

<內容結束>

Introduction to Stateflow

Stateflow軟體當中，比較常用的功能應該是Stateflow Chart(中文沒有人翻譯，我稱之為"狀態流程圖")，在 Simulink中是個Block(區塊)，所謂的Stateflow Chart其實就是Finite-State Machine。

Stateflow軟體較特殊的是他有自己的編輯器(editor)和除錯器(debugger)，其目的就是：你可以和你的系統獨立地分開設計開發。

建置Stateflow Chart有下列步驟和程序：

1. Define the interface to Simulink
   定義和Simulink連結的介面
   ↓
   
2. Define the states for modeling each mode of operation
   定義模型中每個運作模式的狀態
   ↓
   
3. Define state actions an variables
   定義狀態動作和變數
   ↓
   
4. Define the transitions between states
   定義狀態之間的轉移條件
   ↓
   
5. Decide how to trigger the chart
   決定如何觸發狀態流程圖
   ↓
   
6. Simulate the chart
   進行狀態流程圖的模擬
   ↓↑
   
7. Debug the chart
   對狀態流程圖進行除錯動作
   

注意先後順序，步驟1到6都是單方向的，但是最後步驟6和步驟7是個反覆的過程，目的是讓你的model符合你的要求，因此需要先模擬，然後觀察和除錯，修改之後再模擬，反覆這樣的一個過程，最後達到你要的規格。

Simulink Event-Based Modeling

介紹一下Simulink中的Event-Based Modeling這部分的家族，包含兩個軟體：SimEvents(2.2版)和Stateflow(7.1版)，這兩個軟體有個特色，主要是用來模擬Discrete-Event Simulation (DES)的情境。

兩者目的又有點差異，SimEvents目的為模型化(model)與模擬(simulate)用途，而Stateflow目的則為設計(design)和模擬(simulate)，若能將兩者巧妙的結合，應該可能設計出完美系統！(I hope.)。

這麼說好了，對於一種系統是Event-Driven Systems(或稱Reactive Systems)來說，這系統的狀態由事件所驅動，因此會是Discrete的情形，所以我們要模擬這樣的系統，則需要像SimEvents和 Stateflow的工具，用來Event-Based的Model和simulate。

另外一種系統是Time-Based Systems，這種系統的模擬主要是simulink的強項，有更多的軟體支援這塊範疇，稱為Time-Based Simulation。

• 要打開SimEvent的Libraby請輸入：simeventslib
• 要打開Stateflow的Libraby請輸入：sflib
• 要叫出Simulink的所有Library請輸入：simulink
  

其中，Event-Driven Systems如果要模型化的方式，通常是用有限狀態機(Finite-state machines)來表示系統中的狀態，這部分算是Stateflow軟體的強項(主要功能)。另外，除了有限狀態機的方式，另一個方式是用Stateless Flow Charts來表示。

Simulink

因為研究的關係，需要用到Simulink這套工具，簡單介紹一下Simulink的精神。

Simulink可以用來達成三個目的：模型化(model)、模擬(simulate)、分析(analyze)。其對象是系統(system)，對系統建置模型、對系統進行模擬、對系統進行分析，讓我們調整系統的一些參數，看看會發生什麼事情。

Simulink可以模擬線性系統(linear)和非線性系統(nonlinear)，而且支援連續時間(continuous time)跟離散時間(sampled time)的模擬，甚至是混合型時間(hybrid，就是連續和離散時間混合)的模擬，真的是非常強大。

重點來了，做以上這些事情，我認為最終目的其實是要設計(design)，達到Model-Based Design，先分析之後再來設計，藉由模型的方式來設計出我們想要的系統，而Simulink提供graphical user interface (GUI)的方式，使得我們更容易操作，就像終端機時代進化到視窗時代的感覺！

此模型(Model)是階層式(hierarchical)架構的來建置，可以由上到下(top-down)或是由下到上(bottom-up)，所以我們可以擁有不同的視野來看待一個系統！

這時候有個問題：你要用模型化的方式來設計，首先必須得到系統的模型(通常式數學模型)，那要如何得到這個系統的模型呢？

系統模型化過程的步驟有六個：

1. 定義系統(Defining the System)
   這個系統到底要定義多少元件(component)，看看是不是要把系統切割成子系統(subsystem)。
   
2. 確認系統中的元件(Identifying System Components)
   確認每個元件的細節，包含三個細節：參數(parameter)、狀態(state)、信號(signal)。其中參數和狀態在Simulink這套軟體當中是用區塊(block)表示，而信號是用線段(line)來表示。
   
3. 用數學式來表示這個系統(Modeling the System with Equations)
   前面兩步驟只有定義"外殼"，還沒有定義元件的"內涵"。這內涵通常是用數學方程式表示，方程式的總類有：代數(algebraic)方程式、邏輯(logical)方程式、對於連續型系統的微分(differential)方程式、對於離散型系統的差分(difference)方程式
   
4. 建置simulink區塊(Building the Simulink Block Diagram)
   前三個步驟都只是紙上作業，現在開始動手建置simulink的系統，找想要使用的元件放入模型中，如果沒有可能就需要自行建立。
   
5. 實現模擬(Running the Simulation)
   建好模型之後，當然是run看看，你考能需要設定模擬的一些參數。
   
6. 證明模擬結果(Validating the Simulation Results)
   模擬結束之後，必須確認模擬結果符合實際的特性，藉由這些模擬值來研判模型的正確性。

Interview with ycwang

太久沒寫Blog了，為了預防我的Blog開始長草(我還是有在管理，只是內容中斷新增！)，先貼一篇以前訪問我老師的資料，也許在百年之後，可供歷史學家考證之用，考證Queueing Theory與ycwang、t5318019的真實性。就像史記中的故事，到底是真是假都需要"旁證"來校勘，道理是一樣的。

很久很久以前(2004年6月)，曾經和我的老師(ycwang)，有過一次訪問，當時是「生涯發展與選擇」課程，主要目的為訪問一位長者，由受訪者的經驗做為自己生涯發展的參考。以下為當時的內容大綱：

優先考慮興趣

• 老師(ycwang)是覺得有興趣的事情，它不會造成你的壓力，所以你會專心把他做完。
• 老師(ycwang)一再強調學一個東西你一定要對他有興趣，有興趣就花時間下去看，不要太功利 。
• 老師(ycwang)認為：興趣+恆心=成功

社會人觀念

• 老師(ycwang)是認為這個社會和你我是有相關的，如果這個社會不好，你再怎麼好也還是不好，因為你是和這個社會結合在一起的。
• 老師(ycwang)曾說過：成功的企業家 ，常常會有大筆的捐款 。一起提升這個社會上的所有人。

請問老師您當時進入職場時，是否具備就業應有的「專業」與「敬業」？

• 老師(ycwang)認為”專業”不是最大的瓶頸，最大的瓶頸反而是”敬業”問題，因為由敬業去達到專業是很容易的。
• 老師(ycwang)認為：如果說你很敬業的話，對工作上有不懂的地方，你就會很認真去學習，學習之後自然會達到專業。
• 老師(ycwang)認為：個人學習(求學問)也是如此，應有「專業」與「敬業」的態度。

在生涯價值觀當中，「經濟報酬」往往是社會新鮮人所追求的，您認為我們應該要以怎樣的態度看待「經濟報酬」這個價值觀？

• 老師(ycwang)認為：只是一個價值觀「錢夠用就好」，什麼叫夠用呢？當你要使用錢的時候不用去煩惱月底會沒錢。
• 老師(ycwang)認為：人的一生也就只是以快樂為主，而不是要賺很多錢的人生，所以經濟報酬只要能夠負擔你生活 。
• 老師(ycwang)認為：以興趣為基礎，因為興趣可以決定你工作快不快樂的因子，薪資或許不多，但是工作很快樂，我認為這比薪資高而沒興趣的工作要好。

從學校畢業之後，人生的大部分時間都是在從事工作，請問您對「工作」的看法為何？人生只為工作嗎？

• 老師(ycwang)曾說過：工程師是「蟑螂的生活」，打不死而且生活環境很差。
• 老師(ycwang)曾說過：「為了工作而生活」，和「為了生活而工作」是不一樣的觀點。
• 老師(ycwang)認為：應該要重視休閒

「證照不表示實力，卻是一個門檻。」您認為真是如此嗎？

• 老師(ycwang)認為：可以說對的，也可以說錯的。因為要依照你工作的性質來決定，以我們電機這個領域來說，大部分的工作都不太需要證照。
• 老師(ycwang)認為：不同的工作對於職能有不同的要求。
• 老師(ycwang)認為：英文證照是未來必須具備的，或許不需要具備，但是你必須能夠聽英文說英文才可以。

以上是當時訪問老師(ycwang)的一些重點，其實還有一份完整的報告，不過Google Docs目前還沒辦法發佈Word或是PDF，以後再放上來吧！

Long-Run Behavior of Markov Processes

我們討論Markov Process的長時間行為時，通常會有三個議題：

1. Limiting distributions
2. Stationary distributions
3. Ergodicity

首先，limiting distribution指的是P(transition probabilities)隨著時間增加會趨近於固定，即P*P*P*...P=常數。

第二，stationary distribution指的是π(probabitlty in state)隨著時間增加會趨近於固定，即π=常數，而π=π*P。

要注意的是，limiting distribution和stationary distribution指的涵義是不相同的。

第三，Ergodicity的說明，先看看書上的意思(Fundamentals of Queueing Theory,4th Edition)：Closely associated with the concepts of limiting and stationary distributions is the idea of regodicity, which has to do with the information contained in one infinitely lon sample path of a process.